3.

Duality and Sensitivity Analysis

 Duality analysis
 Economic interpretation of duality
 Dual simplex algorithm
 Generalized simplex algorithm
 Sensitivity and post-optimal analysis
• Change in objective function coefficients
• Change in constraint values (RHS values)
• Change in decision variables (LHS values)
3.1 Dual LP model
 The dual LP model leads to intriguing economic interpretations of the LP
model, including dual prices and reduced costs.
 The dual problem is an LP defined directly and systematically from the
primal (or original) LP model.
 The dual problem uses exactly the same parameters as the primal problem,
but in different locations.
 The two models are so closely related that the optimal solution of one
problem automatically provides the optimal solution to the other.
 In the simplex method, solving one of the LP models can provide us the
solution of both models.
 In most LP models, the dual is defined for various forms of the primal
depending on the sense of optimization (maximization or minimization)
and types of constraints (≤, ≥ or =).

2
Rules of Dual LP model formulation from primal model
Primal (original) LP model Dual LP model

Maximize/Minimize Minimize/Maximize
𝑛 𝑚
𝑧 = ∑ 𝑐j 𝑥j 𝑤 = ∑ 𝑏i 𝑦i
j=1 i=1
subject to subject to
𝑛 𝑚
∑ 𝑎ij 𝑥j ≤/ ≥ 𝑏i , i = 1, 2, … , 𝑚. ∑ 𝑎ij 𝑦i ≥/≤ 𝑐j , j = 1, 2, … , 𝑛.
j=1 i=1

𝑥j ≥ 0, j = 1, 2, … , n. 𝑦i ≥ 0, i = 1, 2, … , m.
Where 𝑥j is a primal decision variable. Where 𝑦i is a dual decision variable.
3
Parameters and variables for dual LP model

4
 The dual LP problem is formulated under the assumption that the
primal LP problem is with no restriction that the 𝑏i values must to
be positive.
1) A dual variable is defined for each primal constraint.
2) A dual constraint is defined for each primal variable.
3) The constraint (column) coefficients of a primal variable define the
left-hand side coefficients of the dual constraint and its objective
coefficient define the right-hand side.
4) The objective coefficients of the dual equal the right-hand side of
the primal constraint equations.
5) The value of z equals the value of w if both the primal and dual
problems are optimal.

5
  The rules for determining the sense of optimization (maximization or
minimization) and the type of the constraint are summarized as
follows:
Primal model Dual model
Objective function constraint Objective function constraint
≤ or ≥ or = but should be
Maximization Minimization ≥
converted into equivalent (≤)
≥ or ≤ or = but should be
Minimization Maximization ≤
converted into equivalent (≥)

6
Example 1: Convert the LP problem into its dual form

Primal LP model Dual LP model

Maximize z = 40x1+ 50x2 Minimize w = 40y1+ 120y2
subject to subject to
x1 + 2x2 ≤ 40 y1 + 4y2 ≥ 40
4x1 + 3x2 ≤ 120 2y1 + 3y2 ≥ 50
x1, x2 ≥ 0 y1, y2 ≥ 0

7
 Example 2: Convert the primal LP model into its dual model
Primal LP model
Maximize z = 5x1+ 12x2 + 4x3
subject to Dual LP model
x1 + 2x2 + x3 ≤ 10 (1) Minimize w = 10y1+ 8y2 - 8y3
2x1 - x2 + 3x3 = 8 (2) subject to
x1, x2, x3 ≥ 0 y1 + 2y2 - 2y3 ≥ 5
Constraint (2) should be converted into equivalent (≤) 2y1 - y2 +y3 ≥ 12
x1 + 2x2 + x3 ≤ 10 (1) y1 + 3y2 - 3y3 ≥ 4
2x1 - x2 + 3x3 ≤ 8 (2) y 1, y 2, y 3 ≥ 0
-2x1 + x2 - 3x3 ≤ -8 (3)
x1, x2, x3 ≥ 0
8
Example 3: Convert the primal LP model into its dual model

Primal LP problem Dual LP model

Minimize z = 3x1+ 2x2 Maximize w = 10y1+ 6y2 +12y3
subject to subject to
5x1 + x2 ≥ 10 5y1 + y2 + y3 ≤ 3
x1 + x2 ≥ 6 y1 + y2 + 4y3 ≤ 2
x1 + 4x2 ≥ 12 y1, y2, y3 ≥ 0
x1, x2 ≥ 0

9
Example 4: Convert the primal LP model into its dual model
Primal LP problem
Minimize z = 5x1+ 3x2
subject to Dual LP model
x1 + 2x2 ≤ 6 Maximize w = -6y1+ 5y2 - 5y3 + 12y4
x1 + x2 = 5 subject to
5x1 + 2x2 ≥ 12 -y1 + y2 - y3 + 5y4 ≤ 5
x1, x2 ≥ 0 -2y1 + y2 - y3 + 2y4 ≤ 3
The constraints should be converted into (≥) y 1, y 2, y 3, y 4 ≥ 0
-x1 - 2x2 ≥ -6
x1 + x2 ≥ 5
-x1 - x2 ≥ -5
5x1 + 2x2 ≥ 12 10
 Solution for primal and dual models
 The primal and dual solutions are so closely related that the optimal
solution of either problem directly yields the optimal solution to the
other.
 In a primal LP model in which the number of decision variables is
considerably smaller than the number of constraints, computational
savings may be realized by solving the dual model because the
amount of simplex computation depends largely on the number of
constraints.
 It must be noted that the dual of the dual is itself the primal, which
means that the dual solution can also be used to yield the optimal
primal solution automatically.

11
 When both the primal and dual models are with the optimal solution
(in the optimal simplex tableau):
1. The value of z = the value of w.
2. The value of dual decision variable yi = the absolute value of the
z-row coefficient value of a primal slack/surplus variable si.
3. The value of a primal decision variable xj = the absolute value of
the w-row coefficient value of a dual slack/surplus variable sj.
 With the help of these relationships, ill-behaved minimization
problems with (≥) constraints can be handled using the dual form of
maximization problem with (≤) problem.

12
Example 1: Solve both the primal and dual problems to compare the z/w-row
values of their optimal simplex tableaus.

Primal LP model Dual LP model

Maximize z = 160x1+ 200x2 Minimize w = 40y1+ 216y2 + 240y3
subject to subject to
2x1 + 4x2 ≤ 40 2y1 + 18y2 + 24y3 ≥ 160
18x1 + 18x2 ≤ 216 4y1 + 18y2 + 12y3 ≥ 200
24x1 + 12x2 ≤ 240 y1, y2, y3≥ 0
x1, x2 ≥ 0

13
 The optimal simplex tableau for the primal model

 The optimal solution values for the primal model are x1 = 4, x2 = 8, s1 = 0,

s2 = 0, s3 = 48, and z = 2240.
 Referring to the magnitudes of the z-row coefficients of the primal slack
variables, the values of dual decision variables and the value of the
objective function are y1 = 20, y2 = 20/3, y3 = 0, and w = 2240.
14
 The optimal simplex tableau for the dual model

 The optimal values of the dual problem are y1 = 20, y2 = 20/3, y3 = 0 and w =
2240.
 Referring to the coefficients of dual surplus variables in the w-row, the values of
the primal decision variables and the value of the objective function are x1 = 4, x2
= 8 and z = 2240.

15
Example 2: Which model shall be solved for computational savings?

Primal LP problem Dual LP model

Minimize z = 3x1+ 2x2 Maximize w = 10y1+ 6y2 +12y3
subject to subject to
5x1 + x2 ≥ 10 5y1 + y2 + y3 ≤ 3
x1 + x2 ≥ 6 y1 + y2 + 4y3 ≤ 2
x1 + 4x2 ≥ 12 y1, y2, y3 ≥ 0
x1, x2 ≥ 0
The answer is the dual model, because
1) The number of constraints are relatively smaller in the dual model.
2) Solving the (≤) constraints are easier than the (≥) constraints.

16
After solving the dual model, the optimal simplex tableau is
determined.
Iteration 3

Referring to the magnitudes of the w-row coefficients of s1 and s2, the

values of the primal decision variables, x1 = 1 and x2 = 5; and z = w =13.
The values of dual variables y1 = 1/4, y2 = 7/4 and y3 = 0.

17
3.2 Economic interpretation of duality
 The LP problem can be viewed as a resource allocation model in
which the objective is to maximize revenue or profit subject to the
availability of limited resources.
 Looking at the problem from this standpoint, the associated dual
problem offers interesting economic interpretations of the LP
resource allocation model.
 As a resource allocation model, the primal problem has n economic
activities and m limited resources.
 The coefficient cj in the primal represents the revenue/profit per unit
of activity (decision variable) j.
 Resource i, whose maximum availability is bi , is consumed at the rate
aij units per unit of activity j.

18
 In the resource allocation LP model, the general primal and dual
problems can be represented as:
Primal LP model Dual LP model

Maximize Minimize
𝑛 𝑚
𝑧 = ∑ 𝑐j 𝑥j 𝑤 = ∑ 𝑏i 𝑦i
j=1 i =1
subject to subject to
𝑛 𝑚
∑ 𝑎ij 𝑥j ≤ 𝑏i , i = 1, 2, … , 𝑚. ∑ 𝑎ij 𝑦i ≥ 𝑐j , j = 1, 2, … , 𝑛.
j=1 i=1

𝑥j ≥ 0, j = 1, 2, … , 𝑛. 𝑦i ≥ 0, i = 1, 2, … , m.
19
1. Economic interpretation of dual variables
 For any two primal and dual feasible solutions, the values of the
objective functions, when finite, must satisfy the following inequality:

20
 𝑛 𝑚

𝑧 = ∑ 𝑐j 𝑥j ≤ ∑ 𝑏i 𝑦i = 𝑤
j=1 i=1
 The strict equality, z = w, holds when both the primal and dual
solutions are optimal.
 Given that the primal problem represents a resource allocation
model, the z value represents the total revenue in a given currency.
 The bi represents the number of units available of resource i, the
equation z = w can be expressed in a specified currency when the
dual variable, yi, represents the worth per unit of resource i.
 The dual variable is called worth per unit of resource i or dual
price or shadow price of the system.
 It is the rate of change in the optimal objective function value per
unit change in the availability of resource, i.
21
 The value of w = ∑𝑚 i =1 𝑏 i 𝑦 i represents the total worth of resources.
 The inequality z < w implies that 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 (maximum revenue or profit) is reached only when the
resources have been exploited completely, which can happen only
when the input equals the output.
 In economic terms, the system is said to be unstable (non-optimal)
when the input (worth of the resources) exceeds the output
(revenue).
 Stability occurs only when the two quantities are equal.

22
Example 1: Refer to Example 1.
 The dual prices (worth per unit) of the three resources are y1 = 20, y2
= 20/3 and y3 = 0 respectively.
 The dual prices are also called the contributions to the objective
function values per unit change in available resources.
 The dual prices the third resource is zero, which indicates that the
resource is abundant (free resource).
 The optimal primal simplex tableau indicates this resource has the
slack value of s3 = 48 (oversupplied).
 Such kinds of resources are also known as non-binding resources,
however resources 1 and 2 are binding resources because they affect
the revenue/profitability of the objective function.

23
Example 2: A firm deals with the production of two types of paints
(interior and exterior) using two raw materials (M1 and M2) and
subject to market and demand limits represented by the third and
fourth constraints. The model determines the amounts (in tons/day) of
interior and exterior paints that maximize the daily revenue or profit.

24
 The optimal dual solution shows that the dual price (worth per unit)
of raw material M1 (resource 1) is y1 = 0.75 and that of raw material
M2 (resource 2) is y1 = 0.5.
 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 or freely available (no market and demand
constraints) .
 Hence, their worth per unit is zero, which are nonbinding resources.

25
2. Economic interpretation of dual constraints
 The maximization optimality condition of the simplex method says
that an entering non-basic activity j can improve revenue only if its
improvement rate is positive (its z-row coefficient value is positive).
 The z-row value = cj - zj, and this term is called the net contribution or
improvement rate to the objective function value as an activity j is
produced.
 The negative of the z-row value, or zj - cj, is called reduced cost and
executing an activity j can improve revenue when its reduced cost is
negative.
 The dual variable yi represents the price or imputed cost per unit of
resource i, and from this, the quantity ∑ 𝑚 i=1 𝑎 ij 𝑦 i is the imputed cost
of all the resources needed to produce one unit of activity (decision
variable) j.
26
 This total imputed cost equals the zj value of each activity j.
 The quantity, ∑ 𝑚 𝑎 i j 𝑦 i - cj, is the reduced cost of an activity j.
i=1
 An activity j must be produced only if its reduced cost is negative in
maximization problem (the opposite is true in minimization problems).
 This condition states that:

 The maximization optimality condition thus says that it is economically

advantageous to increase an activity to a positive level if its unit
revenue exceeds its unit imputed cost.
27
Example: A toy assembly company assembles three types of toys:
trains, trucks, and cars using three operations. Available assembly
times for the three operations are 430,460, and 420 minutes per day,
respectively, and the revenues per toy train, truck, and car are $3, $2,
and $5, respectively. The assembly times per train for the three
operations are 1,3, and 1 minutes, respectively. The corresponding
times per truck and per car are (2,0,4) and (1,2,0) minutes for the three
operations respectively.
Solution
 Letting x1, x2, and x3 represent the daily number of units assembled of
trains, trucks and cars, the primal LP model and its dual model are
given as:
28
 Primal LP model Dual LP model
Maximize z = 3x1+ 2x2 + 5x3 Minimize w = 430y1+ 460y2 + 420y3
subject to subject to
x1 + 2x2 + x3 ≤ 430 y1 + 3y2 + y3 ≥ 3
3x1 + 2x3 ≤ 460 2y1 + 4y3 ≥ 2
x1 + 4x2 ≤ 420 y1 + 2y2 ≥5
x1, x2 , x3 ≥ 0 y1, y2, y3 ≥ 0

 Solving the primal model is preferable since it is maximization

problems with all (≤ ) constraints.
29
The optimal simplex tableau of the primal model is:
Iteration 3

 The optimal solution values are x1 = 0, x2 = 100, x3 = 230, and z =1350.

 Referring to the coefficients of slack variables in the z-row, dual prices
are y1 = 1, y2 = 2, y3 = 0; and w =1350.
 The reduced costs of decision variables for x1 is 4, for x2 is 0 and for x3
is 0.
30
 The optimal primal solution calls for producing no toy trains, 100 toy
trucks, and 230 toy cars.
 Suppose that the company is interested in producing toy trains as well.
How can this be achieved?
 Looking at the problem from the standpoint of the interpretation of the
reduced cost for toy trains will become attractive economically only if the
imputed cost of the resources used to produce one toy train is strictly less
than its unit revenue.
 The company thus can either increase the unit revenue per unit by raising
the unit price, or it can decrease the imputed cost of the used resources.
 An increase in unit price may not be possible because of market
competition.
 A decrease in the unit imputed cost is more plausible because it entails
making efficiency improvements in the assembly operations.

31
3.3 Dual simplex algorithm (method)
 In the previous simplex algorithm, the LP starts at a basic feasible
solution and successive iterations continue to be feasible until the
optimal is reached at the last iteration. This algorithm is often
referred to as the primal simplex method.
 In the dual simplex, the LP starts at a better than optimal and basic
infeasible solution and successive iterations remain infeasible and
(better than) optimal until feasibility is restored at the last iteration.
 Dual feasibility condition (selecting a leaving variable) - 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 (feasibility
is attained).

32
 Dual optimality condition (selecting an entering variable) - Given
that xr is the leaving variable, let dj be the z-row coefficient value of
any non-basic variable xj and arj the constraint coefficient in the xr-row
and xj-column of the tableau.
 The entering variable is the non-basic variable with arj < 0 that
corresponds to
𝑑j
min , 𝑎𝑟 j <
Nonbasic variable 𝑥 j 𝑎 𝑟j
0
 Ties are broken arbitrarily.
 If arj > 0 for all non-basic xj, the problem has no feasible solution.

33
 Requirements to use the dual simplex method

 To start the LP optimal and infeasible, two requirements must be met:

‒ The objective function must satisfy the optimality condition of
the regular simplex method.
‒ All the constraints must be converted into the type (≤) using
different conversion techniques.

34
Example: Solve the problem using the dual simplex method.
LP problem Equivalent all (≤) constraints
Minimize z = 3x1+ 2x2 + x3 Minimize z = 3x1+ 2x2 + x3
subject to subject to
3x1 + x2 + x3 ≥ 3 -3x1 - x2 - x3 ≤ -3
-3x1 + 3x2 + x3 ≥ 6 3x1 - 3x2 - x3 ≤ -6
x1 + x2 + x3 ≤ 3 x1 + x2 + x3 ≤ 3
x1, x2, x3 ≥ 0
x1 , x2, x3 ≥ 0

 Convert the problem into its standard form and apply the dual
simplex algorithm.
35
The standard form is

Minimize z = 3x1+ 2x2 + x3

subject to
-3x1 - x2 - x3 + s1 = -3
3x1 - 3x2 - x3 + s2 = -6
x 1 + x 2 + x 3 + s3 = 3
x1 , x2, x3 , s1, s2, s3 ≥ 0

36
 The initial solution (Iteration 0)

 This basic solution is (better than) optimal (all the z-row coefficients
of non-basic variables are non-negative for minimization model) and
infeasible (the values of basic variables s1 and s2 are negative).
 The next step is determining a leaving variable and an entering
variable respectively using feasibility and optimality conditions.
37
 The pivots are selected as follows:

 The leaving basic variable is s2 and the entering non-basic variable is

x2 based on feasibility and optimality conditions.
 The reason x1 is excluded in the replacement ratio is that its arj value,
3, is non-negative as per optimality condition.
38
 Applying the Gauss-Jordan row operations, a new improved solution
is found.
New solution (Iteration 1)

 This solution is optimal but infeasible (s1 = -1).

39
 Applying the same procedures as iteration, iteration is generated.
New solution (iteration 2)

 This solution is both optimal (all the z-row coefficients of non-basic

variables are non-negative) and feasible (all the values of basic
variables are non-negative). The solution values are x1 = 0, x2 = x3
=3/2 and z = 9/2.

40
 The dual simplex solution method can be considered as a useful
alternative method to solve (≥) and (=) constraint problems without
adding artificial variables.

Exercise 1: Solve the LP problem using the dual simplex method.

Minimize Z = 6x1+ 3x2
Subject to
2x1 + 4x2 ≥ 16
4x1 + 3x2 ≥ 24
x1, x2 ≥ 0

41
Exercise 2: Solve the LP problem using the dual simplex method.
Minimize z = 5x1+ 3x2
subject to
x1 + 2x2 ≤ 6
x1 + x2 = 5
5x1 + 2x2 ≥ 12
x1, x2 ≥ 0

42
3.4 Generalized simplex algorithm
 The generalized simplex combines both the primal and dual simplex
methods in one algorithm.
 It deals with problems that start both non-optimal and infeasible
without using artificial variables and constraints.
 In this algorithm, successive iterations are associated with basic
feasible or infeasible (basic) solutions.
 At the final iteration, the solution becomes optimal and feasible
(assuming that one exists).
 The general procedure to solve LP problems using this method is:
 Solve the issues of feasibility first using the dual simplex method, and
 Continue to solve the optimality issues using the primal simplex method

43
Exercise: Solve the LP problem using the generalized simplex method.

Maximize z = 2x1- x2 + x3
subject to
2x1 + 3x2 - 5x3 ≥ 4
-x1 + 9x2 - x3 ≥ 3
4x1 + 6x2 + 3x3 ≤ 8
x1 , x2, x3 ≥ 0

44
3.5 Sensitivity analysis
 It deals with the sensitivity of the optimum solution by determining the
ranges for the different parameters that would keep the optimum basic
solution unchanged.
 In LP, the parameters (input data) of the model can change within certain
limits without causing the optimum solution to change is referred to as
sensitivity analysis.
 In LP models, because the parameters are usually not exact, with sensitivity
analysis, it is possible to ascertain the impact of this uncertainty on the
quality of the optimum solution.
 For example, for an estimated unit profit of a product, if sensitivity analysis
reveals that the optimum remains the same for a ±1O% change in the unit
profit, we can conclude that the solution is more robust than in the case
where the indifference range is only ±1 %.

45
 1. Change in objective function coefficients
― It is the sensitivity range of the coefficients of decision variables in the
objective function and can be found from the optimal simplex tableau
(also the value of the objective function may change).
― The condition assumes that as the coefficient of one variable changes
and others remain fixed (the changes occur one at a time).
― Example: Refer to the optimal simplex tableau of the toy assembly
problem.

46
1) Change the coefficient of x1 , c1 from 3 to (3+δ1), the final simplex table
is changed as:

The solution to stay as an optimal value,

-4 + δ1 ≤ 0
δ1 ≤ 4 or -∞ ≤ δ1 ≤ 4
-∞ ≤ c1 ≤ 7

47
2) Change the coefficient of x2 , c2 from 2 to (2 + δ2), the final simplex
table is changed as:

 The solution to remain optimal, the following conditions must be fulfilled

-4 + δ2/4 ≤ 0 and -1- δ2/2 ≤ 0 and -2+ δ2/4 ≤ 0
Solving the inequalities (taking their intersection)
-2 ≤ δ2 ≤ 8 or 0 ≤ c2 ≤ 10

48
3) Change the coefficient of x3 ,c3 from 5 to (5 + δ3), the final simplex
table is changed as:

 The solution to remain optimal, the following must be fulfilled

-4 -3δ3/2 ≤ 0 and -2- δ3/2 ≤ 0
Solving the inequalities (taking their intersection)
-8/3 ≤ δ3 ≤ ∞ or 7/3 ≤ c3 ≤ ∞

49
Summarized results
Activity Activity Objective coefficient values Objective
values function values
Optimality range Minimum Current Maximum
x1 0 -∞ ≤ δ1 ≤ 4 -∞ 3 7 1350
x2 100 -2 ≤ δ2 ≤ 8 0 2 10 1350 + 100δ2
x3 230 -8/3 ≤ δ3 ≤ ∞ 7/3 5 ∞ 1350 + 230δ3

 When the coefficients of objective function are out these ranges, the
current solution will be non-optimal.
 The optimality must be restored using the primal simplex method.

50
 2. Change in constraint values (RHS values)
― Sensitivity of the optimum solution to changes in the availability of
the resources (right-hand side of the constraints).
― It determines the feasibility ranges of constraining resources that
keep the current optimal solution to remain feasible so long as all
the basic variables are non-negative.
― The ranges can be calculated using the new values of the basic
variables in the optimal simplex tableau while the value of
constraints are changing.
New basic solution values = (Optimal inverse matrix) X (New RHS constraint value)
―It should be noted that the simplex solution method changes the identity matrix
of the initial solution into the optimal inverse matrix in the optimal simplex
tableau (read matrix operations in the simplex method).

51
 For example, see the toy assembly problem
Initial simplex tableau with identity matrix

Optimal simplex tableau with inverse optimal matrix

52
 To determine the feasibility ranges the optimal solution, assume the
first RHS constraint, b1 is changed from 430 into (430+δ1); similarly
the second and third constraints are b2 and b3 changed into (460+δ2)
and (420+δ3) respectively.
 Using the above relationship, the new basic solution values are:
𝑥2 1/2 −1/4 0 430+δ1
𝑥3 = 0 1/2 0 460+δ2
𝑠3 −2 1 1 420+δ3

The new solution values are:

𝑥2 =1/2(430+δ1) - 1/4(460+δ2) + 0(420+δ3) = 100 + δ1/2 - δ2/4
𝑥3 = 230 + δ2/2
𝑠3 =20 - 2δ1 + δ2 + δ3
z = 1350 + δ1+ 2δ2
53
The current optimal solution to stay feasible, the values of all basic
variables must be non-negative.
100 + δ1/2 - δ2/4 ≥ 0 (1)
230 + δ2/2 ≥ 0 (2)
20 - 2δ1 + δ2 + δ3 ≥ 0 (3)
 Changing one constraint at a time and making other constant
1) Change in Operation 1 time from 430 to (430 + δ1) minutes and
setting δ2 = δ3 = 0; the above relations yield that -200 ≤ δ1 ≤ 10.
2) Change in Operation 2 time from 460 to (460 + δ2) minutes and
setting δ1 = δ3 = 0; the above relations yield that -20 ≤ δ2 ≤ 400.
3) Change in Operation 3 time from 420 to (420 + δ3) minutes and
setting δ1 = δ2 = 0; the above relations yield that -20 ≤ δ3 ≤ ∞.

54
 The results can be summarized
Constraining Dual price Resource amount [minutes] Objective
resource per minute Feasibility range Minimum function value
Current Maximum
Operation 1 1 -200 ≤ δ1 ≤ 10 230 430 440 1350 + δ1
Operation 2 2 -20 ≤ δ2 ≤ 400 440 460 860 1350 + 2δ2
Operation 3 0 -20 ≤ δ3 ≤ ∞ 400 420 ∞ 1350

 As the right-hand side constraint values move beyond these limits, at

least one of the basic solution values will be infeasible i.e. the
solution may be (better than) optimal and infeasible.
 The dual simplex method can be applied to restore feasibility of the
optimal solution.
55
3.6 Post-optimal analysis
― It is revising the current optimal and feasible solution.
― It deals with making changes in the parameters of the model due to
dynamism and finding the new optimum solution.
― Post-optimal analysis determines the new solution in an efficient
way.
― The new computations are rooted in the use duality and the primal-
dual relationships.

56
― 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):

57
 Changes affecting feasibility
The feasibility of the current optimum solution may be affected only if
a) The right-hand side of the constraints is changed, or
b) A new constraint is added to the model.
― In both cases, infeasibility occurs when at least one of the current
basic variables become negative.

58
Changes in the right-hand side
Example, Case 1: Suppose that the toy assembly plant 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 affect the total revenue? Check the feasibility of the optimal
solution.
Case 2: Another proposal was thus made to shift the slack capacity of
operation 3 to the capacity of operation 1. How would this change
impact the optimum solution? Do the same as Case 1. If infeasibility is
revealed address the situation using the dual simplex method.

59
Addition of new constraints
 The addition of a new constraint to an existing model can lead to one
of two cases.
1) The new constraint is redundant, meaning that it is satisfied by the
current optimum solution, and hence can be dropped from the
model altogether.
2) The current solution violates the new constraint, in which case the
dual simplex method is used to restore feasibility.
 Notice that the addition of a new constraint can never improve the
current optimum objective value.

60
Example: Suppose that the toy firm is changing the design of its toys,
and that the change will require the addition of a fourth operation in
the assembly lines. The daily capacity of the new operation is 500
minutes and the times per unit for the three products on this operation
are 3, 1, and 1 minutes, respectively. Study the effect of the new
operation on the optimum solution.
The constraint for operation 4 is: 3x1+ x2 + x3 ≤ 500
 This constraint is redundant because it is satisfied by the current
optimum solution x1 = 0, x2 = 100, and x3 = 230.
 Hence, the current optimum solution remains unchanged and the
new constraint must be dropped.

61
Suppose, instead, that toy company unit times on the fourth operation
are changed to 3, 3, and 1 minutes, respectively. All the remaining data
of the model remain the same. Will the optimum solution change?
The constraint for operation 4 is 3x1+ 3x2 + x3 ≤ 500
 This constraint is not satisfied by the current optimum solution.
 Thus, the new constraint must be added to the current optimum and
solved using the dual simplex method by applying separately the
previous row operations on the new constraint row (see Reference 1).

62
Changes affecting optimality
 Two particular situations that could affect the optimality of the
current solution:
a) Changes in the original objective coefficients.
b) Addition of a new economic activity (variable) to the model.

63
Changes in the objective function coefficients.

 These changes affect only the optimality of the solution. Such

changes thus require re-computing the z-row coefficients or reduced
costs.
 This will result:
1) New z-row satisfies the optimality condition. The solution remains
unchanged (the optimum objective value may change, however).
2) The optimality condition is not satisfied. Apply the primal simplex
method to recover optimality.

64
Example, Case 1: In the toy assembly model, suppose that the company has a
new pricing policy to meet the competition. The unit revenues under the new
policy are $2, $3, and $4 for train, truck, and car toys, respectively.
Maximize z = 2x1 + 3x2 + 4x3
How is the optimal solution affected?
 Find the new z-row coefficients of non-basic variables or find the reduced
costs non-basic variables and check the optimality condition.
 New z-row coefficients of non-basic variables x1, s1 and s2 are -13/4, -3/2, -5/4
respectively.
 The solution remains optimal but the z-value is reduced to 1220.
Case 2: Suppose now that the toy firm objective function is changed to
Maximize z = 6x1 + 3x2 + 4x3
 Will the optimum solution change? Do the same thing as Case 1.
 New z-row coefficient of x1 is ¾ (the solution is non-optimal)
 Optimality should be recovered using the primal simplex method.

65
Addition of a new activity
 The addition of a new activity in an LP model is equivalent to adding a
new variable.
 Intuitively, the addition of a new activity is desirable only if it is
profitable-that is, if it improves the optimal value of the objective
function.
 This condition can be checked by computing its coefficient in the z-
row or reduced cost of the new variable.
 If the new activity satisfies the optimality condition, then the activity
is not profitable; else, it is advantageous to undertake the new
activity.

66
Example: The toy company recognizes that toy trains are not currently
in production because they are not profitable. The company wants to
replace toy trains with a new product, a toy fire engine, to be
assembled on the existing facilities. The company estimates the
revenue per toy fire engine to be $4 and the assembly times per unit to
be 1 minute on each of operations 1 and 2, and 2 minutes on operation
3. How would this change impact the solution?
 Check its z-row value or reduced cost.
 Its z-row coefficient = 4 – (1*1 +1*2 +2*0) = 1 (the new product is
profitable).
 Determine the new optimal values using the primal simplex method.

67