Tabular view of the PPP. Simplex - tables.

SIMPLEX METHOD FOR SOLVING ZLP

3.1. general characteristics and the main stages of the simplex method

The founders of the simplex method are the Soviet mathematician L.V. Kantorovich and American mathematician J. Dantzig.

Using the simplex method, you can solve any problem or discover its unsolvability. Many special classes of problems can be solved by other methods that are more effective for these classes. However, the advantage of the simplex method is its versatility. Almost all computers have been developed standard programs for solutions ZLP simplex- method.

Let's describe general idea simplex method.

We believe that the ZLP is written in canonical form and the objective function needs to be minimized. As we already know, optimal plan should be searched among the supporting plans of the ZLP. The simplex method does not go through all the reference plans (which would often be impossible due to their huge number), but, starting from some initial reference plan, he sequentially moves to other reference plans with a decrease objective function. The simplex method stops working when either the optimal reference plan is found or the unsolvability of the problem is established.

When solving a problem using the simplex method, the following stages can be distinguished:

1) bringing the PAP to canonical form;

2) bringing the system linear equations to a Jordan form with non-negative right-hand sides with a simultaneous check for the undecidability of the ZLP due to the inconsistency of the system of linear constraints;

3) study of the reference plan for optimality;

4) study of the ZLP for undecidability due to the unboundedness from below on the ODD of the objective function;

5) transition to a new, “better” reference plan.

To reduce and organize records when solving a problem using the simplex method, so-called simplex tables are used. To use a simplex table, the ZLP must be reduced to tabular form. It's done like this.

Let the ZLP be written in canonical form (2.3-2.5). For bringing the PAP In tabular form, system (2.4) must first be reduced to Jordan form with nonnegative right-hand sides. Let us assume that this Jordan form has the form (2.6). Let us express from (2.6) the basic variables in terms of free ones:

By substituting into the objective function (2.3) instead of the basic variables their expressions through free variables according to formulas (3.1), we thereby exclude the basic variables from the objective function. The objective function will take the form:

In tabular form, the objective function is written as follows:

Where .

Let us note the following features of the tabular form of the PPP:

a) the system of linear equations is reduced to Jordan form with non-negative right-hand sides;

b) the basis variables are excluded from the objective function and it is written in the form (3.3).

Let us now move on to the description of the simplex table. Let the ZLP be written in tabular form:

(3.4)

Then the completed simplex table looks like this.

Table 3.1.

Basis	Variables	Free members
			...	x k			...
			...				...
			...				...
. . .	. .	. .	...	. .	. .	. .	...	. .	. . .
			...				...
f			...				....

PPL basic plan: ..., is called the reference plan corresponding to this simplex table. As can be seen from formula (3.2), the value of the objective function for this reference plan is equal to γ ​​0.

Let's look at an example. Reduce the following ZLP to tabular form and fill out the simplex table:

First, the ZLP should be brought to canonical form. To do this, the function f need to be replaced with - f:

The system of equations must be written in Jordan form with non-negative right-hand sides. General reception the means by which this is achieved will be discussed later (Section 3.7). In our example, such a Jordan form already exists with the basis variables and . Let's exclude the basic variables from the objective function - f. To do this, we express them in terms of free expressions and substitute these expressions into the objective function.

The tabular view of the ZLP is as follows:

Let's fill out the simplex table (to shorten the entries, the first column is headed “B”, the last column is “Q”).

Table 3.2.

B					Q
			-5
	-7		-2
-f	-4				-20

The reference plan corresponding to this simplex table has the form:

The value of the function - f with this reference plan is - 20.

Let there be a completed simplex table. Let us formulate the optimality condition for the reference plan.

If the bottom row of a simplex table contains all the numbers except, perhaps, the rightmost one, non-positive, then the reference plan corresponding to this table is optimal.

For simplicity, we will justify the validity of this statement with an example. Let the completed simplex table look like:

Table 3.3.

B						Q
				-1
					-1
f			-5	-3	-1

The value of the objective function for the reference plan corresponding to the simplex table is equal to 6. Let us write the objective function in tabular form: , where . Since for any admissible solution ZLP variables accept only non-negative values, then from last entry the objective function can be seen that its value at any point of the ODD is not less than 6. Therefore, minimum value the objective function on the ODR is equal to 6 and it is achieved with a reference plan corresponding to the simplex table, .

3.4. The condition for the undecidability of the LLP due to the unboundedness from below on the ODD of the objective function.

If the simplex table is filled for the ZLP, then the ODD of the problem is non-empty, so the reference plan corresponding to the simplex table belongs to the ODD. However, the ZLP may be unsolvable due to the unboundedness from below on the ODD of the objective function.

The undecidability condition is formulated as follows.

If a simplex table contains at least one column other than the rightmost one, which has positive number, and all other rows of the column contain non-positive numbers, then the LLP is unsolvable due to the unboundedness from below on the ODD of the objective function.

To justify this, we will again use an example.

Table 3.4.

B						Q
					-2
			-3		-1
f				-1

The column in the bottom row contains a positive number, and the remaining rows contain non-positive numbers. Let us prove the undecidability of the ZLP.

Let us write out the Jordan form corresponding to the simplex table and transfer the terms containing , to right side. We get

Let a be an arbitrary positive number. Obviously, the ZLP has the following feasible solution:. Let us calculate the value of the objective function for this feasible solution. From Table 3.4 we have:

. With the specified feasible solution f = 4 - 2a. From this we see that the value of the objective function can become as small as desired for sufficiently great importance A. In other words, the objective function is not bounded from below on the ODD. Therefore, the ZLP is undecidable.

3.5. Transition to a new reference plan.

Let us assume that the optimality and undecidability conditions are not satisfied. Then the simplex method moves to a new reference plan. This transition is accomplished by removing one of the basic variables from the basis and introducing one of the free variables into the basis. In this case, the following two conditions must be met:

1) the new basis must still be admissible, i.e. the right-hand sides of the corresponding Jordan form must still be non-negative;

2) with a new reference plan, the value of the objective function should not exceed its value with the previous reference plan.

The column of the simplex table containing the variable entered into the basis is called general column. The line containing the variable derived from the basis is called general line. The element at the intersection of the general row and the general column is called general element.

Rule for choosing a general element.

Any column of the simplex table other than the rightmost one, which has a positive number in the bottom row, is selected as the general column. Then only those rows of the simplex table are considered, other than the lowest one, which have positive numbers at the intersection with the general column. For each of these rows, the ratio of the free term to the element in the general column is calculated. The row for which this ratio is minimal is selected as the general one. The element at the intersection of the general row and the general column will be the general element.

Let's illustrate this rule with an example.

Table 3.5.

B						Q
				2	-1
				-2
F

You can select either column or column as the general column. Let's choose (most often the column with the largest positive number at the bottom is chosen). Now let's start choosing the general line. To do this, consider two lines - and . We make ratios 4:2 and 8:3. The ratio 4:2 has a smaller value, so we select the first line as the general one. Therefore, the general element is 2 - it stands at the intersection of column and row.

After selecting the general element, you need to move to a new reference plan, in which the variable becomes basic, and the variable x 1 becomes free. The coefficient for in the new Jordan form must be equal to 1. Therefore, the first row of table 3.5 is divided by 2. Then multiplying the resulting first row by (-3) and adding to the second row , exclude from the second equation. Similarly, using the Jordan procedure, we exclude it from the third equation and from the objective function (the latter requires a tabular form of the ZLP).

As a result, we get the following table.

Table 3.6

B						Q
f						-2

Please note that in column Q the first three rows contain non-negative numbers, i.e. the new basis is still valid. This is not an accidental fact: this will always be the case if the rule for choosing a general line is strictly followed. Further, the value of the objective function with the new reference plan is equal to -2, with the old one it was equal to 12. “Improvement” of the reference plan guarantees the rule for choosing the general column. Although we do not strictly prove these facts, it should be borne in mind that they always occur.

Looking at table H.6, we see that neither the optimality condition of the reference plan nor the unsolvability condition of the ZLP are met. This means that we need to select the general element again and move on to a new simplex table. The reader can do this on his own.

3.6. Tabular simplex algorithm.

Let there be a completed simplex table. Summarizing the above, we obtain the following algorithm for solving the ZLP using the simplex method.

1. If in the bottom row of the simplex table all the numbers, except perhaps the rightmost one, are non-positive, then the reference plan corresponding to the simplex table is optimal, and the algorithm stops. Otherwise, go to point 2.

2. If the simplex table contains a column other than the rightmost one, which has a positive number in the bottom row and non-positive numbers in all other rows, then the LLP is unsolvable due to the unboundedness from below on the ODD of the objective function, and the algorithm stops. Otherwise, go to point 3.

3. Select any column other than the rightmost one, which has a positive number in the bottom line - let's call it general. Then we consider the rows of the simplex table, other than the bottom one, which have positive numbers in the general column. For each of these rows, we calculate the ratio of the free term to the element in the general column. The row for which this relation is minimal is the general row. The element at the intersection of the general column and the general row will be the general element. Go to point 4.

4. We create a new simplex table in which:

1) the variable in the general line is derived from the basis; a variable in the general column is entered into the basis;

2) the general line is divided into a general element;

3) using the Jordan procedure, all numbers of the general column, with the exception of 1, which is in the general row, are made equal to zero. Go to point 1.

Example I Solve using the simplex method

The problem is written in canonical form, you need to bring it to tabular form. The system of equations is written in Jordan form with non-negative right-hand sides (basic variables and ). It is necessary to reduce the objective function to tabular form. To do this, we express the basic variables in terms of free ones

x 3 =10 - 2x 1 - x 2

x 4 = 8 - x 1 - 2x 2

and substitute it into the objective function

To obtain a tabular form, we write the function as follows:

Now we have a tabular view of the ZLP:

Let's fill in the first simplex table

Table 3.7

B					Q
F

In Table 3.7, the optimality and undecidability conditions are not met. Let us choose as the general column , which has a positive number in the bottom line. Then, comparing the ratios 10:3 and 8:1, we select the first line as the general one. In the table the general element is 2.

Acting in accordance with point 4 of the tabular simplex algorithm, let’s move on to table 3.8.

Table 3.8

B					Q
F			-5		-22

The optimality and undecidability conditions are not satisfied. Select the general element in table 3.8 and move on to the next table

Table 3.9

B					Q
F					-24

Table 3.9 satisfies the optimality condition.

Answer: optimal plan

The minimum value of the objective function f min = - 24.

Example 2. Solve using the simplex method:

First of all, the ZLP needs to be brought to the canonical form

Now we bring the ZLP to a tabular form. We see that the system of equations is written in Jordan form with non-negative right-hand sides (and z-basic variables). However, the objective function includes a basis variable. We have:

Therefore, the tabular view of the ZLP is as follows:

Fill out the simplex table (Table 3.10).

Table 3.10

B				z	Q
	-1
z		-2
g					-1

After selecting the general element, go to table 3.11

Simplex method for solving problems linear programming

The simplex method is analytical method ZLP solutions implementing the algorithm graphic method analytically, without drawing a drawing.

So the point is simplex method consists of directed search admissible solutions, in which the value of the objective function at each step is better than at the previous one. The process is repeated until a solution that is optimal in terms of the value of the objective function is obtained.

The simplex method can be used to solve PLPs with any number of unknowns.

Technical implementation The simplex method is associated with solving systems of linear equations, for which the Gauss method is used; tabular forms and rules for converting simplex tables have been developed.

Simplex method with natural basis applies if the ZLP is given in canonical notation form, and the matrix in the QLP contains a unit submatrix of size m´m. For definiteness, let us assume that the first m The vector matrices of the system of equations form the identity matrix. Then the initial plan is chosen as follows:

The optimality of the reference plan is checked using the optimality sign; the transition to another plan is carried out using the Jordan-Gauss transformation using the mathematical optimality sign. The resulting reference plan is again checked for optimality, etc.

The mathematical criterion for optimality consists of the following two theorems:

1. If for all vectors A 1 , A 2 , … , A n the condition is satisfied where , then the resulting reference plan is optimal. In total to determine Z j participate m terms, that is, not all coefficients of the objective function participate in it c j, but only with numbers corresponding to the numbers of the current basis vectors A i, the number of which is equal m .

2. If for some vector not included in the basis the condition is satisfied , then you should look for a new reference plan for which the CF value is greater than for the current one. In this case, two cases are possible:

a) if all components of the vector A k, to be entered into the basis, are non-positive, then the LLP has no solution (there is no final optimum);

b) if the vector has at least one positive component A k, to be entered into the basis, then a new reference plan can be obtained.

Based on the optimality criterion, a vector is introduced into the basis A k, which gave the minimum negative value of the simplex difference:

In order for the condition of non-negativity of the values ​​of the reference plan to be satisfied, the vector is derived from the basis A r, which gives the minimum positive evaluation ratio

Line A r, in which the old basis vector was located, is called the guide, column A k and element a rk- guides.

The elements of the guide line in the new simplex table are calculated using the formulas:

and any other elements i th line - according to the formulas:

The values ​​of the new reference plan are calculated using similar formulas:

,

The process continues either until an optimal plan is obtained or until the TF is unlimited. If among the differences Δ j , j=1, 2, … , n of the optimal plan, only the differences corresponding to the basis vectors are zero, this indicates the uniqueness of the optimal plan. If the zero estimate corresponds to a vector not included in the basis, then in the general case this means that the optimal plan is not unique.

Example. Solve the ZLP using the model:

find ,

under restrictions

This ZLP is reduced to canonical form by introducing additional variables x 3 And x 4:

KZLP has the required number (two) of zero columns at x 3 And x 4, that is, it has an obvious initial reference plan (0,0,300,150).

The solution is carried out using the simplex method with a natural basis with the calculations formatted in simplex tables:

Simplex table number	Basis	with j	with j					Q
B	A 1	A 2	A 3	A 4
	←A 3
A 4
Δ	-		-2	-3			-
I	→A 2			1/3		1/3
←A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Let us dwell in more detail on filling out the simplex tables and, accordingly, obtaining the KZLP solution.

IN top line general table coefficients added c j , j=1, 2, 3, 4 with variables in the CF. The first two rows of the zero simplex table contain column vectors B, A 1, A 2, A 3, A 4, corresponding vector form KZLP records. Since the initial basis is a pair of vectors A 3 , A 4, they are included in the column called “Base” of the zero simplex table. Wherein, A 3 is included in the first row, which is determined by the unit being the first element of this vector, and the vector A 4- to the second line, for this vector the unit is in the second line. In the column called “ c i” the coefficients of the objective function corresponding to the basis vectors are introduced A 3 , A 4, that is c 3, c 4. They are both equal to zero. Next, the values ​​of the differences Δ for the vectors are calculated B, A 1, A 2, A 3, A 4 and are entered in the third row of the zero table. For vector A 1:

for vector:

Likewise, .

For vector B calculating the difference is somewhat simplified since there is no corresponding coefficient c j , j=1, 2, 3, 4 in CF:

Not for all vectors A 1 , A 2 , A 3 , A 4 the resulting differences are non-negative, so the reference plan we have chosen is not optimal. We need to look for a new reference plan, and for this we need to replace one of the vectors included in the basis A 3 , A 4.

To determine the vector that we must enter, we look for the vector for which the difference value is minimal. This is the vector A 2, it corresponds to the minimum difference value: -3. That is, the index k from formula (8.4) is equal to 2. To determine the vector that we will have to derive from the basis, we calculate the values Q for each line according to formula (8.5) and enter them in the last column. IN in this case in each line we need the value of the vector element B divide by the magnitude of the vector element A 2. In the first line we get 300/3=100, in the second: 150/1=150. The ratio in the first row was smaller; the basis vector corresponded to it A 3, therefore, the index r in formula (8.5) is equal to 1, a rk=3 (highlighted in the table with a frame), and we will derive the vector from the basis A 3(indicated by an arrow in the table).

Since among the elements of the vector A 2, which must be entered into the basis, there are positive ones, then a new reference plan can be obtained and the solution should be continued.

After this, the second simplex table is filled in. To recalculate vector elements B, A 1, A 2, A 3, A 4 formulas (8.6)-(8.8) are used. They are slightly different for defining the elements of the guide line (in our case, the first one) and for defining the elements of other lines. Let's write down the calculations of several elements:

Other elements of the first simplex table are calculated in the same way as we did for the zero table. Since not all differences in the first simplex table are non-negative, it becomes necessary to continue the calculations.

As we see, as a result of calculations in the second simplex table with basis vectors A 2 , A 1 all differences turned out to be non-negative, which means achieving the optimal plan (75; 75; 0; 0). Simplex difference for a vector IN equal to the desired maximum CF value - 375.

Theorem (about the finiteness of the simplex algorithm).If there is an optimal PPP decision, then there is a basic optimal solution. The latter can always be obtained using the simplex method, and you can start from any initial basis.

To apply the simplex method with a natural basis, the KZLP must contain a unit submatrix of size mxm - in this case, the initial support plan (a non-negative basic solution to the system of KZLP constraints) is obvious.
To be specific, we assume that the first m vectors of the matrix of the system of equations constitute the identity matrix. Then the initial reference plan is obvious - (b 1, b 2,..., b m,0,...,0).
The optimality of the reference plan is checked using the optimality criterion; the transition to another reference plan is carried out using the Jordan-Gauss transformations using the mathematical optimality criterion. The resulting reference plan is again checked for optimality, and so on. The process ends in a finite number of steps, and at last step either the unsolvability of the problem is revealed (there is no final optimum), or an optimal reference plan and the corresponding optimal value of the CF are obtained.
The mathematical criterion for optimality consists of the following two theorems:
1. If for all vectors A 1, A 2,…, A n the condition is satisfied
Where ,
then the resulting reference plan is optimal.
2. If for some vector not included in the basis the condition is satisfied , then you can get a new reference plan for which the CF value will be greater than the original one, and there can be two cases:
- if all components of the vector to be entered into the basis are non-positive, then the LLP has no solution (there is no final optimum);
- if there is at least one positive component of the vector to be entered into the basis, then a new reference plan can be obtained.
Based on the optimality criterion, vector A k is introduced into the basis, which gives the minimum negative value of the simplex difference:
In order for the condition of non-negativity of the values ​​of the reference plan to be satisfied, the vector A r is derived from the basis, which gives the minimum positive evaluation ratio

Row A r is called a guide, column A k and element a r k are called guides.
The elements of the guide line in the new simplex table are calculated using the formulas:
A i-th elements lines - according to the formulas:
The values ​​of the new reference plan are calculated using the formulas:
for i = r ;
The decision process continues either until an optimal plan is obtained or until the TF is established as unlimited. If among the simplex differences (estimates) of the optimal plan only the estimates corresponding to the basis vectors are zero, then this indicates the uniqueness of the optimal plan. If a zero estimate corresponds to a vector that is not included, then in the general case this means that the optimal plan is not unique.
Note. To use the given procedure for minimizing linear function f (x 1 ,x 2 ,…, x n) you should look for the maximum - f (x 1 ,x 2 ,…, x n), then take the resulting maximum with the opposite sign. The optimal solution is the same.
Example. Get a solution based on the model:
This problem (model) of linear programming, let us bring it to canonical form by introducing additional variables x 3 and x4:
The KZLP has the required number of single columns, i.e. has an obvious initial reference plan (0,0,300,150). The solution is carried out using the simplex method with a natural basis and calculations are presented in simplex tables:

j. Optimal values variables are equal: x1*=75, x2* =75 (main variables), x3* =0, x4* =0 (additional variables). Maximum value the objective function is 375.
Thus, in the problem discussed above optimal use limited resources, optimal manufacturing program consists of a release of 75 units. products of the first type and 75 units. products of the second type. This program is associated with the maximum revenue from the sale of finished products - 375 USD.

Number			IN	2	3	0	0
simplex-	Basis		plan					Q
tables
	A3	0	300	1	3	1	0	100
0	A4	0	150	1	1	0	1	150
		f(x)	0	-2	-3	0	0
	A2	3	100	1/3	1	1/3	0	300
I	A4	0	50	2/3

Simplex method. Algorithm. Sign of optimality of the reference plan.

From the geometric interpretation of the ZLP it is clear that the maximum or minimum of the function is achieved at the corner point of a convex polyhedron - ODP - system of constraints. Therefore, the simplex method is based on the idea of ​​considering and testing for optimality only the corner points - the vertices of the polyhedron, and not the entire infinite set of its points.

Rice. Geometric interpretation of the idea of ​​the simplex method

in the case of two (Figure a) and three (Figure b) variables.

Simplex is a convex polygon in n-dimensional space with n+1 vertices that do not lie in the same hyperplane (the hyperplane divides the space into 2 half-spaces).

Simplex method is a computational procedure based on the principle of sequential improvement of the solution. In this case, we move from one base point to another. The value of the objective function always improves.

Basic solution– this is one of the acceptable solutions found in the ODR.

Variables for which a system of linear equations is resolved are called basic. Then all other variables are called free.

It has been proven that if an optimal solution exists, then it will be found in a finite number of steps, except in cases of looping.

Simplex method algorithm:

1. Build mathematical model tasks.

1. Convert the resulting mathematical model into canonical form, in which: the right-hand sides of the conditions are non-negative; the conditions are equalities (if necessary, introduce artificial variables).
2. Construct a simplex table and find the initial reference plan for solving the problem. Many variables that are basic, are taken as the initial basic solution. The values ​​of these variables are equal to the free terms. All other variables are zero.
3. Checking the basic solution for optimality is carried out using special estimates of the coefficients of the objective function (see last line tables). If the problem is solved at max, then all estimates must be non-negative, if at min, then all estimates must be non-positive.
4. Transition to a new basic solution. Obviously, the optimal plan should include a variable that will increase the objective function to the greatest extent. When solving max problems, the optimal plan includes products whose production is most profitable. This is determined by the max positive value of the estimate of the coefficients of the objective function. The table column that contains this estimate is called the master column. If at least one element of the column is positive, then the general row is found (otherwise the task has no optimal solution). If there are zeros in this column, then you need to take another column. To find the general row, all free members (resources) are divided into the corresponding elements of the general column (resource consumption rate per unit of product). The smallest one is selected from the results obtained, and the corresponding row is called the general row. It corresponds to a resource that limits production to this step. A simplex table element located at the intersection of a general row and a column is called a general element. All elements of the general string, including the free member, are divided into the general element. As a result, the general element becomes equal to 1. Next, it is necessary that all other elements of the general column become equal to 0. The general column must become one. All lines except the general one are converted as follows: received elements new line multiply by the corresponding elements of the general column, and subtract the resulting product from the elements of the old row. The value of the new basic variables will be obtained in the corresponding cells of the column of free terms (rule of rectangles).
5. The resulting basic solution is checked for optimality (step No. 4). If it is optimal, then the calculations stop, otherwise a new basic solution is found (step No. 5).

Sign of optimality of the reference plan

If we solve a problem for max, then all estimates must be non-negative.

If we solve a problem for min, then all estimates must be non-positive.

If the reference plan is not optimal, you need to move to a better reference plan. To do this, we choose the worst estimate. It will correspond to the resolution column. After this, you need to find the enabling line.

Θ (column of simplex relations) is not drawn for lines with negative and zero values. Of all θ, we choose the smallest; this is always done, no matter whether the original problem is min or max.

The resolving line always shows which element must be removed from the basis, and the resolving column always shows which element must be entered into the basis.