11.4. DUAL SIMPLEX METHOD
From the results of the previous paragraphs it follows that to obtain a solution to the original problem, one can go to the dual one and, using estimates of its optimal plan, determine the optimal solution to the original problem.
The transition to the dual problem is not necessary, since if we consider the first simplex table with a unit additional basis, it is easy to notice that the original problem is written in the columns, and the dual one is written in the rows.
As was shown, when solving a direct problem at any iteration, the difference, i.e. magnitude -coefficient of the variable, is equal to the difference between the right and left sides of the corresponding constraint of the dual problem. If, when solving a direct problem with a maximized objective function, iteration does not lead to an optimal solution, then at least for one variable and only at the optimum for all difference .
Considering this condition taking into account duality, we can write
.
Thus, if, That . This means that when the solution to the direct problem is suboptimal, the solution to the dual problem is not feasible. On the other side 
at . It follows that the optimal solution to the direct problem corresponds to an admissible solution to the dual problem.
This made it possible to develop a new method for solving linear programming problems, which first produces an unacceptable, but “better than optimal” solution (in the usual simplex method, one first finds acceptable, But suboptimal solution). The new method, called dual simplex method, ensures the fulfillment of the conditions for the optimality of the solution and its systematic “approximation” to the region of feasible solutions. When the resulting solution turns out to be feasible, the iterative process of calculations ends, since this solution is also optimal.
The dual simplex method makes it possible to solve linear programming problems whose constraint systems, with a positive basis, contain free terms of any sign. This method allows you to reduce the number of transformations of the constraint system, as well as the size of the simplex table. Let's consider the application of the dual simplex method using an example.
Example. Find the minimum of a function 
under restrictions
.
Let's move on to the canonical form:
under restrictions
The initial simplex table has the form
|
Basic variables |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Solution |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Initial basis solutionoptimal, but not acceptable.
Like the usual simplex method, the solution method under consideration is based on the use of admissibility and optimality conditions.
Admissibility condition. The largest variable is selected as the excluded variable. absolute value negative basic variable (if there are alternatives, the choice is made arbitrarily). If all the basis variables are non-negative, the calculation process ends, since the resulting solution is feasible and optimal.
Condition optimality. The variable included in the basis is selected from among the non-basic variables as follows. The ratios of the coefficients of the left side are calculated-equations to the corresponding coefficients of the equation associated with the excluded variable. Ratios with a positive or zero denominator are not taken into account. In the minimization problem, the input variable must correspond to the smallest of the specified ratios, and in the maximization problem, the ratio that is the smallest in absolute value (if there are alternatives, the choice is made arbitrarily). If the denominators of all ratios are zero or positive, the problem has no feasible solutions.
After selecting the variables to be included in the basis and excluded, to obtain the next solution, the usual operation of converting the rows of a simplex table is carried out.
In this example, the excluded variable is. The ratios calculated to determine the new basis variable are given in the following table:
|
Variables |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
The equation x 4 - equation |
–2 –4 |
–1 –3 |
|||
|
Attitude |
The included variable is selected x 2. Subsequent string conversion results in a new simplex table:
|
Basic variables |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Solution |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
New solution also optimal, but still unacceptable. As a new excluded variable we choose (arbitrarily) x 3. Let's define the variable to be included.
|
Variables |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
The equation x 4 - equation |
|||||
|
attitude |
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 variables of the problem x 1 , x 2 ,..., x n are 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 | Free members under restrictions | Non-basic variables | |||||
| x 1 | x 2 | ... | x l | ... | x n|||
| x n+1 | b 1 | a 11 | 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, choose any of negative elements column of free terms (let this 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 of the 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 from 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 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).
4th step. The analysis of the new simplex table begins with the 1st step of the algorithm. The action continues until a feasible basic solution is found, i.e. all elements of the float column must be positive.
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 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 relation:
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 leading element.
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 cycling occurs, characterized by the fact that the same combination of BPs begins to repeat with a certain frequency (the value of the function F is preserved) and it is impossible to move to a new feasible 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
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1.2 ≥0)
Using the simplex method and give a geometric interpretation of the solution process.
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 corresponds to the optimal solution to the problem, therefore: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Rice. 2. Graphic solution tasks
Simplex method is an iterative process of directed solution of a system of equations step by step, which begins with a reference solution and in search of best option moves along the corner points of the feasible solution area, improving the value of the objective function until the objective function reaches the optimal value.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 saved in a Word and Excel file.
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 online service, you can determine the price of a matrix game (lower and upper bounds), check for the presence of a 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 row coefficient less than zero, then the plan is not optimal and needs to be improved.
- Determining the leading column and row. From the negative coefficients of the index line, the largest in absolute value is selected. 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 finding the minimum value (F(x) → min , see the example of a solution to minimizing a function) and the maximum value ((F(x) → max , see the example of a solution to 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 the 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. The values of the objective functions of the direct and dual problems at optimal points coincide.
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.
If you have already understood the graphical method of solving linear programming problems, it’s time to move on to simplex method. Unlike the first, it has practically no restrictions on the problem (any number of variables, different signs etc.) and is modified depending on the type of problem (for example, the M-method or the artificial basis method).
When solving a problem using the simplex method, calculations are usually carried out (for compactness and clarity) in tables (tabular simplex method), and the last table with the optimal solution contains important additional information: the solution to the dual problem, remaining resources, information about scarce resources, etc. , which allows for an economic analysis of a linear programming problem (see example 3 below).
Examples of solutions to problems using the simplex method are posted free of charge for your convenience - study, look for similar ones, solve. If you need help with tasks like this, go to: Custom Linear Programming Solution.
Solving problems using the simplex method: online examples
Task 1. The company produces bathroom shelves in two sizes - A and B. Selling agents estimate that up to 550 shelves could 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?
Drawing up a mathematical model and solving the ZLP using the simplex method (pdf, 33 Kb)
Task 2. Solve a linear programming problem using the simplex method. 
Solution using the simplex method with an artificial basis (pdf, 45 Kb)
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.
Solution of a linear programming problem with economic analysis (pdf, 163 Kb)
Task 4. Solve a linear programming problem using the simplex method: 
Solution using the tabular simplex method with search for the reference plan (pdf, 44 Kb)
Task 5. Solve a linear programming problem using the simplex method: 
Solution using the tabular simplex method (pdf, 47 Kb)
Task 6. Solve the problem using the simplex method, considering as the initial reference plan the plan given in the condition: 
Solution by manual simplex method (pdf, 60 Kb)
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 production plan for products A and B, ensuring maximum profit from their sale.
Solution using the modified simplex method (pdf, 67 Kb)
Task 8. Find the optimal solution using the dual simplex method 
Solution using the dual simplex method (pdf, 43 Kb)
Examples of solutions to linear programming problems
Methods for solving linear programming problems
Reference solutions to a linear programming problem
Let a linear programming problem be given in canonical notation
under conditions
We will denote by the set of solutions systems (2) – (3). Let us assume that , where is the rank of the matrix , and is the number of equations in system (2).
From the system of column vectors of the matrix, we select some linearly independent subsystem of vectors. It exists because . This system forms a basis in . Let us denote by , . Let's call set of basic values index , – basis submatrix matrices We will call the coordinates of the vector basic , if non-basic otherwise.
Let us write system (2) in the form . Let us divide the terms on the left side into basic and non-basic, that is
Let us define a particular solution of this system as follows. Let us set all non-basic variables equal to zero in (4). Then system (4) will take the form
Let's call (5) basic subsystem system of equations (2). Let us denote by a vector composed of the basic coordinates of the vector . Then system (2) can be rewritten in vector-matrix form
Since the submatrix is basic, it
non-degenerate. Therefore, system (6) has a unique solution. The particular solution of system (2) obtained in this way will be called reference solution direct linear programming problem corresponding to the basis. (Sometimes the reference solution is also called basic ). As we can see, the basis corresponds to a single support solution. Obviously, the number of support solutions is finite.
For this basis, we also determine the reference solution to the dual linear programming problem. Recall that the problem dual to the canonical one has the form
under conditions
Let us write system (8) in the form
Recall that the set of solutions to system (8) is denoted by .
Let us define the vector of dual variables from the condition of fulfilling the basic constraints in system (9) as equalities. We get the following system linear equations:
Let us denote by a vector composed of ba-
zis coordinates of the vector. Then system (10) can be rewritten in vector-matrix form
System (11) also has a unique solution.
Let's call him supporting (basic )decision dual linear programming problem corresponding to the basis. This reference solution is also uniquely determined.
So, any basis corresponds to two vectors - two support solutions and direct and dual linear programming problems, respectively.
Let us further define the following types of bases and support solutions. If all coordinates of the support solution are non-negative, then the basis to which this support solution corresponds is called acceptable reference plan direct linear programming problem, and the reference solution corresponding to the same basis is called pseudoplan dual problem. In fact, for the basis to be admissible, the non-negativity of the basis coordinates is sufficient. Note that the reference plan is a feasible vector of the forward linear programming problem ().
If the reference solution satisfies all restrictions (9) of the dual problem, then the basis to which this reference solution corresponds is called dually valid . In this case, the vector is called reference plan dual linear programming problem, and the reference solution corresponding to the same basis
it's called pseudoplan direct task.
For dual admissibility of a basis, it is sufficient to satisfy only non-basic inequalities. Note that the reference plan is a feasible vector of the dual linear programming problem ().
We denote the differences between the left and right sides of inequalities (9) by , . Then the dual admissibility of a basis can be established by checking the non-negativity of all . Note that, as follows directly from the definition, all basis residuals are equal to zero ().
An example of solving a direct and dual problem using the simplex method
Therefore, it is enough to make sure that the inequalities hold for everyone.
Theorem 1. LetAnd– reference solutions of the linear programming problem corresponding to a certain basis, then the equality holds .
Proof . From the definitions of support solutions it is easy to obtain the equalities
hence the validity of the theorem follows.
Theorem 2. (Optimality criterion for support solutions) If basisis simultaneously admissible and dually admissible, then the corresponding support solutionsAndare solutions, respectively, of the direct and dual linear programming problems.
Proof. The validity of this statement follows from the theory of duality in linear programming and Theorem 1.
Theorem 3. An admissible solution to problem (1) – (3) is a reference plan of the problem if and only if it is the vertex of a convex polyhedral set.
Proof. Let – reference plan of the problem (1) – (3). Let's prove that – top of the set . By definition, a reference plan – admissible reference solution corresponding to some basis, that is – solving a system of linear equations with respect to variables
It is easy to see that this system has a unique solution. This means that the supporting plane of the face containing the point , has dimension 0. Therefore, – top of the set .
Back. Let – the top of the set. Let's prove that – reference plan of the problem (1) – (3). Since is a vertex, it is a face of the set whose dimension is zero. Therefore, the vector there are at least zero components, the set of whose numbers we denote . Thus, – the only solution to the system
Where . Therefore, it remains to prove that the system of vectors is linearly independent. Let's assume the opposite. Then there are numbers that are not all equal to zero, such that . That's why
This means that system (12) has a solution different from , which contradicts the uniqueness of its solution. Thus, is the basis, and the vector – the corresponding reference plan of the problem (1) – (3). That's what was required.
Note that an admissible solution to problem (7), (8) (the dual problem (1) – (3)) is also a support plan if and only if it is the vertex of the admissible set.
Date of publication: 2015-01-10; Read: 695 | Page copyright infringement
Studopedia.org - Studopedia.Org - 2014-2018 (0.005 s)…
For definiteness, we assume that the problem being solved is to find the minimum.
1. Reduce the linear programming problem to canonical form.
After introducing additional variable system equations and a linear function are written in a form called the extended system:
We assume that all additional variables have the same sign as the free terms; otherwise we use the so-called M– a method that will be discussed below.
2. Define basic and free variables.
3. We enter the original extended system into the first simplex - table. The last row of the table, which gives the equation for linear function goals are called assessment. It indicates the coefficients of the goal function. In the left column of the table we write down the main variables (basis), in the subsequent columns we write down the coefficients for the free variables. The penultimate column contains free members of the extended system. The last column is prepared for the estimating relationships needed to determine the basic variable based on relationship (6.29).
4. Determine the possibility of solving the problem by values according to Theorems 6.7,…, 6.9.
5. Select the resolving (reference) element.
Solving a production problem using the tabular simplex method
If the optimality criterion is not met (the conditions of Theorem 6.7 or 6.8 are not met), then the largest absolute negative coefficient in the last row determines the resolving (reference) column 
.
We compose the estimated ratios of each line according to the following rules:
1 0) if all and have different signs;
2 0) if all and ;
3 0) if ;
4 0) 0 if and ;
5 0) if and have the same signs.
Let's define. If there is no final minimum, then the problem does not have a final optimum (). If the minimum is finite, then select the line q, on which it is achieved (any one, if there are several of them), and call it the resolving (reference) line. At the intersection of the resolving row and column there is a resolving (reference) element.
6 0) Go to the next table according to the rules:
a) in the left column we write a new basis: instead of the main variable - a variable, i.e. Let's swap the variables and ;
b) put 1 in place of the supporting element;
c) leave the elements of the original table in the remaining places of the reference row in the new table;
d) in the remaining places in the reference column, put the corresponding elements of the original table, multiplied by –1;
d) for the remaining free places elements , , in the new table write down the numbers , , , which are found as follows:
To simplify the calculations using these formulas, they can be formulated as "Rectangle Rules"(Fig. 6.8): elements on the diagonals of a rectangle with vertices (or , , , , or , , , ) are multiplied (the product that does not contain the supporting element is taken with a minus sign) and the resulting products are added;
f) divide all the received elements of the new table by the reference element.
7 0) Using the value of the element, determine whether the optimal value of the objective function has been found. If the answer is negative, continue the decision (return to point 6).
Rice. 6.8. Rectangle rule for determining numbers:
a − , b − , c − .
An algorithm for converting simplex tables for non-degenerate admissible basic solutions is considered, i.e. the situation described by Theorem 6.9 was fulfilled. If the original linear programming problem is degenerate, then in the course of solving it using the simplex method, degenerate basic solutions may appear. In this case, idle steps of the simplex method are possible, i.e. iterations in which f(x) does not change. Looping is also possible, i.e. an endless sequence of idle steps. To prevent it, special algorithms have been developed - anticyclines. However, in the overwhelming majority of cases, idle steps are replaced by steps with a decrease in the objective function, and the solution process is completed as a result of a finite number of iterations.
Example 6.8. Solve the problem given in example 6.7 using the simplex method.
⇐ Previous45678910111213Next ⇒
Date of publication: 2015-01-23; Read: 174 | Page copyright infringement
Studopedia.org - Studopedia.Org - 2014-2018 (0.002 s)…
Home >> Example No. 3. Simplex method. Finding the largest value of a function (artificial basis)
Simplex method
| — | x 1 | + | x 2 | ≥ | 1 | |
| x 1 | + | 3 | x 2 | ≤ | 15 | |
| — | 2 | x 1 | + | x 2 | ≤ | 4 |
| A variable is called basic for a given equation if it is included in given equation with a coefficient of one and is not included in the remaining equations (provided that there is a positive number on the right side of the equation). If each equation has a basis variable, then the system is said to have a basis. The idea of the simplex method is to move from one basis to another, obtaining a function value that is at least not less than the existing one (each basis corresponds to a single function value). How is the transition from one basis to another carried out? |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. member | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. member | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
There are no positive coefficients among the selected row coefficients. Therefore found highest value functions F.
Answer:
x 1 = 3 x 2 = 4
F max = 13
Go to the solution to your problem
© 2010-2018, for any questions please write to [email protected]
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 per 1 thousand.
Simplex method for solving ZLP
rub. 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 profit trading enterprise was the maximum.
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 thousands of rubles, 1, 2, 3 - her groups, respectively. Then mathematical model the task has the form:
F = 4 x 1 + 5 x 2 + 4 x 3 ->max
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 a 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 = 160
That is, it is necessary to sell the first type of goods in the amount of 40 thousand.
rub. There is no need to sell goods of types 2 and 3. 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
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;
Answer
y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;
The simplex method is a computational procedure based on the principle of sequential improvement of solutions when moving from one base point (basic solution) to another. In this case, the value of the objective function improves.
The basic solution is one of the admissible solutions located at the vertices of the region of admissible values. By checking vertex after vertex of the simplex for optimality, they arrive at the desired optimum. The simplex method is based on this principle.
A simplex is a convex polygon in n-dimensional space with n+1 vertices that do not lie in the same hyperplane (the hyperplane divides the space into two half-spaces).
For example, the line of budget constraints divides goods into available and unavailable.
It has been proven that if an optimal solution exists, then it will certainly be found after a finite number of iterations (steps), except in cases of “cycling”.
The simplex method algorithm consists of a number of stages.
First stage. An initial optimization model is built. Next, the original matrix of conditions is transformed into the reduced canonical form, which, among all other canonical forms, is distinguished by the fact that:
a) the right-hand sides of the conditions (free terms bi) are non-negative quantities;
b) the conditions themselves are equalities;
c) the condition matrix contains a complete unit submatrix.
If the free terms are negative, then both sides of the inequality are multiplied by - 1, and the sign of the inequality is reversed. To transform inequalities into equalities, additional variables are introduced, which usually indicate the amount of underutilized resources. This is their economic meaning.
Finally, if, after adding additional variables, the condition matrix does not contain a complete identity submatrix, then artificial variables are introduced that do not make any economic sense. They are introduced solely to obtain the identity submatrix and begin the process of solving the problem using the simplex method.
In an optimal solution to the problem, all artificial variables (AI) must be equal to zero. To do this, artificial variables are introduced into the objective function of the problem with large negative coefficients (-M) when solving the problem at max, and with large positive coefficients (+M) when the problem is solved at min. In this case, even an insignificant non-zero value of the artificial variable will sharply decrease (increase) the value of the objective function. Typically, M should be 1000 times greater than the values of the coefficients for the main variables.
Second phase. An initial simplex table is constructed and some initial basic solution is found. The set of variables that form the identity submatrix is taken as the initial basis solution. The values of these variables are equal to the free terms. All other off-basis variables are zero.
Third stage. Checking the basic solution for optimality is carried out using special estimates of the coefficients of the objective function. If all estimates of the coefficients of the objective function are negative or equal to zero, then the existing basic solution is optimal. If at least one estimate of the objective function coefficient is greater than zero, then the existing basic solution is not optimal and must be improved.
Fourth stage. Transition to a new basic solution. Obviously, the optimal plan should include a variable that increases the objective function to the greatest extent. When solving problems for maximum profit, the optimal plan includes products whose production is most profitable. This is determined by the maximum positive value estimating the coefficient of the objective function.
The simplex table column with this number at this iteration is called the general column.
To find the general row, all free members (resources) are divided into the corresponding elements of the general column (resource consumption rate per unit of product). The smallest one is selected from the results obtained. The corresponding line at a given iteration is called the general line. It corresponds to the resource that limits production at a given iteration.
An element of a simplex table located at the intersection of a general column and a row is called a general element.
Then all elements of the general string (including the free member) are divided into the general element. As a result of this operation, the general element becomes equal to one. Next, it is necessary that all other elements of the general column become equal to zero, i.e. the general column should become single. All lines (except the general one) are converted as follows. The resulting elements of the new row are multiplied by the corresponding element of the general column and the resulting product is subtracted from the elements of the old row.
We obtain the values of the new basic variables in the corresponding cells of the column of free terms.
Fifth stage. The resulting basic solution is checked for optimality (see the third stage). If it is optimal, then the calculations stop. Otherwise, it is necessary to find a new basic solution (fourth stage), etc.
Simplex method
An example of solving optimization problems of linear programming using the simplex method
Let it be necessary to find the optimal plan for the production of two types of products (x1 and x2).
Initial data:
Let's build an optimization model
– resource limitation A;
– resource limitation B.
Let us reduce the problem to the reduced canonical form. To do this, it is enough to introduce additional variables X3 and X4. As a result, inequalities are transformed into strict equalities.
Let's build the initial simplex table and find the initial basic solution. They will be additional variables, since they correspond to a unit submatrix.
1st iteration. Find the general column and general row:
The general element is 5.
2nd iteration. The found basic solution is not optimal, because the rating line (Fj-Cj) contains one positive element. Find the general column and general row:
max(0,0.3,-1.4,0) = 0.2
The found solution is optimal, since everything special assessments the objective functions Fj – Cj are equal to zero or negative. F(x)=29 x1=2; x2=5.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. member | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. member | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |