Faaliyetler İş Araştırma ve İktisat Sensitivity Analysis " .',' - , . . . . ............ '- Chapter 8 Linear Programming: Sensitivity Analysis and Interpretation of Solution • Introduction to Sensitivity Analysis • Graphical Sensitivity ~ • Sensitivity Analysis: Computer SOlution • Simultaneous - Changes C 2006 Thomson South-Western. All Righu R~suved. Standaid Computer Output • .In the previous chapter we discussed: • objective Jimction value • values ' oe"the decision v~bles • reduced costs • slack/surpl~s Slide 1 . ;f~:~~~~;'- :': I }- -~ ~ :,,~:~r:.e C:!~~~~f the objective function • changes in the pght-hand side value ofa . constraint· -' .'. -- . .. '. ~.' ~ ~ ~ - - -;;~~;~:f~:;:;:':;:'::: .:. .-.. . .. : . :.: ... -- - - .. '. LP Formulation -Example 1- Xl ~ 6 2r1 + 3x 2 .::: 19 'Xl + x 2 .::: 8 . ,. ',' . . ,,' ,! ~! . - ~- - Slid~5 Standarp.Computer Output Software pac~ such as .The Managemen t Scien tist and Microsoft Excel provide the foUowing LP information: • lnformati~about the objective function: • its op~ value • coefficierd: ~ges (ranges of optimality) • lnformati~ut the decision variables: • their op~ values • their redlXEld costs • Informatioaabout-the.amstraints: • the am0u,ntol" slack or surplus • the d~.pri06 · • . right-hand side ranges (ranges of feasibility) IC 2006 TholJ\5on .s.:....r..Wesl"'m. All RighU Reservt'd. ; "; "; _ SeJ>sjtivity Analysis • --Sensiti~ity~am.,sis: (or ~t-optimaljty analysis) is - used to qet"~ how the optimal solution is affedeil 'b¥·.~, ~itrun ~'-pecified ranges, in: . , ... the-.o.b~..function£oefficients ' . i.h~-righ't~_~_de '(IlliS) 'values Sli d", 2 . _ . ~~uiy~~~~ .~6rtant to the manager who_ . :·m~s~,~j:i~~r~~_~.:iI~tJiit 'e .rivironment with '. im·pfedse.. eS'lilutes·of,tt1e roeifu:.if'.Ilts. .. - )- . 1!:_$.ens,itiXi~,~~.alJQ"Ws_Jij~ .to_ ask certain what-if ._ · .. : gu~~o~:~~~~prp~ie,il.::.. . . '.' - . .. . '- .,,' -.-. - - - '-: ----'.:'.: .. "'-:- .:~-1:" --: ., -, ' .' .~-~ .~ .,. -, ~.-,.~~, ~.«:~:):)~~:~)~ . - . . - .,- · .7·~_--: _ Example 1 .~ . Graphica!'Sohdion (12006 Thomson So~. AlFRishts ~ed. Slide 6 1 Objective Function Coefficients • Let us consider how changes in the objective function coeffiCients might affect the optimal solution. • The range of optimality for each coefficient prov~_ the range of values over which the current solution will remain optima[ • Managers should focus on those objective coefficients that have a narrow range of optimality and coefficients ne':lr the endpoints of the range. Cl2006 nion\san South-Western. All Rights ~ed. Slide 7 Range of Optimality • Grap~~llY. :the l,imits of a range of optimality are found·ry.c!:tangmg :the slope of the objective function lme'Wit.friri.' lh·e iitiuts of the slopes of the binding , consttairit Jines. • . Th~~s1D"Pe~f:ai.l ~b1.~~e functio n line, Max ClX 1 + <~2f.is··;~·d '4 ·and the slope of a constraint, a,Xl + Q,X, .. ",p'}"~~'1f'~ ',. I_,~:. t:.'·-·~:f~~f~;{~~~~:~~"~~:~' ::--."., '." / , ... /' .;-... -;;., ..... " '1"' :'" -, -:::: +..:::' -!:' -'': ~: '., ., '; . { '. j; '.~ "J: '. , . \ \ - .. ... ~' . '- .', . ..... .• . im~{~:¢p~mali~ :fbr C, ;PQ1(fthe ·range.of values for c 2 ( with c1staying S) such truit the objective function line slope lies between thaFdf the."bvo bin~nstraints: . Multiplying by -L Inverting. Multiplying by 5, -- 1 5 -Sic, ~ ,2/3 1 .2: Slc,.2: 213 1 .::. c l /5.::: 312 5 ~ - c, < 15/2 C 2006 ThOIJ15()n South-We5t~ All ~hts Reserved. Slide 11 . - _._~.=~ Example 1 • Olanging Slopr~Objective Function r, 02006 Thomson Sou~ All Rights ~(>rv~ . Example 1 • Range of Op~ for C l x, Slid~ 8 The slopeaf6e .oi?j,*~v~ ~"c~~~ .~~ ~ -1:,/C:l. The slope of thrJiist binding constraint, Xl + Xl .. B,.is - 1 and the slopr4th! second bindipg~6p~traint. Xl , of 3x, "" 19, is -2~. " . , , . . . . . Find the ...... _o~ v;aI!l~$.f9(~~t0ti).c~>~Y.ing 1). . . such that the otjt!dive fun~!:ion .lli)e~:.sI~pHleS · betWeeri' that of the twoliitnding torutr'aints:': ~ ." '.' ... . . ~ ~ .. -<'~/! ·~ ·:·.2:!t·;.:j;_~~~>::. ·~ .. : .. :~'- " . . Multiplyu.clhrough by···7 (~ri~ ':"exe:r:sipg th~::: . inequa[;ties) 1:"1413 i i;:;;H57;~;;_ ;: ;:,'.,. . .... " '.'" ,.,', '. . Example 1. ' "". - ' ' . . - , - .. , . • Range of Opt· ~y for c 1 ' and Cj .' . ' , . . . Ad'ustabte Cells An" ,-",:ed Objective Allowable Allowable """ Name .v.lue .".. 1(', mele':" . II'!':"",,," ~~ S9sa Xl 5._ .. 0.0 5 2 0.33333333 SCS8 X2 3.U - 0.0 7 0.5 2 {;oostrniolS Fin. _d~ Con.tntnt Allow.ble AJlowlble Cell Nama ,/.,,- Pm. R.H. $Ide Inc~ .. Decrease S8S13 #1 5 0 6 lE+30 1 SBS1 4 " - .. 2 19 5 1 '9w.; #3 • 1 • 0.33333333 1.66666667 -~ _ .. 02006 ThOIrui On So~tem . All Rights Reserved. Slide 12 _ 2 Right-Hand Sides • Let us consider how a change in the right-hand side for a constraint might affect the feasible region and perhaps cause a change in the optimal solution. • The improvement in the vaitieOnhe optimal solution per urut in~ease in the right-hand side is called the dual price. . • The range of feasibility is the range over which the dual price is applkable. .. • As the RHS increases. olherroJ)StraintS will become binding and limit the chan?::". ci it • alue of the-- . ~ ~- .'-- . ~bjective function. ~ 0 2006 TholJ\5on South-Western. All Rights Reserved. Slide 13 Relevant 'Cost and Sunk Cost • Aresource cost is a relevant cost if the amOilnt paid.for _ it,iS dependent upo~ the aQlO.m:tl of the resource.used ; by tile decision variables. '. Relevant costs are reflected in the objective function :- ;:"?-.-}- ~-~,- . ~ ~- ~--coefficients. ~ '. -,' .. ~- _ ~- _ ~' . ' .- ... . A resource cost is a-sunk costif jt .must be 'paid :);~~~~;~~~~~~;. ;;::;;~'~:;~:~d~{o~::;a~:.·Of the' T~urC~' actually used - " -:~ . :' .:. " -~ _ ' E?Un.k " resource costs are riot reflected in the objective :", ·.Y~·~:i·;.,:;'·~_~·~.~: :-<> , > function coefficients. ", . ~;( -!~« .--~:;~;; ~ \:< -:\. '/.. . .- '.' ': .. '." '. '. ",' .- I - . ,... h- ~ Dual Price -- • Graphically, a dual price is determined by adding + 1 to ihe right hand side value in question and then resolving for the optimal solution in terms of the same two b~g constraints. • The dual price" is equal to the diff~rence in the" values of the objective functions between the new and original prob&ems. • The dual price for a non~inding constraint is O. • A negative dual price indicates that the objective function will ~ iinprove if the RHS is increased. - 0 2006 Thomsoll SoVdt-We;lem. All Righls Reserv~. Slide 14 ." ~· ' .•... '.' . . Example 2: OlympIC Bik~ C~. -ii - • Model Formulation · . " " " • Verbal Statement of the Objective Function _ MaxiIuize t~_ weekly profit ~ 4erba1'St;I~';' -'sf 1 e -ConStTaini~ Total weekJy usage of aluminum·all.oy S. ]00 pounds. Total weekly usage of steel alloy ~ 80 pounds. ·'1)efirution of the Decision Variables --%1 = numeer~luxe &ames produced'weekly. ----X 2 "" nu~ber of Prof~ssionaf frames produced we~ 0-2006 Thomson 5oulh-We;~rn. An Rights Reserved. Sifot' 24 .; 4 . - .~ .:;' . ... ... ~ .- Example 2, Olympic Bike Co. • Model Formulation (continued) Max lOx, + lSx 2 5.1. a l + 4x 2 ~ ]00 3.1'1 + 2x2 ~ 80 _ (Total Weekly Profit) (Aluminum Available) (Steel Availaple) (12006 Tholn$on South-Weslern. All Righ~ Reserved Slide 25 Example 2, ' Olympic Bike Co . . .~ . ' ; " ~ , :.)~}<~~}d~):)o ":;,:::.} .:: ", _ ,_ 0 ., . : ,," ., '. ' . . Example 2: Olympi'c Bike Co . . ~ . • Range of Optimality , ~ Question _ Suppose the profit on delUxe frames is increasiW .Jg.S2..0. 15-the above.solution still optima)?: Wliaf is'-:'" - - 11ie value of the objective function when this wtit profit is increased 10 $20? a-ple 2, Olympic Bike Co. • Partial Sp. 5 'oeet Problem. Data Slide 26 • OPtimal:';;;'.2~ OlympicBike CO. d Accord"i~{ili~ butpnc" "._. ~l~!:-!!~~e:~l ,._ ... ~~ie~si'orfarJrames) 1i:j~~~W~i~::·~~~t:~ ... 0:.;;.', - ", •• ~ 15 17.5 $412.50 . S:lide~ : -''*, • ~I~ Exa"'!'li~ ?C:QllympicjBike Co . . '~C;~ ; ',.. ~ilt';· 1\" ---;.; .~ _Adj~tab!e Cells I ~d~c,;.~ Cbje~!~,~ Allol:able Allo':J3ble ::!! Name , ., Ccst i~ .. ~~Iii:~:.;: ;I,crease Dacre~:;c sese Oe!u.xe 0 10 12.5 ~S SCSB Pro~ess. " '. C.CCD 15 5 8.333333:;33 CcnstrainlJ: I ; S~ ,a~c'/I CUII:.lraim AIIC'.\'able Allowab!e Cell I·lame V: .. ?ri~e R.H. Sic!e Increase Dacrease $ESt3 Alumlnu" ~ 3125 tOO 60 4666€66657 ~Sl_"_' ____ : __ '2~ ___ eD 70 3D Q 2006 Thomson So1l6~ Slide 30 " . . ; 5 Example 2' OlympIC Bike Co. d • Range of Ophmality Answer The output states that the solution remains __ optimal as long as the objective function coefficient of :r 1 is be~.e~?.5 and 22.5. Since 20 is Within this range; theoptimaJ solution will not change. The optimal profit will change: 20.1 1 + 15x 1 = 20(1 5) + 15(17.5) - $562.50. 02006 Thomson South-Wntem. All Right! R~rved. 5lidt31 Ex~mple 2: Olympic Bike Co. Cor,s!';;m-::" FIP31 Snl:::!~'1 Ccnstramt AIlO.'Iable Allowable Cell I~~rre 'J;;~'" P~:e R H Sl~e Increase C;:crease SBS13 1;!.:nM(;;~1 :;:0 J 125 leO 60 45 ea66Wi7 S9$14 Steel ~:) 1 2~ 80 70 30 Reser-ved .- , ': '.: ..... . . ". :~'.. '-. '-. "'. ' . -. -'. -'. ' . " -. . ~"2-it.;((:)p.io/>';lity and 100% Rule ..... • The l00%~~~,;tates , that simultaneous changes in obj~tiv~'~filri£tion:cOefficients will not change the op~iupon ~s tong as the sum of the o~'''<" '''' . .. _._ . percentaJ~eS oHhe ch~ided by the '_ corresponding maximUm aUowable change in the range o(optiinality for each coefficient dOes nol exceed 100%. o 2006 Tho~Of\ South.We:;tern.=.All Righ~Re:served. Slide 35 Example 2:=O JymplC BIke Co ~ • Range of Optlr.nalily ~ Question if the ur":t pmfif on deluxe frames w~re $6 instead of $10, would the optimal solution change? Slide 32 Example 2: • Range of OptiuuJity Answer OlympIC Bike C o" d . . I '" ~ " .. '. '. 1f'e outputstalrs" that the solutio!l_ ~t;~m.s optimal as long as the objettive~hlnctibtt~helti'd~nt 'cjf- --- • r l is between 75arid 22.5. Sirice.6js~oiI~ide· this ~. : : ~ange, the OPtixaalSOIUti~~ :~~~!~:~~~~~,d~;.:; ~,: -.> -',-,::> -. " !',' ,' " _-'~ ,".;:·i·" : · ... ·i c · - .- ·" ."~ , ',- '-" '.,. , . . ~. ~ - _ .,;, ,:;.::;,, ,;- _ . ~ ... ,-.,~.;":.,-'-,t·· .-·-. ; ~.-.~: -.- '.! -, -.' '. :' .... '. Example 2: OlympIC Bi¥· Co .. ~ ' • Range of Optim;llity and 100% Rule- -- ! ' ~ Question ,- =-. If Sl. ''ISty_me'l';rOfit-01\~ names ~aiS~d toSl6~?rofit on Profe~sloj,ai­ frames was raised to $17, would the'current solution be optimal? o 2i96-- Thomson SoaIit-Wf':5tem. All Rights R~ed_ SIide'-3& . - 6 . !' " .:~ :: ,': Example 2. Olympic Bike Co. d • . Range of Ophmality and 100% Rule (I Answer If '1 = 16, the amount '1 ch~]6 ·10 "" 6 . The maximum allowabJe increase is 22.5 .. 10 = 12.5, so this is a 6/ 12.5"'48% change. U '2 = 17, the amount that '2 changed is 17 ·15 = 2 The maximum aliowabJe increase is 20 ·15 ~ 5 so this is a 2/5.F 40% change. The sum of the change percentages is 88 %. Since this d oes not exceed 100% "the pntimal solution would nOl.change. 0 2006 Thomson Soulh·W~tem. All Righl.S Reserved. Slide 37 Example 2: Olympic Bike Co. ~ • ~~e:::~Fea'ibility and Sunk Co," ~ Given that aluminum is a sunk cost, what is the -~. ':-"'.- ¥,~imJlm amoun. t the company should pay for 50 . .' ~x~~ 'pounds of alu.minum? .. ··:·i ;,:.:i .. ~~~l· ..... ·•·•· ...... ···.·· .. · . ';" ";i ~,.-~,\: ~!:: ~ .. . .. ~.:.", i '" . ' ...... ·_("!·t .... • ,.: ..... '", ,'.';".: ··C· -' .' : .-;:'.;;- 7-.(:. 7. '; ':7~:~-=';<'" -'-. "i : ,' . . ,,'., c.; ;: , _ : ; ' : L'~' ,~ .. ~ . ~c>~ . 22~~06~ .. ~Jh~ . o~~= . ~".=50~,~'h-=.~W~.c =!",,=.~. ~~="=:J:lj~ ·,~h=,,= : R1:s=. ='="="'= .. =: :-".:....~ . • ~.= .~ := :-S~.~d~'="= · ~: J ' ... ...... ' ." '\.-~'-'.--'.' '! . , ',, ', ., ', "-- ~'" :'-- '., '. --:".' Example'?: Olympic BikeCo: _.. . Range of Feasibility a~d Sunk Cos~s .' . Answ,", Since tl;1.e cost for aluminum 'is a swUc. cos~· -;::. . .~ price provides-the value of.extra alurinu~. The shadow price for aluminum is the same a$ its dual price (for a maximization problem). The shadow .f----< ... ...E:E":eto, aluminum is $3.125 per pound and the =- - _ !llID:imum aUowable increase ~ 60 pounds, BtJ5.~ ;- :·~>;;i~:I;, ;~_:!\ ·<-··;~ .::",~-' ~ .. ~::):\~~ . " .~~';."':'; . Question . - - - --- - d Example ~ Olympjc Bike Co. • Range of Feasibiti';'and R$levanl Costs ,..,...1-..,;;--- -n aluInimJliH;'e~e-a re!evanlcost, what is the ~imum a~t ·lh·~c·~.~ pa -y for 50 extra pounds of- aluminum? 0 2006 Thormon SOUtb-Wr5~. All Righl.S R~ed. Slide 42 .. ... > 7 ,-~ --=-- ,-- Example 2: Olympic Bike Co. d • Range of Feasibility and Relevant Costs Answer U aluminum were a relevant cost, the shadow price would be the amount above the normal price of aluminuQl the company would be wi.llhlg to pay. Thus if initially aluminum cost $4 per pound, then ' additional uruts in the range of feasibility would be worth $4 +$3.125 == $7.125 per pound. C 2006 Thomson SOuth-Western. All Rights Reserved. .. . . , . Example 3 . . ~:'~~' :.~:~;~;:;~~~..:.;.:~~--:::: ..... .:-:: , ) I I I I I I 1 • 1 , , Reduced Cost 0.000 0.000 Dual'Price 0.000 . -Q.600 4 : 500 ' 5J.ide 43 '. '.' . ,Slide 45 , '. " . ~ . ' . _. '. '. ' . o . ' • • .. :?E::.~::F.inple 3 • OP~ ~-?;~~~, , : AC-~6~dirig " t~ -th~' ~~'tput: ., ,,:·TI .i:,~.'·i.;5 ., ,. '0 Xl :0 2.0= -:."" • ... . Obje 2006 ThoIn5on SO ........ ~te~ . AU ~ghts Reserved. 1 . ,;. ~:.;. " -, 'Ex~mple3 . ~., . " ,'( " "}-;' ~ ··:4:·:~?:f; \~- \~:::~ .~'=" .: - .-,:.:" . ' -... ... . •. -. : . E~~'iple 3 '. ~ - • Range of.Optioulity ~4·~~~:Ru .b! .. . Question _ ~' . _ - Slide 50 !S ~ . ,wlolt:anrously .~e s~tof Xl was ra~ to $7.5 . -" inQdbe cost of Xz wits 'reduCed to $6~d tJ-re current solu tion remain optimal? . ==- - ---- ""," - - fC 2006 ThoIlt5on SOulll-Wfrstrrn. All Righb. ~ Slide 54 9 -~I = .- - Example 3 • Range of Optimality and 100% Rule Answer If c} '" 7.5, the amount c} changed is 7.5 - 6 = 1.5. The maximum aBowable increase is ]2 -_6 = 6, so this is a 1.5/6 = 25% change. If C 2 = 6, the amount that C 2 changed is 9 - &= 3. The maximum allowable decrease is 9 - 4.5 = 4.5, so this is a 3/4.5 = 66.7% change . . The sum of the change percentages is 25% + 66.7% = 91.7%. Since this does not exceed 100% the optimal solution would not change . . 4:1 2006 Thomson SoLith,Wl'5terR AU Rights Reserved. Slide 5S Example 3 Variable . X1~ _X2_" Lower Limit c- QJJOO ,- ~ . Current Value Upper Limit 6.000 ' 12.000 : :4',1)0: 9.000 <02006 Thomson South-We:>lern _AU R!gb.ts ReselVed. No Limit 'Upper Limit N9 L U:n-it . 55:000 4 000 1 Slide 57- _ : Slide 59 Example 3 • Range of Feasibility Question If~-hand side of constraint 3 is increased by 1. what wiU be the effect on the optimal solution? Q 2006 Thomson So~e.tem. All Rights Reserved. Slide 56 Example 3 • Range of Feasibility Amwer - A dual pritr represents the improvement-in-the objective hmctiolll value per unit increase- iJl ··t:h~·r,igh~­ hand side. A negative dual price indiC atE!S :a-:-~ . . deterioration (nrgative improvement}_uj_ ~e: .. - ,;_ .. ~ .. _ objectiv.e, whidt in this problem meanSah.~m&~Se -Ui-· total cost - becausewe';e minimizing: siric~' ~ :righl- ' han.dside.re_~ within tf)e- .range9ne;isj~i:)ri:'~~~--··~--· : there is no thange in theoptimarS6h.iti.0i1: :::~er, ·_· : 'th: e ?pj~tj;je' function-value in;c_~~ll~_§X~~P(~~t t' ~~;"_ , -~ :' :' :' -, - - - '. 10