0

Given a generic LP with a single constraint:

maximize $c_1x_1 + c_2x_2 +.... c_nx_n$

such that: $a_1x_1 + a_2x_2 + .... + a_nx_n \le b$

Is there an obvious solution?

I had originally thought this was a simple matter of choosing the largest coefficient (call it $c_i$) in the objective, and setting it to ($b/a_i$) so the constraint is met, but this only guaranteed to work if all the $a$ coefficients in the constraint are equal.

Next approach was to do the simplex algorithm by hand with all the parameters, but the result is ugly, and requires (unwarranted) assumptions along the way about whether some values are greater than others.

Is the answer some obvious ratio that I'm missing?

mips
  • 25

1 Answers1

0

In the following, I will use the dual linear program and the strong duality theorem.

The dual of \begin{align*} \mbox{maximize } & c_1x_1 + c_2x_2 + \dots + c_nx_m\\ \mbox{subject to } & a_1x_1 + a_2x_2 + \dots + a_nx_m \leq b \end{align*} is \begin{align*} \mbox{minimize } & b\lambda \\ \mbox{subject to } & a_1\lambda = c_1\\ & a_2\lambda = c_2\\ &\vdots\\ & a_n\lambda = c_n\\ &\lambda \geq 0\mbox. \end{align*} Let us look at the solutions of the dual system:

i) In the first step, we check whether there is any row with $a_i=0$ and $c_i\neq 0$. Such a row has no valid solution and, hence, the dual system is infeasible.

ii) Otherwise, we proceed with the second step, where we delete all rows that do not constrain the choice of $\lambda$. Theses are all rows for which $a_i=0$ and $c_i=0$.

iii) If after ii) no rows remain, we have found an optimal solution $\lambda=0$ of the dual system and the optimal value is $b\lambda = 0$. Otherwise, in the remaining rows none of the $a_i$ is equal to $0$. Then the system has a solution if and only if $\frac{c_i}{a_i}=\frac{c_j}{a_j} \geq 0$ holds for all $i,j=1,\dots,n$. In this case the optimal value of the dual system is $b\frac{c_i}{a_i}$. Otherwise the dual system is infeasible.

Now, the primal system has an optimal solution if and only if the dual system has an optimal solution, and the optimal values agree. If the dual system is infeasible, then the primal system is feasible, but unbounded. I.e. there exist solutions, but none of them is optimal.

Note, that we can excluded the case that the dual system is unbounded (due to the constraint $\lambda\geq0$). Hence, it follows that the primal system cannot be infeasible, i.e. it always has a (not necessarily optimal) solution.

Willem Hagemann
  • 618