1
$\begingroup$

Consider a final tableau with entries:

\begin{array} {|c|c|}\hline BV & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & RHS \\ \hline x_3 & 0 & -\frac{1}{2} & 1 & 1 & 2 & 0 & -1 & 4 \\ \ x_1 & 1 & \frac{1}{2} & 0 & 2 & -1 & 0 & -2 & 2 \\ x_6 & 0 & 2 & 0 & -1 & -\frac{1}{2} & 1 & 3 & 1 \\ \hline \end{array}

and the objective function is $x_1 + 3x_2 + 2x_3 + x_4 +x_5 + 3x_6 + 2x_7$

Is there an easy way to change the cost coefficient value of $x_6$ of 3 without affecting optimality? Similarly, is there a way to change $x_3$ of 2 by (-1/2) and shift some other things around so that everything remains optimal?

$\endgroup$

1 Answer 1

0
$\begingroup$

After having calculating all the missing $C^\pi_{NBV}$ of the given tableau, we should have following optimal tableau:

\begin{array} {|c|c|}\hline BV & z & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & RHS \\ \hline z & 1 & 0 & \frac{5}{2} & 0 & 0 & \frac{1}{2} & 0 & 3 & 13 \\ \hline x_3 & 0 & 0 & -\frac{1}{2} & 1 & 1 & 2 & 0 & -1 & 4 \\ \ x_1 & 0 & 1 & \frac{1}{2} & 0 & 2 & -1 & 0 & -2 & 2 \\ x_6 & 0 & 0 & 2 & 0 & -1 & -\frac{1}{2} & 1 & 3 & 1 \\ \hline \end{array}

We can change the basic variable $x_6$ cost coefficient by looking at the following formula for calculating the reduced costs of the non-basic variables:

$$C^\pi_{x_{NBV}}=\!\!\!\!\!\!\!\!\!\!\underbrace{C^T_{BV}}_{\text{Change of coeff BV}}\!\!\!\!\!\!\!\!B^{-1}A_{x_{NBV}}-\!\!\!\!\!\!\!\!\!\underbrace{C_{x_{NBV}}}_{\text{Change of coeff NBV}}$$

Where the change of the basic variable coefficients change $C^T_{BV}$, and the change of non-basic variables coefficients change $C_{NBV}$.

Thus, if we don't want to change the basis when we mess around with the coefficient of $x_6$, we need to need to measure the acceptable range of coefficient values $x_6$ is allowed to have that prevents a pivot from the above tableau. Thus, this is measured as such:

$$C^\pi_{x_2}=\begin{bmatrix}2&1&\Delta\end{bmatrix}\begin{bmatrix}-\frac{1}{2}\\\frac{1}{2}\\2\end{bmatrix}-3=2\Delta-\frac{7}{2}\ge0\Longrightarrow \Delta\ge\frac{7}{4}$$

$$C^\pi_{x_4}=\begin{bmatrix}2&1&\Delta\end{bmatrix}\begin{bmatrix}1\\2\\-1\end{bmatrix}-1=3-\Delta\ge0\Longrightarrow \Delta\le3$$

$$C^\pi_{x_5}=\begin{bmatrix}2&1&\Delta\end{bmatrix}\begin{bmatrix}2\\-1\\-\frac{1}{2}\end{bmatrix}-1=2-\frac{1}{2}\Delta\ge0\Longrightarrow \Delta\le4$$

$$C^\pi_{x_7}=\begin{bmatrix}2&1&\Delta\end{bmatrix}\begin{bmatrix}-1\\-2\\3\end{bmatrix}-2=3\Delta-6\ge0\Longrightarrow \Delta\ge2$$

Thus, the allowable range to change the coefficient of $x_6$ in the objective function is between the range $2\le\Delta\le3$. If we were to change the coefficient of $x_6$ in the objective function to say $\frac{3}{2}$, it will still preserve the current optimality of the tableau.

If we want to find the acceptable range of changing the non-basic variable $x_3$, we'll do the following:

$$C^\pi_{x_j}=\begin{bmatrix}2&1&3\end{bmatrix}B^{-1}A_j-\Delta\ge0$$

For each non-basic variable in the tableau like what has been demonstrated above for the change of basic variables.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .