Optimizations and Programming. Abdelkhalak El Hami

      The final tableau of the simplex algorithm is written as

      We therefore indeed have B = {x₁, x₅, x₂} and N = {x₃, x₄, x₆}. The submatrices AB and AN can be written as:

      Using a block partition based on the index sets B and N, we can write

      The solution can be computed algebraically. The matrix AB is invertible because B is a basis. The optimal solution is given by the formula since the non-basic variables must be zero, i.e. xN = 0. In our example, we have

      which is the correct optimal solution according to the final simplex tableau. The other columns of the final tableau correspond to

      which are indeed the columns that correspond to N = {x₃,x₄,x₆}.

1.10.1. Effect of modifying b

      Let us analyze the effect of modifying the vector b. In other words, we shall study the behavior of the solution of the modified problem when b is replaced by = b+Δb.

      [1.16]

      Let xB be the basic variables of the solution. Our goal is to determine a condition that guarantees that the basis B will remain optimal. In fact, this is easy. The vector b only appears in the optimality condition [1.16]. Therefore, the basic variables xB remain optimal for the modified problem if

      [1.17]

      EXAMPLE 1.12.– Consider the LP:

      [1.18]

      [1.19]

      In matrix form with slack variables, this can be written as:

      Suppose that the optimal basis is B = {x₁,x₂}. Then

      Compute xB:

Compute the reduced costs

      The solution xB = (2, 4)T is therefore optimal, i.e. x = (2, 4, 0, 0, 0)T.

      We will have if and only if

      2 + 2a ≥ 0 and 4 − a ≥ 0.

      This gives an interval for the parameter b₁: −1 ≤ a ≤ 4.

      What is the interval for b₂?

      We will have B ≥ 0 if and only if

      2 − a ≥ 0 and 4 + a ≥ 0.

      This gives the interval for the parameter b₂: −4 ≤ a ≤ 2.

      What is the effect on the minimum value of the objective function?

      The effect is:

      1.10.2. Effect of modifying c

Next, let us find a condition that guarantees that the basis B will remain optimal under First, observe that the solution remains unchanged. However, the simplex tableau might no longer be optimal. To keep it optimal, we must impose the stability condition

      [1.20]

      In general, let us determine the effect of modifying a single variable xi:

      There are two cases to analyze depending on whether xi is a basic or non-basic variable.

       Case of a non-basic variable

      Write ei for the canonical basis vector of ℝn, i.e. ei = (0, 0, . . . , 1, 0, . . . , 0)T with 1 at position i. Then:

      The ith component of the vector is

      where the ri are the components of the final row of the simplex tableau. In other words, we have all the information that we need to compute the stability intervals of the coefficients ci.

      EXAMPLE 1.13.– Again, consider the previous example. The final simplex tableau is:

The last row gives us the vector of reduced costs The basic variables are B = {x₁, x₂}, and the non-basic variables are N = {x₃, x₄, x₅}. The objective function is of the form z = c₁x₁ + c₂x₂