Graphical method for solving linear programming. Graphical method for solving linear programming problems

Let's consider several methods for solving linear programming problems.

The graphical method is quite simple and intuitive for solving linear programming problems with two variables. It is based on the geometric representation of feasible solutions and TFs of the problem.

Each of the inequalities of the linear programming problem defines a certain half-plane on the coordinate plane, and the system of inequalities as a whole defines the intersection of the corresponding planes. The set of intersection points of these half-planes is called a region acceptable solutions (ODR). ODR is always a convex figure, i.e. having the following property: if two points A and B belong to this figure, then the entire segment AB belongs to it. ODR can be graphically represented by a convex polygon, an unlimited convex polygonal area, a segment, a ray, or one point. If the system of constraints in problem (1) is inconsistent, the ODS is an empty set.

All of the above also applies to the case when the system of restrictions (1) includes equalities, since any equality

can be represented as a system of two inequalities

The digital filter at a fixed value defines a straight line on the plane. By changing the values ​​of L, we get a family of parallel lines called lines level.

This is due to the fact that changing the value of L will entail a change only in the length of the segment cut off by the level line on the axis (initial ordinate), and the angular coefficient of the straight line will remain constant. Therefore, to solve it, it will be enough to construct one of the level lines, arbitrarily choosing the value of L.

The vector with coordinates from the CF coefficients at and is perpendicular to each of the level lines. The direction of the vector coincides with the direction increasing the TF, which is an important point for solving problems. Direction the decrease of the CF is opposite to the direction of the vector.

The essence of the graphical method is as follows. In the direction (against the direction) of the vector in the ODR, the optimal point is searched. The optimal point is the point through which the level line passes, corresponding to the largest (smallest) value of the function. The optimal solution is always located on the boundary of the ODD, for example, at the last vertex of the ODD polygon through which the target line will pass, or on its entire side.

When searching for an optimal solution to linear programming problems, the following situations are possible: there is a unique solution to the problem; there is an infinite number of solutions (alternative); TF is not limited; the region of feasible solutions is a single point; the problem has no solutions.

Figure 1 Geometric interpretation of constraints and TFs of the problem

Let's consider a technique for solving LP problems using the graphical method.

• 1) in the constraints of problem (1), replace the inequality signs with exact equality signs and construct the corresponding straight lines;
• 2) find and shade the half-planes allowed by each of the inequality constraints of problem (1). To do this, you need to substitute the coordinates of a point [for example, (0;0)] into a specific inequality and check the truth of the resulting inequality.

If the inequality is true, then we must shade the half-plane containing this point; otherwise (the inequality is false) one must shade the half-plane that does not contain the given point.

Since and must be non-negative, their permissible values ​​will always be above the axis and to the right of the axis, i.e. in the first quadrant.

Equality constraints allow only those points that lie on the corresponding line. Therefore, it is necessary to highlight such straight lines on the graph;

• 3) define the ODR as a part of the plane that simultaneously belongs to all allowed areas and select it. In the absence of SDT, the problem has no solutions;
• 4) if the ODR is not an empty set, then you need to construct the target line, i.e. any of the level lines (where L is an arbitrary number, for example, a multiple and, i.e., convenient for calculations). The construction method is similar to the construction of direct constraints;
• 5) construct a vector that starts at the point (0;0) and ends at the point. If the target line and vector are constructed correctly, then they will be perpendicular;
• 6) when searching for the maximum CF, it is necessary to move the target line to direction of the vector, when searching for the minimum CF - against vector directions. The last top of the ODR in the direction of movement will be the point of maximum or minimum of the CF. If such a point(s) does not exist, then we can conclude that CF on many plans from above (when searching for the maximum) or from below (when searching for the minimum);
• 7) determine the coordinates of the point max (min) of the digital filter and calculate the value of the digital filter. To calculate the coordinates of the optimal point, it is necessary to solve a system of equations of the lines at the intersection of which it is located.

The simplex method is one of the first specialized optimization methods aimed at solving linear programming problems, while simple and directed enumeration methods can be used to solve almost any optimization problem. It was proposed by the American G. Dantzig in 1951. The simplex method consists of moving along a convex polyhedron of constraints from vertex to vertex, in which at each step the value of the objective function is improved until the optimum is reached.

The simplex method is a typical example of iterative calculations used in solving most optimization problems. In the computational scheme of the simplex method, an ordered process is implemented in which, starting from some initial admissible corner point (usually the origin), successive transitions are made from one admissible extreme point to another until a point corresponding to the optimal solution is found ( Figure 2).

Figure 2 Transition from one vertex to another

The simplex method, also known in our literature as the method of sequential improvement of the plan, was first developed by G. Danzig in 1947. This method allows you to move from one feasible basic solution to another, and in such a way that the values ​​of the objective function continuously increase. As a result, the optimal solution is found in a finite number of steps.

The simplex method is a universal method for solving a linear system of equations or inequalities and a linear functional.

Algorithm for solving ZLP using the simplex method.

The simplex method involves sequentially searching through all the vertices of the range of acceptable values ​​in order to find the vertex where the function takes an extreme value. At the first stage, some solution is found, which is improved at each subsequent step. This solution is called basic.

Let's look at the steps of the simplex method.

• 1) in the compiled table, you first need to look at the column with free members. If there are negative elements in it, then it is necessary to move to the second step, if not, then to the fifth;
• 2) at the second step it is necessary to decide which variable to exclude from the basis and which to include in order to recalculate the simplex table. To do this, look through the column with free terms and find a negative element in it. The line with a negative element will be called leading. In it we find the maximum negative element in modulus, the corresponding column is the slave one. If there are negative values ​​among the free terms, but not in the corresponding row, then such a table will not have solutions. The variable in the leading row located in the column of free terms is excluded from the basis, and the variable corresponding to the leading column is included in the basis. Table 1 shows an example of a simplex table.

Table 1

Example of a simplex table

Basic Variables	Free members under restrictions	Non-basic variables

• 3) in the third step, we recalculate the entire simplex table using special formulas;
• 4) if after recalculation there are negative elements left in the column of free terms, then go to the first step, if there are no such elements, then to the fifth;
• 5) if you have reached the fifth step, then you have found a solution that is acceptable. However, this does not mean that it is optimal. It will be optimal only if all elements in the F-string are positive. If this is not the case, then it is necessary to improve the solution, for which we find the leading row and column for the next recalculation using the following algorithm. Initially, we find the minimum negative number in the string F, excluding the function value. The column with this number will be the leading one. In order to find the leading row, we find the ratio of the corresponding free term and the element from the leading column, provided that they are positive. The minimum ratio will allow you to determine the leading line. We recalculate the table again using the formulas, i.e. go to step 3;
• 6) if it is impossible to find the leading row, since there are no positive elements in the leading column, then the function in the region of feasible solutions to the problem is not bounded above and F max ->?. If all elements in row F and the column of free terms are positive, then the optimal solution has been found.

Goal of the work

1. Study the concept of a mathematical model.

2. Consider examples of linear programming problems.

3. Learn the graphical method for solving linear programming problems.

4. Learn to reduce linear programming problems to standard form.

Theoretical introduction

The concept of a mathematical model. Mathematical model in linear programming (LP) problems

Linear programming is a branch of higher mathematics devoted to solving problems related to finding extrema of functions of several variables in the presence of restrictions on the variables. Linear programming methods are used to solve problems about resource allocation, production planning, pricing, transport problems, etc.

Any description of a problem in the form of formulas or algorithms is called mathematical model this task.

Construction of a mathematical model of the problem includes the following steps:

1) selection of task variables;

2) drawing up a system of restrictions;

3) choice of objective function.

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

Restriction system involves a system of equations and inequalities that are satisfied by objective variables and that result from limited resources or other economic or physical conditions.

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

The general problem of mathematical programming is formulated as follows:

find the extremum of the objective function and the corresponding variables, provided that these variables satisfy the system of restrictions and non-negativity conditions.

Function (1.1) is called the objective function, and constraints (1.2) are called the system of constraints of the problem.

If, according to the conditions of the problem, it is required to find such values ​​of variables for which the objective function (1.1) will have a maximum value, then they say that the objective function is subject to maximization(or aimed at maximum). If the objective function is required to take a minimum value, then it is said to be subject to minimization(aimed at minimum).

Pay attention to the result. The objective function is a linear function of the variables x 1, x 2, ... x n; the restrictions themselves on the values ​​of the variables x 1, x 2, ... x n have the form of linear inequalities. All this determined the name of this class of problems - linear programming problems.

Most problems (but not always) require that variables take non-negative values ​​(non-negativity constraint); Some problems require variables to take integer values ​​(integer constraints).

A linear mathematical model can be constructed for many problems solved in practice.

Any values ​​of variables that satisfy the constraints of problem (1.2) are called valid solutions(regardless of what value the objective function takes). Most problems have an infinite number of feasible solutions. The entire set of feasible solutions represents the domain of feasible solutions (ADD).

Acceptable values ​​of variables at which the objective function takes a maximum or minimum value (depending on the formulation of the problem), i.e. reaches an extremum, represent optimal solution.

Method of doing the work

Examples of LP problems

Example 1.1. The chemical industry enterprise produces hydrochloric and sulfuric acid. The production of one ton of hydrochloric acid is 25 monetary units (den. units), the production of one ton of sulfuric acid is 40 den. units To fulfill the state order, it is necessary to produce at least 200 tons of hydrochloric acid and at least 100 tons of sulfuric acid. In addition, it must be taken into account that the release of acids is associated with the generation of hazardous waste. When producing one ton of hydrochloric acid, 0.5 tons of hazardous waste is generated; when producing one ton of sulfuric acid, 1.2 tons of hazardous waste is generated. The total amount of hazardous waste should not exceed 600 tons, since exceeding this limit will result in the company paying a large fine.

It is necessary to determine how much hydrochloric and sulfuric acid the enterprise should produce in order to obtain maximum profit.

Let's create a mathematical model of the problem. To do this, we introduce variables. Let us denote by x 1 the amount of hydrochloric acid produced (in tons), by x 2 – the amount of sulfuric acid.

Let's draw up restrictions related to the need to fulfill government orders. The enterprise needs to produce at least 200 tons of hydrochloric acid. This limitation can be written as follows: x 1,200. Similarly, let’s create a constraint establishing that the enterprise must produce at least 100 tons of sulfuric acid: x 2,100.

We will draw up restrictions on hazardous waste. When one ton of hydrochloric acid is released, 0.5 tons of hazardous waste is generated; This means that the total amount of hazardous waste when releasing hydrochloric acid will be 0.5x 1 ton. When releasing sulfuric acid, 1.2 x 2 tons of hazardous waste is generated. Thus, the total amount of hazardous waste will be 0.5x 1 +1.2x 2 tons. This value should not exceed 600 tons. Therefore, the following limitation can be written: 0.5x 1 +1.2x 2 600.

In addition, the variables, by their physical meaning, cannot take negative values, since they indicate the amount of acids produced. Therefore, it is necessary to take into account the non-negativity restrictions: x 1 0; x 2 0.

In this problem, you need to determine the production of acids at which the profit will be maximum. The profit from the production of one ton of hydrochloric acid is 25 den. units; This means that the profit from the production of hydrochloric acid will be 25x 1 den. units The profit from the production of sulfuric acid will be 40x 2 den. units Thus, the total profit from the production of acids will be 25x 1 + 40x 2 den. units It is required to find such values ​​of the variables x 1 and x 2 at which this value will be maximum. Thus, the objective function for this problem will have the following form:

E=25x 1 +40x 2 → max.

We present a complete mathematical model of the problem under consideration:

0.5x 1 +1.2x 2 600

E=25x 1 +40x 2 → max.

This problem has two greater-than-or-equal constraints and one less-than-or-equal constraint. The objective function is subject to maximization.

Example 1.2. Suppose that in the conditions of task 1.1, due to stricter requirements for environmental safety, it is necessary to minimize the amount of hazardous waste. At the same time, it must be taken into account that in order for the production of acids to be economically feasible, it is necessary to make a profit of at least 20 thousand den. units

The mathematical model of such a problem has the following form:

25x 1 +40x 2 20000

E= 0.5x 1 +1.2x 2 → min.

The third constraint in this model states that the profit from the production of acids must be at least 20 thousand monetary units. The objective function represents the amount of hazardous waste; this value must be minimized.

Graphical method for solving LP problems

The graphical method is used to solve problems in which there are only two variables. For such problems, it is possible to graphically depict the region of feasible solutions (ADS).

Note. The graphical method can also be used to solve problems with any number of variables, if it is possible to express all the variables of the problem through any two variables.

As noted above, the ODR is a set of values ​​of variables that satisfy constraints (1.2). Thus, for problems with two variables, the ODP is a set of points (x 1 ; x 2), i.e. some area on a plane (usually a polygon). For problems with three variables, the ODR is a polyhedron in space; for problems with a large number of variables, it is a certain region of multidimensional space. It can be proven that the extremum (minimum or maximum) of the objective function is always achieved at the values ​​of the variables corresponding to one of the corner points of the ODP. In other words, the optimal solution is always located at the corner point of the ODR. Therefore, the linear programming problem with two variables can be solved as follows: construct the ODD on a plane in the coordinate system (x 1 ; x 2), determine all the corner points of the ODD, calculate the values ​​of the objective function at these points and select the optimal solution.

Let us solve the problem from graphically example 1.1.

The solution is shown in Fig. 1.1.

Rice. 1.1Solving Example 1.1 graphically

The limit x 1,200 is given by the vertical line x 1 =200. All points (x 1 ; x 2) located to the right of this line satisfy the x 1,200 constraint, those located to the left do not. The limit x 2 100 is given by the horizontal line x 2 =100. All points located above this line satisfy the x 2 100 constraint, those located below do not.

To construct a line defining the constraint 0.5x 1 +1.2x 2 600, it is convenient to write it as an equality: 0.5x 1 +1.2x 2 =600. Let's express one of the variables through the other: x 2 = -0.41x 1 +500. This is the equation of a straight line. Let's construct this straight line. It splits the coordinate plane into two half-planes. One of these half-planes contains points that satisfy the constraint, and the other contains points that do not. To find a half-plane that satisfies the constraint 0.5x 1 +1.2x 2 600, we substitute the coordinates of any point into it, for example, (0; 0). For this point the constraint is satisfied. This means that it is in a half-plane that satisfies the constraint.

The intersection of all half-planes satisfying the constraints of the problem represents an ODP. In Fig. 1.1 it is highlighted in gray.

The optimal solution is located at one of the corner points of the ODR (in Fig. 1.1 they are designated as A, B, C). These points can be found from the plotted graph or by solving the corresponding systems of two equations. Let's find the values ​​of the objective function at these points:

E(A) = 25∙200 + 40∙100=9000;

E(B) = 25∙200 + 40∙416.67 = 21666.8;

E(C) = 25∙960 + 40∙100 = 28000.

Thus, the optimal solution is at point C= (960; 100). This means that the enterprise should produce 960 tons of hydrochloric acid and 100 tons of sulfuric acid. The profit will be 28,000 monetary units. You can also find the amount of hazardous waste that will be generated during the production of acids: 0.5 960 + 1.2∙100 = 600 tons.

Let's solve the problem from Example 1.2 graphically. The solution is shown in Fig. 1.2.

Rice. 1.2Solving problem 1.2 graphically

In this case, the ODR has only two corner points (A and B). Let us find the value of the objective function for them:

E(A)= 0.5 ∙ 200+1.2 ∙ 375 =550;

E (B) = 0.5∙640+1.2∙100 =440.

Thus, the optimal solution is at point B(640; 100). This means that the enterprise should produce 640 tons of hydrochloric acid and 100 tons of sulfuric acid. This generates 440 tons of hazardous waste. You can also find the profit from the production of acids: 25 ∙ 640 + 40 ∙ 100 = 20,000 monetary units.

Task. Solve the linear programming problem graphically by determining the extreme value of the objective function:

under restrictions

Let us construct a region of feasible solutions, i.e. Let's solve the system of inequalities graphically. To do this, we construct each straight line and define the half-planes defined by the inequalities (the half-planes are indicated by a prime).

Let's build the equation 3x 1 +x 2 = 9 at two points.
To find the first point, we equate x 1 = 0. We find x 2 = 9. To find the second point, we equate x 2 = 0. We find x 1 = 3. We connect the point (0;9) with (3;0) with a straight line. Let us define the half-plane defined by the inequality. Having chosen the point (0; 0), we define the inequality sign in the half-plane: 3. 0 + 1 . 0 - 9 ≤ 0, i.e. 3x 1 +x 2 - 9≥ 0 in the half-plane above the straight line.
Let's construct the equation x 1 +2x 2 = 8 at two points.
To find the first point, we equate x 1 = 0. We find x 2 = 4. To find the second point, we equate x 2 = 0. We find x 1 = 8. We connect the point (0;4) with (8;0) with a straight line. Let us define the half-plane defined by the inequality. Having chosen the point (0; 0), we define the inequality sign in the half-plane: 1. 0 + 2 . 0 - 8 ≤ 0, i.e. x 1 +2x 2 - 8≥ 0 in the half-plane above the straight line.
Let's construct the equation x 1 + x 2 = 8 at two points.
To find the first point, we equate x 1 = 0. We find x 2 = 8. To find the second point, we equate x 2 = 0. We find x 1 = 8. We connect the point (0;8) with (8;0) with a straight line. Let us define the half-plane defined by the inequality. Having chosen the point (0; 0), we define the inequality sign in the half-plane: 1. 0 + 1 . 0 - 8 ≤ 0, i.e. x 1 +x 2 - 8≤ 0 in the half-plane below the straight line.

The intersection of half-planes will be a region whose point coordinates satisfy the inequalities of the system of constraints of the problem.
Let us denote the boundaries of the area of ​​the solution polygon.

You can check the correctness of the construction of function graphs using a calculator

Consider the objective function of the problem F = 4x 1 +6x 2 → min.
Let's construct a straight line corresponding to the value of the function F = 0: F = 4x 1 +6x 2 = 0. The gradient vector, composed of the coefficients of the objective function, indicates the direction of minimization of F(X). The beginning of the vector is point (0; 0), the end is point (4; 6). We will move this straight line in a parallel manner. Since we are interested in the minimal solution, we therefore move the straight line until it first touches the designated area. On the graph, this straight line is indicated by a dotted line.

Straight F(x) = 4x 1 +6x 2 intersects the region at point B. Since point B is obtained as a result of the intersection of lines (1) And (2) , then its coordinates satisfy the equations of these lines:
3x 1 +x 2 =9
x 1 +2x 2 =8

Having solved the system of equations, we get: x 1 = 2, x 2 = 3
How can we find the minimum value of the objective function:
F(X) = 4*2 + 6*3 = 26

Let us first consider the simplest case, when exactly two variables are included in the LLP:

Each of the inequalities (a)-(b) of the system of constraints of problem (3.8) geometrically defines a half-plane, respectively, with boundary straight lines, X 1 =0 and X 2 =0. Each of the boundary lines divides the plane x 1 Ox 2 into two half-planes. All solutions to the original inequality lie in one of the formed half-planes (all points of the half-plane) and, therefore, substituting the coordinates of any of its points into the corresponding inequality turns it into a true identity. Taking this into account, the half-plane in which the solutions to the inequality lie is determined, i.e. by selecting any point from any half-plane and substituting its coordinates into the corresponding inequality. If an inequality holds for a given point, then it holds for any other point from the same half-plane. Otherwise, the solutions to the inequality lie in another half-plane.

If the system of inequalities (a)-(b) is consistent, then the domain of its solutions is the set of points belonging to all the indicated half-planes. Since the set of intersection points of these half-planes is convex, the domain of admissible solutions to problem (3.8) is a convex set, which is called a solution polygon (the previously introduced term “solution polyhedron” is usually used if n 3). The sides of this polygon lie on straight lines, the equations of which are obtained from the original system of constraints by replacing the inequality signs with exact equality signs.

Thus, the initial ZLP consists of finding a point in the decision polygon at which the objective function F takes on the maximum (minimum) value.

This point exists when the solution polygon is not empty and the objective function on it is bounded from above. Under the specified conditions, at one of the vertices of the solution polygon, the objective function takes on the maximum value. To determine this vertex, construct a level line L: c 1 x 1 +c 2 x 2 =h (where h is some constant), perpendicular to the gradient vector and passing through the solution polygon, and move it parallel along the gradient vector until until it passes through its last common point of intersection with the solution polygon (when constructing a gradient vector, a point (c 1 ; c 2) is laid out in the x 1 Ox 2 plane and a directed segment is drawn to it from the origin of coordinates). The coordinates of the specified point determine the optimal plan for this task.

Summarizing all of the above, we present an algorithm for the graphical method of solving the ZLP.

Algorithm for the graphical method of solving the ZLP

1. Construct a polygon of solutions specified by the system of restrictions of the original ZLP.

2. If the constructed polygon of solutions is an empty set, then the original ZLP has no solutions. Otherwise, construct a gradient vector and draw an arbitrary level line L, moving which, when solving a maximum problem, in the direction of the vector (or in the opposite direction for a minimum problem) to determine the extreme point of the solution polygon, where the maximum (minimum) of the objective function of the problem is achieved .

3. Calculate the coordinates of the found optimal point by solving the system of equations of two boundary lines intersecting in it.

4. By substituting the found optimal solution into the objective function of the problem, calculate its optimal value, i.e.: .

When graphically constructing the set of admissible solutions of the PLP (solution polygon), the following situations are possible.

The simplest and most visual method for solving a linear programming problem (LPP) is the graphical method. It is based on the geometric interpretation of the linear programming problem and is used to solve the ZLP with two unknowns:

We will consider the solution of this problem on a plane. Each inequality of the system of functional constraints geometrically defines a half-plane with a boundary line a p x, + + a j2 x 2 = b n i = 1, T. Non-negativity conditions define half-planes with boundary lines X (= 0, x 2= 0 accordingly. If the system is consistent, then the half-planes, intersecting, form a common part, which is a convex set and represents a collection of points; the coordinates of each of these points are a solution to this system. The set of these points is called solution polygon. It can be a point, a segment, a ray, a bounded or unbounded polygon.

Geometrically, the ZLP is finding a corner point of the solution polygon whose coordinates provide the maximum (minimum) value of the linear objective function, Moreover, all points of the solution polygon are admissible solutions.

A linear equation describes a set of points lying on the same line. A linear inequality describes some region on the plane.

Let us determine which part of the plane describes the inequality 2x ( + 3x 2 12.

First, let's construct a straight line 2x, + Zx 2 = 12. It passes through the points (6; 0) and (0; 4). Secondly, we determine which half-plane satisfies the inequality. To do this, select any point on the graph that does not belong to the line and substitute its coordinates into the inequality. If the inequality holds, then this point is an admissible solution and the half-plane containing the point satisfies the inequality. It is convenient to use the origin of coordinates to substitute into the inequality. Let's substitute x ( = x 2 = 0 to inequality 2x, + 3x 2 12. We get 2 0 + 3 0

Similarly, you can graphically depict all the constraints of a linear programming problem.

The solution to each inequality of the ZLP constraint system is a half-plane containing the boundary line and located on one side of it. The intersection of half-planes, each of which is determined by the corresponding inequality of the system, is called area of ​​feasible solutions(ODR) or domain of definition.

It must be remembered that the region of feasible solutions satisfies the conditions of non-negativity (Xj > 0, j = 1, P). The coordinates of any point belonging to the domain of definition are a valid solution to the problem.

To find the extreme value of the objective function when solving the ZLP graphically, use gradient vector, whose coordinates are partial derivatives of the objective function:

This vector shows the direction of the fastest change in the objective function. Straight c [ x l + c 2 x 2 = f(x 0), perpendicular to the gradient vector is level line target function (Fig. 2.2.2). At any point on the level line, the objective function takes the same value. Let us equate the target function to a constant value A. Changing the meaning A, we obtain a family of parallel lines, each of which is a level line of the objective function.

Rice. 2.2.2.

An important property of the level line of a linear function is that when the line is parallelly shifted to one side, the level only increases and when shifted to the other side - only decreases.

The graphical method for solving the PLP consists of four stages:

• 1. The region of admissible solutions (ADA) of the PLP is constructed.
• 2. The gradient vector of the objective function (TF) is constructed with the beginning at the point x 0(0; 0): V = (s, from 2).
• 3. Level line CjXj + c 2 x 2 = a (a - constant value) - a straight line perpendicular to the gradient vector V, - moves in the direction of the gradient vector in the case of maximizing the objective function f(x v x 2) until it leaves the ODR. When minimizing /(*, x 2) the level line moves in the direction opposite to the gradient vector. The extreme point (or points) of the ODR during this movement is the maximum (minimum) point f(x p jc 2).

If the straight line corresponding to the level line does not leave the ODR during its movement, then the minimum (maximum) of the function f(x p x 2) does not exist.

If the level line of the objective function is parallel to the functional constraint of the problem at which the optimal value of the CF is achieved, then the optimal value of the CF will be achieved at any point of this constraint lying between two optimal corner points, and, accordingly, any of these points is the optimal solution of the ZLP.

4. The coordinates of the maximum (minimum) point are determined. To do this, it is enough to solve a system of equations of lines that give a maximum (minimum) point at the intersection. Meaning f(x ( , x 2), found at the resulting point is the maximum (minimum) value of the objective function.

Possible situations of a graphical solution of the ZLP are presented in Table. 2.2.1.

Table 2.2.1

Type of ODR	Type of optimal solution
Limited	Only decision
	Endless solutions
Unlimited	CF is not limited from below
	CF is not limited from above
	Only decision
	Endless solutions
	Only decision
	Endless solutions

Example 2.2.1. Planning the production of a sewing enterprise (problem about suits).

It is planned to release two types of suits - men's and women's. A woman's suit requires 1 m of wool, 2 m of lavsan and 1 man-day of labor; for men - 3.5 m of wool, 0.5 m of lavsan and 1 man-day of labor. In total there are 350 m of wool, 240 m of lavsan and 150 man-days of labor.

It is required to determine how many suits of each type need to be made to ensure maximum profit if the profit from the sale of a women's suit is 10 den. units, and from men - 20 den. units It should be borne in mind that it is necessary to sew at least 60 men's suits.

Economic and mathematical model of the problem

Variables: X, - number of women's suits; x 2 - number of men's suits.

Objective function:

Restrictions:

The first constraint (on wool) has the form x ( + 3.5x 2 x ( + 3.5x 2 = 350 passes through the points (350; 0) and (0; 100). The second constraint (according to lavsan) has the form 2x (+ 0.5x 2 2x x + 0.5x 2 = 240 passes through the points (120; 0) and (0; 480). The third restriction (on labor) has the form x y + x 2 150. Direct x ( + x 2 = 150 passes through the points (150; 0) and (0; 150). The fourth constraint (on the number of men's suits) has the form x 2> 60. The solution to this inequality is the half-plane lying above the straight line x 2 = 60.

As a result of the intersection of the constructed four half-planes, we obtain a polygon, which is the region of feasible solutions to our problem. Any point on this polygon satisfies all four functional inequalities, and for any point outside this polygon at least one inequality will be violated.

In Fig. 2.2.3 the region of feasible solutions (ADA) is shaded. To determine the direction of movement towards the optimum, we construct a gradient vector V, the coordinates of which are partial derivatives of the objective function:

To construct such a vector, you need to connect the point (10; 20) to the origin. For convenience, you can construct a vector proportional to the vector V. Thus, in Fig. 2.2.3 shows the vector (30; 60).

Then we will build a level line 10xj + 20x 2 = A. Let us equate the target function to a constant value A. Changing the meaning A, we obtain a family of parallel lines, each of which is a level line of the objective function:

Next, we will move the level line until it exits the ODR. In our case (when maximizing the objective function), we will move the level line in the direction of the gradient. At the extreme corner point the maximum of the objective function is achieved. To find the coordinates of this point, we solve a system of two straight line equations that give the maximum point at the intersection:

We get At these values

Answer. To get maximum profit (2300), you need to sew 70 women's (xj 1 = 70) and 80 men's (x 2 = 80) suits.

Rice. 2.2.3. Point (70; 80) is the optimal solution to the problem Example 2.2.2. Find the maximum and minimum f(X):

under restrictions

Solution. When solving this example to the maximum, a situation arises when the level line 3x, + 3 x 2 = a parallel to the first constraint: x x + x 2 8. The objective function reaches its maximum value at two points: A(3; 5) and IN(6; 2) - and takes on the segment AB the same value, equal to 24:

When solving this example for the minimum of the objective function, the level line 3xj + 3 x 2 - a should be moved in the direction opposite to the direction of the gradient vector. The objective function reaches its minimum value at the point D (0,5; 0):

A graphical solution of the example is shown in Fig. 2.2.4.

Rice. 2.2.4.

Answer: max /(2Q = 24; min /( X)= 1.5. Example 2.2.3. Find the maximum /( X):

under restrictions

Solution. The problem has no solution, since the CF is not limited from above on the ODR (Fig. 2.2.5).