The objective function in canonical form has the form. Canonical form of a linear programming problem

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 bringing a linear programming problem to canonical form is as follows:

if in original problem it is necessary to determine 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; x 2 ≥ 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 canonical problem LP. 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. Mathematical model tasks should 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 out 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 - th 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.

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 in that 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 optimality conditions and two options for reaching the next vertex. However, this increases the size basis matrix A [ /, J ], which mainly determine the complexity of one shat. However, in many cases, applying the method to the canonical forms of the problem turns out to be preferable, and in this section we will dwell on variants of the method obtained for particular linear programming problems.

Pages: 1

Linear programming problem of the form ax = b where a is the coefficient matrix, b is the constraint vector.
Example:

In each LP problem, values of variables are sought under the condition that:

these values satisfied some system linear equations or inequalities;
at these values, the objective function would turn to a minimum or maximum.

Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is saved in a Word file.

One of universal methods LP is simplex method, which, however, can be used if the LP problem has a canonical form.

Definition. The LP problem has a canonical form if all system constraints consist only of equations (except for inequalities expressing the non-negativity of variables) and the objective function must be minimized.
An example of such an LP problem in canonical form is Problem 1 – a balanced transport problem with a system of constraints (1) and target function (2).
However, in most economic tasks Most often, the system of constraints initially includes not only equations, but also inequalities.

Statement. Any general LP problem can be reduced to canonical form.
Bringing common task LP to the canonical form is achieved by introducing new (they are called additional) variables.
The system of constraints (3) of this problem consists of four inequalities. By introducing additional variables y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, we can go to the system of restrictions:

These additional variables y i have an absolutely clear economic meaning, namely, they mean the amount of unused work time (machine downtime i-th type).
For example, if machines of the first type worked for all 18 hours, then x + y = 18, therefore, y 1 = 0. But we allow for the possibility of incomplete use of the operating time of the first machine x + y<18. В этом случае y 1 takes on a positive value and can be considered as an unused time limit. For example, knowing the solution to this problem from paragraph 3.3.2, x = 12, y= 6, we can conclude from the system of restrictions (3.9) that y 1 = y 2 = y 3 = 0, and y 4 = 12 – 6 = 6. That is, machines of the first, second, third types use their working time completely. But the fourth machine is only half loaded, 6 hours, and, given the optimal plan, is idle. Perhaps, after such conclusions, the head of the enterprise will want to load it with other work, rent it out for this time, etc.
So, by introducing additional variables, we can reduce any inequality type constraint to an equation.

Let's consider the mixture problem. The system of restrictions has the form:
The inequalities were turned towards “more”, therefore, introducing additional variables y 1, y 2, y 3 ≥ 0, they must be subtracted from the left side in order to equalize it with the right. We obtain a system of restrictions in canonical form:
The variables y i will also make economic sense. If you remember the practical content of the problem, then the variable y 1 will mean the amount of excess substance A in the mixture, y 2 will mean the amount of excess substance IN in the mixture y 3 – surplus WITH in the mixture.
The task of finding the maximum value of the objective function can be reduced to finding the minimum for the function - F due to the obviousness of the statement max F = –min (– F). Look at the picture: if at some point x= x 0 function y= F(x) reaches its maximum, then the function y= –F(x), symmetrical to it relative to the axis OX, at the same point x 0 will reach a minimum, and F max = – (– F min) at x = x 0 .

Conclusion. To represent the LP problem in canonical form it is necessary:

transform the inequalities included in the system of constraints of the problem into equations by introducing additional variables;
if the objective function F→max (maximizes), it is replaced by the function – F→ min (which is minimized).

Canonical form of ZLP- linear programming problem of the form ax = b where a is the coefficient matrix, b is the constraint vector.

Purpose of the service. The online calculator is designed for the transition of a PPP to a KZLP. Bringing the problem to canonical form means that all constraints will have the form of equalities by introducing additional variables.
If a constraint is not imposed on any variable x j, then it is replaced by the difference of additional variables, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is saved in a Word file.

How to reduce a linear programming problem to canonical form

The mathematical model of the ZLP is called basic, if the constraints in it are presented in the form of equations provided that the variables are non-negative.

The mathematical model is called canonical, if its system of constraints is presented in the form of a system of m linearly independent equations (system rank r=m), the system is allocated unit basis, free variables are defined and the objective function is expressed in terms of free variables. In this case, the right-hand sides of the equations are non-negative (b i ≥ 0).

Variables included in one of the equations of the system with a coefficient of one and absent in other equations are called basic unknowns, and all others - free.

The solution to the system is called basic, if the free variables in it are equal to 0, and it has the form:
X bases = (0, 0; b 1 , …, b m), f(X bases) = c 0

Basic solution is the corner point of the set of solutions of the system, i.e. defines the vertex of the model's solution polygon. Among such solutions is the one in which the objective function takes optimal value.

A basic solution is called a reference solution if it is admissible, i.e. all right-hand sides of the system equations (or inequalities) are positive b i ≥ 0.

The compact form of the canonical model is:
AX = b
X ≥ 0
Z = CX(max)

The concept of an admissible solution, a region of admissible solutions, an optimal solution to a linear programming problem.
Definition 1. A vector X that satisfies the system of ZLP constraints, including the non-negativity conditions, if any, is called an admissible solution to the ZLP.
Definition 2. The set of all admissible solutions forms the region of admissible solutions (ADA) of the PLP.
Definition 3. A feasible solution for which the objective function reaches a maximum (or minimum) is called an optimal solution.

Example No. 1. Reduce the following LP problem to canonical form: F(X) = 5x 1 + 3x 2 → max under the restrictions:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
The model is written in standard form. Let us introduce balance non-negative variables x 3 , x 4 , x 5 , x 6 , which we add to the left sides of the inequality constraints. We introduce all additional variables into the objective function with coefficients equal to zero:
In the first inequality of meaning (≤), we introduce the basic variable x 3 . In the 2nd inequality of meaning (≤) we introduce the basic variable x 4 . In the third inequality we introduce the basic variable x 5 . In the 4th inequality - the basic variable x 6. We obtain the canonical form of the model:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Example No. 2. Find two reference solutions of the system
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2