The optimal value of the objective function is called. Tests for current knowledge control

Divide the third row by the key element equal to 5, we get the third row of the new table.

Basic columns correspond to unit columns.

Calculation of other table values:

“BP – Basic Plan”:

; ;

"x1": ; ;

"x5": ; .

The values ​​of the index string are non-negative, therefore we obtain the optimal solution: , ; .

Answer: the maximum profit from the sale of manufactured products, equal to 160/3 units, is ensured by the production of only products of the second type in the amount of 80/9 units.

Task No. 2

A nonlinear programming problem is given. Find the maximum and minimum of the objective function using the graphic-analytical method. Compose the Lagrange function and show that at the extremum points sufficient conditions for the minimum (maximum) are satisfied.

Because the last digit of the cipher is 8, then A=2; B=5.

Because the penultimate digit of the cipher is 1, then you should choose task No. 1.

Solution:

1) Let us draw the area defined by the system of inequalities.

This area is triangle ABC with vertex coordinates: A(0; 2); B(4; 6) and C(16/3; 14/3).

The levels of the objective function are circles with the center at the point (2; 5). The squares of the radii will be the values ​​of the objective function. Then the figure shows that the minimum value of the objective function is achieved at point H, the maximum - either at point A or at point C.

The value of the objective function at point A: ;

The value of the objective function at point C: ;

This means that the maximum value of the function is achieved at point A(0; 2) and is equal to 13.

Let's find the coordinates of point H.

To do this, consider the system:

ó

ó

A line is tangent to a circle if the equation has a unique solution. A quadratic equation has a unique solution if the discriminant is 0.

Then ; ; - minimum value of the function.

2) Let’s compose the Lagrange function to find the minimum solution:

At x 1 =2.5; x 2 =4.5 we get:

ó

The system has a solution at , i.e. sufficient extremum conditions are satisfied.

We compose the Lagrange function for finding the maximum solution:

Sufficient conditions for an extremum:

At x 1 =0; x 2 =2 we get:

ó ó

The system also has a solution, i.e. sufficient extremum conditions are satisfied.

Answer: the minimum of the objective function is reached at ; ; the maximum objective function is reached when ; .

Task No. 3

Two enterprises are allocated funds in the amount d units. When allocated to the first enterprise for a year x units of funds it provides income k 1 x units, and when allocated to the second enterprise y units of funds, it provides income k 1 y units. The balance of funds at the end of the year for the first enterprise is equal to nx, and for the second my. How to distribute all the funds over 4 years so that the total income is greatest? Solve the problem by dynamic programming.

i=8, k=1.

A=2200; k 1 =6; k 2 =1; n=0.2; m=0.5.

Solution:

The entire period of 4 years is divided into 4 stages, each of which is equal to one year. Let's number the stages starting from the first year. Let X k and Y k be the funds allocated respectively to enterprises A and B at the kth stage. Then the sum X k + Y k = a k is the total amount of funds used at the k – that stage and the remainder from the previous stage k – 1. at the first stage, all allocated funds are used and a 1 = 2200 units. the income that will be received at the k – that stage, with the allocation of X k and Y k units will be 6X k + 1Y k. let the maximum income received at the last stages starting from k – that stage be f k (a k) units. Let us write down the functional Bellman equation expressing the principle of optimality: whatever the initial state and the initial solution, the subsequent solution must be optimal with respect to the state obtained as a result of the initial state:

For each stage you need to select the value X k, and the value Yk=ak- Xk. Taking this into account, we will find the income at the kth stage:

The Bellman functional equation will be:

Let's consider all stages, starting with the last one.

(since the maximum of the linear function is achieved at the end of the segment at x 4 = a 4);

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. Create a mathematical model of the 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.

Introduction

The current stage of human development is distinguished by the fact that the age of energy is being replaced by the age of computer science. There is an intensive introduction of new technologies into all spheres of human activity. There is a real problem of transition to an information society, for which the development of education should become a priority. The structure of knowledge in society is also changing. Fundamental knowledge that contributes to the creative development of the individual is becoming increasingly important for practical life. The constructiveness of the acquired knowledge and the ability to structure it in accordance with the goal are also important. New information resources of society are formed on the basis of knowledge. The formation and acquisition of new knowledge should be based on a strict methodology of a systems approach, within which the model approach occupies a special place. The possibilities of the model approach are extremely diverse, both in terms of the formal models used and in the methods of implementing modeling methods. Physical modeling allows one to obtain reliable results for fairly simple systems.

Currently, it is impossible to name an area of ​​human activity in which modeling methods would not be used to one degree or another. This especially applies to the management of various systems, where the main processes are decision-making based on the information received.

1. Statement of the problem

minimum objective function

Solve the problem of finding the minimum of the objective function for the system of constraints specified by the solution polygon in accordance with option No. 16 of the task. The solution polygon is shown in Figure 1:

Figure 1 - Polygon of solutions to the problem

The system of constraints and the objective function of the problem are presented below:

It is necessary to solve the problem using the following methods:

Graphical method for solving LP problems;

Algebraic method for solving LP problems;

Simplex method for solving LP problems;

Method for finding an admissible solution to LP problems;

Solution of the dual LP problem;

Branch and bound method for solving integer LP problems;

Gomori method for solving integer LP problems;

Balazs method for solving Boolean LP problems.

Compare the solution results using different methods and draw appropriate conclusions about the work.

2. Graphical solution to the linear programming problem

The graphical method for solving linear programming problems is used in cases where the number of unknowns does not exceed three. Convenient for qualitative research of the properties of solutions and is used in conjunction with other methods (algebraic, branch and bound, etc.). The idea of ​​the method is based on the graphical solution of a system of linear inequalities.

Rice. 2 Graphical solution of the LP problem

Minimum point

Equation of a line passing through two points A1 and A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

with restrictions:

Solving a linear programming problem using the algebraic simplex method

The application of an algebraic method for solving a problem requires a generalization of the representation of the LP problem. The original system of restrictions, specified in the form of inequalities, is converted to a standard notation when the restrictions are specified in the form of equalities. Converting a system of restrictions to a standard form includes the following steps:

Transform the inequalities so that there are variables and free terms on the left, and 0 on the right, i.e. so that the left side is greater than or equal to zero;

Introduce additional variables, the number of which is equal to the number of inequalities in the system of constraints;

By introducing additional restrictions on the non-negativity of the added variables, replace the inequality signs with strict equality signs.

When solving an LP problem using the algebraic method, a condition is added: the objective function must tend to a minimum. If this condition is not met, it is necessary to transform the objective function accordingly (multiply by -1) and solve the minimization problem. After the solution is found, substitute the values ​​of the variables into the original function and calculate its value.

The solution to a problem using the algebraic method is considered optimal when the values ​​of all basic variables are non-negative, and the coefficients of the free variables in the objective function equation are also non-negative. If these conditions are not met, it is necessary to transform the system of inequalities, expressing some variables in terms of others (changing free and basic variables) to achieve the fulfillment of the above restrictions. The value of all free variables is considered equal to zero.

The algebraic method for solving linear programming problems is one of the most effective methods for solving small-scale problems manually because does not require a large number of arithmetic calculations. The machine implementation of this method is more complicated than, for example, for the simplex method, because The solution algorithm using the algebraic method is to some extent heuristic and the effectiveness of the solution largely depends on personal experience.

Free variables

St. lane - additional kit

The non-negativity conditions are met, therefore, the optimal solution has been found.

3. Solving a linear programming problem using a simplex table

Solution: Let's bring the problem to a standard form for solution using a simplex table.

Let us reduce all equations of the system to the form:

We build a simplex table:

In the upper corner of each cell of the table we enter the coefficients from the system of equations;

We select the maximum positive element in row F, except that this will be the general column;

In order to find the general element, we build a relationship for all positive ones. 3/3; 9/1;- minimum ratio in line x3. Therefore - the general string and =3 - the general element.

We find =1/=1/3. We bring it into the lower corner of the cell where the general element is located;

In all empty lower corners of the general line we enter the product of the value in the upper corner of the cell by;

Select the upper corners of the general line;

In all the lower corners of the general column we enter the product of the value in the upper corner by - and select the resulting values;

The remaining cells of the table are filled in as products of the corresponding selected elements;

Then we build a new table in which the designations of the cells of the elements of the general column and row are swapped (x2 and x3);

The values ​​that were previously in the lower corner are written into the upper corner of the former general row and column;

The sum of the values ​​of the upper and lower corners of these cells in the previous table is written in the upper corner of the remaining cells

4. Solving a linear programming problem by finding an admissible solution

Let a system of linear algebraic equations be given:

We can assume that everything is, otherwise we multiply the corresponding equation by -1.

We introduce auxiliary variables:

We also introduce an auxiliary function

We will minimize the system under restrictions (2) and conditions.

RULE FOR FINDING AN ALLOWABLE SOLUTION: To find an admissible solution to system (1), we minimize form (3) under restrictions (2), taking xj as free unknowns, and taking xj as the basis ones.

When solving a problem using the simplex method, two cases may arise:

min f=0, then all i must be equal to zero. And the resulting values ​​of xj will constitute an admissible solution to system (1).

min f>0, i.e. the original system does not have a feasible solution.

Source system:

The condition of the problem from the previous topic is used.

Let's introduce additional variables:

An admissible solution to the original problem has been found: x1 = 3, x2 = 3, F = -12. Based on the obtained feasible solution, we will find the optimal solution to the original problem using the simplex method. To do this, we will build a new simplex table from the table obtained above, removing the row and the row with the target function of the auxiliary problem:

Analyzing the constructed simplex table, we see that the optimal solution for the original problem has already been found (the elements in the row corresponding to the objective function are negative). Thus, the feasible solution found when solving the auxiliary problem coincides with the optimal solution to the original problem:

6. Dual linear programming problem

The initial system of constraints and the objective function of the problem are shown in the figure below.

with restrictions:

Solution: Let’s bring the system of restrictions to a standard form:

The problem dual to this one will have the form:

The solution to the dual problem will be performed using a simple simplex method.

Let us transform the objective function so that the minimization problem is solved and write down the system of constraints in the standard form for solving by the simplex method.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Let us construct an initial simplex table for solving the dual LP problem.

Second step of the simplex method

So, at the third step of the simplex method, the optimal solution of the minimization problem was found with the following results: y2 = -7 /8, y1 = -11/8, Ф = 12. In order to find the value of the objective function of the dual problem, we substitute the found values ​​of the basic and free variables into the maximization function:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Since the value of the objective function of the direct and dual problems are the same, the solution to the direct problem is found and is equal to 12.

Fmin = Фmax = -12

7. Solving the problem of integer linear programming using the “branches and bounds” method

Let us transform the original problem in such a way that the integer condition is not satisfied when solved using conventional methods.

Initial polygon of solutions to an integer programming problem.

For the transformed polygon of solutions, we will construct a new system of restrictions.

Let us write down the system of restrictions in the form of equalities to be solved using the algebraic method.

As a result of the solution, the optimal plan for the problem was found: x1 = 9/4, x2 = 5/2, F = -41/4. This solution does not meet the integer condition set in the problem. Let's divide the original solution polygon into two areas, excluding area 3 from it

Modified problem solution polygon

Let's create new systems of restrictions for the resulting areas of the solution polygon. The left area is a quadrilateral (trapezoid). The system of restrictions for the left region of the solution polygon is presented below.

Restriction system for the left area

The right area represents point C.

The system of restrictions for the right decision region is presented below.

The new constraint systems represent two auxiliary problems that need to be solved independently of each other. Let's solve an integer programming problem for the left region of the solution polygon.

As a result of the solution, the optimal plan for the problem was found: x1 = 3, x2 = 3, F = -12. This plan satisfies the condition that the variables in the problem are integer and can be accepted as the optimal reference plan for the original integer linear programming problem. There is no point in solving for the right solution region. The figure below shows the progress of solving an integer linear programming problem in the form of a tree.

Progress of solving an integer linear programming problem using the Gomori method.

In many practical applications, an integer programming problem in which a system of linear inequalities and a linear form is given is of great interest

It is required to find an integer solution to system (1), which minimizes the objective function F, and all coefficients are integers.

One of the methods for solving the integer programming problem was proposed by Gomori. The idea of ​​the method is to use continuous linear programming methods, in particular, the simplex method.

1) Using the simplex method, the solution to problem (1), (2) is determined, for which the requirement for an integer solution is removed; if the solution turns out to be integer, then the desired solution to the integer problem will also be found;

2) Otherwise, if some coordinate is not an integer, the resulting solution to the problem is checked for the possibility of the existence of an integer solution (the presence of integer points in an admissible polyhedron):

if in any row with a fractional free term, all other coefficients turn out to be integers, then there are no integers or points in the admissible polyhedron and the integer programming problem has no solution;

Otherwise, an additional linear constraint is introduced, which cuts off a part of the admissible polyhedron that is unpromising for finding a solution to the integer programming problem;

3) To construct an additional linear constraint, select the lth row with a fractional free term and write the additional constraint

where and are respectively fractional parts of the coefficients and free

member. Let us introduce an auxiliary variable into constraint (3):

Let us determine the coefficients and included in constraint (4):

where and are the nearest integers from below for and respectively.

Gomori proved that a finite number of similar steps leads to a linear programming problem whose solution is integer and, therefore, the desired one.

Solution: Let’s bring the system of linear constraints and the goal function to the canonical form:

Let us determine the optimal solution to the system of linear constraints, temporarily discarding the integer condition. We use the simplex method for this. Below, sequentially in the tables, the original solution of the problem is presented, and the transformations of the original table are given in order to obtain the optimal solution to the problem:

Solving Boolean LP problems using the Balazs method.

Create your own version for an integer linear programming problem with Boolean variables, taking into account the following rules: the problem uses at least 5 variables, at least 4 constraints, the coefficients of the constraints and the objective function are chosen arbitrarily, but in such a way that the system of constraints is compatible. The task is to solve the LCLP with Boolean variables using the Balazs algorithm and determine the reduction in the complexity of calculations in relation to solving the problem using the exhaustive search method.

Execution of restrictions

F value

Filtering limitation:

Determination of computational effort reduction

The solution to the problem using the exhaustive search method is 6*25=192 calculated expressions. The solution to the problem using the Balazs method is 3*6+(25-3)=47 calculated expressions. The total reduction in the complexity of calculations in relation to solving the problem using the exhaustive search method is:

Conclusion

The process of designing information systems that implement new information technology is constantly being improved. The focus of systems engineers is increasingly on complex systems, making it difficult to use physical models and increasing the importance of mathematical models and machine simulation of systems. Machine simulation has become an effective tool for studying and designing complex systems. The relevance of mathematical models is continuously increasing due to their flexibility, adequacy to real processes, and low cost of implementation on the basis of modern PCs. More and more opportunities are provided to the user, i.e., a specialist in modeling systems using computer technology. The use of modeling is especially effective in the early stages of designing automated systems, when the cost of erroneous decisions is most significant.

Modern computing tools have made it possible to significantly increase the complexity of the models used in the study of systems; it has become possible to build combined, analytical and simulation models that take into account the whole variety of factors that occur in real systems, i.e., the use of models that are more adequate to the phenomena under study.

Literature:

1. Lyashchenko I.N. Linear and nonlinear programming / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K.: “Higher School”, 1975, 372 p.

2. Guidelines for completing a course project in the discipline “Applied Mathematics” for students of the specialty “Computer Systems and Networks” of full-time and part-time forms of study / Compiled by: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Publishing House , 2003. - 15 p.

3. Guidelines for studying the discipline “Applied Mathematics”, section “Methods of global search and one-dimensional minimization” / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31 p.

4. Guidelines for studying the discipline “Applied Mathematics” for students of the specialty “Computer Systems and Networks” Section “Solving integer linear programming problems” for full-time and part-time education / Compiled by: I.A. Balakireva, A.V. Skatkov - Sevastopol : Publishing House of SevNTU, 2000. - 13 p.

5. Akulich I.L. Mathematical programming in examples and problems:

6. Textbook allowance for economics students. specialist. universities.-M.: Higher. school, 1986.- 319 p., ill.

7. Andronov S.A. Optimal design methods: Text of lectures / SPbSUAP. St. Petersburg, 2001. 169 p.: ill.

Similar documents

Algorithm for solving linear programming problems using the simplex method. Construction of a mathematical model of a linear programming problem. Solving a linear programming problem in Excel. Finding profit and optimal production plan.

course work, added 03/21/2012


Graphic problem solving. Drawing up a mathematical model. Determining the maximum value of the objective function. Solution by the simplex method with an artificial basis of the canonical linear programming problem. Checking the optimality of the solution.

test, added 04/05/2016


Theoretical basis of linear programming. Linear programming problems, solution methods. Analysis of the optimal solution. Solution of a single-index linear programming problem. Statement of the problem and data entry. Model construction and solution stages.

course work, added 12/09/2008


Construction of a mathematical model. Selection, justification and description of the method for solving a direct linear programming problem using the simplex method, using a simplex table. Formulation and solution of a dual problem. Sensitivity analysis of the model.

course work, added 10/31/2014


Construction of a mathematical model in order to obtain maximum profit for the enterprise, graphical solution of the problem. Solving the problem using the SOLVER add-on. Analysis of changes in resource reserves. Determining the limits for changing the coefficients of the objective function.

course work, added 12/17/2014


Mathematical programming. Linear programming. Linear programming problems. Graphical method for solving linear programming problems. Economic formulation of the linear programming problem. Construction of a mathematical model.

course work, added 10/13/2008


Solving a linear programming problem by graphical method, checking it in MS Excel. Analysis of the internal structure of solving a problem in a program. Optimization of production plan. Solving the problem using the simplex method. Multichannel queuing system.

test, added 05/02/2012


Solving a linear programming problem using the simplex method: statement of the problem, construction of an economic and mathematical model. Solving the transport problem using the potential method: constructing the initial reference plan, determining its optimal value.

test, added 04/11/2012


Statement of the nonlinear programming problem. Determination of stationary points and their type. Construction of level lines, three-dimensional graph of the objective function and constraints. Graphic and analytical solution of the problem. User's manual and algorithm diagram.

course work, added 12/17/2012


Analysis of the solution to a linear programming problem. Simplex method using simplex tables. Modeling and solving LP problems on a computer. Economic interpretation of the optimal solution to the problem. Mathematical formulation of the transport problem.

If a linear programming problem has only two variables, then it can be solved graphically.

Consider a linear programming problem with two variables and :
(1.1) ;
(1.2)
Here, there are arbitrary numbers. The task can be either to find the maximum (max) or to find the minimum (min). The system of restrictions may contain both signs and signs.

Construction of the domain of feasible solutions

The graphical method for solving problem (1) is as follows.
First, we draw the coordinate axes and select the scale. Each of the inequalities of the system of constraints (1.2) defines a half-plane bounded by the corresponding straight line.

So, the first inequality
(1.2.1)
defines a half-plane bounded by a straight line. On one side of this straight line, and on the other side. On the very straight line. To find out on which side inequality (1.2.1) holds, we choose an arbitrary point that does not lie on the line. Next, we substitute the coordinates of this point into (1.2.1). If the inequality holds, then the half-plane contains the selected point. If the inequality does not hold, then the half-plane is located on the other side (does not contain the selected point). Shade the half-plane for which inequality (1.2.1) holds.

We do the same for the remaining inequalities of system (1.2). This way we get shaded half-planes. The points of the region of feasible solutions satisfy all inequalities (1.2). Therefore, graphically, the region of feasible solutions (ADA) is the intersection of all constructed half-planes. Shading the ODR. It is a convex polygon whose faces belong to the constructed straight lines. Also, an ODF can be an unlimited convex figure, a segment, a ray or a straight line.

The case may also arise that the half-planes do not contain common points. Then the domain of feasible solutions is the empty set. This problem has no solutions.

The method can be simplified. You don’t have to shade each half-plane, but first construct all the straight lines
(2)
Next, select an arbitrary point that does not belong to any of these lines. Substitute the coordinates of this point into the system of inequalities (1.2). If all inequalities are satisfied, then the region of feasible solutions is limited by the constructed straight lines and includes the selected point. We shade the region of feasible solutions along the boundaries of the lines so that it includes the selected point.

If at least one inequality is not satisfied, then choose another point. And so on until one point is found whose coordinates satisfy system (1.2).

Finding the extremum of the objective function

So, we have a shaded region of feasible solutions (ADA). It is limited by a broken line consisting of segments and rays belonging to the constructed straight lines (2). The ODS is always a convex set. It can be either a bounded set or not bounded along some directions.

Now we can look for the extremum of the objective function
(1.1) .

To do this, choose any number and build a straight line
(3) .
For the convenience of further presentation, we assume that this straight line passes through the ODR. On this line the objective function is constant and equal to . such a straight line is called a function level line. This straight line divides the plane into two half-planes. On one half-plane
.
On another half-plane
.
That is, on one side of straight line (3) the objective function increases. And the further we move the point from the straight line (3), the greater the value will be. On the other side of straight line (3), the objective function decreases. And the further we move the point from straight line (3) to the other side, the smaller the value will be. If we draw a straight line parallel to line (3), then the new straight line will also be a level line of the objective function, but with a different value.

Thus, in order to find the maximum value of the objective function, it is necessary to draw a straight line parallel to straight line (3), as far as possible from it in the direction of increasing values, and passing through at least one point of the ODD. To find the minimum value of the objective function, it is necessary to draw a straight line parallel to straight line (3) and as far as possible from it in the direction of decreasing values, and passing through at least one point of the ODD.

If the ODR is unlimited, then a case may arise when such a direct line cannot be drawn. That is, no matter how we remove the straight line from the level line (3) in the direction of increasing (decreasing), the straight line will always pass through the ODR. In this case it can be arbitrarily large (small). Therefore, there is no maximum (minimum) value. The problem has no solutions.

Let us consider the case when the extreme line parallel to an arbitrary line of the form (3) passes through one vertex of the ODR polygon. From the graph we determine the coordinates of this vertex. Then the maximum (minimum) value of the objective function is determined by the formula:
.
The solution to the problem is
.

There may also be a case when the straight line is parallel to one of the faces of the ODR. Then the straight line passes through two vertices of the ODR polygon. We determine the coordinates of these vertices. To determine the maximum (minimum) value of the objective function, you can use the coordinates of any of these vertices:
.
The problem has infinitely many solutions. The solution is any point located on the segment between the points and , including the points and themselves.

An example of solving a linear programming problem using the graphical method

The task

The company produces dresses of two models A and B. Three types of fabric are used. To make one dress of model A, 2 m of fabric of the first type, 1 m of fabric of the second type, 2 m of fabric of the third type are required. To make one dress of model B, 3 m of fabric of the first type, 1 m of fabric of the second type, 2 m of fabric of the third type are required. The stocks of fabric of the first type are 21 m, of the second type - 10 m, of the third type - 16 m. The release of one product of type A brings in an income of 400 den. units, one product type B - 300 den. units

Draw up a production plan that provides the company with the greatest income. Solve the problem graphically.

Solution

Let the variables and denote the number of dresses produced, models A and B, respectively. Then the amount of fabric of the first type consumed will be:
(m)
The amount of fabric of the second type consumed will be:
(m)
The amount of fabric of the third type consumed will be:
(m)
Since the number of dresses produced cannot be negative, then
And .
The income from the dresses produced will be:
(den. units)

Then the economic-mathematical model of the problem has the form:

We solve it graphically.
We draw the coordinate axes and .

We are building a straight line.
At .
At .
Draw a straight line through the points (0; 7) and (10.5; 0).

We are building a straight line.
At .
At .
Draw a straight line through the points (0; 10) and (10; 0).

We are building a straight line.
At .
At .
Draw a straight line through the points (0; 8) and (8; 0).

We shade the area so that the point (2; 2) falls into the shaded part. We get the quadrilateral OABC.

(A1.1) .
At .
At .
Draw a straight line through the points (0; 4) and (3; 0).

We further note that since the coefficients of and of the objective function are positive (400 and 300), it increases as and increases. We draw a straight line parallel to straight line (A1.1), as far as possible from it in the direction of increasing , and passing through at least one point of the quadrilateral OABC. Such a line passes through point C. From the construction we determine its coordinates.
.

The solution of the problem: ;

Answer

.
That is, to obtain the greatest income, it is necessary to make 8 dresses of model A. The income will be 3200 den. units

Example 2

The task

Solve a linear programming problem graphically.

Solution

We solve it graphically.
We draw the coordinate axes and .

We are building a straight line.
At .
At .
Draw a straight line through the points (0; 6) and (6; 0).

We are building a straight line.
From here.
At .
At .
Draw a straight line through points (3; 0) and (7; 2).

We are building a straight line.
We build a straight line (abscissa axis).

The region of admissible solutions (ADA) is limited by the constructed straight lines. To find out which side, we notice that the point belongs to the ODR, since it satisfies the system of inequalities:

We shade the area along the boundaries of the constructed lines so that point (4; 1) falls into the shaded part. We get triangle ABC.

We build an arbitrary line of the level of the objective function, for example,
.
At .
At .
Draw a straight level line through points (0; 6) and (4; 0).
Since the objective function increases with increasing and , we draw a straight line parallel to the level line and as far as possible from it in the direction of increasing , and passing through at least one point of triangle ABC. Such a line passes through point C. From the construction we determine its coordinates.
.

The solution of the problem: ;

Answer

Example of no solution

The task

Solve a linear programming problem graphically. Find the maximum and minimum value of the objective function.

Solution

We solve the problem graphically.
We draw the coordinate axes and .

We are building a straight line.
At .
At .
Draw a straight line through the points (0; 8) and (2.667; 0).

We are building a straight line.
At .
At .
Draw a straight line through the points (0; 3) and (6; 0).

We are building a straight line.
At .
At .
Draw a straight line through points (3; 0) and (6; 3).

The straight lines are the coordinate axes.

The region of admissible solutions (ADA) is limited by the constructed straight lines and coordinate axes. To find out which side, we notice that the point belongs to the ODR, since it satisfies the system of inequalities:

We shade the area so that the point (3; 3) falls into the shaded part. We obtain an unbounded area bounded by the broken line ABCDE.

We build an arbitrary line of the level of the objective function, for example,
(A3.1) .
At .
At .
Draw a straight line through the points (0; 7) and (7; 0).
Since the coefficients of and are positive, it increases with increasing and .

To find the maximum, you need to draw a parallel line, which is as far away as possible in the direction of increasing , and passing through at least one point of the region ABCDE. However, since the area is unlimited on the side of large values ​​of and , such a straight line cannot be drawn. No matter what line we draw, there will always be points in the region that are more distant in the direction of increasing and . Therefore there is no maximum. you can make it as big as you like.

We are looking for the minimum. We draw a straight line parallel to straight line (A3.1) and as far as possible from it in the direction of decreasing , and passing through at least one point of the region ABCDE. Such a line passes through point C. From the construction we determine its coordinates.
.
Minimum value of the objective function:

Answer

There is no maximum value.
Minimum value
.