Dual simplex method for solving linear programming problems. Solution of the dual problem Solution of the dual problem on the optimal production program

The formulations of the first and second duality theorems are given. It is shown how to obtain a solution to a dual problem from a solution to a straight line using duality theorems. Examples of problem solving.

Content

See also: Rules for composing dual problems

Here we will consider the question of how to obtain a solution to the dual problem from solving a direct problem.

Duality theorems

First duality theorem

If one of a pair of dual problems has an optimal solution, then the dual problem also has an optimal solution. In this case, the values of the objective functions of the direct and dual problems for optimal solutions are equal to each other.

If one of a pair of dual problems does not have a solution due to the unboundedness of the objective function, then the dual problem does not have a solution due to the incompatibility of the system of constraints.

Second duality theorem

;

Let's apply the second duality theorem. Let us substitute the optimal values of the variables into the system of constraints of the direct problem.
(A1.1.1) ;
(A1.1.2) ;
(A1.1.3) ;
(A1.1.4) .
Since the first and fourth lines are strict inequalities (they are not equalities), then
And .

Since and , then the 2nd and 4th lines of the dual problem are equalities:

Let's substitute the already found values and , we have:

From here
;
; .

The dual problem has the form:
;

Her decision
;

Example 2

Given a linear programming problem:
(A2.1.1) ;
(A2.1.2)
Find a solution to this problem by solving the dual problem graphically.

(A2.2.1) ;
(A2.2.2)

The solution to problem (A2.2) is given on the page “Solving linear programming problems using the graphical method.” The solution to problem (A2.2) has the form:
; .

According to the first duality theorem, the optimal value of the objective function is equal to
.

Let's apply the second duality theorem. Let us substitute the optimal values of the variables into the system of constraints of the direct problem (A2.2).
;
;
.
Since the third line is a strict inequality (they are not equality), then
.

Since and , then the 1st and 2nd lines of the dual problem (A2.1) are equalities:

Let's substitute the found value.

We solve a system of equations.
;
;
;
; ;
.

The solution to the original problem (A2.1) has the form:
; .

See also:

A method in which one of the mutually dual problems is first solved using the simplex method, and then the optimum and optimal solution of the other problem are found using duality theorems is called dual simplex method.

Theorem 1 (First Duality Theorem). If one of the mutually dual problems has an optimal solution, then so does

another, and the optimal values of their objective functions are equal to:

If the objective function of the original problem is unconstrained, then the system of constraints of the dual problem is inconsistent.

Note: the converse of the second part of the first duality theorem is not true in the general case.

Theorem 2. Components of the optimal plan for the dual problem ( having the non-negativity condition) are equal absolute values of coefficients

Components of the optimal plan for the dual problem ( not limited by sign) are equal coefficient values with the corresponding variables of the objective function of the original problem, expressed in terms of the free variables of its optimal solution.

Theorem 3. Positive (non-zero) components of the optimal solution to one of the problems symmetric dual pair correspond to the zero components of the optimal solution of another problem, i.e. for any and:

Theorem 4 (Third Duality Theorem). The components of the optimal design of the dual problem are equal to the values of the partial derivatives of the linear function according to the corresponding arguments, i.e.

. (7.2)

Economic interpretation of the third duality theorem: the components of the optimal plan for the dual problem show by how many monetary units the maximum profit (revenue) from the sale of products will change when the stock of the corresponding resource changes by one unit.

Example 9.1. Based on the solution to Example 5.2 (file “Algorithm and examples of the simplex method”), we will use the dual simplex method to determine the optimal solution to the dual problem.

Original problem	Dual problem

This dual pair is symmetric. The problems are written in standard form; let us reduce them to canonical form:

Original problem	Dual problem

Let us establish a correspondence between the variables of mutually dual problems.

Based on the solution to Example 5.2. The simplex table of the last iteration (Table 5.10) looks like:

Table 9.3

In accordance with Theorem 2, the optimal values of the variables and will be equal to the absolute values of the coefficients for the corresponding variables of the objective function of the original problem, expressed through the free variables of its optimal solution.

Using Table 9.3, we write down the objective function of the original problem, expressed in terms of the free variables of its optimal solution:

Hence, , .

The variables , , and are not present in the objective function (i.e., their coefficients are equal to zero), therefore, the optimal values of the corresponding variables , , and are equal to zero.

In accordance with Theorem 1, .

Thus, the optimal value of the objective function, which is achieved at .

Example 9.2. Based on the solution to the original problem, find the optimal solution to the dual problem using the dual simplex method.

Original problem	Dual problem

This dual pair is asymmetrical. Let us bring the dual problem to canonical form.

Original problem	Dual problem

To establish correspondence between the variables of the dual pair, we introduce two missing fictitious variables into the original problem.

Original problem	Dual problem

Let us establish a correspondence between the variables of mutually dual problems.

Table 9.4

Matching variables of a dual pair

Let's solve the original problem using the simplex method.

Using the Jordan-Gauss method, we select in the system of constraints of the original problem the variables and ( note: do not use dummy variables as basic ones).

As a result of the transformations, we obtain the following matrix of coefficients:

The system of constraints of the original problem will take the following form:

Let us express the basic variables in terms of free ones; as a result, the original problem will take the following form:

Substituting the obtained values of the basic variables into the objective function, it will take the following form:

As a result of solving the transformed original problem using the simplex method at the last iteration, we obtain the following simplex table:

Table 9.5

Simplex table of the optimal solution to the original problem

Structure and properties of the dual problem

Any problem of maximizing LP from an economic point of view can be considered as a problem of distributing limited resources b 1 , b 2 ,…, b m between different consumers, for example, between some technological processes, which are represented by columns A 1 , A 2 ,… A n of the problem constraint matrix . Any feasible solution to the problem LPx 1 ,x 2 ,…x n gives a specific distribution indicating the share of each resource that should be used in the implementation of the corresponding technological process.

Let's look at an example. The plant produces three types of products x 1, x 2 and x 3, each of which requires time spent on processing on lathes, milling and drilling machines. The amount of machine time for each machine is limited. Letc 1,c 2,c 3 – profit from the sale of a unit of the corresponding type of product. It is necessary to determine how much of each type of product must be produced during the week in order to obtain maximum profit.

Formally, this task is written as follows:

maximize (c 1 x 1 +c 2 x 2 +c 3 x 3) (1)

under restrictions

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ;

a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2 ;

a 31 x 1 +a 32 x 2 +a 33 x 3 ≤b 3 , (2)

where a 1 j ,a 2 j ,a 3 j is the time required to process a unit of the jth type of product, respectively, on turning, milling and drilling machines (j = 1, 2, 3); b 1 ,b 2 ,b 3 – weekly resource of machine time, respectively, for turning, milling and drilling machines.

Let us denote y 1 , y 2 and y 3 – the price of a unit of operating time on turning, milling and drilling machines. Thena 11 y 1 +a 21 y 2 +a 31 y 3 – can be interpreted as the cost of manufacturing a unit of product of the first type;a 12 y 1 +a 22 y 2 +a 32 y 3 – the cost of manufacturing a unit of product of the second type, etc. .d.

Let us assume that resource prices y 1 ,y 2 ,…,y m are chosen so that the following relations are satisfied:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ c 1 ;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ c 2 ;

a 13 y 1 +a 23 y 2 +a 33 y 3 ≥ c 3. (3)

Since b 1, b 2 and b 3 are the used machine time resources for each of the machines, then b 1 y 1 + b 2 y 2 + b 3 y 3 are the total production costs.

It is required to find such y 1 , y 2 and y 3 that satisfy conditions (3), under which the total production costs are minimized:

minimize g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

under conditions

y 1 ≥0;y 2 ≥0;y 3 ≥0.

This problem is called dual task in relation to problem (1), called direct.

Let us now write down the direct and dual problems in the general case.

Direct task:

maximize

under conditions

(7)

Dual problem:

minimize

under conditions

(10)

In matrix form, a pair of dual problems is written as follows:

maximize

under conditions

minimize

under conditions

A T y≥c; (15)

By comparing the recording forms of the direct and dual problems, the following relationships can be established between them:

if the direct problem is a maximization problem, then the dual problem will be a minimization problem, and vice versa;

coefficients of the objective function of the direct problem c 1 ,c 2 ,…,c n become free terms of the constraints of the dual problem;

free terms of the constraints of the direct problem b 1 ,b 2 ,…,b m become coefficients of the objective function of the dual problem;

the constraint matrix of the dual problem is obtained by transposing the constraint matrix of the direct problem;

the signs of inequalities in the restrictions are reversed;

the number of constraints of the direct problem is equal to the number of variables of the dual problem, and the number of constraints of the dual problem is equal to the number of variables of the direct problem.

The variables y 1 ,y 2 ,…,y m of the dual problem are sometimes called shadow prices.

It is more profitable to solve a dual problem than the original straight line if in the straight line

a problem with a small number of variables has a large number of constraints (m n).

The connection between the optimal solutions of the direct and dual problems is established through the following duality theorems.

THEOREM 1. If - admissible solutions to direct and dual problems, i.e. then

those. the values of the objective function of the direct problem never exceed the values of the objective function of the dual problem.

THEOREM 2 (fundamental duality theorem).If -admissible solutions to the direct and dual problems and if , That – optimal solutions to a pair of dual problems.

THEOREM 3.If in the optimal solution of the direct problem(5) – (7) i-th constraint is satisfied as a strict inequality, then the optimal value of the corresponding dual variable is equal to zero, i.e.

Where - ith row of matrix A.

The meaning of Theorem 3 is as follows. If a certain resource is available in excess and the i-th constraint in the optimal solution is satisfied as a strict inequality, then it becomes insignificant, and the optimal price of the corresponding resource is equal to 0.

Theorem 3 is complemented by Theorem 4, which establishes the relationship between the optimal solution of the direct problem and the constraints of the dual one.

THEOREM 4. If in the optimal solution of the dual problem the constraintjis satisfied as a strict inequality, then the optimal value of the corresponding variable of the direct problem must be equal to zero, i.e. if That

Let us give an economic interpretation of Theorem 4.

Since the quantities represent the prices of the corresponding resources, then

is the cost of the jth technological process, the value is the profit from sales per unit of product. Therefore, from an economic point of view, Theorem 2.7 means the following: if the j-th technological process turns out to be strictly unprofitable from the point of view of optimal resource prices, then in the optimal solution of the direct problem the intensity of this technological process should be equal to 0.

Thus, Theorem 4 expresses profitability principle optimally organized production.

It also follows from this that

(20)

Let us assume that among the variables x 1 ,x 2 ,…,x n of the direct problem there is a set of mvariables that have a non-zero value in the optimal solution. Let, for example, these be the first variables in order.

Then, based on equation (22), mprofitability conditions are obtained:

(21)

Let us present two more important theorems of duality theory.

THEOREM 5 (existence theorem).The direct and dual problems have optimal solutions if and only if they both have feasible solutions.

THEOREM 6 (duality theorem).Valid vectorx 0 is optimal if and only if the dual problem has such a feasible solutiony 0 , What

The following relationship exists between the optimal solutions of the direct and dual problems and the elements of the index rows of the simplex tables corresponding to these solutions:

i=1, 2, …,m;j=1, 2, …,n,

where n is the number of variables of the direct problem; m is the number of its constraints; are the corresponding elements of the index line of the direct and dual problems, respectively. Moreover, if n+i, where 1 ≤i≤m is greater than the number of column vectors of the constraint matrix of the extended form of the corresponding problem, then the elements are found by cyclically rearranging the elements of the index row, starting with the element

General case of duality

In the previous section, the basic relations were established for a pair of dual LP problems under constraints in the form of inequalities. Let us now generalize these results to the case of arbitrary restrictions.

Let the direct LP problem be given in the form:

maximize

under conditions

Then the dual problem with respect to (24)-(26) (or conjugate to it) is to minimize the linear form:

minimize

under conditions

Thus, a problem associated with a problem with mixed conditions is compiled according to the following rules:

If the variable x j of the direct problem is assumed to be non-negative, then the jth condition of the system of constraints (28) is an inequality.

If no such constraint is imposed on x j, then the jth constraint of the dual problem will be equality.

The signs of the variables of the dual problem y i and the corresponding restrictions of the direct problem are related in a similar way. Note that if we set m 1 = min 1 = n, then we obtain a special case of a pair of dual problems with constraints in the form of inequalities.

It should be noted that methods for solving linear programming problems include not to economics, but to mathematics and computer technology. At the same time, the economist needs to ensure the most comfortable conditions for dialogue with the appropriate software. In turn, such conditions can only be provided by dynamically developing and interactive development environments that have in their arsenal a set of libraries necessary for solving such problems. One of which software development environments is definitely Python.

Statement of the problem

The publications considered solutions to direct optimization problems using the linear programming method and proposed a reasonable choice of the scipy solver. optimize.

However, it is known that each linear programming problem corresponds to a so-called distinguished (dual) problem. In it, compared to the direct problem, rows turn into columns, inequalities change sign, instead of a maximum, a minimum is sought (or vice versa, instead of a minimum, a maximum is sought). The task dual to the dual is the original task itself.

Solving the dual problem is very important for analyzing resource use. In this publication, it will be proven that the optimal values of the objective functions in the original and dual problems coincide (i.e., the maximum in the original problem coincides with the minimum in the dual).

The optimal values of material and labor costs will be assessed by their contribution to the objective function. The result will be “objectively determined estimates” of raw materials and labor that do not coincide with market prices.

Solution of the direct problem of the optimal production program

Considering the high level of mathematical training of the vast majority of users of this resource, I will not present balance equations with upper and lower restrictions and the introduction of additional variables to move to equalities. Therefore, I will immediately give the designations of the variables used in the solution:
N – number of types of products produced;
m – number of types of raw materials used;
b_ub - vector of available resources of dimension m;
A_ub is a matrix of dimension m×N, each element of which is the consumption of a resource of type i for the production of a unit of product of type j;
c is the vector of profit from the production of a unit of each type of product;
x – the required volumes of produced products of each type (optimal production plan) ensuring maximum profit.

Goal function
maxF(x)=c×x

Restrictions
A×x≤b

Numerical values of variables:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Tasks
1. Find x to ensure maximum profit
2. Find the resources used when performing step 1
3. Find the remaining resources (if any) when performing step 1

To determine the maximum (by default, the minimum is determined, the coefficients of the objective function must be written with a negative sign c = [-25, -35,-25,-40,-30] and ignore the minus sign in front of the profit.

Notations used to display the results:
x– an array of variable values that provide the minimum (maximum) of the target function;
slack– values of additional variables. Each variable corresponds to an inequality constraint. A variable value of zero means that the corresponding constraint is active;
success– True, if the function managed to find the optimal solution;
status– decision status:
0 – the search for the optimal solution was completed successfully;
1 – the limit on the number of iterations has been reached;
2 – the problem has no solutions;
3 – the objective function is not limited.
nit– number of iterations performed.

Listing of the solution to the direct optimization problem

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # loading LP library c = [-25, -35,-25,-40,-30] # list of coefficients of the goal function b_ub = # list of resource volumes A_ub = [, # matrix of specific resource values , , ] d=linprog(c, A_ub, b_ub) # search for a solution for key,val in d.items(): print(key ,val) # solution output if key=="x": q=#used resources print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #remaining resources print(" b_ub-A_ub*x", q1)

Results of solving the problem
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
fun -5863.63636364
slack [0. 0. 0. 90.90909091]

Conclusions

The optimal plan for product types was found
Found actual resource usage
The remainder of the unused fourth type of resource was found [ 0. 0 0.0 0.0 90.909]
There is no need for calculations according to step 3, since the same result is displayed in the slack variable

Solution of the dual problem on the optimal production program

The fourth type of resource in the direct task is not fully used. Then the value of this resource for the enterprise turns out to be lower compared to resources that limit output, and the enterprise is willing to pay a higher price for the acquisition of resources that increase profits.

Let us introduce a new purpose for the desired variable x as some “shadow” price that determines the value of a given resource in relation to profit from the sale of manufactured products.

C – vector of available resources;
b_ub is the vector of profit from the production of a unit of each type of product;
A_ub_T – transposed matrix A_ub.

Goal function
minF(x)=c×x

Restrictions
A_ub_T ×x≥ b_ub

Numerical values and relationships for variables:
c = ; A_ub_T transpose(A_ub); b_ub = .

Task:
Find x indicating the value for the producer of each type of resource.

Features of the solution with the scipy library. optimize
To replace restrictions from above with restrictions from below, it is necessary to multiply both parts of the constraint by minus one – A_ub_T ×x≥ b_ub... To do this, write the original data in the form: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Listing of the solution to the dual optimization problem

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Results of solving the problem
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

Conclusions

The third type of resource has the greatest value for the manufacturer, so this type of resource should be purchased first, then the first and second types. The fourth type of resource has zero value for the manufacturer and is purchased last.

Results of comparison of direct and dual problems

The dual problem expands the capabilities of product planning, but using scipy. optimize is solved in twice the number of direct iterations.
The slack variable displays information about the activity of constraints in the form of inequalities, which can be used, for example, to analyze raw material balances.
The direct problem is a maximization problem, and the dual problem is a minimization problem, and vice versa.
The coefficients of the objective function in the direct problem are constraints in the dual problem.
Constraints in the direct problem become coefficients of the objective function in the dual one.
The signs of inequalities in restrictions are reversed.
The matrix of the system of equalities is transposed.

Links

Since there are three unit vectors, then
you can immediately write down the reference plan
X=(0,0,0,360,192,180).
Let's create a zero simplex table

We check the resulting reference plan
for optimality.
We calculate the value of the objective function and
simplex differences.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

As can be seen from the 0th table, non-zero
are the variables x4 , x5 , x6 , and x , x , x
1
2
3
are equal to zero, because They are not basic, but free.
Additional variables x4 , x5 , x6
take their values according to
restrictions.
These variable values correspond to this
"plan" under which nothing is produced, raw materials
is not used and the value of the objective function is
zero, i.e. the cost of manufactured products
absent.
This plan, of course, is not optimal.
This can also be seen from the 4th row of the table, in which
there are three negative scores -9, -16 and -10.

10.

Negative numbers are not only
indicate the possibility of increasing
total cost of manufactured products (in
columns above negative ratings
are positive numbers), but also
show how much this amount will increase
when introducing a unit of this or that into the plan
type of product.
So, the number -9 means that when included in
production plan for one product A
provides an increase in cost
products for 9 units

11.

If you include in the production plan for
one product B and C, then the total cost
manufactured products will increase
respectively by 10 and 16 units. Therefore, with
economically feasible
is the inclusion of products C in the plan.
The same must be done from that point
view that -16 is the smallest
negative assessment. So, to the basis
let's introduce the vector P3.

12.

Let's find the number Q.
360 192 180
Q min
;
;
min 30; 24;60
3
12 8
Let's enter it in the last column of the table.
The number 24 corresponds to the vector P5.
192/8=24 from an economic point of view
means how many products C
the enterprise can produce taking into account
consumption rates and available volumes of raw materials
each type.

13.

Since raw materials of each type are available
respectively 360, 192 and 180 kg, and for one
product C requires the expenditure of raw materials for each
types 12, 8 and 3 kg, then the maximum number
products C that can be manufactured
enterprise equals
min(360/12,192/8,180/3)=192/8=24, i.e.
limiting factor for production
products C is the available volume of raw materials
2nd type. Taking into account his enterprise can
produce 24 products C. In this case, raw materials of the 2nd type will be completely used and,
this means that the vector is subject to exclusion from
P5
basis.

14.

Let's create the following table. In it
the second line is permissive,
and the resolving column is the third. On
their intersection contains element 8.
Divide the second line by 8 and then
zero using the Jordan-Gauss method
or according to the formulas of the triangle third
column.

15.

16.

Let's calculate the simplex differences and fill in the 4th row of the table.
With this production plan
24 items C are produced and remain
unused 72 kg of raw materials 1st and 108 kg
raw materials of the 3rd type. 2nd type of raw material used
fully. The cost of all products at
in this regard is CU 384. Specified
the numbers are written in the Plan column. It's again
parameters of the task, but they have undergone
changes. The data of others has also changed
columns. Their economic content
has become even more complex.

17.

There is one negative rating -2.
The plan can be improved. Let us introduce into the basis
vector P2. Let's calculate
72 24 108
Q min ;
;
min 8; 48;72 8.
9 1/ 2 3 / 2
.
We derive from the basis P4.

18.

The permissive lines will be the 1st line and the 2nd
column. Permissive element 9.
Divide the 1st line by 9, fill in
1st row of the new table, then
Let's reset the 2nd column. For this
multiply the 1st line by (-1/2) and
add to the 2nd and then multiply the 1st
line by (-3/2) and add to the 3rd line.
Let's fill out table 2.

19.

20.

We are convinced of this
calculating simplex differences
1 cP1 c1 10 1 16 0.25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2 / 9,
5 cP5 -c5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

The optimal production plan is not
production of products A is envisaged. Introduction to
production plan for type A products would lead to
reduction of the indicated total cost.
This can be seen from the 4th line of the column, where the number is 5
shows that with this plan the inclusion
the output of a unit of product A leads to it
only to a decrease in the total value
value by 5 units
So, the plan provides for the release of 8 products
B and 20 products C. Raw materials of types 1 and 2
is used entirely, and type 3 remains 96 kg unused.

22. DUAL LINEAR PROGRAMMING PROBLEMS

Each ZLP can be matched
problem called dual to the original one
task.
Consider the problem of using
resources. Let's assume that enterprise A
produces n types of products, value
whose release is determined by variables
x1, x2, ..., xn
.
In production m different
types of resources, the volume of which is limited
values b1, b2, ..., bn.

23.

The cost rates of each resource per unit are known
each type of product forming a matrix,
a11
a21
A
...
am1
a12
a22
...
am 2
... a1n
... a2 n
... ...
...amn
as well as the cost per unit of production of each type
c1, c2, ..., cn
It is necessary to organize production so that
enterprise A was provided with maximum
profit.

24.

The task comes down to finding
non-negative variables
x1, x2, ..., xn,
in which resource consumption is not
exceeds their specified number, and
the cost of all products will reach
maximum.

25.

In mathematical form the problem
is written in the following form:
F c1 x1 c2 x2 ... c j x j ... cn xn max
under conditions
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x ... a x ... a x b
mj j
mn
m
m1 1 m 2 2
x j 0, j 1, n.

26.

Based on the same initial data, it may be
another task has been formulated.
Suppose that enterprise B decides to purchase
all resources available to enterprise A. B
In this case, enterprise B needs to establish
optimal prices for these resources, based on
following conditions:
total cost of resources for enterprise B
should be minimal;
for each type of resource, enterprise A needs
pay no less than the amount that it
the enterprise can receive during processing
of this type of resource into finished products.

27.

If denoted by y1 , y2 , ..., yn
prices at which enterprise B
buys resources from enterprise A, then
the task boils down to the following: find
such values of the variables y1, y2, ..., yn,
at which the cost of resources,
spent per unit of any type
products are not less than profit (prices)
for this unit of production, and the total
the cost of resources reaches
minimum,

28.

i.e. what should be the unit rating
each of the resources y1, y2, ..., yn,
so that for given volumes
available resources bi , given
costs c j (j 1, n) units
products and cost standards aij
minimize overall cost estimate
for all products.

29. Mat. dual problem model

In mathematical form the problem
is written as:
*
F b1 y1 b2 y2 ... bm ym min
under restrictions
a11 y1 a21 y2 ... am1 ym c1 ,
a y a y ... a y c ,
m2 m
2
12 1 22 2
..................................................
a y a y ... a y c ,
mn m
n
1n 1 2 n 2
yi 0, i 1, 2,..., m.

30. Economic meaning of the variables of the dual problem

Variables yi of the dual problem in the literature
may have different names: accounting, implicit,
shadow, objectively determined assessments,
dual assessments or “prices” of resources.
These two problems form a pair mutually
dual problems, any of which can
be considered as original. The solution to one
tasks gives an optimal production plan
products, and the solution is different - optimal
rating system for raw materials used for
production of these products.

31.

Dual problems of linear
programming is called
symmetrical if they satisfy
the following properties:
number of variables in dual problem
is equal to the number of constraints of the original problem, and
number of constraints of the dual problem
equal to the number equal to the number of variables in
original;
in one problem the maximum of the target is sought
functions, in the other – a minimum;
coefficients for variables in the target
functions of one task are free
members of the constraint system of another problem;

32.

in each problem the system of constraints is specified in
in the form of inequalities, and, in the problem of finding
maximum, all inequalities of the form “≤”, and in the problem on
finding the minimum, all inequalities of the form “≥”;
constraint system coefficient matrix
one is obtained from the other by transposition;
each constraint of one problem corresponds
variable of another task, variable number
matches the restriction number;
conditions for non-negative variables
are saved in both tasks;

33. Solving symmetric dual problems

First duality theorem.
If one of the dual problems
has an optimal solution, then
another has an optimal solution
task, while the target values
functions of the tasks are equal to each other.
If the target function is one of
tasks is not limited, then another task
has no solution at all

34. Economic content of the first duality theorem

If the problem of determining the optimal plan,
maximizing output is decidable, then
The problem of determining resource estimates is also solvable.
Moreover, the price of the product obtained as a result
implementation of the optimal plan coincides with
total assessment of resources.
Coincidence of target function values for
corresponding solutions to a pair of dual problems
sufficient for these decisions to be
optimal.
Solving the ZLP using the simplex method, we simultaneously
We solve both the original and dual problems.

35. Method for simultaneous solution of a pair of dual problems

Original problem: Dual problem:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cn xn max
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b ,
mn
n m
m
m1 1 m 2 2
x j 0, j 1, 2,..., n m.
bm ym min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
a y a y ... a y y c ,
m2 m
m 2
2
12 1 22 2
.............................................................
a y a y ... a y y c ,
mn m
m n
n
1n 1 2 n 2
yi 0, i 1, 2,..., m n.

36.

The number of variables in problems is the same
and equals m + n. In the original problem
the basic variables are

variables xn 1 , xn 2 , ..., xn m
,
and in the dual problem –
auxiliary non-negative
variables yn 1, yn 2, ..., yn m.
Basic variables of one problem
free variables correspond
another task, and vice versa.

37.

38.

When solving the ZLP using the tabular simplex method, solving the dual problem
contained in the last row of the table.
This is j.
Moreover, the main variables of the dual

corresponding additional
variables of the original problem, and
additional variables of the dual
tasks are contained in columns,
corresponding to the main
(initial) initial variables
tasks.

39. Example.

Let us formulate a model of the problem dual
to the problem from example 2 (beginning of the lecture):
Find the maximum of a function

40.

41.

The variables of the original problem x1, x2, x3 are the number of products A, B and C. Let us introduce
variables of the dual problem y1, y2, y3
Find the minimum of a function
F * 360 y1 192 y2 180 y3 min
under restrictions
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 y 8 y 3 y 16,
2
3
1
y1 , y2 , y3 0.

42. Consider the last table of the original problem

43.

The value of y1 in the last row of column P4,
those. y1 2 ;
9y 5
value 2 3 in the last row of column P5,
the value of y3 0 in the last row of column P6.
The remaining values are found in columns 1,2,3.
2 5
Y (; ;0;5;0;0)
9 3
At the same time
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
- This is the minimum cost for all products.
2/9 and 5/3 are shadow prices of raw materials of the 1st and 2nd
species respectively.