Graphical method for solving linear programming problems. Graphic Methods

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

We will consider the solution of this problem on the 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 respectively. If the system is compatible, then the half-planes, intersecting, form a common part, which is a convex set and is a collection of points; the coordinates of each of these points are the solution of the given system. The collection of these points is called solution polygon. It can be a point, a line segment, a ray, a bounded or an unbounded polygon.

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

A linear equation describes a set of points that lie on a straight line. Linear inequality describes some area on the plane.

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

First, let's construct a 2x line, + Zx 2 = 12. It passes through the points (6; 0) and (0; 4). Second, we determine which half-plane satisfies the inequality. To do this, select any point on the graph that does not belong to the straight line, and substitute its coordinates into the inequality. If the inequality holds, then the given point is a feasible solution and the half-plane containing the point satisfies the inequality. For substitution into the inequality, it is convenient to use the origin of coordinates. Substitute x (= x 2 = 0 into 2x inequality, + Zx 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 LLP 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 domain of feasible solutions(ODR) or domain of definition.

It must be remembered that the domain 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 in the graphical solution of the LLP, 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 \u003d f (x 0), perpendicular to the gradient vector is level line objective function (Fig. 2.2.2). At any point on the level line, the objective function takes the same value. Equate the objective function to a constant value a. Changing 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 with a parallel shift of the line in one direction, the level is only increases and when shifting to the other side - only decreases.

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

• 1. The domain of feasible solutions (ODD) of the LLP is constructed.
• 2. A 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 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 opposite direction 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 ODS during its movement, then the minimum (maximum) of the function f(x p x 2) does not exist.

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

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

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

Table 2.2.1

Example 2.2.1. Planning the output of a sewing enterprise (the problem of costumes).

It is planned to release two types of costumes - men's and women's. A women's costume 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 must be sewn to ensure maximum profit if the profit from the sale of a women's suit is 10 den. units, and from the male - 20 den. units At the same time, it should be borne in mind that at least 60 men's suits must be sewn.

Economic and mathematical model of the problem

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

objective function:

Restrictions:

The first constraint (for 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 \u003d 240 passes through the points (120; 0) and (0; 480). The third constraint (on labor) has the form x y + x 2 150. Straight line x ( + x 2 = 150 passes through the points (150; 0) and (0; 150). The fourth constraint (by the number of men's suits) is x 2> 60. The solution to this inequality is the half-plane lying above the 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 of this polygon satisfies all four functional inequalities, and for any point outside this polygon at least one inequality will be violated.

On fig. 2.2.3 the region of admissible decisions (RDR) 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 build such a vector, you need to connect the point (10; 20) to the origin. For convenience, we can construct a vector proportional to the vector V. Thus, in fig. 2.2.3 shows the vector (30; 60).

Then we will draw a level line 10xj + 20x 2 = a. Equate the objective function to a constant value a. Changing meaning a, we obtain a family of parallel lines, each of which is a level line of the objective function.

Graphical methods are associated primarily with the geometric representation of functional dependence using lines on a plane. Graphs are used to quickly find the value of functions by the corresponding value of the argument, for a visual representation of functional dependencies.
Almost all types of charts are used in economic analysis: comparison charts, time series charts, distribution curves, correlation field charts, statistical cartograms. Comparison diagrams are especially widespread in the analysis - for comparing reporting indicators with planned ones, previous periods and advanced domestic or foreign enterprises. For a visual representation of the dynamics of economic phenomena (and in the analysis of time series one has to deal very often), time series diagrams are used.
With the help of a coordinate grid, graphs are constructed depending, for example, on the level of costs on the volume of manufactured and sold products, as well as. graphs that can also show correlations between indicators. In the system of coordinate axes, the image shows the influence of various factors on a particular indicator.
The graphical method is widely used to study production processes, organizational structures, programming processes, etc. For example, to analyze the efficiency of the use of production equipment, calculated graphs are built, including graphs of multiple factors.

Notation: each circle is considered one of the vertices of the graph; the figure in the upper sector of each vertex means its serial number; from the numbers of two neighboring vertices, the code of the work is added; the figure in the lower sector of each vertex is the serial number of the previous vertex, and the line connecting these two vertices means a certain work. At the bottom, under the line, the planned duration of this work is recorded; the figure in the left sector of each vertex means the total duration of all previous works, the figure in the right sector differs from the figure in the left one by the amount of the reserve (time reserve). Thus, for vertices lying on the critical path, the numbers in the left and right sectors of the vertex are the same, since the time margin is 0.

In a mathematically formalized system of analysis, planning and management, network graphs occupy a special place. They give a great economic effect in the construction and installation of industrial and other enterprises.
The network schedule (Fig. 6.1) allows you to select the most important ones that lie on the critical path from the entire complex of works, and concentrate the main resources of construction and assembly organizations on them, establish the relationship between various specialized organizations and coordinate their work. Activities on the critical path require the longest wait for the arrival of the next event. At the stage of operational analysis and management, the network schedule makes it possible to exercise effective control over the progress of construction, to take timely measures to eliminate possible delays in work.
The use of network schedules for analysis, planning and management provides, as many examples show, a reduction in construction time by 20-30%, an increase in labor productivity by 15-20%.
In the analysis carried out directly at construction sites, the use of network planning and management materials helps to correctly determine the causes that affect the progress of construction, and identify enterprises that do not ensure the execution of the work assigned to them or the delivery of equipment on schedule.
The development of a network schedule in construction is carried out in the presence of: norms for the duration of construction and the period for commissioning an object or a complex of objects, design estimates, a project for organizing construction and work, standard technological maps, current norms for labor costs, materials and machines. In addition, when drawing up the schedule, the experience of performing individual works, as well as data on the production base of construction and installation organizations, are used.
On the basis of all these data, a table of works and resources is compiled, where their characteristics, volume, labor intensity in man-days, performer (organization and team), number of workers, shifts, need for mechanisms and materials, sources of their receipt are indicated in the technological sequence of work. , the total duration of the work in days, as well as the previous task, after which you can start this work. Based on the indicators of such a table, a network schedule is prepared, which can have a different degree of detail, depending on the adopted production scheme.
management of works and level of management; in addition to the general schedule, the performers develop a schedule for the work they perform.
The main elements of the network diagram: event, work, expectation, dependence.
When analyzing the progress of the construction of an object, it should be established whether the network schedule is correctly drawn up, whether the overestimation of the critical path is not allowed, whether all the possibilities of its reduction are taken into account when optimizing the schedule, whether it is possible to perform any work in parallel or reduce the time spent on them by increasing the means of mechanization, etc. This is especially important in cases where the duration of work according to the schedule does not ensure the completion of construction on time.
The main material of network planning used in the analysis is information on the progress of work according to the schedule, which is usually drawn up at least once a decade. As an example, a map of the task and information on the progress of work on the construction object, carried out according to the network schedule, is given (Table 6.1). According to the map, critical work was carried out at the beginning of the month ahead of schedule, but then the installation of crane beams on row B was delayed, and the subsequent work - installation of crane beams on row A - was completed one day behind.
Optimization of network schedules is carried out at the planning stage by reducing the critical path, i.e., minimizing the timing of construction work at given levels of resources, minimizing the level of consumption of material, labor and financial resources with fixed terms of construction work. A mixed approach is also possible: for one part of the work (more expensive) - to minimize the level of resource consumption with fixed deadlines for the performance of work, for the other - to minimize the time with a fixed level of resources.
The solution of optimization problems is greatly facilitated by the availability of application software packages (APP) adapted to the compilation of optimal network schedules on a computer.
In the foreign practice of system analysis, a graph-mathematical method called the "decision tree" is widespread. The essence of this method is as follows.
By preliminary assessment of needs, preliminary analysis of possible organizational, technical or technological conditions, all possible options for solving this problem are outlined. First developed

Installation of crane runways and installation of a tower crane 7-10
Installation of support frames on the foundation for equipment 7-16 Installation of crane beams:
on row B 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2

for row A 10-12 25/IV 26/IV
Installation of the first part of beams and roof slabs 12-13 27/IV 4/V
Installation of crane runways bridge lt;3 cranes 12-14 27/IV 3/V

1. 100 -

enlarged options. Then, as additional conditions are introduced, each of them is divided into a number of options. The graphic representation of these options allows you to exclude the less profitable ones and choose the most acceptable one.
This method can be used by us in determining the order of processing of certain parts on several machines in order to minimize the total processing time; when setting the size of resources to minimize total production costs; when distributing capital investments and other resources among industrial facilities; when solving transport and other problems.

In this lesson, we will get acquainted with the graphical method of solving linear programming problems, that is, such problems in which it is required to find such a solution to a system of linear equations and (or) inequalities (a system of constraints), in which the goal function - a linear function - takes the optimal value.

Due to the fact that the visibility of the graphical solution is achieved only on a plane, we can get acquainted with the graphical representation of the problem only in a two-dimensional space. This representation is suitable for a system of inequality constraints with two variables or for systems of equations in which the number of variables is 2 more than the number of equations, that is, the number of free variables is two.

Therefore, the graphical method has such a narrow scope of application that it is impossible to speak of it as a special method for solving linear programming problems.

However, for the development of visual representations of the solutions of linear programming problems, the graphical method is of particular interest. In addition, it allows geometrically confirming the validity linear programming theorems .

Theoretical foundations of the graphical method

So, the problem of linear programming. It is required to find non-negative values ​​of variables and satisfying the system of inequalities

at which the linear form takes the optimal value.

Example 3

Example 4 Solve a linear programming problem using a graphical method, in which it is required to find the minimum of a function under constraints

We continue to solve problems graphically together

So far, the conclusions drawn have been based on the fact that the solution set of a linear programming problem is configured in such a way that the optimal solution is finite and unique. Now consider examples where this condition is violated. In these examples, the decision polygon is constructed as shown in the previous examples, but let us dwell on the features that distinguish these exceptional examples.

Example 5 Solve a linear programming problem using a graphical method in which it is required to find the maximum of a function under constraints

Decision. The figure shows: an unlimited polyhedral area of ​​solutions of this system of restrictions, the initial level line (black), a vector (burgundy) indicating the direction of movement of the initial level line to find the maximum of the objective function.

It is easy to see that the function F can increase indefinitely under a given system of constraints, so we can conditionally write that .

Example 6 Solve a linear programming problem using a graphical method in which it is required to find the maximum of a function under constraints

Example 6.1.

Decision:

A linear programming problem is given in standard form and has two design parameters, hence

It is possible to solve it by a geometric method.

Stage 1: ( ODR ).

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

.

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

Stage 2: .

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

Let us consider the first inequality of the problem's constraint system. Take some point (control point) that does not belong to the line corresponding to the given inequality, for example, the point (0; 0). Substitute it into the considered inequality:

When substituting the coordinates of the control point, the inequality remains valid. Consequently, the set of points belonging to this straight line (because the inequality is not strict), as well as located below it, will be solutions to the considered inequality (we mark on the graph (Fig. 1) the found half-plane with two arrows pointing down next to the straight line I ) .

Similarly, we determine the solutions of other inequalities and mark them accordingly on the graph. As a result, the graph will take the following form:

Stage 3: .

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

Rice. 1. Domain of admissible solutions of the problem

Stage 4:
The gradient vector shows the direction of maximization of the 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: .

Consider the objective function of this problem:

.

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

.

To construct a straight line according to this equation, we set two arbitrary points, for example:

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

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

Stage 6: determination of the maximum objective function.

Moving the line F(X) parallel to itself in the direction of the gradient vector, we determine the extreme point (s) 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 us determine the coordinates of the point C, for this purpose, we will solve the following system of linear equations:

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

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

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

Decision:

Steps 1-3 are similar to the corresponding steps in 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 mark on this graph with an arrow the direction opposite to the gradient vector - the direction of minimizing the objective function F (X).

Stage 5: construction of a direct objective function.

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

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

Stage 6: determination of the optimal objective function.

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

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

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

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

Decision:

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

Compile the extended matrix and select the basic variables using the Jordan-Gauss method x1 and x 2 .

Multiply (element by element) the first row by -3 and add it to the second:
.

Multiply the second row by:

.

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

.

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

We express the basic variables in terms of the free ones:

We also express the objective function in terms of free variables, for this we substitute the obtained values ​​of the basic variables into the objective function:

We write down the resulting linear programming problem:

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

Then the original problem can be written as the following equivalent standard linear programming problem:

This problem has two design parameters, therefore, it can be solved by a geometric method.

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

Consider a system of constraints for a linear programming problem (for convenience, we number the inequalities):

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

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

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

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

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

Rice. 6. Fragment of MathCAD-document:

construction of the domain of admissible solutions of the 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 the given point (ie, located on the other side of the line).

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

Brief theory

Linear programming is a section of mathematical programming used in the development of methods for finding the extremum of linear functions of several variables with linear additional restrictions imposed on the variables. According to the type of tasks to be solved, its methods are divided into universal and special. With the help of universal methods, any linear programming problem (LPP) can be solved. Special methods take into account the features of the problem model, its objective function and the system of constraints. A feature of linear programming problems is that the objective function reaches an extremum at the boundary of the region of feasible solutions.

The graphical method for solving linear programming problems makes it possible to visualize their structure, identify features, and opens up ways to study more complex properties. A linear programming problem with two variables can always be solved graphically. However, even in a three-dimensional space, such a solution becomes more complicated, and in spaces whose dimensions are greater than three, a graphical solution, generally speaking, is impossible. The case of two variables is not of particular practical importance, but its consideration clarifies the properties of the LLP constraints, leads to the idea of ​​its solution, makes the methods of solution and the ways of their practical implementation geometrically clear.

If the constraints and the objective function contain more than two variables, then it is necessary (or by the method of successive improvement of the solution) - it is universal and any LLP can be solved with it. For some applied linear programming problems, such as , special solution methods have been developed.

Problem solution example

The task

The enterprise produces two types of products: Product 1 and Product 2. For the manufacture of a unit of Product 1, it is required to spend kg of raw materials of the first type, kg of raw materials of the second type, kg of raw materials of the third type. For the manufacture of a unit of Product 2, it is required to spend kg of the first type, raw materials of the second type, raw materials of the third type. Production is provided with raw materials of each type in the amount of kg, kg, kg, respectively. The market price of a unit of Product 1 is thousand rubles, and a unit of Product 2 - thousand rubles.

Required:

• Build a mathematical model of the problem.
• Draw up a plan for the production of products that provides maximum revenue from their implementation using a graphical method for solving a linear programming problem.

In order for the solution of the linear programming problem to be as accurate and correct as possible, many inexpensively order tests on this site. Details (how to leave an application, prices, terms, payment methods) can be found on the page Buy a test in linear programming...

The solution of the problem

Model building

Denote by and the number of manufactured products of the 1st and 2nd type.

Then the resource limits are:

In addition, according to the meaning of the task

The target function of the economic-mathematical model, expressing the proceeds received from the sale:

We get the following economic and mathematical model:

Construction of the domain of feasible solutions

Let's solve the resulting linear programming problem graphically:

To construct the region of feasible solutions, we construct in the coordinate system the boundary lines corresponding to the given constraints-inequalities:

Find the points through which the lines pass:

The solution to each inequality of the LLP constraint system is a half-plane containing the boundary line and located on one side of it.

To determine the half-plane, let's take any point, for example, not belonging to the line (1), substitute the coordinates (0;0) into the corresponding inequality. Because the inequality is true:

The region of solutions of the corresponding 1st inequality corresponds to the left half-plane

Take any point, for example, not belonging to the line (2), substitute the coordinates (0;0) in the corresponding inequality. Because the inequality is true:

Take any point, for example, not belonging to the line (3), substitute the coordinates (0;0) in the corresponding inequality. Because the inequality is true:

The region of solutions of the corresponding 2nd inequality corresponds to the left half-plane

The area of ​​feasible solutions is the figure .

Finding a solution to the LP problem

We build a vector whose coordinates are proportional to the coefficients of the objective function. Here is the coefficient of proportionality.

Draw a level line perpendicular to the constructed vector.

We move the level line in the direction of the vector so that it touches the area of ​​feasible solutions at the extreme point. The solution to the maximum is the point , whose coordinates are found as the point of intersection of lines (2) and (1).

Answer

Thus, it is necessary to produce 56 products of the 1st type and 64 products of the 2nd type. At the same time, the proceeds from the sale of products will be maximum and will amount to 5104 monetary units.

The graphical solution method, if the problem with two variables has linear constraints, and the objective function is quadratic, is discussed in detail here
The page analyzes in detail the solution of a linear programming problem by the simplex method, in addition, it shows the construction of a dual linear programming problem and finding its solution by solving a direct problem.

Transport problem and the method of potentials
The transport problem, its mathematical model and solution methods are considered in detail - finding the reference plan by the minimum element method and searching for the optimal solution by the potential method.

Convex programming - graphical method
An example of solving the problem of quadratic convex programming by a graphical method is given.