Duality in Linear Programming

Soon after Dantzig presented the linear programming problem, John von Neumann presented the duality theorem for linear optimisation.

In mathematical optimisation theory, principle of duality depicts that every optimisation problem may be viewed from the primal problem or the dual problem.

The solution to the dual problem provides a lower bound to the solution of the primal (minimisation) problem (Ekeocha, 2018). However, the optimal values of the primal and dual problems need not always be equal. The difference between the two is called the duality gap. The duality gap is zero for convex optimisation problems, for a constraint qualification condition.

The duality theory in linear programming is concerned with the study of the relationship between two related linear programming problems, where if the primal is a maximisation problem, then the dual is a minimisation problem and vice versa.

Duality Theorem in Linear Programming Problems

The duality theorem in linear programming states that for every linear programming problem, there exists another linear programming problem related to it and therefore, can be derived from it.

Following are the duality theorem:

• Sometimes, initial feasible solution to the dual is easier
• Sometimes, solving the dual is easier
• Sensitivity analysis
• Shadow prices
• An economic interpretation of duality

Sometimes, initial feasible solution to the dual is easier

Sometimes, the dual problem is easier to solve for an initial feasible solution than the primal problem. For example, if the primal is a minimisation problem, the constraints are often of the form Ax ≥ b, x ≥ 0, for b ≥ 0. The dual constraints would then likely be of the form ATy ≤ c, y ≥ 0, for c ≥ 0. For the dual problem, the origin is feasible but not for the primal.

Sometimes, solving the dual is easier

Solving for the dual is easier when the number of decision variables is significantly lower than slack or surplus variables. A primal problem with many constraints and few variables can be changed into a dual problem with few constraints and many variables. It is still possible to obtain the solution for the primal problem from the simplex tableau if the dual problem is solved.

Sensitivity analysis

Sensitivity analysis is a very important part of almost every linear programming study. Because most of the parameter values used in the original model are just estimates of future conditions, it is worthwhile to study the effect on the optimal solution if conditions are different. Duality allows sensitivity analysis of a linear programming study.

Shadow prices

Shadow prices are provided by the optimal solution for the dual problem. Shadow prices indicate the resulting change in contribution margin (in a maximisation problem) or the change in cost (in a minimisation problem) that occurs when a constraint is relaxed. Shadow prices depict the sensitivity of profit to resource quantities.

Interpretation of shadow price is quite valuable for two reasons:

• Shadow prices directly indicate the marginal value of an additional unit of any of the resources.
  
  
• Shadow prices is useful in determining the opportunity cost of allocating resources to an activity, i.e., ‘‘priced out’’ relative to other activities.

An economic interpretation of duality

The interpretation of the dual variable from the loss or economic point of view is prominent for future decisions in the activities being linear programmed.

Primal and Dual Problems

Below are some key features of the relationship between primal and dual problems:

• The dual of dual is primal.
  
  
• If either one of the problems has a solution, then the other one also has a solution and the optimum values of both are equal.
  
  
• In case either one of the problems has an infeasible solution, the value of the objective function of the other is unbounded.
  
  
• In case either one of the problems has an unbounded solution, the solution to the other problem is infeasible.
  
  
• If a feasible solution exists for the primal problem but not for the dual, the primal will not have a finite optimum solution and vice versa.
  
  
• The value of the objective function for any feasible solution of the primal is smaller than the value of the objective function for any feasible solution of the dual.

Converting Primal Into Dual Problem and Vice Versa

Steps for converting primal into a dual problem and vice versa are summarised below:

Step 1: Before formulating the dual problem, write the original linear programming problem in its standard form.

Step 2: Identify the coefficients of the variables of the primal problem as these will become the constraints equation of the dual problem.

Step 3: Identify the constraint values of the primal problem as these will become the coefficient of dual variables in the objective function of a dual problem.

Step 4: If primal problem is maximisation type, then the dual is minimisation type and vice versa. The constraints are also reversed, so if the inequality sign is ≤ in problem, it becomes ≥ in dual problem and vice versa.

Converting a primal into dual problem can be understood through the example given below:

Maximise Z = 40 (x1) + 75 (x2)

Subject to:

4 (x1) + 3 (x2) ≤ 180
3 (x1) + 5 (x2) ≤ 220
x1, x2 ≥ 0

The original linear programming problem can be changed to its dual as:

Minimise C = 180 (y1) + 220 (y2)

Subject to:

4 (y1) + 3 (y2) ≥ 40 3 (y1) +5 (y2) ≥ 75 (y1), (y2) ≥ 0

Economic Interpretation of Duality

Let us look at the economic interpretation of dual variables.

You read in the previous sections that for any pair of feasible primal and dual solutions:

“Objective value in the maximisation problem ≤ Objective value in the minimisation problem”

From this relationship, you can infer that if the total returns from all the activities is less than the resources cost, the corresponding primal and dual solutions are not optimal. Optimality is only met when the resources have been maximally exploited, which is only possible when the input equals the output.

For economic stability, the two quantities must be equal.

An LP problem can be considered as a resource allocation model whose aim is to maximise profit or minimise cost with limited resources. When we look at the problem with this perspective, the associated dual problem also provides rather interesting economic interpretations of the LP resource allocation model.

You saw in the last sections, that the primal and the dual are related in a mathematical sense. In this section, you will see how they are related in the economic sense.

If there are n variables and m resource constraints in the primal problem, there will be m variables and n constraints in the dual problem. Dual variables Ui directly correspond to the primal constraints, which means that dual variable (U1) corresponds with the first primal constraint, dual variable (U2) with the second primal constraint, etc.

Dual variables can therefore be interpreted as the marginal value of each constraint’s resources. These dual variables are known as shadow prices and specify the marginal value of each resource. Likewise, primal variables Xi also directly correspond to the dual constraints, i.e., X1 corresponds to the first dual constraint, X2 corresponds to the second dual constraint, and so on.

Let us use the following example to understand the economic impor- tance of the dual. Consider the following primal problem:

Maximise Z = 200 (X1) + 180 (X2)

subject to:

X1 + 25X2 ≤ 120
X1 + 20X2 ≤ 280
X1, X2 ≥ 0

The associated dual problem is:

Minimise C = 120U1 + 280U2

subject to:

U1 + 25U2 ≥ 200
U1 + 20U2 ≥ 180
U1, U2 ≥ 0

The dual variable U1 gives the marginal value of the first resource and the dual variable U2 gives the marginal value of the second resource. The first dual constraint limits the value of the resources used in producing one unit of X to be greater than or equal to the marginal revenue contribution of X.

In the primal problem, X1 uses one unit of first resource and 25 units of the second resource, which gives a return of 200 and X2 uses one unit of first resource and 20 units of second resource, which gives a return of 180. In the dual problem, the use of first resource times its marginal value (1U1) plus use of second resource times its marginal value (25U2) must be greater than or equal to the returns when one unit of X1 is produced (which is 200).

For the second constraint, the marginal value of first resource plus 20 times the marginal value of second resource has be greater than or equal to the returns when one unit of X2 is produced (which is 180).

The values of the dual variable are thus so constrained that the marginal value of the resources utilised by each primal variable is at least as much as the marginal profit contribution of that variable.

The objective function of the dual problem minimises the total mar- ginal value of the available resources. In the above problem, this equals to the capacity of the first resource times the marginal value of the first resource (120U1) plus the capacity of the second resource times the marginal value of the second resource (280 (U2)).

Thus, a linear problem for minimising the marginal value of the resource capacity (whose constraints require that the marginal value of the resources utilised for producing each product must be no less than the marginal value of the product) gives rise to dual variables. In case there is slack in the constraints, it implies the amount by which cost exceeds returns.

This can be considered a decision-making problem faced by a resource procurer in a competitive market. While the procurer would have to pay a minimum as much for the resources as the value of the goods produced using those resources, but they would try to minimise the total cost of the resources procured.

Primal Dual Relationships

If any changes are made in the original LP model, it will result in a change in the elements of the current optimal tableau. This may influence the optimality and/or the feasibility of the current solution.

An understanding of these relationships is important as they form the basis for the economic interpretation of the LP model and post-optimality analysis. Let us understand the types of prime-dual relationships:

Relationship 1: The dual problem of the dual problem is the primal problem, i.e., either of the primal and dual problems are the dual problem of the other. This means that there is symmetry in their positions, therefore, any fact that holds true for either the primal or dual problem has a corresponding fact that holds true for the other.

Relationship 2: The feasible and optimal solutions of the primal and dual problems are in a close relationship. If feasible solutions to both primal and dual problems exist, then any feasible value of the primal is an upper bound of any feasible value of the dual, while any feasible value of the dual is a lower bound of any feasible value of the primal.

Relationship 3: In case either of the primal and dual problems is unbounded, there is no feasible solution to the other. This relationship is a consequence of the relationship. Let us say a feasible solution to the dual problem exists, and then the primal problem is bounded from below.

Similarly, if a feasible solution to the primal problem exists, the dual problem is bounded above. It follows from the above statements that there is no feasible solution to one if either is unbounded.

Relationship 4: Strong duality theorem states that if an optimal solution to either of the primal and dual problems exists, then an optimal solution to the other also exists and the associated optimal values are equal. That is, if x is an optimal solution for the primal problem and y is an optimal solution for the dual problem, then cx = yb.

Relationship 5: The weak duality property defines the relation- ship between a given pair of solutions for primal and dual problems, where both solutions for their corresponding problems are feasible. If x is a feasible solution for the primal problem and y is a feasible solution for the dual problem, then cx ≤ yb.

Relationship 6: If either of the primal and dual problems is infeasible, then the other problem is infeasible or unbounded.