2. Introduction of natural basic variables. Construction of a simplex table. Definition of the zero plan.

Simplex method. Algorithm of the simplex method.

Simplex method- solution algorithm optimization problem linear programming by enumerating the vertices of a convex polyhedron in multidimensional space. The method was developed by American mathematician George Danzig in 1947.

The idea of ​​the simplex method is that the posed descriptive problem is translated into mathematical form. The mathematical formulation of the problem contains the equation of the objective function indicating the desired result - determining the minimum or maximum of the objective function; systems of linear constraints specified by equalities or inequalities. Received mathematical description lead to matrix form. Then the matrix description of the problem is reduced to canonical form. After the system linear equations reduced to canonical form, we begin to solve the linear programming problem. The algorithm for solving this problem consists of a sequence of constructing matrices. Each step of the solution brings you closer to obtaining the desired result.

In the computational scheme of the simplex method, an ordered process is implemented in which, starting from some initial admissible corner point (usually the origin), successive transitions are made from one admissible extreme point to another until a point corresponding to the optimal solution is found.

Simplex method algorithm

1. We bring the system of restrictions to canonical form(when the system is limited). Moreover, a single basis can be identified in the system.

2. Find the original reference plan(non-negative basic solutions of the KZLP system of equations). Each of the reference plans is determined by a system of m linearly independent vectors contained in a given system of n vectors A 1 , A 2 ,…, A n. The upper limit on the number of reference plans contained in a given problem is determined by the number of combinations With nm);

3. We build simplex table (simplex table a matrix that serves as a means of enumerating admissible basis solutions of a (non-degenerate) linear programming problem when solving it using the simplex method. It is formed from the matrix of coefficients of a system of linear programming equations reduced to canonical form, its sequential transformation according to the so-called simplex algorithm allows a limited number of steps (iterations) to obtain the desired result - a plan that provides an extreme value of the objective function).

4. B simplex table we check the vectors for negativity, i.e. assessments Zj – Сj written in the line must be ≤ 0 (at a minimum), Zj – Сj ≥ 0(to the maximum). If the estimates satisfy the optimality conditions, then the problem is solved.

5. If for some vectors the optimality conditions are violated, then it is necessary to introduce into the basis a vector that corresponds to:

max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min, Where x i> 0

Vector element θ j which corresponds θ 0 j called permissive; the row and column in which it is located are called the guide; the vector in the guide row leaves the basis.

6. Let's find the expansion coefficient for all vectors in the new basis. Let's apply the Giordano Gauss method

Let's check for the optimal reference plan. If the estimate satisfies the optimality conditions, then the problem is solved; if not, then steps 5-7 are performed.

2. Introduction of natural basic variables. Construction of a simplex table. Definition of the zero plan.

The simplex method is most effective in solving complex tasks and represents an iterative (step-by-step) process starting with zero(reference) solution (vertex n-dimensional polyhedron). Next in search optimal option The plan assumes movement along the corner points (vertices of the polyhedron) until the value of the objective function reaches the maximum (minimum) value. Let's consider the algorithm of the simplex method using the example of a turnover planning problem with limited raw material resources.

The company sells n product groups, having m limited material and monetary resources b i ≥0 (1 ≤ i≤ m) . Everyone's resource costs are known i- type of production and sale of a unit of goods of each group, presented in the form of a matrix ( a ij) and the profit received by the enterprise from the sale of a unit of goods j-group included in the objective function Z(X). The linear programming method is no different from system (1) - (2):

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,

a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)

a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

The stages of solving the problem using the simplex method include:

1) Drawing up a zero reference plan. We introduce new non-negative (basic) variables, thanks to which the system of inequalities (2) becomes a system of equations:

a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1

a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

……………………………………..

a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,

If we take the input variables as column vectors, then they represent single (basic) vectors. Note that the basic variables have a simple physical meaning- This remainder specific resource in the warehouse for a given production plan, therefore this basis is called natural. We solve system (3) with respect to the basic variables:

X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n

X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

We rewrite the objective function in the form

Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)

Assuming that the required main variables X 1 = X 2 = X 3 = ... = X n = 0, we obtain a zero reference plan X = (0, 0, ...0, b 1, b 2, b 3 ... b m), at which Z(X) = 0 (all resources in stock, nothing produced). We enter the plan into a simplex table.

Plan	Basis	C i /C j	Meaning X i	X 1	X 2	X n	Xn+1	Xn+2	X n+ 3	Qmin
	Xn+1		b 1	a 11	a 12	a 13				b 1/a 12
Xn+2		b 2	a 21	a 22	a 23				b 2 / a 22
Xn+3		b 3	a 31	a 32	a 33				b 3 / a 32
Z(X) = 0	-C 1	- C 2	- C 3				Index. line

2) From the negative coefficients of the index line, we select the largest in absolute value, which determines the leading column and shows which variable at the next iteration (step) will move from the main (free) to the basic (in fact, the product group whose sales brings maximum income). Then we divide the reserves of raw materials b i by the corresponding cost coefficients, enter the results into a table and determine the minimum value Q min (the resource whose reserve most strongly limits the output of the selected product group is selected). This value selects the leading line and the variable Xi, which at the next step (iteration) will leave the basis and become free.

3) The transition to a new plan is carried out as a result of recalculation of the simplex table using the Jordan-Gauss method. First, we replace X j in the basis with X i of the leading column. Let's divide all the elements of the leading line by the resolving element (RE), as a result of which the place of the RE in the leading line will be 1. Since X i has become basic, its remaining coefficients should be equal to 0. New elements of this plan are found according to the rectangle rule

NE=SE – (A*B)/RE (6)

The resulting plan is evaluated using the coefficients of the index line: if they are all positive, then the plan is optimal; if not, then the plan can be improved by performing the next iteration (step).

Example. 20 thousand rubles were allocated for the purchase of equipment for the production site. The equipment can be placed on an area not exceeding 72 sq.m. You can order equipment of two types: type A, requiring a production area of ​​6 sq.m and providing 6 thousand units. products per shift (price 5,000 rubles) and type B, requiring an area of ​​12 sq.m. and producing 3 thousand units (price 2,000 rubles). What is the optimal equipment acquisition plan to ensure maximum performance plot?

Let us denote the quantity of purchased equipment of type A and B by X 1 and X 2, respectively.

Site productivity ( objective function): Z(X) =6Х 1 +3Х 2.

The main limitations are related

with cash: 5Х 1 +2Х 2 ≤ 20,

with production site area: 6Х 1 +12Х 2 ≤ 72.

We introduce new basic variables X 3 (remainder Money after purchasing equipment) and X 4 (remaining area after equipment placement) and rewrite the restrictions in the form of a system of equations:

5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

In this case, the goal function: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .

We make a reference (0th) plan: X = (0, 0, 20, 72), i.e. nothing has been purchased yet (no money has been spent, the space is empty). Making a simplex table

Plan	Basis	C i /C j	Meaning X i	X 1	X 2	X 3	X 4	Qmin
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Index line
	→X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Index line
	X 1					0,25	-1/24	-
→X 2					-1/8	5/48	-
Z(X) =6*2+3*5=27			9/8	1/16	Index line

Obviously, the leading column corresponds to X 1, since it has the largest index 6. We find the minimum value of Q min = 4 (the most severe resource constraint) by defining a leading row showing that X 3 is derived from the basis variables, and X is entered instead 1 . We recalculate the elements of the leading line, dividing them by 5, and using formula (6) we determine the elements of the second and index lines. The objective function for the 1st plan is equal to Z(X) = 6*4+3*0 = 24.

However, one of the coefficients of the index row for column X 2 remains negative -0.6, therefore this plan is not optimal, and another iteration (step) is required to improve it. Select the 2nd column as leading and minimum value Q min = 5 we define the leading line with the basic variable X 4. Having performed the same transformations, we obtain the 2nd plan, which will be optimal, since all index coefficients are positive.

Let's analyze the results obtained. For an optimal solution, the objective function has maximum value 27 thousand rubles, while both resources are taken out of the base, therefore completely spent.

Let's make sure of this: 5*2+2*5 = 20 thousand rubles, 6*2+12*5=72 sq.m. The required solution is X = (2; 5;0;0). This does not always happen.

Lecture No. 10

Subject: Simplex method for problems with an artificial basis

The simplex solution method is based on the introduction of additional (basic) variables that make it possible to form a unit matrix. If the problem constraints are presented in the form of inequalities:

a i1 X 1 + a i2 X 2 +…a in X n ≥ b i (1)

or equations:

a i1 X 1 + a i2 X 2 +…a in X n = b i (1*),

then it is impossible to obtain the reference plan in the desired form. In this case, to comply with equalities (1*), we introduce artificial basis Y i , and artificial variables are not directly related to the content of the task, but make it possible to construct a reference (starting) plan:

a i1 X 1 + a i2 X 2 +…a in X n +Y i = b i (2)

The objective function when solving the problem to the maximum will be written in the form:

Z(X) =∑C j X j +(-M)∑Y i (3),

when solving a similar problem at a minimum:

Z(X)=∑C j X j +(M)∑Y i (3*),

where M is very large positive number, a kind of penalty for using artificial variables.

In the case of inequalities (1), we initially introduce additional variables X n + i with a minus sign. Their matrix will not be unitary, therefore, into each inequality of system (1) we introduce artificial variables У i:

a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b i (4)

The objective function in this case is Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (to find the maximum). Application artificial basis gives the simplex method greater flexibility and allows it to be used for a wide range of tasks.

Example . Determine the maximum and minimum profit values ​​for the production of two types of products A and B, if production costs and profitability from sales of a unit of product are given in the table. The main condition is full employment of workers at the enterprise.

Mathematically, the production output constraints will be written in the form of a mixed system:

1X 1 + 1X 2 ≤ 6,

2X 1 + 1X 2 =8.

Let us introduce the basic variable X 3 for the first inequality, and the artificial variable Y 1 for the second equation:

1X 1 + 1X 2 + X 3 = 6,

2X 1 + 1X 2 +Y 1 =8.

Let us express X 3 and Y 1 from the resulting system of equations and, to determine the maximum, imagine the objective function:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

For the reference plan - X=(0,0,6,8). Let's build a simplex table:

Plan	Basis	C i /C j	Meaning X i	X 1	X 2	X 3	Y 1	Qmin
	X 3							6/1=6
Y 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Index line
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		M+1.5	Index line
	→X 2						-1	-
X 1					-1		-
Z(X) =3*2+2*4=14				M+1	Index line

As a rule, improvement of the reference plan begins with the removal of the artificial variable Y 1 from the basis. The optimal plan X = (2,4,0,0) was obtained in the second iteration, with a maximum income of 14 thousand. rub. , and the coefficients of the index row are non-negative. It is easy to verify that in this task, with an optimal plan, resources are fully used (2*1+4*1=6; 2*2+1*4=8).

When finding the minimum profitability, we formulate the objective function differently (+MY 1 is entered as a term:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

The reference plan is the same, but the index row coefficients in the simplex table are different. The leading column, as before, is selected by the largest positive coefficient in absolute value for X 1, the leading row is determined by the minimum value of Q min = 4. At the first iteration, the artificial variable Y 1 is derived from the basis.

Plan	Basis	C i /C j	Meaning X i	X 1	X 2	X 3	Y 1	Qmin
	X 3							6/1=6
Y 1	M						8/2=4
Z(X) = 8M	2M-3	M-2			Index line
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-M+1.5	Index line

The resulting negative values ​​of the coefficients in the index line X i indicate the optimality of the 1st plan, while the minimum income is 12 thousand rubles.

It is provided only by the output of product A (product B is not produced), the raw materials are not fully used (remainder X 3 = 2t), while the main condition is met - the workers are fully employed in production.

Lecture No. 11

Topic: Closed transport problem

1. Mathematical formulation of closed transport problem. Determining the required number of unknowns.

2. Stages of determining a plan for solving a transport problem.

Lecture 3. Simplex tables. Algorithm of the simplex method.

§ 3 SIMPLEX METHOD

3.1. General idea of ​​the simplex method. Geometric interpretation

The graphical method is applicable to a very narrow class of linear programming problems: it can effectively solve problems containing no more than two variables. The basic theorems of linear programming were considered, from which it follows that if a linear programming problem has optimal solution, then it corresponds to at least one corner point of the solution polyhedron and coincides, according to at least, with one of the admissible basic solutions of the system of constraints. The way to solve any linear programming problem was indicated: enumerate final number admissible basic solutions of the system of constraints and select among them the one on which the objective function makes the optimal solution. Geometrically, this corresponds to enumerating all the corner points of the solution polyhedron. Such an exhaustive search will ultimately lead to an optimal solution (if it exists), but its practical implementation is associated with enormous difficulties, since for real problems the number of feasible basic solutions, although finite, can be extremely large.

The number of permissible basic solutions to be searched can be reduced if the search is not carried out randomly, but taking into account changes in the linear function, i.e. ensuring that each next solution is “better” (or at least “no worse”) than the previous one, according to the values ​​of the linear function (increasing it when finding a maximum, decreasing it when finding a minimum
). This search allows you to reduce the number of steps when finding the optimum. Let's explain this with a graphic example.

Let the area admissible solutions represented by a polygon ABCDE. Let's assume that its corner point A corresponds to the original feasible basis solution. A random search would require testing five feasible basis solutions corresponding to the five corner points of the polygon. However, it is clear from the drawing that after the top A it is advantageous to move to a neighboring vertex IN, and then to the optimal point WITH. Instead of five, we went through only three vertices, consistently improving the linear function.

The idea of ​​consistent improvement of the solution formed the basis universal method solving linear programming problems – simplex method or method of sequential improvement of the plan.

The geometric meaning of the simplex method consists in a sequential transition from one vertex of the constraint polyhedron (called the initial one) to the neighboring one, in which the linear function takes the best (at least not the worst) value in relation to the goal of the problem; until the optimal solution is found - the vertex where the optimal value of the goal function is achieved (if the problem has a final optimum).

The simplex method was first proposed by the American scientist J. Danzig in 1949, but back in 1939 the ideas of the method were developed by the Russian scientist L.V. Kantorovich.

The simplex method, which allows solving any linear programming problem, is universal. Currently, it is used for computer calculations, but simple examples using the simplex method can be solved manually.

To implement the simplex method - sequential improvement of the solution - it is necessary to master three main elements:

a method for determining any initial feasible basic solution to a problem;

the rule of transition to the best (more precisely, not worse) solution;

criterion for checking the optimality of the solution found.

To use the simplex method, the linear programming problem must be reduced to canonical form, i.e. the system of constraints must be presented in the form of equations.

The literature describes in sufficient detail: finding the initial support plan (initial admissible basic solution), also using the artificial basis method, finding the optimal support plan, solving problems using simplex tables.

3.2. Algorithm of the simplex method.

Let us consider the solution of the ZLP using the simplex method and present it in relation to the maximization problem.

1. Based on the conditions of the problem, its mathematical model is compiled.

2. The completed model is converted to the canonical form. In this case, a basis with an initial reference plan can be identified.

3. The canonical model of the problem is written in the form of a simplex table so that all free terms are non-negative. If the initial reference plan is selected, then proceed to step 5.

Simplex table: a system of constraint equations and an objective function are entered in the form of expressions resolved relative to the initial basis. A line containing the coefficients of the objective function
, called
– a string or a string of the target function.

4. Find the initial reference plan by performing simplex transformations with positive resolving elements corresponding to the minimum simplex relations, and without taking into account the signs of the elements
–lines. If during the transformations a 0-row is encountered, all of whose elements, except for the free term, are zeros, then the system of constraint equations for the problem is inconsistent. If we encounter a 0-row in which, apart from the free term, there are no other positive elements, then the system of restrictive equations has no non-negative solutions.

We will call the reduction of system (2.55), (2.56) to a new basis simplex transformation . If a simplex transformation is considered as a formal algebraic operation, then one can notice that as a result of this operation, roles are redistributed between two variables included in a certain system linear functions: one variable goes from dependent to independent, and the other, on the contrary, goes from independent to dependent. This operation is known in algebra as Jordan elimination step.

5. The found initial support plan is examined for optimality:

a) if in
– there are no negative elements in the row (not counting the free term), then the plan is optimal. If there are no zeros, then there is only one optimal plan; if there is at least one zero, then there is an infinite number of optimal plans;

b) if c
– there is at least one negative element in the row, which corresponds to a column of non-positive elements, then
;

c) if in
– the row has at least one negative element, and its column has at least one positive element, then you can move to a new one reference plan, closer to optimal. To do this, the specified column must be designated as a resolving column, using the minimum simplex ratio, find the resolving row and perform a simplex transformation. The resulting reference plan is again examined for optimality. The described process is repeated until an optimal plan is obtained or until the unsolvability of the problem is established.

The column of coefficients for a variable included in the basis is called resolving. Thus, selecting a variable entered into the basis (or selecting a resolving column) by the negative element
-strings, we provide increasing function
.

It is a little more difficult to determine the variable to be excluded from the basis. To do this, they compose the ratios of free terms to the positive elements of the resolving column (such relations are called simplex) and find the smallest among them, which determines the row (resolving) containing the excluded variable. The choice of a variable excluded from the basis (or the choice of a resolving line) according to the minimum simplex relation guarantees, as has already been established, the positivity of the basis components in the new reference plan.

In point 3 of the algorithm, it is assumed that all elements of the free terms column are non-negative. This requirement is not necessary, but if it is met, then all subsequent simplex transformations are performed only with positive resolving elements, which is convenient for calculations. If there are negative numbers in the free terms column, then the resolving element is chosen as follows:

1) look at the line corresponding to some negative free term, for example – a row, and select any negative element in it, and the corresponding column is taken as resolving (we assume that the constraints of the problem are consistent);

2) make up the relations of the elements of the column of free terms to the corresponding elements of the resolving column that have the same signs (simplex relations);

3) choose the smallest of the simplex relations. This will determine the enabling string. Let it be, for example, R-line;

4) at the intersection of the resolving column and row, a resolving element is found. If the element is permissive –strings, then after the simplex transformation the free term of this string will become positive. Otherwise, in the next step we turn again to -line. If the problem is solvable, then after a certain number of steps there will be no negative elements left in the column of free terms.

If a certain real production situation is put into the form of a PLP, then the additional variables that have to be introduced into the model in the process of converting it to the canonical form always have a certain economic meaning.

The simplex method consists of finding and testing a vertex (angle) that is a solution to the LP problem. At each stage, the method selects a vertex and its corresponding variables, which ensure movement to the minimum (maximum) with highest speed. The selected variable replaces the other, most restrictive one. The simplex method also allows you to determine whether a solution exists. The algorithm implementing the simplex method can be written as:

Step 1. A certain vertex in the ODR is determined, corresponding to the basic admissible solutions (variables) found by extracting from the matrix T- linearly independent columns and equating to zero all other variables corresponding to other columns of the matrix.

Step 2. Selected from all possible remaining p - t edges corresponding to non-basic variables, an edge (variable) that, when moving along it, leads to the fastest decrease in the objective function.

Step 3. It is as if a movement is carried out from the initial vertex along the selected edge to another vertex, which gives a new solution that has a lower CF value. A new vertex is formed by replacing the basis variable (edge) with a new basis variable (edge).

The columns and elements of vectors are usually ordered and written in the form of a simplex table, the formation of which will be shown below.

The simplex method solves the LP problem in standard form.

Minimize (maximize) the function under the conditions x > 0; Ax = b.

Matrix A is real and has the dimension T x "and rank T.

The formulated LP problem can also be written in the form

Based on the recording of the LP problem in the form (8Л), we can say that the extended matrix

dimensions (t + 1) (n + 2) corresponds to solutions[x/] t.

Let's represent matrix A as a set of columns

Since matrix A has rank T, then there will be T linearly independent columns of the matrix A, for example (a V1 ,...,a V/i Consider a vector x° > 0, such that all of it p - t elements are 0 and Ax° = b. Let these be elements with numbers..., i n _ m . Let us also assume that the location aw of linearly independent columns of matrix A corresponds to the location of non-zero elements in the vectors 0. Geometrically, according to Statement 3 of § 7.6, this means that x° is the vertex (angle) of the ODR and, in addition, satisfies given conditions. This solution is called admissible basic solution. The angles of the admissible set are admissible basic solutions.

Recall that the set of basic solutions contains all the information necessary for the optimal solution of the LP problem. For the two-dimensional case considered in § 7.6, the basic solutions are all 6 points, and the admissible basic solutions are the points L, V, Si 0.

Thus, any vector x similar to x° can be written as

Where x in- a vector whose elements correspond to linearly independent columns of matrix A; xF - vector with zero elements.

Let us similarly define the vectors

Variables that are elements of a vector x in, are called basic variables, and the variables that are elements of the vector x F are called free (non-basic) variables.

Because x° F=0, then the value of the objective function for the initial vector x° will be equal to

where /° is the value of / at point x°.

Solution (8.1) of the form [x°/°]t for x > 0 is called obvious (explicit) solution. Thus, if we set non-basic variables equal to zero, we get an obvious solution.

For convenience, let's rearrange T linearly independent columns of matrix A to the left side and write the matrix in the form

Here matrix B corresponds T linearly independent columns has dimension tx t and rank T, and the matrix F

is tx (p - t) matrix. Since matrix B consists of linearly independent columns, it has an inverse B -1 and detB φ 0. Note that to form matrix B you can choose any T linearly independent columns of matrix A.

Let us represent problem (8.1) taking into account the introduced notation

This representation corresponds to the extended matrix. Let us assume that

whence follows

If vector x V will be a solution to the system Bx d = b, then it will be the basic solution. If the inequality holds V= B -1 b > O, then x in will be an acceptable solution.

Thus, the current solution satisfies the following equation:

Let's consider matrix (8.4). The basic variables will be presented in explicit form if we replace the matrix B with the identity matrix I. Multiplying the first row of matrix (8.4) on the left by B~ 1, we get

where B_1 b > O, i.e. T The top elements in the right column are non-negative and represent the current value of the variables.

On the left side top line The result is a unit matrix: B -1 B = I. This presentation very convenient, because when multiplying by a vector x in each variable will be on a separate line.

Thus, basic solution, which we will consider admissible and corresponding to the basis B, is x m = [x in 0], where x in == B_1 b. The basic solution results from the assumption that x F = 0. However, if xF* 0, then x^ can be calculated as x 5 = = B~"b - B^"Fx/r. Substituting this expression into the objective function (cost function), we obtain

Since it is necessary to determine the dependence of cost on non-basic variables, one of which is then included in the basic ones, the bottom line under matrix I should be zero. To do this, in (8.7) we multiply the first row (of the matrix) by from to and add it with the second one

where is the value of the objective function for the initial century

torus x 0 from (8.3).

Matrix (8.8) is called simplex table. Bringing her to this species is the initial stage of the simplex algorithm. During the execution of the algorithm, a transition is made from one table to another until the lower right element of the table becomes the maximum or minimum.

Using a simplex table it is easy to see a valid solution. Variables x F correspond to the zero submatrix, variables x in- unit matrix:

Let us assume that the LP problem has been reduced to standard form, the simplex table has been calculated, and the initial basic solution corresponding to the vertex of the solution polyhedron has been selected.

Then - solution to problem (8.1). So

like b > Oh, this is a basic admissible solution.

Let us present matrix (8.9) in a more convenient form, keeping the basic notation:

Let us consider separately the problems of maximization and minimization.

Let's consider a universal method for solving the canonical linear programming problem

With n variables and m equality constraints, known as the simplex method.

The set of plans for a canonical problem is a convex polyhedral set with a finite number of corner points. And if this problem has an optimal solution, then it is achieved at least at one corner point.

Any corner point is associated with a basic plan of the problem, in which the variables are equal to zero, and the remaining variables correspond to linearly independent columns of the condition matrix. These linearly independent columns form a non-singular basis matrix.

Iterating over all corner points is computationally expensive and therefore ineffective. In 1947, J. Danzig proposed an orderly procedure for enumerating corner points, in which it is enough to examine only a small part of them to find the optimal solution. This procedure is called simplex method.

J. Danzig proposed replacing only one vector in the basis matrix when moving from one extreme point to another. This means that during such a transition we must exclude one of the basic variables - make it non-basic ( equal to zero), and in its place introduce a new variable from among the non-basic (zero) ones - make it basic (positive).

It turns out that geometrically such a replacement leads to a transition from one corner point to an adjacent (neighboring) one associated with previous point common edge.

Of all the neighboring points, the one at which the objective function increases the most is selected. Since the number of corner points is finite, through a finite number of transitions the vertex with highest value objective function, or the unboundedness of the objective function will be established on an unlimited set of plans.

The general scheme of the simplex method consists of the following main steps.

· step 0. Determination of the initial basis and the corresponding initial corner point (baseline).

· step 1. Checking the current baseline for optimality . If the optimality criterion is satisfied, That the plan is optimal and the solution is complete. Otherwise go to step 2.

· step 2. Finding the variable introduced into the basic ones. (From the condition of increasing the objective function).

· step 3. Finding a variable excluded from the basic variables (From the condition of preserving the constraints of the problem).

· step 4 . Finding the coordinates of the new baseline (adjacent corner point). Go to step 1.

Repeated steps 1-4 form one iteration of the simplex method.

From this diagram it follows that, firstly, to start the simplex method, you need to have some kind of corner point - an initial basic plan, and secondly, you need to be able to examine the current corner point for optimality without calculating all adjacent vertices. These problems are easily solved if the canonical LP problem has some special form.

Definition. We will say that the canonical LP problem has a “preferred form” if

1. right-hand sides of the equations, .

2. the condition matrix contains a unit submatrix of size

In other words, in any equation there is a variable with a coefficient equal to one, missing from the other equations. The first condition is not burdensome, since in the case of a negative right-hand side of some equation, it is enough to multiply it by (-1). In a preferential type problem, finding the initial baseline is very simple.

Example 2.1.

Condition Matrix A and the vector of the right-hand sides of the constraints b look like

A target vector c = (1, -3, 0, 4, 2).

One basis matrix is ​​immediately obvious: with unit vectors of conditions.

Therefore, choosing as basic variables x 1 , x 3 ,x 5 , and putting in the system of equations x 2 = x 4 = 0 (non-basic variables) , we find it immediately x 1 = 10,x 3 = 20,x 5 = 8, so the initial baseline x 0 = (10, 0, 20, 0, 8). We see that the values ​​of the basic variables are equal to the right-hand sides of the constraints. From this it is clear that the right-hand sides must be positive b i .

In the future, we will combine the basic variables into a vector x B.

Thus, in canonical problem of the preferred form, the identity submatrix is ​​taken as the initial basis matrix A B = E, and the corresponding basis variables are equal to the right-hand sides of the constraints:

x B = b.

For a basic plan of this type, an optimality criterion that is simple enough to test can be formulated. Let's introduce the quantities

? j = < с B , A j > - c j , j = 1,...,n,(2.1)

Where With B- vector of coefficients of the objective function for basic variables x B , A j -j- th condition matrix column, c j -j- th coefficient of the objective function. Differences ? j are called simplex differences or simplex estimates.

Optimality criterion for the basic plan. If for a basic plan with a unit basis matrix all simplex estimates are non-negative, then this plan is optimal.

Let us apply this criterion to check the optimality of the basic plan x 0 = (10, 0, 20, 0, 8) from example 2.1.

Since in this regard the vector of basic variables x B =(x 1 , x 3 ,x 5 ), That With B = (c 1 , c 3 ,c 5 ) = (1, 0, 2).

Hence,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Since the assessment ? 4 < 0, то базисный план x 0 not optimal. Note that the simplex estimates corresponding to the basic variables are always equal to zero, so it is sufficient to check only the non-basic estimates.

The idea of ​​the simplex method

Simplex method

In the previous section, it was shown that if a linear programming problem has an optimal solution, then one of the optimal solutions is an admissible basic solution to its system of constraints, which corresponds to some corner point of the polyhedron of admissible solutions of the system. It was shown how to find this optimal solution using a finite search of basic solutions to the system of constraints of the problem. However, as the dimension n of the problem constraint system increases, the volume of calculations for solving the problem by the method of exhaustive enumeration of basic solutions grows exponentially and becomes unsuitable in practice. It is possible to organize an enumeration of only feasible basic solutions and sharply reduce the number of enumerated solutions if each subsequent admissible basic solution is chosen so that the corresponding value of the objective function improves or at least does not deteriorate. This approach allows you to reduce the number of steps when finding the optimal basic solution. Let us explain this idea graphically.

Let the polygon ABCDEFGH represent the set of admissible solutions of the PLP with two variables, and the vector – gradient of the objective function.

We need to find the point of this polygon at which the objective function takes on the smallest value. Let the initial admissible basic solution of the problem corresponding to the corner point B be determined. After a complete search of all admissible basic solutions, it will be necessary to examine eight such solutions corresponding to the eight corner points of the polygon. However, it is clear from the figure that, taking into account the direction of the gradient, it is more profitable to go to the neighboring vertex C, then to the neighboring vertex D, which corresponds to the optimal basic solution of the problem. Thus, instead of eight solutions, only three feasible basic solutions will have to be considered.

The idea of ​​sequential improvement of the solution forms the basis of the universal method for solving linear programming problems – simplex method.

Geometric meaning The simplex method consists in performing a sequential transition from one vertex of the polyhedron of feasible solutions to the problem to the neighboring one, in which the objective function takes a value no worse than at the previous vertex. This transition continues until an optimal solution is found or it is discovered that the problem does not have one.

The simplex method and its name were first proposed by the American mathematician John Danzig in 1947, although the ideas of the method were published by the Russian mathematician L.V. Kantorovich back in 1939 in the article “ Mathematical methods organization and production planning."

The simplex method consists of three main elements.