i have an optimization problem

$$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$

the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ (the slack variable)

consequently, the dual problem becomes :

$$\text{ minimize } 450a+600b$$ $$ \text{ such that } a+2b ≥ 3 \text{ and }a+b ≥ 4;$$

the optimal solution of dual becomes $a=4$; $b=0$; $c=1$ (surplus variable)

my doubt is that when i apply the strong duality theorem on the primal solution, i'm unable to get the dual solution. that is:

(C transpose) multiplied by (b inverse) $C^Tb^{-1}$= {4,0}*{{1,0},{-1,1}}={4,0} which is not correct since we should get the dual solution. where am i going wrong?

  • $\begingroup$ Should the primal problem not have two slack variables? Are there any positivity conditions? $\endgroup$ – Lutz Lehmann Feb 22 '14 at 16:27
  • $\begingroup$ the first slack variable in primal comes to be zero. and the second surplus variable in dual also becomes zero. yes, the variables x,y,a,b are all non-negative $\endgroup$ – mathlover Feb 22 '14 at 17:03
  • $\begingroup$ I do not understand your problem. The strong duality theorem holds as the primal and dual optimal solution coincide. $\endgroup$ – guanglei Jan 1 '17 at 11:21

In the primal, for that solution, you need non-negativity constraints on $x$ and $y$.

So, the primal is: $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ $$x,y\geq0$$

which is equivalent to:

$$\text{ minimize } z=-3x-4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ $$x,y\geq0$$

Which gives the answer $(x,y)=(0,450)$ and a primal optimal solution value of $-1800$.

Now, the dual becomes:

$$\text{ maximize } 450a+600b$$ $$ \text{ such that } a+2b \leq -3 \text{ and }a+b \leq -4;$$ $$a,b\leq0$$

Which when solved gives the answer $(a,b)=(-4,0)$ which leads to optimal dual value of $-1800$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.