Brief theory

The method of Lagrange multipliers is a classical method for solving problems of mathematical programming (in particular, convex). Unfortunately, in the practical application of the method, significant computational difficulties may occur, narrowing the area of ​​its use. We consider here the Lagrange method mainly because it is an apparatus actively used to justify various modern numerical methods that are widely used in practice. As for the Lagrange function and Lagrange multipliers, they play an independent and extremely important role in the theory and applications not only of mathematical programming.

Consider a classical optimization problem:

Among the restrictions of this problem there are no inequalities, there are no conditions for the non-negativity of the variables, their discreteness, and the functions and are continuous and have partial derivatives of at least the second order.

The classical approach to solving the problem gives a system of equations (necessary conditions) that must be satisfied by the point that provides the function with a local extremum on the set of points that satisfy the constraints (for a convex programming problem, the found point will be at the same time the global extremum point).

Let us assume that function (1) has a local conditional extremum at the point and the rank of the matrix is ​​equal to . Then the necessary conditions can be written as:

is the Lagrange function; are the Lagrange multipliers.

There are also sufficient conditions under which the solution of the system of equations (3) determines the extremum point of the function . This question is solved on the basis of the study of the sign of the second differential of the Lagrange function. However, sufficient conditions are mainly of theoretical interest.

You can specify the following procedure for solving problem (1), (2) by the Lagrange multiplier method:

1) compose the Lagrange function (4);

2) find the partial derivatives of the Lagrange function with respect to all variables and equate them

zero. Thus, a system (3) consisting of equations will be obtained. Solve the resulting system (if it turns out to be possible!) and thus find all the stationary points of the Lagrange function;

3) from stationary points taken without coordinates, select points at which the function has conditional local extrema in the presence of constraints (2). This choice is made, for example, using sufficient conditions for a local extremum. Often the study is simplified if specific conditions of the problem are used.

Problem solution example

The task

The firm produces two types of goods in quantities and . The useful cost function is defined by the relation . The prices of these goods in the market are equal and respectively.

Determine at what volumes of output the maximum profit is achieved and what it is equal to if the total costs do not exceed

Having trouble understanding the solution process? The site has a service Solving problems by methods of optimal solutions to order

The solution of the problem

Economic and mathematical model of the problem

Profit function:

Cost limits:

We get the following economic and mathematical model:

In addition, according to the meaning of the task

Lagrange multiplier method

Let's compose the Lagrange function:

We find partial derivatives of the 1st order:

We compose and solve the system of equations:

Since then

Maximum Profit:

Answer

Thus, it is necessary to produce units. goods of the 1st type and units. goods of the 2nd type. In this case, the profit will be maximum and will be 270.
An example of solving the problem of quadratic convex programming by a graphical method is given.

Solving a linear problem by a graphical method
A graphical method for solving a linear programming problem (LPP) with two variables is considered. On the example of the problem, a detailed description of the construction of a drawing and finding a solution is given.

Wilson inventory management model
On the example of solving the problem, the main model of inventory management (Wilson model) is considered. Such indicators of the model as the optimal size of the order lot, annual storage costs, the interval between deliveries and the point of placing the order are calculated.

Direct Cost Ratio Matrix and Input-Output Matrix
On the example of solving the problem, the Leontiev intersectoral model is considered. The calculation of the matrix of coefficients of direct material costs, the matrix "input-output", the matrix of coefficients of indirect costs, the vectors of final consumption and gross output is shown.

FROM The essence of the Lagrange method is to reduce the conditional extremum problem to the solution of the unconditional extremum problem. Consider a non-linear programming model:

(5.2)

where
are well-known functions,

a
are given coefficients.

Note that in this formulation of the problem, the constraints are given by equalities, and there is no condition for the variables to be nonnegative. In addition, we assume that the functions
are continuous with their first partial derivatives.

Let us transform conditions (5.2) in such a way that the left or right parts of the equalities contain zero:

(5.3)

Let's compose the Lagrange function. It includes the objective function (5.1) and the right-hand sides of the constraints (5.3), taken respectively with the coefficients
. There will be as many Lagrange coefficients as there are constraints in the problem.

The extremum points of the function (5.4) are the extremum points of the original problem and vice versa: the optimal plan of the problem (5.1)-(5.2) is the global extremum point of the Lagrange function.

Indeed, let the solution be found
problem (5.1)-(5.2), then conditions (5.3) are satisfied. Let's substitute the plan
into the function (5.4) and verify the validity of equality (5.5).

Thus, in order to find the optimal plan of the original problem, it is necessary to investigate the Lagrange function for an extremum. The function has extreme values ​​at the points where its partial derivatives are equal zero. Such points are called stationary.

We define the partial derivatives of the function (5.4)

,

.

After equalization zero derivatives we get the system m+n equations with m+n unknown

,(5.6)

In the general case, the system (5.6)-(5.7) will have several solutions, which include all the maxima and minima of the Lagrange function. In order to highlight the global maximum or minimum, the values ​​of the objective function are calculated at all found points. The largest of these values ​​will be the global maximum, and the smallest will be the global minimum. In some cases it is possible to use sufficient conditions for a strict extremum continuous functions (see Problem 5.2 below):

let the function
is continuous and twice differentiable in some neighborhood of its stationary point (those.
)). Then:

a ) if
, (5.8)

then is the strict maximum point of the function
;

b) if
, (5.9)

then is the strict minimum point of the function
;

G ) if
,

then the question of the presence of an extremum remains open.

Moreover, some solutions of the system (5.6)-(5.7) may be negative. Which is not consistent with the economic meaning of the variables. In this case, the possibility of replacing negative values ​​with zero should be analyzed.

Economic meaning of Lagrange multipliers. Optimal multiplier value
shows how much the value of the criterion will change Z when increasing or decreasing the resource j per unit, because

The Lagrange method can also be applied when the constraints are inequalities. So, finding the extremum of the function
under conditions

,

performed in several stages:

1. Determine the stationary points of the objective function, for which they solve the system of equations

.

2. From stationary points, those are selected whose coordinates satisfy the conditions

3. The Lagrange method is used to solve the problem with equality constraints (5.1)-(5.2).

4. The points found at the second and third stages are examined for a global maximum: the values ​​of the objective function at these points are compared - the largest value corresponds to the optimal plan.

Task 5.1 Let us solve Problem 1.3, considered in the first section, by the Lagrange method. The optimal distribution of water resources is described by a mathematical model

.

Compose the Lagrange function

Find the unconditional maximum of this function. To do this, we calculate the partial derivatives and equate them to zero

,

Thus, we have obtained a system of linear equations of the form

The solution of the system of equations is the optimal plan for the distribution of water resources over irrigated areas

, .

Quantities
measured in hundreds of thousands of cubic meters.
- the amount of net income per one hundred thousand cubic meters of irrigation water. Therefore, the marginal price of 1 m 3 of irrigation water is
den. units

The maximum additional net income from irrigation will be

160 12.26 2 +7600 12.26-130 8.55 2 +5900 8.55-10 16.19 2 +4000 16.19=

172391.02 (den. units)

Task 5.2 Solve a non-linear programming problem

We represent the constraint as:

.

Compose the Lagrange function and determine its partial derivatives

.

To determine the stationary points of the Lagrange function, one should equate its partial derivatives to zero. As a result, we obtain a system of equations

.

From the first equation follows

. (5.10)

Expression substitute into the second equation

,

from which there are two solutions for :

and
. (5.11)

Substituting these solutions into the third equation, we obtain

,
.

The values ​​of the Lagrange multiplier and the unknown calculate by expressions (5.10)-(5.11):

,
,
,
.

Thus, we got two extremum points:

;
.

In order to find out whether these points are maximum or minimum points, we use the sufficient conditions for a strict extremum (5.8)-(5.9). Pre expression for , obtained from the restriction of the mathematical model, we substitute into the objective function

,

. (5.12)

To check the conditions for a strict extremum, we should determine the sign of the second derivative of the function (5.11) at the extreme points we have found
and
.

,
;

.

In this way, (·)
is the minimum point of the original problem (
), a (·)
- maximum point.

Optimal Plan:

,
,
,

.

Description of the method

where .

Rationale

The following justification of the Lagrange multiplier method is not its rigorous proof. It contains heuristic reasoning that helps to understand the geometric meaning of the method.

2D case

Level lines and curve.

Let it be required to find the extremum of some function of two variables under the condition given by the equation . We will assume that all functions are continuously differentiable, and this equation defines a smooth curve S on surface . Then the problem is reduced to finding the extremum of the function f on the curve S. We will also assume that S does not pass through points where the gradient f turns to 0 .

Draw on the plane the level lines of the function f(i.e. curves). It can be seen from geometric considerations that the extremum of the function f on the curve S there can only be points at which the tangents to S and the corresponding level line are the same. Indeed, if the curve S crosses the level line f at a point transversally (that is, at some non-zero angle), then moving along the curve S from the point we can get both to the level lines corresponding to the larger value f, and smaller. Therefore, such a point cannot be an extremum point.

Thus, the necessary condition for the extremum in our case will be the coincidence of the tangents. To write it in analytical form, note that it is equivalent to the parallelism of the gradients of the functions f and ψ at this point, since the gradient vector is perpendicular to the tangent to the level line. This condition is expressed in the following form:

where λ is some non-zero number, which is the Lagrange multiplier.

Consider now Lagrange function depending on and λ :

A necessary condition for its extremum is the zero gradient . In accordance with the rules of differentiation, it is written as

We have obtained a system whose first two equations are equivalent to the necessary local extremum condition (1), and the third one is equivalent to the equation . From it you can find . In this case, since otherwise the gradient of the function f vanishes at a point , which contradicts our assumptions. It should be noted that the points found in this way may not be the desired conditional extremum points - the considered condition is necessary, but not sufficient. Finding a conditional extremum using an auxiliary function L and forms the basis of the Lagrange multiplier method applied here for the simplest case of two variables. It turns out that the above reasoning can be generalized to the case of an arbitrary number of variables and equations that specify the conditions.

On the basis of the method of Lagrange multipliers, one can also prove some sufficient conditions for a conditional extremum, which require an analysis of the second derivatives of the Lagrange function.

Application

• The Lagrange multiplier method is used to solve non-linear programming problems that arise in many areas (for example, in economics).
• The main method for solving the problem of optimizing the quality of encoding audio and video data for a given average bitrate (distortion optimization - English. Rate-distortion optimization).

see also

Links

• Zorich V. A. Mathematical analysis. Part 1. - ed. 2nd, rev. and additional - M.: FAZIS, 1997.

Wikimedia Foundation. 2010 .

See what "Lagrange multipliers" are in other dictionaries:

Lagrange multipliers- additional factors that transform the objective function of the extremal problem of convex programming (in particular, linear programming) when it is solved by one of the classical methods by the method of resolving factors ... ... Economic and Mathematical Dictionary

Lagrange multipliers- Additional factors that transform the objective function of the extremal problem of convex programming (in particular, linear programming) when it is solved by one of the classical methods by the method of resolving factors (Lagrange method). ... ... Technical Translator's Handbook

Mechanics. 1) Lagrangian equations of the 1st kind, differential equations of motion of a mechan. systems, which are given in projections onto rectangular coordinate axes and contain the so-called. Lagrange multipliers. Received by J. Lagrange in 1788. For a holonomic system, ... ... Physical Encyclopedia

Mechanics ordinary differential equations of the 2nd order, describing the motion of a mechanical. systems under the influence of forces applied to them. L. at. established by J. Lag range in two forms: L. at. 1st kind, or equations in Cartesian coordinates with ... ... Mathematical Encyclopedia

1) in hydromechanics, the equation for the motion of a liquid (gas) in Lagrange variables, which are the coordinates of the medium. Received French. scientist J. Lagrange (J. Lagrange; c. 1780). From L. at. the law of motion of h c medium is determined in the form of dependencies ... ... Physical Encyclopedia

Lagrange multiplier method, a method for finding the conditional extremum of the function f(x), where, with respect to m constraints, i varies from one to m. Contents 1 Description of the method ... Wikipedia

A function used in solving problems for a conditional extremum of functions of several variables and functionals. With the help of L. f. the necessary optimality conditions are written down in problems for a conditional extremum. There is no need to express only variables... Mathematical Encyclopedia

Method for solving problems for the Conditional extremum; L. m. m. consists in reducing these problems to problems for an unconditional extremum of an auxiliary function of the so-called. Lagrange functions. For the problem of the extremum of the function f (x1, x2,..., xn) for ... ...

Variables, with the help of which the Lagrange function is constructed in the study of problems for a conditional extremum. The use of L. m. and the Lagrange function makes it possible to obtain the necessary optimality conditions in a uniform way in problems for a conditional extremum ... Mathematical Encyclopedia

1) in hydromechanics, the equations of motion of a liquid medium written in Lagrange variables, which are the coordinates of the particles of the medium. From L. at. the law of motion of particles of the medium is determined in the form of dependences of coordinates on time, and according to them ... ... Great Soviet Encyclopedia

LAGRANGE METHOD

The method of reducing a quadratic form to a sum of squares, indicated in 1759 by J. Lagrange. Let it be given

from variables x 0 , x 1 ,..., x n. with coefficients from the field k characteristics It is required to bring this form to canonical. mind

using a nondegenerate linear transformation of variables. L. m. consists of the following. We can assume that not all coefficients of form (1) are equal to zero. Therefore, two cases are possible.

1) For some g, diagonal Then

where the form f 1 (x) does not contain a variable x g . 2) If all but then

where the form f 2 (x) does not contain two variables x g and x h . The forms under the square signs in (4) are linearly independent. By applying transformations of the form (3) and (4), form (1) after a finite number of steps is reduced to the sum of squares of linearly independent linear forms. Using partial derivatives, formulas (3) and (4) can be written as

Lit.: G a n t m a h e r F. R., Theory of Matrices, 2nd ed., Moscow, 1966; K ur o sh A. G., Course of Higher Algebra, 11th ed., M., 1975; Alexandrov P.S., Lectures on Analytic Geometry..., M., 1968. I. V. Proskuryakov.

Mathematical encyclopedia. - M.: Soviet Encyclopedia. I. M. Vinogradov. 1977-1985.

See what the "LAGRANGE METHOD" is in other dictionaries:

Lagrange method- Lagrange method - a method for solving a number of classes of mathematical programming problems by finding a saddle point (x *, λ *) of the Lagrange function, which is achieved by equating to zero the partial derivatives of this function with respect to ... ... Economic and Mathematical Dictionary

Lagrange method- A method for solving a number of classes of mathematical programming problems by finding the saddle point (x*,?*) of the Lagrange function, which is achieved by equating to zero the partial derivatives of this function with respect to xi and?i. See Lagrangian. (x, y) = C and f 2 (x, y) = C 2 on surface XOY.

From this follows a method for finding the roots of the system. nonlinear equations:

Determine (at least approximately) the interval of existence of a solution to the system of equations (10) or equation (11). Here it is necessary to take into account the type of equations included in the system, the domain of definition of each of their equations, etc. Sometimes the selection of the initial approximation of the solution is used;

Tabulate the solution of equation (11) for the variables x and y on the selected interval, or build graphs of functions f 1 (x, y) = C, and f 2 (x, y) = C 2 (system(10)).

Localize the supposed roots of the system of equations - find several minimum values ​​from the tabulation table of the roots of equation (11), or determine the intersection points of the curves included in the system (10).

4. Find the roots for the system of equations (10) using the add-on Search for a solution.