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

We build in the coordinate system x 1 oh 2 lines

We find the half-planes determined by the system. Since the inequalities of the system are satisfied for any point from the corresponding half-plane, it suffices to check them for any one point. We use the point (0;0). Let us 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). Similarly, we define the remaining half-planes. We find the set of feasible solutions as a common part of the obtained half-planes - this is the shaded area.

We build a vector and a line of zero level perpendicular to it.

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

So, we got the point (13;11) and.

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

So, 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 that process them. Each cabinet requires 5 m2 of boards, for a table - 2 m2. Fittings for $10 are spent on one cabinet, and $8 on one table. The company can receive from its suppliers up to 600 m2 of boards per month and accessories for $2000. For each cabinet, 7 hours of machine work are required, for a table - 3 hours. It is possible to use only 840 hours of machine operation per month.

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

• 1. Compose a mathematical model of the problem and solve it using the simplex method.
• 2. Compose a mathematical model of the dual problem, write down its solution based on the solution of the original one.
• 3. Determine the degree of scarcity of the resources used and justify the profitability of the optimal plan.
• 4. Explore the possibilities of further increasing 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 takes 1 m 2 of boards and accessories for $ 5, and it takes 0.25 hours of machine work and the profit from the sale of one shelf is $ 20.
• 1. Let's build a mathematical model for this problem:

Denote by x 1 - the volume of production of cabinets, and x 2 - the volume of production of tables. Let us compose a system of constraints 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 everything is delta Above zero, then a further increase in the value of the goal function f is impossible and we have obtained an optimal plan.

If there is only one limiting factor (for example, a scarce machine), a solution can be found using simple formulas(see 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 some numerical value, such as marginal gains or costs. In business, it can be used in areas such as production planning to maximize profits, selection of components to minimize costs, investment portfolio selection to maximize profitability, optimization of goods transportation to reduce distances, staff allocation to maximize work efficiency, and scheduling work in in order to save time.

Download note in , drawings in format

Linear programming involves the construction of a mathematical model of the problem under consideration. After that, the solution can be found graphically (discussed below), with using Excel(to be considered separately) or specialized computer programs.

Perhaps the construction of a mathematical model is the most hard part linear programming, which requires 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 compiler of the model.

Consider an example of constructing a mathematical model of linear programming

Nikolai Kuznetsov manages 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.

The manufacture of both products requires the cost of machining, raw materials and labor (Fig. 1). For the manufacture of each unit of product A, 3 hours of machine processing, 16 units of raw materials and 6 units of labor are allotted. The corresponding requirements for unit B are 10, 4, and 6. Nikolai predicts that next month he can provide 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

Nikolay wants to build a model in order to determine the number of units of products A and B that he is supposed to produce in the next month to maximize marginal profit.

The linear model can be built in four steps.

Stage 1. Definition of variables

There is a target variable (let's denote it Z) that needs to be optimized, that is, maximized or minimized (for example, profit, revenue or expenses). Nikolay seeks to maximize marginal profit, therefore, the target variable is:

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 in order to obtain the optimal value of the objective function, which, in our case, is the total marginal profit. This contribution margin depends on the quantity of products A and B produced. The values ​​of these quantities must be calculated, and therefore they are the desired variables in the model. So let's denote:

x 1 = the 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 in terms of the desired variables, ie Z expressed in terms of x 1 , x 2 ... as a linear equation.

In our example, each manufactured product A brings 2500 rubles. marginal profit, and in the manufacture of x 1 units of product A, the marginal profit will be 2500 * x 1. Similarly, the marginal profit from manufacturing x 2 units of product B will be 3500 * x 2. Thus, the total marginal profit received in the next month due to the production of 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 seeks to maximize this indicator. Thus, the objective function in our model is:

Maximize Z = 2500 * x 1 + 3500 * x 2

Stage. 3. Definition of restrictions

Constraints are a system linear equations and/or inequalities that limit the magnitudes of the required 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, products A and B require processing time, raw materials, and labor to produce, and the availability of these resources is limited. The production volumes of these two products (i.e. the values ​​x 1 of 2) will thus be limited by the fact that the amount of resources required in the production process cannot exceed what is available. Consider the situation with machine processing time. The production of each unit of product A requires three hours of machine processing, and if x 1 units are produced, then 3 * x 1 hours of this resource will be spent. Production of each unit of product B requires 10 hours 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 is 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, allowing two more restrictions to be written down:

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 manufactured:

Stage 4. Writing the conditions of non-negativity

The required variables cannot be negative numbers, which must be written as 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.

Complete Linear Programming Model for production task Nicholas 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

Consider a graphical method for solving a linear programming problem.

This method is suitable only for problems with two required variables. The model built above will be used to demonstrate the method.

The axes on the graph represent the two unknown variables (Fig. 2). It doesn't matter which variable to plot along which axis. It is important to choose a scale that will ultimately allow you to build visual 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-axis 1 at x 2 \u003d 0, that is, the equation looks like this: 3 * x 1 + 10 * 0 \u003d 330, and its solution: x 1 \u003d 330 / 3 \u003d 110

Similarly, we calculate the points of intersection with the x 1 and x 2 axes for all constraint conditions:

Acceptable range	Limit of allowed 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 domain of feasible solutions for the first constraint

Any point within the selected triangle or on its borders will comply with this constraint. Such points are called valid, and points outside the triangle are called invalid.

Similarly, we reflect the rest of the restrictions on the chart (Fig. 4). Values ​​x 1 and x 2 on or inside the shaded area ABCDE will comply with all model constraints. Such a region is called the domain of admissible solutions.

Rice. 4. The area of ​​feasible solutions for the model as a whole

Now, in the area 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

we divide (or multiply) the coefficients before x 1 and x 2 by the same number, so that the resulting values ​​fall into the range shown on the graph; in our case, such a range is from 0 to 120; so the coefficients can be divided by 100 (or 50):

Z = 25x 1 + 35x 2

then assign Z value equal to the product 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 axes x 1 and x 2:

Let's plot this target equation on the graph in the same way as the constraints (Fig. 5):

Rice. 5. Application of the objective function (black dotted line) to the area 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 transfer the line of the objective function to such a point within the boundaries of the area of ​​​​admissible 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 its maximum within the region of feasible solutions (at point C)

It can be concluded that optimal solution will be located at one of the extreme points of the decision area. In which one, it will depend on the slope of the objective function and on what problem we are solving: maximizing or minimizing. Thus, it is not necessary to draw an objective function - all that is needed 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 corresponding 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 in which the maximum value of Z is obtained 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 at the intersection of the lines: 3x 1 + 10x 2 = 330 and 6x 1 + 6x 2 = 240. The solution to this system of equations gives: x 1 = 10, x 2 = 30. The calculation results for all vertices of the area of ​​feasible solutions are given in the table:

Dot	Value x 1	Value x 2	Z \u003d 2500x 1 + 3500x 2
BUT	22	12	97 000
AT	20	20	120 000
With	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Thus, Nikolai Kuznetsom must plan the production of 10 items A and 30 items B for the next month, 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 summarized as follows:

1. Draw two axes on the graph representing two decision parameters; draw only the 1st quadrant.
2. Determine the coordinates of the points of intersection of all boundary conditions with the axes, substituting the values ​​x 1 = 0 and x 2 = 0 into the equations of the boundary conditions in turn.
3. Draw model constraint lines on the chart.
4. Determine the area on the graph (called the allowable decision area) that meets all the constraints. If there is no such region, then the model has no solution.
5. Determine the values ​​of the required variables in extreme points decision domain, and in each case calculate the corresponding value of the target variable Z.
6. 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.

TOPIC: LINEAR PROGRAMMING

TASK 2.A. Solving a linear programming problem by a graphical method

Attention!

This is an INTRODUCTION VERSION of work No. 2073, the price of the original is 200 rubles. Framed in Microsoft program word.

Payment. Contacts.

Option 7. Find the maximum and minimum valueslinear function Ф \u003d 2x 1 - 2 x 2with restrictions: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1.2.

Decision:

Replacing conditionally signs of inequalities with signs of equalities, we obtain a system of equations x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

We construct straight lines according to these equations, then, in accordance with the signs of inequalities, we select the half-planes and obtain their common part - the region of admissible solutions of the ODE - the quadrilateral MNPQ.

The minimum value of the function

tsii - at the point M (2; 2)

Ф min = 2 2 - 2 2 = 0.

The maximum value is reached at point N (10; 0),

Ф max \u003d 2 10 - 2 0 \u003d 20.

Option 8. Find the maximum and minimum values

linear function Ф \u003d x 1 + x 2

with restrictions: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1.2.

Decision:

Replacing conditionally signs of inequalities with signs of equalities, we obtain a system of equations x1 - 4 x2 = 4;

3 x1 - x2 = 0;

We construct straight lines according to these equations, then, in accordance with the signs of inequalities, we select half-planes and obtain their common part - the region of admissible solutions of the ODE - an unbounded polygon MNPQ.

The minimum value of the function

tions - on a straight line NP, for example

at the point Р(4; 0)

Ф min = 4 + 0 = 4.

ODE is not limited from above, therefore, Ф max = + ∞.

Option 10. Find the maximum and minimum values

linear function Ф \u003d 2 x 1 - 3 x 2

with restrictions: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1.2.

Replacing conditionally the signs of inequalities with signs of equalities, we obtain a system of equations

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

We construct straight lines according to these equations, then, in accordance with the signs of inequalities, we select half-planes and obtain their common part - the region of admissible solutions of the ODE - the polygon MNPQRS.

We construct the vector Г(2; -3) and draw through the origin level line- straight.

We move the level line in the direction, while the value of F increases. At the point S(7; 0), the objective function reaches its maximum Ф max =2·7–3·0= = 14. We move the level line in the direction, while the value of Ф decreases. The minimum value of the function is at the point N(0; 5)

Ф min = 2 0 – 3 5 = –15.

TASK 2.B. Solving a linear programming problem

analytical simplex method

Option 7. Minimize the objective function Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

under restrictions: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Decision:

The number of unknowns n=6, the number of equations m=3. Therefore, r = n-m = 3 unknowns can be taken as free. Let's choose x 1 , x 3 and x 6 .

We express the basic variables x 2 , x 4 and x 5 in terms of free ones and bring the system to the unit basis

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

The objective function will look like:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Let's put x 1 \u003d x 3 \u003d x 6 \u003d 0, while the basic variables will take on the values ​​x 2 \u003d 2; x 4 \u003d 9; x 5 \u003d 6, that is, the first feasible solution (0; 2; 0; 9; 6; 0), objective function Ф 1 \u003d 13.

Variables x 3 and x 6 are included in the objective function with negative coefficients, therefore, with an increase in their values, the value of Ф will decrease. Take, for example, x 6 . From the 1st equation of the system (*) it can be seen that an increase in the value of x 6 is possible up to x 6 \u003d 1 (as long as x 2 ³ 0). In this case, x 1 and x 3 retain values ​​equal to zero. Now, as basic variables, we take x 4, x 5, x 6, as free - x 1, x 2, x 3. Let us express the new basic variables in terms of the new free ones. Get

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Assign to free variables null values, that is, x 1 \u003d x 2 \u003d x 3 \u003d 0, while x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, that is, the third valid solution (0; 0; 0; 3; 4; 1 ). In this case, Ф 3 \u003d 6.

The variable x 3 is included in the objective function with a negative coefficient, therefore, an increase in x 3 relative to zero will lead to a decrease in F. From the 2nd equation it can be seen that x 3 can increase up to 1/4, from the 3rd equation - up to 2/3 . The second equation is more critical. We translate the variable x 3 into the number of basic ones, x 4 into the number of free ones.

Now we take x 1 , x 2 and x 4 as new free variables. Let's express new basic variables x 3 , x 5 , x 6 in terms of them. Let's get the system

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

The objective function will take the form

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Variables x 1 and x 2 are included in the objective function with negative coefficients, therefore, with an increase in their values, the value of Ф will decrease. Take, for example, x 2 . From the 2nd equation of the system, it can be seen that an increase in the value of x 2 is possible up to x 2 \u003d 5 (as long as x 5 ³ 0). In this case, x 1 and x 4 retain zero values, the values ​​of other variables are equal to x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, that is, the fourth valid solution (0; 5; 3/2; 0; 0; 3/2). In this case, Ф 4 \u003d 5/4.

Now we take x 1 , x 4 and x 5 as new free variables. Let's express new basic variables x 2 , x 3 , x 6 in terms of them. Let's get the system

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

The objective function will take the form

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

The coefficients for both variables in the expression for Ф are positive, therefore, a further decrease in the value of Ф is impossible.

That is, the minimum value of Ф min = - 5, the last feasible solution (0; 5; 3/2; 0; 0; 3/2) is optimal.

Option 8. Maximize the objective function Ф = 4 x 5 + 2 x 6

with restrictions: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Decision:

The number of equations is 4, the number of unknowns is 6. Therefore, r = n - m = 6 - 4 = 2 variables can be chosen as free, 4 variables as basic. We choose x 5 and x 6 as free ones, x 1, x 2, x 3, x 4 as basic ones. We express the basic variables in terms of the free ones and reduce the system of equations to the unit basis

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

We write the objective function in the form Ф = 4 x 5 + 2 x 6 . We assign zero values ​​to free variables x 5 = x 6 = 0. In this case, the basic variables will take on the values ​​x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9, that is, we will get the first feasible solution (12, 30 , 6, 9, 0,) and Ф 1 = 0.

Both free variables enter the target function with positive coefficients, that is, a further increase in F is possible. Let's translate, for example, x 6 into the number of basic ones. Equation (1) shows that x 1 = 0 at x 5 = 12, in (2) ÷ (4) x 6 enters with positive coefficients. Let's move on to a new basis: basic variables - x 6, x 2, x 3, x 4, free - x 1, x 5. Let's express the new basic variables through new free

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

The objective function will take the form Ф = 24 - 2 x 1 + 2 x 5 ;

We assign zero values ​​to free variables x 1 = x 5 = 0. In this case, the basic variables will take on the values ​​x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21, that is, we will obtain the second feasible solution (0, 42 , 30, 21, 0, 12) and Ф 2 = 24.

The target function x 5 enters with a positive coefficient, that is, a further increase in F is possible. Let's move on to a new basis: basic variables - x 6, x 5, x 3, x 4, free ones - x 1, x 2. Let's express new basic variables through new free

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

The objective function will take the form Ф = 38 - 7/2 x 1 - 1/3 x 2;

Assign zero values ​​x 1 = x 2 = 0 to free variables. In this case, the basic variables will take on the values ​​x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/2, that is, we will get the third feasible solution X 3 = (0, 0, 9, 7/2, 7, 5) and Ф 3 = 38.

Both variables enter the target function with negative coefficients, that is, a further increase in Ф is impossible.

Therefore, the last feasible solution is optimal, that is, Х opt = (0, 0, 9, 7/2, 7, 5) and Ф max = 38.

Option 10. Maximize the objective function Ф \u003d x 2 + x 3

under restrictions: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Decision:

The system of equations - constraints is consistent, since the ranks of the matrix of the system of equations and the extended matrix are the same and equal to 2. Therefore, two variables can be taken as free, two other variables - basic - can be expressed linearly in terms of two free ones.

Let's take x 2 and x 3 as free variables. Then the variables x 1 and x 2 will be the basic ones, which we will express in terms of free

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

The target function has already been expressed in terms of x 2 and x 3 , that is, Ф = x 2 + x 3 .

At x 2 \u003d 0 and x 3 \u003d 0, the basic variables will be equal to x 1 \u003d 1, x 4 \u003d 2.

We have the first feasible solution X 1 = (1, 0, 0, 2), while Ф 1 = 0.

An increase in Ф is possible with an increase, for example, in the value of x 3, which is included in the expression for Ф with a positive coefficient (x 2 remains equal to zero). In the first equation of the system (*), it can be seen that x 3 can be increased to 1 (from the condition x 1 ³0), that is, this equation imposes a restriction on increasing the value of x 3. The first equation of the system (*) is resolving. On the basis of this equation, we pass to a new basis, changing x 1 and x 3 places. Now the basic variables will be x 3 and x 4, free - x 1 and x 2. We now express x 3 and x 4 in terms of x 1 and x 2.

We get: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Equating the free variables to zero, we obtain the second admissible basic solution X 2 = (0; 0; 1; 4), in which Ф 2 =1.

An increase in F is possible with an increase in x 2. Magnification same x 2, judging by latest system equations (**), unlimited. Therefore, Ф will take all large positive values, that is, Ф max = + ¥.

So, the objective function Ф is not bounded from above, so there is no optimal solution.

TASK 2.D. Write a problem dual to the given one.

original problem.

Option 7. Maximize the objective function Ф = 2× x 1 - x 4

with restrictions: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Decision:

We bring the system of constraints to a single, for example, canonical form by introducing additional variables into the 2nd and 3rd equations

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

We got an asymmetric problem of the 2nd type. The dual problem will look like:

Minimize objective function F = 20 × y 1 + 5 × y 2 + 8 × y 3

for y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Option 8. Maximize the objective function Ф \u003d x 2 - x 4 - 3× x 5

with restrictions: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Decision:

We have the original maximization problem with a system of constraints in the form of equations, that is, a pair of dual problems has an asymmetric form of the 2nd type, mathematical model which in matrix form has the form:

Initial problem: Dual problem:

F = C × X max F = B T × Ymin

at A × X \u003d B at A T × Y ≥ C T

In the original problem, the matrix-row of coefficients for variables in the objective function has the form С = (0; 1; 0; -1; -3; 0),

the column matrix of free terms and the matrix of coefficients for variables in the constraint system have the form

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

Find the transposed matrix of coefficients, the matrix-row of coefficients for variables in the objective function, and the matrix-column of free members

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

The dual problem can be written in the following form:

find the minimum value of the objective function F = y 1 + 2 × y 2 + 5 × y 3

under restrictions y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Option 10. Minimize the function Ф = x 1 + x 2 + x 3

limited: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Decision:

We have the original minimization problem with a system of constraints in the form of inequalities, that is, a pair of dual problems has a symmetrical form of the 3rd type, the mathematical model of which in matrix form has the form:

Original problem Dual problem

F = C × X min F \u003d B T × Ymax

at A × X ≥ B at A T × Y ≤ C T

X ≥ 0 Y ≥ 0

In the original problem, the matrix-row of coefficients for variables in the objective function, the matrix-column of free terms and the matrix of coefficients for variables in the system of constraints have the form

C \u003d (1; 1; 1), B \u003d 3, A \u003d 6 4 5

Let us find the matrices of the dual problem

B T = (2; 3; 4) C T = 3 A T = 9 4 2

The dual problem is formulated as:

Maximize objective function F = 2y 1 + 3y 2 + 4y 3

under restrictions 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

TASK 2.C. Solving a linear programming problem using simplex tables.

Option 7. Maximize the objective function Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

under restrictions: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Decision:

We reduce the system of constraints to the canonical form

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

We have a system of 3 equations with 7 unknowns. We choose x 1 , z 1 , z 3 as basic 3 variables, x 2 , x 3 , x 4 , z 2 as free ones, we express the basic variables through them.

From (2) we have x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Substitute in (1) and (3), we get

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Compose a simplex table

I iteration Table 1

Basic AC	Freedom. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II iteration Table 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III iteration Table 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

IV iteration Table 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

In the index line last table No negative numbers, that is, in the expression for the objective function, all Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Answer: Ф max = 149/14,

optimal solution (0; 0; 25/14; 37/14; 1/2; 0; 0)

Option 8. Minimize the objective function Ф = 5 x 1 - x 3

under restrictions: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Decision:

The number of variables is 4, the rank of the matrix is ​​​​2, therefore the number of free variables is r \u003d 4 - 2 \u003d 2, the number of basic variables is also 2. We take x 3, x 4 as free variables, we will express the basic variables x 1, x 2 through free and we bring the system to the unit basis:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

We write the system of equations and the objective function in a form convenient for the simplex table, that is, x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 x 3 - 15 x 4 \u003d 10

Let's make a table

I iteration Table 1

Basic AC	Freedom. AC
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II iteration Table 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III iteration Table 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

There is no last table in the index row positive numbers, that is, in the expression for the objective function, all Г i > 0. We have case I, therefore, the last basic solution is optimal.

Answer: Ф min = -7/4, optimal solution (0; 0; 7/4; 1/2)

********************

Option 10. Minimize the objective function Ф \u003d x 1 + x 2,

with restrictions: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Decision:

The number of variables is 5, the rank of the matrix is ​​​​3, therefore the number of free variables is r \u003d 6-3 \u003d 2. We take x 3 and x 4 as free variables, x 1, x 2, x 5 as basic ones. All equations of the system have already been reduced to a single basis (basic variables are expressed in terms of free variables), but they are written in a form that is not convenient for using simplex tables. We write the system of equations in the form

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

We express the objective function in terms of free variables and write it in the form Ф - 3 x 3 +3 x 4 = 3

Let's make a table

I iteration Table 1

Basic AC	Freedom. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

table 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

There are no positive numbers in the index row of the last table, that is, in the expression for the objective function, all Гi > 0. We have case 1, therefore, the last basic solution is optimal.

Answer: Ф min = 3/2, the optimal solution is (3/2; 0; 0; 1/2; 11/2).

Decision: find the maximum and minimum value of the function \(f (x, y)\) under the following constraints $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Graphical way It is advisable to use the solution of the problem for problems with two variables that are written in a symmetrical form, as well as for problems with many variables, provided that their canonical notation contains no more than two free variables.

AT this case task with two variables.

Algorithm for solving the problem "geometric interpretation of a linear programming problem":

1. Let's construct the domain of admissible solutions on the xOy plane.
2. Select the area of ​​non-negative solutions.

4. Let us construct a family of objective functions.
5. Find the maximum (minimum) value of the objective function.

1. We construct the domain of admissible solutions of the problem \(D\).

To build the area of ​​feasible solutions:
1) We build boundary lines:
we transform the inequalities to equalities, and then to the equation of a straight line in segments on the axes of the form \(\frac(x)(a)+\frac(y)(b) = 1\), then \(x=a\) is a segment cut off on the Ox axis, \(y=b\) - on the Oy axis $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ -x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac(y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ For each line, set aside segments on the axes and connect them. We got the right lines.

2) We find half-planes that satisfy the given inequalities:
For the inequality \(2x+3y\geq 6\) is the half-plane that lies above the line \(2x+3y = 6\). Direct AC
For the inequality \(3x-2y\leq 18 => -3x+2y \geq -18\) is a half-plane that lies above the line \(3x-2y = 18\). Direct CB
For the inequality \(-x+2y\leq 8\) is the half-plane that lies below the line \(-x+2y = 8\). Direct AB

The domain of feasible solutions is defined as a common part three half-planes corresponding to the given inequalities. This area is a triangle \(ABC\)

The region \(D\) is the triangle \(ABC\) see fig.

2. Select the area of ​​non-negative solutions.

The area of ​​non-negative solutions is located in the first quarter and is common part of all five half-planes, three of which are the region \(D\) obtained from inequalities and additionally two inequalities \(x \geq 0\) - the upper half-plane (I and II quarters) and \(y \geq 0\) - the right half-plane (I and IV quarters), which express the condition of non-negativity of the variables \(x;y\). Obtained the desired area of ​​non-negative solutions \(DEBFG\)

3.Find the coordinates of the region's vertices.
The coordinates of the four vertices are already known (these are the points of intersection of the lines with the axes).
Let's write down these coordinates:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Find the coordinates of the point \(B\), as the points of intersection of the lines \(-x+2y = 8\) and \(3x-2y = 18\). Solve the system of equations and find the coordinates of this point $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x-2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
We got the coordinates of the point \(B(13;10.5)\)

4. We build a family of objective functions.
The equation \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) defines on the xOy plane a family of concentric circles centered at the point with coordinates \(Q(4 ;3)\), each of which corresponds certain value parameter \(f\). As you know, for the equation of a circle the parameter \(f=R^2\).

Let us represent in the same coordinate system a family of concentric circles \(f\) and a family of lines. The problem of determining the point of maximum (minimum) of the point \(f\) will be reduced to finding in allowable area the point through which the circle of the family \(f=const\) passes, which is responsible for the largest (smallest) value of the parameter \(f\).

5. Find the maximum (minimum) value of the objective function.

Minimum objective function value: way gradual increase radius of the circle, we got that the first vertex through which the circle passes is the point \(G(3;0)\). The objective function at this point will be minimal and equal to \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

The maximum value of the objective function: By further increasing the radius of the circle, we have obtained that the last vertex through which the circle will pass is the point \(B(13;10.5)\). The objective function at this point will be maximum and equal to \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

You can verify the correctness of the solution by substituting the coordinates of the remaining vertices into the objective function equation:
at the vertex \(D(0;2)\) the value of the objective function is equal to \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
at the vertex \(E(0;4)\) the value of the objective function is equal to \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
at the vertex \(F(6;0)\) the value of the objective function is \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Got that

Answer:
the minimum value of the objective function \(f_(min) = 10\)
the maximum value of the objective function \(f_(max) = 137.25\)

Find by a graphical method the maximum of the objective function

F= 2x 1 + 3x 2 ® max

With restrictions

Decision via Excel tables

Let's first build on a sheet excel solution systems of inequalities.

Consider the first inequality.

Let's construct a boundary line from two points. Denote the line by (L1) (or Row1). Coordinates X 2 we count according to the formulas:

To build, select a scatter plot

Choosing data for a straight line

Change the name of the line:

Choose a chart layout. Change the name of the coordinate axes:

Straight line (L1) on the chart:

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)W(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 test point is located (in the figure below the line L1).

Then we solve inequality (2) .

Let us construct the boundary line 2 from two points. Denote the line by (L2).

Straight line (L2) on the chart:

The solution of strict inequality 2 can be found using the only test point that does not belong to the line (L2). For example, using the point (0; 0)W(L2).

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 test point is located (in the figure below, the line L2).

Then we solve inequality (3) .

Let's construct a boundary line from two points. Denote the line by (L3).

Straight line (L3) on the chart:

The solution of strict inequality 2 can be found using the only test point that does not belong to the line (L3). For example, using the point (0; 0)W(L3).

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 test point is located (in the figure below, line L3).

Then we solve inequality (4) .

Let's construct a boundary line from two points. Denote the line by (L4).

Add data to excel sheet

Straight line (L4) on the chart:

Solution of Strict Inequality 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

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 test point is located (to the left of the line L4 in the figure).

By solving two inequalities (5) and (6)

is the 1st quarter bounded by the coordinate lines and .

The system of inequalities is solved. By solving the system of inequalities (1) - (6) in this example is a convex polygon in the lower left corner of the figure, bounded by lines L1, L2, L3, L4 and 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. Substituting the point (1; 1), we obtain that all inequalities, including the natural constraints, are true.

Consider now the objective function

F= 2x 1 + 3x 2 .

Let's build level lines for function values F=0 and F=12 (numerical values chosen arbitrarily). Add data to excel sheet

Level lines on the chart:

Let's construct a vector of directions (or a gradient) (2; 3). The vector coordinates coincide with the coefficients of the objective function F.