How to solve this operation research problem using dual simplex method?

Question

Maximize $$ z = 2x_1 -x_2 +x_3$$

Subject to constraints $$2x_1 + 3x_2 -5x_3 \ge 4$$ $$-x_1 +9x_2 -x_3 \ge 3$$ $$4x_1 +6x_2 +3x_3 \le 8$$ And $x_1, x_2, x_3 \ge 0$

I managed to solve this through simplex method(by 2 stage method) but I was asked solve it using dual simplex method, I found out that this cannot be solved by dual simplex since it doesn't meet the maximization optimality condition here which is the reduced costs in the z-row(or the values in the z-row in the initial table) must be always lesser than $0$ which is not the case here as coefficient of $x_2$ is 2 in the z-row.

Still our teacher says it can be solved by introducing another constraint which is $x_1 + x_3 \le M$ (where M is sufficiently large), now I am at a loss how to proceed further ?

I know the answer will be quiet huge and time taking but any type of help will be greatly appreciated.

Answer 1

Find the optimal solution by the dual simplex algorithm

1. Add the artificial constraint $x_1 + x_3 \le M$ to the problem.
2. Write the problem in canonical form.
3. Add a slack variable to each inequality.
4. Write a simplex tableau for the problem. \begin{equation*} \begin{array}{lrrrl} \max & z = 2 x_1 & - x_2 & + x_3 & \\ \text{s.t.} & - 2 x_1 & - 3 x_2 & + 5 x_3 & \le - 4 \\ & x_1 & - 9 x_2 & + x_3 & \le - 3 \\ & 4 x_1 & + 6 x_2 & + 3 x_3 & \le 8 \\ & x_1 & & + x_3 & \le M \end{array} \\ x_1, x_2, x_3 \ge 0 \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & -2 & -3 & -5 & 1 & 0 & 0 & 0 & -4 \\ x_5 & 1 & -9 & 1 & 0 & 1 & 0 & 0 & -3 \\ x_6 & 4 & 6 & 3 & 0 & 0 & 1 & 0 & 8 \\ x_7 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & -2 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \end{array} \end{equation*} Perform a pivot operation using $y_{7?}$ as a pivot to make all entries in the last row positive. \begin{equation*} \begin{array}{rrrrrrrr|l} x_7 & \color{red}{1} & 0 & \color{red}{1} & 0 & 0 & 0 & 1 & M \\ \hline & \color{red}{-2} & 1 & \color{red}{-1} & 0 & 0 & 0 & 0 & 0 \\ \text{ratio} & \color{red}{2/1=2} & & \color{red}{1/1=1} & & & & & \end{array} \end{equation*} Here, we should choose the maximum ratio. Therefore, we choose $y_{71}$ as a pivot element in the initial tableau. \begin{equation*} \begin{array}{rrrrrrrr|l} x_7 & 1^* & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & -2 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \end{equation*} We apply the dual simplex algorithm to the following tableau. \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & -3 & 7 & 1 & 0 & 0 & 2 & 2M -4 \\ x_5 & 0 & -9 & 0 & 0 & 1 & 0 & -1 & -M -3 \\ x_6 & 0 & 6 & -1 & 0 & 0 & 1 & -4^* & -4M +8 \\ x_1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & 0 & 1 & 1 & 0 & 0 & 0 & 2 & 2M \\ \text{ratio} & & & 1 & & & & 1/2 & \end{array} \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & 0 & 13/2 & 1 & 0 & 1/2 & 0 & 0 \\ x_5 & 0 & -21/2^* & 1/4 & 0 & 1 & -1/4 & 0 & -5 \\ x_7 & 0 & -3/2 & 1/4 & 0 & 0 & -1/4 & 1 & M -2 \\ x_1 & 1 & 3/2 & 3/4 & 0 & 0 & 1/4 & 0 & 2 \\ \hline & 0 & 4 & 1/2 & 0 & 0 & 1/2 & 0 & 4 \\ \text{ratio} & & 8/21 & & & & 2 & & \end{array} \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & 0 & 13/2 & 1 & 0 & 1/2 & 0 & 0 \\ x_2 & 0 & 1 & -1/42 & 0 & -2/21 & 1/42 & 0 & 10/21 \\ x_7 & 0 & 0 & 3/14 & 0 & -1/7 & -3/14 & 1 & M-9/7 \\ x_1 & 1 & 0 & 11/14 & 0 & 1/7 & 3/14 & 0 & 9/7 \\ \hline & 0 & 0 & 25/42 & 0 & 8/21 & 17/42 & 0 & 44/21 \end{array} \end{equation*} Hence, the optimal solution of the primal problem is $(\dfrac97,\dfrac{10}{21},0)^T$, with an optimal value of $\dfrac{44}{21}$.

Find the optimal solution by GNU Octave

I post the Octave code for you to verify the optimal solution shown above.

octave:1> c = [2 -1 3]';
octave:2> A = [2 3 -5; -1 9 -1; 4 6 3];
octave:3> b = [4 3 8]';
octave:4> [x_max,z_max] = glpk(c,A,b,[0,0,0]',[],"UUL","CCC")
x_max =

   1.28571
   0.47619
   0.00000

z_max =  2.0952