Dual tasks
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 economicmathematical 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 economicmathematical model and the meaningful interpretation of the dual problem II obtained in this way are given in the righthand part of Table. 6.1.
Table 6.1
Problem I (initial) 
Problem II (dual) 


under constraints: 
under constraints: 


and the condition of nonnegativity 
and the condition of nonnegativity 


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 nonnegativity 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 nonnegativity 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:
►
thematic pictures
Also We Can Offer!
Essay Writing
[...]
 Argumentative essay
 Best college essays
 Buy custom essays online
 Buy essay online
 Cheap essay
 Cheap essay writing service
 Cheap writing service
 College essay
 College essay introduction
 College essay writing service
 Compare and contrast essay
 Custom essay
 Custom essay writing service
 Custom essays writing services
 Death penalty essay
 Do my essay
 Essay about love
 Essay about yourself
 Essay help
 Essay writing help
 Essay writing service reviews
 Essays online
 Fast food essay
 George orwell essays
 Human rights essay
 Narrative essay
 Pay to write essay
 Personal essay for college
 Personal narrative essay
 Persuasive writing
 Write my essay
 Write my essay for me cheap
 Writing a scholarship essay
Case Study
[...]
Citation Style
[...]
Additional Services
[...]
CV
[...]
Assignment Help
[...]
Admission Services
[...]
Custom Paper
[...]