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

Suppose that the LP that we wish to solve is in the standard form:

The auxiliary program method proceeds by letting M → +∞ in (PM) and solving the program obtained in the limit. Let

Maximizing z^′ (x, y) is equivalent to maximizing z″ (x, y), or maximizing

We therefore solve the auxiliary program (PA) given by

The simplex algorithm can now be applied to (PA) starting from the basic realizable solution y = b.

 – First case: max z″ (y) < 0. There exists yi > 0, i ∈ {1, 2, . . . , m}. In this case, (P ) does not have any realizable solutions.

 – Second case: max z″ (y) = 0. The optimal solution of (PA) can be used as an initial basic realizable solution for applying the simplex algorithm to (P ). The objective function of (P ) is expressed in terms of non-basic variables, then the simplex algorithm is applied to (P ).

REMARK.– For a minimization problem, we add instead.

Let us go into more detail for a minimization problem. The initial tableau of the auxiliary problem is as follows:

where B = I, cB = (1, 1, 1, . . .)T, and the matrices A and b relate to the auxiliary program. For the original variables i, we have ci = 0.

If (x*, y*) is a zero-cost optimal solution of the auxiliary problem, then the artificial variable in the basis is necessarily zero, so the solution is degenerate.

If we assume that the kth basic variable is artificial, consider the kth row of the tableau and select the element of this row in column j, where j is the index of a variable in the original problem. If the element is non-zero: k leaves the basis and j enters the basis, and we pivot the tableau. But what if no such element exists? This would mean that the matrix A does not have full rank, and the row in question corresponds to a redundant constraint.

Once the optimal tableau of the auxiliary problem has been obtained and all artificial variables have left the basis, we obtain the initial tableau of the original problem P1 by deleting any columns that relate to the artificial variables and calculating the reduced initial costs: in the box reserved for the cost function. The following example shows how this method works.

EXAMPLE 1.8.– Consider the following linear programming problem:

[1.10]

We will first perform Phase I of the simplex algorithm. After adding artificial variables, we obtain the tableau as follows:

There are no longer any artificial variables in the basis. We have found the optimal tableau of the auxiliary problem, and therefore an admissible basic solution for the initial problem. Since Phase I is now complete, delete the columns corresponding to the artificial variables and compute the reduced costs to obtain the following tableau:

This tableau is optimal. The optimal solution is x₁ = 1, x₂ = 0, x₃ = 0 and x₄ = 1, giving an optimal value of z = −1.