# Linear Programming: Modifying Coefficients of the Objective Function

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?

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.