When calculating simplex tables, the method is used. Linear programming. Simplex method

Thread, buttons and fabric are used to make three types of shirts. Stocks of thread, buttons and fabric, the norms of their consumption for sewing one shirt are indicated in the table. Find the maximum profit and the optimal product production plan that ensures it (find).

The solution of the problem

Model building

Through and the number of shirts of the 1st, 2nd and 3rd types intended for release.

Then the resource restrictions will look like this:

In addition, according to the meaning of the task

Objective function expressing the profit received:

We get the following linear programming problem:

Reducing a linear programming problem to canonical form

Let's reduce the problem to canonical form. Let's introduce additional variables. We introduce all additional variables into the objective function with a coefficient equal to zero. We add additional variables to the left sides of the restrictions that do not have a preferred form, and we obtain equalities.

Solving the problem using the simplex method

Fill out the simplex table:

Since we are solving the problem to the maximum, the presence of negative numbers in the index line when solving the problem to the maximum indicates that we have not obtained the optimal solution and that it is necessary to move on from the table of the 0th iteration to the next one.

We proceed to the next iteration as follows:

leading column corresponds

The key row is determined by the minimum ratio of free terms and members of the leading column (simplex relations):

At the intersection of the key column and the key row we find the enabling element, i.e. 9.

Now we proceed to compiling the 1st iteration: Instead of a unit vector, we introduce the vector .

IN new table in place of the enabling element we write 1, all other elements of the key column are zeros. The key string elements are divided into the enable element. All other elements of the table are calculated using the rectangle rule.

The key column for the 1st iteration corresponds to

The resolving element is the number 4/3. We derive the vector from the basis and introduce the vector instead. We get the table of the 2nd iteration.

The key column for the 2nd iteration corresponds to

We find the key line, for this we define:

The resolving element is the number 10/3. We derive the vector from the basis and introduce the vector instead. We get the table of the 3rd iteration.

In the index row, all terms are non-negative, so the following solution to the linear programming problem is obtained (we write it out from the column of free terms):

It is necessary to sew 24 shirts of the 1st type, 7 shirts of the 2nd type and 3 shirts of the 3rd type. In this case, the profit received will be maximum and amount to 95 rubles.

You can find help in solving your problems on this subject by sending a message on VKontakte, Viber or filling out the form. Solution cost homework starts from 7 BYN. per task (200 Russian rubles), but not less than 10 Belarusian rubles. (RUB 300) for the entire order. Detailed design. The cost of online exam assistance (in this case, 100% prepayment is required) is from 30 BYR. (1000 Russian rubles) for solving the ticket.

If the problem statement contains restrictions with the ≥ sign, then they can be reduced to the form ∑a ji b j by multiplying both sides of the inequality by -1. Let us introduce m additional variables x n+j ≥0(j =1,m) and transform the restrictions to the form of equalities

(2)

Let us assume that all initial task variables x 1 , x 2 ,..., x n – non-basic. Then the additional variables will be basic, and a particular solution to the system of constraints has the form

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)

Since in this case the value of the goal function F 0 = 0, we can represent F(x) as follows:

F(x)=∑c i x i +F 0 =0 (4)

The initial simplex table (simplex table 1) is compiled based on equations (2) and (4). If the additional variables x n+j are preceded by a “+” sign, as in (2), then all the coefficients in front of the variables x i and the free term b j are entered into the simplex table without changes. When maximizing the goal function, the coefficients are entered in the bottom row of the simplex table with opposite signs. The free terms in the simplex table determine the solution to the problem.

The algorithm for solving the problem is as follows:

1st step. The members of the free members column are viewed. If they are all positive, then acceptable basic solution found and you should go to step 5 of the algorithm, corresponding to finding optimal solution. If the initial simplex table has negative free terms, then the solution is not valid and you should go to step 2.

2nd step. To find an admissible solution, it is carried out, and it is necessary to decide which of the non-basic variables to include in the basis and which variable to remove from the basis.

Table 1.

To do this, select any of the negative elements of the column of free terms (let it be b 2 leading, or resolving. If there are no negative elements in the row with a negative free term, then the system of constraints is inconsistent and the problem has no solution.

At the same time, the variable that is the first to change sign when the selected NP x l increases is excluded from the BP. This will be x n+r, the index r of which is determined from the condition

those. the variable that has the smallest ratio of the free term to the element of the selected leading column. This relationship is called simplex relation. Only positive simplex relations should be considered.

The line corresponding to the variable x n+r is called leading, or allowing. The element of the simplex table a rl, located at the intersection of the leading row and the leading column, is called the leading, or resolving element. Finding the leading element ends the work with each regular simplex table.

3rd step. A new simplex table is calculated, the elements of which are recalculated from the elements of the simplex table previous step and are marked with a prime, i.e. b" j , a" ji , c" i , F" 0 . The elements are recalculated using the following formulas:

First, the new simplex table will fill in the row and column that were leading in the previous simplex table. Expression (5) means that the element a" rl in place of the leading element is equal to the reciprocal of the element of the previous simplex table. The elements of the row a ri are divided by the leading element, and the elements of the column a jl are also divided by the leading element, but are taken with the opposite sign. The elements b" r and c" l are calculated according to the same principle.

The remaining formulas can be easily written using .

The rectangle is constructed according to the old simplex table in such a way that one of its diagonals is formed by the recalculated (a ji) and leading (a rl) elements (Fig. 1). The second diagonal is determined uniquely. To find a new element a" ji, the product of the elements of the opposite diagonal divided by the leading element is subtracted from element a ji (this is indicated by the “-” sign next to the cell). Elements b" j, (j≠r) and c" i are recalculated in the same way. (i≠l).

4th step. The analysis of the new simplex table begins with the 1st step of the algorithm. The action continues until a feasible basic solution is found, i.e. all elements of the free members column must be positive.

5th step. We believe that an admissible basic solution has been found. We look at the coefficients of the line of the goal function F(x) . A sign of the optimality of a simplex table is the non-negativity of the coefficients for non-basic variables in the F-row.

Rice. 1. Rectangle rule

If among the coefficients of the F-row there are negative ones (with the exception of the free term), then you need to move on to another basic solution. When maximizing the objective function, the basis includes one of the non-basic variables (for example x l), the column of which corresponds to the maximum absolute value negative coefficient c l in the bottom row of the simplex table. This allows you to select the variable whose increase leads to an improvement in the goal function. The column corresponding to the variable x l is called the leading column. At the same time, that variable x n+r is excluded from the basis, the index r of which is determined by the minimum simplex relation:

The row corresponding to x n+r is called leading, and the element of the simplex table a rl, standing at the intersection of the leading row and the leading column, is called leading element.

6th step. according to the rules outlined in step 3. The procedure continues until an optimal solution is found or it is concluded that it does not exist.

During solution optimization, if all elements in the leading column are non-positive, then the leading row cannot be selected. In this case, the function in the region of feasible solutions to the problem is not bounded above and F max ->&∞.

If, at the next step of searching for an extremum, one of the basic variables becomes equal to zero, then the corresponding basic solution is called degenerate. In this case, a so-called looping occurs, characterized by the fact that certain frequency the same combination of BP begins to repeat (the value of the function F is preserved) and it is impossible to move to a new admissible basic solution. Looping is one of the main disadvantages of the simplex method, but it is relatively rare. In practice, in such cases, they usually refuse to enter into the basis the variable whose column corresponds to the maximum absolute value of the negative coefficient in the goal function, and randomly select a new basis solution.

Example 1. Solve the problem

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1.2 ≥0)

Using the simplex method and give a geometric interpretation of the solution process.

A graphical interpretation of the solution to the problem is presented in Fig. 2. The maximum value of the goal function is achieved at the vertex of the ODZP with coordinates . Let's solve the problem using simplex tables. Let's multiply the second constraint by (-1) and introduce additional variables to bring the inequalities to the form of equalities, then

We take the initial variables x 1 and x 2 as non-basic, and consider the additional x 3, x 4 and x 5 as basic and compose a simplex table (simplex table 2). The solution corresponding to the simplex table. 2, is not valid; the leading element is outlined and selected in accordance with step 2 of the previous algorithm. The following simplex table. 3 defines an admissible basic solution; the vertex of the ODZP in Fig. 1 corresponds to it. 2 The leading element is outlined and selected in accordance with the 5th step of the problem solving algorithm. Table 4 corresponds to the optimal solution to the problem, therefore: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Rice. 2. Graphic solution tasks

Liked? Add to bookmarks

Solving problems using the simplex method: online examples

Task 1. The company produces bathroom shelves in two sizes - A and B. Sales agents estimate that up to 550 shelves can be sold on the market per week. Each type A shelf requires 2 m2 of material, and each type B shelf requires 3 m2 of material. The company can receive up to 1200 m2 of material per week. To manufacture one shelf of type A, 12 minutes of machine time are required, and to manufacture one shelf of type B - 30 minutes; The machine can be used 160 hours a week. If the profit from the sale of shelves of type A is 3 monetary units, and from shelves of type B - 4 monetary units. units, then how many shelves of each type should be produced per week?

Task 2. Solve a problem linear programming simplex method.

Task 3. The company produces 3 types of products: A1, A2, A3, using two types of raw materials. The costs of each type of raw material per unit of production, the reserves of raw materials for the planning period, as well as the profit from a unit of production of each type are known.

1. How many items of each type must be produced to maximize profit?
2. Determine the status of each type of raw material and its specific value.
3. Determine the maximum interval for changes in inventories of each type of raw material, within which the structure of the optimal plan, i.e. The production nomenclature will not change.
4. Determine the quantity of products produced and the profit from production when increasing the stock of one of the scarce types of raw materials to the maximum possible (within the given range of output) value.
5. Determine the intervals of change in profit from a unit of production of each type at which the resulting optimal plan will not change.

Task 4. Solve a linear programming problem simplex method:

Task 5. Solve a linear programming problem using the simplex method:

Task 6. Solve the problem using the simplex method, considering as the initial reference plan the plan given in the condition:

Task 7. Solve the problem using the modified simplex method.
To produce two types of products A and B, three types of technological equipment are used. To produce a unit of product A, equipment of the first type uses a1=4 hours, equipment of the second type a2=8 hours, and equipment of the third type a3=9 hours. To produce a unit of product B, equipment of the first type uses b1=7 hours, equipment of the second type b2=3 hours, and equipment of the third type b3=5 hours.
Equipment of the first type can work for the production of these products for no more than t1=49 hours, equipment of the second type for no more than t2=51 hours, equipment of the third type for no more than t3=45 hours.
The profit from the sale of a unit of finished product A is ALPHA = 6 rubles, and product B is BETTA = 5 rubles.
Draw up a plan for the production of products A and B, ensuring maximum profit from their sale.

Task 8. Find the optimal solution using the dual simplex method

Linear programming problems. It is in a sequential construction characterizing the process under consideration. The solution is divided into three main stages: selection of variables, construction of a system of constraints and search objective function.

Based on this division, the problem condition can be rephrased as follows: extremum of the objective function Z(X) = f(x1, x2, … ,xn) → max (min) and the corresponding variables, if it is known that they satisfy the system of constraints: Φ_i ( x1, x2, … ,xn) = 0 for i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 for i = k+1, k+2, …, m.

The system of restrictions must be brought to a canonical form, i.e. to the system linear equations, where the number of variables more number equations (m > k). In this system there will certainly be variables that can be expressed through other variables, and if this is not the case, then they can be introduced artificially. In this case, the first ones are called basis or artificial basis, and the second ones are free.

It is more convenient to consider the simplex method on specific example. Let it be given linear function f(x) = 6x1 + 5x2 + 9x3 and the system of restrictions: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. It is required to find the maximum value of the function f(x).

SolutionAt the first stage, specify the initial (reference) solution of the system of equations absolutely randomly, which must satisfy this system of restrictions. IN in this case the introduction of artificial is required, i.e. basic variables x4, x5 and x6 as follows: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.

As you can see, the inequalities have been transformed into equalities thanks to the added variables x4, x5, x6, which are non-negative quantities. Thus, you have brought the system to its canonical form. The variable x4 is included in the first equation with a coefficient of 1, and in the second equation with a coefficient of 0, the same is true for the variables x5, x6 and the corresponding equations, which corresponds to the definition of the basis.

You have prepared the system and found the initial reference solution – X0 = (0, 0, 0, 25, 20, 18). Now present the coefficients of the variables and the free terms of the equations (the numbers to the right of the “=” sign) in the form of a table to optimize further calculations (see figure).

The essence of the simplex method is to bring this table to a form in which all the numbers in row L will be non-negative values. If it turns out that this is impossible, then the system does not have an optimal solution at all. First, select the smallest element of this line, which is -9. The number is in the third column. Convert the corresponding x3 variable to a basis variable. To do this, divide the line by 3 so that the cell ends up with 1.

Now you need the cells and to turn to 0. To do this, subtract from the corresponding numbers of the third row by 3. From the elements of the second row - the elements of the third, multiplied by 2. And, finally, from the elements of the L row - multiplied by (-9). You have obtained the second reference solution: f(x) = L = 54 with x1 = (0, 0, 6, 7, 8, 0).

One of the methods for solving optimization problems ( usually associated with finding the minimum or maximum) linear programming is called . Simplex method includes a whole group of algorithms and methods for solving linear programming problems. One of these methods, which involves recording the source data and recalculating them in a special table, is called tabular simplex method .

Let us consider the algorithm of the tabular simplex method using the example of the solution production task, which boils down to finding a production plan that ensures maximum profit.

Input data for the simplex method problem

The company produces 4 types of products, processing them on 3 machines.

Time standards (min./piece) for processing products on machines are specified by matrix A:

The machine operating time fund (min.) is specified in matrix B:

Profit from the sale of each unit of product (RUB/piece) is given by matrix C:

Purpose of the production task

Draw up a production plan that will maximize the profit of the enterprise.

Solving the problem using the tabular simplex method

(1) Let us denote by X1, X2, X3, X4 the planned number of products of each type. Then the desired plan: ( X1, X2, X3, X4)

(2) Let's write down the plan constraints in the form of a system of equations:

(3) Then the target profit is:

That is, the profit from fulfilling the production plan should be maximum.

(4) To solve the resulting problem on conditional extreme, we replace the system of inequalities with a system of linear equations by introducing into it additional non-negative variables ( X5, X6, X7).

(5) Let's accept the following reference plan:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Let's enter the data into simplex table:

In the last line we enter the coefficients of the objective function and its value itself with the opposite sign;

(7) Select in last line greatest (modulo) a negative number.

Let's calculate b = N / Items_of_the_selected_column

Among the calculated values ​​of b we choose least.

The intersection of the selected column and row will give us the resolving element. We change the basis to a variable corresponding to the resolving element ( X5 to X1).

• The resolving element itself turns to 1.
• For elements of the resolution line – a ij (*) = a ij / RE ( that is, we divide each element by the value of the resolving element and obtain new data).
• For elements of the resolution column, they are simply reset to zero.
• We recalculate the remaining elements of the table using the rectangle rule.

a ij (*) = a ij – (A * B / RE)

As you can see, we take the current cell being recalculated and the cell with the resolving element. They form opposite corners of the rectangle. Next, we multiply the values ​​from the cells of the other 2 corners of this rectangle. This work ( A * B) divide by the resolving element ( RE). And subtract from the current cell being recalculated ( a ij) what happened. We get a new value - a ij (*).

(9) Check the last line again ( c) on presence of negative numbers. If they are not there, the optimal plan has been found, go to last stage solving the problem. If there is, the plan is not yet optimal, and the simplex table needs to be recalculated again.

Since in the last line we again have negative numbers, we begin a new iteration of calculations.

(10) Since there are no negative elements in the last line, this means that we have found the optimal production plan! Namely: we will produce those products that have moved to the “Basis” column - X1 and X2. We know the profit from the production of each unit of output ( matrix C). It remains to multiply the found production volumes of products 1 and 2 with profit per 1 piece, we get the final ( maximum! ) profit for a given production plan.

ANSWER:

X1 = 32 pcs., X2 = 20 pcs., X3 = 0 pcs., X4 = 0 pcs.

P = 48 * 32 + 33 * 20 = 2,196 rub.

Galyautdinov R.R.

© Copying of material is permissible only if a direct hyperlink to