Find the maximum of a function using the simplex method. Simplex method for solving linear programming problems

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 proceed to step 5 of the algorithm, corresponding to finding the 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.

x 2

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.	basic variables
	Table 1.	Free members under restrictions	Non-basic variables	...	x 1	...
x l	x n	x n+1	b 1	...	a 11	...	a 12
a 1l	a 1n	x n+2	b 2	...	a 21	...	a 22
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
a 2l	a 2n	x n+r	b2	...	a r1	...	a r2
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
a rl	arn	x n+m	b m	...	a m1	...	a m2
a ml	a mn	F(x)max	F 0	...	F(x)max	...	-c 1

-c 2

-c n

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 of the 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 rest of the 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 float column must be positive.

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 of the 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 it is found optimal solution

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 cycling occurs, characterized by the fact that the same combination of BPs begins to repeat with a certain frequency (the value of the function F is preserved) and it is impossible to move to a new feasible 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 produce random selection

new basic 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.

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

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 maximum profit And optimal plan release of products providing it (find).

shirt 1

shirt 2

shirt 3

Reserves

threads (m.)

buttons (pcs.)

640

textile (

Profit (r.)

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.

№

c B

A o

x 1

x 2

x 3

x 4

x 5

x 6

Simplex

relationship

x 4

32/3

x 5

640

x 6

F j - c j

-2

-5

-4

x 2

32/3

1/9

1/3

1/9

x 5

1600/3

170/9

80/3

-10/9

x 6

68/3

7/9

4/3

-2/9

F j - c j

160/3

-13/9

-7/3

5/9

x 2

-1/12

1/6

-1/4

x 5

10/3

-20

x 3

7/12

-1/6

3/4

204/7

F j - c j

-1/12

1/6

7/4

x 2

1/4

1/40

-3/4

x 1

3/10

-6

x 3

-3/4

-7/40

17/4

F j - c j

1/4

1/40

5/4

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.

x 1

x 2

S 1

x 1

x 2

S 2

x 1

x 2

S 3

A variable is called basic for a given equation if it is included in this equation with a coefficient of one and is not included in the remaining equations (provided that there is a positive number on the right side of the equation).
If each equation has a basis variable, then the system is said to have a basis.
Variables that are not basic are called free. (see system below)

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.

x 1

x 2

S 1

Therefore, the element that will be the basis has been determined. Next we count.

x 1

x 2

S 2

x 1

x 2

S 3

R 1
x 1 = 0 x 2 = 0 S 1 = 0

S 2 = 15 S 3 = 4 R 1 = 1

=> W = 1

x 1	x 2	S 1	S 2	S 3	Therefore, the element that will be the basis has been determined. Next we count.	Step #1	Θ
-1	1	-1	0	0	1	1	1: 1 = 1
1	3	0	1	0	0	15	15: 3 = 5
-2	1	0	0	1	0	4	4: 1 = 4
1	-1	1	0	0	0	St. member
-1	1	-1	0	0	1	1
4	0	3	1	0	-3	12
-1	0	1	0	1	-1	3
0	0	0	0	0	1	W - 1

x 1

x 2

S 1

x 1

S 1

S 2

x 1

S 1

S 3

=> W = 1

x 1	x 2	S 1	S 2	S 3	Step #1	Θ
-1	1	-1	0	0	1
4	0	3	1	0	12	12: 4 = 3
-1	0	1	0	1	3
4	0	1	0	0	W - 0
-1	1	-1	0	0	1
1	0	3/4	1/4	0	3
-1	0	1	0	1	3
4	0	1	0	0	W - 0
0	1	-1/4	1/4	0	4
1	0	3/4	1/4	0	3
0	0	7/4	1/4	1	6
0	0	-2	-1	0	F - 1

F - 13
S 1 = 0 S 2 = 0

x 1 = 3 x 2 = 4 S 3 = 6

=> F - 13 = 0 => F = 13 There are no positive coefficients among the selected row coefficients. Therefore found highest value

functions F.

Step 0. Preparatory stage. We reduce the LP problem to (15).

special form Step 1. Compiling simplex table

, corresponding to the special form:
Note that this table corresponds to an admissible basic solution problems (15). Meaning objective function

on this decision 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 Lead line selection String
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 a) instead of the basic variable ;

, instead of a nonbasic variable
;

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 transformed 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 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.

One of the solution methods optimization problems (usually associated with finding the minimum or maximum) linear programming 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's consider the algorithm of the tabular simplex method using the example of the solution production task, which boils down to finding production plan ensuring 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 the system linear equations by introducing additional non-negative variables into it ( 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 Compiling:

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.