# Standard Form of linear programming

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.

• You can't. Missing are the bounds $x\ge 0$. – 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?
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.
• What if $Ax = b$ has only one solution, in that case, the optimal solution is also that point – MAh2014 Oct 7 '19 at 4:10
• 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. – MAh2014 Oct 7 '19 at 13:46