Tabular simplex method
One of the methods for solving optimization problems ( usually associated with finding the minimum or maximum) linear programming called . Simplex method includes a whole group of algorithms and methods for solving linear programming problems. One of these methods, which involves recording the source data and recalculating them in a special table, is called tabular simplex method.
Let us consider the algorithm of the tabular simplex method using the example of the solution production task , which boils down to finding a production plan that ensures maximum profit.
Input data for the simplex method problem
The company produces 4 types of products, processing them on 3 machines.
Time standards (min./piece) for processing products on machines are specified by matrix A:
The machine operating time fund (min.) is specified in matrix B:
Profit from the sale of each unit of product (rub/piece) is given by matrix C:
Purpose of the production task
Draw up a production plan that will maximize the profit of the enterprise.
Solving the problem using the tabular simplex method
(1) Let us denote by X1, X2, X3, X4 the planned number of products of each type. Then the desired plan: ( X1, X2, X3, X4)
(2) Let's write down the plan constraints in the form of a system of equations:
(3) Then the target profit is:
That is, the profit from fulfilling the production plan should be maximum.
(4) To solve the resulting problem on conditional extreme, we replace the system of inequalities with the system linear equations by introducing additional non-negative variables into it ( X5, X6, X7).
(5) Let's accept the following reference plan:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Let's enter the data into simplex table:
In the last line we enter the coefficients of the objective function and its value itself with the opposite sign;
(7) Select in last line greatest (modulo) a negative number.
Let's calculate b = N / Items_of_the_selected_column
Among the calculated values of b we choose least.
The intersection of the selected column and row will give us the resolving element. We change the basis to a variable corresponding to the resolving element ( X5 to X1).
- The resolving element itself turns to 1.
- For elements of the resolution line – a ij (*) = a ij / RE ( that is, we divide each element by the value of the resolving element and obtain new data).
- For elements of the resolution column, they are simply reset to zero.
- We recalculate the remaining elements of the table using the rectangle rule.
a ij (*) = a ij – (A * B / RE)
As you can see, we take the current cell being recalculated and the cell with the resolving element. They form opposite corners of the rectangle. Next, we multiply the values from the cells of the other 2 corners of this rectangle. This work ( A * B) divide by the resolving element ( RE). And subtract from the current cell being recalculated ( a ij) what happened. We get a new value - a ij (*).
(9) Check the last line again ( c) on presence of negative numbers. If they are not there, the optimal plan has been found, go to last stage solving the problem. If there is, the plan is not yet optimal, and the simplex table needs to be recalculated again.
Since in the last line we again have negative numbers, we begin a new iteration of calculations.
(10) Since there are no negative elements in the last line, this means that we have found the optimal production plan! Namely: we will produce those products that have moved to the “Basis” column - X1 and X2. We know the profit from the production of each unit of output ( matrix C). It remains to multiply the found production volumes of products 1 and 2 with profit per 1 piece, we get the final ( maximum! ) profit for a given production plan.
ANSWER:
X1 = 32 pcs., X2 = 20 pcs., X3 = 0 pcs., X4 = 0 pcs.
P = 48 * 32 + 33 * 20 = 2,196 rub.
Galyautdinov R.R.
© Copying of material is permissible only if a direct hyperlink to
To simplify the solution process, the initial data of a linear programming problem when solving it using the simplex method are written into special simplex tables. Therefore, one of the modifications of the simplex method is called tabular simplex method. Linear programming problem in canonical form:
a 1.1 x 1 +a 1.2 x 2 +...a 1.n x n + x n+1 =b 1
The source table for the task looks like this:
| 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 |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
x 1 , x 2 , x n - initial variables, x n+1 , x n+2 , x n+m - additional variables. We took all additional variables as basic, and the original variables as non-basic(additional ones are written in the first column of the simplex table and the original ones in the first row). At each iteration, the elements of the simplex table are recalculated according to certain .
Algorithm of the simplex 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 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 “≤”, the coefficients will be written without changes.
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 |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
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 simplex table, located in line F (not taking into account the element b 0 - the current value of the objective function) are not negative, then the optimal solution has been found.
If string F contains negative elements, then the solution requires improvement. Among the negative elements of the string F, we choose the one with the maximum absolute value (excluding the value of the function b 0)
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 new table after recalculation, there are negative elements left in line F, go to step 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.
Simplex table transformation rules.
When creating a new simplex table, the following changes occur:
- Instead of the basic variable x k we write x l ; instead of the non-basic variable x l we write x k.
- the leading element is replaced by the inverse value a k,l "= 1/a k,l
- all elements of the leading column (except a k,l) are multiplied by -1/a k,l
- all elements of the leading line (except a k,l) are multiplied by 1/a k,l
- the remaining elements of the simplex table are transformed according to the formula a i,j "= a i,j - a i,l x a k,j / a k,l
The transformation scheme for elements of a simplex table (except for the leading row and leading column) is called a “rectangle” scheme.
Converted element a i,j and the three factors corresponding to it are precisely the vertices of the “rectangle”.
. Simplex method algorithm
Example 5.1. Solve the following linear programming problem using the simplex method:
Solution:
I iteration:
x3, x4, x5, x6 x1,x2. Let's express the basic variables in terms of free ones:
Let us reduce the target function to next view:
Based on the obtained problem, we will form the initial simplex table:
Table 5.3
Original simplex table
Evaluative Relationships |
||||
According to the definition of the basic solution, the free variables are equal to zero, and the values of the basic variables are equal to the corresponding values of the free numbers, i.e.:
Stage 3: checking the compatibility of the PAP restrictions system.
At this iteration (in Table 5.3), the sign of inconsistency of the constraint system (sign 1) is not identified (i.e. there is no line with a negative free number (except for the line of the objective function) in which there would not be at least one negative element (i.e. . negative coefficient for a free variable)).
At this iteration (in Table 5.3), the sign of unboundedness of the objective function (sign 2) was not identified (i.e., there is no column with a negative element in the row of the objective function (except for the column of free numbers) in which there would not be at least one positive element) .
Since what was found basic solution does not contain negative components, then it is acceptable.
Stage 6: optimality check.
The found basic solution is not optimal, since according to the optimality criterion (sign 4) there should be no negative elements in the line of the objective function (the free number of this line is not taken into account when considering this criterion). Therefore, according to the simplex method algorithm, we move on to stage 8.
Since the found basic solution is admissible, we will search for the resolving column according to the following scheme: we determine the columns with negative elements in the row of the objective function (except for the column of free numbers). According to Table 5.3, there are two such columns: column “ x1" and column " x2" From such columns, the one that contains the smallest element in the row of the target function is selected. She will be the permissive one. Column " x2" contains the smallest element (–3) compared to the column " x1
To determine the resolving line, we find the positive estimated ratios of free numbers to the elements of the resolving column; the line that corresponds to the smallest positive evaluation ratio is accepted as resolved.
Table 5.4
Original simplex table
In Table 5.4, the smallest positive evaluative relationship corresponds to the line “ x5", therefore, it will be permissive.
The element located at the intersection of the enabling column and the enabling row is accepted as enabling. In our example, this is the element that is located at the intersection of the line “ x5" and columns " x2».
The resolving element shows one basis and one free variable that must be swapped in the simplex table to move to a new “improved” basis solution. IN in this case these are variables x5 And x2, in the new simplex table (Table 5.5) we swap them.
9.1. Transformation of the resolving element.
The resolution element of Table 5.4 is converted as follows:
We enter the resulting result into a similar cell in Table 5.5.
9.2. Resolution string conversion.
We divide the elements of the resolving row of table 5.4 by the resolving element of this simplex table, the results fit into similar cells of the new simplex table (table 5.5). Transformations of resolution string elements are given in Table 5.5.
9.3. Conversion of the resolution column.
We divide the elements of the resolution column of Table 5.4 by the resolution element of this simplex table, and the result is taken with the opposite sign. The results obtained fit into similar cells of the new simplex table (Table 5.5). Transformations of the elements of the resolution column are given in Table 5.5.
9.4. Transformation of the remaining elements of the simplex table.
The transformation of the remaining elements of the simplex table (i.e., elements not located in the resolving row and resolving column) is carried out according to the “rectangle” rule.
For example, consider transforming an element located at the intersection of the line " x3" and columns "", let's conditionally denote it " x3" In Table 5.4, we mentally draw a rectangle, one vertex of which is located in the cell whose value we are transforming (i.e. in the cell “ x3"), and the other (diagonal vertex) is in a cell with a resolving element. The other two vertices (of the second diagonal) are uniquely determined. Then the transformed value of the cell " x3" will be equal to the previous value of this cell minus the fraction, in the denominator of which is the resolving element (from Table 5.4), and in the numerator is the product of two other unused vertices, i.e.:
« x3»: .
The values of other cells are converted similarly:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
As a result of these transformations, a new simplex table was obtained (Table 5.5).
II iteration:
Stage 1: drawing up a simplex table.
Table 5.5
Simplex tableII iterations
Estimated relationship |
||||
| ||||
|
|
Stage 2: determination of the basic solution.
As a result of the simplex transformations, a new basic solution was obtained (Table 5.5):
As you can see, with this basic solution the value of the objective function = 15, which is greater than with the previous basic solution.
The inconsistency of the system of restrictions in accordance with feature 1 in Table 5.5 has not been identified.
Stage 4: checking the boundedness of the objective function.
The unboundedness of the objective function in accordance with criterion 2 in Table 5.5 is not revealed.
Stage 5: checking the admissibility of the found basic solution.
The found basic solution in accordance with criterion 4 is not optimal, since the line of the objective function of the simplex table (Table 5.5) contains a negative element: –2 (the free number of this line is not taken into account when considering this characteristic). Therefore, we move on to stage 8.
Stage 8: determination of the resolving element.
8.1. Definition of the resolution column.
The found basic solution is acceptable; we determine the columns with negative elements in the row of the objective function (except for the column of free numbers). According to Table 5.5, there is only one such column: “ x1" Therefore, we accept it as permitted.
8.2. Definition of an enable string.
According to the obtained values of positive evaluative relations in Table 5.6, the minimum is the relation corresponding to the line “ x3" Therefore, we accept it as permitted.
Table 5.6
Simplex tableII iterations
Estimated relationship |
||||
3/1=3 – min |
||||
Stage 9: transformation of the simplex table.
Transformations of the simplex table (Table 5.6) are performed in the same way as in previous iteration. The results of transformations of elements of the simplex table are given in Table 5.7.
III iteration
Based on the results of simplex transformations of the previous iteration, we compose a new simplex table:
Table 5.7
Simplex tableIII iterations
Estimated relationship |
||||
| ||||
|
|
Stage 2: determination of the basic solution.
As a result of the simplex transformations, a new basic solution was obtained (Table 5.7):
Stage 3: checking the compatibility of the system of restrictions.
The inconsistency of the system of restrictions in accordance with feature 1 in Table 5.7 has not been identified.
Stage 4: checking the boundedness of the objective function.
The unboundedness of the objective function in accordance with criterion 2 in Table 5.7 is not revealed.
Stage 5: checking the admissibility of the found basic solution.
The found basic solution in accordance with criterion 3 is acceptable, since it does not contain negative components.
Stage 6: checking the optimality of the found basic solution.
The found basic solution in accordance with criterion 4 is not optimal, since the line of the objective function of the simplex table (Table 5.7) contains a negative element: –3 (the free number of this line is not taken into account when considering this characteristic). Therefore, we move on to stage 8.
Stage 8: determination of the resolving element.
8.1. Definition of the resolution column.
The found basic solution is acceptable; we determine the columns with negative elements in the row of the objective function (except for the column of free numbers). According to Table 5.7, there is only one such column: “ x5" Therefore, we accept it as permitted.
8.2. Definition of an enable string.
According to the obtained values of positive evaluative relations in Table 5.8, the minimum is the relation corresponding to the line “ x4" Therefore, we accept it as permitted.
Table 5.8
Simplex tableIII iterations
Estimated relationship |
||||
5/5=1 – min |
||||
Stage 9: transformation of the simplex table.
Transformations of the simplex table (Table 5.8) are performed in the same way as in the previous iteration. The results of transformations of elements of the simplex table are given in Table 5.9.
IV iteration
Stage 1: construction of a new simplex table.
Based on the results of simplex transformations of the previous iteration, we compose a new simplex table:
Table 5.9
Simplex tableIV iterations
Estimated relationship |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Stage 2: determination of the basic solution.
As a result of the simplex transformations, a new basic solution was obtained; according to Table 5.9, the solution is as follows:
Stage 3: checking the compatibility of the system of restrictions.
The inconsistency of the system of restrictions in accordance with feature 1 in Table 5.9 has not been identified.
Stage 4: checking the boundedness of the objective function.
The unboundedness of the objective function in accordance with criterion 2 in Table 5.9 is not revealed.
Stage 5: checking the admissibility of the found basic solution.
The found basic solution in accordance with criterion 3 is acceptable, since it does not contain negative components.
Stage 6: checking the optimality of the found basic solution.
The found basic solution in accordance with feature 4 is optimal, since there are no negative elements in the line of the objective function of the simplex table (Table 5.9) (the free number of this line is not taken into account when considering this feature).
Stage 7: checking the alternativeness of the solution.
The solution found is unique, since there are no zero elements in the line of the objective function (Table 5.9) (the free number of this line is not taken into account when considering this feature).
Answer: optimal value objective function of the problem under consideration =24, which is achieved at.
Example 5.2. Solve the above linear programming problem provided that objective function is minimized:
Solution:
I iteration:
Stage 1: formation of the initial simplex table.
Original problem linear programming is given in standard form. Let us bring it to canonical form by introducing an additional non-negative variable into each of the inequality constraints, i.e.
In the resulting system of equations, we take as allowed (basic) variables x3, x4, x5, x6, then the free variables will be x1,x2. Let us express the basic variables in terms of free ones.
If the problem statement contains restrictions with the ≥ sign, then they can be reduced to the form ∑a ji b j by multiplying both sides of the inequality by -1. Let us introduce m additional variables x n+j ≥0(j =1,m) and transform the restrictions to the form of equalities
(2)
Let us assume that all initial task variables x 1 , x 2 ,..., x n – non-basic. 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 a “+” sign, as in (2), then all the coefficients in front of the variables x i and the free term b j are entered into the simplex table without changes. When maximizing the goal function, the coefficients are entered in the bottom row of the simplex table with opposite signs. The free terms in the simplex table determine the solution to the problem.
The algorithm for solving the problem is as follows:
1st step.
The members of the free members column are viewed. If they are all positive, then an admissible basic solution has been found and one should proceed to step 5 of the algorithm, which corresponds to finding the optimal solution. If the initial simplex table has negative free terms, then the solution is not valid and you should go to step 2.
2nd step.
| To find an admissible solution, it is carried out, and it is necessary to decide which of the non-basic variables to include in the basis and which variable to remove from the basis. | Table 1. | basic variables | |||||
| x 1 | x 2 | ... | Free members under restrictions | ... | Non-basic variables|||
| x n+1 | b 1 | x l | a 12 | ... | a 1l | ... | a 1n |
| x n+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | a r1 | a r2 | ... | a rl | ... | arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | a m1 | a m2 | ... | a ml | ... | a mn |
| F(x)max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
To do this, select any of the negative elements of the column of free terms (let it be b 2 leading, or resolving. If there are no negative elements in the row with a negative free term, then the system of constraints is inconsistent and the problem has no solution.
At the same time, the variable that is the first to change sign when the selected NP x l increases is excluded from the BP. This will be x n+r, the index r of which is determined from the condition
those. the variable that has 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 line corresponding to the variable x n+r is called leading, or allowing. The element of the simplex table a rl, located 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 regular simplex table.
3rd step. A new simplex table is calculated, the elements of which are recalculated from the elements of the simplex table previous step
and are marked with a prime, i.e. b" j , a" ji , c" i , F" 0 . The elements are recalculated using the following formulas:
First, the new simplex table will fill in the row and column that were leading in the previous 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. The 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 constructed 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 determined uniquely. To find a new element a" ji, the product of the elements of the opposite diagonal divided by the leading element is subtracted from element a ji (this is indicated by the “-” sign next to the cell). Elements b" j, (j≠r) and c" i are recalculated in the same way. (i≠l).
5th step.
We believe that an admissible 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 ones (with the exception of the free term), then you need to move on to another basic solution. When maximizing the objective function, the basis includes one of the non-basic variables (for example x l), the column of which corresponds to the maximum absolute value
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 relation: leading element.
The row corresponding to x n+r is called leading, and the element of the simplex table a rl, standing at the intersection of the leading row and the leading column, is called
6th step.
according to the rules outlined in step 3. The procedure continues until an optimal solution is found or it is concluded that it does not exist. During solution optimization, if all elements in the leading column are non-positive, then the leading row cannot be selected. In this case, the function in the region of feasible solutions to the problem is not bounded above and F max ->&∞. If, at the next step of searching for an extremum, one of the basic variables becomes equal to zero, then the corresponding basic solution is called degenerate. In this case, a so-called looping occurs, characterized by the fact that
certain frequency
the same combination of BP begins to repeat (the value of the function F is preserved) and it is impossible to move to a new admissible basic solution. Looping is one of the main disadvantages of the simplex method, but it is relatively rare. In practice, in such cases, they usually refuse to enter into the basis the variable whose column corresponds to the maximum absolute value of the negative coefficient in the goal function, and randomly select a new basis solution.
Example 1. Solve the problem
A graphical interpretation of the solution to the problem is presented in Fig. 2. The maximum value of the goal function is achieved at the vertex of the ODZP with coordinates . Let's solve the problem using simplex tables. Let's multiply the second constraint by (-1) and introduce additional variables to bring the inequalities to the form of equalities, then
We take the initial variables x 1 and x 2 as non-basic, and consider the additional x 3, x 4 and x 5 as basic and compose 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 previous algorithm. The following simplex table. 3 defines an admissible basic solution; the vertex of the ODZP in Fig. 1 corresponds to it. 2 The leading element is outlined and selected in accordance with the 5th step of the problem solving algorithm. Table 4 matches optimal solution tasks, therefore: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Rice. 2. Graphic solution tasks
