MHB How to Determine \( z_k - c_k \) Values in Simplex Method?

[evinda]

Hello! (Wave)

I want to solve the following linear programming problem:

$$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 \}$$

$\begin{bmatrix}
1 & 1 & 7 & 2 & | & 3\\
-2 & -1 & 3 & 3 & | & 2\\
2 & 2 & 8 & 1 & | & 4
\end{bmatrix} \to \begin{bmatrix}
1 & 1 & 7 & 2 & | & 3\\
0 & 1 & 17 & 7 & | & 8\\
0 & 0 & 6 & 3 & | & 2
\end{bmatrix}$

So the problem is written equivalently as follows:

$$-\max (-5y_1+10y_2-7y_3+3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ y_2+17y_3+7y_4=8 \\ 6y_3+3y_4=2 \\ y_i \geq 0, i \in \{ 1, \dots, 4 \}$$But we want the $3 \times 3$ identity matrix to appear at the matrix that represents the linear programming problem, right?

So we solve the following problem, right?$$-\max (-5y_1+10y_2-7y_3+3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ y_2+17y_3+7y_4+y_5=8 \\ 6y_3+3y_4+y_6=2 \\ y_i \geq 0, i \in \{ 1, \dots,6 \}$$Then:

$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_5 & \theta & \\
P_1 & -5 & 3 & 1 & 1 & 7 & 2 & 0 & 0 & \frac{3}{7} &L_1 \\
P_5 & 0 & 8 & 0 & 1 & 17 & 7 & 1 & 0 & \frac{8}{17} & L_2\\
P_6 & 0 & 2 & 0 & 0 & 6 & 3 & 0 &1 & \frac{1}{3} &L_3 \\
& z & 0 & -5 & 10 & -7 & 3 & 0 & 0 & & L_4
\end{matrix}$

$|-7|> |-5|$ so $P_3$ gets in the basis and $P_6$ gets out of the basis.

Then we get the following tableau:

$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_5 & \theta & \\
P_1 & -5 & \frac{2}{3} & 1 & 1 & 0 & -\frac{3}{2} & 0 & -\frac{7}{6} & &L_1'=L_1-7L_3' \\
P_5 & 0 & \frac{7}{3} & 0 & 1 & 0 & -\frac{3}{2} & 1 & -\frac{17}{6} & & L_2'=L_2-17L_3'\\
P_3 & -7 & \frac{1}{3} & 0 & 0 & 1 & \frac{1}{2} & 0 &\frac{1}{6} & &L_3'=\frac{L_3}{6} \\
& z & \frac{7}{3} & -5 & 10 & 0 & \frac{13}{2} & 0 & \frac76 & & L_4'=L_4+7L_3'
\end{matrix}$Have I maybe done something wrong? Because from the last tableau we get that $P_1$ gets out of the basis and $P_1$ gets in the basis... (Tmi)

 

[I like Serena]

Hey evinda! (Smile)

I see that you introduced $x_5$ and $x_6$.
But aren't the corresponding equations equalities instead of inequalities? (Wondering)

Have I maybe done something wrong? Because from the last tableau we get that $P_1$ gets out of the basis and $P_1$ gets in the basis... (Tmi)

I didn't check your calculations, but I think $P_1$ isn't properly in the basis yet.
We should still do $L_4'' = L_4 + 5L_1'$. (Nerd)

 

[evinda]

Hey evinda! (Smile)

I see that you introduced $x_5$ and $x_6$.
But aren't the corresponding equations equalities instead of inequalities? (Wondering)

I thought that we have to use artificial variables... Is there an other way to solve the problem without introducing other variables? (Thinking)

I didn't check your calculations, but I think $P_1$ isn't properly in the basis yet.
We should still do $L_4'' = L_4 + 5L_1'$. (Nerd)

But what column do we then remove now that we can't use $\theta$ ? (Thinking)

 

[I like Serena]

I thought that we have to use artificial variables... Is there an other way to solve the problem without introducing other variables? (Thinking)

We only introduce artificial variables for inequalities.
That's to turn them into equalities.
So if we have for instance $x_1+ 2x_2 \le 5$, we turn it into $x_1+2x_2 + x_3 = 5$.
But if we already have an equality, like $x_1+ 2x_2 = 5$, there's nothing to do. (Nerd)

But what column do we then remove now that we can't use $\theta$ ? (Thinking)

First we have to have a basis before we can (or should) move from basis to basis.
$P_1$ is not in the basis yet, since its column still has a non-zero entry in the bottom row. (Nerd)

 

[evinda]

Then we have this matrix:
$ \begin{bmatrix}
1 & 1 & 7 & 2 & | & 3\\
0 & 1 & 17 & 7 & | & 8\\
0 & 0 & 6 & 3 & | & 2
\end{bmatrix}$How can we find the basic variables given that the identity matrix doesn't appear? (Thinking)

 

[I like Serena]

Then we have this matrix:
$ \begin{bmatrix}
1 & 1 & 7 & 2 & | & 3\\
0 & 1 & 17 & 7 & | & 8\\
0 & 0 & 6 & 3 & | & 2
\end{bmatrix}$

How can we find the basic variables given that the identity matrix doesn't appear? (Thinking)

There are no basic variables until we create them.
To create a basic variable, we need a column that contains only a single non-zero entry.
We have to do row-reductions to achieve that. (Nerd)

 

[evinda]

There are no basic variables until we create them.
To create a basic variable, we need a column that contains only a single non-zero entry.
We have to do row-reductions to achieve that. (Nerd)

I see... But what else could we do expect from the operations that I have already done? (Thinking)

 

[I like Serena]

$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_5 & \theta & \\
P_1 & -5 & \frac{2}{3} & 1 & 1 & 0 & -\frac{3}{2} & 0 & -\frac{7}{6} & &L_1'=L_1-7L_3' \\
P_5 & 0 & \frac{7}{3} & 0 & 1 & 0 & -\frac{3}{2} & 1 & -\frac{17}{6} & & L_2'=L_2-17L_3'\\
P_3 & -7 & \frac{1}{3} & 0 & 0 & 1 & \frac{1}{2} & 0 &\frac{1}{6} & &L_3'=\frac{L_3}{6} \\
& z & \frac{7}{3} & -5 & 10 & 0 & \frac{13}{2} & 0 & \frac76 & & L_4'=L_4+7L_3'
\end{matrix}$

Have I maybe done something wrong? Because from the last tableau we get that $P_1$ gets out of the basis and $P_1$ gets in the basis... (Tmi)

I see... But what else could we do expect from the operations that I have already done? (Thinking)

You turned $P_3$ and $P_5$ into basic variables, but you did not finish with $P_1$ yet. (Smirk)

 

[evinda]

You turned $P_3$ and $P_5$ into basic variables, but you did not finish with $P_1$ yet. (Smirk)

So without the artificial variables which were wrong we have the following tableau, right?$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & \theta & & \\
P_1 & 5 & 3 & 1 & 1 & 7 & 2 & & &L_1 \\
& & 8 & 0 & 1 & 17 & 7 & & & L_2\\
& & 2 & 0 & 0 & 6 & 3 & & & L_3 \\
& z & 0 & -5 & 10 & -7 & 3 & & & L_4
\end{matrix}$So $P_1$ is already in the basis, isn't it? So now we can pick $P_3$ to get in the basis. Or am I wrong? (Thinking)

 

[I like Serena]

So without the artificial variables which were wrong we have the following tableau, right?$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & \theta & & \\
P_1 & 5 & 3 & 1 & 1 & 7 & 2 & & &L_1 \\
& & 8 & 0 & 1 & 17 & 7 & & & L_2\\
& & 2 & 0 & 0 & 6 & 3 & & & L_3 \\
& z & 0 & -5 & 10 & -7 & 3 & & & L_4
\end{matrix}$So $P_1$ is already in the basis, isn't it? So now we can pick $P_3$ to get in the basis. Or am I wrong? (Thinking)

Just looked it up and according to wiki $P_1$ is already called a basic variable.
Still, to properly find the optimized solution, we should still zero out the $-5$ in the bottom row. (Thinking)

 

[evinda]

Just looked it up, and according to wiki $P_1$ is already called a basic variable .
Still, to properly find the optimized solution, we should still zero out the $-5$ in the bottom row. (Thinking)

Could you explain it further to me why we have to zero out the $-5$ in the bottom row? (Thinking)

 

[I like Serena]

Could you explain it further to me why we have to zero out the $-5$ in the bottom row? (Thinking)

To find the optimal solution, we need to eliminate all negative entries from the bottom row.
As it is now, $x_1$ still gives a contribution that ensures that the objective function will not attain its maximum. (Nerd)

 

[evinda]

To find the optimal solution, we need to eliminate all negative entries from the bottom row.
As it is now, $x_1$ still gives a contribution that ensures that the objective function will not attain its maximum. (Nerd)

So now do we try to find simultaneously both the basic variables and the optimal solution? (Thinking)

Also what can we do so that $P_3$ gets in the basis? Now we cannot use the pivot since we just have one column in the basis... (Sweating)

 

[I like Serena]

So now do we try to find simultaneously both the basic variables and the optimal solution? (Thinking)

Also what can we do so that $P_3$ gets in the basis? Now we cannot use the pivot since we just have one column in the basis... (Sweating)

What do you mean that we cannot use the pivot, or that we cannot get $P_3$ in the basis?

 

[evinda]

What do you mean that we cannot use the pivot, or that we cannot get $P_3$ in the basis?

We can't use the procedure we use when we apply the simlex method, where we use $\theta$ to determine which column gets in the basis and then we divide the line at which the pivot is by the pivot and so on...

 

[I like Serena]

We can't use the procedure we use when we apply the simlex method, where we use $\theta$ to determine which column gets in the basis and then we divide the line at which the pivot is by the pivot and so on...

How do you use $\theta$ to determine the column? (Wondering)

I thought we were selecting the column based on a negative entry in the bottom row. (Thinking)

 

[evinda]

How do you use $\theta$ to determine the column? (Wondering)

We are looking for the smallest value of $\theta$ and the column of the basis that corresponds to this row gets out of the basis, or not? (Thinking)

I thought we were selecting the column based on a negative entry in the bottom row. (Thinking)

Yes, the column $P_j$ such that $|z_j-c_j|= \max \{ |z_k-c_k|: z_k-c_k<0\}$ gets in the basis.

- - - Updated - - -

Yes, the column $P_j$ such that $|z_j-c_j|= \max \{ |z_k-c_k|: z_k-c_k<0\}$ gets in the basis.

So in this case we apply this and simultaneously find the basic variables, right? (Thinking)

 

[I like Serena]

We are looking for the smallest value of $\theta$ and the column of the basis that corresponds to this row gets out of the basis, or not? (Thinking)

Yes, the column $P_j$ such that $|z_j-c_j|= \max \{ |z_k-c_k|: z_k-c_k<0\}$ gets in the basis.

So in this case we apply this and simultaneously find the basic variables, right? (Thinking)

Right. (Nod)
More specifically, first we select the column based on a negative entry in the bottom row.
And then we select the row based on the corresponding values of $\theta$. (Nerd)

In this case we would select the column $P_1$.
And we would select the top row, which is the only possibility.
And indeed, $P_1$ is already in the basis, and it stays in the basis - there is no change in the basis.
However, we still need to eliminate the $-5$ in the bottom row.
Then we can see if there will be a new negative entry. (Thinking)

 

[evinda]

The initial matrix was this: $\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
& & 3 & 1 & 1 & 7 & 2 & & L_1 \\
& & 2 & -2 & -1 & 3 & 3 & & L_2\\
& & 4 & 2 & 2 & 8 & 1 & & L_3\\
& z & 0 & -5 & 10 & -7 & 3 & & L_4
\end{matrix}$

Since $|-7|> |-5|$ don't we have to put firstly $P_3$ in the basis? (Thinking)

 

[I like Serena]

Sure.

 

[evinda]

Sure.

So now do we do whatever possible operations to get $\begin{bmatrix}
1\\
0\\
0
\end{bmatrix}$ at the column $P_3$?

For example $L_1'=L_1-2L_2, L_2'=L_2-3L_1'$ ? (Thinking)

 

[evinda]

I think that we have to use the the two-phase method.

We introduce artificial variables:

$$- \max (-5x_1+10x_2-7x_3+3x_4) \\ x_1+x_2+7x_3+2x_4+x_5=3 \\ -2x_1-x_2+3x_3+3x_4+x_6=2 \\ 2x_1+2x_2+8x_3+x_4+x_7=4 \\ x_i \geq 0, i=1,2, \dots, 7$$

At the first phase, we solve the linear programming problem $\min (x_5+x_6+x_7)$ under the new restrictions and at the second phase the initial problem, for which we will have found from the first phase a basic feasible solution.
Then I thought that the initial simplex tableau of the first phase would be the following:$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\
P_5 & -1 & 3 & 1 & 1 & 7 & 2 & 1 & 0 & 0 & & L_1\\
P_6 & -1 & 2 & -2 & -1 & 3 & 3 & 0 & 1 & 0 & & L_2\\
P_7 & -1 & 4 & 2 & 2 & 8 & 1 & 0 & 0 & 1 & & L_3\\
& z & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & & L_4
\end{matrix}$But I found that the following is the initial tableau. How do we get the $z_k-c_k$ values?

View attachment 5129