Dual method online. Simplex method for solving problems
Page 1
The dual simplex method only changes the order in which the resolving element is found, so all the features (inconsistency of the system, unlimited functionality) here have the same characteristics as in the conventional simplex method. We will only consider overcoming degeneracy, since it is caused by zero among the coefficients of the z-row, and not among the free terms.
The dual simplex method starts with a dually feasible solution and keeps it dually valid throughout all steps. The dual simplex method is implemented using the same tables as the direct simplex method. First, it is determined which variable should be removed from the basis, and then which should be introduced into the basis. The dual simplex method for the minimization problem consists of the following steps.
The dual simplex method, like the simplex method, is used to find a solution to the problem linear programming, written in the form of the main problem, for which among the vectors P /, composed of coefficients for unknowns in the system of equations, there are m unit ones.
It is convenient to solve problems using the dual simplex method using modified exceptions integer programming(see chap.
Using the dual simplex method, it was obtained not in three steps, but in two.
Using the dual simplex method, a solution to the problem resulting from adding an additional constraint is found.
Using the dual simplex method, they find a solution to the problem resulting from problem (32) - (34) as a result of adding an additional constraint.
There is also a dual simplex method, which is designed to solve problems with a large number constraints or tasks in which the number of constraints increases. In addition, there are methods problem solving with changing parameters, when only rows or only columns are not necessarily added.
Applying the dual simplex method to a linear programming problem can run into difficulties if the problem is degenerate. Geometrically this means that same values objective function are achieved at more than one vertex of the dual polyhedron of conditions.
Using the dual simplex method to solve a linear programming problem is equivalent to using the usual simplex method to solve the corresponding dual problem.
Let us use the standard dual simplex method to solve the maximization problem and obtain the desired system of optimal prices.
In the dual simplex method, the solution of the problem is performed in the following sequence: first, the coefficients of the z row are non-negative, and then the free terms are non-negative. It is necessary to justify the rule for choosing a resolving element for this order.
If the dual simplex method is used, then we need, having a dual admissible y, to obtain an inequality that the current y does not satisfy. Thus, the calculation consists of two parts. The second part is auxiliary calculations of the (generated) inequalities used in the first part. If you use the current Y in the graph H (G, m), y), you can find the shortest path from 0 to g0 of length yt Yo - Then the inequality yt To does not hold. This inequality is added to the inequalities of the first part. The inequality must be modified before writing it at the end of the dual simplex table.
It consists in constructing an optimal infeasible plan and then converting it into an admissible one without violating optimality.
Algorithm for the dual simplex method
1) select the resolution line according to the largest absolute value the negative element of the free terms column;
2) select the resolution column according to the smallest absolute value ratio of the elements L of the row to the negative elements of the resolution row;
3) recalculate the simplex table according to the rules of the usual simplex method;
4) the solution is checked for optimality. A sign of obtaining an admissible optimal solution is the absence of negative elements in the free members column.
Notes
1. If there is not a single negative element in the resolution line, the problem is unsolvable.
2. If the constraints of the problem are specified by inequalities of the “≥” type, the dual simplex method eliminates the need to introduce artificial variables.
Example. Solve the problem using the dual simplex method algorithm
L = x 1 + 4x 2 → min
We compile the initial simplex table.
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | St. |
| x 4 | -2 | -3 | 1 | 0 | 0 | 0 | -20 | |
| x 5 | -5 | 1 | -2 | 0 | 1 | 0 | 0 | -12 |
| x 6 | 1 | 2 | -1 | 0 | 0 | 1 | 0 | 2 |
| x 7 | -1 | 4 | -2 | 0 | 0 | 0 | 1 | 1 |
| L | -1 | -4 | -1 | 0 | 0 | 0 | 0 | 0 |
Absence in L line positive ratings indicates the optimality of the original solution, and the presence of negative elements in the free members column indicates its inadmissibility. According to the algorithm of the dual simplex method, we select the resolving row according to the largest in absolute value negative element of the column of free elements. In our example, the enabling line is the first. The enabling column is selected in accordance with the rule set out in paragraph 2 of the algorithm diagram. The resolution element is (-4). After recalculation we get the following table
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | St. |
| x 3 | 1 | 0 | 0 | 0 | 5 | |||
| x 5 | 0 | 1 | 0 | 0 | -2 | |||
| x 6 | 0 | 0 | 1 | 0 | 7 | |||
| x 7 | 0 | 0 | 0 | 0 | 1 | 11 | ||
| L | 0 | 0 | 0 | 0 | 5 |
Reasoning similarly, we get another table
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | St. |
| x 3 | 0 | 1 | 0 | 0 | ||||
| x 1 | 1 | 0 | 0 | 0 | ||||
| x 6 | 0 | 0 | 1 | 0 | ||||
| x 7 | 0 | 0 | 0 | 0 | 1 | 11 | ||
| L | 0 | 0 | 0 | 0 |
The absence of negative elements in the free members column indicates that the result has been obtained optimal solution , 
.
Comment. If PPP decision and is unacceptable and non-optimal, then we first obtain an admissible solution using the algorithm of the dual simplex method, and then, according to the rules of the ordinary simplex method, we obtain the optimal solution.
Example.
L = 5x 1 – x 2 – x 3 → max 
or 
Compiling the initial simplex table
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | St. | |
| x 4 | 0 | -2 | 1 | 0 | 0 | 0 | -9 | |
| x 5 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | -1 |
| x 6 | -1 | -1 | 3 | 0 | 0 | 1 | 0 | -8 |
| x 7 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 4 |
| L | -5 | 1 | 4 | 0 | 0 | 0 | 0 | 0 |
The solution is invalid because the dummy column has negative elements and is suboptimal because row L has a negative score (-5). We first obtain a feasible solution using the dual simplex method algorithm. After recalculation we obtain the following simplex table
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | St. |
| x 2 | 0 | 1 | 2 | -1 | 0 | 0 | 0 | 9 |
| x 5 | 1 | 0 | 2 | -1 | 1 | 0 | 0 | 8 |
| x 6 | -1 | 0 | 5 | -1 | 0 | 1 | 0 | 1 |
| x 7 | 0 | -1 | 0 | 0 | 0 | 1 | 4 | |
| L | -5 | 0 | 2 | 1 | 0 | 0 | 0 | -9 |
There are no negative elements in the free terms column, but in row L there is a negative score (-5), which means the solution is acceptable, not optimal.
We use the usual simplex method and get the following tables
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | St. |
| x 2 | 0 | 1 | 2 | -1 | 0 | 0 | 0 | 9 |
| x 5 | 0 | 0 | 3 | -1 | 1 | 0 | -1 | 4 |
| x 6 | 0 | 0 | -1 | 0 | 1 | 1 | 5 | |
| x 1 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 4 |
| L | 0 | 0 | -3 | 1 | 0 | 0 | 5 | 11 |
Let's consider simplex method for solving linear programming (LP) problems. It is based on the transition from one reference plan to another, during which the value of the objective function increases.
The simplex method algorithm is as follows:
- We translate the original problem into canonical view by introducing additional variables. For inequalities of the form ≤, additional variables are introduced with a sign (+), but if of the form ≥, then with a sign (-). Additional variables are introduced into the objective function with corresponding signs with a coefficient equal to 0 , because the target function should not change its economic meaning.
- Vectors are written out P i from the coefficients of the variables and the column of free terms. This action determines the number of unit vectors. The rule is that there should be as many unit vectors as there are inequalities in the system of constraints.
- After this, the source data is entered into a simplex table. Unit vectors are introduced into the basis, and by excluding them from the basis, the optimal solution is found. The coefficients of the objective function are written with the opposite sign.
- An optimality sign for an LP problem is that the solution is optimal if in f– in the row all coefficients are positive. Rule for finding the enabling column - viewed f– a string and among its negative elements the smallest one is selected. Vector P i its containing becomes permissive. The rule for choosing a resolving element - the ratios of the positive elements of the resolving column to the elements of the vector are compiled P 0 and the number that gives the smallest ratio becomes the resolving element with respect to which the simplex table will be recalculated. The line containing this element is called the enable line. If there are no positive elements in the resolution column, then the problem has no solution. After determining the resolving element, they proceed to recalculation of a new simplex table.
- Rules for filling out a new simplex table. Unit is put in place of the resolving element, and other elements are assumed to be equal 0 . The resolving vector is added to the basis, from which the corresponding zero vector is excluded, and the remaining basis vectors are written without changes. The elements of the resolution string are divided by the resolution element, and the remaining elements are recalculated according to the rectangle rule.
- This is done until f– all elements of the string will not become positive.
Let's consider solving the problem using the algorithm discussed above.
Given:
We bring the problem to canonical form:
We compose the vectors:
Fill out the simplex table:
:
Let's recalculate the first element of the vector P 0, for which we make a rectangle of numbers: and we get: 
.
We perform similar calculations for all other elements of the simplex table:
In the received plan f– the line contains one negative element – (-5/3), vector P 1. It contains in its column a single positive element, which will be the enabling element. Let's recalculate the table regarding this element:
No negative elements in f– line means found optimal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Linear programming, M: Nauka, 1998,
- Ventzel E.S. Operations Research, M: Soviet Radio, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Mathematical programming, M: graduate School, 1986
Custom Linear Programming Solution
You can order any assignments in this discipline on our website. You can attach files and specify deadlines at
Dual simplex method is based on the theory of duality (see solution of the dual problem) and is used to solve linear programming problems, the free terms of which b i can take any values, and the system of restrictions is specified by inequalities of meaning “≤”, “≥” or the equality “=”.Purpose of the service. Online calculator used to solve linear programming problems P-method in the following recording forms: the basic recording form of the simplex method, in the form of a simplex table, in the modified simplex method.
Instructions for solving problems dual simplex method. Select the number of variables and number of rows (number of constraints), click Next. The resulting solution is stored in Word file(see example of a solution using the dual simplex method).
At the same time, restrictions like x i ≥ 0 don't take it into account.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 |
In the P-method, the optimal plan is obtained by moving along pseudoplans. Pseudoplane- a plan in which the optimality conditions are satisfied, and among the values of the basic variables x i there are negative numbers. Algorithm for the dual simplex method includes the following steps:
- Drawing up a pseudo-plan. System of restrictions original problem lead to a system of inequalities meaning “≤”.
- Checking the plan for optimality. If the optimality condition is not satisfied in the resulting reference plan, then the problem is solved using the simplex method.
- Selecting leading row and column. Among the negative values of the basic variables, the largest in absolute value are selected. The line corresponding to this value is the leading one.
- Calculation of a new reference plan. New plan is obtained by recalculating the simplex table using the Jordan-Gauss method. Next, move on to stage 2.
Example. The company needs to produce A1 units, A2 units, and A3 units according to the production plan. Each type of product can be produced on two machines.
How to distribute the work of machines so that the total time spent on executing the plan is minimal? The cost matrix and time resource of each machine are given. Write down the model of the operation under study in a form that allows the use of the P-method.
It is known that the content of n nutrients A, B and C in the diet should be at least m1, m2, m3 units, respectively. Three types of foods contain these nutrients. The content of nutrient units in one kilogram of each type of product is shown in the table. determine the daily diet that provides required quantity nutrients at minimal cost.
Task: Solve the problem using the dual simplex method algorithm.
Let us reduce the system of restrictions to the system of inequalities of meaning ≤ by multiplying the corresponding lines by (-1).
Let us determine the minimum value of the objective function F(X) = 4x 1 + 2x 2 + x 3 under the following constraint conditions.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
To construct the first reference plan, we reduce the system of inequalities to a system of equations by introducing additional variables (transition to the canonical form).
In the first inequality of meaning (≤), we introduce the basic variable x 4 . In the second inequality of meaning (≤), we introduce the basic variable x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
The coefficient matrix A = a(ij) of this system of equations has the form:
| A= |
|
x 4 , x 5 ,
Assuming that the free variables are equal to zero, we obtain the first reference design:
X1 = (0,0,0,-10,8)
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iteration #1
Plan 0 in simplex table is a pseudoplan, so we determine the leading row and column.
The leading line will be the first line, and the variable x 4 should be derived from the basis.
3. Definition of a new basic variable. Minimum valueθ corresponds to the 2nd column, i.e. the variable x 2 must be entered into the basis.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Recalculation of the simplex table. We carry out transformations of the simplex table using the Jordano-Gauss method.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Let's present the calculation of each element in the form of a table:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iteration #2
1. Checking the optimality criterion.
Plan 1 in a simplex table is a pseudo-plan, so we determine the leading row and column.
2. Definition of a new free variable.
Among the negative values of the basic variables, we select the largest in absolute value.
The second line will be leading, and the variable x 5 should be derived from the basis.
3. Definition of a new basic variable. The minimum value of θ corresponds to the third column, i.e. the variable x 3 must be entered into the basis.
At the intersection of the leading row and column there is a resolving element (RE) equal to (-1).
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Recalculation of the simplex table. We carry out transformations.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
In the basis column, all elements are positive. Let's move on to the main algorithm of the simplex method.
Iteration #3
1. Checking the optimality criterion.
There are no positive values among the index string values. Therefore, this table determines the optimal plan for the problem.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
The optimal plan can be written as follows: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
So, successive transitions from one conjugate basis to another they carry out until they obtain a solution to the problem or establish its unsolvability. Each transition from one pseudoplan to another is one iteration (one step).
Each iteration contains two stages. At the first stage, they find out whether the pseudo-plan is optimal plan direct problem, and if not, then whether the problem is solvable. To do this, it is necessary to calculate and establish their signs. The second stage is to implement elementary transformation- (one iteration) complete exclusion method Jordan-Gauss, leading to a new pseudo-plan with a smaller value of the objective function.
Description of the algorithm. The LP problem must be specified in the canonical form (1.1), (1.2) or reduced to it. Looking for conjugate basis dual problem
and designate it 
. Let us expand A 0 into the basis vectors A i1 ,.,A im in accordance with (1.9) and find the pseudoplan 
direct task.
Let's explore the signs (x i0). If the case occurs, then the initial pseudoplan is optimal plan direct task. If there are negative components (x i0), we calculate the coefficients vector decompositions A j by vectors conjugate basis(х ij) in accordance with (1.8).
If for some r such that x r0<0 , все то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.
If the third case occurs (that is, for every r such that x r0<0 , по крайней мере одна из компонент х rj <0 ), то переходим к второму этапу. С этой целью составляют таблицу k -й итерации (аналогичную simplex table), which consists of (m+2) rows and (n+1) column (Table 6.1).
Column B x of the table, as usual, contains the vectors (A i) of the basis of the pseudoplan xk, and column A 0 - the basis components of the pseudoplan (x i0 (k)). The (m+1)-index line is filled with parameters that are estimates of the vectors A j:
value - the value of the objective function for a pseudoplan
Iteration k is completed by filling the main part of the table (from the first to (m+1) th rows).
| C | C 1 | C 2 | . | Cj | . | Cn | ||
| B x | A 0 | A 1 | A 2 | . | A j | . | A n | |
| C 1 | X 1 | X 10 | X 11 | X 12 | . | X 1j | . | X 1n |
| C 2 | X 2 | X 20 | X 21 | X 22 | . | X 2j | . | X2n |
| . | . | . | . | . | . | . | . | . |
| C i | X i | X i0 | Xi1 | Xi2 | . | X ij | . | Xin |
| . | . | . | . | . | . | . | . | . |
| Cm | Xm | X m0 | X m1 | X m2 | . | X mj | . | X mn |
| . | . | |||||||
| . | . |
At the first stage (k+1) - and iterations find out whether the first, second or third case occurs.
In the third case, we move on to the second stage. First, the vector A r is determined, which must be derived from the basis. Its index r is determined from the condition
Only those positions for which x rj are filled in the line<0 . Вектор А l , который должен быть введен в базис, находят из условия
Having determined the guide row r and column l, the elements of the main part of the table of the (k+1)th iteration are calculated using recurrence relations
 |
(1.15) |
Where x ri is the transformation guide element.
Computational scheme of the algorithm dual simplex method similar to the computational scheme of the simplex method. The forms of the tables are similar.
The difference between the methods is that with the simplex method a sequential transition is made from one feasible basic solution (reference plan) of the problem to another, and with dual simplesk method- transition from one pseudoplan to another.
The formal difference between the computational schemes of these methods manifests itself only in the rules for transition from one basis to another, as well as in the signs of optimality and unsolvability of the problem. In the simplex method, the vector introduced into the basis is first determined, and then the vector excluded from the basis is determined, and in dual simplex method this order is reverse.
Let us note some important properties dual simplex method.
Unlike direct
