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

Example 6.1.

Solution:

The linear programming problem is given in standard form and has two design parameters, therefore

It is possible to solve it using the geometric method.

Stage 1: ( ODR ).

Consider the first constraint, replace the inequality sign with an equal sign and express the variable x2 through x1:

Similarly, we determine the points for the remaining constraints of the system and construct straight lines from them corresponding to each inequality (Fig. 1). We number the lines according to the previously adopted scheme.

Stage 2: .

Let us define half-planes - solutions to each of the inequalities.

Let us consider the first inequality of the problem constraint system. Let's take some point (control point) that does not belong to the line corresponding to this inequality, for example, point (0; 0). Let's substitute it into the inequality under consideration:

When substituting coordinates control point inequality remains fair. Consequently, the set of points belonging to this line (since the inequality is not strict), as well as those located below it, will be solutions to the inequality under consideration (let us mark on the graph (Fig. 1) the found half-plane with two arrows pointing down next to the line I ) .

We similarly determine the solutions to other inequalities and mark them on the graph accordingly. As a result, the graph will look like this:

Stage 3: .

The found half-planes (solutions to each of the inequalities of the system of constraints) form a polygon when intersecting ABCDEO, which is the ODD of the problem under consideration.

Rice. 1. Area admissible solutions tasks

Stage 4:
The gradient vector shows the direction of maximization objective function. Let's determine its coordinates: the coordinates of its initial point (application point) – (0; 0), the coordinates of the second point:

Let's plot this vector on the graph (Fig. 2).

Stage 5: .

Let's consider the objective function of this problem:

Let's give it some value, for example, . Let's express the variable x2 through x1:

To construct a straight line using this equation, we will specify two arbitrary points, for example:

Let's construct a straight line corresponding to the objective function (Fig. 2).

Rice. 2. Construction of the target function F(X) and gradient vector C

Stage 6: determining the maximum of the target function.

Moving a straight line F(X) parallel to itself in the direction of the gradient vector, we determine the extreme point (points) of the ODR. According to the graph (Fig. 3), such a point is point C - the point of intersection of lines I And II .

Rice. 3. Determination of the maximum point of the objective function F(X)

Let's determine the coordinates of point C, for this purpose, solve the following system of linear equations:

Let's substitute the found coordinates into the objective function and find its optimal (maximum) value:

Answer: under given restrictions, the maximum value of the objective function F(X)=24, which is achieved at point C, the coordinates of which x1=6, x2=4.

Example 6.2. Solve the linear programming problem using the geometric method:

Solution:

Stages 1-3 are similar to the corresponding stages of the previous task.
Stage 4: construction of a gradient vector.
The construction of the gradient vector is carried out in the same way as in the previous problem. Let's plot this vector on the graph (Fig. 4). We also note on this chart the arrow is the direction opposite to the gradient vector – the direction of minimization of the objective function F (X).

Stage 5: construction of a direct target function.

Construction of a direct objective function F(X) is carried out in the same way as in the previous problem (the construction result is shown in Fig. 4).

Rice. 4. Construction of the objective function F(x) and gradient vector C

Stage 6: determining the optimum of the target function.

Moving a straight line F(x) parallel to itself in the direction opposite to the gradient vector, we determine the extreme point (points) of the ODR. According to the graph (Fig. 5), such a point is point O with coordinates (0; 0).

Rice. 5. Determination of the minimum point of the objective function

Substituting the coordinates of the minimum point into the target function, we determine its optimal (minimum) value, which is equal to 0.
Answer: under given restrictions minimum value objective function F(X)=0, which is reached at point O (0; 0).

Example 6.3. Solve the following linear programming problem using the geometric method:

Solution:

The linear programming problem under consideration is given in canonical form, we select as basic variables x 1 And x2 .

Let's create an extended matrix and select it using the method Jordan-Gauss basic variables x1 And x 2 .

Multiply (element by element) the first line by –3 and add it to the second:
.

Multiply the second line by:

Let's add the second line to the first line:

As a result, the system of restrictions will take the following form:

Let's express the basic variables in terms of free ones:

Let's also express the target function in terms of free variables; to do this, we substitute the obtained values of the basic variables into the target function:

Let us write the resulting linear programming problem:

Since the variables x1 And x2 non-negative, then the resulting system of restrictions can be written in the following form:

Then original problem can be written in the form of the following equivalent standard task linear programming:

This problem has two design parameters, therefore, it can be solved using the geometric method.

Stage 1: construction of straight lines limiting the area of feasible solutions ( ODR ).

Let us consider the system of constraints of the linear programming problem (for convenience, we number the inequalities):

Let's construct straight lines corresponding to each inequality (Fig. 6). We number the straight lines according to the previously adopted scheme.

Stage 2: determination of the solution to each of the inequalities of the system of constraints.

Using control points, we determine half-planes - solutions to each of the inequalities, and mark them on the graph (Fig. 6) using arrows.

Stage 3: determination of the ODD of a linear programming problem.

The found half-planes (i.e., solutions to each of the inequalities of the constraint system) do not have a common intersection (so the solutions to inequality I generally contradict the remaining inequalities of the constraint system), therefore, the constraint system is not consistent and the linear programming problem therefore has no solution.

Rice. 6. Fragment of a MathCAD document:

constructing a region of feasible solutions to a problem

Answer: The linear programming problem under consideration has no solution due to the inconsistency of the system of constraints.

If, after substituting the coordinates of the control point into the inequality, its meaning is violated, then the solution to this inequality is a half-plane that does not contain this point (i.e., located on the other side of the line).

The direction opposite to the gradient vector corresponds to the direction of minimizing the objective function.

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. 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 given 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 a level line linear function is that when the line is parallelly shifted to one side, the level is only increases and when shifted to the other side - only decreases.

Graphical method the decision of the PPP 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 target function level line is parallel to the functional constraint of the task at which optimal value CF, then the optimal CF value 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 graphic solution PAPs are presented in table. 2.2.1.

Table 2.2.1

Type of ODR	Type of optimal solution
Limited	Only decision
Limited	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 necessary to determine how many suits of each type need to be sewn 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 limitation (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 vector-gradient V, whose coordinates 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.

The graphical method for solving the ZLP is based on the statements given in paragraph 2.1. According to Theorem 2, optimal solution is at the top of the region of feasible solutions and therefore solve the ZLP - find the top of the region of feasible solutions, the coordinates of which give the optimal value of the objective function.

The graphical method is used to solve a limited class of problems with two variables, sometimes with three variables. It should be noted that for three variables this area is not clear enough.

Algorithm for the graphical method of solving problems

We will consider the implementation of the graphical method for solving the ZLP using examples.

Example 2.2.1. Solve the ZLP graphically:

(2.2.1)

max z=x 1 + 4x 2 (2.2.2)

Solution. To construct a region of feasible solutions, which consists of the intersection of half-planes corresponding to each inequality of the system of constraints (2.2.1), we write the equations of the boundary straight lines:

l 1: x 1 + 5x 2 = 5; l 2: x 1 + x 2 = 6; l 3: 7x 1 + x 2 = 7.

l 1 to the form (2.2.3.) we divide both its parts by 5:
. Thus, straight l 1 cuts on axis Oh 1 5 units, on axis Oh 2 1 unit. Similarly we have for l 2:
And l 3:
.

To determine half-planes that meet the constraints of system (2.2.1), you need to substitute the coordinates of any point that does not lie on the boundary line into the constraints. If we obtain a true inequality, then all points from this half-plane are solutions to this inequality. Otherwise, choose another half-plane.

Thus, the first and second desired half-planes are located in the opposite direction from the origin of coordinates (0 – 5 0 - 5; 7 0 + 0 7), and the second – towards the origin of coordinates (0 + 0 6). The region of feasible solutions in Figure 2.2.1 is shaded.

Figure 2.2.1 – Area of feasible solutions

To find the optimal plan, which will be located at the vertex of the solution polygon, you need to construct a vector of directions
=(With 1 ,With 2), which indicates the direction of the greatest increase in the objective function z=With 1 X 1 +With 2 X 2 .

In this problem, the direction vector
= (1, 4): it starts at the point ABOUT(0,0) and ends at the point N(1, 4).

Next, we construct a straight line that passes through the region of feasible solutions, perpendicular to the vector, and is called target level line functions. We move the level line in the direction of the vector in case of maximizing the objective function z and in the opposite direction, in the case of minimization z, until the last intersection with the region of feasible solutions. As a result, the point or points are determined where the objective function reaches an extreme value, or the unboundedness of the objective function is established z on the set of solutions to the problem.

Thus, the maximum point of the objective function z is the point A line intersections l 2 and l 3 .

To calculate the optimal value of the objective function z find the coordinates of the point A . Since the point A is the point of intersection of the lines l 2 and l 3, then its coordinates satisfy a system of equations composed of the equations of the corresponding boundary lines:

So the point A has coordinates x 1 =1/6, x 2 = 35/6.

To calculate the optimal value of the objective function, you need to substitute the coordinates of the point into it A .

Substituting the coordinates of the point A into the objective function (2.4), we obtain

max z = 1/6 + 4·(35/6) = 47/2.

Example 2.2.2. Construct on the plane the region of feasible solutions of the system of linear inequalities (2.2.4) and find the largest and smallest values of the objective function (2.2.5):

(2.2.4)

z= –2x 1 –x 2 (2.2.5)

l 1: 4x 1 – x 2 = 0; l 2: x 1 + 3x 2 = 6; l 3: x 1 – 3x 2 = 6; l 4: x 2 = 1.

Straight l 1 passes through the point with coordinates (0;0). To construct it, we express x 2 through x 1: x 2 = 4x 1 . Let's find another point through which the line passes l 1, for example (1;4). Through the point with coordinates (0;0) and the point with coordinates (1;4) we draw a straight line l 1 .

To reduce the equation of a straight line l 2 to the form in segments on the axes (2.2.3), we divide both of its parts by 6:
. Thus, straight l 2 cuts on axis Oh 1 6 units, on axis Oh 2 - 2 units. Similarly we have for l 3:
and Direct l 4 parallel to the axis Oh 1 and passes through the point with coordinates (0;1) .

To determine half-planes that meet the constraints of system (2.2.4), it is necessary to substitute the coordinates of any point that does not lie on the boundary line into the constraints. Due to restrictionsX 1 0, X 2 0, the region of admissible solutions of the ZLP lies in the first quarter of the coordinate plane.

ABOUT
the area of feasible solutions in Figure 2.2.2 is shaded.

Figure 2.2.2 – Area of feasible solutions

Let's construct a vector of directions
= (–2,–1). Next, we build a level line perpendicular to the vector .

To find highest value of the objective function, we move the level line in the direction of the vector until the last intersection with the region of feasible solutions. Thus, the maximum point of the objective function z is the point A(intersection of lines l 1 and l 2).

To calculate the optimal value of the objective function z find the coordinates of the point A. Since the point A is the point of intersection of the lines l 1 and l 2, then its coordinates satisfy a system of equations composed of the equations of the corresponding boundary lines:

So the point A has coordinates x 1 =6/13, x 2 = 24/13.

Substituting the coordinates of the point A into the objective function (2.2.5), we obtain the optimal value of the objective function

max z= – 2·(6/13) – (24/13) = – 36/13.

To find the smallest value of the objective function, we move the level line in the direction opposite to the vector until the last intersection with the region of feasible solutions. In this case, the objective function is unlimited in the region of feasible solutions, i.e. ZLP has no minimum.

As a result of the decision of the PPP, the following cases are possible:

The objective function reaches its optimal value at a single vertex of the solution polygon;

The objective function reaches its optimal value at any point on the edge of the solution polygon (the ZLP has alternative reference plans with the same values z );

The PAP does not have optimal plans;

PAP has optimal plan in the case of an unlimited range of feasible solutions.

Linear programming uses a graphical method to determine convex sets (solution polyhedron). If the main linear programming problem has an optimal plan, then the objective function takes a value at one of the vertices of the solution polyhedron (see figure).

Purpose of the service. By using of this service possible in online mode solve the linear programming problem using the geometric method, and also obtain a solution to the dual problem (assess the optimal use of resources). Additionally, a solution template is created in Excel.

Instructions. Select the number of rows (number of restrictions).

If the number of variables is more than two, it is necessary to bring the system to the SZLP (see example and example No. 2). If the constraint is double, for example, 1 ≤ x 1 ≤ 4, then it is split into two: x 1 ≥ 1, x 1 ≤ 4 (i.e., the number of rows increases by 1).
You can also build a feasible solution area (ADA) using this service.

The following are also used with this calculator:
Simplex method for solving ZLP

Solution of the transport problem
Solving a matrix game
Using the online service, you can determine the price of a matrix game (lower and upper bounds), check for the presence of a saddle point, find a solution to a mixed strategy using the following methods: minimax, simplex method, graphical (geometric) method, Brown's method.
Extremum of a function of two variables
Calculation of limits

Solving a linear programming problem by graphical method includes the following steps:

Lines are constructed on the plane X 1 0X 2.
Half planes are determined.
Define a solution polygon;
A vector N(c 1 ,c 2) is constructed, which indicates the direction of the objective function;
Move forward objective function c 1 x 2 + c 2 x 2= 0 in the direction of vector N to the extreme point of the solution polygon.
The coordinates of the point and the value of the objective function at this point are calculated.

The following situations may arise:

Example. The company produces two types of products - P1 and P2. For the production of products, two types of raw materials are used - C1 and C2. Bulk prices unit of production is equal to: 5 units. for P1 and 4 units for P2. The consumption of raw materials per unit of product of type P1 and type P2 is given in the table.
Table - Consumption of raw materials for production

Restrictions on product demand have been established: the daily production volume of P2 products should not exceed the daily production volume of P1 products by no more than 1 ton; The maximum daily production volume of P2 should not exceed 2 tons.
You need to determine:
How many products of each type should the enterprise produce in order to maximize income from product sales?

Formulate mathematical model linear programming problems.
Solve a linear programming problem graphically(for two variables).

Solution.
Let us formulate a mathematical model of the linear programming problem.
x 1 - production of products P1, units.
x 2 - production of products P2, units.
x 1 , x 2 ≥ 0

Resource Limits
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Demand restrictions
x 1 +1 ≥ x 2
x 2 ≤ 2

Objective function
5x 1 + 4x 2 → max

Then we get the following PLP:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → max

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). Let's move this straight line in a parallel way. Since we are interested minimal solution, so we 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