An example of solving a problem. Graphical method for solving ZLP. Solving linear programming problems using the simplex method Examples of solving graphical linear programming
The simplest and most visual method of linear programming (LP) is the graphical method. It is used to solve LP problems with two variables. Consider the LP problem in standard form:
max f(x 1 , x 2 , ..., x n) = ,
, i = 1, 2, …, m,
x j 0, j = 1, 2, …, n.
Let's put n=2 and we will consider the problem on the plane. Let the system of inequalities be consistent (have at least one solution).
Each inequality of this system geometrically defines a half-plane with the boundary line a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. The non-negativity conditions define half-planes with boundary straight lines x 1 = 0, x 2 = 0, respectively. The system is consistent, therefore half-planes, like convex sets, intersecting, form a common part, which is a convex set and is a collection of points, where the coordinates of each point are a solution to this system. The set of these points is called a solution polygon. It can be a point, a segment, a ray, a bounded or unbounded polygon.
Thus, geometrically, the ZLP is the search for such a point of the solution polygon, the coordinates of which provide the maximum (minimum) value to the linear function of the goal, and all points of the solution polygon are admissible solutions.
A linear equation describes a set of points lying on the same line. A linear inequality describes some region on the plane. Let us determine which part of the plane is described by the inequality 2x 1 + 3x 2 12.
First, let's construct a straight line 2x 1 + 3x 2= 12. It passes through the points (6; 0) and (0; 4). In order to determine which half-plane satisfies the inequality, it is necessary to select any point on the graph that does not belong to the line and substitute its coordinates into the inequality. If the inequality holds, then the given point is a feasible solution, and the half-plane containing the point satisfies the inequality. To substitute into the inequality, it is convenient to use the origin point. Substitute x 1 = x 2 = 0 into the inequality 2x 1 + 3x 2 12. We get 2x0 + 3x0 12. This statement is true, therefore, the inequality 2x 1 + 3x 2 12 corresponds to the lower half-plane containing the point (0; 0). This is reflected in the graph shown in Fig. 1.1.
Similarly, all the constraints of the LP problem can be graphically depicted.
The solution to each inequality of the ZLP constraint system is a half-plane containing the boundary line and located on one side of it. The intersection of half-planes, each of which is determined by the corresponding inequality of the system, is called the region of admissible solutions, or the region of definition. It must be remembered that the region of feasible solutions satisfies the conditions of non-negativity ( x j 0, j = 1, 2, …, n). The coordinates of any point belonging to the domain of definition are a valid solution to the problem.
To find the extreme value of the objective function when solving LP problems graphically, a gradient vector is used, the coordinates of which are partial derivatives of the objective function, i.e.
This vector shows the direction of the fastest change in the objective function. Direct line with 1 x 1 + with 2 x 2 = f(x 0), perpendicular to the gradient vector, is the level line of the objective function. At any point on the level line, the objective function takes the same value. Let us equate the target function to a constant value "A". Changing the value of “a”, we obtain a family of parallel lines, each of which is a level line of the objective function.
An important property of the level line of a linear function is that when the line is parallelly shifted in one direction, the level only increases, and when shifted in the other direction, it only decreases.
From a geometric point of view, in a linear programming problem, we are looking for such a corner point or a set of points from an admissible set of solutions at which the highest (lowest) level line is reached, located further (closer) than the others in the direction of fastest growth.
The graphical method for solving the ZLP consists of the following steps.
1. A polygonal region of admissible solutions (ADS) of the PLP is constructed.
2. The gradient vector of the objective function (TF) is constructed at some point x 0 belonging to the ODR:
3. The level line c 1 x 1 + c 2 x 2 = a (a is a constant value) - a straight line perpendicular to the gradient vector - moves in the direction of this vector in the case of maximizing f (x 1, x 2) until until it leaves the ODR. The limit point (or points) of the area during this movement is the maximum point f(x 1, x 2).
4. To find the coordinates of the maximum point, it is enough to solve two straight line equations obtained from the corresponding restrictions and giving the maximum point at the intersection. The value f(x 1, x 2) found at the resulting point is the maximum.
When minimizing (maximizing) the function f(x 1, x 2), the level line moves in the direction opposite to the gradient vector. If the straight line corresponding to the level line does not leave the ODR during its movement, then the minimum (maximum) of the function f(x 1, x 2) does not exist.
If the level line is parallel to any functional constraint of the problem, then the optimal value of the CF will be achieved at any point of this constraint lying between two optimal corner points, and, accordingly, any of these points is the optimal solution of the ZLP. Possible situations for graphically solving LP problems are presented in Table. 1.3.
Table 1.3
| № | Type of ODR | Type of optimal solution | Notes |
| Polygonal closed | Only decision | ||
| Only decision | |||
| Polygonal | CF is not limited from below | ||
| CF is not limited from above | |||
| Polygonal open | Only decision | ||
| Endless solutions | |||
| Line segment | Only decision |
Let's consider the graphical solution of linear programming problems using the following example.
Example 1.1. Planning the production of a sewing enterprise (problem about suits).
It is planned to release two types of suits - men's and women's. A woman's suit requires 1 m of wool, 2 m of lavsan and 1 person/day of labor. For a men's suit - 3.5 m of wool, 0.5 m of lavsan and 1 person/day of labor. In total there are 350 m of wool, 240 m of lavsan and 150 man/days of labor. It is necessary to determine how many suits of each type need to be made to ensure maximum profit, if the profit from the sale of a women's suit is 10 monetary units, and from a men's suit - 20 monetary units. It should be borne in mind that it is necessary to sew at least 60 men's suits.
Let us introduce the following notation: x 1 - the number of women's suits; x 2 – number of men's suits. The profit from the sale of women's suits is 10x 1, and from the sale of men's suits - 20x 2, i.e. it is necessary to maximize the objective function:
10x 1 + 20x 2
The task constraints have the form:
x 1 + x 2 150,
2 x 1 + 0.5x 2 240,
x 1 + 3.5x 2 350,
x 2 60,
x 1 0.
The first labor limitation is x 1 + x 2 150. The straight line x 1 + x 2 = 150 passes through the points (150; 0) and (0; 150) (Fig. 1.2).
The second constraint on lavsan is 2 x 1 + 0.5x 2 240. The straight line 2 x 1 + 0.5x 2 = 240 passes through the points (120; 0) and (0; 480). Third limitation on wool x 1 + 3.5x 2 350. Let's add a fourth limitation on the number of men's suits x 2 60. The solution to this inequality is the half-plane lying above the straight line x 2 = 60. In Fig. 1.3 the region of feasible solutions is shaded. To determine the direction of movement towards the optimum, we construct a gradient vector, the coordinates of which are partial derivatives of the objective function, i.e.
To construct such a vector, you need to connect the point (10;20) to the origin. When maximizing the objective function, it is necessary to move in the direction of the gradient vector, and when minimizing, in the opposite direction. For convenience, you can construct a vector proportional to the vector . So, in Fig. 1.4 shows the gradient vector (30;60).
To determine the direction of movement towards the optimum, we construct a gradient vector, the coordinates of which are partial derivatives of the objective function, i.e.
In our case, we will move the level line until it leaves the region of feasible solutions. At the extreme, corner point, the maximum of the objective function is achieved. To find the coordinates of this point, it is enough to solve two straight line equations obtained from the corresponding restrictions and giving a maximum point at the intersection:
x 1 + 3.5x 2 = 350,
x 1 + x 2 = 150.
From here it is easy to write down the solution to the original ZLP: max f(x)= 2300 and is achieved at x 1 = 70 and x 2 = 80 (see Fig. 1.4).
1.3.TECHNOLOGY FOR SOLVING LINEAR PROGRAMMING PROBLEMS USING THE SOLUTION SEARCH ADD-ON IN EXCEL ENVIRONMENT
1.3.1. General information about working with the Excel spreadsheet
Let's consider some aspects of working with the Excel spreadsheet processor, which will simplify the calculations necessary to solve optimization problems. A table processor is a software product designed to automate the processing of tabular data.
Excel Screen Elements. After launching Excel, a table appears on the screen, the appearance of which is shown in Figure 1.5.
This image is called a worksheet. It is a grid of rows and columns, the intersections of which form rectangles called cells. Worksheets are designed for entering data, performing calculations, organizing an information base, etc. The Excel window displays the main program elements: title bar, menu bar, status bar, window control buttons.
Working with formulas. Spreadsheet programs use formulas to perform many different calculations. Using Excel, you can quickly create a formula. The formula consists of three main parts:
1) equal sign;
2) a set of values or references in the cells with which calculations are performed;
3) operators.
4) If there is no equal sign, then Excel interprets the data not as a formula, but as data entered into a cell. Formulas can be entered directly into a cell or into the formula bar - either text or numbers. In this case, you need to perform the following steps:
· select the cell that should contain the formula and enter the sign (=);
· enter an operator or action sign;
· select another cell included in the formula;
· press the Enter key.
The entered formula will appear in the formula bar, and the calculation result will appear in the cell.
Using functions in formulas. To make entering formulas easier, you can use Excel functions. Functions are formulas built into Excel. Excel contains many formulas. They are grouped into different types: logical, mathematical, engineering, statistical, etc.
To activate a particular formula, click the Insert, Functions buttons. The Function Wizard window that appears on the left contains a list of function types. After selecting a type, a list of the functions themselves will be placed on the right. A function is selected by clicking on the corresponding name.
Different functions perform different types of calculations according to certain rules. When a function is a single object in a worksheet cell, it begins with a (=) sign, followed by the name of the function, and then the arguments to the function, enclosed in parentheses.
Find a Solution is an Excel add-in that allows you to solve optimization problems. If the Search for Solution command is not available in the Tools menu, then you need to download this add-on. Select the command Tools => Add-ons and activate the Search for a solution add-on. If this add-in is not in the Add-Ins dialog box, then you need to go to the Windows Control Panel, click on the Add or Remove Programs icon and use the Excel (or Office) installer to install the Find a Solution add-in.
After selecting the commands Tools => Search for a solution, the Search for a solution dialog box will appear.
There are three main options in the Find Solution dialog box;
Set target cell.
Changing cells.
Restrictions.
First you need to fill out the Set target cell field. In all tasks for the Find a Solution tool, the result in one of the worksheet cells is optimized. The target cell is related to other cells in that worksheet using formulas. The Find Solution tool uses formulas that produce a result in the target cell to test possible solutions. You can choose to find the smallest or largest value for the target cell, or set a specific value.
The second important option in the Find Solution tool is the Changing Cells option. Here you specify the cells whose values will be changed in order to optimize the result in the target cell. You can specify up to 200 changeable cells to find a solution. There are two main requirements for these cells: they must not contain formulas, and changes in their values must be reflected in a change in the result in the target cell. In other words, the target cell depends on the cells being modified.
The third parameter that must be entered on the Search for a solution tab is restrictions.
To solve the problem you need:
1) indicate the addresses of the cells in which the result of the decision will be placed (changeable cells);
2) enter the initial data;
3) introduce a dependence for the objective function;
4) introduce dependencies for restrictions,
5) run the Search for solutions command;
6) assign a cell to the target function (set target cell);
7) introduce restrictions;
8) enter parameters for solving the LLP.
Let's consider the solution technology using the conditions of Example 1.1 (the suit problem).
Economic and mathematical model of the problem
Let x 1 be the number of women's suits; x 2 - the number of men's suits,
10 x x 1 + 20 x x 2 max
The task constraints have the form:
x 1 + x 2 150 - labor limitation;
2 x x 1 + 0.5 x X 2,240 - limit on lavsan;
x 1 + 3.5 x x 2 350 - wool limit;
x 2 60 - limit on men's suits;
x 1 0 - restriction on women's suits.
1. Specify the addresses of the cells in which the solution result will be placed (changeable cells).
Denote by x 1 , x 2 the number of suits of each type. In our problem, the optimal values of the vector = (x 1, x 2) will be placed in cells A2:B2, the optimal value of the objective function - in cell S3.
2. Enter the initial data.
Enter the initial task data as shown in Fig. 1.6.
3. Introduce a dependency for the objective function.
· Place the cursor in the “NW” cell, the cell will be selected.
· Place the cursor on the Function Wizard button located on the toolbar.
· Enter Enter. The Function Wizard step 1 of 2 dialog box appears on the screen.
· In the Functions window, select the SUMPRODUCT line (Fig. 1.7). On the screen
· the SUMPRODUCT dialog box appears (Fig. 1.8).
· Enter in the Array 1 line A2:B2.
· Enter AZ:VZ in the Array 2 line.
Array 1 will be used when entering dependencies for constraints, so an absolute reference must be made to this array. In Fig. Figure 1.9 shows that a function has been introduced into cell SZ.
5. Enter dependencies for constraints (Figure 1.10).
· Place the cursor in cell NW.
· On the toolbar there is a Copy to Clipboard button.
· Place the cursor in cell C4.
· Place the cursor in cell C5.
· On the toolbar, the Paste from Clipboard button.
· Place the cursor in the Sat cell.
· On the toolbar, the Paste from Clipboard button.
· Place the cursor in cell C7.
· On the toolbar, click the Paste from Clipboard button. (The contents of cells C4-C7 must be checked. They must contain information, as shown for example in Fig. 1.11; the contents of cell C5 are presented as an example.)
· In the Menu line, place the mouse pointer on Service. In the expanded menu, select the Search for solution command. The Search for Solution dialog box appears (Fig. 1.12).
5. Run the Search for solution command.
6. Assign a cell to the target function (set the target cell), indicate the addresses of the cells to be changed.
· Place the cursor in the Set target cell line.
· Enter the address of cell $С$3.
· Enter the type of objective function depending on the conditions of your problem. To do this, note whether the objective function is equal to the Maximum value or the Minimum value.
· Place the cursor in a row by changing cells.
· Enter the addresses of the required variables A$2:B$2 (Fig. 1.13).
7. Introduce restrictions.
· Place the mouse pointer on the Add button. The Add Constraint dialog box appears.
· Enter a restriction sign.
· In the Restriction line, enter the address $D$4 (Fig. 1.14).
· Place the mouse pointer on the Add button. The Add Restriction dialog box will reappear.
· Enter the remaining constraints of the problem using the algorithm described above.
· After entering the last restriction, click on the OK button. The Search for Solution dialog box with the entered conditions will appear on the screen (Fig. 1.15).
8. Enter parameters for solving the linear programming problem.
· In the dialog box, place the mouse pointer on the Options button. The Solution Search Options dialog box will appear on the screen (Fig. 1.16).
· Check the boxes in the Linear model (this will ensure the use of the simplex method) and Non-negative values.
· Place the mouse pointer on the OK button. The Search for Solution dialog box will appear on the screen.
· Place the mouse pointer on the Run button.
After a short time, the solution search results dialog box and the original table with filled cells AZ:VZ for values x i and cell SZ with the maximum value of the objective function will appear (Fig. 1.17).
If you specify the report type Stability, you can get additional information about the optimal solution (Fig. 1.18).
As a result of solving the problem, the answer was received: it is necessary to sew 70 pieces. women's suits and 80 pcs. men's suits to get a maximum profit of 2300 USD.
1.4. DUALITY IN LINEAR PROGRAMMING PROBLEMS. ANALYSIS OF OBTAINED OPTIMAL SOLUTIONS
In 1975, our compatriot L.V. Kantorovich was awarded the Nobel Prize in Economics (together with the American economist T. Koopmans) for developing the theory of optimal use of resources (see Appendix 1).
Closely related to every linear programming problem is another linear problem called the dual; the original problem is called the original, or direct. The connection between the original and dual problems lies, in particular, in the fact that the solution of one of them can be obtained directly from the solution of the other.
The variables of the dual problem y i are called objectively determined estimates, or dual estimates, or “prices” of resources, or shadow prices.
Each of the dual pair problems is actually an independent linear programming problem and can be solved independently of the other.
The dual problem in relation to the original one is composed according to the following rules:
1) the objective function of the original problem is formulated as a maximum, and the objective function of the dual problem is formulated as a minimum, while in the maximum problem all inequalities in the functional constraints have the form (), in the minimum problem they have the form ( );
2) matrix A, composed of coefficients for unknown constraints in the system of the original problem, and a similar matrix A T in the dual problem are obtained from each other by transposing;
3) the number of variables in the dual problem is equal to the number of functional constraints in the original problem, and the number of restrictions in the system of the dual problem is equal to the number of variables in the original one;
4) the coefficients for the unknowns in the objective function of the dual problem are the free terms in the system of constraints of the original problem, and the right-hand sides in the restrictions of the dual problem are the coefficients for the unknowns in the objective function of the original; j 0.
The two problems presented form a pair of symmetric dual problems. The main statements about mutually dual problems are contained in the following two theorems.
First duality theorem. For mutually dual problems, one of the mutually exclusive cases occurs.
1. In the direct and dual problems there are optimal solutions,
in this case, the values of the objective functions on the optimal solutions
match
2. In the direct problem, the admissible set is not empty, and the objective function on this set is not bounded from above. In this case, the dual problem will have an empty admissible set.
3. In a dual problem, the admissible set is not empty, and the objective function on this set is not bounded from below. In this case, the admissible set of the direct problem turns out to be empty.
4. Both of the problems under consideration have empty admissible sets.
Second duality theorem (complementary non-rigidity theorem). Let = ( x 1 , x 2,..., x n) is an admissible solution to the direct problem, a = (y 1,y 2,...,y t) is an admissible solution to the dual problem. In order for them to be optimal solutions to the direct and dual problems, respectively, it is necessary and sufficient that the following relations hold:
Conditions (1.4) and (1.5) allow, knowing the optimal solution of one of the mutually dual problems, to find the optimal solution of another problem.
Let us consider another theorem, the conclusions of which will be used further.
Estimation theorem. The values of the variables y i in the optimal solution of the dual problem represent estimates of the influence of the free terms b i of the system of constraints (inequalities) of the direct problem on the value
By solving the ZLP using the simplex method, we simultaneously solve the dual ZLP. The variables of the dual problem y i are called objectively determined estimates.
Let us consider the economic interpretation of the dual problem using the carpet problem as an example.
Example 1 .2. Using the statement of the carpet problem, complete the following tasks.
1. Formulate an economic-mathematical model of the problem of carpets for the maximum total cost of production, using the data in Table. 1.1.
2. Using the Search for a solution, find a production plan at which the total cost of production will be maximum.
3. Formulate an economic-mathematical model of the dual problem to the carpet problem.
4. Find the optimal plan for the dual problem, using duality theorems, explain the equality to zero of X 1 and X 4.
5. Using the Solution Search protocols, perform an analysis of the resulting optimal solution to the original problem.
6. Determine how the total cost and production plan will change when the pipe service life increases by 12 units.
1. Let us formulate an economic and mathematical model of the problem.
Let us denote by X 1, X 2, X 3, X 4 the number of carpets of each type. The objective function has the form
F(X) = ZX 1 + 4X 2 + ZX 3 + X 4 max,
and resource limitations
7Х 1 + 2Х 2 + 2Х 3 + 6X 4 80,
5Х 1 + 8Х 2 + 4 X 3 + ZH 4 480,
2X 1 + 4 X 2 + X 3 + 8X 4 130,
X 1, X 2, X 3, X 4 0.
2. Search for the optimal release plan.
We will solve the problem using the Excel add-in Search for a solution. The technology for solving the problem was discussed in detail in the costume problem. In our problem, the optimal values of the vector X = (X 1, X 2, X 3, X 4) will be placed in cells VZ:EZ, the optimal value of the objective function - in the cell F4.
Let's enter the initial data. First, we describe the target function using the function - SUMPRODUCT (Fig. 1.19). And then we will enter data for the left parts of the restrictions. In the Search for a solution, we will enter the direction of the objective function, the addresses of the sought variables, and add restrictions. The Search for Solution dialog box with the entered conditions will appear on the screen (Fig. 1.20).
After entering the parameters for solving the problem, click the Execute button. A message will appear on the screen that a solution has been found (Fig. 1.21).
The resulting solution means that the maximum income is 150 thousand rubles. a factory can receive 30 carpets of the second type and 10 carpets of the third type upon production. In this case, the resources “labor” and “equipment” will be fully used, and out of 480 kg of yarn (resource “raw materials”), 280 kg will be used.
Creating a report based on the results of searching for a solution. Excel allows you to present the results of the search for a solution in the form of a report (Table 1.4). There are three types of such reports:
· Results (Answer). The report includes the initial and final values of the target and modified cells, and additional information about restrictions.
· Stability (Sensitivity). A report containing information about the sensitivity of a solution to small changes in the cells being modified or in the constraint formulas.
· Limits. In addition to the source and destination values of the affected and target cells, the report includes upper and lower bounds on the values that the influencing cells can accept if the constraints are met.
Let us first consider the simplest case, when exactly two variables are included in the LLP:
Each of the inequalities (a)-(b) of the system of constraints of problem (3.8) geometrically defines a half-plane, respectively, with boundary straight lines, X 1 =0 and X 2 =0. Each of the boundary lines divides the plane x 1 Ox 2 into two half-planes. All solutions to the original inequality lie in one of the formed half-planes (all points of the half-plane) and, therefore, substituting the coordinates of any of its points into the corresponding inequality turns it into a true identity. Taking this into account, the half-plane in which the solutions to the inequality lie is determined, i.e. by selecting any point from any half-plane and substituting its coordinates into the corresponding inequality. If an inequality holds for a given point, then it holds for any other point from the same half-plane. Otherwise, the solutions to the inequality lie in another half-plane.
If the system of inequalities (a)-(b) is consistent, then the domain of its solutions is the set of points belonging to all the indicated half-planes. Since the set of intersection points of these half-planes is convex, the domain of admissible solutions to problem (3.8) is a convex set, which is called a solution polygon (the previously introduced term “solution polyhedron” is usually used if n 3). The sides of this polygon lie on straight lines, the equations of which are obtained from the original system of constraints by replacing the inequality signs with exact equality signs.
Thus, the initial ZLP consists of finding a point in the decision polygon at which the objective function F takes on the maximum (minimum) value.
This point exists when the solution polygon is not empty and the objective function on it is bounded from above. Under the specified conditions, at one of the vertices of the solution polygon, the objective function takes on the maximum value. To determine this vertex, construct a level line L: c 1 x 1 +c 2 x 2 =h (where h is some constant), perpendicular to the gradient vector and passing through the solution polygon, and move it parallel along the gradient vector until until it passes through its last common point of intersection with the solution polygon (when constructing a gradient vector, a point (c 1 ; c 2) is laid out in the x 1 Ox 2 plane and a directed segment is drawn to it from the origin of coordinates). The coordinates of the specified point determine the optimal plan for this task.
Summarizing all of the above, we present an algorithm for the graphical method of solving the ZLP.
Algorithm for the graphical method of solving the ZLP
1. Construct a polygon of solutions specified by the system of restrictions of the original ZLP.
2. If the constructed polygon of solutions is an empty set, then the original ZLP has no solutions. Otherwise, construct a gradient vector and draw an arbitrary level line L, moving which, when solving a maximum problem, in the direction of the vector (or in the opposite direction for a minimum problem) to determine the extreme point of the solution polygon, where the maximum (minimum) of the objective function of the problem is achieved .
3. Calculate the coordinates of the found optimal point by solving the system of equations of two boundary lines intersecting in it.
4. By substituting the found optimal solution into the objective function of the problem, calculate its optimal value, i.e.: .
When graphically constructing the set of admissible solutions of the PLP (solution polygon), the following situations are possible.
Mathematical modeling in operations research is, on the one hand, a very important and complex process, and on the other, a process that is practically impossible to scientifically formalize. Note that repeated attempts to identify general principles for creating mathematical models have led either to the declaration of recommendations of a very general nature, difficult to apply to solve specific problems, or, conversely, to the emergence of recipes that are actually applicable only to a narrow range of problems. Therefore, it seems more useful to become familiar with the technique of mathematical modeling using specific examples.
Linear programming problems can be solved using the following methods:
Floyd's algorithm;
Dijkstra's algorithm on graphs;
graphic method;
simplex table method, etc.
Algorithm for solving linear programming problems using Dijkstra's method on graphs.
In the simplest implementation, an array of numbers can be used to store numbers d[i], and an array of Boolean variables can be used to store the membership of an element in the set U.
At the beginning of the algorithm, the distance for the initial vertex is set to zero, and all other distances are filled with a large positive number (greater than the maximum possible path in the graph). The flags array is filled with zeros. Then the main loop starts.
At each step of the cycle, it is necessary to find a vertex U with a minimum distance and a flag equal to zero. Then you need to set the flag in it to 1 and check all the vertices U adjacent to it. If the distance is greater than the sum of the distance to the current vertex and the length of the edge, then you need to reduce it. The cycle ends when the flags of all vertices become equal to 1, or when all vertices have a flag of 0. The latter case is possible if and only if the graph G is not connected.
A way to solve linear programming problems using the graphical method.
The graphical method for solving a linear programming problem is based on the geometric interpretation of a linear programming problem and is used mainly when solving problems in two-dimensional space and only some problems in three-dimensional space, since it is quite difficult to construct a solution polyhedron that is formed as a result of the intersection of half-spaces. It is generally impossible to depict a problem in a space of dimensions greater than three graphically.
Let the linear programming problem be specified in a two-dimensional space, that is, the constraints contain two variables.
The minimum value of the function is determined by formula (1).
(1)
The restrictions are represented by formulas (2) and (3).
(2)
(3)
Let system (2) under condition (3) be consistent. Each of the inequalities from systems (2) and (3) defines a half-plane with boundary lines represented by formula (4):
Linear function (1) for fixed values of Z is the equation of a straight line: 
It is necessary to construct a polygon of solutions to the constraint system (2) and the graph of the linear function (1) at Z=0. Then the posed linear programming problem can be given the following interpretation:
Find the point of the solution polygon at which the line 
the reference and function Z reaches a minimum.
Values 
decrease in the direction of the vector 
, therefore the straight line Z=0 must be moved parallel to itself in the direction of the vector N.
If the solution polygon is bounded, then the straight line becomes a reference line twice with respect to the solution polygon (at points B and E), with the minimum value at point E. Coordinates of the point 
must be found by solving the system of equations of lines DE and EF.
If the solution polygon is an unbounded polygonal area, then two cases are possible.
Case 1. Direct 
, moving in the direction of vector N or opposite to it, constantly intersects the solution polygon and is not a support to it at any point. In this case, the linear function is not bounded on the solution polygon either from above or from below.
Case 2. The straight line, while moving, nevertheless becomes a support relative to the solution polygon. Then, depending on the type of domain, a linear function can be bounded from above and unbounded from below, bounded from below and unbounded from above, or bounded from both below and above.
To solve this problem, the simplex method, the most well-known and widely used in practice for solving linear programming problems, was chosen. Despite the fact that the simplex method is a fairly effective algorithm that has shown good results in solving applied linear programming problems, it is an algorithm of exponential complexity.
The simplex method of linear programming problems is based on the transition from one reference plan to another, in which the value of the objective function increases or decreases.
Before compiling a simplex table, the problem must be transformed, the system of constraints brought to an acceptable basic form, with the help of which basic variables must be excluded from the objective function as shown in Figure 1.
Figure 1 – Initial transformation of the constraint system
Here, for the definiteness of the notation, it is assumed that the variables X1, X2, ..., Xr can be taken as basic variables and that b1, b2,..., br ≥ 0 (the corresponding basic solution is the reference one).
To compile a simplex table in all equalities in the problem statement, terms containing variables are transferred to the left side, free ones are left on the right, i.e. the problem is written in the form of a system of equalities as shown in Figure 2.
Figure 2 – Transformation of the system of inequalities
The algorithm for moving to the next table is as follows:
the last row (index) of the table is looked through and among the coefficients of this row (excluding the column of free terms) the smallest negative number is selected when finding max, or the largest positive number when searching for min. If there is none, then the original basic solution is optimal and this table is the last;
the table column corresponding to the selected negative (positive) coefficient in the last row is looked through - the key column, and positive coefficients are selected in this column.
If there are none, then the objective function is unlimited in the range of permissible values of the variables and the problem has no solutions;
Among the selected coefficients of the column, the one for which the absolute value of the ratio of the corresponding free term (located in the column of free terms) to this element is minimal is selected. This coefficient is called the resolving coefficient, and the line in which it is located is key;
in the future, the basic variable corresponding to the row of the resolving element must be transferred to the category of free, and the free variable corresponding to the column of the resolving element must be entered into the number of basic ones.
A new table is built containing the new names of the basic variables:
Let's divide each element of the key line (excluding the column of free terms) into a resolving element and write the resulting values in the line with the changed basic variable of the new simplex table.
the string of the allowing element is divided by this element and the resulting string is written to a new table in the same place.
in the new table, all elements of the key column = 0, except for the cutting column, which is always equal to 1.
a column that has a 0 in its key row will be the same in the new table.
a row that has a 0 in its key column will be the same in the new table.
the result of transforming the elements of the old table is written into the remaining cells of the new table, as shown in Figure 3.
Figure 3 – Compiling a new element in a simplex table
To solve the problem of this course work, the direction of the problem was chosen for the optimal distribution of funds in the enterprise. The optimal plan or optimal solution to a linear programming problem is a plan in which the target value will increase (decrease).
After analyzing the collected information, a linear programming problem was compiled for workshop No. 8 at NefAZ OJSC. On the painting conveyor on which parts are painted. It is necessary to paint the optimal number of parts in one work shift in order to maximize profits.
To further solve the problem, it is necessary to create a statement of the problem and a mathematical model of the problem.
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.
The production of both products requires costs for machining, raw materials and labor. Each unit of product A requires 3 hours of machining, 16 units of raw materials and 6 units of labor. 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.
| Resource name | A | B | Volume of resources |
|---|---|---|---|
| Machining hours | 3 | 10 | 330 |
| Units of raw materials | 16 | 4 | 400 |
| Units of labor | 6 | 6 | 240 |
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 solution of the problem
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 is the 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 is the number of units of product A produced in the next month.
x 2 is the number of units of product B produced in the next month.
It is very important to clearly define all variables; Pay special 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 2500x 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 = 2500x 1 +3500x 2.
Nikolay strives to maximize this indicator. Thus, the objective function in our model is:
Stage. 3. Define constraints
Constraints are a system of linear equations and/or inequalities that limit the values of the desired 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 and x 2) will therefore be limited by the fact that the amount of resources required 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 3x 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 3x 1 + 10x 2. This total machine time cannot exceed 330 hours. Mathematically this is written as follows:
3x 1 +10x 2 ≤330
Similar considerations apply to raw materials and labor, which allows us to write down two more restrictions:
16x 1 +4x 2 ≤400
6x 1 +6x 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.
\[\left\( (\begin(array)()
(3(x_1) + 10(x_2) \le 330)\\
(16(x_1) + 4(x_2) \le 400)\\
(6(x_1) + 6(x_2) \le 240)\\
((x_1)\ge 0)\\
((x_2)\ge 12)
\end(array)) \right.\]
Solution using the simplex method
The simplex method is a universal method for solving the problem of linear programming, since it allows you to solve almost any problem presented in canonical form.
The idea of the simplex method is that, starting from a certain reference solution, a sequentially directed movement is carried out along the reference solutions of the system to the optimal reference solution. Since the number of support solutions is finite, the optimal solution will be found after a finite number of steps.
The simplex method algorithm can be described as follows:
- Bring the problem to canonical form
- Find a non-negative basic solution to the system of constraints
- Calculate estimates of free variables using the formula:
\[(\Delta)_j = \sum\limits_(i = 1)^r ((c_i)(h_(ij)) – (c_j)) ,\;j = \overline (1,n) ,\]
where h ij are the coefficients of the free variable x j,
c i – coefficients for the basic variables in the objective function,
c j – coefficients of the free variable in the objective function,
- Check the found support solution for optimality:
a) if all estimates are \((\Delta)_j \ge 0\) , then the solution found is optimal and the problem is solved;
b) if at least one estimate \((\Delta)_j< 0\) , а при соответствующей переменной x j нет ни одного положительного коэффициента, то задача не имеет оптимального решения из-за ограниченности целевой функции
c) if at least one estimate is \((\Delta)_j< 0\) , а при соответствующей переменной x j есть хотя бы один положительный коэффициент, то решение не оптимально и его можно улучшить переходом к новому базису. Если отрицательных оценок несколько,то в базис ввести переменную с наибольшей по абсолютной величине отрицательной оценкой.
Let's reduce the problem to canonical form.
The complete linear programming model for Nikolai's production problem can be written as:
\[\left\( (\begin(array)()
(3(x_1) + 10(x_2) + (x_3) = 330)\\
(16(x_1) + 4(x_2) + (x_4) = 400)\\
(6(x_1) + 6(x_2) + (x_5) = 240)\\
(-(x_2) +(x_6) = 12)\\
((x_j) \ge 0\;j = \overline (1,n))
\end(array)) \right.\]
| B.p. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | b i |
|---|---|---|---|---|---|---|---|
| x 3 | 3 | 10 | 1 | 0 | 0 | 0 | 330 |
| x 4 | 16 | 4 | 0 | 1 | 0 | 0 | 400 |
| x 5 | 6 | 6 | 0 | 0 | 1 | 0 | 240 |
| x 6 | 0 | -1 | 0 | 0 | 0 | 1 | 12 |
\[\bar(x)_(\text(support))=(0;0;330;400;20;12)\]
Let's check this solution for optimality by finding free variables in the simplex table. The calculations are presented in the file lp_simplex.xlsx.
This solution is not optimal because there are negative values in the bottom line. Since there are positive coefficients, the solution can be improved; to do this, we introduce the variable x 2 into the basis. Since there are several positive coefficients in the x2 column, we determine the ratio of the free term b i to the corresponding coefficients in this column and select the smallest result.
Let's transform the table and repeat the calculation.
This solution is not optimal because there are negative values in the bottom line. Since there are positive coefficients, the solution can be improved; to do this, we introduce the variable x 1 into the basis.
The resulting solution (10; 30) is optimal.
Solution using Excel and LibreOffice
The solution in Excel is carried out using the “Search for Solution” add-in, which also uses the simplex method.
Similar problems can be solved using the Solver in LibreOffice. It should be noted that in LibreOffice there are no restrictions on the number of variables, unlike Excel.
Solution in R
The following packages can be used to solve linear programming problems in GNU R:
- lpSolve
- linprog
The second package is an add-on to the first and allows you to display more diagnostic information
Solution with lpSolve package
library(lpSolve) # Included library f.obj<- c(2500, 3500) # Описали целевую функцию names(f.obj) <-c("A","B") a.mat<-rbind(c(3,10), # матрица c(16,4), # коээфициентов c(6,6), # при ограничениях c(1,0), c(0,1)) a.dir<-c("<=","<=","<=",">=",">=") b.vec<-c(330,400,240,0,12) # вектор ограничений result<-lp ("max", f.obj, a.mat, a.dir, b.vec)Result
result ## Success: the objective function is 130000 result$solution ## 10 30Thus, the maximum value of the objective function is 130000 and it is achieved when x 1 and x 2 are equal to 10 and 30, respectively.
Solution with linprog package
Because the package linprog is an addition to the previous package, then the variables are already all initialized.
Library(linprog) ## Warning: package "linprog" was built under R version 3.2.2 (result<-solveLP(f.obj, b.vec, a.mat, TRUE,const.dir=a.dir,lpSolve=T)) ## ## ## Results of Linear Programming / Linear Optimization ## (using lpSolve) ## ## Objective function (Maximum): 130000 ## ## Solution ## opt ## A 10 ## B 30 ## ## Constraints ## actual dir bvec free ## 1 330 <= 330 0 ## 2 280 <= 400 120 ## 3 240 <= 240 0 ## 4 10 >= 0 10 ## 5 30 >= 12 18
The result was the same; additionally, information on free resources was displayed. Thus, GNU R provides a fairly convenient mechanism for solving linear programming problems.
In contact with
If you need to solve a linear programming problem using simplex tables, then our online service will be of great help to you. The simplex method involves sequentially searching through all the vertices of the range of acceptable values in order to find the vertex where the function takes an extreme value. At the first stage, some solution is found, which is improved at each subsequent step. This solution is called basic. Here is the sequence of actions when solving a linear programming problem using the simplex method:
First step. In the compiled table, first of all, you need to look at the column with free members. If there are negative elements in it, then it is necessary to move to the second step, if not, then to the fifth.
Second step.
At the second step, it is necessary to decide which variable to exclude from the basis and which to include in order to recalculate the simplex table. To do this, look through the column with free terms and find a negative element in it. The line with a negative element will be called leading. In it we find the maximum negative element in modulus, the corresponding column is the slave one. If there are negative values among the free terms, but there are none in the corresponding row, then such a table will not have solutions. The variable in the leading row located in the column of free terms is excluded from the basis, and the variable corresponding to the leading column is included in the basis.
| Table 1. | basic variables | Free members under restrictions | |||||
| x 1 | x 2 | ... | Non-basic variables | ... | x l | ||
| x n | x n+1 | b 1 | a 11 | ... | a 12 | ... | a 1l |
| a 1n | x n+2 | b 2 | a 21 | ... | a 22 | ... | a 2l |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| a 2n | x n+r | b2 | a r1 | ... | a r2 | ... | a rl |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| arn | x n+m | b m | a m1 | ... | a m2 | ... | a ml |
| a mn | F(x)max | F 0 | -c 1 | ... | F 0 | ... | -c 2 |
-c n
Third step.
Fifth step.