1

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?

Michael Hardy
  • 1
Sudipta Roy
  • 779
  • So in a sense you are trying to solve the related linear problem. If you are the optimizer which direction is most profitable to explore? – gt6989b Feb 08 '16 at 16:36
  • Yes, this is a linear programme. But I could not understand your question. Would you give an example to explain it? – Sudipta Roy Feb 08 '16 at 16:44
  • Is there a constraint on $c_i$, such as the one on $a_i$ and $b$? – vnd Feb 08 '16 at 18:49

1 Answers1

1

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.

Kuifje
  • 9,584