Solving a production problem using the tabular simplex method. An example of solving a problem. Simplex method for solving ZLP

This method is a method of purposeful enumeration of reference solutions to a linear programming problem. It allows, in a finite number of steps, either to find an optimal solution or to establish that there is no optimal solution.

1. Indicate a method for finding the optimal reference solution
2. Indicate the method of transition from one reference solution to another, at which the value objective function will be closer to optimal, i.e. indicate a way to improve the reference solution
3. Set criteria that allow you to promptly stop searching for support solutions at the optimal solution or draw a conclusion about the absence of an optimal solution.

Algorithm of the simplex method for solving linear programming problems

1. Bring the problem to canonical form
2. Find the initial support solution with a “unit basis” (if there is no support solution, then the problem does not have a solution due to the incompatibility of the system of constraints)
3. Calculate estimates of vector decompositions based on the reference solution and fill in the table of the simplex method
4. If the criterion for the uniqueness of the optimal solution is satisfied, then the solution of the problem ends
5. If the condition for the existence of a set of optimal solutions is met, then all optimal solutions are found by simple enumeration

An example of solving a problem using the simplex method

Solve the problem using the simplex method:

Solution:

We bring the problem to canonical form.

For this purpose in left side For the first inequality constraint, we introduce an additional variable x 6 with a coefficient of +1. The variable x 6 is included in the objective function with a coefficient of zero (i.e., it is not included).

We get:

We find the initial support solution. To do this, we equate free (unresolved) variables to zero x1 = x2 = x3 = 0.

We get reference solution X1 = (0,0,0,24,30,6) with unit basis B1 = (A4, A5, A6).

We calculate estimates of vector decompositions conditions on the basis of the reference solution according to the formula:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vector of coefficients of the objective function for the basic variables
• X k = (x 1k, x 2k, ..., x mk) - vector of expansion of the corresponding vector A k according to the basis of the reference solution
• C k is the coefficient of the objective function for the variable x k.

The estimates of the vectors included in the basis are always equal to zero. The reference solution, coefficients of expansions and estimates of expansions of vectors of conditions on the basis of the reference solution are written in simplex table:

At the top of the table, for the convenience of calculating estimates, the coefficients of the objective function are written. The first column "B" contains the vectors included in the basis of the reference solution. The order in which these vectors are written corresponds to the numbers of allowed unknowns in the constraint equations. In the second column of the table "C b" the coefficients of the objective function for the basic variables are written in the same order. At correct location The coefficients of the objective function in the column "C b" of the estimate of the unit vectors included in the basis are always equal to zero.

IN last line tables with estimates of Δ k in the column “A 0” the values ​​of the objective function on the reference solution Z(X 1) are written.

The initial support solution is not optimal, since in the maximum problem the estimates Δ 1 = -2, Δ 3 = -9 for vectors A 1 and A 3 are negative.

According to the theorem on improving the support solution, if in a maximum problem at least one vector has a negative estimate, then you can find a new support solution on which the value of the objective function will be greater.

Let us determine which of the two vectors will lead to a larger increment in the objective function.

The increment of the objective function is found by the formula: .

We calculate the values ​​of the parameter θ 01 for the first and third columns using the formula:

We obtain θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Table 26.1).

We find the increment of the objective function when introducing into the basis the first vector ΔZ 1 = - 6*(- 2) = 12, and the third vector ΔZ 3 = - 3*(- 9) = 27.

Consequently, for a faster approach to the optimal solution, it is necessary to introduce vector A3 into the basis of the reference solution instead of the first vector of the basis A6, since the minimum of the parameter θ 03 is achieved in the first row (l = 1).

We perform the Jordan transformation with the element X13 = 2, we obtain the second reference solution X2 = (0,0,3,21,42,0) with the basis B2 = (A3, A4, A5). (Table 26.2)

This solution is not optimal, since vector A2 has a negative estimate Δ2 = - 6. To improve the solution, it is necessary to introduce vector A2 into the basis of the reference solution.

We determine the number of the vector derived from the basis. To do this, we calculate the parameter θ 02 for the second column, it is equal to 7 for l = 2. Consequently, we derive the second basis vector A4 from the basis. We perform the Jordan transformation with the element x 22 = 3, we obtain the third reference solution X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Table 26.3).

This solution is the only optimal one, since for all vectors not included in the basis the estimates are positive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Answer: max Z(X) = 201 at X = (0.7,10,0.63).

Linear programming method in economic analysis

Linear programming method makes it possible to justify the most optimal economic solution under conditions of severe restrictions related to the resources used in production (fixed assets, materials, labor resources). The use of this method in economic analysis makes it possible to solve problems related mainly to planning the activities of an organization. This method helps to determine the optimal quantities of product output, as well as the directions for the most effective use of the production resources available to the organization.

Using this method, the so-called extremal problems are solved, which consists in finding extreme values, that is, the maximum and minimum of functions of variable quantities.

This period is based on the solution of the system linear equations in cases where the analyzed economic phenomena are connected linearly, strictly functional dependence. The linear programming method is used to analyze variables in the presence of certain limiting factors.

It is very common to solve the so-called transport problem using the linear programming method. The content of this task is to minimize the costs incurred in connection with the operation of vehicles under existing restrictions regarding the number of vehicles, their carrying capacity, the duration of their operation, if there is a need to service the maximum number of customers.

Besides this, this method is widely used in solving scheduling problems. This task consists of such a distribution of operating time for the personnel of a given organization that would be most acceptable both for the members of this personnel and for the clients of the organization.

This task is to maximize the number of clients served under conditions of limitations on the number of available staff members, as well as the working time fund.

Thus, the linear programming method is quite common in placement and usage analysis. various types resources, as well as in the process of planning and forecasting the activities of organizations.

Nevertheless, mathematical programming can also be applied to those economic phenomena, the relationship between which is not linear. For this purpose, nonlinear, dynamic and convex programming methods can be used.

Nonlinear programming relies on the nonlinear nature of the objective function or constraints, or both. The forms of the objective function and inequality constraints in these conditions can be different.

Nonlinear programming is used in economic analysis, in particular, when establishing the relationship between indicators expressing the efficiency of an organization’s activities and the volume of this activity, the structure of production costs, market conditions, etc.

Dynamic programming is based on constructing a decision tree. Each tier of this tree serves as a stage for determining the consequences of a previous decision and for eliminating ineffective options for that decision. Thus, dynamic programming has a multi-step, multi-stage nature. This type of programming is used in economic analysis to find optimal options development of the organization both now and in the future.

Convex programming is a type of nonlinear programming. This type of programming expresses the nonlinear nature of the relationship between the results of an organization’s activities and its costs. Convex (aka concave) programming analyzes convex objective functions and convex constraint systems (feasibility points). Convex programming is used in the analysis of economic activities with the aim of minimizing costs, and concave programming with the aim of maximizing income under existing restrictions on the action of factors that influence the analyzed indicators in the opposite way. Consequently, with the types of programming under consideration, convex objective functions are minimized, and concave objective functions are maximized.

Step 0. Preparatory stage.

We reduce the LP problem to special form (15).

Step 1. Compiling simplex table, corresponding to the special form:

Note that this table corresponds to an admissible basic solution
problems (15). The value of the objective function on this solution

Step 2. Optimality check

If among the elements of the index row there are simplex tables
there is not a single positive element then
, the optimal solution to the LP problem is found:. The algorithm terminates.

Step 3. Undecidability check

If among
there is a positive element
, and in the corresponding column
there is not a single positive element
, then the objective function L is unbounded from below on the admissible set. In this case, there is no optimal solution. The algorithm terminates.

Step 4. Selecting a Leading Column q

Among the elements
choose the maximum positive element
.We declare this column to be the leading (permissive) column.

Step 5. Lead line selection p

Among the positive elements of the column
find the element
, for which the equality holds

.

String p We declare it to be leading (permitting). Element
We declare it to be the leader (permitting).

Step 6. Simplex table conversion

We create a new simplex table in which:

a) instead of the basic variable write down , instead of a nonbasic variable write down ;

b) the leading element is replaced by the inverse value
;

c) all elements of the leading column (except
) multiply by
;

d) all elements of the leading line (except
) multiply by ;

e) the remaining elements of the simplex table are converted according to the following “rectangle” scheme.

The product of three factors is subtracted from the element:

the first is the corresponding element of the leading column;

the second is the corresponding element of the leading line;

the third is the reciprocal of the leading element
.

The transformed element and the three factors corresponding to it are precisely the vertices of the “rectangle”.

Step 7 The transition to the next iteration is carried out by returning to step 2.

2.3. Simplex method algorithm for the maximum problem

The simplex method algorithm for the maximum problem differs from the algorithm for the minimum problem only in the signs of the index line of the coefficients in the objective function
, namely:

In step 2:
:

In step 3
. The objective function is unbounded from above on the admissible set.

In step 4:
.

2.4. An example of solving a problem using the simplex method

Solve the problem written in the form (15).

Let's create a simplex table:

Since the coefficients of the line of the objective function are non-negative, the initial basis solution is not optimal. The value of the objective function for this basis L=0.

Select the leading column - this is the column corresponding to the variable .

Select the leading line. To do this we find
. Therefore, the leading line corresponds to the variable .

We transform the simplex table by introducing a variable into the basis and outputting the variable from the basis. We get the table:

One iteration of the method is completed. Let's move on to a new iteration. The resulting table is not optimal. The basic solution corresponding to the table has the form . The value of the objective function on this basis L= -2.

The leading column here is the column corresponding to the variable . Leading line – the line corresponding to the variable . After carrying out the transformations, we obtain a simplex table:

Another iteration completed. Let's move on to a new iteration.

The line of the objective function does not contain positive values, which means that the corresponding basic solution is optimal, and the algorithm terminates.

An example of solving a problem using the simplex method is considered, as well as an example of a solution dual problem.

Problem condition

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

To the direct problem of turnover planning, solved by simplex method, compose dual problem linear programming.
Install conjugate pairs of variables direct and dual problems.
According to conjugate pairs of variables, from the solution of the direct problem we obtain solution of the dual problem, in which it is produced resource assessment, spent on the sale of goods.

Solving the problem using the simplex method

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

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

We solve the simplex method.

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

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

We enter the data into simplex table

Simplex table No. 1

Objective function:

0 240 + 0 200 + 0 160 = 0

We calculate estimates using the formula:

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

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

We introduce the variable x 2 into the basis.

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

= 26.667

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

Divide the 3rd line by 6.
From the 1st line, subtract the 3rd line, multiplied by 3
From the 2nd line, subtract the 3rd line, multiplied by 2

We calculate:

We get 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. 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

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, during which the value of the 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 string 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