Solving by the simplex method, examples of solutions. An example of solving a direct and dual problem using the simplex method
. Simplex method algorithm
Example 5.1. Solve the following problem linear programming 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 the found basic solution does not contain negative components, it is admissible.
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 basic and one free variable that must be swapped in the simplex table to move to the new “improved” one. basic 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: compiling 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 characteristic).
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 the 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's bring it to canonical form by introducing into each of the inequality constraints an additional non-negative variable, 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.
An example of solving a problem using the simplex method, as well as an example of solving a dual problem, is considered.
The task
To sell three groups of goods, a commercial enterprise has three types of limited material and monetary resources in the amount of b 1 = 240, b 2 = 200, b 3 = 160 units. At the same time, for the sale of 1 group of goods for 1 thousand rubles. commodity turnover, the resource of the first type is consumed in the amount of a 11 = 2 units, the resource of the second type in the amount of a 21 = 4 units, the resource of the third type in the amount of a 31 = 4 units. For the sale of 2 and 3 groups of goods for 1 thousand rubles. turnover is consumed according to the resource of the first type in the amount of a 12 = 3, a 13 = 6 units, the resource of the second type in the amount of a 22 = 2, a 23 = 4 units, the resource of the third type in the amount of a 32 = 6, a 33 = 8 units . Profit from the sale of three groups of goods for 1 thousand rubles. turnover is respectively c 1 = 4, c 2 = 5, c 3 = 4 (thousand rubles). Determine the planned volume and structure of trade turnover so that the profit of the trading enterprise is maximized.
To the direct problem of turnover planning, solved by simplex method, compose dual problem linear programming.
Install conjugate pairs of variables direct and dual problems.
According to conjugate pairs of variables, from the solution of the direct problem we obtain solution of the dual problem, in which it is produced resource assessment, spent on the sale of goods.
Solving the problem using the simplex method
Let x 1, x 2, x 3 be the number of goods sold, in thousand rubles, of 1, 2, 3 groups, respectively. Then mathematical model the task has the form:F = 4 x 1 + 5 x 2 + 4 x 3 ->max
0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
We solve the simplex method.
We introduce additional variables x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 to transform the inequalities into equalities.
Let's take x 4 = 240 as a basis; x 5 = 200; x 6 = 160.
We enter the data into simplex table
Simplex table No. 1
Objective function:
0 240 + 0 200 + 0 160 = 0
We calculate estimates using the formula:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Since there are negative estimates, the plan is not optimal. Lowest score:
We introduce the variable x 2 into the basis.
We define a variable emerging from the basis. To do this, we find the smallest non-negative ratio for the x2 column.
= 26.667
Smallest non-negative: Q 3 = 26.667. We derive the variable x 6 from the basis
Divide the 3rd line by 6.
From the 1st line, subtract the 3rd line, multiplied by 3
From the 2nd line, subtract the 3rd line, multiplied by 2
We calculate:
We get new table:
Simplex table No. 2
Objective function:
0 160 + 0 440/3 + 5 80/3 = 400/3
We calculate estimates using the formula:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Since there is a negative estimate Δ 1 = - 2/3, the plan is not optimal.
We introduce the variable x 1 into the basis.
We define a variable emerging from the basis. To do this, we find the smallest non-negative ratio for the column x 1.
Smallest non-negative: Q 3 = 40. We derive the variable x 2 from the basis
Divide the 3rd line by 2/3.
From the 2nd line, subtract the 3rd line, multiplied by 8/3
We calculate:
We get a new table:
Simplex table No. 3
Objective function:
0 160 + 0 40 + 4 40 = 160
We calculate estimates using the formula:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Since there are no negative ratings, the plan is optimal.
The solution of the problem:
Answer
x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160That is, it is necessary to sell the first type of goods in the amount of 40 thousand rubles. Products of types 2 and 3 do not need to be sold. In this case, the maximum profit will be F max = 160 thousand rubles.
Solution of the dual problem
The dual problem has the form:
Z = 240 y 1 + 200 y 2 + 160 y 3 ->min
Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}
We introduce additional variables y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 to transform the inequalities into equalities.
Conjugate pairs of variables of the direct and dual problems have the form:
From the last simplex table No. 3 of the direct problem, we find the solution to the dual problem:
Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Liked? Add to bookmarks
Solving problems using the simplex method: online examples
Task 1. The company produces bathroom shelves in two sizes - A and B. Sales agents estimate that up to 550 shelves can be sold on the market per week. Each type A shelf requires 2 m2 of material, and each type B shelf requires 3 m2 of material. The company can receive up to 1200 m2 of material per week. To manufacture one shelf of type A, 12 minutes of machine time are required, and to manufacture one shelf of type B - 30 minutes; The machine can be used 160 hours a week. If the profit from the sale of shelves of type A is 3 monetary units, and from shelves of type B - 4 monetary units. units, then how many shelves of each type should be produced per week?
Task 2. Solve a linear programming problem using the simplex method. 
Task 3. The company produces 3 types of products: A1, A2, A3, using two types of raw materials. The costs of each type of raw material per unit of production, the reserves of raw materials for the planning period, as well as the profit from a unit of production of each type are known.
- How many items of each type must be produced to maximize profit?
- Determine the status of each type of raw material and its specific value.
- Determine the maximum interval for changes in inventories of each type of raw material, within which the structure of the optimal plan, i.e. The production nomenclature will not change.
- Determine the quantity of products produced and the profit from production when increasing the stock of one of the scarce types of raw materials to the maximum possible (within the given range of output) value.
- Determine the intervals of change in profit from a unit of production of each type at which the resulting optimal plan will not change.
Task 4. Solve a linear programming problem simplex method:
Task 5. Solve a linear programming problem using the simplex method: 
Task 6. Solve the problem using the simplex method, considering as the initial reference plan the plan given in the condition: 
Task 7. Solve the problem using the modified simplex method.
To produce two types of products A and B, three types of technological equipment are used. To produce a unit of product A, equipment of the first type uses a1=4 hours, equipment of the second type a2=8 hours, and equipment of the third type a3=9 hours. To produce a unit of product B, equipment of the first type uses b1=7 hours, equipment of the second type b2=3 hours, and equipment of the third type b3=5 hours.
Equipment of the first type can work for the production of these products for no more than t1=49 hours, equipment of the second type for no more than t2=51 hours, equipment of the third type for no more than t3=45 hours.
The profit from the sale of a unit of finished product A is ALPHA = 6 rubles, and product B is BETTA = 5 rubles.
Draw up a plan for the production of products A and B, ensuring maximum profit from their sale.
Task 8. Find optimal solution dual simplex method 
Purpose of the service. The service is intended for online solutions Linear programming problems (LPP) using the simplex method in the following notation forms:
- in the form of a simplex table (Jordan transformation method); basic recording form;
- modified simplex method; in column form; in line form.
Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is stored in Word file and Excel.
In this case, do not take into account restrictions like x i ≥ 0. If there are no restrictions in the task for some x i, then the ZLP must be converted to the KZLP, or use this service. When solving, the usage is automatically determined M-method(simplex method with artificial basis) and two-stage simplex method.The following are also used with this calculator:
Graphical method for solving ZLP
Solution of the transport problem
Solving a matrix game
Using the service in online mode you can determine the price of a matrix game (lower and upper bounds), check the availability saddle point, find a solution to a mixed strategy using the following methods: minimax, simplex method, graphical (geometric) method, Brown’s method.
Extremum of a function of two variables
Dynamic programming problems
Distribute 5 homogeneous lots of goods between three markets so as to obtain maximum income from their sale. Income from sales in each market G(X) depends on the number of sold batches of product X and is presented in the table.
| Product volume X (in lots) | Income G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Simplex method algorithm includes the following steps:
- Drawing up the first basic plan. Transition to the canonical form of the linear programming problem by introducing non-negative additional balance variables.
- Checking the plan for optimality. If there is at least one index line coefficient less than zero, then the plan is not optimal and needs to be improved.
- Determining the leading column and row. Of the negative coefficients of the index line, the largest one is selected absolute value. Then the elements of the free member column of the simplex table are divided into elements of the same sign of the leading column.
- Building a new reference plan. The transition to a new plan is carried out as a result of recalculation of the simplex table using the Jordan-Gauss method.
If it is necessary to find the extremum of the objective function, then we're talking about about search minimum value(F(x) → min , see an example of a solution for minimizing a function) and maximum value ((F(x) → max , see an example of a solution for maximizing a function)
An extreme solution is achieved on the boundary of the region of feasible solutions at one of the vertices of the corner points of the polygon, or on the segment between two adjacent corner points.
Fundamental Theorem of Linear Programming. If the ZLP objective function reaches an extreme value at some point in the region of feasible solutions, then it takes this value at the corner point. If the ZLP objective function reaches an extreme value at more than one corner point, then it takes the same value at any of the convex linear combinations of these points.
The essence of the simplex method. Movement to the optimum point is carried out by moving from one corner point to the neighboring one, which brings closer and faster to X opt. Such a scheme for enumerating points, called the simplex method, suggested by R. Danzig.
Corner points are characterized by m basic variables, so the transition from one corner point to a neighboring one can be accomplished by changing only one basic variable in the basis to a variable from a non-basis.
Implementation of the simplex method in force various features and problem statements, LP has various modifications.
The construction of simplex tables continues until the optimal solution is obtained. How can you use a simplex table to determine that the solution to a linear programming problem is optimal?
If last line(values of the objective function) does not contain negative elements, therefore, it will find the optimal plan.
Remark 1. If one of the basic variables is equal to zero, then the extreme point corresponding to such a basic solution is degenerate. Degeneracy occurs when there is ambiguity in the choice of the guide line. You may not notice the degeneracy of the problem at all if you choose another line as a guide. In case of ambiguity, the row with the lowest index should be selected to avoid looping.
Remark 2. Let at some extreme point all simplex differences be non-negative D k ³ 0 (k = 1..n+m), i.e. an optimal solution is obtained and there exists A k - a non-basis vector for which D k = 0. Then the maximum is achieved at least at two points, i.e. there is an alternative optimum. If we introduce this variable x k into the basis, the value of the objective function will not change.
Remark 3. The solution to the dual problem is in the last simplex table. The last m components of the vector of simplex differences (in the columns of balance variables) are the optimal solution to the dual problem. Meaning target functions The direct and dual problems coincide at optimal points.
Remark 4. When solving the minimization problem, the vector with the largest positive simplex difference is introduced into the basis. Next, the same algorithm is applied as for the maximization problem.
If the condition “It is necessary that type III raw materials be completely consumed” is specified, then the corresponding condition is an equality.
