Chapter 4: �Duality and Post Optimal Analysis

A lecture by:

Dr. Moayad Tanash

​

​

Introduction

• One of the most important discoveries in the early development of linear programming was concept of duality and its many important ramifications.
• This discovery reveled that every linear programming problem has associated with it another linear programming problem called dual.
• The relation between the dual problem and the original problem prove to be extremely useful in a variety ways

​

Definition of the dual problem

• The dual problem is an LP defined directly and systematically from the primal ( original) LP model.
• The two problems are closely related that the primal solution of one problem automatically provides the optimal solution to the other one.
• The primal problem represents a resource allocation case where the dual problem represents resource valuation problem.
• Duality help simplification of the simplex problem.

​

The Dual problem

The following is a summary of how the dual is constructed from the (equation form) primal:

1. A dual variable is assigned to each primal (equation) constraint and a dual constraint is assigned to each primal variable.

2. The right-hand sides of the primal constraints provide the coefficients of the dual objective function.

3. The dual constraint corresponding to a primal variable is constructed by transposing the primal variable column into a row with (i) the primal objective coefficient becoming the dual right-hand side and (ii) the remaining constraint coefficients comprising the dual left-hand side coefficients.

4. The sense of optimization, direction of inequalities, and the signs of the variables in the dual are governed by the rules in Table 4.1

The Dual problem

Example 1

Example 1

Example 2

Example 2

Rules for constructing the dual

Optimal Dual Solution

The primal and dual solutions are so closely related that the optimal solution of either problem directly yield ( with little additional computation) the optimal solution to the other problem.

The dual of the dual is itself the primal, which means that the dual solution can also used to yield the optimal primal solution automatically.

​

​

Optimal Dual Solution

Two methods for determining the dual values

Method 1

​

​

​

Method 2

​

​

​

Example

Example

Example

​

​

​

​

Optimal Dual Solution

Using M-Method, the optimal primal tableau is

​

​

​

​

Method 1

​

​

Optimal Dual Solution

Method 2

Optimal invers =

and

(original objective coefficient ) = (x2,x1) = (12,5)

Thus, the optimal dual values are computed as:

​

Primal-Dual objective value

The relation between the primal and dual is given by :

​

​

​

​

• Only the sense of optimization ( minimize or maximize) is important in this case.

​

Primal-Dual objective value

In Example 4.2-1 ( x1 = 0, x2=0, x3=2.67) and ( y1=6, y2=0) are feasible primal and optimal solution. The associated value of the objective function are

​

z= 5x1+12x2+4x3 = 10.667

w= 10y1+8y2 = 60

​

thus, z= (10.67) for the maximization problem (primal) is less than w = (60) for the minimization problem ( dual). The optimal value of z = (54.8) falls within the range (10.67 60)

​

Simplex Tableau Computations

We can generate any iteration of the entire simplex tableau using the original data of the problem, the invers associated with the problem and the dual problem.

​

Example 4.2-3

Economical Interpretation of Duality

• The LP problems can be viewed as a resource allocation model in which the objective is to maximize revenue subject to the availability of limited recourses.
• Consider the following representation of the general primal and dual problems:

​

​

• Cj represents the revenue per unit of activity j
• bi represents the maximum availability
• Resources i is consumed at the rate aij units

per unit of activity j

​

​

Economical Interpretation of Duality

• Remember, for any two primal and dual feasible solution, the value of the objective function, when finite, must satisfy the following inequality:

​

• The strict equality z=w holds when both primal and dual solution are optimal
• Now, let us consider the optimal condition z=w first. Given that, the primal problem represents a resource allocation model, then we can see z a representing revenue dolars

Economical Interpretation of Duality

• Remember, for any two primal and dual feasible solution, the value of the objective function, when finite, must satisfy the following inequality:

​

• The strict equality z=w holds when both primal and dual solution are optimal
• Now, let us consider the optimal condition z=w first. Given that, the primal problem represents a resource allocation model, then we can see z a representing revenue dollars

Economical Interpretation of Duality

• This means that the dual variable, yi , represents the worth per unit of resource I

​

• Using the same dimensional analysis, we can interpret the inequality z<w (for any two feasible primal and dual solution) as

​

• This relationship says that so long as the total revenue from all the activities is less than the worth of the resources, the corresponding primal and dual solutions are not optimal.
• Optimality is reached only when the resources have been exploited completely. This can happen only when the input (worth of the resources) equals the output (revenue dollars).

Example

​

​

​

​

​

• The optimal dual solution shows that the dual price (worth per unit) of raw material M1 (resource 1) is y1 = .75 (or $750 per ton) and that of raw material M2 (resource 2) is y2 = .5 (or $500 per ton).
• These results hold true for specific feasibility ranges as was shown in Section 3.6.

Example

​

​

​

• For resources 3 and 4, representing the market and demand limits, the dual prices are both zero, which indicates that their associated resources are abundant (i.e., they are not critical in determining the optimum and, hence, their worth per unit, or dual price, is zero).

Additional Simplex Algorithms

• In the Simplex algorithm, the problem starts at a feasible solution.
• Successive iterations continue to be feasible until the optimal solution is reached at the last iteration.
• Dual simplex and generalized simplex are two other methods to solve LP.
• Dual simplex starts at a solution better than optimal infeasible solution.
• Successive iterations continue to be infeasible and optimal until feasibility is restored at the last iteration.
• Generalized simplex combines both primal simplex and dual simplex. It deals with problems both nonoptimal and infeasible.
• Successive iterations are associated with basic feasible or infeasible solutions

​

Dual Simplex method

Example (Dual Simplex method)

In the present example, the first two inequalities are multiplied by -1 to convert them to ≤ constraints. The starting tableau is thus given as follows:

Example (Dual Simplex method)

Example (Dual Simplex method)

Notice how the dual simplex works. In all the iterations, optimality is maintained (all reduced costs are ≤ 0) as each new iteration moves the solution toward feasibility. At iteration 3, feasibility is restored for the first time, and the process ends with the optimal feasible solution given as

Generalized Simplex method

• The primal simplex algorithm starts feasible but nonoptimal
• The dual simplex starts optimal but infeasible

​

Generalized Simplex method

The primal simplex algorithm starts feasible but nonoptimal

The dual simplex starts optimal but infeasible

​

Generalized Simplex method

The new solution is now feasible but nonoptimal, and we can use the primal simplex to determine the optimal solution. In general, had we not restored feasibility in the preceding tableau, we would repeat the procedure as necessary until feasibility is satisfied or until there is evidence that the problem has no feasible solution.

Post-Optimal Analysis

We deal with making changes in the parameter of the model and finding the new optimal solution.

Changes effecting feasibility

The feasibility of the current optimal solution maybe effected only if:

​

1. The right-hand side of the constraint is changed, or
2. A new constraint is added to the model

​

in both cases, infeasibility occurs when at least one element of the right hand side of the optimal tableau becomes negative, that is, one or more of the current basic variable become negative

Example Changes effecting feasibility

Example Changes effecting feasibility

Situation1: Supposed that TOYCO wants to expand its assembly lines by increasing the daily capacity of operations 1,2 and 3 by 40% to 602,644 and 588 minutes, respectively. How would this change effect the total revenue ?

​

Ans :

​

​

​

​

​

​

Example Changes effecting feasibility

​

Situation2: although the new solution is appealing from the standpoint of increasing revenue, TOYCO recognizes that this implementation may take time. Another proposal was thus made to shift the slacks capacity of operation 3 (x6=20 mins) to the capacity of operation 1. How would this changes impact the optimal solution.

The resulting solution is infeasible which required applying the dual simplex method

Addition of new constraints

The addition of a new constraint to an existing model can lead to:

1. The new constraint is redundant,
2. The current solution violate the new constraint, in which case the dual simplex method is used to restore feasibility

Example: suppose that TOYCO is changing the design for its toys and that required the addition of a fourth operation in the assembly line. The daily capacity of the new operation is 500 mins and the time per unit for the three products on this operation are 3,1 and 1 min respectively. Study the effect of the new operation on the optimal solution

The constraint of operation 4 is

3x1+x2+x3<=500

The constraint is redundant because it is satisfied by the current optimal solution ( x1=0,x2=100 and x3=230)

​

Addition of new constraints

Now, suppose that TOYCO unit times in the fourth operation are changed to 3,3,1 mins, respectively. All remaining data of the model remain the same. Will the optimal solution change ?

​

Ans: the constraint for operation 4 is

​

3x1+3x2+x3<=500

3x1+3x2+x3+x7=500

​

The new constraint is not satisfied by the current optimal solution. Thus, the new constraint must be added to the current optimal tableau

Addition of new constraints

Addition of new constraints

Changes effecting optimality

• Changes in the original objective coefficient
• Addition of a new economic activity ( variable) to the model

Changes objective coefficient

These changes effect only the optimality of the solution. Such changes require recomputing the z-row coefficient as follows:

​

1- Compute the dual values using method 2

​

2- use the new dual values to determine the new reduced cost ( z_row)

Changes effecting optimality

Two cases will result:

1. The new z-row satisfy the optimality condition. The solution remains unchanged ( the value of the optimal solution may change )
2. The optimality condition is not satisfied. Apply primal simplex method to recover optimality

Example:

In the TOYCO model, suppose that the company is instituting a revised pricing policy to meet the competition. The new unit revenues are $2, $3, and $4 for train, truck, and car toys, respectively. The new objective function is

Changes effecting optimality

Example:

In the TOYCO model, suppose that the company is instituting a revised pricing policy to meet the competition. The new unit revenues are $2, $3, and $4 for train, truck, and car toys, respectively. The new objective function is

​

Maximize z=2x1+3x2+4x3

​

Changes effecting optimality

Note that the right-hand side of the first dual constraint is 2, the new coefficient in the modified objective function. The computations show that the current solution, x1 = 0 train, x2 = 100 trucks, and x3 = 230 cars, remains optimal. The corresponding new revenue is computed as 2 * 0 + 3 * 100 + 4 * 230 = $1220. The new pricing policy is not recommended because it lowers revenue