Which solution is considered optimal? Simplex method for solving linear programming problems

Linear programming is a branch of mathematics that studies methods for finding the minimum or maximum of a linear function of a finite number of variables, provided that the variables satisfy a finite number of constraints in the form of linear equations or linear inequalities.

Thus, the general linear programming problem (GLP) can be formulated as follows.

Find values ​​of real variables for which objective function

takes a minimum value on the set of points whose coordinates satisfy system of restrictions

As is known, an ordered collection of values n variables , , … is represented by a point in n-dimensional space. In what follows we will denote this point X=( , , … ).

In matrix form, the linear programming problem can be formulated as follows:

, A– size matrix ,

Dot X=( , , … ), satisfying all conditions, is called valid point . The set of all admissible points is called valid area .

Optimal solution (optimal plan) a linear programming problem is called a solution X=( , , … ), belonging to the admissible region and for which the linear function Q takes the optimal (maximum or minimum) value.

Theorem. The set of all feasible solutions to the system of constraints of a linear programming problem is convex.

The set of points is called convex , if it, together with any two of its points, contains their arbitrary convex linear combination.

Dot X called convex linear combination points if the conditions are met

The set of all feasible solutions to a linear programming problem is a convex polyhedral region, which we will henceforth call polyhedron of solutions .

Theorem. If the ZLP has an optimal solution, then the objective function takes the maximum (minimum) value at one of the vertices of the solution polyhedron. If the objective function takes a maximum (minimum) value at more than one point, then it takes this value at any point that is a convex linear combination of these points.

Among the many solutions of the system m linear equations describing the polyhedron of solutions, the so-called basic solutions are distinguished.

Basic solution of the system m linear equations with n variables is a solution in which all n-m non-core variables are zero. In linear programming problems such solutions are called admissible basic solutions (reference plans).

Theorem. Each admissible basic solution to a linear programming problem corresponds to a vertex of the solution polyhedron, and vice versa, to each vertex of the solution polyhedron there corresponds an admissible basic solution.

An important corollary follows from the above theorems:

If a linear programming problem has an optimal solution, then it coincides with at least one of its feasible basic solutions.

Consequently, the optimum of the linear function of the goal of a linear programming problem must be sought among the finite number of its feasible basic solutions.

The general linear programming problem (GLP) is formulated as follows - find the problem variables x 1 , x 2 , ..., x n , which provide the extremum of the objective function

An admissible solution (plan) of a linear programming problem (LPP) is any n-dimensional vector X=(x 1 , x 2 , ..., x n) satisfying the system of equalities and inequalities. The set of feasible solutions to a problem forms the domain of feasible solutions D.

An optimal solution (plan) of a linear programming problem is a feasible solution such that the objective function Z(X) reaches an extremum.

The canonical linear programming problem (CLP) has the form

(1.2)

It differs from OZLP in that its system of constraints is a system of only equations and all variables are non-negative.

Bringing the OPLP to the canonical form of the OPLP:

To replace the original minimization problem with a maximization problem (or vice versa, a maximization problem with a minimization problem), it is enough to multiply the objective function by “-1” and look for the maximum (minimum) of the resulting function;

If there are inequalities among the restrictions, then by introducing additional non-negative variables x n +1 ≥ 0 they transform into equalities:

inequality a i 1 x 1 +…+a in x n ≥ b i is replaced by equality a i 1 x 1 +…+a in x n+ x n +1 = b i,

inequality a i 1 x 1 +…+a in x n ≤ b i is replaced by equality a i 1 x 1 +…+a in x n+ x n +1 = b i ;

If some variable x k has no sign restrictions, then it is replaced (in the objective function and in all restrictions) by the difference between two new non-negative variables: x k = x" k – x” k , Where x" k ≥ 0. x” k ≥ 0.

Graphical method for solving ZLP with two unknowns

The ZLP with two unknowns has the form:

The method is based on the possibility of graphically depicting the region of feasible solutions and finding the optimal solution among them.

The region of feasible solutions (ADA) of the problem is a convex polygon and is constructed as the intersection (common part) of the solution regions of each of the problem constraint inequalities.

The domain of solution of the inequality a i 1 x 1 +a i 2 x 2 ≤ b i is one of the two half-planes on which the line a i 1 x 1 +a i 2 x 2 = b i corresponding to this inequality divides the coordinate plane. To determine which of the two half-planes is the solution region, it is enough to substitute the coordinates of any point that does not lie on the dividing line into the inequality:

If the inequality is true, then the solution region is the half-plane containing this point;

If the inequality is not true, then the solution domain is a half-plane that does not contain this point.

To find the optimal one among the feasible solutions, level lines are used.

A level line is a straight line With 1 x 1 +With 2 x 2 = l, Where l= const, at which the objective function of the problem takes a constant value. All level lines are parallel to each other.

Objective function gradient grad Z(X) specifies the normal vector C = (c 1 , c 2) level lines. The objective function on the level lines increases if the level lines are moved in the direction of their normal, and decreases in the opposite direction.

The reference line is a level line that has at least one common point with the ODR and in relation to which the ODR is located in one of the half-planes. The ODD of the problem has no more than two support lines.

The optimal solution of the ZLP lies on the reference line at the corner point of the ODR polygon. The ZLP has a unique solution if the reference line passes through one corner point of the ODR, and an infinite number of solutions if the support line passes through the edge of the ODR polygon. The ZLP has no solution if the ODP is an empty set (when the system of constraints is inconsistent) and if the ODP is unbounded in the direction of the extremum (the objective function is unbounded).

Algorithm for the graphical method of solving the ZLP with two unknowns:

Build ODR.

Construct normal vector C = (c 1 , c 2) and level line With 1 x 1 +With 2 x 2 = 0 passing through the origin and perpendicular to the vector WITH.

Move the level line to the reference line in the direction of the vector WITH in a max problem, or in the opposite direction – in a min problem.

If, when the level line moves in the direction of the extremum, the ODR goes to infinity, then the ZLP has no solution due to the unboundedness of the objective function.

If the ZLP has an optimal solution, then to find it, solve jointly the equations of the lines that limit the ODR and have common points with the reference line. If the extremum is reached at two corner points, then the ZLP has an infinite set of solutions belonging to the ODR edge bounded by these corner points. In this case, the coordinates of both corner points are calculated.

Calculate the value of the objective function at the extremum point.

Simplex method for solving the problem of problems

The simplex method is based on the following provisions:

The ODP of a linear programming problem is a convex set with a finite number of corner points;

The optimal solution of the ZLP is one of the corner points of the ODR. The corner points of the ODR algebraically represent some basic (reference) solutions of the system of constraints of the ZLP.

The basic (reference) solution of the ZLP is such an admissible solution X 0 =(x 10 , x 20 , ..., x m 0 , 0,…0), for which the vectors of conditions (columns of coefficients for unknown constraints in the system) are linearly independent.

Non-zero coordinates x 10 , x 20 , ..., x m 0 solutions X 0 are called the basis variables, the remaining solution coordinates X 0 - free variables. The number of non-zero coordinates of the reference solution cannot be greater than the rank r systems of restrictions of the PLP (number of linearly independent equations in the system of restrictions of the PLP). Next, we assume that the system of PLP restrictions consists of linearly independent equations, i.e. r = m.

The meaning of the simplex method is a purposeful transition from one reference solution of the PLP to another (i.e. from one corner point of the ODP to another) in the direction of the extremum and consists of a sequence of stages:

Find the initial support solution;

Make the transition from one reference solution to another;

Determine the criterion for achieving an optimal solution or make a conclusion about the absence of a solution.

Execution algorithmSimplex method ZLP

The simplex method algorithm transitions from one reference solution of the PLP to another in the direction of the extremum of the objective function.

Let the ZLP be given in the canonical form (1.2) and the condition be satisfied

b i ≥ 0, i=1,2,…,m, (1.3)

relation (1.3) can always be fulfilled by multiplying the corresponding equation by “-1” in case of negative b i. We also believe that the system of equations in the constraints of problem (1.2) is linearly independent and has rank r = m. In this case, the vector of the support solution has m non-zero coordinates.

Let the original problem (1.2), (1.3) be reduced to the form where the basic variables x 1 , x 2 , ..., x m are expressed in terms of free variables x m + 1 , x m + 2 , ..., x n

(1.4)

Based on these relationships, we will construct Table 1

Table 1.

Table 1 is called a simplex table. All further transformations are associated with changes in the contents of this table.

Algorithm withcomplex method:

1. In the last line Z Simplex tables in a min problem find the smallest positive element (in a max problem, the smallest negative element), not counting the free term. The column corresponding to this element is called the enabling column.

2. Calculate the ratio of free terms to the positive elements of the resolution column (simplex ratio). Find the smallest of these simplex relations; it corresponds to the resolution string.

3. At the intersection of the resolving row and the resolving column there is a resolving element.

4. If there are several simplex relations of equal size, then choose any of them. The same applies to the positive elements of the last row of the simplex table.

5. After finding the enabling element, move on to the next table. The unknown variables corresponding to the resolution row and column are swapped. In this case, the basic variable becomes a free variable and vice versa. The simplex table is converted as follows (table 2):

table 2

6. Element of table 2, corresponding to the resolving element of table 1, is equal to the reciprocal value of the resolving element.

7. The elements of the row of table 2 corresponding to the elements of the allowing row of table 1 are obtained by dividing the corresponding elements of table 1 by the allowing element.

8. The elements of the column of table 2, corresponding to the elements of the resolving column of table 1, are obtained by dividing the corresponding elements of table 1 by the resolving element and are taken with the opposite sign.

9. The remaining elements are calculated by rectangle rule: We mentally draw a rectangle in Table 1, one vertex of which coincides with the resolving element (Re), and the other with the element we are looking for; Let us denote the element in the new table 2 by (Ne), and the element in the same place in the old table 1 by (Se). The remaining two vertices A and B complete the figure to a rectangle. Then the required element He from Table 2 is equal to He = Se – A*B/Re.

10. Optimality criterion. As soon as a table is obtained in which all elements in the last row in the min problem are negative (in the max problem all elements are positive), it is considered that the extremum has been found. The optimal value of the objective function is equal to the free term in the row Z, and the optimal solution is determined by the free terms of the basis variables. All free variables are set to zero.

11.If all elements in the resolution column are negative, then the problem has no solutions (the minimum is not achieved).

Artificial basis method for solving ZLP

The simplex method algorithm is applicable if any reference solution of the PLP is selected, i.e., the original PLP (1.2) is reduced to the form (1.4). The artificial basis method offers a procedure for constructing such a reference solution.

The artificial basis method is based on the introduction of artificial basis variables y 1 , y 2 ,…, y m , with the help of which the system of restrictions of the PLP (2.2)

(1.5)

can be converted to the form

(1.6)

Systems (1.5) and (1.6) will be equivalent if all y i will be equal to zero. As before, we believe that everything b i ≥ 0. In order to at i were equal to 0, we must transform the problem so that all artificial basis variables y i switched to free variables. Such a transition can be made using the simplex method algorithm with respect to an additional objective function

F(y) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 +d 2 x 2 +…+d n x n). (2.7)

The initial simplex table for this method looks like

First, the simplex table is transformed with respect to the objective function F(y) until a reference solution is obtained. The reference solution is found when the following criterion is met: F(y) = 0 and all artificial variables at i translated into free variables. Then a row is crossed out from the simplex table for F(y) and columns for at i and solve the problem for the original objective function Z(x) until the optimal solution is obtained.

The simplex method is a universal economics and mathematics
mathematical method. To use it, the conditions of the problem must be presented in the form of equations and inequalities that quantitatively describe the features of the functioning of the object being studied.

A significant advantage of the method is its universality, i.e. the ability to be used to solve any problems, the conditions of which are written in the form of a system of equations and inequalities. Along with this, the simplex method has the advantage that when the half-space expressing the objective function approaches the extreme corner point, it allows skipping a whole series of intermediate extreme corner points.

The method got its name from the geometric interpretation of the problem conditions. They make it possible to obtain a polyhedron of solutions or a simplex, the extreme corner point of which, being equal to the values ​​of the variables, turns the function into a maximum or minimum.

There are several variants of the simplex method algorithm: regular, m-method (artificial basis), etc.

Let's consider an option that allows for the most
simple calculations.

The simplex method algorithm includes several stages:

1) preparation of information (includes the introduction of variables
and the formation of restrictions);

2) transforming constraints and recording them in a matrix;

3) search for a reference solution;

4) search for an optimal solution.

For example, we have the following economic and mathematical
task:

The transformation of constraints is associated, first of all, with the transformation of inequalities into equations. If the restrictions are reduced to type , then the calculation procedure is significantly
simplified. For this type constraint, multiply by (-1).

The transformation of inequalities into equations is associated with the introduction
additional variables. In type constraints, additional variables indicate the amount of underutilization
resources, in type restrictions - the amount of excess of resources over the minimum need for them.

Additional variables are not introduced into the equations (or are entered equal to zero):

In this case, any decision is made on the assumption that

We obtain the solution by searching for the reference and optimal solutions.

Reference solution we obtain for the values ​​of the variables when the constraints of the problem are satisfied. A sign of fulfillment of the restrictions is the absence of 0-values ​​among the basic variables and negative free terms.

In this case, the variables, based on the values ​​of which we begin the solution, will be basic.

In the first simplex table (Table 5.1), such basic variables will be additional variables, i.e., a vector of additional variables. The remaining variables denoting column vectors will be non-basic. In Table 5.1, the main variables will be non-basic.

Table 5.1 - Simplex table No. 1

Basic Variables	Free members	Non-basic variables
			…
					…
					…
					…
………………………………………………
					…
					…

If there is a 0 in the column of additional variables, then this indicates a distortion of the basis, i.e., the absence of a reference solution. Thus, the resulting record at indicates that there is no basic solution for two reasons,
namely:

– there are negative free terms;

– there are 0-values ​​among the basic variables.

All information is assumed to be entered into a table. Table 5.1 contains t + 2 lines (where T- number of constraint lines) and P+ 2 columns (where P- number of non-basic variables).

The coefficients of the objective function in Table 5.1 are written
with the opposite sign.

Finding a reference solution involves replacing basic variables with non-basic ones or searching for a new basis. To eliminate 0 from the vector of basic variables, it is necessary to find in the 0-row such a coefficient, from dividing by which the coefficient A t,we obtain the smallest positive quotient. To do this, divide the column vector of free terms by the corresponding column coefficients . Let us assume that when dividing
to the coefficients of the first column, i.e. the ratio . This means that the requirement is not met. In another case (with ) . Let's say that when dividing, the ratio is less than all other values.

Then the coefficient can be taken as resolving.
It indicates that the 0-value and the coefficient will switch places. This replacement means that the objective function (or half-space F) has moved parallel to itself and therefore the value of the coefficients changes. Replacing values ​​requires
calculations that are always carried out according to the same rules.

To write the formulas by which the coefficients of the new simplex table are determined (Table 5.2), we introduce symbols, in particular, the coefficient in the line i
and column j. Wherein F-string will have value i+ 1, and the column of free terms j = 0.

Table 5.2 - Simplex table No. 2

Basic Variables	Free members	Non-basic variables
…………………………………………………………..

Let us assume that the coefficient is resolving, i.e. it costs
in line r and column k at . When dividing the dummy column values ​​by the corresponding column coefficients k the quotient of division by was the smallest.

Let us agree that the coefficient of the following table will be denoted with a prime, i.e. .

Rules:

1. The new coefficient (instead of the resolving coefficient) is equal to its inverse, i.e. or in this case .

2. The new coefficients of the resolution element column are equal to the coefficients of the previous table, divided by the resolution coefficient with the opposite value:

i.e. in this case - at .

3. The new coefficients of the row of the resolving element are equal to the coefficients of the previous table of this row, divided
to the resolution factor:

(at ) or , at .

4. The remaining coefficients that are not in the row and column of the resolving element are determined by the rectangle rule, i.e. in the numerator of the product of the coefficients of the main diagonal, among which the resolving element is found, we subtract the product of the secondary diagonal and divide the result by the resolving coefficient:

Having transferred the 0-values ​​from the basic values ​​to the non-basic ones, we get n-dimensional space T independent vectors. Then we cross out the 0-column, which does not take part in further calculations. Looking through the column of free terms, we find negative terms among them. To obtain a support solution, we transform negative free terms into positive ones. To do this, basic variables with negative free terms must be converted into non-basic ones. In this case, we take as many steps (tables) as there are negative free terms. We take as a basis any string with a negative free term. The best option is the line that has more ones or integers among its coefficients. It happens that all free terms are negative
and they correspond to negative coefficients in some of the columns. In this case, the reference solution can be obtained in one step by taking a negative coefficient as a resolution coefficient, dividing by which the largest positive quotient is obtained. Thus, in one step, all negative free terms will be turned into positive ones.

From the point of view of geometric interpretation (convex sets), this will mean that from the imaginary polyhedron of solutions we have moved to the real polyhedron, but we are
not at the best convex corner point.

To find the resolving coefficient, we divide the values ​​of the column of free terms by the corresponding coefficients of the columns of non-basic variables.

If , then we get a smaller value than from dividing other quotients.

Let us assume that in this case the particular is less than all the others. Therefore, coefficient () is resolved
wandering.

We change places and , after which we carry out calculations
according to the four rules above (Table 5.3).

Table 5.3 - Simplex table No. 3

Basic Variables	Free members	Non-basic variables
………………………………………………..

This table contains the reference solution. It's received
with the following variable values:

After the reference solution has been obtained (i.e., all restrictions are met), we find the optimal one, the sign of which is the presence of positive values ​​of the coefficients of the objective function when solving it to the maximum and negative -
to a minimum.

To find the optimal solution, select the resolution column. It will be the one in F-the line of which contains the largest absolute negative value when solving the problem for the maximum and the largest positive value for the minimum.

Let's assume that . Therefore, the table vector
bets is permissive. In this case, the resolving element is the coefficient from dividing the free term
for which the smallest positive quotient will be obtained, i.e.

Let us assume that from division WITH 3 on With 32 the smallest positive quotient was obtained. Hence, X 2 and X 1 are swapped, and we find a new solution using four rules.

We will continue the calculations until F-line
we will not get positive values ​​(when solving a maximum problem) or negative values ​​(when solving a minimum problem).

Then it is advisable to check the fulfillment of the requirements of each of the restrictions. To do this, variables are substituted into each of the constraints. If there are no violations, then the calculations are correct; if there are any, there is an error in the arithmetic operations.

When using the simplex method, the following four special cases are possible:

1. Degeneracy.

2. Alternative optimal solutions.

3. Unlimited solutions.

4. Lack of feasible solutions.

Let's find out the reasons for the occurrence of such situations and how to interpret them in real problems.

Degeneracy. If at least one basic variable is zero, then the basic solution is called degenerate. Such a situation may well arise in the process of solving a problem. Then it may happen that the transition to a new basis does not improve the value of the functional. As a rule, with subsequent iterations the degeneracy disappears. The fact is that in practice its occurrence is explained by the presence of redundant restrictions in the initial formulation of the problem. In this case, when an artificial variable corresponding to one of these constraints is removed from the basis, the functional may not improve. This situation is shown in Fig. 2.4.

Of the two resource-type constraints, the second is redundant. With a graphical solution (Fig. 2.4), this is obvious, but such a conclusion cannot be drawn from the data in the simplex table. If an additional variable corresponding to the second constraint is excluded from the basis, the value of the functional will not increase. As a result, we get a point A, as an optimal solution that does not cease to be true because it is degenerate.

Rice. 2.4

One can imagine a situation where a sequence of iterations with a degenerate basis will lead to a repetition of an iteration that has already taken place, i.e., a loop will arise. Artificial examples of this kind exist, but in real problems, looping is so unlikely that most programs that implement the simplex method do not provide protection against looping, since they significantly slow down the computation process. Firstly, we need to control the occurrence of looping, and secondly, we need to implement an algorithm to change the order in which the enabling rows and columns are selected.

If such difficulties nevertheless arise during computer calculations, then you can try to make minor changes to individual coefficients of the model (within the limits of the accuracy of their determination) and repeat the calculation. If looping has previously occurred, the order in which the enabling elements are selected will likely change.

Alternative optimal solutions. According to the fundamental theorem of linear programming, if the objective function reaches an extreme value at more than one corner point, then it takes the same value at any point that is a convex linear combination of them. A graphical illustration for the case of two variables is shown in Fig. 2.5. The objective function obtains its maximum value at corner points A And B. Let us assume that using the simplex method a point is obtained A as the optimal plan. Then the non-basic variable will correspond to a zero estimate, since when it is introduced into the basis and then goes to the point B the meaning of the functionality will not change.

Rice. 2.5

Thus, a sign of the existence of alternative plans is the presence of zero estimates for non-basic variables. In practice, the existence of alternative solutions can be used to incorporate additional considerations when choosing a course of action. If the considered example is interpreted as a problem about the optimal production plan, then it is better to choose the point B to be less dependent on changes in market conditions.

If all estimates of non-basic variables are strictly greater than zero, then the optimal plan found is unique.

From a practical point of view, small positive estimates do not differ very significantly from zero, if only because most of the data used are determined with some error. Therefore, there is reason to perform calculations of additional options in order to assess the real effect of introducing such variables into the adopted plan.

Unlimited solutions. An unlimited increase in variables without violating constraints is a clear sign of an error. For example, in a production plan problem, each resource is limited. It is unlikely that such restrictions were missed when recording the model, but when entering them, a sign error is possible. When using computer programs, if you do not specify the requirement for non-negativity of variables, formally giving one of the variables a negative value, the program can receive resources for unlimited growth of other variables.

If the error cannot be quickly detected, then additional restrictions can be introduced, for example, on the minimum and maximum values ​​of variables, setting them with a large tolerance in relation to the actually possible values. The error will be detected when analyzing constraints that involve variables whose values ​​are outside the acceptable limits.

Lack of feasible solutions. This situation arises when the constraints of the problem are incompatible, which can be considered an error in its formulation or in the data used. Figure 2.6 shows the restrictions on the minimum production volumes of each of the two types of products. It can be seen that the third constraint, which determines the maximum allowable use of a certain resource, makes it possible to satisfy either of these requirements, but not both at the same time.

Rice. 2.6

Such contradictions naturally arise in a planned economy with different targets set by the central planning body and production managers. The former, as a rule, strives to increase the volume of planned tasks, while the latter prefers a plan that is easier to fulfill and receive rewards for overfulfillment. When actual data is distorted for this purpose, it may happen that a retrospective calculation of the plan based on the reported data will show that there are no feasible solutions.

A market economy is also not free from such problems. Data may be deliberately distorted, for example, in order to influence the current stock price. In any case, the optimization model becomes an effective means of monitoring and analyzing the entire set of statistical reports.

However, the reason for the lack of valid solutions can be very trivial - an incorrectly placed decimal point, or an erroneous entry of the correct numerical value, but in the wrong cell. The larger the dimension of the problem, the more likely such errors are and the more difficult it is to find them. To identify such errors, it can be recommended to introduce variables into the model that would show how much and what kind of resource is missing. Of course, such variables in the functionality must correspond to some penalties, otherwise the missing resources will be included in the solution, which does not make sense. The values ​​of the penalties are arbitrary, but large enough so that the corresponding variables (we will call them penalties) can enter into the solution only when it is otherwise impossible to satisfy the remaining constraints of the problem. Penalties that are too large will only increase rounding errors. In accordance with the principle of “reasonable sufficiency,” it is possible, for example, to increase the estimated price of a real resource by an order of magnitude.

A universal method for solving LP problems is called the simplex method. Application of this method and its most common modification - the two-phase simplex method.

In the graphical method of solving LP problems, we actually chose from the set of vertices belonging to the boundary of the set of solutions to the system of inequalities the vertex at which the value of the objective function reached a maximum (minimum). In the case of two variables, this method is completely intuitive and allows you to quickly find a solution to the problem.

If a problem has three or more variables, and in real economic problems this is exactly the situation, it is difficult to visualize the solution area of ​​the system of constraints. Such problems are solved using simplex method or by the method of successive improvements. The idea of ​​the method is simple and is as follows.

According to a certain rule, the initial reference plan (some vertex of the constraint area) is found. It checks whether the plan is optimal. If yes, then the problem is solved. If not, then we move on to another improved plan - to another peak. the value of the objective function on this plane (at this vertex) is obviously better than in the previous one. The transition algorithm is carried out using a certain computational step, which is conveniently written in the form of tables called simplex tables . Since there are a finite number of vertices, in a finite number of steps we arrive at the optimal solution.

Let's consider the simplex method using a specific example of the problem of drawing up a plan.

Let us note once again that the simplex method is applicable to solving canonical LP problems reduced to a special form, i.e., having a basis, positive right-hand sides and an objective function expressed in terms of non-basic variables. If the task is not reduced to a special form, then additional steps are needed, which we will talk about later.

Let us consider the problem of a production plan, having previously constructed a model and brought it to a special form.

Task.

For the manufacture of products A And IN The warehouse can release no more than 80 units of raw materials. Moreover, for the manufacture of the product A two units are consumed, and the products IN- one unit of raw materials. It is necessary to plan production so that the greatest profit is ensured if the products A it is required to produce no more than 50 pieces, and products IN- no more than 40 pcs. Moreover, the profit from the sale of one product A- 5 rubles, and from IN- 3 rub.

Let's build a mathematical model, denoting X 1 quantity of products A in plan, for X 2 - number of products IN. then the constraint system will look like this:

x 1 ≤50
x 2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max

Let's bring the problem to canonical form by introducing additional variables:

x 1 +x 3 =50
x 2 +x 4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max
-F = -5x 1 - 3x 2 → min.

This problem has a special form (with a basis, the right-hand sides are non-negative). It can be solved using the simplex method.

Istage. Recording a problem in a simplex table. There is a one-to-one correspondence between the system of constraints of problem (3.10) and the simplex table. There are as many rows in the table as there are equalities in the system of constraints, and there are as many columns as there are free variables. Basic variables fill the first column, free variables fill the top row of the table. The bottom line is called the index line; the coefficients of the variables in the objective function are written in it. In the lower right corner, 0 is initially written if there is no free member in the function; if there is, then write it with the opposite sign. At this place (in the lower right corner) there will be a value of the objective function, which should increase in absolute value when moving from one table to another. So, Table 3.4 corresponds to our system of restrictions, and we can move on to stage II of the solution.

Table 3.4

basic			free

IIstage. Checking the reference plan for optimality.

This table 3.4 corresponds to the following reference plan:

(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).

Free variables X 1 , X 2 equals 0; X 1 = 0, X 2 = 0. And the basic variables X 3 , X 4 , X 5 take values X 3 = 50, X 4 = 40, X 5 = 80 - from the free terms column. Objective function value:

-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.

Our task is to check whether a given reference plan is optimal. To do this, you need to look at the index line - the target function line F.

Various situations are possible.

1. In the index F- there are no negative elements in the string. This means that the plan is optimal, and a solution to the problem can be written down. The objective function has reached its optimal value, equal to the number in the lower right corner, taken with the opposite sign. Let's move on to stage IV.

2. The index row has at least one negative element whose column has no positive elements. Then we conclude that the objective function F→∞ decreases without limit.

3. The index row has a negative element that has at least one positive element in its column. Then we move on to the next stage III. We recalculate the table, improving the reference plan.

IIIstage. Improvement of the reference plan.

From the negative elements of the index F-rows, select the one with the largest modulus, call the corresponding column resolving and mark it with “”.

To select a resolving row, it is necessary to calculate the ratios of the elements of the free terms column only To positive elements of the resolution column. Select the minimal one from the obtained relations. The corresponding element at which the minimum is reached is called resolving. We will highlight it with a square.

In our example, element 2 is permissive. The line corresponding to this element is also called resolving (Table 3.5).

Table 3.5

Having selected the allowing element, we recalculate the table according to the rules:

1. In a new table of the same size as before, the variables of the resolving row and column are swapped, which corresponds to the transition to a new basis. In our example: X 1 is included in the basis, instead X 5, which leaves the basis and is now free (Table 3.6).

Table 3.6

2. In place of the resolving element 2, write its inverse number ½.

3. We divide the elements of the resolution line by the resolution element.

4. We divide the elements of the resolution column by the resolution element and write them with the opposite sign.

5. To fill in the remaining elements of table 3.6, we recalculate using the rectangle rule. Let's say we want to count the element at position 50.

We mentally connect this element with the resolving one, find the product, subtract the product of the elements located on the other diagonal of the resulting rectangle. We divide the difference by the resolving element.

So, . We write 10 in the place where there were 50. Similarly:
, , , .

Table 3.7

We have a new table 3.7, the basic variables are now the variables (x 3,x 4,x 1). The value of the objective function became -200, i.e. decreased. To check this basic solution for optimality, we must go again to stage II. The process is obviously finite; the stopping criterion is points 1 and 2 of stage II.

Let's complete the solution of the problem. To do this, let's check the index line and, seeing a negative element -½ in it, call the corresponding column resolving and, according to stage III, recalculate the table. Having compiled the relations and choosing the minimum = 40 among them, we determined the resolving element 1. Now we carry out the recalculation according to rules 2-5.

Table 3.8

After recalculating the table, we make sure that there are no negative elements in the index row, therefore, the problem is solved, the basic plan is optimal.

IVstage. Writing out the optimal solution.

If the simplex method has stopped according to point 1 of stage II, then the solution to the problem is written out as follows. The basis variables take the values ​​of the dummy terms column accordingly. In our example X 3 = 30, X 2 = 40, X 1 = 20. Free variables are 0, X 5 = 0, X 4 = 0. The objective function takes the value of the last element of the column of free terms with the opposite sign: - F = -220 → F= 220, in our example the function was examined at min, and initially F→ max, so the sign actually changed twice. So, X* = (20, 40, 30, 0, 0), F* = 220. Answer to the problem:

It is necessary to include 20 products of the type in the production plan A, 40 products of type B, while the profit will be maximum and will be equal to 220 rubles.

At the end of this section, we present a flowchart of the simplex method algorithm, which exactly repeats the steps, but perhaps for some readers it will be more convenient to use, since the arrows indicate a clear direction of actions.

The links above the boxes in the flowchart indicate which stage or sub-point the corresponding group of transformations belongs to. the rule for finding the initial reference plan will be formulated in paragraph 3.7.

Example. Solve the following LP problem in canonical form using the simplex method.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → min
x 1 +x 4 =20
x 2 +x 5 =50
x 3 +x 6 =30
x 4 +x 5 +x 6 =60
x i ≥ 0, i = 1,…,6
An LP problem is said to have a canonical form if all restrictions (except for the conditions for non-negativity of variables) have the form of equalities, and all free terms are non-negative. So we have the problem in canonical form.
The idea of ​​the simplex method is as follows. First you need to find some (initial) vertex of the polyhedron of feasible solutions (initial feasible basic solution). Then you need to check this solution for optimality. If it is optimal, then a solution has been found; if not, then go to another vertex of the polyhedron and check again for optimality. Due to the finiteness of the vertices of the polyhedron (a consequence of the finiteness of the constraints of the LP problem), in a finite number of “steps” we will find the required point of minimum or maximum. It should be noted that when moving from one vertex to another, the value of the objective function decreases (in the minimum problem) or increases (in the maximum problem).
Thus, the idea of ​​the simplex method is based on three properties of the LP problem.
Solution. To find the initial feasible basis solution, i.e. to determine the basis variables, system (5.6) must be reduced to a “diagonal” form. Using the Gaussian method (method of sequential elimination of unknowns), we obtain from (5.6):
x 2 +x 1 +x 3 =40
x 4 +x 1 =20
x 5 -x 1 -x 3 =10
x 6 +x 3 =30
Therefore, the basic variables are x 2 , x 4 , x 5 , x 6 , We give them values ​​equal to the free members of the corresponding strings: x 2 =40, x 4 =20, x 5 =10, x 6 =30,. Variables x 1 And x 3 are non-basic: x 1 =0, x 3 =0.
Let's construct the initial feasible basic solution
x 0 = (0.40,0.20,10,30) (5.9)
To check the optimality of the found solution x 0 it is necessary to exclude basic variables from the target function (using system (5.8)) and build a special simplex table.
After eliminating variables, it is convenient to write the objective function in the form:
f(x) = -7x 1 – 14x 3 +880 (5.10)
Now, using (5.8)–(5.10), we compose the initial simplex table:

The zero line contains the coefficients with the opposite sign of the corresponding variables for the objective function. Optimality criterion (for the minimum search problem): admissible basic solution( x 0) is optimal if there is not a single strictly positive number in the zero line (not counting the value of the objective function (880)). This rule also applies to subsequent iterations (tables). The elements of the zeroth row will be called column estimates.
So the initial feasible basis solution (5.9) is suboptimal: 7>0, 14>0 .
The zero column contains the values ​​of the basic variables. They must be non-negative (see equation (5.7)). The coefficients of the variables from system (5.8) are written from the first to fourth lines.
Because x 0 is not optimal, then we need to move to another vertex of the polyhedron of admissible solutions (construct a new d.b.r.). To do this, you need to find the leading element and carry out a certain transformation (simplex transformation).
First, we find the leading element of the table, which stands at the intersection of the leading column (the column with the highest positive score) and the leading row (the row corresponding to the minimum ratio of the elements of the zero column to the corresponding elements (strictly positive) of the leading column).
In Table 1, the leading column is the third column, and the leading row is the fourth row. (min(40/1,30/1)=30/1) are indicated by arrows, and the leading element is indicated by a circle. The leading element indicates that the underlying variable x 6 needs to be replaced with a non-basic one x 3. Then the new basic variables will be x 2 , x 3 , x 4 , x 5 ,, and non-basic - x 1, x 6,. This means the transition to a new vertex of the polyhedron of admissible solutions. To find the coordinate values ​​of a new feasible basis solution x00 you need to build a new simplex table and carry out elementary transformations in it:
A) divide all elements of the leading line by the leading element, thereby turning the leading element into 1 (for ease of calculation);
b) using the leading element (equal to 1), turn all elements of the leading column into zeros (similar to the method of eliminating unknowns);
As a result, the values ​​of new basic variables are obtained in the zero column x 2 , x 3 , x 4 , x 5 ,(see table 2) - basic components of the new vertex x00(non-basic components x 1 =0, x 6 =0,).

As Table 2 shows, the new basic solution x 00 =(0,10,30,20,40,0) suboptimal (the zero line contains a non-negative score of 7). Therefore, with leading element 1 (see Table 2) we build a new simplex table, i.e. construct a new feasible basic solution

Table 3 corresponds to an acceptable basic solution x 000 =(10,0,30,10,50,0) and it is optimal, because there are no positive ratings in the zero line. That's why f(x 000)=390 is the minimum value of the objective function.
Answer: x 000 =(10, 0, 30, 10, 50, 0)- minimum point, f(x 000)=390.

Conventionally standard linear programming problem

You must complete the following tasks in the order listed.

1. Find the optimal plan for the direct problem:
   a) graphical method;
   b) using the simplex method (to construct the initial reference plan, it is recommended to use the artificial basis method).
2. Construct a dual problem.
3. Find the optimal plan for the dual problem from the graphical solution of the straight line, using the conditions of complementary slackness.
4. Find the optimal plan for the dual problem using the first duality theorem, using the final simplex table obtained by solving the direct problem (see section 1b). Check the statement “the values ​​of the objective functions of a pair of dual problems coincide in their optimal solutions.”
5. Solve the dual problem using the simplex method, then, using the final simplex table of the dual problem, find the optimal plan for the direct problem using the first duality theorem. Compare the result with the result that was obtained graphically (see paragraph 1a).
6. Find the optimal integer solution:
   a) graphical method;
   b) Gomori method.
   Compare the values ​​of integer and non-integer solution functions

Questions for self-control

1. How is a simplex table constructed?
2. How is a change in basis reflected in the table?
3. Formulate a stopping criterion for the simplex method.
4. How to organize table recalculation?
5. Which line is convenient to start recalculating the table?

After obtaining the reference solution to the linear programming problem, we proceed to determining the optimal solution. The optimal solution (plan) of a linear programming problem is a solution in which the objective linear function takes extreme (maximum or minimum) values.

The optimality condition when finding the maximum value of the objective function using the simplex method is the absence of negative coefficients in the Z-row of the simplex table, i.e. all free terms (elements of the column under 1) in the simplex table are non-negative, in the Z-row (except for the free term) all coefficients of the variables are also non-negative, then the resulting solution is reference and optimal.

If there is a negative coefficient in the Z-row, then the resulting solution will not be optimal. The simplex method for determining the optimal solution means moving from one vertex of the solution polyhedron to the neighboring one of this polyhedron, in which the value of the objective function Z is greater or not less than at the original vertex.

To implement such a transition, a modified Jordan elimination step is performed. In a simplex table, the enabling (leading) column is assumed to be the variable being entered, and the enabling (leading) row is assumed to be the variable being excluded. The element located at the intersection of the resolving row and the resolving column is called resolving (leading).

If there are several negative coefficients in the Z-row of a simplex table, then we select the largest negative element of this row as the resolving column.

In the resolution column, select all positive coefficients and divide the corresponding free terms by them. From the obtained relations we take the smallest one and consider the corresponding row to be resolving. After the modified Jordan elimination step with the corresponding resolving element, the sign of the Z-row coefficient changes to the opposite. If all the coefficients of this line turn out to be non-negative, then the plan will be optimal and the problem will be solved.

If there are no positive coefficients in the resolution column (the column with a negative Z-row coefficient), then the objective function is not bounded above and there is no optimal solution.

Example 4.3

To sell three types of goods, the enterprise has three types of resources b 1 = 180, b 2 = 50 and b 3= 40 . To sell the first group of goods, one thousand rubles of trade turnover requires resources of the first type in the amount and 11 = 3 units, resources of the second type a 21= 2 units and third and 31 = 2 units. To sell the second and third groups of goods per 1 thousand rubles of turnover, the following is spent accordingly:

a 2 l = 6 units, a l 3 = 4 units, a 22 = 1 unit, a 23 = 2 units, a 32 =3 units, a 33 = 1 unit.

The profit received from the sale of three groups of goods per unit of turnover is: with 1 = 6, with 2 = 5 and with 3 = 5.

Determine the maximum profit of the enterprise.

The mathematical model of the problem has the form:

under inequality restrictions:

(4.21)

and conditions:

Solution

1. Enter dependent variables y i ≥ 0 satisfying the following conditions:

and rewrite restrictions (4.16) and the objective function Z (4.20) in the form:

2. Compose a simplex table. No. 1, including independent variables -x 1 -x 2 ,-x 3, at the top of the table, dependent variables y 1 , y 2 , y 3 and the objective function Z, writing in the left column of the table with the corresponding signs of the coefficients - a ik . We do not include sign restrictions in the table.

The original plan (initial solution) is the reference plan, since when x 1 = x 2 = x 3= 0 (all variables at the top of the table are zero) and dependent variables y 1 = 180, at 2= 50, y y= 40 meet the conditions y i ≥ 0 .

3. Determine the optimal (maximum) solution to the linear programming problem. Finding the enabling element ars. As a resolving column, we select the column containing the largest Z-row coefficient negative in absolute value, equal to “-6”. In table No. 1 is indicated by a vertical arrow. The resolving string is determined from the min condition

This line will be the third (indicated by a horizontal arrow). Therefore a rs = and 31 = 2 .

Let's perform a modified Jordan elimination step with a resolving element a 31 = 2 , marked with a square. We get the table. No. 2 in the form:

Permissive element a 31 = 2 , we replace it with the reciprocal value equal to 1/2. We divide all other elements of the resolution column by “-2”, we get

We divide the remaining elements of the resolution string by 2 and get:

All elements of the table. No. 2 is obtained by calculating using the “rectangle” rule.

We write the calculations of the table elements line by line:

The solution presented in table. No. 2 is not optimal, since the Z-row has a negative coefficient equal to -2. Let's perform a modified Jordan elimination step with a resolving element a 23= 1 (the third column is permissive, and the row is determined from the condition min

and we get table. No. 3 in the form:

Calculations for filling out the table. We carry out No. 3, starting with the resolving row and column, and then determining the elements of the free member column and the Z-row. Since the free terms and coefficients of the Z-row are non-negative, the solution is optimal. The remaining elements of the simplex table need not be calculated.

We write out the solution to the problem from the table. No. 3:

y 3 = x 2 = y 2 = 0, since all variables located at the top of the table are equal to zero. Then the variables located in the left column of the table are equal to the corresponding values ​​of the free terms (elements in the column under “1”), that is

Examination.

Example 4.4

For a given linear objective function

Find the maximum value under linear inequality constraints:

and conditions:

Solution

1. Let us introduce dependent variables that satisfy the conditions y i> 0 , and rewrite the system of restrictions (4.26) and the objective function (4.25) in the form:

2. Compose a simplex table. No. 1, including addicts y j independent variables -x to (4.28) and the objective function Z (4.29). Restrictions on the sign of variables x k We do not include them in the table. We will indicate the table numbers in the upper left corner:

The original (initial) plan is non-supporting, since in the third line y s = -5 (free term, i.e. element of table No. 1 in the column under 1, the value is negative).

3. Determine the reference solution by performing the modified Jordan elimination step with a resolving element a 33 = -1 selected in accordance with the rules stated above, i.e. as a resolving column we take the coefficient in the third row (the free term is -5) under the variable x 3 , and the resolving row will be the one with the smallest positive ratio of the free terms to the corresponding coefficients of the resolving column, i.e.

The solution to the problem presented in Table. No. 2 shows that the plan is reference, but not optimal, since all the coefficients in the Z-row are negative.

4. Determine the optimal solution by performing the modified Jordan elimination step with a resolving element a 21 = 1 . As a resolving column, we take the largest negative coefficient in absolute value - 16, i.e. column under variable x 1 (marked with a vertical arrow), and the resolving one will be a line with a single positive coefficient equal to 1. Therefore, a 21= 1 , and the solution will be presented in table. No. 3:

The solution to the problem presented in Table. No. 3 is optimal, since all Z-row coefficients are positive values. We write out the solutions to the problem from the table. No. 3:

Checking dependent variables and objective function:

Example 4.5

Determine the values ​​of independent variables x k, delivering the maximum value to the objective function

satisfying linear inequality constraints:

And the conditions:

Solution

1. Let's introduce dependent variables y t > 0 and restrictions (4.31) we rewrite in the form:

We exclude from the table. No. 1 free independent variable xv choosing any coefficient in this column (under the variable) as a resolving element x x ), since, according to the rule for choosing a resolving element, when excluding a free variable, there are no restrictions on its choice.

The resolving element is marked with a square, and the corresponding resolving row and column are indicated by arrows. Let's perform a modified Jordan elimination step with a resolving element and 31 = 1 and we get table. No. 2:

(4.33)
Since if the ratios of free terms to the coefficients of the resolving column are equal to zero, we take a coefficient with a positive sign as a resolving element, we obtain Table. No. 4:

The resulting solution is not optimal, since the Z-row has a negative coefficient equal to -8. We accept the column with this coefficient as resolving, and determine the row from the condition:

Since in the relation the coefficient in the denominator is negative, we take the third line with the coefficient equal to 7 as the resolving line. Let us perform the modified Jordan elimination step with and 31 = 7 and table No. 5 will have the form (we calculate the elements of the resolving column, resolving row, column of free terms and Z-row. The remaining elements of table No. 5 need not be calculated).

The plan presented in table. No. 5 is optimal. We write down the solutions to the problem:

We calculate the value of the free variable x 1 based on (4.33):

Calculating the values ​​of dependent variables y ( and the objective function, substituting the found values ​​into (4.30) and (4.31).

Example 4.6

For a given objective function, find the maximum value:

and conditions:

Solution

1. We introduce dependent variables and rewrite the condition of the problem (4.34)-(4.36) in the form:

(4.38)

2. Compose a simplex table. No. 1:

3. Eliminate the free independent variable x 3 by performing a modified Jordan elimination step with a resolving element a 43 = 1 . We get the table. No. 2:

Write out the value of the variable x 3:

and cross out the fourth line in the table. No. 2.

We get the table. No. 3 in the form:

Since in the table. No. 3 in the column of free terms there are two negative elements -5 and -10, then the plan is not supported. We take 1 column as the resolving one, since the third row contains the element with the largest negative absolute value -10 and the coefficient -8 is located in this column, and the resolving row is determined from the condition:

Therefore, we perform the modified Jordan elimination step with the resolving element a 11 =-8 , we get table. No. 4:

The solution presented in table. No. 4 is not a reference, since in the column of free terms there is a negative element equal to -5. By performing a modified Jordan elimination step with a resolving element a 31 = -1 , we get table. No. 5:

The solution obtained in the form of a table. No. 5, is reference, but not optimal, since in the Z-row the coefficient is equal - 15/8 in the first column is negative, but there are no positive coefficients in this column. Therefore, the objective function has no restrictions on the maximum.