Gazdasági Ismeretek | Operációkutatás » Operációkutatás tételek, 2003

Lineáris programozású feladat és megoldása Definíció: Az LP feladat olyan feltételes szélsőérték feladat, amelyben adott függvény minimumát vagy maximumát keressük az értelmezési tartomány ismert lineáris korlátokkal megadott részében (azaz L-en). L zárt, így a lineáris korlátokat csak ≥, ≤, = -vel adhatjuk meg. Definíció: Az LP feladat optimális megoldásán azt a lehetséges megoldását értjük, amely esetében a célfüggvény értéke minimális (/maximális). Definíció: Adott LP feladat lehetséges (fizibilis) megoldásán olyan szám n-est értünk, amely kielégíti a feladat feltételrendszerét. 2 x1 + 3 x2 + x3 ≤ 5 4 x1 + x2 + 2 x3 ≤ 11 3x1 + 4 x2 + 2 x3 ≤ 8 xi ≥ 0 (i = 1,  ,3) 5 − 5 x1 − 4 x2 − 3 x3 = z min x4 x5 x6 x1 x2 x3 x4 x5 x6 x7 2* 3 1 1 0 0 5 4 1 2 0 1 0 11 3 4 2 0 0 1 3 -5 -4 -3 0 0 0 z-5 Lehetséges kanonikus alakú feladat és bázismegoldása. Optimumkritérium

Lehetséges kanonikus alakú feladat Egy LP feladat lehetséges kanonikus alakú feladat, ha sor- és oszlopcserékkel valamint a változók átjelölésével az alábbi formában írható fel: x1 x2 xm xj ≥ 0 (1 ≤ α + a1m+1 xm+1 + a2 m+1 xm+1 + . + a1m+n xm+n + . + a2 m+n xm+n = b1 = b2 . . . + . + amm+n xm+n = bm + amm+1 xm+1 j ≤ m + n ); + cm+1 xm+1 (bi ≥ 0; (1 ≤ i ≤ m )) = Z ( x ) min + . + cm+n xm+n x1 , x2 ,. xm változók az (aktuális) bázisváltozók xm+1 ,., xm+n változók az (aktuális) döntési változók Lehetséges kanonikus alakú feladat bázismegoldása A lehetséges kanonikus alakú feladat aktuális bázismegoldásának az x1 = b1; x2 = b2 ; xm = bm ; x m +1 = 0;.; x m + n = 0 megoldását nevezzük. Következmény: a) Bármely lehetséges kanonikus alakú feladat összes lehetséges megoldásainak L halmaza nem üres b) Az aktuális bázismegoldáson felvett célfüggvényérték α c) A lehetséges kanonikus alakú feladat

bázismegoldása egyben optimális megoldás is, ha cm+t ≤ 0 (t = 1,  , n ) Optimumkritérium Ha valamely LKAF célfüggvényében nincs negatív együttható, akkor a feladat megoldása is. Bizonyítás: Bármely ~ x ≥ 0 ⇒ Z (~ x)=α + x ∈ L esetén ~ m+n ∑ c ~x j = m +1 j j ≥0 Megjegyzés: Ez elegendő, de nem szükséges feltétel. ( ) ≥α = Z x * * x aktuális bázismegoldása egyúttal optimális A bázisváltoztatás tétele Ha a x1 x2 xm (1 ≤ xj ≥ 0 + a1m+1 xm+1 + a2 m+1 xm+1 + . + a1m+n xm+n + . + a2 m+n xm+n = b1 = b2 . . . + . + amm+n xm+n = bm + amm+1 xm+1 j ≤ m + n ); (bi ≥ 0; (1 ≤ i ≤ m )) + cm+1 xm+1 + . + cm+n xm+n = Z ( x ) min LKAF célfüggvényében a c j (m + 1 ≤ j ≤ m + n ) együttható negatív és létezik a α  b  ∆ j = min  r a rj > 0, 1 ≤ r ≤ m   a rj  mennyiség, akkor megadható a feladattal ekvivalens LKAF, melyhez tartozó x bázismegoldásán

felvett célfüggvényérték: α + c j∆ j . Bizonyítás: Tegyük fel, hogy a kj generátorelem, ekkor a végrehajtandó átalakítások: rk ⇐ r i a régi  i − ik feltétel r i az új  1 rk a kj r i ⇐ r i − Z ⇐ Z − aij a kj cj a kj rk (1 ≤ i ≤ m és i ≠ k ) rk Z a régi  célfüggvény Z i az új  A kapott feladat 1.) Ekvivalens az előzővel, hiszen belőle azonos átalakításokkal nyertük 2.) Lehetséges kanonikus alakú, hiszen a) x j együtthatói 0-k lesznek (kivéve a kj = 1 -et) és a bázisváltozók közül csak a k. feltétel eddigi bázisváltozójának együtthatói „romlanak el” b) a jobboldalak nemnegatívak maradnak: b k = (a bk ≥0 a kj bi = bi − aij a kj bk kj > 0 és bk ≥ 0) (1 ≤ i ≤ m és i ≠ k ) aij ≤ 0 bi ≥ bi ≥ 0 aij > 0 bi b ≥ k a k . feltétel min hányadosa aij a kj ⇒ b j = b j − c) a célfüggvény értéke az új bázismegoldáson Behelyettesítve az új

aij a kj bk ≥ 0 α + c j∆ j x bázismegoldást, a célfüggvény új Z alakjába m+n α + ∑ c t x t = Z − c j t =1 bk a kj Ha xt bázisváltozó, akkor ct = 0 ⇒ ct x t = 0 Ha xt döntési változó, akkor x t = 0 ⇒ ct x t = 0 ct x t = 0 (1 ≤ t ≤ m + n ) Ezért α = Z − cj bk a kj ⇒ Z (x ) = α + c j ∆ j = ∆j Mikor nemkorlátos a LKAF célfüggvénye L-en? Ha a x1 x2 xm xj ≥ 0 (1 ≤ α + a1m+1 xm+1 + a2 m+1 xm+1 + . + a1m+n xm+n + . + a2 m+n xm+n = b1 = b2 . . . + . + amm+n xm+n = bm + amm+1 xm+1 j ≤ m + n ); + cm+1 xm+1 (bi ≥ 0; (1 ≤ i ≤ m )) + . + cm+n xm+n = Z ( x ) min (m + 1 ≤ j ≤ m + n ) és az arj LKAF-ban valamely c j < 0 célfüggvénye alulról nem korlátos L-en. Bizonyítás: { } (1 ≤ r ≤ m ) együtthatók egyike sem pozitív, akkor a feladat ( ) ∞ Megadjuk lehetséges megoldásainak egy olyan x (t ) t =1 sorozatát, melyen Z x (t )  −∞ t ∞ ( t)  xj = t (t

)  Legyen  a döntési változók értékei x -ben ( t) xs = 0 m + 1 ≤ s ≤ m + n és s ≠ j  ( ) Ekkor a bázisváltozók értékei: xr(t ) = br − arj t ≥ 0 (1 ≤ r ≤ m ) ( ) Tehát: x (t ) ∈ L és Z x (t ) = α + c j t  −∞ Megjegyzés: t ∞ >0 Az 1. 2 és 3 tételek sokféle generálóelem kiválasztási stratégiát tesznek lehetővé: a) Bármelyik negatív célfüggvény együttható oszlopát kiválaszthatjuk b) Melyben bármely minimális nemnegatív hányadosú sor választható A szimplex típusú algoritmusok működésének elemzése (degeneráció, ciklizálás) Egy iterációs lépésben a feladat aktuális lehetséges kanonikus alakjáról a következő lehetséges kanonikus alakjára való áttérést értünk 1. nem tudunk generáló elemet választani . T 1  optimális megoldásunk van 3. T b. vagy a negatív célfüggvény együttható oszlopában nincs pozitív együttható   nemkorlátos eset

a. mert nincs negatív célfüggvény együttható 2. tudunk generálóelemet választani, de a célfüggvény értéke mégsem csökken Oka: ∆ j = 0 ⇒ a bázismegoldás nem változik (de a feladat alakja igen) ↑ degenerációs lépés Az olyan bázismegoldásokat, melyek degenerált iterációs lépést idézhetnek elő, szokás degenerált bázismegoldásnak nevezni (= az aktuális bázismegoldásban legalább 1 bázisváltozó értéke≡ 0az aktuális feltételrendszer jobboldalán 0 fordul elő) Megjegyzés 1. 2. degenerált bázismegoldás megjelenése nem mindig eredményez degenerált iterációs lépést (csak lehetőség) a gyakorlatban sokszor ütközünk degenerált bázismegoldásokba, melyek előbb utóbb degenerált iterációs lépéseket eredményeznek. A szimplex algoritmusok azonban rendszerint (néhány iterációs lépés után) túljutnak ezeken a nehézségeken Ciklizálás Ha valamely szimplex algoritmus sosem ér véget, akkor ciklizál. A

végtelenségig folytatható, bizonyos számú lépés megtétele után mindig ugyanoda jutunk. Heurisztikus szimplex típusú algoritmusok A 2. tétel szerint a generálóelem sokféleképpen választható, tehát sokféle „heurisztikus” szimplex típusú algortimust használnak. Ezek közül néhán+y: (a megállási feltételek a korábbiak) A generálóelem véletlenszerű kiválasztása a) A negatív célfügvény együtthatójú oszlopok közül véletlenszerűen választok egyet b b) A kiválasztott j-edik oszlopban azon akj > 0 együtthatók közül választok véletlenszerűen, melyekre ∆ j = k akj teljesül Megjegyzés Ez az algoritmus 1 valószínséggel véges számú lépésben ér véget A legnagyobb csökkentés módszere a) Minden c j < 0 oszlopban kiszámítjuk ∆ j -t, majd a minimális c j ∆ j értékű oszlopok közül a legkisebb indexűt választom b b) A kiválasztott j-edik oszlopban fentről kezdve az első olyan akj > 0

együtthatót választjuk, melyre ∆ j = k teljesül. akj Megjegyzés Ez az algoritmus ciklizálhat A legmeredekebb csökkenés módszere Olyan döntési változót választunk, amely értékének növelésével (0-ról) a célfüggvény értéke a legmeredekebben csökken. Megjegyzés Ez az algoritmus is ciklizálhat, viszont általában a leggyorsabb Bland-féle algoritmus (a legkisebb index szabálya) a) A legkisebb indexű negatív célfüggvényegyüttható oszlopát választjuk b b) A kiválasztott j-ik oszlopban tekintem azon akj > 0 együtthatókat, melyekre ∆ j = k teljesül. Ezek közül azt akj választom, amelyik sorában a bázisváltozó a legkisebb indexű. Megjegyzés A gyakorlatban ez bizonyult a leglassabbnak, ezért célszerű olyankor bevetni, amikor arra gyanakszunk, hogy az általunk használt szimplex algoritmus ciklizál. Számolás szimplex táblázattal Ötlet: a) Felesleges a bázisváltozók együtthatóvektorait tárolni b) A

bázisváltozóvá váló döntési változó együtthatóvektora helyére az új döntési változó együtthatóvektora kerülhet Megoldás lépései: x n +1 xn + m x1 a1, n +1 a1, n + m b1 xn a n , n +1 a n, n + m cn +1 cn + m bn −α Tegyük fel, hogy a generáló elem a kj . xk kikerül a bázisból, x j bekerül a generáló elem helyére a reciproka kerül a generáló elem oszlopát osztjuk a -1-szeresével a generáló elem sorát osztjuk a generáló elemmel a a többi elem az úgynevezett négyszögszabállyal számolandó: ais = ais − ks * a kj aij x1 xn x n +1 xn + m x1 a1, n +1 xn 0 a n , n +1 a1, n + m a n, n + m 1 0 0 0 1 b1 bn cn +1 cn + m 0 0 −α A szimplex tipusú algoritmus egy lépésének leírása a mátrixalgebra segítségével: Megoldandó a következő lkaf: Ax = b x≥0 (b≥0) α+cTx =z(x)  min ahol 1 0 0 a1,n+1 A= 0 0 1 an,n+1 a1,n+m x= an,n+m x1 xm xm+n b=

cT=[0,0,,0,cm+1,,cm+n] Tfh : a kj a generáló elem: így az elvégzendő ekvivalens átalakítások: 1 rk = * rk a kj ri = ri − z = z − aij a kj cj a kj rk rk Legyen 1 Q-1= 0 − aij 0 0 a kj 0 0 1 0 1 a kj 0 0 0 0 0 0 0 0 a mj 1 0 0 1 − a kj dT=[0,,0,cj,0,0]1 x m Végrehajtva az elvégzendő ekvivalens átalakításokat, a kapott új lka leírható az alábbi módon: Q-1Ax = Q-1b x≥0 (Q-1b≥0) T -1 T T -1 α+d Q b+(c -d Q A)x =z(x)  min Egy darab iterációs lépés akj generálóelemmel b1 bn A szimplex algoritmusok v (≥ 0) db iterációs lépésének végrehajtása után kapott és a feladat kiindulási l k alakja közötti kapcsolat leírása mátrixalgebra segítségével: Tétel: Ha v (≥0) db iterációs lépés után kapott l k alak bázisváltozói rendre: x i1 ,.,x im (az 1, m-edik feltételé) a(0) 1,i1 a(0) 1,im Bv= a(0) m,i1 (0) a m,im dT v = [c i1 (0), , c im (0)] Akkor a v-edik lépés

után kapott lk a f leírható az alábbi módon: Bv-1A(0)x = Bv-1b(0) x≥0 (Bv-1b(0)≥0) α(0)+dTBv-1b+(c(0)-dTBvA(0))x =z(x)  min Bizonyítás: segédtételünk v-szeri alkalmazásával nyerjük, hogy v db szimplex lépés után a feltételrendszer : Q-1v.Q-11A(0) = Q-1vQ-11b(0) alakú és a kapott együtthatómátrix i1-edik oszlopa e1, ., im-edik oszlopa em Kiemelve ezen oszlopokat az e-edik rendszerből nyerjük: Q-1v.Q-11* [a(0)i1,, a(0)im] = [e1, ., em] (=Em) =B-1v =Bv Mivel szimplex lépéseket hajtottunk végre, ezért B-1vb(0) ≥ 0 is teljesül. Balról szorozva dTv = [ci1(0), , cim(0)]- lal a feladat jelenlegi B-1vA(0)x = B-1vb(0) feltételrendszerét, a kapott: dTv B-1vA(0)x = dTv B-1vb(0) egyenletben xi1 együtthatója ci1(0),., xim-é cim(0) Kivonva ezt az egyenletet a célfüggvény eredeti egyenletéből a célfüggvény új α (0) +c (0)Tx - dTv B-1vA(0)x = z(x) - dTv B-1vb(0) alakjában xi1,,xim együtthatói mind 0-k lesznek  az eredetivel ekvivalens

lkaf-ot kapunk, melynek célfüggvénye a kívánt alakú. A szimplex típusú algoritmus „módosított” változatának táblázatos elrendezése Az induló feladat A v-edik lépés után LKA A(v ) = Bv−1 A(0 ) b c (v ) = Bv−1 b (0 ) (v )T =c (0 )T − d v Bv−1 A(0 ) T − α (v ) = −α (0 ) − d v Bv−1 b T (0 ) Áttérés a (v+1)-edik LKA-ra Kiválasztom az új generálóelemet, melynek alapján meghatározom d v +1 -et és Qv−1 -et, majd rendre kiszámolom és a T következő táblázatba írom az alábbiakat 1. Bv−+11 = Qv−1 Bv−1 2. b 3. − d v +1 Bv−+11 4. c 5. − α (v +1) = −α (0 ) − d v +1 Bv−+11 b 6. A(v +1) = Bv−+11 A(0 ) -nak csak azt a részét kell meghatározni, amelyik a következő generálóelem kiválasztásakor (v +1) = Qv−1 b (v ) T (v +1) T =c (0 ) T − d v +1 Bv−+11 A(0 ) T T feltétlenül szükséges!! (0 ) A lexikografikus szimplex algoritmus d ∈ R n lexikografikusan nagyobb

vagy egyenlő, mint c ∈ R n , ha az első eltérő d i és ci elemeik közül d i > ci , vagy d = c . Jelölése: d c A  reláció teljes rendezés, mert • Dichotom: bármely két n-elemű vektor összehasonlítható vele, és az összehasonlítás kétféle lehet: o Vagy a lexikografikusan nagyobb vagy egyenlő mint b o Vagy b lexikografikusan nagyobb vagy egyenlő mint a • Reflexív: ∀a ∈ R n : a a • Tranzitív: ∀a, b, c ∈ R n : ab és bc ⇒ ac • Antiszimmetrikus: ∀a, b ∈ R n : ab és b a ⇒ a = b ( ) ( ) n Mivel a  reláció teljes rendezés, ezért R bármely véges sok elemű részhalmazának van legkisebb eleme, amely vektort a halmaz lexikografikus minimumának nevezzük. A  relációhoz tartozó szigorú rendezés: d  c d ∈ R lexikografikusan pozitív, ha d  0 P mátrix lexikografikusan pozitív, ha minden sorvektora lexikografikusan pozitív. A lexikografikus szimplex algoritmus egy iterációs

lépése (megállási feltétel nélkül) 1. Vegyük a legnegatívabb célfüggvényegyütthatójú cáltozók közül a legkisebb indexűt, jelölje ezt x j 2.   bk i Ha a j. oszlop generátorelemként szóbajövő elemei ak1 j , ak 2 j ,ak s j  ak i j > 0 és = ∆ j , (1 ≤ i ≤ s ) , akkor   ak i j   képezzük az alábbi vektorokat: 1 hTk = bk , ak ,1 ,.ak1 , m + n 1 a k1 j 1 1 [ ] . hTk = s melyek 3. [ 1 bk , ak s ,1 ,.ak s , m + n ak s1 j s ] T h ki lexikografikus minimuma jelöli ki az a ki j generálóelemet. a kiválasztott genereálóelemmel végrehajtjuk a 2. tétel átalakításait Megjegyzés: Mivel a hkTi vektorok páronként különbözőek, így a generálóelem kiválasztása egyértelmű. A lexikografikus szimplex algoritmus véges számú lépésben végetér. Szabályos alakú feladat megoldása általános esetben n ∑a j =1 ij x j ≤ bi (1 ≤ i ≤ m ) x j ≥ 0 (1 ≤ j ≤ n ) bi lehet negatív! n α +

∑ c j x j min j =1 Van-e l ehetséges megoldása és ha van, ak kor h ogyan l ehet a feladat valamely l ehetséges kanonikus al akját megadni? ( amit azután megoldhatunk) Társítsuk az alábbi segédfeladatot: n ∑a j =1 ij x j − x0 ≤ bi (1 ≤ i ≤ m ) x j ≥ 0 (0 ≤ j ≤ n ) x0 = w min Észrevételek: a) Van lehetséges megoldása (pl.: ~ x j = 0 (1 ≤ j ≤ n ) és ~ x0 „elég nagy”) b) A szabályos alakú feladatnak p ontosan a kkor van lehetséges megoldása, ha a segédfeladat optimuma 0. meg először a segédfeladatot ⇒ oldjuk Az algoritmus kiegészítése, helyességének igazolása a) A társított segédfeladat mindig megoldható, mindig elkészíthető a vele ekvivalens LKAF, amely mindig megoldható pl.: a lexikografikus szimplex algoritmussal (melynek véget érése bizonyított) b) Oldjuk meg tehát ezt a LKAF-ot. Jelöje ( ) * c) ( ) ⇒ w(x ) = 0 ⇒ * w x ≥0⇒w x >0⇒ * * x a kapott optimális megoldást! A t ársított

s egédfeladatnak ( és í gy az eredeti s zabályos feladatnak) n incs l ehetséges megoldása A t ársított s egédfeladatnak ( és í gy az megoldása eredeti s zabályos feladatnak) v an lehetséges x0 bázisváltozó valamelyik feltételben x0 döntési változó : e) Ezen feltétel jobboldala 0 w( x ) = x 0  *  x0 = 0 * w x =0 d) x0 kiküszöbölésére a b ázisváltozók k özül v an-e az x0 bázisváltozójú f eltételben másik változónak n emnulla ( ) együtthatója? - Van: ezen együtthatók közül valamelyiket (lehet negatív is) generálóelemnek tekintve végrehajtjuk a 2. tétel átalakításait. Ennek során: • A jobboldalak nem változnak (0 jobboldalú feltétel számszorosait vonjuk ki belőlük) • Ismét LKAF-ot kapunk • x0 döntési változó lesz - • a bázismegoldás nem változik (degenerált iterációs lépést végeztünk) Nincs: elhagyom ezt a feltételt ( x0 = 0 alakú, azaz az ö sszes többi változó bármely értéke

esetén teljesül) a megmaradt feltételekben x0 már nem szerepel x0 változót (ezután L-ben maradunk ↔ x0 = 0 ) e) Törlöm a feladatból az f) Az eredeti célfüggvény szerint haladok tovább (és már van bázismegoldásom is) Szabályos alakú feladat megoldása általános esetben - Elhagyom a w( x ) segéd célfüggvényt 2/2 Z ( x ) eredeti célfüggvényt - Csatolom a - A célfüggvényből eliminálom 1 a b ázisváltozókat: az xit bázisváltozójú f eltétel cit -szeresét k ivonom a célfüggvényből (1 ≤ t ≤ m ) g) Az eredeti szabályos feladattal ekvivalens LKAF-ot kaptam, amelyet megoldok 1 kiküszöbölöm Standard alakú feladattá alakítás LP feladat általános alakja A(1) x ≤ b (1) A( 2 ) x = b A(3 ) x ≥ b (2 ) (3 ) max    min  α + cT x  Standardizálás lépései 1. 2. 3. 4. a maximumfeladat helyett a célfüggvényegyütthatók (-1)-szeresének minimumát keressük az alsókorlátos

változóinkat 0 alsó korlátos változókkal helyettesítjük negatív jobboldalú feltételeinket a (-1)-szeresükkel helyettesítjük új nemnegatív változók hozzáadásával illetve kivonásával feltételeinket egyenletekké alakítjuk (kivéve a változók nemnegítivitását előírókat) 5. minden alsó korlát nélküli változót két nemnegatív változó különbségeként írunk fel Az átalakítások után elegendő a standard feladat megoldásával foglalkozni. Standardizálás lépései (a gyakorlat alapján) 1. 2. 3. 4. Ha a megoldandó feladat maximum feladat, akkor szorozzuk meg a célfüggvényt -1-gyel és keressük az új célfüggvény minimumát Ha a jobb oldalon szerepel negatív mennyiség, akkor szorozzuk -1-gyel a megfelelő egyenlőtlenséget vagy egyenlőséget Ha szerepelnek olyan változók a feladatban, amelyekre nincs előírva nemnegativitási feltétel, akkor helyettesítsük rendre ezeket a változókat két nemnegatív változó

különbségével. Minden egyenlőtlenség bal oldalához adjunk hozzá, illetve vonjunk ki egy nemnegatív változót attól függően, hogy a tekintett egyenlőtlenség „≤” vagy „≥” szerepel és a változtassuk az egyenlőtlenségeket egyenlőségekké. Mikor ekvivalens a standard alakú feladat valamely LKAF-tal? Ha a (*) standard alakú feladatban az [ B = a i , a i ,., a i 1 2 B − A x = B −1 b ( x ≥ 0 B −1 b ≥ 0 ) [ m ] mátrix nemszinguláris és B xi1 , xi2 ,., xim −1 változókhoz tartozó A-beli oszlopvektorokból képzett [ ] b ≥ 0 , továbbá d T = ci1 , ci2 ,., cim , akkor a ] α + d T B −1 b + cT − d T B −1 A x = Z min feladat lehetséges kanonikus alakú és ekvivalnes a (*) standanrd alakú feldattal. Bizonyítás: 1. A kapott feladat LKAF: [ B −1 A -nak az i1 , i2 ,., im -edik oszlopaiból alkotott mátrix éppen Em , B −1 a i , a i ,, a i B −1 b ≥ 0 feltevés szerint [ ]( 1 2 ) m ]= B −1 B =

Em Z’ célfüggvényben xi1 , xi2 ,., xim együtthatója 0, cit = cit − ci1 , ci2 ,, cim B −1 A i = cit − cit = 0 2. Ekvivalensek: L A = LB −1A (egybeesnek a lehetséges megoldások halmazai) minden x ∈ L esetén a két célfüggvény értéke ugyanaz: [ ] z (x ) = α + d T B −1b + c T − d T B −1 A x = α + c T x + d T B −1 (b − Ax ) = z (x ) t