Gazdasági Ismeretek | Operációkutatás » Érzékenység vizsgálat

Érzékenység vizsgálat Hallgatói segédlet ! 1 Érzékenység vizsgálat 1. Elméleti alapok: Egy már megoldott LP feladatban a megoldás ismeretében az induló táblában csoportosítsuk a sorokat (ui) és az oszlopokat (xi) úgy, hogy vegyük előre azokat amelyek részt vettek a generálásban. (Ez megvalósítható, mivel az induló táblában a sor és oszlop csere megengedett) Tegyük ezt még azzal a körül tekintéssel, hogy a generáló elemek rendre a főátló elemei legyenek. Ezáltal az induló táblánkat tulajdonképpen partícionáltuk: a báziscserében részt vevő, ill. részt nem vevő részekre Invariáns jelöléssel az alábbi alakot kapjuk: I. u1 u2 -z x 1T A11 A21 c1T x 2T A12 A22 c2T b1 b2 0 a régebbi xT A cT I. u -z helyett. b 0 Ahol: x1 , u1 a báziscserében részt vett változók, u1T= ( u1, u2, .ur ) x1T= ( x1, x2, .xr ) x2 , u2 pedig a báziscserében részt nem vett változók: x2T= ( xr+1, xr+2, .xn ) u2T= ( ur+1, ur+2, .um )

Valamint: xT= [ x1T, x2T ] u= u 1 u2 cT= [ c1T, c2T ] A11 A12 A= A21 A22 Ekkor - a levezetést mellőzve – az optimális tábla invariáns alakja: sbc c1 0 sfTb = [ b1T 0T ] , u1T A11-1 -A21 A11-1 -c1T A11-1 opt. x1 u2 -z sacT= [ 0T x 2T A11-1 A12 A22 -A21 A11-1A12 c2T -c1T A11-1 A12 , c2T b -1 A11 b1 b2 -A21 A11-1 b1 -c1T A11-1 b1 sjb 0 b2 ] Melyet már kiegészítettünk a számunkra szükséges s segédvektorokkal. sfb = b1 0 sjb = 0 b2 sac = 0 c2 sbc = c1 0 Mj. Az optimális táblában az könnyen belátható, hogy az A11 mátrix helyére az inverze kerül, mert a főátló végiggenerálásával éppen a mátrix inverzét kapjuk. 2 A fenti tábla - hasonlóan a "program módosítás" név alatt megismert módszerhez - szintén megvizsgálható azon szempontból, hogy az optimális tábla értékei ( b opt, c opt, z opt ) a tábla mely ilyetén felosztott részeitől függnek. Ezen vizsgálat elvégzését az olvasóra bízzuk! 1. Állítás

A opt s fb = b opt - s jb (1) Bizonyítás: ( 1 ) alakja ha s segédvektorok definícióit felhasználjuk: [A opt. ] b1 0 = bopt - 0 b2 Továbbá A opt. és bopt -nak az optimális tábla invariáns alakjában szereplő képleteit helyettesítve: A11-1 -A21 A11-1 A11-1 A12 A22 -A11-1 A12 b1 o A11-1 b1 b2 - A21 A11-1 b1 = o b2 a műveletek ( szorzás, kivonás ) elvégzéséből A11-1 b1 -A21 A11-1 b1 = A11-1 b1 b2 - A21 A11-1 b1 - b2 láthatóan azonosságot kapunk. Tehát az ( 1 ) állítás – mivel azonosságra vezethető vissza – bizonyított! 2. Állítás s bcT A opt = s ac T - c opt T (2) Bizonyítás: Szintén a definíciót és az optimális tábla elemeit helyettesítve: [ c1T, 0T ] A opt = [ 0T, c2T] - coptT [ c1T, 0T ] ⋅ A11-1 A11-1 A12 -A21 A11-1 A22 -A11-1 A12 = [ 0T, c2T] - [ c1T A11-1 , c2T -c1T A11-1 A12 ] A szorzást elvégezve ez esetben is azonosságra jutunk! 3 Az (1) (2) állítás igaz marad akkor is, ha nem rendezzük a sorokat,

oszlopokat. Ezt egy példán mutatjuk be. va a következőképpen egészítjük ki az optimális táblát: ( Induló tábla:) 1. u1 u2 u3 u4 -z x1 x2 1 1 6 3 -2 0 1 -5 3 7 ( Optimális tábla: ) tfb = [ 0 , 12 , 8 ] x3 2 0 4 0 9 b 8 12 28 15 0 tbc 9 7 0 0 opt. x3 x2 u3 u4 -z x1 -1/2 2 0 11 -13/2 u2 u1 -1/6 1/2 1/3 0 2/3 -2 5/3 0 -5/6 -9/2 b 2 4 20 35 -46 tjb 0 0 28 15 tacT = [ 3, 0, 0 ] Az így definiált t fb , t jb , t ac t bc vektorok csak a koordináták sorrendjében különböznek a fenn definiált s vektoroktól. Ekkor az (1) (2) (3) alábbi összefüggések (1* ) (2 ) (3 ) alakot öltik: A opt t fb = b opt - t jb (1*) t bcT A opt = t ac T - c opt T ( 2* ) z opt.= c opt T· t fb ( 3* ) A t vektorok első indexei az induló táblában való elhelyezkedésüket jelzi, a második pedig azt, hogy b vagy c vektorból származtatjuk. Ennek megfelelően: t fb dimenziója x dimenziójával egyezik meg, s elemei ott különböznek 0-tól ahol a felső sorban u van,

értéke pedig az adott u-nál az induló táblában szereplő b érték. t jb u-val azonos dimenziójú, elemei ott 0-tól különbözőek, amely sorban u áll, értéke pedig az induló táblában az adott u sorában álló b érték. t ac c-vel azonos dimenziójú, elemei ott 0-tól különbözőek ahol a tábla alsó sorában x áll, értéke az induló táblában az adott x oszlopában a célfüggvény értékével egyezik meg. t bc dimenziója u dimenziójával egyezik, elemei szintén ott különböznek 0-tól ahol optimális táblában x áll, értéke pedig az induló táblában az adott x oszlopában a célfüggvény értékévek egyezik meg. Az ilyetén levezetett (1* ) (2 ) (3 ) képlet már jól hasznosítható az LP feladat ellenőrzésére, variánsszámításra, és érzékenység vizsgálat elvégzésére is. 4 2., Ellen rzés: Az ellenőrzés egyszerűen az (1* ) (2 ) (3 ) képletekbe –az eredeti értékek - behelyettesítésével végezhető el: b opt = A opt

t fb + t jb bopt = -1/2 2 0 11 -1/6 1/3 2/3 5/3 1/2 0 -2 0 bopt = -2 + 4 = 4+0 8–16+28 20 + 15 (1*) 0 12 8 + = -1/2 ⋅ 0 0 + 0 + 0 + 0 0 28 15 1/6 ⋅ 12 1/3 ⋅ 12 2/3 ⋅ 12 5/3 ⋅ 12 + 1/2⋅ 8 + 0 + 0 0 + -2 ⋅ 8 28 + 0 15 2 4 20 35 Eredményünk láthatóan egyezik az optimális táblabeli boptimális értékkel. A optimális táblabeli célfüggvény együtthatók ellenőrzése a ( 2 ) képlet segítségével történik: c opt T = 3 , 0 , 0 - 9,7,0,0 -1/2 2 0 11 -1/6 1/3 2/3 5/3 1/2 0 -2 0 = 3 – ( -1/2 ⋅ 9 + 2 ⋅ 7 ) , 0 – ( -1/6 ⋅ 9 + 1/3 ⋅ 7 ) , 0 – ( ½ ⋅ 9 ) = 6/2 + 9/2 – 28/2 , 9/6 – 14/6 , - 4.5 = - 13 / 2 , -5 / 6 , - 45 c optimális értéke szintén egyezik. zopt. = c opt T· t fb ( 3* ) - z = -13/2 -5/6 -9/2 0 = - 5/6 ⋅12 – 9/2 ⋅ 8 = -10 - 36 = - 46 12 8 Szintén helyes értéket kaptunk. 3. Variáns számítás: A variáns számításkor ugyanezen képletek használhatók, csak c és b eredeti értékei helyett c uj ill.

b uj értékeivel kell számolni. 5 3.a) Kapacitás vektor változtatás: Legyen b uj = 6 12 30 20 t fbuj = 0 12 6 ekkor : t jbuj = 0 0 30 20 = 0 0 0 0 + + + b opt uj = A opt t fbuj + t jbuj bopt = -1/2 2 0 11 -1/6 1/3 2/3 5/3 1/2 0 -2 0 bopt = -2 + 3 = 4+0 8–12+30 20 + 20 1 4 26 40 zopt. = c opt T· t fbuj = 0 12 6 0 0 30 20 + 1/6 ⋅ 12 1/3 ⋅ 12 2/3 ⋅ 12 5/3 ⋅ 12 + 1/2⋅ 6 + 0 + 0 0 + -2 ⋅ 6 30 + 0 20 Megkaptuk az optimális táblabeli b értéket, melynek minden eleme pozitív, azaz leolvasható a megoldás a táblából: xT = [ 0 , 4 , 1 ] [ 13/2 , 5/6 , 9/2 ] = 5 /6 ⋅12 + 9/2 ⋅ 6 = 10 + 27 = 37 0 12 6 Amennyiben negatív b értéket is kaptunk volna, úgy azt mondhatjuk, hogy az eredeti termék szerkezet ezen megváltozott kapacitás korlátok mellett nem maradt optimális! Ez azt jelenti, hogy nem szűkíthetők, változtathatók a kapacitás korlátok ilyen mértékben az eredeti termékszerkezet megtartása mellett. Ekkor vagy más

módszerrel folytatni kell a feladatot – ez nem tárgya jelen kiadványunknak, vagy sajnos mégis előlről kell kezdeni a megoldást. 3.b) Célfüggvény együttható változtatás: Most a célfüggvény értékeit változtatjuk – a kapacitás vektor értékeinek változatlanul hagyása mellett: c uj = [ 5 , 9 , 8 ] Ekkor t ac T uj = [ 5 , 0 , 0 ] t bcT uj = [ 8 , 9 , 0 , 0 ] c opt T uj = t ac T uj - t bcT uj A opt c opt T = 5 , 0 , 0 - 8,9,0,0 -1/2 2 0 11 -1/6 1/3 2/3 5/3 1/2 0 -2 0 6 = 5 – ( -1/2 ⋅ 8 + 2 ⋅ 9 ) , 0 – ( -1/6 ⋅ 8 + 1/3 ⋅ 9 ) , 0 – ( ½ ⋅ 8 ) = ( 5 + 4 – 18 ) , ( 8/6 – 18/6 ) , - 4 = - 9 , -5 / 3 , - 4 Megkaptuk az új optimális táblabeli célfüggvény együtthatókat, mivel ezek mind negatívak ezért az eredeti megoldás továbbra is optimális marad. Amennyiben lenne közöttük pozitív elem, úgy tovább kellene folytatni a feladatot, - generáló elemet választani a pozitív elem oszlopában - amíg az új optimális

táblához nem jutunk. 3.c) A kapacitás vektor és a célfüggvény együttható együttes változtatása: Azért, hogy az előbbi esetek számításait fel tudjuk használni, legyen adott b uj és c uj is az előbb már megadott értékű változása. Ekkor az optimális tábla az előbbiekben kiszámoltak alapján: tfb t bc 8 9 0 0 [ 0 , 12 , 6 ] x1 u2 -1/2 -1/6 2 1/3 0 2/3 11 5/3 -9 -10/6 x3 x2 u3 u4 -z tac [ 5 , 0 , uy ½ 0 -2 0 -4 B 1 4 26 40 ? t jb 0 0 30 20 0] A változás az előbbiekhez képest csak annyi, hogy mind a b-ben mind c-ben az új értékekből kiszámított elemek állnak a táblában, illetve z optimális számításában mind c opt , tfb értékek újak: zopt. = c opt T· t fbuj = [ 9 , 10/6 , 4 ] 0 12 6 = 10 /6 ⋅12 + 4 ⋅ 6 = 20 + 24 = 44 4. Érzékenység vizsgálat: Az ellenőrzés módszere lehetővé teszi a megoldás elemzését is, azaz, hogy: - a., hogyan módosíthatjuk a célfüggvény együtthatóit úgy, hogy az optimális

megoldás ne változzon, - b., meddig változtathatjuk a kapacitás vektor komponenseit, hogy az optimális megoldás bázisa ne változzék. Mindkét esetben egy vizsgálatban egyetlen b i vagy ci paraméterre keressük a határokat, miközben az összes többi paraméter az eredeti változatlan értéken marad. Az ilyen jellegű vizsgálatokat nevezzük érzékenység vizsgálatnak. 7 4.a ) A kapacitás vektor komponenseinek érzékenység vizsgálata: Tehát a kapacitásvektor elemeinek változtathatósága úgy értendő, hogy egy bi elem milyen határok között változhat, az összes többi érték ( bj ; j ≠ i , c , A ) változatlanul, eredeti értéken történő hagyása mellett. Ehhez az eredeti módszerünkben bi-t paraméternek tekintjük, s azt vizsgáljuk, hogy az a*) képletből b opt.-t kifejezve meddig marad ezen vektor minden eleme pozitív ( Ez jelenti azt, hogy a tábla optimális marad. ) b opt = A opt t fb + t jb > 0 (1*) A módszer elvégzésékor

célszerű az ( 1* ) - ból adódó egyenletet bi-ben paraméteresen felírni, s csak aztán helyettesíteni bj j ≠ i eredeti értékeit: tfb t bc 9 7 0 0 (1) -1/6 1/3 2/3 5/3 1/2 0 -2 0 x3 x2 u3 u4 -z 0 b2 b1 + 1/3 b2 2/3 b2 – 2 b1 + b3 > 0 (4) 5/3 b2 + b4 > 0 b= b2 , b1 ] 3 , 0 , 0 0 b3 b4 b 2 4 20 35 0 0] > 0 > 0 (3) 4.a1) eset: , > 0 -1/6 b2 + 1/2 b1 (2) 0 x1 u2 u1 -1/2 -1/6 ½ 2 1/3 0 0 2/3 -2 11 5/3 0 -13/2 -5/6 -9/2 tac [ -1/2 2 0 11 [ b1 12 28 15 (1) -1/6 12 + 1/2 b1 > 0 (2) - (3) 3/2 12 - 2b1 + 28 > 0 +2 < 1/2 b1 4 < b1 46 > 2b1 b1 < 23 8 t jb 0 0 b3 b4 (4) 4 < b1 < 23 4.a2) eset: b = 8 b2 28 15 (1) -1/6 b2 + 1/2 8 > 0 4 > 1/6 b2 (2) 1/3 b2 > 0 0 < b2 (3) 2/3 b2 - 2 ⋅ 8 + 28 > 0 2/3 b2 > - 12 -18 < b2 (4) 5/3 b2 + 15 > 0 b2 > -3/5 ⋅ 15 - 9 < b2 0 < b2 < 24 4.a3) eset: b2 = 8 12 b3 15 (1) - (2) - (3) 2/3 ⋅ 12 - 2 ⋅ 8 +

b3 > 0 (4) - b3 > 8 8 < b3 4.a4) eset: b = (1) 8 12 28 b4 9 b2 < 24 0 < b2 (2) - (3) - (4) 5/3 ⋅12 + b4 > 0 - 20 < b4 de mivel b4 kapacitás ezért 0 < b4 Fontos még kiszámítani a célfüggvény értékeit a paraméterek minimális és maximális értékeinél 4.a1) esetre: z opt. b1min = [ 13/2 , 5/6 , 9/2 ] ⋅ z opt. b1max = [13/2 , 5/6 , 9/2 ] 0 12 4 = 10 + 18 = 28 0 12 23 = 10 + 207/2 = 10+103.5 = 1135 Hasonlóan a többi esetre is. Eredményeinket táblázatba foglalhatjuk. b1 b2 b3 b4 Min 4 0 8 0 Max 23 24 ∞ ∞ z min 28 36 46 46 z max 113.5 56 46 46 4.b) A célfüggvény együtthatók érzékenység vizsgálata: A célfüggvény értékeinek érzékenység vizsgálatához az eredeti táblabeli célfüggvény együtthatókat tekintjük paraméternek, a kapacitásokat pedig az eredeti változatlan értéken vesszük: tfbT [ 0 , 12 , 8 ] t bc c3 c2 0 0 x3 x2 u3 u4 -z x1 u2 uy -1/2 -1/6 ½ 2 1/3 0 0 2/3 -2 11 5/3 0

-13/2 -5/6 -9/2 tacT [ c1 , 10 0 , 0] b 2 4 20 35 -46 t jb 0 0 28 15 A vizsgálat elvégzéséhez a már használt ( 2* ) képlet alábbi alakját tekintjük: c opt T = t ac T - t bcT A opt c opt T = c1 , 0 , 0 < 0 - c3, c2, 0, 0 ⋅ -1/2 2 0 11 ( 2* ) -1/6 1/3 2/3 5/3 (5) c1 – ( -1/2 ⋅ c3 + 2 c2 ) < 0 (6) 0 – ( - 1/6 ⋅ c3 + 1/3 c2 ) < 0 (7) 0 < 0 1/2 0 -2 0 4.b5) eset: (5) (6) - ( 1/2 c3 ) < 0 c = [ c1 , 7 , 9 ] c1 – ( - 1/2 ⋅ 9 + 2 ⋅ 7 ) < 0 c1 < - 4.5 + 14 c1 < 9.5 4.b6) eset: (5) (6) (7) c = [ 3 , c2 , 9 ] 3 – ( 1/2 ⋅ 9 + 2 ⋅ c2 ) < 0 - ( - 1/6 ⋅ 9 + 1/3 c2 ) < 0 - - 1.5 < 2 ⋅ c2 9/6 < 1/3 ⋅ c2 3.75 < c2 4.5 < c2 - 11 < 1/2 ⋅ c3 1/6 ⋅ c3 < 7/3 0 < 1/2 ⋅ c3 22 ≥ c3 c3 < 14 0 < c3 4.5 < c2 4.b7) eset: (5) (6) (7) c = [ 3 , 7 , c3 ] 3 – ( -1/2 ⋅ c3 + 2 ⋅ 7 ) < 0 - ( - 1/6 ⋅ c3 + 1/3 ⋅ 7 ) < 0 - ( 1/2 ⋅ c3 ) < 0 0 < c3 < 14

11 A célfüggvény értékeinek a határokon történő kiszámításához szükségünk van c opt kiszámítására is. c Tc1min = [ - ∞ , 0 , 0 ] - [ 9 , 7 , 0 , 0 ] -1/2 2 0 11 -1/6 1/3 2/3 5/3 1/2 0 -2 0 = [-∞ – ( -1/2 ⋅ 9 + 2 ⋅ 7 ) , 0 – ( -1/6 ⋅ 9 + 1/3 ⋅ 7 ) , 0 – ( ½ ⋅ 9 ) ] = [ - ∞ , - 5/6 , - 9/2 ] zopt. = c opt Tuj · t fbuj = [∞ , 5/6 , 9/2 ] 0 = 5 /6 ⋅12 + 9/2 ⋅ 6 = 10 + 36 = 46 12 8 És így tovább, a többi zopt. értékekre Eredményeinket ismét táblázatba foglalva: c1 c2 c3 Min -∞ 4.5 0 Max 9.5 ∞ 14 z min 46 36 28 12 z max 46 ∞ 56