Történeti bevezetés. Történeti bevezetés. Történeti bevezetés. Fourier-Motzkin elimináció lineáris egyenlőtlenségrendszerek megoldására

Történeti bevezetés Fourier-Motzkin elimináció lineáris egyenlőtlenségrendszerek megoldására.

Operációkutatás előadáshoz segédanyag A segédanyag hibákat tartalmaz, melyek az előadáson javításra kerültek. A jegyzet csak az előadáson elhangzottakkal együtt képezi a vizsga anyagát!!!!

Jean Baptiste Joseph Fourier (1768. március 21. – 1830. május 16.) francia matematikus és fizikus. Theodore Samuel Motzkin (1908. március 26. – 1970.december 15.) izraeli-amerikai matematikus.

Burai Pál

2013. december 5.

x +y −z ≥ 2

=⇒

2x − y ≥ 3

x +y −2≥ z

=⇒

x − 2y ≤ z

x +y −2≥

x − 2y

2x − y ≥

3

−x + 2y + z ≥ 0 2x − y ≥ 3 És így tovább. Végül azt kapjuk, hogy x ≥ 11 6 , melyből visszafejthetjük a többi változót is. Burai Pál

Burai Pál

Operációkutatás előadáshoz segédanyag

Történeti bevezetés


Történeti bevezetés Lineáris programozás polinom időben megoldható.

Lineáris programozás kezdetei. Leonid Genrikhovich Khachiyan (1952. május 3. - 2005. április 29.) amerikai-orosz matematikus. Az ellipszoid algoritmus felfedezője, amely az első polinom idű algoritmus lineáris programozási feladatok megoldására.

Leonyid Vitaljevics Kantorovics (1912. január 19. - 1986. április 7.) szovjet-orosz matematikus és közgazdász. 1975-ben Tjalling Koopmans holland közgazdásszal megosztva közgazdasági Nobel-emlékdíjban részesült. George Bernard Dantzig (1914. november 8. – 2005. május 13.) amerikai matematikus. Jelentő eredményeket ért el az operciókutatás, a közgazdaságtan és a statisztika területén. A szimplex algoritmus felfedezője.

Burai Pál


Narendra Krishna Karmarkar (1957 - ) indiai matematikus, a róla elnevezett Karmarkar algoritmus felfedezője. Ez az első, gyakorlatban is hasznalható, polinom időben futó algoritmus lineáris programozási feladatok megoldására. Burai Pál


Példák lineáris programozási feladatokra

Példák lineáris programozási feladatokra Jones farmer

Giapetto faüzeme Giapetto fajátékokat készítő üzeme kétféle játékot készít. Fakatonákat és vonatokat. Egy fakatona ára 27$, az anyagköltsége 10$, a ráfordított munka költsége pedig 14$. Ugyanezek az adatok a vonatra vonatkozóan 21$, 9$ és 10$. Mindket játék elkészítéséhez kétfajta szakmunkára van szükség, összeszerelésre és polírozásra. A katonához az előbbiből 2, az utóbbiból 1 óra szükséges, ugyanezek az adatok a vonat esetében 1 − 1 óra. Minden héten 80 órányi összeszerelés és 100 órányi polírozás áll rendelkezésre, a nyersanyag pedig korlátlan mennyiségben. A vonatokból bármennyit el lehet adni a piacon, de a katonákból csak 40-et hetente. Maximalizáljuk Giapetto heti nyereségét!

A modellalkotás 1

Döntési változók meghatározása.

2

Célfüggvény meghatározása.

3

Feltelek meghatározása. Burai Pál



Jones farmernek el kell döntenie, hogy hány hold kukoricát és hány hold búzát fog vetni. Egy hold búza 25 véka termést hoz és heti 10 munkaóra szükséges a megműveléséhez. Ugyanezek a számok a kukoricánál 10 és 4. Egy véka búza 4$-t adható el, míg a kukorica 3$-t. Jonesnak 7 hold föld és heti 40 munkaóra áll rendelkezésre. Egy kormányrendelet értelmében legalább 30 véka kukoricát kell termelnie ebben az évben. Maximalizáljuk a farmer nyereségét.

Bevco cég A Bevco cég egy Oranj nevű narancs ízesítésű üdítőitalt gyárt narancs-szóda és narancslé keverésével. Egy deka narancs-szóda fél deka cukrot és egy mg. C-vitamint, egy deka narancslé pedig negyed deka cukrot és három mg C-vitamint tartalmaz. A Bevrónak egy deka narancs-szóda két centbe kerül, egy deka narancslé pedig három centbe. A Bevco marketing osztálya elhatározta, hogy minden 10 dekás Oranj-palack legalább 20 mg C-vitamint és legfeljebb 4 deka cukrot tartalmazhat. Minimalizáljuk a költségeket a fentiek figyelembe vétele mellett. Burai Pál Operációkutatás előadáshoz segédanyag


Bloomington Sörfőzde A Bloomington Sörfőzde pilzenit és angol világos sört állít elő. A pilzeni eladási ára 5$ hordónként, a angol világosé 2$ hordónként. Egy hordó pilzeni előállításához 5 font kukorica és 2 font komló szükséges. Egy hordó világos sörhöz pedig 2 font kukorica és 1 font komló kell. Rendelkezésre áll 60 font kukorica és 25 font komló. Fogalmazzunk meg egy LP-t, amellyel maximalizálható a bevétel! Oldja meg az Lp-t grafikusan!

Jones farmer süteménye Jones farmer kétféle süteményt süt (csokoládésat és vaníliásat), hogy kiegészítse a jövedelmét. Egy csokoládés sütemény 1 dollárárt adható el, a valíliás pedig 50 centért. Minden csokoládés süteménybe kell 4 tojás, és 20 percig kell sütni. Minden vaníliás süteménybe kell egy tojás, és 40 percig kell sütni. Rendelkezésre áll 8 óra sütési idő és 30 tojás. Fogalmazzon meg egy LP-t, amelynek megoldása maximalizálja Jones farmer bevételét! Ezután oldja meg a feladatot grafikusan! Burai Pál


Reklámköltség minimalizálása A Dorian Auto cég luxusautókat és teherautókat gyárt. A vállalat ógy gondolja, hogy vásárlói legnagyobb valószínűséggel magas jövedelmű nők és férfiak. Ennek a fogyasztói csoportnak a megnyerésére a cég egy komoly tévé-hirdetési kampányt indított és elhatározta, hogy 1 perces reklámhelyeket vásárol kétféle típusú tévéműsorban: vidám műsorokban és futballmeccsek alatt. Minden kabarébeli reklámot 7 millió magas jövedelmű nő és 2 millió magas jövedelmű férfi néz. Minden futballmeccs alatti reklámot 2 millió magas jövedelmű nő és 12 millió magas jövedelmű férfi néz. Az egyperces kabarébeli reklám 50 ezer dollárba kerül, és az egyperces futballmeccs alatti reklám ára 100 ezer dollár. A cég azt szeretné, ha hirdetéseit legalább 28 millió magas jövedelmű nő és 24 millió magas jövedelmű férfi látná. Alkalmazzuk a lineáris programozást arra, hogy a Dorian cég a reklámcéljait minimális költségek mellett érje el!

Burai Pál


Lineáris programozási feladat általános- és standard alakja

Standard alakra hozás

Általános alakú lineáris programozási feladat Legyenek n, m, j, k, l természetes számok, A1 ∈ Rj×n , A2 ∈ Rk×n , A3 ∈ Rl×n , A ∈ Rm×n adott mátrixok, b1 ∈ Rj , b2 ∈ Rk , b3 ∈ Rl , b ∈ Rm , c ∈ Rn adott oszlopvektorok, ekkor a következőt T

c x +α

−→

min vagy max

A1 x A2 x A3 x

≥ ≤ =

b1 b2 b3

1

Ha a feladat maximum feladat, akkor a celfüggvényt szorozzuk meg −1-gyel.

2

Ha bi negatív, akkor szorozzuk meg a szóban forgó sort −1-gyel.

3

Az egyenlőtlenségekhez(ből) adjunk hozzá (vonjunk le) egy nemnegatív változót.

4

Azon változókat, melyekre nincs nemnegativitási feltétel, írjuk fel két nemnegatív változó összegeként.

f .h. (LP)

általános alakú lineáris programozási feladatnak, a

(LP-S)

cT x + α

−→

min

Ax x ≥ 0,

=

b (b ≥ 0)

f .h.

A fentieket végrehajtva, tetszőleges (LP)-t standard alkra hozhatunk, majd azt megoldva, az eredeti feladat megoldását is visszafejthetjük. A standard alakú feladatra már van megoldási algoritmusunk. Ez a kétfázisu szimplex módszer. Először a második fázissal foglalkozunk, amely speciális standard alakú feladatok megoldására használható.

optimalizálási feladatot pedig standard alakú lineáris programozási feladatnak nevezzük. Burai Pál Operációkutatás előadáshoz segédanyag

Kanonikus alak


Néhány fogalom

Tegyük fel, hogy a feltételben található A mátrix a következő alakú: A = [E , B], ahol E az m × m-es egységmátrix, B pedig egy m × (n − m)-es mátrix. Ekkor az (LP-S) feladat a következő alakot ölti:

(LP-K)

Burai Pál

cT x + α −→ (c1 , . . . , cm = 0)

min

[E , B]x x ≥ 0,

b (b ≥ 0)

f .h. =

melyet kanonikus alakú lineáris programozási feladatnak nevezünk.

Burai Pál


Definíció (Megoldások) A (LP-K) feladat feltételrendszerének eleget tevő vektorokat a (LP-K) megengedett megoldásainak nevezzük. Az x = (b1 , . . . , bm , 0, . . . , 0) vektort bázismegoldásnak, az x1 , . . . xm | {z } n−m db

változókat pedig bázisváltozóknak nevezzük. Ha valamelyik bi = 0, i = 1, . . . , m, akkor a hozzá tartozó bázismegoldást degenerált bázismegoldásnak nevezzük.

Definíció (Ekvivalencia) Két standard alakú feladatot ekvivalensnek nevezünk, ha a megengedett megoldások halmazai megegyeznek és ezen a célfüggvények egyenlőek. Ha a célfüggvények különbsége konstans a megengedett megoldások halmazán, akkor gyengén ekvivalensek.

Burai Pál


Szimplex algoritmus

Szimplex algoritmus, transzformációs formulák

Tétel (Optimalitás elegendő feltétele)

Tétel (Bázistranszformációs tétel)

Ha a célfüggvény minden olyan együtthatója nemnegatív, amely nem bázisváltozóhoz tartozik, akkor a szóban forgó bázismegoldás egyben optimális is.

Ha a célfüggvény minden nem bázisváltozóhoz tartozó negatív együtthatója olyan, hogy a feltételi mátrixban a neki megfelelő oszlopban van pozitív elem, akkor megadható egy, az eredetivel ekvivalens, kanonikus alakú feladat, amelynek bázismegoldásán a célfüggvény értéke nem nő. Amennyiben a megfelelő bi pozitív, akkor az új bázismegoldáson a célfüggvény értéke szigorúan kisebb.

Tétel (Feltétel a nem-megoldhatóságra) Ha a célfüggvény valamely nem bázisváltozóhoz tartozó negatív együtthatója olyan, hogy a feltételi mátrixban a neki megfelelő oszlopban nincs pozitív elem, akkor a célfüggvény alulról nem korlátos a megengedett megoldások halmazán.

Tegyük fel, hogy cj < 0 és legyen akj = min{ abrjr | arj > 0, r = 1, . . . , m}. Az így kiválasztott akj elemet generáló elemnek nevezzük. Jelölje a feltételt leíró egyenletrendszer i. sorát ri , a célfüggvény sorát pedig z. Ekkor a transzformációs formulák a következők:

Példa −2x3

x1 x2

xi −x3

4 3

+x4 −x4

+2x5 +x5

= =

≥0 +x4

−2x5

i = 1, . . . , 5 = z(x) → min

Burai Pál

2

3

=

ri0

= ri −

aij akj rk

z0

= z−

cj akj rk .


Szimplex algoritmus

1

rk0

1 akj rk ,

Burai Pál

i = 1, . . . , m, i 6= k,


Szimplex algoritmus, Ciklizálás elkerülése

Ha a célfüggvény nem tartalmaz olyan negatív együtthatót, amely nem bázisváltozóhoz tartozik, akkor a bázismegoldás optimális. Ha ez nem áll, akkor a második lépés következik. Tekintsük a negatív célfüggvényegyütthatók minimumát, majd ezek közül a legkisebb indexűt jelölje cj . Ha arj ≤ 0, r = 1, . . . , m, akkor a célfüggvény alulról nem korlátos a megengedett megoldások halamzán, így vége az eljárásnak. Ha ez nem áll, akkor a harmadik lépés következik. Tekintsük a pozitív arj , r = 1, . . . , m elemek esetén a br arj , r = 1, . . . , m, arj > 0 alakú törtek minimumát. Azon indexek közül, ahol ez felvétetik, válasszuk a legkisebbet, jelölje ezt akj . Ezzel az elemmel hajtsuk végre a transzformációs formulák által előírtakat, majd folytassuk az első lépéssel.

Legyen x, y ∈ Rn , ekkor x lexikografikusan kisebb vagy egyenlő, mint y , ha az y − x vektor első nem nulla komponenese pozitív.

Lexikografikus szimplex algoritmus 1

Az első két lépés megegyezik a szimplex algoritmus első két lépésével.

2

Válasszuk ki a hkt = (bkt , akt 1 , . . . , akt 1 ),

t = 1, . . . , s

alakú vektorokból a lexikografikusan legkisebbet. Ez jelöli ki a b generáló elemet. Itt a a kt , t = 1, . . . , s hányadosok a korábban kt j jelzett minimum tulajdonsággal rendelkeznek.

Állítás A lexikografikus szimplex algoritmus véges sok lépésben véget ér.

Burai Pál


Burai Pál


Szimplex módszer (kétfázisú szimplex algoritmus) Egy adott standard alakú feladatból fogunk kanonikus alakú feladatot készíteni. vT · 1 = w (LP-M1)

(LP-M2)

−→

1

Konstruáljuk meg a szóban forgó standard alakú feladathoz a megfelelő (LP-M2) feladatot, és ezt oldjuk meg a szimplex algoritmussal. Ha az optimum értéke pozitív, akkor a feladatnak nincs lehetséges megoldása. Ellenkező esetben folytassuk a második lépéssel.

2

Ha az első lépés után kapott feladat bázisváltozói között nem szerepel mesterséges

min

f .h. Ev + Ax x ≥ 0,

Szimplex módszer (kétfázisú szimplex algoritmus)

változó (vi ), akkor a harmadik lépés következik. Ellenkező esetben távolítsuk el a

= b v ≥ 0, (b ≥ 0)

−(1 · A)x = w − 1 · b

−→

Ev + Ax x ≥ 0,

= b v ≥ 0, (b ≥ 0)

mesterséges változókat a bázisváltozók közül a következő szerint. (i) Az eltávolítandó mesterséges változók közül vegyük az olyan legkisebb indexűt, amelynek egyenlete tartalmaz nullától különböző, természetes változóhoz tartozó együtthatót. Ha ilyen nincs, akkor folytassuk az eljárást a következő alponttal. Ha létezik ilyen tulajdonságú mesterséges változó, akkor a kiválasztott egyenletekben vegyük a nullától különböző, természetes változókhoz tartozó együtthatók közül a legkisebb indexűt. Ezzel, mint generáló elemmel hajtsuk végre a bázistranszformációs tételbeli átalakításokat. Ha az előállított új feladat bázisváltozói között nincs mesterséges változó, akkor folytassuk az eljárást a harmadik lépéssel. Ellenkező esetben az algoritmus ezen alpont ismételt végrehajtásával folytatódik. (ii) Hagyjuk el az eltávolítandó mesterséges változókat egyenleteikkel együtt a feltételrendszerből, majd folytassuk az eljárást a harmadik lépéssel.

min

f .h.

Állítás

3

A (LP-M1) feladatnak pontosan akkor létezik lehetséges megoldása, ha a (LP-M2) feladatnak optimális megoldásán a célfüggvény nulla. Burai Pál

Hagyjuk el a feltételrendszerből a mesterséges változókat és együtthatóikat. Az így kapott feltételrendszerhez vegyük hozzá az α + c T x = z elsődleges célfüggvényt, majd a z célfüggvény egyenletéhez rendre adjuk hozzá a t. egyenlet −cit -szeresét, ahol it a t. egyenletben szereplő bázisváltozó indexe. Az így előállított lehetséges kanonikus alakú feladatot oldjuk meg szimplex algoritmussal.


Érzékenység vizsgálat

Burai Pál



Reddy Mikks Company A Reddy Mikks vállalat házak külső és belső festésére gyárt festéket. A gyártáshoz kétféle alapanyagot használnak fel, jelölje ezeket A és B. Az anyagokból naponta korlátozott mennyiség áll rendelkezésre; 6 ill. 8 tonna. A belső festék egy tonnájához A-ból két tonna B-ből egy tonna szükséges, a B-hez egy ill. két tonna. A piackutatás azt mutatja, hogy a napi kereslet a belső festékre legfeljebb egy tonnával több, mint a külső festékre, továbbá, a belső festék iránti kereslet nem haladja meg a napi két tonnát. A nagykereskedelmi ár a külső festék esetén 3000$/tonna a belső festék esetén pedig 2000$/tonna. Maximalizáljuk a bevételt! Oldjuk meg a feladatot úgy is, hogy a külső festék ára 5000$/tonna! Ha a célfüggvényben a − cc12 hányados − 21 és −2 között marad, akkor az optimális megoldás nem változik, egyébként igen. Tehát ha az előbbi hányados a kijelölt intervallumban marad, akkor arra a megoldás nem "érzékeny". Burai Pál


cT x + α

−→

min

Ax x ≥ 0,

=

b (b ≥ 0)

f .h.

(LP-S)

Tétel Tegyük fel, hogy (LP-S)-ben az xi1 , . . . , xim változókhoz tartozó B mátrix reguláris, és B −1 b ≥ 0. Ekkor a d T B −1 b + (c − d T B −1 A)T x + α

−→

min

B −1 Ax x ≥ 0,

=

B −1 b (B −1 b ≥ 0)

f .h.

feladat (LP-S)-el ekvivalens lehetséges kanonikus alakú feladat, ahol d T = (ci1 , . . . , cim ). Burai Pál



Érzékenység vizsgálat, célfüggvény

Jelöljük a v . transzformáció után előálló feladatot a következőképpen: (0)

(LP-S-v.)

Legyen cj

(c (v ) )T x + α(v )

−→

min

A(v ) x x ≥ 0,

=

b (v ) (b (v ) ≥ 0)

(0)

f .h.

Tegyük fel, hogy v . feladat bázisváltozói xi1 , . . . , xim , B pedig az ezen változókhoz tartozó, az eredeti feladatban szereplő együtthatókból álló (0) (0) mátrix, továbbá dvT = (ci1 , . . . , cim ) . Ekkor a v . feladat megegyezik az alábbival: dvT Bv−1 b (0) + (c (0) − dvT Bv−1 A(0) )T x + α(0)

−→

min

Bv−1 A(0) x x ≥ 0,

=

Bv−1 b (0) (Bv−1 b (0) ≥ 0)

f .h.

Burai Pál

1. eset: xj nincs benne a bázisban. Ekkor cj nem eleme a dv vektornak. Ekkor az utolsó feladatban a j. célfüggvény együttható: (0) cj − dvT Bv−1 Aj , ahol Aj a j. oszlopot jelöli. Ez a kifejezés nemnegatív, ellenkező esetben folytatódna az algoritmus. Így a (0)

cj

A v . feladat jobb oldalának nemnegatívnak kell lennie. Azaz, a Bv(−1) b ≥ 0 becslést kapjuk. Ebben a b vektor valamelyik komponensét változónak véve alsó ill. felső becsléseket kapunk. Ebben a tartományban maradva a nem változik az optimumhely. Ellenben az optimum értéke változik. Ezt is ki lehet számítani a megfelelő komponens függvényeként az α + dv Bv−1 b képlettel. Minimum feladat esetén, a szóban forgó bi komponens egy egységnyi növeléséből származó csökkenést a céfüggvény értékében árnyékárnak nevezzük, amennyiben az optimális bázis nem változik.


≥ dvT Bv−1 Aj ,

becslés adódik. (0) 2. eset: Ha xj benne van a bázisban, akkor cj eleme a dv vektornak. Így a v . feladat minden nem nulla célfüggvény együtthatóját (0) megváltoztathatja cj megváltozása. Így az összes célfüggvény együttható nemnegativitását vizsgálni kell.


Érzékenység vizsgálat, b vektor

Burai Pál

az induló feladat célfüggvényének j. együtthatója.

Burai Pál


Dualitás

Legyenek a1 , . . . , amP∈ Rn tetszőleges vektorok. Ekkor a m K := {x ∈ Rn |x = i=1 λi ai , λi ≥ 0, i = 1, . . . , m} halmazt az a1 , . . . , am vektorok által generált kúpnak nevezzük. Könnyű látni, hogy K konvex részhalmaza Rn -nek.

Lemma Legyen a ∈ Rn tetszőleges. Ekkor létezik olyan b ∈ K vektor, hogy kb − ak = min kv − ak. v ∈K

Ez K -ban a a-hoz legközelebbi elem. Belátható az is, hogy pontosan egy ilyen b vektor létezik, de erre a Farkas lemma bizonyításához nem lesz szükségünk.

Burai Pál


Dualitás

Dualitás

Tétel (Farkas-lemma)

(LP-P) n

Legyenek a, a1 , . . . , am ∈ R tetszőleges vektorok. Ekkor az a x ≤ 0 T egyenlőtlenség pontosan akkor következménye a a1T x ≤ 0, . . . am x ≤0 egyenlőtlenség rendszernek, ha a ∈ K , azaz, a előáll az a1 , . . . , am vektorok nemnegatív lineáris kombinációjaként. Farkas Gyula (Pusztasárosd, 1847. március 28. – Pestszentlőrinc, 1930. december 27.) matematikus, fizikus, a Magyar Tudományos Akadémia rendes tagja. A magyarországi alkalmazott matematika és elméleti fizika jelentős alakja.

Következmény n×m

(LP-D) c T x = z(x) −→

T

f .h.

y T b = w (y ) −→

min

yT A y ≥ 0,

c

f .h. Ax x ≥ 0,

≤

b

≥

Tétel (gyenge dualitás) Tegyük fel, hogy x lehetséges megoldása a primál feladatnak, y pedig lehetséges megoldása a duál feladatnak. Ekkor z(x) ≤ w (y ).

Következmény Ha a primál feladat célfüggvénye felülről nem korlátos, akkor a duális feladatnak nincs lehetséges megoldása.

Következmény n

T

Legyen A ∈ R , c ∈ R . Ekkor az y A = c egyenletrendszernek pontosan akkor létezik nemnegatív megoldása, ha c T x ≥ 0 minden olyan x-re, amelyre Ax ≥ 0. Burai Pál

Ha a duál feladat célfüggvénye alulról nem korlátos, akkor a primál feladatnak nincs lehetséges megoldása. Burai Pál


Dualitás


Dualitás, Duális szimplex algoritmus

Tétel (erős dualitás)

c T x = w (y ) −→

Bizonyítás vázlat: Tegyük fel, hogy a (LP-P) feladatnak létezik x¯ optimális megoldása. Tekintsük a következő egyenlőtlenség rendszert és vezessük be az alábbi jelöléseket:  A −b ˆ :=  −E 0 , A cˆT := (c T , −c T x¯) 0 −1 x x ˆ Bebizonyítható, hogy tetszőleges esetén, ha A ≤ 0, akkor t t x cˆ ≤ 0 is fennáll. Ekkor a Farkas lemmából és a gyenge dualitási t tételből már következik az állítás.

[E , A](y , x) y , x ≥ 0,

Burai Pál


= b (c ≥ 0)

1

Ha az egyenlet jobboldala nemnegatív, akkor a bázismegoldás optimális. Ellenkező esetben a következő lépés.

2

Vegyük a negatív jobboldali elemek minimumát, majd ezek közül a legkisebb indexűt, jelölje ezt bj . Ha ennek a sorában minden elem nemnegatív, akkor a feladatnak nincsen lehetséges megoldása. Egyébként a következő lépés.

3

Tekintsük a negatív arj , r = 1, . . . , m elemek esetén a cr −arj , r = 1, . . . , m, arj < 0 alakú törtek minimumát. Azon indexek közül, ahol ez felvétetik, válasszuk a legkisebbet, jelölje ezt akj . Ezzel az elemmel hajtsuk végre a transzformációs formulák által előírtakat, majd folytassuk az első lépéssel.



≤ 0 ≤ 0 ≤ 0

min

f .h.

Ha a primál-duál feladatpárból valamelyiknek létezik optimális megoldása, akkor mindkettőnek létezik, és az optimumértékek megegyeznek.

Ax − tb −Ex −t

max

Burai Pál


Hozzárendelési feladat

Hozzárendelési feladat

Két lehetséges interpretáció Adott n fiú és n leány egy lakatlan szigeten. A lányok 1-től n-ig pontozzák a fiúkat. A közösség boldogsága arányos a lányok boldogságával, amit az adott pontszámok összegével mérünk. Minden lányhoz pontosan egy fiút rendelhetünk. Adjunk meg egy olyan hozzárendelést, amellyel maximális elégedettséget érhetünk el. Adott n munka és ugyanannyi munkás és egy n × n-es C költségmátrix, amelynek cij eleme azt jelöli, hogy az i. munkás a j. munkát milyen költséggel vállalja el. Osszuk szét a munkát úgy, hogy mindenki pontosan egyet végezzen el, és az összköltség minimális legyen.

Legyen C , D ∈ Rn×n . Azt mondjuk, hogy C ekvivalens D-vel (C ∼ D), ha léteznek olyan γi , δj , i, j = 1, . . . , n valós számok, hogy cij = dij + γi + δj , i, j = 1, · · · , n.

Állítás Az előbb definiált reláció ekvivalencia reláció az n × n-es mátrixok halmazán.

Állítás Ha két hozzárendelési feladatnak a költségmátrixa ekvivalens, akkor az optimális megoldásaik megegyeznek. Egy n × n-es mátrixbeli 0-ák halmazát függetlennek nevezzük, ha minden sorban és oszlopban legfeljebb egy található a halmaznak.

Modell Pn

i=1

Pn

j=1 cij xij

f .h. P n Pni=1 xij j=1 xij xij ∈ {0, 1} Burai Pál

−→

min

= =

1 1 i, j = 1, . . . , n


Hozzárendelési feladat, Magyar módszer Egerváry Jenő ( Debrecen, 1891 április 16. – Budapest, 1958 november 30.) magyar matematikus. Alapvető eredményeket ért el a gráfelmélet és a kombinatorikus optimalizálás területén. Kőnig Dénes (Budapest, 1884. szeptember 21. – Budapest, 1944. október 19.) magyar matematikus, az első gráfelméleti tankönyv szerzője. Édesapja Kőnig Gyula szintén neves matematikus volt. Legfontosabb eredményeit a gráfelmélet területén érte el. Kuhn, Harold W. (Santa Monica, 1925. július 29.) amerikai matematikus. Jelentős eredményeket ért el a játékelméletben és a nemlineáris optimalizálás elméletében.

Burai Pál


Állítás Ha egy nemnegatív elemű n × n-es mátrixban ki van jelölve egy n elemű független nullából álló rendszer, akkor az egyben a mátrixhoz tartozó hozzárendelési feladat megoldását is adja egyben. Burai Pál


Hozzárendelési feladat, Magyar módszer Előkészítő rész: A C mátrix minden sorából vonjuk ki az illető sor minimumát! Az így kapott C mátrix minden oszlopából vonjuk ki a szóban forgó oszlop minimumát! A kapott mátrix az alábbi iteráció nulladik eleme, jele: C (0) . Jelöljünk ki C (0) -ban oszlopfolytonosan egy független nullákból álló rendszert csillaggal, majd kezdjük el az iterációt! Ha a C (r ) -ben kijelölt független 0-rendszer elemeinek a száma n, akkor készen vagyunk. Ellenkező esetben kössük le a független nullákat tartalmazó oszlopokat és folytassuk az eljárást a második lépéssel. Keressünk sorfolytonosan szabad nullát, ha nincs, akkor az ötödik lépés következik. Ha találunk szabad nullát, akkor vizsgáljuk meg a sorát. Ha ez a sor nem tartalmaz csillagozott nullát, akkor a negyedik lépés következik, ellenkező esetben a harmadik. A tekintett szabad nullát lássuk el vesszővel, kössük le a sorát, és szüntessük meg a sorában lévő csillagozott nulla oszlopának lekötését, majd folytassuk a második lépéssel. A tekintett szabad nullát lássuk el vesszővel, és ebből kiindulva képezzünk láncot a következő módon.: minden láncbeli vesszős nulla után az oszlopában lévő csillagos nullával folytatódik a lánc, és minden láncbeli csillagos nulla után a sorában lévő vesszős nullával folytatódik a lánc, feltéve, hogy vannak ilyen elemek. Ellenkező esetben a lánc véget ér. Ezek után legyen C (r +1) a jelölések nélküli C (r ) mátrix, és lássuk el csillaggal az olyan nullákat, amelyek csillagozva voltak és nem szerepelnek a láncban, vagy vesszősek és szerepelnek a láncban. Folytassuk az első lépéssel. Képezzük a szabad elemek minimumát, majd ezt a minimumot vonjuk ki az összes szabad elemből és adjuk hozzá a kétszer kötött elemekhez. Folytassuk a második lépéssel!

Burai Pál


Hozzárendelési feladat, tiltott hozzárendelések

Szállítási feladat m X

Az ekvivalencia tétel tiltott hozzárendelések esetén is igaz, így elegendő nemnegatív elemű mátrixokkal foglalkozni. Jelölje M a mátrix összes elemének összegénél eggyel nagyobb számot. Az eredeti költségmátrixban írjunk M-et a tiltott hozzárendelést jelölő helyekre, majd hajtsuk végre a korábbi algoritmust.

i = 1, · · · , n

xis = ai ,

s=1 n X

j = 1, · · · , m

xtj = bj ,

t=1

xij ≥ 0 , i = 1, · · · , n ; j = 1, · · · , m

Állítás n X m X

A tiltott hozzárendeléses feladatnak pontosan akkor létezik megoldása, ha a fenti eljárással elkészített mátrixhoz tartozó hozzárendelési feladat optimális megoldása kisebb, mint M. Ekkor a két feladat optimális megoldáshelye is egyenlő.

cij xij = z(X ) −→ min

i=1 j=1

Állítás A szállítási feladatnak pontosan akkor létezik optimális megoldása, ha a feladóhelyeken lévő összes anyag mennyisége megegyezik az összes felvevőhely szükséges anyagmennyiségének összegével. Burai Pál

Burai Pál


Szállítási feladat, Lehetséges megoldás keresése észak-nyugat módszerrel

Szállítási feladat

(0)

(0)

x1t = min a1 −

t−1 X

(0)

,

(0)

(0)

(0)

(0)

(0)

(0)

(0)

(0)

x31 = x32 = 0, x33 = 1, x43 = 2 (

= min ai , b1 −

i−1 X

) (0) xs1

Kitüntetett változók

s=1

(0)

(0)

xij > 0, ( (0) xij

= min ai −

(0)

t = 2, · · · , m

s=1

(0) xi1

(0)

x21 = x22 = 0, x23 = 3, x24 = 0

) x1s , b1

(0)

x11 = x12 = 2 , x13 = x14 = 0

(0)

x11 = min {a1 , b1 } (


j−1 X

(0) xit , bj

t=1

amelyre

) (0) xsj

,

s=1

j = 2, · · · , m, Burai Pál

−

i−1 X

és xts = 0 ,

(0)

(0)

(0)

xt+1s−1 = 0, xts−1 > 0, xt+1s > 0.

i = 2, · · · , n.


Burai Pál


Szállítási feladat, Példa

Szállítási feladat, Disztribúciós módszer lépései

 

1 C = 3 5 b=

2,

3 3 4

4 2 3

2,

4,

 3 1 , 3 2,

 4 a= 3  3 Γ0 =

v1 = 0 2

v2 = 2 2 1

n

2 0 0

0 3 1

(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4)

v3 = 3 0 3

3

3

2

Válasszunk egy olyan indexpárt, amelyik nincs a kitüntetett elemek halmazában. Legyen ez xrs . Továbbá ur + vs > crs és ur + vs − crs maximális. Képezzünk xrs -bõl induló olyan zárt ciklust, amelyben csak kitüntetett elemek szerepelnek xrs -n kívûl. Legyen δ az xrs -tõl páratlan távolságra elhelyezkedõ ciklusbeli cellákhoz tartozó értékek minimuma. Az új disztribúciós táblában legyen xrs = δ, a ciklusban tõle páratlan távolságra lévõ értékeket δ-val csökkentjük, a párosra lévõket δ-val növeljük, a többit nem változtatjuk.

o

3

2

1

1 5

2

4

3

Burai Pál

3


Szállítási feladat

Burai Pál


Szállítási feladat, Lehetséges megoldás keresése

v1 = 0 2

v2 = 2 2 1

v3 = 3 3

u2 = 0

Minimális költség módszer

v4 = 2 0 4

3

2

1

1

Keressük meg a minimális szállítási költséget, válasszuk azt a mezőt, amelyiknek a legkisebb a sorindexe, ha egy sorban több ilyen van, akkor azok közül azt, amelyiknek legkisebb az oszlopindexe. Ennek a mezőnek adjuk a lehetséges maximális értéket és a megfelelő oszlopot vagy sort kinullázzuk.

2

Az értékkel még nem rendelkező mezőkre végezzük el az előző lépést addig, míg minden mezőnek értéket nem adunk.

3 3

3

5

4

u3 = 1

u1 = 1

Ha ui + vj ≤ cij minden indexpárra, akkor a tábla optimális. Ellenkezõ esetben a második lépés következik.

3

u3 = 0

u1 = 1

1

v4 = 3 4

u2 = −1

 0 0  2

(i, j) ∈ Γ

ui + vj = cij , u1 = 1

2  0 0



1

v1 = 0 2

v2 = 2 2 1

2 3

3

v3 = 2 3

u2 = −1

4 1

3

3

5

4

u3 = 0

Vogel módszer

v4 = 2 0

1

Minden sorhoz és oszlophoz számítsuk ki a két legkisebb szállítási költség különbségét (büntetések).

2

Válasszuk ki a legnagyobb számmal rendelkező sor vagy oszlop legkisebb szállítási költségű mezőjét, majd adjuk ennek a lehetséges legnagyobb értéket. A megfelelő sort vagy oszlopot nullázzuk ki, és az a vagy b vektor szóban forgó komponensét módosítsuk.

3

Számítsuk ki újra a sorok és oszlopok büntetését, kivéve a kinullázottakét, majd azBurai eljárást folytassuk addig míg lehetséges. Pál Operációkutatás előadáshoz segédanyag

3 2

2

1

3

3

3

Burai Pál


Szállítási feladat, Kiegyensúlyozatlan feladatok

Nemlineáris problémák, rövid kitekintés

Ha az összkínálat meghaladja az összkeresletet Ekkor vezessünk be egy fiktív keresleti pontot, melynek igénye megegyezik a túlkínálattal és ehhez rendeljünk nulla szállítási költséget.

Csak a feltétel nélküli eset. Legyen f : Rn → R adott függvény. Keressük a megoldását a következő feltétel nélküli optimalizálási feladatnak: min f (x)

Ha az összkínálat kevesebb, mint az összkereslet Ekkor vezessünk be egy fiktív kínálati pontot, majd az innen a j. keresleti helyre való szállítás költsége legyen a szóban forgó szállítási ponton keletkező kielégítetlen igényre vonatkozó büntetés.

Megjegyzés

x∈Rn

1

Első- másodrendű feltételek az optimalitásra.

2

Konvexitás.

3

Alapalgoritmus vázlata.

4

Csökkenési irány, lépésköz.

Mivel a hozzárendelési feladatokat is tekinthetjük speciális szállítási feladatnak, a fentiekhez hasonló módon azokat is megoldhatjuk, ha a feladat mátrixa nem n × n-es.

Burai Pál


Nemlineáris problémák, Jelölések, alapfogalmak

Burai Pál


Nemlineáris problémák, Numerikus módszerek a megoldás keresésére

Legyen f : Rn → R egy adott függvény, ekkor a

problémát feltétel nélküli optimalizálási feladatnak nevezzük. Ha adott egy M ⊂ Rn halmaz is, akkor a

A továbbiakban feltesszük, hogy az f : Rn → R függvény folytonosan differenciálható. A már említett (1) feltétel nélküli feladatot szeretnénk numerikusan megoldani. x )T s < 0. Az sRn vektor az f függvény x¯-beli csökkenési iránya, ha f 0 (¯

(2)

Egyenes menti keresés általános modellje

(1)

min f (x)

x∈Rn

min f (x)

x∈M

vagy rövidebben

vagy rövidebben

min f n R

min f M

problémát feltétes optimalizálási feladatnak nevezzük. A fenti jelölések mellett f az optimalizálási feladat célfüggvénye, míg M a megengedett megoldások halmaza. Azt mondjuk, hogy az f függvénynek lokális minimuma van az x¯ ∈ Rn pontban, ha létezik olyan pozitív ε valós szám, hogy (3)

f (¯ x ) ≤ f (x),

1

Válasszunk egy x 0 ∈ Rn kiinduló pontot. k = 0, 1, 2, . . . -re

2

Ha x k stacionárius pontja a függvénynek, akkor az algoritmus leáll. Egyébként a 3. lépés.

3

Válasszunk egy s k x k -beli csökkenési irányt és egy σk lépéstávolságot úgy, hogy az f (x k + σk s k ) − f (x k ) csökkenés "elegendõen" nagy legyen. Legyen x k+1 := x k + σk s k .

x ∈ Bε (¯ x )(∩M), 4

ahol Bε (¯ x ) az ε sugarú x¯ középpontú nyílt gömböt jelöli. Burai Pál


Burai Pál


Nemlineáris problémák, Gradiens módszer Tegyük fel, hogy f x-beli deriváltja nem tûnik el. Ekkor a min f 0 (x)T d

(4)

kdk=1

probléma megoldásának nemnegatív skalárszorosait f x-beli legmeredekebb csökkenési irányainak nevezzük.

Nemlineáris problémák, Armijo-szabály a lépésköz megválasztására Legyen adott β, γ ∈]0, 1[ (tipikus értékek: β = 0.5, γ = 0.01). Legyen σk a legnagyobb olyan {1, β, β 2 , . . . } halmazbeli elem, amelyre fennáll a következõ egyenlõtlenség. f (x k + σk s k ) − f (x k ) ≤ σk γf 0 (x k )T s k .

Állítás Az elõbbi feltételek mellett a (4) problémának pontosan egy d megoldása létezik, és −f 0 (x) d= 0 . kf (x)k

Állítás Legyen f : Rn → R folytonosan differenciálható az x pont egy környezetében, γ ∈]0, 1[ adott. Ha s f egy x-beli csökkenési iránya, akkor létezik olyan σ ¯ pozitív valós szám, hogy

Bizonyítás. A Cauchy-Schwarz egyenlõtlenségbõl tetszõleges egy normájú d vektor esetén kapjuk, hogy −f 0 (x)T d ≤ |−f 0 (x)T d | ≤ k−f 0 (x)kkd k = kf 0 (x)k ⇒ f 0 (x)T d ≥ kf 0 (x)k. Egyenlõség pedig pontosan akkor teljesül, ha a két vektor lineárisan függõ, azaz, d = λ(−f 0 (x)). Mivel d egységvektor, λ = kf 01(x)k , ami adja az állítást. Burai Pál


Nemlineáris problémák Gradiens módszer algoritmusa 1

Válasszunk egy x 0 ∈ Rn kiinduló pontot és két valós számot β, γ ∈]0, 1[. k = 0, 1, 2, . . . -re

2

Ha x k stacionárius pontja a függvénynek, akkor az algoritmus leáll. Egyébként a 3. lépés.

3

4

Legyen s k := f 0 (xk ), σk -t pedig válasszuk meg az Armijo-szabály szerint. Legyen x k+1 := x k + σk s k .

Állítás (A Gradiens módszer globális konvergenciája) Az elõbbi algoritmus vagy véges lépésben leáll f egy stacionárius pontjánál, vagy egy olyan sorozatot eredményez, melynek tagjain a függvény szigorúan monoton csökken és minden torlódási pontja stacionárius pontja f -nek. Burai Pál


f (x + σs) − f (x) ≤ σγf 0 (x)T s, Bizonyítás.

∀ σ ∈ [0, σ ¯ ].

Mivel s csökkenési irány

f (x + σs) − f (x) − γf 0 (x)T s → (1 − γ)f 0 (x)T s < 0. σ Burai Pál


Történeti bevezetés. Történeti bevezetés. Történeti bevezetés. Fourier-Motzkin elimináció lineáris egyenlőtlenségrendszerek megoldására

Recommend Documents