Standard Form of linear programming

convex optimizationlinear 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.

Best Answer

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.