Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Context
A Graphical Introduction to Sensitivity
Analysis
Some Important Formulas
Sensitivity Analysis
Sensitivity Analysis When More Than One
Parameter is Changed: The 100% Rule
Finding the Dual of an LP
Economic Interpretation of the Dual Problem
1
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
A Graphical Introduction to
Sensitivity Analysis
Giapetto’s Woodcarving Example:
Types of toys Soldier Train
Price $27 $21
Raw material $10 $9
Variable labor and overhead costs $14 $10
Labor:carpentry 1hour 1hour
Labor:finishing 2hours 1hour
Available resource&Demand:
Raw material:unlimited
Finishing hours:100;Carpentry hours:80hours
Trains:unlimited; Soldiers: <=40
Objective:Maximize weekly profit
2
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Solution:
x1=number of soldiers produced each
week
x2=number of trains produced each week
Solution:
Optimal Solution: z=180, x1=20, x2=60
3
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
A s1,x2,s3
B x1,x2,s3
C x1,x2,s2
D
4
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Effect of a Change in an Objective Function Coefficient
x2=-C/2 x1+constant/2
? <=C<= ?
the current basis remain optimal
5
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Effect of a Change in a RHS on the LP’s Optimal Solution
the current basis remain optimal
? <=b1<= ?
b1= 100+D
2x1+x2= 100+D
x1+x2=80
x1= 20+D
x2=60-D
6
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Shadow Prices
Shadow Prices for the ith constraint of an LP to
be the amount by which the optimal z-value is
improved—increased in a max problem and
decreased in min problem –if the rhs of the ith
constraint is increased by 1
7
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Max Problem
New optimal z-value=(old optimal z-value)+(Constraint
i’s shadown price) △bi
Min Problem
New optimal z-value=(old optimal z-value)-(Constraint
i’s shadown price) △bi
8
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Importance of Sensitivity Analysis:
9
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Some Important Formulas
10
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Tableau
11
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Simplifying Formula for Slack, Excess, and Artificial Variables
NBV
If they are BV, its coefficients =?
12
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Example 1: Compute the optimal
tableau
13
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
z x1 x2 s1 s2 rhs BV
1 1 0 2 0 12
0 1 0 3
0 0 1 5
14
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Sensitivity Analysis
Criteria:
A simplex tableau (max problem) for a set
of basic variables BV is optimal if and
only if each constraint has a nonnegative
right-hand side and each variable has a
nonnegative coefficient in row 0 Methods:
Using the matrix forms, determine how changes in the
LP’s parameters change the rhs and row 0 of the optimal
tableau
If each variable in row 0 has a nonnegative coefficient
and each constraint has a nonnegative rhs, BV is still
optimal. Otherwise, BV is no longer optimal.
15
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Example:
Optimal basis?
BV’s values
Z-value
16
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
1. Changing the Objective Function Coefficient of a
Nonbasic Variable
•The current basis remain optimal
•The current basis is no longer optimal
=>A new basic variable in optimal solution.
17
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China 18
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
c2 is changed and BV remains optimal,
but the values of decision variables and z-value remain unchanged
19
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
x2 is entering variable
20
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
2. Changing the Objective Function Coefficient of a basic
Variable
•The current basis remain optimal
•The current basis is no longer optimal:
21
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
3. Changing the Right-Hand Side of a Constraint
•The current basis remain optimal
•The current basis is no longer optimal
=>Dual simplex algorithm
22
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
4. Changing the Column of a Variable
•Basic Variable:
•Nonbasic Variable:
•Remain optimal
•No longer optimal
23
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
5. Adding a New Activity
•Optimal
•No optimal
24
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Summary (Max Problem)
Change in Initial Problem
Effect on Optimal
Tableau
Current Basis Is Still
Optimal If:
Changing nonbasic
objective function
coefficient cj
Coefficient of xj in
optimal row 0 is changed
Coefficient of xj in row 0
for current basis is still
nonnegative
Changing basic objective
function coefficient cj
Entire row0 may change
Each variable still has a
nonnegative coefficient in
row 0
Changing right-hand side
of a constraint
Right-hand side of
constraints and row 0 are
changed
Right-hand side of each
constraint is still
nonnegative
Changing the column of a
nonbasic variable xj or
adding a new variable xj
Changes the coefficient
for xj in row 0 and xj’s
constraint column in
optimal tableau
The coefficient of xj in
row 0 is still nonnegative
Next
25
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Sensitivity Analysis When More Than One Parameter Is
Changed: The 100% Rule
1. The 100% Rule for Changing Objective
Function Coefficients
Case 1:
All variable who’s objective function coefficients are
changed have nonzero reduced costs in the optimal
row 0
Case 2:
At least one variable whose objective function
coefficient is changed has a reduced cost of zero
26
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
If and only if the objective function
coefficient for each variable remains within
the allowable current basis remains
optimal, both the values of the decision
variables and objective function remain
unchanged.
If the objective function coefficient for any
variable is outside its allowable range, the
current basis is no longer optimal.
Case 1:
27
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Case 2:
100% Rule:
Define ratio rj:
28
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
2. The 100% Rule for Changing Right-Hand
Sides
Case 1:
All constraints whose right-hand sides are being
modified are nonbinding constraints
Case 2:
At least one of the constraints whose right-hand
side is being modified is a binding constraint
29
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
If and only if each right-hand side remains
within its allowable range. Then both the
values of the decision variables and optimal
objective function remain unchanged.
If the objective function coefficient for any
variable is outside its allowable range, the
current basis is no longer optimal.
Case 1:
30
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Case 2:
100% Rule:
Define ratio rj:
31
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Finding the Dual of an LP
Normal max problem Normal min problem
DUA
L
CAT
bT
≤
max
m
n
≥
min
bA
CT
m
n
32
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Finding the Dual of a Normal Max or
Min Problem
33
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Example
34
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Finding the Dual of a Nonnormal LP
Transform nonnormal form into normal form
For >= constraint: Multiply by -1
For = constraint: <= and >=
For urs : x=x’-x”
35
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Example:
36
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Finding the Dual of a Nonnormal Max
Problem
•For >= constraints, dual variables must satisfy
<=0
•For = constraints, dual variables is urs
•For urs’s variable, the dual constraint is an equality constraint
37
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Example:
38
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Finding the Dual of a Nonnormal Min
Problem
•For <= constraints, dual variables must satisfy
<=0
•For = constraints, dual variables is urs
•For urs’s variable, the dual constraint is an equality constraint
39
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Exercise:
40
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Economic Interpretation of the
Dual Problem
Interpreting the Dual of a Max Problem
Resource/product Amount of
Resource
AvailabbleResource Desk Table Chair
Lumber 8 board ft 6 board ft 1 board ft 48 board ft
Finishing 4hours 2hours 20hours
Carpentry 2hours 8hours
Selling price $60 $30 $20
41
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Decision variables:
•y1=price paid for 1 board ft of lumber
•y2=price paid for 1 finishing hour
•y3=price paid for 1 carpentry hour
42
Author:Zhang Zhihai, Dept. of Industrial Engineering, Tsinghua University, 100084, Beijing, China
Interpreting the Dual of a Min Problem
43
