Two forms of duality in linear programming

Question

I do not know much about this subject, but I am trying to learn a little.

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?

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

callculus42 · Answer 1 · 2014-08-18T20:48:22.813

0

You can check out the following table. enter image description here

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)

edited Aug 18 '14 at 20:48

answered Aug 18 '14 at 20:42

callculus42

30,550

Two forms of duality in linear programming

1 Answers1