The simplex method is universal. It can be used to solve any linear programming problem. However, due to its versatility, it is not free from some shortcomings. In some cases, the so-called dual method is more suitable for solving linear programming problems. This method is based on the theory of duality, one of the most important components of the general theory of linear programming.

The duality theory is used to develop methods for solving many practically important classes of linear optimization problems: problems of transport type, linear integer problems, etc. Consider the main provisions of this theory.

Each problem of linear programming corresponds to another problem, in a certain sense opposite to it. If the first task is called direct, then the opposite is called dual. Since the dual with respect to the dual problem is the original direct problem, it does not matter which of the problems is called direct and which is dual. Therefore, the primal and dual problems are called dual pair problems.

The dual problem is formulated directly from the direct line using certain rules. Since direct problems can have restrictions in the form of inequalities of type , type or in the form of equalities, then the rules for obtaining dual problems for them turn out to be different.

There are symmetric, asymmetric and mixed dual problems. In symmetric problems, the constraints of the direct problem have the form . In the constraints of the asymmetric problem, the constraints of the direct problem use equal signs. In mixed problems, both types of relations "less than or equal to" and "Equal to" are used. In asymmetric and mixed problems, the newly introduced variables are not subject to the requirement that they be non-negative.

Computations based on duality relations begin by reducing the primal and dual problems to standard form. Therefore, we can confine ourselves to formulating the rules for the formation of a problem dual with respect to a standard linear programming problem. The rules for deriving the dual problem for other types of LP problem can be derived from these rules.

We write the LP problem in the standard form:

,

,

i=1,..,m; j=1,..,n.

Let's call this problem direct. Then the dual problem with respect to it will be:

,

i=1,..,m; j=1,..,n.

After analyzing the tasks, we can draw the following conclusions:

1. Each constraint of the primal problem corresponds to a variable of the dual problem.

2. Each variable of the direct problem corresponds to the restriction of the dual problem.

3. The coefficients for any variable in the constraints of the direct problem become the coefficients for the constraint of the dual problem corresponding to this variable, and the right side of the constraint being formed is equal to the coefficient for this variable in the expression of the objective function.

4. The form of the extremum of the dual problem is opposite to the form of the extremum of the direct problem;

5. The vectors B and C in the direct and dual problems are interchanged;

6. Matrix A of the dual problem is obtained by transposing the matrix A direct task;

7. All constraints of the dual problem have the form for the maximization problem and the form for the linear form minimization problem.

For the case of a symmetric dual problem:

For the case of an asymmetric problem:

The dual problem looks like:

Mixed problems contain restrictions in the form of equalities and inequalities. When compiling a dual problem, it is necessary to use the transition rules for symmetric and asymmetric problems.

The examples below serve to illustrate the rules for obtaining dual problems.

Example A linear programming problem is given (to the left of each constraint there is a dual variable associated with it). This task refers to asymmetrical.

,

Let us formulate a dual problem for this problem. The objective function of the dual problem is a linear form obtained as the product of the vector b=(10,20,60,80) and the vector of variables of the dual problem Y =( ). In addition, since the objective function is maximized in the primal problem, it is minimized in the dual problem. Taking into account the remarks made, we obtain

The left side of the first constraint of the dual problem is the product of the vector of the constraint system of the direct problem, associated with the variable , by the vector of variables of the dual problem. The right side of this constraint is equal to the coefficient of the variable , in the objective function of the direct problem.

And since, in addition, the direct problem is the problem of finding the maximum, the first constraint has the form:

Arguing similarly, we obtain the second constraint of the dual problem: . The absence of a variable in this constraint is due to the fact that there is no variable in the second constraint of the direct problem.

The variable associated with the third variable of the dual problem occurs only in the first constraint of the primal problem. For this reason, for the third constraint, we get . Arguing by analogy, we get the fourth, fifth and sixth restrictions: .

Thus, despite the fact that the non-negativity condition was not specifically imposed on the variables of the dual problem, nevertheless, for all of them it turned out to be satisfied.

Example Given a linear programming problem in non-standard form

,

,

,

Unlimited in sign .

We write this problem in standard form. To do this, we make a change of variables , let us introduce a redundant variable into the second constraint, and an additional variable into the third constraint. Get

,

.

Let us formulate a dual problem. Since the objective function is minimized in the direct problem, the objective function of the dual problem has the form .

For the same reason, the first, second, and third constraints of the dual problem, associated respectively with the variables are written as follows:

,

Since the variable occurs only in the second and the variable only in the third equation of the primal problem, the associated constraints of the dual problem are:

.

Thus, of the three variables of the dual problem, one - turned out to be unbounded in sign.

With the help of duality theorems, knowing the solution of one of the problems, you can find the optimal solution of the other without solving it.

Consider a mixed problem.

The dual task for it will look like:

If we use the canonical form of a linear programming problem, then we are dealing with an asymmetric linear programming problem.

The canonical form of the problem is:

The dual problem will look like:

Theorem 1. For any pair of feasible solutions to the primal and dual problems, the value of the objective function in the maximization problem does not exceed the value of the objective function in the minimization problem.

The practical value of this theorem is as follows. In practice, sometimes it is better to get a solution that is close to the optimum, but in a short time, than the optimal one, but in a much longer time. In this case, the last inequality can serve as an estimate of the proximity of the solution obtained at the next iteration to the optimum.

Theorem 2. If one of the dual problems has an optimal solution, then the other one also has an optimal solution, and the values ​​of the objective functions for both solutions are the same. If one of the dual problems has an unbounded objective function, then the other one is unsolvable, i.e. has no feasible solutions.

Theorem. For admissible solutions to be optimal, it is necessary and sufficient that they satisfy the system of equations

.

This theorem means that one of the variables of any of the problems is strictly greater than zero, then the restriction corresponding to it in the other dual problem is satisfied as a strict equality, and, conversely, if for an optimal solution any restriction is satisfied as a strict inequality, then the corresponding restriction the variable in the optimal solution is zero.

Example Let's solve a symmetrical problem. Let the original problem look like

Having solved the problem by a graphical method, we obtain

Let's create a dual problem for it

Since the objective functions at the optimum point are equal, then

Since the variables
, then the constraints corresponding to them in the dual problem contain an equal sign. These restrictions have the form

Substitute in the constraints values . Get

.

In this system, only the first inequality is strict. Hence, . Other values ​​of variables can be found from the system of equations

.

As a result of solving this system of linear algebraic equations, we obtain

We solve the same problem, but assuming that the solution is known

Since the second and third variables are strictly greater than zero, the restriction corresponding to them is satisfied as a strict equality.

.

Deciding this system equations, we get

If the original problem is solved by the simplex method and the coefficients - matrix - row of coefficients are obtained in the final objective function, then the solution of the dual problem can be found by the formula where is the matrix of coefficients for the basic variables of the objective function in the optimal solution of the original problem.

Consider the economic interpretation of the dual problem.

Theorem. The values ​​of the variables in the optimal solution of the dual problem are estimates of the influence of the free terms of the constraints of the original problem on the optimal value of its objective function. Because

Then the dual variables show how the objective function will change when the resource changes by one

Brief theory

We fill in the simplex table of the 0th iteration.

BP Simplex
relationship		 8 6 4 0 0 0 0 520 16 18 9 1 0 0 65/2 0 140 7 7 2 0 1 0 20 0 810 9 2 1 0 0 1 90 0 -8 -6 -4 0 0 0

Since we are solving the problem for the maximum, the presence of negative numbers in the index line when solving the problem for the maximum indicates that we have not received the optimal solution and that it is necessary to move from the table of the 0th iteration to the next one.

The transition to the next iteration is carried out as follows:

The leading column matches .

The key row is determined by the minimum ratios of free members and members of the leading column (simplex ratios):

At the intersection of the key column and the key row, we find the enabling element, i.e. 7.

Now we start compiling the 1st iteration. Instead of a unit vector, we introduce a vector .

IN new table we write 1 in place of the enabling element, all other elements of the key column are zeros. The key string elements are divided by the permissive element. All other elements of the table are calculated according to the rectangle rule.

We get the table of the 1st iteration:

BP Simplex
relationship		 8 6 4 0 0 0 0 200 0 2 31/7 1 -16/7 0 1400/31 8 20 1 1 2/7 0 1/7 0 70 0 630 0 -7 -11/7 0 -9/7 1 - 160 0 2 -12/7 0 8/7 0

The key column for the 1st iteration corresponds to .

We find the key line, for this we define:

At the intersection of the key column and the key row, we find the enabling element, i.e. 31/7.

We deduce the vector from the basis and enter the vector .

We get the table of the 2nd iteration:

BP Simplex
relationship		 8 6 4 0 0 0 4 1400/31 0 14/31 1 7/31 -16/31 0 8 220/31 1 27/31 0 -2/31 9/31 0 0 21730/31 0 -195/31 0 11/31 -65/31 1 7360/31 0 86/31 0 12/31 8/31 0

In the index row, all members are non-negative, so the following solution of the linear programming problem is obtained (we write it out from the column of free members):

Thus, it is necessary to sell 7.1 thousand rubles. goods of the 1st type and 45.2 thousand rubles. goods of the 3rd type. Goods of the 2nd type are unprofitable to sell. In this case, the profit will be maximum and will amount to 237.4 thousand rubles. When implementing the optimal plan, the remaining resource of the 3rd type will be 701 units.

Dual problems of linear programming.

Each linear programming problem has a dual problem.

Algorithm for compiling a dual problem.

Example 1

Write a dual problem

1. We reduce all inequalities of the system of constraints of the original problem to one meaning

2. Compose the augmented matrix

3. Transpose the matrix

4. We formulate the dual problem

Initial (direct) problem

Dual problem

The problem of linear programming can be considered as a model for the distribution of limited resources, in which the objective function, representing profit or income from production activities, is to be maximized. If we consider the problem of linear programming from this point of view, the corresponding dual problem receives an interesting economic interpretation.

variable at i of the dual problem represents the cost per unit of resource i. In the operations research literature, variables at i dual problem is often called dual prices . In addition, they are sometimes called shadow prices And simplex multipliers .

Similarly, for any pair of admissible solutions to the primal and dual problems, the inequality f < z can be interpreted as follows:

Income< Общая стоимость ресурсов

This relationship shows that as long as the total income from all activities is strictly less than the total cost of all resources used, the solution to both the direct and dual problems cannot be optimal. The optimum (maximum income) can only be achieved when all consumed resources are fully utilized.

Of great practical interest is the economic interpretation of the second duality theorem, as well as its corollary on complementary slackness.

1. If the total assessment of the i-th resource is positive

then this resource is fully utilized in accordance with the optimal plan x*

2. If i-th resource not fully used

then its optimal estimate is zero and i-th constraint insignificant.

3. If according to the optimal plan x* j-th production produced

then this production is efficient, since the unit price of the j-th product

is equal to the cost of its production in units

4. If production j-th production unprofitable (reduced costs are non-zero

then, according to the optimal plan, this product is not produced

Thus, the dual estimates are related to the optimal design of the direct problem. Any change in the initial data of the direct problem affects its optimal design and system of dual estimates. In turn, dual assessments serve as a tool for analyzing and making the right decisions in a changing business situation.

Rules for composing dual problems are presented. Symmetrical, asymmetrical and mixed pairs are considered. Examples of composing dual problems are analyzed.

Content

Dual or conjugate problems of linear programming have the property that from the solution of one of the problems it is possible to obtain the solution of another problem. Here we consider the rules for composing dual problems.

Symmetric dual problem

Consider a linear programming problem with non-negative variables and inequalities of the constraint system of the following form:
(1.1) ;
(1.2)
Here , , there are some numbers. All rows of system (1.2) are inequalities with signs .


(2.1) ;
(2.2)
Here all rows of system (2.2) are inequalities with signs . The coefficient matrix of the constraint system (2.2) is the transposed matrix of system (1.2). It contains rows and columns. The dual problem has variables . All variables are non-negative.

The original problem (1) is often called the direct problem, while problem (2) is called the dual problem. If we take problem (2) as the initial problem, then problem (2) will be a direct problem, and problem (1) will be a dual problem. Tasks (1) and (2) are called symmetric dual problems.

Thus, a symmetric dual problem can be composed only if all the variables of the original problem are non-negative and the system of constraints does not contain equalities. If the maximum of the objective function is sought, then the inequalities must be converted to the form . If a minimum is sought, then the inequalities must be converted to the form . To change the sign, you need to multiply both sides of the inequality by -1 .

An example of composing a symmetric dual problem


;

The original problem is the problem of finding the minimum. Therefore, all inequalities must have signs . The first and third inequalities contain the sign . Let's multiply them by -1 :




Let's transpose this matrix. That is, we write the first row as the first column, we write the second row as the second column, we write the third row as the third column.

The dual problem looks like:
;

;

Asymmetric dual problem

The challenge to the maximum

Let us consider the canonical maximum linear programming problem with non-negative variables and equalities of the constraint system:
(3.1) ;
(3.2)
Here , , there are some numbers. All rows of system (3.2) are equalities. All variables are non-negative.

The dual problem looks like:
(4.1) ;
(4.2)
Here all rows of system (4.2) are inequalities with signs . The coefficient matrix of the constraint system (4.2) is the transposed matrix of system (3.2). The dual problem has variables . Variables can be both positive and negative.

The difference between the asymmetric pair of problems (3) and (4) and the symmetric pair (1) and (2) is that the system of constraints (3.2) contains only equalities, while system (4.2) does not contain conditions for the variables to be non-negative.

The minimum challenge

Now consider the canonical minimum linear programming problem:
(5.1) ;
(5.2)

The dual problem looks like:
(6.1) ;
(6.2)

The system of constraints (6.2) differs from (4.2) in that the inequalities have signs .

Connection with a symmetric pair of dual problems

Let us show that an asymmetric pair of problems (3)-(4) can be obtained from a symmetric pair (1)-(2).

So, let's say we have a direct problem with an objective function
(3.1)
and a system of restrictions
(3.2)
Each equality can be represented by two inequalities:

We multiply inequalities with signs by -1 :

The system of constraints has inequalities.

According to formulas (1)-(2), we obtain a dual problem:
;


the dual problem has non-negative variables:
.
It is easy to see that these variables enter the problem in the form of differences
.

Let's make substitutions
.
Since and , the variables can be both positive and negative.

And we get the dual problem (4):
(4.1) ;
(4.2)

If we take (4) as the original problem, then, performing all the actions in the reverse order, we obtain the dual problem (3).

In the same way, it is possible to obtain the dual problem (6) from problem (5) and the dual problem (5) from problem (6).

mixed problem

Now consider a mixed problem.

Let we have a direct problem (1) for maximum, in the system of constraints of which the -th row is an equality. Then the dual problem has the form (2) with one exception - the variable can be either positive or negative. That is, there is no restriction.

The same will happen if we have a direct problem (2) for a minimum, in the constraint system of which the -th row is an equality. The dual problem has the form (1) with one exception - the variable can be of any sign.

Now let's assume that we have a direct maximum problem (1), but there is no constraint . That is, the variable can be either positive or negative. Then the dual problem has the form (2) with one exception - the -th row of the constraint system is an equality.

And finally, let we have a direct problem (2) for a minimum, but there is no constraint . Then the dual problem has the form (1) with one exception - the -th row of the constraint system is an equality.

All this allows us to formulate rules for composing dual problems.

Rules for Compiling Dual Problems

1. For the original maximum problem, we reduce all inequalities of the constraint system to the form:
.
For the original minimum problem, we reduce all inequalities to the form:
.
If it is required to change the sign, then we multiply both parts of the inequalities by -1 .
2. We compose the dual problem in the same way as for the symmetrical pair of problems.
3. If in the original problem, the -th row of the system of constraints is an equality, then we delete the condition of non-negativity of the -th variable of the dual problem.
4. If in the original problem, there is no non-negativity condition for the -th variable, , then in the -th line of the dual problem we change the inequality sign to the equal sign.

An example of composing a mixed dual problem

Given a linear programming problem:
;

Write a dual problem.

The objective function has a free term 5. To bring it to the form (2.1), we introduce a variable and add the equality . Then the task will take the form:

;

This problem is the problem of finding the minimum. Therefore, all inequalities must have signs . The third inequality contains the sign . So let's multiply it by -1 :

Let us rewrite the system of constraints, explicitly specifying the coefficients of the variables:

The matrix of coefficients of the constraint system has the form:

Let's transpose this matrix. That is, we write the first row as the first column, we write the second row as the second column, and so on.

Let us compose the dual problem as for a symmetrical pair.
;

Since in the original problem the 1st, 2nd and 4th lines of the constraint system are equalities, in the dual problem the variables , and can have any sign. The only non-negative variable is . Therefore, the conditions for the non-negativity of variables have the form:
.

Since the variables and can have arbitrary signs in the original problem, the 3rd and 4th rows of the system of constraints of the dual problem are equalities.

Thus, the dual problem looks like:
;

from the fourth equation. Replace the variable with its value and multiply the third row by -1 .

It should be noted that the methods for solving linear programming problems are not to economics, but to mathematics and computer technology. At the same time, the economist needs to provide 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. Which development environment software definitely is Python.

Formulation of the problem

In the publications, solutions to direct optimization problems by linear programming were considered and a reasonable choice of the scipy solver was proposed. optimize.

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

The solution of the dual problem is very important for the analysis of the use of resources. In this publication, it will be proved that the optimal values ​​of the objective functions in the original and dual problems are the same (i.e., the maximum in the original problem coincides with the minimum in the dual problem).

The optimal values ​​of the cost of material and labor will be evaluated by their contribution to the objective function. The result will be "objectively determined valuations" of raw materials and labor that do not match market prices.

Solution of the direct problem of the optimal production program

Considering high level mathematical training For the vast majority of users of this resource, I will not give balance equations with upper and lower restrictions and an introduction to the transition to equalities of additional variables. Therefore, I will immediately give the notation of the variables used in the solution:
N - the number of types of manufactured products;
m is the number of types of raw materials used;
b_ub - vector of available resources of dimension m;
A_ub is an m × N matrix, 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 - profit vector from the production of a unit of a product of each type;
x - the desired volumes of manufactured products of each type (optimal production plan) providing 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 for 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 (the minimum is determined by default, the coefficients of the objective function must be written with negative sign c = [-25, -35,-25,-40,-30] and ignore the minus sign before profit.

Notations used in the output of results:
x– an array of variable values ​​that provide the minimum (maximum) of the objective function;
slack– values ​​of additional variables. Each variable corresponds to an inequality constraint. The zero value of the variable 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 is the number of iterations performed.

Listing of the direct optimization problem solution

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # load 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) # output solution if key=="x": q=#used resources print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #residual resources print(" b_ub-A_ub*x", q1)


Problem solution results
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

  1. Found the optimal plan for the types of products
  2. Found actual resource usage
  3. Found the rest of the unused fourth type of resource [ 0. 0 0.0 0.0 90.909]
  4. There is no need for calculations according to item 3, since the same result is displayed in the slack variable

Solving the dual problem of the optimal production program

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

Let's introduce a new assignment of the desired variable x as some "shadow" price that determines the value of this resource in relation to the profit from the sale of manufactured products.

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

goal function
minF(x)=c×x

Restrictions
A_ub_T ×x≥ b_ub

Numerical values ​​and ratios 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 the restrictions from above with restrictions from the bottom, it is necessary to multiply both parts of the restriction by minus one – A_ub_T ×x≥ b_ub… To do this, write the initial data in the form: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Listing of the solution of 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)


Problem solution results
nit7
message Optimization terminated successfully.
fun5863.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 highest value for the producer, therefore this species resources must be purchased first, then the first and second kind. The fourth type of resource has zero value for the producer and is purchased last.

Results of comparison of direct and dual problems

  1. The dual task extends the possibilities of production planning, but by means of scipy. optimize is solved in twice the number of iterations than the direct one.
  2. The slack variable displays information about the activity of restrictions in the form of inequalities, which can be used, for example, to analyze the remains of raw materials.
  3. The direct problem is the maximization problem, and the dual problem is the minimization problem, and vice versa.
  4. The goal function coefficients in the primal problem are constraints in the dual problem.
  5. Constraints in the direct problem become coefficients of the goal function in the dual problem.
  6. The signs of the inequalities in the constraints are reversed.
  7. The matrix of the system of equalities is transposed.
Links