صفحه 1:
ی
V1 ملاسما مه ر() توم موم لته سول( ود ساس م11
Oxotra ond Dusievakne Ovosatarnrannnt .با Dane روا ,مت 24
resection: W. Guarper
0
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 2:
اه مه مس 1 21-10 3
و را و و موه توا رت لهج ورین تروق
raised ork ars. موكلا
we z= Oxy + Oxo وه اس
Ce Pe ORT Oxy te SDD (Prichin rocetctd)
OO (Gapeuy mwtrcd) 5 ولا ود
mS PO (deword sowie)
eX ZO — (ees revretva)
Okere:
aq = cucvber oP subdiers produced wack weels
امه < ود oP tras produced each weeh.
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 3:
DDN 0-0 ۵ 0 © Cowan Pooks
“her opted ack Pow ty
LO wae 2 = 100, x=
BO, xo = OO (port O ms
the صمي to the right) ocd it
baw ma, 20, orl 56 (fe shark
تج امه لین
اد هت مت
ew would chooges to the
probles's vbievtive Pucmtioa
تام or right-hoerd
side vohues chorge this
vpttcral svhutica?
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 4:
اه مه سس 10 21-10 3
(Graphic ocralysis oP the ePPet of مس( مشاه مه و من و
vite Por the Biapetto LP skews:
Oy tepevion, we cod see thot wokiag the slope oP the isoproP it lice
wore aegaive thac the Poishte coastratat (slope = -O) will couse the
vpticodl potat to switchs Prose poiat to نمی C.
Likewise, wohiog the slope oP the tsvproPit hoe bess oeyative tho the:
perpediry ovestratat (slope = -() wil couse the optical pote to switchs
Prow poict @ te port @.
Cleury, the slope oP the isoproPit hoe west be betwees -O ocd -0 Por
the curred busis to اون تحص
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 5:
اه سم ۹ 10۱ 10-10 BED
Dke vdhuer oP he cootibutica to proPit Por svlders Por whick tke cuncect optical
basis (xq,%0,59) wil rewrote optcodl coo be deterciced os Polis!
Let ma be the coairbutios ($9 per solder) to the proPt. (Por what ches oP cy doer
مس متا امه با opal?
ممصم 2 رو + زورك مه له 0 - زد بو ۵
ed 0
ا ولتت = رس weg
>©- :ل > وراد > مه
© > وح > © ١. :صاصر يه سا وام
و
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 6:
اه مه مس 1 21-10 3
(Graphicd @odbsis of the @PPect oP oa Okoage ic RWG a the
L's Opticodl Gotutiva (usiag the Giapetio problew).
© qropkicd ccdpsis coc ds be used to deterxvice whether ذا جات و
the rhe oP a poestroict wil wake the punedt basis uv brogyer optical. (Por
mop, bet ba = currber oP ما رجا الم
he curred opteal svtutiva (pot B) ts where the corpeury ced Pietshtargy
باه تسه IP the vale oP by is cbooged, theo os bray os
وی رن امه ری سا مور ane biedicy, the optical
از
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 7:
اه مه سس 10 21-10 3
0
4a tke Btapetio problew to ke
right, we see that P ba >
(20, xa wil be مج قصب
PO ced wil viokte the لحم
powirad. ,مدا & by < OO,
رید Wil be bese tort CD oerd ther
اوه شوه Por x
wail be vickted.
DherePore: OO S$ وط > 00
on x
Rotoking cocstratal, bd = CdtD
OAD = 2 سا ول
وه
ایس مسا
Rothiag eoastratal, bd = AD
وه
هه
Dhe curred baste rewaier
دمج Por OD Shu S120, -g
bat the devisiva vorble uve
رت سره لو
و مه وه وم eo
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 8:
اه وه سور( سدس 0-0 BOM
Ohad Prives (veka he Brapetiy problew)
is ote koportedd io detec how o choy io cousin's rhs chores the
ساره مرن جرا Or :متا
Dhe shadow price Por the tis cocstcatat oP oa LP is the ارت روا مج
و و او و مان و و و او مود لوف
pevblese) او بطم و خأ bay mar. (Dist ebsites op tre
Pei و ا eaves the ون مه
۳ ره بت ما ما۳ ۵ + 100 رم بط (ase cris fe
ع وج موه ام را با رن عم ما مه 90 + A ocd
x0 = OO - ۵ حطس = Oni + Oxo = (CO + A) + 60606 - ۸۵( ۶ 6۵ + ۸
hve, oe bag oF he cunt boasts ی بط و و او و ره مر
و و مج the سرد اوه by $0. Go, he shadow price Por
the Prat (Proshioy hours) cocmtrctct is $0.
و
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 9:
اه وه سور( سدس 0-0 BOM
عصراهه<) روهظ oP جججواءصوو |"
Por severd recs! مروت وراه و6
۰ و ۳ سوه تن من راو ون cheer,
جراوه وا موی ج ۱ موه وراه رورطووو the problecr orci.
0
chaps to $9.60, sevstviy omer shows he curred schtiod recrcics
paced.
٠١ بف ص9 obo LP parnveters. athe Bipot problew Por رام
Pike weehy deword Por sober of lest OO, the opted schar
ewan OO sokters ord OO trace. Phus, evra P dewond Por
ری ها ماو the poepaay con be Rady ooaPidet frat it ott
و من produce OD sokters ard OO wats.
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 10:
سه ما لت 105 2-11 5
AP aa LD kos wore thao two decisive varubles, the rocge oF
valves Por a rhe (or objective Puortioa ooePPictet) Por
whick the basis newvuies opticcd! cocant be detercviced
دی مد
hoe but this is oPtec روا مه سا مت مرجم لك
deterxviced by a puckoged دیص they are و رصح
powpuier progrca. LIDOO wil be used aed the
interpretaiiva oP its secsiiviy osdsis discussed.
0
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 11:
عبت رم لسن 2-1 3
Oovsider the Polowieg soxvizaiog probes. Oteov sels Pour types
oP produsts. The resvurves ueeded ty produce vor voit oP eal
we!
شمه | یی | Prot | Prk | عمج
موم 9 8 Rav word
Ss 9 5000 م« 9 Lows oP bor
se 56 5 so عم 5
Do weet nse dew, exardy OSO total vite wast be produced.
بسا هلجم مومس POO units of product @ be produced.
Pore oa LP ty مرو proba.
Detox = xeober oP units oF product i produced by Diary.
00
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 12:
3 ۰-1 هه مر لسن
ل موز ول(
wor z= Pxq بعرم ۲+ م9 + ©
ود را + xe + x9 + xp = 0
xe 2 FOO
Ox + Oxe + Ps + Pap S FOOO
Ox + Px + Gag + Oxe S SOOO
7,7۵, 2 0
©
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 13:
0 — Vke Ovwputer ced Grusiivipy Poabsis
1۷۸ 411 + 610 + 723 + 06
SUBJECT TO
2( 1 +۵ +3 + 4 2 0
3( ۱4 <- 0
4 21 + 322 + 413 + 7 14 >< 0
5( 3۱1 + 42 + 513 + 6164 >< 0
END
LP OPTIMUM FOUND AT STEP 4
ای فجفی LAIDOO
و
FUNCTION VALUE
.6650 )1 مخ هو وا
VARIABLE VALUE REDUCED cost سارت
x1 0.000000 1.000000 ات لبون
0.000000 4400.000000 2
x3 150,000000 0,000000 اس سا نم
clea x4 490.000000, 0.000000, 0
Row SLACK OR SURPLUS DUAL PRICES الحم سره سل
3.000000 0.000000 )2
sek in. 3) 0.000000, 2.000000
1.000000 0.000000 )4
0.000000 250.000000 )5
NO.ITERATIONS=_4
9
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 14:
له هه له 0 20-7 7
۱00۵۵۵ WW OVO MC OGOAG ۵ 000۵۵۵
Od COOPMOAGOT KOOL
CORMOLO — CORROOP.— OLOOHOLD
PUOOOOLD
مموهومهد 2 مومه
01
Xd F.OOOHOD همهم
x8 B.M0ODOD 0666668
©S00000
PMOOOOD — d.DOOOO
B.H00O0D =~ E.-MDODD
ROUVMLOOO O18 OOH
ROM CORREO OUOMOOLD
OULOOOOLD
100۵۵۵۵۵ مد
ae
IGaryriabtd@k2003 Brooks/Cole, a division of Thomson
صفحه 15:
اه مه له 0 20-1 7
MAX 4 )1 + 6 3ع 7 + 2ك + 4
SUBJECT TO
2) XL4+X24X34X4= 0
3) X4>= 0
4) 2 )1 + 3 2 + 43 + 7 4 >- 0
5( 301+ 4 (2 + 513 + 614 > 0
END
OPTIMUM FOUND AT STEP 4
REDUCED COST
1.000000
0.000000
1150.000000 0.000000
x4 400.000000 0.000000
Row SLACK OR SURPLUS DUAL PRICES.
2) 0.000000 3.000000
3) 0.000000 -2.000000
4) 0.000000 1.000000
0.000000 250.000000 كك
NO. ITERATIONS= 4
ط77###ح##7بب 77_77 22 ۰ زر
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 16:
5-1 Oowputer ord Grusiviy Poabsis
eterpretaiva oP shadow prives Por the Diao LP
ROO CLOCK OR GCORELOG OOGL PRICES
سم 5000000 0.000000 (
اد
9) 0.000000 ©.000OOO —(praxhes
© decreed)
(raw watered ۱۵۵۵۵۵۵ 0.000000 م
chard, steht (Died) prise whine’ $O وو ع سم eins rece oF جد قيمع
عو تاج سس تن opi RD ۲ مس(
0.7۳ SOR رت 0ب rot pack al korewer fr he requirewed Fi
proche wil deorewse revenue by $2. Phe $0 shadow price Por ovceirctat © trophies
له من uot of ra arent (al 07 cost) eoreases td even by $11. 6۳
ای 4 مین coy orklioad kibor (oto pet) wil wt koprove tokd reve.
©
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 17:
3 2-1 عبت رم لسن
Gkhadow price sigue
0 مرو < لب موی wil duvays have موی
shadow prives.
Corcstrotts with < wil dvds hove woreysive shadow
prices.
9. Equality coostrots way have o posiive, a ceqaive, oro
zero shadow price.
ae
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 18:
سه و ای 105 2-171 5
Geusiivipy Podpsis ont Glack/Bxcess Ourubles
(Por ony equity comminddt, fhe product of the volves oP the coats
sholexcess varble oad the poosirad's shadow price cvet equ 267.
Dhis kophes thot oay ورن موه stack or excess vartble > D wal ave
zeny shadow price. Orolo), وله موه و موه زو price
swust be bray (have stuck or excess equals er). Por cocsirakts wth
xwwery stack or excess, rehiicuships ore detaled in ihe toble below
Dye oP Clune Iarewe lund Orrewe
اون Por rhe ۳ وا
s م = othe oP shaky
2 = ude oP excess bod
06
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 19:
له هه اه 0 20-17 0
وب ز()]
or basic بسا همم تا م) مور سا مشاه ون بط میا
ta the opiard schiios eqs (D), coniog cet be used usec ter prety نون
te LIDOO rips.
Por aa LP watts oo
sree Fler eters 00 ۰ 10+ ۱۵ + 9 +
۱۱۵۵۵ له نت
fess نانوی جه نو are GOBIECT TO
-> 0 + ۱۵+ 6۵ +0( ره ec bein اد
بويا وود ا ماو
he LADO LE | PO سین
to te 9) +۱8 + 9 29 +۱۵6 <= 060 سای مج(
vutput 0006۵ را عطا لجت یت
> 6 .0 + ۱+ + 0< © ( ات مج wrt tke
6) ۱+۱۵ +۱ > 0
0©
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 20:
LP OPMOOD 60۵00 6 و هه
6090001۳16۵ 0۳000۵0/۵۵ ۵ 8
0( ۵
60100 0) ۲۵۵۵۵۵0
0 .0۵۵00 9000007079
o.ooodkh 100000000080
Sboooow 0 000000
مه
ROD GLECK OR GORPLOG ۵86 ۵0۵
0 00000
0 000000
0 00000
0 000000
صفحه 21:
O@d COEPPICIEDT ۹۵۵
a. ۱ ۵ OI ور nee بارا RO ie
COG 08
06008
xa 0000۳00 90000000
9.000000
xe 0000 9000000
000000
xo 90000۳00 9.000000
9809
xe 500000000 9000000
۹
RIGLTPLOOD GIDE ROOEES
ROO CORREDT او
@LLODCOLE
RUG 08
06006
e 000000 222220000
6000000000
9 19000000 00000۳00
۲ سح 60
Copyright (c) 2003 Brooks/Cole, a division of Thomson] ووومومووه
صفحه 22:
۲۳۱۸۵۶ ۵
004۵ © 9 x
BONE, 0 Oana كك Bd oe
اه وس و یی
e xe 0.000 ۰ O00 ۵
0900 ۰ 00
9 X98 0/060 ۰ ۰0۵۵0 0۵۵0 ۵
8
€ GK F DOOD ۵۵۵۵ 0۵۵ 0
000
5 x 1۵۵8۵ DOOD 0.0۵۵۵ 6
0.06
ROO CKD )ارا 6: ۵9
0 990 0000 0
20۵000
e 0960 0.000 0
000
9 0969 0000 9
8 سس
Fe eer Copyright (c) 2003 Brooks/Cole, a division of Thomson]
صفحه 23:
اه مه له 0 20-1 7
by لح شاوی اون چا یحو وه ما تللن
ure: هجو < ۱۱۵۵۵
4 19۲ ۹۵۵60۵ 10۵ OWICW MLE C€EIG 16 OOCLOOGEDO
thew ar coastal wil have a DB or BO. Phir wets that Por ot
با منهج یا DDL PRICE can tel ur abou he ew رت
و سوه و و وی بر ia the rhe, but at bots.
©. ماو و و۳ vartble i becowe postive, «azabasir vortoble's vbjevive
و بو لو سا و جوا رو اوه مخ tras
000۵0000
9. Teoreasien 3 vartcble's objective Puccio oebPictet by core trax ts B41 or
deoreasteny by soore then ts (BO way feave the opal sokicg the sore.
oo
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 24:
5 2 - اب10 2 Oke Prices
ke ای MAX 4۱ + 612 + 78 + 04
SUBJECT TO 55
ور + ۵+ ۵ )2 ما و و + 4 - a ad rw
Prices ts tho hey oot 3) Xa >=" 400
be 4) 2X14+3x244x347x4 سير ter
Pec be vse to detercice 5) 3X144X2+5X346X4 << 5000
هس سا a ENP a
لاس با له بو LP OPTIMUM FOUND AT STEP 4
ی لاله مت ۳2 روم و OBJECTIVE FUNCTION VALUE
oP موی و 1( 6650.000
2 ص مص( ددا VARIABLE VALUE REDUCED
rich. cost
x1 0.000000 1.000000
x2 400.000000 0.000000
Okt te the worst Oia 13 ۰ 0 0.000000
be onan x4 400.000000 0.000000
cuckliicod unis oP raw Row SLACK OR SURPLUS DUAL PRICES.
2) ‘0.000000 3.000000
لس or bebo? 3) 6.000000 -2.000000
4) 0.000000 1.000000
5) 250.000000 0.000000
NO. ITERATIONS= 4
Copyright (c) 2003 Brooks/Cole, a division of Thomson
50
صفحه 25:
و
۰ MAX 401+ 62 + 744
he shed prive Por raw مس
wwotertd powstratdl (row @) 2( 4لا+ ويا 2+ 1ك - 950
X4>= 400 )3
> 4لا 7 + 43 + 2ع 3 + 261 (4
)5
shows oa extra it oF rows
وه ات اون
Diary could pay .50 عمج
wp te $0 Por os extra uri oP
OBJECTI
re cote urd be oy well ea
4600
3X1+4X24+5X34+6X4 <= 5000
IM FOUND AT STEP 4
UNCTION VALUE
0
OPP oe tis ww.
VARIABLE VALUE REDUCED
; 7 cost
ده را (mu 9(
0.000000 1.000000
‘000000 6.000000,
محم اعم 100000 0000۵
that ca extra ها اه سح will 400.000000 0.000000
wt norrase revenue. Gv, ROW DUAL PRICES
3 2) 3.000000,
۳ عا 9 3) -2:000000
سوت موه سوریو رم 2 0 9
5) 250.0000 0.000000
oP اه
NO.ITERATIONS= 4
6
8
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 26:
11 8. — Oat لا له لمع سل وا عم وبا
Qurredt Basis Is De booger Optical?
41a Gevion 8.6 shebw prices were weed ip detente the caw opted ude
the rhe oP a postnatal wer choaged but reczotaed wait the range Where the
Dunne buses rewake موه و هب بط پم اون ty volves where
مه تا مه بط racer opera cant be addressed by 00اط) اس
POROOETRICG Petre, Phe Prone cat be used to detercoiae how the
shadow price of a سارت امن کج اوه oho.
Dhe wer of te LIDOO PORCOEMCG Pecture ty thstrated by varie he
exont oP raw woterid ia he Diao eeaope. Guppose we usm و و
how the opierd z-vokie oad shadow price cham oF the او تج ۴و ام
vanes bewera O ond (DOOD vite. Dik O raw crater, we thea obra
Fraow te ROOGE axed GEOSIMOTPY CBOCLY CAG revs kat show
Row & ber ot PLLOOBOLE IWMORECECE cf SOOO, ‘Phes treater ot
feet 9900 rite oF raw watertdl ane required to woke the problew Prasble.
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 27:
8. — Oke koppeas tz the Opttaral 2-Odhie P the Ourredt Basis Is De
05
] 6۳/9900 فلس | RANGES IN WHICH THE BASIS 1S UNCHANGED
OBJECTIVE FUNCTION VALUE OB) COEFFICIENT RANGES
PAIMESTABLEAU 8۳5 INCREASE
0.0086 — (BASIS) x1 202 x3 4 BLK 9581800600 0.000000
3 SLK # 0.000000 183.333328 0.000 5.400.000
6.000600 ART 0.000 0.000 1.0 0.0003 400.000000 55000000000
6.000 4.000 0.000000 137.500000 0.000 400.000
2.000800 x1 1.000 0.000 -1.000 0.000 - 39000000009 0
4.000 00 22000 1.000 950.000
0.000600 4 0.000 0.000 0.000 1.006 5000.000000 ‘ONFOWITY
00
eos 5 0.000
0.008 op}x9GAt (@}02903 Brooks/Cole, a division of Thomson
صفحه 28:
9۵ - 0 koppeve to the Opterral 2-Ockee the Ourrect Beasts Ir
111 De bower Opel?
Choreretery Row €'s rhs to SOOO, resvltay the LO, oad selevtay he REPORTS
20 20008 كم RLG MOOBL PRICE
O®d
۳ 10 ROO OL ®EPORE PIOOT OWL
9900.00 8.00000
SFOO.0O
xd 8 8
9600.00
GLa 6 6 9 S ۳990000 00000
9800.00
8 CM & 6 9660.000 0999000200
9900.00
re be te coord oF catkble ran wooterid. ۱۳9۹900, کی
Bw te Pare cove, Prow GOGO <r. < PPOO, te shabw prior
(OOGL) & $6, swrcher v $0 Prow PPPS <r, < POPO, ond Pay &
30.00 8.00000
9
9 Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 29:
— Oke koppecs to the Opticval 2-Ockue P the Ourreat Basis Is
ok
111 1ك
RHS Parametries for Row: 4
Righthand Side (<=)
Copyright (c) 2003 Brooks/Cole, a division of Thomson
يبلل :ابي |
‘Objective (MAX)
صفحه 30:
111 .P — Oke koppeve ما the Opterd 2-Ocke: P the Ournect Dost ‘I
Oo boxmger Opteral?
Cor oy LO, the qraph of the vpicodl objevive Puortiog value os
و و a rhe will be .مصاعصخا جوا مرجم و he
نصخ ۶ مره ع متسه اي ۲و رواد the د وه
shadow prive.
4 Por < poostronts ino worxivizeiod LO, the slope oP eu
the slopes oP successive له مرمع امه مهو
foe sexpveds wil ۰ص و
or و < powstrant, igo wordtvizeiod problew, the yrapk oP
جوا روصم و وی نوتم موه با
The slope of euck tae اجه توح لاب موجه the
slopes oP survessive sexes wil be actor easing
eo
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 31:
CP=dhakees ele Od Ode PR Osa Oae'G ا
Do boxer Optra?
(BPRent oF chore it Obecive Puccioa OoePRriccl oa Optra 2-uchie
Oxia oP المح عا wax z= Oxi + Oxo
vbecive و جه دادس مس
Pocntoa oP a vartable's 9 بل 400 5 ود * ود vowwirctcd)
objective Puacton coe Pica
تفت 00۵ paw be oreded, Onvetder th
(مسه لس 60۵ ک .ود را مرا با وی
shown the rh.
(squresirvios) — 0 2 ورد
objevive ovePPrteat oP a. Ourredly, cy = © oad we wae to deter > رت اسر
ci عدي how the opted vce depecdd
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 32:
9۵ - 0 koppeve to the Opterral 2-Ockee the Ourrect Beasts Ir
111 De bower Opel?
وه با مج سا تست بط Proc the Bropetiy problew, م6
و[
بط ما سا بح موه رو با ما مه و سا ارت
سرت بط Piri, Port O(PO,2O) t opal ۵ the slope oP نویه
رده تا و thre ctype oP tbe Bashy بو مه سا بط
hae i con + Oxo = by we hon the slope oP the toproPt hee i het 9[
تا ۲۰ .0ب
0. Port @ te opted F/O 2 “lor O Sm SO (lie he vapeur
vorwirict shoe).
Porat © is vpicod P -C ارم ک S$ -dor © Sm S @ (between the slopes
oP ke carpeury oad Prisha coamircd siopes).
رو Port C te opted P/O > 46 بات 46) 6 2 وه Prishtoy او
sbyr).
Dh piecewise اه با من موه هم PO.
oo
Copyright (c) 2003 Brooks/Cole, a division of Thomson
صفحه 33:
9S. — Oket koppeas tv the Optard 2-Odke P the Ourred Bass Ie
Optimal 2¥alue vs el
— evalue
Copyright (c) 2003 Brooks/Cole, a division of Thomson
LA Oo boxmger Opteral?
dcy):=|160if 0<cy <2 4950
120+ 2@1 if 2<c, <4
40+ 40c1 if e124 ae
doa ratio LAP, the stop oP
ان ای سا the optical zuko ۵
اه ی aa pbjevive موی
روت سا ان یلیم
و
uraph oP مت امن سط a a
میت ماه مه تاه موی( 5
لین wil be wakerrstay.
on Value
10
oo
Chapter 5
Sensitivity Analysis: An Applied Approach
to accompany
Introduction to Mathematical Programming: Operations Research, Volume 1
4th edition, by Wayne L. Winston and Munirpallam Venkataramanan
Presentation: H. Sarper
1
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
Sensitivity analysis is concerned with how changes in an LP’s parameters
affect the optimal solution.
Reconsider the Giapetto
problem from Chapter
3 shown to the right:
max z = 3x1 + 2x2
2 x1 + x2 ≤ 100 (finishing constraint)
x1 + x2 ≤ 80 (carpentry constraint)
x1
≤ 40 (demand constraint)
x1,x2 ≥ 0
(sign restriction)
Where:
x1 = number of soldiers produced each week
x2 = number of trains produced each week.
2
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
80
fi n i sh i n g co n st ra i n t
Sl o p e = -2
Fe a si b l e Re g i o n
A
d e ma n d co nst ra i n t
60
Iso p ro fi t l i ne z = 120
Sl o p e = -3/2
B
D
40
20
How would changes in the
problem’s objective function
coefficients or right-hand
side values change this
optimal solution?
100
The optimal solution for this
LP was z = 180, x1 =
20, x2 = 60 (point B in
the figure to the right) and it
has x1, x2, and s3 (the slack
variable for the demand
constraint.
X2
ca rp e n t ry co n st ra i nt
Sl o p e = -1
C
10
20
40
50
60
80 X1
3
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
Graphical analysis of the effect of a change in an objective function
value for the Giapetto LP shows:
By inspection, we can see that making the slope of the isoprofit line
more negative than the finishing constraint (slope = -2) will cause the
optimal point to switch from point B to point C.
Likewise, making the slope of the isoprofit line less negative than the
carpentry constraint (slope = -1) will cause the optimal point to switch
from point B to point A.
Clearly, the slope of the isoprofit line must be between -2 and -1 for
the current basis to remain optimal.
4
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
The values of the contribution to profit for soldiers for which the current optimal
basis (x1,x2,s3) will remain optimal can be determined as follows:
Let c1 be the contribution ($3 per soldier) to the profit. For what values of c1 does
the current basis remain optimal?
At present c1 = 3 and each
isoprofit line has the form:
Rearranging:
x2
Since -2 < slope < -1:
Solving for c1 yields:
3x1 + 2x2 = constant
3
1
x 1 constant
2
2
2
c1
2
c1
1
x 1 constant
2
2
1
2 c 1 4
Note: the profit will change in
this range of c1
5
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
Graphical Analysis of the Effect of a Change in RHS on the
LP’s Optimal Solution (using the Giapetto problem).
A graphical analysis can also be used to determine whether a change in
the rhs of a constraint will make the current basis no longer optimal. For
example, let b1 = number of available finishing hours.
The current optimal solution (point B) is where the carpentry and finishing
constraints are binding. If the value of b1 is changed, then as long as
where the carpentry and finishing constraints are binding, the optimal
solution will still occur where the carpentry and finishing constraints
intersect.
6
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
fi n i sh i n g co n st ra i n t , b 1 = 100
Iso p ro fi t l i n e z = 120
A
d e ma n d co n st ra i n t
60
fi n i sh i n g co n st ra i n t , b 1 = 80
B
D
40
ca rp e n t ry co n st ra i n t
Fe a si b le Re g i o n
20
The current basis remains
optimal for 80 ≤ b1 ≤ 120,
but the decision variable values
and z-value will change.
80
Therefore: 80 ≤ b1 ≤ 120
fi n i sh in g co n st ra i n t , b 1 = 120
100
In the Giapetto problem to the
right, we see that if b1 >
120, x1 will be greater than
40 and will violate the demand
constraint. Also, if b1 < 80,
x1 will be less than 0 and the
nonnegativity constraint for x1
will be violated.
X2
C
20
40
50
60
80 X1
7
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
Shadow Prices (using the Giapetto problem)
It is often important to determine how a change in a constraint’s rhs changes the
LP’s optimal z-value. We define:
The shadow price for the i th constraint of an LP is the amount by which the
optimal z-value is improved (increased in a max problem or decreased in a min
problem) if the rhs of the i th constraint is increased by one. This definition applies
only if the change in the rhs of constraint i leaves the current basis optimal.
For the finishing constraint, 100 + finishing hours are available (assuming the
current basis remains optimal). The LP’s optimal solution is then x1 = 20 + and
x2 = 60 – with z = 3x1 + 2x2 = 3(20 + ) + 2(60 - ) = 180 + .
Thus, as long as the current basis remains optimal, a one-unit increase in the number
of finishing hours will increase the optimal z-value by $1. So, the shadow price for
the first (finishing hours) constraint is $1.
8
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.1 – A Graphical Approach to Sensitivity Analysis
Importance of Sensitivity Analysis
Sensitivity analysis is important for several reasons:
• Values of LP parameters might change. If a parameter changes,
sensitivity analysis shows it is unnecessary to solve the problem again.
For example in the Giapetto problem, if the profit contribution of a soldier
changes to $3.50, sensitivity analysis shows the current solution remains
optimal.
• Uncertainty about LP parameters. In the Giapetto problem for example,
if the weekly demand for soldiers is at least 20, the optimal solution
remains 20 soldiers and 60 trains. Thus, even if demand for
soldiers is uncertain, the company can be fairly confident that it is still
optimal to produce 20 soldiers and 60 trains.
9
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
If an LP has more than two decision variables, the range of
values for a rhs (or objective function coefficient) for
which the basis remains optimal cannot be determined
graphically.
These ranges can be computed by hand but this is often
tedious, so they are usually determined by a packaged
computer program. LINDO will be used and the
interpretation of its sensitivity analysis discussed.
10
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Consider the following maximization problem. Winco sells four types
of products. The resources needed to produce one unit of each
are:
Product 1
Product 2
Product 3
Product 4
Available
Raw material
2
3
4
7
4600
Hours of labor
3
4
5
6
5000
Sales price
$4
$6
$7
$8
To meet customer demand, exactly 950 total units must be produced.
Customers demand that at least 400 units of product 4 be produced.
Formulate an LP to maximize profit.
Let xi = number of units of product i produced by Winco.
11
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
The Winco LP formulation:
max z = 4x1 + 6x2 +7x3 + 8x4
s.t.
x1 + x2 + x3 + x4 = 950
x4 ≥ 400
2x1 + 3x2 + 4x3 + 7x4 ≤ 4600
3x1 + 4x2 + 5x3 + 6x4 ≤ 5000
x1,x2,x3,x4 ≥ 0
12
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
LINDO output and
sensitivity analysis
example(s).
Reduced cost is
the amount the
objective function
coefficient for
variable i would
have to be increased
for there to be an
alternative optimal
solution.
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
LP OPTIMUM FOUND AT STEP
4
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
X1
X2
X3
X4
ROW
2)
3)
4)
5)
VALUE
REDUCED COST
0.000000
1.000000
400.000000
0.000000
150.000000
0.000000
400.000000
0.000000
SLACK OR SURPLUS
DUAL PRICES
0.000000
3.000000
0.000000
-2.000000
0.000000
1.000000
250.000000
0.000000
NO. ITERATIONS=
4
13
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
RANGES IN WHICH THE BASIS IS UNCHANGED:
LINDO sensitivity
analysis example(s).
Allowable range (w/o
changing basis) for the
x2 coefficient (c2) is:
5.50 c2
6.667
Allowable range (w/o
changing basis) for the
rhs (b1) of the first
constraint is:
850 b1 1000
OBJ COEFFICIENT RANGES
VARIABLE
ALLOWABLE
CURRENT
COEF
INCREASE
DECREASE
X1
INFINITY
4.000000
1.000000
X2
0.500000
6.000000
0.666667
X3
0.500000
7.000000
1.000000
X4
INFINITY
8.000000
2.000000
RIGHTHAND SIDE RANGES
ROW
CURRENT
ALLOWABLE
RHS
14
ALLOWABLE
ALLOWABLE
INCREASE
DECREASE
2
950.000000
50.000000
Copyright
(c) 2003 Brooks/Cole, a division of Thomson
100.000000
5.2 – The Computer and Sensitivity Analysis
Shadow prices
are shown in the
Dual Prices
section of
LINDO output.
Shadow prices are
the amount the
optimal z-value
improves if the rhs
of a constraint is
increased by one
unit (assuming no
change in basis).
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
LP OPTIMUM FOUND AT STEP
4
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
X1
X2
X3
X4
ROW
2)
3)
4)
5)
VALUE
REDUCED COST
0.000000
1.000000
400.000000
0.000000
150.000000
0.000000
400.000000
0.000000
SLACK OR SURPLUS
DUAL PRICES
0.000000
3.000000
0.000000
-2.000000
0.000000
1.000000
250.000000
0.000000
NO. ITERATIONS=
4
15
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Interpretation of shadow prices for the Winco LP
ROW
SLACK OR SURPLUS
2)
demand)
3)
4 demand)
0.000000
0.000000
DUAL PRICES
3.000000
(overall
-2.000000
(product
4)
0.000000
1.000000
(raw material
availability)
Assuming the allowable range of the rhs is not violated, shadow (Dual) prices show: $3
for
that each one-unit increase in total
demand will increase
netavailability)
sales by
5)constraint 1 implies
250.000000
0.000000
(labor
$3. The -$2 for constraint 2 implies that each unit increase in the requirement for
product 4 will decrease revenue by $2. The $1 shadow price for constraint 3 implies
an additional unit of raw material (at no cost) increases total revenue by $1. Finally,
constraint 4 implies any additional labor (at no cost) will not improve total revenue.
16
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Shadow price signs
1.
Constraints with symbols will always have nonpositive
shadow prices.
2.
Constraints with will always have nonnegative shadow
prices.
3.
Equality constraints may have a positive, a negative, or a
zero shadow price.
17
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Sensitivity Analysis and Slack/Excess Variables
For any inequality constraint, the product of the values of the constraint’s
slack/excess variable and the constraint’s shadow price must equal zero.
This implies that any constraint whose slack or excess variable > 0 will have
a zero shadow price. Similarly, any constraint with a nonzero shadow price
must be binding (have slack or excess equaling zero). For constraints with
nonzero slack or excess, relationships are detailed in the table below:
Type of
Constraint
Allowable Increase
for rhs
Allowable Decrease
for rhs
≤
∞
= value of slack
≥
= value of excess
∞
18
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Degeneracy and Sensitivity Analysis
When the optimal solution is degenerate (a bfs is degenerate if at least one basic
variable in the optimal solution equals 0), caution must be used when interpreting
the LINDO output.
For an LP with m
constraints, if the optimal
LINDO output indicates
less than m variables are
positive, then the optimal
solution is degenerate bfs.
Consider the LINDO LP
formulation shown to the
right and the LINDO output
on the next slide.
MAX
6 X1 + 4 X2 + 3 X3 + 2 X4
SUBJECT TO
2) 2 X1 + 3 X2 + X3 + 2 X4 <=
400
3) X1 + X2 + 2 X3 + X4 <= 150
4) 2 X1 + X2 + X3 + 0.5 X4 <=
200
5) 3 X1 + X2 + X4 <= 250
19
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Since the LP
has four
constraints and
in the optimal
solution only
two variables
are positive, the
optimal solution
is a degenerate
bfs.
2
0
LP OPTIMUM FOUND AT STEP
3
OBJECTIVE FUNCTION VALUE
1)
700.0000
VARIABLE
VALUE
REDUCED COST
X1
50.000000
0.000000
X2
100.000000
0.000000
X3
0.000000
0.000000
X4
0.000000
1.500000
ROW SLACK OR SURPLUS DUAL PRICES
2)
0.000000
0.500000
3)
0.000000
1.250000
4)
0.000000
0.000000
5)
0.000000
1.250000
Copyright (c) 2003 Brooks/Cole, a division of Thomson
OBJ COEFFICIENT RANGES
CURRENT
ALLOWABLE
VARIABLE
5.2 – The Computer and Sensitivity Analysis
ALLOWABLE
COEF
INCREASE
DECREASE
X1
6.000000
3.000000
3.000000
X2
4.000000
5.000000
1.000000
X3
3.000000
3.000000
2.142857
X4
2.000000
1.500000
INFINITY
ROW
ALLOWABLE
RIGHTHAND SIDE RANGES
CURRENT
ALLOWABLE
RHS
21
DECREASE
2
200.000000
3
0.000000
4
0.000000
400.000000
150.000000
200.000000
INCREASE
0.000000
0.000000
INFINITY
Copyright (c) 2003 Brooks/Cole, a division of Thomson
THE TABLEAU
ROW (BASIS)
X1
X2
X3
X4
5.2
SLK
2 – The Computer and Sensitivity Analysis
1 ART
0.000 0.000 0.000 1.500
LINDO TABLEAU command indicates the optimal basis is RV = { x1,x2,x3,s4}.
0.500
2
X2
0.000 1.000 0.000
0.500 0.500
3
X3
0.000 0.000 1.000 0.167
-0.167
4 SLK 4
0.000 0.000 0.000 -0.500
0.000
5
X1
1.000 0.000 0.000 0.167
-0.167
2
2
ROW
1
700.000
2
100.000
3
0.000
4
SLK 3
1.250
SLK 4
SLK 5
0.000
1.250
-0.250
0.000
-0.250
0.583
0.000
-0.083
-0.500
1.000
-0.500
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.2 – The Computer and Sensitivity Analysis
Oddities that may occur when the optimal solution found by
LINDO is degenerate are:
1.
2.
3.
2
3
In the RANGE IN WHICH THE BASIS IS UNCHANGED
at least one constraint will have a 0 AI or AD. This means that for at
least one constraint the DUAL PRICE can tell us about the new z-value
for either an increase or decrease in the rhs, but not both.
For a nonbasic variable to become positive, a nonbasic variable’s objective
function coefficient may have to be improved by more than its
RECDUCED COST.
Increasing a variable’s objective function coefficient by more than its AI or
decreasing it by more than its AD may leave the optimal solution the same.
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.3 – Managerial Use of Shadow Prices
The managerial
significance of shadow
prices is that they can
often be used to determine
the maximum amount a
manger should be willing
to pay for an additional unit
of a resource.
Reconsider the Winco to
the right.
What is the most Winco
should be willing to pay for
additional units of raw
material or labor?
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
raw
material
labor
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
COST
X1
X2
X3
X4
VALUE
0.000000
1.000000
400.000000
0.000000
150.000000
0.000000
400.000000
0.000000
ROW
2)
3)
4)
5)
SLACK OR SURPLUS
DUAL PRICES
0.000000
3.000000
0.000000
-2.000000
0.000000
1.000000
250.000000
0.000000
NO. ITERATIONS=
2
4
4
REDUCED
4
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.3 – Managerial Use of Shadow Prices
The shadow price for raw
material constraint (row 4)
shows an extra unit of raw
material would increase
revenue $1. Winco could pay
up to $1 for an extra unit of
raw material and be as well
off as it is now.
Labor constraint’s (row 5)
shadow price is 0 meaning
that an extra hour of labor will
not increase revenue. So,
Winco should not be willing to
pay anything for an extra hour
of labor.
MAX
4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
END
LP OPTIMUM FOUND AT STEP
OBJECTIVE FUNCTION VALUE
1)
6650.000
VARIABLE
COST
X1
X2
X3
X4
VALUE
0.000000
1.000000
400.000000
0.000000
150.000000
0.000000
400.000000
0.000000
ROW
2)
3)
4)
5)
SLACK OR SURPLUS
DUAL PRICES
0.000000
3.000000
0.000000
-2.000000
0.000000
1.000000
250.000000
0.000000
NO. ITERATIONS=
2
5
4
REDUCED
4
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the
Current Basis Is No Longer Optimal?
In Section 5.2 shadow prices were used to determine the new optimal z-value if
the rhs of a constraint was changed but remained within the range where the
current basis remains optimal. Changing the rhs of a constraint to values where
the current basis is no longer optimal can be addressed by the LINDO
PARAMETRICS feature. This feature can be used to determine how the
shadow price of a constraint and optimal z-value change.
The use of the LINDO PARAMETICS feature is illustrated by varying the
amount of raw material in the Winco example. Suppose we want to determine
how the optimal z-value and shadow price change as the amount of raw material
varies between 0 and 10,000 units. With 0 raw material, we then obtain
from the RANGE and SENSITIVTY ANALYSIS results that show
Row 4 has an ALLOWABLE INCREASE of -3900. This indicates at
least 3900 units of raw material are required to make the problem feasible.
2
6
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is No
Longer Optimal?
Raw Material rhs = 3900 optimal solution
OBJECTIVE FUNCTION VALUE
1)
VARIABLE
ALLOWABLE
5400.000
VARIABLE
COST
X1
0.000000
X2
0.000000
X3
1.000000
X4
0.000000
VALUE
550.000000
0.000000
0.000000
400.000000
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
CURRENT
ALLOWABLE
COEF
REDUCED
DECREASE
X1
INFINITY
X2
0.500000
X3
INFINITY
X4
INFINITY
INCREASE
4.000000
1.000000
6.000000
INFINITY
7.000000
1.000000
8.000000
6.000000
RIGHTHAND SIDE RANGES
CURRENT
ALLOWABLE
RHS
INCREASE
ROW
ALLOWABLE
ROW SLACK OR SURPLUS
DUAL
THE TABLEAU
PRICES
DECREASE
2)
0.000000
ROW
(BASIS)
X1
X2
X3
X4
2SLK
950.000000
0.000000
SLK 5
0.000000
3
SLK 3)
4
183.333328
0.000
5400.000
0.000000
1
ART
0.000
0.000
1.000
0.000
3
400.000000
0.000000
0.000
550.000
6.000000
6.000
137.500000
0.000
400.000
4)2.000 0.000000
2
X1
1.000
0.000
-1.000
0.000
4
3900.000000
550.000000
0.000
0.000
2.000000
4.000
-1.000
0.000000
1.000
950.000
5)
950.000000
3
X4
0.000
0.000
0.000
1.0005 - 5000.000000
INFINITY
0.000
0.000
0.000000
1.000
0.000
950.000000
4
X2
0.000
1.000
2.000
0.000
2
5.000
1.000
7 5
SLK 5
0.000
0.000
0.000 (c)
0.000
Copyright
2003 Brooks/Cole,
a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is
No Longer Optimal?
Changing Row 4’s rhs to 3900, resolving the LP, and selecting the REPORTS
PARAMTERICS
feature.
In this feature weREPORT
choose Row
4, setting
RIGHTHANDSIDE
PARAMETRICS
FOR
ROW:the
4Value to
10000, and select text output. We then obtain the output below:
VAR
OBJ
OUT
VAR
IN
PIVOT
ROW
RHS
VAL
DUAL PRICE
BEFORE PIVOT
3900.00
VAL
2.00000
5400.00
X1
X3
2
4450.00
2.00000
6500.00
SLK 5 SLK 3
5
4850.00
1.00000
6900.00
X3
SLK 4
2
5250.00
-0.333067E-15
6900.00
Let rm be the amount of available raw material. 10000.0
If r m < 3900, we
know the LP is
-0.555112E-16
infeasible.
From the figure above, from 3899 < r m < 4450, the shadow price
6900.00
(DUAL) is $2, switches to $1 from 4449 < rm < 4849, and finally to $0 at 4850.
2
8
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is
No Longer Optimal?
LINDO Parametric Feature
Graphical Output (z-value vs. Raw
Material rhs from 3900 to
10000)
2
9
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is
No Longer Optimal?
For any LP, the graph of the optimal objective function value as
a function a rhs will be a piecewise linear function. The
slope of each straight line segment is just the constraint’s
shadow price.
3
0
1.
For < constraints in a maximization LP, the slope of each
segment must be nonnegative and the slopes of successive
line segments will be nonincreasing.
2.
For a > constraint, in a maximization problem, the graph of
the optimal function will again be piecewise linear function.
The slope of each line segment will be nonpositive and the
slopes of successive segments will be nonincreasing
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is
No Longer Optimal?
Effect of change in Objective Function Coefficient on Optimal z-value
A graph of the optimal
objective function value as a
function of a variable’s
objective function coefficient
can be created. Consider
again the Giapetto LP
shown to the right.
max z = 3x1 + 2x2
2 x1 + x2 ≤ 100 (finishing constraint)
x1 + x2 ≤ 80 (carpentry constraint)
x1
≤ 40 (demand constraint)
x1,x2 ≥ 0
(sign restriction)
Let c1 = objective coefficient of x1. Currently, c1 = 3 and we want to determine
how the optimal z-value depend upon c1..
31
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is
No Longer Optimal?
Recall from the Giapetto problem, if the isoprofit line is flatter than the carpentry
constraint, Point A(0,80) is optimal. Point B(20,60) is optimal if the
isoprofit line is steeper than the carpentry constraint but flatter than the finishing
constraint. Finally, Point C(40,20) is optimal if the slope of the isoprofit
line is steeper than the slope of the finishing constraint. Since a typical
isoprofit line is c1x1 + 2x2 = k, we know the slope of the isoprofit line is just
-c1/2. This implies:
1.
2.
3.
Point A is optimal if -c1/2 ≥ -1 or 0 ≤ c1 ≤ 2 ( -1 is the carpentry
constraint slope).
Point B is optimal if -2 ≤ -c1/2 ≤ -1 or 2 ≤ c1 ≤ 4 (between the slopes
of the carpentry and finishing constraint slopes).
Point C is optimal if -c1/2 ≤ -2 or c1 ≥ 4 ( -2 is the finishing constraint
slope).
This piecewise function is shown on the next page.
3
2
Copyright (c) 2003 Brooks/Cole, a division of Thomson
5.4 – What happens to the Optimal z-Value if the Current Basis Is
No Longer Optimal?
z c 1 160 if 0 c 1 2
Optimal z-Value vs c1
440500
120 20c 1 if 2 c 1 4
40 40c
1 if c 1 4
In a maximization LP, the slope of
the graph of the optimal z-value as a
function of an objective function
coefficient will be nondecreasing.
In a minimization LP, the slope of the
graph of the optimal z-value as a
function of an objective function
coefficient will be nonincreasing.
Optimal z-Value
400
300
z c1
200
100
0
0
2
0
4
6
8
c1
C1
z-value
3
3
Copyright (c) 2003 Brooks/Cole, a division of Thomson
10
10