Chapter 18

Simplex-Based Sensitivity Analysis and

Duality
 Sensitivity Analysis with the Simplex Tableau
 Duality

1
 Objective Function Coefficients
and Range of Optimality
 The range of optimality for an objective
function coefficient is the range of that
coefficient for which the current optimal
solution will remain optimal (keeping all
other coefficients constant).
 The objective function value might
change in this range.

2
 Objective Function Coefficients
and Range of Optimality
 Example: Dakota Company Makes X1 number of Desks, X2 Tables,
and X3 Chairs Primal
Max z = 60X1 + 30X2 + 20X3
s.t. 8X1 + 6X2 + X3 ≤ 48 (b1) (ft2 lumber constraint)
4X1 + 2X2 + 1.5X3 ≤ 20 (b2) (Hours finishing constraint)
2X1 + 1.5X2 + 0.5X3 ≤ 8 (b3) (Hours carpentry constraint)
X2 ≤ 5 (b4) (Table demand constraint)
X1, X 2, X 3 ≥ 0
The Dual problem
Min z=48y1+20y2+8y3+5y4
s.t:
8y1+4y2+2y3 > 60
6y1+2y2+1.5y3 +y4 > 30
y1+1.5y2+0.5y3 > 20
y1,y2,y3 , y4 > 0 3
1-Changing the objective function coefficient of a non-
basic variable
The following is the optimal solution to the above
Basis Cij 60X1 30X2 example:
20X3 0S1 0S2 0S3 0S4 RHS
S1 0 0 -2 0 1 2 -8 0 24
X3 20 0 -2 1 0 2 -4 0 8
X1 60 1 1.25 0 0 -0.5 1.5 0 2
S4 0 0 1 0 0 0 0 1 5
z 60 35 20 0 10 10 0 280
c-z 0 -5 0 0 -10 -10 0
BV = {z, S1, X3, X1, S4} NBV = {S3, S2, X2}
X2 did not appear in the optimal solution as BV, because its coefficient value in the
objective function was not big enough (Profitable) to “enter” into the basis. So, if
we want to introduce it into the basis, we must add extra value to its original
coefficient of the objective function. X2 is called underpriced. The minimum
amount that makes X2 as basic variable is the X2 coefficient in the objective
function plus the value of underpriced, this will lead us to value equal to the value
of X2 in z. The range in which X2 will be out of basis can be illustrated as follows:
C2>= (30+5) >= 35 >>>> C2<35 C2<35 Max
30- ∞ < C2 < 30+5 - ∞ < C2<35
4
 Original Value Under Price Max. value of X2 to Max. Decrease to
NBV in the Problem in (c-z) keep out of Basis stay out of Basis
X2 30 5 < 35 ∞
30-∞ < C2 < 30+5
-∞ < C2 < 35
2- Changing the objective function coefficient of a
basic variable
In order to determine the optimality ranging for the basic variables (BV) of the
objective function we divide all nonzero values in c-z row by its corresponding
values in the basic row of the optimal simplex table. Then we pick up the least
negative value and the least positive value to represent the allowed changes on the
original coefficient of objective function. The following table will show the
calculations for c-z values
X1 (BV): -5 -10 -10
Row values X1 1.25 -0.5 1.5
c-z / X1 -4 20 S-6.67
Sele

5
For the basic variable X3, the optimality calculation as follows:

c-z values -5 -10 -10

Row values X3 -2 2 -4
c-z / X3 2.5 -5 2.5
Therefore the range of optimality for coefficient of X3 that will keep the solution
always optimal is: 20-5 < C3 < 20+2.5
15 < C3 < 22.5

6
 Right-Hand Side (RHS) Values
and Range of Feasibility
 The range of feasibility for a right-hand side
coefficient is the range of that coefficient for
which the shadow price remains unchanged.
 The range of feasibility is also the range for
which the current set of basic variables
remains the optimal set of basic variables
(although their values change.)

7
3- Changing the right-hand side of a constraint
In order find the range of optimality for the RHS, we divide the RHS column by
the opposite sign of corresponding S column associated with this constraint.
Basis RHS (-)(+S1) Result (RHS/S1)
S1 24 -1 -24
X3 8 -0 -∞
X1 2 -0 -∞
S4 5 -0 -∞
(48- 24) < b1 < (48 + ∞)
24 < b1 < ∞

Basis RHS (-)(+S2) Result(RHS/S2)

S1 24 -2 -12
X3 8 -2 -4
X1 2 +0.5 +4
S4 5 -0 -∞
(20- 4) < b2 < (20 + 4)
16 < b2 < 24

8
Basis RHS (-)(+S3) Result(RHS/S3)
S1 24 +8 +3
X3 8 +4 +2
X1 2 -1.5 -1.33
S4 5 -0 -∞
(8- 1.33) < b3 < (8 + 2)
6.67 < b3 < 10

Basis RHS (-)(+S4) Result(RHS/S4)

S1 24 -0 -∞
X3 8 -0 -∞
X1 2 -0 -∞
S4 5 -1 -5
(5- 5) < b4 < (5 + ∞)
0 < b4 < ∞

9
 Shadow (Dual) Price
 A shadow price for a constraint is the increase in the objective function
value resulting from a one unit increase in its right-hand side value.
 Shadow prices and dual prices on The Management Scientist output
are the same thing for maximization problems.
 Usually we might see two types of questions related to shadow price
principles.
 First question is to find the shadow price for constraint i (i=1 to n
constraints)
 Second question is related of the meaning of shadow price which it
means the economical interpretation of the shadow price. It will tell us
what will happen exactly to the value of the objective function (Max
or Min) by increasing one unit in the RHS of ith constraint.
 This will imply that we should understand the question properly (i.e.
to find the shadow price of constraint i or how much the objective
function will change because of one-unit change in ith RHS)

10
 Shadow Price (Dual Price)
 Shadow prices are found in the optimal tableau as follows:
 "less than or equal to" constraint -- zj value of the corresponding slack variable
for the constraint
 "greater than or equal to" constraint -- negative of the zj value of the
corresponding surplus variable for the constraint
 "equal to" constraint -- zj value of the corresponding artificial variable for the
constraint.
 Maybe the safest to calculate the shadow prices for all types of models (Max or
Min) and for all types of constraints by applying the following role (Result of 3
multiplications):
 Shadow Price=[Type of O.F.(+ Max)(- Min)]*[Type of (±Si)or(+ai)]*[Value in
Z row under column of S or a]
 For our example on slide-4:
 1st constraint Shadow price= [Max+]*[+S1]*[ 0 in Z-row under S1 column]=0
 2nd constraint Shadow price=[Max+]*[+S2]*[10 in Z-row under S2 column]=+10
• 3rd constraint Shadow price= [Max+]*[+S3]*[10 in Z-row under S3 column]=+10
• 4th constraint Shadow price=[Max+]*[+S4]*[ 0 in Z-row under S4column]=+0
11
 Economical Interpretation of Shadow price
In many occasions, the question on shadow price formatted in different way. The question is
more about the meaning of shadow price rather to calculate the shadow price itself. In this case
the question will not mention calculating the shadow price, instead the question will ask about
how much it worth an extra unit (one unit) of recourses? How much one extra unit of resources
in the RHS of a specific constraint will increase (decrease) the value of objective function? So
this time you have to do the economical interpretation of the shadow price.
Let us assume the following question to be applied on previous example.
How much an extra square feet of lumber worth (add) to the objective function?
All what you need to do is to multiply the shadow price of 1st constraint by the sign of the
objective function and must comment on it as follows:
One extra ft2 of lumber worth= Shadow price of Lumber constraint (0) * Objective Fn.
Sign(Max=+)=, , so therefore the product is =+*+0= 0
For second Const. an extra hour added to the RHS of the Finishing department will have the
following effect: +shadow price of 2nd Const.(+10)* (Max+) = +$10. the comment as follows:
adding one hour to Finishing department will (+) increase the (Max) profit by $10.
For the third Constraint= (+10)*(Max+)= +$10 which implies that one extra hour added to the
carpentry department hours will increase the objective function profit by $10.

12
 Canonical Form

 A maximization linear program is said to be

in canonical form if all constraints are "less
than or equal to <" constraints and the
variables are non-negative.
 A minimization linear program is said to be
in canonical form if all constraints are
"greater than or equal to >" constraints and
the variables are non-negative.

13
 Primal and Dual Problems
 Every linear program (called the primal) has associated with it
another linear program called the dual.
 The dual of a maximization problem in canonical form is a
minimization problem in canonical form.
 The rows and columns of the two programs are interchanged and
hence the objective function coefficients of one are the right hand
side values of the other and vice versa.

14
 Primal and Dual Variables
 The dual variables are the "value per unit" of the corresponding primal
resource, i.e. the shadow prices. Thus, they are found in the zj row of
the optimal simplex tableau.
 If the dual is solved, the optimal primal solution is found in zj row of
the corresponding surplus variable in the optimal dual tableau.
 The optimal value of the primal' s slack variables are the negative of
the cj - zj entries in the optimal dual tableau for the dual variables.

15
 Primal and Dual Problems
 The optimal value of the objective function of the primal problem
equals the optimal value of the objective function of the dual problem.
 Solving the dual might be computationally more efficient when the
primal has numerous constraints and few variables.
 The followings are the general roles to be used in converting Primal LP
model L.P. to Dual L.P. model:
Primal Dual
Max Min
< >
Ci bi
# constraints # Variables
Column Row
Z value = Z value

16
 Sensitivity Analysis Minimization Exercise
Consider the following LP model and its optimal solution:
Min Z=2X1+2X2+3X3+X4 X1 +X2 +X3 +X4 >20 (y’1)
s.t.: X1+X2+X3+X4 =$20 Capital in ,000 -X1-X2 -X3 -X4 >-20 (y’’1 ) (*-1)
2X1+X2+X3+X4 >28 Demand 2X1+X2 +X3 +X4 >28 (y2)
-X1+X2 +X4 <10 Workers X1 -X2 -X4 >-10 (y3)
X1, X2, X3, X4 > 0 Max Z=20y’1-20y’’1 +28y2-10 y3
BasiThe optimal solution: s.t: y’ 1-y’’1 +2y2+y3 < 2
C ij 2X 2X
1 3X21X a 3 S 4 S1 RHS
2 3
s
X
y’1-y’’1+y2 -y3 < 2
4 1 0 1 1 1 2 1 0 12
X1 2 1 0 0 0 -1 -1 0 8 y’1-y’’1+y2 <3
S3 0 0 0 -1 0 -3 -2 1 6
Z 2 1 1 1 0 -1 0 28 y’1- y’’1+y2 -y3 < 1
C-Z 0 1 2 0 0 1 0
y2,y3 > 0 y’1,y’’1 unrestricted
Find the followings:
1-Extract (Write) the dual problem
2-Determine the shadow prices for 1st , 2nd , and 3rd constraints
3-How much is it worth an extra unit in 1st, 2nd and 3rd constraints?
4-What is the range of optimality for C1?
5-What is the range of optimality for C3?
6-What effect of increasing the value of C 1 from 2 to 6 on the objective function value?
7-What effect of decreasing the value of C 3 from 3 to 1on the objective function value?
8-What is the range of b2?
9-What will happen to the optimal solution if we decrease the value of b3 from 10 17to 2?
Solution:
1- Convert the model into Standard Min:
Min Z=2X1+2X2+3X3+X4
s.t:

2- Shadow (Dual) prices for the 3 constraints are as follows:

1st Constraint= (Min-)*(+a1)*(0) =0
2nd Constraint=(Min-)*(-S2) *(-1) =-1
3rd Constraint= (Min-)*(+S3)*(0) =0
3- Each extra unit added to the right-hand side of the constraint is worth (Shadow prices
Interpretation) as follows:
1st Constraint= (Min-)*(1st Constraint Shadow price=0) = (0). This means that if we increase
(or decrease) the RHS of this constraint by one unit, then the total cost will increase
(decrease) by 0 unit of money ($).
2nd Constraint= (Min-)*(2nd Constraint Shadow price=-1) = $(+1). This means that if we
increase (or decrease) the RHS of this constraint by one unit, then the total cost will
increase (decrease) by 1$. 18
4- Range of optimality for C1 is:
C-Z 1 2 1
X1 0 0 -1
C-Z/X1 +∞ +∞ -1

2-1<C1<2+∞ >>>>>>>>> 1<C1<+∞

5- X3 is non-basic decision variable, thus, C3 > 1
6- Changing C1 (cost) from $2 to $6 is allowed as we see in part # 4 the range of C1 can be
increased up to ∞, therefore the affect will be applied on C 1 in the final table of optimal
solution as follows: Z=(1*12)+(6*8)=+60 (Cost increases from $28-$60)
7- Changing C3 from 3 to 1 needs to be tested before judging on what will happen to the
objective function value. But X3 is non-basic decision Variable therefore the range must be
C3 >(3-2) >1 in order to stay outside the basis. So, the question suggested to reduce C 3 by 2,
thus, the value of C3 will be =1. This will let X3 enter the basis and therefore the optimal
solution will change. So, it is not feasible.
This implies that we can decrease C3 by maximum of $2 is feasible with no change on the
optimal solution. Therefore, the question asked to reduce C3 by $2, thus the effect will equal to
0 as X3 is non-basic variable and will not contribute to z value as long as a maximum
reduction is $2 (see C3 range). But if you reduce more than $2, then the optimal solution will
change.

19
8- The range of b2 can be calculated as follows:

28-3 < b2 <28+12>>>>>>>>>>>>>> 25 < b2 <40

9- Changing b3 from 10 to 2 needs to be tested first if we can make
reduction of 10-2=8(reduction)

Since max reduction allowed by the range =6, so it is not feasible and
optimal solution will change.
The C -range for a non-basic decision
variable
If Max
-∞ <C3 < (Value in Z-row under X3 column)=1 Or C3<1
X3 is underpriced good
If Min
(Value in Z-row under X3 Column)=(3-2)1 <C3 <+∞ or C3 >1
X3 is overpriced good by 2
20
 10-6 <b3<10+∞ >>>>>>>>>>>>>> 4 < b3 <∞
Decreasing b3 from 10 to 2 is not allowed as 2 is outside the lower range of b 3 ,and
therefore it will change the solution optimality.
10- Decreasing b1 from 20 to 16=4, needs to be tested.
RHS 12 8 6
-(+a1) -2 1 3
RHS/a1 -6 8 2

20-6 <b1<20+2
14 <b1< 22
Therefore, reducing b1 by 4 units is feasible,. We go to next step to find the new optimal
solution as follows:
As we see from testing a range, reduction is allowed and therefore:
Old RHS1 Decrease=
+a1 Column= + New RHS
-4
X4 12 - (4 * 2) =-8 4
X1 8 - (4 * -1) =+4 12
S3 - (4
6 -3) =+12 18
*
Z 28 - (4 * 0) =0 28

21
 Example: Primal and Dual Problem

 LP Formulation

Max 2x1 + x2 + 3x3

s.t. x1 + 2x2 + 3x3 < 15

3x1 + 4x2 + 6x3 > 24
x1 + x2 + x3 = 10

x1, x2, x3 > 0

22
 Example: Primal and Dual Problem

 Primal in Canonical Form

• Constraint (1) is a "<" constraint. Leave it
alone.
• Constraint (2) is a ">" constraint. Multiply it
by -1.
• Constraint (3) is an "=" constraint. Rewrite
this as two constraints, one a "<", the other
a ">" constraint. Then multiply the ">"
constraint by -1.
(result on next slide)

23
 Example: Primal and Dual Problem

 Primal in Canonical Form (continued)

Max 2x1 + x2 + 3x3

s.t. x1 + 2x2 + 3x3 < 15

-3x1 - 4x2 - 6x3 < -24
x1 + x2 + x3 < 10
-x1 - x2 - x3 < -10
x1, x2, x3 > 0

24
 Example: Primal and Dual Problem

 Dual of the Canonical Primal

• There are four dual variables, y1, y2, y3’, y3".
• The objective function coefficients of the dual
are the RHS of the primal.
• The RHS of the dual is the objective function
coefficients of the primal.
• The rows of the dual are the columns of the
primal.
(result on next slide)

25
 Example: Primal and Dual Problem

 Dual of the Canonical Primal (continued)

Min 15y1 – 24y2 + 10y3' – 10y3"

s.t. y1 - 3y2 + y3' - y3" >

2
2y1 - 4y2 + y3' - y" > 1
3y1 - 6y2 + y3' - y3" >
3
y1, y2 > 0 y3’, y3"
unrestricted

26
Example (2)
A company produces cattle feed and it uses in the mixture two types of corn and two types of grain. The
product should contain three types of nutrition (A, B, and C) that are necessary to the animals as shown in the
following table:
The minimum requirement of food in each bag of 10 Kilograms is 150 gm from A and 250 gm of B and
200gm from nutrition C. There is a limit on the grain-1 that its amount cannot exceed 3 Kilograms in the bag.
Find:
1- What are the optimal quantities of the four types of food that should be used in the mixture that minimize
the total cost?
2- What are the shadow prices in all constraints?
3- Find the ranges of c1, c2, c3, c4?
4- Find the ranges of b1, b2, b3, b4, b5?
5- Suppose we increased the cost of corn-1 by $0.5, what effect of that on the optimal solution?
6- If we reduce the requirement of C-nutrition by 5 grams, what effect of that on the optimal solution?
7- Find the dual problem.

Cost C B A
Ingredients
$/K.g gm/K.g gm/K.g gm/K.g

1.2 16 15 25 Corn-1

1.75 20 20 10 Corn-2

2.25 20 35 17 Grain-1

2.7 25 70 10 Grain-2

27
 2.7X4 + +2.25X3 +1.75X2 1.2 X1 = Min Z
S.t

150 ) gm of A nutrition( > + 10 X4 + 17 X3 + 10 X2 25 X1

250 )gm of B-nutrition( > +70 X4 +35 X3 + 20 X2 15 X1

200 ) gm of C nutrition( + 25 X4 + 20 X3 + 20 X2 16 X1
>

3 ) Kg from grain-1( < X3

10 )Bag weight( + X4 + X3 + X2 X1

1. We can solve this problem using simplex method and the optimal solution is:
X4 > 0 X3 > 0 X2 > 0 X1 > 0

0 0 0 0 0 2.7 2.25 1.75 1.2

RHS Cij Basis
a5 S4 S3 S2 S1 X4 X3 X2 X1

1.7
4 6.2 0 0.2 0 0.12 0 0.16 1 0 X2
5
66.67 -203.3 0 - 10 1 -2.33 0 1.33 0 0 0 S2
2.67 -4.53 0 -0.2 0 -0.05 1 0.37 0 0 2.7 X4
3 0 1 0 0 0 0 0 0 0 0 S4
3.33 -0.67 0 0 0 -0.07 0 0.47 0 1 1.2 X1
-
18.2 -2.19 0 -0.19 0 2.7 1.85 1.75 1.2 Z
0.014
2.19 0 0.19 0 0.014 0 0.4 0 0 C-Z

28
2- Shadow Price (Dual Price) and its interpretation:

Economic Additional
Shadow price Constraint Name
Interpretation Variable Name

0.014 - 0.014 (Min(-)*>(-)*-0.014 S1 (1) Nutrition A

0 0 (Min(-)*>(-)*0 S2 (1) Nutrition B

+0.19 - 0.19 (Min(-)*>(-)*-0.19 S3 (1) Nutrition C

0 0 (Min(-)*<(+-)*0 S4 (1) Grain-1 Limit

-2.19 2.19 (Min(-)*=(+)*-2.19 a5 (1) Bag Weight

The table above shows that if we increase first constraint's requirement by one gram
(from 150 to 151) then the total cost (objective function value) will increase by
$0.014. But for second constraint the effect equal zero, whereas increment of one gram
in third constraint will increase the total cost by $0.19. For the fourth constraint, the
increment of one Kilograms of grain-1 in the mixture will not affect the total cost.
Finally the increment of kilogram on the total bag weight will reduce the cost by $2.19

29
3. Changes in Objective Function Coefficients:
The ranging of the objective function coefficients (cost per kilogram)
can be shown as follows:

(1.2-0.2) 1 < C1 < 2.061(1.2+0.85)

(1.75-∞ ) -∞ < C2 < 1.87 (1.75+0.12)

1.84 < C3 <+∞ (X3 is non-basic decision Variable)

(2.75-0.28) 2.43 < C4 < 3.83(2.75+1.08)

30
3. Changes in RHS:
For the ranging of the right-hand side (bi) that changes can occur without affecting the
optimality of the final table can be shown as follows:
RHS 4 66.67 2.67 3 3.33
  33.3  28.6 53.4   47.6
 (  S 1 ) 0.12  2.33 0.05 0  0.07

(150-28.6) 121.4 < b1 < 183.3 (150+33.3)

RHS 4 66.67 2.67 3 3.33
  66.67   
 ( S 2 ) 0 1 0 0 0

(250-∞) -∞ < b2 < 316.67 (250+66.67)

RHS 4 66.67 2.67 3 3.33
 20  6.6 7  13.35  
 (  S 3 ) 0.2  10  0.2 0 0

(200-6.67) 193.33 < b3 < 220 (200+20)

RHS 4 66.67 2.67 3 3.33
        3  
 ( S 4 )  0 0 0 1 0

(3-3) 0 < b4 < + ∞ (3+∞)

RHS 4 66.67 2.67 3 3.33
  0.65 0.33 0.59   4.97
 ( a 5 )  6.2 203.3 4.53 0 0.67

(10-0.65) 9.35 < b5 < 10.33 (10+0.33)

31
5- Since increasing the cost of corn-1 from $1.2 to $1.7 will not affect the optimal
solution as the increment will keep the cost within the range. Therefore the changes on
the solution as follows:
0 0 0 0 0 2.7 2.25 1.75 1.7
RHS Cij Basis
a5 S4 S3 S2 S1 X4 X3 X2 X1

4 6.2 0 0.2 0 0.12 0 0.16 1 0 1.75 X2

66.67 -203.3 0 - 10 1 -2.33 0 1.33 0 0 0 S2
2.67 -4.53 0 -0.2 0 -0.05 1 0.37 0 0 2.7 X4
3 0 1 0 0 0 0 0 0 0 0 S4
3.33 -0.67 0 0 0 -0.07 0 0.47 0 1 1.7 X1

-
19.87 -2.19 0 -0.19 0 2.7 1.85 1.75 1.7 Z
0.014

2.19 0 0.19 0 0.014 0 0.4 0 0 C-Z

6- Since reducing nutrition-C by 5 gram (i.e. from 200 to 195) is allowable according
to b3 range, the change on the final solution can be shown as follows:
New Chang in(-b3)*[(-S3) Column] Old RHS Basis
RHS

5 -5*-0.2= +1 4 X2

16.67 - 5*10 = --50 66.67 S2

1.67 -5*0.2 = -1 2.67 X4

3 -5*0 = 0 3 S4

3.33 -5*0 = 0 3.33 X1

18.2
17.25 -5*0.19= -0.95 Z

32
7- Dual problem:
You should notice that the 5th constraint has (=) sign. In such case when we want to find
the dual problem, we should produce two constraints for this particular equal
constraint, one with (<) sign and same constraint but with (>) sign as explained below:
=
10 )Bag weight( + X4 + X3 + X2 X1
X1 + X2 +X3 + X4 < 10 (*-1) >>> -X1 - X2 -X3 - X4 > -10
X1 + X2 +X3 + X4 > 10

Now, we put the problem in standard LP. Since originally the problem is minimization one,
therefore, we should deal with it as standard minimization. This implies that all constraints
should be represented in (>) sign:

33
 The Primal Problem
2.7X4 + +2.25X3 +1.75X 1.2 X1 = Min Z
2
S.t
150 )gm of A( > + 10 X4 + 17 + 10 25 X1
X3 X2
250 )gm of B( > +70 X4 +35 X3 + 20 15 X1
X2
200 )gm of C( > + 25 X4 + 20 + 20 16 X1
X3 X2
-3 (Kg from grain-1) > - X3

10 )Bag weight( > + X4 + + X1

X3 X2

The Dual Problem:

Max Z= 150Y1+250Y2+200Y3-3Y4+10Y’5 -10 Y’’5
s.t:
25Y1+15Y2+16Y3+ Y’5- Y’’5 < 1.2
10Y1+20Y2+20Y3+ Y’5- Y’’5 < 1.75
17Y1+35Y2+20Y3-Y4+ Y’5- Y’’5 < 2.25
10Y1+70Y2+25Y3+ Y’5- Y’’5 < 2.7
Y1, Y2, Y3, Y4 > 0 Y’5 and Y’’5 unrestricted in sign
N.B: we have used -Y10’5, Y)Bag X .
weight( th - X - X2
5 to refer to 5 constraint
’’ > -
4 -
3 X1

34
End of Chapter 6

35