Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 36

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₆}.