How can we prove that all linear programming problem cannot be converted to the form below: \begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to}& A x = b \\ \end{array} I think we need to come up with an example that cannot be converted to this form, but I can't figure out how to mathematically define "not being able to be converted to that form". suppose we have an LP in the standard form whose answer would be $x$ if there is a function $f(x) $ that can convert x to an answer of a problem of the above form then these two problems are equivalent, but $f$ can be any function so this definition is not very helpful.

  • 2
    $\begingroup$ You can't. Missing are the bounds $x\ge 0$. $\endgroup$ – Erwin Kalvelagen Oct 7 '19 at 7:04

Hint: If $\ x_1\ $ and $\ x_2\ $ are any feasible solutions with $\ c^Tx_1 \ne c^Tx_2\ $, can you show that $\ x_t = (1-t)x_1 + tx_2\ $ is a feasible solution for any real $\ t\ $? Using $\ x_t\ $, can you determine what must be the range of values the objective function takes over the set of feasible solutions? Can you find a linear program whose objective function is not constant, but has a different range over its set of feasible solutions?

Clarification: The OP has correctly pointed out in the comments below that, under a sufficiently loose interpretation of what it means to "convert" one linear program to another, it would be true that any linear program could be "converted" to one of the given form.

In the above hints, I was assuming that "conversion" of one linear program $P_1$ with objective $\ c_1^Tx\ $ to another, $P_2$ with objective $\ c_2^Ty\ $, meant that there would be a surjective mapping $\ \varphi\ $ from the feasible solutions of $P_2$ onto those of $P_1$ such that $\ c_1^T\varphi(y)=c_2^Ty\ $ for all feasible solutions $\ y\ $ of $P_2$. Under this interpretation of "conversion" it is true that not all linear programs can be converted to the given form.

  • $\begingroup$ What if $ Ax = b $ has only one solution, in that case, the optimal solution is also that point $\endgroup$ – MAh2014 Oct 7 '19 at 4:10
  • $\begingroup$ Unless I'm misunderstanding your question that's irrelevant. Obviously some linear programs can be written in the given form, so I was presuming you wanted to show that not all linear programs can be. To do that, all you have to do is find just one linear program that can't be written in that form. My hint outlines a strategy for finding such a one. $\endgroup$ – lonza leggiera Oct 7 '19 at 5:52
  • $\begingroup$ Thank you for your hint. I understood the clue, but I thought maybe if there is a problem with that form whose optimal solution is $y$ if and only if $f(y) = x$ is the solution of a special LP in the standard form, then we can say that this problem can be transformed to that form. $\endgroup$ – MAh2014 Oct 7 '19 at 13:46
  • $\begingroup$ Ah, I see your point. Yes, if all you require of being "converted to that form" is that the converted form have the same optimal solution as the original (or no optimal solution if the original has no optimal solution) then it would be true that any linear program could be "converted to" the given form. However, I don't think that's a very useful interpretation of what "converted to" should mean, or is likely to be what anyone using that expression would mean. I'll add a clarification to my answer. $\endgroup$ – lonza leggiera Oct 7 '19 at 22:41
  • $\begingroup$ Thank you for the clarification, I marked it as the answer. $\endgroup$ – MAh2014 Oct 8 '19 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.