Linear models for business decision making. Linear programming models in solving problems of transport process control General view of a linear programming model

Lecture 2

IN canonical form

acceptable decision of the PPP(valid plan).

optimal solution for the ZLP.

Necessity

Example.

Let's write the problem in canonical form

Special situations of the graphical solution of the ZLP

Except when the task has the only thing optimal solution for and , maybe special situations:

1. the task has an infinite number of optimal solutions – the extremum of the function is achieved on the segment ( alternative optimum)– Figure 2;

2. task not solvable due to the unlimited nature of the ODR, or – Figure 3;

3. ODR - single point Ah, then ;

4. task not solvable , if ODR is an empty area.

A

Figure 2 Figure 3

If the level line is parallel to the side of the region of feasible solutions, then the extremum is reached at all points on the side. The problem has countless optimal solutions - alternative optimum . The optimal solution is found by the formula

where is the parameter. For any value from 0 to 1, you can get all points of the segment, for each of which the function takes the same value. Hence the name - alternative optimum.

Example. Solve the problem graphically linear programming (alternative optimum):

Questions for self-control

1. Write down the linear programming problem in general form.

2. Write the linear programming problem in canonical and standard forms.

3. What transformations can be used to move from the general or standard form of a linear programming problem to the canonical one?

4. Define admissible and optimal solutions to a linear programming problem.

5. Which of the solutions is the “best” for the problem of minimizing the function if ?

6. Which of the solutions is the “best” for the problem of maximizing the function if ?

7. Write down the standard form of a mathematical model for a linear programming problem with two variables.

8. How to construct a half-plane defined by a linear inequality in two variables ?

9. What is called the solution to a system of linear inequalities in two variables? Construct on the plane a region of admissible solutions of such a system of linear inequalities that:

1) has a unique solution;

2) has an infinite number of solutions;

3) has no solution.

10. Write for a linear function vector gradient, name the type of level lines. How are the gradient and level lines located relative to each other?

11. Formulate an algorithm for a graphical method for solving a standard ZLP with two variables.

12. How to find the coordinates of the solution and the values ​​of , ?

13. Construct the region of feasible solutions, gradient and level lines, for linear programming problems in which:

1) is achieved at a single point, a - on the ODR segment;

2) is achieved at a single point of the ODR, and .

14. Give a geometric illustration of the ZLP if it:

1) has unique optimal solutions for and ;

2) has many optimal solutions for .

Lecture 2

graphical method for finding the optimal solution

1. Forms of linear mathematical models and their transformation

2. Graphical method for solving a linear programming problem

3. Special situations of the graphical solution of the ZLP

4. Graphical solution of economic linear programming problems

Forms of linear mathematical models and their transformation

The mathematical model of a linear programming problem (LPP) can be written in one of three forms.

IN general form of the mathematical model you need to find the maximum or minimum of the objective function; the system of constraints contains inequalities and equations; not all variables can be non-negative.

IN canonical form the mathematical model needs to find the maximum of the objective function; the system of constraints consists only of equations; all variables are non-negative.

In the standard form of a mathematical model, you need to find the maximum or minimum of a function; all constraints are inequalities; all variables are non-negative.

A solution to a system of constraints that satisfies the conditions of non-negativity of variables is called acceptable decision of the PPP(valid plan).

The set of feasible solutions is called area of ​​admissible solutions of the PLP.

An admissible solution at which the objective function reaches an extreme value is called optimal solution for the ZLP.

The three forms of recording the ZLP are equivalent in the sense that each of them can be reduced to another form using mathematical transformations.

Necessity transition from one form of mathematical model to another associated with problem solving methods: e.g. simplex method, widely used in linear programming, is applied to a problem written in canonical form, and the graphical method is applied to a standard form of a mathematical model.

Transition to the canonical form of recording ZLP.

Example.

Let's write the problem in canonical form, introducing into the left side of the first inequality of the system of restrictions an additional (balance) variable with a “+” sign, and into the left side of the second inequality an additional variable with a “minus” sign.

The economic meaning of various additional variables may not be the same: it depends on the economic meaning of the restrictions in which these variables are included.

So, in the problem of using raw materials they show the balance of raw materials, and in the problem of choosing optimal technologies– unused operating time of the enterprise using a certain technology; in a cutting problem – production of blanks of a given length in excess of the plan, etc.

T10. Statement of the linear programming problem

Mathematical model An economic problem is a set of mathematical relationships that describe the economic process.

To compile a mathematical model you need:

1. select task variables;

2. create a system of restrictions;

3. set the objective function.

Task variables are called the quantities x 1, x 2,..., x n, which completely characterize the economic process. They are usually written as a vector X = (x 1, x 2,…, x n).

Problem constraint system is a set of equations and inequalities that are satisfied by the variables of the problem and which follow from the limited resources and other economic conditions, for example, the positivity of the variables. In general, they look like:

The objective function is called function F(X) = f(x 1, x 2,..., x n) of task variables, which characterizes the quality of the task and the extremum of which needs to be found.

General task mathematical programming is formulated as follows: find the task variables x 1, x 2,..., x n, which provide the extremum of the objective function

F(X) = f(x 1, x 2,…, x n) ® max (min) (2)

and satisfy the system of restrictions (1).

If the objective function (2) and the system of constraints (1) are linear, then the mathematical programming problem is called linear programming problem (LPP).

Vector X (set of problem variables) is called acceptable solution, or the ZLP plan if it satisfies the system of restrictions (1). An admissible plan X that provides an extremum of the objective function is called optimal solution ZLP.

2. Examples of drawing up mathematical models of economic problems

The study of specific production situations leads to ZLP, which are interpreted as problems about the optimal use of limited resources.

1.Optimal production plan problem

To produce two types of products T 1 and T 2, three types of resources S 1, S 2, S 3 are used. Resource reserves, the number of resource units spent on producing a unit of product, as well as profit from the sale of a unit of product are shown in the table:

It is required to find a production plan that will maximize the profit from its sale.

Solution.

Let us denote x 1, x 2 – the number of units of production, respectively T 1 and T 2, planned for production. To produce them, you will need (x 1 + x 2) units of resource S 1, (x 1 + 4x 2) units of resource S 2, (x 1) units of resource S 3. Consumption of resources S 1 , S 2 , S 3 should not exceed their reserves, respectively 8, 20 and 5 units.

Then the economic and mathematical model of the problem can be formulated as follows:

Find the production plan X = (x 1, x 2) that satisfies the system of constraints:

and condition,

at which the function takes the maximum value.

The problem can be easily generalized to the case of producing n types of products using m types of resources.

2.Optimal diet problem

There are two types of food, K 1 and K 2, containing nutrients S 1, S 2 and S 3. The content of the number of nutrient units in 1 kg of each type of feed, the required minimum of nutrients, as well as the cost of 1 kg of feed are shown in the table:

It is necessary to create a daily diet that has a minimum cost, in which the content of each type of nutrient would not be less than the established limit.

Solution.

Let us denote x 1, x 2 – the amount of feed K 1 and K 2 included in the daily diet. Then this diet will include (3x 1 + x 2) units of nutrient S 1, (x 1 + 2x 2) units of nutrient S 2, (x 1 + 6x 2) units of nutrient S 3. Since the content of nutrients S1, S2 and S3 in the diet should be 9, 8 and 12 units, respectively, the economic and mathematical model of the problem can be formulated as follows:

Create a daily ration X = (x 1, x 2) that satisfies the system of restrictions:

and condition,

at which the function accepts minimum value.

PAP recording forms

In the ZLP it is required to find the extremum of the linear objective function:

with restrictions:

and the condition of non-negativity

where a ij, b i, c j ( , ) are given constant values.

This is how the ZLP is written in general form. If the system of restrictions contains only inequalities, then the LLP is presented in standard form. Canonical (main) The ZLP notation form is a notation when the system of constraints contains only equalities. So the above ZLPs are written in standard form.

The general, standard and canonical forms of the ZLP are equivalent in the sense that each of them can be rewritten in a different form with the help of simple transformations. This means that if there is a way to solve one of the specified problems, then the optimal plan for any of the problems can be determined.

In order to move from one form of recording the PLP to another, one must be able to move from inequality constraints to equality constraints and vice versa.

The inequality constraint (£) can be converted to an equality constraint by adding an additional non-negative variable to its left side, and the inequality constraint (³) can be converted to an equality constraint by subtracting an additional non-negative variable from its left side. The number of introduced additional non-negative variables is equal to the number of transformed inequality constraints.

Input additional variables make some economic sense. Thus, if the limitations of the original PPP reflect the consumption and availability of resources, then the value of the additional PPP variable in canonical form is equal to the volume of the unused corresponding resource.

Example 1. Write in the canonical form of the ZLP:

with restrictions:

Solution.

The objective function remains unchanged:

The system of inequalities is transformed into a system of equalities:

When solving the ZLP by the graphical method, a transition from the canonical form to the standard form is required.

To bring the PPP to a standard form, use Jordan–Gauss method SLAU solutions. Unlike the Gauss method, in which the extended matrix of the system is reduced to a stepwise form, in the Jordan–Gauss method, a unit matrix is ​​formed as part of the extended matrix. Therefore, reversing is not required here.

To convert the original canonical ZLP to the equivalent standard ZLP:

a) in the extended matrix of the constraint system, a non-zero element a qp is selected. This element is called permissive, and q is the i string and rth column are called resolve row and resolve column.

b) the permitting row is rewritten without change, and all elements of the permitting column, except the permitting one, are replaced with zeros. The remaining elements of the extended matrix are determined using the “rectangle rule”:

Let's consider four elements of the extended matrix: element a ij to be transformed, resolving element a qp and elements a i p and a qj. To find the element a ij, one should subtract from the element a ij the product of the elements a i p and a qj located at opposite vertices of the rectangle, divided by the resolving element a qp:

c) at the same time, allowed unknowns are excluded from the objective function. To do this, the coefficients of the objective function are written in the last row of the extended matrix. The calculations take into account that the enabling element in the last line cannot be selected.

Example 2. Reduce to standard form:

Solution.

Using the Jordan–Gauss method, we reduce the system of equations-constraints of the ZLP to an equivalent system of inequalities. Let us select the third element of the first row as the resolving element:

The number -9 obtained in the last column of the last row must be written into the objective function with the opposite sign. As a result of transformations, the ZLP takes the form:

Because variables x 2 and x 3 are non-negative, then discarding them, we can write the ZLP in a symmetric form:

In the canonical form of the ZLP, the objective function can be either minimized or maximized. To move from finding the maximum to finding the minimum or vice versa, it is enough to change the signs of the coefficients of the objective function: F 1 = - F. The resulting problem and the original ZLP have the same optimal solution, and the values ​​of the objective functions on this solution differ only in sign.

Properties of ZLP

1. 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 contains the entire segment connecting any two points of this set.

According to this definition, the polygon in Fig. 1a is a convex set, but the polygon in Fig. 1b is not, because the segment MN between its two points M and N does not completely belong to this polygon.

Not only polygons can be convex sets. Examples of convex sets are circle, sector, segment, cube, pyramid, etc.

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

Point X is called convex linear combination points X 1, X 2,…, X n, if the following conditions are met:

X = α 1 X 1 +α 2 X 2 +…+ α n X n,

α j ≥ 0, Σα j = 1.

Obviously, in the special case for n = 2, a convex linear combination of two points is the segment connecting them.

3. Each admissible basic solution of the system of restrictions of the canonical ZLP corresponds to a corner point of the solution polyhedron, and vice versa, to each corner point of the solution polyhedron there corresponds an admissible basis solution.

From the last two properties it follows: if a ZLP has an optimal solution, then it coincides with at least one of its admissible basic solutions.

Thus, the extremum of the linear ZLP function must be sought among the finite number of its admissible basic solutions.

The basis for solving economic problems are mathematical models.

Mathematical model problem is a set of mathematical relationships that describe the essence of the problem.

• selection of problem variables
• drawing up a system of restrictions
• choice of objective function

Task variables are called the quantities X1, X2, Xn, which completely characterize the economic process. They are usually written as a vector: X=(X 1, X 2,...,X n).

System of restrictions problems are a set of equations and inequalities that describe the limited resources in the problem under consideration.

Objective function tasks are called a function of task variables that characterizes the quality of the task and the extremum of which needs to be found.

In general, a linear programming problem can be written as follows:

This entry means the following: find the extremum of the objective function (1) and the corresponding variables X=(X 1 , X 2 ,...,X n) provided that these variables satisfy the system of restrictions (2) and the non-negativity conditions (3) .

Valid solution(plan) of a linear programming problem is any n-dimensional vector X=(X 1 , X 2 ,...,X n) that satisfies the system of constraints and non-negativity conditions.

The set of feasible solutions (plans) of the problem forms region of feasible solutions(ODR).

The optimal solution(plan) of a linear programming problem is such an admissible solution (plan) of the problem in which the objective function reaches an extremum.

Example of compiling a mathematical model

The problem of using resources (raw materials)

Condition: To produce n types of products, m types of resources are used. Create a mathematical model.

Known:

• b i (i = 1,2,3,...,m) — reserves of each i-th type of resource;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - the costs of each i-th type of resource for the production of a unit of volume of the j-th type of product;
• c j (j = 1,2,3,...,n) is the profit from the sale of a unit of volume of the j-th type of product.

It is required to draw up a production plan that ensures maximum profit under given restrictions on resources (raw materials).

Solution:

Let's introduce a vector of variables X=(X 1, X 2,...,X n), where x j (j = 1,2,...,n) is the volume of production of the jth type of product.

The costs of the i-th type of resource for the production of a given volume x j of products are equal to a ij x j , therefore the restriction on the use of resources for the production of all types of products has the form:
Profit from the sale of the jth type of product is equal to c j x j, so the objective function is equal to:

Answer- The mathematical model looks like:

Canonical form of a linear programming problem

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 and matrix notation.

The canonical linear programming problem in coordinate notation has the form:

The canonical linear programming problem in matrix notation has the form:

• A is the matrix of coefficients of the system of equations
• X—matrix-column of task variables
• Ао — matrix-column of the right parts of the system of restrictions

Linear programming problems, called symmetric ones, are often used, which in matrix notation have the form:

Reducing a general linear programming problem 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 models of economic problems, constraints are mainly formed in the form of a system of inequalities, so it is necessary to be able to move from a system of inequalities to a system of equations.

Let's take the linear inequality a 1 x 1 +a 2 x 2 +...+a n x n ≤b and add to its left side a certain value x n+1 such that the inequality turns into the equality a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Moreover, this value x n+1 is non-negative.

Let's look at everything using an example.

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 x 4 x 5 (in the mathematical model this operation is marked with the letter D).
The variable x 4 is introduced into the left side of the second inequality with the “+” sign, since the inequality has the form “≤”.
The variable x 5 is introduced into the left side of the third inequality with a “-” sign, since the inequality has the form “≥”.
The variables x 4 x 5 are entered into the objective function with a coefficient. equal to zero.
We write the problem in canonical form.

LINEAR PROGRAMMING MODEL

1 Mathematical description linear programming models

2 Methods for implementing linear programming models

3 Dual linear programming problem

Linear programming model(LP) occurs if in the system (object) under study there are restrictions on variables and the objective function linear.

LP models are used to solve two main types of applied problems:

1) optimal planning in any spheres of human activity - social, economic, scientific, technical and military. For example, with optimal production planning: distribution of financial, labor and other resources, supply of raw materials, inventory management, etc.

2) transport problem (finding an optimal plan for various types of transportation, an optimal plan for distributing various means to objects for various purposes, etc.)

MATHEMATICAL DESCRIPTION OF THE LINEAR PROGRAMMING MODEL

You need to find non-negative values ​​of variables

satisfying linear constraints in the form of equalities and inequalities

,

Where – given numbers,

and providing the extremum of the linear objective function

,

where are the given numbers, which is written in the form

Valid solution any collection is called , satisfying the conditions.

Range of feasible solutions– the set of all feasible solutions.

Optimal solution
, for which .

Notes

1. The given LP model is general. There are also standard And canonical forms of LP models.

2. Conditions of existence implementation of the LP model:

– the set of feasible solutions is not empty;

– objective function is limited by (at least from above when searching for the maximum and from below when searching for the minimum).

3.LP is based on two theorems

Theorem 1. A bunch of G, defined by a system of restrictions of the form, is a convex closed set ( convex polyhedron in with corner points - peaks.)

Theorem 2. Linear form , defined on a convex polyhedron

j=1,2,…,s

i=s+1,s+2,…, m,

reaches an extremum at one of the vertices of this polyhedron.

This theorem is called the linear form extremum theorem.

In accordance with Weierstrass's theorem, the optimal solution is unique and is a global extremum.

There is a general analytical approach to the implementation of the LP model - the simplex method. When solving linear programming problems, quite often there is no solution. This happens for the following reasons.

Let us illustrate the first reason with an example

For this reason they say that the restrictions are incompatible. The region of feasible solutions is an empty set.

The second reason is illustrated by the following example:

In this case, the range of feasible solutions is not limited from above. The range of feasible solutions is not limited.

Following the traditions of linear programming, we will give the LP problem an economic interpretation. Let us have at our disposal m types of resources. Quantity of resource type j equals . These resources are needed for production n types of goods. Let us denote the quantity of these goods by symbols respectively. Unit type i costs . Production of goods type i should be limited by values respectively. For the production of a unit of product type i resource type is consumed j. It is necessary to determine such a plan for the production of goods ( ) so that their total cost is minimal.

Linear programming problems used to optimize the functioning of real objects contain a significant number of variables and constraints. This makes it impossible to solve them using graphical methods. At large number variables and restrictions, algebraic methods are used, which are based on iterative computational procedures. In linear programming, many algebraic methods have been developed, differing in the methods of constructing the initial feasible solution and the conditions for transition from one iteration to another. However, all these methods are based on general theoretical principles.

The commonality of the basic theoretical principles leads to the fact that algebraic methods for solving linear programming problems are largely similar to each other. In particular, almost any of them requires preliminary reduction of the linear programming problem to the standard (canonical) form.

Algebraic methods for solving the LP problem begin with reducing it to standard (canonical) form:

,

,

i=1,..,n;j=1,..,m.

Any linear programming problem can be reduced to a standard form. Comparison general model with the canonical model allows us to conclude that in order to bring the LP problem to the standard form it is necessary, firstly, to move from the system of inequalities to equalities, and secondly, to transform all variables so that they are non-negative.

The transition to equalities is carried out by adding a non-negative residual variable to the left side of the restrictions for inequalities of type , and subtracting from the left side a non-negative redundant variable for inequalities of type . For example, inequality when passing to the standard form, it is converted into equality , a inequality - into equality . In this case, both the residual variable and the redundant variable are non-negative.

It is assumed that the right side of the inequalities is non-negative. Otherwise, this can be achieved by multiplying both sides of the inequality by “-1” and changing its sign to the opposite one.

If in the original linear programming problem the variable is not limited in sign, it can be represented as the difference of two non-negative variables , Where .

An important feature of variables is that for any acceptable solution only one of them can take a positive value. This means that if , That and vice versa. Therefore, it can be considered as a residual and - as a redundant variable.

Example Let the linear programming problem be given:

,

.

It needs to be brought to a standard form. Note that the first inequality of the original problem has the sign , therefore, it is necessary to introduce a residual variable into it. As a result we get .

The second inequality has a sign and, to convert to the standard form, requires the introduction of a redundant variable; after performing this operation, we obtain .

In addition, the variable is not limited in sign. Therefore, both in the objective function and in both constraints it must be replaced by the difference . After performing the substitution, we obtain a linear programming problem in standard form, equivalent to the original problem:

.

The linear programming problem, written in standard form, is the problem of finding the extremum of the objective function on a set of vectors that are solutions to the system linear equations taking into account non-negativity conditions. As is known, a system of linear equations may have no solutions, have a single solution, or have an infinite number of solutions. Optimization of the objective function is possible only if the system has infinite many solutions. A system of linear equations has an infinite number of solutions if it is consistent (the rank of the main matrix is ​​equal to the rank of the extended one) and if the rank of the main matrix is ​​less than the number of unknowns.

Let the rank of the constraint system matrix be equal to m. This means that the matrix has at least one minor m of order not equal to zero. Without loss of generality, we can assume that the minor is located in the upper left corner of the matrix. This can always be achieved by changing the numbering of the variables. This non-zero minor of rank m is usually called basic. Let's create a system from the first m equations of the system, writing it as follows:

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

In practice, constraints in a linear programming problem are often specified not by equations, but by inequalities.

Let's show how you can move from a problem with inequality constraints to a basic linear programming problem.

Let there be a linear programming problem with variables in which the constraints imposed on the variables have the form of linear inequalities. In some of them, the inequality sign may be different from others (the second type is reduced to the first by simply changing the sign of both sides). Therefore, we set all inequality constraints in standard form:

It is required to find a set of non-negative values ​​that would satisfy inequalities (4.1), and, in addition, would minimize the linear function:

From the problem posed in this way it is easy to move on to the main problem of linear programming. Indeed, let us introduce the following notation:

where are some new variables, which we will call “additional”. According to conditions (4.1), these additional variables must also be non-negative.

Thus, we are faced with a linear programming problem in the following formulation: find such non-negative values ​​of the variables that they satisfy the system of equations (4.3) and simultaneously minimize the linear function of these variables:

As you can see, before us in pure form basic linear programming problem (LPLP). Equations (4.3) are given in a form already resolved with respect to the basic variables, which are expressed through free variables. The total number of variables is equal to , of which “initial” and “additional”. The function L is expressed only through the “initial” variables (the coefficients of the “additional” variables in it are equal to zero).

Thus, we have reduced the problem of linear programming with inequality constraints to the main problem of linear programming, but with a larger number of variables than was originally in the problem.

Example 1 There is a linear programming problem with inequality constraints: find non-negative values ​​of variables that satisfy the conditions

and minimizing the linear function

It is required to bring this problem to the form of an OPLP.

Solution. We reduce inequalities (4.4) to standard form;

We introduce additional variables:

The task comes down to finding non-negative values ​​of the variables

satisfying equations (4.6) and minimizing the linear function (4.5).

We showed how we can move from a linear programming problem with inequality constraints to an equality constraint problem (ICP). The reverse transition is always possible - from the OLP to a problem with inequality constraints. If in the first case we increased the number of variables, then in the second case we will reduce it, eliminating basic variables and leaving only free ones.

Example 2. There is a linear programming problem with equality constraints (LPLP):

and the function to be minimized

It is required to write it as a linear programming problem with inequality constraints.

Solution. Since , we choose some two of the variables as free. Note that variables cannot be chosen as free, since they are related by the first of the equations (4 7): the value of one of them is completely determined by the value of the other, and free variables must be independent

For the same reason, it is impossible to select variables as free (they are connected by the second equation). Let us choose the free variables and express all the rest through them:

Since conditions (4 9) can be replaced by inequalities:

Let us pass in the expression of the linear function L to free variables, substituting their expressions (4.9) in L instead of and. we'll get it.