Simplex method with artificial variables examples. Solving linear programming problems using the artificial basis method

The solution of the problem linear programming The simplex method begins with finding some reference plan.

Let's consider the third case of constructing the initial reference plan (the first and second are described in paragraph 2.1).

Let the system of restrictions have the form

Let's move on to canonical form by introducing additional variables
, which we subtract from the left-hand sides of the system inequalities. Let's get the system

.

Now the constraint system does not have a preferred form, since additional variables x n + i enter the left side (with b i 0) with coefficients equal to –1. In this case, the so-called artificial basis by going to M-task.

Artificial variables are added to the left sides of equality constraints that do not have a preferred form w i. Variables in the target function w i entered with a coefficient M in the case of solving the problem at a minimum and with a coefficient – M– for the maximum problem, where M– big positive number. The resulting problem is called M-task, corresponding to the original one. She always has a preferred look.

Let the original linear programming problem have the form

;
;

However, none of the constraints has a preferred variable. M-task will be written as follows:

;

In this case, the “–” sign in function (10) refers to the maximum problem. Problem (10)–(12) has a preferred form. Her initial reference plan looks like

.

If some of the equations (8) have a preferred form, then artificial variables should not be introduced into them.

Theorem 5. If optimally X wholesale 

M-problems (10)–(12) all artificial variables
then the plan
is the optimal plan for the original problem (7)–(9).

Theorem 6 (a sign of incompatibility of the system of restrictions ) . If optimally M-problem, at least one of the artificial variables is different from zero, then the system of constraints of the original problem is inconsistent.

When M-task index line simplex table We break it into two. The first line contains the free terms of the expressions
And
, and in the second – coefficients containing M. The optimality sign is checked first against the second line. It also determines the variable to be included in the basis. As artificial variables are excluded from the basis, the corresponding columns of elements can be omitted. This is explained by the fact that artificial variables are not returned to the basis, and therefore the corresponding columns will no longer be needed. After eliminating all artificial variables from the basis, the process of finding the optimal plan continues using the first line objective function.

Example 4. Solve a linear programming problem using an artificial basis

The first constraint has a preferred variable X 3, but the second one is not. Therefore, we introduce an artificial variable into it w 1 . We come to M- task

Let's add a condition M- problems in a simplex table. 5. The initial reference plan looks like x 0 = (x 1 ;x 2 ;x 3 ;x 4 ;w 1) = (0; 0; 2; 0; 12),z(x 0) = 0 – 12M.

Table 5

	With B
z j – c j

Let us make the necessary explanations.

It is convenient to split the index line into two. In the first of them the free terms of the expressions  0 = c B A 0 и j =c B A j –c j, and in the second – coefficients containing M. For example, for table. 5:

We first check the optimality sign using the second line of the index line. Since there are negative assessments in it, the plan x 0 is not optimal.

Let's move on to a new table. 6.

The resolving column is found by max(|–3 M|; |–4M|} = 4M, the resolution line is determined by
. Therefore, 1 is the enabling element.

Table 6

	With B
z j – c j

There are no negative ratings in the index line. Therefore, according to the optimality criterion, the reference plan (0; 2; 0; 0; 4) is optimal. But since in the optimal plan the artificial variable w 1 is not equal to 0, then by Theorem 6 the system of constraints of the original problem is inconsistent. The problem has no solution.

Answer: there is no decision.

Example 5. Solve the problem using an artificial basis

Let's organize the recording of the original task. Multiply the second inequality by –1:

Let us reduce the problem to its canonical form. We get

The first and fourth constraints have preferred variables, but the second and third do not. Therefore, we introduce artificial variables into them w 1 and w 2. We come to M- task

Let's add a condition M- problems in a simplex table. 7. The initial reference plan looks like x 0 = (0; 0; 10; 0; 0; 4; 3; 9),z(x 0) = 0 + 12M.

Table 7

	With B
z j – c j

We solve the problem to the minimum. We first check the optimality sign using the second line of the index line. Since there is a positive assessment in it, the plan x 0 is not optimal. Let's move on to a new table. 8.

Table 8

		With B

Until now, we have comprehensively considered the problem, the solution of which was carried out on the basis of the simplest algorithm of the simplex method, since all the constraints were of the form less than or equal to. In this case, additional task variables form a unit basis. But it may turn out that the system of restrictions is presented in canonical form, but it is not reduced to a unit basis.

When solving such problems, it was introduced artificial basis method. It is especially convenient when the number of variables significantly exceeds the number of equations.

Algorithm for solving the problem simplex method Let's look at an example with an artificial basis.

Example 1

Find the maximum Z=4X1+2X2+X3

3Х1+2Х2+Х3=15

Хj³0, j=1,...,3

Let's move on to the canonical form:

X1+X2+X3-X4=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3=15

Хj³0, j=1,...,5

Zmax=4X1+2X2+X3+0×X4+0×X5

This system restrictions does not have a unit basis, since the additional variable X4 has a coefficient of minus one, and the third constraint was represented by an equation and does not have a basis variable. In order to have a unit basis, we introduce into the corresponding restrictions artificial variables y1 and y2 with positive coefficients (+1).

It should be noted that artificial variables are introduced only for the mathematical formalization of the problem. Therefore, the calculation scheme must be such that artificial variables cannot be included in the final solution among the basic variables. For this purpose, for artificial variables in the objective function, a coefficient M is introduced, denoting a very big number. In practice (especially when solving a problem on a computer), instead of M, they take a specific large number, for example, 10000. Moreover, when solving a problem to the maximum, this coefficient is entered into the objective function with a minus sign, and when solving to a minimum, with a plus sign. Now we will solve the T (M)-problem, the objective function of which contains the objective function of the Z-task and artificial variables with a coefficient ±M, i.e.

T=Z-M S yi, when solving for the maximum of the objective function and

T=Z+M S y, when solving for the minimum of the objective function

In our case:

X1+X2+X3-X4+y1=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3+y2=15

Хj³0, j=1,...,5

Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)

This problem is solved in simplex tables, but for convenience the objective function is divided into 2 lines:

In the first line we write down estimates that do not contain the coefficient M;

The second line contains estimates for each free variable, containing the coefficient M.

The calculation of the elements (scores) of these two lines is carried out according to formula (2). Only difference:

When calculating Z-row estimates, the coefficients Cj included in the Z function must be taken into account;

When calculating M-line estimates, this coefficient is not taken into account, and M is taken out as a common factor.

In order for the T-task and the Z-task to be equal, it is necessary that yi be equal to zero. Therefore, as long as y i is not zero, the resolving column is selected based on the estimates in the second row using the simplex method algorithm.

Only after all y i become equal to zero, further calculation will be carried out using the first index line, i.e. -regular Z-task.

Moreover, when the artificial variable is derived from the basis, we will throw it out of the simplex table, and the next simplex table will not have the former resolving column.

There is a connection between the optimal solutions of the M-problem and the Z-problem, established by the following theorem:

1. If in optimal solution In the M-problem, all artificial variables (y i) are equal to zero, then this solution will be the optimal solution to the Z-problem.

2. If in the optimal solution of the M-problem at least one of the artificial variables is different from zero, then the Z-problem has no solution due to the incompatibility of the system of constraints.

3. If the M-problem turns out to be unsolvable (T®+¥ or -¥), then the original problem is also unsolvable either because of the incompatibility of the system of constraints or because the function Z is unbounded.

Let's create the first simplex table. When solving using the M-method, the resolving column in the M-row can be selected not according to the largest negative estimate in absolute value (when solving for the maximum) and not according to the largest positive estimate (when solving for the minimum), but according to the one that displays Y faster from the basis. IN in this example the resolving column will be the column of the free variable X2 with a score of (-3).

Table 3.1.

First simplex table

Filling the Z-line is carried out according to formula (2):

a00 = 0 × 8– 0 = 0

a01 =0 × 2– 4 = -4

a02 =0 × 1– 2 = -2

a03 =0 × 1– 1 = -1

а02 =0 × 0– 0 = 0

Filling out the M-line:

а¢00 = -М × 8 + (–М) × 15 = -23М

a¢01 = -M × 1 + (–M) × 3 = -4M

а¢02 = -М × 1 + (–М) × 2= -3М

а¢03 = -М × 1+ (–М) × 1 = -2М

а¢04 = -М ×(-1)+ (–М) × 0 = 1М

We take out M as a common factor.

The last column in the resolution line contains 0, so the column of the free variable X4 is transferred without changes.

Table 3.2.

Second simplex table

In the second table we obtain a degenerate solution, since we obtain two identical minimal simplex relations. Therefore, we find the relationship of the elements of the column next to the resolving one to the elements of the resolving column, taking into account the sign.

Table 3.3.

Third simplex table

Now we solve using the usual simplex method.

Table 3.4.

Fourth simplex table

St.P	Cj
B.P.	Ci	ai0	X5	X4
X3				-1
X1
X2			-2	-1
Z

In the evaluation line, all elements are non-negative values, therefore the optimal solution is obtained:

Zmax=15 Xopt(0,7,1,0,0)

Example2

The problem was solved to the minimum (Z®min) of the objective function. At the last iteration we got the following table:

Table 3.5.

Latest simplex table

St.P	Cj
B.P.	Ci	ai0	X1	X3	X4
U1	M	-1/2	-1/2	-1/2	-1
X5		1/2	1/2	1/2
X2		15/2	3/2	1/2
Z			-1
	M	-1/2	-1/2	-1/2	-1

In the T-problem, an optimal solution was obtained, since there are no more positive estimates in the M-row, i.e. the choice of a resolving column is impossible, and U1 is in the basis. In this case, the original problem has no solution due to incompatibility of the system of restrictions.

A necessary condition for using the simplex method is the presence of a reference plan, that is, an acceptable basic solution canonical system equations. To do this, the following conditions must be met:

• the system must have a canonical (step) structure;
• there are only equality constraints;
• the right-hand sides of the constraints are positive;
• the problem variables are positive.

Without these conditions, it is impossible to obtain a reference plan. However, in real problems the listed conditions are not always met.

There is a special method called an artificial basis, which allows you to obtain an initial reference plan in any linear programming problem.

Let the linear programming problem be reduced to standard form:

Let all /? > 0, but some or all of the basis variables are negative, X; 0. Therefore, there is no reference plan.

Let us supplement the constraint equations with artificial variables (we assume that all x j j - 1, P).

Let's introduce T variables (by number of equations): x lM those that are in new system will be basic, and negative X-

As a result, we obtain the following equivalent problem.

Here are the variables x n+i have nothing to do with original problem linear programming. They serve only to obtain a reference plan and are called artificial variables. And the new one

the target function /(.t) is formed for the completeness of the problem.

In an optimal reference design, the artificial variables should be zero. Otherwise, the conditions of the original problem will be violated.

In the initial reference plan, the artificial variables are basic, that is, they are not equal to zero, and in the optimal plan, the artificial variables must be equal to zero. This means that artificial variables should optimally become free. This translation is the main idea of ​​the method: the translation of artificial variables from basic variables to free ones. Let's look at the mechanism of such a translation using an example.

Let's rewrite the ZLP in standard form. To do this, we introduce additional variables x ) , x A, x 5 , x 6 and write the problem in canonical form.

Free variables x, X 2 = 0, in which case the basic variables will take the values ​​x 3 = -5, x 4 = -5, x 5 = 7, x 6 = 9. Since some of the basic variables are negative, therefore there is no reference plan. To obtain the initial reference plan, we introduce the variables x 7, x 8 in the first two constraint equations and formulate an auxiliary problem:

Thus, the initial basis is

Simplex table with artificial basis

	X4

Let's write down the sequences of reference plans.

For the first three increment steps A to are calculated only from artificial variables that are included in the artificial objective function /(x) = x 7 + x 8 with coefficient c, = 1.

In the third step, artificial variables are excluded, since all A to are positive.

So, the simplex method with the introduction of artificial variables includes two stages.

Formation and decision auxiliary task LP with the introduction of artificial variables. The artificial variables in the initial reference design are basic. An artificial objective function includes only artificial variables. Upon receipt of adjacent reference plans, we transfer artificial variables from basic ones to free ones. As a result, the optimal reference plan for the auxiliary problem /(x) = 0 was obtained.

The optimal reference plan for the auxiliary LP problem is the initial reference plan for the main LP problem. The problem is solved for the original objective function /(x) using the usual simplex method.

Notes

• 1. The introduction of artificial variables is required in two cases:
  • a number of basic variables x are negative in canonical form;
  • if it is difficult to reduce to a canonical form, then simply add an artificial variable to any constraint equation.
• 2. Occurring in practice automatic control linear programming problems contain from 500 to 1500 constraints and more than 1000 variables. It is clear that problems of this dimension can only be solved with the help of a computer and a special software. The complexity of the algorithm lies in the fact that:
  • PPP requires a canonical view;
  • PPP for problems of this size requires the use of large computers (and parallel computing), since the simplex method stores the entire table.
• 3. The computational efficiency of the simplex method can be assessed by the following indicators:
  • number of steps (adjacent support plans);
  • machine time costs.

There are such theoretical estimates for standard task linear programming with T restrictions and variables:

• average number of steps * 2 T and lies in the range )