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 included in left side(at 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. IN target function variables 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 is a large 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. Its initial support 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-problems at least one of the artificial variables is different from zero, then the system of constraints original problem incompatible.
When M-task index line simplex table 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 of the 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 using artificial basis task
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 | |||||||||||
The system is solved by entering artificial variables R i with a sign depending on the type of optimum, i.e. to exclude these variables from the basis, the latter are introduced into the objective function with large negative coefficients M, which have the meaning of “penalties” for introducing artificial variables, and into the minimization problem - with positive M. Thus, from the original one we obtain new M-problem(this is why the artificial basis method is also called M-method ).
If there are no artificial variables in the optimal solution to the M-problem, this solution is optimal solution original task. If in the optimal solution of the M-problem at least one of the artificial variables is different from zero, then the system of constraints of the original problem is inconsistent and the original problem is unsolvable.
A simplex table, which is compiled during the solution process using the artificial basis method, is called expanded . It differs from the usual one in that it contains two lines for the goal function: one for the component F, and the other for the component M. When compiling a simplex table, it is assumed that the initial variables are non-basic, and additional(xn+m) and artificial(R i) - basic.
The source table for the "Artificial Basis Method" has next view:
| x 1 | x 2 | ... | xn-1 | x n | b | |
| F | -a 0.1 | -a 0.2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| x n+1 | a 1.1 | a 1.2 | ... | a 1,n-1 | a 1,n | b 1 |
| x n+2 | a 2.1 | a 2.2 | ... | a 2,n-1 | a 2,n | b 2 |
| R i | a i,1 | a i,2 | ... | a i,n-1 | a i,n | b i |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
| M | -∑a i,1 | -∑a i,2 | ... | -∑a i,n-1 | -∑a i,n | -∑b i |
Elements additional line M are calculated as the sum of the corresponding coefficients of equality conditions (conditions in which, after reduction to canonical form, the variables R i are introduced) taken with the opposite sign.
Algorithm of the artificial basis method.
We reduce the LP problem to canonical form
F=a 0.1 x 1 +a 0.2 x 2 +...a 0.n x n +b 0 → max
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1
a 2.1 x 1 +a 2.2 x 2 +...a 2.n x n +x n+2 =b 2
.........................................
a i,1 x 1 +a i,2 x 2 +...a i,n x n +R i =b i
.......................................
a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m
If in the original problem it is necessary to find a minimum, the signs of the coefficients of the objective function F change to the opposite a 0,n = -a 0,n . The signs of the coefficients of limiting conditions with the sign “≥” also change to the opposite. If the condition contains the sign "≤" or "=", the coefficients will be written without changes. To each inequality condition, when moving to the canonical form, we add an additional variable, x n+m, to each i-th equality condition we add an artificial variable R i.
Step 0. Create a simplex table corresponding to the original problem
| x 1 | x 2 | ... | xn-1 | x n | b | |
| F | -a 0.1 | -a 0.2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| x n+1 | a 1.1 | a 1.2 | ... | a 1,n-1 | a 1,n | b 1 |
| x n+2 | a 2.1 | a 2.2 | ... | a 2,n-1 | a 2,n | b 2 |
| R i | a i,1 | a i,2 | ... | a i,n-1 | a i,n | b i |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
| M | -∑a i,1 | -∑a i,2 | ... | -∑a i,n-1 | -∑a i,n | -∑b i |
Step 1. Validation check.
We check the elements of column b (free terms) for positivity; if there are no negative ones among them, then an admissible solution is found (a solution corresponding to one of the vertices of the polyhedron of conditions) and we move on to step 2. If there are negative elements in the column of free terms, then we select among them the maximum in modulus - it specifies the leading row k. In this line we also find the maximum absolute negative element a k,l - it specifies the leading column - l and is leading element. The variable corresponding to the leading row is excluded from the basis, the variable corresponding to the leading column is included in the basis. We recalculate the simplex table according to .
If among the free terms there are negative elements - but in the corresponding line - there are none, then the conditions of the problem are inconsistent and it has no solutions.
If after recalculation there are negative elements left in the column of free terms, then we proceed to the first step; if there are none, then to the second.
Step 2. Check for optimality.
At the previous stage, a feasible solution was found. Let's check it for optimality. If among the elements of the simplex table located in rows M and F (not taking into account the element b 0 - the current value of the objective function and the element -∑ b i) there are no negative ones, then the optimal solution has been found.
2.1 Positivity of string M
If the string M contains negative elements, then the solution requires improvement. We choose among the negative elements of the string M the maximum in modulus (excluding -∑b i)
When a i,l >0, b i >0
We recalculate the simplex table using . If in new table after recalculation, there are negative elements left in line M, go to step 2
If in row M and in the column of free terms all elements are positive, then we go to step 2.2.
2.2 Positivity of string F
We check the elements of the string F for positivity. If there are negative elements (not counting b 0), we choose among the negative elements of the string F the one with the maximum absolute value.
-a 0,l =min(-a 0,i )
l - the column in which it is located will be the leading one. In order to find the leading row, we find the ratio of the corresponding free term and the element from the leading column, provided that they are non-negative.
b k /a k,l =min (b i /a i,l ) for a i,l >0, b i >0
k - the row for which this relation is minimal - the leading one. Element a k,l is the leading (permissive) element. The variable corresponding to the leading row (x k) is excluded from the basis, the variable corresponding to the leading column (x l) is included in the basis.
We recalculate the simplex table using . If in the new table after recalculation there are still negative elements in row F, go to step 2.2
If it is impossible to find the leading row because there are no positive elements in the leading column, then the function in the region of feasible solutions to the problem is not limited - the algorithm terminates.
If all elements in row F and the column of free terms are positive, then the optimal solution has been found.
When the condition contains restrictions such as equality. Let's consider the problem:
max(F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0).
The so-called “artificial variables” R j are introduced into the constraints and into the goal function as follows:
∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j
When introducing artificial variables in the artificial basis method into the objective function, they are assigned a sufficiently large coefficient M, which has the meaning of a penalty for introducing artificial variables. In the case of minimization, artificial variables are added to the goal function with a coefficient M. The introduction of artificial variables is permissible if, in the process of solving the problem, they successively vanish.
A simplex table, which is compiled during the solution process using the artificial basis method, is called extended. It differs from the usual one in that it contains two lines for the goal function: one for the component F = ∑c i x i , and the other for the component M ∑R j Let's consider the procedure for solving the problem using a specific example.
Example 1. Find the maximum of the function F(x) = -x 1 + 2x 2 - x 3 under the restrictions:
2x 1 +3x 2 +x 3 =3,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
Let's use the artificial basis method. Let's introduce artificial variables into the problem constraints
2x 1 + 3x 2 + x 3 + R 1 = 3;
x 1 + 3x 3 + R 2 = 2 ;
Objective function F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).
Let us express the sum R 1 + R 2 from the system of restrictions: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , then F(x) = -x 1 + 2x 2 - x 3 - M(5 - 3x 1 - 3x 2 - 4x 3) .
When compiling the first simplex table (Table 1), we will assume that the original variables x 1 , x 2 , x 3 are non-basic, and the introduced artificial variables are basic. In maximization problems, the sign of the coefficients for non-basic variables in the F- and M-rows is reversed. The sign of the constant value in the M-line does not change. Optimization is carried out first along the M-line. The selection of leading columns and rows, all simplex transformations when using the artificial basis method are carried out as in the usual simplex method.
Maximum by absolute value the negative coefficient (-4) defines the leading column and the variable x 3, which will go into the basis. The minimum simplex ratio (2/3) corresponds to the second row of the table, therefore, the variable R 2 must be excluded from the basis. The leading element is outlined.
In the artificial basis method, artificial variables excluded from the basis are no longer returned to it, so the columns of elements of such variables are omitted. Table 2. decreased by 1 column. Carrying out a recalculation of this table, we move on to table. 3., in which the line M has been reset, it can be removed. After eliminating all artificial variables from the basis, we obtain the admissible basic solution of the original problem, which in the example under consideration is optimal:
x 1 =0; x 2 =7/9; F max =8/9.
If, when eliminating the M-string, the solution is not optimal, then the optimization procedure continues and is performed using the usual simplex method. Let's consider an example in which there are restrictions of all types: ≤,=,≥
Example 2. Find minimum value functions F(x) = 2x 1 + 3x 2 - x 3 under the following restrictions
2x 1 +x 2 -3x 3 ≥6,
x 1 -x 2 +2x 3 =4,
x 1 +x 2 +x 3 ≤5,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
Let's multiply the first of the restrictions by (-1) and introduce additional variables x 4, x 5 and the artificial variable R into the restrictions as follows:
2x 1 -x 2 +3x 3 +x 4 =-6,
x 1 -x 2 +2x 3 +R=4,
x 1 +x 2 +x 3 +x 5 =5,
Let x 4, R and x 5 be basic variables, and x 1, x 2, x 3 – non-basic. Objective function F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).
In the first (Table 4), the coefficients for non-basic variables in the F-row and M-rows do not change sign, since the function is being minimized. The free term in the artificial basis method in the M-row is taken with the opposite sign. The solution corresponding to table. 4 is not valid because there is a negative dummy term.
Let's select the leading column and row in accordance with step 2 of the solution algorithm. After recalculation we get table. 5. Optimization of the solution in the artificial basis method (step 5 of the algorithm) is carried out first along the M-line. As a result, we introduce x 3 into the basis, and exclude the variable R from consideration, reducing the number of columns. After recalculation we get table. 6, which corresponds to the optimal solution of the problem.
Table 4
| basic variables | Free members | Non-basic variables | ||
| x 1 | x 2 | x 3 | ||
| x 4 | -6 | -2 | -1 | 3 |
| R | 4 | 1 | -1 | 2 |
| x 5 | 5 | 1 | 1 | 1 |
| F | 0 | 2 | 3 | -1 |
| M | -4 | -1 | 1 | -2 |
Table 5
| basic variables | Free members | Non-basic variables | ||
| x 4 | x 2 | x 3 | ||
| x 1 | 3 | -1/2 | 1/2 | -3/2 |
| R | 1 | 1/2 | -3/2 | 7/2 |
| x 5 | 2 | 1/2 | 1/2 | 5/2 |
| F | -6 | 1 | 2 | 2 |
| M | -1 | -1/2 | 3/2 | -7/2 |
Table 6
The required minimum of the function F(x) is equal to the free term of the F-row of the table. 6, taken with the opposite sign, since min F(x) = -max(-F(x)); x 4 = x 2 = 0;
x 1 =24/7; x 3 =2/7; x 5 =9/7; F min =46/7;
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Warning
Clear all cells?
Close Clear
Data entry instructions. Numbers are entered as integers (examples: 487, 5, -7623, etc.), decimals (ex. 67., 102.54, etc.) or fractions. The fraction must be entered in the form a/b, where a and b (b>0) are integers or decimal numbers. Examples 45/5, 6.6/76.4, -7/6.7, etc.
Simplex method
Examples of solving ZLP using the simplex method
Example 1. Solve the following linear programming problem:
 |
The right side of the constraints of the system of equations has the form:
Let's write down the current reference plan:
 |
This reference plan is not optimal, since last line there are negative elements. The largest negative element in modulus is (-3), therefore the vector is included in the basis x 
at 
. min(40:6, 28:2)=20/3 corresponds to line 1. The vector emerges from the basis x 3. Let's do Gaussian elimination for the column x 2, given that the leading element corresponds to row 1. Let's reset all elements of this column except the leading element. To do this, add the lines of line 2, 3, 4 with line 1, multiplied by -1/3, 1/6, 1/2, respectively. Next, we divide the line with the leading element by the leading element.
This reference plan is not optimal, since the last row has a negative element (-3), therefore the basis includes the vector x 1 . We determine which vector comes out of the basis. To do this, we calculate 
at 
. min(44/3:11/3, 62/3:5/3)=4 corresponds to line 2. The vector emerges from the basis x 4 . Let's do Gaussian elimination for the column x 1, given that the leading element corresponds to row 2. Let's reset all elements of this column except the leading element. To do this, add lines 1, 3, 4 with line 2 multiplied by 1/11, -5/11, 9/11, respectively. Next, we divide the line with the leading element by the leading element.
The simplex table will take the following form:
The current reference plan is optimal, since in lines 4 under the variables 
there are no negative elements.
The solution can be written like this: 
.
The value of the objective function at this point: F(X)=
.
Example 2. Find the maximum of a function
Solution.
Basis vectors x 4 , x 3 therefore all elements in columns x 4 , x 3, below horizontal line must be zero.
Reset all column elements to zero x 4, except for the leading element. To do this, add row 3 with row 1 multiplied by 4. Reset all elements of the column to zero x 3, except for the leading element. To do this, add line 3 with line 2 multiplied by 1.
The simplex table will take the form:
This reference plan is not optimal, since the last row has a negative element (-11), therefore the basis includes the vector x 2. We determine which vector comes out of the basis. To do this, we calculate 
at 
. Therefore, the objective function is unbounded from above. Those. the linear programming problem is unsolvable.
Examples of solving ZLP using the artificial basis method
Example 1. Find the maximum of a function
Solution. Since the number of basis vectors must be 3, we add an artificial variable, and add this variable multiplied by −M to the objective function, where M is very big number:
 |
The coefficient matrix of the system of equations has the form:
Basis vectors therefore all elements in the columns below the horizontal line must be zero.
Let's reset all elements of the column except the leading element. To do this, add line 5 with line 3 multiplied by -1.
The simplex table will take the form:
This reference plan is not optimal because there are negative elements in the last row. The largest absolute negative element is (-5), therefore the vector is included in the basis. We determine which vector comes out of the basis. To do this, we calculate 
at 
corresponds to row 3. A vector emerges from the basis. Let's do a Gaussian exception for the column, given that the leading element corresponds to row 3. Let's reset all elements of this column, except the leading element. To do this, add the lines line 5 with line 3 multiplied by 1. Next, divide the line with the leading element by the leading element.
The simplex table will take the following form:
This reference plan is not optimal because there are negative elements in the last row. The largest absolute negative element is (-3), therefore the vector is included in the basis. We determine which vector comes out of the basis. To do this, we calculate 
at 
corresponds to row 1. The vector emerges from the basis x 2. Let's do Gaussian elimination for the column x 1 , given that the leading element corresponds to row 1. Let's reset all elements of this column except the leading element. To do this, add the lines of line 2, 3, 4 with line 1, multiplied by 3/2, -1/10, 3/2, respectively. Next, we divide the line with the leading element by the leading element.
The simplex table will take the following form:
This reference plan is not optimal because there are negative elements in the last row. The largest negative element in modulus (-13/2), therefore the basis includes the vector x 3. We determine which vector comes out of the basis. To do this, we calculate 
at 
corresponds to line 3. The vector emerges from the basis x 5 . Let's do Gaussian elimination for the column x 3, given that the leading element corresponds to row 3. Let's reset all elements of this column except the leading element. To do this, add the lines of line 1, 2, 4 with line 3, multiplied by 5/3, 25/9, 65/9, respectively. Next, we divide the line with the leading element by the leading element.
The simplex table will take the following form:
The current reference plan is optimal, since there are no negative elements under the variables in lines 4−5.
The solution to the original problem can be written as follows:
Example 2. Find the optimal plan for a linear programming problem:
The coefficient matrix of the system of equations has the form:
Basis vectors x 4 , x 5 , x 6 therefore all elements in columns x 4 , x 5 , x 6, below the horizontal line should be zero.
Reset all column elements to zero x 4, except for the leading element. To do this, add line 4 with line 1 multiplied by -1. Reset all column elements to zero x 5, except for the leading element. To do this, add line 5 with line 2 multiplied by -1. Reset all column elements to zero x 6, except for the leading element. To do this, add line 5 with line 3 multiplied by -1.
The simplex table will take the form:
In line 5 the elements corresponding to the variables x 1 , x 2 , x 3 , x 4 , x 5 , x 6 are non-negative, and the number located at the intersection of a given row and column x 0 is negative. Then the original problem has no reference plan. Therefore it is undecidable.
In cases where the basis variables are not immediately identified (and they are immediately identified only after bringing the problem to the canonical form, in which there are only inequalities of the type “≤” with non-negative right-hand sides), one can use the so-called artificial basis method , which is essentially a type of simplex method.
Let the problem be reduced to canonical form (1.6), in which in some equations, say in i 1m, i 2nd, …, i s -m, the basic variables are not clearly identified. Let's add to these equations artificial variablesx m +1 , x m +2 , …, x m + s , and into the target function - the terms ± Mx m +1 , ± Mx m +2 , …, ± Mx m + s , Where M >>1 (M - a fairly large positive number) and “±” is “+” if the problem is solved for min, and “±” is “-” if the problem is solved for max. This results in a new problem called additional or auxiliary .
For example, an auxiliary (additional) problem with artificial variables for problem (1.5) will have the form
c 1 x 1 +c 2 x 2 +…+c n x n +Mx n + m +1 +Mx n + m +2 +…+Mx n +2 m ®min
Similarly, if problem (2.1) is solved for max and it is necessary to introduce artificial variables into all constraints, then we obtain the following auxiliary problem:
c 1 x 1 +c 2 x 2 +…+c n x n -Mx n +1 -Mx n +2 -…-Mx n + m ®max
(5.1)
5.1.1. If( , , …, , , …, ) optimal solution to an auxiliary problem, Where , …, - values of artificial variables, , , …, - the values of the variables in the original problem in canonical form , That =…= =0 And ( , , …, ) -optimal solution to the original problem. In this case, the values of the objective function of the original and auxiliary problems coincide.
From here we get that to solve a linear programming problem using the artificial basis method it is enough:
1. Bring the problem to canonical form.
2. If the problem in canonical form does not have a basis of unit vectors, then create an auxiliary problem (if the problem in canonical form has a basis of unit vectors, then the problem is solved using the usual simplex method).
3. Solve the auxiliary problem, and if ( , , …, , , …, ) is the optimal solution to the auxiliary problem, where x 1 , x 2 , …, x m - main and additional variables (from the problem in canonical form), x m +1 , x m +2 , …, x m + s - artificial variables then ( , , …, ) - solution to the problem in canonical form. The optimal value of the objective function of the auxiliary problem is equal to optimal value original task.
In this case, the usual simplex method with some of its own features is applied to the auxiliary problem:
1. Since the objective function of the auxiliary problem has terms with coefficients ± M , then estimates D k look like ± M , and M - a fairly large number. Therefore, for ≠0 the sign of D k is actually determined by the sign at . In this regard, in the simplex table at the initial stage (while the basis includes artificial variables), instead of one row D k write down two lines and , and when applying the optimality criterion, focus only on the line .
2. Artificial variables, as they are removed from the basis, are excluded from further consideration.
3. After all artificial variables are removed from the basis, the coefficients D k at M will be equal to zero, only the row remains in the table =D k .
Example. Solve the example from the previous paragraph using the artificial basis method.
Solution. We remind you of the task:
3x 1 +x 2 +2x 3 ® max(min)
1. Let’s bring the problem to canonical form:
3x 1 +x 2 +2x 3 ® max(min)
2. The basis in the form of a unit vector includes only the vector at x 4, that is, the variable in the second equation. We introduce artificial variables into the first and third equations of the constraint system x 6 and x 7:
They will be included in the objective function with coefficients M or - M depending on whether the problem is solved with min or max.
Let's solve the problem to the maximum. Then the auxiliary task is the following:
3x 1 +x 2 +2x 3 -Mx 6 -Mx 7®max
3. We solve the resulting auxiliary problem using simplex tables:
| Basis | WITH b | Free member | -3 | -M | -M | q 2 | q 3 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |||||||
| x 6 | -M | -1 | min | ||||||||||
| x 4 | - | ||||||||||||
| x 7 | -M | -1 | |||||||||||
| -1 | -2 | ||||||||||||
| -8 | -2 | -3 |
Here D 2 =-2 M -1, D 3 =-3 M -2. Coefficients at M written in the line . We have that D 2<0 и D 3 <0, то есть для переменных x 2 and x 3 the optimality criterion is violated. Therefore, we will introduce into the basis x 2 or x 3. Which of these variables, and instead of which of the artificial ones (instead of x 6 or instead x 7), determined using columns q 2 and q 3. At the intersection of a column q 2 and lines and numbers 2 and 4, respectively, mean that if included in the basis x 2 the value of the function will increase by - q 2 D 2 =4 M +2, and if included in the basis x 3 the value of the function will increase by - q 3 D 3 =3 M +2<-q 2 D 2 . Therefore, we include in the basis x 2 (which provides a greater increase in the function and ultimately speeds up the process of solving the problem). Since min =2 is reached in the line x 6, then we exclude from the basis x 6. We build a new simplex table, which already contains a column with an artificial variable x 6 is missing (crossed out) because it is an artificial variable x 6 is excluded from the further process. In the new table the coefficient at x 2 in the first line (which now corresponds to the new basis variable x 2) is equal to 1, and in the second it is equal to zero. Therefore, we rewrite the first two rows into the new table from the old one. In order for the line x 7 at x 2 get 0, from string x 7 in the old table we subtract the new first. We get the following, next, table:
| Basis | WITH b | Free member | -3 | -M | -M | q 1 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | ||||||
| x 2 | -1 | - | ||||||||||
| x 4 | ||||||||||||
| x 7 | -M | -1 | -1 | min | ||||||||
| -4 | -2 |
Since D k <0 только для одного значения k =1, namely, D 1 =-2 M +2<0 (напоминаем, что M - a fairly large number, so -2 M <2 и D 1 <0), то ищем только отношения q 1 . The minimum of these relations is achieved in the line x 7: min =2. Therefore, the artificial variable is excluded from the basis, and instead it is included in the basis x 1 .
Artificial variables are now excluded from the basis. Therefore, we further work with the usual simplex table, in which the new third row (corresponding to the variable x 1) is obtained by dividing the old third line by 2. Then we add this new third to the old first and subtract from the old second. As a result, in the new table in the column x 1 will appear 0, 0 and 1 respectively:
| Basis | WITH b | Free member | -3 | ||||
| x 1 | x 2 | x 3 | x 4 | x 5 | |||
| x 2 | 3/2 | -1/2 | |||||
| x 4 | 3/2 | 1/2 | |||||
| x 7 | -3 | -1/2 | -1/2 | ||||
| D k | -2 |
In the resulting table D k ³0 for everyone k X 0 =(2; 4; 0) is the optimal solution in which the value of the objective function is -2 ( x 4 is not taken into account in the final answer, since it is an additional variable and is not included in the original problem).
Let's solve the problem to the minimum (min). Then the auxiliary task is the following:
3x 1 +x 2 +2x 3 -Mx 6 -Mx 7®max
As above, we solve the resulting auxiliary problem using a simplex table:
| Basis | WITH b | Free member | -3 | M | M | q 2 | q 3 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |||||||
| x 6 | M | -1 | min | ||||||||||
| x 4 | - | ||||||||||||
| x 7 | M | -1 | |||||||||||
| -1 | -2 | ||||||||||||
| -1 |
The optimality criterion is violated for variables x 2 and x 3: D 2 =2 M -1>0, D 3 =3 M -2>0. Because - q 2 D 2 =-4 M +2 is superior in absolute value to - q 3 D 3 =-3 M +2, then we include in the basis x 2. In this case, min =2 is achieved in the line x 6 , and exclude from the basis x 6. The transition to a new table is similar to the transition when solving a max problem:
| Basis | WITH b | Free member | -3 | -M | -M | q 1 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | ||||||
| x 2 | -1 | - | ||||||||||
| x 4 | ||||||||||||
| x 7 | -M | -1 | -1 | min | ||||||||
| -1 | -1 |
Now D 1 >0. Therefore, the transition to a new table is similar to the corresponding transition when solving a problem on max: the basis is entered x 1 instead x 7:
| Basis | WITH b | Free member | -3 | q 3 | q 5 | ||||
| x 1 | x 2 | x 3 | x 4 | x 5 | |||||
| x 2 | 3/2 | -1/2 | 8/3 | - | |||||
| x 4 | 3/2 | 1/2 | 4/3 | ||||||
| x 7 | -3 | -1/2 | -1/2 | - | - | ||||
| D k | -2 | -4/3 | -4 |
We have D 3 =1>0 and D 5 =1>0. Since |- q 5 D 5 |=|- q 3 D 3 |, then we introduce into the basis x 5 (instead of x 4): first we multiply the 2nd line by 2, and then add the new second line, multiplied by ½, to the first and third (in fact, we add the old second line to the first and third):
In the resulting table D k £0 for everyone k =1, 2, …, 5, that is, the optimality criterion is met. That's why X 0 =(4; 6; 0) is the optimal solution for which the value of the objective function is -6.
Answer: F min =-6, the minimum is reached at the point X 2 =(4; 6; 0);
F max =-2, the maximum is reached at the point X 1 =(2; 4; 0).
5.2. Exercise. Solve the corresponding linear programming problems from Exercises 1.3 artificial basis method.
Duality theory
