An example of solving a direct and dual problem using the simplex method. Linear programming. Simplex method

If you need to solve a linear programming problem using simplex tables, then our online service will be of great help to you. The simplex method involves sequentially searching through all the vertices of the range of acceptable values ​​in order to find the vertex where the function takes an extreme value. At the first stage, some solution is found, which is improved at each subsequent step. This solution is called basic. Here is the sequence of actions when solving a linear programming problem using the simplex method:

First step. In the compiled table, first of all, you need to look at the column with free members. If there are negative elements in it, then it is necessary to move to the second step, if not, then to the fifth.

Second step. At the second step, it is necessary to decide which variable to exclude from the basis and which to include in order to recalculate the simplex table. To do this, we look through the column with free terms and find a negative element in it. The line with a negative element will be called leading. In it we find the maximum negative element in modulus, the corresponding column is the slave one. If there are negative values ​​among the free terms, but not in the corresponding row, then such a table will not have solutions. The variable in the leading row located in the column of free terms is excluded from the basis, and the variable corresponding to the leading column is included in the basis.

Table 1.

Third step. In the third step, we recalculate the entire simplex table using special formulas; these formulas can be seen using.

Fourth step. If after recalculation there are negative elements left in the column of free terms, then go to the first step; if there are none, then to the fifth.

Fifth step. If you have reached the fifth step, then you have found a solution that is acceptable. However, this does not mean that it is optimal. It will be optimal only if all elements in the F-string are positive. If this is not the case, then it is necessary to improve the solution, for which we find the leading row and column for the next recalculation using the following algorithm. Initially, we find the minimum negative number in line F, excluding the function value. The column with this number will be the leading one. In order to find the leading row, we find the ratio of the corresponding free term and the element from the leading column, provided that they are positive. The minimum ratio will allow you to determine the leading line. We recalculate the table again using the formulas, i.e. go to step 3.

Here is a manual (not applet) solution of two problems using the simplex method (similar to the applet solution) with detailed explanations in order to understand the algorithm for solving problems using the simplex method. The first problem contains inequality signs only “≤” (problem with an initial basis), the second can contain signs “≥”, “≤” or “=” (problem with an artificial basis), they are solved differently.

Simplex method, solving a problem with an initial basis

1)Simplex method for a problem with an initial basis (all signs of inequality constraints " ≤ ").

Let's write the problem in canonical form, i.e. we rewrite the inequality restrictions in the form of equalities, adding balance sheet variables:

This system is a system with a basis (basis s 1, s 2, s 3, each of them is included in only one equation of the system with a coefficient of 1), x 1 and x 2 are free variables. Problems to be solved using the simplex method must have the following two properties: - the system of constraints must be a system of equations with a basis; -free terms of all equations in the system must be non-negative.

The resulting system is a system with a basis and its free terms are non-negative, so we can apply simplex method. Let's create the first simplex table (Iteration 0) to solve the problem on simplex method, i.e. a table of coefficients of the objective function and a system of equations for the corresponding variables. Here “BP” means the column of basic variables, “Solution” means the column of the right-hand sides of the system equations. The solution is not optimal, because there are negative coefficients in the z-row.

simplex method iteration 0

To improve the solution, let's move on to the next iteration simplex method, we get the following simplex table. To do this you need to select enable column, i.e. a variable that will be included in the basis at the next iteration of the simplex method. It is selected by the largest absolute negative coefficient in the z-row (in the maximum problem) - in the initial iteration of the simplex method this is column x 2 (coefficient -6).

Then select enable string, i.e. a variable that will leave the basis at the next iteration of the simplex method. It is selected by the smallest ratio of the “Decision” column to the corresponding positive elements of the resolution column (column “Ratio”) - in the initial iteration this is row s 3 (coefficient 20).

Permissive element is at the intersection of the resolving column and the resolving row, its cell is highlighted in color, it is equal to 1. Therefore, at the next iteration of the simplex method, the variable x 2 will replace s 1 in the basis. Note that the relationship is not searched for in the z-string; a dash “-” is placed there. If there are identical minimal relations, then any of them is selected. If all coefficients in the resolution column are less than or equal to 0, then the solution to the problem is infinite.

Let's fill out the following table “Iteration 1”. We will get it from the “Iteration 0” table. The goal of further transformations is to turn the x2 resolution column into a unit column (with a one instead of the resolution element and zeros instead of the remaining elements).

1) Calculate row x 2 of the “Iteration 1” table. First, we divide all members of the resolving row s 3 of the “Iteration 0” table by the resolving element (it is equal to 1 in in this case) of this table, we get row x 2 in the table “Iterations 1”. Because the resolving element in this case is equal to 1, then row s 3 of the “Iteration 0” table will coincide with row x 2 of the “Iteration 1” table. Row x 2 of the Iteration 1 table we got 0 1 0 0 1 20, the remaining rows of the Iteration 1 table will be obtained from this row and the rows of the Iteration 0 table as follows:

2) Calculation of the z-row of the “Iteration 1” table. In place of -6 in the first row (z-row) in the x2 column of the Iteration 0 table, there should be a 0 in the first row of the Iteration 1 table. To do this, multiply all the elements of row x 2 of the table "Iteration 1" 0 1 0 0 1 20 by 6, get 0 6 0 0 6 120 and add this row with the first row (z - row) of the table "Iteration 0" -4 -6 0 0 0 0, we get -4 0 0 0 6 120. A zero 0 appears in the x 2 column, the goal is achieved. Elements of the resolution column x 2 are highlighted in red.

3) Calculation of row s 1 of the “Iteration 1” table. In place of 1 in s 1 row of the “Iteration 0” table there should be a 0 in the “Iteration 1” table. To do this, multiply all the elements of row x 2 of the table "Iteration 1" 0 1 0 0 1 20 by -1, get 0 -1 0 0 -1 -20 and add this row with s 1 - row of the table "Iteration 0" 2 1 1 0 0 64, we get the row 2 0 1 0 -1 44. In the x 2 column we get the required 0.

4) Calculate row s 2 of the “Iteration 1” table. In place 3 in s 2 row of the table "Iteration 0" there should be 0 in the table "Iteration 1". To do this, multiply all elements of row x 2 of the table “Iteration 1” 0 1 0 0 1 20 by -3, get 0 -3 0 0 -3 -60 and add this row with s 1 - row of the table “Iteration 0” 1 3 0 1 0 72, we get the row 1 0 0 1 -3 12. In the x 2 column, the required 0 is obtained. The x 2 column in the “Iteration 1” table has become a unit, it contains one 1 and the rest 0.

The rows of the table “Iteration 1” are obtained according to the following rule:

New row = Old row – (Old row resolution column coefficient)*(New resolution row).

For example, for a z-string we have:

Old z-string (-4 -6 0 0 0 0) -(-6)*New resolving string -(0 -6 0 0 -6 -120) =New z-string (-4 0 0 0 6 120).

For the following tables, recalculation of table elements is done in a similar way, so we omit it.

simplex method iteration 1

Resolving column x 1, resolving row s 2, s 2 leaves the basis, x 1 enters the basis. In exactly the same way, we obtain the remaining simplex tables until we obtain a table with all positive coefficients in the z-row. This is a sign of an optimal table.

simplex method iteration 2

Resolving column s 3, resolving row s 1, s 1 leaves the basis, s 3 enters the basis.

simplex method iteration 3

In the z-row, all coefficients are non-negative, therefore, the optimal solution x 1 = 24, x 2 = 16, z max = 192 is obtained.

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).
Obviously, the number of possible bases for any problem is finite (and not very large).
Therefore, sooner or later, the answer will be received.

How is the transition from one basis to another carried out?
It is more convenient to record the solution in the form of tables. Each line is equivalent to an equation of the system. The highlighted line consists of the coefficients of the function (compare for yourself). This allows you to avoid rewriting variables every time, which significantly saves time.
In the highlighted line, select the largest positive coefficient. This is necessary in order to obtain a function value that is at least no less than the existing one.
Column selected.
For positive coefficients of the selected column, we calculate the ratio Θ and select the smallest value. This is necessary so that after the transformation the column of free terms remains positive.
Row selected.
Therefore, the element that will be the basis has been determined. Next we count.

To sell three groups of goods, a commercial enterprise has three types of limited material and monetary resources in the amount of b 1 = 240, b 2 = 200, b 3 = 160 units. At the same time, for the sale of 1 group of goods for 1 thousand rubles. commodity turnover, the resource of the first type is consumed in the amount of a 11 = 2 units, the resource of the second type in the amount of a 21 = 4 units, the resource of the third type in the amount of a 31 = 4 units. For the sale of 2 and 3 groups of goods for 1 thousand rubles. turnover is consumed according to the resource of the first type in the amount of a 12 = 3, a 13 = 6 units, the resource of the second type in the amount of a 22 = 2, a 23 = 4 units, the resource of the third type in the amount of a 32 = 6, a 33 = 8 units . Profit from the sale of three groups of goods for 1 thousand rubles. turnover is respectively c 1 = 4, c 2 = 5, c 3 = 4 (thousand rubles). Determine the planned volume and structure of trade turnover so that the profit of the trading enterprise is maximized.

To the direct problem of turnover planning, solved by simplex method, compose dual problem linear programming.
Install conjugate pairs of variables straight and dual problem.
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

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

We solve the simplex method.

We introduce additional variables x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 to transform the inequalities into equalities.

Let's take x 4 = 240 as a basis; x 5 = 200; x 6 = 160.

We enter the data into simplex table

Simplex table No. 1

Objective function:

0 240 + 0 200 + 0 160 = 0

We calculate estimates using the formula:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Since there are negative estimates, the plan is not optimal. Lowest score:

We introduce the variable x 2 into the basis.

We define a variable emerging from the basis. To do this, we find the smallest non-negative ratio for the x2 column.

= 26.667

Smallest non-negative: Q 3 = 26.667. We derive the variable x 6 from the basis

Divide the 3rd line by 6.
From the 1st line, subtract the 3rd line, multiplied by 3
From the 2nd line we 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.

Solution to the problem:

Answer

That is, it is necessary to sell the first type of goods in the amount of 40 thousand rubles. Products of types 2 and 3 do not need to be sold. In this case, the maximum profit will be F max = 160 thousand rubles.

Solution of the dual problem

The dual problem has the form:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

We introduce additional variables y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 to transform the inequalities into equalities.

Conjugate pairs of variables of the direct and dual problems have the form:

From the last simplex table No. 3 of the direct problem, we find the solution to the dual problem:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Let's consider simplex method for solving linear programming (LP) problems. It is based on the transition from one reference plan to another, in which the value objective function increases.

The simplex method algorithm is as follows:

1. We transform the original problem into canonical form 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.
2. 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.
3. 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.
4. 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.
5. 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 line are divided by the resolution element, and the remaining elements are recalculated according to the rectangle rule.
6. 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: Higher 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