1
$\begingroup$

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ $$2x_{1}-2x_{2}-6x_{3}\le -4$$

so first I turned the problem into a maximization by multiplying z by -1 and all of the coefficients on the right hand side of my constraints must be non negative so I multiplied the 3rd constraint by -1

Maximize: $$z=-12x_{1}+-4x_{2}-2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ $$-2x_{1}+2x_{2}+6x_{3}\ge 4$$

then I changed all inequalities into equations by adding surplus and artificial variables and added the new variables to the objective function

Maximize: $$z=-12x_{1}+-4x_{2}-2x_{3}+0x_4-Mx_5+0x_6-Mx_7$$ **Constraints:**$$-6x_{1}+3x_{2}-x_4+x_5= 9$$ $$-2x_{1}+2x_{2}+6x_{3}-x_6+x_7=4$$

then I constructed my tableau, sorry for the formatting there doesn't seem to be a good way to set up tableau

$$x_1\; x_2\; x_3\; x_4\; x_5\; x_6\; x_7$$ $$12 \; 4 \; 2 \; 0 \; M \; 0 \; M $$ $$x_7\; -M\; -2\; 2\; 6\; 0\; 0\; -1\; 1\; 4$$ $$x_5 \; -M \; -6 \; 3 \; 0 \; -1 \; 1 \; 0\; 0\; 9$$ $$12+8M\; 4-5M\; 2-6M\; -M\; 0\; M\; 0\; -13M$$

I get a little confused trying to find my pivot column with the M's but using the fact the M is a large positive number I supplemented 1000 for each M and determined the 2-6M must be the most negative value in the last row making $x_3$ my pivot column

then dividing the coefficients of the last row by the coefficients of the pivot column i determined that the smallest $9/0 = 0 \; \; \;4/6=2/3$ so $x_7$ must be my pivot row and 6 is my pivot

Then I created my new tableau by dividing the pivot row by the pivot, leaving $x_5$ unchanged since the coefficient is already 0 and (-2+6M)(new $x_3$ row) and adding it to the last row to make my new last row $$x_1\; x_2\; x_3\; x_4\; x_5\; x_6\; x_7$$ $$x_5\; -6\; 3\; 0\; -1\; 1\; 0\; 0\; 9$$ $$x_3\; \frac{-1}{3}\; \frac13\; 1\; 0\; 0\; \frac{-1}{6}\; \frac16\; \frac23$$ $$(\frac{38}{3}+6M) \; (\frac{34}{3} +10M)\; 0\; -M\; 0\; \frac 13 \; (\frac{-1}{3}+M)\; (\frac{-4}{3}-9M)$$

Now obviously there is still a negative in my last row with -M in $x_4$ so this should be my new pivot column but to find the pivot row one coefficient is -1 and one 0. I can't use a negative and I don't think I can use 0 since then my entire pivot row would be divided by 0 so I am stuck.

This would lead me to believing no solution but the problem makes it seem like there should be a solution. What am I doing wrong? And what does it mean by find the solution of the dual?

$\endgroup$
1
$\begingroup$

Using the Maple I am obtaining

$$[ 12.0,[x_{{1}}= 0.0,x_{{2}}= 3.0,x_{{3}}= 0.0]]$$

Using Z3opt I am obtaining the same result

(+ (* 12 x1) (* 4 x2) (* 2 x3)) |-> 12 
sat 
(model 
  (define-fun x3 () Int 0) 
  (define-fun x2 () Int 3) 
  (define-fun x1 () Int 0) 
)

Please run the code online here

$\endgroup$
  • $\begingroup$ thank you for figuring that out. I'm still not sure how to get there tho using tabeau's by hand. Any ideas what i'm doing wrong? $\endgroup$ – Mikky Davey Sep 23 '14 at 2:22

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.