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

We now apply the transformation x → that increased the value of z. Since the value z() (> z(x)) is not necessarily maximal in general, we may need to repeat the steps for choosing r and k several times until we find a basic feasible solution that is also a maximum of z.

To do this, we need a second tableau where xJ is replaced by interpreted in the same way as the first. The same linear transformation that allowed us to pass from x to is applied to the columns of A.

The matrix A = (aij, i = 1, . . . , m, j = 1, . . . , n) is replaced by Ā = (āij, i = 1, . . . , m, j = 1, . . . , n) as follows:

[1.5]

This gives

[1.6]

where i, i = 1, . . . , m, are the new basic variables

The last row of the new tableau is computed in the same way:

[1.7]

EXAMPLE 1.5.– If we apply the above procedure to our example, we obtain Table 1.2.

Table 1.2. Second simplex tableau

As we saw above, the value of z increases from 0 to 8, but there are still negative values in the last row of the tableau, so we need to perform another change of basis by applying the formulas [1.4] and [1.3] after substituting . This gives:

r = 1, x₃ leaves the basis. = {2, 1} is the new basis.

The computation with this new basis is presented in Table 1.3.

Table 1.3. Third simplex tableau

The value of z now increases from 8 to This value is maximal because every value in the final row is non-negative. The optimal solution is therefore This solution is unique because no further change of basis is possible.

EXAMPLE 1.6.– Consider the linear problem:

[1.8]

Let us introduce slack variables x₃, x₄ and x₅:

[1.9]

This gives the following initial tableau with the basis (x₃, x₄, x₅):

The new basis is (x₃, x₁, x₅) given as:

The next basis is (x₂, x₁, x₅) given as:

Since the reduced costs are all positive, this tableau is optimal. The optimal solution is x₁ = 150 and x₂ = 100, giving an optimal value of z = −1, 500, 000 for the objective function.