Calculation of the maximum and minimum of the objective function using the graphic-analytical method. Determination of the optimal parametric range of products to meet a given demand
If there is only one limiting factor (for example, a scarce machine), the solution can be found using simple formulas (see the link at the beginning of the article). If there are several limiting factors, the linear programming method is used.
Linear programming is the name given to a combination of tools used in management science. This method solves the problem of allocating scarce resources among competing activities in order to maximize or minimize certain numerical values, such as contribution margin or expenses. In business, it can be used in areas such as planning production to maximize profits, selecting components to minimize costs, selecting a portfolio of investments to maximize returns, optimizing the transport of goods to reduce distances, assigning personnel to maximize work efficiency, and scheduling work in to save time.
Download the note in the format, pictures in the format
Linear programming involves constructing a mathematical model of the problem under consideration. After which the solution can be found graphically (discussed below), with using Excel(will be considered separately) or specialized computer programs.
Perhaps the construction of a mathematical model is the most difficult part of linear programming, requiring the translation of the problem under consideration into a system of variables, equations and inequalities - a process that ultimately depends on the skills, experience, abilities and intuition of the modeler.
Let's consider an example of constructing a mathematical model of linear programming
Nikolai Kuznetsov runs a small mechanical plant. Next month, he plans to produce two products (A and B), for which the specific marginal profit is estimated at 2,500 and 3,500 rubles, respectively.
Both products require machining, raw materials, and labor costs to make (Figure 1). Each unit of product A requires 3 hours of machining, 16 units of raw materials, and 6 units of labor to produce. The corresponding unit requirements for Product B are 10, 4, and 6. Nicholas predicts that next month he can supply 330 hours of machining, 400 units of raw materials, and 240 units of labor. The technology of the production process is such that at least 12 units of product B must be produced in any given month.
Rice. 1. Use and provision of resources
Nikolai wants to build a model to determine the number of units of products A and B that he must produce in the next month to maximize his contribution margin.
The linear model can be built in four stages.
Step 1: Defining Variables
There is a target variable (let's call it Z) that needs to be optimized, that is, maximized or minimized (for example, profit, revenue or expenses). Nikolay seeks to maximize contribution margin, hence the target variable:
Z = total marginal profit (in rubles) received in the next month as a result of the production of products A and B.
There are a number of unknown unknown variables (let’s denote them x 1, x 2, x 3, etc.), whose values must be determined to obtain the optimal value of the objective function, which, in our case, is the total marginal profit. This contribution margin depends on the quantities of products A and B produced. The values of these quantities need to be calculated, and therefore they represent the desired variables in the model. So, let's denote:
x 1 = number of units of product A produced in the next month.
x 2 = number of units of product B produced in the next month.
It is very important to clearly define all variables; Special attention Pay attention to the units of measurement and the time period to which the variables refer.
Stage. 2. Construction of the objective function
An objective function is a linear equation that must be either maximized or minimized. It contains the target variable expressed using the target variables, that is, Z expressed in terms of x 1, x 2 ... in the form of a linear equation.
In our example, each manufactured product A brings 2,500 rubles. marginal profit, and when producing x 1 units of product A, the marginal profit will be 2500 * x 1. Similarly, the marginal profit from producing x 2 units of product B will be 3500 * x 2. Thus, the total marginal profit received in the next month by producing x 1 units of product A and x 2 units of product B, that is, the target variable Z will be:
Z = 2500 * x 1 + 3500 * x 2
Nikolay strives to maximize this indicator. Thus, the objective function in our model is:
Maximize Z = 2500 * x 1 + 3500 * x 2
Stage. 3. Define constraints
Constraints are a system linear equations and/or inequalities that limit the values of the sought variables. They mathematically reflect the availability of resources, technological factors, marketing conditions and other requirements. Constraints can be of three types: “less than or equal”, “greater than or equal”, “strictly equal”.
In our example, producing products A and B requires machining time, raw materials, and labor, and the availability of these resources is limited. The production volumes of these two products (that is, the values of x 1 x 2) will therefore be limited by the fact that the amount of resources needed in the production process cannot exceed those available. Let's consider the situation with machine processing time. The production of each unit of product A requires three hours of machining, and if x 1 units are produced, then 3 * x 1 hours of this resource will be spent. Each unit of product B requires 10 hours to produce and therefore if x 2 products are produced, then 10 * x 2 hours will be required. Thus, the total amount of machine time required to produce x 1 units of product A and x 2 units of product B is 3 * x 1 + 10 * x 2 . This general meaning machine time cannot exceed 330 hours. Mathematically this is written as follows:
3 * x 1 + 10 * x 2 ≤ 330
Similar considerations apply to raw materials and labor, which allows us to write down two more restrictions:
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Finally, it should be noted that there is a condition according to which at least 12 units of product B must be produced:
Stage 4. Writing non-negativity conditions
The required variables cannot be negative numbers, which must be written in the form of inequalities x 1 ≥ 0 and x 2 ≥ 0. In our example, the second condition is redundant, since it was determined above that x 2 cannot be less than 12.
The complete linear programming model for Nikolai's production problem can be written as:
Maximize: Z = 2500 * x 1 + 3500 * x 2
Provided that: 3 * x 1 + 10 * x 2 ≤ 330
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Let's consider a graphical method for solving a linear programming problem.
This method is only suitable for problems with two unknown variables. The model constructed above will be used to demonstrate the method.
The axes on the graph represent the two variables of interest (Figure 2). It doesn't matter which variable is plotted along which axis. It is important to choose a scale that will ultimately allow you to create a clear diagram. Since both variables must be non-negative, only the 1st quadrant is drawn.
Rice. 2. Linear programming graph axes
Consider, for example, the first constraint: 3 * x 1 + 10 * x 2 ≤ 330. This inequality describes the area below the line: 3 * x 1 + 10 * x 2 = 330. This line intersects the x 1 axis at x 2 = 0, that is, the equation looks like this: 3 * x 1 + 10 * 0 = 330, and its solution: x 1 = 330 / 3 = 110
Similarly, we calculate the intersection points with the x1 and x2 axes for all constraint conditions:
| Range of acceptable values | Limit of acceptable values | Intersection with x-axis 1 | Intersection with x-axis 2 |
| 3 * x 1 + 10 * x 2 ≤ 330 | 3 * x 1 + 10 * x 2 = 330 | x 1 = 110; x 2 = 0 | x 1 = 0; x 2 = 33 |
| 16 * x 1 + 4 * x 2 ≤ 400 | 16 * x 1 + 4 * x 2 = 400 | x 1 = 25; x 2 = 0 | x 1 = 0; x 2 = 100 |
| 6 * x 1 + 6 * x 2 ≤ 240 | 6 * x 1 + 6 * x 2 = 240 | x 1 = 40; x 2 = 0 | x 1 = 0; x 2 = 40 |
| x 2 ≥ 12 | x 2 = 12 | does not cross; runs parallel to the x axis 1 | x 1 = 0; x 2 = 12 |
Graphically, the first limitation is shown in Fig. 3.
Rice. 3. Construction of the region of feasible solutions for the first constraint
Any point within the selected triangle or on its boundaries will meet this constraint. Such points are called valid, and points outside the triangle are called invalid.
We similarly display the remaining restrictions on the graph (Fig. 4). Values of x 1 and x 2 on or inside the shaded region ABCDE will satisfy all model constraints. This region is called the region of feasible solutions.
Rice. 4. Region of feasible solutions for the model as a whole
Now, in the region of feasible solutions, it is necessary to determine the values x 1 and x 2 that maximize Z. To do this, in the objective function equation:
Z = 2500 * x 1 + 3500 * x 2
divide (or multiply) the coefficients before x 1 and x 2 by the same number, so that the resulting values fall within the range reflected on the graph; in our case, this range is from 0 to 120; so the odds can be divided by 100 (or 50):
Z = 25x 1 + 35x 2
then assign Z a value equal to the product of the coefficients before x 1 and x 2 (25 * 35 = 875):
875 = 25x 1 + 35x 2
and finally, find the points of intersection of the line with the x 1 and x 2 axes:
Let's plot this target equation on a graph similar to the constraints (Fig. 5):
Rice. 5. Applying the objective function (black dotted line) to the region of feasible solutions
The Z value is constant throughout the objective function line. To find the values x 1 and x 2 that maximize Z, you need to parallelly move the line of the objective function to a point within the boundaries of the region of feasible solutions, which is located at the maximum distance from the original line of the objective function up and to the right, that is, to point C (Fig. 6).
Rice. 6. The line of the objective function has reached a maximum within the region of feasible solutions (at point C)
We can conclude that the optimal solution will be located at one of the extreme points of the decision area. Which one will depend on the slope of the objective function and on what problem we are solving: maximization or minimization. Thus, it is not necessary to draw target function– all that is necessary is to determine the values of x 1 and x 2 at each of the extreme points by reading from the diagram or by solving the appropriate pair of equations. The found values of x 1 and x 2 are then substituted into the objective function to calculate the corresponding value of Z. The optimal solution is the one that obtains the maximum value of Z when solving the maximization problem, and the minimum when solving the minimization problem.
Let us determine, for example, the values of x 1 and x 2 at point C. Note that point C is located at the intersection of the lines: 3x 1 + 10x 2 = 330 and 6x 1 + 6x 2 = 240. Solving this system of equations gives: x 1 = 10, x 2 = 30. The calculation results for all vertices of the region of feasible solutions are given in the table:
| Dot | Value x 1 | Value x 2 | Z = 2500x 1 + 3500x 2 |
| A | 22 | 12 | 97 000 |
| IN | 20 | 20 | 120 000 |
| WITH | 10 | 30 | 130 000 |
| D | 0 | 33 | 115 500 |
| E | 0 | 12 | 42 000 |
Thus, Nikolai Kuznets must plan for the next month the production of 10 products A and 30 products B, which will allow him to receive a marginal profit of 130 thousand rubles.
Briefly, the essence of the graphical method for solving linear programming problems can be stated as follows:
- Draw two axes on the graph, representing the two parameters of the solution; draw only the 1st quadrant.
- Determine the coordinates of the points of intersection of all boundary conditions with the axes, substituting alternately the values x 1 = 0 and x 2 = 0 into the equations of the boundary conditions.
- Plot the model's constraint lines on the graph.
- Determine the region on the graph (called the feasible decision region) that meets all of the constraints. If there is no such region, then the model has no solution.
- Determine the values of the target variables at the extreme points of the decision area, and in each case calculate the corresponding value of the target variable Z.
- For maximization problems, the solution is the point at which Z is maximum; for minimization problems, the solution is the point at which Z is minimum.
Tests for current knowledge control
1. Any economic and mathematical model of a linear programming problem consists of:
A. objective function and system of restrictions
B.objective function, system of restrictions and conditions for non-negativity of variables
C. systems of restrictions and conditions for non-negativity of variables
D. objective function and conditions for non-negativity of variables
A.objective function
B. system of equations
C. system of inequalities
D. condition of non-negativity of variables
3. The optimal solution to a mathematical programming problem is
A. admissible solution to the system of constraints
B. any solution to a system of constraints
C.an acceptable solution to a system of constraints leading to a maximum or minimum of the objective function
D. maximum or minimum solution to a system of constraints
4. A system of restrictions is called standard if it contains
A. all signs
B.all signs
C. all signs
D. all signs
5. The linear programming problem is solved graphically if in the problem
A. one variable
B.two variables
C. three variables
D. four variables
6. Inequality of the form 
describes
B. circle
C.half-plane
D. plane
7. The maximum or minimum of the objective function is found
A. at the origin
B. on the sides of a convex polygon of solutions
C. inside a convex solution polygon
D.at the vertices of a convex solution polygon
8. The canonical type of PLP is the type in which the system of restrictions contains signs
A. all signs
B. all signs
C.all signs
D. all signs
9. If the constraint is specified with the “>=” sign, then an additional variable is introduced into this constraint with a coefficient
B.-1
10. Additional variables are introduced into the objective function with coefficients
C.0
A.the amount of resource number i required to produce 1 unit of product of the jth type
B. unused resources of the i -th type
C. profit from the sale of 1 unit of product of the jth type
D. quantity of products of type j
12. The resolving column when solving the LLP for max of the objective function is selected based on the condition
A.the largest positive value of the coefficient Cj of the objective function
B. the smallest positive value of the coefficient Cj of the objective function
C. the largest negative value of the coefficient Cj of the objective function
D. any column of coefficients for unknowns
13. The value of the objective function in the table with the optimal plan is
A. at the intersection of the row of coefficients of the objective function with the column of coefficients for x1
B.at the intersection of the row of coefficients of the objective function with column b
C. in the column of coefficients for xn
D. at the intersection of the row of coefficients of the objective function with the column of the original basis
14. Artificial variables are introduced into the system of restrictions in canonical form with a coefficient
A.1
15. The optimality of the plan in the simplex table is determined
A. by column b
B.by row of objective function values
C. by resolution line
D. by resolution column
16. Given a linear programming problem
B.1
17. Given a linear programming problem
The number of artificial variables for this problem is
C.2
18. If the original ZLP has the form
then the constraints of the dual problem
A. look like
B.look like
C. look like 
D. look like 
19. If the original ZLP has the form
A. look like
B. look like
C. look like
D.look like
20. The coefficients of the unknowns of the objective function of the dual problem are
A. coefficients for the unknown objective function of the original problem
B.free terms of the system of constraints of the original problem
C. unknowns of the original problem
D. coefficients for unknown system constraints of the original problem
21. If the original ZLP was at the maximum of the objective function, then the dual problem will be
A. also to the maximum
B. either to the maximum or to the minimum
C. both maximum and minimum
D.to a minimum
22. The connection between the original and dual problems is that
A. both problems must be solved
B.the solution to one of them is obtained from the solution to the other
C. from the solution of the dual problem it is impossible to obtain solutions to the original one
D. both have the same solutions
23. If the original ZLP has the form
then the objective function of the dual problem is
A. look like
B. look like
C.look like
D. look like
24. If the original ZLP has the form
then the number of variables in the dual problem is equal to
B.2
25. Closed model of the transport problem,
A.If
26. The cycle in the transport problem is
A. a closed rectangular polyline, all of whose vertices are in occupied cells
B. a closed rectangular polyline, all vertices of which are located in free cells
C. a closed rectangular broken line, one vertex of which is in an occupied cell, the rest in free cells
D. a closed rectangular broken line, one vertex of which is in a free cell, and the rest are in occupied cells
27. Potentials of a transport problem of dimension (m*n) are m+n numbers ui and vj for which the conditions are met
A.ui+vj=cij for occupied cells
B. ui+vj=cij for free cells
C. ui+vj=cij for the first two columns of the distribution table
D. ui+vj=cij for the first two rows of the distribution table
28. Estimates of a transport problem of dimension (m+n) are the numbers
yij=cij-ui-vj, which are calculated
A. for occupied cells
B.for free cells
C. for the first two rows of the distribution table
D. for the first two columns of the distribution table
29. When solving a transport problem, the value of the objective function must, from iteration to iteration
A. increase
B. increase or remain unchanged
C. increase by the amount of any estimate.
D.decrease or remain unchanged
30. The number of occupied cells of a non-degenerate plan of a transport problem must be equal to
C.m+n-1
31. Economic sense objective function of the transport problem
A. total traffic volume
B.total cost of transportation
C. total supplies
D. total 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. The general linear programming problem is reduced to the canonical problem (the constraints contain equal signs) by introducing as many auxiliary variables as the number of inequalities the system of constraints contains.
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 in 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 written 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-on. 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 and 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 appears and the initial table with filled cells for variable values and the optimal value of the objective function.
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 constraints. 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 appears and the initial table with filled cells for variable values and the optimal value of the objective function.
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 to solve a linear programming problem 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.
Find the maximum of the objective function using a graphical method
F= 2x 1 + 3x 2 ® max
With restrictions
Solution using Excel tables
First, let's construct a solution to the system of inequalities on an Excel sheet.
Let's consider the first inequality.
Let's construct a boundary line using two points. We denote the straight line (L1) (or Row1). Coordinates X 2 we calculate using the formulas:
To construct, select a scatter plot
Selecting data for direct
Change the name of the line:
Selecting a chart layout. Change the name of the coordinate axes:
Straight line (L1) on the graph:
The solution to the strict inequality can be found using a single test point that does not belong to the line (L1). For example, using the point (0; 0)П(L1).
0 + 3×0< 18 или 0 < 18 .
The inequality is true, therefore the solution to inequality (1) will be the half-plane in which the trial point is located (in the figure below, line L1).
Then we solve inequality (2).
Let's construct boundary line 2 using two points. We denote the straight line by (L2).
Straight line (L2) on the graph:
The solution to strict inequality 2 can be found using a single test point that does not belong to the line (L2). For example, using the point (0; 0)П(L2).
When substituting the coordinates of the point (0; 0), we obtain the inequality
2×0 + 0< 16 или 0 < 16 .
The inequality is true, therefore the solution to inequality (2) will be the half-plane in which the trial point is located (in the figure below line L2).
Then we solve inequality (3).
Let's construct a boundary line using two points. We denote the straight line (L3).
Straight line (L3) on the graph:
The solution to strict inequality 2 can be found using a single test point that does not belong to the line (L3). For example, using the point (0; 0)П(L3).
When substituting the coordinates of the point (0; 0), we obtain the inequality
The inequality is true, therefore the solution to inequality (3) will be the half-plane in which the trial point is located (in the figure below line L3).
Then we solve inequality (4).
Let's construct a boundary line using two points. We denote the straight line (L4).
Add data to an Excel sheet
Straight line (L4) on the graph:
Solving strict inequality 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).
When substituting the coordinates of the point (0; 0), we obtain the inequality
The inequality is true, therefore, the solution to inequality (4) will be the half-plane in which the trial point is located (in the figure to the left of line L4).
By solving two inequalities (5) and (6)
is the 1st quarter, bounded by the coordinate lines and .
The system of inequalities has been resolved. The solution to the system of inequalities (1) – (6) in this example is the convex polygon in the lower left corner of the figure, bounded by the lines L1, L2, L3, L4 and the coordinate lines and . You can make sure that the polygon is chosen correctly by substituting a test point, for example (1; 1), into each inequality of the original system. When substituting the point (1; 1), we find that all inequalities, including natural restrictions, are true.
Let us now consider the objective function
F= 2x 1 + 3x 2 .
Let's construct level lines for the function values F=0 And F=12(numeric values are chosen arbitrarily). Add data to an Excel sheet
Level lines on the chart:
Let's construct a direction vector (or gradient) (2; 3). The vector coordinates coincide with the coefficients of the objective function F.
