Duality and Post-Optimal Analysis
LP Post-Optimal Analysis
Sometimes, making changes in the parameters of an LP model, after finding its optimum basic solution, implies changes of the optimal (feasible) solution which require the further application of simplex-type algorithms. Post-optimal analysis determines the new optimal solution in an efficient way, by using duality and the primal-dual relationships. The following table lists the cases that can arise in post-optimal analysis and the actions needed to obtain the new solution (assuming one exists).
Condition after
parameters change Recommended action
Current solution remains No further action is necessary
optimal and feasible
Current solution becomes Use the dual* simplex method
infeasible to recover feasibility
Current solution becomes Use the primal# simplex
nonoptimal method to recover optimality
Current solution becomes Use the generalized* simplex
both nonoptimal method to obtain the new
and infeasible optimal solution
Additional* Simplex Algorithms
- Dual* Simplex Algorithm
- Generalized* Simplex Algorithm
The dual* simplex algorithm starts with a better than optimal and infeasible basic solution, and successive iterations (based on the dual* optimality condition and dual* feasibility condition) preserve the (better than) optimality of the basic solutions while moving towards its feasibility (the feasibility is reached at the last iteration). To start the LP optimal and infeasible, two requirements must be met:
- The objective function must satisfy the optimality condition on the primal simplex method;
- All the constraints must be of the type (≤).
Dual* feasibility condition. The leaving variable, xr, is the basic variable having the most negative value (ties are broken arbitrarily). If all the basic variables are nonnegative, the algorithm ends.
Dual* optimality condition. Given that xr is the leaving variable, let cj be the reduced cost of nonbasic variable xj and αrj the constraint coefficient in the xr-row and xj-column of the tableau. The entering variable is the nonbasic variable with αrj < 0 that corresponds to
min {|cj ∕ αrj|, where we use all nonbasic variables xj for which αrj < 0}
(ties are broken arbitrarily). If αrj ≥ 0 for all nonbasic xj, the problem has no feasible solution.
We illustrate this algorithm using Example 4.4-1 in CO_Curs5EX.pdf.
Generalized* Simplex Algorithm
The algorithm starts with both nonoptimal and infeasible basic solution. Successive iterations remove infeasibility by applying a version of the dual* simplex feasibility conditions (or there is evidence that the problem has no feasible solution – which happens if a basic variable is negative and all its constraint coefficients are nonnegative); then we can use the primal simplex method to determine the optimal solution (by applying the optimality condition of the primal simplex method). At the final iteration, the solution becomes optimal and feasible (assuming that one exists).
We illustrate this algorithm using Example 4.4-2 in CO_Curs5Ex.pdf. This example treats the following LP problem:
max z = 2x3
subject to
−x1 + 2x2 − 2x3 ≥ 8
−x1 + x2 + x3 ≤ 4
2x1 − x2 + 4x3 ≤ 10
x1, x2, x3 ≥ 0.
Definition of the dual problem
The dual of a (primal) LP problem is an LP defined directly and systematically from the original (primal) LP model as follows:
- A dual variable is defined for each primal constraint, i.e. constraint of the primal.
- A dual constraint is defined for each primal variable (with opposite inequality sign).
- The constraint (column) coefficients of a primal variable define the left-hand side of the dual constraint and its objective coefficient defines the right-hand side.
- The objective coefficients of the dual equal the right-hand side of the primal constraints (and taking the opposite sense of optimization).
Example 4.3-1 (Reddy Mikks model)
______
Reddy Mikks primal Reddy Mikks dual
______
Maximize z = 5x1 + 4 x2 Minimize w = 24y1 + 6y2 + y3 + 2y4
subject to subject to
6x1 + 4x2 ≤ 24 (resource 1, M1) 6y1 + y2 − y3 ≥ 5
x1 + 2x2 ≤ 6 (resource 2, M2) 4y1 + 2y2 + y3 + y4 ≥ 4
−x1 + x2 ≤ 1 (resource 3, market) y1, y2, y3, y4 ≥ 0
x2 ≤ 2 (resource 4, demand)
x1, x2 ≥ 0
Optimal solution: Optimal solution:
x1 = 3, x2 = 1.5, z = 21 y1= .75, y2 = 0.5, y3 = y4 = 0,
w = 21
Define the primal in equation form as follows:
Maximize or minimize z = ∑nj =1 cjxj
subject to
∑nj = 1 aijxj = bi, i = 1, 2, …, m
xj ≥ 0, j = 1, 2, …, n
Extended Simplex tableaux:
Primal variables
x1 x2 … xj … xn
Dual variables c1 c2 … cj … cn Right-hand side
y1 a11 a12 … a1j … a1n b1
y2 a21 a22 … a2j … a2n b2
......
......
ym am1 am2 … amj … amn bm
↑ ↑
jth dual Dual objective
constraint coefficients
Remark. The sense of optimization in the dual is always opposite to that of the primal. The constraint type in the dual (i.e. ≤ or ≥) is ≥ (≤) if the dual is a minimization (maximization) problem. The nonnegativity conditions hold in the dual standard form corresponding to the primal standard form. The dual of the dual is itself the primal.
Changes made in the original LP model will change the elements of the current optimal tableau, which in turn will affect the optimality and/or the feasibility of the current solution. A number of primal-dual relationships can be used to recompute the elements of the optimal simplex tableau, and will form the basis for the economic interpretation of the LP model as well as for post-optimality analysis.
The simplex tableau computations use only three elementary matrix operations:
- (row vector) × (matrix),
- (matrix) × (column vector), and
- (scalar) × (matrix).
Simplex Tableau Layout
Starting (basic) variables
Objective z-row =
Identity
Constraint matrix =
columns
(Starting tableau)
The coefficients of the starting (basic) variables in the starting tableau form an identity matrix. Subsequent iterations of the simplex tableau generated by the Gauss-Jordan row operations will modify the identity matrix to produce the inverse matrix in the columns corresponding to the starting variables in the starting tableau.
Starting (basic) variables
Objective z-row =
Inverse
Constraint matrix =
columns
(General iteration tableau)
Simplex Tableau Computations
The data for any simplex tableau corresponding to an iteration i of the primal simplex method can be generated from the original data of the problem (in the starting simplex tableau), the inverse matrix associated with iteration i, and the dual problem.
We can divide the computations in two types:
- Constraint columns (left- and right-hand sides).
- Objective z-row.
Formula 1:
Constraint column in iteration i =
Inverse matrix in iteration i× Original constraint column.
Formula 2:
Primal z-row coefficient of variable xj =
(Use of values of dual variables)
↓
Left-hand side of jth dual constraint −
Right-hand side of jth dual constraint.
The use of Formula 1 and Formula 2 is illustrated in Example 4.2-3 in CO_Curs5Ex.pdf. In this example we use the LP problem in Example 4.2-1 and its optimal tableau given in Table 4.4 below:
Basic x1 x2 x3 x4 R Solution
z 0 0 3/5 29/5 −2/5+M 544/5
x2 0 1 −1/5 2/5 −1/5 12/5
x1 1 0 7/5 1/5 2/5 26/5
Table 4.4 Optimal tableau of the primal of Example 4.2-1
Optimal Dual Solution
Method 1.
Optimal value of dual variable yi =
Optimal primal z-coefficient of starting variable xi
+
Original objective coefficient of xi.
Method 2.
Optimal values of dual variables =
Row vector of original objective coefficients of
optimal primal (basic) variables × Optimal primal inverse,
where the elements of the above row vector must appear in the same order in which the basic variables are listed in the Basic column of the optimal simplex tableau.
Example 4.2-1 in CO_Curs5Ex.pdf.
Primal-dual objective values
For any pair of feasible primal and dual problems:
Objective value in the maximization LP ≤
Objective value in the minimization LP
Optimum
Maximize z → ↓ ← Minimize w
Example 4.2-2 in CO_Curs5Ex.pdf
Economic Interpretation of Duality
Consider the following representations of the general primal and dual problems:
______
Primal Dual
______
Maximize z = ∑nj = 1cjxj Minimize w = ∑mi = 1biyi
subject to subject to
∑nj = 1 aijxj ≤ bi, i = 1, 2,…, m ∑mi = 1 aijyi ≥ cj, j = 1, 2, …, n
xj ≥ 0, j = 1, 2, …, n yi ≥ 0, i = 1, 2, …, m
______
The primal problem can be viewed as a resource allocation model with n activities and m resources. The coefficient cj in the primal represents the revenue per unit of activity j. Resource i, whose maximum availability is bi, is consumed at the rate aij units per unit of activity j.
- Economic Interpretation of Dual Variables
For any two primal and dual feasible solutions, the values of the objective functions, when finite, must satisfy the inequality
z = ∑nj=1cjxj ≤ ∑mi=1biyi = w.
The strict equality, z = w, holds when both the primal and dual solutions are optimal. Because bi represents the units available of resource i, this equation can be expressed dimensionally as
$ = ∑i (units of resource i) × ($ per unit of resource i),
which means that the dual variable yi represents the worth per unit of resource i, whose standard name is the dual (or shadow) price of resource i.
Now, the inequality z < w is interpreted as
(Revenue) < (Worth of resources).
This relationship says that as long as the total revenue is less than the worth of the resources, the corresponding primal and dual solutions are not optimal. Optimality (maximum revenue) is reached only when the resources have been exploited completely. In economic terms, the system is said to be unstable (nonoptimal) when the input (worth of the resources) exceeds the output (revenue). Stability occurs only when the two quantities are equal.
Example 4.3-1in CO_Curs5Ex.pdf.
- Economic Interpretation of Dual Constraints
The dual constraints can be interpreted by using Formula 2, which states that at any primal iteration
Objective coefficient of xj = (*)
(LHS of dual constraint j) − (RHS of dual constraint j)
= ∑mi=1 aijyi − cj..
By using dimensional analysis, we interpret ∑mi=1 aijyi as a cost; further
$ cost = ∑mi=1aijyi =
∑mi=1(usage of resource i per unit of activity j) ×
(cost per unit of resource i).
Here, the dual variable yi represents the imputed cost per unit of resource i, and we can think of the above sum as the imputed cost of all the resources needed to produce one unit of activity j. In the previous course, we referred to (∑mi=1 aijyi − cj) as the reduced cost of activity j. The maximization optimality condition of the (primal) simplex method says that an increase in the level of an unused (nonbasic) activity j can improve the revenue only if its reduced cost is negative, i.e.
Imputed cost of resources used by one unit of activity j <
Revenue per unit of activity j.
We use the TOYCO model of Example 4.3-2 to explain the different procedures.
TOYCO primal TOYCO dual
max z = 3x1 + 2x2 + 5x3 min w = 430y1 + 460y2 + 420y3
subject to subject to
x1 + 2x2 + x3 ≤ 430 (Operation 1) y1 + 3y2 + y3 ≥ 3
3x1 + 2x3 ≤ 460 (Operation 2) 2y1 + 4y3 ≥ 2
x1 + 4x2 ≤ 420 (Operation 3) y1 + 2y2 ≥ 5
x1, x2, x3 ≥ 0 y1, y2,y3 ≥ 0
Optimal solution: Optimal solution:
x1 = 0, x2 = 100, x3 = 230, z = $1350 y1 = 1, y2 = 2, y3 = 0, w = $1350
The associated optimum tableau for the primal is given as
Basic x1 x2 x3 x4 x5 x6 Solution
z 4 0 0 1 2 0 1350
x2 −1∕4 1 0 ½ −1/4 0 100
x3 3/2 0 1 0 ½ 0 230
x6 2 0 0 −2 1 1 20
Changes Affecting Feasibility
- Changes in the right-hand side
Such changes requires recomputing the RHS (which gives the values of the basic variables) of the (optimal) tableau using Formula 1.
New RHS of tableau in iteration i =
Inverse in iteration i × New RHS of constraints
Example 4.5-1 (Situation 1 & Situation 2 for the TOYCO model)
- Addition of New Constraints
The addition of a new constraint to an existing model may lead to one of the two cases:
- The new constraint is redundant, i.e. is satisfied by the current optimal solution, and hence can be dropped.
- The current (optimal) solution violates the new constraint, implying the application of the dual simplex method to restore feasibility.
Example 4.5-3 (Situation 1 & Situation 2 for the TOYCO model)
Changes Affecting Optimality
- Changes in the (original) Objective Function Coefficients
Such changes require recomputing the z-row coefficients (reduced costs) in two steps:
- Compute the values of the dual variables using Method 2;
- Use these values in Formula 2 to determine the new reduced costs (z-row coefficients).
If the new z-row satisfies the optimality condition, then the optimal solution remains unchanged (the optimum objective value may change, however); otherwise apply the (primal) simplex method to recover optimality.
Example 4.5-4 (Situation 1 & Situation 2, TOYCO model)
- Addition of a New Economic Activity
The addition of a new activity in the original LP model is equivalent with adding a new variable. This is desirable only if it is profitable, i.e. if it improves the optimum value of the objective function. The reduced cost of the new variable can be computed using Formula 2. It is advantageous to undertake the new activity only if it does not satisfy the optimality condition.
Example 4.5-5 (TOYCO model).