# Two forms of duality in linear programming

In a book I have it says that a primal problem is:

max $c'X$

subject to

$AX \ge b$

$X \ge 0$

It says that the dual of this is:

maximize $b'Y$

subject to:

$A'y \le c$

$Y \ge 0$

However they did not prove the linear programming duality theorem.

However I found another text where they do this, but there they use that:

max $c'X$

$AX \le b$

Has a dual

min $b'Y$

$A'Y=c$

$y \ge 0$

Notice that in the third last onee I do not have a restriction on X, and in the last one we have an equality not an inequality, are these two representations equal? Is it a way to prove they are?

• Are the links posted here helpful? – user147263 Aug 17 '14 at 21:38
• It's useful to know the general dual problem construction in convex optimization, which is presented in Boyd and Vandenberghe for example. You can use it to derive dual problems for linear programs. – littleO Aug 18 '14 at 21:14

You can check out the following table. If the restrictions have the relation sign $\geq$ in the max-problem, then the dual-variables (min-Problem) has to be $y\leq 0$ (row 8 of the table)
And it should be $A'y\geq c$, because $x \geq 0$ (row 9 of the table)