Beyond the Optimum, keys to Post-Optimization

Imagine you run a business. You formulate a mathematical model to maximize your profits (or minimize your costs), run the algorithm, and that’s it! You have the optimal solution in your hands. You know exactly how much to produce and which resources to use. Everything seems perfect until… real life gets in the way: the price of a raw material fluctuates, a supplier offers you an extra ton of resources, or you decide to launch a new product.

Does this mean you have to throw everything away and solve the problem from scratch? Fortunately, no. This is where post-optimization comes in, one of the most powerful and practical applications of linear optimization.

What is post-optimization?

In practice, almost no optimization problem remains unchanged for long. Costs change, new products are introduced, more resources become available, or new constraints arise that did not exist when the model was originally solved.

Post-optimization studies exactly how these changes affect an optimal solution that has already been obtained. Instead of solving the entire problem from scratch, it takes advantage of the information contained in the final Simplex tableau to determine whether the current solution remains valid or how it can be updated efficiently.

Broadly speaking, whenever the problem changes, post-optimization allows us to deal with two main situations:

Modifying the original model: What happens if the availability of existing resources changes, or if the profit associated with our current products changes?
Extending the original model: What happens if we introduce new variables (such as an entirely new product) or if new operational constraints must be added?

Example: a production planning problem

To illustrate the different post-optimization scenarios, we will use the same problem throughout this post. This makes it easier to see what changes in each situation and which information from the original solution can be reused.

Consider a company that manufactures three products using two limited resources.

The corresponding linear optimization model is

\[\begin{aligned} \max\quad & z=3x_1+2x_2+x_3\\ \text{s.t.:}\quad & 4x_1 + 2x_2 + 3x_3 \leqslant 40\\ & 2x_1 + 2x_2 + x_3 \leqslant 30\\ & x_1,x_2,x_3 \geqslant 0 \end{aligned}\]

whose final Simplex tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & 1 & \frac{1}{2} & \frac{1}{2} & 35 \\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac{1}{2} & -\frac{1}{2} & 5 \\ {\color{gray}2} & x_2 & 0 & 1 & -\frac{1}{2} & -\frac{1}{2} & 1 & 10 \\ \hline \end{array}\]

The optimal solution is

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0)\]

with an optimal objective value of

\[z^*=35\]

Once this solution has been obtained, questions far more interesting than the original optimization problem begin to arise:

What happens if the profit of one of the products increases?
What happens if more raw material becomes available?
Which resource is actually the bottleneck?
What happens if the production process for one product changes and its technical specifications are modified?
What happens if a new product is added to the production line?
What happens if new constraints are introduced into the model?

These questions lie at the heart of post-optimization.

Model Modifications

In the following sections, we will study changes that do not alter the structure of the problem itself, but only the data used to formulate it. The optimal basis that has already been computed may still be useful, although we must verify whether it remains feasible and/or optimal. In this case, the input data change.

Resource vector

One of the most common sensitivity analyses consists of studying how changes in resource availability affect the optimal solution. In terms of the model, this amounts to modifying the resource vector, $\mathbf{b}$.

Let $\hat{\mathbf{b}}$ denote the new resource vector. If the optimal basis $\mathbf{B}$ remains unchanged, the new basic solution is given by

\[\hat{\mathbf{x}}_\mathbf{B} = \mathbf{B}^{-1}\hat{\mathbf{b}}\]

and the new objective function value is

\[\hat{z}= \mathbf{c}_\mathbf{B}^\intercal \hat{\mathbf{x}}_\mathbf{B}\]

Once the new basic solution has been computed, two situations may arise:

The solution remains feasible, that is,
\[\hat{\mathbf{x}}_\mathbf{B} \geqslant \mathbf{0}\]
In this case, the basis remains feasible and, since the reduced costs have not changed, it also remains optimal. Therefore, the new solution to the problem is $\hat{\mathbf{x}}_\mathbf{B}$, and the new optimal objective value is $\hat{z}$.
The solution is no longer feasible, that is, at least one component of $\hat{\mathbf{x}}_\mathbf{B}$ is negative.

In this situation, primal feasibility is lost, although the basis remains dual feasible. As a result, there is no need to solve the problem from scratch. Instead, it is sufficient to apply the Dual Simplex algorithm, which restores feasibility and efficiently finds the new optimal solution.

Example: modifying the resource vector

To illustrate the procedure, consider the problem solved in the previous section and suppose that the resource vector changes. We will analyze two different cases:

$\hat{\mathbf{b}}_1^\intercal=(38,36)$
$\hat{\mathbf{b}}_2^\intercal=(20,60)$

In both cases, we will use the same optimal basis obtained previously and check whether it remains feasible.

Case 1: the new basis remains feasible

Suppose the new resource vector is

\[\hat{\mathbf{b}}^\intercal=(38,36)\]

The new basic solution is

\[\hat{\mathbf{x}}_\mathbf{B}=\mathbf{B}^{-1}\hat{\mathbf{b}}= \begin{pmatrix} \frac12 & -\frac12\\ -\frac12 & 1 \end{pmatrix} \begin{pmatrix} 38\\ 36 \end{pmatrix}= \begin{pmatrix} 1\\ 17 \end{pmatrix}\]

Since

\[\hat{\mathbf{x}}_\mathbf{B} \geqslant \mathbf{0}\]

the basis remains feasible and therefore also remains optimal.

The new objective value is

\[\hat{z}=\mathbf{c}_\mathbf{B}^\intercal\hat{\mathbf{x}}_\mathbf{B}=(3,2) \begin{pmatrix} 1\\ 17 \end{pmatrix} = 37\]

Hence, the new optimal solution is

\[(\mathbf{x}^*)^\intercal=(1,17,0,0,0)\qquad z^*=37\]

The final tableau changes only in the right-hand-side column:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & 1 & \frac12 & \frac12 & 37\\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac12 & -\frac12 & 1\\ {\color{gray}2} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 17\\ \hline \end{array}\]

In this case, no additional Simplex iterations are required.

Case 2: the new basis loses feasibility

Now consider the new resource vector

\[\hat{\mathbf{b}}^\intercal=(20,60)\]

The new basic solution is

\[\hat{\mathbf{x}}_\mathbf{B}=\mathbf{B}^{-1}\hat{\mathbf{b}}= \begin{pmatrix} \frac12 & -\frac12\\ -\frac12 & 1 \end{pmatrix} \begin{pmatrix} 20\\ 60 \end{pmatrix}= \begin{pmatrix} -20\\ 50 \end{pmatrix}\]

In this case,

\[\hat{\mathbf{x}}_\mathbf{B} \ngeqslant \mathbf{0}\]

so the basis is no longer feasible.

Although the objective value associated with this basis would be

\[\hat{z}=\mathbf{c}_\mathbf{B}^\intercal\hat{\mathbf{x}}_\mathbf{B}= (3,2) \begin{pmatrix} -20\\ 50 \end{pmatrix} =40\]

this solution is not valid because one of the basic variables takes a negative value.

The updated tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & 1 & \frac12 & \frac12 & 40\\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac12 & {\color{#2698ba}-\frac12} & -20\\ {\color{gray}2} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 50\\ \hline \end{array}\]

Since primal feasibility has been lost, we must apply the Dual Simplex algorithm to recover a feasible solution while preserving dual optimality.

After one iteration of the Dual Simplex algorithm, we obtain the following optimal tableau:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}0} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 1 & 0 & 2 & 1 & 0 & 20\\ \hline {\color{gray}0} & x_5^s & -2 & 0 & -2 & -1 & 1 & 40\\ {\color{gray}2} & x_2 & 2 & 1 & \frac32 & \frac12 & 0 & 10\\ \hline \end{array}\]

Therefore, the new optimal solution is

\[(\mathbf{x}^*)^\intercal=(0,10,0,0,40) \qquad z^*=20\]

Cost Vector

Another very common sensitivity analysis consists of studying how changes in the coefficients of the objective function, that is, in the cost vector $\mathbf{c}$, affect the optimal solution.

Unlike changes to the resource vector, the basic solution itself does not change. What does change are the reduced costs and, consequently, the value of the objective function.

Let $\hat{\mathbf{c}}$ be the new cost vector. If the same basis $\mathbf{B}$ is retained, the new values of $\hat{z}_j-\hat{c}_j$ are given by

\[\hat{z}_j-\hat{c}_j = \hat{\mathbf{c}}_\mathbf{B}^\intercal \mathbf{B}^{-1}\mathbf{a}_j - \hat{c}_j = \hat{\mathbf{c}}_\mathbf{B}^\intercal \mathbf{y}_j - \hat{c}_j\]

while the new value of the objective function is

\[\hat{z} = \hat{\mathbf{c}}_\mathbf{B}^\intercal \mathbf{x}_\mathbf{B}\]

Based on these new reduced costs, two situations may arise:

The basis remains optimal. For a maximization problem, this occurs if
\[\hat{z}_j-\hat{c}_j \geqslant 0 \qquad \forall j\]
In this case, the basic solution $\mathbf{x}_\mathbf{B}$ remains optimal, and only the value of the objective function changes.
The basis is no longer optimal. If there exists a nonbasic variable whose reduced cost satisfies
\[\hat{z}_j-\hat{c}_j<0\]
then the tableau is no longer optimal. Since feasibility has not been lost, it is sufficient to continue the iterations using the Primal Simplex algorithm.

Example: modifying the cost vector

Consider the previous problem and suppose that the cost vector is modified. We will analyze two cases:

$\hat{\mathbf{c}}_1^\intercal=(4,3,1)$
$\hat{\mathbf{c}}_2^\intercal=(1,1,1)$

Case 1: the basis remains optimal

\[\hat{\mathbf{c}}^\intercal=(4,3,1)\]

the new values of $z_j-c_j$ are

\[\begin{aligned} \hat{z}_1-\hat{c}_1 &=0\\ \hat{z}_2-\hat{c}_2 &=0\\ \hat{z}_3-\hat{c}_3 &=\frac32\\ \hat{z}_4-\hat{c}_4 &=\frac12\\ \hat{z}_5-\hat{c}_5 &=1 \end{aligned}\]

Since all reduced costs are nonnegative, the basis remains optimal.

The new value of the objective function is

\[\hat{z} = (4,3) \begin{pmatrix} 5\\ 10 \end{pmatrix} = 50\]

so the optimal solution remains

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0) \qquad z^*=50\]

The new final tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}4} & {\color{gray}3} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & \frac32 & \frac12 & 1 & 50\\ \hline {\color{gray}4} & x_1 & 1 & 0 & 1 & \frac12 & -\frac12 & 5\\ {\color{gray}3} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 10\\ \hline \end{array}\]

No additional iterations of the Simplex algorithm are required.

Case 2: the basis is no longer optimal

Now suppose that

\[\hat{\mathbf{c}}^\intercal=(1,1,1)\]

The new values of $z_j-c_j$ are

\[\begin{aligned} \hat{z}_1-\hat{c}_1 &=0\\ \hat{z}_2-\hat{c}_2 &=0\\ \hat{z}_3-\hat{c}_3 &=-\frac12\\ \hat{z}_4-\hat{c}_4 &=0\\ \hat{z}_5-\hat{c}_5 &=\frac12 \end{aligned}\]

Notice that

\[\hat{z}_3-\hat{c}_3<0\]

so the optimality condition is no longer satisfied.

The updated tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\color{gray}1} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & -\frac12 & 0 & \frac12 & 15\\ \hline {\color{gray}1} & x_1 & 1 & 0 & {\color{#2698ba}1} & \frac12 & -\frac12 & 5\\ {\color{gray}1} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 10\\ \hline \end{array}\]

Since the solution remains feasible but is no longer optimal, we simply apply the Primal Simplex algorithm.

After one iteration, we obtain the new final tableau:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\color{gray}1} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & \frac12 & 0 & 0 & \frac14 & \frac14 & \frac{35}{2}\\ \hline {\color{gray}1} & x_3 & 1 & 0 & 1 & \frac12 & -\frac12 & 5\\ {\color{gray}1} & x_2 & \frac12 & 1 & 0 & -\frac14 & \frac34 & \frac{25}{2}\\ \hline \end{array}\]

Therefore, the new optimal solution is

\[(\mathbf{x}^*)^\intercal = (0,25/2,5,0,0) \qquad z^* = 35/2\]

Technical Coefficients of a Nonbasic Column

Another type of sensitivity analysis consists of studying how modifications to one of the nonbasic columns of the constraint matrix affect the optimal solution. This type of change may arise, for example, when an activity consumes a different amount of resources or when the formulation of a variable is modified.

If the modified column corresponds to a nonbasic variable, the basis remains unchanged. However, both the corresponding column in the Simplex tableau and the reduced cost of that variable are modified.

Let $\hat{\mathbf{a}}_j$ denote the new column associated with the nonbasic variable $x_j$. The new tableau column is given by

\[\hat{\mathbf{y}}_j = \mathbf{B}^{-1}\hat{\mathbf{a}}_j\]

while its new reduced cost is

\[\hat{z}_j-c_j = \mathbf{c}_\mathbf{B}^\intercal \mathbf{B}^{-1} \hat{\mathbf{a}}_j - c_j = \mathbf{c}_\mathbf{B}^\intercal \hat{\mathbf{y}}_j - c_j\]

Based on this new reduced cost, two situations may arise:

The basis remains optimal. For a maximization problem, this occurs if
\[\hat{z}_j - c_j \geqslant 0\]
In this case, the basic solution remains unchanged, and the value of the objective function is unaffected.
The basis is no longer optimal. If
\[\hat{z}_j-c_j<0\]
then the modified variable becomes a candidate to enter the basis. Since the solution remains feasible, it is sufficient to continue the iterations using the Primal Simplex algorithm.

Example: modifying the vector of technical coefficients

Consider the previous problem and suppose that the third column of the constraint matrix is modified. We will analyze two possibilities:

$\hat{\mathbf{a}}_{3_1}^\intercal=(4,2)$
$\hat{\mathbf{a}}_{3_2}^\intercal=\left(\frac12,1\right)$

Case 1: the basis remains optimal

\[\hat{\mathbf{a}}_{3_1}^\intercal=(4,2)\]

the new tableau column is

\[\hat{\mathbf{y}}_3 = \mathbf{B}^{-1} \hat{\mathbf{a}}_{3_1} = \begin{pmatrix} \frac12 & -\frac12\\ -\frac12 & 1 \end{pmatrix} \begin{pmatrix} 4\\ 2 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix}\]

The new value of $z_j-c_j$ is

\[\hat{z}_3-c_3 = (3,2) \begin{pmatrix} 1\\ 0 \end{pmatrix} - 1 = 2\]

Since the reduced cost remains nonnegative, the basis is still optimal.

The optimal solution remains unchanged,

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0)\]

and so does the optimal value,

\[z^*=35\]

The new final tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & 2 & \frac12 & \frac12 & 35\\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac12 & -\frac12 & 5\\ {\color{gray}2} & x_2 & 0 & 1 & 0 & -\frac12 & 1 & 10\\ \hline \end{array}\]

No additional iterations are required.

Case 2: the basis is no longer optimal

Now suppose that

\[\hat{\mathbf{a}}_{3_2}^\intercal = \left(\frac12,1\right)\]

The new tableau column is

\[\hat{\mathbf{y}}_3 = \mathbf{B}^{-1} \hat{\mathbf{a}}_{3_2} = \begin{pmatrix} -\frac14\\ \frac34 \end{pmatrix}\]

and the new value of $z_j-c_j$ is

\[\hat{z}_3-c_3 = (3,2) \begin{pmatrix} -\frac14\\ \frac34 \end{pmatrix} - 1 = -\frac14\]

Since

\[\hat{z}_3-c_3<0\]

the optimality condition is no longer satisfied.

The updated tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & -\frac14 & \frac12 & \frac12 & 35\\ \hline {\color{gray}3} & x_1 & 1 & 0 & -\frac14 & \frac12 & -\frac12 & 5\\ {\color{gray}2} & x_2 & 0 & 1 & \frac34 & -\frac12 & 1 & 10\\ \hline \end{array}\]

Since the solution remains feasible, it is sufficient to continue the iterations using the Primal Simplex algorithm.

After one iteration, the following final tableau is obtained:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}1} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & \frac13 & 0 & \frac13 & \frac56 & \frac{115}{3}\\ \hline {\color{gray}3} & x_1 & 1 & \frac13 & 0 & \frac13 & -\frac16 & \frac{25}{3}\\ {\color{gray}1} & x_3 & 0 & \frac43 & 1 & -\frac23 & \frac43 & \frac{40}{3}\\ \hline \end{array}\]

Therefore, the new optimal solution is

\[(\mathbf{x}^*)^\intercal = (25/3,0,40/3,0,0) \qquad z^* = 115/3\]

Model Extensions

So far, we have only modified existing data in the problem. We now turn to situations where the model itself changes in size by incorporating new variables or new constraints. In this case, the model grows in dimension.

Adding a New Variable

Another common post-optimality scenario is to analyze what happens when a new decision variable is added to the model. This situation arises, for example, when a company considers manufacturing a new product or offering a new service without having to reformulate the entire problem.

From the Simplex algorithm perspective, adding a new variable amounts to introducing a new column into the final tableau.

Let $x_{n+1}$ denote the new variable, characterized by its constraint column $\mathbf{a}_{n+1}$ and its objective coefficient $c_{n+1}$. The corresponding column in the tableau is computed as

\[\mathbf{y}_{n+1} = \mathbf{B}^{-1}\mathbf{a}_{n+1}\]

while its reduced cost is

\[z_{n+1}-c_{n+1} = \mathbf{c}_\mathbf{B}^\intercal \mathbf{y}_{n+1} - c_{n+1}\]

Two situations may occur:

The new variable does not improve the solution. For a maximization problem, this happens when
\[z_{n+1}-c_{n+1} \geqslant 0\]
In this case, the new variable remains nonbasic and the optimal solution is unchanged.
The new variable improves the solution. If
\[z_{n+1}-c_{n+1}<0\]
the new variable becomes eligible to enter the basis. Since feasibility is preserved, we simply continue the iterations using the Primal Simplex algorithm.

Adding a New Constraint

Another common post-optimality analysis consists of studying the effect of introducing a new constraint into the model. This situation arises whenever the original problem must be adapted to new limitations, such as the availability of an additional resource, a new capacity limit, or an extra operational requirement.

Unlike the previous cases, adding a constraint also requires introducing a new slack variable, so the Simplex tableau gains both a new row and a new column.

Initially, the new row does not generally preserve the identity matrix associated with the current basic variables. However, this structure can be restored by appropriately combining the existing rows of the tableau.

Once the identity has been reconstructed, two situations may arise:

The solution remains feasible. In this case, the tableau is still optimal and the solution remains unchanged.
The solution becomes infeasible. If any basic variable becomes negative, primal feasibility is lost and the Dual Simplex algorithm must be applied.

Example: Adding a New Constraint

Consider the problem solved previously and suppose that a third resource is introduced, whose coefficients are

\[(1,1,1)\]

We analyze two different availability levels for this new resource:

$b_3=20$.
$b_3=10$.

Case 1: the solution remains feasible

The new constraint is

\[x_1+x_2+x_3 \leqslant 20\]

In standard form,

\[x_1+x_2+x_3+x_6^s=20\]

After adding this equation to the tableau, we initially obtain

\[\begin{array}{cc|rrrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^s & \\ \hline & z_j-c_j & 0 & 0 & 1 & \frac12 & \frac12 & 0 & 35\\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac12 & -\frac12 & 0 & 5\\ {\color{gray}2} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 0 & 10\\ {\color{gray}0} & x_6^s & 1 & 1 & 1 & 0 & 0 & 1 & 20\\ \hline \end{array}\]

Notice that the identity matrix no longer appears explicitly. It can be restored simply by subtracting the sum of the two existing basic rows from the new row.

After performing this operation, the tableau becomes

Since all basic variables remain nonnegative, primal feasibility is preserved.

Therefore, the optimal solution becomes

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0,5)\]

with the same objective value,

\[z^*=35\]

No additional iterations are required.

Case 2: the solution becomes infeasible

Now suppose that the availability of the new resource is only

\[b_3=10\]

The new constraint becomes

\[x_1+x_2+x_3+x_6^s=10\]

Repeating the same procedure to reconstruct the identity matrix yields

In this case, a basic variable becomes negative,

\[x_6^s=-5\]

so the current solution is no longer feasible.

Dual optimality is preserved, but primal feasibility has been lost. Consequently, the tableau can be reoptimized directly using the Dual Simplex algorithm.

After one iteration, we obtain the following final tableau:

\[\begin{array}{cc|rrrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^s & \\ \hline & z_j-c_j & 0 & 0 & \frac32 & \frac12 & 0 & 1 & 30\\ \hline {\color{gray}3} & x_1 & 1 & 0 & \frac12 & \frac12 & 0 & -1 & 10\\ {\color{gray}2} & x_2 & 0 & 1 & \frac12 & -\frac12 & 0 & 2 & 0\\ {\color{gray}0} & x_5^s & 0 & 0 & -1 & 0 & 1 & -2 & 10\\ \hline \end{array}\]

The new optimal solution is

\[(\mathbf{x}^*)^\intercal=(10,0,0,0,10,0)\]

with objective value

\[z^*=30\]

Summary

Throughout this post, we have seen that not all modifications affect an optimal solution in the same way. Depending on which element of the model changes, feasibility, optimality, or both may be lost. This determines whether the final tableau can be reused directly or whether additional iterations of one of the Simplex algorithms are required.

The following table summarizes the most common cases:

Modification	Is primal feasibility lost?	Is dual feasibility lost?	Algorithm to apply
Change in the resource vector $\mathbf{b}$	Possibly	No	Dual Simplex (if feasibility is lost)
Change in the cost vector $\mathbf{c}$	No	Possibly	Primal Simplex (if optimality is lost)
Change in a nonbasic column $\mathbf{a}_j$	No	Possibly	Primal Simplex (if optimality is lost)
Addition of a new variable	No	Possibly	Primal Simplex (if the new variable improves the solution)
Addition of a new constraint	Possibly	No	Dual Simplex (if feasibility is lost)

A very clear pattern emerges:

Whenever a modification affects the feasibility of the current solution, the appropriate algorithm for recovering optimality is the Dual Simplex algorithm.
Whenever the modification affects only optimality, while feasibility is preserved, it is sufficient to continue with the Primal Simplex algorithm.

One of the main strengths of the Simplex method is that its final tableau contains much more information than just an optimal solution. This information makes it possible to analyze the impact of changes in the model without resolving the entire problem from scratch in many situations.

As we have seen, the type of modification also determines the appropriate reoptimization procedure. If primal feasibility is lost, the Dual Simplex algorithm is the natural choice. If only dual feasibility (optimality) is lost, the Primal Simplex algorithm can simply continue from the current tableau.

Post-optimality analysis therefore transforms an optimal solution into a dynamic decision-making tool, capable of adapting efficiently to the inevitable changes that arise in real-world optimization problems.

Beyond the Optimum, keys to Post-Optimization

What is post-optimization?

Example: a production planning problem

Model Modifications

Resource vector

Example: modifying the resource vector

Cost Vector

Example: modifying the cost vector

Technical Coefficients of a Nonbasic Column

Example: modifying the vector of technical coefficients

Model Extensions

Adding a New Variable

Example: Adding a New Variable

Adding a New Constraint

Example: Adding a New Constraint

Summary

References

Enjoy Reading This Article?