Optimizations and Programming. Abdelkhalak El Hami

Читать онлайн книгу.

Optimizations and Programming - Abdelkhalak El Hami


Скачать книгу
image

      The final tableau of the simplex algorithm is written as

image

      We therefore indeed have B = {x1, x5, x2} and N = {x3, x4, x6}. The submatrices AB and AN can be written as:

image

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

image

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

image

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

image

      which are indeed the columns that correspond to N = {x3,x4,x6}.

      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 images = bb.

      [1.16]image

      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]image

      EXAMPLE 1.12.– Consider the LP:

      [1.18]image

      [1.19]image

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

image

      Suppose that the optimal basis is B = {x1,x2}. Then

image

      Compute xB:

image image

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

image

      We will have images if and only if

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

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

      What is the interval for b2?

image

      We will have imagesB ≥ 0 if and only if

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

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

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

      The effect is:

image

      1.10.2. Effect of modifying c

      [1.20]image

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

image

      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:

image

      The ith component of the vector images is

image

      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:

image
Скачать книгу