minimum possible value of a linear function of n variables Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint 
$a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$.
Then the minimum possible value of the expression  $c_1x_1 + \cdots + c_nx_n$ is $c_i\cdot b/a_i$ where $i$ denotes the index for which
the ratio $c_i/a_i$ is minimum. How to prove this fact?
 A: If you are familiar with the simplex algorithm, it provides a quite straightforward proof. 
Assume you have a feasible solution $x_j = \frac{b}{a_j}$, $x_{\ell}=0$ for each $\ell \neq j$. The current objective function equals $z=c_{j}\frac{b}{a_{j}}$.
The reduced costs of variables $x_{\ell}$ are $c_{\ell}-\frac{a_{\ell}}{a_j}c_j$, choosing the variable with the most negative reduced cost will give you the entering variable, say $x_i$. The leaving variable test requires you to select the variable with minimum value $\frac{b/a_{j}}{a_i/a_j}=\frac{b}{a_i}$. This gives you the minimum value that variable $x_i$ can take in order for the problem to remain feasible. 
So you select variable $x_i$, and the objective function decreases by $(c_{i}-\frac{a_{i}}{a_j}c_j)\frac{b}{a_i}$, which yields 
$$
z=c_{i}\frac{b}{a_{i}}.
$$
Now you have two possibilities: either the solution is optimal and you are done, either there is another variable with a negative reduced cost, and you repeat the exact steps. In all cases, you will end with the statement you are trying to prove.
