The optimal value of the objective function is called. Solving linear programming problems using the graphical method

Let us construct on the plane a set of feasible solutions to the system of linear inequalities and geometrically find the minimum value of the objective function.

We build straight lines in the x 1 x 2 coordinate system

We find the half-planes defined by the system. Since the inequalities of the system are satisfied for any point in the corresponding half-plane, it is enough to check them for any one point. We use the point (0;0). Let's substitute its coordinates into the first inequality of the system. Because , then the inequality defines a half-plane that does not contain the point (0;0). We similarly define the remaining half-planes. We find the set of feasible solutions as the common part of the resulting half-planes - this is the shaded area.

We construct a vector and a zero level line perpendicular to it.

Moving straight line (5) in the direction of the vector and we see that the maximum point of the region will be at point A of the intersection of straight line (3) and straight line (2). We find the solution to the system of equations:

This means we got the point (13;11) and.

Moving straight line (5) in the direction of the vector and we see that the minimum point of the region will be at point B of the intersection of straight line (1) and straight line (4). We find the solution to the system of equations:

This means we got the point (6;6) and.

2. A furniture company produces combined cabinets and computer tables. Their production is limited by the availability of raw materials (high-quality boards, fittings) and the operating time of the machines processing them. Each cabinet requires 5 m2 of boards, for a table - 2 m2. Fittings cost $10 for one cabinet, and $8 for one table. The company can receive from its suppliers up to 600 m2 of boards per month and accessories worth $2,000. Each cabinet requires 7 hours of machine operation, and the table requires 3 hours. A total of 840 machine operating hours can be used per month.

How many combination cabinets and computer tables should a company produce per month to maximize profits if one cabinet brings in $100 in profit and each desk brings in $50?

• 1. Compose mathematical model problem and solve it using the simplex method.
• 2. Create a mathematical model of the dual problem, write down its solution based on the solution to the original one.
• 3. Establish the degree of scarcity of the resources used and justify the profitability of the optimal plan.
• 4. Explore the possibilities of further increasing production output depending on the use of each type of resource.
• 5. Assess the feasibility of introducing a new type of product - bookshelves, if the manufacture of one shelf costs 1 m 2 of boards and accessories worth $5, and it is necessary to spend 0.25 hours of machine operation and the profit from the sale of one shelf is $20.
• 1. Let's build a mathematical model for this problem:

Let us denote by x 1 the volume of production of cabinets, and x 2 the volume of production of tables. Let's create a system of restrictions and a goal function:

We solve the problem using the simplex method. Let's write it in canonical form:

Let's write the task data in the form of a table:

Table 1

Because Now all deltas are greater than zero, then a further increase in the value of the goal function f is impossible and we have obtained an optimal plan.

CONTROL WORK ON DISCIPLINE:

“METHODS OF OPTIMAL SOLUTIONS”

Option No. 8

1. Decide graphical method linear programming problem. Find the maximum and minimum of the function with the given restrictions:

,

.

Solution

It is necessary to find the minimum value of the objective function and the maximum, under the system of restrictions:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

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).

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.

Let's construct a straight line corresponding to the value of the function F = 0: F = 2x 1 +3x 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 (2; 3). We will move this straight line in a parallel manner. Since we are interested in the minimal solution, we therefore move the straight line until it first touches the designated area. On the graph, this straight line is indicated by a dotted line.

Straight
intersects the region at point C. Since point C is obtained as a result of the intersection of lines (4) and (1), its coordinates satisfy the equations of these lines:
.

Having solved the system of equations, we get: x 1 = 3.3333, x 2 = 0.

How can we find the minimum value of the objective function: .

Let's consider target function tasks .

Let's construct a straight line corresponding to the value of the function F = 0: F = 2x 1 +3x 2 = 0. The gradient vector, composed of the coefficients of the objective function, indicates the direction of maximization of F(X). The beginning of the vector is point (0; 0), the end is point (2; 3). We will move this straight line in a parallel manner. Since we are interested in the maximum solution, we therefore move the straight line until the last touch of the designated area. On the graph, this straight line is indicated by a dotted line.

Straight
intersects the region at point B. Since point B is obtained as a result of the intersection of lines (2) and (3), its coordinates satisfy the equations of these lines:

.

How can we find the maximum value of the objective function: .

Answer:
And
.

2 . Solve a linear programming problem using the simplex method:

.

Solution

Let's solve a direct linear programming problem using the simplex method, using a simplex table.

Let's determine the minimum value of the objective function
under the following conditions-restrictions:
.

To construct the first reference plan, we reduce the system of inequalities to a system of equations by introducing additional variables.

In the 1st inequality of meaning (≥) we introduce the basic variable x 3 with a minus sign. In the 2nd inequality of meaning (≤) we introduce the basic variable x 4 . In the 3rd inequality of meaning (≤) we introduce the basic variable x 5 .

Let's introduce artificial variables : in the 1st equality we introduce a variable x 6 ;

To set the problem to a minimum, we write the objective function as follows: .

For the use of artificial variables introduced into the objective function, a so-called penalty of M is imposed, a very large positive number that is usually not specified.

The resulting basis is called artificial, and the solution method is called the artificial basis method.

Moreover, artificial variables are not related to the content of the problem, but they make it possible to construct a starting point, and the optimization process forces these variables to take zero values ​​and ensure the admissibility of the optimal solution.

From the equations we express artificial variables: x 6 = 4-x 1 -x 2 +x 3, which we substitute into the objective function: or.

Coefficient matrix
this system of equations has the form:
.

Let's solve the system of equations for the basic variables: x 6 , x 4 , x 5.

Assuming that the free variables are equal to 0, we obtain the first reference plan:

X1 = (0,0,0,2,10,4)

The basic solution is called admissible if it is non-negative.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

The current reference plan is not optimal because there are positive coefficients in the index line. As the leading column, we will choose the column corresponding to the variable x 2, since this is the largest coefficient. Let's calculate the values D i and from them we choose the smallest: min(4: 1, 2: 2, 10: 2) = 1.

Therefore, the 2nd line is the leading one.

The resolving element is equal to (2) and is located at the intersection of the leading column and the leading row.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

We form the next part of the simplex table. Instead of the variable x 4, plan 1 will include the variable x 2.

The row corresponding to the variable x 2 in plan 1 is obtained by dividing all elements of the row x 4 of plan 0 by the resolving element RE = 2. In place of the resolving element we get 1. In the remaining cells of the x 2 column we write zeros.

Thus, in the new plan 1, row x 2 and column x 2 are filled. All other elements of the new plan 1, including the elements of the index row, are determined by the rectangle rule.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

The current reference plan is not optimal because there are positive coefficients in the index row. As the leading column, we will choose the column corresponding to the variable x 1, since this is the largest coefficient. Let's calculate the values D i by row as a quotient of division: and from them we choose the smallest: min (3: 1 1 / 2, -, 8: 2) = 2.

Therefore, the 1st line is the leading one.

The resolving element is equal to (1 1/2) and is located at the intersection of the leading column and the leading row.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

We form the next part of the simplex table. Instead of the variable x 6, plan 2 will include the variable x 1.

We get a new simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

There are no positive values ​​among the index string values. Therefore, this table determines the optimal plan for the problem.

The final version of the simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Since there are no artificial variables in the optimal solution (they are equal to zero), this solution is admissible.

The optimal plan can be written as follows: x 1 = 2, x 2 = 2:.

Answer:
,
.

3. The Three Fat Men company delivers canned meat from three warehouses located in different parts of the city to three stores. Stocks of canned food available in warehouses, as well as volumes of store orders and delivery rates (in conventional monetary units) are presented in the transport table.

Find a transportation plan that provides the lowest monetary costs (perform the initial transportation plan using the “northwest corner” method).

Solution

Let us check the necessary and sufficient condition for the solvability of the problem:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

The balance condition is met. Supplies equal needs. Therefore, the model of the transport problem is closed.

Let's enter the initial data into the distribution table.

Needs

Using the northwest corner method, we will construct the first reference plan of the transport problem.

The plan begins to fill in from the upper left corner.

The required element is 4. For this element, inventories are 300, requirements are 250. Since the minimum is 250, we subtract it: .

			300 - 250 = 50
250 - 250 = 0

The required element is equal to 2. For this element, inventories are 50, requirements are 400. Since the minimum is 50, we subtract it: .

			50 - 50 = 0
	400 - 50 = 350

The required element is 5. For this element, inventories are 300, requirements are 350. Since the minimum is 300, we subtract it:

			300 - 300 = 0
	350 - 300 = 50

The required element is 3. For this element, inventories are 200, requirements are 50. Since the minimum is 50, we subtract it:

			200 - 50 = 150
	50 - 50 = 0

The required element is 6. For this element, inventories are 150, requirements are 150. Since the minimum is 150, we subtract it:

			150 - 150 = 0
		150 - 150 = 0

Needs

Laboratory work No. 1. Solving linear programming problems

Goal of the work Gaining skills in solving linear programming problems using graphical, simplex and Excel methods.

The problem of linear programming is to study ways to find the maximum or minimum values ​​of a linear function in the presence of linear constraints. An objective function is a function whose maximum or minimum value is found. The set of values ​​of variables at which the maximum or minimum values ​​are achieved is called an optimal solution (optimal plan), any other set of values ​​that satisfies the restrictions is called an admissible solution (admissible plan).

Geometric solution method I Let's look at linear programming problems using an example.

Example. Find the maximum value of the objective function L=2x 1 +2x 2 under given restrictions

Solution. Let us construct the solution domain of the system of constraints, changing the inequalities signs to exact equalities signs:

l 1: 3x 1 -2x 2 +6=0,

l 2: 3x 1 +x 2 -3=0,

l 3:x 1 -3=0.

DWITH

2 0 1 3 X 1

(l 1) (l 3)

Straight l 1 divides the plane X ABOUT at into two half-planes, from which you need to choose one that satisfies the first inequality in system (3). To do this, let's take t. ABOUT(0; 0) and substitute it into the inequality. If it is true, then you need to shade the half-plane from the straight line in which the so-called is located. ABOUT(0; 0). Do the same with straight lines. l 2 and l 3. The domain of solutions to inequalities (3) is a polygon ABCD. For each point on the plane the function L takes a fixed value L=L 1 . The set of all current points is a straight line L=c 1 x 1 +c 2 x 2 (in our case L=2x 1 +2x 2), perpendicular to the vector WITH(With 1 ;With 2) (WITH(2; 2)), coming from the origin. If this line is moved in the positive direction of the vector With, then the objective function L will increase, otherwise it will decrease. Thus, in our case, the straight line at the exit from the polygon ABCD decisions will go through the so-called IN(3; 7.5), and therefore incl. IN the objective function takes the maximum value, i.e. L max =2ּ3+2ּ7.5=21. Similarly, it is determined that the minimum value the function takes is D(1; 0) and L min =2ּ1+2ּ0=2.

The algorithm of the simplex method for solving a linear programming problem is as follows.

1. General task Linear programming is reduced to a canonical problem (constraints contain equal signs) by introducing as many auxiliary variables as there are inequalities in the system of constraints.

2. The goal function is expressed through basic and auxiliary variables.

3. The first simplex table is compiled. The variables in relation to which the system of restrictions is allowed are written into the basis (it is best to take auxiliary variables as the basis ones). The first row of the table lists all the variables and provides a column for free terms. The coefficients of the goal function with opposite signs are written in the last row of the table

4. Each simplex table gives a solution to a linear programming problem: free variables are equal to zero, basic variables are equal to free terms, respectively.

5. The optimality criterion is the absence of negative elements in the last row of the table for solving the maximum problem and positive elements for the minimum.

6. To improve the solution, it is necessary to move from one simplex table to another. To do this, find a key column in the previous table that corresponds to the smallest negative element in the last row of the table in the maximum problem and the largest positive coefficient in the minimum problem. Then a key row is found corresponding to the minimum ratio of free terms to the corresponding positive elements of the key column. At the intersection of a key column and a key row is the key element.

7. We begin filling out the following simplex table by filling out the basis: the variable corresponding to the key row is derived from the basis, and the variable corresponding to the key column is entered in its place. The elements of the former key string are obtained by dividing the former element by the key one. The elements of the former key column become zeros, except for the key element, which is one. All other elements are calculated using the rectangle rule:

8. Transformation of simplex tables is carried out until an optimal plan is obtained.

Example. Find the maximum value of a function
, if variables
satisfy the system of restrictions:

Solution. 1. Introduce new variables
, with the help of which we transform the inequalities of the system into equations:

We change the sign of the coefficients of the objective function or write it in the form
. We fill out the first simplex table, in the zero line we write X 1 ,X 2 and (free odds). In the zero column - X 3 ,X 4 ,X 5 and F. We fill out this table using the resulting system of equations and the transformed objective function.

We check the optimality criterion to find the maximum value: in the last line, all coefficients must be positive. This criterion is not met, so we proceed to compiling the second table.

2. Find the resolving element of the first table as follows. Among the elements of the last row, we select the largest negative coefficient in magnitude (this is -3) and take the second column as resolving. If all the coefficients of the column are non-positive, then
.

To determine the resolving row, we divide the free coefficients into the corresponding elements of the resolving column and select the minimum ratio, while we do not take negative coefficients. We have
, the second line is permissive. The intersection of the resolving row and column gives the resolving element - this is 3.

3. Fill in the second simplex table. The variables at the intersection of which we obtain a resolving element are swapped, i.e. And . We replace the resolving element with its inverse, i.e. on the. The elements of the resolving row and column (except for the resolving element) are divided into the resolving element. In this case, we change the sign of the coefficients of the resolution column.

The remaining elements of the second table are obtained using the rectangle rule from the elements of the first table. For the cell to be filled and the cell with the resolving element, we make a rectangle. Then, from the element for the cell to be filled, we subtract the product of the elements of the other two vertices, divided by the resolving element. Let's show the calculations using this rule to fill out the first row of the second table:

.

We continue filling out the tables according to these rules until the criterion is met. We have two more tables for our task.

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

4. The result of executing this algorithm is written as follows. In the final table, the element at the intersection of the row
and column b, gives the maximum value of the objective function. In our case
. The values ​​of the row variables are equal to the free coefficients. For our problem we have
.

There are other ways to compile and fill out simplex tables. For example, for stage 1, all variables and free coefficients are recorded in the zero line of the table. After finding the resolving element using the same rules in the following table, we replace the variable in the zero column, but not in the row. We divide all elements of the allowing line by the allowing element and write them in a new table. For the remaining elements of the resolution column we write zeros. Next, we perform the specified algorithm taking into account these rules.

When solving a linear programming problem for a minimum, the largest positive coefficient is selected in the last line, and the specified algorithm is performed until there are no positive coefficients in the last line.

Solving linear programming problems using Excel is carried out as follows.

To solve linear programming problems, use the Solution Search add-in. First you need to make sure that this add-in is present on the Data tab in the Analysis group (for 2003, see Tools). If the Find a Solution command or the Analysis group is missing, you must download this add-in.

To do this, click Microsoft Office File (2010), then click the Excel Options button. In the Excel Options window that appears, select the Add-ins box on the left. On the right side of the window, the value of the Control field should be set to Excel Add-ins, click the “Go” button, which is located next to this field. In the Add-Ins window, select the checkbox next to Find a solution and click OK. Then you can work with the installed Search for Solutions add-on.

Before calling Search for a Solution, you need to prepare data for solving a linear programming problem (from a mathematical model) on a worksheet:

1) Determine the cells in which the result of the solution will be placed for this; in the first line we enter the variables and the objective function. We do not fill in the second line (changeable cells) in these cells the optimal result will be obtained. Enter the data for the objective function in the next line, and the system of restrictions (coefficients for unknowns) in the next lines. Right side restrictions (free coefficients) are introduced, leaving a free cell after recording the coefficients of the system of restrictions.

2) Introduce a dependence on variable cells for the objective function and a dependence on variable cells for the left parts of the constraint system in the remaining free cells. To introduce dependency formulas, it is convenient to use the mathematical function SUMPRODUCT.

Next, you need to use the Search for a solution add-on. On the Data tab, in the Analysis group, select Find a Solution. The Search for Solution dialog box will appear, which must be completed as follows:

1) Specify the cell containing the objective function in the “Optimize objective function” field (this cell must contain the formula for the objective function). Select the option for optimizing the value of the target cell (maximization, minimization):

2) In the “Changing variable cells” field, enter the cells to change. In the next field “In accordance with restrictions”, enter the specified restrictions using the “Add” button. In the window that appears, enter the cells containing the formulas of the constraint system, select the constraint sign and the constraint value (free coefficient):

3) Check the “Make unconstrained variables non-negative” checkbox. Select the solution method “Searching for solutions to linear problems using the simplex method.” After clicking the “Find solution” button, the process of solving the problem starts. As a result, the “Solution Search Results” dialog box and the original table with filled cells for variable values ​​and the optimal value of the objective function appear.

Example. Solve a linear programming problem using the Excel Solution Add-in: find the maximum value of a function
under restrictions

,

;

,
.

Solution. To solve our problem, let’s execute the specified algorithm on an Excel worksheet. Enter the initial data in the form of a table

We introduce dependencies for the objective function and the system of restrictions. To do this, enter the formula =SUMPRODUCT(A2:B2;A3:B3) in cell C2. In cells C4 and C5, respectively, the formulas are: =SUMPRODUCT(A2:B2,A4:B4) and =SUMPRODUCT(A2:B2,A5:B5). As a result, we get a table.

Run the “Search for a solution” command and fill out the Search for a solution window that appears as follows. In the “Optimize objective function” field, enter cell C2. Select optimization of the target cell value “Maximum”.

In the “Changing variable cells” field, enter the changing cells A2:B2. In the “In accordance with restrictions” field, enter the specified restrictions using the “Add” button. References to cell $C$4:$C$5 References to restrictions =$D$4:$D$5 between them sign<= затем кнопку «ОК».

Check the “Make unconstrained variables non-negative” checkbox. Select the solution method “Searching for solutions to linear problems using the simplex method.”

Clicking the “Find solution” button starts the process of solving the problem. As a result, the “Solution Search Results” dialog box and the original table with filled cells for variable values ​​and the optimal value of the objective function appear.

In the “Solution Search Results” dialog box, save the result x1=0.75, x2=0.75, F=1.5 - equal to the maximum value of the objective function.

Tasks for independent work

Exercise 1. Using graphical, simplex methods and Excel tools, find the maximum and minimum value of a function F(x) under a given system of restrictions.

1. F(x)=10x 1 +5x 2 2. F(x)=3x 1 -2x 2

3. F(x)=3x 1 +5x 2 4. F(x)=3x 1 +3x 2

5. F(x)=4x 1 -3x 2 6. F(x)=2x 1 -x 2

7. F(x)=-2x 1 +4x 2 8. F(x)=4x 1 -3x 2

9. F(x)=5x 1 +10x 2 10. F(x)=2x 1 +x 2

11. F(x)=x 1 +x 2 12. F(x)=3x 1 +x 2

13. F(x)=4x 1 +5x 2 14. F(x)=3x 1 +2x 2

15. F(x)=-x 1 -x 2 16. F(x)=-3x 1 -5x 2

17. F(x)=2x 1 +3x 2 18. F(x)=4x 1 +3x 2

19. F(x)=-3x 1 -2x 2 20. F(x)=-3x 1 +4x 2

21. F(x)=5x 1 -2x 2 22. F(x)=-2x 1 +3x 3

23. F(x)=2x 1 +3x 2 24. F(x)=4x 1 +3x 2

25. F(x)=-3x 1 -2x 2 26. F(x)=-3x 1 +4x 2

27. F(x)=-2x 1 +4x 2 28. F(x)=4x 1 -3x 2

29. F(x)=-x 1 -x 2 30. F(x)=-3x 1 -5x 2

Control questions.

1. What problems are called linear programming problems?

2. Give examples of linear programming problems.

3. How is a linear programming problem solved using the graphical method?

4. Describe the algorithm of the simplex method for solving linear programming problems.

5. Describe an algorithm for solving linear programming problems using Excel.

Federal Agency for Education

State budgetary educational institution

higher professional education

"Omsk State Technical University"

CALCULATION AND GRAPHIC WORK

by discipline "OPTIMAL CONTROL THEORY »

on the topic "OPTIMIZATION METHODS AND OPERATIONS RESEARCH »

option 7

Completed:

correspondence student

4th year group ZA-419

Full name: Kuzhelev S. A.

Checked:

Devyaterikova M. V.

Omsk – 2012
^

Task 1. Graphical method for solving linear programming problems.

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Step 1: Constructing the Feasible Region

The conditions for non-negativity of variables and squares limit the range of their permissible values ​​to the first quadrant. Each of the remaining four inequality constraints of the model corresponds to a certain half-plane. The intersection of these half-planes with the first quadrant forms the set of feasible solutions to the problem.

The first constraint of the model has the form . Replacing the ≤ sign in it with the = sign, we obtain the equation . In Fig. 1.1 it defines a straight line (1), which divides the plane into two half-planes, in this case above the line and below it. To choose which one satisfies the inequality , substitute into it the coordinates of any point not lying on a given line (for example, the origin X 1 = 0, X 2 = 0). Since we obtain the correct expression (20 0 + 6 0 = 0 ≤15), then the half-plane containing the origin of coordinates (marked with an arrow) satisfies the inequality. Otherwise, another half-plane.

We proceed similarly with the remaining constraints of the problem. The intersection of all constructed half-planes with the first quadrant forms ABCD(see Fig. 1). This is the feasible area of ​​the problem.

Step 2. Drawing a level line Level line The objective function is the set of points in the plane at which the objective function takes a constant value. Such a set is given by the equation f ( x) = const. Let's put, for example, const = 0 and draw a line at the level f ( x) = 0, i.e. in our case straight line 7 x 1 + 6x 2 = 0.

This line passes through the origin and is perpendicular to the vector. This vector is the gradient of the objective function at the point (0,0). The gradient of a function is a vector of values ​​of the partial derivatives of a given function at the point in question. In the case of the LP problem, the partial derivatives of the objective function are equal to the coefficients Ci, j = 1 , ..., n.

The gradient shows the direction of the fastest growth of the function. Moving the objective function level line f ( x) = const. perpendicular to the direction of the gradient, we find the last point at which it intersects with the region. In our case, this is point D, which will be the maximum point of the objective function (see Fig. 2)

It lies at the intersection of lines (2) and (3) (see Fig. 1) and specifies the optimal solution.

^ Note that if you want to find the minimum value of the objective function, the level line is moved in the direction opposite to the direction of the gradient.

^ Step 3. Determining the coordinates of the maximum (minimum) point and the optimal value of the objective function

To find the coordinates of point C, it is necessary to solve a system consisting of equations corresponding to straight lines (in this case, equations 2 and 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

We get the optimal solution = 1.33.

^ Optimal value of the objective function f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8