simplex M-method minimization problem

Question

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?

Answer 1

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