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

Let us show how we can go from the problem with inequality constraints to the main problem of linear programming.

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

It is required to find a set of nonnegative values ​​that would satisfy inequalities (4.1), and, moreover, would minimize the linear function:

It is easy to pass from the task set in this way to the main task of linear programming. Indeed, let us introduce the notation:

where are some new variables, which we will call "additional". According to conditions (4.1), these additional variables, as well as should be non-negative.

Thus, we are faced with a linear programming problem in the following formulation: find such nonnegative values ​​of the variables so that they satisfy the system of equations (4.3) and simultaneously reduce the linear function of these variables to a minimum:

As you can see, we have before us in its pure form the main task of linear programming (LPP). Equations (4.3) are given in the form already allowed for basic variables that are expressed in terms of free variables. The total number of variables is equal, of which "initial" and "additional". The function L is expressed only in terms of 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 satisfying the conditions

and minimizing the linear function

It is required to bring this task to the form of an OZLP.

Decision. We reduce inequalities (4.4) to the standard form;

We introduce additional variables:

The task is reduced to finding the non-negative values ​​of the variables

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

We have shown how we can go from a linear programming problem with inequality constraints to a problem with equality constraints (LPPP). The reverse transition is always possible - from the LPP to the problem with inequality constraints. If in the first case we increased the number of variables, then in the second case we will decrease it, eliminating the basic variables and leaving only free ones.

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

and the function to be minimized

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

Decision. Since, then we will choose some two of the variables as free. Note that variables cannot be chosen as free variables, since they are related by the first of 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 choose variables as free (they are connected by the second equation). Let's choose as free variables and express all the others 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 in L instead of their expressions (4.9). we get.

T10. Statement of the linear programming problem

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

To draw up a mathematical model, you must:

1.select variable tasks;

2. draw up a system of restrictions;

3. set the objective function.

Variables tasks called the values ​​x 1, x 2, ..., x n, which fully characterize the economic process. They are usually written as a vector X = (x 1, x 2, ..., x n).

System of task constraints 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 the task variables, which characterizes the quality of the task and the extremum of which you want to find.

General problem of mathematical programming is formulated as follows: find the variables of the problem 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 constraints (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).

The vector X (the set of variables of the problem) is called acceptable decision, or the plan of the LPP, if it satisfies the system of restrictions (1). A feasible design X that provides the extremum of the objective function is called optimal solution ZLP.

2. Examples of compiling mathematical models of economic problems

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

1.Optimal production plan challenge

For the production of two types of products T 1 and T 2, three types of resources S 1, S 2, S 3 are used. Stocks of resources, the number of units of resources spent on the manufacture of a unit of production, as well as profit from the sale of a unit of production are shown in the table:

It is required to find such a plan for the production of products, in which the profit from its sale will be maximum.

Decision.

Let's designate x 1, x 2 - the number of units of production, respectively, T 1 and T 2, planned for production. To make 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. The 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 a production plan X = (x 1, x 2) that satisfies the system of restrictions:

and the condition

in which the function takes on the maximum value.

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

2.Optimal Diet Challenge

There are two types of food, K 1 and K 2, containing the 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 formulate a daily diet that has a minimum cost, in which the content of each type of nutrient would be at least the established limit.

Decision.

Let's designate x 1, x 2 - the amount of feed K 1 and K 2 included in the daily ration. Then this diet will include (3x 1 + x 2) units of nutrient S 1, (x 1 + 2x 2) units of substance S 2, (x 1 + 6x 2) units of nutrient S 3. Since the content of nutrients S 1, S 2 and S 3 in the diet should be 9, 8 and 12 units, respectively, the economic and mathematical model of the problem can be formulated as follows:

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

and the condition

in which the function takes on a minimum value.

LPP recording forms

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

with restrictions:

and the non-negativity condition

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

This is how the ZLP is recorded in general form. If the system of constraints contains only inequalities, then the LPP is represented in standard form. Canonical (main) a form of LPP record is a record when the system of restrictions contains only equalities. So the above LPPs are written in standard form.

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

To move from one form of writing LPP to another, one must be able to move from inequality constraints to equality constraints and vice versa.

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

Introduced additional variables have some economic meaning... So, if the constraints of the original LPP reflect the consumption and availability of resources, then the value of the additional variable LPP in the canonical form is equal to the volume of the unused corresponding resource.

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

with restrictions:

Decision.

The objective function remains unchanged:

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

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

To bring the LPP to a standard form, use Jordan-Gauss method SLAE solutions. In contrast to the Gauss method, in which the extended matrix of the system is reduced to a stepped form, in the Jordan - Gauss method, the unit matrix is ​​formed as part of the extended matrix. Therefore, the reverse is not required here.

To transform the original canonical LPP into an equivalent standard LPP:

a) in the extended matrix of the constraint system, a nonzero element a qp is selected. This item is called permissive, and q is the i row and the pth column are called the permissive row and permissive column.

b) the resolving line is rewritten without change, and all elements of the resolving column, except for the resolving one, are replaced with zeros. The rest of the elements of the extended matrix are defined using the "rectangle rule":

Consider four elements of the extended matrix: the element a ij to be transformed, the resolving element a qp and the elements a i p and a qj. To find the element a ij, it follows from the element a ij to subtract 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) the allowed unknowns are simultaneously excluded from the objective function. For this, the coefficients of the objective function are written in the extended matrix in the last row. The calculations take into account that the resolving element in the last line cannot be selected.

Example 2... Bring to standard form:

Decision.

Using the Jordan - Gauss method, we reduce the system of equations-constraints of the LPP to an equivalent system of inequalities. Let's select the third element of the first line 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 the transformations, the LPP takes the form:

Because variables x 2 and x 3 are non-negative, then dropping them, you can write the LPP in a symmetric form:

In the canonical form of the LPP, the objective function can be both minimized and maximized. To go from finding the high to finding the low 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 LPP have the same optimal solution, and the values ​​of the objective functions on this solution differ only in sign.

ZLP properties

1. The set of all feasible solutions of the system of constraints of the 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, while 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 a circle, a sector, a line segment, a cube, a pyramid, etc.

2. If the LPP has an optimal solution, then the linear function takes the maximum (minimum) value at one of the corner points of the solution polytope. If a linear function takes the 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 constraints of the canonical LPP corresponds to a corner point of the solution polytope, and vice versa, to each corner point of the solution polytope there corresponds an admissible basic solution.

It follows from the last two properties: if the LPP 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 a finite number of its admissible basic solutions.

Definition. Linear Programming (LP) - the science of research methods and finding the extreme (largest and smallest) values ​​of a linear function, on whose unknowns linear constraints are imposed.

This linear function is called target, and constraints that are mathematically written in the form of equations or inequalities are called system of restrictions.

Definition. The mathematical expression of the objective function and its limitations is called mathematical model of the economic problem.

In general, the mathematical model of a linear programming problem (LP) is written as

with restrictions:

Where x j- unknown; a ij, b i, c j- given constant values.

All or some of the equations of the system of constraints can be written in the form of inequalities.

The mathematical model in a more concise notation has the form

with restrictions:

Definition. A feasible solution (plan) of a linear programming problem is a vector = ( x 1 , x 2 ,..., x n), satisfying the system of restrictions.

The set of feasible solutions forms the area of ​​feasible solutions (ODS).

Definition. A feasible solution at which the objective function reaches its extreme value is called the optimal solution to the linear programming problem and is denoted by opt.

Basic feasible solution (x 1 , x 2 , ..., x r , 0, …, 0) is the reference solution, where r - the rank of the system of restrictions.

The mathematical model of the LP problem can be canonical and non-canonical.

7.Solution of linear programming problems by graphical method... Function-constraints graphs. Level lines.

Graphical method for solving linear programming problems

The simplest and most intuitive method of linear programming is the graphical method. It is used to solve LP problems with two variables given in non-canonical form and many variables in canonical form, provided that they contain at most two free variables.

From a geometric point of view, in a linear programming problem, one looks for such a corner point or a set of points from the feasible set of solutions at which the highest (lowest) level line is reached, located farther (closer) than the others in the direction of the fastest growth.

To find the extreme value of the objective function in the graphical solution of LP problems, use the vector L() on surface X 1 OH 2 , which we denote . This vector shows the direction of the fastest change in the objective function. In other words, the vector is the normal of the level line L()

Where e 1 and e 2 - unit vectors along the axes OX 1 and OX 2 respectively; thus = (∂L / ∂х 1 , ∂L / ∂х 2 ). The coordinates of the vector are the coefficients of the objective function L (). The construction of the level line will be considered in detail when solving practical problems.

Algorithm for solving problems

1. Find the region of feasible solutions to the system of constraints of the problem.

2. Building a vector .

3. Draw a level line L 0 , which is perpendicular .

4. Move the level line in the direction of the vector for tasks to the maximum and in the opposite direction , for tasks to a minimum.

The level line is moved until it has only one common point with the area of ​​admissible solutions. This point, which determines the only solution to the LP problem, will be the extremum point.

If it turns out that the level line is parallel to one of the sides of the ODR, then in this case the extremum is reached at all points of the corresponding side, and the LP problem will have an infinite number of solutions. It is said that such an LP problem has alternative optimum, and its solution is found by the formula:

Where 0 ≤ t≤ 1, 1 and 2 - optimal solutions at the corner points of the ODR.

The LP problem can be unsolvable when the constraints defining it turn out to be contradictory.

5. Find the coordinates of the extremum point and the value of the objective function in it.

Example 3. Selection of the optimal product release option

The company produces 2 types of ice cream: creamy and chocolate. For the manufacture of ice cream, two initial products are used: milk and fillers, the costs of which per 1 kg of ice cream and daily supplies are given in the table.

The study of the sales market showed that the daily demand for ice cream exceeds the demand for chocolate ice cream, but by no more than 100 kg.

In addition, it was found that the demand for chocolate ice cream does not exceed 350 kg per day. Retail price of 1 kg of creamy ice cream 16 rubles, chocolate - 14 rubles.

How much ice cream of each type should the firm produce in order to maximize the income from product sales?

Decision. Let's denote: x 1 - daily volume of ice cream production, kg; x 2 - daily output of chocolate ice cream, kg.

Let's make a mathematical model of the problem.

The prices for ice cream are known: 16 rubles and 14 rubles, respectively, so the objective function will look like:

We will set limits on milk for ice cream. Its consumption for creamy ice cream - 0.8 kg, for chocolate - 0.5 kg. Milk stock 400kg. Therefore, the first inequality will look like:

0.8x 1 + 0.5x 2 ≤400 - the first inequality is a limitation. The rest of the inequalities are composed in a similar way.

The result is a system of inequalities. that is the solution area of ​​each inequality. This can be done by substituting the coordinates of the point O (0: 0) into each of the inequalities. As a result, we get:

Figure OABDEF - area of ​​admissible solutions. We build a vector (16; 14). Level line L 0 is given by the equation 16x 1 + 14x 2 = Const. We choose any number, for example the number 0, then 16x 1 + 14x 2 = 0. In the figure, for the line L 0, a certain positive number is selected that is not equal to zero. All level lines are parallel to each other. Level line normal vector.

Move the level line in the direction of the vector. Exit point L 0 from the region of feasible solutions is the point D, its coordinates are determined as the intersection of straight lines given by the equations:

Solving the system, we get the coordinates of the point D(312.5; 300), in which there will be an optimal solution, i.e.

Thus, the company should produce 312.5 kg of ice cream and 300 kg of chocolate ice cream per day, while the income from sales will amount to 9,200 rubles.

8. Reduction of an arbitrary linear programming problem to the main problem. Converting inequality constraints into corresponding equations.

9.Simplex method... Description and algorithm of the method, its applicability.

To solve the problem using the simplex method, it is necessary:

1. Indicate a way to find the optimal support solution

2. Indicate the method of transition from one support solution to another, at which the value of the objective function will be closer to the optimal one, ie. indicate a way to improve the reference solution

3. Set the criteria that allow you to timely stop the search for support solutions on the optimal solution or to pass a conclusion on the absence of an optimal solution.

Algorithm of the simplex method for solving linear programming problems

1. Bring the problem to the canonical form

2. Find the initial support solution with a "unit basis" (if there is no support solution, then the problem has no solution, due to the incompatibility of the system of constraints)

3. Calculate the estimates of the vector expansions in the basis of the support solution and fill in the table of the simplex method

4. If the criterion of uniqueness of the optimal solution is satisfied, then the solution to the problem ends

5. If the condition for the existence of a set of optimal solutions is satisfied, then by a simple enumeration all optimal solutions are found

10. Transport problem. Definition, types, methods of finding the initial solution of the transport problem.

The transport problem is one of the most common linear programming problems. Its goal is to develop the most rational ways and means of transporting goods, eliminating excessively long-distance, oncoming, repeated transportation.

1. Finding the original support solution;

2. Checking this solution for optimality;

3. Transition from one support solution to another.

1.

2. directions of use mat. models in the economy.

Mathematical models make it possible to determine the optimal values ​​of unknown parameters of economic systems, which is important in the decision-making process. Mathematical programming just provides the apparatus that allows you to optimize the process of selecting the best options for plans in the process of management in economic systems.

Used in mathematics, optimization methods, economic methods. cybernetics, experimental problems.

In the study of complex processes and phenomena in the economy, modeling is very often used - a well-defined concrete display of the considered characteristics of the object under study. Its essence lies in the fact that the phenomenon under study is reproduced under experimental conditions using a model on a different time and space scales. A model is a specially created object with the help of which well-defined characteristics of the system under study are reproduced in order to study it. Mathematical modeling is the most perfect and at the same time effective method of obtaining information about the object under study. It is a powerful analytical tool in economics. The results of a study using models will be of practical interest when the constructed model is sufficiently adequate to the phenomenon under consideration, i.e. represent the real situation well enough.

2. mathematical programming as a science, its structure. Optimization problems. Difficulties in applying classical optimization methods when solving economic problems.

Mathematical programming Is a branch of applied mathematics that develops theoretical foundations and methods for solving extreme problems.

Mathematical programming includes a number of sections, the main ones of which are as follows:

1. Linear programming. This section includes problems in which unknown variables are included in mathematical relations to the first degree.

2. Non-linear programming. This section includes problems in which the objective function and (or) constraints may be nonlinear.

3. Dynamic programming. This section includes tasks in which the solution process can be broken down into separate stages.

4. Integer programming. This section includes tasks in which unknown variables can only take integer values.

5. Stochastic programming. This section includes problems that contain random variables in the objective function or constraints.

6. Parametric programming. This section includes problems in which the coefficients of unknown variables in the objective function or constraints depend on some parameters.

To solve mathematical programming problems, it is difficult to use classical methods for finding the extremum, since in mathematical programming problems the objective function reaches its extreme value on the boundary of the region of admissible values ​​of unknown variables, and derivatives at the boundary points do not exist. A complete enumeration of the feasible points is impossible due to their significant number.

3. The concept of a mathematical model, types of mat. models

Mathematical model Is an abstraction of a real phenomenon or process written in mathematical symbols and expressions. Mathematical models of economic processes and phenomena are called economic and mathematical models

Models are divided into:

1. linear, in which all dependencies are described by linear relations,

2. nonlinear, in which there are nonlinear relations;

3. stochastic, which take into account the random nature of the studied processes,

4. deterministic, which take into account the averaged values ​​of all parameters.

5. dynamic models in which the systems under study are considered in development over several periods,

6. static, in which the time factor is not taken into account.

7. optimization models in which the choice is made depending on extremization some criterion,

8. non-optimization, in which there is no optimality criterion.

9. macromodels(the entire economy as a whole)

10. micromodels(individual links or processes of the economy).

Types of mathematical models: linear, nonlinear, quadratic, integer, discrete, parametric, linear fractional, dynamic, stochastic

4. General formulation of mathematical programming problems.

Consider the general formulation of the mathematical programming problem.

The general problem of mathematical programming is to determine the optimal value of the objective function, and the values ​​of the variables must belong to a certain range of admissible values. Mathematically, the definition of the optimal solution is expressed in finding the extremum (max or min) of a function of many variables

Z = f (x1, x2, ..., xn)

in the given range of these variables

gi (x1, x2, ..., xn) Ribi (i = 1, 2, ..., m),

where Ri is one of the signs ≥, =, ≤.

5. The problem of optimizing the production plan. Economic formulation and construction of a mathematical model of problems.

Economic setting:

The enterprise produces n types of products using m types of raw materials. For the production of a unit of production, a strictly defined amount of raw materials of one kind or another is used. Each type of raw material is limited at the enterprise. The enterprise receives a certain profit from the sale of a unit of production. It is necessary to find a plan for the production of products in which the company will receive the maximum total profit.

Mathematical setting:

Let j be the index of the type of product j = 1, n

i is the index of the resource type i = 1, m

and ij - raw material costs i-th type for the production of a unit of production j-th type;

Аi - a specified restriction on the available volume of resources of the i-th type;

Рj - profit received from the sale of a unit of production of the j-th type;

xj is the volume of products of the j-th type.

z = P1x 1 + P2x 2 +… + Pnx n → max

a11x 1 + a12x 2 +… + a1nx n ≤ A1

a21x 1 + a22x 2 +… + a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +… + a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. The problem of the diet. Economic formulation and construction of a mathematical model of the problem.

Economic setting

Some farms feed animals. Used for fattening n types of feed. The content of nutrients (calcium, phosphorus, etc.) in a feed unit of each species is known. For adequate nutrition of animals, the intake of nutrients is not less than the specified amounts. The unit cost of each feed is known. It is necessary to determine the ration for feeding animals, in which the total cost of feeding will be minimal.

Mathematical setting:

j - index of the type of feed, j = 1, n

i - index of the type of nutrients, i = 1, m

Аi - the required daily intake of the i-th type of nutrient;

Сj is the cost of a feed unit of the j-th type.

Let's introduce unknown variables:

хj - the daily amount of feeding of animals with the j-th type of food.

In terms of the introduced notation, this problem will be written as follows

a11x1 + a12x2 + ... + a1nxn ≥ A1

a21x1 + a22x2 + ... + a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +… + a mnxn ≥Am

xj ≥ 0, j = 1, n

7. Transport problem ... Economic formulation and construction of a mathematical model of the problem.

Economic setting :

There is m suppliers of homogeneous products and n consumers of these products. The unit costs for the delivery of a unit of production from each supplier to each consumer are known. Supplier stocks are limited. The needs for the products of each consumer are also known.

It is necessary to determine such a plan for the transportation of products from suppliers to consumers, in which the total cost of transportation will be minimal.

Mathematical setting :

Let us introduce the notation for the given parameters:

j - consumer index, j = 1, n

i - supplier index, i = 1, m

Аi - the volume of products available from the i-th supplier;

Вj is the volume of demand for products of the j-th consumer;

Cij is the unit cost of transporting a unit of production from the i-th supplier to the j-th consumer.

Let's introduce unknown variables:

хij is the volume of transportation of products from the i-th supplier to the j-th consumer.

z = С11x11 + С12x12 + ... + С1nx1n + С21x21 + ... + Сm (n -1) xm (n-1) + Сmnxmn → min

Limitations of the task.

I. From each supplier, you can withdraw products no more than the available quantity:

x11 + x12 +… + x1n ≤ A1

x21 + x22 +… + x2n ≤ A2 (2)

…………………….

xm1 + xm2 +… + xmn ≤ Am

II. The need of each consumer for products must be satisfied

x11 + x21 +… + xm1 ≥B1

x12 + x22 +… + xm2 ≥B2

……………………. (3)

x1n + x2n +… + xmn ≥Bn

III. Non-negativity condition: xij ≥0, i = 1, m; j = 1, n

It is often convenient to condense the mathematical formulation:

, i = 1, m , j = 1, n

8. The problem of choosing appointments or appointments. Economic formulation and construction of a mathematical model of the problem.

Economic setting :

There are n types of work and n performers. Each of the performers can perform any, but only one job. The cost price of each work is set by each performer. It is necessary to assign performers to work in such a way that the total cost of performing the work is minimal.

Mathematical setting .

Let us introduce the notation for the given parameters.

i - index of jobs, i = 1, m

j - index of performers, j = 1, n

Cij is the cost of performing the i-th job by the j-th performer.

Let's introduce unknown variables. In this problem, unknown variables can take only two values ​​0 or 1. Such variables are called zero.

1 - if the j-th performer is assigned to the i-th work;

0 - otherwise.

In terms of the introduced notation, this problem will be written as follows:

z = С11x11 + С12x12 + ... + С1nx1n + С21x21 ... + С (n-1) (n -1) x (n-1) (n-1) + Сnnxnn → min

I group of restrictions.

Only one performer should be assigned to each work:

x11 + x12 +… + x1n = 1

x21 + x22 +… + x2n = 1

……………………..

xn1 + xn2 +… + xnn = 1

II. group of restrictions.

Each performer can only perform one job:

x11 + x21 +… + xn1 = 1

x12 + x22 +… + xn2 = 1

……………………..

x1n + x2n +… + xnn = 1

x ij = (0,1) i = 1, n; j = 1, n

9. The problem of cutting materials. Economic formulation and construction of a mathematical model of the problem.

Economic setting .

The starting material of the same size is supplied for cutting. It needs to be cut into pieces of a given size in a given quantity, so that the total waste is minimal.

Mathematical setting .

Let's introduce the notation:

i - index of blanks,

Аi - the required number of workpieces of the i-type;

j - index of cutting options,

Сj - the size of the waste when cutting a unit of the source material according to option j;

and ij is the number of blanks of the i-th type when cutting a unit of source material according to option j.

Let us introduce the notation for the unknown variables.

хj is the amount of starting material cut by option j.

In terms of the introduced notation, this problem will be written as follows:

z = С1x1 + С2x2 +… + Сnxn → min

a11x1 + a12x2 + ... + a1nxn = A1

a21x1 + a22x2 + ... + a2nxn = A2

…………………………….

am1x1 + am2x2 +… + amnxn = Am

xj ≥ 0, j = 1, n

The use of mathematical models allows you to save raw materials up to 20%.

The mathematical model of cutting is built in two stages.

At the first stage, the construction of cutting options is carried out, as a result of which the values ​​of the number of options n, the number of blanks of each type obtained with different cutting options (аij), as well as the values ​​of waste (Сj) are determined.

The construction of cutting options for a unit of source material is carried out in the form of the following table:

Option No.

Blank i1

Blank i2

Workpiece im

The workpieces are arranged in the order of their non-increasing size. Variants are constructed by exhaustive search.

10. The general form of the model of LP tasks and its features

The general form of ZLP is:

z = С1x1 + ... + Сnxn max (min)

a11 X1 + a12 X2 + ... + a1n Xn R1 a1

a21 X1 + a22 X2 +… + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +… + amnxn Rm am

хj ≥ 0, j = 1, k, k ≤ n

In general form, each symbol R1, R2,…, Rm means one of the signs: ≥, = or ≤.

The general form of the LP problem model has the following features.

1. The system of constraints is presented in the form of equations (rigid conditions) and inequalities (non-rigid conditions).

2. Conditions of non-negativity are imposed on not all variables

3. The objective function tends to either the maximum or the minimum.

11. The standard form of the model of LP tasks and its features

The standard form is as follows.

Find the maximum or minimum of the objective function z:

z = С1x1 +… + Сnxn → max (min) (1)

Subject to the following restrictions:

a11 X1 + a12 X2 + ... + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 + ... + amn Xn ≥ am

хj ≥ 0, j = 1, k, k ≤ n

The features of the standard form of the LP problem model are as follows:

1.the system of restrictions is presented in the form of inequalities (non-rigid conditions)

2.non-negativity conditions are imposed on all variables

3.the objective function tends to either max or min

12. Canonical form of LP problem model and its features

The canonical form is:

Find the minimum of the objective function z:

z = С1x1 +… + Сnxn → min

Subject to the following restrictions:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

The features of the canonical form are as follows:

1. The system of restrictions is presented in the form of equations (stringent conditions).

2. Non-negativity conditions are imposed on all variables

3. The objective function tends to

In some sources, the objective function of the LP problem, presented in the canonical form, tends to a maximum. This is done for the convenience of solving the problem using an algorithm designed to maximize the objective function.

13. Possible, admissible, optimal base plan of the task, ODZ of the LP task

Definition 1. The values ​​of unknown variables that satisfy all the constraints of a linear programming problem are called admissible values ​​of variables or plans .

Definition 2. The set of all plans for a linear programming problem is called the range of admissible values ​​of variables ( ODZ ).

Definition 3. The plan of the linear programming problem, in which the objective function takes the minimum (or maximum) value on the ODZ is called optimal .

14. Types of LP task records: expanded, collapsed, matrix, vector.

LP task models can be written in various forms.

1. Expanded view of the model record

Z = c1 X1 + c2 X2 +… + cn Xn → min

a11 X1 + a12 X2 +… + a1n Xn = a1,

a21 X1 + a22 X2 +… + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 +… + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Collapsed view:

,

Xj ≥ 0, j = 1, n.

3. Model of the LP problem in matrix form:

X ≥ 0

Where

a11 a12 ... a1n X1 a1

A = a21 a22 ... a2n, X = X2, A0 = a2

… … … … … …

am1 am2… amn X3 am

4. Model of the LP problem in vector form:

Where

X1 a11 a12 a1n a1

X2, a21, a22, a2n, a2

… … … … …

Xn am1 am2 am2 am

15. Transition from the standard and general form of LP problems to the canonical one. Connection theorem

To switch from a general or standard form to a canonical one, the following techniques are used.

1. Converting Variables... If some variable Xk is non-positive (Xk ≤ 0), then a new variable Xk "is introduced, so that Xk" = –Xk. Obviously, Xk "≥ 0. After that, in each constraint and objective function, the variable Xk is replaced by [ – Xk "].

If some variable Xt can take any values, then it is replaced by the difference of two non-negative variables Xt 'and Xt' ', i.e., it is assumed that xt = Xt' - Xt '', where Xt '0 ≥ and Xt' ' ≥ 0.

2. Convert Constraints. If any of the constraints in the model has the form of an inequality, then it is converted into equality by adding (if the inequality is of type ≤) or subtraction (if the inequality is of type ≥) from its left side. These variables are called balance sheet. Balance variables are included in the objective function with zero coefficients. The balance variable takes on the value of the index sequentially after the existing ones. If, for example, the system of restrictions has 5 variables, then the first balance variable will be X6, and the second - X7, etc.

16. Transition from the canonical form of the ZLP model to the standard

To switch from the canonical to the standard form, each of the

equations to replace the system of inequalities:

Another way is to bring the system of equations to a special form and further exclude some variables.

Using the Jordan-Gauss method, we select a basic variable in each equation. This selection is carried out using equivalent (elementary) Gaussian transformations. These include:

a) multiplication of any equation by a nonzero constant;

b) adding to any equation any other equation multiplied by any constant.

It is convenient to write the original system of linear equations before transformation in the form of a matrix or table:

We write down the task in a standard form.

17. The concept of a hyperplane of a half-plane, a support hyperplane.

18. Geometric. interpretation of the system of constraints and objective function in LP tasks

19. Convex set: extreme (corner) points of the set. Convex polyhedron

Definition A set M is called convex if, together with any two points belonging to this set, it also contains a segment connecting them.

Convex set

Definition A point x of a set M is called angular or extreme if it is not interior for any segment that entirely belongs to this set.

Theorem 1. Any point of a line segment can be represented as a convex combination of its corner points.

x = λ 1 A + λ 2 B

λ 1, λ 2 ≥ 0 convex combination of points of corner points A and B

λ 1 + λ 2 = 1

Theorem 2. Any point of a convex closed set can be represented as a convex combination of its corner points.

20.Algorithm of the graphical method for solving LP problems

1. It is checked whether the original LPP is in the standard form, if not, then the problem must be transformed to the standard form.

2. The number of unknown variables is checked. If this number is more than three, then the problem cannot be solved graphically (there are other effective methods for solving such problems).

3. The area of ​​admissible values ​​of variables for the LPP is constructed.

4. Direction vector is constructed c .

5. The initial isocoel is drawn through the ODZ (perpendicular to the direction vector).

6. A mental movement of the original iso-target is carried out in the direction of the vector c, if the maximum value of the objective function is determined, or in the opposite direction, if its minimum value is determined, until the isocoel becomes the reference one to the ODZ. The points of intersection of the reference iso-target and ODZ will be the optimal points of the problem.

7. In order to determine the coordinates of the optimal point, it is necessary to solve the system of corresponding linear equations.

8. To find the optimal value of the objective function, it is necessary to substitute the optimal values ​​of the variables into the objective function and calculate its value.

20. graphical algorithm. method for solving LP problems

Algorithm of the graphical method.

1. By sequential construction of each of the conditions of the system of constraints of the problem, the construction of the ODZ is carried out.

2. The direction vector C is constructed according to the coefficients at the variables of the objective function.

3. The original isocoil is drawn perpendicular to the direction vector through the origin of coordinates.

4. A mental movement of the initial iso-target is carried out in the direction of increasing the values ​​of the vector C, if the maximum value of the objective function is determined, or in the opposite direction, if its minimum value is determined, until the iso-target becomes the reference one to the ODZ. The points of intersection of the reference iso-target and the LDZ will be the optimal points of the problem.

5. To determine the coordinates of the optimal point, it is necessary to solve the system of the corresponding linear equations of those conditions at the intersection of which the optimal point is located.

6. To find the optimal value of the objective function, it is necessary to substitute the coordinates of the optimal point into the objective function and calculate its value.

23.theorems on the range of admissible values ​​of the LP problem and on the target function

ODZ theorem. The domain of feasible solutions of the LP problem is a convex set (closed and bounded in n-dimensional space)

Theorem 2. On the objective function of a linear programming problem.

The objective function of the LPP takes its optimal value at one of the corner points of the range of admissible values ​​of the variables. If the objective function takes its optimal value at several corner points, then it takes the same value at any point that is a convex combination of these corner points.

24. The corner point theorem. Sufficient and necessary condition

25. Consequences from the theorem on the properties of solutions of LP problems and conclusions. Basic plan concept.

Consequences from theorems.

Definition. Plan = (x1, x2, ..., xn), the positive coordinates of which correspond to linearly independent vectors, is called basic plan of ZLP .

Corollary 1. The reference plan has at most m positive coordinates.

If it has exactly m positive coordinates, then such a reference design is called non-degenerate, otherwise degenerate.

Corollary 2. Each corner point of the LDZ is a reference plan.

27. Algorithm of the simplex method.

When solving LP problems using the simplex method, it is necessary to perform the following sequence of actions.

1. It is checked whether the LP problem is in canonical form. If not, then it is necessary to convert the original model to the canonical form.

2. The initial reference plan and the value of the objective function for this reference plan are highlighted.

3. The construction of the original simplex table is carried out.

4. Values ​​of optimality estimates in the index row are checked. If there are no positive estimates, then the optimal solution is written out and the algorithm ends its work. Otherwise, point 5 is fulfilled.

5. In the basis, a vector is introduced, which corresponds to the greatest positive estimate. This column is called permissive.

6. A vector is derived from the basis, which corresponds to the simplex ratio calculated by the formula 0< Ө ≤ . Данная строка называется разрешающей строкой.

7. A new simplex table is constructed. Columns B and C are changed accordingly B. The rest of the table is filled from the previous one using Gaussian transformations, and the index row is considered to be m + 1 rows and is also transformed using Gaussian transformations. Let's proceed to step 4 of this algorithm.

After building each table, you can check the correctness of the calculations using the formulas for calculating the estimates given in the previous paragraph.

28. choice of basis and construction of the initial reference plan for solving problems by the simplex method.

29. Simplex tables, their filling. Formulas for calculating the coefficients of the index row.

30 ... The optimality theorem for the plan of a linear programming problem is a consequence of the optimality estimate theorem for solving problems by the simplex method.

Theorem 1: If for some vector Ā j in the system

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n = a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n = a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 +… + a mn X n = a m

The relation Z j - c j> 0 is satisfied, then the plan X B0 is not optimal and you can go to the plan X B1 such that Z (X B1) ≤ Z (X B0).

Here Z j = (С, Ā j) is the scalar product of vectors.

C is a vector consisting of the coefficients at the basis variables of the objective function Z

Ā j is a vector consisting of the coefficients of the expansion of the corresponding vector in terms of the basis vectors.

c j - coefficient of the objective function Z at variable X j

Consequence of theorems: If for all vectors Ā 1, Ā 2,…, Ā n of some reference plan X, the relation Z j - c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Thus, the theorem and corollary make it possible to establish whether the next baseline plan is optimal and, if it is not, then it is necessary to switch to another baseline plan, in which the value of the objective function will be less.

Comment... In the theorem and corollary, it is assumed that the problem is in canonical form with the objective function at its minimum. However, the simplex method can also be used to solve problems with the maximum objective function. In this case, when analyzing the values ​​of estimates, their opposite meaning is used, that is, the plan will be optimal if all estimates of optimality are not negative (positive or negative).

31. The choice of the vector, entered into the basis and deduced from the basis. Simplex relationship.

One of the free vectors is required to switch to a new reference plan enter into the basis, and deduce some of the basis vectors. For introduction into the basis, we choose a vector with at least one positive coordinate. Let such a vector be the vector А m + 1.

Decomposition -

Corresponding vector, cat. will be a reference plan if its coordinates are non-negative, and the number of positive coordinates equals m.

The coordinates of the X1 vector must be non-negative, i.e. ...

If a , then this coordinate will be non-negative.

Let the minimum in relation (5) be obtained for i = 1, then if we take

then the first coordinate of vector 1 x becomes zero.

Relation (6) is called simplex relation... Thus, we have switched from the original reference plan 0 x(basis vectors A1, A2, ... Am) to the baseline 1 x(basis vectors А2, А3, ..., Аm, Am + 1).

32. resolving element of the table, its choice. The Jordan full exception rule for recalculating a simplex table.

33. Rule of "quadrangle" for recalculation of a simplex table

34. A criterion for the uniqueness of the optimal design, the set of optimal designs and the absence of the optimal design when solving the LP problem using the simplex method.

When solving problems using the simplex method, the following types of optimal solutions are possible:

1. Uniqueness . If the estimates of all free vectors are strictly negative, then the resulting support design is optimal and unique. (see example in the previous paragraph).

2. Alternative optimum (set of optimal solutions).

If among the non-positive estimates of free vectors there is at least one zero one, then the resulting support plan will be optimal, but not the only one. In this case, you can go to other reference plans (vectors are introduced into the basis, which correspond to zero estimates) and, then, the general optimal solution can be written in the form of a convex combination of the obtained optimal reference plans.

3. LPP does not have an optimal solution, since the objective function is not bounded from below . If the simplex table has a positive score, and all the elements of this column are negative and zero, then this vector can be entered into the basis. However, none of the basis vectors can be derived from the basis. It follows from this that a further decrease in the objective function is possible when switching to a non-support plan.

4. LPP does not have an optimal solution, since the system of restrictions is contradictory. Since, when solving the LPP, the original reference plan must be used by the usual simplex method, the system of linear equations is certainly not inconsistent. Therefore, such a case cannot be encountered when solving with the usual simplex method.

5. If the ODZ consists of one point, then the solution of such a problem is trivial and can be obtained without using the simplex method.

35. In what cases is the artificial basis method applied?

artificial.

36. Construction of the M-problem in the method of artificial basis

If the linear programming problem is in canonical form, however, not all equations have basic variables, that is, the original reference plan is absent. In this case, in those equations in which there are no basic variables, it is necessary to add some non-negative variable with a coefficient of +1. Such a variable is called artificial.

An artificial variable must be added to the objective function with a very large positive number (since the objective function is to find the minimum). This number is denoted by the Latin letter M. It can be considered equal to + ∞. In this regard, sometimes the artificial basis method is called the M-method. This transformation of the original problem is called the construction of the extended problem. If a problem is solved with an objective function to find an artificial variable, it is necessary to add to the objective function with a very large positive number (since the objective function is to find the minimum). This number is denoted by the Latin letter M. It can be considered equal to + ∞. In this regard, sometimes the artificial basis method is called the M-method. This transformation of the original problem is called the construction of the extended problem. If a problem is solved with an objective function to find the maximum, then artificial variables are included in the objective function with the coefficient –M.

Thus, in the extended problem, we have a baseline (although some of the basic variables are artificial).

The original simplex table is built.

37.constructing the index line in the artificial basis method

An initial simplex table is constructed, in which the index row is split into two lines, since the estimates consist of two terms. The top line contains the term of the estimate without M, in the bottom line - the coefficients at M. The sign of the estimate is determined by the sign of the coefficient at M, regardless of the magnitude and sign of the term without M, since M is a very large positive number.

Thus, to determine the vector that is entered into the basis, it is necessary to analyze the lower index row. If an artificial vector is derived from the basis, then the corresponding column in the subsequent simplex tables can be omitted if there is no need to obtain a solution to the dual problem (see the next topic).

After all the artificial vectors are deduced from the basis, the bottom row will have all zero elements, except for the estimates corresponding to the artificial vectors. They will be -1. Such a row can be removed from consideration and the further solution can be carried out by the usual simplex method, if there is no need to obtain a solution to the dual problem (see the next topic).

38. The criterion of optimality in the method of artificial basis. Sign of building the initial baseline plan of the original problem.

39. Algorithm of the dual simplex method

Algorithm of the dual simplex method:

1.The first simplex table is filled in the usual way, not paying attention to the signs of free members. It is believed that such a problem should have an initial unit basis.

2. Select the guiding line according to the largest in absolute value negative element of the column of free members A0

3. A guide column is selected according to the smallest absolute ratio of the index line elements to the negative elements of the guide line.

4. Recalculate the simplex table according to the rule of complete Jordanian exceptions

5. check the received plan for admissibility. A sign of obtaining a valid baseline plan is the absence of negative elements in column A0. If there are negative elements in column A0, then go to the second item. If they do not exist, then proceed to solving the resulting problem in the usual way.

6. The criterion of optimality of the usual simplex method is a sign of obtaining an optimal solution by the dual simplex method.

41. Open and closed transport models. Transition from an open transport model to a closed one.

Types of transport tasks.

There are m suppliers of homogeneous products with known stocks of products and n consumers of these products with given volumes of needs. The unit transportation costs are also known.

If the sum of the volumes of stocks of products is equal to the volume of needs of all consumers, then such a task is called closed transport task

(i.e., if ∑ Ai = ∑ Bj), otherwise the transport problem is called open... To solve the transport problem, it is necessary that it be closed.

An open transport task can be converted to a closed one as follows.

Let ∑Ai> ∑Bj. In this case, it is necessary to introduce a fictitious n + 1 consumer with the volume of needs ∑Ai - ∑Bj The unit costs of transportation from suppliers to a fictitious consumer are assumed to be 0, since in fact such transportation will not be carried out and some of the products will remain with the suppliers.

If ∑Bj> ∑Ai. In this case, it is necessary to enter a fictitious m + 1 supplier with an inventory volume Bj - ∑Ai. The unit costs of transportation from a fictitious supplier to consumers are assumed to be 0, since in reality such transportation will not be carried out and consumers will receive less of the products.

42. Methods for constructing the initial distribution in the transport problem: the method of the northwest corner and the method of the least element in the matrix.

Northwestern reception of building a reference plan. According to this method, the formation of traffic values ​​begins with s.-z. corner of the table, i.e. from cell x11. According to this technique, first of all, the goods of the first supplier are distributed. Moreover, the first supplier first satisfies the first consumer as much as possible. Then, if the supplier still has goods,

Least element method in a matrix.

The essence of the method lies in the fact that the maximum possible supply is always put into the cell, which corresponds to the lowest tariff of the matrix.

First, we make notes (for example, with the ▼ sign) in those cells of the lines in which the lowest price per line is observed. Then we go through the table column by column and make the same marks in the cells in which the lowest price is by columns.

Further distribution is done first, as much as possible, over the cells with two marks, then - with one, and then the task is rebalanced up to (m + n - 1) fillings. We organize the fillings by going through the table from left to right and from top to bottom.

43. Properties of transport tasks

The transport problem has some properties that can be reflected in the following theorems.

Theorem 1. A closed transport problem always has a solution.

Theorem 2. If the volume of stocks of products and the volume of needs are integers, then the solution to the transport problem will also be integer.

Theorem 3. the system of constraints of a closed transport problem is always linearly dependent.

It follows from this theorem that the distribution of a closed transport problem always has m + n - 1 basic variables and (m - 1) (n - 1) free time variables.

44. Degenerate distribution in transport problems, getting rid of degeneracy. The combination to be crossed out.

A distribution is called degenerate if the number of cells is less than m + n - 1.

45. Optimality theorem for the transport problem.

Theorem. If for some distribution of the transport problem you

the conditions are met:

but). ui + vj = сij for occupied cells

b) ui + vj ≤ сij, for free cells,

then this distribution is optimal.

The quantities ui are called row potentials, and the quantities vj are called column potentials.

46. ​​Potentials and methods of their calculation.

To find the potentials of rows and columns, the following reasoning is used, proceeding from condition a) of the optimality theorem.

Based on this condition, the number of equations is equal to m + n - 1, and the number of unknowns ui and vj is equal to m + n. So the number of variables is greater than the number of equations, and all equations are linearly independent. The solution of such a system of linear equations is uncertain, so one of the potentials must be assigned any value. In practice, ui = 0. a system of m + n - 1 equations with m + n - 1 unknown variables is obtained. This system can be solved by any method. In practice, to calculate the potentials, occupied cells are considered, for which one of their potentials is known, and proceeding from condition a) of the theorem, the values ​​of the remaining unknown potentials are calculated.

47. Calculation of estimates of the optimality of the distribution of transport problems and the criterion of optimality.

Based on the relation b) of the theorem, we can write the following formula for calculating the estimates: δ ij= ui + vj - сij. In order not to confuse estimates with traffic volumes, they (estimates) are enclosed in circles.

Estimates of optimality in free cells of TK are an optimality criterion, with the help of which the distribution is checked for optimality. If the estimates of all free cells are less than or equal to zero, then this distribution is optimal.

48. redistribution of supplies in the transport task

If the distribution is not optimal, then it is necessary to carry out a reallocation of supplies.

For redistribution, a recalculation cycle is built. The cell with the highest positive score is selected as a cell. This box is marked with a "+" sign, that is, it is necessary to write a certain amount of delivery into it. But then the balance for this column will be violated, therefore, one of the occupied cells of this column must be marked with a “-” sign, that is, the supply volume should be reduced by the same amount. But then the balance for this line will change, therefore, some occupied cell of this line must be marked with a "+" sign. This process continues until the "-" sign is placed in the line where the original cell was.

For any free cell, there is a recalculation cycle and, moreover, the only one.

49. chains of redistribution, their types.

Let the transportation plan under consideration be not optimal, i.e. there are positive relative ratings. Then an unfavorable cell (one of the unfavorable ones) is taken and a recalculation cycle is constructed for it, according to which the redistribution of the planned traffic is then done. The cycle is built in the form of a closed broken line, the segments of which run either along the column or along the line. In one of the corners of the broken line there is an unfavorable cell claiming to be a product, and in the other corners the cells are filled, i.e. when constructing a cycle, we start from the claiming cell and return to it along the broken line, but we can only make turns in the cells filled (corresponding to the basic variables). Let an unfavorable cell claim to be a product Q. To avoid an imbalance in the table, it is necessary in the transitions through the cycle in turn

add and subtract Q to the available shipments. Since there are an even number of corners, Q will be added in half of the cells, and in the other half it will be subtracted. The bypass of the cycle begins clockwise or counterclockwise from the claiming cell, placing the product Q there, then subtracting Q from the adjacent cell, then adding, etc. The value of Q itself is chosen so that one of the cells is empty, but none of the supplies becomes negative.

To do this, Q must be chosen equal to the smallest decreasing of the cells in which Q is subtracted. The following fig. 7.1 and 7.2 show examples of loops and the calculation rule.

This empties two cells. But it is necessary that only one cell becomes mutually empty. They do this: make one of the emptying cells empty in the new table, and put zero in the other emptying cell. This cell is considered basic (filled) in the new table.

50. The choice of the volume of redistribution.

Determination of the volume of transported products. When determining the volume of products moved through the recalculation cycle, we must proceed from the following two considerations:

a) after the transformation, negative numbers should not be obtained in the cells of the table;

b) one of the occupied cells must become free.

In order for these conditions to be fulfilled, it is necessary to choose the volume of transported products as follows: θ = min (хij) -, where (хij) are the volumes of traffic from the cells of the recalculation cycle, marked with "-".

θ = min (20; 30) = 20

Θ is added to the values ​​of the cells marked with "+". Θ is subtracted from the values ​​of the cells marked with "-". The supply value of the remaining cells is overwritten unchanged. As a result, we get the following table.

53. Algorithm of the method of potentials.

Algorithm:

1. Check if the task is running if not, then a fictitious supplier or consumer is introduced into the problem

2. The condition of the problem is written in the form of a transport table

3. An initial reference plan is built

4. Potentials of supply and consumption are determined

5. Estimates of free cells are calculated. If all of them are not negative, the plan is optimal and you need to write out the answer. Transportation matrix X and determine the amount of transportation costs. If the plan is not optimal, i.e. there are negative ones among the estimates, then choose the promising cell with the largest negative value. estimated and pass in magnitude to the next.

6. Load a perspective cell. Design a new reference plan in the form of a transport table. Go to step 4.

54. Accounting for production and transportation costs. Transport problem with delivery bans.

When solving some problems, it is necessary to take into account the costs not only for the transportation of goods, but also for the production of the transported products. To do this, in the matrix transp. tasks

Where Cij ’- reduced costs for the production of one unit of production.

Cij “- the cost of transporting one unit of production.

Problems with delivery bans.

In some situations, it is impossible to transport products along any route.

To do this, in the matrix of the transport problem, transportation through which is forbidden, a prohibitive tariff M. is put down, then the problem is solved in the usual way. However, this cell will always correspond to a negative score of the cell.

55. taking into account restrictions on the throughput of routes, taking into account the obligation of some deliveries in the transport task.

consideration of restrictions on the throughput of routes.

In some transport tasks, on some routes, less capacity is set than is necessary to meet the demand of the point of consumption.

taking into account the obligation of some deliveries in the transport task.

In some cases, the task requires that, for example, along the route Ak Bs, a delivery in the amount of A unit must be carried out. In this case, from the volume of production of point A and the volume of S Bs, the obligatory delivery is taken into account and the problem is solved with respect to the non-obligatory delivery. After obtaining the optimal solution, the supply is necessarily added to the volume standing in the cell Ak Bs.

56. Possible conclusions with econom. interpretation of the optimal distribution for open transport problems.

When obtaining the optimal distribution, it is necessary to return to the original problem and make the corresponding economical ones. conclusions. They are as follows:

1. if a consumption point is introduced, this means that the analyzed system has excessive production volumes, and it is possible, without prejudice to the system under consideration, to reduce the capacity of those production points by the amount of pegs that are tied to a fictitious consumption point.

2. If a fictitious point of production is introduced, then this means that the capacities of real points of production are not enough and they need to be increased. The capacities of those points of production that are closest to the points of consumption tied to a fictitious point of production are increasing. The power of the manufacturer is increased by the value of the binding. To do this, consider the column of the point of consumption, which is tied to a fictitious point of production, and find the lowest tariff in it. The capacity of the point of production corresponding to this tariff is most effectively increased by the value of the tie.

57. The concept of duality. Economic formulation of dual tasks on the example of the problem of optimizing the production plan.

The dual problem is an auxiliary linear programming problem formulated using certain rules directly from the conditions of the original, or direct problem.

Let there be a problem of optimizing the production plan. It looks like this:

Initial task:

a 11 x 1 + a 12 x 2 +… + a 1n x n ≤ b 1 | at 1

a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤w 2 | at 2

……………….. |.. (1)

but t 1 x 1 + a t 2 x 2 + ... + a t n x n ≤w 1 | at t

x j ≥0, j = 1, n (2)

z = c 1 x 1 + c 2 x 2 +… + c n x n -> max (3)

X = (x 1, x 2, ..., x n)

a ij - the number of raw materials of the i-th type, spent for the release of the j-th type of product

Dual task

Let the enterprise, for whatever reason, cannot produce products. In order to reduce downtime costs, an enterprise can sell the raw materials it has. At what prices do you need to sell raw materials?

i - the price of the i-type of raw materials available at the enterprise.

a 11 y 1 + a 21 y 2 + ... + a t 1 y t≥s 1

a 12 x 1 + a 22 y 2 + ... + a t 2 x n ≥s 2

……………….. (1’)

but 1p y 1 + a 2p y 2 + ... + a TP at t≥s P

for i ≥0, j = 1, m (2 ')

F = b 1 y 1 + b 2 y 2 +… + b m y m -> min (3 ')

58. Correspondence between the structural elements of direct and dual tasks

Each linear programming problem can be associated with

dual problem according to the following rules:

1. In all the constraints of the original problem, the free terms must

to the right, and terms with unknowns to the left.

2. The inequality constraints of the original problem must have signs,

directed in one direction.

3. If the objective function in the original problem is minimized, the inequality constraints should be written with the sign "≤", then in the dual problem the objective function will be minimized and the signs of the inequality constraints will be "≥".

4. Each constraint of the original problem corresponds to a variable in

dual task. If a variable corresponds to an inequality, it is non-negative, if to an equality, then a variable without restrictions on the sign ("arbitrary").

5. The coefficients of the variables in the constraints of the dual problem are obtained by transposing the matrix composed of

coefficients for the variables of the original problem.

6. The free terms of the original problem are the coefficients of

variables in the goal function of the dual problem, and free

terms in the dual problem are the coefficients of the variables in

function of the original problem. Note also that the duality relation is reciprocal, that is, the problem, dual to the dual, coincides with the original. Dual pairs of problems are subdivided into symmetric and asymmetric. In a symmetric pair, the constraints of the direct and dual problems are nonstrict inequalities and, therefore, the variables of both problems can take only non-negative values.

59. Construction of dual problems to the original problems written in the standard, canonical and general form of the model (construction of symmetric and asymmetric dual problems)

Standard form (original)

Σ a ij x j ≤ b i, i = 1, n (1)

x j ≥0, j = 1, n (2)

z = Σ c j x j -> max (3)

Dual standard

Σ a ij y i ≤ c j, j = 1, n (1)

y i ≥0, j = 1, m (2)

F = Σ b i y i -> min (3)

The original problem in canonical form:

Σ a ij x j = b i, i = 1, m (1)

x j ≥0, j = 1, n (2)

z = Σ c j x j -> min (3)

Dual canonical

Σ a ij y i ≤ c j, j = 1, n (1)

y i - any (2)

F = Σ b i y i -> max (3)

Let us give an economic interpretation of a pair of dual problems. Consider the problem of rational use of resources. Let the enterprise has resources b1, b2, ... bm, which can be used to produce n-types of products. Let also know the cost of a unit of the j-type of product cj (j = 1, n) and the rate of consumption of the i-th resource (i = 1, m) for the production of a unit of the j-th product - aij. It is required to determine the volume of production of each type of product xj ( j = 1, n) maximizing the total cost

f = c1x1 +… + cnxn (1)

In this case, the consumption of resources should not exceed their availability:

a11x1 +… + a1nxn<=b1 }

…………………….. } (2)

am1x1 +… + amnxn<=bm }

All known in their economic sense are non-negative:

Xj> = 0 (j = 1, n). (3)

Note that this problem forms a symmetric dual problem.

Asymmetric dual problems.

Let's take the LPP to its maximum in the canonical form:

Max Z = (n; j = 1) Σcj * xj

(n; j = 1) Σaij * xj = bi (i = 1, m)

Xj> = 0 (j = 1, n).

60 The main and second duality theorem (formulate theorems and explain)

First duality theorem.

Theorem: if one of the dual problems has an optimal design, then the other is solvable, i.e. has an opt.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. the objective function is unbounded on the set of plans, then in the dual problem the system of constraints is incompatible.

The second duality theorem and its economic interpretation.

For the feasible solutions of a pair of dual problems to be optimal, it is necessary and sufficient to satisfy the condition: xj * (∑aij yi * -cj) = 0, j from 1 to n, yi * (∑aij xj * -bi) = 0, I from 1 to m. These are conditions of complementary slackness. It follows from them: if any restriction of the dual problem turns into a strict equality by the optimal plan, then the corresponding component of the opt. plan of the dual task should be equal to zero. If some component of opt. plan is equal to zero, then the corresponding restriction of the dual problem turns into the strict equality xj *> 0 by the optical plan, therefore (i = from 1 to m) Σaij yi * = cj (cost of production = price) - If the product is included in opt.plan, then if costs> prices, production volume = 0 Σaij yi *> cj hence xj * = 0

yi *> 0 therefore (j = from 1 to n) Σaij xj * = bi (distribution of res = stock of res).

(j = 1 to n) Σaij xj *

The meaning of the theorem boils down to the following:

If the cost estimate of the cost of the consumption for the production of the product unit = the price, then this type of production is included in the optimal plan;

If the costs exceed the price, then the product should not be produced;

If the consumption of resources = stock, then the value of this resource is positive. Such a res is called a deficit. The most scarce.res-s has the highest score;

If the res-s is not fully consumed, then its cost estimate = 0.

61. Construction of the optimal support plan for the dual problem using the simplex table of the original problem

Information from the columns of the inverse matrix of linear transformations leading to the optimal result. The columns of matrix D-1 provide some very useful information.

Column A3: the “shadow” price of resource S2 is equal to y01 = 0, the column remains

single and from the first line you can read that x3 = 9, i.e. when the found optimal plan is implemented, the 1st resource will be in excess, and this excess (underutilization) will just amount to 9 conventional units.

Column A4: the “shadow” price of the resource S2 is equal to y02 = 1, the resource will be fully used and its possible increase will lead to an increase in the objective function (ie income). And since y02 = 1, then an increase in the resource S2 by 1 c.u. will give an addition to income by.Z = y02 · .в2 = = 1.1 = 1 (thousand UAH) (here. в2 is the resource increment S2 and.Z is the corresponding income increment). With such an increase in the resource S2, the maximum income will already be Zmax = 58 thousand UAH. + 1 thousand UAH = 59 thousand UAH In fig. 6.2 illustrates this situation, commentary on which will be given below. From column A4 it also follows that with an increase in resource S2 by 1 c.u. for the new optimal point, the output of goods T1 will decrease by ½ ton (at the intersection of the row with the basic variable x1 and column A4, there is “-1/2”), and the output of goods T2 will increase by 3/2 ton (because in the row with the basic variable x2 in column A4 we have "3/2"). What has been said on column A4 will be commented below with the help of graphical constructions (Fig. 6.2). Column A5: the "shadow" price of the resource S3 is equal to y03 = 2. This means that an increase in the resource S3 by 1 c.u. will bring an addition in Z to.Z = y03 · .v3 = 2.1 = 2 (thousand UAH) and will amount to Zmax = 58 thousand UAH. + 2 thousand UAH = 60 thousand UAH Moreover, as follows from the column A5 of the table. 3, T1 output will increase by ½ ton and T2 will decrease by ½ ton. The stock of raw materials S1 (see 1st line) will increase by 3/2 c.u.

62. The idea of ​​the dynamic programming method and its geometric interpretation. Bellman's optimality principle.

The optimal solution to the problem by the dynamic programming method is found on the basis of the functional equation

To determine it, you must:

1.write the functional equation for the last state of the process (it corresponds to l = n-1)

fn-1 (Sl-1) = optimum (Rn (Sn-1, Un) + f0 (Sn))

2. find Rn (Sn-1, Un) from a discrete set of its values ​​for some fixed Sn-1 and Un from the corresponding admissible regions (since f0 (Sn) = 0, then f1 (Sn-1) = optimum (Rn ( Sn-1, Un)

As a result, after the first step, we know the solution Un and the corresponding value of the function f1 (Sn-1)

3. Decrease the value of l by one and write down the corresponding functional equation. For l = n-k (k = 2, n) it has the form

fk (Sn-k) = optimum (Rn-k + 1 (Sn-k, Un-k + 1) + fk-1 (Sn-k + 1)) (2)

4. find a conditionally optimal solution based on the expression (2)

5. check what the value of l is. If l = 0, the calculation of conditionally optimal solutions is completed, and the optimal solution to the problem for the first state of the process is found. If l is not equal to 0, go to step 3.

6. Calculate the optimal solution to the problem for each subsequent step of the process, moving from the end of the calculations to the beginning.

The dynamical program method allows one problem with many variables to be replaced by a number of sequentially solved problems with fewer variables. The solution is carried out in steps. The main principle on which the optimization of a multistep process is based, as well as the features of the computational method, is the Bellman optimality principle.

Optimal behavior has the property that whatever the initial state and the initial solution are, subsequent solutions must be optimal with respect to the state obtained as a result of the initial solution.

Mathematically, it is written as an expression of the form:

fn-1 (Sl) = optimum (Rl + 1 (Sl, Ul + 1) + fn- (l + 1) (Sl + 1)) (1)

(l = 0, n-1) Optimum in expression means maximum or minimum depending on the problem condition.

63. Requirements for the problems solved by the DP method

Dynamic programming is a mathematical method for finding optimal solutions to multistep problems. A multi-step process is a process that develops over time and breaks down into a number of steps, or stages.

One of the features of the dynamic programming method is that the decisions made in relation to multistep processes are considered not as a single act, but as a whole complex of interrelated decisions. This sequence of interrelated decisions is called a strategy. The goal of optimal planning is to choose the strategy that provides the best result in terms of a predetermined criterion. This strategy is called optimal.

Another important feature of the method is the independence of the optimal decision taken at the next step from the prehistory, i.e. how the process being optimized has reached its current state. The optimal solution is chosen only taking into account the factors that characterize the process at the moment.

The method of dynamical programs is also characterized by the fact that the choice of the optimal solution at each step should be made taking into account its consequences in the future. This means that while optimizing the process at each individual step, in no case should you forget about all subsequent steps.

64. Economic formulation and construction of a mathematical model of the problem solved by the DP method (for example, the problem of the distribution of capital investments). Bellman recurrence relation.

Let us first explain that the dynamic programming method is applied primarily to those problems in which the process (or situation) being optimized unfolds in space or time, or in both.

Let the process (situation) itself be so complicated that there is no way to optimize it using known methods. Then, according to the method of dynamic programming, a COMPLEX process (operation, situation) is divided (divided) into a number of stages (steps). This breakdown is in many cases natural, but in general it is artificially introduced. . For example, when considering a game of chess, any move of each of the players just serves

breakdown of the whole batch into separate steps (stages). And in a military operation to pursue one missile with another, the entire continuous process has to be artificially divided into stages, for example, every second of observation. The dynamic programming method allows the optimization of the entire complex process to be replaced by conditional optimization for each of the stages

(steps) followed by the synthesis of optimal control of the entire process. In this case, the method provides that conditional optimization at a separate step (stage) is done in the interests, first of all, of the entire operation.

All calculations that make it possible to find the optimal value of the effect achieved in n steps, fn (S0), are carried out according to formula (1), which is called the basic functional Bellman equation or recurrence relation. When calculating the next value of the function fn-1, the value of the function fn- (l + 1) obtained at the previous step, and the direct value of the effect Rl + 1 (Sl, Ul + 1), achieved as a result of the choice of the solution Ul + 1 for a given state systems Sl. The process of calculating the value of the function fn-1 (l = 0, n-1)

It is carried out under the natural initial condition f0 (Sn) = 0, which means that outside the final state of the system, the effect is zero.

65. The problem of the distribution of capital investments (example).

To solve the problem of the optimal distribution of investments, we will use the Bellman functional equation. First, using the simplest situation, we illustrate the derivation of the Bellman functional equation, and then, using an example, we will prove how to use this equation to solve the problem of interest to us.

Let's start with the optimal distribution of the allocated capital investment in the amount of K between the two enterprises. The planning departments of enterprises, on the basis of their calculations, formed the income functions q (x) for enterprise P1 and h (x) - for enterprise P2. These functions mean that if the first or second enterprise receives an investment of x, then the first enterprise

income q (x) will be received, and the second will be h (x), and the value x can take continuous or known discrete values ​​from 0 to K.

So, let the company P1 allocated capital investments in the amount of x, then the company P2 is allocated the amount of K - x. In this case, income q (x) will be received from the first enterprise, and h (K - x) from the second. If investments K were allocated for one planning period, then the total income from the two enterprises will be R (K, x) = q (x) + h (K - x). Obviously, x and, accordingly, K - x must be chosen such that R (K, x) takes its maximum value, which we denote by F (K):

This record is like a skeleton for more complete records.

functional Bellman equation. LET'S COMPLICATE our task by distributing capital investments over two planning periods (two stages) . Let it be initially decided to allocate the sum x to the first enterprise P1, and to the second K - x. In general, the income would be equal to R (K, x) = q (x) +

h (K - x). If we keep in mind that investments are distributed over 2 periods (2 stages), then in the first enterprise the remainder of investments will be .x, where, and on the second -. (K - x), where Accordingly, the income for the second period will be q ( .x) - for the first enterprise and h [. (K - x)] - for the second. Dynamic programming optimization usually starts at the back end. Therefore, we will start from the second stage, denoting F1 the maximum possible income from two enterprises in the second

stage. We get

Then, to the last considered (in our case, the second) stage, we sort of add the previous (we have the first) stage and find the maximum income from the two stages together:

Similarly, for n stages, we obtain

where Fn-1 is the objective function that gives the best result in the last (n - 1) stages. The resulting functional Bellman equation is of a recurrent nature, i.e. associates the Fn value with the Fn-1 value.

More generally, the Bellman equation has the form

where, Fn-1 is the maximum income for (n - 1) last stages, Fn is

maximum income for all n stages.

66. The concept of solving nonlinear programming problems

Let the nonlinear programming problem be posed in the following general form: find such values ​​of the variables x1, x2, ..., xn that meet the conditions:

and bring the required extremum (maximum or minimum) of the objective function

f = f (x1, x2, ..., xn), (13.2)

where f (x1, ..., xn) and qi (x1, ..., xn) (m, 1 i =) are real nonlinear,

regular functions of n real variables.

By their general properties, nonlinear programming problems can

differ significantly from linear ones. For example, the region of feasible solutions may already be non-convex, and the extremum of the objective function can be observed at any point in the feasible region. Methods for solving nonlinear problems also differ significantly. Let's consider only some approaches to solving these problems.

First of all, a graphical approach is also valid for solving the simplest problems of nonlinear programming. So, if the arguments of the problem are variables x1 and x2, then first on the plane of these variables the region of feasible solutions is constructed, and then using the levels of the objective function f (x1, x2) the optimal point in the region is determined.

In nonlinear programming, a gradient approach is used to solve many problems. There are a number of gradient methods, the essence of which is to find the optimal result using the gradient of the objective function - a vector indicating the direction of maximum increase in the goal for the point under consideration. In the general case, the search procedure is performed in an iterative mode from the initially selected point to the points with the best index. For example, let. - area of ​​feasible solutions

of the problem under consideration, and the iterative process of calculations starts from the point

Further, first, a transition is made along the gradient of the objective function, and then a return to the region. along the gradient to the disturbed boundary of the O2 O3 region. 13.3 shows that Ai with odd indices belong to the region., And points Ai with even indices do not belong. As we approach the optimal point Q, the directions of the working gradients converge. Therefore, the ideal criterion for stopping the process will be the collinearity of the target gradient and the gradient of the broken boundary.

67. The concept of parametric and integer programming .

Formulation and mathematical model of ZTsLP.

In problems with indivisible objects, integer conditions are imposed on variables. Sometimes these conditions apply to all variables, sometimes to some of the variables. Consider a fully integer problem

f = (n, j = 1) ∑CjXi max

(n, j = 1) ∑AijXj = bi, i = 1, m

xi-integer, j = 1, n

Now, unlike the general linear programming problem, the optimal plan will not necessarily be at the top of the plan polyhedron. There are the following methods for solving integer problems:

1 clipping methods

2.Combinatorial

3. Approximate methods.

Parametric programming is a section of mathematical programming devoted to the study of optimization problems in which the admissibility conditions and the objective function depend on some deterministic parameters.