3. linear programming senstivity analysis

LP-senstivity analysis

1. ADVANCED
OPERATIONS
RESEARCH
By: -
Hakeem–Ur–Rehman
IQTM–PU
1
RAO
LINEAR PROGRAMMING : SENSITIVITY ANALYSIS

2. LINEAR PROGRAMMING:
SENSITIVITY ANALYSIS
2
Thetermsensitivityanalysis,sometimesalsocalled
post-optimalityanalysis,referstoananalysisofthe
effectontheoptimalsolutionofchangesinthe
parametersofproblemonthecurrentoptimalsolution.
The following questions arise in connection with performing the
sensitivity analysis.
1.Howdochangesmadetothecoefficientsoftheobjective
functionaffecttheoptimalsolution?
2.Howdochangesmadetotheconstantsontherighthand
sideoftheconstraintaffecttheoptimalsolution?

3. EXAMPLE
3
XYZmanufacturingcompanyhasadivisionthatproducestwomodelsof
grates,model–Aandmodel–B.Toproduceeachmodel–Agraterequires‘3’g.
ofcastironand‘6’minutesoflabor.Toproduceeachmodel–Bgraterequires
‘4’g.ofcastironand‘3’minutesoflabor.Theprofitforeachmodel–Agrate
isRs.2andtheprofitforeachmodel–BgrateisRs.1.50.Onethousandg.of
castironand20hoursoflaborareavailableforgrateproductioneachday.
Becauseofanexcessinventoryofmodel–Agrates,Company’smanagerhas
decidedtolimittheproductionofmodel–Agratestonomorethan180grates
perday.
SolvethegivenLPproblemandperformsensitivityanalysis.
LPMODEL:LetX
1
andX
2
bethenumberofmodel–Aandmodel–B
gratesrespectively.
ThecompleteLPmodelisasfollow:
Maximum:Z=2X
1
+1.5X
2
2X
1
+(3/2)X
2
Subjectto:
3X
1
+4X
2
≤1000
6X
1
+3X
2
≤1200
X
1
≤180
X
1
,X
2
≥0

4. EXAMPLE (Cont…)
4
Contribution Per Unit C
j 2 3/2 0 0 0
C
Bi
Basic
Variables (B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
1 1000 3 4 1 0 0
0 S
2 1200 6 3 0 1 0
0 S
3 180 1 0 0 0 1
TotalProfit(Z
j) 0 0 0 0 0 0
Net Contribution (C
j–Z
j) 2 3/2 0 0 0
0 S
1 460 0 4 1 0 –3
0 S
2 120 0 3 0 1 –6
2 X
1 180 1 0 0 0 1
Total Profit (Z
j) 360 2 0 0 0 2
Net Contribution (C
j–Z
j) 0 3/2 0 0 –2
0 S
1 300 0 0 1 –4/3 5
3/2 X
2 40 0 1 0 1/3 –2
2 X
1 180 1 0 0 0 1
Total Profit (Z
j) 420 2 3/2 0 1/2 –1
Net Contribution (C
j–Z
j) 0 0 0 –1/2 1
0 S
3 60 0 0 1/5 –4/15 1
3/2 X
2 160 0 1 2/5 –1/5 0
2 X
1 120 1 0 –1/5 4/15 0
Total Profit (Z
j) 480 2 3/2 1/5 7/30 0
Net Contribution (C
j–Z
j) 0 0 –1/5 –7/30 0
Sinceallthevaluesof(C
j
–Z
j
)≤0;so,
thesolutionisoptimal.
‘Z=480;at‘X
1
=120’and‘X
2
=160’.Thus,XYZmanufacturing
companyrealizesamaximumprofitofRs.480perdayby
producing120model–Agratesand160model–Bgratesperday.

5. LP:SENSITIVITY ANALYSIS
5
Thefollowingquestionsariseinconnectionwithperformingthe
sensitivityanalysisoftheaboveproblem.
1.Howdochangesmadetothecoefficientsoftheobjective
functionaffecttheoptimalsolution?
2.Howdochangesmadetotheconstantsontherighthand
sideoftheconstraintaffecttheoptimalsolution?
CHANGE INTHECOEFFICIENTS OFTHEOBJECTIVE
FUNCTION:
Nowtwoquestionsaretobeanswered:
1.Howdochangesmadetothecoefficientsofnon–basic
variableaffecttheoptimalsolution?
2.Howdochangesmadetothecoefficientsofbasicvariable
affecttheoptimalsolution?

6. LP:SENSITIVITY ANALYSIS (Cont…)
6
Howdochangesmadetothecoefficientsofnon–basic
variableaffecttheoptimalsolution?
Accordingtotheaboveoptimalsimplextable,S
1,&S
2are
thenon–basicvariables.
Nowthequestionarisesthathowmuchhavethe
objectivefunctioncoefficientstobechangedbeforeS
1,
&S
2wouldenterthesolutionandreplacesoneofthe
basicvariables(X
1,X
2&S
3)?
Accordingtothesimplexalgorithmaslongastherow
(C
j–Z
j)≤0,therewillnotbeanychangeinthe
optimalsolution.Thus,C
j–Z
j≤0C
j≤Z
j
Rangeforanon–basicvariable:
Therangeof‘C
j
’valuesfornon–basicvariablesare:“–∞≤C
j
≤Z
j
”.So,
Therangeofvaluesfor‘S
1
’is:“–∞≤C
j
≤1/5”
Therangeofvaluesfor‘S
2
’is:“–∞≤C
j
≤7/30”

7. LP:SENSITIVITY ANALYSIS (Cont…)
Howdochangesmadetothecoefficientsofbasicvariableaffecttheoptimal
solution?
Accordingtotheaboveoptimalsimplextable,X
1,X
2&S
3arethebasicvariables.
Nowthequestionarisesthathowmuchtheobjectivefunctioncoefficientonabasic
variablecanchangewithoutchangingtheoptimalsolutionofanLPproblem.
ChangeintheCoefficientoftheBasicVariable‘X
1
’:
Letusdenotethechangeinavariablevalueby‘h’.Thechangein‘X
1
’is‘2+h’.Now,were–
computethenewfinalsimplextablewhichisasfollows:
Contribution Per Unit C
j 2+h 3/2 0 0 0
C
Bi
Basic Variables
(B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
3 60 0 0 1/5 –4/15 1
3/2 X
2 160 0 1 2/5 –1/5 0
2+h X
1 120 1 0 –1/5 4/15 0
Total Profit (Z
j) 480+120h 2+h 3/2 (1–h)/5 (7+8h)/30 0
Net Contribution (C
j–Z
j) 0 0 –(1–h)/5 –(7+8h)/30 0
Sinceallthevaluesinthe(C
j
–Z
j
)≤0,sothesolutionisoptimal.Theoptimalsolutionwillchangeifatleast
oneof(C
j
–Z
j
)>0.Wewillfindthevalueof‘h’forwhichthenewsolutionremainsoptimal.Inordertodo
this,weevaluate‘h’ineachcolumnforthenon–basicvariables.
From‘S
1
’Column:(C
j
–Z
j
)≤0–(1–h)/5≤0h≤1
Itmeansthat‘S
1
’willnotenterthebasisunlesstheprofitperunitfor‘X
1
’willincreaseto‘2+h
=2+1=3’;ifitgoesabove,thesolutionwillnotremainoptimal.
From‘S
2
’Column:(C
j
–Z
j
)≤0–(7+8h)/30≤0h≥–(7/8)
Itmeansthat‘S
2
’willnotenterthebasisunlesstheprofitperunitfor‘X
1
’willreduceto‘2+h
=2–(7/8)=9/8’;ifitgoesbelow,thesolutionwillnotremainoptimal.

8. LP:SENSITIVITY ANALYSIS (Cont…)
8
Howdochangesmadetothecoefficientsofbasicvariableaffect
theoptimalsolution?
RangeofOptimalityfor‘X
1
’:
Here,thevalueof‘C
1
’rangesfrom‘(9/8)to3’(i.e.1.125≤C
1
≤3).Inthisintervalof‘C
1
’,the
optimalityisunaffected.So,weconcludethatthecontributiontotheprofitofamodel–Agratecan
assumevaluesbetweenRs.1.125andRs.3withoutchangingtheoptimalsolution.
ChangeintheCoefficientoftheBasicVariable‘X
2
’:
Letusdenotethechangeinavariablevalueby‘k’.Thechangein‘X
2
’is‘(3/2)+k’.Now,were–
computethenewfinalsimplextablewhichisasfollows:
Contribution Per Unit C
j 2 (3/2)+k 0 0 0
C
Bi
Basic Variables
(B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
3 60 0 0 1/5 –4/15 1
(3/2)+k X
2 160 0 1 2/5 –1/5 0
2 X
1 120 1 0 –1/5 4/15 0
Total Profit (Z
j) 480+160k 2 (3/2)+k (1+2k)/5 (7–6k)/30 0
Net Contribution (C
j–Z
j) 0 0 –(1+2k)/5–(7–6k)/30 0
Sinceallthevaluesinthe(C
j
–Z
j
)≤0,sothesolutionisoptimal.Theoptimalsolutionwill
changeifatleastoneof(C
j
–Z
j
)>0.Wewillfindthevalueof‘k’forwhichthenewsolution
remainsoptimal.Inordertodothis,weevaluate‘k’ineachcolumnforthenon–basicvariables.

9. LP:SENSITIVITY ANALYSIS (Cont…)
9
Howdochangesmadetothecoefficientsofbasicvariableaffect
theoptimalsolution?
From‘S
1
’Column: (C
j
–Z
j
)≤0–(1+2k)/5≤0k≥(–1/2)
Itmeansthat‘S
1
’willnotenterthebasisunlesstheprofitperunitfor‘X
2
’willdecreaseto
‘(3/2)+k=(3/2)–(1/2)=1’;ifitgoesbelow,thesolutionwillnotremainoptimal.
From‘S
2
’Column: (C
j
–Z
j
)≤0–(7–6k)/30≤0k≤7/6
Itmeansthat‘S
2
’willnotenterthebasisunlesstheprofitperunitfor‘X
2
’willincreaseto
‘(3/2)+k=(3/2)+(7/6)=15/6’;ifitgoesabove,thesolutionwillnotremainoptimal.
RangeofOptimalityfor‘X
2
’:
Here,thevalueof‘C
2
’rangesfrom‘1to15/6’(i.e.1≤C
2
≤2.5).Inthisintervalof‘C
2
’,the
optimalityisunaffected.So,weconcludethatthecontributiontotheprofitofamodel–B
gratecanassumevaluesbetweenRs.1andRs.2.5withoutchangingtheoptimalsolution.

10. LP:SENSITIVITY ANALYSIS (Cont…)
10
Howdochangesmadetothecoefficientsofbasicvariableaffect
theoptimalsolution?
ChangeintheCoefficientoftheBasicVariable‘S
3’:
Letusdenotethechangeinavariablevalueby‘L’.Thechangein‘S
3’is‘0+L’.Now,were–
computethenewfinalsimplextablewhichisasfollows:
Contribution Per Unit C
j 2 3/2 0 0 0+L
C
Bi
Basic Variables
(B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0+L S
3 60 0 0 1/5 –4/15 1
3/2 X
2 160 0 1 2/5 –1/5 0
2 X
1 120 1 0 –1/5 4/15 0
Total Profit (Z
j) 480+60L 2 3/2 (1+L)/5 (7–8L)/30 0+L
Net Contribution (C
j–Z
j) 0 0 –(1+L)/5–(7–8L)/30 0
Sinceallthevaluesinthe(C
j
–Z
j
)≤0,sothesolutionisoptimal.Theoptimalsolutionwill
changeifatleastoneof(C
j
–Z
j
)>0.Wewillfindthevalueof‘L’forwhichthenewsolution
remainsoptimal.Inordertodothis,weevaluate‘L’ineachcolumnforthenon–basicvariables.

11. LP:SENSITIVITY ANALYSIS (Cont…)
11
Howdochangesmadetothecoefficientsofbasicvariableaffect
theoptimalsolution?
From‘S
1
’Column: (C
j
–Z
j
)≤0–(1+L)/5≤0L≥–1
Itmeansthat‘S
1
’willnotenterthebasisunlesstheprofitperunitfor‘S
3
’willdecreaseto‘0+L
=0–1=–1’;ifitgoesbelow,thesolutionwillnotremainoptimal.
From‘S
2
’Column: (C
j
–Z
j
)≤0–(7–8L)/30≤0L≤7/8
Itmeansthat‘S
2
’willnotenterthebasisunlesstheprofitperunitfor‘S
3
’willincreaseto‘0+L=
0+(7/8)=7/8’;ifitgoesabove,thesolutionwillnotremainoptimal.
RangeofOptimalityfor‘S
3
’:
Here,thevalueof‘C
5
’rangesfrom‘–1to7/8’(i.e.–1≤C
5
≤0.875).Inthis
intervalof‘C
5
’,theoptimalityisunaffected

12. LP:SENSITIVITY ANALYSIS (Cont…)
12
ChangetotheConstantsontheRight–HandsideoftheConstraint
Inequalities:
TheLPproblemis:
Maximum:Z=2X
1
+1.5X
2
2X
1
+(3/2)X
2
Subjectto:
3X
1
+4X
2
≤1000
6X
1
+3X
2
≤1200
X
1
≤180
X
1
,X
2
≥0
Contribution Per Unit C
j 2 3/2 0 0 0
C
Bi
Basic Variables
(B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
1 1000 +1h 3 4 1 0 0
0 S
2 1200 + 0h 6 3 0 1 0
0 S
3 180 + 0h 1 0 0 0 1
Total Profit (Z
j) 0 0 0 0 0 0
Net Contribution (C
j–Z
j) 2 3/2 0 0 0
Analyzingthe1
st
Constraint:Now,consider
an‘h’increaseintheright–handsideofthefirst
constraintthentheLPmodelconstraints
become:
3X
1
+4X
2
≤1000+1h
6X
1
+3X
2
≤1200+0h
X
1
≤180+0h
Contribution Per Unit C
j 2 3/2 0 0 0
C
BiBasic Variables (B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
3 60+(h/5) 0 0 1/5 –4/15 1
3/2 X
2 160+(2h/5) 0 1 2/5 –1/5 0
2 X
1 120–(h/5) 1 0 –1/5 4/15 0
Total Profit (Z
j) 480+(h/5) 2 3/2 1/5 7/30 0
Net Contribution (C
j–Z
j) 0 0 –1/5 –7/30 0

13. LP:SENSITIVITY ANALYSIS (Cont…)
13
ChangetotheConstantsontheRight–HandsideoftheConstraint
Inequalities:
Rememberthatastherequirementofthesimplexmethodisthatthevaluesinthequantity
columnnotbenegative.Ifanyvalueinthequantitycolumnbecomesnegativethenthecurrent
solutionwillnolongerbefeasibleandanewvariablewillenterthesolution.
Thus,theinequalities:60+(h/5)≥0,160+(2h/5)≥0&120–(h/5)≥0;aresolvedfor‘h’:
60+(h/5)≥0(h/5)≥(–60)h≥–300;
160+(2h/5)≥0(2h/5)≥–160h≥–400;
120–(h/5)≥0–(h/5)≥–120h≤600.
Wewillget:h≥–300,h≥–400&h≤600
Since:b
1
=1000+hthenh=b
1
–1000;
Thevalue‘h=b
1
–1000’isputintotheinequalitiesh≥–300,h≥–400&h≤600
asfollows:
h ≥ –300
b
1–1000 ≥ –300
b
1≥ –300+1000
b
1≥ 700
h ≥ –400
b
1–1000 ≥ –400
b
1≥ –400+1000
b
1≥ 600
h ≤ 600
b
1–1000 ≤ 600
b
1≤ 600+1000
b
1≤ 1600
Thus,therangeof‘b
1’is:600≤b
1≤1600.Undertheseconditions,XYZ
ManufacturingCompanyshouldproduce‘120–(h/5)’model–Agratesand
‘160+(2h/5)’model–Bgrates.

14. LP:SENSITIVITY ANALYSIS (Cont…)
14
ChangetotheConstantsontheRight–HandsideoftheConstraint
Inequalities:
TheLPproblemis:
Maximum:Z=2X
1
+1.5X
2
2X
1
+(3/2)X
2
Subjectto:
3X
1
+4X
2
≤1000
6X
1
+3X
2
≤1200
X
1
≤180
X
1
,X
2
≥0
Analyzingthe2
nd
Constraint:
Now,considera‘k’increaseintheright–hand
sideofthefirstconstraintthentheLPmodel
constraintsbecome:
3X
1+4X
2≤1000+0k
6X
1+3X
2≤1200+1k
X
1 ≤180+0k
Contribution Per Unit C
j 2 3/2 0 0 0
C
BiBasic Variables (B) Quantity (Qty) X
1 X
2 S
1 S
2 S
3
0 S
1 1000 +0k 3 4 1 0 0
0 S
2 1200 + 1k 6 3 0 1 0
0 S
3 180 + 0k 1 0 0 0 1
Total Profit (Z
j) 0 0 0 0 0 0
Net Contribution (C
j–Z
j) 2 3/2 0 0 0
Contribution Per Unit C
j 2 3/2 0 0 0
C
Bi Basic Variables (B) Quantity (Qty) X
1 X
2 S
1 S
2 S
3
0 S
3 60–(4k/15) 0 0 1/5 –4/15 1
3/2 X
2 160–(k/5) 0 1 2/5 –1/5 0
2 X
1 120+(4k/15) 1 0 –1/5 4/15 0
Total Profit (Z
j) 480+(7k/30) 2 3/21/5 7/30 0
Net Contribution (C
j–Z
j) 0 0 –1/5–7/30 0

15. LP:SENSITIVITY ANALYSIS (Cont…)
15
ChangetotheConstantsontheRight–HandsideoftheConstraint
Inequalities:
Rememberthatastherequirementofthesimplexmethodisthatthevaluesinthequantity
columnnotbenegative.Ifanyvalueinthequantitycolumnbecomesnegativethenthecurrent
solutionwillnolongerbefeasibleandanewvariablewillenterthesolution.
Thus,theinequalities:60–(4k/15)≥0,160–(k/5)≥0&120+(4k/15)≥0;aresolvedfor‘k’:
60–(4k/15)≥0–(4k/15)≥–60k≤225,
160–(k/5)≥0–(k/5)≥–160k≤800&
120+(4k/15)≥0(4k/15)≥–120k≥–450
Wewillget:k≤225,k≤800&k≥–450.
Since:b
2=1200+kthenk=b
2–1200;
Thevalue‘k=b
2–1200’isputintotheinequalitiesk≤225,k≤800&k≥–450as
follows:
Thus,therangeof‘b
2’is:750≤b
2≤2000.Undertheseconditions,XYZ
Companyshouldproduce‘120+(4k/15)’model–Agratesand‘160–(k/5)’model–B
grates.
k ≤ 225
b
2–1200 ≤ 225
b
2≤ 225+1200
b
2≤ 1425
k ≤ 800
b
2–1200 ≤ 800
b
2≤ 800+1200
b
2≤ 2000
k ≥ –450
b
2–1200 ≥ –450
b
2≥ –450+1200
b
2≥ 750

16. LP:SENSITIVITY ANALYSIS (Cont…)
16
ChangetotheConstantsontheRight–HandsideoftheConstraint
Inequalities:
TheLPproblemis:
Maximum:Z=2X
1
+1.5X
2
2X
1
+(3/2)X
2
Subjectto:
3X
1
+4X
2
≤1000
6X
1
+3X
2
≤1200
X
1
≤180
X
1
,X
2
≥0
Analyzingthe3
rd
Constraint:
Now,consideran‘L’increaseintheright–hand
sideofthefirstconstraintthentheLPmodel
constraintsbecome:
3X
1+4X
2≤1000+0L
6X
1+3X
2≤1200+0L
X
1 ≤180+1L
Contribution Per Unit C
j 2 3/2 0 0 0
C
Bi
Basic Variables
(B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
1 1000 + 0L 3 4 1 0 0
0 S
2 1200 + 0L 6 3 0 1 0
0 S
3 180 + 1L 1 0 0 0 1
TotalProfit(Z
j) 0 0 0 0 0 0
NetContribution(C
j–Z
j) 2 3/2 0 0 0
Contribution Per Unit C
j 2 3/2 0 0 0
C
BiBasic Variables (B)
Quantity
(Qty)
X
1 X
2 S
1 S
2 S
3
0 S
3 60+L 0 0 1/5 –4/15 1
3/2 X
2 160 0 1 2/5 –1/5 0
2 X
1 120 1 0 –1/5 4/15 0
Total Profit (Z
j) 480 2 3/2 1/5 7/30 0
Net Contribution (C
j–Z
j) 0 0 –1/5 –7/30 0

17. LP:SENSITIVITY ANALYSIS (Cont…)
17
ChangetotheConstantsontheRight–HandsideoftheConstraint
Inequalities:
Rememberthatastherequirementofthesimplexmethodisthatthevaluesinthequantity
columnnotbenegative.Ifanyvalueinthequantitycolumnbecomesnegativethenthecurrent
solutionwillnolongerbefeasibleandanewvariablewillenterthesolution.
Thus,theinequalities:60+L≥0,160≥0&120≥0;aresolvedfor‘L’:60+L≥0
L≥–60.
Wewillget:L≥–60.
Since:b
3=180+LthenL=b
3–180;
Thevalue‘L=b
3–1200’isputintotheinequalityL≥–60asfollows:
L≥–60b
3–180≥–60b
3≥–60+180b
3≥120
Thus,therangeof‘b
3’is:120≤b
3≤∞.

18. LP:SENSITIVITY ANALYSIS (Cont…)
18
ShadowPrices:
ShadowPricefor1
st
Resource:
Asweshowedearlierthatiftherighthandsideofconstraint–1isincreased
by‘h’unitsthentheoptimalsolutionis:X
1=120–(h/5)&X
2=160+(2h/5).
Theresultingprofitiscalculatedasfollows:
Z=2X
1+1.5X
2=2X
1+(3/2)X
2
Z=(2)[120–(h/5)]+(3/2)[160+(2h/5)]
Z=(480+h/5)
Now,let‘h=1’,wefindthatZ=(480+(1/5))=480.20.
Asweknowthattheoptimalvalueoftheobjectivefunctionoftheoriginal
problemisRs.480.20,sotheshadowpriceforthe1
st
resourceis480.20–480
=Rs.0.20.

19. LP:SENSITIVITY ANALYSIS (Cont…)
19
ShadowPrices:
ShadowPricefor2
nd
Resource:
Asweshowedearlierthatiftherighthandsideofconstraint–2isincreased
by‘k’unitsthentheoptimalsolutionis:X
1=‘120+(4k/15)’&X
2=‘160–
(k/5)’.Theresultingprofitiscalculatedasfollows:
Z=2X
1+1.5X
2=2X
1+(3/2)X
2
Z=(2)[120+(4k/15)]+(3/2)[160–(k/5)]
Z=480+(7k/30)
Now,let‘k=1’,wefindthatZ=[480+(7(1)/30]=480.23.
Asweknowthattheoptimalvalueoftheobjectivefunctionoftheoriginal
problemisRs.480,sotheshadowpriceforthe2
nd
resourceis480.23–480=
Rs.0.23.

20. LP:SENSITIVITY ANALYSIS (Cont…)
20
ShadowPrices:
ShadowPricefor3
rd
Resource:
Asweshowedearlierthatiftherighthandsideofconstraint–3isincreased
by‘L’unitsthentheoptimalsolutionis:X
1=‘120’&X
2=‘160’.
Theresultingprofitiscalculatedasfollows:
Z=2X
1+1.5X
2=2X
1+(3/2)X
2
Z=(2)[120]+(3/2)[160]
Z=480
Theshadowpriceforthisresourceis‘Zero’.
Thereisasurplus(i.e.,excess)ofthisresource.Duetotheexcessofthis
resourceconstraint“X
1≤180”isnotbindingontheoptimalsolution(X
1=120
&X
2=160).
While,Constraint–1andConstraint–2,whichholdwithequalityattheoptimal
solution(X
1=120&X
2=160),aresaidtobebindingconstraints.Theobjective
functioncannotbeincreasedwithoutincreasingtheseresources.Theyhave
positiveshadowprices.

21. QUESTIONS
21