Transition from the limitations of a linear mathematical model. Create a mathematical model of a linear programming problem. Choice of the volume of redistribution
Lecture 2
V canonical form
acceptable decision of the LPP(acceptable plan).
the optimal solution to the LPP.
Need
Example. 
Let's write the task in canonical form
Special situations of the graphic solution of the LPP
Except when the problem has the only optimal solution for and maybe special situations:
1.problem has infinite number of optimal solutions - the extremum of the function is reached on the interval ( alternative optimum)- Figure 2;
2.task not solvable due to the unboundedness of the IDT, or - Figure 3;
3. SDT - single point Ah, then;
4.task not solvable if the ODR is an empty area.
A
Picture 2 Picture 3
If the level line is parallel to the side of the region of feasible solutions, then the extremum is reached at all points of the side. The problem has countless optimal solutions - alternative optimum ... The optimal solution is found by the formula
where is the parameter. For any value from 0 to 1, you can get all points of the segment, for each of which the function takes the same value. Hence the name - alternative optimum.
Example... Solve the problem graphically linear programming (alternative optimum):
Questions for self-control
1. Write down a 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 pass from the general or standard form of the linear programming problem to the canonical one?
4. Give the definition of the feasible and optimal solutions to the linear programming problem.
5. Which of the solutions is the “best” for the problem of minimizing a function if 
?
6. Which of the solutions is the “best” for the problem of maximizing a 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 in two variables 
?
9. What is called the solution of a system of linear inequalities in two variables? Construct on the plane the region of feasible solutions of such a system of linear inequalities, which:
1) has a unique solution;
2) has an infinite number of solutions;
3) does not have a single solution.
10. Make a note for linear function 
vector gradient, name the kind of level lines. How are the gradient and level lines positioned relative to each other?
11. Formulate an algorithm for a graphical method for solving a standard LPP with two variables.
12. How to find the solution coordinates and values?
13. Plot the area of feasible solutions, gradient and level lines, for linear programming problems, in which:
1) is attained at a single point, and - on the segment ODR;
2) is attained at a single point of the ODR, and.
14. Give a geometric illustration of the LPP, if it is:
1) has the only optimal solutions for and;
2) has many optimal solutions for.
Lecture 2
graphical method finding the optimal solution
1. Forms of linear mathematical models and their transformation
2. A graphical method for solving a linear programming problem
3. Special situations of the graphic solution of the LPP
4. Graphical solution of economic problems of linear programming
Forms of linear mathematical models and their transformation
The mathematical model of a linear programming problem (LPP) can be written in one of three forms.
V general form of mathematical model it is required to find the maximum or minimum of the objective function; the system of constraints contains inequalities and equations; not all variables can be non-negative.
V canonical form the mathematical model is required to find the maximum of the objective function; the system of constraints consists only of equations; all variables are non-negative.
In the standard form of a mathematical model, it is required to find the maximum or minimum of a function; all constraints are inequalities; all variables are non-negative.
A solution to a system of constraints that satisfies the conditions of non-negativity of variables is called acceptable decision of the LPP(acceptable plan).
The set of feasible solutions is called the area of admissible solutions of the LPP.
A feasible solution at which the objective function reaches an extreme value is called the optimal solution to the LPP.
The three forms of writing LPP are equivalent in the sense that each of them can be reduced to a different form using mathematical transformations.
Need transition from one form of a mathematical model to another is associated with methods of 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 form of LPP.
Example.
Let's write the task in canonical form by introducing an additional (balance) variable with a "+" sign in the left side of the first inequality of the system of restrictions, and an additional variable with a minus sign in 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 constraints 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 the optimal technologies - the unused time of the enterprise for a certain technology; in the cutting problem - the release of blanks of a given length over the plan, etc.
Definition. Linear Programming (LP) - the science of research methods and finding the extreme (largest and smallest) values of a linear function, the unknowns of which are subject to linear constraints.
This linear function is called target, and constraints that are mathematically written in the form of equations or inequalities are called system of restrictions.
Definition. The mathematical expression of the objective function and its limitations is called mathematical model of the economic problem.
In general, the mathematical model of a linear programming problem (LP) is written as
with restrictions:
where x j- unknown; a ij, b i, c j- given constant values.
All or some of the equations of the system of constraints can be written in the form of inequalities.
The mathematical model in a more concise notation has the form
with restrictions:
Definition. A feasible solution (plan) of a linear programming problem is a vector = ( x 1 , x 2 ,..., x n), satisfying the system of restrictions.
The set of feasible solutions forms the area of feasible solutions (ODS).
Definition. A feasible solution at which the objective function reaches its extreme value is called the optimal solution to the linear programming problem and is denoted by opt.
Basic feasible solution (NS 1 , NS 2 , ..., x r , 0, …, 0) is the reference solution, where r - the rank of the system of restrictions.
The mathematical model of the LP problem can be canonical and non-canonical.
7.Solution of linear programming problems by graphical method... Function-constraints graphs. Level lines.
Graphical method for solving linear programming problems
The simplest and most intuitive method of linear programming is the graphical method. It is used to solve LP problems with two variables given in non-canonical form and many variables in canonical form, provided that they contain at most two free variables.
From a geometric point of view, in a linear programming problem, one looks for such a corner point or a set of points from the feasible set of solutions at which the highest (lowest) level line is reached, located farther (closer) than the others in the direction of the fastest growth.
To find the extreme value of the objective function in the graphical solution of LP problems, use the vector L() on surface NS 1 OH 2 , which we denote . This vector shows the direction of the fastest change in the objective function. In other words, the vector is the normal of the level line L()
where e 1 and e 2 - unit vectors along the axes OX 1 and OX 2 respectively; thus = (∂L / ∂х 1 , ∂L / ∂х 2 ).
The coordinates of the vector are the coefficients of the objective function L (). The construction of the level line will be considered in detail when solving practical problems.
Algorithm for solving problems
1. Find the region of feasible solutions to the system of constraints of the problem.
2. Building a vector .
3. Draw a level line L 0 , which is perpendicular .
4. Move the level line in the direction of the vector for tasks to the maximum and in the opposite direction , for tasks to a minimum.
The level line is moved until it has only one common point with the area of admissible solutions. This point, which determines the only solution to the LP problem, will be the extremum point.
If it turns out that the level line is parallel to one of the sides of the ODR, then the extremum is reached at all points of the corresponding side, and the LP problem will have an infinite number of solutions. It is said that such an LP problem has alternative optimum, and its solution is found by the formula:
Where 0 ≤ t≤ 1, 1 and 2 - optimal solutions at the corner points of the ODR.
The LP problem can be unsolvable when the constraints defining it turn out to be contradictory.
5.
Find the coordinates of the extremum point and the value of the objective function in it.
Example 3. Selection of the optimal product release option
The company produces 2 types of ice cream: creamy and chocolate. For the manufacture of ice cream, two initial products are used: milk and fillers, the costs of which per 1 kg of ice cream and daily stocks are given in the table.
The study of the sales market showed that the daily demand for ice cream exceeds the demand for chocolate ice cream, but by no more than 100 kg.
In addition, it was found that the demand for chocolate ice cream does not exceed 350 kg per day. Retail price of 1 kg of creamy ice cream 16 rubles, chocolate - 14 rubles.
How much ice cream of each type should the firm produce in order to maximize the income from product sales?
Solution. Let's denote: x 1 - daily volume of ice cream production, kg; x 2 - daily output of chocolate ice cream, kg.
Let's compose mathematical model tasks.
The prices for ice cream are known: 16 rubles and 14 rubles, respectively, so the objective function will look like:
We will set limits on milk for ice cream. Its consumption for creamy ice cream - 0.8 kg, for chocolate - 0.5 kg. Milk stock 400kg. Therefore, the first inequality will look like:
0.8x 1 + 0.5x 2 ≤400 - the first inequality is a limitation. The rest of the inequalities are composed in a similar way.
The result is a system of inequalities. that is the solution area of each inequality. This can be done by substituting the coordinates of the point O (0: 0) into each of the inequalities. As a result, we get:
Figure OABDEF - area of admissible solutions. We build a vector (16; 14). Level line L 0 is given by the equation 16x 1 + 14x 2 = Const. We choose any number, for example the number 0, then 16x 1 + 14x 2 = 0. In the figure, for the line L 0, a certain positive number is selected that is not equal to zero. All level lines are parallel to each other. Level line normal vector.
Move the level line in the direction of the vector. Exit point L 0 from the region of feasible solutions is the point D, its coordinates are determined as the intersection of straight lines given by the equations:
Solving the system, we get the coordinates of the point D(312.5; 300), in which there will be an optimal solution, i.e.
Thus, the company should produce 312.5 kg of ice cream and 300 kg of chocolate ice cream per day, while the income from sales will amount to 9,200 rubles.
8. Reduction of an arbitrary linear programming problem to the main problem. Converting inequality constraints into corresponding equations.
9.Simplex method... Description and algorithm of the method, its applicability.
To solve the problem using the simplex method, it is necessary:
1. Indicate a way to find the optimal support solution
2. Indicate the method of transition from one support solution to another, at which the value of the objective function will be closer to the optimal one, ie. indicate a way to improve the reference solution
3. Set the criteria that allow you to timely stop the search for support solutions on the optimal solution or to pass a conclusion on the absence of an optimal solution.
Algorithm of the simplex method for solving linear programming problems
1. Bring the problem to the canonical form
2. Find the initial support solution with a "unit basis" (if there is no support solution, then the problem has no solution, due to the incompatibility of the system of constraints)
3. Calculate the estimates of the vector expansions in the basis of the support solution and fill in the table of the simplex method
4. If the criterion of uniqueness of the optimal solution is satisfied, then the solution to the problem ends
5. If the condition for the existence of a set of optimal solutions is satisfied, then by a simple enumeration all optimal solutions are found
10. Transport problem. Definition, types, methods of finding the initial solution of the transport problem.
The transport problem is one of the most common linear programming problems. Its goal is to develop the most rational ways and means of transporting goods, eliminating excessively long-distance, oncoming, repeated transportation.
1. Finding the original support solution;
2. Checking this solution for optimality;
3. Transition from one support solution to another.
3.1. General linear programming problem
Linear programming- this is the most developed section mathematical programming, with the help of which the analysis and solution of extreme problems with linear connections and constraints are carried out.
Linear programming includes a number of heuristic (approximate) solution methods that allow, under given conditions, of all possible options solutions to production problems to choose the best, optimal. These methods include the following - graphic, simplex, potential method (modified distribution method - MODI), Hitchkova, Kreko, Vogel approximation method and others.
Some of these methods are united by a common name - 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 specified Nobel Prize also recognizes 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 cargo; shift-daily planning; planning of transportation of small-lot cargo; distribution of buses by routes and others.
The features of the linear programming model are as follows:
The objective function and constraints are expressed by linear dependencies (equalities or inequalities);
The number of dependencies is always less than the number of unknowns (uncertainty condition);
Non-negativity of the sought variables. The general form of writing a linear programming model in an abbreviated form is as follows:
Find NS ij ≥ 0 (j = 1, 2 ... n) under constraints of the following type:
These constraints minimize (or maximize) the objective function
The standard form of writing a linear programming model is the system linear equations recorded in canonical form, that is, in the form of linear equalities, in non-negative numbers:
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.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, that is, 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 record is reduced to canonical form (3.1) by introducing additional variables x n +1> 0 (i=1,2…m) to the left of the inequality (or cancellation of the number of variables, if the inequality sign is directed in the other direction). Additional variables make up 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. In this case, the objective function has the form
L = s 1 x 1 + s 2 x 2 ... s n x n → min, (3.3)
where s 1, s 2 ... s n- coefficients of the objective function L with variables NS 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 again come to the problem of minimization, i.e. one task is reduced to another by substitution L on - L or max L= min (- L).
A basic solution to the 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 optimal solution is a feasible solution that maximizes (or minimizes) the objective function (3.3).
Each linear programming problem corresponds to another, called the dual linear programming problem. The original problem with respect to the dual is called direct. Direct and dual problems form a pair, called a dual pair in linear programming. The direct and dual pair form an asymmetric pair when the direct problem is written in canonical form, and a symmetric pair when the problem conditions are written by inequalities.
The rules for compiling a mathematical model of the 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 duality property is considered in detail in each specific case.
3.2. Graphic-analytical method
The graphoanalytic method is one of the simplest methods of linear programming. He 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, that is, it is applicable for 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 in the sense of the problem should not be negative, is performed in the Cartesian coordinate system. Equations x 1= 0 and x 2= 0 are the axes of the first quadrant coordinate system
Let us consider the solution method using a specific example.
Example 3.1. There are 300 tons of foam concrete products and 200 tons of steel in the warehouse. The car company 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 ride 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 ensure the greatest profit for the car company.
Let's build a mathematical model of the problem. Let us denote by x 1 the required number of KamAZ-5320 riders and through NS 2 the required number of riders ZIL-4314.
Total carriage in t of foam concrete products is 6 x 1 + 2x 2, and from steel 2 x 1 + 4x 2... Transportation restrictions based on the number of items available are 6 x 1 + 2x 2 ≤ 300t for foam concrete and 2 x 1 + 4x 2 ≤ 200t for steel.
Total profit in thousand rubles is expressed as 4 NS 1 + 6NS 2, which needs to be maximized and which is the criterion of optimality in the problem under consideration. Thus, the mathematical model of the problem looks as follows. 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 straight line described by this equation, we find two points lying on this straight line. At x 1= 0 from the equation of the straight line we find 2 x 2 = 300, whence x 2 = 150. Therefore, point A with coordinates (0,150) lies on the desired straight line. At x 2= 0 we have 6 x 1= 300, whence x 1 = 50, and point D with coordinates (50,0) is also on the sought line. Draw a straight line through these two points AD(fig. 3.1).
Linear inequality 6 x 1 + 2x 2 ≤ 300 is a half-plane located on one of the sides of the constructed straight line 6 x 1 + 2x 2 = 300. To find out on which side of this straight line the points of the required half-plane are located, we substitute 6 x 1 + 2x 2 ≤ 300 coordinates of any point that does not lie on the boundary line. For example, the origin is 0- (0,0). For him, the inequality 6 ∙ 0 + 2 ∙ 0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD and in fig. 3.1 is shaded.
Equation 2 x 1 + 4x 2= 200 we will build on two points. At x 1 = 0 4x 2 = 200, from where x 2 = 50. Then the point E has coordinates (0.50) and belongs to the desired straight line. At x 2= 0, 2x 2 = 200, point with is located on the given line with coordinates (100,0). Substituting the coordinates of the point into the inequality with(0,0), we get 2 ∙ 0 + 4 ∙ 0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.
The system of task constraints requires that plans ( x 1; x 2) satisfy all four inequalities, i.e., admissible designs are points ( x 1; x 2) must be simultaneously 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 feasible 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 problem, 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 clear geometric representation can also be obtained for the objective function. L = 4x 1 + 6x 2... Let's fix some value of the objective function, for example L= 120.equation 4 x 1 + 6x 2 = 120 defines a line through a point V with coordinates (x 1 = 0; x 2 = 20) and point L with coordinates (( NS 1 = 30; NS 2 = 0). Section 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. By assigning other values to the objective function, we obtain parallel lines, which are called level lines objective function.
Moving straight 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 the straight line BL to the right determines the increase in the objective function that we are maximizing. We do this as long as the straight BL will have at least one common point with the polygon of feasible solutions OEKD... Fig. 3.1 it follows that the last point crossed by the straight line of the objective function level will be the point TO... This means that the point TO determines the optimal task plan.
The ascending direction perpendicular to the level line is called direction of greatest increase the objective function and determines its maximum growth. This direction can be set without drawing level lines. For this it is necessary on the axes x 1 and x 2 to postpone the segments equal to the coefficients of the objective function, and from them, as coordinates, to construct the vector of the greatest increase of the objective function. In mathematics, it is called gradient and denote by grad. Gradient for function L = 4x 1 + 6x 2 there will be a vector n| 4; 6 | ... For the convenience of its construction, we will increase the coordinates, for example, 10 times, i.e. n | 40; 60 | ... 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 plotted perpendicular to the direction of the gradient.
So, in one way or another it has been established that the point TO determines the optimal plan of the problem, 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.
Let's equalize the coefficients at x 1 by multiplying the second equation by 3, and subtract the first from the second equation. We get 10 x 2= 300,x 2 = 30. Substituting the value x 2 = 30 in any of the equations, for example, in the first, we determine the value NS 1:
6x 1+ 2NS · 30 = 300,
whence 6 x 1 = 300 - 60 = 240, therefore x 1 = 40.
Thus, in order to get the greatest profit, the auto enterprise needs to complete 40 trips on the KamAZ-5320 and 30 trips on the ZIL-4314. The maximum profit in this case will be
L = 4x 1 + 6x 2= 4 40 + 6 30 = 340 thousand rubles.
Based on the considered example and the geometric interpretation of the optimization problem with two variables, the following conclusions can be drawn:
1) in two-dimensional space, the region 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 feasible solutions corresponds to the values of two variables equal to zero;
4) a straight line corresponds to each value of the objective function;
5) the optimal solution of the problem corresponds to the vertex of the polygon, in which the objective function acquires the optimal value, and the coordinates of this vertex are the optimal variables.
In general, optimization problems have a similar geometric interpretation. The set of plans of the problem will be a polyhedron, the vertices of which correspond to the reference plans. When solving the problem, a transition is made from one vertex of the polyhedron to another with a large value of the objective function until its optimal value is obtained. Note that the efficiency of optimization methods lies precisely in the fact that the search of vertices (iteration) is carried out only in the direction of the greatest increase in the objective function. Therefore, not all peaks, of which there are a huge number, are considered, but only those that are closer to the extreme.
When defining 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 nonlinear objective function.
By definition, the 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.
In fig. 3.2b depicts nonconvex sets. In nonconvex 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", which means 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. Danzig in the late 1940s.
The simplex method includes obtaining a nonnegative basic solution of a system of canonical linear equations of the type (3.1), subsequent minimization (maximization) of the objective function (3.3) and finding in this way the optimal values of the sought variables x 1, x 2 ... x n.
The idea of the simplex method is that in the process of computing, one passes sequentially from the first basic solution to the second, third, etc. through the so-called simplex transformations. Conversions are performed in the form of simplex tables, which greatly simplifies and speeds up the 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: as a new base variable, any free variable is taken, for which there is at least one positive coefficient; a variable is derived from the basis that corresponds to the smallest ratio of free terms of equations to the corresponding positive coefficients of the equations for the variable introduced into the basis. Such transformations are called simplex converters.
This is very important, since in order to find a particular non-negative solution corresponding to the largest possible value of any one free variable at zero values of other free variables, instead of determining the range of the specified variable and substituting its maximum possible value into the general solution, it is enough 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.
It is convenient to perform calculations 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, one goes to the basis, for which the optimal (minimum or maximum) value of the objective function is obtained. Let's consider the simplex method in general.
The general problem of linear programming is to minimize (maximize) the objective function, the variables of which are interconnected by a system of linear equations, are subject to the condition of non-negativity.
Let it be necessary to minimize the linear form
L = with 1 x 1 + with 2 x 2 + ... with n x n.
Under the conditions (for clarity, zero and one coefficients in the equations are preserved):
1x 1+ 0x 2 + ... 0x m + a 1m + 1x m + 1 ... + a 1n x n = b 1;
0x 1 + 1x 2 +… 0x m + a 2m + 1x m + 1 ... + a 2n x n = b 2;
……………………………………………
0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n = b m.
In this system of equations, there is already a ready-made basis, since each equation of restrictions contains an unknown with a coefficient equal to one, which is not in other equations, that is, from the coefficients of the variables NS 1 , NS 2 …, x m you can compose the identity matrix.
Let's solve the equations for the basic variables:
x 1 = b 1 - (a 1m + 1 · x m + 1 ... + a 1n x n);
x 2 = b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);
………………………………
x m = b m - (a mm + 1x m + 1 ... + a mn x n),
and we express the objective function in terms of free variables, substituting their expressions in terms of free variables in place of the basic variables:
L = c 1 b 1 + c 2 b 2 + cmbm - (c 1 a 1m + c 2 a 2m + 1 +… + cma mn + 1) x m + 1 -… - (c 1 a 1n + c 2 a 2n +… + cma mn) xn… + cnx 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 nonnegativity condition, the smallest value of free variables is zero. The obtained basic solution of the system of equations is its initial admissible solution, i.e. x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 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 tested for optimality. If it is not optimal, then by introducing free variables into the basis, the following feasible solutions with a smaller value of the objective function are found. To do this, define a free variable that must be entered into the basis, as well as a variable that must be derived from the basis. Then one moves from the previous system to the next equivalent system. This is done using simplex tables. The solution to the problem continues until the optimal value of the objective function is obtained.
Simplex tables are composed as follows (see table 3.1). All variables are placed at the top of the table NS 1 , NS 2 …, x n and coefficients c j, with which the corresponding variables are included in the target 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 equations. The elements of the remaining columns of the table represent the coefficients of the variables with which the latter are included in 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 define
∆j = z j - c j,
where c j- the coefficients for the corresponding variables in the objective function; z j - the sum of the products of the coefficients of the objective function for basic variables by the corresponding variables - elements j-Th column of the table.
table 3.1
Simplex table with initial valid
In practice, constraints in a linear programming problem are often specified not by equations, but by inequalities.
Let us show how we can go from the problem with inequality constraints to the main problem of linear programming.
Let there be a linear programming problem with variables, in which the constraints imposed on the variables are in the form of linear inequalities. In some of them, the inequality sign may be, while in others (the second type is reduced to the first by a simple change in the sign of both parts). Therefore, we set all inequality constraints in the standard form:
It is required to find a set of nonnegative values that would satisfy inequalities (4.1), and, moreover, would minimize the linear function:
It is easy to pass from the task set in this way to the main task of linear programming. Indeed, let us introduce the notation:
where are some new variables, which we will call "additional". According to conditions (4.1), these additional variables, as they should, be non-negative.
Thus, we are faced with a linear programming problem in the following formulation: find such nonnegative values of the variables so that they satisfy the system of equations (4.3) and simultaneously reduce the linear function of these variables to a minimum:
As you can see, we have before us in its pure form the main task of linear programming (LPP). Equations (4.3) are given in the form already allowed for basic variables that are expressed in terms of free variables. The total number of variables is equal, of which "initial" and "additional". The function L is expressed only in terms of the "initial" variables (the coefficients of the "additional" variables in it are equal to zero).
Thus, we have reduced the problem of linear programming with inequality constraints to the main problem of linear programming, but with a larger number of variables than was originally in the problem.
Example 1 There is a linear programming problem with inequality constraints: find non-negative values of variables satisfying the conditions
and minimizing the linear function
It is required to bring this task to the form of an OZLP.
Solution. We reduce inequalities (4.4) to the standard form;
We introduce additional variables:
The task is reduced to finding the non-negative values of the variables
satisfying equations (4.6) and minimizing the linear function (4.5).
We have shown how we can go from a linear programming problem with inequality constraints to a problem with equality constraints (LPPP). The reverse transition is always possible - from the LPP to the problem with inequality constraints. If in the first case we increased the number of variables, then in the second case we will decrease it, eliminating the basic variables and leaving only free ones.
Example 2. There is a linear programming problem with equality constraints (LPPP):
and the function to be minimized
It is required to write it down as a linear programming problem with inequality constraints.
Solution. Since, then we will choose some two of the variables as free. Note that the variables cannot be chosen as free variables, since they are related by the first of equations (4-7): the value of one of them is completely determined by the value of the other, and free variables must be independent
For the same reason, it is impossible to choose variables as free (they are connected by the second equation). Let's choose as free variables and express all the others through them:
Since conditions (4 9) can be replaced by inequalities:
Let us pass in the expression of the linear function L to free variables Substituting in L instead of their expressions (4.9). we get.
Basic modeling concepts
In the process of human activity, ideas about certain properties of real objects and their interactions are developed. These representations are formed by a person in the form of descriptions of objects for which a description language is used. This can be a verbal description (verbal models), drawing, drawing, graph, layout, etc. All of the above is summarized by one concept model, and the process of building models is modeling.
Modeling Is a universal way of studying processes and phenomena of the real world. Modeling is of particular importance in the study of objects inaccessible to direct observation and research. These include, in particular, socio-economic phenomena and processes.
The study of any object, any form of movement is the disclosure of not only its qualitative, but also quantitative laws studied by mathematics. The foregoing fully applies to the economy.
Economy- This is a system of social production that actually carries out the production, distribution, exchange and consumption of material goods necessary for society.
Respectively, economic and mathematical model Is an economic abstraction expressed in formal mathematical terms, the logical structure of which is determined both by the objective properties of the subject of description and by the subjective target factor of the study for which this description is being undertaken.
Economic and mathematical problems in agriculture are solved using mathematical methods. Among them, the most developed are methods of linear programming (LP). Such methods are used to solve economic and mathematical problems in which quantitative relationships are expressed linearly, i.e. all conditions are expressed as a system of linear equations and inequalities, and the optimality criterion is expressed as a linear function tending to a minimum or maximum (to an extremum).
A linear programming problem consists of an objective function, a system of constraints, and a non-negativity condition for variables.
Let a function be given n variables It is necessary to find the largest or smallest value of this function, provided that the argument 
The optimization problem posed in this way is called a mathematical programming problem. Lots of NS is called the set of feasible decisions, and the function is the objective function or the objective function. The feasible solution at which the function takes the largest (or smallest) value is called the optimal solution to the problem.
If the objective function is linear and the set NS is specified using a system of linear equations and inequalities, then the problem is called a linear programming problem (LPP). Thus, the general statement of the linear programming problem is as follows:
find the extremum of the function
with restrictions
under non-negativity conditions
Let us introduce the notation:
Stocks i-Th type of resource;
expenses i-Th type of resource for production j-Th type of product;
unit profit j-Th type of product.
In a compact form, the linear programming problem has the form:
The compact notation shows that the general linear programming problem model includes five main elements:
Variables, the value of which is found in the process of solving the problem;
Technical and economic coefficients for variables in constraints;
The volume of the right-hand side of the inequalities, which are called the constants of the problem;
Coefficients of variables in the objective function, which are called variable estimates;
Variable index;
Restriction index.
Target function(goal function) is a mathematical expression for which you want to find the extreme, that is, the maximum or minimum value.
Variables x j denote such types and methods of activity, the size of which is unknown and must be determined in the course of solving the problem. Usually, in problems on agriculture, the variables mean the required sizes of branches of the economy, types of feed in the diet, brands of tractors and agricultural machines, etc. According to specific conditions, the same crop or type of livestock can be expressed by several variables. For example, grain and feed grain; corn for grain, silage, green fodder; perennial grasses for hay, haylage, green forage, grass meal and seeds, etc.
Variables can be arbitrarily changed under the conditions of the problem under consideration. Variable , whose coefficients form a unit column are called basic. Basic variables form unit basis systems. Variables that are not included in the unit basis are called free.
The total number of variables included in a task is determined by the nature of the task, specific production conditions, the ability to collect information, etc.
Variables can be expressed in a wide variety of units: ha, q, kg, pcs., Heads, etc. By their nature, the variables are subdivided into main, additional and auxiliary ones. The main variables include the sought-for activities: industries, types of feed, car brands. Additional variables are called variables that form in the process of transforming inequalities into equations. They can mean an underutilized part of resources, an excess over right side inequality (if it is an inequality of the type "no more"). Auxiliary variables are included in the task in order to determine the estimated values of the acquired production resources, the estimated values of indicators of the economic efficiency of production.
Additional and auxiliary variables always have unit coefficients (+1 or –1).
Technical and economic coefficients (a ij) with variables in the system of constraints, the rates of production resources or the rate of output per unit of measurement of the variable are expressed.
In both cases, it is necessary that the technical and economic coefficients exactly correspond to the planning period for which the problem is being solved. For example, if the problem is solved for the economic and mathematical analysis of production for the past period, then the coefficients will be calculated according to the reported data. If it is decided for the future, then the coefficients should be calculated for this perspective.
The rates of resource consumption are most often determined by reference books, they must be adjusted to the corresponding specific conditions. Yield ratios are calculated based on planned crop yields and animal productivity.
In cases where it is necessary to provide for predetermined relationships between variables, technical and economic coefficients represent proportionality coefficients. For example, the share of crops in a crop rotation or the share of any feed in the total feed group, etc.
Right side of restrictions (b i) are called constants, i.e. constant values. These include the volume of production resources - land, labor, machinery, fertilizers, capital investments, etc. Production resources should be determined taking into account their actual state and it is imperative to take into account the planning period. In addition, those production resources, the use of which is uneven throughout the year, are calculated not only for the year as a whole, but also for individual intense periods or months (labor resources).
Production resources are determined in different units: land - in hectares, labor resources - in man-days or in man-hours, equipment - in the number of machine shifts, shift or daily output, etc.
Thus, determining the availability of productive resources is not easy. It is necessary to carefully analyze the production activity of the economy, the use of labor, land, technical and other resources, and only after that include their volumes in the restrictions.
The right side of the restrictions reflects not only the amount of resources, but also the volume of production at the upper or lower level. The lower level is shown in cases where the volume of production is known in advance, less than which the farm should not produce, and the upper level does not allow production of products above a certain volume. These restrictions are not always required. However, almost no problem involving the definition of a combination of industries does not do without corresponding restrictions on products, otherwise a one-sided solution will turn out. This is due to the fact that the efficiency of the industries is not the same.
In all other restrictions, zeros are put on the right side, since they formulate conditions for the production and use of products or reflect restrictions on proportional communication.
Limitation Is a mathematical expression that binds variables in the form of equalities and inequalities. All restrictions form system of restrictions tasks. The system of constraints in mathematical form characterizes the conditions of the problem. The completeness of the reflection of these conditions depends on the composition of the restrictions. Therefore, when determining the number of restrictions, two circumstances must be taken into account:
v reflect in the task only those conditions that really limit the possibilities of production;
v too many constraints increase the size of the problem and make it difficult to solve
There are three types of constraints: equality (=), type inequality less than or equal to (≤), type inequality greater than or equal to (≥). For example,
where i = 1, 2, … , m... Variable coefficients are denoted a ij where index i- restriction number, index j- variable number, free members (right side of constraints) are denoted b i, index i- restriction number.
Constraints of the first type are called upper constraints, since the left side of the inequality cannot be higher than a certain value (constant). Constraints of the third type are called constraints from below, since the left side of the inequality cannot be lower than a certain value (constant).
In terms of meaning, all restrictions can be subdivided into main, additional and auxiliary ones.
The main limitations are - these are the ones that overlap with all or most of the task variables. As a rule, with their help, the basic conditions of the problem are reflected - in terms of land, labor, feed, nutrients, technology, etc.
Additional restrictions are superimposed on a part of variables or on one variable. These restrictions are introduced in cases where it is necessary to limit the size of individual variables from above or below, for example, taking into account crop rotation requirements or taking into account the physiological limits of saturation of the diet with individual feeds or their groups. Thus, additional constraints reflect various additional conditions that arise during the simulation. But each additional restriction narrows the scope of freedom of choice. Therefore, they should be introduced into the task carefully, within reasonable limits and when necessary.
Auxiliary restrictions, as a rule, they have no independent meaning and are introduced into the problem to formalize individual conditions. These include constraints that establish a proportional relationship between individual variables or their groups.
Estimation of variables in the objective function (with j) are coefficients that express the amount of total income or costs per unit of measure of the variable. The estimate of a variable, as a rule, expresses the accepted criterion of optimality. It can be presented both in kind and in cash, i.e. unit costs (cost of production).
The condition for the nonnegativity of variables is written in the form
x j≥ 0, j = 1, 2, ..., n.
In real life of production, based on the conditions of the task, a list of variables and restrictions is compiled from this record of the structural economic and mathematical model (EMM), initial information is prepared, a detailed EMM problem is built, which is then written in the form of a matrix (table), entered into a computer and according to the corresponding program, the calculation and analysis of the results is performed. i = 1, ..., m, (1.5)
j = 1, …, n. (1.6)
Vector x = (x 1 , x 2 , …, x n), components x j which satisfy constraints (1.2) and (1.3) [or (1.5) and (1.6) in the minimum problem] is called acceptable decision or acceptable plan LP tasks. The collection of all valid plans is called many valid plans.
Canonical the form of the linear programming problem is characterized by the fact that it contains an objective function, all restrictions equality, all variables are non-negative.
Any linear programming problem can be reduced to a linear programming problem in canonical form. To do this, in the general case, you need to be able to reduce the problem of maximization to the problem of minimization; go from inequality constraints to equality constraints and replace variables that do not obey the non-negativity condition.
The rule for reducing a linear programming problem to the canonical form is as follows:
1) if in the original problem it is required to determine the maximum of a linear function, then the sign should be changed and the minimum of this function should be sought;
2) if in the restrictions the right side is negative, then this restriction should be multiplied by - 1;
3) if among the constraints there are inequalities, then by introducing additional variables of non-negative variables, they are transformed into equalities. For example, additional variables S j in constraints of the type less than or equal to (£) are entered with a plus sign:
Additional variables S j in type constraints greater than or equal to (≥) are entered with a minus sign:
To eliminate the negativity of additional variables - S j introduce artificial variables with plus sign + M j with very large values.
How do I enable line-in?
Recovering deleted files from a USB flash drive
Installing windows 8 64 bit