Write the system in canonical form. Linear programming problems (LPP)

Any task linear programming can be reduced to a linear programming problem in canonical form. For this purpose in general case you need to be able to reduce the maximization problem to the minimization problem; move from inequality constraints to equality constraints and replace variables that do not obey the non-negativity condition. Maximizing a certain function is equivalent to minimizing the same function taken with the opposite sign, and vice versa.

The rule for reducing a linear programming problem to canonical form is as follows:

if the original problem requires determining the maximum linear function, then you should change the sign and look for the minimum of this function;
if there are restrictions right part is negative, then this limit should be multiplied by -1;
if there are inequalities among the restrictions, then by introducing additional non-negative variables they are transformed into equalities;
if some variable x j 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 3 = x 3 + - x 3 - , Where x 3 + , x 3 - ≥ 0 .

Example 1. Reducing the linear programming problem to canonical form:

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x2 ≥ 0; x 3 ≥ 0.

Let us introduce leveling variables into each equation of the system of constraints x 4 , x 5 , x 6. The system will be written in the form of equalities, and in the first and third equations of the system of constraints the variables x 4 , x 6 are entered into left side with a "+" sign, and in the second equation the variable x 5 is entered with a "-" sign.

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

The free terms in the canonical form must be positive; to do this, multiply the last two equations by -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

In the canonical form of writing linear programming problems, all variables included in the system of constraints must be negative. Let's assume that x 1 = x 1 " - x 7 , Where x 1 "≥ 0, x 7 ≥ 0 .

Substituting this expression into the system of constraints and the objective function and writing the variables in increasing index order, we obtain a linear programming problem presented in canonical form:

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Optimality condition for the basic plan of the canonical LP problem. Simplex method and its convergence.

The simplex method is universal, since it allows you to solve almost any linear programming problem written in canonical form.

The idea of the simplex method consistent improvement of the plan, is that, starting from some initial reference solution, sequentially directed movement from the reference solutions of the problem to the optimal one.

The value of the objective function does not decrease during this movement for problems to the maximum.

Since the number of support solutions is finite, then after a finite number of steps we obtain the optimal support solution.

A reference solution is a basic non-negative solution.

Simplex method algorithm

1. The mathematical model of the problem must be canonical. If it is non-canonical, then it must be brought to canonical form.

2. Find the initial reference solution and check it for optimality.
To do this, fill out simplex table 1.
We fill in all rows of the table of the 1st step according to the data of the system of restrictions and the objective function.

Possible following cases when solving problems on maximum:

1. If all coefficients last line simplex tables Dj³ 0, then found

solution optimal.

2 If at least one coefficient Dj £ 0, but for the corresponding variable there is not a single positive evaluative relationship, then the solution we stop tasks, since F(X) ® ¥ , i.e. the objective function is not limited in the area of feasible solutions.

If at least one coefficient of the last row is negative, and for the corresponding variable there is at least one positive evaluative attitude, then you need to move to another reference solution.

4. E if there are several negative coefficients in the last row, then to the underlying variable column(BP) introduce that variable, which corresponds to largest in absolute value negative coefficient.

5. If at least one coefficient Dk< 0 ,That k - thy column accept for the presenter.

6. For leading line we accept the one that corresponds minimum ratio of free members bi to positive coefficients leading, k – that one column.

7. The element located at the intersection of the leading rows and column is called leading element.

Filling out simplex table 2 :

· fill the base column with zeros and ones

· rewrite the leading line by dividing it by the leading element

· if the leading row has zeros, then the corresponding columns can be moved to the next simplex table

· we find the remaining coefficients using the “rectangle” rule

We obtain a new reference solution, which we check for optimality:

If all coefficients of the last row Dj³ 0, then the solution found maximum.

If not, then fill out the simplex table of the 8th step and so on.

If the objective function F(X) requires finding minimum value, then the criterion optimality of the problem is non-positive coefficients D j for all j = 1,2,...n.

Convergence of the simplex method. Degeneracy in LP problems. The most important property Any computational algorithm is convergence, i.e. the possibility of obtaining the desired results during its application (with a given accuracy) in a finite number of steps (iterations).

It is easy to see that problems with the convergence of the simplex method can potentially arise at the stage of choosing the value of r (section 2") in the case where the same minimum values relationship

will be achieved for several rows of table T (q) simultaneously. Then at the next iteration, column b(β(q+1)) will contain zero elements.

In the general case, a linear programming problem is written in such a way that the constraints are both equations and inequalities, and the variables can be either non-negative or arbitrarily varying. In the case where all constraints are equations and all variables satisfy the non-negativity condition, the linear programming problem is called canonical. It can be represented in coordinate, vector or matrix notation.

1. The canonical linear programming problem in coordinate notation has the form

In a more compact form this task can be written using the summation sign,

(1.7)

2. The canonical linear programming problem in vector notation has the form

(1.8)

Where ,

3. The canonical linear programming problem in matrix notation has the form

(1.9)

, .

Here A– matrix of coefficients of the system of equations, X– matrix-column problem variables, – matrix-column of the right parts of the system of restrictions.

Linear programming problems are often used, called symmetrical, which in matrix notation have the form

(1.10)

(1.11)

1.4. Bringing common task linear programming
to canonical form

In most methods for solving linear programming problems, it is assumed that the system of constraints consists of equations and natural conditions for the non-negativity of variables. However, when compiling mathematical models economic tasks restrictions are mainly formed into systems of inequalities, so it is necessary to be able to move from a system of inequalities to a system of equations. To this end, we prove the following theorem.

Theorem 1.1. On replacing an inequality with an equation. Every decision inequalities

corresponds to a unique solution to the equation

and inequalities

, (1.14)

and, conversely, each solution to equation (1.13) and inequality (1.14) corresponds to a unique solution to inequality (1.12).

Proof. Let is the solution to inequality (1.12), then . Let us denote the difference between the right and left sides of this inequality by , i.e.

Obviously . Let us substitute into equation (1.13) instead variable values , we get

Thus, satisfies equation (1.13) and inequality (1.14). This means the first part of the theorem has been proven.

Let now satisfy equation (1.13) and inequality (1.14), i.e. we have

AND

Discarding the non-negative value on the left side of the last equality, we obtain

i.e. satisfies inequality (1.12). The theorem has been proven.

If the inequality is , then an additional non-negative variable must be introduced into its left side with a minus sign, i.e.

Non-negative variables introduced into inequality constraints to turn them into equations are called additional variables. Additional variables are introduced into the objective function with zero coefficients and therefore do not affect its value.

In the case when the problem has arbitrarily changing variables, then any such variable is replaced by the difference of two non-negative variables, i.e. , Where And .

Sometimes it becomes necessary to move in a problem from finding the minimum to finding the maximum or vice versa. To do this, it is enough to change the signs of all coefficients of the objective function to the opposite ones, and otherwise leave the problem unchanged. The optimal solutions of the maximum and minimum problems obtained in this way coincide, and the values of the objective functions for the optimal solutions differ only in sign.

Example 1.1. Bring the linear programming problem to canonical form.

Solution. Let's move on to the problem of finding the maximum of the objective function. To do this, we change the signs of the coefficients of the objective function. To transform the second and third inequalities of the system of constraints into equations, we introduce non-negative additional variables (on mathematical model this operation is marked with the letter D). The variable is introduced into the left side of the second inequality with a “+” sign, since the inequality has the form . The variable is introduced into the left side of the third inequality with a “-” sign, since the inequality has the form . Variables are entered into the objective function with a coefficient equal to zero. The variable on which the non-negativity condition is not imposed is replaced by the difference , . We write the problem in canonical form

In some cases, it becomes necessary to reduce the canonical problem to symmetric problem. Let's look at an example.

Example 1.2. Bring a linear programming problem to a symmetric form

Page 1

The canonical form of the problem is characterized by the following three features: 1) a homogeneous system of constraints in the form of a system of equations; 2) homogeneous non-negativity conditions that apply to all variables involved in the problem, and 3) maximization of a linear function. In this problem, all three of these features are violated.

The canonical form of the linear programming problem is convenient because it is easy to find the initial vertex of the feasible region.

Let's consider the canonical form of the linear programming problem and the Jordan-Gauss elimination method.

The canonical form of a linear programming problem is often convenient.

When transforming a system of constraints to the canonical form of a linear programming problem, inequalities (12) and (13) must be replaced by equalities. To do this, additional non-negative variables are introduced.

Prove that pairwise commuting real matrices are simultaneously reduced to the canonical form of Problem 1128 by a similarity transformation using an orthogonal matrix.

Essentially (4) - (5) can be considered as the canonical form of the nonlinear programming problem, since the methods outlined in Chap. Usually in nonlinear programming problems there is no requirement for the variables to be integer.

Types of restrictions and methods for their transformation.

The canonical form of the problem is characterized by the homogeneity of the system of constraints in the form of a system of equations; maximizing the objective function; the condition of non-negativity of all variables involved in the problem.

None additional features the canonical form of problems does not add to the computational scheme under consideration.

Let us first consider the second canonical form of the minimum problem.

The simplex-mete algorithm can be divided into two stages. At the first stage, a basic solution is found by eliminating variables. If it is found, then we have the canonical form of the problem to move to the second stage. The second step is to check whether there is a bounded optimum. If it exists, then admissible basic solutions are determined and from which the optimal one is selected.

If the problem is solved in canonical form, then only part of the operations introduced in the second paragraph is used. Thus, for the canonical minimum problem, only the case of paragraph 3.4.1 is realized, and only the operations of cyclic rearrangement of columns, passing the column through the vertical border zone, correcting structural violations and part of the truncation operation are needed. Symmetrically, when solving the canonical maximum problem, only the case of paragraph 3.4.2 is realized, and operations of cyclic rearrangement of strings, passing a string through the horizontal border zone, correction of structural violations, and another part of the truncation operation are needed. Otherwise nothing additional specifics the canonical form of the task does not add.

The first paragraph of the introduction showed how a general linear programming problem can be reduced to one of the canonical forms. For canonical problems, the description of the sequential improvement method is formally simplified, since there is no need to consider two options for violating the optimality conditions and two options for reaching the next vertex. However, this increases the size of the basis matrix A [ /, J ], which mainly determines the complexity However, in many cases the application of the method to the canonical forms of the problem turns out to be preferable, and in this section we will dwell on the variants of the method obtained for particular linear programming problems.

Pages: 1

An analytical method for solving a linear programming problem is simplex method. To apply it, the LP problems presented in various ways, must be reduced to canonical form. The linear programming problem, written in the form (2.1.1)-(2.1.3), is an expanded form of writing the general linear programming problem (GLP).

We will call the following problem a canonical linear programming problem (CLPT):

under restrictions having the form of equalities,

If for a problem in the form (2.3.1)-(2.3.4) the condition is satisfied t = n, then its solution reduces to solving the system of equations

(2.3.2) . In this case, the problem will have no solutions if the condition
(2.3.3) is not satisfied or the system of equations has no solution.

condition T

1. To go from the maximization problem objective function (2.3.1) to minimization problem enough take all coefficients Cj objective function with reverse signs and solve the resulting problem to the maximum. After finding the maximum, the value of the objective function must be taken with the opposite sign. The optimal solution will remain the same.
2. To go from less than or equal to equality constraint it is necessary with a plus sign:

3. To go from a “greater than or equal to” constraint to equality it is necessary introduce an additional non-negative variable with a minus sign:

In this case, each inequality introduces its own (n +/)-th additional variable.

4. Everything equalities having negative free terms are divided into-1, in order for condition (2.3.4) to be satisfied.
5. If on some variable Xj the non-negativity condition is not imposed, That make a change of variables Xj=x".- X" x"j > 0, x"> 0. In the transformed problem all variables are non-negative.

There is a statement that any ZLP can be reduced to a canonical form.

Example 2.3.1. Let's transform the problem given in Example 2.2.2 into canonical form. The objective function and system of constraints look like this:

Let us introduce an additional variable jc 3 > 0 with a plus sign into the first inequality, and into the second x 4> 0 with a minus sign and in the third x 5> 0 also with a plus sign. As a result, we obtain a system of problem constraints in canonical form:

Given these restrictions, you need to find the maximum value of the function:

Let's consider the economic meaning of additional variables in canonical problem optimal use of resources.

Example 2.3.2. Optimal resource utilization problem (carpet problem)[17 J.

The factory has at its disposal a certain amount of resources of three types: labor (80 man-days), raw materials (480 kg) and equipment (130 machine hours). The factory can produce four types of carpets. Information on the number of units of each resource required to produce one carpet of each type, and on the income received by the enterprise from a unit of each type of product is given in Table. 2.3.1.

It is required to find a production plan at which its total cost will be maximum.

Economic and mathematical model of the problem Variables: x x, x 2, x 3, x 4 - number of carpets of each type. Objective function - is the total cost of production that needs to be maximized:

Resource Limits:

Let us bring the problem to canonical form by introducing additional variables x 5, x 6 And x 7:

It will be shown below that the optimal production plan is the vector X* =(0; 30; 10; 0), the value of the objective function is 150, i.e. To maximize the total cost of production, it is necessary to produce 30 carpets of the second type and 10 carpets of the third type. Let's substitute optimal values vector X in the restrictions of the KZLP:

We obtain that the resources “labor” and “equipment” are fully used, the resource “raw materials” is available in abundance:

In this case x in shows that there are 200 kg of raw materials left.

So the main variables x v x 2, x 3, x l mean the number of carpets of each type, and additional variables x 5, x 6 their 7 - volume of underutilized resources.

Answer. Optimal production plan X* = (0; 30;

10; 0).

Plan, or acceptable solution, KZLP is called a vector X =(jc p X 2 ,..., x n), satisfying conditions (2.3.2)-(2.3.4).

If all components of the basic solution of the system of CLLP constraints are non-negative, then such a solution is called reference solution or reference plan. The number of positive components of the reference plan cannot exceed T.

The reference plan is called non-degenerate, if it contains T positive components, otherwise it is called degenerate.

Optimal plan or optimal solution A plan is called a plan that delivers the largest (smallest) value of the linear function (2.3.1).

The set of all plans of the PAP (if they exist) is convex polyhedron. Each corner (extreme) point of the solution polyhedron corresponds to reference plan(non-negative basic solutions of the KZLP system of equations). Each reference plan is determined by the system T linearly independent vectors contained in a given system of P vectors D, D,..., A p. If there is an optimal plan, then there is a corner point of the decision polyhedron at which the linear function reaches its greatest (smallest) value.

To find the optimal plan, it is enough to examine only the reference plans. The upper limit on the number of reference plans contained in a problem is determined by the number of combinations S t p (see paragraph 1.4).

Example 2.3.3. Get a solution to the problem about optimal use limited resources (solve AP P):

Solution. Let us bring the problem to canonical form by introducing additional variables x 3, x 4 and x 5:

Let's find all the supporting plans of the system of restrictions of this KZLP (l? - 5; /77 - 3); their number does not exceed 10:

Using the Jordan-Gauss method (see paragraph 1.4), we write out all the basic solutions of the system of equations (Table 2.3.2).

Number basis nogo solutions	Basis	Plan

Among ten basic solutions five support:

The indicated reference plans in Fig. 2.3.1 correspond respectively to the following corner points and the values of the CF in them:

Rice. 2.3.1.

According to theory LP optimal solution contained among the reference plans.

Thus, the maximum value equal to 2300 is reached by the objective function at the point IN on the reference plan X 5 = (70; 80; 0; 60; 0).

Answer. Optimal task plan: x ( = 70, x 2 = 80, objective function value f(x v x 2) = 2300.

MP tasks

General ZLP is called <,=,>=)bi (i=1,n) (2) provided xj>

Symmetrical < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Canonical mixed.

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Geometric interpretation of the objective function and constraints of the ZLP. Geometric formulation of the ZLP.

Let the problem f=c1x1+c2x2-max (1) be given

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

The plan of the problem (x1,x2) is a point on the plane. Each inequality with-we 2 representations. is a half-plane. A half-plane is a convex set. Convex is called a set in which the points of the segment connecting (x1 and x2) belonging to this set also belong to the set. C-ma 2 represents the intersection of half-planes. When crossing you can get:

1) convex polygonal closed area.

2) convex open polygonal area

3) single point

4) empty set

5) ray and segment

Geometric interpretation of the objective function: Function 1 is a family of parallel straight lines, which are called level lines (lines of constant value of the objective function). The partial derivatives of the function with respect to x1 and x2 show the rate of increase of the objective function along the coordinates of the axes. Gradient vector shows the direction of the fastest increase in the objective function. For problem 1-3, the gradient vector = (c1;c2) Leaves the point (0,0) and is directed to the point with coordinates (c1;c2). The gradient vector is perpendicular to the level lines. The intersection of half-planes is usually called area of admissible solutions (ADD).

The main theorem of LP. Schematic diagram solution of the ZLP, which follows from this theorem.

If the ZLP has a solution, then the objective function reaches an extreme value at at least one of the extreme points of the plan polyhedron. If the objective function reaches an extreme value at more than one extreme point, then it reaches one and the same value, which is a convex linear combination of them, at any point. At decision of the PPP It is convenient to use a table entry manually.

BP		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
f	boo	bo1 bo2 bon-m

Algorithm of the simplex method.

1. bring the problem model to canonical form;

2. find the initial reference plan;

3. write the problem in simple. table;

5. move to a new reference plan, to a new symp. table. In order to move to a new reference plan, it is enough to replace one basic variable with a free one. The variable included in the basis and the corresponding resolution column are determined by the largest absolute negative element of the f-row. The variable that excludes from the basis and the corresponding resolving line are determined by the smallest simplex ratio, i.e. the relationship of the elements of the unit column to the corresponding element of the resolution column. The simplex ratio is a non-negative quantity. At the intersection of the resolving row and the resolving column there is a resolving element, with respect to which the simplex transformation is performed in the following way. rule: 1. the elements of the allowing string are divided into the allowing element; 2. the elements of the resolving column are divided into the resolving element and change their sign to the opposite; 3. the remaining elements of the table are re-arranged according to the rectangle rule:

bij bis bkj=(bkj*bis-bij*bks)/bi

The second duality theorem.

if one of the dual problems has an optimal plan, then the other is also solvable, i.e. has an optical plan. In this case, the extreme values of the objective functions coincide (j=from 1 to n) Σcjxj*= (i=from 1 to m)Σbiyi* if in the original. problem, the objective function is unlimited on the set of plans, then in dual problem the system of restrictions is inconsistent.

Theorem on the rank of the TK matrix.

The rank of matrix A of the transport problem is one less than the number of equations: r(A)=m+n-1.

39. Algorithm for constructing the initial reference plan of the ZLP.

To find the initial reference plan, we can suggest the following algorithm:

1. write the problem in the form of a Jordan table so that all elements of the column of free terms are non-negative, i.e. the inequality aio>=0 (i=1,m) was satisfied. Those equations in which the free terms are negative are first multiplied by -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	amo	am1…..amn
f=		-c1…. -cn

Transform the table using Jordan elimination steps, replacing the zeros in the left column with the corresponding x. At the same time, at every step permissive can be selected any column containing at least one positive element. The resolving row is determined by the smallest of the ratios of the free terms to the corresponding positive elements of the resolving column. If, in the process of elimination, a 0-row is encountered, all of whose elements are zero, and the free term is non-zero, then the system of constraint equations has no solutions. If we encounter a 0-row in which, apart from the free term, there are no other positive elements, then the set of restrictive equations does not have non-negative solutions. If the set of restrictive equations joint, then after a certain number of steps all the zeros in the left column will be replaced by x and thereby obtaining a certain basis, and, consequently, a corresponding reference plan.

40. Algorithm for constructing the optimal reference plan of the ZLP.

Ho's initial support plan is examined for optimality.

If there are no negative elements in the f-row (not counting the free term), the -plan is optimal. If there are also no zero elements in the f-row, then there is only one optimal plan; if among the elements there is at least one zero, then there is an infinite number of optimal plans. If there is at least one negative element in the f-row, and there are no positive elements in the corresponding column, then the objective function is not limited in the feasible region. The problem is not solvable. If there is at least one negative element in the f-row, and in each column with such an element there is at least one positive element, then you can move to a new reference plan that is closer to the optimal one. To do this, the column with a negative element in the f-row is taken as permissive; They determine the resolving string from the minimum simplex relation and perform the Jordan elimination step. The resulting reference plan is again examined for optimality. This is repeated until the optimal reference plan is found or the unsolvability of the problem is established.

Algorithm of the Gomori method.

1. Using the simplex method, the optimal plan for the problem is found. If all components of an optimal plan are integers, then it is optimal. Otherwise, go to step 2

2. Among the non-integer components, you should choose the one with fraction is the largest and, using the corresponding row of the simplex table, formulate the correct cutoff using the formula

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Convert the formulated inequality into an equivalent zero equality and include it in a simplex table with a non-integer optimal plan

4. The resulting extended problem is solved using the simplex method. If the resulting plan is not integer, proceed to step 2.

If during the solution process a line appears with a non-integer free term and other integer coefficients, then the corresponding equation does not have a solution in integers. In this case, and original problem undecidable in integers. Gomori's method has limited application. With its help, it is advisable to solve small problems, because... the number of interactions can be very large.

Various forms of notation of ZLP (general, canonical, symmetric)

MP tasks: determination of the optimal plan, determination of the optimal volume of output, determination of the optimal combination of crops, formation of the optimal package of assets, maximizing bank profits, etc.

General ZLP is called maximization (minimization) problem linear function f=Σcj*xj-max(min) (1) under linear restrictions ∑aij *xj(=<,=,>=)bi (i=1,n) (2) provided xj>=0(j=1,n1), xj-arbitrary (j=n1+1,n)(3) where cj,aij, bi-constants numbers.

Symmetrical The form of writing the ZLP is called the problem of maximizing function (1) under linear constraints in signed inequalities< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >or = and non-negative variables. Canonical the form for recording the PAP is called a task maximum function(1) under linear constraints of equalities and non-negative variables. Any other form is called mixed.

min f(x) = -max(-f(x))

The transformation of an inequality into an equation and vice versa is carried out on the basis of the Lemma: for every solution x1...xn of the inequality a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) and vice versa. Every solution x1…xn,xn+1 of equation 6 and inequality 7 corresponds to a solution x1…xn of inequality 5.

To move from the back sim form to the back canonical form, you must enter balance (equalizing) variables. This is based on the inequality theorem: any inequality can be represented as an equation or a simple inequality.