Types of linear programming. Solving linear programming problems using the graphical method

Annotation: This lecture reveals a number of issues devoted to linear programming as one of the sections mathematical programming; in particular, formulates the main types of tasks linear programming, reveals the differences between these tasks and classical problems mathematical analysis; introduces various forms records these tasks, sets them up and studies their 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 that develops methods for finding extreme values objective function among the set of its possible values, determined by restrictions.

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 value 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 the objective function and constraint functions are 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. Therefore, the correct translation of the 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 for solution mathematical models 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 problem); in tasks optimal distribution personnel, etc.

Linear programming problem(LP), as is already clear from what was said above, consists in finding the minimum (or maximum) linear function under linear restrictions.

General form the problem has the form: find under the conditions

Along with general form 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

Linear programming- a mathematical discipline devoted to the theory and methods of solving extremal problems on sets of -dimensional vector space defined by systems of 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 generalization of 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 form) 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 task 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, among the maximum flows, you need to select a flow with minimum cost. 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 with general algorithms for 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 compile 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 player 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 for solving a general linear programming (LP) problem is the simplex method. Despite the fact that the simplex method is a fairly effective algorithm that has shown good results in solving applied LP problems, it is an algorithm with exponential complexity. The reason for this is the combinatorial nature of the simplex method, which sequentially iterates over the vertices of the polyhedron admissible 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 a problem that had remained unsolved for a long time. 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.

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.: Higher 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 its most general form, the problem of L.p. can be written like this. Dana... ... Economic and mathematical dictionary

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 solved 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 a device that allows you to find a conditional extremum on a set given 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 relate to 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 of definition 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 PPP:

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.

Linear programming is considered a revolutionary achievement that gave man the ability to formulate general goals and find optimal solutions for a wide class through the simplex method practical problems making decisions of great complexity.

Linear programming– a mathematical discipline devoted to the theory and methods of solving problems about extrema of linear functions on sets n-dimensional vector space defined by systems of linear equations and inequalities.

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 problem(LP), consists of finding the minimum (or maximum) of a linear function under linear constraints.

Linear programming is used to solve the following economic problems:

1. The problem of production management and planning.

2. Problems of determining the optimal placement of equipment on sea vessels, in the workshops.

3. The problem of determining the optimal cargo transportation plan (transport problem).

4. The problem of optimal personnel distribution.

5. Problems about mixtures, diet (planning product composition), etc.

3. LINEAR PROGRAMMING MODEL, ITS REPRESENTATION IN MS EXCEL ELECTRONIC TABLES.

Traditionally, management science refers to the construction of detailed models, as a result of the analysis of which management decisions are made. Today there are millions of managers to analyze business tasks spreadsheets are used. Modern spreadsheets have many powerful tools that can be used to analyze models more accurately, resulting in more balanced and closer-to-fit models. optimal solutions. Given the increasingly widespread use spreadsheets In the management process, future specialists need to have professional model development skills - how to “plan” a blank worksheet so as to obtain a useful and practical model of a business situation, without delving into the algorithmic and mathematical intricacies of calculations.

The main steps for creating a linear programming model in Excel:

1. Writing and testing a symbolic linear programming model. The model is written down on paper in mathematical form.

2. Creation and Debugging tabular model linear programming. Based on the symbolic model of the drug product, its representation is created in Excel .

3. An attempt to optimize the model using the SEARCH FOR SOLUTION add-on.

4. USING THE ADD-ON SEARCHING FOR A SOLUTION.

Using spreadsheets, you can simulate real situations and evaluate the results. In other words, using spreadsheets, you can analyze the results of operations and predict the future prospects of the enterprise. These tasks in the environment MS Excel makes it possible to solve with the Search for Solution add-in.

Finding a solution – This is an add-on that is designed to optimize models in the presence of constraints. It consists of two software components: programs written in Visual language Basic, which translates the information presented on the work letter for internal representation, which is used by another program. The second program is located in the computer memory as a separate software module. It performs the optimization and returns the solution found to the first program, which resumes the data on the worksheet. You can use it to find optimal value formula that is stored in the target cell. This procedure works on a group of cells that are directly related to a formula in the target cell. To get the formula result in the target cell, the procedure changes the value in the cells that affect the search. In order to reduce the plurality of values that are used in the problem model, a constraint is applied. These constraints may contain a reference to other cells that affect the search.

General algorithm working with the add-on Finding a solution.

On the menu Service select a team Finding a solution.
In the field Sets the target cell Enter the address of the cell containing the formula to optimize the model.
To maximize the value of a target cell by changing the values of influencing cells, set the switch to Maximum value . To minimize the value of the target cell by changing the values of the influencing cells, set the switch to Minimum value . In order for the target cell to acquire a value specific number, set the switch to position Meaning and enter the appropriate number.
In the field Changing cells Enter the addresses of the cells that change their values, separating them with commas. The cells being modified must be directly or indirectly related to the target cell. Installation up to 200 is allowed changeable cells.
In the field Restrictions enter all the restrictions that are imposed on the search for a solution.
Click the button Execute.
To save the solution found, select the switch in the dialog box Solution search results to position Save the solution found. To resume input data, set the switch to Restore original values.
To interrupt the search for a solution, press the key Esс. MS Excel will recalculate the sheet taking into account the found cell values that affect the result.

Robotic algorithm with nadbudova Finding a solution.

5. SOLVING A LINEAR PROGRAMMING PROBLEM USING A PROGRAM MS EXCEL.

Example. Confectionery shop for making three types of caramel A, B, C uses three main types of raw materials: sugar, molasses and fruit puree. Standard sugar consumption for the production of 1 kg of caramel of each type, respectively, levels: 0.8 kg; 0.5kg; 0.6kg; molasses – 04kg; 0.4kg; 0.3kg; fruit puree – 0kg; 0.1kg; 0.1kg. Sweets can be produced in any quantities (sales are guaranteed), but the supply of raw materials is limited: sugar reserves - 80 kg, molasses - 60 kg, fruit puree - 12 kg. Profit from the sale of 1 kg of caramel A is 10 UAH, type IN – 11 UAH, type WITH – 12 UAH.

Table 1

Determine a plan for the production of caramel that provides maximum profit from the activities of the confectionery shop.

15. Analytical methods. Linear programming methods.

15.1. Analytical methods

Throughout his entire evolution, man, when performing certain actions, sought to behave in such a way that the result achieved as a consequence of some action turned out to be, in a certain sense, the best. Moving from one point to another, he sought to find the shortest possible path. When building a dwelling, he looked for a geometry that would provide acceptable living conditions with the least fuel consumption. While building ships, he tried to give them a shape in which the water would offer the least resistance. The list of similar examples can easily be continued.

The best solutions to problems in a certain sense are usually called optimal. Currently, no problem can be solved without the use of optimization principles. complex problem. When setting and solving optimization problems, two questions arise: what and how to optimize?

The answer to the first question is obtained as a result of an in-depth study of the problem to be solved. The parameter that determines the degree of perfection of the solution to the problem that has arisen is identified. This parameter is usually called target function or quality criterion. Next, a set of quantities is established that determine the objective function. Finally, all the constraints that must be taken into account when solving the problem are formulated. After this, a mathematical model is constructed, which consists in establishing the analytical dependence of the objective function on all arguments and the analytical formulation of the constraints associated with the problem. Next, we begin to search for an answer to the second question.

So, let, as a result of the formalization of the applied problem, it is established that the objective function is , where the set X is a generalization of restrictions, it is called the set of feasible solutions. The essence of the optimization problem is to search on the set X - the set of feasible solutions for such a solution
, at which the target function f reaches its minimum or maximum value.

An integral part of optimization methods is linear programming.

15.2. Basic concepts of linear programming

The first mention (1938) of mathematical methods in effective production management belongs to the Soviet mathematician L. V. Kantorovich. A year later, in 1939, L. V. Kantorovich published the work “Mathematical methods of organizing and planning production” and practically applied the results obtained. The term “linear programming” was introduced by American mathematicians J. Danzig and T. Koopmans in the late 40s. J. Dantzig developed the mathematical apparatus of the simplex method for solving linear programming problems (1951). Simplex method is used to solve a wide range of linear programming problems and is still one of the main methods.

Linear programming is a branch of mathematics focused on finding an extremum (maximum or minimum) in problems that are described by linear equations. Moreover, linear equations describe both the objective function itself and the input parameters (variables) of the conditions of restrictions on input parameters. A necessary condition for linear programming problems is the mandatory presence of restrictions on resources (raw materials, materials, finance, demand for manufactured products, etc.). To others an important condition solving the problem is the choice of stopping criterion for the algorithm, i.e. the objective function must be optimal in some sense. The optimality of the objective function must be expressed quantitatively. If the target function is represented by one or two equations, then in practice such problems can be solved quite easily. The algorithm stopping criterion (or optimality criterion) must satisfy the following requirements:

be the only one for a given task;

measured in units of quantity;

linearly depend on the input parameters.

Based on the above, we can formulate the linear programming problem in general form:

find the extremum of the objective function

under restrictions in the form of equalities:

(2.2)

under restrictions in the form of inequalities:

(2.3)

and conditions of non-negativity of input parameters:

In short form, the linear programming problem can be written as follows:

(2.5)

given that

Where
- input variables;

Numbers are positive, negative and equal to zero.

In matrix form, this problem can be written as follows:

Linear programming problems can be solved analytically and graphically.

15.3. Canonical linear programming problem

, i=1,…,m,

, j=1,…,n.

The main computational methods for solving linear programming problems were developed specifically for the canonical problem.

15.4. General linear programming problem

It is necessary to maximize (minimize) a linear function of n variables.

under restrictions

, i=1,…, k,

, i=1+ k,…, m,

, …,

Here k≤ m, r≤ n. The standard problem is obtained as a special case of the general one with k= m, r= n; canonical – at k=0, r= n.

Example.

The confectionery factory produces several types of sweets. Let's call them "A", "B" and "C". It is known that the sale of ten kilograms of sweets “A” gives a profit of 90 rubles, “B” - 100 rubles and “C” - 160 rubles. Candy can be produced in any quantity (sales are guaranteed), but supplies of raw materials are limited. It is necessary to determine what kind of sweets and how many tens of kilograms need to be produced so that the total profit from sales is maximized. The consumption rates of raw materials for the production of 10 kg of sweets of each type are given in Table 1.

Table 1. Raw material consumption rates

for production

The economic and mathematical formulation of the problem has the form

Find such variable values X=(x1, x2, x3), to

objective function

under conditions-restrictions: