Optimizations and Programming. Abdelkhalak El Hami

Чтение книги онлайн.

СКАЧАТЬ − x₃) to the objective function, where λ is the Lagrangian relaxation coefficient, which is updated at each iteration of the method:

      [1.13]

      The last constraint is added to bound the variables xi. This guarantees that the problem is bounded for every λ > 0. The coefficient λ is updated as follows: λ^k+1 = max It can be shown that λ tends to 1 and z tends to 8.4.

1.10. Postoptimal analysis

      Consider the LP:

      [1.14]

      We will now perform a postoptimal analysis of the optimal solution in terms of the problem data, also known as a sensitivity analysis. In other words, how does the solution or the objective function vary if we modify one of the entries of the vectors c or b, or the matrix A?

      To conduct a postoptimal analysis, we need to be able to express the solution of the simplex algorithm in terms of the initial problem data instead of simplex tableaus, which change at each iteration.

      As always, we introduce slack variables to the problem [1.14], writing A for the resulting matrix of size m × (m + n). We also assume that the basic variables B of the optimal solution xB are known. This information can be read off from the final tableau of the simplex algorithm, which is why this procedure is called postoptimal analysis.

      Let B = {x_j1, x_j2, . . . , xjm} be the list of basic variables, and let N be its complement with respect to the index set {1, 2, . . . , m + n}. For example, if m = n = 3 and B = {x₁, x₅, x₂}, then N = {x₃, x₄, x₆}. Based on the sets B and N, we can extract the following submatrices of A:

       – AB is the submatrix formed by the columns corresponding to the variables of B. We take them in the order specified by B.

       – AN is the submatrix formed by the columns corresponding to the variables of N in the order specified by N.

      EXAMPLE 1.11.– Consider the problem

      [1.15]

The matrix system Ax = b with slack variables is given as

      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 СКАЧАТЬ