# Linear programming duality theorem

As far as I know, there are 2 versions of this theorem:

1) $\max \{xc^T: xA \le b, x \ge 0, x \in R^n\} = \min \{by^T: Ay^T \ge c^T, y \ge 0, y \in R^m\}$

2) $\max \{xc^T: xA \ge b, x \in R^n\} = \min \{by^T: Ay^T = c^T, y \le 0, y \in R^m\}$

Can someone show me how 1) => 2)? It just seems very bizarre to me. I've searched for a transformation but can't seem to find one.

• – Mike Spivey Mar 4 '13 at 4:55

http://www.me.utexas.edu/~jensen/ORMM/supplements/methods/lpmethod/S3_dual.pdf. This link provides the transformation, the trick apparently is to replace the constraint $Ay^T = c^T$ by two inequalities $Ay^T \ge c^T$ and $-Ay^T \ge -c^T$. This is confirmed in the following link as well. http://www.econ.ucsd.edu/~jsobel/172aw02/notes5.pdf