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?
Best Answer
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$.