Simplex method for solving linear programming problems. An example of solving a direct and dual problem using the simplex method

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

(2)

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

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

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

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

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

The algorithm for solving the problem is as follows:

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

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

Table 1.

x n

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

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

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

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

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

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

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

The rest of the formulas can be easily written using .

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

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

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

Rice. 1. Rectangle rule

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

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

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

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

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

Example 1. Solve the problem

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

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

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

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

Rice. 2. Graphic solution tasks

To simplify the solution process, the initial data of the problem linear programming When solving it using the simplex method, they are written into special simplex tables. Therefore, one of the modifications of the simplex method is called tabular simplex method. Linear programming problem in canonical form:

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1

The source table for the task has next view:

	x 1	x 2	...	xn-1	x n	b
F	-a 0.1	-a 0.2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1.1	a 1.2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2.1	a 2.2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

x 1 , x 2 , x n - initial variables, x n+1 , x n+2 , x n+m - additional variables. We took all additional variables as basic, and the original variables as non-basic(additional ones are written in the first column of the simplex table and the original ones in the first row). At each iteration, the elements of the simplex table are recalculated according to certain .

Algorithm of the simplex method.

Preparatory stage

We reduce the LP problem to canonical form

F=a 0.1 x 1 +a 0.2 x 2 +...a 0.n x n +b 0 → max

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1

a 2.1 x 1 +a 2.2 x 2 +...a 2.n x n +x n+2 =b 2

.......................................

a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m

If in the original problem it is necessary to find the minimum - the signs of the coefficients objective function F are reversed a 0,n = -a 0,n . The signs of the coefficients of limiting conditions with the sign “≥” also change to the opposite. If the condition contains the sign “≤”, the coefficients will be written without changes.

Step 0. Create a simplex table corresponding to the original problem

	x 1	x 2	...	xn-1	x n	b
F	-a 0.1	-a 0.2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1.1	a 1.2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2.1	a 2.2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

Step 1. Validation check.

We check the elements of column b (free terms) for positivity; if there are no negative ones among them, then an admissible solution is found (a solution corresponding to one of the vertices of the polyhedron of conditions) and we move on to step 2. If there are negative elements in the column of free terms, then we select among them the maximum in modulus - it specifies the leading row k. In this line we also find the maximum absolute negative element a k,l - it specifies the leading column - l and is leading element. The variable corresponding to the leading row is excluded from the basis, the variable corresponding to the leading column is included in the basis. We recalculate the simplex table according to .

If among the free terms there are negative elements - but in the corresponding line - there are none, then the conditions of the problem are inconsistent and it has no solutions.

If after recalculation there are negative elements left in the column of free terms, then we proceed to the first step; if there are none, then to the second.

Step 2. Check for optimality.

At the previous stage, a feasible solution was found. Let's check it for optimality. If among the elements of the simplex table located in row F (not taking into account the element b 0 - the current value of the objective function) there are no negative ones, then the optimal solution has been found.

If string F contains negative elements, then the solution requires improvement. Among the negative elements of the string F, we choose the one with the maximum absolute value (excluding the value of the function b 0)

a 0,l =min(a 0,i )

l - the column in which it is located will be the leading one. In order to find the leading row, we find the ratio of the corresponding free term and the element from the leading column, provided that they are non-negative.

b k /a k,l =min (b i /a i,l ) for a i,l >0, b i >0

k - the row for which this relation is minimal - the leading one. Element a k,l is the leading (permissive) element. The variable corresponding to the leading row (x k) is excluded from the basis, the variable corresponding to the leading column (x l) is included in the basis.

We recalculate the simplex table by . If in new table after recalculation, there are negative elements left in line F, go to step 2

If it is impossible to find the leading row because there are no positive elements in the leading column, then the function in the region of feasible solutions to the problem is not limited - the algorithm terminates.

If all elements in row F and the column of free terms are positive, then the optimal solution has been found.

Simplex table transformation rules.

When creating a new simplex table, the following changes occur:

Instead of the basic variable x k we write x l ; instead of the non-basic variable x l we write x k.
the leading element is replaced by the inverse value a k,l "= 1/a k,l
all elements of the leading column (except a k,l) are multiplied by -1/a k,l
all elements of the leading line (except a k,l) are multiplied by 1/a k,l
the remaining elements of the simplex table are transformed according to the formula a i,j "= a i,j - a i,l x a k,j / a k,l

The transformation scheme for elements of a simplex table (except for the leading row and leading column) is called a “rectangle” scheme.

Converted element a i,j and the three factors corresponding to it are precisely the vertices of the “rectangle”.

Our simplex table is an extended constraint system matrix with some additional columns and rows. Let's consider an example of a simplex table for the following problem:

Find variable values x 1 ...x 5, for which the function:

Q =

x 1

x 2

accepts maximum value, subject to the following restrictions:

x 1

x 2

x 3

(1)

x 1

x 2

x 4

(2)

x 2

x 5

(3)

x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

The simplex table looks like this:

x 1

x 2

x 3

x 4

x 5

Solution

Attitude

x 3

x 4

x 5

-1

-2

The most top line- purely informational, it indicates the purpose of the columns. The "BP" column is also informational; each cell of this column contains the name of a variable that is in the corresponding equation of the system of constraints. In our example, in first equation, variable X 3, in the second X 4, in the third X 5.

Columns X 1...X 5 contain coefficients for the corresponding variables in the equations of the system of constraints (each equation has a separate line). The "Solution" column initially contains the free terms of the corresponding equations. They also show the values for the current solution, displayed by the simplex table, at a certain step (iteration) of solving the problem.

The coefficients of the objective function are reflected in the simplex table in the “Q” row; the free term, as in the case of equations of the system of constraints, is initially written in the “Solution” column. It is also the value of the objective function, but written with the opposite sign (this is convenient for the simplex method). In our example, the simplex table shown corresponds to a certain solution in which the variables X 3, X 4, X 5 are equal to 64, 70, 18, respectively (see the “Solution” column), and the remaining variables are equal to zero. The value of the objective function "Q" is equal to two (which is easy to check by substituting the values of the variables into the expression for the objective function).

In our example, the free term is equal to -2 (minus two) because in the recording of the objective function it is written together with the variables on one side of the equal sign, and the free terms in the equations of the system of constraints on the other. Therefore, before writing it into the table, it must be moved to the right of the equal sign.

Line "Q" in in this example allocated yellow, this means that it will be used to make a decision regarding the choice of a resolution column (sometimes called a guide column). The resolving column corresponds to a variable that will be entered into the basis (into the list) at the next iteration of solving the problem. The purpose of such a replacement of the basis is to improve the value of the objective function. The criterion for selecting a resolving column is the maximum positive coefficient in the “Q” row when solving a maximum problem, or the minimum negative coefficient when solving a minimum problem. If after the next iteration there are no positive (during maximization) or negative (during minimization) coefficients in the line, then the optimal solution has been achieved. In our example, the resolving column is selected by coefficient 7 (maximum positive since the problem is for the maximum), it corresponds to the variable X 2, it is this that will be entered into the basis at the next iteration. The numbers in the guide column are colored red.

The resolving (guiding) line is also colored red; it corresponds to a variable that will be removed from the basis (list) at the next iteration. To determine it, the "Ratio" column is calculated and filled in. Its elements represent the relationships of the elements of the "Solution" column to the corresponding elements of the guide column (except for the "Q" row). The resolution line is selected according to minimum value from all relationships. The important thing is that these ratios are calculated only for positive elements of the guide column. If at some iteration there are no positive coefficients in the guide column, then the objective function original problem unlimited, the problem has no solution.
In our example, the guide line is selected according to the minimum ratio of 16, it corresponds to X 3, and it is this line that will be removed from the basis at the next iteration (its place will be taken by X 2).

We form the next part of the simplex table. Instead of variable x6, plan 1 will include variable x2.

The row corresponding to variable x2 in plan 1 is obtained by dividing all elements of row x6 of plan 0 by the resolving element RE=1. In place of the resolving element in plan 1 we get 1. In the remaining cells of column x2 of plan 1 we write zeros.

Thus, in the new plan 1, row x2 and column x2 are filled. All other elements of the new plan 1, including the elements of the index row, are determined by the rectangle rule. To do this, we select four numbers from the old plan, which are located at the vertices of the rectangle and always include the resolving element

RE. NE = SE - (A*B)/RE

STE - element of the old plan, RE - resolving element (1), A and B - elements of the old plan, forming a rectangle with the elements STE and RE.

Let's present the calculation of each element in the form of a table:





(0)-(2 * (-2+2M)):1	(-1-M)-(-2 * (-2+2M)):1	(-2+2M)-(1 * (-2+2M)):1	(-M)-(-1 * (-2+2M)):1	(-M)-(0 * (-2+2M)):1	(0)-(0 * (-2+2M)):1	(0)-(1 * (-2+2M)):1	(0)-(0 * (-2+2M)):1

We get a new simplex table

Iteration No. 1.

1. Checking the optimality criterion. The current reference plan is not optimal because there are positive coefficients in the index row.
2. Definition of a new basic variable. We will choose the column corresponding to the variable x1 as the leading one, since this is the largest coefficient.
3. Definition of a new free variable. Let's calculate the values of Di in rows as the quotient of division: bi / ai1 and choose the smallest of them:

min (-, 1: 3, -) = 1/3

Therefore, the 2nd line is the leading one.

The resolving element is equal to (3) and is located at the intersection of the leading column and leading row

We form the next part of the simplex table.

Instead of variable x7, plan 2 will include variable x1. The line corresponding to variable x1 in plan 2 is obtained by dividing all elements of line x7 of plan 1 by the resolving element RE=3

In place of the resolving element in plan 2 we get 1. In the remaining cells of column x1 of plan 2 we write zeros.

Thus, in the new plan 2, row x1 and column x1 are filled. All other elements of the new plan 2, including the elements of the index row, are determined by the rectangle rule.

Let's present the calculation of each element in the form of a table





(0)-(1 * (-5+3M)):3	(-5+3M)-(3 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(-2+M)-(1 * (-5+3M)):3	(-M)-(-1 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(2-2M)-(-1 * (-5+3M)):3	(0)-(1 * (-5+3M)):3

We get a new simplex table:

3.1.
3.2.
3.3.
3.4.
3.5.
3.6. Example(1) of solving the LP problem using the simplex table method
3.7. Example(2) of solving the LP problem using the simplex table method

The idea of the simplex table method is to purposefully enumerate the vertices of a simplex. To start the search, you need to select a reference vertex from which to start the search. The simplex method for solving a linear programming problem is based on the transition from one reference plan to another (by enumerating the simplex of the vertices) during which the value of the objective function increases (decreases). The specified transition is possible if some initial reference plan is known. To draw up such a plan, it is necessary to perform a vector analysis, on the basis of which to determine the reference vertex from which the search will begin.The system of inequalities is reduced to canonical form:

x 1 + a 1,m+1* x m+1 + ... + a 1s* x s +...+ a 1n * x n = b 1 ;

x 2 + a 2,m +1* x m+1 + ... + a 2s * x s +...+ a 2n* x n = b 2 ;

x m + a m,m+1* x m+1 + ... + a ms* x s +...+ a mn* x n = b m.

Variables x 1, x 2,...,x m, included with unit coefficients in only one equation of the system and with zero coefficients in the rest, are called basic. In the canonical system, each equation corresponds to exactly one basic variable. Rest n-m variables(x m+1 , ...,x n) are called non-basic variables.

3.1. Bringing a mathematical model to canonical form

Let's give mathematical model problems to canonical form.To do this, let’s get rid of the inequality signs by introducing additional variables and replacing the inequality sign with an equal sign. An additional variable is added for each inequality exclusively, and this variable is specified in the objective function with a coefficient of zero. Rule for entering additional variables: with ">=" - the variable is entered into the inequality with a coefficient of +1; at "<=" - с коэффициентом (-1).

Moreover, sometimes, when there is no basic variable in the equation, in order to make a negative additional variable a basic one, you can multiply the entire equation by (-1).

You can also reorient the objective function from minimum to maximum or vice versa by multiplying all coefficients of the variables in this function by (-1).

3.2. Vector analysis

In vector analysis, vectors are constructed for each variable: the component coordinates of the n-dimensional (n-number of equations of the system) vector will be the coefficients of this variable in the corresponding equations.

As mentioned above, a vector in which there is a unit coefficient in only one equation and zero coefficients in others is called basic. In the canonical system, each equation corresponds to exactly one basic variable. After checking all the restrictions, the system is obtained in canonical form and it becomes possible to fill out the initial simplex table.

3.3. Artificial Variables Method

It often happens that there are fewer basis vectors than the number of equations, i.e. several equations do not contain basic variables. In this case, use the artificial variable method to add basic variables.

Since the introduced variables are not related to the essence of the LP problem in the original formulation, it is necessary to ensure that the artificial variables vanish. This can be done using the two-step simplex method.

Stage 1. An artificial objective function is considered, equal to the sum of artificial variables, which is minimized using the simplex method. In other words, artificial variables are excluded. If the minimum value of the auxiliary problem is zero, then all artificial variables vanish and an admissible basic solution to the initial problem is obtained. Next, stage 2 is implemented. If the minimum value of the auxiliary problem is positive, then at least one of the artificial variables is also positive, which indicates the inconsistency of the initial problem, and the calculations stop.

Stage 2. The feasible basic solution found at the first stage is improved in accordance with the objective function of the original LP problem based on the simplex method, i.e. the optimal table of stage 1 turns into the initial table of stage 2 and the objective function changes.

3.4. Construction of a simplex table

Choose initial feasible basis solution. Basic solution is a solution obtained for zero values of non-basic variables, i.e. x i =0, i=m+1,...,n. The basic solution is called admissible basic solution, if the values of the basic variables included in it are non-negative, i.e. x j = b j>=0, j=1,2,...,m. In this case, the objective function will take the following form: S = c b* x b = c 1* b 1+ c 2* b 2 +...+c m* b m . We fill in the initial table of the simplex method:

Table 2.3

c b x b c 1 c 2 ... c m c m+1 ... c n b i
basis x 1 x 2 ... x m x m+1 ... x n
from 1 x 1 1 0 ... 0 a 1,m+1 ... a n b 1
from 2 x 2 0 1 ... 0 a 2,m+1 ... a 2 n b 2
... ... ... ... ... ... ... ... ... ...
c m x m 0 0 ... 1 a m,m+1 ... a m n b m
S

3.5. Simplex table analysis

Calculate the vector of relative estimates c using the dot product rule

c j = c j - c b* S j,

Where

With b - vector of estimates of basic variables;

S j - j-th column in the canonical system corresponding to the basis under consideration.

We supplement the original table c - line.

Table 2.4

basis x 1 x 2 ... x m x m+1 ... x n with 1 x 1 1 0 ... 0 a 1,m+1 ... a 1 n b 1with 2 x 2 0 1 ... 0 a 2,m+1 ... a 2 n b 2... ... ... ... ... ... ... ... ... ... c m x m 0 0 ... 1 a m,m+1 ... a m n b m 0 0 ... 0 ... W

c b	x b	c 1	c 2	...	c m	c m+1	...	c n	b i

c- line

3. If all estimates c j <=0 (c j >= 0), i=1,...,n, then the current feasible solution is the maximum (minimum). The solution has been found.

4. Otherwise, it is necessary to introduce a non-basic variable x r with the largest value into the basis c j instead of one of the basic variables (Table 2.5).

Using the rule minimum ratio min( b i/ a ir) we define the variable x p derived from the basis. If the coefficient a ir is negative, then b i/ a ir =infinity. As a result, the intersection of the column where the input non-basic variable x r is located and the line where the output basic variable x p is located will determine the position of the leading element of the table (Table 2.6).

Table 2.5

		c m+1			b i
	basis	x m+1
from 1		a 1,m+1	a 1 r	a 1 n
from 2		a 2,m+1	a 2 r	a 2 n

		a m,m+1	a m r	a m n	b m
c- line

Table 2.6

c m+1

b i

b i /

a ir

x m+1

from 1

a 1,m+1

a 1 r

a 1 n

b 1/ a 1r

from 2

a 2,m+1

a 2 r

a 2 n

b 2 / a 2r

with p

a p,m+1

apr

apn

b p / a pr

a m,m+1

a m r

a m n

b m

b m / a nr

c- line

6. We apply elementary transformations to obtain a new feasible base solution and a new table. As a result, the leading element should be equal to 1, and the remaining elements of the leading element column should take the value zero.

We calculate new relative scores using the scalar transformation rule and move on to step 4.