The main stages of writing a linear programming model. Solving linear programming problems using the graphical method
Linear programming
Linear programming- a mathematical discipline devoted to the theory and methods of solving extremal problems on sets of -dimensional vector space defined by systems linear equations and inequalities.
Linear programming is a special case of convex programming, which in turn is a special case of mathematical programming. At the same time, it is the basis of several methods for solving integer and nonlinear programming problems. One of the generalizations linear programming is fractional linear programming.
Many properties of linear programming problems can also be interpreted as properties of polyhedra and thus geometrically formulated and proven.
Story
The interior point method was first mentioned by I. I. Dikin in 1967.
Tasks
The main (standard) linear programming problem is called the problem of finding the minimum of a linear objective function ( linear shape) of the form:
under conditions
, .The linear programming problem will have canonical view , if in the main problem instead of the first system of inequalities there is a system of equations:
,The main problem can be reduced to canonical by introducing additional variables.
Linear programming problems of the most general form (problems with mixed constraints: equalities and inequalities, the presence of variables free from constraints) can be reduced to equivalent ones (having the same set of solutions) by replacing variables and replacing equalities with a pair of inequalities.
It is easy to see that the problem of finding the maximum can be replaced by the problem of finding the minimum by taking coefficients with the opposite sign.
Sample problems
Maximum matching
Consider the maximum matching problem in a bipartite graph: there are several boys and girls, and for each boy and girl it is known whether they are attractive to each other. We need to marry the maximum number of couples with mutual sympathy.
Let us introduce variables that correspond to the pair of the -boy and the -girl and satisfy the restrictions:
with objective function. It can be shown that among the optimal solutions to this problem there is an integer one. Variables equal to 1 will correspond to couples that should be married.
Maximum flow
Let there be a graph (with oriented edges), in which for each edge its throughput. And two vertices are given: drain and source. It is necessary to indicate for each edge how much liquid will flow through it (no more than its capacity) so as to maximize the total flow from source to drain (liquid cannot appear or disappear at all vertices except the drain and source).
Let us take as variables the amount of liquid flowing through the rib. Then
,where is the capacity of that edge. These inequalities must be supplemented by the equality of the amount of inflowing and outflowing fluid for each vertex, except for the drain and source. As a function, it is natural to take the difference between the amount of outflowing and inflowing fluid at the source.
A generalization of the previous problem is maximum flow of minimum cost. In this problem, the costs for each edge are given and you need to select the flow with the minimum cost among the maximum flows. This problem comes down to two linear programming problems: first you need to solve the problem of the maximum flow, and then add to this problem the constraint , where is the value of the maximum flow, and solve the problem with new feature- flow cost.
These problems can be solved faster than general algorithms solving linear programming problems due to the special structure of equations and inequalities.
Transport task
There is a certain homogeneous cargo that needs to be transferred from warehouses to factories. For each warehouse it is known how much cargo it contains, and for each plant its demand for cargo is known. The cost of transportation is proportional to the distance from the warehouse to the factory (all distances from the th warehouse to the th factory are known). It is required to compose the most cheap plan transportation.
Decisive variables in in this case are the quantities of cargo transported from the th warehouse to the th plant. They satisfy the restrictions:
The objective function has the form: , which must be minimized.
Zero sum game
There is a size matrix. The first player chooses a number from 1 to , the second - from 1 to . Then they check the numbers and the first player gets points, and the second gets points (the number chosen by the first player gets the second). We need to find the optimal strategy for the first player.
Suppose that in an optimal strategy, for example, the first player must choose a number with probability . Then the optimal strategy is a solution to the following linear programming problem:
, , (),in which the function needs to be maximized. The value in the optimal solution will be the mathematical expectation of the first player's payoff in the worst case.
Solution algorithms
The most famous and widely used in practice to solve common task Linear programming (LP) is a simplex method. Despite the fact that the simplex method is a fairly effective algorithm that has shown good results when deciding applied problems LP, it is an algorithm with exponential complexity. The reason for this is the combinatorial nature of the simplex method, which sequentially enumerates the vertices of the polyhedron of feasible solutions when searching for the optimal solution.
The first polynomial algorithm, the ellipsoid method, was proposed in 1979 by the Soviet mathematician L. Khachiyan, thus solving the problem for a long time remained unresolved. The ellipsoid method has a completely different, non-combinatorial nature than the simplex method. However, from a computational point of view, this method turned out to be unpromising. However, the very fact of polynomial complexity of problems led to the creation of a whole class efficient algorithms LP - interior point methods, the first of which was N. Karmarkar's algorithm proposed in 1984. Algorithms of this type use a continuous interpretation of the LP problem, when instead of enumerating the vertices of the polyhedron of solutions to the LP problem, a search is carried out along trajectories in space problem variables, not passing through the vertices of the polyhedron. The interior point method, which, unlike the simplex method, bypasses points from the interior of the region acceptable values, uses log-barrier nonlinear programming methods developed in the 1960s by Fiacco and McCormick.
see also
- Graphical method for solving a linear programming problem
Notes
Literature
- Thomas H. Corman et al. Chapter 29. Linear programming // Algorithms: construction and analysis = INTRODUCTION TO ALGORITHMS. - 2nd ed. - M.: “Williams”, 2006. - P. 1296. - ISBN 5-8459-0857-4
- Akulich I.L. Chapter 1. Linear programming problems, Chapter 2. Special linear programming problems // Mathematical programming in examples and problems. - M.: graduate School, 1986. - 319 p. - ISBN 5-06-002663-9
- Karmanov V. G. Mathematical programming. - 3rd edition. - M.: Nauka, 1986. - 288 p.
- Danzig George Bernard "Memories of the Beginning of Linear Programming"
Links
- - Free optimization package designed to solve linear, integer and goal programming problems.
- Vershik A. M. “About L. V. Kantorovich and linear programming”
- Bolshakova I. V., Kuralenko M. V. “Linear programming. Educational and methodological manual for the test."
- Barsov A. S. “What is linear programming”, Popular lectures on mathematics, Gostekhizdat, 1959.
- M. N. Vyalyi Linear inequalities and combinatorics. - MCNMO, 2003.
Wikimedia Foundation. 2010.
- Salten, Felix
- Glagow, Martina
See what “Linear programming” is in other dictionaries:
linear programming- - linear programming An area of mathematical programming devoted to the theory and methods of solving extremal problems characterized by linear dependence between… … Technical Translator's Guide
Linear programming
Linear programming- a field of mathematical programming devoted to the theory and methods of solving extremal problems characterized by a linear relationship between variables. In the very general view L.p. problem can be written like this. Are given… … Economic and mathematical dictionary
The solution occurs in three stages:
- Transition to KZLP. Any LLP of the form ax ≤ b , ax ≥ b , ax = b (F(X) → extr) reduces to the form ax = b , F(X) → max ;
- Transition to SZLP. A CLLP of the form ax = b reduces to the form ax ≤ b , F(X) → max ;
- Solution using the simplex method;
Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is saved in a Word file.
Transition from the objective function minimization problem to the maximization problem
The problem of minimizing the objective function F(X) can easily be reduced to the problem of maximizing the function F*(X) under the same restrictions by introducing the function: F*(X) = -F(X) . Both problems have the same solution X*, and at the same time min(F(X)) = -max(F*(X)) .Let's illustrate this fact graphically:
| F(x) → min |
F(x) → max  |
Base plan– a plan with defined through free basic variables.
Basic plan– reference plan with zero basic variables.
Optimal plan– a basic plan that satisfies optimal function goals (FC).
Leading (resolving) element is the coefficient of the free unknown, which becomes the basic one, and the coefficient itself is converted to unity.
Guide line– the line of the leading element, in which the basic unknown is located with a unit coefficient, excluded during the transformation (line with the minimum limiting coefficient, see below).
Guide Column– column of the leading element, the free unknown of which is converted to the basic one (column with maximum benefit, see below).
Variables x 1, …, x m, included with unity coefficients in only one equation of the system, with zero coefficients in the rest, are called basic or dependent. In the canonical system, each equation corresponds to exactly one basic variable. The transition is carried out using the Gauss-Jordan method. The main idea of this method is to reduce a system of m equations with n unknowns to canonical form using elementary operations on strings.
Rest n-m variables(x m +1 ,…, x n) are called non-basic or independent variables.
Basic solution called admissible basic solution, if the values of the basic variables included in it x j ≥0, which is equivalent to the non-negativity condition b j ≥0.
Acceptable basic solution is corner point admissible set S of a linear programming problem and is sometimes called reference plan.
If among the non-negative numbers b j there is equal to zero, then the admissible basic solution is called degenerate(degenerate corner point) and the corresponding linear programming problem is called degenerate.
Example No. 1. Reduce the linear programming problem to a standard ZLP.
F(X) = x 1 + 2x 2 - 2x 3 → min with restrictions:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
To bring the PAP to canonical form necessary:
1. Change the sign of the objective function. Let us reduce the problem F(X) → min to the problem F(X) → max. To do this, multiply F(X) by (-1). In the first inequality of meaning (≤) we introduce the basic variable x 4 ; in the second inequality of meaning (≥) we introduce the basic variable x 5 with a minus sign.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Transition to SZLP.
Extended matrix of the system of equality constraints for this problem:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Let us reduce the system to the identity matrix using the Jordan transformation method.
1. You can choose x 4 as the base variable.
2. We choose x 2 as the base variable.
Resolution element RE=-2. The line corresponding to the variable x 2 is obtained by dividing all elements of the line x 2 by the resolving element RE = -2. In place of the resolving element we get 1. In the remaining cells of the x 2 column we write zeros. All other elements are determined by the rectangle rule. Let's present the calculation of each element in the form of a table:
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
We get a new matrix:
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. We choose x 3 as the base variable.
Resolution element RE=2. The line corresponding to the variable x 3 is obtained by dividing all elements of the line x 3 by the resolving element RE=2. In place of the resolving element we get 1. In the remaining cells of the x 3 column we write zeros. All other elements are determined by the rectangle rule. Let's present the calculation of each element in the form of a table:
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
We get a new matrix:
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Since the system has an identity matrix, we take X = (4,2,3) as the basis variables.
The corresponding equations are:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1/4 x 1 + x 2 + 1/2 x 5 = 9 3/4
1/2 x 1 + x 3 = 4 1/2
Let's express the basic variables in terms of the rest:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1/4 x 1 - 1/2 x 5 +9 3/4
x 3 = - 1 / 2 x 1 +4 1 / 2
Let's substitute them into the target function:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
or
System of inequalities:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1/4 x 1 - 1/2 x 5 +9 3/4 ≥ 0
- 1/2 x 1 +4 1/2 ≥ 0
We reduce the system of inequalities to next view:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 5 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Let's simplify the system.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 2 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max
Example No. 2. Find first graphical method, and then using the simplex method to solve the problem
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) with restrictions:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0
Linear programming emerged as a separate branch of applied mathematics in the 40s and 50s. XX century thanks to the work of the Soviet scientist, Nobel Prize winner L.V. Kantorovich. In 1939, he published the work “Mathematical methods of organizing and planning production,” in which he used mathematics to solve economic problems about best download machines, cutting materials at the lowest cost, distributing cargo across several modes of transport and others, proposing the method of resolving multipliers 8.
L.V. Kantorovich was the first to formulate such widely used economic and mathematical concepts as optimal plan, optimal allocation of resources, objectively determined assessments, indicating numerous areas of economics where they can be applied.
The concept of linear programming was introduced by the American mathematician D. Dantzig, who in 1949 proposed an algorithm for solving the linear programming problem, called the “simplex method”.
Mathematical programming, which includes linear programming, is currently one of the areas of operations research. Depending on the type of problems being solved, it distinguishes such areas as linear, nonlinear, discrete, dynamic programming, etc. The term “programming” was introduced due to the fact that unknown variables that are in the process of solving a problem usually determine a program or plan operation of some economic entity.
In classical mathematical analysis, the general formulation of the problem of determining a conditional extremum is studied. However, in connection with the development of industrial production, transport, agriculture, and the banking sector, the traditional results of mathematical analysis were not enough. The needs of practice and the development of computer technology have led to the need to determine optimal solutions when analyzing complex economic systems.
The main tool for solving such problems is mathematical modeling. In this case, a simple model is first built, then its research is carried out, making it possible to understand which of the integrating properties of the object are not captured by the formal scheme, after which, by complicating the model, its greater adequacy to reality is ensured. In many cases, the first approximation to reality is a model in which all dependencies between the variables characterizing the state of the object are linear. Practice shows that a sufficient number of economic processes are described quite fully by linear models. Consequently, linear programming as an apparatus that allows one to find a conditional extremum on a set defined by linear equations and inequalities plays an important role in the analysis of these processes.
Linear programming has received widespread development due to the fact that it has been established that a number of planning and control problems can be formulated in the form of linear programming problems, for solving which there are effective methods. According to experts, approximately 80–85% of all optimization problems solved in practice are linear programming problems.
The created mathematical apparatus in combination with computer programs that perform labor-intensive calculations makes it possible to widely use linear programming models in economic science and practice.
Definition 1 9 . Linear programming (LP) is a field of mathematical programming, which is a branch of mathematics that studies methods for finding extreme (largest and smallest) values of a linear function of a finite number of variables, the unknowns of which are subject to linear constraints.
This linear function is called the target function, and the constraints, which represent quantitative relationships between variables that express the conditions and requirements of the economic problem and are written mathematically in the form of equations or inequalities, are called a system of constraints.
A wide range of issues of planning economic processes is reduced to linear programming problems, where the task of finding the best (optimal) solution is posed.
A general linear programming problem (GLP) is to find the extreme value (maximum or minimum) of a linear function, called the objective 10:
from n variables x 1 , x 2 , …, X n with imposed functional restrictions:
(3.2)
and direct restrictions (the requirement of non-negativity of variables)
, (3.3)
Where a ij , b i , c j– given constant values.
In the system of restrictions (3.2), the signs “less than or equal to,” “equal to,” and “greater than or equal to” can appear simultaneously.
The ZLP in a more concise form has the form:
,
with restrictions:
;
.
Vector` X = (x 1 , x 2 , …, X n) whose components satisfy the functional and direct constraints of the problem are called plan(or acceptable solution) ZLP.
All feasible solutions form domain linear programming problems, or region of feasible solutions (ODR). A feasible solution that delivers the maximum or minimum of the objective function f(`X), is called the optimal plan of the problem and is denoted f(`X * ), Where ` X * =(x 1 * , x 2 * , …, X n * ).
Another form of recording the PAP:
,
Where f(`X * ) is the maximum (minimum) value f(WITH, X), taken over all solutions included in the set possible solutions X .
Definition 2 11 . The mathematical expression of the objective function and its constraints is called a mathematical model of an economic problem.
To compile a mathematical model you need:
1) identify the variables;
2) create an objective function based on the goal of the problem;
3) write down a system of restrictions, taking into account the indicators in the problem statement and their quantitative patterns.
Annotation: This lecture covers a number of issues devoted to linear programming as one of the branches of mathematical programming; in particular, formulates the main types of linear programming problems, reveals the differences between these problems and classical problems of mathematical analysis; introduces various forms of recording these tasks, carries out their formulation and study of the structure. The question of solving linear programming problems using the simplex method is most fully explored.
1. The concept of mathematical programming
is a mathematical discipline in which methods are developed for finding extreme values of an objective function among the set of its possible values determined by constraints.
The presence of restrictions makes the problems fundamentally different from the classical problems of mathematical analysis of finding extreme values of a function. Methods of mathematical analysis for searching extremum of the function in tasks mathematical programming turn out to be unsuitable.
To solve problems mathematical programming Special methods and theories have been developed and are being developed. Since solving these problems requires performing a significant amount of calculations, when comparative assessment methods great importance is given to the efficiency and convenience of their implementation on a computer.
It can be considered as a set of independent sections involved in the study and development of methods for solving certain classes of problems.
Depending on the properties of the objective function and the constraint function, all problems mathematical programming are divided into two main classes:
- linear programming problems,
- tasks nonlinear programming.
If objective function and constraint functions – linear functions, then the corresponding problem of finding an extremum is a linear programming problem. If at least one of specified functions is nonlinear, then the corresponding problem of finding an extremum is the problem nonlinear programming.
2. The concept of linear programming. Types of linear programming problems
Linear programming(LP) – one of the first and most thoroughly studied sections mathematical programming. Exactly linear programming was the section from which the discipline itself began to develop" mathematical programming". The term "programming" in the title of the discipline has nothing in common with the term "programming (i.e., compiling a program) for a computer" has nothing to do with the discipline " linear programming" arose even before the time when computers began to be widely used to solve mathematical, engineering, economic and other problems.
The term " linear programming" arose as a result of an inaccurate translation of the English "linear programming". One of the meanings of the word "programming" is making plans, planning. Consequently, correct translation English "linear programming" would not be " linear programming", and "linear planning", which more accurately reflects the content of the discipline. However, the terms linear programming, nonlinear programming, mathematical programming etc. have become generally accepted in our literature and will therefore be preserved.
So, linear programming arose after the Second World War and began to develop rapidly, attracting the attention of mathematicians, economists and engineers due to the possibility of wide practical application, as well as mathematical harmony.
It can be said that linear programming applicable to solving mathematical models of those processes and systems that can be based on the hypothesis of a linear representation of the real world.
Linear programming used in solving economic problems, in tasks such as management and production planning; in problems of determining optimal placement equipment on sea vessels, in workshops; in problems of determining optimal plan cargo transportation (transport task); in problems of optimal personnel distribution, etc.
Linear programming problem(LP), as is already clear from what was said above, consists of finding the minimum (or maximum) of a linear function under linear restrictions.
General form the problem has the form: find under the conditions
Along with the general form, they are also widely used canonical And standard forms. In both canonical and standard form
Those. all variables in any feasible solution to the problem must take non-negative values (such variables are usually called non-negative unlike the so-called free variables whose range of values is not subject to such restrictions). The difference between these forms is that in one case I 2 = 0, and in the other - I 1 = 0.
The LP problem in canonical form.
Linear programming is one of the most significant branches of mathematics, where the theoretical and methodological foundations for solving certain problems are studied. This mathematical discipline is widely used in last years in various economic and technical areas, where not the last role is given to mathematical planning and use automatic systems calculations. This branch of science is devoted to the study of linear optimization models. That is, linear programming is about numbers. First this term was proposed by T. Koopmans in 1951. Optimal plan for each linear program must be automatically associated with the optimal price level, that is, with objectively determined assessments.
Linear programming: methods
Using the technique, it is possible to solve a considerable number of extreme problems related to economics. In this case, it is usually necessary to find the extreme values of some functions of a variable value. The solution to a system of transformable equations and inequalities is expressed as the basis of linear programming. This type programming is characterized by the mathematical formulation of variables, sequence and in a certain order calculations, as well as logical analysis. This applies:
If there is mathematical certainty and quantitative limitation between the factors being studied and variable quantities;
If there is interchangeability of factors due to the sequence of calculations;
If mathematical logic is combined with an understanding of the essence of the phenomena that are being studied.
Linear programming in promotes calculus optimal performance all machines, production lines, units, as well as solving problems of rational use of available materials.
IN agriculture with help this method The minimum cost of the feeding ration is determined taking into account the available amount of feed. In this case, the types and content of certain useful substances in them are taken into account.
In foundry this technique allows you to find a solution transport problem and problems about mixtures that are part of the metallurgical charge. The essence of the transport problem in this case implies the optimal attachment of consuming enterprises to enterprises that are engaged in production.
Linear programming: problems
Distinctive feature everyone economic tasks, which are solved using linear programming techniques, is the choice certain options solutions, as well as limiting conditions. By solving this problem it is possible to find optimal solution of all alternative options.
A significant value of using linear programming techniques in economics is the choice of the optimal option from large quantity all options that are considered acceptable. Such problems are almost impossible to solve in other ways, since only they allow us to find the degree of rationality of application. Using linear programming, such a basic problem as transport is solved, which should minimize the cargo turnover of consumer goods during their delivery from the manufacturer.
Linear Programming in Excel
In the process of solving such problems, it is first necessary to create a model, which implies the formulation of conditions in mathematical language. After this stage, a solution can be found using the graphical method. For this purpose in Excel program exists special function"Finding a solution."
As is already clear from the above, linear programming has a very wide scope of application.
