Why are the quantities equal to 0?

122 Views Asked by At

I am looking at the general form of the Simplex algorithm with the use of tableaux.

$\overline{x_0}$ is a basic non degenarate feasible solution and thus the columns $P_1, \dots, P_m$ are linearly independent.

The first step is to create a $(m+1) \times (n+4)$ matrix as follows:

  • At the first column we write the basic columns: $P_1, \dots, P_m$.

  • At the second column we write the values of the corresponding coefficients of the objective funtion.

  • At the third column we write the initial basic feasible non degenerate solution $\overline{x_0}$.

  • At the next $n$ columns we write the elements of the columns of the matrix $A$.

  • The last column remains empty for now.

  • At the last row we write the value $z_0$ of the objective function that corresponds to the solution $\overline{x_0}$ and also the values of the differences $z_k-c_k, k=1, \dots, n$

Remark

The value of $z_k$ is the dot product of the second and the $(3+k)$-th column.

Why does it hold that $z_1-c_1=0, \dots, z_m-c_m=0$ ?

Isn't it $z_1-c_1=c_1 \cdot 1 + c_2 \cdot 0+ \dots + c_m \cdot z_m=c_1$? Or am I wrong?

EDIT: Also, suppose that we are given the following linear programming problem:

$$\max (5x_1-4x_2) \\ x_1-x_2+x_3=6 \\ 3x_1-2x_2+x_4=24 \\ -2x_1+3x_2+x_5=9 \\ x_1 \geq 0, i=1, \dots, 5$$

The first tableau is this:

$$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta \\ P_3 & 0 & 6 & 1 & -1 & 1 & 0 & 0 & \\ P_4 & 0 & 24 & 3 & -2 & 0 & 1 & 0 & \\ P_5 & 0 & 9 & -2 & 3 & 0 & 0 & 1 & \\ & z & 0 & -5 & 4 & 0& 0 & 0 & \end{matrix}$$

How did we deduce that $z_1-c_1=-5$ ?

1

There are 1 best solutions below

16
On

$Why\ does\ it\ hold\ that\ z_1-c_1=0, \dots, z_m-c_m=0? \tag{Q1}$ $Isn't\ it\ z_1-c_1=c_1 \cdot 1 + c_2 \cdot 0+ \dots + c_m \cdot z_m=c_1? \ Or\ am\ I\ wrong? \tag{Q2}$ $How\ did\ we\ deduce\ that\ z_1−c_1=−5 ? \tag{Q3}$

$(A3)$: The $z$ row only has non zero entries for non basic variables, $x_1,x_2$. The cost function is $\max (5x_1-4x_2)$. When a pivot is performed only a $1$ is left in a basic variable column note columns $P_3,P_4,P_5$. Pivoting changes the $z$ values.

$(A1)$: The $z$ value of a basic variable is always zero. It is zeroed when a pivot occurs.

$(A2)$: $z_k$ is the result of a row reduction during the pivoting process.

There is a very good example at Tableau example


Q: "Also wh does it hold that the $z$ value of a basic variable is always zero?"

Given:

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta \\ P_3 & 0 & 6 & \color{red}{1} & -1 & 1 & 0 & 0 & \\ P_4 & 0 & 24 & 3 & -2 & 0 & 1 & 0 & \\ P_5 & 0 & 9 & -2 & 3 & 0 & 0 & 1 & \\ & z & 0 & \color{red}{-5} & 4 & 0& 0 & 0 & \end{matrix}

To select $P_1$ as a basic variable and remove $P_3$

$RowZ := RowZ + 5*Row1$

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta \\ P_3 & 0 & 6 & 1 & -1 & 1 & 0 & 0 & \\ P_4 & 0 & 24 & 3 & -2 & 0 & 1 & 0 & \\ P_5 & 0 & 9 & -2 & 3 & 0 & 0 & 1 & \\ & z & 30 & 0 & -1 & 5 & 0 & 0 & \end{matrix}

Continuing to reduce all the entries in the $P_!$ column to zero except for the top:

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta \\ P_1 & \color{red}{5} & 6 & 1 & -1 & 1 & 0 & 0 & \\ P_4 & 0 & 6 & 0 & 1 & -3 & 1 & 0 & \\ P_5 & 0 & 21 & 0 & 1 & 2 & 0 & 1 & \\ & z & 30 & 0 & -1 & 5 & 0 & 0 & \end{matrix}

There is only a $1$ left in the $P_1$ column after the reduction and $z_1$ was reduced to zero.

The $z_k$ values are the coefficients of the cost function for the set of non basic variables.


$C_k$? : I don't know why you need this column?. The $z$ row keeps track of the coefficients of the cost function with respect to the non basic variables. Only $x_1$ and $x_2$ contribute to the cost.

Perhaps I'm not clear about the definition of the $c_B$ column?