1

I am learning about Linear Programming right now.. I learned that we can use simplex to solve linear program and I also learned that every linear problem has a dual problem because of duality.. I am so confused now.. Since we can use simplex algorithm to solve Primal LP(get max or min), why should we transform Primal LP to Dual LP? I mean for what purpose, we should transform Primal LP to dual LP?

ZonghanXU
  • 111

1 Answers1

0

PRIMAL: $$ \mbox{MAX } c x; \; x \geq 0, \; A x \leq b. $$

DUAL $$ \mbox{MIN } y b; \; y \geq 0, \; y A \geq c. $$

With $c,y$ row vectors and all entries of $y$ non-negative, written $y \geq 0,$ and with $b,x$ row vectors and all entries of $x$ non-negative, written $x \geq 0,$ with $Ax \leq b$ and $yA \geq c,$ WEAK DUALITY is nothing more than this: $$\color{magenta}{ c x \leq y A x \leq y b.} $$ I wish people would tell me these things.

So weak duality is nothing more than associativity of matrix multiplication and the fact that all entries of the column vector $x$ and the row vector $y$ are required to be non-negative.

Strong duality is the fact that, if both problems are feasible, the optimal values of the objective functions ($cx, yb$) are the same. I will see if I can find a one-line proof of that. But it may be more difficult.

In the end, I suspect the dual problem is for sensitivity analysis: what happens if some of the entries in $A$ or $b$ or $c$ are changed a little? This is a reasonable question; all of this is done on computer, and everything is a decimal (well, binary) approximation.

Will Jagy
  • 139,541
  • Maybe you misunderstood what I asked? What I ask is since simplex algorithm can help us get the min or max value, I cannot see when or why we should transform Primal LP to Dual LP? This transformation does not help us get the min or max value. This job is done by simplex.. – ZonghanXU Oct 28 '13 at 03:54
  • I do not really understand what you asked. However, you seemed upset. – Will Jagy Oct 28 '13 at 03:59
  • ,haha a little.. What I ask is suppose you transform max problem to min problem, you just transform one problem to another instead of solving this problem, right? To really get the max value , you still need Simplex to solve. So why do we need this transformation? – ZonghanXU Oct 28 '13 at 04:08
  • @ZonghanXU, I've been reading some answers by experts...I would say that there is probably nothing I can describe to an undergraduate that will seem to be an advantage. However, it is not possible to prove that the simplex method converges without it. So, be patient, you are learning how to do some difficult things for which you will not yet understand the justification. That is learning. – Will Jagy Oct 28 '13 at 04:21
  • Maybe you can give me the link to show why we need this transformation? – ZonghanXU Oct 28 '13 at 04:40
  • @ZonghanXU, look on the right side of this web page, it should say "Related" and give links to about 10 related questions. – Will Jagy Oct 28 '13 at 04:42