Optimizations and Programming - Abdelkhalak El Hami

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

href="#fb3_img_img_2cf00e5d-3eb4-5d18-ae93-8e2fd91303b2.png" alt="images"/>

      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 images. This gives:

image

      r = 1, x3 leaves the basis. images = {2, 1} is the new basis.

images

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

      EXAMPLE 1.6.– Consider the linear problem:

      [1.8]image

      [1.9]image

      This gives the following initial tableau with the basis (x3, x4, x5):

image

      The new basis is (x3, x1, x5) given as:

image

      The next basis is (x2, x1, x5) given as:

image

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

      1.5.4. Existence and uniqueness of an optimal solution

      After writing out the first simplex tableau and adding zj = −cj to the last row, there are three possible cases:

       1) zj − cj ≥ 0 for j = 1, . . . , n. The basic feasible solution x is already optimal. This optimal solution may or may not be unique;

       2) there exists j ∈ {1, . . . , n} such that zj −cj < 0 and aij ≤ 0 for every i ∈ J. In this case, the domain of realizable solutions is unbounded and the problem is ill-posed, since max z(x) = +∞;

       3) the usual case: there exists j ∈ {1, . . . , n} such that zj − cj < 0, and there exists i ∈ J such that aij > 0. The change in basis described earlier is now possible and should be performed, possibly several times, until case (1) is reached.

      Could the simplex algorithm ever fail to terminate if case (3) leads to a loop? The answer is yes, and examples have been successfully constructed. However, they are very rare in practice.

      Let us therefore state two important theorems about the simplex method.

      THEOREM 1.3.– Let images be a basic realizable solution of (P ) with respect to a basis J (|J| = m = rank(A)). Let images for every j = 1, . . . , n, then x is an optimal basic realizable solution.

      THEOREM 1.4.– Let images be a basic realizable solution of (P ) with respect to a basis images Suppose that aij ≤ 0 for every i ∈ J and for every j ∈ {1, . . . , n} such that zj − cj < 0. Then the set {z(x), x is a realizable solution} is unbounded.

      REMARK.– For a comprehensive discussion of the efficiency of the simplex method, refer to [CHV 83].

      This section presents two techniques for finding a basic realizable solution to initialize the simplex algorithm: the first is the Big M method, and the second is the Phase I method.

      1.6.1. Big M method

      Suppose that we wish to solve the LP

image

      By adding slack variables (with positive or negative signs), we can always reduce the LP to the form (P) described above, with images If there is no obvious basic realizable solution to initialize the simplex algorithm, we proceed by adding artificial variables yi ≥ 0 to the constraints:

      Ax = b is replaced by Ax + y = b, y = (y1, y2, . . . , ym)T ∈ images

      The new constraints are not equivalent to the initial constraints. The yi > 0 are penalized by replacing the objective function z(x) with

image

      where M is some very large positive value. We will choose yi = bi, i = 1, . . . , m, as a basic feasible solution to serve as the initial solution.

      Since the yi significantly reduce the value of z′, they will disappear from the basis over the course of the simplex algorithm. As they are non-basic variables, their value will be equal to zero, and the LP that is ultimately solved is the same as the program (P).

      EXAMPLE 1.7.– Consider the LP

image

      The new program is given as

image image

      The

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