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

Suppose that we wish to solve the LP

where A is an m × n matrix, rank A = m < n.

By adding slack variables (with positive or negative signs), we can always reduce the LP to the form (P) described above, with 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 = (y₁, y₂, . . . , ym)T ∈

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

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

The new program is given as

The first tableau is as follows:

The second tableau is as follows:

The third tableau is as follows:

The unique optimal solution is given by x₁ = 4, x₂ = 0, x₃ = 1, and z(x₁, x₂, x₃) = −6.