2

primal problem is: $$\min z = 4x_1-3x_2+5x_3$$

$$7x_1+6x_2+24x_3\le16$$

$$2x_1+5z_2+3x_3\le10$$

$$x_i\ge0$$ the optimal solution is: $(0,2,0), z = -6$

The dual problem is : $$ \max g = 16w_1+10w_2$$

$$7w_1+2w_2\le4$$

$$6w_1+5w_2\le-3$$

$$24w_1+3w_2\le5$$

$$w_1,w_2\le0$$ I get the optimal solution $g=0$ which is wrong because of the duality theorem, $z(opt)=g(opt)$. What's wrong with it? Thanks.

Peter Woolfitt
  • 21,114
kabal
  • 23

2 Answers2

2

The linear program you give as the dual is correct. However, the optimal solution isn't $g=0$, but rather $g=-6$ at $(w_1,w_2)=\left(0,-\frac{3}{5}\right)$.

Notice that $g=0$ isn't a possibility because if $g=0$ then we have $w_1=w_2=0$ which then does not satisfy the constraint $$6w_1+5w_2\le-3$$ You can also notice that this is the only nontrivial constraint in the dual program - the other constraints are satisfied merely by the $w_1,w_2\le 0$ requirement.

Peter Woolfitt
  • 21,114
  • Hi thanks. How do you solve the problem, I tried the II phase method adding an artificial variable to try to get a starting basic feasible solution, but it failed because no basic variable outgoing I've found, but i think I've done some computation errors. – blob Apr 01 '15 at 20:16
  • @blob Sorry, I actually know quite little about linear programming - I solved this question with basic calculus which was easy to do because I only had one nontrivial constraint to deal with. If you want to know about a particular method I might suggest asking another question. – Peter Woolfitt Apr 01 '15 at 22:29
  • I'm wrong with the simplex method because the variable space is $(-infinity,0)$, so the basic feasible solution must be negative. – kabal Apr 03 '15 at 06:14
0

i think this will help you

MIN zx = x1 + 2 x2 subject to - 2 x1 - 4 x2 ≥ -160 x1 - x2 = 30 x1 ≥ 10 and x1,x2≥0;

Since 2nd constraint in the primal is equality, the corresponding dual variable y2 will be unrestricted in sign.

Dual is (Solution stpes of Dual by BigM method)

MAX zy = - 160 y1 + 30 y2 + 10 y3 subject to - 2 y1 + y2 + y3 ≤ 1 - 4 y1 - y2 ≤ 2 and y1,y3≥0;y2 unrestricted in sign

khaled
  • 1