Dual Problems, Economic Interpretation of the Problem Dual to...

Each task of linear programming corresponds to another problem, called dual, or conjugate, with respect to the original one. The duality theory turned out to be useful for carrying out qualitative studies of linear programming problems.

Economic interpretation of the problem dual to the problem of using resources

In Ch. 1, the problem of the use of resources is considered (the economic-mathematical model and a meaningful interpretation of this problem are presented in the left part of Table 6.1). In the given model, b - (r = 1, 2, ..., t) denotes the resource of the resource S 'a. - the number of units of the resource S jt consumed in the production of a unit of output P. (j = 1,2, ..., n); Cj - profit (gain) from the sale of a unit of output Р. (or the price of production Р.).

Suppose that some organization decided to purchase the resources 5, S 2, ..., S m of the enterprise and it is necessary to establish the optimal prices for these resources y v y 2, ..., y m.

Obviously, the buying organization is interested in the cost of all the resources Z in the quantities b v b 2, ..., b m at the prices, respectively, y y y 2, ..., y m were minimal, ie . At the same time, an enterprise selling resources is interested in the fact that the revenue received is not less than the amount that an enterprise can receive when processing resources into finished products. To produce a unit of output P {consumes "Π of resource units 54, a 2 [resource units S 2, ..., and n resource units 5 (, ..., a mi of resource units S m at the price of y ( , y 2, ..., y m. Therefore, to meet the seller's requirements, the cost of resources consumed in the manufacture of the unit of production P {should be less than its prices c v ie Similarly, you can make constraints in the form of inequalities for each type of product . The economic-mathematical model and the meaningful interpretation of the dual problem II obtained in this way are given in the right-hand part of Table. 6.1.

Table 6.1

 Problem I (initial) Problem II (dual)  under constraints: under constraints:  and the condition of non-negativity and the condition of non-negativity  Draw up such a plan of output X = (x v x 2, .... x n ), at which the profit (revenue) from the sale of products will be maximized, provided that the consumption of resources for each type of product does not exceed the available reserves Find such a set of prices (estimates) of resources Y = (y r y 2, ..., n ), at which the total cost of resources will be minimal, provided that the cost of resources in the production of each type of product will be no less than the profit (revenue) from the sale of this product

Resource prices in the economic literature have received different names: accounting, implicit, shadow. The meaning of these names is that it is conditional , false prices. Unlike external prices for products that are known, usually before the start of production, the resource prices are internal, so as they are not set from the outside, but are determined directly as a result of the solution of the problem, therefore they are often called estimates of resources.

Mutually dual linear programming problems and their properties

Let us consider formally two problems I and 11 of linear programming, presented in Table. 6.1, abstracting from the meaningful interpretation of the parameters that make up their economic and mathematical models. Both problems have the following properties.

1. In one problem, the maximum of a linear function is sought, in another - minimum.

2. The coefficients of the variables in the linear function of one problem are free members of the constraint system in the other.

3. Each of the problems is given in the standard form, and in the maximization problem all inequalities of the form & lt ;, & quot ;, and in the minimization problem all the inequalities of the form & gt; .

4. The coefficients matrices for variables in the constraint systems of both problems are transposed to each other: 5 6 5. The number of inequalities in the constraint system of a single problem is the same as the number of variables in another task.

6. Conditions for the non-negativity of variables exist in both problems.

Two tasks I and II of linear programming that have the specified properties are called symmetric mutually dual tasks . For the sake of simplicity, we will simply refer to them simply as dual tasks.

Based on the determination, it is possible to propose the following algorithm of drawing up of the dual problem.

1. To bring all the inequalities of the constraint system of the original problem to the same meaning: if in the original problem the maximum of a linear function is sought, then all inequalities of the constraint system lead to the form ≤ & quot ;, and if minimum to the form ≥ & quot ;. For this inequality, in which this requirement is not satisfied, multiply by -1.

2. To make up the extended matrix of the system A y in which to include the matrix of coefficients for the variables A, the column of the free terms of the constraint system and the row of coefficients for the variables in the linear function.

3. Find the matrix Ai, transposed to the matrix A r

4. Formulate a dual problem on the basis of the obtained matrix A and the condition of non-negativity of variables.

6.1. Write a problem that is dual to the following problem: under constraints: Solution. 1. Since the original maximization problem, we reduce all inequalities of the constraint system to the form ≤ for which both parts of the first and fourth inequalities are multiplied by -1. We get 2. Let's make up the extended matrix of the system: 3. We find the matrix A , transposed to A: 4. We formulate the dual problem: under constraints: [...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.

How to ...

We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)