Presentation of the graphical method of linear programming. Presentation linear programming
Introduction
Linear programming as a branch of operations research has a history of almost forty years. Implementation computer technology gave a significant impetus to research in this area of mathematics. A number of algorithms for solving linear programming problems were developed, and in subsequent years programs and software packages were created primarily for mainframe computers. The bulk of the literature on. linear programming in our country was released in the 60s and 70s. Research in this area (both theoretical and applied) continues to this day.
Methods linear programming have proven to be very effective for solving some problems in the field of operations research. We understand the word “programming” as planning, and this determines the nature of the applications under consideration. The basic ideas of linear programming arose during the Second World War in connection with the search for optimal strategies in conducting military operations. Since then, they have found wide application in industry, commerce and government - both locally and nationally. These methods can solve many (though not all) problems associated with effective use limited resources.
Mathematical methods and models are well known, common and used under various names - mathematical methods in decision making; operations research methods; economic and mathematical methods; methods of economic cybernetics; methods of optimal control, applied mathematics in economics and production organization, etc. In many publications on this topic(more or less all-encompassing) they are considered in certain combinations.
Operations research is a scientific discipline that deals with the development and practical application of methods for the most effective management of various organizational systems.
Management of any system is implemented as a process that obeys certain laws. Their knowledge helps to determine the conditions necessary and sufficient for the implementation of this process. To do this, all parameters characterizing the process and external conditions must be quantified and measured. Consequently, the goal of operations research is to provide quantitative justification for decisions made regarding the organization of management.
The goal of any modeling is to study the object, first at a qualitative level, and then, as information accumulates and the model develops, at increasingly more accurate quantitative levels.
These considerations can be illustrated with a simple example. There was (and still is) the “probability theory” method as a broad class mathematical models, operating with the concepts of “probability”, “random event”, “random variable”, “mathematical expectation (average value) random variable", "dispersion (scattering)", etc. At the border of the 19th and 20th centuries. a new object appears - a switched system telephone communication, with which the concepts of “connection request”, “failure”, “connection waiting time”, “switching” and other characteristics of the system are associated.
In the 20s A. K. Erlang combined these method and object; As a result, a mathematical probability-theoretic model of processes in switched telephone networks was created, operating with the concepts of “request flow”, “average waiting time”, “average queue length for service”, “waiting time dispersion”, “probability of failure”, etc. The further development of this scientific direction showed the fruitfulness of the conceptual basis of this model and its wide design possibilities. The model developed into a method for studying complex systems - “queuing theory”, the terminology and conceptual basis of which were abstracted from associations with telephone networks and acquired a general theoretical character. And now new models can be built by applying the theory of queuing to other objects (production processes, computer operating systems, traffic flows, etc.).
Thus, on the one hand, the method is defined if a homogeneous set of models is developed, i.e., ways of considering various objects in one aspect, and on the other hand, the object is cognized the more deeply, the more models of the object are developed. At the same time, the dual nature of the model leads to the dualism of the conceptual base of modeling, including general (from the “method”) and specific (from the “object”) concepts.
Operations research is a set of applied mathematical methods used to solve practical organizational (including economic) problems. It is a complex scientific discipline. The range of problems studied by it is not sufficiently defined. Sometimes operations research is understood very broadly, including a number of purely mathematical methods, sometimes, on the contrary, very narrowly - as a practical technique for solving a strictly defined list of problems using economic and mathematical models.
The main method of operations research is a systematic analysis of targeted actions (operations) and an objective (in particular, quantitative) comparative assessment of the possible results of these actions.
Among the most important classes of operations research problems are problems of inventory management, resource allocation and assignment (distribution problems), queuing problems, equipment replacement problems, ordering and coordination (including scheduling theory), adversarial (for example, games), search problems and etc. Among the methods used are mathematical programming (linear, nonlinear, etc.), differential and difference equations, graph theory, Markov processes, game theory, theory of (statistical) solutions, pattern recognition theory and a number of others.
It is believed that operations research originated on the eve of the Second World War, when a group of specialists was created at a radar station in England to solve technical problems using mathematics. They focused on comparing the effectiveness of ways to solve problems and finding the optimal solution. The participation of representatives of different specialties in this group predetermined an integrated, or, as they now say, systematic approach. Currently, hundreds of research institutions and groups in dozens of countries are working in this direction. Operations Research Societies, united by the International Federation (IFRS), were organized.
Russian scientists L.V. Kantorovich, N.P. made a great contribution to the creation of a modern mathematical apparatus and the development of many areas of operations research. Buslenko, E.S. Ventzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin and many others.
Significant contributions to the formation and development of operations research were made by foreign scientists R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman and others.
Operations research methods, like any mathematical methods, always simplify and coarse the problem to one degree or another, reflecting nonlinear processes linear models, stochastic systems - deterministic, etc. Therefore, one should neither exaggerate the importance of quantitative methods of operations research, nor underestimate it by referring to examples bad decisions. There is a well-known paradoxical definition given by a prominent American specialist in this field
T. A. Saaty: “Operations research is the art of giving bad answers to those practical questions that are answered even worse by other means.”
CENTRAL INTERREGIONAL TECHNOLOGY SCHOOL OF INDUSTRY TECHNOLOGIES AND ENTREPRENEURSHIP
I approve
Deputy Director of Academic Affairs
" " 200 G .
EXERCISE
for course design
in the subject "Mathematical methods"
Student: Evgeniy Anatolyevich Sergeev.
Project topic: “Linear programming, solving problems using the simplex method.”
EXPLANATORY NOTE
- Introduction
- Theoretical part
- Practical part
Problems and their solutions:
Task one:
Solve the problem using the simplex method:
F = 2X1 +3X2 → max
3.1.2 Task two:
The company produces two types of products. Types of raw materials, their reserves, consumption rates of raw materials per y. That is, for each type of product, production profits from product sales are given in the table:
3.1.3. Task three:
The company produces 3 types of products, using 3 types of raw materials. Inventories of raw materials, consumption rates and profit from the sale of each product are shown in the table:
How should production be planned to maximize profits?
3.1.4. Task four:
To manufacture 4 types of products, 3 types of raw materials are used. Inventories of raw materials, consumption rates and profit from the sale of each product are shown in the table:
How should production be planned to maximize profits?
3. Conclusion
4. Bibliography
Chairman of the cycle commission/Baranov V.A.
Head of course project/Karpushkin A.G.
Assignment date: Completion date:
" " 2007 " " 2007
SIMPLEX METHOD
The simplex method was first proposed by the American scientist J. Danzig in 1949, however, back in 1939, the ideas of the method were developed by a Russian scientist
L V. Kantorovich.
The simplex method, which allows solving any linear programming problem, is universal. Currently, it is used for computer calculations, but simple examples using the simplex method can be solved manually.
To implement the simplex method - consistent improvement of the solution - it is necessary to master three basic
element:
A method for determining any initial acceptable
basic solution to the problem;
The rule of transition to the best (more precisely, not worse) solution;
Criterion for checking the optimality of the found solution.
To use the simplex method, the linear programming problem must be reduced to canonical form, i.e. the system of constraints must be presented in the form of equations.
Ordinary Jordan exceptions
Consider a system of m linear equations with n unknowns
a11 x1 + a12 x2 + … + a1n xn = b1,
am1 x1 + am2 x2 + … + amn xn = bm.
Let's write this system in the form of a table
a11…a1j…a1n |
||
……………….. |
||
ai1…aij…ain |
||
……………….. |
||
am1…amj…amn |
The ordinary Jordan elimination (OJE) step performed on a given table with a resolving element aij ≠ 0 with I resolving row and j resolving column is called the operation of solving the equation
bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn
relative to xj, substituting this solution into the original system and recording the newly obtained system in the form of a new table.
It is easy to check that the new table will look like
b11 b12 … a1j … b1n |
|||
b21 b22 … a2j … b2n |
|||
……………….. |
|||
Ai1 –ai2…1… -ain |
|||
……………….. |
|||
bm1 bm2 … amj … bmn |
where brs = ars aij - arj ais (i ≠ r, j ≠ s),
and all elements of the table must be divided by aij.
Thus, one step of Jordan elimination (JE) transforms the original table into a new one according to a scheme consisting of the following 5 rules:
1) the resolving element is replaced by one
2) the remaining elements of the resolution column j remain unchanged.
3) the remaining elements of the resolution string i change only their signs.
4) the remaining elements of brs are calculated using the formula brs = ars aij - arj ais
5) all elements of the new table are divided by the resolving element aij.
Example 1. For a table
Jordan exceptions allow us to go from a randomly taken Cartesian system of coordinate planes to new system, in which the coordinates of points are their deviations from a system of planes that is more interesting for a particular problem.
Modified Jordan exceptions
If the original system of equations ai1 x1 + ai2 x2 + … + ain xn = bi, where i = 1,m,
write in the form –ai1 (-x1) – ai2 (-x2) - … - ain (-xn) = bi
and make a table
which is obtained according to rules 1 - 5 of the OJI with the only change that rules 2 and 3 change roles:
1) the remaining elements of the permission string remain unchanged
2) the remaining elements of the resolution column change only their signs
Consider the system
2X1 + 3X2 – 5X3 = 16 = b1,
3X1 - 2X2 + 4X3 = 36 = b2,
5X1 + 7X2 – 11X3 = 44 = b3.
Let's write it in the form of a table
Extrema of a linear function
Let us consider a general linear programming problem. The basis of LP computational methods is the following fundamental theorem.
Theorem. If a linear programming problem has optimal solution
(in a bounded domain always, and in an unbounded domain depending on the boundedness of the function Z), then it coincides with at least one of the supporting solutions of the system of constraint equations.
According to this theorem, instead of studying an infinite set of feasible solutions in order to find the desired optimal solution among them, it is necessary to study only a finite number of reference solutions.
This theorem states that there is at least one reference optimal solution, however, problems may contain several reference optimal solutions (alternative optimum).
Hence, circuit diagram solving linear programming problems is as follows:
1. Using the LC, we find all the support solutions of the system.
a11 x1 + a12 x2 + … + a1n xn = b1,
……...................
ak1 x1 + ak2 x2 + … + akn xn = bk,
ak+1.1 x1 + ak+1.2 x2 + … + ak+1n xn ≤ bk+1 ,
……...................
am1 x1 + am2 x2 + … + amn xn ≤ bm .
2. Let us calculate for each of them the value of the function Z, determined by the relation.
Z = c1 x1 + c2 x2 + … + cn xn.
3. Let us choose an extremal Z from them.
It should be noted that there may be a very large number of support solutions, so it is necessary to carry out an orderly search of support solutions, achieving
each step of a monotonic change in the function Z.
This idea of sequential improvement of the solution is embedded in the main computational method for solving linear programming problems, called the simplex method.
Simplex method based on complete tables
Statement of the problem of determining the optimal product range
The enterprise can produce two types of products A and B, having for their production limited resources of cast iron and steel material in quantities of 350 and 392 kg, respectively, and equipment in the amount of 408 machine-hours. The data, presented in table form, characterizes the costs of each of the listed three types of resources for the manufacture of one product A and B.
It is necessary to determine how many products A and B the enterprise should produce in order to achieve the greatest profit.
Let us introduce the unknown unknowns X1 and X2, which denote the number of products A and B that the enterprise should produce.
Then mathematically the problem can be formulated as follows.
Among the set of non-negative solutions to the system of inequalities
14X1 + 5X2 ≤ 350, (1.1)
14Х1 + 8Х2 ≤ 392,
6Х1 + 12Х2 ≤ 408,
find a solution for which the function
Z = 10 X1 + 5 X2
reaches its greatest value.
Geometric solution to the problem
First of all, let us construct a region of feasible solutions corresponding to the system of inequalities.
To do this, replacing each of the inequalities with equality
14X1 + 5X2 = 350, (1st line),
14X1 + 8X2 = 392, (2nd line),
6X1 + 12X2 = 408, (3rd line),
build a boundary line. Taking into account that X1 ≥ 0 and X2 ≥ 0, we obtain a shaded part of the plane that forms the OABCD solution polygon (Fig. 1).
Then we build the level line 10X1 + 5X2 = 0 and the vector (10;5), which are mutually perpendicular. It is easy to show that the vector gives the direction of greatest increase in the linear function.
Really
Z0= 10X10 + 5X20 = 10 * 0 + 5 * 0 = 0,
ZA = 10X1A + 5X2A = 10 * 0 + 5 * 34 = 170,
ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 etc.
From all the level lines, we select two, of which one passes through point 0 and gives the min value of the function Z, and the other passes through point C and the function Z for it takes the max value. These level lines are called reference lines.
Rice. 1
Point C is formed by the first and second straight lines. Therefore, solving the system of equations
14Хl + 5Х2 = 350,
14X1 + 8X2 = 392,
find the coordinates of point C
X1 = 20, X2 = 14,
in this case Zmax = 10 * 20 + 5 * 14 = 270 rub.
Thus, the maximum profit is 270 rubles. will be received if the enterprise produces 20 products of type A and 14 products of type B.
Finding the maximum of a linear function
The basis of the simplex method for solving linear programming problems is, with some additions, the previously discussed method of sequential elimination, which is a set of convenient computational algorithms built on the sequential application of identical (simplex) transformations of a system of equations.
Adding to the left side of the inequalities
14X1 + 5X2 ≤ 350,
14Х1 + 8Х2 ≤ 392,
6Х1 + 12Х2 ≤ 408,
some non-negative quantity Yj ≥ 0 (i = 1, 2, 3), (1.2)
called the leveling or basis variable, let's turn them into equations:
X1 + 5X2 + U1 | |||
In this case, it can be shown that each solution to the system of inequalities (1.1) corresponds to a unique solution to the system of equations (1.3) and inequalities (1.2) and vice versa.
Each of the variables Y1, Y2, Y3 is included in only one equation and depends on the variables X1 and X2, which we call free.
System (1.3) corresponds to the initial admissible basis solution X1 = X2 = 0;
Y1 = 350; Y2 = 392; Y3 = 408 and Z = 0.
We perform the first identity transformation of the system of equations (1.3). We select the resolving column corresponding to the smallest negative element in the Z row, because it has been theoretically established that in this case we can expect, all other things being equal, a greater increase in the function Z. We divide the right side of the equations into elements of the resolving column and select the smallest positive ratio corresponding to the resolving row (equation) . At the intersection of the selected column and row there is a resolution number.
We divide the first equation by the resolving number and write out the resulting equation. Multiplying this equation by 14, 6 and -10 and subtracting from the 2nd, 3rd and 4th equations of system (1.3), respectively, we arrive at next system (1.4):
X2 + 1/4 Y1 = 25, |
||
X2 – 6/14 Y1 + U3 | ||
Such an identical transformation, in which the resolution number is chosen according to the specified rule, will be called a simplex transformation.
Thus, the simplex transformation is performed according to the following rule:
1. The resolution column corresponding to the smallest negative element in the Z-row is selected.
2. A resolving row is selected that corresponds to the smallest positive of the ratios of the elements of the right side of the equations to the corresponding elements of the resolving column. At the intersection of the resolution column and the resolution row there is a resolution number.
3. The elements of the resolution string are divided by the resolution number.
4. The elements of all other rows are calculated using the formula:
From system (1.4) we find the second admissible basic solution X2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, which corresponds to the new increased value of the function Z = 250.
Thus, the process of successive simplex transformations is a process of successive improvement of the solution. Wherein:
1. If there is at least one negative element in the Z-row and
a) there is at least one positive element in the resolution column, then the solution can be improved;
b) if the resolution column does not contain positive elements, then the function Z increases without limit.
2. If all elements in the Z-row are non-negative, then the optimal solution has been achieved.
These are sufficient conditions for the existence of an optimal solution plan.
In system (1.4), the coefficient of X2 in the Z row is negative, so the second column will be resolving. We find that the second line will be resolving. Next, we carry out a simplex transformation of system (1.4) in accordance with the specified rule:
X1 + 8/42 Y1 – 5/42 Y2 = 20,
X2 – 1/3 Y1 + 1/3 Y2 = 14,
20/7 Y1 – 23/7 Y2 + Y3 = 120,
10/42 Y1 + 20/42 Y2 + Z = 270, (1.5)
Since all elements in the Z-row are non-negative, this plan is optimal. In this case, Yl = Y2 = 0; X1 = 20; X2 = 14 and Zmax = 270.
Performing simplex transformations involves painstaking and often quite cumbersome calculations. These calculations can be greatly simplified by using so-called simplex tables to solve problems.
Each simplex transformation of the system is reduced to a transition from one simplex table to another.
According to the original system of equations (1.3), we compose the first simplex table (Table 1.1).
Table 1.1
The first column is the column of basic variables, the second column contains the free coefficients on the right side of equations (1.3), the first row contains all the variables, the last column is the control column and the coefficients in it are equal to the sum of all coefficients in the row.
From the table 1.1 we have the first feasible solution of system (1.3) X1 = X2 = 0, Y1 = 350,
Y2 = 392, Y3 = 408, Z = 0, which corresponds to vertex O (0,0) of the polygon of feasible solutions OABCD (Fig. 1).
The transition to the second simplex table (Table 1.2) is performed according to the rule specified in this paragraph for simplex transformations of systems of equations, while the resolving variable X1 goes to the basis instead of the resolving variable Y1. We obtain the table. 1.2.
Table 1.2
After filling out the table. 1.2, you should check that it is filled out correctly by summing the coefficient by row and this sum should be equal to the coefficients in the corresponding cells of the control column. From the table 1.2 the second feasible solution will be X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 and Z = 250.
It is easy to see that this table corresponds to system (1.4), and the reference solution
X1 = 25, X2 = 0 corresponds to the vertex D(25,0) of the solution polygon.
Since there is a negative element in the Z-row, we improve the solution, for which we compile a simplex table. 1.3.
Table 1. 3
*Note. To simplify calculations, remember that in the new table, the elements of the resolution column (except for the resolution element) are replaced by zeros. If the resolution line contains zeros, then the corresponding columns are transferred to the new table without changes:
Since there are no negative elements in the Z-string, then this decision will be optimal.
Table 1.3 corresponds to the system of equations (1.5) and the optimal solution X1 = 20,
X2 = 14 and Zmax = 270 and vertex C (20,14) of the polygon of feasible solutions OABCD.
Such extended tables, containing all the variables in the first row, thanks to the presence of a control column, allow you to control the correctness of filling out the tables and avoid arithmetic errors.
Simplex method based on shortened tables
Let's consider the system of equations (1.3) and write it in the form of table 1.4
Table 1.4
We write basic variables (BP) in the first column, and free variables (SP) in the first row. Next, we move to the new table 1.5 according to the rule:
1) swap SP and BP
2) in place of the resolving element there is a value inverse to it
3) elements of the resolving flow are divided by the resolving number
4) divide the elements of the resolving column by the resolving column and change the sign
5) the remaining elements are found as in the chapter “Finding the maximum of a linear function”, rule 4 (rule of rectangles for OGI). We get table 1.5.
Table 1.6
We obtained the optimal plan Zmax = 270 with X1 = 20, X2 = 14, and the equipment resources turned out to be in excess in the amount of 120 machine hours.
Solving a linear programming problem
Find the maximum of the objective function
under restrictions
14x + 5y ≤ 350
Solving a problem using a program Microsoft Excel.
Let us assign A3 and B3 to the values of the variables x and y.
In cell C4 we enter the goal function
In cells A7:A9 we enter the left parts of the restrictions
and in cells B7:B9 – the right parts of the restrictions.
After that, select the command Service, Finding a solution(Tools, Solver) and fill in the dialog box that opens Finding a solution ( Solver) as shown in Fig. 2. After pressing the button Execute(Solve) window opens Solution search results(Solver Results), which reports that a solution has been found (Fig. 3).
Rice. 2. Finding a solution
Rice. 3. Results of searching for a solution
Geometric solution of the problem using the program MATHCAD 2000.
- Write down in the form y = kx + b the equations of the lines that limit the range of permissible values of the variables. To enter and resolve the constraint 14x + 5y ≤ 350 relative to y, enter the left side of the inequality, press the Ctrl button and simultaneously press the = button, holding the previous one until the bold = sign pops up, mark the y variable with a highlight frame, click in the Symbolic menu (Symbols) on the line Solve (Calculate) – the result of the calculations will be displayed in the working document to the right of the equation; Enter the name of the function (in this example, y1(x)) and assign the resulting expression to it. Thus, the equation of one of the lines limiting the range of permissible values has been determined. Enter the remaining restrictions in the same way. Enter the equation 10x + 5y = C level line (reference line) of the objective function. Proceed in the same way as when entering constraints, but before solving the equation for y, assign some value to the constant C.
- Draw the corresponding straight lines on the graph and determine the region of feasible solutions of the system.
- By changing the values of the constant C, for example C = 100,150,200,250,..., observe the movement of the reference line and formulate a conclusion about the solvability of the problem.
- If the problem has a unique solution, find the vertex at which Z = Zmax. In our example, the maximum of the objective function is achieved at the point of intersection of the lines 14x + 5y = 350 and 7x + 14y = 196. Find the coordinates of the point using the Find function.
- Calculate the value of the objective function at the found point.
14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70
7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49
x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34
10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C
Rice. 4.
Find (x, y) → (20, 14)
f(x, y): = 10x + 5y
fmin: = f(20, 14)
Analytical solution of the problem using the program MATHCAD 2000.
Analytical solution of a problem in MathCAD is much simpler.
- Set the automatic calculation mode.
- Write the problem with arbitrary x and y assigned arbitrary (valid) values so that the program can start counting.
Z(x, y): = 10x + 5y
14x + 5x ≤ 360
M: = Maximize(z, x, y) M = (20, 14) Z(M0, M1) = 270
The problem of maximizing a linear function in the presence of negative free coefficients
Find the maximum of a linear function
under restrictions
X1 – X2 ≤ 3,
2X1 – 3X2 ≤ 6,
X1 ≥ 0, X2 ≥ 0.
Let us write the system in the form
Y1 = -X1 + X2 + 3 ≥ 0
Y2 = X1 + X2 - 5 ≥ 0
Y3 = -2X1 + 3X2 + 6 ≥ 0
Y4 = -X2 + 6 ≥ 0
Let's make a table.
We continue to work with the 2nd line, since the negative element is not missing. We perform SMGI with a resolving element -2. We get a table.
Linear function minimization problem
Reducing the minimization problem to the maximization problem of a linear function
We considered solving the problem of finding the maximum of a linear function using the simplex method
W = c1 x1 + c2 x2 + … + cn xn.
However, in many economic problems it is necessary to find the minimum of a linear function. To do this, it is enough to put
W = -Z = -c1 x1 – c2 x2 - … - cn xn
and solve the problem of maximizing the resulting function W under appropriate restrictions. Since it is clear that
Minimize Linear Function
when fulfilling restrictions
7X1 + 2X2 ≥ 14,
5X1 + 6X2 ≤ 30,
3X1 + 8X2 ≥ 24,
X1 ≥ 0, X2 ≥ 0.
Geometric solution of the problem in (Fig. 5) and it corresponds to the optimal solution at the point
C (48/11, 15/11) and at the same time Zmin = -21/11.
Figure 5. Geometric solution to the problem
Introducing the leveling variables Yi ≥ 0 and the function W = -Z = 2X1 - 5X2 → max, we write the problem in the form.
Y1 = 7X1 + 2X2 - 14,
Y2 = -5X1 - 6X2 + 30,
Y3 = 3X1 + 8X2 - 24,
We write this system in the form of a table.
We get rid of the negative free term in the Y1 row by performing the SMGI with the resolving element “-50/8”, we get a table.
Since there are no negative elements in W - row and 1 - column, we got the optimal solution X1 = 48/11, X2 = 15/11, Wmax – 21/11 or Zmin = –Wmax = -21/11,
Practical part
1. Solve the problem using the simplex method.
X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → max
Solution
X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0
X1 + X2 + X4 = 150
Answer: X1 = 75; X2 = 75; X3 = 0; X4 = 0.
Task No. 1.
The company produces two types of products. Types of raw materials, their reserves, consumption rates of raw materials per equivalent. For each type of product, production profits from product sales are given in the table.
Solution
2X1 + 2X2 ≤ 17
X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0
2X1 + X2 + X4 = 10
2X1 + 2X2 + X5 =17
Answer: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7.
Task No. 2.
The company produces three types of products, using three types of raw materials. Inventories of raw materials, rates of consumption and profit from the sale of each product are shown in the table.
How should production be planned so that the enterprise's profit is greatest?
Solution
2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → max
5X1 + 3X2 ≤ 900
2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0
X1 +X2 + X5 = 250
5X1 +3X2 + X6 = 900
X1 + 3X2 ≤ 20 F = 2X1 + X2 → max
2X1 + 2X2 ≤ 17
(-1/3)(-1/3)(2/3)
Answer: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5.
Conclusion
Let us dwell on the simplest interpretations of the simplex method.
The algebraic meaning of the simplex method is that, by performing identical algebraic transformations, we move from one feasible solution of a system of algebraic equations to another improved one, achieving an optimal solution to the problem.
From a geometric point of view, identical transformations using the simplex method represent successive movements from one vertex of a convex polygon of solutions to the neighboring one, from it to the next, and so on to the optimal vertex along the sides of this polygon.
The economic essence of the simplex method lies in the fact that it is a method of consistent improvement of solutions. This method makes it possible, having chosen a starting – reference plan of action, to gradually move forward and ultimately achieve an optimal plan, if, of course, such exists.
A simplex is a convex polygon in n-dimensional space with n + 1 vertices that do not lie on the same hyperplane. Simplexes are separated into a separate class because a simplex is the simplest polygon containing a certain volume of n-dimensional space.
It has been proven that if an optimal solution exists, it will certainly be found after a finite number of steps (with the exception of the so-called “degenerate problem”, in which the phenomenon of “cycling” is possible, i.e. repeated returns to the same position).
Linear programming is a field of mathematical programming dedicated to the theory and methods of solving extremal problems characterized by a linear relationship between variables.
Mathematical programming ( optimal programming) is a field of mathematics that combines various mathematical methods and disciplines: linear programming, dynamic programming, convex programming, etc. The general task of mathematical programming is to find the optimal (maximum or minimum) value of the objective function, and the values of the variables must belong to a certain range of acceptable values.
List of used literature
1) A. S. Shapkin, N. P. Mazaeva; Mathematical methods and research models operations, 2005.
2) N.Sh. Kremer, B A Putko, I.M. Trishin, M.N. Friedman; Operations research in economy. - UNITY, 2002.
Decision making under uncertainty If the first subject has m strategies, and the second has n strategies, then we are said to be dealing with an m x n game. Consider the game m x n. Let a set of strategies be given: for the first player (Ai), for the second player (Bj), a payment matrix, where aij is the gain of the first player or the loss of the second player when they choose strategies Ai and Bj, respectively. Each player chooses uniquely with probability I some strategy, i.e. uses a pure strategy when choosing a solution. In this case, the solution to the game will be in pure strategies. Since the interests of the players are opposite, the first player strives to maximize his winnings, and the second player, on the contrary, minimizes his losses. The solution to the game is to determine the best strategy for each player. The choice of the best strategy by one player is carried out in the complete absence of information about the decision being made by the second player.
Solving systems of linear inequalities
Inequalities
Linear inequalities are inequalities of the form ∑ai xi +b≥c
Specifying a system of linear inequalities with two or three unknowns means specifying a convex polygonal region on a plane or, accordingly, a convex polyhedral body in space.
Since the mid-1940s, a new field of applied mathematics has emerged - linear programming - with important applications in economics and technology. Ultimately, linear programming is just one section (albeit a very important one) of the theory of systems of linear inequalities.
Consider a first degree equation with two unknowns x and y
Interpreting x and y as point coordinates
on a plane, we can say that
the set of points defined by equation (1) is a straight line on the plane.
Geometric meaning of the first degree equation
Similarly for the inequality ax+by+c≥0. (2)
If b≠0, then this inequality is reduced to one of the types y≥kx+p or y≤kx+p.
The first of these inequalities is satisfied by all points lying “above” the line y=khx+p or on this line, and the second is satisfied by all points lying “below” the line y=khx+p or on this line.
If b=0, then the inequality is reduced to one of the types x≥h or x≤h. The first of them is satisfied by all points lying “to the right” of the line x=h or on this line, the second – by all points lying “to the left” of the line x=h or on this line.
Geometric meaning of the system of linear inequalities
Let a system of inequalities be given with two unknowns x and y. a1 x+b1 y+c1 ≥0,
a2 x+b2 y+c2 ≥0,
………….........
am x+bm y+cm ≥0.
The first inequality of the system defines a certain half-plane P1 on the xOy coordinate plane, the second – the half-plane P2, etc. If a pair of numbers x, y satisfies all the inequalities of the system, then the corresponding point M(x, y) belongs to all half-planes P1, P2,..., Pm simultaneously. In other words, the point M belongs to the intersection (of the common part) of the indicated half-planes. It is easy to see that the intersection of a finite number of half-planes is a certain polygonal region.
Example
Along the contour of the area there are strokes going into the area. They simultaneously indicate on which side of a given line the corresponding half-plane lies; the same is indicated with the help of arrows.
Unlimited scope of solutions
The region K is called the region of solutions to the system of inequalities. Let us immediately note that the scope of solutions is not always limited; As a result of the intersection of several half-planes, an unbounded region can arise.
Description of the presentation by individual slides:
1 slide
Slide description:
Decision making theory PetrSU, A.P. Moshchevikin, 2004 Linear programming This class of linear programming (75% of problems solved by Americans) includes problems in which the objective function is Wm(x), m=1,2,..., M, restrictions in the form of equalities hk(x)=0, k=1,2...K, and inequalities gj(x)>0, j=1,2,...J, are linear and there is no mathematical solution. Possible topics of LP tasks: rational use of raw materials and materials; cutting optimization problems; optimizing the production program of enterprises; optimal placement and concentration of production; to draw up an optimal transportation plan and transport operation; inventory management; and many others belonging to the field of optimal planning. Statement of the LP problem (determining the efficiency indicator, task variables, specifying the linear objective function W(x) to be minimized or maximized, functional hk(x), gj(x) and regional xli 2 slide
Slide description:
Decision-making theory PetrSU, A.P. Moshchevikin, 2004. Example of a LP problem Example - Optimization of the placement of by-products of a forestry department The forestry district has 24 hectares of free fallow land and is interested in extracting income from it. It can raise fast-growing hybrid Christmas tree seedlings that reach maturity in one year, or bulls, devoting part of the land to pasture. Trees are grown and sold in batches of 1,000. It takes 1.5 hectares to grow one batch of trees and 4 hectares to feed one bull. The forestry can only spend 200 hours per year on its by-products. Practice shows that it takes 20 hours to cultivate, trim, cut down and bundle one batch of trees. Caring for one bull also requires 20 hours. The forestry has the opportunity to spend 6 thousand rubles for this purpose. Annual costs for one batch of trees amount to 150 rubles. and 1.2 thousand rubles. for one bull. A contract has already been concluded for the supply of 2 bulls. At current prices, one Christmas tree will bring a profit of 2.5 rubles, one bull - 5 thousand rubles. 3 slide
Slide description:
Decision-making theory of PetrSU, A.P. Moshchevikin, 2004. Statement of the problem 1. As an indicator of efficiency, it is advisable to take the profit for the operation (annual profit from land in rubles). 2. The following should be taken as controllable variables of the problem: x1 - the number of bull calves fed per year; x2 - the number of grown batches of fast-growing Christmas trees of 1000 pieces. each per year. 3. Objective function: 5000 x1 + 2500 x2 max, where 5000 is the net income from one bull, rub.; 2500 - net income from one batch of trees (1000 pieces for 2.5 rubles). 4. Limitations: 4.1. By land use, hectares: 4 x1 + 1.5 x2 24 4.2. According to the budget, rub.: 1200 x1 + 150 x2 6000 4.3. By labor resources, h: 20 x1 + 20 x2 200 4.4. Obligations under the contract, pcs.: x1 2 4.5. Regional restrictions: x1 0, x2 0 4 slide
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004 Graphical solution of the LP problem Displaying on the graph the straight lines corresponding to the following equations, 4 x1 + 1.5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 200 x1 = 2 x2 = 0 shade the area at the points of which all restrictions are satisfied. Each such point is called a feasible solution, and the set of all feasible solutions is called a feasible region. Obviously, the solution to the LP problem consists of finding the best solution in the feasible region, which, in turn, is called optimal. In the example under consideration, the optimal solution is the feasible solution that maximizes the function W=5000 x1 + 2500 x2. The value of the objective function corresponding to the optimal solution is called the optimal value of the LP problem. 5 slide
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004 Graphical solution of the LP problem 6 slide
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004. Graphical solution of the LP problem. Enumeration of all corner points of the region of feasible solutions leads to finding the maximum income in the amount of 34 thousand rubles. (W=5000x1+2500x2), which the forestry department can extract by growing 3.6 bulls and 6.4 batches of Christmas trees. Integer methods (for example, brute force) give x1=3 and x2=6, which leads to an income of 30 thousand rubles, x1=4 and x2=5 leads to a more optimal result of 32.5 thousand rubles, point x1 =3 and x2=7 leads to a similar result. The graphical method, due to the large dimension of real practical LP problems, is rarely used, but it allows one to clearly understand one of the main properties of LP - if there is an optimal solution to a LP problem, then at least one of the vertices of the admissible region represents an optimal solution. Despite the fact that the feasible domain of the LP problem consists of an infinite number of points, the optimal solution can always be found by purposefully searching through a finite number of its vertices. The simplex method for solving the LP problem considered below is based on this fundamental property. 7 slide
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004 Solving the LP problem in MS Excel One of the built-in functions of the MS Excel spreadsheet editor (you must check the box during installation of MS Office) is “Search for a solution.” This package allows you to quickly solve linear and nonlinear programming problems. 8 slide
Slide description:
Decision theory PetrSU, A.P. Moshchevikin, 2004. LP problem in standard form. LP problem in standard form with m constraints and n variables has the following form: W = c1x1 + c2x2 + ... + cnxn min (max) under restrictions a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 In matrix form W = cx min (max) with restrictions Ax = b; x0; b0, where A is a matrix of dimension m*n, x is a column vector of variables of dimension n*1, b is a column vector of resources of dimension m*1, c is a row vector of estimates for the LP problem 1*n. Slide 9
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004 Transformation of inequalities Constraints in the form of inequalities can be converted into equalities by introducing so-called residual or redundant variables. The equation from the previous example 4x1 + 1.5x2 24 can be converted into an equality using the residual non-negative variable 4x1 + 1.5x2 + x3 = 24. The variable x3 is non-negative and corresponds to the difference of the right and left sides of the inequality. Similarly, x1 2 can be transformed by introducing a redundant variable x4: x1 - x4 = 2. 10 slide
Slide description:
Theory of decision making PetrSU, A.P. Moshchevikin, 2004. Conversion ungr. by sign of variables Conversion of variables with unlimited sign Variables that take both positive and negative values should be replaced by the difference of two non-negative ones: x = x+ - x-; x+0; x- 0. Example. 3x1+4x2+5x3+4x4 max 2x1+x2+3x3+5x4 5 5x1+3x2+x3+2x4 20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 = sign -3x1-4x2+5x3-4x4 min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 = sign; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8 -x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x7 = 15 x1,x2,x3,x4,x5,x6,x70; x8 replaced with x4 11 slide
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004. Simplex LP method The simplex method is an iterative procedure for solving LP problems written in standard form, the system of equations in which, using elementary operations on matrices, is reduced to canonical form: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. The variables x1, x2,...,xm, included with unit coefficients in only one equation of the system and with zero coefficients in the rest, are called basic. In the canonical system, each equation corresponds to exactly one basic variable. The remaining n-m variables (xm+1, ..., xn) are called non-basic variables. To bring the system to canonical form, you can use two types of elementary operations on strings: Multiplying any equation of the system by a positive or negative number. Adding to any equation another equation of the system, multiplied by a positive or negative number. 12 slide
Slide description:
Decision making theory PetrSU, A.P. Moshchevikin, 2004. Simplex LP method Writing the problem in the form of equations x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. is identical to the matrix entry 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 am,m+1 .. ams .. amn xn bm Slide 13
Slide description:
Decision making theory PetrSU, A.P. Moshchevikin, 2004. Simplex method algorithm 1. Select an initial feasible basic solution. A basic solution is a solution obtained for zero values of non-basic variables, i.e. xi=0, i=m+1,...,n. A basic solution is called an admissible basic solution if the values of the basic variables included in it are non-negative, i.e. xj = bj 0, j=1,2,...,m. In this case, the objective function will take the following form: W=cbxb=c1b1+c2b2+...+cmbm. We fill in the initial table of the simplex method: Slide 14
Slide description:
Decision making theory PetrSU, A.P. Moshchevikin, 2004. Simplex method algorithm 2. Calculate the vector of relative estimates c using the scalar product rule сj = сj - cbSj, where сb is the vector of estimates of the basic variables; Sj is the j-th column of the coefficients aij in the canonical system corresponding to the basis under consideration. We supplement the original table with a c - row. 15 slide
Slide description:
Decision making theory PetrSU, A.P. Moshchevikin, 2004. Simplex method algorithm 3. If all estimates cj 0 (cj 0), i=1,...,n, then the current feasible solution is the maximum (minimum ). The solution has been found. 4. Otherwise, it is necessary to enter into the basis a non-basic variable xr with the largest value cj instead of one of the basic variables (see table). 16 slide
Slide description:
Decision Making Theory PetrSU, A.P. Moshchevikin, 2004. Simplex method algorithm 5. Using the minimum ratio rule min(bi/air), we determine the variable xp derived from the basis. If the coefficient air is negative, then bi/air=. As a result, the intersection of the column containing the input non-basic variable xr and the row containing the output basic variable xp will determine the position of the leading element of the table. 6. We apply elementary transformations to obtain a new feasible basic solution and a new table. As a result, the leading element should be equal to 1, and the remaining elements of the leading element column should take the value zero. 7. Calculate new relative scores using the scalar transformation rule and go to step 4. Slide 17
Slide description:
Decision-making theory of PetrSU, A.P. Moshchevikin, 2004. Example of a decision using the simplex method Example - Optimization of the placement of by-products of a forestry 3. Objective function: 5000 x1 + 2500 x2 max, 4. Limitations: 4.1. By land use, hectares: 4 x1 + 1.5 x2 24 4.2. According to the budget, rub.: 1200 x1 + 150 x2 6000 4.3. By labor resources, h: 20 x1 + 20 x2 200 4.4. Obligations under the contract, pcs.: x1 2 4.5. Regional restrictions: x1 0, x2 0 Let us reduce the problem to standard form: 4 x1 + 1.5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6 0 The first three equations have, respectively, the basis variable x3, x4, x5, but in the fourth it is absent due to the fact that the variable x6 has a negative unit coefficient. To bring the system to canonical form, we use the method of artificial variables. x1 – x6+x7= 2, introduced an artificial variable x7.
