Simplex method for solving linear programming problems. checking the optimality of the solution found
Kursk Academy of State and Municipal Service
Department of Information and Technosphere Security
Essay
by discipline "Methods of optimal solutions"
on the topic "The idea of the simplex method"
Completed by: 2nd year student
Specialties "Economics"
Moskaleva O. S.
Checked by: Ph.D., Associate Professor Pogosyan S. L.
Kursk – 2012
Introduction………………………………………………………………………………..3
1. The idea of the simplex method…………………………………………….…4
2. Implementation of the simplex method using the example……………………..……6
3. Tabular implementation of a simple simplex method……………….10
Conclusion………………………………………………………………………………….15
List of used literature……………………………..…….16
Introduction.
The Simplex method is a typical example of iterative calculations used in solving most optimization problems.
In the computational scheme of the simplex method, an ordered process is implemented in which, starting from some initial admissible corner point (usually the origin), successive transitions are made from one admissible extreme point to another until a point corresponding to the optimal solution is found.
The idea of the simplex method
Let's consider a universal method for solving the canonical linear programming problem, with n variables and m equality constraints, known as the simplex method.
The set of plans of a canonical problem is a convex polyhedral set having final number corner points. And if this problem has an optimal solution, then it is achieved at least at one corner point.
Any corner point is associated with a basic plan of the problem, in which the variables are equal to zero, and the remaining variables correspond to linearly independent columns of the condition matrix. These linearly independent columns form a non-singular basis matrix.
Iterating over all corner points is computationally expensive and therefore ineffective. In 1947, J. Danzig proposed an orderly procedure for enumerating corner points, in which it is enough to examine only a small part of them to find the optimal solution. This procedure is called simplex method.
J. Danzig proposed, when moving from one extreme point to another, to replace in basis matrix just one vector. This means that during such a transition we must exclude one of the basic variables - make it non-basic ( equal to zero), and in its place introduce a new variable from among the non-basic (zero) ones - make it basic (positive).
It turns out that geometrically such a replacement leads to a transition from one corner point to an adjacent (neighboring) one associated with previous point common edge.
From all neighboring points, the one at which objective function increases the most. Since the number of corner points is finite, through a finite number of transitions the vertex with highest value objective function, or the unboundedness of the objective function will be established on an unlimited set of plans.
General scheme The simplex method consists of the following main steps: step 0. Determination of the initial basis and the corresponding initial corner point (baseline).
step 1. Checking the current baseline for optimality . If the optimality criterion is satisfied, That the plan is optimal and the solution is complete. Otherwise go to step 2.
step 2. Finding the variable introduced into the basic ones. (From the condition of increasing the objective function).
step 3. Finding a variable excluded from the basic variables (From the condition of preserving the constraints of the problem).
step 4 . Finding the coordinates of the new baseline (adjacent corner point). Go to step 1.
Repeated steps 1-4 form one iteration of the simplex method.
From this diagram it follows that, firstly, to start the simplex method, you need to have some kind of corner point - an initial basic plan, and secondly, you need to be able to examine the current corner point for optimality without calculating all adjacent vertices. These problems are easily solved if the canonical LP problem has a certain special type.
Definition. We will say that the canonical LP problem has a “preferred form” if: the right-hand sides of the equations; the condition matrix contains a unit size submatrix.
In other words, in any equation there is a variable with a coefficient equal to one, missing from the other equations. The first condition is not burdensome, since in the case of a negative right-hand side of some equation, it is enough to multiply it by (-1). In a preferential type problem, finding the initial baseline is very simple.
Implementation of the simplex method using an example
Let us demonstrate the use of the simplex method with an example. Let's consider canonical problem LP
| f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 > max | ||
| -x 1 + 2x 2 +x 3 = 4, | ||
| 3x 1 + 2x 2 +x 4 = 12, | ||
| x j? 0, j = 1,2,3,4. | ||
Condition Matrix A = (A 1 , A 2 , A 3 , A 4), where
Target vector c =(c 1, c 2, c 3, c 4) = (1, 2, 0, 0); vector of right parts b=(b 1 ,b 2) = (4, 12).
Step 0. Finding the starting corner point (baseline).
The problem has a preferable form, since the right-hand sides of the equations are positive, and the columns of the condition matrix A 3, A 4 form a unit submatrix. This means the initial basis matrix = (A 3 ,A 4); x 3 And x 4 - basic variables x 1 And x 2 - non-basic variables, c B = (c 3, c 4) = = (0, 0).
The initial baseline looks like x 0 =(0, 0, x 3 , x 4) = (0, 0, 4, 12); f(x o) = 0.
Step 1. Checking the basic plan for optimality.
Let's calculate simplex estimates for non-basic variables using formula (5.1)
? 1 = 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .
? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .
Since the estimates are negative, the plan x- not optimal. We will look for a new baseline (adjacent corner point) with a larger value of the objective function.
Step 2. Finding the variable introduced into the basis.
The objective function can be increased by introducing one of the non-basic variables into the basic variables (making it positive) x 1 or x 2, since both estimates ? j x 2.
Step 3. Definition of a variable derived from the basis.
After entering the variable into the basis x 2 the new plan will look like
x" =(0, x 2, x 3 , x 4).
This plan is not a basic one, since it contains only one zero coordinate, which means it is necessary to make one of the variables zero (exclude from the basis) x 3 or x 4 . Let's substitute the coordinates of the plan x" =(0, x 2, x 3 ,x 4) in the constraints of the problem. We get
2x 2 +x 3 = 4,
2x 2 + x 4 = 12.
Let us express the basic variables from here x 3 And x 4 via variable x 2 , entered into the basis.
| x 3 = 4 - 2x 2, | ||
| x 4 = 12 - 2x 2 . | ||
So variables x 3 And x 4 must be non-negative, we obtain a system of inequalities
| 4 - 2x 2 ? 0, | ||
| 12 - 2x 2 ? 0. | ||
The higher the value x 2 , the more the objective function increases. We'll find maximum value a new basic variable that does not violate the constraints of the problem, that is, satisfies conditions (2.8), (2.9).
Let us rewrite the last inequalities in the form
2x 2 ? 4,
2x 2 ? 12,
where does the maximum value come from? x 2 = min ( 4/2, 12/2 ) = 2. Substituting this value into expressions (2.6), (2.7) for x 3 And x 4 , we get x 3 = 0. Therefore x 3 derived from the basis .
Step 4. Determining the coordinates of the new baseline.
The new baseline (adjacent corner point) is:
x" = (0, x 2, 0, x 4)
The basis of this point consists of columns A 2 and A 4 , so =( A 2, A 4). This basis is not unitary, since the vector A 2 = (2,2), and therefore problem (2.2)-(2.5) does not have a preferred form with respect to the new basis. Let us transform the conditions of problem (2.3), (2.4) so that it takes the preferred form with respect to the new basic variables x 2, x 4, that is, so that the variable x 2 was included in the first equation with a coefficient equal to one, and was not present in the second equation. Let's rewrite the equations of the problem
- x 1 + 2 x 2 + x 3 = 4, (p 1)
3x 1 +2 x 2 + x 4 = 12. (p 2)
Let's divide the first equation by the coefficient at x 2 . We get a new equation = p 1/2 equivalent to original
1/2 x 1 + x 2 + 1/2 x 3 = 2. ()
We use this equation, which we call resolving, to eliminate the variable x 2 from the second equation. To do this, you need to multiply the equation by 2 and subtract from p 2 . We get = p 2 - 2= p 2 - p 1:
4 x 1 - x 3 + x 4 = 8. ()
As a result, we obtained a new “preferred” representation of the original problem with respect to new basic variables x 2 , x 4:
f(x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 ? max
1/2 x 1 + x 2 + 1/2 x 3 = 2 ()
4 x 1 - x 3 + x 4 = 8 ()
x j? 0, j = 1,2,3,4
Substituting here the representation of the new baseline x 1 = (0, x 2, 0, x 4), we will immediately find its coordinates, since the values of the basic variables are equal to the right sides of the equations
x" = (0, 2, 0, 8); f(x 1)=4.
This completes the first iteration of the simplex method. Next, the process of solving the problem continues from step 1, which consists of checking the found plan for optimality. The solution ends when all simplex estimates of the current basic plan turn out to be non-negative.
We will not carry out the second iteration according to the scheme of the first, since it is more convenient to carry out all calculations of the simplex method in tabular form.
Tabular implementation of a simple simplex method
We will demonstrate the tabular implementation using the same example (2.2)-(2.5).
Step 0. The solution begins by constructing an initial simplex table. Filled in first right part tables from the third column. In two top lines names are recorded problem variables (x 1, ...,x 4) and coefficients of the objective function for these variables. Below are the coefficients of the equations - elements of the condition matrix A, so under the variable x 1 located column A 1, under variable x 2 - column A 2 etc. The right-hand sides of the constraints (numbers) are entered in the right column b i > 0).
Then we find the columns of the condition matrix that form the unit basis - in our example this is A 3 and A 4 - and their corresponding basis variables x 3, x 4 write in the second column. Finally, in the first column we write the coefficients of the objective function for the basic variables.
Table 1- Initial simplex table
| Basic Variables | Basic variable values ( x B =b) |
|||||
| x 1 | x 2 | x 3 | x 4 | |||
| x 3 | a 11 =-1 | |||||
| x 4 | ||||||
| Rating line ? j | ? 1 = -1 | ? 2 = -2 |
Since the problem has a preferred form, the values of the basic variables are equal to the right-hand sides of the equations located in the last column. Since the non-basis variables are zero, the initial baseline is
x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).
Step 1. To check the plan x o for optimality we calculate simplex estimates for non-basic variables x 1 And x 2 according to the formula
? j = B, A j > - c j .
? 1 = B, A 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .
With a tabular implementation for calculating the score ? 1 we need to find the sum of the products of the elements of the first column ( c B) to the corresponding column elements A 1 for a non-basic variable x 1 . The score is calculated in the same way ? 2 , as the scalar product of the first column ( c B) per column at variable x 2.
? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .
Simplex estimates are written in the last row of the simplex table, which is called the delta row. In this case, not only the cells for non-basic variables are filled, but also the basic cells. It is easy to check that for the basic unit columns of the condition matrix the simplex estimates are equal to zero. In the last cell of the evaluation line we write the value of the objective function at the point xo. Note that since the non-basic coordinates of the basic plan are equal to zero, it is convenient to calculate the objective function using the formula
f(x)= c B, x B >,
scalarly multiplying the first and last columns of the table.
Since among the estimates ? j There is negative , then the plan x o is not optimal, and it is necessary to find a new basic plan by replacing one of the basic variables with a new one from among the non-basic ones.
Step 2. Since both estimates ? 1 And ? 2 then any of the variables can be included in the basis x 1, x 2 . Let us introduce into the basis the variable with the largest absolute negative estimate, that is x 2 .
The column of the simplex table in which the variable entered into the basis is located is called the leading column.
In the example, the leading column will be at x 2 .
Step 3. If all elements in the leading column are negative, then there is no solution to the problem and max f(x) ???. In the example, all elements of the leading column are positive, therefore, we can find the maximum value x 2 , at which one of the old basic variables goes to zero. Recall that the maximum value x 2 = min(4/2, 12/2)=2.
According to the table, this value is calculated as the smallest of the ratios of the components of the baseline (from the last column) to the corresponding positive elements of the leading column.
The smallest ratio is in the row with the basis variable x 3. So the variable x 3 excluded from the basic variables ( x 3 = 0).
The line containing the variable to be excluded from the basis is called the leading line.
In the example, the leading line will be the first line.
The element located at the intersection of the leading row and leading column is called the leading element.
In our case, the leading element a 12 = 2.
Table 2- Initial simplex table with leading row and column
| Basic changes. | Basic variable values | Equations |
|||||
| x 2 | |||||||
| c 3 =0 | x 3 | -1 | 2 | 1 | 0 | 4 | |
| 2 | |||||||
| Rating line ? j | ? 1 = -1 | ? 2 = -2 | |||||
Step 4. To obtain a new basic plan, we reduce the problem to a new preferred form with respect to the new basic variables.
To do this, we will build a new simplex table, in the second column of which instead of the excluded variable x 3 let's write a new basic variable x 2, and in the first column ( with B) instead of from 3 Let's write down the coefficient of the objective function at x 2: c 2 =2. In the new simplex table, the column at x 2 must become one (the leading element must be equal to one, and all other elements must become zero). This is achieved by the following table row transformations.
a. We divide all elements of the leading line by the leading element and write them in the same line as a new one simplex tables.
The resulting string p 1" Let's call it permissive.
b. To the remaining second line we add the resolving line, multiplied by such a number that the element in the leading column becomes zero.
p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.
c. Let's fill in the last line by calculating the estimates ? j " = - - c j, Where c B ", A j " - the corresponding columns of the new simplex table, and the value of the objective function f(x)= .
We obtain a second simplex table with a new basis.
Table 3- Result of the first iteration
| Basic changes. | Basic variable values | Equations | ||||||
| -1/2 | ||||||||
| x 4 | 4 | 0 | -1 | 1 | 8 | p 2 " =p 2 - p 1 | ||
| estimates ? j" | -2 | |||||||
New baseline x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ). Since the assessment ? 1 = -2 then plan x " not optimal. To move to a new basic plan (of the neighboring corner point), we will carry out another iteration of the simplex method.
Because? 1 then a variable is introduced into the basis x 1. The first column containing x 1 - leading.
We find the relationships between the components of the basic plan and the corresponding positive elements of the leading column and take the row with the smallest ratio as the leading row. In Table 2, in the leading column only the second element is greater than zero (= 4), hence the second line will be the leading one, and the basis located in it variable x 4 subject to exclusion from basis.
We select the leading column and leading row and at their intersection we find leading element (= 4).
We build a new (third) simplex table, replacing the basic variable in it x 4 on x 1 , and again transforming the table rows so that the leading element becomes equal to one, and the remaining elements of the leading column become zero. To do this, divide the leading (second) line by 4, and add the resulting second line divided by 2 to the first line. Last line calculate using formulas for simplex estimates ? j"" = "", A j""> - c j, Where c B"", A j"" - the corresponding columns of the new simplex table. The value of the objective function on the new baseline is found using the formula f(x"")= "", x B"" >.
Table 4- Result of the second iteration
| Basic change. | Basic variable values | equations |
|||||
| p 1 "" = p 1 "+p 2 ""/2 |
|||||||
| p 2 "" = p 2 "/4 |
|||||||
| estimates ? j "" | f(x"")= 8 | ||||||
New baseline x "" = (x 1, x 2, 0, 0) = (2, 3, 0, 0 ). Since all estimates are non-negative, then the plan x ""- optimal plan.
Thus, x* = (2, 3, 0, 0 ), f(x*) = 8.
CONCLUSION
Considered methods for solving problems linear programming are widely used in practice. However, it should be noted that
the mathematical model is always poorer than the real one economic system. It describes this system only approximately, highlighting some properties and neglecting others. To compensate for this shortcoming in mathematical economics, several types of models are being developed, each of which is designed to reflect one specific aspect of economic reality so that when solving a specific economic problem, it is possible to select a model that best suits it.
LIST OF REFERENCES USED
1. Ashmanov S.A. Linear programming. - M.: Nauka, 1981.
2. Introduction of natural basic variables. Construction of a simplex table. Definition of the zero plan.
Simplex method. Algorithm of the simplex method.
Simplex method- solution algorithm optimization problem linear programming by enumerating the vertices of a convex polyhedron in multidimensional space. The method was developed by American mathematician George Danzig in 1947.
Idea simplex method consists in the fact that the posed descriptive task is translated into mathematical form. The mathematical formulation of the problem contains the equation of the objective function indicating the desired result - determining the minimum or maximum of the objective function; systems of linear constraints specified by equalities or inequalities. Received mathematical description lead to matrix form. Then the matrix description of the problem is reduced to canonical form. After the system linear equations reduced to canonical form, we begin to solve the linear programming problem. The algorithm for solving this problem consists of a sequence of constructing matrices. Each step of the solution brings you closer to obtaining the desired result.
In the computational scheme of the simplex method, an ordered process is implemented in which, starting from some initial admissible corner point (usually the origin), successive transitions are made from one admissible extreme point to another until a point corresponding to the optimal solution is found.
Simplex method algorithm
1. We bring the system of restrictions to canonical form(when the system is limited). Moreover, a single basis can be identified in the system.
2. Find the original reference plan(non-negative basic solutions of the KZLP system of equations). Each of the reference plans is determined by a system of m linearly independent vectors contained in a given system of n vectors A 1 , A 2 ,…, A n. The upper limit on the number of reference plans contained in a given problem is determined by the number of combinations With nm);
3. We build simplex table (simplex table a matrix that serves as a means of enumerating admissible basis solutions of a (non-degenerate) linear programming problem when solving it using the simplex method. It is formed from the matrix of coefficients of a system of linear programming equations reduced to canonical form, its sequential transformation according to the so-called simplex algorithm allows a limited number of steps (iterations) to obtain the desired result - a plan that provides an extreme value of the objective function).
4. B simplex table we check the vectors for negativity, i.e. estimates Zj – Сj written in the line must be ≤ 0 (at a minimum), Zj – Сj ≥ 0(to the maximum). If the estimates satisfy the optimality conditions, then the problem is solved.
5. If for some vectors the optimality conditions are violated, then it is necessary to introduce into the basis a vector that corresponds to:
max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min, Where x i> 0
Vector element θ j which corresponds θ 0 j called permissive; the row and column in which it is located are called the guide; the vector in the guide row leaves the basis.
6. Let's find the expansion coefficient for all vectors in the new basis. Let's apply the Giordano Gauss method
Let's check for the optimal reference plan. If the estimate satisfies the optimality conditions, then the problem is solved; if not, then steps 5-7 are performed.
2. Introduction of natural basic variables. Construction of a simplex table. Definition of the zero plan.
The simplex method is most effective in solving complex tasks and represents an iterative (step-by-step) process starting with zero(reference) solution (vertex n-dimensional polyhedron). Next in search optimal option The plan assumes movement along the corner points (vertices of the polyhedron) until the value of the objective function reaches the maximum (minimum) value. Let's consider the algorithm of the simplex method using the example of a turnover planning problem with limited raw material resources.
The company sells n product groups, having m limited material and monetary resources b i ≥0 (1 ≤ i≤ m) . Everyone's resource costs are known i- type of production and sale of a unit of goods of each group, presented in the form of a matrix ( a ij) and the profit received by the enterprise from the sale of a unit of goods j-group included in the objective function Z(X). The linear programming method is no different from system (1) - (2):
Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)
a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,
a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)
a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,
X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0
The stages of solving the problem using the simplex method include:
1) Drawing up a zero reference plan. We introduce new non-negative (basic) variables, thanks to which the system of inequalities (2) becomes a system of equations:
a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1
a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)
……………………………………..
a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,
If we take the input variables as column vectors, then they represent single (basic) vectors. Note that the basic variables have a simple physical meaning- This remainder specific resource in the warehouse for a given production plan, therefore this basis is called natural. We solve system (3) with respect to the basic variables:
X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n
X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)
………………………………………..
X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n
We rewrite the objective function in the form
Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)
Assuming that the required main variables X 1 = X 2 = X 3 = ... = X n = 0, we obtain a zero reference plan X = (0, 0, ...0, b 1, b 2, b 3 ... b m), at which Z(X) = 0 (all resources in stock, nothing produced). We enter the plan into a simplex table.
| Plan | Basis | C i /C j | Meaning X i | X 1 | X 2 | Xn | Xn+1 | Xn+2 | X n+ 3 | Q min |
| Xn+1 | b 1 | a 11 | a 12 | a 13 | b 1/a 12 | |||||
| Xn+2 | b 2 | a 21 | a 22 | a 23 | b 2 / a 22 | |||||
| Xn+3 | b 3 | a 31 | a 32 | a 33 | b 3 / a 32 | |||||
| Z(X) = 0 | -C 1 | - C 2 | - C 3 | Index. line |
2) From the negative coefficients of the index line, we select the largest in absolute value, which determines the leading column and shows which variable at the next iteration (step) will move from the main (free) to the basic (in fact, the product group whose sales brings maximum income). Then we divide the reserves of raw materials b i by the corresponding cost coefficients, enter the results into a table and determine the minimum value Q min (the resource whose reserve most strongly limits the output of the selected product group is selected). This value selects the leading line and the variable Xi, which at the next step (iteration) will leave the basis and become free.
3) The transition to a new plan is carried out as a result of recalculation of the simplex table using the Jordan-Gauss method. First, we replace X j in the basis with X i of the leading column. Let's divide all the elements of the leading line by the resolving element (RE), as a result of which the place of the RE in the leading line will be 1. Since X i has become basic, its remaining coefficients should be equal to 0. New elements of this plan are found according to the rectangle rule
NE=SE – (A*B)/RE (6)
The resulting plan is evaluated using the coefficients of the index line: if they are all positive, then the plan is optimal; if not, then the plan can be improved by performing the next iteration (step).
Example. 20 thousand rubles were allocated for the purchase of equipment for the production site. The equipment can be placed on an area not exceeding 72 sq.m. You can order equipment of two types: type A, requiring a production area of 6 sq.m and providing 6 thousand units. products per shift (price 5,000 rubles) and type B, requiring an area of 12 sq.m. and producing 3 thousand units (price 2,000 rubles). What is the optimal equipment acquisition plan to ensure maximum performance plot?
Let us denote the quantity of purchased equipment of type A and B by X 1 and X 2, respectively.
Site productivity (objective function): Z(X) =6Х 1 +3Х 2.
The main limitations are related
with cash: 5Х 1 +2Х 2 ≤ 20,
with production site area: 6Х 1 +12Х 2 ≤ 72.
We introduce new basic variables X 3 (remainder Money after purchasing equipment) and X 4 (remaining area after equipment placement) and rewrite the restrictions in the form of a system of equations:
5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)
6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)
In this case, the goal function: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .
We make a reference (0th) plan: X = (0, 0, 20, 72), i.e. nothing has been purchased yet (no money has been spent, the space is empty). Making a simplex table
| Plan | Basis | C i /C j | Meaning X i | X 1 | X 2 | X 3 | X 4 | Q min | |||
| X 3 | 20/5=4 | ||||||||||
| X 4 | 72/6=12 | ||||||||||
| Z(X) = 0 | - 6 | - 3 | Index line | ||||||||
| →X 1 | 0,4 | 0,2 | 4/0,4=10 | ||||||||
| X 4 | 9,6 | -1,2 | 48/9,6=5 | ||||||||
| Z(X) = 6*4=24 | -0,6 | 1,2 | Index line | ||||||||
| X 1 | 0,25 | -1/24 | - | ||||||||
| →X 2 | -1/8 | 5/48 | - | ||||||||
| Z(X) =6*2+3*5=27 | 9/8 | 1/16 | Index line | ||||||||
Obviously, the leading column corresponds to X 1, since it has the largest index 6. We find the minimum value of Q min = 4 (the most severe resource constraint) by defining a leading row showing that X 3 is derived from the basis variables, and X is entered instead 1 . We recalculate the elements of the leading line, dividing them by 5, and using formula (6) we determine the elements of the second and index lines. The objective function for the 1st plan is equal to Z(X) = 6*4+3*0 = 24.
However, one of the coefficients of the index row for column X 2 remains negative -0.6, therefore this plan is not optimal, and another iteration (step) is required to improve it. Select the 2nd column as leading and minimum value Q min = 5 we define the leading line with the basic variable X 4. Having performed the same transformations, we obtain the 2nd plan, which will be optimal, since all index coefficients are positive.
Let's analyze the results obtained. At optimal solution the objective function has a maximum value of 27 thousand rubles, while both resources are removed from the basis, therefore completely spent.
Let's make sure of this: 5*2+2*5 = 20 thousand rubles, 6*2+12*5=72 sq.m. The required solution is X = (2; 5;0;0). This does not always happen.
Lecture No. 10
Topic: Simplex method for problems with an artificial basis
The simplex solution method is based on the introduction of additional (basic) variables that make it possible to form a unit matrix. If the problem constraints are presented in the form of inequalities:
a i1 X 1 + a i2 X 2 +…a in X n ≥ b i (1)
or equations:
a i1 X 1 + a i2 X 2 +…a in X n = b i (1*),
then it is impossible to obtain the reference plan in the desired form. In this case, to comply with equalities (1*), we introduce artificial basis Y i , and artificial variables are not directly related to the content of the task, but make it possible to construct a reference (starting) plan:
a i1 X 1 + a i2 X 2 +…a in X n +Y i = b i (2)
The objective function when solving the problem to the maximum will be written in the form:
Z(X) =∑C j X j +(-M)∑Y i (3),
when solving a similar problem at a minimum:
Z(X)=∑C j X j +(M)∑Y i (3*),
where M is a very large positive number, a kind of penalty for using artificial variables.
In the case of inequalities (1), we initially introduce additional variables X n + i with a minus sign. Their matrix will not be unitary, therefore, into each inequality of system (1) we introduce artificial variables У i:
a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b i (4)
The objective function in this case is Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (to find the maximum). Application artificial basis gives the simplex method greater flexibility and allows it to be used for a wide range of tasks.
Example . Determine the maximum and minimum profit values for the production of two types of products A and B, if production costs and profitability from sales of a unit of product are given in the table. The main condition is full employment of workers at the enterprise.
Mathematically, the production output constraints will be written in the form of a mixed system:
1X 1 + 1X 2 ≤ 6,
2X 1 + 1X 2 =8.
Let us introduce the basic variable X 3 for the first inequality, and the artificial variable Y 1 for the second equation:
1X 1 + 1X 2 + X 3 = 6,
2X 1 + 1X 2 +Y 1 =8.
Let us express X 3 and Y 1 from the resulting system of equations and, to determine the maximum, imagine the objective function:
Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=
3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M
For the reference plan - X=(0,0,6,8). Let's build a simplex table:
| Plan | Basis | C i /C j | Meaning X i | X 1 | X 2 | X 3 | Y 1 | Q min |
| X 3 | 6/1=6 | |||||||
| Y 1 | -M | 8/2=4 | ||||||
| Z(X) = -8M | -2M-3 | -M-2 | Index line | |||||
| X 3 | 0,5 | -0,5 | 2/0,5=4 | |||||
| →X 1 | 0,5 | 0,5 | 4/0,5=8 | |||||
| Z(X) = 3*4=12 | - 0,5 | M+1.5 | Index line | |||||
| →X 2 | -1 | - | ||||||
| X 1 | -1 | - | ||||||
| Z(X) =3*2+2*4=14 | M+1 | Index line |
As a rule, improvement of the reference plan begins with the removal of the artificial variable Y 1 from the basis. The optimal plan X = (2,4,0,0) was obtained in the second iteration, with a maximum income of 14 thousand. rub. , and the coefficients of the index row are non-negative. It is easy to verify that in this task, with an optimal plan, resources are fully used (2*1+4*1=6; 2*2+1*4=8).
When finding the minimum profitability, we formulate the objective function differently (+MY 1 is entered as a term:
Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=
3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M
The reference plan is the same, but the index row coefficients in the simplex table are different. The leading column, as before, is selected by the largest positive coefficient in absolute value for X 1, the leading row is determined by the minimum value of Q min = 4. At the first iteration, the artificial variable Y 1 is derived from the basis.
| Plan | Basis | C i /C j | Meaning X i | X 1 | X 2 | X 3 | Y 1 | Q min | ||
| X 3 | 6/1=6 | |||||||||
| Y 1 | M | 8/2=4 | ||||||||
| Z(X) = 8M | 2M-3 | M-2 | Index line | |||||||
| X 3 | 0,5 | -0,5 | 2/0,5=4 | |||||||
| →X 1 | 0,5 | 0,5 | 4/0,5=8 | |||||||
| Z(X) = 3*4=12 | - 0,5 | -M+1.5 | Index line | |||||||
The resulting negative values of the coefficients in the index line X i indicate the optimality of the 1st plan, while the minimum income is 12 thousand rubles.
It is provided only by the output of product A (product B is not produced), the raw materials are not fully used (remainder X 3 = 2t), while the main condition is met - the workers are fully employed in production.
Lecture No. 11
Topic: Closed transport problem
1. Mathematical formulation of closed transport problem. Determining the required number of unknowns.
2. Stages of determining a plan for solving a transport problem.
Finding the optimal plan. This method is universal; it allows solving linear programming problems of any dimension in a general formulation. However, this method requires reducing the original problem to canonical form.
The main idea of the simplex method is to move from one vertex of the ODR to another so that with each transition the value of the CF decreases. This is how you can get from any vertex to the optimal one and get the optimal plan.
For example: let the reference plan X =(x1,x2,…,xm,0,0,…,0) and the associated system of linearly independent vectors: A1,A2,…,Am be known, then for this reference plan you can calculate the value CF Z=(c1x1+c2x2+…+cmxm) and write the limitation conditions in the following form x1A1+x2A2+…+xmAm=b
Since the vectors A1, A2,…, Am are linearly independent, any vector Aj can be expanded into these vectors: Aj=x1jA1+x2jA2+…+xmjAm (*) Let us introduce the values Zj Zj=x1jc1+x2jc2+…+xmjcm, where xij is the coefficient corresponding to Ai in the expansion vector Aj by basis vectors
Theorem 1: Improvement of the reference plan
If for some index j the condition Zj-Cj>0 is satisfied, then the value of the CF can be reduced and:
· if the CF is limited from below, then it is possible to construct a reference plan with a smaller CF value, the same previous
· if the TF is not limited from below, then it is possible to construct a plan corresponding to an arbitrarily small value of the TF
Theorem 2: optimality criterion for the reference plan
If for some index j in the reference plan the inequality Zj-Cj0. Let this minimum be achieved for the vector Ak, then it is this vector that must be derived from the basis. The line corresponding to this vector is called a guide and is denoted “à”.
4. After defining the column and row guides, fill out a new simplex table. In such a table, Ai will appear in place of the guide line. Filling new table starts with a guide line. As a component of the reference plan, the value Ө0 X'l=Ө0=Xk/Xkl is written there, the remaining elements of this line are determined by the formula X'lj X'lj=Xkj/Xkl where Xkl is the element located at the intersection of the row and column guides, specifically on it all former elements of the guide line are divided, and in place former element Xkl automatically appears unit. General rule to recalculate the guide line, you can write it like this: Ak (new element of the guide line) = (old element of the guide line)/(element standing at the intersection of the guide column and row)
5. All elements of the remaining rows of the table are recalculated, including the additional bottom row. Recalculation is carried out according to the formulas
· for components of the reference plan X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil
· for components expanded over the basis X’ij=Xij-(Xkj/Xkl)*Xil
· For additional line Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)
All these formulas are built according to one rule:
(new email)=(old email)-(new row direction email)*(column direction email in the corresponding row)
After filling out the new simplex table, the transition to the second stage of the algorithm occurs.
Methods of natural and artificial basis. Basic concepts, algorithms of methods.
For most linear programming problems, difficulties arise in solving them associated with determining the initial reference plan and the initial simplex table from which all iterations begin. This is due to the fact that in real problems among the vectors Ai there are no vectors containing only one non-zero component, i.e. vectors of the form (0,0,0,…,0,1,0,…,0) or their number is not enough to form a basis. That is, it is not possible to form a natural basis.
The artificial basis method is based on the artificial introduction into mathematical model problems of such vectors.
Let a ZLP of canonical form be given
F: C1X1=C2X2+…+CnXnàmin
a11x1+a21x2+…+an1xn=b1
a12x1+a22x2+…+an2xn=b2
…………………………
a1mx1+a2mx2+…+anmxn=bm
Then it is converted to the form
F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin
a11x1+a21x2+…+an1xn+xn+1=b1
a12x1+a22x2+…+an2xn+xn+2=b2
……………………………….
a1mx1+a2mx2+…+anmxn+xn+m=bm
Where M is infinite big numbers. In the resulting problem, the initial basis is immediately visible; the vectors with the artificially introduced variables xn+1, xn+2,…, xn+m should be taken as it. Since these vectors will have the form: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). The transformed problem is then solved using the simplex method algorithm. The initial reference plan of the transformed problem has the form (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…,bm). The original simplex table looks like this:
| Basis | coefficient CF | Plan | C1 | C2 | … | Cn | M | M | … | M |
| A1 | A2 | … | An | An+1 | An+2 | … | An+m | |||
| An+1 | M | b1 | a11 | a21 | … | an1 | 1 | 0 | … | 0 |
| An+2 | M | b2 | a12 | a22 | … | an2 | 0 | 1 | … | 0 |
| … | … | … | … | … | … | … | … | … | … | … |
| An+m | M | bm | a1m | a2m | … | anm | 0 | 0 | … | 1 |
| Z0 | ||||||||||
We determine the elements of the additional line using the formulas Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi
To determine the differences Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n
Zj-Cj=M∑mj=1aij-Cj
After receiving the original simplex table, it is transformed, trying to derive from the basis vectors corresponding to the introduced additional variables.
Since M is very big number, then among the differences Zj-Cj there will be many positive numbers. That is, there will be many candidates for inclusion in the basis among the vectors A1,A2,…,An
If some vector corresponds to the artificially introduced variables xn+1,xn+2,…,xn+m, then the corresponding vector is derived from the basis, and the simplex column of the table with this vector is crossed out and is not returned to it again. At the end of the simplex table transformation, two options are possible:
· all vectors corresponding to artificial variables have been derived from the basis, in this case all columns of the simplex table corresponding to additional variables will disappear, and the solution will be original problem
· the resulting optimal plan will still contain some additional variable, this means that the ODD of the original problem is empty, i.e., its restrictions are contradictory, therefore the original problem has no solutions at all.
Dual linear programming problems. Statement of problems, their properties.
Symmetric dual problems:
First standard form
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+…+an1xn>=b1
a12x1+a22x2+…+an2xn>=b2
…………………………………………..
a1mx1+a2mx2+…+anmxn>=bm
Dual problem
d(y)=b1y1+b2y2+…+bmymàmax
a11y1+a12y2+…+a1mym=0, V j=1,m
Non-septenary pair of dual problems
The original problem in canonical form
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+..+an1xn=b1
a12x1+a22x2+..+an2xn=b2
…………………………..
Lecture 3. Simplex tables. Algorithm of the simplex method.
§ 3 SIMPLEX METHOD
3.1. General idea of the simplex method. Geometric interpretation
The graphical method is applicable to a very narrow class of linear programming problems: it can effectively solve problems containing no more than two variables. The basic theorems of linear programming were considered, from which it follows that if a linear programming problem has an optimal solution, then it corresponds to at least one corner point of the solution polyhedron and coincides, according to at least, with one of the admissible basic solutions of the system of restrictions. A way to solve any linear programming problem was indicated: enumerate a finite number of feasible basic solutions to the system of constraints and select among them the one on which the objective function makes the optimal solution. Geometrically, this corresponds to enumerating all the corner points of the solution polyhedron. Such an exhaustive search will ultimately lead to an optimal solution (if it exists), but its practical implementation is associated with enormous difficulties, since for real problems the number of feasible basic solutions, although finite, can be extremely large.
The number of permissible basic solutions to be searched can be reduced if the search is not carried out randomly, but taking into account changes in the linear function, i.e. ensuring that each next solution is “better” (or at least “no worse”) than the previous one, according to the values of the linear function (increasing it when finding a maximum, decreasing it when finding a minimum 
).
This search allows you to reduce the number of steps when finding the optimum. Let's explain this with a graphic example.
Let the region of feasible solutions be represented by a polygon ABCDE. Let's assume that its corner point A corresponds to the original feasible basis solution. A random search would require testing five feasible basis solutions corresponding to the five corner points of the polygon. However, it is clear from the drawing that after the top A it is advantageous to move to a neighboring vertex IN, and then to the optimal point WITH. Instead of five, we went through only three vertices, consistently improving the linear function.
The idea of successively improving the solution formed the basis of a universal method for solving linear programming problems - simplex method or method of sequential improvement of the plan.
The geometric meaning of the simplex method consists in a sequential transition from one vertex of the constraint polyhedron (called the initial one) to the neighboring one, in which the linear function takes the best (at least not the worst) value in relation to the goal of the problem; until the optimal solution is found - the vertex where the optimal value of the goal function is achieved (if the problem has a final optimum).
The simplex method was first proposed by the American scientist J. Danzig in 1949, but back in 1939 the ideas of the method were developed by the Russian scientist L.V. Kantorovich.
The simplex method, which allows solving any linear programming problem, is universal. Currently, it is used for computer calculations, but simple examples using the simplex method can be solved manually.
To implement the simplex method - sequential improvement of the solution - it is necessary to master three main elements:
a way to determine some initial acceptable basic solution tasks;
the rule of transition to the best (more precisely, not worse) solution;
criterion for checking the optimality of the solution found.
To use the simplex method, the linear programming problem must be reduced to canonical form, i.e. the system of constraints must be presented in the form of equations.
The literature describes in sufficient detail: finding the initial support plan (initial admissible basic solution), also using the artificial basis method, finding the optimal support plan, solving problems using simplex tables.
3.2. Algorithm of the simplex method.
Let us consider the solution of the ZLP using the simplex method and present it in relation to the maximization problem.
1. Based on the conditions of the problem, its mathematical model is compiled.
2. The completed model is converted to the canonical form. In this case, a basis with an initial reference plan can be identified.
3. The canonical model of the problem is written in the form of a simplex table so that all free terms are non-negative. If the initial reference plan is selected, then proceed to step 5.
Simplex table: a system of constraint equations and an objective function are entered in the form of expressions resolved relative to the initial basis. A line containing the coefficients of the objective function 
, called 
– a string or a string of the target function.
4. Find the initial reference plan by performing simplex transformations with positive resolving elements corresponding to the minimum simplex relations, and without taking into account the signs of the elements 
–lines. If during the transformations a 0-row is encountered, all of whose elements, except for the free term, are zeros, then the system of constraint equations for the problem is inconsistent. If we encounter a 0-row in which, apart from the free term, there are no other positive elements, then the system of restrictive equations has no non-negative solutions.
We will call the reduction of system (2.55), (2.56) to a new basis simplex transformation . If a simplex transformation is considered as a formal algebraic operation, then one can notice that as a result of this operation, roles are redistributed between two variables included in a certain system linear functions: one variable goes from dependent to independent, and the other, on the contrary, goes from independent to dependent. This operation is known in algebra as Jordan elimination step.
5. The found initial support plan is examined for optimality:
a) if in 
– there are no negative elements in the row (not counting the free term), then the plan is optimal. If there are no zeros, then there is only one optimal plan; if there is at least one zero, then there is an infinite number of optimal plans;
b) if c 
– there is at least one negative element in the row, which corresponds to a column of non-positive elements, then 
;
c) if in 
– the row has at least one negative element, and its column has at least one positive element, then you can move to a new one reference plan, closer to optimal. To do this, the specified column must be designated as a resolving column, using the minimum simplex ratio, find the resolving row and perform a simplex transformation. The resulting reference plan is again examined for optimality. The described process is repeated until an optimal plan is obtained or until the unsolvability of the problem is established.
The column of coefficients for a variable included in the basis is called resolving. Thus, selecting a variable entered into the basis (or selecting a resolving column) by the negative element 
-strings, we provide increasing function 
.
It is a little more difficult to determine the variable to be excluded from the basis. To do this, they compose the ratios of free terms to the positive elements of the resolving column (such relations are called simplex) and find the smallest among them, which determines the row (resolving) containing the excluded variable. The choice of a variable excluded from the basis (or the choice of a resolving line) according to the minimum simplex relation guarantees, as has already been established, the positivity of the basis components in the new reference plan.
In point 3 of the algorithm, it is assumed that all elements of the free terms column are non-negative. This requirement is not necessary, but if it is met, then all subsequent simplex transformations are performed only with positive resolving elements, which is convenient for calculations. If there are negative numbers in the free terms column, then the resolving element is chosen as follows:
1) look at the line corresponding to some negative free term, for example 
– a row, and select any negative element in it, and the corresponding column is taken as resolving (we assume that the constraints of the problem are consistent);
2) make up the relations of the elements of the column of free terms to the corresponding elements of the resolving column that have the same signs (simplex relations);
3) choose the smallest of the simplex relations. This will determine the enabling string. Let it be, for example, R-line;
4) at the intersection of the resolving column and row, a resolving element is found. If the element is permissive 
–strings, then after the simplex transformation the free term of this string will become positive. Otherwise, in the next step we turn again to 
–line. If the problem is solvable, then after a certain number of steps there will be no negative elements left in the column of free terms.
If a certain real production situation is put into the form of a PLP, then the additional variables that have to be introduced into the model in the process of converting it to the canonical form always have a certain economic meaning.