Convex sets and their properties. In order to study the properties of the LPP, it is necessary to give a rigorous definition of a convex set. Earlier, a convex set was defined as a set that, together with any two of its points, contains a segment connecting them.

A generalization of the concept of a segment for several points is their convex linear combination.

Point X is called convex linear combination points, if conditions are met

The set of points is convex, if it, together with any of its two points, contains their arbitrary convex, linear combination.

The following theorem on the representation of a convex polyhedron can be proved.

Theorem 1.1. A convex n-polytope is a convex linear combination of its corner points.

From Theorem 1.1 it follows that a convex polyhedron is generated by its corner points or vertices: a segment by two points, a triangle by three, a tetrahedron by four points, etc. At the same time, a convex polyhedral region, being an unbounded set, is not uniquely determined by its corner points: any point of it cannot be represented as a convex linear combination of corner points.

Properties of the linear programming problem. Previously, various forms of a linear programming problem were considered and it was shown that any linear programming problem can be represented as a general or canonical problem.

To substantiate the properties of a linear programming problem and methods for its solution, it is advisable to consider two more types of writing the canonical problem.

Matrix notation:

Here WITH- row matrix, A- system matrix, X- matrix-column of variables, V- matrix-column of free members:

Vector notation:

where vectors correspond to columns of coefficients for unknowns.

The following theorem was stated above, but not proved in general form.

Theorem 1.2. The set of all feasible solutions to the system of constraints of a linear programming problem is convex.

Proof: Let - two admissible solutions of the LPP given in matrix form. Then and . Consider a convex linear combination of solutions, i.e.

and show that it is also an admissible solution to system (1.3). Indeed

i.e. solution X satisfies system (1.3). But since, then X> 0, i.e. the solution satisfies the non-negativity condition.

So, it has been proved that the set of all admissible solutions of the linear programming problem is convex, or, more precisely, it represents a convex polyhedron or a convex polyhedral domain, which in what follows will be called by one term - polyhedron of solutions.

The answer to the question at what point of the polytope of solutions is the optimal solution to a linear programming problem is possible is given in the following fundamental theorem.

Theorem 1.3. If the linear programming problem has an optimal solution, then the linear function takes its maximum value at one of the corner points of the solution polytope. If a linear function takes its maximum value at more than one corner point, then it takes it at any point that is a convex linear combination of these points.

Proof: We will assume that the solution polytope is bounded. Let us denote its corner points by , and the optimal solution is through X *... Then F (X *)³ F (X) for all points X polyhedron of solutions. If X * Is a corner point, then the first part of the theorem is proved.

Let's pretend that X * is not a corner point, then by Theorem 1.1 X * can be represented as a convex linear combination of corner points of the solution polyhedron, i.e.

Because F (X) Is a linear function, we obtain

In this expansion, we choose the maximum value among the values. Let it correspond to the corner point X k(£ 1 k£ R); let us denote it by M, those. . Replace each value in expression (1.5) with this maximum value M. Then

By assumption X* Is the optimal solution, therefore, on the one hand, but, on the other hand, it is proved that
F (X *)£ M, hence, where X k- corner point. So there is a corner point X k in which the linear function takes its maximum value.

To prove the second part of the theorem, assume that the objective function takes its maximum value at more than one corner point, for example, at the points , where , then

Let X- a convex linear combination of these corner points, i.e.

In this case, given that the function F (X)- linear, we get

those. linear function F takes the maximum value at an arbitrary point X which is a convex linear combination of corner points.

Comment. The requirement that the polytope of solutions be bounded in the theorem is essential, since in the case of an unbounded polyhedral domain, as noted in Theorem 1.1, not every point of such a domain can be represented by a convex linear combination of its corner points.

The proved theorem is fundamental, since it indicates a fundamental way of solving linear programming problems. Indeed, according to this theorem, instead of studying an infinite set of feasible solutions to find the desired optimal solution among them, it is necessary to investigate only a finite number of corner points of the polyhedron of solutions.

The next theorem is devoted to the analytical method for finding corner points.

Theorem 1.4. Each admissible basic solution of a linear programming problem corresponds to a corner point of the solution polyhedron, and vice versa, each corner point of the solution polyhedron corresponds to an admissible basic solution.

Proof: Let be an admissible basic solution to the system of LPP constraints (1.4), in which the first T the component is the main variables and the rest n - t component - minor variables equal to zero in the basic solution (if this is not the case, then the corresponding variables can be renumbered). Let us show that X

Suppose the opposite, i.e. what X is not a corner point. Then the point X can be represented by an interior point of a segment connecting two different ones that do not coincide with X, points

in other words, a convex linear combination of points polyhedron of solutions, i.e.

where (we assume that, otherwise the point X coincides with point X 1 or X 2).

We write the vector equality (1.6) in coordinate form:

Because all variables and coefficients are non-negative, then from the latter p-t equalities it follows that, i.e. in decisions X 1 , X 2 and X system of equations (1.4) the values n - t components are equal in this case to zero. These components can be thought of as the values ​​of minor variables. But the values ​​of the minor variables unambiguously determine the values ​​of the major ones, therefore,

So all P component in solutions X 1 , X 2 and X coincide, and therefore the points X 1 and X 2 merge, which contradicts the assumption. Hence, X Is the corner point of the solution polyhedron.

Let us prove the converse statement. Let be the corner point of the polytope of solutions and its first T coordinates are positive. Let us show that X- admissible basic solution. is not a corner point, which contradicts the condition. Therefore, our assumption is incorrect, i.e. vectors are linearly independent and X Is an admissible basic solution to problem (1.4).

An important corollary follows directly from Theorems 1.3 and 1.4: if a linear programming problem has an optimal solution, then it coincides with at least one of its admissible basic solutions.

So, the optimum of a linear function of a linear programming problem should be sought among a finite number of its admissible basic solutions.

Optimization of linear models in MS Excel is performed simplex method- purposeful enumeration of support solutions of the linear programming problem. The algorithm of the simplex method is reduced to the construction of a convex polyhedron in a multidimensional space, and then to iterating over its vertices in order to find the extreme value objective function.

Effective remedies linear programming underlie both integer and nonlinear programming for more complex optimization problems. These methods, however, take a longer computation time.

In subsequent lectures, examples of solving typical optimization problems and making management decisions using the MS Excel add-in "Search for a solution" will be analyzed in detail. The tasks that are best accomplished by this tool have three main properties:

• there is a single goal, functionally related to other parameters of the system, which needs to be optimized (find its maximum, minimum, or a certain numerical value);
• there are restrictions, usually expressed in the form of inequalities (for example, the volume of raw materials used cannot exceed the stock of raw materials in the warehouse, or the operating time of the machine per day should not be more than 24 hours minus the time for service);
• there is a set of input variable values ​​that affect the optimized values ​​and constraints.

Task parameters are limited by the following limit values:

• number of unknowns - 200;
• the number of formula constraints on unknowns - 100;
• the number of limiting conditions for unknowns is 400.

The algorithm for finding optimal solutions includes several stages:

• preparatory work;
• debugging the solution;
• analysis of the solution.

The sequence of the necessary preparatory work performed in solving the problems of economic and mathematical modeling using MS Excel is shown in the block diagram of Figure 1.6.

Rice. 1.6.

Of the five points of the preparatory work plan, only the fifth point is formalized. The rest of the work requires creativity - and they can be done in different ways by different people. Let us briefly explain the essence of the wording of the points of the plan.

When setting the problem, target coefficients and normalized coefficients are known. In the previous example, the coefficients forming the objective function were the values ​​of the normalized profit per shelf of the type ( ) and one shelf of type ( ). The normalized coefficients were the rates of material consumption and machine time per shelf of each type. The matrix looked like this:

In addition, the resource values ​​are always known. In the previous example, it was a weekly supply of boards and the ability to use machine time: , ... Often in tasks, the values ​​of variables need to be limited. Therefore, it is necessary to determine the lower and upper limits of the area of ​​their changes.

Thus, in the dialog box of the "Search for a solution" optimization program, we must specify the following target algorithm:

The objective function is equal to the product of the vector of desired values ​​of variables by the vector of objective coefficients

The normalized coefficients for the vector of the sought-for values ​​of the variables should not exceed the value of the given vector of resources

The values ​​of the variable must be within the specified limits the number of initial elements of the system

The number of initial elements of the system

The number of specified types of resources

Debugging the solution is necessary in the case when the program issues a message about negative results (Figure 1.7):

Rice. 1.7.

• if a feasible solution is not obtained, then correct the model of the initial data;
• if not received optimal solution, then introduce additional restrictions.

The program issues optimal solution only to model a real problem, not a solution to the problem itself. When constructing the model, various simplifying assumptions of the real situation were made. This made it possible to formalize the process, approximately reflecting the real quantitative relationships between the parameters of the system and the goal. And if the real parameters differ from those included in the model, how will the decision change? To find out, before making a management decision, a model decision is analyzed.

Analysis optimal solution, built into the program, is the final stage of mathematical modeling of economic processes. It allows for a more in-depth check of the model's suitability to the process, as well as the reliability of the optimal solution. It's data driven optimal solution and reports that are issued in the "Search for a solution". But it does not exclude or replace the traditional analysis of the plan from an economic standpoint before making a management decision.

Economic analysis has the following goals:

• determination of possible consequences in the system as a whole and its elements when changing the model parameter;
• assessment of the stability of the optimal plan to changes in individual parameters of the problem: if it is not resistant to changes in most parameters, the guarantee of its implementation and achievement of the calculated optimum decreases;
• carrying out variant calculations and obtaining new variants of the plan without re-solving the problem from the original basis by means of adjustments.

Possible analysis methods are shown in the diagram in Figure 1.8.

After obtaining the optimal solution, it is analyzed according to the reports received. Stability analysis- study of the influence of changes in individual parameters of the model on the indicators of the optimal solution. Limit analysis- analysis of acceptable changes in the optimal plan, in which the plan remains optimal.

Given the responsibility of making economic management decision, the leader must make sure that the received optimal plan is the only correct one. To do this, it is necessary to obtain answers to the following questions on the basis of the model:

• "what if…"
• "what is needed to ..."

Analysis to answer the first question is called variant analysis; analysis to answer the second question is called customized solutions.

Variant analysis is of the following types:

• Parametric- analysis, which consists in solving a problem for different values ​​of a certain parameter.
• Structural Analysis- when the solution to the optimization problem is sought with a different structure of constraints.
• Multi-criteria analysis- This is a solution to the problem for different target functions.
• Analysis with conditional input data- when the initial data used in solving the problem depend on the observance of additional conditions.

After the analysis, the results should be presented in graphic form and a report should be drawn up with recommendations for making a decision, taking into account the specific economic situation.

Definition... Any solution to the system of constraints is called an admissible solution of the LPP.
Definition... A feasible solution in which the objective function reaches its maximum or minimum value is called the optimal solution.

By virtue of these definitions, the LP problem can be formulated as follows: among all points of a convex region that is a solution to the system of constraints, choose one whose coordinates minimize (maximize) the linear function F = With 1 x + With 2 y.
Note that the variables x, y in the LPP take, as a rule, non-negative values ​​( x≥ 0, y≥ 0), so the region is located in the I quarter of the coordinate plane.

Consider a linear function F = With 1 x + With 2 y and fix some of its values F... Let, for example, F= 0, i.e. With 1 x + With 2 y= 0. The graph of this equation will be a straight line passing through the origin of coordinates (0; 0) (Fig.).
Drawing
When changing this fixed value F = d, straight With 1 x+ With 2 y = d will move in parallel and "trace" the entire plane. Let D- polygon - the area for solving the system of constraints. When it changes d straight With 1 x + With 2 y = d, at some value d = d 1 will reach the polygon D, let's call this point A"Entry point", and then, passing the polygon, at some value d = d 2 we will have the last common point with it V, let's call V"Exit point".
Obviously, the objective function of its smallest and largest value F=With 1 x + With 2 y will reach at the entry points A and "exit" V.
Taking into account that the objective function takes the optimal value on the set of feasible solutions at the vertices of the region D, the following plan for solving the LPP can be proposed:

1. to build the area of ​​solutions of the system of restrictions;
2. build a straight line corresponding to the objective function, and by parallel transfer of this straight line find the "entry" or "exit" point (depending on the requirement to minimize or maximize the objective function);
3. determine the coordinates of this point, calculate the value of the objective function in them.

Note that the vector ( With 1 , With 2), perpendicular to the straight line, shows the direction of growth of the objective function.

When solving the LPP graphically, there are two possible cases that require special discussion.

Case 1
Figure 6
When moving straight With 1 x + With 2 y= d"Entry" or "exit" (as in the picture) will occur on the side of the polygon. This will happen if the polygon has sides parallel to a straight line. With 1 X+ With 2 at = d .
In this case, the points of "exit" ("entry") are countless, namely, any point of the segment AB... This means that the objective function takes the maximum (minimum) value not at one point, but at all points lying on the corresponding side of the polygon D.

Case 2
Consider the case when the range of admissible values ​​is unlimited.
In the case of an unbounded area, the objective function can be specified in such a way that the corresponding straight line does not have an “exit” (or “entry”) point. Then the maximum value of the function (minimum) is never reached - they say that the function is not limited.
Drawing
It is necessary to find the maximum value of the objective function F = 4x + 6y→ max, with a system of restrictions
Let us construct the region of feasible solutions, i.e. we will solve graphically the system of inequalities. To do this, we construct each line and define the half-planes given by the inequalities.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x= 12 - parallel to the axis OY ;
y= 9 - parallel to the axis OX ;
x= 0 - axis OY ;
y = 0 - axis OX;
x OY;
y≥ 0 - half-plane above the axis OX;
y≤ 9 - half-plane below y = 9;
x ≤ 12 - half-plane to the left x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.
Drawing
The intersection of all these half-planes is obviously the pentagon OAVSD, with vertices at points O(0; 0), A(0; 9), V(6; 9), WITH(12; 6), D(12; 0). This pentagon forms the region of feasible solutions to the problem.

F = 4x + 6y→ max.

x	3	0
y	–2	0

F = 0: 4x + 6y x+ 6y WITH(12; 6). It is in her F = 4x + 6y
Hence, for x = 12, y= 6 function F F= 4 ∙ 12 + 6 ∙ 6 = 84, equal to 84. The point with coordinates (12; 6) satisfies all inequalities of the system of constraints, and the value of the objective function in it is optimal F* = 84 (the optimal value will be denoted by "*").
The problem has been solved. So, it is necessary to produce 12 products of type I and 6 products of type II, while the profit will be 84 thousand rubles.

The graphical method is used to solve problems that had only two variables in the system of restrictions. This method can also be applied to systems of inequalities with three variables. Geometrically, the situation will be different, the role of straight lines will be played by planes in three-dimensional space, and the solution to the inequality in three variables will be a half-space located on one side of the plane. The role of regions will be played by polyhedra, which are the intersection of half-spaces.

Example No. 2. The mine develops two seams. The output of the cut in the first layer is a1%; on the second - a2%. The maximum production of the longwall for the first layer is B1 thousand tons per year, for the second layer - B2 thousand tons per year. According to the work technology, the production from the second layer cannot exceed the production from the first layer. The output of the mine in the mine should not exceed C1 thousand tons per year. The total load on the two layers per year should be at least C2 thousand tons per year. Create a mathematical model and build a set of permissible load values ​​for the first and second layers per year.

Example No. 3. The shop sells 2 types of soft drinks: Cola and lemonade. The income from one can of cola is 5 cents, while the income from one can of lemonade is 7 cents. On average, a store sells no more than 500 cans of both drinks per day. Despite the fact that the cola is produced by a well-known brand, buyers prefer lemonade because it is much cheaper. It is estimated that the sales of cola and lemonade should be at least 2: 1, and the store is known to sell at least 100 cans of cola a day. How many cans of each drink should the store have at the start of the day to maximize revenue?

Example No. 4. Solve the linear programming problem approximately graphically with the subsequent calculation of the exact value and max (min) of the objective function value.

Example No. 5. A travel agency requires no more than three-ton buses and no more than five-ton buses. The selling price of buses of the first brand is 20,000 USD, the second brand is 40,000 USD. A travel agency can allocate for the purchase of buses no more than $ 1. How many buses of each brand should be purchased separately so that their total (total) carrying capacity is maximum. Solve the problem graphically.

Example No. 6. Using the graphical method, find the optimal production plan for the task given in the table.

Example No. 7. Solve the linear programming problem by a graphical method, subjecting the system of constraints of the problem to the Jordan-Gauss transformations. The system of problem constraints is as follows:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Guidelines... Jordan-Gauss transformations can be performed using this service or through the study of SLAEs.

Example No. 8. The enterprise produces two types of products, A and B, for the production of which three types of raw materials are used. For the manufacture of a unit of product A, it is required to spend raw materials of each type a1, a2, a3 kg, respectively, and for a unit of product B - b1, b2, b3 kg. The production is provided with raw materials of each type in the amount of Р1, Р2, Р3 kg, respectively. The cost of a unit of product A is C1 rubles, and unit of product B is C2 rubles. It is required to draw up a plan for the production of products A and B, which ensures the maximum cost of the finished product.

Example No. 2. It is necessary to find the maximum value of the objective function F = 4x + 6y→ max, with a system of restrictions:

Let us construct the region of feasible solutions, i.e. we will solve graphically the system of inequalities. To do this, select the number of restrictions equal to 4 (Figure 1).
Picture 1

Then we fill in the coefficients for the variables and the constraints themselves (Figure 2).
Picture 2

Figure 3
x= 12 - parallel to the axis OY;
y= 9 - parallel to the axis OX;
x> = 0 - axis OY
y= 0 - axis OX;
x≥ 0 - half-plane to the right of the axis OY;
y≥0 - half-plane above the axis OX;
y≤ 9 - half-plane below y = 9;
x≤ 12 - half-plane to the left x = 12;
0,5x + y≤ 12 - half-plane below a straight line 0.5 x + y = 12;
x + y≤ 18 - half-plane below the straight line x + y = 18.

The intersection of all these half-planes is the pentagon ABCDE, with vertices at points A(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). This pentagon forms the region of feasible solutions to the problem.

Consider the objective function of the problem F = 4x + 6y→ max.

x	3	0
y	–2	0

We construct a straight line corresponding to the value of the function F = 0: 4x + 6y= 0. We will move this line in a parallel manner. Of the whole family of lines, 4 x + 6y= const the last vertex through which the straight line passes when going beyond the boundary of the polygon will be the vertex WITH(12; 6). It is in her F = 4x + 6y reaches its maximum value.

Hence, for x = 12, y= 6 function F reaches its maximum value F= 4 ∙ 12 + 6 ∙ 6 = 84, equal to 84. The point with coordinates (12; 6) satisfies all inequalities of the system of constraints, and the value of the objective function in it is optimal F* = 84.

Test in the discipline "Operations Research"

(correct answers are the first)

1. The term "operations research" appeared ...

during the second world war

in the 50s of the XX century

in the 60s of the XX century

in the 70s of the XX century

in the 90s of the XX century

at the beginning of the XXI century

2. Operations research means (choose the most appropriate option) ...

a set of scientific methods for solving problems of effective management of organizational systems

a set of measures taken to implement certain operations

a set of methods for implementing the conceived plan

scientific methods of resource allocation in the organization of production

3. Arrange the steps that any operational research typically goes through:

formulation of the problem

construction of a meaningful (verbal) model of the considered object (process)

building a mathematical model

solving problems formulated on the basis of the constructed mathematical model

verification of the results obtained for the adequacy of the nature of the system under study

implementation of the obtained solution in practice

4. In operations research, an operation is understood ...

any event (system of actions), united by a single concept and aimed at achieving a goal

any uncontrollable event

a set of technical measures to ensure the production of consumer products

5. The solution is called optimal, ...

if it is preferable for one reason or another

if it is rational

if it is agreed with the authorities

if approved by the general meeting

6. Mathematical programming ...

is engaged in the study of extreme problems and the development of methods for their solution

is the process of creating computer programs under the guidance of mathematicians

solves mathematical problems on a computer

7. The task of linear programming is ...

finding the largest (smallest) value of a linear function in the presence of linear constraints

creating a linear program in a selected programming language designed to solve the problem

description of a linear algorithm for solving a given problem

8. In a quadratic programming problem ...

the objective function is quadratic

the area of ​​admissible solutions is a square

constraints contain quadratic functions

9. In integer programming problems ...

unknowns can only take integer values

the objective function must necessarily take an integer value, and the unknowns can be any

the target function is a numeric constant

10. In parametric programming tasks ...

objective function and / or constraint system contains parameter (s)

the area of ​​admissible solutions is a parallelogram or parallelepiped

the number of variables can only be even

11. In dynamic programming problems ...

the process of finding a solution is multi-stage

need to rationalize dynamite production

you want to optimize the use of speakers

12. The following linear programming problem is posed:

F(X 1, X 2) = 5X 1 + 6X 2→ max

0.2X 1 + 0.3X 2 ≤ 1.8,

0.2X 1 + 0.1X 2 ≤ 1.2,

0.3X 1 + 0.3X 2 ≤ 2.4,

X 1 ≥ 0, X 2 ≥ 0.

Select a task that is equivalent to this task.

F(X 1, X 2)= 5X 1 + 6X 2 → max,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 6X 1 + 5X 2 → min,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 50X 1 + 60X 2 → max,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 5X 12 + 6X 22 → max,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

3X 1 + X 2 ≤ 2.4,

X 1 ≥ 0,

X 2 ≥ 0.

13. The objective function of a linear programming problem can be the function:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→max.

14. The system of constraints of the linear programming problem can be the system:

15. The simplex method is:

analytical method for solving the main problem of linear programming

a method for finding the region of feasible solutions to a linear programming problem;

a graphical method for solving the main problem of linear programming;

a method for reducing a general linear programming problem to a canonical form.

16. The task of linear programming is:

finding the largest or smallest value of a linear function in the presence of linear constraints

development of a linear algorithm and its implementation on a computer

drawing up and solving a system of linear equations

the search for a linear trajectory of the development of the process described by a given system of restrictions.

17. Domain of feasible solutions of the linear programming problem can not look like this:

18. The target function of a linear programming problem can be the function:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→max.

19. The system of constraints of the linear programming problem can be the system:

20. The region of feasible solutions of the linear programming problem is as follows:

F(X 1, X 2)= 3X 1 + 5X 2 equals ...

21. The region of feasible solutions of the linear programming problem has the form:

Then the maximum value of the function F(X 1, X 2)= 5X 1 + 3X 2 equals ...

22. The region of feasible solutions of the linear programming problem has the form:

Then the maximum value of the function F(X 1, X 2)= 2X 1 - 2X 2 equals ...

23. The region of feasible solutions of the linear programming problem has the form:

F(X 1, X 2)= 2X 1 - 2X 2 equals ...

24. The region of feasible solutions to the problem of nonlinear programming has the form:

Then the maximum value of the function F(X 1, X 2)= X 2 – X 12 equals ...

25. Maximum value of the objective function F(X 1, X 2)= 5X 1 + 2X 2 with restrictions
X 1 + X 2 ≤ 6,

X 1 ≤ 4,

X 1 ≥ 0, X 2 ≥ 0, equals ...

26. A small business produces products of two types. For the manufacture of one product of type A, 2 kg of raw materials are consumed, for the manufacture of one product of type B - 1 kg. There are 60 kg of raw materials in total. It is required to draw up a production plan that ensures the receipt of the largest proceeds, if the selling cost of one product of type A is 3 units, type B is 1 unit. That is, products of type A need to be made no more than 25, and type B - no more than 30.

This task is ...

linear programming problem

the problem solved by the dynamic programming method

task of network planning.

27. A small business produces products of two types. For the manufacture of one product of type A, 2 kg of raw materials are consumed, for the manufacture of one product of type B - 1 kg. There are 60 kg of raw materials in total. It is required to draw up a production plan that ensures the receipt of the largest proceeds, if the selling cost of one product of type A is 3 units, type B is 1 unit. That is, products of type A need to be made no more than 25, and type B - no more than 30.

The objective function of this task is the function ...

F(x1, x2)=3x1+x2→max

F(x1, x2)=25x1+30x2→max

F(x1, x2)=2x1+x2→max

F(x1, x2)=60 -2x1 - x2→min

28. A small business produces products of two types. For the manufacture of one product of type A, 2 kg of raw materials are consumed, for the manufacture of one product of type B - 1 kg. There are 60 kg of raw materials in total. It is required to draw up a production plan that ensures the receipt of the largest proceeds, if the selling cost of one product of type A is 3 units, type B is 1 unit. That is, products of type A need to be made no more than 25, and type B - no more than 30

A valid plan for this task is a plan:

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. In two points A1 and A2, there are respectively 60 and 160 units of goods. All goods need to be transported to points B1, B2, B3 in the amount of 80, 70 and 70 units, respectively. The tariff matrix is ​​as follows:. Plan transportation so that the cost is minimal.

This task is ...

transport task

nonlinear programming problem

traveling salesman problem

assignment task

30. In two points A1 and A2, there are respectively 60 and 160 units of goods. All goods need to be transported to points B1, B2, B3 in the amount of 80, 70 and 70 units, respectively. The tariff matrix is ​​as follows:. Plan transportation so that the cost is minimal

The basic plan for this task is the plan:

;

31. In two points A1 and A2, there are respectively 60 and 160 units of goods. All goods need to be transported to points B1, B2, B3 in the amount of 80, 70 and 70 units, respectively. The tariff matrix is ​​as follows:. Plan transportation so that the cost is minimal.

The objective function of this task is the function:

F=4x11+6x12 + 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2 + 80x3+70x4+705 →max

F=60x1+160x2– 80x3– 70x4– 705 →min

32. In two points A1 and A2, there are respectively 60 and 160 units of goods. All goods need to be transported to points B1, B2, B3 in the amount of 80, 70 and 70 units, respectively. The tariff matrix is ​​as follows:. Plan transportation so that the cost is minimal.

The optimal plan for this task is the plan:

;

.

;

;

33. Transport problem

will be closed if ...

34. Transport problem

is an…

open

closed

insoluble

35. Transport problem

is an…

closed

open

insoluble

36. To solve the following transport problem

you must enter ...

fictitious consumer

fictitious supplier;

effective tariff

37. To solve the following transport problem

you must enter ...

fictitious supplier;

fictitious consumer

effective tariff

effective interest rate.

38. Among these transport tasks

closed are ...

39. The initial baseline plan of the transport problem can be drawn up ...

by all the above methods

Northwest corner method

by the minimum tariff method

double preference method

by the Vogel approximation method

40. If the objective function of the linear programming problem is set to the maximum, then ... the objective function of the dual problem is set to the minimum

there is no objective function in the dual problem

the dual problem has no solutions

the dual problem has infinitely many solutions

41. A linear programming problem is given:

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

The following will be dual for this task ...

F *(y1, y2) = 14y1 + 8y2 → min,

3y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 £ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 £ 0.

F *(y1, y2) = 14y1 + 8y2 → min,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

42. If one of a pair of dual problems has an optimal plan, then ...

and the other has an optimal plan

the other has no optimal plan

the other has no feasible solutions

43. If one of the pair of dual problems has an optimal plan, then ...

and the other has an optimal plan and the values ​​of the objective functions for their optimal plans are equal to each other

and the other has an optimal plan, but the values ​​of the objective functions for their optimal plans are not equal to each other

another problem may not have an optimal plan, but have feasible solutions

44. If the objective function of one of the pair of dual problems is not bounded (for the maximum problem - from above, for the minimum problem - from below), then

another task has no valid plans

another task has feasible plans, but does not have an optimal plan

the objective function of another task is also not limited

45. When solving some problems of nonlinear programming, it is used ...

Lagrange multiplier method

Gauss method

Vogel approximation method

Gomori method

46. ​​The problem of nonlinear programming is set

F(X 1, X 2)= X 12 + X 22 → max,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

not reachable (+ ¥)

47. The problem of nonlinear programming is set

F(X 1, X 2)= X 12 + X 22 → min,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

48. The problem of nonlinear programming is set

F(X 1, X 2)= X 12 + X 22 → max,

X 1 + X 2 =6,

X 1, X 2 - any.

The highest value of the objective function F(X 1, X 2) …

not reachable (+ ¥)

49. The problem of nonlinear programming is set

F(X 1, X 2)= X 12 + X 22 → min,

X 1 + X 2 =6,

X 1, X 2 - any.

The smallest value of the objective function F(X 1, X 2) …

not reachable (- ¥)

50. The region of feasible solutions to the problem of nonlinear programming has the form:

Then the maximum value of the function F(X 1, X 2)= X 12 +X 22 equals ...

51. The region of feasible solutions to the problem of nonlinear programming has the form:

Then the minimum value of the function F(X 1, X 2)= X 12 +X 22 equals ...

52. To solve the transport problem can be applied ...

potential method

Lagrange multiplier method

Gauss method

disorientation method

53. In the system of constraints of the general linear programming problem ...

54. In the system of constraints of the standard (symmetric) linear programming problem ...

only inequalities can be present

both equations and inequalities can be present

only equations can be present

55. In the system of constraints of the canonical (basic) linear programming problem ...

only equations can be present (provided that the variables are nonnegative)

only inequalities can be present (provided that the variables are nonnegative)

both equations and inequalities can be present (provided that the variables are nonnegative)

56. The problem of linear programming

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

recorded in ...

standard (symmetrical) form

canonical (basic) form

verbal form

57. To record a task

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

in canonical form ...

58. To record a task

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

in canonical form ...

it is necessary to introduce three additional non-negative variables

it is necessary to introduce two additional non-negative variables

it is necessary to introduce four additional non-negative variables

59. To record a task

F(X 1, X 2)= 2X 1 + 7X 2 → max,

2X 1 + 3X 2 = 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

in canonical form ...

it is necessary to introduce two additional non-negative variables

it is necessary to introduce three additional non-negative variables

it is necessary to introduce four additional non-negative variables

it is necessary to introduce five additional non-negative variables

60. When solving problems of integer programming, it can be used ...

Gomori method

Lagrange multiplier method

Gauss method

Vogel approximation method

61. At the heart of solving problems by the method of dynamic programming is ...

Occam's razor

the principle "a tooth for a tooth, an eye for an eye"

Heisenberg principle

62. A situation in which parties are involved, whose interests are completely or partially opposite, is called ...

(conflict, conflict, conflict, conflict)

63. An actual or formal conflict in which there are at least two participants (players), each of whom strives to achieve their own goals, is called ...

(game, game)

64. The permissible actions of each of the players, aimed at achieving a certain goal, are called ...

(game rules, game rules)

65. The quantitative assessment of the results of the game is called ...

(by payment, payment, payment)

66. If only two sides (two persons) participate in the game, then the game is called ...

(doubles, doubles, doubles, doubles)

67. If in a doubles game the sum of payments is equal to zero, that is, the loss of one player is equal to the gain of the other, then the game is called a game ...

(zero sum)

68. An unambiguous description of the player's choice in each of the possible situations in which he must make a personal move is called ..

(player strategy, player strategy, strategy, strategy)

69. If, with multiple repetitions of the game, the strategy provides the player with the maximum possible average gain (minimum possible average loss), then such a strategy is called ...

(optimal, optimal, optimal strategy, optimal strategy)

70. Let a be the low price and b the high price of a zero-sum doubles game. Then the statement is true ...

71. Let a be the low price and b the high price of a zero-sum doubles game. If a = b = v, then the number v is called ...

at the cost of the game

equilibrium point

optimal strategy

mixed strategy

72. Let a be the low price and b the high price of a zero-sum doubles game. If a = b, then the game is called ...

saddle point game

insoluble conflict

a game without rules

73. A vector, each of whose components shows the relative frequency of the player's use of the corresponding pure strategy, is called ...

mixed strategy

direction vector

normal vector

gradient

74. The lower price of the matrix game, given by the payment matrix, is equal to ...

More bottom price

equal to the bottom price

does not exist

81. A matrix game given by a payoff matrix, ...

has a saddle point

has no saddle point

not paired

82. The price of the game, given by the payoff matrix, is ...

83. A matrix game given by a payoff matrix ...

is paired

has a saddle point

not paired

84. Zero-sum doubles game, given by its pay-off matrix, can be reduced to ...

linear programming problem

nonlinear programming problem

integer linear programming problem

classical optimization problem

85. The lower price of the matrix game given by the payment matrix is ​​...

More bottom price

equal to the bottom price

does not exist

92. A matrix game given by a payoff matrix ...

has no saddle point

has a saddle point

not paired

93. The price of the game, given by the payment matrix, is within ...

94. If in the stream of events events follow one another at predetermined and strictly defined intervals of time, then such a stream is called ...

regular

organized

95. If the probability of any number of events falling on a time interval depends only on the length of this interval and does not depend on how far this interval is located from the start of time, then the corresponding stream of events is called:

stationary

flow without consequences

the simplest

Poisson

96. If the number of events falling on one of the arbitrarily chosen time intervals does not depend on the number of events falling on another, also arbitrarily chosen time interval, provided that these intervals do not intersect, then the corresponding stream of events is called ...

flow without consequences

regular

indicative

normal

97. If the probability of two or more events hitting a very short time interval at once is negligible compared to the probability of hitting only one event, then the corresponding stream of events is called ...

ordinary

extraordinary

normal

Poisson

98. If the flow of events simultaneously possesses the properties of stationarity, ordinariness and absence of consequences, then it is called:

simplest (Poisson)

normal

99. A single-channel system with failures is a daily service station for car wash. Application - a car that arrived at the moment when the post is occupied - receives a denial of service. Car flow rate λ = 1.0 (car per hour). Average service time is 1.8 hours. Car flow and service flow are the simplest. Then, in the steady state, the relative throughput q equals ...

100. A single-channel system with failures is a daily service station for car wash. Application - a car that arrived at the moment when the post is occupied - receives a denial of service. Car flow rate λ = 1.0 (car per hour). Average service time is 1.8 hours. Car flow and service flow are the simplest. Then, in the steady state, the percentage of cars that receive a denial of service is ...

General formulation of the linear programming problem (LPP). Examples of LPP

Linear programming is a branch of mathematics that studies methods for solving extreme problems, which are characterized by a linear relationship between variables and a linear criterion of optimality. A few words about the very term linear programming. It requires correct understanding. In this case, programming is, of course, not writing computer programs. Programming here should be interpreted as planning, the formation of plans, the development of an action program. Mathematical problems of linear programming include the study of specific production and economic situations, which in one form or another are interpreted as problems of the optimal use of limited resources. The range of tasks that can be solved using linear programming methods is quite wide. This is, for example:

• - the problem of the optimal use of resources in production planning;
• - the problem of mixtures (planning the composition of products);
• - the problem of finding the optimal combination of various types of products for storage in warehouses (inventory management or "knapsack problem");
• - transport tasks (analysis of the location of the enterprise, movement of goods). Linear programming is the most developed and widely used branch of mathematical programming (in addition, this includes: integer, dynamic, nonlinear, parametric programming). This is due to the following:
• - mathematical models of a large number of economic problems are linear with respect to the sought variables;
• - this type of problem is currently the most studied. For him, special methods have been developed with the help of which these tasks are solved, and the corresponding computer programs;
• - many problems of linear programming, having been solved, have found wide application;
• - some problems that in the original formulation are not linear, after a number of additional restrictions and assumptions can become linear or can be reduced to such a form that they can be solved by linear programming methods. The economic and mathematical model of any linear programming problem includes: an objective function, the optimal value of which (maximum or minimum) needs to be found; restrictions in the form of a system of linear equations or inequalities; requirement of non-negativity of variables. In general terms, the model is written as follows:
• - objective function:

C1x1 + c2x2 + ... + cnxn> max (min); - restrictions:

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

Non-negativity requirement:

In this case, aij, bi, cj () are given constants. The problem is to find the optimal value of function (2.1) subject to constraints (2.2) and (2.3). The system of constraints (2.2) is called the functional constraints of the problem, and constraints (2.3) are called direct. A vector satisfying constraints (2.2) and (2.3) is called a feasible solution (plan) of the linear programming problem. The design in which function (2.1) reaches its maximum (minimum) value is called optimal.

Below are examples of some typical problems solved using linear programming methods. Such tasks have real economic content. Now we will only formulate them in terms of LPP, and we will consider methods for solving such problems below.

1. The problem of the optimal use of resources in production planning. The general meaning of the tasks of this class is as follows. The enterprise produces n different products. Their production requires m different types of resources (raw materials, materials, labor time, etc.). Resources are limited, their reserves in the planning period are, respectively, b1, b2, ..., bm conventional units. Technological coefficients aij are also known, which show how many units of the i-th resource are required to produce a unit of the j-th type of product (). The profit received by the enterprise from the sale of the product of the j-th type is equal to cj. In the planning period, the values ​​of aij, bi and cj remain constant. It is required to draw up such a production plan, in the implementation of which the profit of the enterprise would be the greatest. Below is a simple example of a task of this class.

The company specializes in the production of hockey sticks and chess sets. Each club generates $ 2 in profit for the company, and $ 4 for each chess set. It takes four hours to make one club in Site A and two hours in Site B. A chess set is made with six hours in Site A, six hours in Site B and one hour in Site C. The available production capacity in Site A is 120 Nm. - hours a day, section B - 72 n-hours and section C - 10 n-hours. How many clubs and chess sets should a company produce daily to maximize profits?

The conditions for problems of this class are often presented in tabular form (see Table 2.1).

Under this condition, we formulate a linear programming problem. Let's designate: x1 - the number of hockey sticks produced daily, x2 - the number of chess sets produced daily. ZLP wording:

4x1 + 6x2? 120,

Let us emphasize that each inequality in the system of functional constraints corresponds in this case to one or another production site, namely: the first to site A, the second to site B, and the third to site C.

The system of variables in the problem of optimizing the structure of sown areas, taking into account crop rotations