Find a solution to the problem. Graphic method for solving lp problems. An example of solving a linear programming problem using the graphical method

The solution occurs in three stages:

1. Transition to KZLP. Any LLP of the form ax ≤ b , ax ≥ b , ax = b (F(X) → extr) reduces to the form ax = b , F(X) → max ;
2. Transition to SZLP. A CLLP of the form ax = b reduces to the form ax ≤ b , F(X) → max ;
3. Solution using the simplex method;

Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is saved in a Word file.

Transition from the objective function minimization problem to the maximization problem

F(x) → min

F(x) → max

Leading (resolving) element is the coefficient of the free unknown, which becomes the basic one, and the coefficient itself is converted to unity.
Guide line– the line of the leading element, in which the basic unknown is located with a unit coefficient, excluded during the transformation (line with the minimum limiting coefficient, see below).
Guide Column– the column of the leading element, the free unknown of which is converted to the basic one (the column with the maximum benefit, see below).

Variables x 1, ..., x m, included with unit coefficients in only one equation of the system, with zero coefficients in the rest, are called basic or dependent. In the canonical system, each equation corresponds to exactly one basic variable. The transition is carried out using the Gauss-Jordan method. The main idea of ​​this method is to reduce a system of m equations with n unknowns to a canonical form using elementary operations on strings.
The remaining n-m variables (x m +1 ,…, x n) are called non-basic or independent variables.

Basic solution called admissible basic solution, if the values ​​of the basic variables included in it x j ≥0, which is equivalent to the non-negativity condition b j ≥0.
A feasible basis solution is corner point admissible set S of a linear programming problem and is sometimes called reference plan.
If among the non-negative numbers b j there are equal to zero, then the admissible basic solution is called degenerate(degenerate corner point) and the corresponding linear programming problem is called degenerate.

Example No. 1. Reduce the linear programming problem to a standard ZLP.
F(X) = x 1 + 2x 2 - 2x 3 → min with restrictions:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
To bring the ZLP to the canonical form it is necessary:
1. Change the sign of the objective function. Let us reduce the problem F(X) → min to the problem F(X) → max. To do this, multiply F(X) by (-1). In the first inequality of meaning (≤) we introduce the basic variable x 4 ; in the second inequality of meaning (≥) we introduce the basic variable x 5 with a minus sign.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Transition to SZLP.
Extended matrix of the system of equality constraints for this problem:

Example No. 2. First, find the solution to the problem using the graphical method and then the simplex method.
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) with restrictions:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

This method is a method of purposeful enumeration of reference solutions to a linear programming problem. It allows, in a finite number of steps, either to find an optimal solution or to establish that there is no optimal solution.

1. Indicate a method for finding the optimal reference solution
2. Indicate the method of transition from one reference solution to another, at which the value of the objective function will be closer to the optimal one, i.e. indicate a way to improve the reference solution
3. Set criteria that allow you to promptly stop searching for support solutions at the optimal solution or draw a conclusion about the absence of an optimal solution.

Algorithm of the simplex method for solving linear programming problems

1. Bring the problem to canonical form
2. Find the initial support solution with a “unit basis” (if there is no support solution, then the problem does not have a solution due to the incompatibility of the system of constraints)
3. Calculate estimates of vector decompositions based on the reference solution and fill in the table of the simplex method
4. If the criterion for the uniqueness of the optimal solution is satisfied, then the solution of the problem ends
5. If the condition for the existence of a set of optimal solutions is met, then all optimal solutions are found by simple enumeration

An example of solving a problem using the simplex method

Solve the problem using the simplex method:

Solution:

We bring the problem to canonical form.

To do this, we introduce an additional variable x 6 with coefficient +1 to the left side of the first inequality constraint. The variable x 6 is included in the objective function with a coefficient of zero (i.e., it is not included).

We get:

We find the initial support solution. To do this, we equate free (unresolved) variables to zero x1 = x2 = x3 = 0.

We get reference solution X1 = (0,0,0,24,30,6) with unit basis B1 = (A4, A5, A6).

We calculate estimates of vector decompositions conditions on the basis of the reference solution according to the formula:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vector of coefficients of the objective function for the basic variables
• X k = (x 1k, x 2k, ..., x mk) - vector of expansion of the corresponding vector A k according to the basis of the reference solution
• C k is the coefficient of the objective function for the variable x k.

The estimates of the vectors included in the basis are always equal to zero. The reference solution, expansion coefficients and estimates of expansions of condition vectors based on the reference solution are written in simplex table:

At the top of the table, for ease of calculation of estimates, the coefficients of the objective function are written. The first column "B" contains the vectors included in the basis of the reference solution. The order in which these vectors are written corresponds to the numbers of allowed unknowns in the constraint equations. In the second column of the table "C b" the coefficients of the objective function for the basic variables are written in the same order. With the correct arrangement of the coefficients of the objective function in the column "C b", the estimates of the unit vectors included in the basis are always equal to zero.

In the last row of the table with estimates of Δ k in the column “A 0” the values ​​of the objective function on the reference solution Z(X 1) are written.

The initial support solution is not optimal, since in the maximum problem the estimates Δ 1 = -2, Δ 3 = -9 for vectors A 1 and A 3 are negative.

According to the theorem on improving the support solution, if in the maximum problem at least one vector has a negative estimate, then you can find a new support solution on which the value of the objective function will be greater.

Let us determine which of the two vectors will lead to a larger increment in the objective function.

The increment of the objective function is found by the formula: .

We calculate the values ​​of the parameter θ 01 for the first and third columns using the formula:

We obtain θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Table 26.1).

We find the increment of the objective function when introducing into the basis the first vector ΔZ 1 = - 6*(- 2) = 12, and the third vector ΔZ 3 = - 3*(- 9) = 27.

Consequently, for a faster approach to the optimal solution, it is necessary to introduce vector A3 into the basis of the reference solution instead of the first vector of the basis A6, since the minimum of the parameter θ 03 is achieved in the first row (l = 1).

We perform the Jordan transformation with the element X13 = 2, we obtain the second reference solution X2 = (0,0,3,21,42,0) with the basis B2 = (A3, A4, A5). (Table 26.2)

This solution is not optimal, since vector A2 has a negative estimate Δ2 = - 6. To improve the solution, it is necessary to introduce vector A2 into the basis of the reference solution.

We determine the number of the vector derived from the basis. To do this, we calculate the parameter θ 02 for the second column, it is equal to 7 for l = 2. Consequently, we derive the second basis vector A4 from the basis. We perform the Jordan transformation with the element x 22 = 3, we obtain the third reference solution X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Table 26.3).

This solution is the only optimal one, since for all vectors not included in the basis the estimates are positive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Answer: max Z(X) = 201 at X = (0.7,10,0.63).

Linear programming method in economic analysis

Linear programming method makes it possible to justify the most optimal economic solution under conditions of severe restrictions related to the resources used in production (fixed assets, materials, labor resources). The use of this method in economic analysis makes it possible to solve problems related mainly to planning the activities of an organization. This method helps to determine the optimal quantities of product output, as well as the directions for the most effective use of the production resources available to the organization.

Using this method, the so-called extremal problems are solved, which consists in finding extreme values, that is, the maximum and minimum of functions of variable quantities.

This period is based on solving a system of linear equations in cases where the analyzed economic phenomena are connected by a linear, strictly functional dependence. The linear programming method is used to analyze variables in the presence of certain limiting factors.

It is very common to solve the so-called transport problem using the linear programming method. The content of this task is to minimize the costs incurred in connection with the operation of vehicles under existing restrictions regarding the number of vehicles, their carrying capacity, the duration of their operation, if there is a need to serve the maximum number of customers.

In addition, this method is widely used in solving the scheduling problem. This task consists of such a distribution of operating time for the personnel of a given organization that would be most acceptable both for the members of this personnel and for the clients of the organization.

This task is to maximize the number of clients served under conditions of limitations on the number of available staff members, as well as the working time fund.

Thus, the linear programming method is very common in the analysis of the placement and use of various types of resources, as well as in the process of planning and forecasting the activities of organizations.

Nevertheless, mathematical programming can also be applied to those economic phenomena, the relationship between which is not linear. For this purpose, nonlinear, dynamic and convex programming methods can be used.

Nonlinear programming relies on the nonlinear nature of the objective function or constraints, or both. The forms of the objective function and inequality constraints in these conditions can be different.

Nonlinear programming is used in economic analysis, in particular, when establishing the relationship between indicators expressing the efficiency of an organization’s activities and the volume of this activity, the structure of production costs, market conditions, etc.

Dynamic programming is based on constructing a decision tree. Each tier of this tree serves as a stage for determining the consequences of a previous decision and for eliminating ineffective options for that decision. Thus, dynamic programming has a multi-step, multi-stage nature. This type of programming is used in economic analysis to find optimal options for the development of an organization both now and in the future.

Convex programming is a type of nonlinear programming. This type of programming expresses the nonlinear nature of the relationship between the results of an organization’s activities and its costs. Convex (aka concave) programming analyzes convex objective functions and convex constraint systems (feasibility points). Convex programming is used in the analysis of economic activities with the aim of minimizing costs, and concave programming with the aim of maximizing income under existing restrictions on the action of factors that influence the analyzed indicators in the opposite way. Consequently, with the types of programming under consideration, convex objective functions are minimized, and concave objective functions are maximized.

If you need to solve a linear programming problem using simplex tables, then our online service will be of great help to you. 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. Here is the sequence of actions when solving a linear programming problem using the simplex method:

First step. In the compiled table, first of all, you 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.

Second step. 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, we 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 there are none 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.

Third step. In the third step, we recalculate the entire simplex table using special formulas; these formulas can be seen using.

Fourth step. If after recalculation there are negative elements left in the column of free terms, then go to the first step; if there are none, then to the fifth.

Fifth step. 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.

The simplest and most visual method of linear programming (LP) is the graphical method. It is used to solve LP problems with two variables. Consider the LP problem in standard form:

max f(x 1 , x 2 , ..., x n) = ,

, i = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Let's put n=2 and we will consider the problem on the plane. Let the system of inequalities be consistent (have at least one solution).

Each inequality of this system geometrically defines a half-plane with the boundary line a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. The non-negativity conditions define half-planes with boundary straight lines x 1 = 0, x 2 = 0, respectively. The system is consistent, therefore half-planes, like convex sets, intersecting, form a common part, which is a convex set and is a collection of points, where the coordinates of each point are a solution to this system. The set of these points is called a solution polygon. It can be a point, a segment, a ray, a bounded or unbounded polygon.

Thus, geometrically, the ZLP is the search for such a point of the solution polygon, the coordinates of which provide the maximum (minimum) value to the linear function of the goal, and 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 is described by the inequality 2x 1 + 3x 2 12.

First, let's construct a straight line 2x 1 + 3x 2= 12. It passes through the points (6; 0) and (0; 4). In order to determine which half-plane satisfies the inequality, it is necessary to 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 the given point is a feasible solution, and the half-plane containing the point satisfies the inequality. To substitute into the inequality, it is convenient to use the origin point. Substitute x 1 = x 2 = 0 into the inequality 2x 1 + 3x 2 12. We get 2x0 + 3x0 12. This statement is true, therefore, the inequality 2x 1 + 3x 2 12 corresponds to the lower half-plane containing the point (0; 0). This is reflected in the graph shown in Fig. 1.1.

Similarly, all the constraints of the LP problem can be graphically depicted.

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 the region of admissible solutions, or the region of definition. It must be remembered that the region of feasible solutions satisfies the conditions of non-negativity ( x j 0, j = 1, 2, …, n). 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 LP problems graphically, a gradient vector is used, the coordinates of which are partial derivatives of the objective function, i.e.

This vector shows the direction of the fastest change in the objective function. Direct line with 1 x 1 + with 2 x 2 = f(x 0), perpendicular to the gradient vector, is the level line of the objective function. 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 value of “a”, we obtain a family of parallel lines, each of which is a level line of the objective function.

An important property of the level line of a linear function is that when the line is parallelly shifted in one direction, the level only increases, and when shifted in the other direction, it only decreases.

From a geometric point of view, in a linear programming problem, we are looking for such a corner point or a set of points from an admissible set of solutions at which the highest (lowest) level line is reached, located further (closer) than the others in the direction of fastest growth.

The graphical method for solving the ZLP consists of the following steps.

1. A polygonal region of admissible solutions (ADS) of the PLP is constructed.

2. The gradient vector of the objective function (TF) is constructed at some point x 0 belonging to the ODR:

3. The level line c 1 x 1 + c 2 x 2 = a (a is a constant value) - a straight line perpendicular to the gradient vector - moves in the direction of this vector in the case of maximizing f (x 1, x 2) until until it leaves the ODR. The limit point (or points) of the area during this movement is the maximum point f(x 1, x 2).

4. To find the coordinates of the maximum point, it is enough to solve two straight line equations obtained from the corresponding restrictions and giving the maximum point at the intersection. The value f(x 1, x 2) found at the resulting point is the maximum.

When minimizing (maximizing) the function f(x 1, x 2), the level line moves in the direction opposite to the gradient vector. 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 1, x 2) does not exist.

If the level line is parallel to any functional constraint of the problem, 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. Possible situations for graphically solving LP problems are presented in Table. 1.3.

Table 1.3

Let's consider the graphical solution of linear programming problems using the following example.

Example 1.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 person/day of labor. For a men's suit - 3.5 m of wool, 0.5 m of lavsan and 1 person/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 made to ensure maximum profit, if the profit from the sale of a women's suit is 10 monetary units, and from a men's suit - 20 monetary units. It should be borne in mind that it is necessary to sew at least 60 men's suits.

Let us introduce the following notation: x 1 - the number of women's suits; x 2 – number of men's suits. The profit from the sale of women's suits is 10x 1, and from the sale of men's suits - 20x 2, i.e. it is necessary to maximize the objective function:

10x 1 + 20x 2

The task constraints have the form:

x 1 + x 2 150,

2 x 1 + 0.5x 2 240,

x 1 + 3.5x 2 350,

x 2 60,

x 1 0.

The first labor limitation is x 1 + x 2 150. The straight line x 1 + x 2 = 150 passes through the points (150; 0) and (0; 150) (Fig. 1.2).

The second constraint on lavsan is 2 x 1 + 0.5x 2 240. The straight line 2 x 1 + 0.5x 2 = 240 passes through the points (120; 0) and (0; 480). Third limitation on wool x 1 + 3.5x 2,350. Let's add a fourth limitation on the number of men's suits x 2 60. The solution to this inequality is the half-plane lying above the straight line x 2 = 60. In Fig. 1.3 the region of feasible solutions is shaded. To determine the direction of movement towards the optimum, we construct a gradient vector, the coordinates of which are partial derivatives of the objective function, i.e.

To construct such a vector, you need to connect the point (10;20) to the origin. When maximizing the objective function, it is necessary to move in the direction of the gradient vector, and when minimizing, it is necessary to move in the opposite direction. For convenience, you can construct a vector proportional to the vector . So, in Fig. 1.4 shows the gradient vector (30;60).

To determine the direction of movement towards the optimum, we construct a gradient vector, the coordinates of which are partial derivatives of the objective function, i.e.

In our case, we will move the level line until it leaves the region of feasible solutions. At the extreme, corner point, the maximum of the objective function is achieved. To find the coordinates of this point, it is enough to solve two straight line equations obtained from the corresponding restrictions and giving a maximum point at the intersection:

x 1 + 3.5x 2 = 350,

x 1 + x 2 = 150.

From here it is easy to write down the solution to the original ZLP: max f(x)= 2300 and is achieved at x 1 = 70 and x 2 = 80 (see Fig. 1.4).

1.3.TECHNOLOGY FOR SOLVING LINEAR PROGRAMMING PROBLEMS USING THE SOLUTION SEARCH ADD-ON IN EXCEL ENVIRONMENT

1.3.1. General information about working with the Excel spreadsheet

Let's consider some aspects of working with the Excel spreadsheet processor, which will simplify the calculations necessary to solve optimization problems. A table processor is a software product designed to automate the processing of tabular data.

Excel Screen Elements. After launching Excel, a table appears on the screen, the appearance of which is shown in Figure 1.5.

This image is called a worksheet. It is a grid of rows and columns, the intersections of which form rectangles called cells. Worksheets are designed for entering data, performing calculations, organizing an information base, etc. The Excel window displays the main program elements: title bar, menu bar, status bar, window control buttons.

Working with formulas. Spreadsheet programs use formulas to perform many different calculations. Using Excel, you can quickly create a formula. The formula consists of three main parts:

1) equal sign;

2) a set of values ​​or references in the cells with which calculations are performed;

3) operators.

4) If there is no equal sign, then Excel interprets the data not as a formula, but as data entered into a cell. Formulas can be entered directly into a cell or into the formula bar - either text or numbers. In this case, you need to perform the following steps:

· select the cell that should contain the formula and enter the sign (=);

· enter an operator or action sign;

· select another cell included in the formula;

· press the Enter key.

The entered formula will appear in the formula bar, and the calculation result will appear in the cell.

Using functions in formulas. To make entering formulas easier, you can use Excel functions. Functions are formulas built into Excel. Excel contains many formulas. They are grouped into different types: logical, mathematical, engineering, statistical, etc.

To activate a particular formula, click the Insert, Functions buttons. The Function Wizard window that appears on the left contains a list of function types. After selecting a type, a list of the functions themselves will be placed on the right. The selection of a function is carried out by clicking the mouse button on the corresponding name.

Different functions perform different types of calculations according to certain rules. When a function is a single object in a worksheet cell, it begins with a (=) sign, followed by the name of the function, and then the arguments to the function, enclosed in parentheses.

Find a Solution is an Excel add-in that allows you to solve optimization problems. If the Search for Solution command is not available in the Tools menu, then you need to download this add-on. Select the command Tools => Add-ons and activate the Search for a solution add-on. If this add-in is not in the Add-Ins dialog box, then you need to go to the Windows Control Panel, click on the Add or Remove Programs icon and use the Excel (or Office) installer to install the Find a Solution add-in.

After selecting the commands Tools => Search for a solution, the Search for a solution dialog box will appear.

There are three main options in the Find Solution dialog box;

Set target cell.

Changing cells.

Restrictions.

First you need to fill in the Set target cell field. In all tasks for the Find a Solution tool, the result in one of the worksheet cells is optimized. The target cell is related to other cells in that worksheet using formulas. The Find Solution tool uses formulas that produce a result in the target cell to test possible solutions. You can choose to find the smallest or largest value for the target cell, or set a specific value.

The second important option in the Find Solution tool is the Changing Cells option. Here you specify the cells whose values ​​will be changed in order to optimize the result in the target cell. You can specify up to 200 changeable cells to find a solution. There are two main requirements for these cells: they must not contain formulas, and changes in their values ​​must be reflected in a change in the result in the target cell. In other words, the target cell depends on the cells being modified.

The third parameter that must be entered on the Search for a solution tab is restrictions.

To solve the problem you need:

1) indicate the addresses of the cells in which the result of the decision will be placed (changeable cells);

2) enter the initial data;

3) introduce a dependence for the objective function;

4) introduce dependencies for restrictions,

5) run the Search for solutions command;

6) assign a cell to the target function (set target cell);

7) introduce restrictions;

8) enter parameters for solving the LLP.

Let's consider the solution technology using the conditions of Example 1.1 (the suit problem).

Economic and mathematical model of the problem

Let x 1 be the number of women's suits; x 2 - the number of men's suits,

10 x x 1 + 20 x x 2 max

The task constraints have the form:

x 1 + x 2 150 - labor limitation;

2 x x 1 + 0.5 x X 2,240 - limit on lavsan;

x 1 + 3.5 x x 2 350 - wool limit;

x 2 60 - limit on men's suits;

x 1 0 - restriction on women's suits.

1. Specify the addresses of the cells in which the solution result will be placed (changeable cells).

Denote by x 1, x 2 the number of suits of each type. In our problem, the optimal values ​​of the vector = (x 1, x 2) will be placed in cells A2:B2, the optimal value of the objective function - in cell SZ.

2. Enter the initial data.

Enter the initial task data as shown in Fig. 1.6.

3. Introduce a dependency for the objective function.

· Place the cursor in the “NW” cell, the cell will be selected.

· Place the cursor on the Function Wizard button located on the toolbar.

· Enter Enter. The Function Wizard step 1 of 2 dialog box appears on the screen.

· In the Functions window, select the SUMPRODUCT line (Fig. 1.7). On the screen

· the SUMPRODUCT dialog box appears (Fig. 1.8).

· Enter in the Array 1 line A2:B2.

· Enter AZ:VZ in the Array 2 line.

Array 1 will be used when entering dependencies for constraints, so an absolute reference must be made to this array. In Fig. Figure 1.9 shows that a function has been introduced into cell SZ.

5. Enter dependencies for constraints (Figure 1.10).

· Place the cursor in cell NW.

· On the toolbar there is a Copy to Clipboard button.

· Place the cursor in cell C4.

· Place the cursor in cell C5.

· On the toolbar, the Paste from Clipboard button.

· Place the cursor in the Sat cell.

· On the toolbar, the Paste from Clipboard button.

· Place the cursor in cell C7.

· On the toolbar, click the Paste from Clipboard button. (The contents of cells C4-C7 must be checked. They must contain information, as shown for example in Fig. 1.11; the contents of cell C5 are presented as an example.)

· In the Menu line, place the mouse pointer on Service. In the expanded menu, select the Search for solution command. The Search for Solution dialog box appears (Fig. 1.12).

5. Run the Search for solution command.

6. Assign a cell to the target function (set the target cell), indicate the addresses of the cells to be changed.

· Place the cursor in the Set target cell line.

· Enter the address of cell $С$3.

· Enter the type of objective function depending on the conditions of your problem. To do this, note what the objective function is equal to - Maximum value or Minimum value.

· Place the cursor in a row by changing cells.

· Enter the addresses of the required variables A$2:B$2 (Fig. 1.13).

7. Introduce restrictions.

· Place the mouse pointer on the Add button. The Add Constraint dialog box appears.

· Enter a restriction sign.

· In the Restriction line, enter the address $D$4 (Fig. 1.14).

· Place the mouse pointer on the Add button. The Add Restriction dialog box will reappear.

· Enter the remaining constraints of the problem using the algorithm described above.

· After entering the last restriction, click on the OK button. The Search for Solution dialog box with the entered conditions will appear on the screen (Fig. 1.15).

8. Enter parameters for solving the linear programming problem.

· In the dialog box, place the mouse pointer on the Options button. The Solution Search Options dialog box will appear on the screen (Fig. 1.16).

· Check the boxes in the Linear model (this will ensure the use of the simplex method) and Non-negative values.

· Place the mouse pointer on the OK button. The Search for Solution dialog box will appear on the screen.

· Place the mouse pointer on the Run button.

After a short time, the solution search results dialog box and the original table with filled cells AZ:VZ for values ​​x i and cell SZ with the maximum value of the objective function will appear (Fig. 1.17).

If you specify the report type Stability, you can get additional information about the optimal solution (Fig. 1.18).

As a result of solving the problem, the answer was received: it is necessary to sew 70 pieces. women's suits and 80 pcs. men's suits to get a maximum profit of 2300 USD.

1.4. DUALITY IN LINEAR PROGRAMMING PROBLEMS. ANALYSIS OF OBTAINED OPTIMAL SOLUTIONS

In 1975, our compatriot L.V. Kantorovich was awarded the Nobel Prize in Economics (together with the American economist T. Koopmans) for developing the theory of optimal use of resources (see Appendix 1).

Closely related to every linear programming problem is another linear problem called the dual; the original problem is called the original, or direct. The connection between the original and dual problems lies, in particular, in the fact that the solution of one of them can be obtained directly from the solution of the other.

The variables of the dual problem y i are called objectively determined estimates, or dual estimates, or “prices” of resources, or shadow prices.

Each of the dual pair problems is actually an independent linear programming problem and can be solved independently of the other.

The dual problem in relation to the original one is composed according to the following rules:

1) the objective function of the original problem is formulated as a maximum, and the objective function of the dual problem is formulated as a minimum, while in the maximum problem all inequalities in the functional constraints have the form (), in the minimum problem they have the form ( );

2) matrix A, composed of coefficients for unknown constraints in the system of the original problem, and a similar matrix A T in the dual problem are obtained from each other by transposing;

3) the number of variables in the dual problem is equal to the number of functional constraints in the original problem, and the number of restrictions in the system of the dual problem is equal to the number of variables in the original one;

4) the coefficients of the unknowns in the objective function of the dual problem are the free terms in the system of constraints of the original problem, and the right-hand sides in the constraints of the dual problem are the coefficients of the unknowns in the objective function of the original; j 0.

The two problems presented form a pair of symmetric dual problems. The main statements about mutually dual problems are contained in the following two theorems.

First duality theorem. For mutually dual problems, one of the mutually exclusive cases occurs.

1. In the direct and dual problems there are optimal solutions,
in this case, the values ​​of the objective functions on the optimal solutions
match

2. In the direct problem, the admissible set is not empty, and the objective function on this set is not bounded from above. In this case, the dual problem will have an empty admissible set.

3. In a dual problem, the admissible set is not empty, and the objective function on this set is not bounded from below. In this case, the admissible set of the direct problem turns out to be empty.

4. Both of the problems under consideration have empty admissible sets.

Second duality theorem (complementary non-rigidity theorem). Let = ( x 1 , x 2,..., x n) is an admissible solution to the direct problem, a = (y 1,y 2,...,y t) is an admissible solution to the dual problem. In order for them to be optimal solutions to the direct and dual problems, respectively, it is necessary and sufficient that the following relations hold:

Conditions (1.4) and (1.5) allow, knowing the optimal solution of one of the mutually dual problems, to find the optimal solution of another problem.

Let us consider another theorem, the conclusions of which will be used further.

Estimation theorem. The values ​​of the variables y i in the optimal solution of the dual problem represent estimates of the influence of the free terms b i of the system of constraints (inequalities) of the direct problem on the value

By solving the ZLP using the simplex method, we simultaneously solve the dual ZLP. The variables of the dual problem y i are called objectively determined estimates.

Let us consider the economic interpretation of the dual problem using the carpet problem as an example.

Example 1 .2. Using the statement of the carpet problem, complete the following tasks.

1. Formulate an economic-mathematical model of the problem of carpets for the maximum total cost of production, using the data in Table. 1.1.

2. Using the Search for a solution, find a production plan at which the total cost of production will be maximum.

3. Formulate an economic-mathematical model of the dual problem to the carpet problem.

4. Find the optimal plan for the dual problem, using duality theorems, explain the equality to zero of X 1 and X 4.

5. Using the Solution Search protocols, perform an analysis of the resulting optimal solution to the original problem.

6. Determine how the total cost and production plan will change when the pipe service life increases by 12 units.

1. Let us formulate an economic and mathematical model of the problem.

Let us denote by X 1, X 2, X 3, X 4 the number of carpets of each type. The objective function has the form

F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 max,

and resource limitations

7Х 1 + 2Х 2 + 2Х 3 + 6X 4 80,

5Х 1 + 8Х 2 + 4 X 3 + ZH 4 480,

2X 1 + 4 X 2 + X 3 + 8X 4 130,

X 1, X 2, X 3, X 4 0.

2. Search for the optimal release plan.

We will solve the problem using the Excel add-in Search for a solution. The technology for solving the problem was discussed in detail in the costume problem. In our problem, the optimal values ​​of the vector X = (X 1, X 2, X 3, X 4) will be placed in cells VZ:EZ, the optimal value of the objective function - in the cell F4.

Let's enter the initial data. First, we describe the target function using the function - SUMPRODUCT (Fig. 1.19). And then we will enter data for the left parts of the restrictions. In the Search for a solution, we will enter the direction of the objective function, the addresses of the sought variables, and add restrictions. The Search for Solution dialog box with the entered conditions will appear on the screen (Fig. 1.20).

After entering the parameters for solving the problem, click the Execute button. A message will appear on the screen that a solution has been found (Fig. 1.21).

The resulting solution means that the maximum income is 150 thousand rubles. a factory can receive 30 carpets of the second type and 10 carpets of the third type upon production. In this case, the resources “labor” and “equipment” will be fully used, and out of 480 kg of yarn (resource “raw materials”), 280 kg will be used.

Creating a report based on the results of searching for a solution. Excel allows you to present the results of the search for a solution in the form of a report (Table 1.4). There are three types of such reports:

· Results (Answer). The report includes the initial and final values ​​of the target and modified cells, and additional information about restrictions.

· Stability (Sensitivity). A report containing information about the sensitivity of a solution to small changes in the cells being modified or in the constraint formulas.

· Limits. In addition to the source and destination values ​​of the affected and target cells, the report includes upper and lower bounds on the values ​​that the influencing cells can accept if the constraints are met.

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

Each of the inequalities of the LP problem determines on the coordinate plane (X 1 ,X 2 ) some half-plane (Fig. 1), and the system of inequalities as a whole is the intersection of the corresponding planes. The set of intersection points of these half-planes is called area of ​​acceptablesolutions(ODR). ODR always represents 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 represented graphically by a convex polygon, an unlimited convex polygonal area, a segment, a ray, or one point. In the case of inconsistency of the system of constraints of the problem, the ODD is an empty set.

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

a il x 1 +a i 2 x 2 =b

can be represented as a system of two inequalities (Fig. 1)

A i 2 x 2<Ь 1э +a i 2 x 2 >bj.

DF L(x)= c1x1 + c2x2 with a fixed value L(x)=L defines a straight line c1x1 on the plane + c2x2 = L. By changing the values ​​of L, we get a family of parallel lines called level lines.

This is due to the fact that a change in the value of L will entail a change only in the length of the segment cut off by the level line on the x2 axis (initial ordinate), and the angular coefficient of the straight line tga = -- will remain constant (Fig. 1).

Therefore, to solve it, it will be enough to construct one of the level lines, arbitrarily choosing the value of L.

Vector C = (c1;c2) with coordinates from the CF coefficients at x1 and x2 is perpendicular to each of the level lines (see Fig. 1). Directionvector C coincides with direction increasing TF, which is an important point for solving problems. Direction descending CF oppositedirection of vector C.

The essence of the graphical method is as follows. In the direction (against the direction) of vector C in the ODR, the optimal point X = (x1; x2) is searched ). The optimal point is considered to be the point through which the level line L max (L min) passes, corresponding to the largest (smallest) value of the function L(x). 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 LP problems, the following situations are possible: there is a unique solution to the problem; there are an infinite number of solutions (alternative optium); TF is not limited; the region of feasible solutions is a single point; the problem has no solutions.

Admissible area - half-plane

Figure 1

1.2. Technique for solving LP problems using the graphical method

I. In the constraints of the problem, replace the inequality signs with exact equality signs and construct the corresponding straight lines.

II. Find and shade the half-planes allowed by each of the inequality constraints of the problem. To do this, 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, That it is necessary to shade the half-plane containing this point; otherwise (the inequality is false) we must shade the half-plane that does not contain the given point.

Since x1 and x2 must be non-negative, then their permissible values ​​will always be above the x-axis 1 and to the right of the x2 axis, i.e. in the 1st quadrant.

Equality constraints allow only those points that lie on the corresponding line, so highlight such lines on the graph.

Define the ODR as a part of the plane that simultaneously belongs to all allowed areas and select it. In the absence of ODR, the task Not has solutions, about which draw the appropriate conclusion.

If ODR is not an empty set, then construct the target line, i.e. any of the level lines c 1 x 1 + c 2 x 2 = L, where L is an arbitrary number, for example, a multiple of 1 and with 2, i.e. convenient for making calculations. The construction method is similar to the construction of direct constraints.

V. Construct a vector C = (c 1,c 2), which starts at the point (0;0) and ends at the point (c 1,c 2). If the target line and vector C are constructed correctly, then they will be perpendicular.

VI. When searching for max CF, move the target line in the direction vector C, when searching for min CF - against the direction vector C. Last in the direction of movement, the top of the ODR will be the max or min point of the CF. If such point(s) does not exist, then draw a conclusion about unlimited TF for many plans from above (when searching for check) or from below (when searching for min).

Determine the coordinates of the point max (min) TF X = (x1 *; x2 * ) and calculate the value of the CF l(x *). To calculate the coordinates of the optimal point X *, solve the system of equations of lines at the intersection of which X * is located.

Problem 1

Let us find the optimal solution to the problem, the mathematical model of which has the form

L(X) = 3x 1 + 2x 2 → max

x 1 + 2x 2< 6, (1)

2x 1 + x 2< 8, (2)

X 1 + x 2<1, (3)

x 2< 2, (4)

x 1 >0, x 2 >0.

Let's construct constraint lines, for which we calculate the coordinates of the points of intersection of these lines with the coordinate axes (Fig. 2).

x 1 + 2x 2 = 6,(1)

2x1 + x2= 8,(2)

(1) x1=0, x1=6, x2=3, x2=0,

(2) x1=0, x1=4, x2=8, x2=0,

(3) x1=0, x1=-1, x2=1, x2=0,

Straight line (4) passes through the point x 2 = 2 parallel to the L(X) axis.

Rice. 2. Graphical solution to the problem

Let's define ODR. For example, we substitute the point (0;0) into the original constraint (3), we get 0< 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, containing point (0;0), i.e. located to the right and below the straight line (3). We similarly define the admissible half-planes for the remaining restrictions and indicate them with arrows at the corresponding direct restrictions (Fig. 2). The general area allowed by all restrictions, i.e. ODR is a polygon ABCDEF.

The target line can be constructed using the equation

We construct vector C from point (0;0) to point (3;2). Point E is the last vertex of the polygon of feasible solutions ABCDEF, through which the target line passes, moving in the direction vector C. Therefore E is the point of maximum CF. Let us determine the coordinates of point E from the system of equations of direct constraints (1) and (2)

X1 +2x 2 =6, (1) x1=10/3=3 1/3, x2=4/3=1 1/3

2 X1 +x 2 =8, (2) E 3 1/3; 1 1/3

The maximum CF value is L(E) = 3*10/3+2*4/3 = 12 2 / 3