Optimal Solution for Linear Programming Problem

[evinda]

Hello! (Wave)
I want to find the optimal solution using the simplex method of the following linear programming problem:

$$ \max (-x_1+2x_2-3x_3) \\ x_1-x_2+x_3+2x_4=10 \\ 2x_2-x_3 \leq 1 \\ x_2+ 2x_4 \leq 8 \\ x_i \geq 0, i=1,2,3,4$$

$A=\begin{bmatrix}
1 & -1 & 1 & 2 & 0 & 0\\
0 & 2 & -1 & 0 & 1 & 0\\
0 & 1 & 0 & 2 & 0 & 1
\end{bmatrix}$

A basic feasible non degenerate solution is $(10,0,0,0,1,8)$.

$\begin{bmatrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta & \\
P_1 & -1 & 10 & 1 & -1 & 1 & 2 & 0 & 0 & - & L_1\\
P_5 & 0 & 1 & 0 & 2 & -1 & 0 & 1 & 0 & \frac{1}{2} & L_2\\
P_6 & 0 & 8 & 0 & 1 & 0 & 2 & 0 & 1 & \frac{8}{1} & L_3 \\
& z & 0 & 1 & -2 & 3 & 0 & 0 & 0 & & L_4
\end{bmatrix}$Since $z_2-c_2<0$, $P_2$ will get in the basis and $P_5$ gets out of the basis.

So we get the following tableau:$\begin{bmatrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta & \\
P_1 & -1 & \frac{21}{2} & 1 & 0 & \frac{1}{2} & 2 & \frac{1}{2} & 0 & & L_1'=L_1+L_2'\\
P_2 & 2 & \frac{1}{2} & 0 & 1 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2'=\frac{L_2}{2}\\
P_6 & 0 & \frac{15}{2} & 0 & 0 & \frac{1}{2} & 2 & -\frac{1}{2} & 1 & & L_3'=L_3-L_2' \\
& z & 1 & 1 & 0 & 2 & 0 & 1 & 0 & & L_4'=L_4+2L_2'
\end{bmatrix}$

Thus , $-\frac{19}{2}$ is the optimal solution and is achieved at the vertex $\left( \frac{21}{2}, \frac{1}{2}, 0,0, ,0, \frac{15}{2}\right)$.

Is it right or have I done something wrong? (Thinking)

 

[I like Serena]

Hey evinda! (Smile)

It looks fine to me. (Mmm)

 

[evinda]

Hey evinda! (Smile)

It looks fine to me. (Mmm)

Nice! What does the bottom row mean in this case and specifically the 1 next to z? (Thinking)

 

[I like Serena]

Nice! What does the bottom row mean in this case and specifically the 1 next to z? (Thinking)

The original objective function is:
$$z=-x_1+2x_3-3x_3= -\frac {21} 2 + 2\cdot \frac 12 = -\frac {19}2$$
It is inserted into the original tableau as:
$$z+x_1-2x_2+3x_3 = 0$$
After the transformations it is:
$$z+x_1+2x_3+x_5=1 \Rightarrow z = 1 - x_1 -2x_3-x_5 = 1 - \frac {21}2 = -\frac{19}2$$
The $1$ next to the $z$ corresponds with the right hand side, just like it does for the other equations. (Mmm)

 

[evinda]

The original objective function is:
$$z=-x_1+2x_3-3x_3= -\frac {21} 2 + 2\cdot \frac 12 = -\frac {19}2$$
It is inserted into the original tableau as:
$$z+x_1-2x_2+3x_3 = 0$$
After the transformations it is:
$$z+x_1+2x_3+x_5=1 \Rightarrow z = 1 - x_1 -2x_3-x_5 = 1 - \frac {21}2 = -\frac{19}2$$
The $1$ next to the $z$ corresponds with the right hand side, just like it does for the other equations. (Mmm)

I see... Thanks a lot! (Nod)