Nature is renewed, a new year begins, the living awakens on the day of the holiday...
Here is a manual (not applet) solution of two problems by the simplex method (similar to applet solution) with detailed explanations in order to understand the algorithm for solving problems with the simplex method. The first problem contains inequality signs only " ≤ " (a problem with an initial basis), the second one can contain signs " ≥ ", " ≤ " or " = " (a problem with an artificial basis), they are solved in different ways.
Simplex method, solution of a problem with an initial basis
1)Simplex method for a problem with an initial basis (all signs of constraint inequalities are " ≤ ").
Let's write the problem in canonical form, i.e. we rewrite the inequality constraints as equalities, adding balance sheets variables:
This system is a system with a basis (basis s 1, s 2, s 3, each of them is included in only one equation of the system with a coefficient of 1), x 1 and x 2 are free variables. Problems for which the simplex method is used must have the following two properties: - the system of constraints must be a system of equations with a basis; -free terms of all equations in the system must be non-negative.
The resulting system is a system with a basis and its free terms are non-negative, so we can apply simplex method. Compile the first simplex table (Iteration 0) for solving the problem on simplex method, i.e. a table of coefficients of the objective function and a system of equations for the corresponding variables. Here "BP" means the column of basic variables, "Solution" - the column of the right parts of the equations of the system. The solution is not optimal, because there are negative coefficients in the z-line.
simplex method iteration 0
|
Attitude |
|||||||
To improve the solution, let's move on to the next iteration simplex method, we get the following simplex tableau. For this you need to choose enable column, i.e. a variable that will enter the basis at the next iteration of the simplex method. It is chosen by the largest negative coefficient in the z-row (in the maximum problem) - in the initial iteration of the simplex method, this is the column x 2 (coefficient -6).
Then choose permission string, i.e. a variable that will leave the basis at the next iteration of the simplex method. It is selected by the smallest ratio of the "Decision" column to the corresponding positive elements of the resolving column ("Ratio" column) - in the initial iteration, this is row s 3 (coefficient 20).
Permissive element is located at the intersection of the resolving column and the resolving row, its cell is highlighted in color, it is equal to 1. Therefore, at the next iteration of the simplex method, the variable x 2 will replace s 1 in the basis. Note that the relation is not searched in the z-string, a dash "-" is put there. If there are identical minimum ratios, then any of them is chosen. If all coefficients in the resolution column are less than or equal to 0, then the solution to the problem is infinite.
Let's fill in the following table "Iteration 1". We will get it from the "Iteration 0" table. The purpose of further transformations is to turn the x2 enable column into a single column (with one instead of the enable element and zeros instead of the rest of the elements).
1) Calculating row x 2 of the "Iteration 1" table. First, we divide all members of the resolving row s 3 of the "Iteration 0" table by the resolving element (it is equal to 1 in this case) of this table, we get the row x 2 in the "Iteration 1" table. Because the resolving element in this case is equal to 1, then the row s 3 of the "Iteration 0" table will match the row x 2 of the "Iteration 1" table. Row x 2 of the "Iteration 1" table we got 0 1 0 0 1 20, the remaining rows of the "Iteration 1" table will be obtained from this row and the rows of the "Iteration 0" table as follows:
2) Calculation of the z-row of the "Iteration 1" table. In place of -6 in the first row (z-row) in column x2 of the "Iteration 0" table, there should be a 0 in the first row of the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by 6, we get 0 6 0 0 6 120 and add this row with the first row (z - row) of the "Iteration 0" table -4 -6 0 0 0 0, we get -4 0 0 0 6 120. Zero 0 appeared in the x 2 column, the goal was achieved. The elements of the permission column x 2 are highlighted in red.
3) Calculation of row s 1 of the "Iteration 1" table. In place of 1 in s 1 row of the "Iteration 0" table should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -1, we get 0 -1 0 0 -1 -20 and add this row with s 1 - the row of the "Iteration 0" table 2 1 1 0 0 64, we get the row 2 0 1 0 -1 44. The required 0 is obtained in the x 2 column.
4) Calculation of row s 2 of the "Iteration 1" table. In place of 3 in s 2 row of the "Iteration 0" table should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -3, we get 0 -3 0 0 -3 -60 and add this row with s 1 - the row of the "Iteration 0" table 1 3 0 1 0 72, we get the row 1 0 0 1 -3 12. The required 0 is obtained in the x 2 column. The x 2 column in the "Iteration 1" table has become single, it contains one 1 and the rest 0.
The rows of the "Iteration 1" table are obtained according to the following rule:
New Row = Old Row - (Old Row Permission Factor)*(New Row).
For example, for the z-line we have:
Old z-string (-4 -6 0 0 0 0) -(-6)*New z-string -(0 -6 0 0 -6 -120) = New z-string (-4 0 0 0 6 120).
For the following tables, recalculation of table elements is done in a similar way, so we omit it.
simplex method iteration 1
|
Attitude |
|||||||
Permissive column x 1 , permissive row s 2 , s 2 leaves the basis, x 1 enters the basis. In exactly the same way, we obtain the remaining simplex tables until a table with all positive coefficients in the z-row is obtained. This is a sign of an optimal table.
simplex method iteration 2
|
Attitude |
|||||||
Resolving column s 3 , resolving row s 1 , s 1 leaves the basis, s 3 enters the basis.
simplex method iteration 3
|
Attitude |
|||||||
In the z-row, all coefficients are non-negative, therefore, the optimal solution x 1 = 24, x 2 = 16, z max = 192 is obtained.
Find the largest value of a function
x 1 ≥ 0 x 2 ≥ 01. The free members of the system must be non-negative.
This condition has been met.
2. Each constraint of the system must be an equation.
| x 1 + | 2 | x2 | ≤ | 4 | ||
| x 1 | - | x2 | ≥ | 1 | ||
| x 1 | + | x2 | ≤ | 8 |
| x 1 + | 2 | x2 | + | S1 | = | 4 | |||||||||
| x 1 | - | x2 | - | S2 | = | 1 | |||||||||
| x 1 | + | x2 | + | S3 | = | 8 |
S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. The introduced variables S 1 , S 2 , S 3 are called balance variables.
3. Finding the initial basis and the value of the function F, which corresponds to the found initial basis.
What is a basis?
A variable is called basic for a given equation if it enters the given equation with factor one and is not included in the remaining equations of the system (provided that there is a non-negative number on the right side of the equation).
If every equation has a basis variable, then the system is said to have a basis.
Variables that are not basic are called free variables.
What is the idea behind the simplex method?
Each basis corresponds to a single value of the function. One of them is the largest value of the function F.
We will move from one basis to another.
The next basis will be chosen in such a way as to obtain the value of the function F not less than the existing one.
Obviously, the number of possible bases for any problem is not very large.
Therefore, sooner or later, the answer will be received.
How is the transition from one basis to another carried out?
It is more convenient to record the solution in the form of tables. Each row of the table is equivalent to the equation of the system. The highlighted line consists of the coefficients of the function (see the table below). This allows you not to rewrite variables every time, which saves a lot of time.
In the selected line, select the largest positive coefficient (you can choose any positive one).
This is necessary in order to obtain the value of the function F not less than the existing one.
Column selected.
For positive coefficients of the selected column, we calculate the ratio Θ and choose the smallest value.
This is necessary so that after the transformation the column of free terms remains non-negative.
Row selected.
The element that will be the base element is defined. Next, we count.
Does our system have a basis?
| x 1 + | 2 | x2 | + | S1 | = | 4 | |||||||||
| x 1 | - | x2 | - | S2 | = | 1 | |||||||||
| x 1 | + | x2 | + | S3 | = | 8 |
There is no basis, i.e. we can't start a solution.
Will have to find him. To do this, we solve an auxiliary problem.
Let's add an artificial variable to the equation where there is no base variable.
| x 1 + | 2 | x2 | + | S1 | = | 4 | ||||||||||||
| x 1 | - | x2 | - | S2 | + | R1 | = | 1 | ||||||||||
| x 1 | + | x2 | + | S3 | = | 8 |
R 1 ≥ 0. The introduced variable R 1 is called an artificial variable.
We introduce the function W into consideration and look for its smallest value.
The algorithm for finding the smallest value of the function W has only one difference from the algorithm discussed above.
| x 1 | x2 | S1 | S2 | S3 | R1 | St. member | Θ |
| 1 | 2 | 1 | 0 | 0 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 0 | -1 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 8 | 8: 1 = 8 |
| -1 | 1 | 0 | 1 | 0 | 0 | W - 1 | |
| 0 | 3 | 1 | 1 | 0 | -1 | 3 | |
| 1 | -1 | 0 | -1 | 0 | 1 | 1 | |
| 0 | 2 | 0 | 1 | 1 | -1 | 7 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
We equate the free variables to zero. Verbally find the values of the basic variables. (see table)
The function W is expressed in terms of free variables. Therefore, the value of the function W, for a given basis, can be found instantly. (see highlighted line of the table)
| x 2 = 0 S 2 = 0 R 1 = 0 x 1 = 1 S 1 = 3 S 3 = 7 |
=> W - 0 = 0 => W = 0 |
Among the coefficients of the selected line, there are no negative ones. Therefore, the smallest value of the function W is found.
A basis is obtained without using an artificial variable. Which is what was required.
The column corresponding to the artificial variable can be crossed out.
As a result, our system looks like this:
| 3 | x2 | + | S1 | + | S2 | = | 3 | |||||||||
| x 1 | - | x2 | - | S2 | = | 1 | ||||||||||
| 2 | x2 | + | S2 | + | S3 | = | 7 |
| F | = | - | x 1 | + | 3 | x2 |
|
|
Linear programming is a mathematical modeling technique designed to optimize the use of limited resources. LP has been successfully applied in the military field, industry, agriculture, transport industry, economics, healthcare system and even in the social sciences. The widespread use of this method is also supported by highly efficient computer algorithms that implement this method. Linear programming algorithms are the basis for optimization algorithms for other, more complex types of models and operations research (OR) problems, including integer, non-linear, and stochastic programming.
Optimization problem is an economic and mathematical problem, which consists in finding the optimal (maximum or minimum) value of the objective function, and the values of the variables must belong to a certain range of acceptable values.
In its most general form, a linear programming problem is mathematically written as follows:
where X = (x 1 , x 2 , ... , x n ) ; W– range of admissible values of variables x 1 , x 2 , ... , x n ;f(X) is the target function.
In order to solve an optimization problem, it is sufficient to find its optimal solution, i.e. indicate that 
for any .
An optimization problem is unsolvable if it does not have an optimal solution. In particular, the maximization problem will be unsolvable if the objective function f(X) unbounded from above on the admissible set W.
Methods for solving optimization problems depend both on the type of objective function f(X), and on the structure of the admissible set W. If the objective function in the problem is a function n variables, then the solution methods are called methods of mathematical programming.
The characteristic features of linear programming problems are as follows:
optimality indicator f(X) is a linear function of solution elements X = (x 1 , x 2 , ... , x n ) ;
restrictive conditions imposed on possible solutions have the form of linear equalities or inequalities.
Linear programming problem is called the problem of operations research, the mathematical model of which has the form:
(2)
(3)
(4)
(5)
In this case, the system of linear equations (3) and inequalities (4), (5), which determines the admissible set of solutions to the problem W, is called system of restrictions linear programming problems, and a linear function f(X) called objective function or optimality criterion .
Valid Solution is a collection of numbers plan ) X = (x 1 , x 2 , ... , x n ) satisfying the constraints of the problem. Optimal solution is a plan in which the objective function takes its maximum (minimum) value.
If the mathematical model of a linear programming problem has the form:
then they say that the task is presented in canonical form .
Any linear programming problem can be reduced to a linear programming problem in canonical form. To do this, in the general case, you need to be able to reduce the problem of maximization to the problem of minimization; move from inequality constraints to equality constraints and replace variables that do not obey the non-negativity condition. The maximization of some function is equivalent to the minimization of the same function taken with the opposite sign, and vice versa.
The rule for reducing a linear programming problem to a canonical form is as follows:
if in the original problem it is required to determine the maximum of a linear function, then you should change the sign and look for the minimum of this function;
if the right side of the restrictions is negative, then this restriction should be multiplied by -1;
if there are inequalities among the constraints, then by introducing additional non-negative variables they are transformed into equalities;
if some variable x j has no sign restrictions, then it is replaced (in the objective function and in all restrictions) by the difference between two new non-negative variables: x 3 = x 3 + - x 3 - , where x 3 + , x 3 - ≥ 0 .
Example 1. Reduction to the canonical form of a linear programming problem:
min L = 2x 1 + x 2 -x 3 ; 2x 2 -x 3 ≤ 5; x 1 + x 2 -x 3 ≥ -1; 2x 1 -x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.
Let us introduce equalizing variables into each equation of the constraint system x 4 , x 5 , x 6 . The system will be written in the form of equalities, and in the first and third equations of the system of constraints, the variables x 4 , x 6 are entered in the left side with the "+" sign, and in the second equation the variable x 5 entered with a "-" sign.
2x 2 -x 3 + x 4 = 5; x 1 + x 2 -x 3 -x 5 = -1; 2x 1 -x 2 + x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.
The free terms in the canonical form must be positive, for this we multiply the last two equations by -1:
2x 2 -x 3 + x 4 = 5; -x 1 -x 2 + x 3 + x 5 = 1; -2x 1 + x 2 -x 6 = 3.
Simplex method for solving linear programming problems.
The simplex method algorithm finds the optimal solution by considering a limited number of valid basic solutions. The simplex method algorithm always starts with some feasible basic solution and then tries to find another feasible basic solution that "improves" the value of the objective function. This is possible only if the increase in any zero (non-basic) variable leads to an improvement in the value of the objective function. But in order for a non-basic variable to become positive, one of the current basic variables must be made zero, i.e. convert to non-basic. This is necessary so that the new solution contains exactly m basic variables. In accordance with the terminology of the simplex method, the chosen null variable is called introduced (to the basis), and the basis variable to be deleted - excluded (from basis).
Two rules for choosing input and exclusive variables in the simplex method will be called optimality condition And admissibility condition . Let us formulate these rules, and also consider the sequence of actions performed when implementing the simplex method.
Optimality condition. The input variable in the maximization (minimization) problem is a nonbasic variable that has the largest negative (positive) coefficient in target-string. If in target-line contains several such coefficients, then the choice of the input variable is made arbitrarily. The optimal solution is reached when target-line, all coefficients for non-basic variables will be non-negative (non-positive).
Admissibility condition. Both in the maximization problem and in the minimization problem, the basis variable is chosen as the excluded one, for which the ratio of the value of the right side of the constraint to the positive coefficient of the leading column is minimal. If there are several basic variables with this property, then the choice of the excluded variable is performed arbitrarily.
We present an algorithm for solving the linear programming problem of finding the maximum using simplex tables.
F \u003d s 1 x 1 + s 2 x 2 + ... + s n x n max
x 1 0, x 2 0,…, x n 0.
1st step. We introduce additional variables and write down the resulting system of equations and a linear function in the form of an extended system.
F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.
2nd step. We compose the initial simplex tableau.
|
Variables |
Main and additional variables |
free members (solution) |
Estimated attitude |
|||||||
3rd step. We check the fulfillment of the optimality criterion - the presence of negative coefficients in the last row. If there are none, then the solution is optimal and F * =co , basic variables are equal to the corresponding coefficients b j , non-basic variables are equal to zero, i.e. X * =(b 1 ,b 2 ,…, b m , 0, …, 0).
4th step. If the optimality criterion is not met, then the largest negative coefficient in absolute value in the last (evaluative) row determines the resolution column s.
To determine the permissive string, we calculate the estimated ratios 
and fill in the last column of the table.
The estimated ratio of the i-th line is equal to
if b i and a is have different signs;
if b i =0 and a is<0;
if a is =0;
0 if b i =0 and a is >0;
In the column of estimated relations we find the minimum element min 
which defines the enable string g.
If there is no minimum, then the problem does not have a finite optimum I and is unsolvable.
At the intersection of the permissive row and column is the permissive element a gs .
5th step. We build the following table. For this
Let's move on to the third step.
M-method Sometimes, when solving the LLP, in the matrix of coefficients for unknown constraints, there are no single columns from which the identity matrix can be composed, i.e. there is a problem in the choice of basic variables, or the initial solution is invalid. In such cases, use artificial basis method (M - method). In all constraints where there are no basic variables, we introduce artificial variables. Artificial variables are introduced into the objective function with a coefficient (- M) for tasks on max and with a coefficient (+ M) for tasks on min, where M is a sufficiently large positive number. Then the extended problem is solved according to the rules of the simplex method. If all artificial variables turn out to be equal to zero, i.e. are excluded from the basis, then either the optimal solution of the original problem is obtained, or the original problem is solved further and its optimal solution is found or its unsolvability is established. If at least one of the artificial variables turns out to be different from zero, then the original problem has no solution.
To enable the applet to run on your computer, do the following - click Start>Control Panel>Programs>Java. In the Java Control Panel window, select the Security tab, click the Edit Site List button, the add button and paste the path to this page from the browser address bar into the free field. Next, press the OK button, then restart the computer.
To run the applet, click on the "Simplex" button. If the "Simplex" button is not visible above this line, Java is not installed on the computer.
After clicking on the "Simplex" button, the first window is displayed for entering the number of variables and the number of restrictions of the problem on the simplex method.
After pressing the “ok” button, a window is displayed for entering the remaining data of the task for the simplex method: display mode (decimal fractions or ordinary), type of task criterion min or max , input of objective function coefficients and coefficients of the constraint system with signs “≤”, “ ≥ ” or “ = ”, there is no need to introduce restrictions of the form x i ≥ 0, takes them into account in the algorithm.
After clicking on the “Solve” button, a window with the results of solving the problem is displayed on .The window consists of two parts, in the upper part there is a text field containing a description of the reduction of the original problem to the canonical form, which is used to compile the first simplex table. At the bottom of the window, in a tabbed pane, there are simplex tables of each iteration with a small text field at the bottom indicating the enable column, enable row, and other information that makes the program educational. In the tab with the optimal (last) table, the obtained optimal solution of the problem is shown in the text field.
Please send any bugs and comments about the applet to [email protected] or call 8 962 700 77 06, for which we will be very grateful to you.
M-method program
Program for solving the transport problem
Here is a manual (not applet) solution of two problems by the simplex method (similar to applet solution) with detailed explanations in order to understand the problem solving algorithm. The first problem contains inequality signs only " ≤ " (a problem with an initial basis), the second one can contain signs " ≥ ", " ≤ " or " = " (a problem with an artificial basis), they are solved in different ways.
Simplex method, solution of a problem with an initial basis
1)Simplex method for a problem with an initial basis (all signs of constraint inequalities are " ≤ ").
Let's write the problem in canonical form, i.e. we rewrite the inequality constraints as equalities, adding balance sheets variables:
This system is a system with a basis (basis s 1, s 2, s 3, each of them is included in only one equation of the system with a coefficient of 1), x 1 and x 2 are free variables. Problems for which the simplex method is used must have the following two properties:
-system of constraints must be a system of equations with a basis;
-free terms of all equations in the system must be non-negative.
The resulting system is a system with a basis and its free terms are non-negative, so the simplex method can be applied. Compile the first simplex table (Iteration 0), i.e. a table of coefficients of the objective function and a system of equations for the corresponding variables. Here "BP" means the column of basic variables, "Solution" - the column of the right parts of the equations of the system. The solution is not optimal, because there are negative coefficients in the z-line.
iteration 0
BP |
Solution | Attitude | |||||
To improve the solution, we move on to the next iteration and obtain the following simplex table. For this you need to choose enable column, i.e. a variable that will enter the basis at the next iteration. It is selected by the largest negative coefficient in the z-row (in the maximum problem) - in the initial iteration, this is the x 2 column (coefficient -6).
Then choose permission string, i.e. a variable that will leave the basis on the next iteration. It is selected by the smallest ratio of the "Decision" column to the corresponding positive elements of the resolving column ("Ratio" column) - in the initial iteration, this is row s 3 (coefficient 20).
Permissive element is located at the intersection of the resolving column and the resolving row, its cell is highlighted in color, it is equal to 1. Therefore, at the next iteration, the variable x 2 will replace s 3 in the basis. Note that the relation is not searched in the z-string, a dash "-" is put there. If there are identical minimum ratios, then any of them is chosen. If all coefficients in the resolution column are less than or equal to 0, then the solution to the problem is infinite.
Let's fill in the following table "Iteration 1". We will get it from the "Iteration 0" table. The purpose of further transformations is to turn the x2 enable column into a single column (with one instead of the enable element and zeros instead of the rest of the elements).
1) Calculating row x 2 of the "Iteration 1" table. First, we divide all members of the resolving row s 3 of the "Iteration 0" table by the resolving element (it is equal to 1 in this case) of this table, we get the row x 2 in the "Iteration 1" table. Because the resolving element in this case is equal to 1, then the row s 3 of the "Iteration 0" table will match the row x 2 of the "Iteration 1" table. Row x 2 of the "Iteration 1" table we got 0 1 0 0 1 20, the remaining rows of the "Iteration 1" table will be obtained from this row and the rows of the "Iteration 0" table as follows:
2) Calculation of the z-row of the "Iteration 1" table. In place of -6 in the first row (z-row) in column x2 of the "Iteration 0" table, there should be a 0 in the first row of the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by 6, we get 0 6 0 0 6 120 and add this row with the first row (z - row) of the "Iteration 0" table -4 -6 0 0 0 0, we get -4 0 0 0 6 120. Zero 0 appeared in the x 2 column, the goal was achieved. The elements of the permission column x 2 are highlighted in red.
3) Calculation of row s 1 of the "Iteration 1" table. In place of 1 in s 1 row of the "Iteration 0" table should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -1, we get 0 -1 0 0 -1 -20 and add this row with s 1 - the row of the "Iteration 0" table 2 1 1 0 0 64, we get the row 2 0 1 0 -1 44. The required 0 is obtained in the x 2 column.
4) Calculation of row s 2 of the "Iteration 1" table. In place of 3 in s 2 row of the "Iteration 0" table should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -3, we get 0 -3 0 0 -3 -60 and add this row with s 2 - the row of the "Iteration 0" table 1 3 0 1 0 72, we get the row 1 0 0 1 -3 12. The required 0 is obtained in the x 2 column. The x 2 column in the "Iteration 1" table has become single, it contains one 1 and the rest 0.
The rows of the "Iteration 1" table are obtained according to the following rule:
New Row = Old Row - (Old Row Permission Factor)*(New Row).
For example, for the z-line we have:
Old z-string (-4 -6
0
0
0
0)
-(-6)*New permission string -(0-6
0
0
-6
-120)
=New z-row(-4
0
0
0
6
120)
.
For the following tables, recalculation of table elements is done in a similar way, so we omit it.
iteration 1
| Solution | Attitude | ||||||
Permissive column x 1 , permissive row s 2 , s 2 leaves the basis, x 1 enters the basis. In exactly the same way, we obtain the remaining simplex tables until a table with all positive coefficients in the z-row is obtained. This is a sign of an optimal table.
Iteration 2
| Solution | Attitude | ||||||
Resolving column s 3 , resolving row s 1 , s 1 leaves the basis, s 3 enters the basis.
Iteration 3
| Solution | Attitude | ||||||
In the z-row, all coefficients are non-negative, therefore, the optimal solution x 1 = 24, x 2 = 16, z max = 192 is obtained.
Simplex method, solution of a problem with an artificial basis
2) Let's solve the problem with an artificial basis (at least one sign of inequalities-restrictions " ≥ " or " = ").
We write the problem in canonical form (in the form of a system of equations, which requires the simplex method), for this we introduce two variables x 3 ≥ 0 and x 4 ≥ 0, we get:
The constraint system offers only one valid basic variable x 4 , only it is included in only one equation in the third with a coefficient of 1, so we add artificial variables R 1 ≥ 0 and R 2 ≥ 0 to the first and second equations So that the simplex method can be applied system constraint equations must be a system with a basis, i.e. in each equation there must be a variable with a coefficient of 1, which is included in only one equation of the system, in our case it is R 1, R 2 and x 4. We got the so-called M-problem:
This system is a system with a basis in which R 1 , R 2 and x 4 are basic variables, and x 1 , x 2 and x 3 are free variables, the free terms of all equations are non-negative. Therefore, the simplex method can be applied to solve the problem. Let's write the initial simplex table:
iteration 0
| Solution | Attitude | |||||||
| -16 | ||||||||
The line "Evaluation" has been added to the table for problems with an artificial basis. It is obtained by summing the corresponding coefficients of rows with artificial variables (R) with the opposite sign. It will be present in the table as long as at least one of the artificial variables is in the basis. By the absolute value of the negative coefficient of the "Rating" row, the resolution column is determined while it is in the table. When the "Score" row leaves the table (there are no artificial variables in the basis), the resolving column will be determined by the z-row, as in the problem with the initial basis. In this table, the resolving column is x 2 , it is selected according to the largest negative estimate (-7). The resolving row R 2 is chosen according to the smallest ratio of the "Solution" column to the corresponding positive elements of the resolving column, as in the problem without artificial variables. This means that at the next iteration the variable x 2 will go from free to basic, and the variable R 2 from basic to free. We write the following simplex table:
Resolving column x 1 , resolving row R 1 , R 1 leaves the basis, x 1 enters the basis. After that, there are no artificial variables left in the basis, so there is no “Score” row in the following table:
iteration 2
| Solution | Attitude | |||||||
Next, the resolution column is selected by the z-row. In the z-row, all coefficients are non-negative except for the coefficient at the artificial variable R 1 , which does not affect the optimality when the artificial variables are out of the basis. Therefore, the optimal solution x 1 = 6/5 is obtained; x 2 \u003d 3/5; zmax = 72/5.
Special cases of application of the simplex method
1) When the line (if a two-dimensional linear programming problem is considered, and in the general case a hyperplane) representing the objective function is parallel to the line (hyperplane) corresponding to one of the constraint inequalities (which is fulfilled at the optimum point as an exact equality), the objective function takes one and is also an optimal value on some set of points on the boundary of the region of feasible solutions. These solutions are called alternative optimal solutions. The presence of alternative solutions can be determined from the optimal simplex table. If there are zero coefficients of non-basic variables in the z-row of the optimal table, then there are alternative solutions.
2) If in the resolving column of the simplex table all the coefficients are less than or equal to zero, then it is impossible to choose the resolving row, in this case the solution is unlimited.
3) If the constraints of a linear programming problem are inconsistent (i.e., they cannot be executed simultaneously), then the problem has no feasible solutions. Such a situation cannot arise if all the inequalities that make up the system of constraints are of type " ≤ " with non-negative right-hand sides, because in this case, additional variables may constitute a valid solution. For other types of constraints, artificial variables are used. If the problem has a solution, then there are no artificial variables (R i) in the optimal table in the basis. If they are there, then the problem has no solutions.
If there are restrictions with the sign ≥ in the condition of the problem, then they can be reduced to the form ∑a ji b j by multiplying both parts of the inequality by -1. We introduce m additional variables x n+j ≥0(j =1,m ) and transform the constraints to the form of equalities
(2)
Let us assume that all initial variables of the problem x 1 , x 2 ,..., x n are nonbasic. Then the additional variables will be basic, and a particular solution to the system of constraints has the form
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Since in this case the value of the goal function F 0 = 0 , we can represent F(x) as follows:
F(x)=∑c i x i + F 0 =0 (4)
The initial simplex table (simplex table 1) is compiled based on equations (2) and (4). If the additional variables x n+j are preceded by the “+” sign, as in (2), then all the coefficients before the variables x i and the free term b j are entered into the simplex table without change. The coefficients of the goal function during its maximization are entered in the bottom line of the simplex table with opposite signs. Free members in the simplex table determine the solution of the problem.
The algorithm for solving the problem is as follows:
1st step. The elements of the free members column are looked up. If they are all positive, then an acceptable basic solution has been found and one should proceed to step 5 of the algorithm, which corresponds to finding the optimal solution. If there are negative free terms in the initial simplex tableau, then the solution is not valid and you should go to step 2.
2nd step. To find a feasible solution, is carried out, while it is necessary to decide which of the non-basic variables to include in the basis and which variable to withdraw from the basis.
Table 1.
| basis variables | Free members in restrictions | Nonbasic variables | |||||
| x 1 | x2 | ... | x l | ... | x n|||
| xn+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| xn+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | a m1 | a m2 | ... | a ml | ... | amn |
| F(x)max | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
To do this, choose any of the negative elements of the column of free members (let it be b 2 leading, or allowing. If there are no negative elements in the row with a negative free member, then the system of restrictions is inconsistent and the problem has no solution.
At the same time, the variable that is the first to change sign with an increase in the selected NP x l is excluded from the BP. This will be x n+r , whose index r is determined from the condition
those. the variable that corresponds to the smallest ratio of the free term to the element of the selected leading column. This relationship is called simplex relation. Only positive simplex relations should be considered.
The string corresponding to the variable x n+r is called leading, or allowing. The element of the simplex table a rl , which is at the intersection of the leading row and the leading column, is called the leading or resolving element. Finding the leading element ends the work with each next simplex tableau.
3rd step. A new simplex table is calculated, the elements of which are recalculated from the elements of the simplex table of the previous step and marked with a prime, i.e. b" j , a" ji , c" i , F" 0 . The elements are recalculated according to the following formulas:
First, the row and column that were leading in the previous simplex table will be filled in the new simplex table. Expression (5) means that the element a "rl in place of the leading element is equal to the reciprocal of the element of the previous simplex table. The elements of the row a ri are divided by the leading element, and the elements of the column a jl are also divided by the leading element, but are taken with the opposite sign. Elements b" r and c" l are calculated according to the same principle.
The rest of the formulas can be easily written using .
The rectangle is built according to the old simplex table in such a way that one of its diagonals is formed by the recalculated (a ji) and leading (a rl) elements (Fig. 1). The second diagonal is uniquely determined. To find a new element a "ji, the product of elements of the opposite diagonal, divided by the leading element, is subtracted from element a ji (this is indicated by the sign" - "at the cell). Similarly, elements b" j, (j≠r) and c" i are recalculated, (i≠l).
4th step. The analysis of a new simplex table starts from the 1st step of the algorithm. The action continues until a feasible basic solution is found, i.e. all elements of the free members column must be positive.
5th step. We believe that an acceptable basic solution has been found. We look at the coefficients of the line of the goal function F(x) . A sign of the optimality of a simplex table is the non-negativity of the coefficients for non-basic variables in the F-row.
Rice. 1. Rectangle rule
If among the coefficients of the F-row there are negative (with the exception of the free term), then you need to go to another basic solution. When maximizing the goal function, the basis includes that of the non-basic variables (for example, x l), whose column corresponds to the maximum absolute value of the negative coefficient c l in the bottom row of the simplex table. This allows you to select the variable whose increase leads to an improvement in the goal function. The column corresponding to the variable x l is called the leading column. At the same time, that variable x n+r is excluded from the basis, the index r of which is determined by the minimum simplex ratio:
The row corresponding to x n+r is called the leading row, and the element of the simplex table a rl , which is at the intersection of the leading row and the leading column, is called leading element.
6th step. according to the rules set out in the 3rd step. The procedure continues until an optimal solution is found or it is concluded that it does not exist.
If in the process of optimizing the solution in the leading column all elements are nonpositive, then the leading row cannot be selected. In this case, the function in the domain of admissible solutions of the problem is not bounded from above and F max ->&∞.
If at the next step of the search for an extremum one of the basic variables becomes equal to zero, then the corresponding basic solution is called degenerate. In this case, the so-called looping occurs, which is characterized by the fact that the same combination of BP begins to repeat with a certain frequency (the value of the function F is preserved in this case) and it is impossible to switch to a new acceptable basic solution. Looping is one of the main drawbacks of the simplex method, but it is relatively rare. In practice, in such cases, one usually refuses to enter into the basis the variable whose column corresponds to the maximum absolute value of the negative coefficient in the goal function, and a random choice of a new basic solution is made.
Example 1. Solve a problem
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1.2 ≥0)
Simplex method and give a geometric interpretation of the solution process.
Graphical interpretation of the solution of the problem is shown in fig. 2. The maximum value of the goal function is reached at the top of the ODZP with coordinates . Let's solve the problem using simplex tables. We multiply the second constraint by (-1) and introduce additional variables to bring the inequalities to the form of equalities, then
The initial variables x 1 and x 2 are taken as non-basic, and the additional x 3 , x 4 and x 5 are considered basic and we compile a simplex table (simplex table 2). The solution corresponding to the simplex table. 2, is not valid; the leading element is outlined and selected in accordance with step 2 of the algorithm above. The next simplex tab. 3 defines an admissible basic solution; 2 The leading element is outlined and selected in accordance with the 5th step of the algorithm for solving the problem. Tab. 4 corresponds to the optimal solution of the problem, therefore: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F max = 20.
Rice. 2. Graphical solution of the problem
