The simplest are the so-called linear deterministic models. They are given in the form of a linear form of control variables ( X):

W = a 0 + a 1 x 1 + … + a k x k

under linear constraints of the form

b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ b j , j = 1,…, q 1 ;

c 1 j x 1 + c 2 j x 2 + … + c kj x k = cj , j = 1,…, q 2 ;

d 1 j x 1 + d 2 j x 2 + … + d kj x k £ dj , j = 1,…, q 3 .

Total number of restrictions m = q 1 + q 2 + q 3 may exceed the number of variables (m> k). In addition, the condition of positivity of variables ( x i ³ 0).

The response surface for the linear model is hyperplane. For example, consider a linear two-variable model of the following form:

W=–2x 1 –3x 2 (2.2)

under the following restrictions

(2.3)

2x 1 + 3x 2 £18;

x 1 – 4x 2 £4;

–2x 1 + x 2 £2;

X 1 ³ 0; x 2 ³ 0.

Valid range (scope of definition) OABCD for model (2.2) is formed by constraints (2.3) (Fig. 2.2). The response surface is a flat polygon OA"B"C"D"(Fig. 2.2, b).

For a certain constraint relation, the set of feasible solutions may be absent (empty). An example of such a set is shown in Fig. 2.3. Direct AU And sun limit the range of allowable values ​​from above. The third constraint cuts off the region of admissible values ​​below from the straight line AB. Thus, there is no common area that satisfies all three constraints.

Linear models are quite simple and therefore, on the one hand, they imply a significant simplification of the problem, and on the other hand, they allow the development of simple and effective solution methods.

In the study of DLA, linear models are used rarely and almost exclusively in the approximate description of problems.

Linear models can be used for step-by-step approximation of non-linear models (linearization of the problem). This technique is especially effective when studying small areas of the studied space. The representation of individual sections of the nonlinear response surface by a linear model underlies large group optimization methods, the so-called methods with linear tactics.

The study of linear models is not difficult. In particular, the influence of each of the variables on the characteristics of the model of the form

W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k

is given by its coefficients:

, i = 1,…, k.

To find the optimum of the linear model W opt developed an efficient simplex method.

The simplest cost models, considered as a set of costs incurred, are sometimes reduced to linear ones.

An example of such a model is the classic transportation cost model (transport problem)(Figure 2.4).

Available k production points
(i = 1,…, k) And m consumption points
(j = 1,…, m) of some product. The amount of product produced in each k points of production, a i; the amount of product needed in each m consumption points, b j.

The equality of total production and consumption is assumed:

Quantity of product transported from i-th point of production in j-th point of consumption, equal to xij; the cost of transporting a unit of this product - with ij.

Total cost of transportation WITH S is given linear model:

under the following restrictions

Linear models also include models in the form of linear differential equations (ordinary or partial derivatives).

Linear ordinary differential equation n th order has the form

The initial conditions are written as

A linear partial differential equation has the form

The model, given as a partial differential equation, includes initial and boundary conditions (conditions on the boundary of the domain of definition of the function F( t)).

2.3. Study of the simplest mathematical model
operation of a gas turbine engine

The gas turbine engine (GTE) is the main power plant of modern aircraft.

The GTE scheme has the form shown in Fig. 2.5.

Here 1 – inlet diffuser; 2 - compressor; 3 - the combustion chamber; 4 – turbine;
5 - outlet nozzle.

The GTE work cycle includes the following stages:

1) Oncoming with speed V air flow through the diffuser enters the compressor.

2) The compressor, rotating on the same shaft with the turbine, compresses the air that enters the combustion chamber.

3) Fuel (kerosene) is constantly injected into the combustion chamber, which is mixed with compressed air.

4) The gas generated from combustion enters the turbine, which accelerates it to a speed W.

5) At this speed, the gas is ejected through the nozzle into the atmosphere.

Due to the fact that W > V, traction force is generated R, which allows the aircraft to fly in the atmosphere.

The change in traction force is carried out by changing the rate of fuel injection into the combustion chamber by moving the engine control knob (THROT). The movement of the throttle to a certain angle d of the throttle is carried out either manually by the pilot, or with the help of an actuator according to signals from the ACS in flight. An increase in the value of d thrust causes an increase in force R, and a decrease is a decrease in this force.

GTE is complex technical system, in which a significant number of physical and chemical processes take place. The engine is equipped with all kinds of automation devices, systems for turning and cooling turbine blades, etc. Naturally, the mathematical description of the functioning of the gas turbine engine will also be quite cumbersome, including systems of differential equations in partial derivatives, ordinary differential equations, transcendental functions, algorithms digital system engine control. Such models are used in the process of designing gas turbine engines.

To solve the problems of flight control, more than simple model GTE, which is the dependence of the thrust force R from the angle d of the throttle deviation of the throttle. The process of changing the thrust force is described by an ordinary differential equation of the form:

, (2.11)

where t > 0 is the time constant of the engine, which depends, in addition to design characteristics also on the ambient temperature, its humidity and other external factors; k[kg/deg] – coefficient of proportionality.

The initial condition for equation (2.11) is written as

R(0) = R 0 . (2.12)

Thus, equation (2.11) together with the initial condition (2.12) is the simplest mathematical model of the gas turbine engine, written in the form of an ordinary differential equation 1-th order.

To determine the proportionality factor k calibration curves of the dependence of thrust on the angle of rotation of the throttles, built on the basis of experimental data, are used. The tangent of the slope of the graph is equal to the desired coefficient.

Integration of equation (2.11) with the initial condition (2.12) makes it possible to find out how the thrust force changes over time (Fig. 2.6).

When the throttle is deflected, the thrust R increases and then stabilizes at a certain limit value, i.e. GTE is an inertial object.

Thrust limit we obtain from (2.11) when the rate of its change is equal to zero:

. (2.13)

Rise time depends on the value of the motor time constant t. The process is considered to be steady when t = t mouth, when the thrust enters the so-called five percent corridor of the limit value of the thrust force (Fig. 2.6). The larger t, the more inertial the engine and, consequently, the more t mouth

On fig. 2.7 shows the behavior of the thrust force depending on the throttle deflection angle at t = 0.5.

The thrust force during takeoff, when the throttle is deflected by 10°, reaches a steady state in the third second and reaches a value of 3390 kg. Ten seconds after takeoff, when the throttle is deflected 20°, the thrust force is set to 6780 kg, and another ten seconds later, when the throttle is deflected 30°, the thrust force is set to 10170 kg. The limiting value of the traction force is
14270 kg.

Similar information.

3.1. General task linear programming

Linear programming- this is the most developed section of mathematical programming, with the help of which the analysis and solution of extremal problems with linear connections and restrictions are performed.

Linear programming includes a number of heuristic (approximate) solution methods that allow, under given conditions, from all options solutions to production problems to choose the best, optimal. These methods include the following - graphical, simplex, potential method (modified distribution method - MOD), Khichkov, Kreko, Vogel approximation method and others.

Some of these methods are united by a common name - the distribution, or transport, method.

The birthplace of linear programming is Russia. The first works on linear programming by the future academician L.V. Kantorovich were published in 1939. In 1975, he received the Nobel Prize in Economics for the development of linear programming methods. Since most of the works of Academician L.V. Kantorovich is devoted to solving transport problems, it can be considered that the mentioned Nobel Prize also marks the merits of Russian transport science.

In road transport, linear programming methods have been used since the 1960s to solve a large number of the most important production problems, namely: reducing the distance of cargo transportation; drawing up an optimal transportation scheme; selection of the shortest routes of movement; tasks of transportation of different, but interchangeable cargoes; shift-daily planning; planning of transportation of small batch cargoes; distribution of buses along routes and others.

The features of the linear programming model are as follows:

The objective function and constraints are expressed linear dependencies(equalities or inequalities);

The number of dependencies is always less than the number of unknowns (uncertainty condition);

Non-negativity of the required variables. The general form of writing a linear programming model in abbreviated form is as follows:

Find X ij ≥ 0 (j = 1, 2…n) under the following type of constraints:

These constraints minimize (or maximize) the objective function

The standard form of writing a linear programming model is a system of linear equations written in canonical form, i.e. in the form of linear equalities, in non-negative numbers:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

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

a m x 1 + a m 2 x 2 + ...+ a mn x n = b m ..

If the model is written in the form of inequalities in non-negative numbers, i.e., it has the form

a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

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

a m x 1 + a m 2 x 2 + …+ a mn x n ≤ b m ,..

then this entry is reduced to canonical form (3.1) by introducing additional variables x n +1> 0 (i=1,2…m) to the left side of the inequality (or reduction of the number of variables if the inequality sign is directed in the opposite direction). Additional variables form the basis.

The standard form of solving a linear programming problem is to find solutions to a system of linear equations in non-negative numbers that minimize the objective function. The objective function then has the form

L = c 1 x 1 + c 2 x 2 ... c n x n → min, (3.3)

Where s 1 , s 2 … s n are objective function coefficients L with variables X j .

Additional variables enter the objective function with zero coefficients.

In the case of maximizing the objective function L the signs of the variables of the objective function should be reversed, and we will again come to the minimization problem, i.e. one task is reduced to another substitution L on - L or max L=min(- L).

A basic solution of a system of linear equations (3.1) is a solution in which zero values ​​are given to non-basic variables.

A basic solution is called admissible in which the variables included in the basis are non-negative.

An admissible solution that maximizes (or minimizes) the objective function (3.3) is called optimal.

Each linear programming problem corresponds to another, called the dual linear programming problem. The original problem with respect to the dual one is called the direct problem. The primal and dual problems form a pair, called the dual pair in linear programming. The primal and dual pair form an asymmetric pair when the primal problem is written in canonical form, and a symmetric pair when the conditions of the problems are written as inequalities.

The rules for compiling a mathematical model of a dual problem are based on the rules of matrix calculus.

The concept of duality is widely used in the analysis of linear programming problems. The property of duality is considered in detail in each particular case.

3.2. Graph-analytical method

Graph-analytical method is one of the simplest methods of linear programming. It clearly reveals the essence of linear programming, its geometric interpretation. Its disadvantage is that it allows you to solve problems with 2 or 3 unknowns, i.e., it is applicable to a narrow range of problems. The method is based on the rules of analytical geometry.

Solving a problem with two variables x 1 And x 2, which, according to the meaning of the problem, should not be negative, is performed in the system of Cartesian coordinates. Equations x 1=0 and x 2= 0 are the axes of the coordinate system of the first quadrant

Let's consider the solution method using a specific example.

Example 3.1. There are 300 tons of foam concrete products and 200 tons of steel products in stock. The auto enterprise needs to deliver these products to the facility under construction. The car company has trucks KAMAZ - 5320 and

ZIL-4314. For one trip, KamAZ-5320 can deliver 6 tons of foam concrete and 2 tons of steel, and the profit from the trip will be 4 thousand rubles. ZIL-4314 delivers 2 tons of foam concrete and 4 tons of steel in one trip, the profit from the trip is 6 thousand rubles. It is necessary to organize transportation in such a way as to provide the auto enterprise with the greatest profit.

Let us construct a mathematical model of the problem. Denote by x 1 the desired number of trips KamAZ-5320 and through X 2 required number of ZIL-4314 riders.

The total transportation in tons of foam concrete products is 6 x 1+ 2x 2, and from steel 2 x 1+ 4x 2. The shipping limit, based on the number of items available, is 6 x 1+ 2x 2 ≤ 300t for foam concrete and 2 x 1+ 4x 2 ≤ 200t for steel.

Total profit in thousand rubles. expressed as 4 X 1 + 6X 2 , which needs to be maximized and which is the optimality criterion in the problem under consideration. The mathematical model of the problem thus looks like the following. It is necessary to maximize the objective function

L = 4x 1+ 6x 2 → max under conditions: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Consider Equation 6 x 1+ 2x 2 = 300. To construct a line described by this equation, we find two points lying on this line. At x 1= 0 from the equation of a straight line we find 2 x 2 = 300, whence x 2 \u003d 150. Therefore, point A with coordinates (0.150) lies on the desired line. At x 2= 0 we have 6 x 1\u003d 300, from where x 1 \u003d 50, and the point D with coordinates (50,0) is also on the desired line. Draw a line through these two points AD(Fig. 3.1).

Linear inequality 6 x 1+ 2x 2 ≤ 300 is a half-plane located on one side of the constructed line 6 x 1+ 2x 2 = 300. To find out on which side of this line the points of the desired half-plane are located, we substitute into inequality 6 x 1+ 2x 2 ≤ 300 coordinates of some point not lying on the boundary line. For example, the origin is 0-(0,0). It satisfies the inequality 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD and in fig. 3.1 is shaded.

Equation 2 x 1+ 4x 2= 200 will be constructed from two points. At x 1 = 0 4x 2 = 200 from where x 2 = 50. Then point E has coordinates (0,50) and belongs to the required line. At x 2= 0, 2x 2 = 200 dot With is on the given line with coordinates (100,0). Substituting into the inequality the coordinates of the point With(0,0), we get 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

The task constraint system requires that plans ( x 1; x 2) satisfy all four inequalities, i.e., admissible designs are points ( x 1; x 2) must simultaneously be in all four half-planes. This requirement is met only by points located inside and on the border of the polygon. OEKD, which is the polygon of admissible solutions.

The vertices of the polygon of feasible solutions are the points O, E, K, D line segments OE, EK, KD, OD- his ribs. Any point of the polygon OEKD is the plan of the task, satisfying all its conditions. The vertices of the polygon are formed by the intersection of two straight lines and correspond to the basic plans of the problem, among which is the best (optimal) plan. Thus, there will be as many base plans as there are vertices in the polygon of feasible solutions.

A visual geometric representation can also be obtained for the objective function L = 4x 1+ 6x 2. We fix some value of the objective function, for example L= 120. equation 4 x 1+ 6x 2 = 120 defines a line passing through a point IN with coordinates (x 1 \u003d 0; x 2 \u003d 20) and a point L with coordinates (( X 1 = 30; X 2 = 0). Line segment BL lies inside the polygon OEKD. Therefore, for all plans (points) of this segment, the value of the objective function is the same and equal to 120. Giving other values ​​of the objective function, we obtain parallel lines, which are called level lines target function.

Moving the line L parallel to itself in one direction, we get an increase in the objective function, and in the opposite direction - its decrease. In this example, the movement of a straight line BL to the right determines the increase in the objective function that we are maximizing. We do this until the line BL will have at least one common point with the polygon of admissible solutions OEKD. From fig. 3.1 it follows that the last point that the straight line of the level of the objective function intersects will be the point TO. This means that the point TO determines the optimal task plan.

The direction of increase perpendicular to the level line is called direction of greatest increase objective function and determines its maximum gain. This direction can be set without drawing level lines. For this, it is necessary on the axes x 1 And x 2 set aside segments equal to the coefficients of the objective function, and using them, as in coordinates, construct a vector of the greatest increase in the objective function. In mathematics it is called gradient and denoted by the sign grad. Gradient for a feature L = 4x 1 + 6x 2 will vector n| 4; 6 | . For the convenience of its construction, we increase the coordinates, for example, by 10 times, i.e. n | 40; 60 | . Let's construct the gradient of the objective function L, for which we connect the point with coordinates (40; 60) with the origin. The objective function level lines are drawn perpendicular to the direction of the gradient.

So, in one way or another, it is established that the point TO determines the optimal task plan, the values ​​of the variables of which correspond to the coordinates of the given point. To establish the coordinates, it is necessary to solve the system of equations of the straight lines that form this vertex:

6x 1+ 2x 2= 300;

2x 1+ 4x 2= 200.

We equalize the coefficients at x 1 by multiplying the second equation by 3, and subtract the first from the second equation. Let's get 10 x 2= 300,x 2 = 30. Substituting the value x 2 \u003d 30 into any of the equations, for example, into the first, we determine the value X 1:

6x 1+ 2X · 30 = 300,

whence 6 x 1 = 300 - 60 = 240, therefore, x 1 = 40.

Thus, in order to get the most profit for a car company, it is necessary to complete 40 trips to KamAZ-5320 and 30 trips to ZIL-4314. The maximum profit in this case will be

L = 4x 1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 thousand rubles.

Based on the considered example and the geometric interpretation of the optimization problem with two variables, we can draw the following conclusions:

1) in two-dimensional space, the area of ​​feasible solutions is a polygon;

2) each side of the polygon corresponds to the value of one variable equal to zero;

3) each vertex of the polygon of admissible solutions corresponds to the values ​​of two variables equal to zero;

4) each value of the objective function corresponds to a straight line;

5) the optimal solution of the problem corresponds to the vertex of the polygon, in which the objective function acquires the optimal value, while the optimal variables are the coordinates of this vertex.

In the general case, optimization problems have a similar geometric interpretation. The set of task plans will be a polyhedron whose vertices correspond to the reference plans. When solving the problem, the transition from one vertex of the polyhedron to another with a large value of the objective function is carried out until its optimal value is obtained. Note that the efficiency of optimization methods lies precisely in the fact that the enumeration of vertices (iteration) is carried out only in the direction of the greatest increase in the objective function. Therefore, not all vertices are considered, of which there are a huge number, but only those that are closer to the extreme one.

When determining a class of optimization problems and choosing a method for solving it, it is necessary to know whether the set of feasible solutions is convex or non-convex, a linear or non-linear objective function.

By definition, a set is called convex if for any two points the entire segment connecting these points belongs to this set. Examples of convex sets are, for example, a segment (Fig. 3.2, a), a plane in the form of a circle, a cube, a parallelepiped, as well as polygons that are entirely located on one side of each of its sides, etc.

On fig. 3.2b shows non-convex sets. In non-convex sets, one can indicate at least two points of the segment AB that do not belong to the set under consideration.

3.3. Simplex method

Simplex method is a common method for solving linear programming problems. The method got its name from the word "simplex", denoting the simplest convex polygon, the number of vertices of which is always one more than the dimension of the space. The simplex method was developed in the USA by the mathematician J. Dantzig in the late 1940s.

The simplex method includes obtaining a non-negative basic solution of a system of canonical linear equations of type (3.1), subsequent minimization (maximization) of the objective function (3.3) and, in this way, finding the optimal values ​​of the required variables x 1, x 2… x n.

The idea of ​​the simplex method lies in the fact that in the course of the calculation one sequentially passes from the first basic solution to the second, third, etc. through the so-called simplex transformations. Transformations are made in the form of simplex tables, which greatly simplifies and speeds up calculations.

To obtain non-negative basic solutions of a system of linear equations, it is necessary to conduct the process of eliminating unknowns in such a way that the free terms of the equations remain non-negative at all stages of the process. In this case, one should be guided by the following rule: any free variable for which there is at least one positive coefficient is taken as a new basic variable; a variable is derived from the basis, which corresponds to the smallest ratio of the free terms of the equations to the corresponding positive coefficients of the equations with the variable introduced into the basis. Such transformations are called simplex converters.

This is very important, because in order to find a particular non-negative solution that corresponds to the largest possible value of one free variable with zero values ​​of other free variables, instead of determining the range of the specified variable and substituting its largest possible value into common decision it suffices to take this variable as the basic one and subject the system to a simplex transformation, passing to a new basis, which greatly simplifies the calculations.

Calculations are conveniently performed using simplex tables. The transition from one table to another corresponds to one iteration, i.e., the transition from one basis to another, while the value of the objective function decreases. For a certain number of iterations, they pass to the basis for which the optimal (minimum or maximum) value of the objective function is obtained. Let us consider the simplex method in general form.

The general task of linear programming is to minimize (maximize) the objective function, the variables of which are interconnected by a system of linear equations, subject to the non-negativity condition.

Let it be necessary to minimize the linear form

L = c 1 x 1 + c 2 x 2 + ... c n x n.

Under the following conditions (for clarity, zero and unit coefficients are kept in the equations):

1x 1+ 0x 2 + ... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

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

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

This system of equations already has a ready-made basis, since each constraint equation contains an unknown with a coefficient equal to one, which is not in other equations, i.e., from the coefficients of the variables X 1 , X 2 …, x m you can create an identity matrix.

Let's solve the equations for the basic variables:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

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

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

and we will express the objective function in terms of free variables, substituting into it, in place of the basic variables, their expressions in terms of free variables:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Variables x 1, x 2 ..., x m, with the help of which the first basic plan is found, are basic, and the rest x m +1 , x m +2 ,…x n – free. There should always be as many basic variables as there are equations in the system. Based on the non-negativity condition, the smallest value of free variables is equal to zero. The resulting basic solution of the system of equations is its initial feasible solution, i.e. x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

This solution corresponds to the value of the objective function

L = c 1 b 1 + c 2 b 2 + ... c m b m.

The initial solution is checked for optimality. If it is not optimal, then by introducing free variables into the basis, the following feasible solutions are found with a smaller value of the objective function. To do this, a free variable is determined that must be entered into the basis, as well as a variable that must be removed from the basis. Then they move from the previous system to the next equivalent system. This is done using simplex tables. The solution of the problem continues until the optimal value of the objective function is obtained.

Simplex tables are compiled as follows (see Table 3.1). Place all variables at the top of the table X 1 , X 2 …, x n and coefficients cj, with which the corresponding variables are included in the objective function. First column c i consists of the coefficient of the objective function for the variables included in the basis. This is followed by a column of basic variables and free terms of the equations. The elements of the remaining columns of the table are the coefficients of the variables with which the latter enter the system of equations. Thus, each row of the table corresponds to the equation of the system, solved with respect to the basic variable. The table also shows a variant of the plan that corresponds to the objective function for a given basis.

The bottom row of the table is called index. Each of its elements (estimate) ∆ j determine

∆j = z j – c j ,

Where cj are the coefficients for the corresponding variables in the objective function; zj – the sum of the products of the coefficients of the objective function with basic variables and the corresponding variables - elements j-th column of the table.

Table 3.1

Simplex table with initial valid

1.

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

Mathematical models allow you to determine the optimal values ​​of unknown parameters economic systems which is important in the decision making process. Mathematical programming just provides an apparatus that allows you to optimize the selection process the best options plans in the management process in economic systems.

Used in mathematical statistics, optimization methods, economic methods. cybernetics, experimental problems.

When studying complex processes and phenomena in the economy, modeling is 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 temporal and spatial scale. A model is a specially created object with the help of which quite certain characteristics of the system under study are reproduced in order to study it. Math modeling is the most perfect and at the same time effective method of obtaining information about the object under study. It is a powerful tool for analysis in economics. The results of research using models will be of practical interest when the constructed model is sufficiently adequate to the phenomenon under consideration, i.e. well enough to reflect the real situation.

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

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

Mathematical programming includes a number of sections, the main of which are the following:

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

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

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

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

5. Stochastic programming. This section includes tasks 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 an extremum, since in mathematical programming problems the objective function reaches its extreme value at the boundary of the region of acceptable values ​​of unknown variables, and derivatives do not exist at the boundary points. A complete enumeration of admissible 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 economic processes and phenomena are called economic and mathematical models

Models are divided into:

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

2. non-linear, in which there are nonlinear relations;

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

4. deterministic, which take into account the average 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(for the entire household)

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 statement of problems of mathematical programming.

Consider the general statement of the problem of mathematical programming.

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 change 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 company 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. The raw materials of each type in the enterprise are limited. The company receives a certain profit from the sale of a unit of production. It is necessary to find such a production plan in which the enterprise will receive the maximum total profit.

Mathematical setting:

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

i - index of resource type i = 1, m

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

Аi is a given limit on the available volume of resources of the i-th type;

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

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

z \u003d 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 task 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.) is known per feed unit of each species. For proper nutrition of animals, it is necessary to consume nutrients not less than the specified amounts. The unit cost of each feed is known. It is necessary to determine the diet of animal feeding, in which the total cost of fattening will be minimal.

Mathematical setting:

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

i – nutrient type index, i = 1, m

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

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

Let's introduce unknown variables:

хj - daily volume of animal feeding j-th view stern.

In terms of the introduced notation given task will be written next

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

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

am1x1 + am2x2 +…+ and mnxn ≥Am

xj ≥ 0, j = 1, n

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

Economic setting :

Available m suppliers of homogeneous products and n consumers of this product. Known unit costs for the delivery of a unit of production from each supplier to each consumer. 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 set parameters:

j – consumer index, j = 1, n

i – supplier index, i = 1, m

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

Bj - the volume of demand for the products of the j-th consumer;

Cij is the unit cost of transporting a unit of product 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

Task restrictions.

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 write the mathematical statement in a folded form:

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

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

Economic setting :

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

Mathematical setting .

Let us introduce the notation for the given parameters.

i – index of works, i = 1, m

j is the index of performers, j = 1, n

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

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

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

0 - otherwise.

In terms of the introduced notation, this problem can 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. restriction group.

Each executor can perform only 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 raw material of the same size is supplied for cutting. It is required to cut it into blanks of a given size in a given quantity, so that the total waste is minimal.

Mathematical setting .

Let's introduce the notation:

i is the index of blanks,

Аi - the required number of blanks of the i-th type;

j - index of cutting options,

Cj is the size of waste when cutting a unit of initial material according to option j;

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

Let us introduce the notation of unknown variables.

xj is the amount of raw material cut according to option j.

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

z \u003d С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 up to 20% of raw materials.

The mathematical model of cutting is built in two stages.

At the first stage, the cutting options are constructed, 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 (aij), as well as the values ​​of waste (Cj) are determined.

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

option number

Blank i1

i2 blank

blank im

The blanks are arranged in non-increasing order of their sizes. The construction of variants is carried out by the method of complete enumeration.

10. General form of the LP problem model and its features

The general form of the LLP is:

z \u003d С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

xj ≥ 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 (nonrigid conditions).

2. Non-negativity conditions are not imposed on all variables

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

11. Standard form of the LP problem model 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

xj ≥ 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 the 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 apply to all variables

3. The objective function tends to

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

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

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

Definition 2. The set of all plans for a linear programming problem is called the domain 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 records of LP tasks: expanded, folded, matrix, vector.

LP problem 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

… … … … …

Хn am1 am2 am2 am

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

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

1. Variable conversion. 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. Constraint transformation. If any of the constraints in the model has the form of an inequality, then it is converted to equality by adding (if the inequality is of type ≤) or subtracting (if the inequality is of type ≥) from its left side. These variables are called balance variables. Balance variables are included in the objective function with zero coefficients. The balance variable takes the index value sequentially after the already 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 pass from the canonical form to the standard form, each of

equations to be replaced by a system of inequalities:

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

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

a) multiplication of any equation by a constant other than zero;

b) addition to any equation of any other equation, multiplied by any constant.

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

We write the problem in standard form.

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

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

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 given set, it also contains a segment connecting them.

convex set

Definition A point x of a set M is called a corner or extreme point if it is not internal to any segment that entirely belongs to the given set.

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

x \u003d λ 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 task must be converted 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 by a graphical method (there are other effective methods for solving such problems).

3. The region of admissible values ​​of variables for ZLP is under construction.

4. A guide vector is being built c .

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

6. The mental movement of the initial isocoel in the direction of the vector is carried out c, if the maximum value of the objective function is determined, or in the opposite direction, if its minimum value is determined, until the isogoal becomes a reference to the ODZ. The intersection points of the reference isocoel and the 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. LP problem solving method

Algorithm of the graphical method.

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

2. The directing vector C is constructed by the coefficients for the variables of the objective function.

3. The initial isocoel is drawn perpendicular to the direction vector through the origin.

4. The initial isogoal is mentally moved in the direction of increasing 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 isogoal becomes a reference to the ODZ. The intersection points of the reference isocoel and the ODZ 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 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 objective function

The ODZ theorem. The domain of admissible 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 LLP objective function takes its optimal value at one of the corner points of the region of acceptable values ​​of 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 theorem about the corner point. Sufficient and necessary condition

25. Corollaries from the theorem on the properties of solutions to LP problems and conclusions. The concept of a baseline.

Consequences from theorems.

Definition. Plan = (х1,х2,…,хn), whose positive coordinates correspond to linearly independent vectors, is called basic plan PLP .

Consequence 1. The reference plan has no more than m positive coordinates.

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

Consequence 2. Each corner point ODZ is the basic plan.

27. Algorithm of the simplex method.

When solving LP problems by 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 into a canonical form.

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

3. The initial simplex table is constructed.

4. The values ​​of the optimality estimates in the index line 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 largest positive estimate. This column is called the enable column.

6. A vector is derived from the basis, which corresponds to the simplex ratio calculated by the formula 0< Ө ≤ . Given line called the enable string.

7. A new simplex table is built. Columns B and C B are changed accordingly. The rest of the table is filled from the previous one using Gaussian transformations, with the index row considered to be m+1 rows and also transformed using Gaussian transformations. We proceed to the implementation of paragraph 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 a basis and construction of an initial reference plan for solving problems by the simplex method.

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

30 . The optimality theorem for the plan of a linear programming problem is a consequence of the optimality estimation 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 \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d 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 fulfilled, then the plan X B0 is not optimal and it is possible to pass 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 coefficients at the basic variables of the objective function Z

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

c j is the coefficient of the objective function Z with variable Х j

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

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

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

31. Choice of a vector entering the basis and deriving from the basis. Simplex relation.

To switch to a new reference plan, one of the free vectors is needed enter into the basis, and output some of the basis vectors. To introduce into the basis, we choose a vector that has at least one positive coordinate. Let the vector A m+1 be such a vector.

decomposition -

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

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

If , then this coordinate will be non-negative.

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

then the first coordinate of the vector 1 X will become zero.

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

32. permissive element of the table, its choice. Full Jordan elimination rule for simplex table recalculation.

33. Quadrilateral rule for simplex table recalculation

34. A sign of the uniqueness of the optimal plan, the set of optimal plans and the absence of an optimal plan when solving the LP problem by the simplex method.

When solving problems by 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 obtained support design is optimal and unique. (see the example in the previous paragraph).

2. Alternative optimum (set of optimal solutions).

If among the nonpositive estimates of free vectors there is at least one zero estimate, then the obtained support design will be optimal, but not the only one. In this case, you can go to other support plans (vectors that correspond to zero estimates are introduced into the basis) and, then, write the general optimal solution as a convex combination of the obtained optimal support plans.

3. LLP 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 elements given column are negative and zero, then given vector can be included in the basis. However, none of the basis vectors can be deduced from the basis. It follows from this that a further decrease in the objective function is possible when switching to a non-supporting plan.

4. LLP does not have an optimal solution, since the system of constraints is inconsistent. Since when solving the LLP, the usual simplex method should be the initial reference plan, the system of linear equations is certainly not inconsistent. Therefore, such a case cannot occur when solving by 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. When is the artificial basis method used?

artificial.

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

If the linear programming problem is in canonical form, however, not all equations contain basic variables, i.e., there is no original baseline. 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 Latin letter M. It can be considered equal to +∞. In this regard, sometimes the artificial basis method is called the M-method. Such a transformation of the original problem is called the construction of the extended problem. If you are solving a problem with an objective function to find an artificial variable, you must 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. Such a transformation of the original problem is called the construction of the extended problem. If a problem is being solved with an objective function to find the maximum, then artificial variables enter the objective function with a coefficient -M.

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

The initial simplex table is constructed.

37. building an index line in the artificial basis method

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

Thus, to determine the vector that is introduced into the basis, it is necessary to analyze the lower index line. If an artificial vector is derived from the basis, then the corresponding column in 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 artificial vectors have been taken out of the basis, the bottom row will have all zero elements, except for the estimates corresponding to artificial vectors. They will be equal to -1. Such a line 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. Optimality criterion in the artificial basis method. The sign is the construction of the initial basic plan of the original task.

39. Algorithm of the dual simplex method

Algorithm of the dual simplex method:

1. fill in the first simplex table in the usual way, regardless of the signs of free members. It is believed that such a problem should have an initial unit basis.

2. Select the guide line by the largest absolute negative element of the column of free members A0

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

4. Recalculate the simplex table according to the rule of full Jordan eliminations

5. check the received plan for admissibility. A sign of obtaining an acceptable reference plan is the absence of negative elements in column A0. If there are negative elements in column A0, then go to the second paragraph. If there are none, then they proceed to solve the problem in the usual way.

6. A sign of obtaining an optimal solution by the dual simplex method is the optimality criterion for the ordinary simplex method.

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

Types of transport tasks.

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

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

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

An open transportation task can be converted to a closed one in the following way.

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

If ∑Bj > ∑Ai . In this case, it is necessary to introduce a fictitious m + 1 supplier with inventory volume ∑Bj – ∑Ai . The unit costs of transportation from a fictitious supplier to consumers are assumed to be equal to 0, since in fact such transportation will not be carried out and consumers will not receive some 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 technique for constructing a reference plan. According to this technique, the formation of traffic values ​​begins with the s.-z. table corner, i.e. from cell x11. According to this method, 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 the goods,

The method of the smallest element in the matrix.

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

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

Further distribution is first made as far as possible over cells with two marks, then - with one, and then the problem is rebalanced to (m + n - 1) fillings. We organize fillings when passing 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 of the transport problem will also be integer.

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

It follows from this theorem that the distribution of a closed transportation 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. Crossed out combination.

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

45. Optimality theorems for the transport problem.

Theorem. If for some distribution of the transport task you

conditions are fulfilled:

A). ui+vj = cij for occupied cells

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

then this distribution is optimal.

The values ​​ui are called row potentials, and the values ​​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, based on condition a) of the optimality theorem.

The number of equations based on this condition is m + n – 1, and the number of unknowns ui and vj is m + n. That. 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 indefinite, 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 potentials, occupied cells are considered, for which one of their potentials is known, and based on 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 tasks and the criterion of optimality.

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

Optimality estimates in free TK cells are an optimality criterion that checks the distribution 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 problem

If the distribution is not optimal, then it is necessary to redistribute supplies.

For redistribution, a recalculation cycle is built. The cell with the highest positive score is selected as the cell. This cell is marked with a “+” sign, that is, it is necessary to record a certain amount of delivery in it. But then the balance in this column will be disturbed, therefore, one of the occupied cells of this column must be marked with a “-” sign, that is, the volume of supply 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 located.

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

49. redistribution chains, their types.

Let the transportation plan under consideration be not optimal, i.e. there are positive relative estimates. Then an unfavorable cell is taken (one of the unfavorable ones) and a recalculation cycle is built for it, according to which the planned transportation is then redistributed. The cycle is built in the form of a broken closed 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 the product, and in the other corners the cells are filled, i.e. when constructing a cycle, we start from a candidate cell and return to it along a broken line, but we can only make turns in filled cells (corresponding to the basic variables). Let an unfavorable cell lay claim to product Q. In order to prevent an imbalance in the table, it is necessary in the cycle transitions to take turns

add and subtract Q to the available traffic. Since there are an even number of corners, Q will be added in half of the cells, and subtracted in the other half. The cycle is started clockwise or counter-clockwise from the candidate cell, placing good Q there, then Q is subtracted from the neighboring cell, then added, and so on. The value of Q itself is chosen so that one of the cells is emptied, but none of the supplies would become negative.

To do this, Q must be chosen equal to the smallest reducible of the cells in which Q is subtracted. In the following fig. 7.1 and 7.2 we will show examples of cycles and the calculation rule.

In this case, two cells are emptied. But it is necessary that only one cell becomes mutually empty. They do this: one of the emptying cells is made empty in the new table, and zero is put 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 counting cycle, we must proceed from the following two considerations:

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

b) one of the occupied cells must become free.

In order for these conditions to be met, it is necessary to select the volume of transported products as follows: θ=min (хij) -, where (хij) is the volume of transportation from the cells of the recalculation cycle marked with the “-” sign.

θ = min(20;30)=20

θ is added to the values ​​of cells marked with a “+” sign. θ is subtracted from the values ​​of cells marked with a “-” sign. The supply value of the remaining cells is overwritten without changes. As a result, we get the following table.

53. Algorithm of the method of potentials.

Algorithm:

1. Check if the equation is satisfied for the task if not, a fictitious supplier or consumer is introduced into the task

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

3. An initial baseline is being built

4. Potentials of supplies and consumers are determined

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

6. Load a perspective cell. Prepare a new base plan in the form of a transport table. Go to point 4.

54. Accounting for the cost of production and transportation of products. Transport task with supply 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 transported products. To do this, in the matrix transp. tasks

Where Cij ' is the reduced cost of producing one unit of output.

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

Tasks with supply bans.

In some situations, it is not possible to transport products on any route.

To do this, in the matrix of the transport task, the transportation through which is prohibited, a prohibitive tariff M is entered. Further, the task is solved in the usual way. However, this cell will always correspond to a negative cell score.

55. taking into account the restrictions on the throughput of routes, taking into account the obligatory nature of certain deliveries in the transport problem.

accounting for restrictions on the throughput of routes.

In some transport tasks, on some routes, a smaller throughput than is necessary to satisfy the demand of the point of consumption.

taking into account the mandatory nature of certain deliveries in the transport problem.

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

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

Upon receipt of the optimal distribution, it is necessary to return to the original problem and make the appropriate economical. conclusions. They are the following:

1. If a point of consumption is introduced, this means that there are excessive production volumes in the analyzed system, and it is possible, without prejudice to the system under consideration, to reduce the capacities of those points of production by the amount of binding that are tied to the fictitious point of consumption.

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 capacity of those production points that are closest to the consumption points tied to the fictitious production point is increased. The manufacturer's capacity is increased by the binding value. To do this, consider the column of the point of consumption, which is tied to the fictitious point of production, and find the lowest tariff in it. It is most efficient to increase the capacity of the production point corresponding to this tariff by the amount of binding.

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

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

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

Initial task:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | at 2

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

A T 1 x 1 +a T 2 x 2 + ... + a T n x n ≤v 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 \u003d (x 1, x 2, ..., x n)

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

Dual problem

Let the enterprise for any reason not be able to produce products. In order to reduce the cost of downtime, the company can sell the raw materials that it has. At what price should raw materials be sold?

i - the price of the i-th type of raw material 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’)

A 1p y 1 +a 2p y 2 +…+ a tp at T≥s P

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 the direct and dual problems

Each linear programming problem can be associated

dual task according to the following rules:

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

be on the right, and terms with unknowns on the left.

2. Constraints-inequalities 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 it corresponds to equality, then the variable is 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 at

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

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

functions of the original problem. We also note that the duality relation is mutual, i.e. the task dual with respect to the dual one coincides with the original one. Dual pairs of tasks are divided into symmetrical and asymmetric. In a symmetric pair, the constraints of the primal and dual problems are non-strict 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)

yi ≥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 have resources b1,b2,…bm that can be used to produce n-types of products. Let us also know the unit cost of the j-type of product cj (j=1,n) and the consumption rate of the i-th resource (i=1,m) for production j-th units products - aij. It is required to determine the volume of production of each type xj (j=1,n), maximizing the total cost

f= c1x1+…+cnxn (1)

At the same time, 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 ZLP to the 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. Main and second duality theorem (state theorems and explain)

The first duality theorem.

Theorem: if one of the dual problems has an optimal plan, 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. problem the objective function is unbounded on the set of plans, then in the dual problem the system of constraints is inconsistent.

Second duality theorem and its economic interpretation.

In order for the feasible solutions of a pair of dual problems to be optimal, it is necessary and sufficient that the following condition be satisfied: 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 is converted by the optimal plan into strict equality, then the corresponding component of the opt. plan of the dual problem should be equal to zero. If some component opt. plan is equal to zero, then the corresponding restriction of the dual problem is converted by the opt.plan into a strict equality xj*>0, therefore (i= from 1 to m)Σaij yi*=cj 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 (resource races = resource stock).

(j=1 to n) Σaij xj*

The meaning of the theorem is as follows:

If the cost estimate of the resource consumption for the production of a unit of prod-ii \u003d price, then this type of prod-ii is included in the optimal plan;

If the costs exceed the price, then the prod-yu should not be produced;

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

If the resource is not fully spent, then its cost estimate = 0.

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

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

Column A3: "shadow" price of resource S2 is y01=0, the column remains

single and from the first line it can be read that x3=9, i.e. when implementing the found optimal plan, 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 because y02=1, then the increase in resource S2 by 1 c.u. will give an addition in terms of income by.Z = y02· .w2 = = 1.1 = 1 (thousand UAH) (here.w2 is the increment of the resource S2 and .Z is the corresponding increment of income). With such an increment of the resource S2, the maximum income will already be Zmax=58 thousand UAH. + 1 thousand UAH = 59 thousand UAH. On fig. 6.2 illustrates this situation, commentary on which will be given below. It also follows from column A4 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 of the basic variable x1 and column A4 is "-1/2"), and the output of goods T2 will increase by 3/2 tons (because in the row with the basic variable x2 in column A4 we have "3/2". What has been said about column A4 will be commented below using graphical constructions (Fig. 6.2). Column A5: the "shadow" price of 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 hryvnia) and will be Zmax=58 thousand hryvnia. + 2 thousand UAH = 60 thousand UAH. At the same time, as follows from column A5 of Table. 3, output of T1 will increase by ½ ton and T2 will decrease by ½ ton. The stock of raw materials S1 (see line 1) will increase by 3/2 c.u.

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

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

To define it, you need:

1. write down the functional equation for the last state of the process (it corresponds to l \u003d 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 areas (since f0(Sn)=0, then f1(Sn-1)= optimum(Rn( Sn-1,Un)

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

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

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 expression (2)

5. check what the value of l is equal to. If l=0, the calculation of conditionally optimal solutions is completed, and the optimal solution of 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 of the problem for each subsequent step of the process, moving from the end of the calculations to the beginning.

The dynamism of programs method allows one problem with many variables to be replaced by a number of successively solved problems with a smaller number of variables. The decision is made step by step. The main principle on which the optimization of a multi-step 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 decision are, subsequent decisions must be optimal with respect to the state resulting from the initial decision.

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 the expression means the maximum or minimum depending on the condition of the problem.

63. Requirements for problems solved by the DP method

Dynamic programming is a mathematical method for finding optimal solutions to multi-step 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 multi-step 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 a strategy that provides the best result in terms of a pre-selected criterion. Such a 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. on how the process being optimized has reached its present state. The optimal solution is chosen only taking into account the factors characterizing the process at the moment.

The method of dynamic 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 (on the example of the problem of the distribution of capital investments). Bellman recurrence relation.

Let us preliminarily explain that the dynamic programming method is applied primarily to those problems in which the process (or situation) being optimized is deployed in space or time, or 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 (partitioned) into a number of stages (steps). This breakdown is in many cases natural, but in the general case it is introduced artificially. . For example, when considering any game of chess, any move of each of the players just serves

breaking down the entire batch into separate steps (stages). And in a military operation to pursue one missile against 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. At the same time, 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 the 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 is used, and the direct value of the effect Rl+1(Sl,Ul+1), achieved as a result of choosing the solution Ul+1 for a given state Sl systems. 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 capital investments, we will use the functional Bellman equation. First, using the simplest situation, we will 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 allocated capital investments in the amount of K between two enterprises. The planning departments of the enterprises, on the basis of their calculations, formed the income functions q(x) for the enterprise P1 and h(x) for the enterprise P2. These functions mean that if the first or second enterprise receives an investment in the amount of x, then the first enterprise

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

So, let the company P1 allocated capital investments in the amount x, then the company P2 is allocated the amount 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 on its maximum value, which we denote by F(K):

This entry is like a skeleton for more complete entries.

functional Bellman equation. COMPLICATE our task by distributing capital investments over two planning periods (two stages) . Let it be initially decided to allocate the amount x to the first enterprise P1, and x to the second enterprise P1. 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 at the first enterprise the balance of investments will be x, where , and at the second - .(K - x), where Accordingly, income for the second period will be q( .x) - according to the first facility and h[.(K - x)] - according to the second one. Dynamic programming optimization, as a rule, starts from the end stage. Therefore, we start from the second stage, denoting F1 the maximum possible income from two enterprises in the second

stage. Get

Then, to the considered last (in our case, the second) stage, we kind of add the previous (in our case, 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 for the last (n - 1) stages. The resulting functional Bellman equation is recurrent, i.e. associates the Fn value with the Fn-1 value.

More generally, the Bellman equation has the form

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

maximum income for all n stages.

66. The concept of solving problems of nonlinear programming

Let the problem of nonlinear programming 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(х1, …, хn) and qi(х1, …, хn) (m , 1 i =) are real non-linear,

regular functions of n real variables.

According to their general properties, nonlinear programming problems can

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

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

In non-linear 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 that indicates the direction of maximum increase in the goal for the considered point. In the general case, the search procedure is performed in an iterative mode from the initially selected point to the points with the best indicator. Let, for example, . - domain of admissible solutions

considered problem, 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 area. along the gradient to the disturbed boundary of the O2 O3 region. 13.3 is shown so that Ai with odd indices belong to the area., and points Ai with even indices do not. 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 broken boundary gradient.

67. The concept of parametric and integer programming .

Statement and mathematical model of ZCLP.

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 completely 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 vertex 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 branch of mathematical programming devoted to the study of optimization problems in which the admissibility conditions and the objective function depend on some deterministic parameters.

Definition. Linear programming (LP) - the science of research methods and finding extreme (maximum and minimum) values ​​of a linear function, on the unknowns of which linear restrictions are imposed.

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

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

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

with restrictions:

Where x j- unknown; aij, b i, cj are given constants.

All or some equations of the constraint system can be written as inequalities.

The mathematical model in a shorter notation has the form

with restrictions:

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

The set of admissible solutions forms the region of admissible solutions (ODD).

Definition. A feasible solution, in which the objective function reaches its extreme value, is called the optimal solution of the linear programming problem and is denoted opt.

Basic admissible solution (X 1 , X 2 ,..., x r , 0, …, 0) is a reference solution, where r- the rank of the constraint system.

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

7. Solving linear programming problems by a graphical method. Graphs of constraint functions. Level lines.

Graphical Method for Solving Linear Programming Problems

The simplest and most visual 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 no more than two free variables.

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

To find the extreme value of the objective function in the graphical solution of LP problems, the vector is used 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 vector coordinates are the objective function coefficients L(). The construction of the level line will be considered in detail when solving practical problems.

Problem solving algorithm

1. We find the area of ​​feasible solutions for the system of constraints of the problem.

2. Building a vector .

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

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

The level line is moved until it has only one common point with the area of ​​feasible solutions. This point, which determines the unique solution of 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 ODT, 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 given by the formula:

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

An LP problem can be unsolvable when the constraints that define it turn out to be contradictory.

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

Example 3 Choosing the best product release option

The company produces 2 types of ice cream: cream 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.

Market research showed that the daily demand for butter 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 is 16 rubles, chocolate - 14 rubles.

How much of each type of ice cream should the firm produce in order to maximize its sales revenue?

Solution. Denote: x 1 - daily volume of production of creamy ice cream, 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:

Set limits on milk for ice cream. Its consumption for cream ice cream is 0.8 kg, for chocolate ice cream - 0.5 kg. Stock of milk 400kg. Therefore, the first inequality will look like:

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

The result is a system of inequalities. what 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- domain of admissible solutions. We build the 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 some positive number, not equal to zero, is chosen. All level lines are parallel to each other. The normal vector of the level line.

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 defined as the intersection of the lines given by the equations:

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

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

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

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

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

1. Indicate a method for finding the optimal reference solution

2. Specify the method of transition from one reference solution to another, on which the value of the objective function will be closer to the optimal, i.e. indicate a way to improve the reference solution

3. Set criteria that allow you to timely stop the enumeration of reference solutions on the optimal solution or pass a conclusion about 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 estimates of vector expansions in terms of the basis of the reference solution and fill in the table of the simplex method

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

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

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

The transportation 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 initial reference solution;

2. Checking this solution for optimality;

3. Transition from one basic solution to another.

Lecture 2

IN canonical form

admissible solution of the PLP(acceptable plan).

optimal solution of the LLP.

Necessity

Example.

Let's write the problem in canonical form

Special situations of the graphical solution of the ZLP

Except when the task is the only optimal solution for and , can be special situations:

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

2. task not solvable due to the unlimitedness of the ODR, or - Figure 3;

3. ODR - single point Ah, then ;

4. task not solvable if the ODR has an empty area.

A

Figure 2 Figure 3

If the level line is parallel to the side of the area of ​​feasible solutions, then the extremum is reached at all points of the side. The problem has an infinite number of 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 graphically the linear programming problem ( alternative optimum):

Questions for self-control

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

2. Write down 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. Give a definition of feasible and optimal solutions to the 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 the mathematical model of a linear programming problem with two variables.

8. How to construct a half-plane given by a linear inequality with two variables ?

9. What is called the solution of a system of linear inequalities with two variables? Construct on the plane the domain of feasible solutions of such a system of linear inequalities, which:

1) has a unique solution;

2) has an infinite set 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 LLP with two variables.

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

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

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

2) is reached at a single point of the ODS, and .

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

1) has unique optimal solutions for and ;

2) has a set of 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 GRAPHIC SOLUTION OF LLP

4. Graphical solution of economic problems of linear programming

Forms of linear mathematical models and their transformation

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

IN general form of the mathematical model it is required to find the maximum or minimum of the objective function; the constraint system 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 constraint system consists only of equations; all variables are non-negative.

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

The solution of the system of constraints that satisfies the conditions of non-negativity of the variables is called admissible solution of the PLP(acceptable plan).

The set of feasible solutions is called the area of ​​feasible solutions of the LLP.

A feasible solution, in which the objective function reaches an extreme value, is called optimal solution of the LLP.

The three forms of the LLP are equivalent in the sense that each of them can be reduced to a different form with the help of mathematical transformations.

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

Transition to the canonical notation ZLP.

Example.

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

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 the use of raw materials, they show the remainder of the raw materials, and in the problem of choosing optimal technologies, they show the unused time of the enterprise using a certain technology; in the problem of cutting - the release of blanks of a given length in excess of the plan, etc.