0
$\begingroup$

There is an LP.
It is already given that $x_1 = 0, x_2 = 1$ is the optimal solution.
First I find the corresponding simplex tableaux. Then what I don't get is how to apply the dual simplex method when you add the constraint $x_1 - x_2 \geq 1$. What I don't understand is described in step 3.
So the steps I did:

Step 1: finding the simplex tableaux that corresponds to the optimal solution $$\begin{align} \text{min} \ z = & \ 2x_1 \ & + & x_2 & & \\ \ & \ \ x_1 \ & + & x_2 & \geq & \ 1\\ \ & \ \ 3x_1 \ & + &2x_2 & \leq & \ 6 \\ \ & \ \ \ & & x_2 \geq 0 & & \ x_2 \geq 0 \\ \end{align} $$

$$\begin{array}{c | c | c c c c c c } \text{basic variables} & \vec{b} & x_1 & x_2 & s_1 & s_2 & x_2^{a} \\ \hline x_2 & 1 & 1 & 1 & -1 & 0 & 1 \\ s_2 & 6 & 3 & 2 & 0 & 1 & 0 \\ \hline -z & 0 & 2 & 1 & 0 & 0 & 0 \\ \end{array}$$

$$\begin{array}{c | c | c c c c c c } \text{basic variables} & \vec{b} & x_1 & x_2 & s_1 & s_2 \\ \hline x_2 & 1 & 1 & 1 & -1 & 0 \\ s_2 & 4 & 1 & 0 & 2 & 1 \\ \hline -z & -1 & 1 & 0 & 1 & 0 \\ \end{array}$$

Step 2: Add the constraint $x_1 - x_2 \geq 1$:

$$\begin{array}{c | c | c c c c c c } \text{basic variables} & \vec{b} & x_1 & x_2 & s_1 & s_2 & s_3 & x_3^{a} \\ \hline x_2 & 1 & 1 & 1 & -1 & 0 & 0 & 0 \\ s_2 & 4 & 1 & 0 & 2 & 1 & 0 & 0 \\ x_3^{a} & 1 & 1 & -1 & 0 & 0 & -1 & 1 \\ \hline -z & -1 & 1 & 0 & 1 & 0 & 0 & 0 \\ \end{array}$$

Express third row in non-basic variables using $ x_2 = 1 - x_1 +s_1$ (row 1). Then:

$$\begin{array}{c | c | c c c c c c } \text{basic variables} & \vec{b} & x_1 & x_2 & s_1 & s_2 & s_3 & x_3^{a} \\ \hline x_2 & 1 & 1 & 1 & -1 & 0 & 0 & 0 \\ s_2 & 4 & 1 & 0 & 2 & 1 & 0 & 0 \\ x_3^{a} & 2 & 2 & 0 & -1 & 0 & -1 & 1 \\ \hline -z & -1 & 1 & 0 & 1 & 0 & 0 & 0 \\ \end{array}$$

Step 3: solve using dual simplex method
All $b_i$ are positive, so then this should be the optimal solution then right?
But $x_3^{a}$ is in the basis. So you want that to be removed right? And if you remove it what pivot should you then choose and why?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.