. Simplex Method Algorithm

Example 5.1. Solve the following linear programming problem using the simplex method:

Solution:

I iteration:

x3, x4, x5, x6 x1,x2. We express the basic variables in terms of the free ones:

We bring the objective function to the following form:

Based on the obtained problem, we will form the initial simplex table:

Table 5.3

Initial simplex table

				Estimated relations

According to the definition of the basic solution, the free variables are equal to zero, and the values of the basic variables are equal to the corresponding values of the free numbers, i.e.:

Stage 3: checking the compatibility of the system of restrictions of the LLP.

At this iteration (in Table 5.3), the sign of inconsistency of the constraint system (feature 1) was not revealed (i.e., there is no line with a negative free number (except for the objective function line) that does not contain at least one negative element (i.e. . negative coefficient with a free variable)).

At this iteration (in Table 5.3), the sign of unboundedness of the objective function (sign 2) was not revealed (i.e. there is no column with a negative element in the line of the objective function (except for the column of free numbers) in which there would be at least one positive element) .

Since the found basic solution does not contain negative components, it is admissible.

Stage 6: optimality check.

The found basic solution is not optimal, since, according to the criterion of optimality (sign 4), there should be no negative elements in the line of the objective function (the free number of this line is not taken into account when considering this sign). Therefore, according to the algorithm of the simplex method, we proceed to the 8th stage.

Since the found basic solution is admissible, we will search for the resolving column according to the following scheme: we determine the columns with negative elements in the line of the objective function (except for the column of free numbers). According to Table 5.3, there are two such columns: the column " x1" and column " x2". From such columns, the one that contains the smallest element in the line of the objective function is selected. She will be resolving. Column " x2' contains the smallest element (-3) compared to the column ' x1

To determine the permissive string, we find the positive estimated ratios of free numbers to the elements of the permissive column, the string, which corresponds to the smallest positive estimated ratio, is taken as allowed.

Table 5.4

Initial simplex table

In table 5.4, the smallest positive evaluation ratio corresponds to the line " x5”, therefore, it will be resolving.

The element located at the intersection of the enabling column and the enabling line is accepted as enabling. In our example, this is the element that is located at the intersection of the line " x5» and columns « x2».

The resolving element shows one basic and one free variables that need to be swapped in the simplex table to go to the new “improved” basic solution. In this case, these are variables. x5 And x2, in the new simplex table (table 5.5) we swap them.

9.1. Allow element transformation.

The permissive element of table 5.4 is transformed as follows:

We enter the result obtained in a similar cell in Table 5.5.

9.2. Allow string conversion.

The elements of the permissive line of table 5.4 are divided by the permissive element of this simplex table, the results fit into similar cells of the new simplex table (table 5.5). Transformations of elements of the enabling string are given in Table 5.5.

9.3. Permissive column transformation.

The elements of the resolving column of table 5.4 are divided by the resolving element of this simplex table, and the result is taken with the opposite sign. The results obtained fit into similar cells of the new simplex table (tables 5.5). Transformations of elements of the resolving column are given in Table 5.5.

9.4. Transformation of the remaining elements of the simplex table.

The transformation of other elements of the simplex table (i.e. elements not located in the resolving row and resolving column) is carried out according to the "rectangle" rule.

For example, consider the transformation of an element located at the intersection of the string " x3” and columns “”, conditionally denote it as “ x3". In table 5.4, we mentally draw a rectangle, one vertex of which is located in the cell, the value of which is being transformed (i.e., in the cell " x3”), and the other (diagonal vertex) is in a cell with a resolving element. The other two vertices (of the second diagonal) are uniquely determined. Then the transformed value of the cell " x3"will be equal to the previous value of this cell minus a fraction, in the denominator of which is the resolving element (from Table 5.4), and in the numerator the product of two other unused vertices, i.e.:

« x3»: .

The values of other cells are converted similarly:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

As a result of these transformations, a new simplex table was obtained (table 5.5).

II iteration:

Stage 1: compiling a simplex table.

Table 5.5

Simplex tableII iterations

				Estimated relationship

Stage 2: determination of the basic solution.

As a result of the simplex transformations, a new basic solution was obtained (table 5.5):

As you can see, with this basic solution, the value of the objective function =15, which is more than with the previous basic solution.

The incompatibility of the system of restrictions in accordance with sign 1 in Table 5.5 was not revealed.

Stage 4: checking the boundedness of the objective function.

The unboundedness of the objective function in accordance with sign 2 in Table 5.5 was not revealed.

Stage 5: checking the admissibility of the found basic solution.

The found basic solution in accordance with feature 4 is not optimal, since the line of the objective function of the simplex table (Table 5.5) contains a negative element: -2 (the free number of this line is not taken into account when considering this feature). So let's move on to step 8.

Stage 8: definition of the enabling element.

8.1. Definition of a resolution column.

The found basic solution is admissible, we determine the columns with negative elements in the line of the objective function (except for the column of free numbers). According to Table 5.5, there is only one such column: " x1". Therefore, we accept it as permitted.

8.2. Permissive string definition.

According to the obtained values of positive estimated ratios in table 5.6, the minimum is the ratio corresponding to the line " x3". Therefore, we accept it as permitted.

Table 5.6

Simplex tableII iterations

				Estimated relationship
				3/1=3 – min

Stage 9: transformation of the simplex table.

The transformations of the simplex table (Table 5.6) are performed in the same way as in the previous iteration. The results of transformations of elements of the simplex table are shown in Table 5.7.

III iteration

Based on the results of the simplex transformations of the previous iteration, we compile a new simplex table:

Table 5.7

Simplex tableIII iterations

				Estimated relationship

Stage 2: determination of the basic solution.

As a result of the simplex transformations, a new basic solution was obtained (table 5.7):

Stage 3: checking the compatibility of the system of restrictions.

Inconsistency of the system of restrictions in accordance with sign 1 in Table 5.7 has not been identified.

Stage 4: checking the boundedness of the objective function.

The unboundedness of the objective function in accordance with sign 2 in Table 5.7 was not revealed.

Stage 5: checking the admissibility of the found basic solution.

The found basic solution in accordance with criterion 3 is admissible, since it does not contain negative components.

Stage 6: checking the optimality of the found basic solution.

The found basic solution in accordance with feature 4 is not optimal, since the line of the objective function of the simplex table (Table 5.7) contains a negative element: -3 (the free number of this line is not taken into account when considering this feature). So let's move on to step 8.

Stage 8: definition of the enabling element.

8.1. Definition of a resolution column.

The found basic solution is admissible, we determine the columns with negative elements in the line of the objective function (except for the column of free numbers). According to Table 5.7, there is only one such column: " x5". Therefore, we accept it as permitted.

8.2. Permissive string definition.

According to the obtained values of positive estimated ratios in table 5.8, the minimum is the ratio corresponding to the line " x4". Therefore, we accept it as permitted.

Table 5.8

Simplex tableIII iterations

				Estimated relationship

				5/5=1 – min

Stage 9: transformation of the simplex table.

The transformations of the simplex table (Table 5.8) are performed in the same way as in the previous iteration. The results of transformations of the elements of the simplex table are shown in Table 5.9.

IV iteration

Stage 1: construction of a new simplex table.

Based on the results of the simplex transformations of the previous iteration, we compile a new simplex table:

Table 5.9

Simplex tableIV iterations

				Estimated relationship
			–(–3/5)=3/5

			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Stage 2: determination of the basic solution.

As a result of the simplex transformations, a new basic solution was obtained, according to Table 5.9, the solution is as follows:

Stage 3: checking the compatibility of the system of restrictions.

Inconsistency of the system of restrictions in accordance with feature 1 in Table 5.9 was not revealed.

Stage 4: checking the boundedness of the objective function.

The unboundedness of the objective function in accordance with sign 2 in Table 5.9 was not revealed.

Stage 5: checking the admissibility of the found basic solution.

The found basic solution in accordance with criterion 3 is admissible, since it does not contain negative components.

Stage 6: checking the optimality of the found basic solution.

The basic solution found in accordance with feature 4 is optimal, since there are no negative elements in the row of the objective function of the simplex table (Table 5.9) (the free number of this row is not taken into account when considering this feature).

Stage 7: checking the alternative solution.

The solution found is the only one, since there are no zero elements in the line of the objective function (Table 5.9) (the free number of this line is not taken into account when considering this feature).

Answer: optimal value objective function of the problem under consideration =24, which is achieved at.

Example 5.2. Solve the above linear programming problem assuming that the objective function is minimized:

Solution:

I iteration:

Stage 1: formation of the initial simplex table.

The original linear programming problem is given in standard form. Let us bring it to the canonical form by introducing an additional non-negative variable into each of the inequality constraints, i.e.

In the resulting system of equations, we take as allowed (basic) variables x3, x4, x5, x6, then the free variables are x1,x2. We express the basic variables in terms of the free ones.

>> >> >> Simplex method

Simplex method

Any solution can be found simplex method. Before applying the simplex method, one should write the original problem in the form of the main linear programming problem, if it does not have such a form of writing.

The simplex method for solving a linear programming problem is based on the transition from one support plan to another, in which the value of the objective function increases(provided that given task has an optimal design and each of its supporting designs is non-degenerate). This transition is possible if some initial reference plan is known. Consider a problem for which this plan can be written down directly.

Let it be required to find the maximum value of the function

under conditions

Here and are given constant numbers

The vector form of this problem has the following form: find the maximum of the function

under conditions

then, by definition of the baseline, is the baseline of the given task (the last components of the vector X are equal to zero). This plan is determined by a system of unit vectors that form the basis m- dimensional space. Therefore, each of the vectors and can also be represented as a linear combination of the vectors of the given basis. Let

Let's put Since the vectors – singular, then and

Theorem 5

(a sign of the optimality of the basic plan). Basic task plan (22) – (24) is optimal if for any j

Theorem 6.

If for some j=k and none of the numbers are positive , then the objective function(22) tasks (22) – (24) is not limited on the set of her plans.

Theorem 7.

If the baseline X of the task (22) – (24)non-degenerateAnd , But among the numbersthere are positive (not all), then there exists a support plan X" such that

The formulated theorems make it possible to check whether the found base plan is optimal and to determine the expediency of switching to a new base plan.

The study of the reference plan for optimality, as well as the further computational process, is more convenient to conduct if the conditions of the problem and the initial data obtained after determining the initial reference plan are written as shown in Table. 3.

In column C 6 of this table, the coefficients for unknown objective functions are recorded, which have the same indices as the vectors of this basis.

The column contains the positive components of the original reference plan, and as a result of the calculations, the positive components of the optimal plan are obtained in it. The columns of vectors represent the expansion coefficients of these vectors in vectors of the given basis.

In table. 3 first m rows are determined by the initial data of the problem, and the indicators of the (m + 1)th row are calculated. In this line, in the vector column, the value of the objective function is written, which it takes with a given reference plan, and in the vector column – meaning

The value of Z j is found as the scalar product of a vector by a vector

The value is equal to the scalar product of the vector P 0 by the vector :

After filling in table 3, the original reference plan is checked for optimality. To do this, look through the elements of the -th row of the table. As a result, one of the following three cases may occur:

1) for j=m+1, (at ). Therefore, in this case, the numbers for all j from 1 to n;

2) for some j, and all quantities corresponding to this index

3) for some indices j, and for each such j at least one of the numbers is positive.

In the first case, based on the sign of optimality, the original basic plan is optimal. In the second case, the objective function is not bounded from above on the set of plans, and in the third case, it is possible to switch from the original plan to a new reference plan, in which the value of the objective function will increase. This transition from one reference plan to another is carried out by excluding one of the vectors from the original basis and introducing a new vector into it. As a vector introduced into the basis, you can take any of the vectors with the index j, for which . Let, for example, and it is decided to introduce the vector into the basis

To determine the vector to be excluded from the basis, find for all Let this minimum be reached at i=r. Then the vector is excluded from the basis, and the number is called permission element.

The column and row at the intersection of which there is an enabling element is called guides.

After highlighting the guide row and guide column, a new base plan and coefficients of vector expansion through the vectors of the new basis corresponding to the new base plan are found. This is easy to implement using the Jordan–Gauss method. In this case, it can be shown that the positive components of the new base plan are calculated by the formulas

(25)

and the expansion coefficients of the vectors in terms of the vectors of the new basis corresponding to the new base plan, according to the formulas

(26)

After calculation and according to formulas (25) and (26), their values are entered in Table. 4. The elements of the th row of this table can be calculated either by the formulas

(27)

(28)

or based on their definition.

Table 3

Basis

C b

c 1

c 2

...

c m

c m+1

...

c k

...

c n

...

P r

...

Pm+1

...

P k

...

P n

c 1

b 1

...

a 1m+1

...

a 1k

...

a 1n

c 2

b 2

...

a 2m+1

...

a 2k

...

a 2n

P r

...

rm+2

...

a rk

...

a rn

c m

b m

...

amm+1

...

a mk

...

amn

m+1

F m

...

∆m+1

...

∆k

...

Δn

Table 4

baz
is

C b

c 1

c 2

...

c m

c m+1

...

c k

...

c n

...

P r

...

Pm+1

...

P k

...

P n

c 1

b 1

...

a "1r

...

a "1m+1

...

a "1n

c 2

b 2

...

a "2r

...

a "2m+1

...

a "2n

P r

...

a "rr

...

a "rm+2

...

a "rn

c m

b m

...

a "mr

...

a"mm+1

...

a "mn

m+1

F m

...

z" r-c r

...

z "m+1 -c m+1

...

z "n-cn

The presence of two ways of finding the elements of the -th row allows you to control the correctness of the calculations.

It follows from formula (27) that when passing from one reference plan to another, it is most expedient to introduce the vector into the basis, which has the index j, at which the maximum absolute value is the number . However, in order to simplify the computational process, in the future we will determine the vector introduced into the basis based on the maximum absolute value of negative numbers . If there are several such numbers, then we will introduce a vector into the basis that has the same index as the maximum of the numbers determined by these numbers

So, the transition from one basic plan to another is reduced to the transition from one simplex tableau to another. The elements of the new simplex table can be calculated both with the help of recursive formulas (25)–(28) and according to the rules that follow directly from them. These rules are as follows.

In the columns of the vectors included in the basis, at the intersection of the rows and columns of the vectors of the same name, units are put down, and all other data elements of the columns are assumed to be equal to zero.

The elements of the vectors and in the row of the new simplex table, in which the vector entered into the basis is written, are obtained from the elements of the same row of the original table by dividing them by the value of the resolving element. In the column in the row of the input vector put down the value , where k – the index of the input vector.

The remaining elements of the columns of the vector and the new simplex table are calculated according to the triangle rule. To calculate any of these elements, three numbers are found:

1) the number standing in the original simplex table in place of the desired element of the new simplex table;

2) the number in the original simplex table at the intersection of the row containing the required element of the new simplex table and the column corresponding to the vector introduced into the basis;

3) the number in the new simplex table at the intersection of the column containing the desired element and the row of the newly introduced vector into the basis (as noted above, this row is obtained from the row of the original simplex table by dividing its elements by the resolving element).

These three numbers form a kind of triangle, two vertices of which correspond to the numbers in the original simplex table, and the third to the number in the new simplex table. To determine the desired element of the new simplex table, the product of the second and third is subtracted from the first number.

After filling in the new simplex table, the elements of the i-th row are looked up. If all , then the new baseline is optimal. If among the indicated numbers there are negative ones, then, using the sequence of actions described above, a new reference plan is found. This process is continued until either the optimal plan of the problem is obtained or its unsolvability is established.

When finding a solution to a linear programming problem, we assumed that this problem has supporting plans and that each such plan is non-degenerate. If the problem has degenerate base plans, then at one of the iterations one or more variables of the base plan may turn out to be equal to zero. Thus, when moving from one reference plan to another, the value of the function may remain the same. Moreover, it is possible that the function retains its value for several iterations, and it is also possible to return to the original basis. In the latter case, they usually say what happened looping. However, when solving practical problems, this case is very rare, so we will not dwell on it.

So, finding the optimal plan by the simplex method includes the following steps:

1. Find a reference plan.

2. Make up a simplex table.

3. Find out if there is at least one negative number. If not, then the found base plan is optimal. If among the numbers there are negative ones, then either the problem is unsolvable, or they switch to a new basic plan.

4. Find the column and row guides. The steering column is determined by the largest negative number in absolute value , and the steering row is determined by the minimum ratio of the vector column components to the positive components of the steering column.

5. According to formulas (25) - (28), the positive components of the new reference plan, the expansion coefficients of the vectors pj over the vectors of the new basis and the number , . All these numbers are written in a new simplex table.

6. Check the found base plan for optimality. If the plan is not optimal and it is necessary to switch to a new base plan, then they return to stage 4, and if an optimal plan is obtained or unsolvability is established, the process of solving the problem is completed.

Example 9

For the manufacture of various products A,IN and C the enterprise uses three different types of raw materials. Consumption rates of raw materials for the production of one product of each type, the price of one product A,IN And WITH, as well as the total amount of raw materials of each type that can be used by the enterprise, are given in table. 5.

Table 5

Type of raw material	Raw material cost rates (kg) per product	Total amount of raw materials (kg)
Type of raw material		Total amount of raw materials (kg)

The price of one product (rub.)

Products A,IN And WITH can be produced in any ratio (sales are secured), but production is limited by the raw materials of each type allocated to the enterprise.

Draw up a plan for the production of products in which the total cost of all products manufactured by the enterprise is maximum.

Solution. Let's make a mathematical model of the problem. Desired product release A denoted by x 1, products IN - through , products WITH - through . Since there are restrictions on the fund of raw materials of each type allocated to the enterprise, the variables must satisfy the following system of inequalities:

(29)

The total value of the products manufactured by the enterprise, subject to the release of x 1 products A, products IN and products WITH is

According to their economic content, the variables can take only non-negative values:

Thus, we come to the following mathematical problem: among all non-negative solutions of the system of inequalities (29), it is required to find one for which function (30) takes the maximum value.

Let us write this problem in the form of a basic linear programming problem. To do this, we pass from inequality constraints to equality constraints. We introduce three additional variables, as a result of which the constraints are written in the form of a system of equations

These additional variables, in economic sense, mean the amount of raw materials of one kind or another that is not used in a given production plan. For example, – this is the unused amount of raw materials of type I.

We write the transformed system of equations in vector form:

Since among the vectors Since there are three unit vectors, a reference plan can be written directly for this problem. That is the plan X=(0; 0; 0; 360; 192; 180), defined by a system of three-dimensional unit vectors that form the basis of a three-dimensional vector space.

We compile a simplex table for the first iteration (Table 6), calculate the values and check the original reference plan for optimality:

For basis vectors

Table 6



	R 5

As can be seen from Table 6, the values of all main variables are equal to zero, and additional variables take their values in accordance with the constraints of the problem. These values of the variables correspond to such a “plan” in which nothing is produced, raw materials are not used, and the value of the objective function is zero (i.e., there is no cost of production). This plan is certainly not optimal.

This can be seen from the 4th row of Table. 6, since it contains three negative numbers: and Negative numbers not only indicate the possibility of increasing the total cost of manufactured products, but also show how much this amount will increase when a unit of one or another type of product is introduced into the plan.

So, the number - 9 means that when one product is included in the production plan A an increase in output by 9 rubles is ensured. If included in the production plan for one product IN and C, then the total cost of manufactured products will increase by 10 and 16 rubles, respectively. Therefore, from an economic point of view, it is most expedient to include in the plan for the production of products WITH. The same must be done on the basis of the formal sign of the simplex method, since the maximum negative number in absolute value is in the 4th row of the vector column R 3 . Therefore, we introduce the vector into the basis R 3 . determine the vector to be excluded from the basis. For this we find

Having found the number, we thereby determined from an economic point of view how many products WITH the enterprise can produce taking into account the consumption rates and the available volumes of raw materials of each type. Since there are 360, 192 and 180 kg of raw materials of this type, respectively, and for one product WITH it is required to spend raw materials of each type, respectively, 12, 8 and 3 kg, then maximum number products WITH, which can be produced by the enterprise, is equal to i.e. the limiting factor for the production of products WITH is the available volume of raw materials of type II. Taking into account its availability, the enterprise can produce 24 products WITH. In this case, raw materials of the II type will be fully used.

Therefore, the vector R 5 is to be excluded from the basis. Vector column R 3 to 2nd line are guides. We compile a table for the second iteration (Table 7).

Table 7

P 4

p 3

First, we fill in the line of the vector newly introduced into the basis, i.e., the line whose number matches the number of the guide line. Here the guide is the 2nd line. The elements of this row in Table. 7 are obtained from the corresponding elements of table 6 by dividing them by the resolving element (i.e. by 8). However, in the column C b write down the coefficient in the column of the vector introduced into the basis. Then we fill in the elements of the columns for the vectors included in the new basis. In these columns, at the intersection of the rows and columns of the vectors of the same name, we put down units, and all other elements are set equal to zero.

To determine the remaining elements of the table. 7 apply the triangle rule. These elements can also be calculated directly using recursive formulas.

Let's calculate the elements of the table. 7 standing in a vector column R 0 . The first one is in the 1st row of this column. To calculate it, we find three numbers:

1) the number in the table. 6 at the intersection of the vector column R 0 and 1st lines (360);

2) the number in the table. 6 at the intersection of the vector column P 3rd and 1st lines (12);

3) the number in the table. 7 at the intersection of the vector column R 0 and 2nd row (24).

Subtracting the product of the other two from the first number, we find the desired element: 360 - 12 x 24 = 72; write it in the 1st row of the vector column R 0 tab. 7.

The second column element of the vector R 0 tab. 7 has already been calculated previously. To compute the third column element of a vector R 0 also find three numbers. The first of them (180) is located at the intersection of the 3rd row and column of the vector R 0 tab. 6, second (3) - at the intersection of the 3rd row and column of the vector P 3 tab. 6, third (24) - at the intersection of the 2nd row and column of the vector R 0 tab. 8. So, the indicated element is 180 - 24 x 3 = 108. The number 108 is written in the 3rd row of the vector column R 0 tab. 7.

Meaning F 0 in the 4th row of a column of the same vector can be found in two ways:

1) according to the formula, i.e.

2) according to the triangle rule; in this case, the triangle is formed by the numbers 0, -16, 24. This method leads to the same result: 0 - (-16) x 24 \u003d 384.

When determining according to the triangle rule the elements of the vector column R 0, the third number at the lower vertex of the triangle, remained unchanged all the time and only the first two numbers changed. Let's take this into account when finding the elements of the vector column P 1 tab. 7. To calculate the indicated elements, the first two numbers are taken from the columns of vectors P 1 and R 3 tab. 6, and the third number - from the table. 7. This number is at the intersection of the 2nd row and column of the vector P 1 of the last table. As a result, we obtain the values of the required elements: 18 - 12 x (3/4) = 9; 5 - 3 x (3/4) = 11/4.

Number in 4th column row of vector P 1 tab. 7 can be found in two ways:

1) according to the formula Z 1 -С 1 \u003d (C, P 1) -C 1 we have

2) according to the triangle rule, we get

Similarly, we find the elements of the vector column P 2 .

Vector column elements R 5 is calculated according to the triangle rule. However, the triangles constructed to define these elements look different.

When calculating the element of the 1st row of the specified column, a triangle is obtained, formed by the numbers 0.12 and 1/8. Therefore, the desired element is 0 - 12x (1/8) = -3/2. The element in the 3rd row of this column is 0 - 3 x (1/8) = -3/8.

At the end of the calculation of all elements of Table. 7, a new reference plan and the coefficients of the expansion of vectors through the basis vectors P 4 , P 3 , P 6 and the values and . As can be seen from this table, the new baseline task plan is the plan X=(0; 0; 24; 72; 0; 108). With this production plan, 24 products are manufactured WITH and remains unused 72 kg of raw materials of the 1st type and 108 kg of raw materials of the III type. The cost of all products produced under this plan is 384 rubles. Specified numbers are written in the vector column R 0 tab. 7. As you can see, the data in this column still represent the parameters of the problem under consideration, although they have undergone significant changes. The data in other columns has also changed, and their economic content has become more complex. So, for example, take the column data of the vector R 2 . The number 1/2 in the 2nd row of this column shows how much to reduce the production of products WITH, if you plan to release one product IN. Numbers 9 and 3/2 in the 1st and 3rd rows of the vector P 2 show, respectively, how much raw materials of I and II types will be required when one product is included in the production plan IN, and the number - 2 in the 4th line shows that if the release of one product is planned IN, then this will ensure an increase in output in value terms by 2 rubles. In other words, if one product is included in the production plan IN, then this will require a decrease in the output of the product WITH for 1/2 unit and will require additional costs of 9 kg of raw materials of type I and 3/2 kg of raw materials of type III, and the total cost of manufactured products in accordance with the new optimal plan will increase by 2 rubles. Thus, the numbers 9 and 3/2 act, as it were, as new “norms” for the costs of raw materials of types I and III for the manufacture of one product. IN(as can be seen from Table 6, earlier they were equal to 15 and 3), which is explained by a decrease in the output of products WITH.

The data of the vector column have the same economic meaning. R 1 tab. 7. The numbers written in the vector column have a slightly different economic content. R 5 . The number 1/8 in the 2nd line of this column shows that an increase in the volume of raw materials of type II by 1 kg would increase the output of products WITH for 1/8 unit. At the same time, an additional 3/2 kg of type I raw materials and 3/8 kg of type III raw materials would be required. Increase in product output WITH for 1/8 unit. will lead to an increase in output by 2 rubles.

From the above economic content of the data in Table. 7 it follows that the task plan found at the second iteration is not optimal. This can be seen from the 4th row of Table. 7, because in the vector column P 2 of this line is a negative number - 2. This means that the vector should be entered into the basis P 2, i.e., the new plan should provide for the release of products IN. When determining the possible number of products to be manufactured IN the available amount of raw materials of each type should be taken into account, namely: the possible release of products IN is determined for , i.e., we find

Therefore, the vector is subject to exclusion from the basis R 4 in other words, product release IN limited by the type I raw materials available to the enterprise. Taking into account the available volumes of this raw material, the enterprise should produce 8 products IN. The number 9 is the resolving element, and the vector column P 2 and 1st line of the table. 7 are guides. We compile a table for iteration III (Table 8).

Table 8

P 2

P 3

In table. 8 first fill in the elements of the 1st row, which is a row of the vector newly introduced into the basis R 2 . The elements of this row are obtained from the elements of the 1st row of Table. 7 by dividing the latter by the resolving element (i.e. by 9). However, in the column C b this line we write .

Then we fill in the elements of the columns of the basis vectors and, according to the triangle rule, calculate the elements of the remaining columns. As a result, in table. 8 get a new baseline X=(0; 8; 20; 0; 0; 96) and coefficients of expansion of vectors in terms of basis vectors and corresponding values and

We check whether the given basic plan is optimal or not. To do this, consider the 4th line, Table. 8. There are no negative numbers in this line. This means that the found base plan is optimal and

Therefore, the production plan, including the manufacture of 8 products IN and 20 items WITH, is optimal. With this plan for the production of products, raw materials of types I and II are completely used and 96 kg of raw materials of type III remain unused, and the cost of manufactured products is 400 rubles.

The optimal production plan does not provide for the manufacture of products A. Introduction to the production plan for products of the type A would result in a reduction in the said total cost. This can be seen from the 4th row of the vector column P 1 , where the number 5 shows that, under this plan, the inclusion in it of the release of a unit of product A leads only to a decrease in the total value of the cost by 5 rubles.

The solution of this example by the simplex method could be carried out using only one table (Table 9). In this table, all three iterations of the computational process are sequentially recorded one after the other.

Table 9



	R 5 P 4 p 3 P 2 p 3

As can be seen from Table. 10, the original reference plan is not optimal. Therefore, we move on to a new basic plan. This can be done, since in the columns of vectors P 1 and p 5 , the 4th line of which contains negative numbers, there are positive elements. To switch to a new reference plan, we introduce the vector into the basis p 5 and exclude the vector from the basis p 4 . Compiling a table of iteration II.

Table 11

As can be seen from Table. 11, the new basic task plan is not optimal, because in the 4th row of the vector column P 1 is worth a negative number -11/3. Since there are no positive elements in the column of this vector, this problem does not have an optimal plan.

Here is a manual (not applet) solution of two problems using the simplex method (similar to 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 " ≤ " (a problem with an initial basis), the second one can contain signs " ≥ ", " ≤ " or " = " (a problem with an artificial basis), they are solved in different ways.

Simplex method, solution of a problem with an initial basis

1)Simplex method for a problem with an initial basis (all signs of constraint inequalities are " ≤ ").

Let's write the problem in canonical form, i.e. we rewrite the inequality constraints as 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 for which the simplex method is used 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. Compile the first simplex table (Iteration 0) for solving 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" - the column of the right parts of the equations of the system. The solution is not optimal, because there are negative coefficients in the z-line.

simplex method iteration 0

							Attitude

To improve the solution, let's move on to the next iteration simplex method, we obtain the following simplex tableau. For this you need to choose enable column, i.e. a variable that will enter the basis at the next iteration of the simplex method. It is chosen by the largest negative coefficient in the z-row (in the maximum problem) - in the initial iteration of the simplex method, this is the column x 2 (coefficient -6).

Then choose permission 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 resolving column ("Ratio" column) - in the initial iteration, this is row s 3 (coefficient 20).

Permissive element is located at the intersection of the enabling column and the enabling 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 relation is not searched in the z-string, a dash "-" is put there. If there are identical minimum ratios, then any of them is chosen. 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 in the following table "Iteration 1". We will get it from the "Iteration 0" table. The purpose of further transformations is to turn the x2 enable column into a single column (with one instead of the enable element and zeros instead of the rest of the elements).

1) Calculating 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 this case) of this table, we get the row x 2 in the "Iteration 1" table. Because the resolving element in this case is equal to 1, then the row s 3 of the "Iteration 0" table will match the 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 column x2 of the "Iteration 0" table, there should be a 0 in the first row of the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by 6, we get 0 6 0 0 6 120 and add this row with the first row (z - row) of the "Iteration 0" table -4 -6 0 0 0 0, we get -4 0 0 0 6 120. Zero 0 appeared in the x 2 column, the goal was achieved. The elements of the permission 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 should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -1, we get 0 -1 0 0 -1 -20 and add this row with s 1 - the row of the "Iteration 0" table 2 1 1 0 0 64, we get the row 2 0 1 0 -1 44. The required 0 is obtained in the x 2 column.

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

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

New Row = Old Row - (Old Row Permission Factor)*(New Row).

For example, for the z-line we have:

Old z-string (-4 -6 0 0 0 0) -(-6)*New enable 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

							Attitude

Permissive column x 1 , permissive 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 a table with all positive coefficients in the z-row is obtained. This is a sign of an optimal table.

simplex method iteration 2

							Attitude

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

simplex method iteration 3

							Attitude

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

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

The main content of the simplex method is as follows:

Specify a method for finding the optimal reference solution
Specify the method of transition from one reference solution to another, on which the value of the objective function will be closer to the optimal, i.e. indicate a way to improve the reference solution
Set the criteria that allow you to timely stop the enumeration of support solutions on the optimal solution or follow the conclusion that there is no optimal solution.

Algorithm of the simplex method for solving linear programming problems

In order to solve the problem by the simplex method, you must do the following:

Bring the problem to canonical form
Find an initial reference solution with a "unit basis" (if there is no reference solution, then the problem does not have a solution due to the incompatibility of the system of constraints)
Calculate estimates of vector expansions in terms of the basis of the reference solution and fill in the table of the simplex method
If the criterion for the uniqueness of the optimal solution is satisfied, then the solution of the problem ends
If the condition for the existence of a set of optimal solutions is satisfied, then by simple enumeration, all optimal solutions are found

An example of solving the problem by the simplex method

Example 26.1

Solve the problem using the simplex method:

Solution:

We bring the problem to the canonical form.

To do this, we introduce an additional variable x 6 with the coefficient +1 into the left side of the first inequality constraint. 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 reference solution. To do this, we equate the 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).

Calculate vector decomposition estimates conditions on the basis of the reference solution according to the formula:

Δ k \u003d C b X k - c k

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

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

Above 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 of writing these vectors corresponds to the numbers of allowed unknowns in the constraint equations. In the second column of the table "With b" the coefficients of the objective function are written with basic variables in the same order. At correct location coefficients of the objective function in the column "C b" estimates of the unit vectors included in the basis, always equal to zero.

In the last row of the table with estimates of Δ k in the column "A 0 "the values of the objective function are written on the reference solution Z(X 1).

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

According to the reference solution improvement theorem, if at least one vector in the maximum problem has a negative estimate, then it is possible to find a new reference 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 of the objective function.

The objective function increment is found by the formula: .

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

We get θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (table 26.1).

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

Therefore, for a faster approach to optimal solution it is necessary to introduce the 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 reached in the first row (l = 1).

We perform the Jordan transform 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 the vector A2 has a negative estimate Δ2 = - 6. To improve the solution, it is necessary to introduce the 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. Therefore, 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 that are not included in the basis, the estimates are positive

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 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 in the face of severe restrictions related to the resources used in production (fixed assets, materials, labor resources). The application of this method in economic analysis allows us to solve problems related mainly to the planning of the organization's activities. This method helps to determine the optimal values of output, as well as the directions for the most efficient use of the production resources available to the organization.

Using this method, the solution of the so-called extremal problems is carried out, which consists in finding the extreme values, that is, the maximum and minimum of functions of variables.

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

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

In addition, this method is widely used in solving the problem of scheduling. This task consists in such a distribution of the time of functioning of the personnel of this organization, which would be the most acceptable both for the members of this personnel and for the clients of the organization.

The objective is to maximize the number of clients served while limiting the number of available staff members and working hours.

Thus, the linear programming method is very common in the analysis of the placement and use of various kinds 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, methods of nonlinear, dynamic and convex programming can be used.

Nonlinear programming relies on the non-linear nature of the objective function or constraints, or both. The forms of the objective function and constraint inequalities under these conditions can be different.

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

Dynamic programming is based on building a decision tree. Each tier of this tree serves as a stage for determining the consequences previous decision and to eliminate inefficient options for this solution. Thus, dynamic programming has a multi-step, multi-stage character. This type of programming is used in economic analysis to find best options organization, both now and in the future.

Convex programming is a type of non-linear programming. This type of programming expresses the non-linear nature of the relationship between the results of the organization's activities and the costs incurred by it. Convex (otherwise concave) programming analyzes convex objective functions and convex constraint systems (feature points). Convex programming is used in the analysis of economic activity in order to minimize costs, and concave programming is used in order to maximize income in the conditions of existing restrictions on the action of factors that affect the analyzed indicators in the opposite way. Consequently, under the types of programming under consideration, convex objective functions are minimized, and concave ones are maximized.

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

Content

The task

For the implementation of 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. turnover, a resource of the first type is consumed in the amount of a 11 = 2 units, a resource of the second type in the amount of a 21 = 4 units, a 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 spent, respectively, 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 \u003d 4, c 2 \u003d 5, c 3 \u003d 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 commodity circulation planning, solvable 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, obtain dual problem solution, in which resource estimation spent on the sale of goods.

Solution of the simplex problem by the method

Let x 1, x 2, x 3 - the number of goods sold, in thousand rubles, 1, 2, 3 groups, respectively. Then mathematical model task looks like:

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 by the method.

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

As a basis, we take x 4 \u003d 240; x5 = 200; x6 = 160.

Data is entered into simplex table

Simplex table number 1

Target function:

0 240 + 0 200 + 0 160 = 0

We calculate the scores according to the formula:

Δ 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
Δ 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
Δ 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
Δ 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
Δ 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0

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

We introduce the variable x 2 into the basis.

We define a variable leaving the basis. To do this, we find the smallest non-negative ratio for the column x 2 .

= 26.667

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

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

We calculate:

We get a new table:

Simplex table number 2

Target function:

0 160 + 0 440/3 + 5 80/3 = 400/3

We calculate the scores according to the formula:

Δ 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
Δ 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 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 leaving the basis. To do this, we find the smallest non-negative ratio for column x 1 .

The smallest non-negative: Q 3 \u003d 40. We derive the variable x 2 from the basis

Divide the 3rd row by 2/3.
From the 2nd row subtract the 3rd row multiplied by 8/3

We calculate:

We get a new table:

Simplex table number 3

Target function:

0 160 + 0 40 + 4 40 = 160

We calculate the scores according to the formula:

Δ 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
Δ 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
Δ 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
Δ 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1

Since there are no negative estimates, the plan is optimal.

The solution of the problem:

x 1 = 40; x2 = 0; x 3 \u003d 0; x 4 = 160; x5 = 40; x6 = 0; F max = 160

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

Solving the dual problem

The dual problem looks like:

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 convert 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 of the dual problem:

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

Y1=0; y2 = 0; y 3 = 1; Z min = 160;

Definition of basic variables in the simplex method. Solve the problem of linear programming by the simplex method. Reduction of a linear programming problem to canonical form

Simplex method

Simplex method, solution of a problem with an initial basis

Algorithm of the simplex method for solving linear programming problems

An example of solving the problem by the simplex method

Linear programming method in economic analysis

The task