I am doing some practice problems and am unsure how to proceed with the following proof:
Let $A$ be an $m \times n$ matrix with $A \geq 0$ and each column of $A$ has a non-zero positive entry. Let $b \geq 0$. Then show that the LP $$ \max \mathbf{c} \cdot \mathbf{x}$$ $$A\mathbf{x} \leq \mathbf{b}$$ $$\mathbf{x} \geq 0$$ always has an optimal solution.
I would greatly appreciate any help on this question if possible.
Thank you
Let the feasible set be $P$.
$0 \in P$, hence it is non-empty.
$\forall j \in \left\{1, \ldots, n \right\}$, $\exists i \in \left\{1, \ldots, m \right\}$such that $a_{ij} > 0$
Since $A \geq 0$, $x \geq 0$, and $$\sum_{j'=1}^n a_{ij'}x_{j'} \leq b_i$$
We have $a_{ij}x_j \leq b_i$ and hence $x_j \leq \frac{b_i}{a_{ij}}$.
Hence $x$ is bounded.
Hence this is a linear optimization problem over a non-empty, closed and bounded set. Hence the optimal value can be attained.
