Convert the standard Linear Programming where $\mathbf{A}\in\mathbb{R}^{m\times n} $ and $x\in\mathbb{R}^n$ $$\min \mathbf{c}^T\mathbf{x}\\ s.t\;\;\;\;\;\;\;\mathbf{Ax}=\mathbf{b}\\ \;\;\;\;\;\;\;\;\;\;\mathbf{x}\geq 0 $$ The question wants to convert the above LP in the form of $$\min \mathbf{d}^T\mathbf{y}\\ s.t.\;\;\;\;\;\;\;\mathbf{Gy}\leq \mathbf{h}\\ \;\;\;\;\;\;\;\;\;\;\mathbf{y}\in\mathbb{R}^{n-m}$$ where $\mathbf{G,h,d}$ should be expressed in terms of $\mathbf{A,b,c}$. Could someone enlighten me how to start? I am thinking along the line of converting back to auxilliary LP but it does not work.
Asked
Active
Viewed 34 times
0
-
I understand dual LP can solve it when $n\geq 2m$ but I am stuck with the case where $n<2m$. – user122049 Mar 06 '18 at 04:49
-
@copper.hat I am well aware of that but the constraint is that $\mathbf{y}$ has $n-m$ dimensions which is fewer than $\mathbf{x}$, which has $n$. – user122049 Mar 06 '18 at 04:54
-
2Perhaps you could express ${x | Ax = b }$ as ${x_0 + L y}$? – copper.hat Mar 06 '18 at 04:58