Nemlineáris optimalizálás

Dr. Házy, Attila

Új Széchenyi Terv logó.

Miskolci Egyetem

Kelet-Magyarországi Informatika Tananyag Tárház

Kivonat

Kivonat

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Lektor

Kósa Péter

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.


Tartalom

1. Bevezetés
2. Jelölések és alapfogalmak
2.1. Konvexitás, kvázikonvexitás
2.2. Definitség, feltételes definitéség
2.3. Differenciálhatóság
2.4. Karakterizációs tételek
2.5. Farkas lemma
2.6. Dualitás
2.7. Függvények szélsőértékei
2.8. Matematikai programozási (MP) feladat
2.9. Lineáris programozási (LP) feladat
2.10. Gráfelméleti fogalmak, jelölések
2.11. Gráfok ábrázolási módjai
2.11.1. Szomszédsági listás
2.11.2. Szomszédsági mátrixos
3. Általános nemlineáris optimalizálási feladat
3.1. Nemlineáris optimalizálási feladatok osztályozása
3.2. Kvadratikus függvények és szélsőértékeik
3.3. Egyenlőségi feltételek
3.4. Egyenlőtlenségi feltételek
3.5. A konvex optimalizálási feladat
3.6. Duális programozási feladatok
4. Minimumkereső eljárások
4.1. Egyváltozós függvények kereső eljárásai
4.1.1. Általános minimum kereső algoritmus
4.1.2. Dichotomous keresés
4.1.3. Aranymetszéses keresés
4.1.4. Fibonacci keresés
4.1.5. Parabola kereső eljárás
4.1.6. Newton módszer
4.2. Többváltozós függvények kereső eljárásai
4.2.1. A Newton-módszer
4.2.2. Módosított Newton-módszer
4.2.3. A Gill-Murray algoritmus
4.2.4. A Levenberg-Marquardt módszer
4.2.5. Trust region módszerek
4.2.6. Kvázi-Newton módszerek
4.2.7. Broyden módszer
4.2.8. BFGS (Broyden-Fletcher-Goldfarb-Shanno) eljárás
4.2.9. A vonalmenti minimalizálás algoritmusa
4.2.10. Armijo-Goldstein feltételek
4.2.11. Szögfeltétel
4.2.12. Iránykeresési módszerek
4.2.13. Gradiens módszer (Cauchy módszer, 1847)
4.2.14. Konjugált gradiens módszer (Fletcher, Reeves)
4.2.15. Newton-módszer vonalmenti minimalizálással
4.2.16. Módositott Newton-módszer vonalmenti minimalizálással
4.2.17. DFP (Davidon-Fletcher-Powell) eljárás
4.2.18. Hooke-Jeeves módszer
4.3. A büntetőfüggvény módszerek
5. A játékelmélet elemei
5.1. Bimátrix játékok
5.2. Mátrixjátékok
5.3. A játék alsó és felső értéke, a ”minimax” elv
5.4. Mátrixjátékok kevert bővítése
5.4.1. A mátrixjáték és a lineáris programozás kapcsolata
6. Egészértékű lineáris programozási (ILP) feladat
6.1. Egészértékű optimalizálási modellek
6.1.1. Befektetési modellek
6.1.2. Transzformálás 0-1 programozási feladattá
6.1.3. Hátizsák feladat
6.1.4. Halmazlefedési, halmazfelbontási és halmazkitöltési feladatok
6.2. Integer lineáris programozási feladatok megoldási módszerei
6.2.1. Integer és folytonos lineáris programozás kapcsolata
6.2.2. A korlátozás és szétválasztás módszer (Branch and Bound)
6.2.3. Vágási módszerek
7. Gráfelméleti algoritmusok
7.1. A szélességi keresés
7.2. A mélységi keresés
7.3. Minimális feszítőfa
7.3.1. Kruskal-algoritmus
7.3.2. Prim-algoritmus
7.4. Legrövidebb utak
7.5. Adott csúcsból induló legrövidebb utak
7.5.1. Bellman-Ford algoritmus
7.5.2. Dijkstra algoritmusa
7.6. Legrövidebb utak minden csúcspárra
7.6.1. A Floyd-Warshall-algoritmus
8. Feladatok
Irodalomjegyzék

1. fejezet - Bevezetés

Optimalizálási feladat számos helyen előfordul. A legrégebbi ilyen típusú feladatok a következőek:

  • Izoperimetrikus probléma. Adott hosszúságú síkbeli zárt görbék közül határozzuk meg azokat, amelyek által bezárt terület maximális.

  • Dido első problémája. Adott hosszúságú, egy zárt félsíkban haladó görbék közül határozzuk meg azokat, amelyek végpontjai a félsík határoló egyenesén vannak, és amelyek ezzel az egyenessel maximális területet zárnak be.

  • Dido második problémája. Adott hosszúságú, egy zárt félsíkban haladó és a félsík határoló egyenesének előírt pontjában kezdődő és végződő görbék közül határozzuk meg azokat, amelyek ezzel az egyenessel maximális területet zárnak be.

  • Euklidesz feladata. Adott háromszögbe írjunk maximális területű paralelogrammát.

Manapság például azt kell meghatároznunk, hogy hogyan lehet az egyik városból egy másik városba a legrövidebb úton (leghamarabb) eljutni. A lineáris programozás feladata gazdasági jelentőséggel is bír. Például tegyük fel, hogy egy üzem -féle alapanyagból különböző terméket gyárt. Legyen az üzem technológiai mátrixa: az mátrix eleme azt a nyersanyag mennyiséget jelenti, amely az -edik anyagból a -edik termék egy egységének előállításához kell. Az -edik nyersanyagból mennyiség (kapacitás) áll rendelkezésre.

A

vektort kapacitásvektornak nevezzük. Ha jelöli az -edik termékből gyártott mennyiséget, akkor az

vektort termelési programnak nevezzük. Az termelési program anyagszükséglete . Az termelési programot lehetségesnek nevezzük, ha

Ha a -edik termék ára és

akkor az termelési programhoz tartozó árbevétel

Ha az árbevétel maximalizálása a cél, akkor az alábbi lineáris programozási feladatot kapjuk:

2. fejezet - Jelölések és alapfogalmak

Ebben a fejezetben néhány, a későbbiekben felhasználásra kerülő, jelölést és fogalmat gyűjtünk össze.

2.1. Konvexitás, kvázikonvexitás

Az halmazt konvexnek nevezzük, ha tetszőleges két pontjával együtt az azokat összekötő szakaszt is tartalmazza azaz, minden és esetén .

A vektor az pontok lineáris kombinációja. Tetszőleges pontok konvex kombinációját a következőképpen definiálhatjuk:

2.1. Definíció. Legyenek olyan pozitív számok, melyre

Ekkor az

vektor az adott pontok konvex kombinációja.

2.1. Példa. Példák Konvex és konkáv halmazokra:

Konvex halmazok

Konkáv halmazok

2.2. Definíció. Az függvény konvex, ha minden és esetén

Az függvény szigorúan konvex, ha minden és esetén

Az függvény (szigorúan) konkáv, ha (szigorúan) konvex.

Ez a definíció ekvivalens módon megfogalmazható a következőképpen is:

2.3. Definíció. Az függvény konvex, ha

ahol

Az függvény szigorúan konvex, ha

Szükségünk lesz ezen klasszikus függvénytípusok következő általánosítására is:

2.4. Definíció. Az függvény kvázikonvex, ha minden és esetén

Az függvény szigorúan kvázikonvex, ha minden és esetén

Az függvény (szigorúan) kvázikonkáv, ha (szigorúan) kvázikonvex.

Ez a definíció valós esetben megfogalmazható alsó és felső nívóhalmazok segítségével is.

2.5. Definíció. Legyen egy intervallum és . Az függvényt kvázikonvexnek mondjuk, ha az

alsó nívóhalmazok minden mellett konvexek. Hasonlóan: az függvényt kvázikonkávnak nevezzük, ha az

felső nívóhalmazok minden mellett konvexek.

A konvex függvények az értelmezési tartomány belsejében folytonosak, a kvázikonvexitásból viszont nem következik a folytonosság. Erre példa lehet tetszőleges szakadásos monoton függvény, például a sgn .

2.2. Példa. A következő ábrákon konvex, szigorúan konvex, kvázikonvex és szigorúan kvázikonvex függvények láthatóak.

(a)

(b)

(c)

(d)

(e)

(f)

 

(g)

 

Az ábrán egy szigorúan konvex, a és ábrákon látható függvények konvexek, a és szigorúan kvázikonvex függvényeket mutat, végül az és függvények kvázikonvexek.

2.6. Definíció. Egy . Az függvény epigráfja

halmaz.

Epigráf -ben

Egy konvex halmazon értelmezett függvény akkor es csak akkor konvex, ha epigráfja konvex halmaz.

Egy halmaz affin burkán az őt tartalmazó legszűkebb lineáris sokaságot értjük, jele .

Legyen , az pont benne van relatív belsejében ha létezik olyan pozitív valós szám, hogy . relatív belsejében lévő pontok halmazát -val jelöljük.

2.2. Definitség, feltételes definitéség

Jelöljön egy tetszőleges normát és jelöljük az Az -edrendű egységmátrixot , vagy -nel. Egy mátrix szimmetrikus, ha , ferdén szimmetrikus, ha .

2.7. Definíció. Az mátrix pozitív (negatív) definit, ha

Az mátrix pozitív (negatív) szemidefinit, ha

Az mátrix indefinit, ha nem tartozik a fenti kategóriák egyikébe sem.

Adunk két példát konvex függvényekre, amely a későbbiekben fontosak lesznek számunkra:

2.3. Példa. Legyen szimmetrikus valós mátrix, és . Az

kvadratikus függvény akkor és csak akkor konvex, ha a mátrix pozitív szemidefinit.

2.4. Példa. Legyen és . Az

lineáris függvény konvex és egyúttal konkáv is. Ez utóbbi triviális, mert minden és minden esetén fennáll, hogy

Könnyen látható, hogy egy mátrix akkor és csak akkor negatív definit, ha pozitív definit. Legyen és jelölje

az mátrix -adik főminor mátrixát (). Ekkor igazak a következő tételek.

2.8. Tétel. Egy szimmetrikus mátrix akkor és csak akkor pozitív definit, ha

Egy szimmetrikus mátrix akkor és csak akkor negatív definit, ha

2.9. Tétel. Egy szimmetrikus mátrix akkor és csak akkor pozitív (negatív) definit, ha minden sajátértéke pozitív (negatív) valós szám.

2.10. Tétel. Egy szimmetrikus mátrix akkor és csak akkor pozitív definit, ha az -felbontásban (ahol egység alsó, felső háromszögmátrix) az mátrix diagonális elemei mind pozitívak.

2.11. Definíció. Legyen szimmetrikus mátrix, pedig egy típusú valós mátrix, amelynek rangja maximális, azaz . Az mátrix feltételesen pozitív definit a -re nézve, ha

feltételesen pozitív szemidefinit, ha

feltételesen negatív definit, ha

feltételesen negatív szemidefinit, ha

2.12. Megjegyzés. A homogén lineáris egyenletrendszer általános megoldása megadható alakban, ahol , és . Ezért és a feltételes definitség a redukált kvadratikus alak

feltétel nélküli definitségét jelenti.

2.13. Tétel. [Főminor teszt feltételes pozitív/negatív definitségre] Tekintsük a szimmetrikus mátrixot. Konstruáljuk meg a mátrixokat az alábbi módon:

ahol az mátrix első sora és első oszlopa (az mátrix -adik főminor mátrixa), a mátrix első oszlopa.

Az mátrix feltételesen pozitív definit a mátrixra nézve akkor és csak akkor, ha

Az mátrix feltételesen negatív definit a mátrixra nézve akkor és csak akkor, ha

2.3. Differenciálhatóság

Az egyváltozós valós függvény differenciálhatósága jól ismert fogalom, mi szerint akkor mondjuk, hogy az függvény az pontban differenciálható, ha létezik az alábbi határérték és az véges

vagy szokás az előzővel ekvivalens definíció is használni

A határértéket differenciálhányadosnek, vagy deriváltnak nevezik és szimbólummal jelölik.

Az utóbbi formula egyszerűen általánosítható többváltozós függvényekre ezt nevezzük iránymenti deriváltnak. Viszont egyik formula sem alkalmas a többváltozós függvény differenciálására. Amennyiben az első formulát átírjuk az

alakra, akkor az függvény pontbeli differenciálhatósága az alábbiak szerint fogalmazható át:

Az függvény differenciálható az pontban, ha létezik egy véges valós szám és egy függvény úgy, hogy

ahol .

Sokszor a második formula átírását használjuk, amely szerint Az függvény differenciálható az pontban, ha létezik egy véges valós szám és egy függvény úgy, hogy

ahol .

A következő fogalom amit bevezetünk az Iránymenti derivált fogalma. Legyen egy nemüres halmaz és legyen függvény. Legyen és legyen olyan vektor, hogy elegendően kicsi valós számra. Az függvénynek az pontban a irány mentén vett iránymenti deriváltjának nevezzük és -vel jelöljük az alábbi határértéket, ha létezik:

Az iránymenti derivált az függvénynek a változását méri a irányban. A irány elvileg bármilyen vektor lehet, a változás mérése azonban csak akkor lesz hasonló az egyváltozós esethez, ha a irányvektor hossza egy.

A differenciálhatóság fogalma:

Legyen egy nemüres halmaz, legyen függvény. Az függvényt differenciálhatónak mondunk az halmaz egy belső pontjában, ha létezik egy vektor és egy függvény úgy, hogy

ahol .

2.14. Megjegyzés. A későbbiekben általában úgy használjuk a differenciálhatósági összefüggést, hogy az helyébe -et, helyébe pedig vektort írunk, ekkor az alábbi formulát használjuk:

minden vektorra és valós számra. A formulában szereplő határérték az alábbiak szerint alakul, .

Az alábbiakban a vektort vizsgáljuk. Kimondjuk az iránymenti derivált és a vektor kapcsolatára vonatkozó tételt.

2.15. Tétel. Legyen differenciálható függvény és legyen a irányvektor egységhosszúságú. Ekkor az iránymenti derivált megegyezik a vektor és az egységhosszúságú irányvektor skaláris szorzatával, azaz

Bizonyítás. Induljunk ki a

differenciálhatósági összefüggésből. Átrendezés, határérték képzés után adódik, hogy

A baloldal pedig definíció szerint az iránymenti derivált.

A következő tétel mutatja, hogy a vektor a parciális deriváltak vektora.

2.16. Tétel. Legyen differenciálható függvény. A vektor elemei az függvény parciális deriváltjai, azaz

Bizonyítás. Alkalmazzuk az előző tételt az -edik egységvektorokra:

A baloldal:

amely definíció szerint az függvény -edik parciális deriváltja. A jobboldal pedig a vektor -edik koordinátája. Ebből azonnal következik a tétel állítása.

A következő tételben összefoglaltuk a gradiens vektor fontosabb tulajdonságait.

2.17. Tétel. Legyen differenciálható függvény. Ekkor

a) vektor az függvény legnagyobb növekedési irányát jelöli ki,

b) értéke az függvény legnagyobb növekedésnek mértékét adja,

c) vektor az szintfelület normálisa, azaz az függvény pontbeli érintősíkjára merőleges.

Bizonyítás. a) Az

alapképletet használva a jobboldalon lévő skaláris szorzat akkor a legnagyobb, ha a irányvektor párhuzamos a vektorral, tehát a gradiens vektor az függvény legnagyobb növekedési irányába mutat.

b) Ha az irányvektor a gradiens vektor irányába mutató egység hosszúságú vektor, azaz , akkor , amelyből nyilvánvaló az állítás.

c) Az alapképlet szerint, ha a gradiens vektor merőleges az irányvektorra, akkor az függvény ebben az irányban nem változik. Ez az irány nem más mint az ponton áthaladó szintfelület normálisa.

Most a kétszer differenciálhatóság fogalma-val foglalkozunk. Legyen egy nemüres halmaz, legyen függvény. Az függvényt kétszer differenciálhatónak mondunk az halmaz egy belső pontjában, ha létezik egy vektor, egy -es szimmetrikus mátrix és egy függvény úgy, hogy

minden -re, ahol .

2.18. Definíció. A mátrixot Hesse mátrixnak nevezzük, elemei az függvény másodrendű parciális deriváltjai, azaz

más szóval úgy is mondhatjuk, hogy a Hesse mátrix -edik sora a gradiens vektor -edik koordinátájának, mint valós függvénynek a gradiense. A Hesse mátrixot nagyon gyakran vagy szimbólummal jelöljük.

2.19. Megjegyzés.

Hasonlóan az előző megjegyzéshez, itt is gyakran használatos az alábbi formula:

minden vektorra és valós számra. A formulákban szereplő határérték az alábbiak szerint alakul, .

A differenciálhatóságot mint láttuk egy belső pontban definiáltuk. Az függvényt differenciálhatónak mondunk az halmazon, ha az függvény az halmaz minden belső pontjában differenciálható. Ez természetesen a kétszer differenciálhatóságra is vonatkozik.

A definícióból könnyen észrevehetjük, hogy kétszer folytonosan differenciálható függvények Hesse-mátrixa szimmetrikus.

2.20. Definíció. Az

vektor-vektor függvény gradiensén az

előírással megadott -es mátrixot értjük.

2.4. Karakterizációs tételek

2.21. Tétel. [Karakterizációs tétel, egyváltozós konvex függvényekre] Legyen nemüres konvex halmaz, legyen konvex függvény. Legyen és legyen olyan, hogy . Legyen , ahol . Az függvény akkor és csak akkor konvex, ha a egyváltozós függvény konvex.

A következő tétel azt mutatja, hogy a konvex függvények olyanok, hogy mindig az érintő felett haladnak.

2.22. Tétel. [Karakterizációs tétel differenciálható konvex függvényre] Legyen egy nemüres nyílt konvex halmaz és legyen differenciálható függvény az halmazon. Ekkor az függvény akkor és csak akkor konvex, ha bármely pontra

Bizonyítás. Első lépésként legyen egy konvex függvény. Ekkor

Ebből kapjuk, hogy

A határátmenetet felhasználva az pontban az irány szerinti iránymenti derivált adódik, innen kapjuk, hogy

amelyből rendezés után a bizonyítandó összefüggés adódik.

Második lépésként induljunk ki abból, hogy az függvényre bármely és esetén teljesül a tételbeli egyenlőtlenség, azaz

Az definíciójából könnyen látható, hogy

Ezt az előző egyenlőtlenségekbe behelyettesítve ezeket, majd -val és -val beszorozva és a két egyenlőtlenséget összeadva, kapjuk, hogy

amely a konvex függvény definíciójával azonos.

Az előző tételt nemdifferenciálható konvex függvények esetén úgy lehet módosítani, hogy a nemlétező gradiens vektor helyett a szubgradiens-t használjuk.

2.23. Definíció. [Szubgradiens definíciója] Legyen egy nemüres konvex halmaz, legyen konvex függvény és . A vektort az függvény pontbeli szubgradiensének nevezzük, ha

A következő tétel azt mutatja, hogy konvex halmaz esetén a szubgradiens pontosan megegyezik a gradiens vektorral.

2.24. Tétel. [a szubgradiens és a gradiens kapcsolata] Legyen egy nemüres konvex halmaz és legyen konvex függvény. Tegyük fel, hogy az függvény differenciálható az halmaz egy belső pontjában. Ekkor az függvény pontbeli szubgradienseiből álló halmaznak egyetlen eleme van és ez a .

2.25. Tétel. [karakterizációs tétel differenciálható konvex függvényre] Legyen egy nemüres nyílt konvex halmaz és legyen differenciálható függvény az halmazon. Ekkor az függvény akkor és csak akkor konvex, ha bármely pontra

2.26. Tétel. [karakterizációs tétel kétszer differenciálható konvex függvényre] Legyen egy nemüres nyílt konvex halmaz és legyen kétszer differenciálható függvény az halmazon. Ekkor az függvény akkor és csak akkor konvex, ha az függvény Hesse mátrixa pozitív szemidefinit minden pontban.

2.27. Tétel. [Karakterizációs tétel, differenciálható kvázikonvex függvényre] Legyen egy nemüres nyílt konvex halmaz és legyen differenciálható függvény az halmazon. Ekkor az függvény akkor és csak akkor kvázikonvex, ha bármely esetén, melyekre teljesül, hogy igaz, hogy

2.28. Tétel. [Karakterizációs tétel, kétszer differenciálható kvázikonvex függvényre]

Legyen egy nemüres nyílt konvex halmaz és legyen kétszer differenciálható függvény az halmazon. Ekkor az függvény akkor és csak akkor kvázikonvex, ha az függvény Hesse mátrixa minden pontban feltételesen pozitív szemidefinit minden vektorra nézve.

2.5. Példa. Tekintsük az alábbi kétváltozós függvényt. Állapítsuk meg, hogy függvény kvázikonvex vagy kvázikonkáv!

ahol egy tetszőleges valós szám.

Megoldás:

A függvény kétszer differenciálható, a függvény gradiens vektora és a Hesse mátrixa az alábbiak szerint írható:

A Hesse mátrix indefinit, így sem nem konvex sem nem konkáv a függvény. A Hesse mátrix determinánsa

A főminor teszt szerint akkor lenne konvex vagy konkáv a függvény, ha minden vektorra a második főminor, vagyis a Hesse mátrix determinánsa pozitív lenne, de ez nincs így. Most nézzük meg lehet-e a függvény kvázikonvex vagy kvázikonkáv. Ez esetben a tétel alapján azt kellene megvizsgálni, hogy a Hesse mátrix feltételesen pozitív vagy negatív definit. A feltételes definitség, mint korábban láttuk, a szegélyezett mátrix segítségével dönthető el. Képezzük a szegélyezett Hesse mátrixot, amelynél a szegélyt a gradiens vektor adja.

A főminor teszt segítségével fogjuk eldönteni a definitséget. Mivel esetünkben , így csak esetében kell determinánst számolni, amely valójában a szegélyezett Hesse mátrix determinánsa. Ez a determináns:

Két eset van. Ha pozitív, akkor a determináns minden vektorra negatív. Így azt kapjuk, hogy -re, így a főminor teszt alapján a Hesse mátrix feltételesen pozitív definit. Ez pedig a fenti tétel értelmében az jelenti, hogy a példabeli függvény kvázikonvex.

Ha negatív, akkor akkor a determináns minden vektorra pozitív. Így azt kapjuk, hogy -re, így a főminor teszt alapján a Hesse mátrix feltételesen negatív definit. Ez pedig a fenti tétel értelmében az jelenti, hogy a példabeli függvény kvázikonkáv.

2.5. Farkas lemma

A Farkas tételt szokás Farkas lemmaként is emlegetni. Ez a tétel nagyon fontos szerepet játszik az optimalizálásban, a lineáris és nemlineáris programozás optimalitási feltételeinek meghatározásában. A lemma bizonyításához szükségünk lesz a következő szeparációs tételre.

2.29. Tétel. Legyen nemüres zárt konvex halmaz és . Ekkor létezik olyan vektor és , hogy

A tétel azt fejezi ki, hogy létezik egy hipersík ( a hipersíkra merőleges vektor), amely szeparálja (elválasztja) a pontot és a halmazt, azaz a hipersík által meghatározott félterek közül az egyikben van a pont, a másik féltérben pedig a halmaz minden eleme. Ezek után kimondhatjuk a Farkas lemmát.

2.30. Lemma. Legyen adott egy -es mátrix és egy elemű vektor. Ekkor az alábbi két rendszer közül pontosan egyiknek van megoldása:

Bizonyítás. Először tegyük fel, hogy a baloldali rendszernek van megoldása, azaz létezik olyan , hogy . Indirekt tegyük fel, hogy a jobboldali rendszernek is van megoldása, ekkor , ami ellentmond annak, hogy . Tehát ha a baloldali rendszernek van megoldása, akkor a jobboldali rendszernek nincs.

Most tegyük fel, hogy a baloldali rendszernek nincs megoldása. Konstruáljuk meg az alábbi halmazt a következőképpen:

Ez az nemüres zárt konvex halmaz és mivel a feltevésünk szerint a baloldali rendszernek nincs megoldása, így . Ekkor az előző tétel (pont és konvex halmaz szeparációja) szerint létezik egy () vektor és skalár úgy, hogy és minden vektorra. Mivel , így , amiből . Továbbá , ebből pedig adódik, hogy minden vektorra. A akkor és csak akkor lehet kisebb vagy egyenlő egy nem negatív számnál minden esetén, ha minden . Amennyiben ugyanis valamelyik lenne, akkor megadható lenne egy olyan , hogy . Összefoglalva tehát ha a baloldali rendszernek nincs megoldása, akkor a jobboldali rendszernek van megoldása, azaz létezik olyan vektor, hogy .

2.6. Dualitás

Legyen adott függvény, ekkor a

függvényt első konjugáltjának nevezzük.

2.31. Lemma. Legyen tetszőleges függvény, ekkor konvex és zárt.

Bizonyítás. Legyen , ekkor affin, azaz konvex és zárt függvény. Másrészt, ilyeneknek a pontonkénti szuprémuma, így is konvex és zárt.

A

függvényt pedig második konjugáltjának nevezzük.

2.32. Megjegyzés. Az előző tételhez hasonlóan bizonyítható, hogy is konvex, zárt függvény.

2.33. Tétel. [Fenchel-Moreau tétel]

Legyen . Ekkor a következő állítások ekvivalensek:

  1. konvex és zárt;

  2. ;

  3. az olyan affin függvények pontonkénti szuprémuma, melyek pontonként nem nagyobbak nála.

Bizonyítás. Ha , akkor készen vagyunk. Tegyük fel, hogy . Legyen tetszőleges és . Ekkor , így a szeparációs tétel miatt létezik olyan vektor, hogy

Mivel , az előző egyenlőtlenségből kapjuk, hogy

azaz

Ebből .

eset: . Ekkor , ezért feltehető, hogy . Ekkor

Mivel minden esetén, az második egyenlőtlenségből kapjuk, hogy

minden esetén. Ekkor a affin függvényre a korábbiak miatt teljesülnek a következő egyenlőtlenségek:

Mivel tetszőleges volt, kapjuk az állítást esetén.

eset: .

Az előző eset előtti gondolatmenet működik. Ha , akkor a bizonyítás ugyanúgy megy. Ha , akkor a 2.6 alatti egyenlőtlenségek a következő alakot öltik:

Az előző rész miatt létezik olyan affin függvény , amelyik nem nagyobb -nél. Tetszőleges esetén legyen . Ekkor az előző két egyenlőtlenség miatt elegendően nagy esetén tetszőlegesen nagy lehet, de is teljesül minden -re.

Ekkor létezik olyan és , hogy , ebből , másrészt affin függvények szuprémuma, így

Itt kihasználtuk azt is, hogy sehol sem , mert .

Mivel konvex, zárt függvény a definíciója miatt, így is az.

2.7. Függvények szélsőértékei

Első lépésként definiáljuk a környezet fogalmát.

2.34. Definíció. Az

halmazt az pont körüli sugarú nyílt gömbi környezetnek nevezzük.

Ebben a fejezetben összefoglaljuk az egy- és többváltozós függvények szélsőértékeivel kapcsolatos alapvető definíciókat és eredményeket.

2.35. Definíció. Legyen adott egy vektor-skalár függvény (). Az pont az függvény globális minimumhelye, ha

és globális maximumhelye, ha

2.36. Definíció. Legyen adott egy vektor-skalár függvény (). Az pont az függvény lokális minimumhelye, ha létezik szám, hogy

és lokális maximumhelye, ha

A minimum-, vagy maximumhelyre egyaránt az extremális pont elnevezéssel utalunk.

2.6. Példa. Az függvénynek egyetlen minimumhelye van: , amit az alábbi ábra is mutat:

2.37. Definíció. Egy minimumhelyet szigorúnak nevezzük, ha egy számra fennáll, hogy

Egy maximumhelyet szigorúnak nevezzük, ha egy számra fennáll, hogy

Ha egy minimumhely nem szigorú (erős), akkor gyenge minimumhelynek is hívjuk. Az előző példa minimumhelye szigorú minimum. Az függvénynek az egyenes bármely pontja gyenge minimumhelye.

Ismertek a következő eredmények:

2.38. Tétel. Legyen egy függvény. Ha és extremális pont, akkor .

2.39. Tétel. Legyen egy függvény. Ha és minimumhely (maximumhely), akkor és ().

2.40. Tétel. Legyen egy függvény. Ha és teljesül, hogy (), akkor az függvény minimumhelye (maximumhelye).

2.41. Tétel. Legyen egy vektor-skalár függvény. Ha és extremális pont, akkor

A feltételt stacionárius egyenletnek (egyenletrendszernek) nevezzük.

2.42. Tétel. Legyen egy vektor-skalár függvény. Ha és minimumhely (maximumhely), akkor

és a

Hesse-mátrix pozitív (negatív) szemidefinit.

2.43. Tétel. Legyen egy vektor-skalár függvény. Ha , és a Hesse-mátrix pozitív (negatív) definit, akkor az pont minimumhely (maximumhely).

A () egyenlet megoldásait, amelyeket az optimalizálásban stacionárius pontoknak nevezünk, az függvény kritikus pontjainak is szokás hívni. Mi csak olyan kritikus pontokkal foglalkozunk, amelyek nem degeneráltak, azaz .

Megmutatható, hogy csak olyan nemdegenerált kritikus (stacionárius) pontok léteznek, amelyekben a Hesse-mátrixnak pozitív és negatív sajátértéke van (). Ha , akkor negatív definit (maximumhely), ha , akkor pozitív definit (minimumhely), a esetben nyeregpontról beszélünk. Nyeregpontban nincs szélsőérték.

Degenerált kritikus pontokban elvileg lehet szélsőérték ám ennek vizsgálata általában nem egyszerű.

2.7. Példa. Határozzuk meg az függvény szélsőértékeit és nyeregpontjait! Az

stacionárius egyenletből könnyen kapjuk, hogy az és értékekkel képezett darab pontpár adja a függvény kritikus pontjait. Minthogy

behelyettesítéssel könnyen megkaphatjuk, hogy az pontban lokális minimuma van, az pontban lokális maximuma van, míg az és a pontokban inflexiós (nyereg) pontja van.

2.8. Példa. Vizsgáljuk az függvény extremális pontjait! Itt , amiből adódik, hogy A Hesse-mátrix ebben az esetben:

Ez a mátrix indefinit (azaz se nem pozitív, se nem negatív definit), így a pont nyeregpont. A -et nyeregfelületnek nevezzük.

Következő lépésben felírjuk az vektor-skalár függvény Taylor-sorát.

2.44. Definíció. Az vektor-skalár függvény Taylor-sorát az

összefüggéssel adjuk meg, ahol , és

Ebből az általános formulából nekünk két speciális esetre (lineáris, kvadratikus) lesz szükségünk. Először, a közelítés pontosságának megállapításához definiálnunk kell az (ordó) nagyságrend fogalmát.

2.45. Definíció. , ha létezik egy olyan konstans, hogy .

2.46. Definíció. Az függvény lineáris közelítése:

A közelítés hibája , ha .

Az

függvény az függvény pontbeli érintősíkját adja meg.

2.47. Definíció. Az függvény kvadratikus közelítése (érintő paraboloidja):

A kvadratikus közelítés hibája , ha .

2.9. Példa. Tekintsük az függvény lineáris és kvadratikus közelítéseit az helyen!

Megoldás:

és

Az -t behelyettesítve kapjuk, hogy , és

Ez alapján a lineáris közelítés alakja , míg a kvadratikus közelítés alakja . Az függvény és kvadratikus közelítésének képét mutatják a következő ábrák:

2.8. Matematikai programozási (MP) feladat

A matematikai programozási feladatot a következőképpen definiáljuk.

Meghatározandó az vektor, amely minimalizálja az

függvényt az alábbi feltételek mellett

ahol az a döntési változó vektor, az

változós valós függvények, amelyeket rendre célfüggvénynek, egyenlőtlenséges ill. egyenlőséges feltételi függvényeknek nevezünk. Az halmaz pedig nyílt halmaz. Számos problémában és , az ilyen feladatot feltétel nélküli optimalizálási feladatnak nevezzük. Egyéb problémákat pedig feltételes optimalizálási feladatnak nevezünk.

2.9. Lineáris programozási (LP) feladat

A legegyszerűbb feltételes optimalizálási feladatban a célfüggvény és a feltételi függvények a döntési változónak lineáris függvényei, ezt az optimalizálási problémát lineáris programozási feladatnak nevezzük. A lineáris programozási feladat standard formája a következő:

Skalár formában:

Minimalizálandó a

a következő feltételek mellett

Mátrix-vektor formában:

ahol ismert konstans mátrix ill. vektorok, pedig a döntési változó vektor. A a és az vektorok skaláris szorzatát jelöli. Néha, ahol nem zavaró, ott az egyszerűség kedvéért a jelölést használjuk, vagy a jelölés is elfogadott.

2.10. Gráfelméleti fogalmak, jelölések

2.48. Definíció. Legyen egy véges halmaz, pedig -beli rendezetlen elempárok véges rendszere. Ekkor a párt gráfnak nevezzük.

Vezessük be a következő jelöléseket egy gráf esetében:

  • (csúcsok száma)

  • (élek elemszáma)

Egy gráf nagyon sok probléma szemléltetésére szolgálhat, a legegyszerűbb például az úthálózat, telefonhálózat, de akár házassági problémát is ábrázolhatunk vele.

A gráfokat többféle szempontból is szokás csoportosítani. A legjelentősebb szempont az irányítottság.

2.49. Definíció. A rendezett párt irányított gráfnak (digráfnak) nevezzük. A rendezett pár elemeire tett kikötések:

véges halmaz, a -beli csúcsok halmaza.

bináris reláció a halmazon, az élek halmaza.

={ rendezett pár | } . Hurkok megengedettek.

Hurok az él.

2.50. Definíció. A rendezett párt irányítatlan gráfnak nevezzük. A rendezett pár elemeire tett kikötések:

véges halmaz, a -beli csúcsok halmaza.

bináris reláció a halmazon, az élek halmaza.

={ rendezett pár | } . Hurok nem megengedett.

Mint ahogy már fentebb utaltunk rá, a csúcsok közötti kapcsolat sokszor jelentheti út létezéset vagy kommunikáció lehetőséget. Ilyenkor gyakran költségek vagy súlyok tartoznak az élekhez, amelyek az út esetében időt vagy akar pénzt is jelenthetnek (gondoljunk csak az autópályákra, amelyek használatáért fizetni kell).

2.51. Definíció. Az a gráf (irányított vagy irányítatlan), amelynek minden éléhez egy számot (súlyt) rendelünk hozzá, hálózatnak (súlyozott gráfnak) nevezzük.

2.52. Megjegyzés. A súlyt rendszerint egy súlyfüggvény segítségével adunk meg: , egy él súlya .

Az ilyen gráfok sok helyen előfordulnak, például optimalizálási feladatokban, mint az utazó ügynök probléma. Az élhez rendelt érték lehet az él költsége, súlya vagy hossza az alkalmazástól függően.

2.53. Definíció. A gráf egymáshoz csatlakozó éleinek olyan sorozatát, amely egyetlen ponton sem megy át egynél többször, útnak nevezzük.

2.54. Definíció. Legyen adott egy irányított vagy irányítatlan gráf a élsúlyokkal. A gráf egy -ból -be menő útjának hossza az úton szereplő élek súlyának összege.

2.11. Gráfok ábrázolási módjai

Két módszert szokás használni egy gráf ábrázolására: az egyikben szomszédsági listákkal, a másikban szomszédsági mátrixszal adjuk meg a gráfot.

Rendszerint a szomszédsági listákon alapuló ábrázolást választják, mert ezzel ritka gráfok tömören ábrázolhatók.

2.55. Definíció. Egy gráfot ritkának nevezünk, ha sokkal kisebb, mint .

Ugyanakkor a csúcsmátrixos ábrázolás előnyösebb lehet sűrű gráfok esetén, vagy ha gyorsan kell eldönteni, hogy két csúcsot összeköt-e él.

2.56. Definíció. Egy gráfot sűrűnek nevezünk, ha megközelíti -et.

2.11.1. Szomszédsági listás

szomszédsági listás ábrázolása során egy tömböt használunk. Ez darab listából áll, és az tömbben minden csúcshoz egy lista tartozik. Minden csúcs esetén az szomszédsági lista tartalmazza az összes olyan csúcsot, amelyre létezik él. Azaz: elemei az csúcs -beli szomszédjai. (Sokszor nem csúcsokat, hanem megfelelő mutatókat tartalmaz a lista.) A szomszédsági listákban a csúcsok sorrendje rendszerint tetszőleges.

Ha irányított gráf, akkor a szomszédsági listák hosszainak összege , hiszen egy élt úgy ábrázolunk, hogy -t felvesszük az listába. Ha irányítatlan gráf, akkor az összeg , mert irányítatlan él ábrázolása során -t betesszük szomszédsági listájába, és fordítva. Akár irányított, akár irányítatlan a gráf, a szomszédsági listás ábrázolás azzal a kedvező tulajdonsággal rendelkezik, hogy az ábrázoláshoz szükséges tárterület .

A szomszédsági listákat könnyen módosíthatjuk úgy, hogy azokkal súlyozott gráfokat ábrázolhassunk. Például, legyen súlyozott gráf súlyfüggvénnyel. Ekkor az él súlyát egyszerűen a csúcs mellett tároljuk szomszédsági listájában. A szomszédsági listás ábrázolás könnyen alkalmassá tehető sok gráfváltozat reprezentálására.

A szomszédsági listás ábrázolás hátránya, hogy nehéz eldönteni szerepel-e egy él a gráfban, hiszen ehhez az szomszédsági listában kell -t keresni. Ez a hátrány kiküszöbölhető csúcsmátrix használatval, ez azonban aszimptotikusan növeli a szükséges tárterület méretét.

2.11.2. Szomszédsági mátrixos

Ha egy gráfot szomszédsági mátrixszal (vagy más néven csúcsmátrixszal) ábrázolunk, feltesszük, hogy a csúcsokat tetszőleges módon megszámozzuk az 1,2, ... , értékekkel. A ábrázolásáhz használt csúcsmátrix mérete , és

A csúcsmátrix tárterületet foglal el, függetlenül a gráf éleinek számától. Gyakran kifizetődő a csúcsmátrixból csak a főátlóban és az efölött szereplő elemeket tárolni, ezzel majdnem felére csökkenthetjük az ábrázoláshoz szükséges tárterület méretét.

A szomszédsági listás ábrázoláshoz hasonlóan csúcsmátrixokkal is reprezentálhatunk súlyozott gráfokat. Ha súlyozott gráf súlyfüggvénnyel, akkor az él súlyát a csúcsmátrix sorában és oszlopában tároljuk. Nem létező él esetén a mátrix megfelelő elemét nil-nek választjuk, noha sokszor célszerű ehelyett 0 vagy végtelen értéket használni.

A szomszédsági listák együttesen aszimptotikusan kevesebb tárterületet igényelnek, mint a csúcsmátrix, azonban a használat során hatékonyságban ugyanennyivel elmaradnak attól, így ha a gráf mérete nem túl nagy, akkor kedvezőbb a hatékonyabb és egyszerűbb csúcsmátrixos ábrázolást használni. Ha a gráf nem súlyozott, akkor a csúcsmátrixos ábrázolás tovább javítható. Ebben az esetben a mátrix elemei lehetnek bitek, így jelentősen csökkenthetjük a szükséges tárterület méretét.

3. fejezet - Általános nemlineáris optimalizálási feladat

Az általános nemlineáris optimalizálási feladat (Nonlinear Optimization NLO) a következőképpen írható fel:

ahol , és A

korlátozást egyenlőségi feltételeknek, a

korlátozást pedig egyenlőtlenségi feltételeknek nevezzük. Ha nincs semmilyen korlátozó feltétel, akkor feltétel nélküli optimalizálásról beszélünk.

A feltételeket kielégítő pontokat megengedett megoldásoknak nevezzük, halmazukat -fel jelöljük, vagyis

A fenti feladatot tömörebb formában is felírhatjuk. Legyen

és vezessük be a következő jelölést.

3.1. Definíció. Legyen Az egyenlőtlenség akkor és csak akkor teljesül, ha ().

A fenti jelöléseket felhasználva a feladatot a következő alakban írhatjuk:

3.2. Definíció. A 3.1 feladat megengedett megoldásainak halmaza:

Az vektort megengedett megoldásnak nevezzük, ha .

3.3. Megjegyzés. Valójában

volna a helyes definíció, de feltesszük, hogy a és feltételek együttes fennállása esetén .

Előfordulnak csak egyenlőségi, vagy csak egyenlőtlenségi korlátokat tartalmazó szélsőértékfeladatok is. Ezek általános alakja

illetve

A feladatok megengedett megoldás halmazai értelemszerűen az

illetve a

halmazok.

Az optimalizálási feladatot felírhatjuk a következő formában is:

Feltétel nélküli optimalizálás esetén . Feltételes optimalizálásról valójában akkor beszélünk, ha és .

3.4. Definíció. Az vektor optimális megoldás, ha fennáll, hogy

Az vektort megengedett megoldásnak nevezzük, ha .

Tömören jelölve egy megoldást optimálisnak nevezünk, ha

3.5. Definíció. Az vektor lokálisan optimális megoldás, ha létezik olyan szám, hogy

3.6. Definíció. Egy minimumhelyet szigorúnak nevezünk, ha egy számra fennáll, hogy

Egy maximumhelyet szigorúnak nevezünk, ha egy számra fennáll, hogy

Számos esetben csak egy lokális optimumot tudunk (akárcsak közelítőleg is) meghatározni. Az optimum létezésére következtethetünk Weierstrass-tételéből, ha korlátos és zárt halmaz és az célfüggvény az halmazon folytonos. A gyakorlatban ezt a tényt csak ritkán használhatjuk ki.

Végül megjegyezzük, hogy elég csak az minimum feladatot vizsgálni, mert fennáll a egyenlőség.

3.1. Nemlineáris optimalizálási feladatok osztályozása

A fenti definíciókat használva megadhatjuk a NLO feladatok néhány osztályát. Ezeknek az osztályoknak a leírásakor felhasználjuk azt a triviális tényt, hogy az -beli nemnegatív vektorokból álló halmaz konvex. Egy függvényt kvadratikusnak nevezünk, ha

ahol szimmetrikus mátrix, és . Ha , akkor -et affin vagy lineáris függvénynek mondjuk.

Általában a NLO feladatok következő osztályait különböztetjük meg:

  • Lineáris optimalizálás (LO): és affin (lineáris) függvények és a halmaz vagy -nel vagy -szal egyezik meg.

  • Feltétel nélküli optimalizálás: Az és (azaz az indexhalmazok üresek), valamint .

  • Konvex optimalizálás (CO): konvex függvények, affin (lineáris) függvények és konvex halmaz.

  • Folytonos konvex optimalizálás: Konvex optimalizálási feladat az előbbi értelemben, de emellett az összes függvény kétszer folytonosan differenciálható. Megjegyezzük, hogy ezen kívül még további folytonossági követelményeket is fel fogunk tenni a későbbiekben.

  • Kvadratikus optimalizálás (QO): Az célfüggvény kvadratikus, a feltételben szereplő összes és függvény affin (lineáris) és a halmaz vagy -nel, vagy -szal egyezik meg.

  • Kvadratikusan korlátozott kvadratikus optimalizálás: Ugyanaz, mint a QO, de a függvények kvadratikusak.

  • Konvex kvadratikus optimalizálás (KKO): Ugyanaz, mint a QO, de az célfüggvény konvex.

  • Konvex kvadratikusan korlátozott kvadratikus optimalizálás: Azonos a kvadratikusan korlátozott kvadratikus optimalizálási feladattal, viszont az célfüggvény és a kvadratikus függvények konvexek.

3.2. Kvadratikus függvények és szélsőértékeik

A kvadratikus függvények az optimalizásban fontos szerepet játszanak.

A következőkben vizsgáljuk a kvadratikus függvények tulajdonságait. Könnyű igazolni, hogy

és

Ha létezik , akkor a

stacionárius egyenlet megoldása . Vizsgáljuk az értékét az helyen:

Ha pozitív definit, akkor esetén és

Ekkor tehát minimumhely és .

Ha negatív definit, akkor esetén és

Ekkor tehát maximumhely és .

Ha indefinit, akkor megmutatható, hogy nyeregpont.

3.1. Példa. Az függvénynek egy szigorú (erős) minimumhelye van az pontban. A Hesse mátrix pozitív definit, mivel

Az függvénynek gyenge minimumhelye van, mivel esetén a minimuma a függvénynek. A Hesse mátrix ebben az esetben pozitív szemidefinit

Az függvénynek szigorú (erős) maximumhelye van az pontban. Ebben az esetben a Hesse mátrix negatív definit

Az függvénynek nyeregpontja van, a Hesse mátrix itt indefinit)

3.3. Egyenlőségi feltételek

Legyen és vizsgáljuk az

feltételes szélsőértékfeladatot!

3.7. Definíció. Legyen és tegyük fel, hogy valamilyen értékre. Az pont reguláris, ha a

gradiens vektorok lineárisan függetlenek.

3.8. Definíció. Az 3.3 optimalizálási feladat Lagrange-függvénye

ahol .

A együtthatókat Lagrange-szorzóknak (multiplikátoroknak) is nevezik. A függvény vektor szerinti gradiensét , az vektor szerinti Hesse-mátrixát pedig fogja jelölni.

3.9. Tétel. Legyen lokális minimum (maximum) pont és tegyük fel, hogy az pont reguláris. Ekkor egyértelműen létezik egy úgy, hogy

Ha és minimumhely, akkor fennáll

Ha és maximumhely, akkor fennáll

Az pont az Lagrange-függvény nyeregpontja. Minimum esetén a Hesse-mátrix feltételesen pozitív szemidefinit, a maximum esetén pedig feltételesen negatív szemidefinit.

3.10. Tétel. Tegyük fel, hogy reguláris pont, és létezik úgy, hogy

Ha feltételesen pozitív definit, azaz

akkor szigorú lokális minimumhely. Ha a Hesse-mátrix feltételesen negatív definit, azaz

akkor szigorú lokális maximumhely.

A feltételes pozitív definitség ellenőrzése meglehetősen nehéz feladat. Ismertetjük a két legismertebb eredményt.

3.11. Tétel. Legyen szimmetrikus. Az mátrix akkor és csak akkor feltételesen pozitív definit (negatív definit), ha a

polinomegyenlet gyökei mind pozitívak (negatívak).

A következő tétel Chabrillac és Crouzeix eredménye:

3.12. Tétel. Legyen szimmetrikus. Az mátrix feltételesen pozitív definit, akkor és csak akkor, ha az

szegélyezett mátrixnak negatív, zérus és pozitív valós sajátértéke van. Az mátrix akkor és csak akkor feltételesen negatív definit, ha a fenti szegélyezett mátrixnak negatív, zérus és pozitív valós sajátértéke van.

3.13. Definíció. Legyen szimmetrikus mátrix. Az vektort az mátrix inerciájának nevezzük, ha az mátrix pozitív, az zérus, pedig az mátrix negatív sajátértékeinek a számát jelenti.

Az inercia meghatározása és a feltételes definitség meghatározása véges lépésben is lehetséges. A Chabrillac-Crouzeix tételt ez alapján a következő alakban is kimondhatjuk (mivel tulajdonképpen a a szegélyezett mátrix inerciájára mond ki feltételt). Értelemszerűen .

3.14. Tétel. Legyen szimmetrikus. Az mátrix feltételesen pozitív definit, akkor és csak akkor, ha az

szegélyezett mátrix inerciája . Az mátrix akkor és csak akkor feltételesen negatív definit, ha .

Az előző két tétel alapján a Hesse-mátrix feltételes definitségét a

polinomegyenlet gyökeinek, vagy a

szegélyezett mátrix inerciájának vizsgálatával dönthetjük el. Megjegyezzük, hogy a szegélyezett mátrix az Lagrange-függvény változó szerinti Hesse-mátrixa az helyen, azaz

A 3.3 feltételes optimalizálási feladat megoldása a következőképpen történhet:

  1. Megoldjuk a

    egyenletrendszert. Jelölje a megoldást:

  2. Ellenőrizzük a Hesse-mátrix feltételes definitségét a fenti két tétel valamelyikével.

3.2. Példa.

Határozzuk meg az kör origóhoz legközelebbi és legtávolabbi pontját!

Ebben az esetben a következő feltételes szélsőértékfeladatot kell megoldanunk:

A feladatnak egy legkisebb és egy legnagyobb pontja van. A feladat Lagrange-függvénye:

Az függvény gradiense:

Az egyenletrendszer megoldása

amelyet a feltételi egyenletbe helyettesítve

adódik. Innen a lehetséges megoldások:

Ebből kapjuk, hogy

Mindkét pont reguláris.

A pontok jellegét először a determináns tétel alapján ellenőrizzük. Ekkor

amelyet kifejtve kapjuk, hogy

Innen az egyetlen gyök . Ha , akkor , ami a determináns tétel szerint azt jelenti, hogy a pont szigorú lokális minimumhely. A pont esetén , amiből az következik, hogy a pont szigorú lokális maximumhely.

A Chabrillac-Crouzeix tétel alapján eljárva kapjuk, hogy a szegélyezett mátrix

Ennek sajátértékei a esetben:

A negatív sajátértékek száma 1, a zérus sajátértékek száma 0, a pozitívaké pedig 2 (azaz ). Eszerint itt a feladatnak szigorú lokális minimuma van.

A szegélyezett mátrix sajátértékei a esetben:

Ekkor tehát 2 negatív, 0 zérus és 1 pozitív sajátérték van (azaz ), ami azt jelenti, hogy az adott pont szigorú lokális maximumhely.

3.4. Egyenlőtlenségi feltételek

A következő általános esetet vizsgáljuk:

ahol , , adott függvények és .

3.15. Definíció. Ha , akkor -edik egyenlőtlenségi feltételt aktívnak nevezzük. Az pontban aktív egyenlőtlenségi feltételek halmazát

jelöli. Egy egyenlőtlenségi feltétel az pontban inaktív, ha .

3.16. Definíció. Legyen és tegyük fel, hogy valamilyen értékre. Az pont reguláris, ha a

gradiens vektorok lineárisan függetlenek.

Vezessük be az változót az alábbiak szerint

Legyen továbbá

valamint és . Könnyű belátni, hogy ha az eredeti feladat lokális minimumhelye, akkor az

pont az ekvivalens

optimumfeladat lokális minimumhelye. Tehát alkalmazható rá a korábban megismert Lagrange-féle elmélet. Igazak a következő szükséges tételek. Az első tétel Carathéodory és John tétele:

3.17. Tétel. Legyenek és (, ) folytonosan differenciálhatók egy halmazon. Tegyük fel, hogy belső pont és egyúttal az 3.4 feladat lokális minimuma. Ekkor létezik és úgy, hogy

és

A tétel

szükséges feltételét szokás az alábbi ekvivalens formában is megadni:

A Carathéodory-John tétel híres következménye a következő Karush-Kuhn-Tucker tétel:

3.18. Tétel. Legyenek és (, ) folytonosan differenciálhatók egy halmazon. Tegyük fel, hogy belső pont és egyúttal az 3.4 feladat lokális minimuma. Ekkor létezik és úgy, hogy

és

A tétel alapján bevezethetjük a

Lagrange-féle függvényt és az alábbi fogalmat.

3.19. Definíció. Az pontot az 3.4 szélsőérték feladat KKTL-pontjának (Karush-Kuhn-Tucker-Lagrange pontjának) nevezzük, ha léteznek és Lagrange-szorzók úgy, hogy

és

Igaz a következő elégséges eredmény.

3.20. Tétel. Legyen az 3.4 szélsőérték feladat reguláris KKTL-pontja és tegyük fel, hogy minden esetén. Tegyük fel továbbá, hogy valamilyen értékre. Ha

fennáll

esetén, akkor szigorú lokális minimum pont.

A feltételes pozitiv definitség ellenőrzésére vezessük az

és

mátrixokat. Jelöljük -sel a mátrix oszlopainak számát. Ha a szegélyezett mátrixnak negatív, zérus és pozitív sajátértéke van, akkor szigorú lokális minimumhely. (Ez következik az előző részben bevezetett inerciára kimondott tételből),

A tétel alkalmazásához szükséges, hogy teljesüljön minden esetén.

3.3. Példa. Oldjuk meg a

feladatot! Az és gradiense

A Lagrange-függvény

A KKTL-pontokra vonatkozó tétel szerint az alábbi egyenletrendszert kell megoldanunk:

Innen esetén és adódik, amely nem KKTL pont, mert .

esetén és adódik, amit visszahelyettesítve a harmadik egyenletbe adódik, hogy . Innen megoldás adódik, amely KKTL pont. Megállapíthatjuk, hogy az egyenlőtlenségi feltétel aktív, (így kaptuk a KKTL pontot) és . A KKTL pont nyilvánvalóan reguláris, valamint . A szegélyezett mátrix

Ennek 2 pozitív és egy negatív sajátértéke van, így az inerciája: . Az elégségességi tétel alapján a KKTL pontban szigorú lokális minimum van.

A , ill. szükséges feltételeket elsőrendű optimalitási feltételeknek, a , ill. Hesse-mátrixok feltételes pozitív (szemi) definitségére vonatkozó feltételeket másodrendű feltételeknek nevezzük. Fontos speciális esetekben a másodrendű feltételek vizsgálata elhagyható. Ezeket a következő szakaszban vizsgáljuk.

3.5. A konvex optimalizálási feladat

3.21. Definíció. Legyen nemüres, konvex halmaz, egy -n véges, konvex függvény, konvex függvények, és affin függvények. Ekkor az

problémát konvex optimalizálási problémának nevezzük.

A Lagrange-féle függvény:

A együtthatókat Lagrange szorzók-nak (vagy Lagrange multiplikátoroknak nevezzük.

3.22. Tétel. [Karush-Kuhn-Tucker szükséges feltétel] Legyen a 3.5 probléma megoldása. Ekkor léteznek olyan Lagrange szorzók, hogy

és ;

;

.

Bizonyítás. Legyen

Ekkor , mert -vel. Továbbá, konvex, így ri egy korábbi tétel miatt.

Bebizonyítjuk, hogy ri . Tegyük fel az ellenkezőjét. Ekkor létezik olyan pozitív valós szám, hogy . Mivel eleme az előbbi metszetnek, is eleme. Így létezik olyan , hogy , ami ellentmondás. Tehát ri . Az első szeparációs tétel szerint és elválaszthatóak azaz, létezik , hogy

Helyettesítsük -t a következő vektorokkal:

ahol az utolsó vektorban a helyen áll . Ezzel kapjuk, hogy . Így az állítás első részét bebizonyítottuk.

Helyettesítsük most 3.6-ben helyére a

vektorokat. Az állítás első részét és azt a tényt felhasználva, hogy lehetséges megoldás, kapjuk az állítás második részét.

Legyen tetszőleges lehetséges megoldás. Ekkor . Felhasználva ezt, az előző részt, 3.6, és az egyenleteket kapjuk a következőt:

Ezzel a bizonyítás kész.

3.23. Tétel. [Karush-Kuhn-Tucker elegendő feltétel] Tegyük fel, hogy a pont lehetséges megoldása a 3.5 feladatnak és az előző tételbeli feltételek -val teljesülnek, akkor optimális megoldás is egyben.

Bizonyítás. A tétel feltételei mellett tetszőleges lehetséges megoldás esetén

-lal osztva kapjuk az állítást.

3.24. Tétel. [Slater-féle szükséges feltétel] Ha 3.5-ben , a probléma megoldása és létezik olyan lehetséges megoldás, amelyre , akkor .

Bizonyítás. Indirekt tegyük fel, hogy . Ekkor a feltételek miatt valamelyik pozitív, ezért

ami ellentmond a KKT-szükséges feltételének.

3.25. Megjegyzés. A tételben szereplő feltételeket -beli Slater feltételnek nevezzük. Ebben az esetben módosíthatjuk a Lagrange függvényt (osztunk -lal) a következő módon:

3.26. Tétel. Tegyük fel, hogy teljesül a Slater feltétel -ben és -k folytonosan differenciálhatóak. Ekkor pontosan akkor optimális, ha létezik úgy, hogy

;

.

Bizonyítás. Ha megoldás, akkor a Slater-féle szükséges feltétel tételt és a KKT szükséges feltétel tételt használva adódik az állítás. A megfordítás pedig következik a KKT elegendő feltétel tétel és a Slater-féle szükséges feltétel tétel felhasználásával.

3.6. Duális programozási feladatok

Egy programozási feladathoz természetes módon hozzárendelhetünk egy un. duális problémát. A két programozási feladat viszonya speciális és ez az optimalizálási feladatok megoldásánál sok esetben igen hasznos. Az

primál konvex optimalizálási feladat duálisa a

programozási feladat. A duális feladat megengedett megoldásainak halmazát jelölje

Igaz a következő, úgynevezett gyenge dualitási tétel. A tétel azt jelenti, hogy a primál feladat minimuma, ha létezik nem lehet kisebb mint a duál feladat maximuma (ha létezik). Az erős dualitási tételek a két optimum egyenlőségét mondják ki létezés esetén.

3.27. Tétel. Ha differenciálható konvex függvények -en, akkor

A következőkben az alkalmazások szempontjából fontos lineáris programozási feladatot vizsgáljuk. Ennek alakja

ahol , és . Hozzuk a feltételi egyenlőtlenségeket a (), ill. alakra, ahol az mátrix -edik sorvektora. Az lineáris programozási feladat Lagrange függvénye

A Kuhn-Tucker tétel alapján teljesülnie kell a

feltételnek. Elimináljuk -t a Lagrange-függvényből és a feltételekből. Minthogy kapjuk, hogy

Figyelembevéve, hogy , a primál lineáris programozási feladat duálisa:

3.28. Tétel. [A lineáris programozás dualitási tétele]

(Gyenge dualitás): Fennáll, hogy

(Erős dualitás): Ha a primál, vagy a duál feladatok valamelyikének van optimális megoldása, akkor a másiknak is van és a két optimum (célfüggvényérték) megegyezik.

4. fejezet - Minimumkereső eljárások

Egy és többváltozós függvények minimumhelyének és minimumának meghatározására két fő lehetőség van:

1. Valamilyen gyökkereső eljárást (pl. Newton-módszert) alkalmazunk a stacionárius egyenletre.

2. Direkt kereső eljárást alkalmazunk.

A fejezetben mindkét csoportba tartozó hatékony eljárásokat ismertetünk. A feltételes szélsőértékek meghatározásának általános módszereként a büntetőfüggvények módszerét ismertetjük.

4.1. Egyváltozós függvények kereső eljárásai

A direkt kereső eljárásoknál egy, az minimumhelyet biztosan tartalmazó intervallumból indulunk ki. Ezt az úgynevezett befoglaló intervallumot (vagy más néven bizonytalansági intervallumot, mivel csak azt tudjuk, hogy a minimumpont itt keresendő, de a helyéről nincs információnk) szűkítjük az eljárások során lépésről lépésre.

Ehhez nem teszünk mást, mint az intervallumot részekre osztjuk (általában két belső pont felvételével) és az osztópontokban a függvényértéket kiszámítjuk, a függvényértékek nagysága alapján fogjuk az új (szűkebb) bizonytalansági intervallumot meghatározni. Ahhoz, hogy az eljárás konvergens legyen a függvénynek bizonyos konvexitási, vagy más bizonyos tulajdonsággal kell rendelkeznie.

Megjegyezzük, hogy sok esetben anélkül is alkalmazzuk az alábbi eljárásokat,hogy meggyőződnénk a konvexitásról, ekkor azonban nincs garancia az eljárások konvergenciájára.

4.1. Definíció. Az függvényt unimodálisnak nevezzük, ha tetszőleges esetén

Az unimodális függvény az minimumhelytől balra szigorúan monoton csökkenő, tőle jobbra pedig szigorúan monoton növő. A szigorúan konvex és a szigorúan kvázikonvex függvények unimodálisak. Az unimodális függvények kereső eljárásai a következő észrevételen alapulnak.

4.2. Tétel. Legyen unimodális függvény és . Ekkor

[(i)] Ha , akkor .

[(ii)] Ha , akkor .

[(iii)] Ha , akkor .

Bizonyítás. [(i)] Tegyük fel, indirekt, hogy . Ekkor az unimodalitás miatt -tól balra a függvény szigorúan monoton csökkenő, amelyből adódik. Ez pedig ellentmond a feltételnek. Így .

A többi rész igazolása hasonló.

Megjegyezzük, hogy csak egy belső pontból származó információ alapján nem lehet a minimumhelyet tartalmazó intervallumot szűkíteni. A fenti tétel alapján a következő eljárást definiálhatjuk unimodális függvények minimumhelyének megkeresésére.

4.1.1. Általános minimum kereső algoritmus

A kapott

intervallumsorozat közös pontként tartalmazza az minimumhelyet. Ha , akkor a minimumhely adott pontosságú közelítését véges iterációs lépésben megkaphatjuk. A vagy pont ismételt felhasználásával az függvény behelyettesítéseinek számát csökkenthetjük.

4.1.2. Dichotomous keresés

Legegyszerűbben úgy tudjuk biztosítani az új bizonytalansági intervallumok hosszának megegyezését, ha az intervallum középpontjától balra és jobbra azonos távolságra választjuk meg a pontokat. Jelölje a középponttól való távolságot, egy alkalmasan választott szám.

Ekkor:

Az új bizonytalansági intervallum számítása:

Ha , akkor az új bizonytalansági intervallum .

Ha , akkor az új bizonytalansági intervallum .

Nyilvánvaló, hogy mindkét esetben .

Az eljárást addig folytatjuk, amig valamely -ra , ahol a pontossági előírás. Ekkor, ha a minimumpontot a megállásnál kapott intervallum középpontjára választjuk, akkor -nál kisebb hibát követünk el a minimumpont közelítésében.

4.1. Példa. Oldjuk meg az egyváltozós optimalizálási feladatot dichotomous módszerrel, ha a bizonytalansági intervallum , , .

Megoldás:

1. lépés: Az első közelítésbeli bizonytalansági intervallum , melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek:

2. lépés: Mivel , így az új bizonytalansági intervallum , melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek:

3. lépés: Mivel , így az új bizonytalansági intervallum ,melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek:

4. lépés: Mivel , így az új bizonytalansági intervallum ,melynek hossza . Itt megállunk, mivel . A minimumpont közelítése . Általában kisebb értéket szokás megadni, de ezzel is elég közel kerültünk a pontos minimumhelyhez, az értékhez.

4.1.3. Aranymetszéses keresés

Ez az eljárás egyike a leggyakrabban használtaknak. Előnye, hogy minden lépésben csak egy olyan új pont adódik, ahol ki kell kiszámolni a függvényértéket.

Legyen . Ha az aranymetszéses keresés (Golden section) eljárás befejeződik, akkor az lokális minimumhely a legfeljebb hosszúságú intervallumban van. Az intervallum bármelyik pontja választható az közelítéseként. Célszerű azonban az közelítést alkalmazni, mert ekkor biztosan teljesül az feltétel.

Az aranymetszés eljárása a következő:

Az aranymetsző keresés sebessége lineáris. Ugyanis az intervallum hossza pontosan -szorosa (-szorosa) az intervallum hosszának. Jelöljük el -val az hosszát, azaz . Ekkor

Ezért adott intervallum és adott ismeretében előre meg lehet határozni, hogy hány lépést kell végrehajtanunk ahhoz, hogy kisebb legyen -nál. Például, ha és , akkor a egyenletet kell megoldanunk. Innen , azaz 28 intervallumot kell meghatározni.

4.2. Példa. Oldjuk meg az egyváltozós optimalizálási feladatot aranymetszés módszerrel, ha a bizonytalansági intervallum , .

Megoldás:

1. lépés: Az első közelítésbeli bizonytalansági intervallum , melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek:

2. lépés: Mivel , így az új bizonytalansági intervallum , melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek az alábbiak. Ne feledjük, hogy most a pont az előző intervallumbeli értékkel azonos.

3. lépés: Mivel , így az új bizonytalansági intervallum ,melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek az alábbiak. Ez esetben a pont lesz az előző intervallumbeli értékkel azonos.

4. lépés: Mivel , így az új bizonytalansági intervallum , melynek hossza . Itt megállunk, mivel . A minimumpont közelítése . Most még közelebb kerültünk a pontos minimumhelyhez (az értékhez, mint a Dichotomous keresés esetén.

4.1.4. Fibonacci keresés

A golden section módszernél láttuk, hogy a bizonytalansági intervallumok hossza minden lépésben azonos arányban csökken, azaz . A Fibonacci módszernél a redukciós arány lépésről lépésre változik, de megmarad a golden section módszernek az a jó tulajdonsága, hogy az első intervallumban kettő, a többi intervallumban pedig csak egy függvény-kiértékelésre van szükség. Az eljárás alapját a Fibonacci számok képezik, amelyeket az alábbi rekurzív formula definiál:

A sorozat első néhány eleme:

A módszer elején kiválasztunk egy természetes számot, amelyet a lépésszám meghatározására fogunk használni a későbbiekben. A Fibonacci módszernél az és a Fibonacci számok segítségével az alábbi formulákkal számítjuk ki az intervallum belsejében a pontokat:

Az első intervallumbeli közbülső pontok számításánál a nevezőben mindig áll, a számlálóban pedig attól kettővel ill. eggyel kisebb indexű Fibonacci szám áll. A további lépésekben a Fibonacci számok indexe mindig eggyel csökken.

4.3. Megjegyzés.

Akár a baloldali, akár a jobboldali intervallum lesz az új bizonytalansági intervallum, mindkét esetben

és az intervallumok hosszára igaz a Fibonacci számok képzéséhez formailag hasonló összefüggés

Akár a baloldali, akár a jobboldali intervallum lesz az új bizonytalansági intervallum, mindkét esetben az új bizonytalansági intervallumbeli egyik pont megegyezik az előző bizonytalansági intervallum egyik belső pontjával, azaz ha az új bizonytalansági intervallum , akkor

ha pedig az új bizonytalansági intervallum , akkor

A esetben

Ez az állítás azt fejezi ki, hogy egy bizonyos lépés után az algoritmus megáll, mivel a két belső pont megegyezik.

Összefoglalva, a Fibonacci módszernél az új bizonytalansági intervallum és abban lévő két pont számítása a következő:

Ha , akkor az új bizonytalansági intervallum

Ha , akkor az új bizonytalansági intervallum

Az eljárást lépésig folytatjuk és a közös értékre választjuk a minimumpontot. Ekkor a hiba, amit elkövethetünk legfeljebb . Könnyen ellenőrizhető, hogy a közös érték nem más, mint a intervallum középpontja.

Az értékét a következőképpen választjuk: Az első intervallum esetén kettő, a további intervallumokban csak egy függvény-kiértékelés szükséges. Ha az utolsó, azaz a -edik intervallumban is kiszámítjuk a függvény minimumát, akkor a függvény-kiértékelések száma , tehát az előre nem definiált a függvény-kiértékelések számát jelenti. Ha előírjuk, hogy a választott minimumpontnak legfeljebb legyen a hibája, azaz

akkor az értéke ennek a formulának a segítségével számítható. Itt a -edik intervallum hosszára az adódik, hogy

Ezt felhasználva, helyettesítéssel

A hibára vonatkozó képlet használható formában az alábbiak szerint írható

amelyből az adott kezdeti intervallumhossz () és egy előre megadott pontossági tűrés () ismertében értékét úgy kell megválasztani, hogy

4.3. Példa. Oldjuk meg az egyváltozós optimalizálási feladatot Fibonacci módszerrel, ha a bizonytalansági intervallum .

Megoldás:

Válasszuk meg az értékét -re. Az algoritmushoz szükséges Fibonacci számok:

1. lépés: Az első közelítésbeli bizonytalansági intervallum , melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek:

2. lépés: Mivel , így az új bizonytalansági intervallum , melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek az alábbiak. A pont az előző intervallumbeli értékkel azonos.

3. lépés: Mivel , így az új bizonytalansági intervallum ,melynek hossza . A két közbülső pont és a hozzájuk tartozó függvényértékek az alábbiak. Ez esetben a pont lesz az előző intervallumbeli értékkel azonos.

4. lépés: Mivel , így az algoritmust be kell fejezni. A minimumpont közelítése , vagyis a közbülső pontok értéke.

Megfigyelhető, hogy a bizonytalansági intervallumok hosszának csökkenése minden lépésben a Fibonacci számok hányadosával arányos. Például az .

Ha az értékét önkényesen választjuk meg, akkor - mint ahogy tapasztaltuk - nem tudjuk befolyásolni a pontosságot. Amennyiben azt szeretnénk, hogy a pontossági tűrés például legyen, akkor az értékét olyanra kell választani, hogy fennálljon az

összefüggés, ez pedig azt jelenti példánkban, hogy . A Fibonacci számokból adódik, hogy , mivel .

4.1.5. Parabola kereső eljárás

A parabola kereső eljárás gyorsabb, az előzőnél, azonban több információt használ fel. A kvadratikus interpolációs eljárás alapgondolata a következő.

Tegyük fel, hogy unimodális az intervallumon. Tegyük fel, hogy tartalmazza az minimumhelyet, adott az pont és teljesülnek az , feltételek. Közelítsük az függvényt az ponton átmenő Lagrange-féle interpolációs polinommal, amelynek alakja

A parabola minimumhelyét használjuk az minimumhely újabb közelítéseként. A parabolának pontosan akkor van minimumhelye, ha a másodfokú tag együtthatója pozitív, azaz ha

Deriválással könnyen igazolható, hogy a parabola minimumhelye

A következő esetek lehetségesek:

  1. [1. eset] Ha , akkor . Az új pontok a következők lesznek: , , .

  2. [2. eset] Ha , akkor . Az új pontok a következők lesznek: , , .

  3. [3. eset] Ha , akkor . Az új pontok a következők lesznek: , ,

  4. [4. eset] Ha , akkor . Az új pontok a következők lesznek: , , .

Ennél az eljárásnál is alkalmazhatjuk az kilépési feltételt. Szokás azonban használni a

feltételt is, amely az függvény közelítésének relatív hibája a közelítő parabola minimumhelyén. A parabola kereső eljárást a következőképpen foglalhatjuk össze:

Az eljárás gyorsabb konvergenciát biztosít mint az aranymetszéses keresés.

4.1.6. Newton módszer

A klasszikus Newton módszer a egyenlet gyökét keresi meg bizonyos feltételek (pl. folytonosan differenciálhatóság) mellett egy adott intervallumon. Ezt az eljárást alkalmazzunk most a stacionárius egyenlet megoldására. Tegyük fel, hogy az egyváltozós függvény, amelynek szélsőértékét keressük, kétszer differenciálható függvény. Induljunk ki egy pontból és alkalmazzuk az egyenlet megoldására a Newton iterációs eljárást, amely a következő

A Newton-módszer konvergenciájára az alábbi tételt ismertetjük.

4.4. Tétel. Ha az függvényre teljesülnek a következők:

(i) , azaz háromszor folytonosan differenciálható -n,

(ii) , ha azaz és állandó előjelűek az -n,

(iii) -nek van szélsőértéke -n, azaz -nak van zérushelye -n

(iv) , valamint teljesül, hogy és azonos előjelű,

akkor az

sorozat konvergál az egyetlen -beli szélsőértékhez. Érvényes továbbá az alábbi hibabecslés:

ahol és , azaz a deriváltak abszolút értékeinek alsó, illetve felső korlátjai -n.

Bizonyítás. A szélsőérték egyedüli volta az szigorú monotonitásából következik (). Az is világos, hogy ekkor az intervallum két végpontjában ellentétes az előjele, következésképpen az egyik végpont mindig teljesíti a (iv) feltételt. Négy eset különböztethető meg, az és előjeleitől függően. Mind a négyre hasonló a bizonyítás, ezért csak az ábrán is látható esetet mutatjuk meg.

Ekkor az (iv) feltétel miatt is pozitív, az pozitivitása és korlátossága miatt (zárt intervallumon folytonos függvény ott korlátos is) pedig Felírva -ra a másodfokú, maradéktagos Taylor-polinomot

innen látható, hogy az érintő fölött halad, így is fennáll.

A második lépésben az játsza az szerepét, tehát , és így tovább. Az sorozat monoton csökkenő tehát, és korlátos is az intervallumban. Következésképp az egy alsó korlát. Monoton korlátos sorozat konvergens is, legyen a határérték . Vegyük az

mindkét oldalán a határátmenetet, a folytonosság miatt mindkét oldal határértéke ugyanaz a , ami csak az mellett lehetséges, azaz . A megoldáshoz való konvergenciát ezzel beláttuk.

A hibabecsléshez írjuk fel az elsőfokú maradéktagos Taylor-polinomot az pontban, a másodfokút pedig az -ben:

ahol . A két egyenlet baloldala egyenlő, így a jobboldalukon álló kifejezések is. Az elsőben , a másodikban . Ezért

Vegyük mindkét oldal abszolút értékét, helyett írjunk -et. Rendezzük át az egyenletet és vegyük figyelembe, hogy az alsó, pedig az felső korlátja. Ezzel megkapjuk a tételben szereplő hibabecslést.

Ezek után írjuk le az algoritmust a már megszokott pszeudókódban.

Kilépési feltételként a következőket szokás használni:

Ha igazolni tudtuk a konvergenciát és becsülni az , értékeket, akkor (A) egzakt hibabecslést végezhetünk, egyébként a (B)-t használjuk. Megjegyezzük azonban, hogy a (B) teljesülése esetén nem biztos, hogy a szélsőértékhez már elég közel vagyunk.

4.4. Példa. Keressük meg az függvény szélsőértékét a [0,1] intervallumon hibakorláttal Newton-módszerrel. Ekkor az egyenletet a kell megoldanunk Newton-módszerrel a . A számítások előtt igazoljuk a konvergenciát is.

Megoldás. A könnyen kiszámolható

deriváltakból azonnal látszik azok állandó előjele is az adott intervallumon; ezzel a konvergenciatétel első két feltételét igazoltuk. Az és értékek ellentétes előjele egyben az (iii) feltétel teljesülését jelenti. Az választással pedig az utolsó feltétel is fennáll. Van tehát egyedüli megoldás a -n és az a Newton-módszerrel megközelíthető. Az egzakt hibabecsléshez szükséges konstansok is könnyen adódnak: mindkét derivált abszolút értéke szigorúan monoton nő, így az első a minimumát az helyen, a második pedig a maximumát a helyen veszi fel. Tehát és . Itt is előre kiszámolhatjuk a példára nézve állandó értéket.

Az iterációk eredményeit itt is táblázatba foglaltuk.

4.5. Példa. Oldjuk meg az egyváltozós optimalizálási feladatot Newton módszerrel, ha a kiinduló közelítő megoldás , és a (B) kilépési feltételt használjuk.

Megoldás:

A függvény első és második deriváltjai:

A közelítések:

Az utolsó két közelítés távolsága: .

A hibabecslés: .

A hibabecslés: .

A hibabecslés: . A 4. közelítésben megkaptuk a pontos értéket kilenc tizedes pontossággal.

4.2. Többváltozós függvények kereső eljárásai

4.2.1. A Newton-módszer

Legyenek többváltozós differenciálható valós függvények. Tekintsük az alábbi egyenletből álló egyenletrendszert:

Közelítsük ezeket a függvényeket a többváltozós valós függvényekre megismert elsőfokú Taylor polinommal egy helyen, azaz

Legyen , az vektor elemei legyenek az függvények. Az () egyenletrendszer esetén a Newton-módszer alakja

ahol

a Jacobi mátrix. Innen kapjuk, hogy a közelítés sorozata (hasonlóan az egyváltozós esethez)

ahonnan az

egyenletrendszer adódik. Ha , és invertálható, akkor

Mindkét formulát használják a Newton-módszernek, de az Jacobi-mátrix invertálásának elkerülése miatt célszerű az eljárást az alábbi módon használni:

Ha a Newton-módszert az stacionárius egyenletrendszerre alkalmazzuk, akkor a Jacobi mátrix alakja

ami nem más mint az függvény Hesse-mátrixa. A Newton-módszert itt is két alakban használjuk. Az eső esetben nem kell invertálni. Ekkor a módszer alakja következő lesz:

Ezt az alakot a későbbiekben Newton I. formulának fogjuk nevezni.

Invertálást használva azt kapjuk, hogy az közelítő sorozat a következőképpen állítható elő:

Ezt az alakot Newton II. formulának fogjuk nevezni.

A együtthatómátrix szimmetrikus. Ha és pozitív definit, akkor is pozitív definit.

A Newton-módszer lépésenkénti számítási költsége szimmetrikus lineáris egyenletrendszer megoldása, a a gradiens vektor és a Hesse-mátrix kiértékelése.

A Newton-módszer fenti alakját megkaphatjuk egy más, geometria jellegű okfejtéssel is! Közelítsük az függvényt az pontban az

kvadratikus kifejezéssel. Ennek minimumhelyét a egyenletrendszer megoldása adja, ahonnan az függvény minimumhelyének következő közelitése:

4.6. Példa. Határozzuk meg az

függvény minimumát Newton módszerrel az startvektorból kiindulva!

Megoldás:

A gradiensvektor és a Hesse mátrix a következő:

Az pontban kiszámítva az értékeiket kapjuk, hogy

Első esetben használjuk a megoldás során a Newton I. formulát. Ekkor a megoldandó lineáris egyenletrendszer

az vektor két koordinátájára

Innen a megoldás: , , amelyből az közelítés

Azt tapasztaltuk, hogy egy lépésben megkaptuk az optimumpontot. Könnyen ellenőrizhető, hogy az optimumpont . Az optimális célfüggvény érték .

Most alkalmazzuk a Newton II. formulát. Ehhez ki kell számítanunk a Hesse mátrix inverzét, ami

és így alkalmazva az

formulát azt kapjuk, hogy

Innen az előző formulához hasonlóan

A példában azt tapasztaltuk, hogy egyetlen lépésben megkaptuk az optimális megoldást. Ez mindig így van, ha a minimalizálandó függvény kvadratikus. Emlékezzünk a Newton módszer második levezetésére, amikor az függvényt annak másodfokú Taylor polinomjával helyettesítettük, ez pedig kvadratikus függvényeknél mindig önmagával egyezik meg.

4.2.2. Módosított Newton-módszer

A Newton módszer alkalmazásánál előfordulhat, hogy a Hesse mátrix nem invertálható, vagy az vektor nem csökkenő irány, vagy ha csökkenő is (), azonban az pontbeli függvényérték nem kisebb az pontbeli függvényértéknél. Ezeken próbál segíteni a módosított Newton-módszer. (Emellett az is segít, ha a Newton módszert összekapcsoljuk egy vonalmenti optimalizálással. Ezt be is fogjuk mutatni a későbbiekben).

A módosított Newton-módszert az alábbi alakban szokás használni:

ahol olyan diagonális mátrix, amelynek diagonális elemei nemnegatívak úgy, hogy jól kondícionált pozitív definit lesz.

Az diagonális mátrix megválasztására sokféle algoritmus ismert. Itt kettőt fogunk ismertetni. A legismertebb Gill és Murray eljárása. A másik az úgynevezett Levenberg-Marquardt módszer.

4.2.3. A Gill-Murray algoritmus

Legyen adott az szimmetrikus mátrix, az és paraméter. Az eljárás egy olyan felső háromszögmátrixot és egy diag diagonális mátrixot állít elő, amelyekre fennáll.

A paraméter javasolt értéke

4.2.4. A Levenberg-Marquardt módszer

A Hesse mátrixot most helyettesítsük egy szimmetrikus pozitív definit mátrix-szal, amelyet a következőképpen definiálunk

ahol paraméter, ezzel megnöveljük a Hesse mátrix főátlójában lévő elemek értékét. A Newton módszerben az meghatározása a

egyenletrendszer megoldására fog módosulni. Az algoritmus során az paramétert módosítjuk, mégpedig egy arány függvényében. Ez az arány az és pontokbeli függvényértékek különbségének hányadosa, számlálóban a minimalizálandó függvény, nevezőben pedig annak kvadratikus közelítő függvénye szerepel. Legyen ez az arány , képletben

Levenberg és Marquardt az alábbi eljárást javasolta.

  • Induló lépés : Kiindulunk egy tetszőleges vektorból és egy paraméterből.

  • Kísérletet teszünk a mátrix Cholesky felbontására. Ha nem sikerül, akkor az paraméter értékét négyszeresére növeljük, azaz: . Addig folytatjuk a kísérletet a Cholesky felbontására és az értékének módosítását, amig nem sikerül a felbontás.

  • Ha sikerül a Cholesky felbontás, azaz a mátrix pozitív definit, akkor megoldjuk az egyenletrendszert -ra.

  • Meghatározzuk a következő közelítést: .

  • Megállunk, ha , egyébként folytatjuk az eljárást a következő sorral.

  • Kiszámítunk az arányt.

    Ha , akkor legyen

    Ha , akkor legyen

    Ha , akkor legyen .

    Ha , akkor legyen és az értékét visszaállítjuk -ra, azaz

  • Folytatjuk az eljárást, .

4.2.5. Trust region módszerek

A trust-region módszereket Levenberg (1944), Marquardt (1963), valamint Goldfeld, Quandt és Trotter (1966) munkái nyomán fejlesztették ki. A trust-region módszerek azon alapulnak, hogy a kvadratikus modell csak az közelében pontos. Legyen

az úgynevezett trust region (megbízhatósági tartomány). Az közelítést -ban keressük: az lépést az

feltételes kvadratikus programozási feladat megoldásával adjuk meg, ahol a trust-region paraméter valamilyen adott konstans. Ha elég nagy, akkor a megoldás azonos a feltétel nélküli kvadratikus esettel. Ha elég kicsi, akkor ez megszorítást jelent. A paraméter értékét az értékének becsült és tényleges csökkenését figyelembevéve változtatjuk

A trust region módszer algoritmusa

A esetben az iterációs lépést sikeresnek nevezzük. A esetben az iterációs lépést sikertelennek nevezzük. A hányados jelentése:

A paramétert megválasztó algoritmus a következő. A update algoritmus:

Az algoritmus a paraméterek megválasztására nem túl érzékeny. Néhány javasolt érték: .

A feltételes kvadratikus optimalizálási probléma megoldására vonatkozik a következő

4.5. Lemma. [Gay, 1981] Az vektor a feladat megoldása akkor és csak akkor, ha létezik úgy, hogy

fennáll.

Eset szétválasztással adódik, hogy és , vagy és . Az utóbbi esetben a fenti feltételrendszer átmegy a

egyenletrendszerbe, amely -ra nézve nemlineáris. Ez relatíve könnyen megoldható iteratív úton.

Elég nagy esetén már nem csökken, az feltétel inaktívvá válik, lesz és a Newton-lépéssel lesz azonos. A következőkben , ill. meghatározásával foglalkozunk. Minthogy

ezért az egyváltozós

egyenletet kell megoldanunk -ra. A Hesse-mátrix szimmetrikus, tehát van olyan ortogonális mátrix, hogy , ahol . Innen

ahol a vektor -edik komponense. Mármost igaz, hogy

ahol a legkisebb, a legnagyobb sajátértéke. Tehát a megoldás az

intervallumban van. Az helyen -nak szingularitása van. Ezért a Newton-módszer nem a legjobban viselkedik.

Hebden az egyenlet megoldása helyett javasolta az

egyenlet megoldását, amelynek már nincs szingularitása.

A gyakorlatban a feladat helyett a

alakot is használják, ahol valamilyen skálázó mátrix. Ekkor az optimális megoldás meghatározható az értelemszerűen módosított

feltételből, ahol .

4.2.6. Kvázi-Newton módszerek

A kvázi-Newton módszerek olyan közelítő Newton-módszerek, amelyek iterációnkénti számítási költsége (ideje) rendkívül kicsi és ezért a számítási összköltsége (ideje) is kisebb mint a Newton-módszereké. Alapgondolatuk a következő.

Vizsgáljuk () nemlineáris egyenletrendszert! Legyen . A Newton-módszerben az Jacobi-mátrixot kicseréljük egy alkalmas módon definiált közelítő mátrixszal:

A mátrixot a mátrixból nyerjük egy, vagy több diadikus mátrix hozzáadásával. A alakja egyrangú módositás (update) esetén

kétrangú módositás esetén pedig

A diadikus mátrixszal történő módositás egy fontos előnyét mutatja a következő

4.6. Tétel. [Sherman-Morrison-Woodbury] Ha nemszinguláris és fennáll, hogy , akkor

Ha a mátrix inverzét ismerjük, akkor inverzét a fenti formulával flop művelettel tudjuk kiszámolni. Minthogy és egy mátrix-vektor szorzás szintén flop, az új közelitést összességében flop művelettel kaphatjuk meg.

A Gauss-eliminációval a egyenletrendszer megoldásának műveletigénye flop. Ezért a kvázi-Newton módszerek használata lényeges számitási költség megtakarítást jelent. Hasonló eredményt lehet elérni a mátrixok -felbontásával is.

A mátrixoknak ki kell elégíteniük bizonyos feltételeket. Legyen

az függvény egy lineáris közelítése. Az közelítést az egyenletrendszer megoldása adja. A kvázi-Newton módszerek esetén kikötjük, hogy

Vezessük be az mennyiséget! Ekkor a fenti két feltételből kapjuk az úgynevezett

szelő egyenletet. Az egyrangú kvázi-Newton update formulák általános alakja

ahol alkalmas módon megválasztott paraméter. Az optimális Broyden-módszer esetén .

4.2.7. Broyden módszer

A Newton-módszer konvergencia rendje 2. A kvázi-Newton módszerek konvergenciája a Jacobi mátrixot közelitő mátrixok konstrukciója miatt csak szuperlináris. Ezért adott pontosságú közelitő megoldás eléréséhez a kvázi-Newton módszereknek általában több lépésre van szükségük. Azonban a lépések lényegesen kisebb számitási költsége miatt a kvázi-Newton módszerek számitási összköltsége, különösen nagyméretű feladatok esetén, sok esetben lényegesen kisebb mint a Newton-módszeré. Ezért a kvázi-Newton módszerek használata előnyös.

A minimalizálási feladatoknál közvetlenül alkalmazhatunk bármilyen kvázi-Newton módszert az stacionárius egyenletre. Minthogy a stacionárius egyenletrendszer Jacobi mátrixa , azaz Hesse-mátrixa, célszerű olyan kvázi-Newton módszereket alkalmazni, amelyekben a mátrix szimmetrikus. Ezt biztosítják az egy- vagy kétrangú diáddal dolgozó kvázi-Newton módszerek. A ma legjobbnak tartott eljárás a BFGS (Broyden-Fletcher-Goldfarb-Shanno) módszer.

4.2.8. BFGS (Broyden-Fletcher-Goldfarb-Shanno) eljárás

Itt a mátrixot a Hesse-mátrixra való utalásként -szel is jelölhetnénk.

A mátrixok kiszámítására többféle módszer létezik. A

formulát kétrangú formulának szokés nevezni. Az úgynevezett egyrangú formula a következő:

4.2.9. A vonalmenti minimalizálás algoritmusa

A direkt minimumkereső eljárások közül az egyik legbeváltabb módszertípus vonalmenti (iránymenti) minimalizálásokon alapul. általános alakja a következő.

A vonalmenti minimalizálás algoritmusa

Az eljárástól megköveteljük az

csökkenési feltételt. Ez teljesül, ha az irányt úgy választjuk meg, hogy fennálljon

Ekkor miatt a függvény csökkenő az helyen. Következésképpen létezik , hogy . A tapasztalatok szerint az függvényértékek csökkenése nem lehet túl gyors. Az alábbi három heurisztikus feltételt a gyakorlati eljárások kielégítik.

4.2.10. Armijo-Goldstein feltételek

ahol fix paraméterek.

A gyakorlatban (), vagy kisebb. Az Armijo-Goldstein feltételek azt biztosítják, hogy a függvényértékek se túl lassan, se túl gyorsan ne csökkenjenek: és miatt , de

Egy lépéshossz akkor és csak akkor elégíti ki a két Armijo-Goldstein feltételt, ha

4.2.11. Szögfeltétel

ahol és

Az 4.2 feltétel helyett használják az un. Wolfe-féle feltételt is

valamint más hasonló feltételeket is. Egy lépéshossz akkor és csak akkor elégíti ki az 4.1 és 4.4 feltételeket, ha

4.7. Megjegyzés. A most vizsgált feltételek kielégítése esetén a vonalmenti minimalizálások nem a függvény feltétel melletti globális minimumát adják meg, hanem csak egy olyan pontot, amelyre fennáll . Bizonyos esetekben ez az minimumhely egy intervallumon.

Igaz a következő

4.8. Tétel. Tegyük fel, hogy minden esetén fennállnak az alábbi feltételek:

(i) ,

(ii) ,

(iii) ,

(iv) ,

Ha kétszer folytonosan differenciálható és az nívóhalmaz korlátos és zárt, akkor

Bizonyítás. A feltétel miatt és . Minthogy az halmazon alulról korlátos, a monoton csökkenő sorozat alulról korlátos. Következésképpen konvergens. Tegyük fel, hogy 4.5 nem teljesül. Ekkor van egy szám és egy végtelen indexhalmaz, hogy

Az 4.1 feltétel azt mutatja, hogy

Minthogy konvergens sorozat, az sorozat zérushoz konvergál. A (4.4) feltételből a

egyenlőtlenség következik. Ebből, az előző és az egyenlőtlenségekből

adódik. Minthogy zérushoz tart és egyenletesen folytonos az halmazon, a jobboldal zérushoz kell, hogy tartson. Ellentmondásra jutottunk. Tehát a (4.5) reláció teljesül.

Ezt a fajta konvergencia tételt gyakran globálisnak nevezik, mert nincs benne feltevés az kiindulási pont és a stacionárius pont közelségéről.

4.9. Következmény. Ha a 4.3 szögfeltételt is kikötjük, akkor

Bizonyítás. Definíció szerint

ahol . Ennek következtében

csak akkor állhat fenn, ha , azaz, ha .

Megjegyezzük, hogy a konvergenciából még nem következik , csak annyi, hogy létezik konvergens részsorozat, amelynek határértéke kielégíti a stacionárius egyenletrendszert.

4.2.12. Iránykeresési módszerek

Számos lehetőség van az kutatási irányok megválasztására:

1. A leggyorsabb lecsökkenés módszere: ;

2. Newton-szerű módszerek: , ahol szimmetrikus pozitív definit mátrix.

Mindkét esetben a csökkenő tulajdonság teljesül. A leggyorsabb lecsökkenés módszerénél

A pozitív definitsége miatt a Newton-szerű módszereknél

4.2.13. Gradiens módszer (Cauchy módszer, 1847)

Mint tudjuk, a gradiens vektor a függvény legnagyobb növekedésének irányába mutat. Legkézenfekvőbb tehát a kereső irányra a választás, hisz ebben az irányban várható a függvény legnagyobb csökkenése. Szokás ezt a módszer a legnagyobb csökkenés módszerének is nevezni. A módszer lényege az alábbiakban foglalható össze.

Gradiens módszer algoritmusa

Megállási feltétel lehet például ha , vagy ha .

4.7. Példa. Oldjuk meg az alábbi optimalizálási feladatot gradiens módszerrel. Legyen az a startvektor és legyen a pontossági tűrés.

Megoldás:

A célfüggvény gradiense

1. lépés:

Innen . Az egyváltozós optimalizálási feladat és megoldása: , amelyből

2. lépés: . Innen és . Az egyváltozós optimalizálási feladat és megoldása:

Ennek megoldása

3. lépés: , ahonnan

Az egyváltozós optimalizálási feladat és megoldása:

Innen

4. lépés: , , .

Az egyváltozós optimalizálási feladat és megoldása:

ahonnan

5. lépés: , , .

Az egyváltozós optimalizálási feladat és megoldása:

Innen

6. lépés: Az eljárást befejezzük, mert az 5. lépésben már elég közel kerültünk a minimumhelyhez, amely .

4.2.14. Konjugált gradiens módszer (Fletcher, Reeves)

Első lépésként definiáljuk a konjugált vektorok fogalmát. Legyen egy -es szimmetrikus mátrix. A vektorokat -konjugáltaknak vagy egyszerűen konjugáltaknak nevezzük, ha lineárisan függetlenek és minden esetén.

Az irány megválasztására eddig sok módszert láttunk, a gradiens módszerben , a későbbiekben ismertetésre kerülő DFP módszerben . A DFP módszer úgy is felfogható, hogy nem a legnagyobb csökkenés irányába mutató vektort használjuk irányvektornak, hanem annak egy mátrix-szal szorzott transzformáltját. A konjugált gradiens módszerben sem a gradiens vektor -szeresét használjuk irányvektornak, hanem ahhoz egy vektort adunk hozzá, amely az előző lépésben használt irányvektor irányába mutat, képletben

Több módszer ismert az szorzóra, Fletcher és Reeves az alábbi szorzót javasolta

Fletcher-Reeves módszer algoritmusa:

Induló lépés : Kiindulunk egy tetszőleges vektorból és a irányvektorból.

Közbülső lépés:

  1. Megállunk, ha , egyébként folytatjuk az eljárást a következő sorral.

  2. Megoldjuk a minimalizálási feladatot -ra, legyen az optimális megoldás .

  3. Meghatározzuk a következő közelítést: .

  4. Irányvektor meghatározása: .

  5. Folytatjuk az eljárást, .

4.10. Tétel. Legyen a minimalizálandó függvény kvadratikus, azaz . Alkalmazzuk ennek a feladatnak a megoldására a Fletcher-Reeves módszert, amelyben a kiindulásnál legyen tetszőleges vektor és . Végezzünk el darab iterációt. Ha minden esetén , akkor igazak az alábbi állítások

(1) kereső irányok ,

(2) kereső irányok javító (csökkenő) irányok

(3) .

4.8. Példa. Oldjuk meg az alábbi optimalizálási feladatot Fletcher-Reeves módszerrel. Legyen az a startvektor és legyen a pontossági tűrés.

Megoldás:

A célfüggvény gradiense:

1. lépés: Az első lépés megegyezik a gradiens módszerrel.

, ,

Az egyváltozós optimalizálási feladat és megoldása:

2. lépés: , .

Ettől a lépéstől térünk el a gradiens módszertől, mert az irányvektor meghatározása kissé bonyolultabb. Ehhez számítsuk ki a két utolsó közelítéshez tartozó gradiensek hosszának négyzetét:

Az új irányvektor

Az egyváltozós optimalizálási feladat és megoldása:

3. lépés: , .

Mivel az közelítéshez tartozó gradiensvektor zérus, így befejezzük az eljárást.

Az pontban teljesül a minimum szükséges feltétele, így megkaptuk az optimális megoldást.

Mivel a minimalizálandó függvényünk kvadratikus, így érvényes a Fletcher-Reeves módszerre a fentebb közölt tétel állításai.

4.2.15. Newton-módszer vonalmenti minimalizálással

Tekintsük most néhány Newton-típusú módszer vonalmenti minimalizálással kiegészített változatát!

4.2.16. Módositott Newton-módszer vonalmenti minimalizálással

Az egyik legismertebb, vonalmenti minimalizálást is használó kvázi-Newton módszer a Davidon-Fletcher-Powell-féle DFP eljárás.

4.2.17. DFP (Davidon-Fletcher-Powell) eljárás

Adott egy kiinduló pont és egy szimmetrikus pozitív definit mátrix.

Itt is, hasonlóan a BFGS-módszerhez, beszélhetünk egyrangú illetve kétrangú formuláról. A

formula az úgynevezett kétrangú formula. Az egyrangú formula a következő:

4.9. Példa. Oldjuk meg az alábbi optimalizálási feladatot Davidon-Fletcher-Powell módszerrel a kétrangú formulát használva a előállítására.

Legyen az startvektor és a Hesse mátrixot helyettesítő startmátrix az alábbi.

Megoldás:

Előkészületként határozzuk meg a célfüggvény gradiensét

1. lépés: Az első lépés megegyezik a gradiens módszerrel.

Az egyváltozós optimalizálási feladat és megoldása:

Ennek megoldása:

2. lépés:

Most előkészítjük a mátrix számítását.

Az ponthoz tartozó irányvektor:

.

Az egyváltozós optimalizálási feladat és megoldása:

Ennek megoldása:

3. lépés:

Most jön a mátrix számítása.

Mivel az közelítéshez tartozó gradiensvektor zérus, így befejezzük az eljárást. Az pontban teljesül a minimum szükséges feltétele, így megkaptuk az optimális megoldást.

Mivel a minimalizálandó függvényünk kvadratikus, folytassuk tovább a számítást, hogy az algoritmushoz közölt tételek állításainak helyességét ellenőrizhessük.

A célfüggvény Hesse mátrixa:

és ellenőrizhetjük a fenti tételek egyik állításának helyességét, miszerint a mátrix a Hesse mátrix inverze.

A Davidon-Fletcher-Powell módszer az egyik leggyakrabban alkalmazott eljárás.

4.2.18. Hooke-Jeeves módszer

Végül megadunk egy egyszerű, lassú, de sok esetben használható eljárást.

Az irányok ciklikusan rendre az -dimenziós egységkoordináta irányok. Képletben kifejezve

A Hooke-Jeeves módszer bizonyos esetekben nem konvergál. Ennek oka az irányok rögzítése. Szokás az választással élni, aszerint, hogy az , vagy feltételek közül melyik teljesül. Más hatékonyabb módszerek pl. Rosenbrock-módszer az irányokat nem rögzítik, hanem valamilyen elv alapján változtatják.

4.3. A büntetőfüggvény módszerek

Az alábbiakban közölt módszerek alapgondolata az, hogy a feltételes optimalizálási feladat megoldását visszavezetjük feltétel nélküli optimalizálási feladatok sorozatos megoldására. Ezt a megoldási eljárást szokás SUMT (Sequential Unconstrained Minimization Technique) módszer néven is emlegetni. Két változatát ismertetjük, az egyik a büntetőfüggvényes eljárás, a másik a korlátfüggvényes eljárás. Mindkét módszer lényege az, hogy a feltételeket beépíti a célfüggvénybe, így kapunk egy feltételnélküli optimalizálási feladatot.

Ezen két módszer közül mi a büntetőfüggvények módszerét ismertetjük.

Vizsgáljuk elsőként az

egyenlőségi feltétellel megadott szélsőérték feladatot, ahol és A SUMT módszerek alapgondolata R. Couranttól származik 1943-ból. Az ötlet a következő: Vezessük be a

büntetőfüggvényt és az eredeti feladat helyett vizsgáljuk a

feltétel nélküli szélsőérték feladatot a büntető paraméter különböző értékeire!

Ha , akkor . Ha , akkor van legalább egy index, hogy . Ezért

Tehát attól függően, hogy milyen mértékben tér el a vektortól és mekkora a paraméter. Ha nagyobb, a büntetés is nagyobb.

Vizsgáljuk meg a következő két egyszerű példát!

4.10. Példa. Az feladat célfüggvényét, megengedett megoldásainak halmazát és a értékhez tartozó büntetőfüggvényt ábrázolja az alábbi ábra.

 A Courant-féle büntetőfüggvény. 

Látható, hogy büntetőfüggvény a célfüggvényt a megengedett megoldások halmazán (az egységkörön) kívül mintegy felhajlítja.

4.11. Példa. Legyen

Ekkor , amelynek minimumhelye . Ez esetén tart -hez, az eredeti feladat minimumhelyéhez. Ha tehát elég nagy, akkor elég pontosan megközelíti az eredeti feladat megoldását (lásd a következő ábrát).

 Courant-féle büntetőfüggvény különböző értékekre 

A büntetőfüggvény módszerek egy lehetséges általános sémája a következő.

A SUMT algoritmus

Általában a sorozatot használjuk. Az eljárás konvergenciáját mondja ki a következő tétel.

4.11. Tétel. Tegyük fel, hogy és folytonos függvények, alulról korlátos a megengedett megoldások nemüres halmazán és

Ha monoton növekedő, akkor

(i) A sorozat monoton növekedő.

(ii) A sorozat monoton csökkenő.

(iii) Az sorozat monoton növekedő.

Továbbá és az sorozat bármely torlódási pontja megoldása a feltételes szélsőérték feladatnak.

Bizonyítás. Legyen és . Az definíciójából és 4.7-ből

következik. Az első két egyenlőtlenség bizonyítja az állítást. Az egyenlőtlenség láncból adódó

egyenlőtlenség igazolja az állítást. A egyenlőtlenségből kapjuk, hogy

amiből az sorozat monoton növekedése következik. Az definíciója és 4.9 alapján

Ha , akkor

miatt, . Ha , akkor a folytonosság miatt . Ezért . De 4.10 miatt , amiből következik. A két egyenlőtlenség együtt az egyenlőséget adja, amivel állitásunkat maradéktalanul igazoltuk.

Megjegyezzük, hogy a tételben nem tettünk fel differenciálhatóságot és a szokásos Kuhn-Tucker feltevéseket sem.

Vizsgáljuk most az egyenlőtlenségeket is tartalmazó

feltételes szélsőérték feladatot. Ekkor a megfelelő büntetőfüggvény

A büntetőfüggvény geometriai tartalma az egyenlőségi feltételek esetén már ismert. Ha valamely egyenlőtlenségre, mondjuk a -edikre fennáll, hogy , akkor . Igy az ebből származó büntetés mértéke .

A fenti büntetőfüggvénnyel a SUMT eljárás változatlan. Változik azonban az eljárás konvergenciája.

Sok esetben a büntetőfüggvény Hesse-mátrixa sok esetben rosszul kondicionált lesz nagy esetén. Ha a Newton módszeren alapuló minimalizálást alkalmazzuk, akkor Broyden és Attia egy speciális lineáris egyenletrendszer megoldó módszerét lehet alkalmazni. A probléma egy elterjedtebb kezelési módja a Powell-féle büntetőfüggvény, amelynek alakja

ahol és . A paraméterek az origótól való eltolást, a paraméterek pedig a büntetés mértékét szabályozzák. A Powell-féle büntetőfüggvény jellegében egy nemlineáris legkisebb négyzetes feladat célfüggvénye.

A 4.11 példa esetén , amelynek minimumhelye .

A Powell-féle büntetőfüggvény egy jobban számitható alakját kapjuk, ha bevezetjük a változókat és elhanyagoljuk az -től független tagot. Ekkor a

büntetőfüggvényt kapjuk, ahol és .

Megmutatható, hogy létezik olyan vektor, amelyre a minimuma lesz minden esetén (Itt az , () jelölést használjuk).

A következő eljárást lehet ennek alapján megfogalmazni:

Powell javaslata a és meghatározására a következő. Legyen

A Powell módszer algoritmusa

4.12. Példa. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel:

Megoldás

A feltétel nélküli segédfeladat:

A kiinduló vektor legyen , a kiinduló büntető paraméter pedig legyen . A megoldás egyes lépéseit az alábbi táblázatban közöljük:

A feladat optimális megoldása: . A táblázatban jól látható, hogy a feladat megoldása hogyan konvergál az optimális megoldáshoz, továbbá az is látható, hogy a büntetőparaméter növekedésével növekszik, míg csökken.

4.13. Példa. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel:

Megoldás

A kiinduló vektor legyen , a kiinduló büntető paraméter pedig legyen . A feltétel nélküli segédfeladat:

A megoldás egyes lépéseit az alábbi táblázatban közöljük:

Az optimális megoldás: . A táblázatban jól látható a feladat megoldásának az optimális megoldáshoz való konvergálása, továbbá az is látható, hogy a büntetőparaméter növekedésével növekszik, míg csökken.

5. fejezet - A játékelmélet elemei

A döntéshozatal számos eljárása és technikája ismert bizonytalanság esetén. A két legjobban kidolgozott terület a játékelmélet és a statisztikai döntéselmélet. A játékelmélet szoros kapcsolatban áll a gazdaság egyensúlyi modellezésével is. A következőkben a (stratégiai, nemkooperatív) játékelmélet néhány elemét vesszük sorra.

5.1. Bimátrix játékok

Legyen két játékosunk és akik egymástól függetlenül választják meg stratégiájukat. Legyen az játékosnak különböző stratégiája, a játékosnak pedig . A játékosok nyereményei a két játékos együttes stratégiájától függenek. Jelölje az játékos nyereményét, pedig a játékos nyereményét, ha az -edik stratégiáját, pedig a -edik stratégiáját játssza. A és függvényeket kifizető függvényeknek nevezzük. Legyen

Ekkor az

mátrixokat az , ill. játékos kifizető mátrixának nevezzük. A most definiált un. bimátrix játékot általában a kifizető mátrixokból álló mátrixpár formában adjuk meg.

5.1. Definíció. Az stratégiapárt az bimátrix játék Nash-féle egyensúlypontjának nevezzük, ha minden és esetén fennáll, hogy

Az egyensúlyi pont olyan stratégia pár, amelyre igaz, hogy ha a játékosok bármelyike eltér az egyensúlyi stratégiától, mialatt a másik tartja az egyensúlynak megfelelő stratégiát, akkor az egyensúlyi stratégiától eltérő játékos nem tudja megnövelni nyereményét. A kifizető mátrixok elemeiben megfogalmazva pár egyensúlyi stratégia, ha fennáll, hogy

Ez azt jelenti, hogy az mátrixban a -adik oszlop legnagyobb eleme, míg a mátrixban az -adik sor legnagyobb eleme.

5.1. Példa. Az

játék esetén egyetlen egyensúlyi pár van és ez .

5.2. Mátrixjátékok

5.2. Definíció. Ha , akkor az bimátrix játékot zérusösszegűnek, vagy mátrixjátéknak nevezzük.

Ekkor az stratégia pár esetén az játékos nyeresége , míg a játékos nyeresége (vesztesége ). Tehát az egyik játékos nyereményét a másik játékos fizeti. A játék szokásos megadási formája:

Zérusösszegű játék esetén az stratégiapár akkor és csak akkor egyensúlypont, ha az mátrixban a -adik oszlop legnagyobb és az -adik sor legkisebb eleme. Ebben az esetben az elemet az kifizetőmátrix nyeregpontjának is nevezzük.

A mátrixjátékokat és nyeregpontjukat elsőként Neumann János vizsgálta az 1920-as évektől. Tőle származik a mátrixjátékok úgynevezett kevert bővítése is, amely a játék sokszori lejátszását tételezi fel. Egy mátrixjáték kevert bővítésének mindig van egyensúly-, vagy nyeregpontja. A Nash-féle egyensúlyi pont koncepció 1950-ből származik a Neumann-féle nyeregpont fogalom többváltozós általánosításaként.

5.2. Példa. Két játékos egymástól függetlenül egy-egy számot ír le az számok közül. Ha a számok összege páros, akkor kifizeti -nak az összeget. Ha a számok összege páratlan, akkor fizeti ki az összeget -nek.

Egyik játékosnak sincs információja a másikról. Mindkét játékosnak három választása van: , , vagy . A játék egy -es zérusösszegű játék a következő mátrixszal:

A játéknak nincs Nash-egyensúlypontja.

De van-e jó stratégia? Választhat-e olyan stratégiát, ami mindig jó számára?

5.3. Példa. [kétujjas Morra v. malom játék] Mindkét játékos felmutatja egy, vagy két ujját és egyidejűleg becslést ad a másik játékos által felmutatandó ujjak számára. Ha mindkét játékos jól, vagy rosszul becsül, akkor a nyeremény . Ha csak az egyik becsül jól, akkor nyereménye a két játékos által mutatott ujjak összege, amit a másik játékos fizet.

Minden stratégia két komponensből áll: , ahol az ujjak száma, a másik játékos által mutatott ujjak számának becslése. Mindkét játékosnak lehetséges stratégiája van: , , , . A -es mátrixjáték kifizető mátrixa:

A játéknak szintén nincs egyensúlypontja.

5.3. A játék alsó és felső értéke, a ”minimax” elv

A következőkben biztonsági stratégiákat próbálunk meghatározni a játékosok számára.

Ha az -edik stratégiát választja, akkor feltehetjük, hogy olyan stratégiát választ, amelyre nyereménye ( vesztesége) minimális. Ez az a stratégia lesz, amelyre -edik sora minimális. Jelölje ezt a legkisebb értéket

Ha most olyan stratégiát keres, amelynél kevesebbet nem nyerhet, akármit is játszik , akkor az értékek maximumát kell keresni. Legyen ez az érték

Legyen olyan stratégia, amelyre . Ha az játékos az stratégiát játssza, akkor nyereménye bármilyen stratégiája esetén garantáltan legalább . Az stratégiát ”maximin” stratégiájának, az értéket maximin nyereségének, és/vagy a játék alsó értékének nevezzük.

Hasonló okfejtés érvényes a játékosra is. abban érdekelt, hogy nyereségét minimalizálja. Legyen stratégiája . Tekintsük az értékek maximumát a -edik oszlopban:

Vegyük ezek minimumát:

A mennyiséget a játék felső értékének, vagy ”minimax” értékének nevezzük. Legyen olyan stratégia, amelyre . A stratégia ”minimax” stratégiája. Ha a stratégiát játssza, akkor nem veszíthet -nál nagyobb összeget.

Az sor minimumokkal és oszlop maximumokkal az alábbi módon ki lehet egészíteni a játék mátrixát:

A maximin és minimax stratégiákat szokás közös néven minimax stratégiáknak is nevezni. Tekintsük ismét a korábbi példákat!

5.4. Példa.

Ekkor . Az játékos maximin stratégiája: . Ha ezt szisztematikusan játssza, akkor legfeljebb dollárt veszíthet játékonként. Az ellenfél minimax stratégiája vagy . Ez garantálja, hogy vesztesége nem nagyobb mint . Ha eltér a maximin stratégiától, akkor játszhatja a -ik stratégiáját és -re redukálja nyereségét. Ha tér el a maximin stratégiától, akkor a -ik stratégia választásával -ra növelheti nyereségét.

5.5. Példa. [kétujjas Morra/malom játék]

Ekkor .

Az eddigi példákban megfigyelhettük, hogy . Igaz a következő eredmény.

5.3. Tétel. .

Bizonyítás. Definíció szerint

Tehát fennáll, hogy

ami bizonyítandó volt.

A tétel sokkal általánosabb esetben is igaz. Ha

akkor a minimax stratégia stabil. Ekkor a játéknak nyeregpontja, azaz Nash-egyensúlypontja van.

5.4. Mátrixjátékok kevert bővítése

A továbbiakban is zérusösszegű játékokat vizsgálunk. Feltesszük, hogy a játékot sokszor játsszuk, mindkét játékos véletlenszerűen választja stratégiáját egy-egy diszkrét valószínűségeloszlás alapján és nyereségének várható értékét kívánja maximalizálni (minimalizálni).

Legyen az játékos új stratégia halmaza

a játékosé pedig

Egy tetszőleges stratégia azt jelenti, hogy az játékos -edik stratégiáját az vektor -edik komponensének megfelelő valószínűséggel választja. Hasonló az stratégia jelentése a játékos esetén.

Ha végigjátsszuk az és az stratégiának megfelelő összes játékot, akkor az játékos nyereményének várható értéke

míg a játékosé

A és függvényeket a kevert bővítésű játék kifizetőfüggvényeinek nevezzük.

Levezetésük a következő: az stratégia pár megválasztásának valószínűsége a függetlenség miatt . Ilymódon a diszkrét

valószínűségeloszlásokat nyerjük, amelyek várható értékei éppen és .

Az új, úgynevezett kevert bővítésű mátrixjátékot az szimbólummal jelöljük. Egy , stratégia pár egyensúlyi stratégia (egyensúlypont), ha fennáll, hogy

Figyelembevéve, hogy , az utolsó egyenlőtlenség a

alakban írható fel. összevonva az egyenlőtlenségeket kapjuk, hogy akkor és csak akkor egyensúlypontja a játék kevert bővítésének, ha kielégíti a

nyeregpont feltételt. Mátrix formában felírva ez a következő

5.4. Tétel. [Neumann János, 1928] Tekintsük az mátrixjáték kevert bővítését! Ekkor léteznek a

és

mennyiségek és ezek egyenlők.

A tételből következik az alábbi megfogalmazás is.

5.5. Tétel. [Neumann János] Az kevert bővítésű mátrixjátéknak mindig van Nash-egyensúlypontja. A érték minden egyensúlyi stratégia párra ugyanaz.

A tétel azt mondja ki, hogy a kevert bővítésű mátrixjátéknak mindig van nyeregpontja, azaz Nash-féle egyensúlypontja. A közös értéket a játék értékének nevezzük. A érték jelentése: az stratégia szerint lejátszott mérkőzés sorozatban az játékos nyereményének várható értéke biztosan , míg a játékos vesztesége biztosan . Ettől eltérő nem egyensúlyi stratégia esetén nyereségének várható értéke csökken, a játékos veszteségének várható értéke pedig nő (a veszteség mértéke csökken!).

5.6. Példa. Tekintsük az

mátrixjátékot! A játék kevert bővítését az

statégia halmazok és a

kifizetőfüggvény adja meg. Ekkor

és

A következő esetek lehetségesek:

Ennek minimuma a intervallumon . Tehát . Hasonlóan láthatjuk be, hogy

amelynek maximuma a intervallumon . Tehát és . A

egyenletnek végtelen sok megoldása van: .

Vizsgáljuk most azt, hogy mely megoldások nyeregpontjai a kifizetőfüggvénynek.

Egyszerű behelyettesítéssel kapjuk, hogy

mindig teljesül, de

csak akkor teljesül, ha . Hasonlóképpen eljárva kapjuk, hogy

mindig teljesül, de

csak akkor, ha . Tehát csak egy egyensúlypontja van a játék kevert bővítésének: és .

Ez azt jelenti, hogy mindkét játékos a pénzfeldobás módszerével választja stratégiáját és ennél jobb stratégia nincs. Megjegyezzük még, hogy és !

5.7. Példa. Tekintsük az

mátrixjátékot! A játék kevert bővítését az

statégia halmazok és a

adják meg. Keressük a függvény nyeregpontját! Tekintsük a függvény

gradiensét és

Hesse-mátrixát! A gradiens az és pontban tűnik el. A Hesse mátrix sajátértékei: .

Tehát az pont nyeregpont, a megfelelő

kevert stratégiák (vsz. eloszlások) pedig a kevert játék Nash-egyensúlypontját adják. A kevert bővítésű játék értéke: . Az alapul szolgáló mátrixjáték alsó és felső értéke: , .

A most látott példák megoldásai ad hoc jellegűek voltak, amelyek bonyolultabb esetekben nem feltétlenül vezetnek eredményre.

5.4.1. A mátrixjáték és a lineáris programozás kapcsolata

Az eddigiekben sok mindennel megismerkedtünk, de egyetlen fontos kérdésre még nem adtunk választ, nevezetesen arra, hogy minden mátrixjáték megoldható-e? A következőkben erre a kérdésre az igenlő választ megadó tételt, a játékelmélet alaptételét ismertetjük. A tételt Neumann János bizonyította be először, így szokás Neumann-tételnek is nevezni. A tételre konstruktív bizonyítást adunk, amellyel megadjuk a mátrixjáték lineáris programozással való megoldásának módját is.

5.6. Tétel. [A játékelmélet alaptétele (Neumann-tétel)] Tetszőleges kifizetési mátrixszal rendelkező mátrixjátéknak létezik nyeregpontja, azaz létezik olyan stratégiapár, hogy

minden stratégiapárra teljesül.

Bizonyítás. A játékos a következőképpen okoskodik. Ha a játékosnak sikerülne olyan stratégiát választania, amelyre

akkor legalább várható nyereségre tesz szert. Ha ugyanis a játékos stratégiája , a játékosnak pedig az 1. stratégiája , akkor a játékos várható nyeresége

amelyből az előbbi állítás kiolvasható. Hasonlóan, ha a játékos 2. stratégiája , akkor legalább várható nyereséget akkor tud elérni a játékos, ha

Ezt a játékos minden stratégiájára felírhatjuk. Így a játék során a játékos nyereménye legalább

lesz. Nyilvánvaló, hogy célja a nyereményének maximalizálása, tehát olyan stratégiát próbál választani, amelynél minden indexre legalább nyereségeket tud elérni és az össznyeresége minél nagyobb legyen, azaz

Mint látható a játékos stratégiájának meghatározására egy lineáris programozási feladat adódott, amelyet a mátrix-vektor jelölésekkel egyszerűbben is írhatunk:

Most nézzük meg a játékos hasonló okoskodását. Ha a játékosnak sikerülne olyan stratégiát választania, amelyre

akkor legfeljebb várható vesztesége lenne, amikor a játékos 1. stratégiája . Ezt a játékos minden stratégiájára felírhatjuk. Ekkor a játék során a játékosnak legfeljebb vesztesége lesz és a játékos célja, hogy ezt a veszteségét minimalizálja. A játékos stratégiájának meghatározására tehát az alábbi lineáris programozási feladat szolgál:

A két játékos stratégiáinak meghatározására szolgáló lineáris programozási feladatok egymásnak duálisai. A második feladatot tekintsük primál, az elsőt pedig duál feladatnak. Könnyen megállapíthatjuk, hogy mind a primál, mind a duál feladatnak van lehetséges megoldása. Például az ill. az lehetséges megoldások, mert mindig található hozzájuk olyan ill. , amelyek kielégítik a feltételeket. A lineáris programozás dualitási tétele értelmében pedig a fenti lineáris programozási feladatpárnak van optimális megoldása is. Emlékeztetőül a lineáris programozás dualitási tétele azt mondja ki, hogy ha a primál és a duál feladatnak is van lehetséges megoldása, akkor van mindkettőnek optimális megoldása is. Jelölje az optimális megoldásokat ill. . Ismert, hogy a célfüggvényeknek az optimális értékei megegyeznek, jelöljük ezt -vel, azaz . Most pedig megmutatjuk, hogy a fenti lineáris programozási feladatpár megoldása a mátrixjáték megoldását szolgáltatja, vagyis az vektor a játékos, az vektor a játékos nyeregponti stratégiája és a közös célfüggvényérték pedig a játék értéke.

Az optimális megoldás egyben lehetséges is, így . Szorozzuk be az egyenlőtlenséget jobbról tetszőleges stratégiával, ekkor kapjuk, hogy

Hasonlóan az optimális megoldás egyben lehetséges is, így . Szorozzuk be az egyenlőtlenséget balról tetszőleges stratégiával, ekkor kapjuk, hogy

A fenti két egyenlőtlenséget egybevetve tehát minden és stratégiára fennáll, hogy

Ha az és az stratégiák helyébe az , stratégiákat helyettesítjük, azt kapjuk hogy

Az előző egyenlőtlenségből viszont az

egyenlőtlenség adódik, ami a nyeregponti összefüggéssel azonos, tehát a lineáris programozási feladatpár optimális megoldásai a mátrixjáték egyensúlyi stratégiái, a pedig a játék értéke. Ezzel a Neumann-tételt bebizonyítottuk.

Összefoglalva tehát a mátrixjáték megoldásához meg kell oldanunk az alábbi lineáris programozási feladatpárt:

A fenti lineáris programozási feladatpárban szereplő és ismeretlenekre a nemnegativitási feltétel nem vonatkozik, azaz előjelkötetlen változók. A megoldandó lineáris programozási feladatpárt át lehet alakítani úgy, hogy könnyebben kezelhető legyen. Ehhez a primál feladat minden feltételét -val, a duál feladat minden feltételét pedig -val elosztjuk. Az és változó mennyiségek, értéküket nem ismerjük, így az osztással problémák lehetnek. Azonban, ha biztosítani tudjuk, hogy és értékei csak pozitívok lehetnek, akkor valóban eloszthatjuk az egyenlőtlenségeket, mert az egyenlőtlenség iránya nem változik meg.

Ha az mátrix pozitív, akkor az és lehetséges értékei is csak pozitívak lehetnek. Ezt mindig elérhetjük úgy, hogy a kifizetési mátrix minden eleméhez hozzáadunk egy tetszőleges számot. Ekkor az új kifizetési mátrixszal jellemzett mátrixjáték és az eredeti mátrixjáték nyeregpontja ugyanaz marad, csak a játék értéke változik értékkel. Tehát ha feltételezzük, hogy az mátrix pozitív (ha nem az, akkor mindig pozitívvá tehető), a primál feladat -val való osztás után az alábbi alakot ölti:

Vezessük be a új változót. A második összefüggés ily módon az egyenletté alakul és a minimalizálása egyenértékű a reciprokának, azaz az mennyiségnek a maximalizálásával. Hasonlóképpen a duál feladatot is átalakíthatjuk, ahol az új változót -vel () jelöljük. Ekkor az alábbi kanonikus alakú lineáris programozási feladatpárt nyerjük, ne felejtsük, hogy ebben az esetben már feltételezéssel élünk:

Könnyen meggyőződhetünk, hogy a két feladat egymásnak duálisa. Mindkét feladatnak van lehetséges megoldása (például a ill. elegendően nagy vektor), így optimális megoldása is. Jelölje az optimális megoldásokat ill. , a célfüggvények közös optimális értékét pedig . Az értéke az feltevés miatt pozitív.

A lineáris programozási feladatpár optimális megoldásaiból a játékos , a játékos nyeregponti stratégiáját és a játék értékét az alábbiak szerint számítjuk ki:

5.8. Példa. Oldjuk meg az alábbi sémával adott mátrixjátékot. E példán keresztül mutatjuk meg a mátrixjáték lineáris programozással történő megoldását.

A lineáris programozási feladatpár a következő alakban irható:

A feladatpár megoldásához az alábbi induló táblát írhatjuk fel, amennyiben a primál feladatot tekintjük alapfeladatnak (a hiányváltozókat -vel jelölve):

Tovább nem is folytatjuk a megoldást, mivel az előjelkötetlen változó és az egyenlet miatt a megoldás bonyolult. A másik lineáris programozási feladatpár példánkban az alábbiak szerint írható. Ne feledkezzünk el, hogy az mátrix elemeihez hozzá kell adni egy olyan számot, hogy a mátrix pozitívvá váljon. Példánkban 3-at adtunk minden elemhez.

Ha baloldali feladatot tekintjük primál feladatnak, akkor a megoldás szimplex módszerrel végezhető és a mint primál megoldás, a pedig mint duál megoldás olvasható ki a szimplex táblázatból. Ha pedig a jobboldali feladatot tekintjük primál feladatnak, akkor a megoldás duál módszerrel végezhető és a mint primál megoldás, a pedig mint duál megoldás olvasható ki a szimplex táblázatból. Az alábbiakban a szimplex módszerrel történő megoldás induló és optimális tábláját közöljük.

A lineáris programozási feladatpár optimális megoldása:

A mátrixjáték megoldása:

Megjegyezzük, hogy végtelen sok lineáris programozási feladat írható fel. Példánkban az eredeti mátrixszal is felírhattuk volna a lineáris programozási feladatpárt, mivel a játék értéke pozitív. Ezt előre nem lehet tudni, ezért javasoltuk azt, hogy az mátrix elemeihez adjunk annyit, hogy pozitív legyen.

5.9. Példa. A jól ismert ,,kő-papír-olló" játékban mindegyik játékos ,,követ", ,,ollót" vagy ,,papírt" mutat egyidejűleg (a kő jele az ökölbe szorított kéz, az olló jele a mutató és a középső ujj szétnyitása, a papír jele pedig a vízszintes tenyértartás). Ha mindketten ugyanazt jelzik, akkor egyik sem nyer, egyébként a nyerés azon alapszik, hogy az olló szétvágja a papírt, a kő kicsorbítja az ollót, a papír beborítja a követ. A fizetés kő-olló esetén legyen , olló-papír esetén legyen , papír-kő esetén pedig legyen pénzegység. Határozzuk meg a nyeregponti stratégiákat!

Először felírjuk a kifizetési mátrixot:

A kifizetési mátrix minden eleméhez adjunk -et a pozitivitás biztosítása érdekében. Ezután a lineáris programozási feladatot oldjuk meg, az induló és az optimális szimplex táblák az alábbiak: A lineáris programozási feladatpár megoldása:

A mátrixjáték megoldása:

A megoldás szerint mindkét játékosnak a kő, olló, papír jelzését arányban kell keverni. A játék értéke 0, így a játék igazságos. A 4. észrevétel alapján előre tudhattuk, hogy mindkét játékosnak ugyanaz lesz az egyensúlyi stratégiája és a játék értéke zérus. Ez utóbbit felhasználva elég lett volna a kifizetési mátrix elemeihez -et (vagy tetszőleges pozitív számot) hozzáadni, mert akkor az új játéknak már biztosan pozitív lesz az értéke.

5.10. Példa. Oldjuk meg a kétujjú Morra játékot. Mivel a játék szimmetrikus, a 4. észrevétel értelmében a játék értéke zérus. Ebben az esetben a kifizetési mátrixhoz elegendő például -et hozzáadni, hisz ekkor már az új mátrixjáték értéke pozitív lesz. Az nem érdekes, hogy az elemek között lesz és esetleg negatív is. Most csak a mátrixjáték megoldását, azaz a nyeregponti stratégiákat és a játék értékét írjuk fel. Megoldásként két nyeregponti stratégia is adódott. Mivel a példában szereplő játék szimmetrikus, így a két játékos egyensúlyi stratégiája megegyezik, a játék értéke pedig zérus:

Igazolható, hogy több egyensúlyi stratégia esetén az egyensúlyi stratégiák minden konvex lineáris kombinációja is egyensúlyi stratégia, azaz a mátrixjáték megoldása:

5.11. Példa. Oldjuk meg az alábbi mátrixszal adott játékot. A megoldás során bemutatjuk a dominancia elv használatát is, amellyel a lineáris programozási feladatpár mérete csökkenthető.

Érdemes azzal kezdeni a megoldást, hogy megállapítjuk egyszerű számolással, hogy a mátrixjátéknak van-e tiszta nyeregponti stratégiája. Ha van, akkor megtaláltuk a megoldást. Ezután érdemes domináns stratégiákat keresni. A mátrix 3. sora dominálja az 1. és a 2. sort, így a játékos biztosan nem fogja e két sort választani, tehát elhagyható. Az 5. oszlop pedig az 1., 2. és a 6. oszlopot dominálja, így az utóbbi 3 oszlop is elhagyható. A redukció után az alábbi mátrix keletkezik:

Ebben a mátrixban pedig a 3. sor dominálja a 4. sort, így a mátrix tovább redukálható:

Vegyük észre, hogy e mátrixban az 1. és 2. oszlop átlaga dominálja a 3. oszlopot, így a 3. oszlop is elhagyható:

Végül pedig az látjuk, hogy az első két sor átlaga a 3. sort adja, így a 3. sor is elhagyható. Végeredményben az alábbi -es kifizetési mátrix adódik:

A fenti -es játéknak az egyensúlyi stratégiáit pedig a már megismert nagyon egyszerű módszerrel meghatározhatjuk, amely az alábbi:

Az eredeti mátrixjáték egyensúlyi stratégiái pedig:

6. fejezet - Egészértékű lineáris programozási (ILP) feladat

Számos optimalizálási feladatban megköveteljük, hogy a döntési változó értéke csak egész szám lehet, ezeket a feladatokat egészértékű programozási feladatoknak nevezzük, szokásos elnevezés még az integer programozás is.

A következőkben az integer programozásban használatos elnevezéseket ismertetünk.

Ha egy optimalizálási probléma minden döntési változójáról megköveteljük az egészértékűséget, akkor azt tiszta integer programozási feladatnak nevezzük, amennyiben nem mindegyik döntési változó egész, akkor vegyes (mixed) integer programozási feladatnak nevezzük. Abban az esetben, amikor az integer döntési változó csak vagy értéket vehet fel, akkor tiszta (vegyes) 0-1 programozási feladatról beszélünk, szokásos még a tiszta (vegyes) bináris programozási feladat elnevezés is. Szigorú értelemben minden integer programozási feladat nemlineáris feladat, mivel a probléma függvényei csak diszkrét értékeknél vannak értelmezve. Azonban egy integer programozási feladatot integer lineáris programozási feladatnak nevezünk, ha eltekintünk a döntési változók egészértékűségétől és az így keletkező feladat lineáris programozási feladat, azaz a probléma összes függvénye lineáris függvény.

A következő fejezetekben az integer lineáris programozási feladatokkal fogunk foglalkozni, azok néhány ismert modelljét és a leginkább alkalmazott megoldási módszereket mutatjuk be. Az integer lineáris programozási feladat standard alakja a következő:

6.1. Egészértékű optimalizálási modellek

Ebben a fejezetben néhány olyan modellt ismertetünk, amelyekben a döntési változó csak egész szám lehet.

6.1.1. Befektetési modellek

Ezekben a modellekben különböző befektetési/beruházási lehetőségeket vizsgálunk olyan szempontból, hogy kiválasszuk azokat, amelyek megvalósításához elegendő pénzeszközök állnak rendelkezésünkre és a hozamuk minél nagyobb legyen. Egy- és többperiódusos modelleket különböztetünk meg.

Egyperiódusos befektetési modell

Tegyük fel, hogy legfeljebb 19 millió Ft-ot akarunk befektetni. Négy beruházási/befektetési lehetőséget vizsgálunk, amelyekre vonatkozóan az alábbi ismereteink vannak. Az befektetési lehetőségek megvalósítási költsége rendre 7, 9, 5 és 6 millió Ft. Az egyes befektetési lehetőségek hozama rendre 10, 13, 8 és 7 millió Ft. Melyik beruházási lehetőséget tudjuk teljes mértékben megvalósítani a rendelkezésre álló pénzkeretből úgy, hogy a hozam maximális legyen?

Kézenfekvő az alábbi döntési változó alkalmazása:

Ez az alábbi 0-1 programozási feladatra vezet:

Többperiódusos befektetési modell

Tekintsünk szintén négy befektetési/beruházási lehetőséget, de most két éves időszakot vegyünk figyelembe. Minden évben ismert, hogy legfeljebb mennyi pénzt tudunk a beruházásokra fordítani, ez legyen az első évben 20, a másodikban 25 millió Ft. Az első beruházás az egyes években rendre 6 és 10 millió Ft-os pénzbefektetést követel meg. A második beruházásnál ez 8 és 10 millió Ft, a harmadik beruházás esetén rendre 5 és 7 millió Ft-ot, míg a negyedik esetében pedig 5, 5 millió Ft. Az egyes befektetések hozama a második év végén 20, 25, 15 és 10 millió Ft.

Ennél a modellnél is a 0-1 típusú döntési változót használhatjuk, amely a következő

Az alábbi 0-1 programozási feladatot kapjuk:

6.1.2. Transzformálás 0-1 programozási feladattá

Könnyen látható, hogy minden integer programozási feladat megfogalmazható ekvivalens módon bináris programozási feladatként is. Ez mutatja a 0-1 programozási problémák fontosságát. A leghatékonyabb transzformációs módszer az alábbi kettes számrendszerben való felírás: Legyen az integer nemnegatív változó. Ekkor -et felírhatjuk a következő alakban:

ahol bináris (vagy 0-1) változók.

Ezt akkor lehet jól csinálni, ha ismerünk egy felső korlátot az értékére, mert ebből meg lehet határozni a értékét, és így meg lehet határozni a bináris változók számát (amely a felső korlát kettes alapú logaritmusától függ).

Szokás még a következő transzformációt is használni, ám ebben az esetben a változók száma lényegesen magasabb lesz, mint az előző esetben. Legyen az integer nemnegatív változó és legyen ismert a változónak egy felső korlátja, jelölje ezt integer szám, azaz . Ekkor az integer változó felírható az - változók összegeként, azaz

Egy integer problémánál, ha az változó helyébe behelyettesítjük az bináris változókat, akkor vagy egy tiszta 0-1 feladatot vagy egy vegyes 0-1 feladatot kapunk. Ennek az eljárásnak az a hátránya, hogy túl sok bináris változó keletkezhet, ami a megoldáshoz szükséges számítási időt erőteljesen megnövelheti.

6.1.3. Hátizsák feladat

A feladat elnevezése a következő megfogalmazásra utal. Egy turista a hátizsákjában különböző tárgyat szeretne a túrájára vinni. Az egyes tárgyak súlya legyen . A tárgyaknak van egy értéke (itt nem feltétlenül a tárgyak árára kell gondolni, hanem sokkal inkább a túra alkalmával jelentett hasznosságát mutatja), jelölje ezeket . A turista a hátizsákjában egy bizonyos, előre meghatározott súlynál nem tud többet elvinni.

Ha az összes tárgy nem fér a hátizsákba akkor a turista kénytelen szelektálni és a válogatást úgy végzi, hogy a súlykorlátozás betartása mellett a magával vitt tárgyak összértéke (összhasznossága) minél nagyobb legyen.

A válogatást tárgyanként egy vagy értéket felvehető döntési változóval írhatjuk le. Legyen a döntési változó a , amelynek értéke legyen , ha a -edik tárgyat a turista beteszi a hátizsákjába, ill. értéke legyen , ha a -edik tárgyat nem teszi be a hátizsákjába.

A mennyiség mutatja a hátizsákba behelyezett tárgyak összsúlyát, a mennyiség pedig a hátizsákba behelyezett tárgyak összértékét.

Így a fenti probléma matematikai megfogalmazása a következő: Adott a vektor és a szám, amelyek pozitív egészek és .

Általában minden olyan integer programozási feladatot hátizsák feladatnak neveznek, amelynek csak egyetlen feltétele van. A fentebb megfogalmazott hátizsák feladatot bináris hátizsák feladatnak is nevezhetjük, amelynek két fő jellemző tulajdonsága van:

  • csak egy feltételt tartalmaz,

  • a benne szereplő összes alapadat pozitív egész szám.

Speciális hátizsák feladat az előzőleg bemutatott egyperiódusos befektetési modell, illetve az úgynevezett pénzváltási probléma.

Ebben a feladatban egy adott pénzösszeget akarunk pontosan kifizetni egy adott pénzrendszer címleteivel úgy, hogy minimális számú pénzdarabot használunk fel. Ilyen feladat volt például a készpénzes bérkifizetés, amikor a dolgozók borítékban kapták meg a fizetésüket, vagy az üzletekben történő készpénzes vásárlások esetén amikor a pénztárgép automatikusan a legkevesebb darabszámú pénzt adja vissza.

Feltételezzük, hogy bármilyen címletű pénzből tetszőleges mennyiséget használhatunk fel. Legyen egy pénzrendszer címleteinek száma , az egyes címletek értékei pedig . Legyen a kifizetendő pénzösszeg. Legyen a döntési változó az egész szám, amelynek értéke azt mutatja, hogy a -edik címletből hány darabot használtunk fel a kifizetésnél.

A mennyiség azt jelenti, hogy mennyi pénzt fizetünk ki összesen.

A mennyiség a pénzdarabok számát jelenti.

Ezek alapján a pénzváltási probléma matematikai megfogalmazása a következő:

6.1.4. Halmazlefedési, halmazfelbontási és halmazkitöltési feladatok

A feladat eredetileg az amerikai légitársaságoknál merült fel a személyzet szolgálatra vezénylése kapcsán, de többek között használható a mozdonyvezetők esetében, vagy a kórházi ügyeleti rend kialakításakor is.

A halmazlefedési, a halmazfelbontási és a halmazkitöltési feladatok mindegyikének az a jellemzője, hogy bináris változókkal vannak megfogalmazva és a feltételek együtthatói szintén binárisak. A feltételek jobboldalai és a célfüggvény együtthatói általában tetszőleges egész számok.

A feladatok angol elnevezései rendre Set Covering problem, Set Partitioning problem, Set Packing problem, ennek megfelelően a feladatok rövidítésére rendre az SC, SPart, SPack jeleket használjuk.

Halmazlefedési feladat (SC)

Legyen adott egy alaphalmaz elemmel és adott továbbá az halmaznak részhalmaza. A halmazlefedési feladat a következő: a részhalmazokból válasszunk ki minimális számút úgy, hogy az alaphalmaz minden eleme le legyen fedve, más szavakkal minden alaphalmazbeli elem legalább egyszer szerepeljen a kiválasztott részhalmazok egyesítésében. A következőkben nézzünk erre egy példát:

6.1. Példa. Legyen és , a részhalmazok pedig a következők:

A feladat matematikai megfogalmazásához szerkesszük meg az alábbi ún. incidencia (tartalmazási) mátrixok, amelynek elemei az alábbiak:

Így a példánkban az mátrix:

Az mátrix sorainak és oszlopainak összegére az alábbi megjegyzéseket tehetjük:

jelentése (sorösszeg): azon részhalmazok száma, amelyek tartalmazzák az -t.

jelentése (oszlopösszeg): az részhalmazban lévő elemek száma.

A feladat döntési változóját a következőképpen definiáljuk:

A célfüggvényünk a feladat szerint a kiválasztott részhalmazok száma, ezt pedig a döntési változók összege adja, amelyet minimalizálni kell, azaz

A feltételeket pedig az alábbiak szerint írhatjuk. Akkor mondhatjuk, hogy az alaphalmazt lefedtük a részhalmazaival, ha az alaphalmaz minden eleme legalább egy részhalmazzal le van fedve. A mennyiség azt jelenti, hogy hány darab kiválasztott részhalmaz tartalmazza az elemet, ennek pedig legalább 1-nek kell lennie.

Összefoglalva tehát a halmazlefedési feladat a következőképpen fogalmazható meg:

Általánosított halmazlefedési feladat (GSC)

A standard halmazlefedési feladat adatain kívül legyen adott a részhalmazok kiválasztásának valamilyen értelemben vett költsége, valamint legyen megadva, hogy az egyes elemek legalább -szer legyenek lefedve.

Most a feladatunk úgy kiválasztani a részhalmazokat, hogy a kiválasztott részhalmazok összköltsége minél kisebb legyen és az egyes elemeknek legalább számú lefedése legyen. A feladat matematikai formája:

Halmazfelbontási feladat (SPart)

A halmazfelbontási feladat egy speciális halmazlefedési feladat, itt azonban nem lefedésről van szó valójában, hanem az alaphalmaz részekre bontásáról. A kiválasztott részhalmazoknak tehát diszjunknak kell lennie, azaz minden elem pontosan egyszer legyen lefedve (például el kell kerülni azt, hogy egy mozdonyvezetőnek egyszerre két különböző vonaton is rajta kelljen lennie).

A két feladat között csupán az a különbség, hogy a feltételek relációja " " helyett " ".

Általánosított halmazfelbontási feladat (GSPart)

A halmazfelbontási feladatot ugyanúgy általánosítjuk, mint a halmazlefedési feladatot, amely a következőképpen írható le:

Halmazkitöltési feladat (SPack)

Ebben a problémában az alaphalmazba minél több diszjunk részhalmazát akarjuk betenni. Válasszunk ki tehát a maximális számú diszjunkt részhalmazt. Ebben a feladatban nem követeljük meg, hogy minden elem le legyen fedve, viszont a diszjunkság miatt legfeljebb egyszer lehet lefedve.

A halmazkitöltési feladat matematikai formában a következőképpen írható:

Általánosított halmazkitöltési feladat (GSPack)

A halmazkitöltési feladatot az eddigiekhez hasonlóan általánosítjuk és a következőképpen írható le:

Végül összefoglalásképpen közöljük a három általánosított feladatot mátrixos-vektoros formában:

Adott az mátrix és a vektorok, ahol , a pedig pozitív egész számok.

6.2. Integer lineáris programozási feladatok megoldási módszerei

Az előző fejezetben bemutattunk néhány integer problémát, ebben a fejezetben pedig a megoldási módszereket ismertetjük. Az integer problémák megoldására két módszercsalád, a Vágási módszer (cutting planes) és a Korlátozás és szétválasztás (Branch and Bound) módszer a leginkább elterjedt.

A két módszer lényege a következő.

A Vágási módszer lényege, hogy megoldjuk a lineáris programozási feladatot az egészértékűségi feltétel nélkül. Ha a megoldás egész, akkor készen vagyunk, ha nem akkor új feltételek bevezetésével kényszerítjük ki az egészértékűséget. Itt egy alkalmas hipersíkkal vágjuk le a kapott optimális megoldást úgy, hogy semmilyen egész megengedett megoldást nem vágunk le. Itt nehézséget jelent például hogy tudjuk-e garantálni az eljárás végességét, hány vágás kell az optimum eléréséhez, és mennyire érzékeny a kerekítési hibákra. Az első vágás típusú módszert Gomory dolgozta ki 1958-ban, és ez lett az alapja a későbbi módszerek kifejlesztésének.

A korlátozás és szétválasztás módszere az egyik legelterjedtebb módszer. A lényege pedig abban áll, hogy a feladatot (a megengedett megoldások halmazát) felbontják kisebb feladatokra (részekre). Az így kapott feladatok megoldására pontos alsó vagy felső korlátot tudunk mondani.

6.2.1. Integer és folytonos lineáris programozás kapcsolata

Tekintsük az alábbi integer lineáris programozási feladatot (ILP):

Az ILP feladat egészértékűségi megkötését hagyjuk el, így egy, az eredeti feladathoz rendelt lineáris programozási feladatot kapunk, amelyet az adott egy (IP) egészértékű probléma, folytonos relaxációjának nevezzünk. Ezt a folytonos lineáris programozási feladat (FP) a következő:

Ha adott egy (IP) egészértékű probléma, oldjuk meg a folytonos relaxációját. Amennyiben a kapott megoldás (tulajdonképpen egy poliéder csúcspont) egész koordinátájú, akkor készen vagyunk. Ha nem, akkor hagyjuk el -ot a lehetséges megoldások közül, és próbálkozzunk újra. Természetesen nem akárhogy kell megszabadulnunk -tól, hiszen a célunk, hogy a létrejövő új feladat(ok) is LP feladat(ok) legyen(ek). Ez úgy érhető el, ha -ot egy hipersíkkal vágjuk le a lehetséges megoldások poliéderéről, ami algebrailag azt jelenti, hogy egy plusz feltételt adtunk az eddigi egyenlőtlenségeinkhez.

Mivel az (FLP) feltételi halmaza bővebb, mint az (ILP) feladaté, ebből a tényből azonnal következnek az alábbi állítások:

  1. Ha az (ILP) minimalizálási feladat, akkor az feladat célfüggvényének optimális (minimális) értéke nem lehet (vagyis kisebb vagy egyenlő), mint az (ILP) feladat célfüggvényének optimális (minimális) értéke.

  2. Ha az (ILP) maximalizálási feladat, akkor az feladat célfüggvényének optimális (minimális) értéke nem lehet kisebb (vagyis nagyobb vagy egyenlő), mint az feladat célfüggvényének optimális (maximális) értéke.

  3. Ha az (FLP) feladat feltételi halmaza üres, akkor az (ILP) feladaté is az.

  4. Ha az (FLP) feladat optimális megoldásában a változók egészek, akkor ez az optimális megoldás az (ILP) feladatnak is optimális megoldása.

  5. Ha a célfüggvény együtthatói egész számok, akkor az feladat célfüggvényének optimális értékének egészre kerekített értékére is igaz az 1. és 2. állítás. Minimum feladat esetén felfelé kell kerekíteni, maximum feladat esetén pedig lefelé kell kerekíteni.

Ha tehát megoldjuk az feladatot, akkor ez számunkra értékes információkat ad. Szerencsés esetben azonnal megkapjuk az integer feladat optimális megoldását. Ha ez nem is következik be, akkor viszont az 1. és 2. állítások értelmében az feladat célfüggvényének optimális értékére kapunk korlátokat, minimalizálási feladat esetén alsó korlátot, maximalizálási feladat esetén pedig felső korlátot.

6.2.2. A korlátozás és szétválasztás módszer (Branch and Bound)

A korlátozás és szétválasztás módszer alapjai

A módszer lényegét elsőként a korábban bemutatott egyperiódusos befektetési modellnél felírt példa megoldásán keresztül mutatjuk be.

Emlékeztetőként a feladat matematikai modellje:

A feladathoz rendelt folytonos lineáris programozási feladat (FP) a következő:

Ez a feladat csak egyetlen feltételt tartalmaz, így az egyszerűen megoldható. Rendezzük át a feladatot a (célfüggvény együttható/feltétel együttható) hányadosok csökkenő sorrendjében. Példánkban a hányadosok rendre:

Ezeket csökkenő sorrendbe rendezve az alábbi adódik:

Az változókról térjünk át új változókra úgy, hogy az változók esetén már a csökkenő sorrend fennálljon. A változócsere a következő lesz:

Az új változókkal a megoldandó folytonos lineáris programozási feladat az alábbi:

Ennek a feladatnak az optimális megoldása mindig legfeljebb egyetlen tört értéket tartalmazhat. Ugyanis a csökkenő sorrendbe rendezés utáni első darab ismeretlen értéke legyen , amíg ez a feltételnek megfelel, a -edik ismeretlen, azaz az pedig tört (vagy lehet egész is) úgy, hogy a feltétel egyenlőséggel teljesüljön, a többi ismeretlen értéke .

Tehát a hátizsák terminológiával elmondva a folytonos lineáris programozási feladat megoldása a következő: amíg a soron következő tárgy belefér a hátizsákba, beletesszük, amelyik már nem fér bele azt törtértékkel "tesszük bele", a többit pedig nem tesszük bele. Vagy ebben az esetben azt is mondhatjuk, hogy azokat a befektetéseket teljesen megvalósítjuk amelyekre még van pénzünk, a következőt csak részben, a többit pedig nem (ez mutatja, hogy miért érdemes csökkenő sorrendbe rendezzük a befektetéseket a hozam/kölstég szerint).

A példabeli feladat megoldása az alábbi: Az , mert az 1. befektetés még belefér a keretbe (teljesül az feltétel), az , mert ). Az változó már nem lehet 1, csupán (mert így kapjuk meg az feltételt), az pedig .

Tehát a folytonos lineáris programozási feladat optimális megoldása tehát: , és , a célfüggvény maximális értéke pedig . Ez azt jelenti, hogy az eredeti integer feladat célfüggvényének maximuma nem lehet -nél, sőt az egészértékűség miatt 28-nál sem.

Sajnos azonban a megoldás nem egész, így tovább kell folytatni az eljárást.

Most az eredeti feladatot két részfeladatra bontjuk (ez a ,,szétválasztás"), mivel az optimális megoldásban egyetlen változó értéke, az értéke tört, ezért az egyik részfeladatban legyen , a másikban pedig legyen, azaz először oldjuk meg a feladatokat úgy, hogy az 3. befektetést nem valósítjuk meg, aztán úgy, hogy igen.

1. részfeladat: Legyen . Ekkor a megoldandó feladat:

Ennek az optimális megoldás, amely a következő:

2. részfeladat: Legyen . Ekkor a megoldandó feladat:

Ekkor az FLP feladat a következő:

Ennek az optimális megoldása:

A megoldás menetét egy fagráfon célszerű illusztrálni. A fagráf pontjai reprezeltálják a részfeladatokat. A szétbontás előtti feladatot 0. részfeladatnak nevezzük. A pontokban a folytonos lineáris programozási feladat optimális megoldását és annak optimális célfüggvényértékéből az integer lineáris programozási feladatra kapott célfüggvény korlátot tüntetjük fel. Mivel maximum feladatunk van és a célfüggvény együtthatók egészek, így a korlát meghatározásánál lefelé kerekítünk.

A fenti gráfból leolvashatjuk, hogy az eredeti feladat célfüggvénye -nál nem lehet nagyobb, a részfeladatokból pedig azt, hogy esetén nem lehet -nál, esetén pedig nem lehet -nál nagyobb a célfüggvény maximuma. Most újabb részfeladatokat határozunk meg, amelyet az alábbi elvek szerint végzünk:

  • Szétválasztás elve: Olyan részfeladaton ágaztatunk el, amelynél a megoldás nem integer (aktív részfeladat).

  • Korlátozás elve: Olyan részfeladaton ágaztatunk el, amelynél a célfüggvénykorlát értéke a legnagyobb (minimum feladatnál a legkisebb).

Esetünkben az 1. és a 2. részfeladat egyikében sem kaptunk egész megoldást, mindegyik aktív. Ezek közül a 2. részfeladatot választjuk, mert a célfüggvénykorlát itt a legnagyobb. Mivel a 2. részfeladatban az változó értéke tört, ezért a 2. részfeladat két elágaztatásában ill. . A 3. és a 4. részfeladatot és azok megoldása az alábbiak mutatják:

3. részfeladat:

Ekkor az feladat a következő:

Az optimális megoldás:

Ebben a részfeladatban egész megoldás adódott, tehát ezt az ágat lezárhatjuk.

4. részfeladat: Legyen .

Ekkor a megoldandó feladat:

Ennek az optimális megoldása:

Most a következő fagráfnál tartunk:

Most a 3. részfeladatban egész megoldást kaptunk, de ennél még a 2. és 4. részfeladat esetén is kaphatunk jobb megoldást. Ezek közül a 4. részfeladatot választjuk, mert a célfüggvénykorlát itt a nagyobb. Ebben a részfeladatban az változó értéke tört, ezért az elágaztatásában ill. . A 5. és a 6. részfeladat megoldása:

5. részfeladat:

Ekkor a feladat:

Az optimális megoldás:

6. részfeladat: Legyen .

Ekkor a megoldandó feladat:

Ennek a folytonos feladatnak nincs lehetséges megoldása, így az eredeti (integer) feladatnak sincs. Így ezt az ágat lezárjuk.

A fagráf most a következő:

A 6. részfeladatnak nincs megoldása, és az 5-ben pedig tört van. Ez a részfeladat ígéri a legjobb megoldást, így ezt folytatjuk. Az elágaztatásában ill. . A 7. és a 8. részfeladat megoldása:

7. részfeladat: .

Ez egy egész megoldása a feladatnak, ahol .

8. részfeladat:

Ekkor a feladatnak nincs lehetséges megoldása, mivel

Most az 1. részfeladat ígéri a legjobb megoldást, így azt folytatjuk. Itt az ill. . A 9. és a 10. részfeladat megoldása:

9. részfeladat: Legyen .

Ekkor a megoldandó feladat:

Ennek a folytonos feladatnak a megoldása: . Ennél már kaptunk jobb megoldást, így ezt az ágat is lezárjuk.

10. részfeladat: Legyen .

Ekkor a megoldandó feladat:

Ennek a folytonos feladatnak a megoldása: .

A fagráf most a következő:

Ez a 10-es ág ígéri a legjobb megoldást, Itt az alapán kell elágaztatni.

11. részfeladat: Legyen . Innen és . Ezt az ágat is lezárhatjuk, mert van már jobb megoldásunk.

12. részfeladat: Legyen . Innen és .

Ezt a 12-es ágat még ketté bontjuk az alapján.

13. részfeladat: A megoldás . Innen . Ez szintén egész megoldás, de nem optimális.

14. részfeladat: Ekkor , ami nem tesz eleget a feltételnek.

Tehát a kapott optimális megoldást a 3. részfeladat egész megoldása szolgáltatja, amely alapján: . Innen az eredeti feladatunk megoldása: , azaz az első a harmadik és a negyedik beruházást kell megvalósítanunk, és akkor az elérhető maximális hozamunk 24 millió Ft.

Az utolsó fagráf, amely a megoldás teljes menetét mutatja a következő:

A fentiekben tehát bemutattuk a hátizsák feladat Szétválasztás és korlátozás módszerével történő megoldását. Az algoritmus lépései az alábbi pontokban foglalható össze:

  1. Megoldjuk a feladathoz rendelt folytonos lineáris programozási feladatot. Ha a megoldás egész, akkor készen vagyunk. Egyéb esetben két új részfeladatot fogalmazunk meg az egyetlen tört értékű változó ill. értéken való rögzítésével.

  2. Egy részfeladatot a következő négy esetben nem tekintünk aktívnak:

    • Ha a részfeladaton már végeztünk elágaztatást, azaz, ha nem a fagráf végső pontján van,

    • Ha a részfeladat megoldása integer (ekkor ezt az ágat lezárhatjuk),

    • Ha a részfeladat nem megoldható (ekkor ezt az ágat lezárhatjuk),

    • Ha a részfeladat célfüggvényértéke (eredeti feladat célfüggvényének felső korlátja) kisebb mint az egész megoldásokhoz tartozó legnagyobb célfüggvényérték (ekkor ezt az ágat is lezárhatjuk).

  3. Kiválasztunk egy aktív részfeladatot és elágaztatunk a törtértékű változó szerint. Azt az aktív részfeladatot választjuk ki, amelynek célfüggvénye a legnagyobb. Az eljárást addig folytatjuk amíg van aktív részfeladat.

A Szétválasztás és korlátozás módszere egy módszercsalád, a megoldandó feladat jellege szabja meg, hogy milyen elven választjuk meg a szétválasztás szabályát ill. hogyan határozzuk meg a célfüggvény korlátját. Például ha egy részfeladatban egy integer változó értéke , akkor az ill. feltételekkel bontjuk ketté a feladatot. Ezt az elvet követi a következőkben bemutatandó DAKIN algoritmus.

Dakin algoritmus

A DAKIN algoritmus tiszta vagy vegyes integer lineáris programozási feladatot old meg szétválasztás és korlátozás módszerével. Az algoritmus első lépéseként az integer feladathoz rendelt folytonos feladatot oldjuk meg. Ha ez teljesíti az egészértékűségi megkötéseket, akkor készen vagyunk. Egyébként a folytonos megoldásból kiválasztjuk azt a törtértékű változót, amelyre egészértékűségi megkötés vonatkozik, legyen ez az változó. Az mennyiség egész értékének() megfelelően két részfeladatra bontjuk a problémát, egyiket az , a másikat az előírásoknak az eredeti feltételekhez való hozzáadásával kapjuk. Ez a felbontás természetes, hiszen egész megoldást nem kapunk a lefelé és a felfelé kerekített egész értékek közötti tartományban.

Az új feladatokat vagy az induló táblából kiindulva oldjuk meg vagy az optimális szimplex táblázatba beépítjük az új feltételt. Az alábbiakban röviden megmutatjuk, hogyan építhetjük be az optimális szimplex táblába az új feltételt. Legyen az új feltétel a következő:

ahol és vektorok, valós szám. Tekintsük az optimális szimplex táblát:

A feltétel együtthatóvektorát () partícionáljuk bázis () és nembázis részre (). Az optimális szimplex táblába az új feltételt az alábbi szimplex táblán látható módon építhetjük be. Ha a tábla szegélyeire felírjuk az új feltétel adatait, akkor a számolást könnyebbé tehetjük. A feltétel hiányváltozója legyen , ami bázisváltozóként szerepel a módosított szimplex táblában.

Mivel ez a szimplex tábla duál megengedett, így a duál módszerrel folytathatjuk a megoldást.

Az típusú feltételek beépítését -el való beszorzással vezethetjük vissza a bemutatott esetre.

6.2. Példa. Tekintsük az alábbi tiszta integer lineáris programozási feladatot és oldjuk meg Dakin algoritmussal.

Vezessük be az hiányváltozókat, mivel a feltételek együtthatói és a jobboldal egészek, így a hiányváltozókra is érvényesíthetjük az egészértékűséget, azaz a standard alakú LP is tiszta integer feladat lesz, amely a következőképpen írható:

Először megoldjuk a folytonos feladatot, a megoldást szimplex módszerrel végezzük, a kezdő és az optimális szimplex tábla a következő:

A folytonos feladat optimális megoldása (0. részfeladat):

A célfüggvény korlátot, azaz a lefelé kerekített célfüggvényértéket aláhúzással jelöltük. Az változó értéke tört, így e változó szerint határozzuk meg a két részfeladatot.

1. részfeladat:

Az új feladat egyetlen új feltételt tartalmaz, amelyet a fentiekben részletezett módon építünk be az optimális szimplex táblába, ezt mutatja a következő szimplex tábla. A feltétel hiányváltozója legyen , amelyre szintén érvényes az egészértékűség.

Az új szimplex tábla duál megengedett, a duál módszer szerint a pivotelem kiválasztása a következők szerint történik: a megoldásoszlopban megkeressük melyik sorban van negatív szám, ezt választjuk pivotsornak. Példánkban ez az bázisváltozó sora. Ebben a pivotsorban negatív pivotelemet választunk a hányadoskritérium alapján, a vizsgálósorbeli értékek és a pivotsorbeli negatív értékek hányadosát vesszük és ahol ez a hányados a legkisebb ott választunk pivotelemet. Példánkban a és a a hányadosok, ezek közül pedig az első a legkisebb, így a pivotelem lesz.

Az 1. részfeladat optimális megoldása:

2. részfeladat:

A feltétel típusú, így a . Az új szimplex tábla:

Az sorában nincs negatív szám, ez pedig azt jelenti, hogy a 2. részfeladatnak nincs lehetséges megoldása, így az integer feladatnak sincs, tehát ez az ág lezárható.

Mivel csak az 1. részfeladat aktív, ezért az elágaztatást ennél a részfeladatnál kell végrehajtani, mégpedig az törtmegoldást figyelembe véve. A két feladat új feltétele: ill. .

3. részfeladat:

Az új szimplex táblát az 1. részfeladat optimális szimplex táblájából nyerhetjük. Az új szimplex tábla a következő:

A duál módszer végrehajtása után az alábbi optimális szimplex tábla adódik:

A 3. részfeladat optimális megoldása (egész megoldás adódott):

4. részfeladat:

Az új szimplex tábla, amely az 1. részfeladat optimális szimplex táblájából építhető fel:

A duál módszer végrehajtása után az alábbi optimális szimplex tábla adódik:

A 4. részfeladat optimális megoldása:

Mivel egyetlen aktív (4. számú) részfeladatunk van és annál a célfüggvénykorlát nagyobb mint az integer megoldáshoz tartozó célfüggvény maximum, ezért ezt az aktív részfeladatot kell tovább bontani, mégpedig az törtváltozónak megfelelően az és az részfeladatokra.

5. részfeladat:

Az új szimplex táblát a 4. részfeladat optimális szimplex táblájának módosításával állítjuk elő:

A duál módszer végrehajtása után az alábbi optimális szimplex tábla adódik:

Az 5. részfeladat optimális megoldása:

6. részfeladat:

Az új szimplex tábla, amely szintén a 4. részfeladat optimális szimplex táblájából építhető fel:

Az változó sorában nem választható negatív pivotelem, ezért a 6. részfeladatnak nincs lehetséges megoldása, így az integer feladatnak sincs, ezért ez az ág lezárható.

Most tekinsük az eddigi munkánk során kapott fagráfot.

Mivel egyetlen aktív részfeladatunk van (5. sorszámú) és ennél a célfüggvénykorlát (365) kisebb mint az integer megoldáshoz tatozó célfüggvény maximum (370), ezért ezt az aktív részfeladatot nem érdemes tovább bontani, tehát az algoritmus befejeződött.

Az eredeti feladat optimális megoldása:

6.2.3. Vágási módszerek

A vágási módszer alapgondolata

A korábbiakban megismerkedtünk az egész értékű lineáris programozási feladatokkal, jelentőségükkel. Most Gomorynak egy 1959-ből származó eljárását vázoljuk, amely egy geometriai megfontoláson alapszik. Az elgondolás legnagyobb előnye és hátránya is egyben a nagyfokú általánossága, amely miatt főként elméleti jelentőségű. Bár az eredeti algoritmust elvétve használják, az alapgondolata sok lényeges eredmény kiindulópontjában szerepel.

Ez a gondolat a következő. Ha adott egy ILP egészértékű probléma, akkor ehhez hozzárendeljük az egészértékűség megkötése nélkül nyert folytonos lineáris programozási feladatot, legyen ez a megoldás . A folytonos lineáris programozási feladat feltételi halmaza egy konvex poliéder. Az integer lineáris programozási feladat feltételi halmaza pedig a konvex poliéder diszkrét pontjai, amelyeket rácspontoknak nevezünk. Az optimális megoldás a konvex poliéder egy extremális pontja (csúcspont) lesz. Ha ez az optimális csúcspont egyben rácspont is, akkor ez az optimális megoldás egyben az integer lineáris programozási feladat optimális megoldása is. Ha nem, akkor hagyjuk el ot a lehetséges megoldások közül, és próbálkozzunk újra. Természetesen nem akárhogy kell megszabadulnunk -tól, hiszen a célunk, hogy a létrejövő új feladat(ok) is LP feladat(ok) legyen(ek). Ez úgy érhető el, ha -ot egy hipersíkkal vágjuk le a lehetséges megoldások poliéderéről, ami azt jelenti, hogy egy plusz feltételt adtunk az eddigi egyenlőtlenségeinkhez. A következő lépésben újra megoldjuk a módosított folytonos feladatot és ezt ismételjük mindaddig, amíg a folytonos feladat optimális megoldása rácspont nem lesz.

Az elmondottakat szemlélteti az alábbi példa szemlélteti:

6.3. Példa.

A problémánk a síkban ábrázolható. A lehetséges megoldásai nem mások, mint a lineáris programozási feladat poliéderének és a sík egész koordinátájú pontjainak metszete. Az ábrákon nyíllal jelöljük az optimum helyét.

A folytonos feladat megoldása , nem egész. Vegyük fel az feltételt, illetve metsszük le ezzel a politópunkat.

Nagyon fontos, hogy a vágással nem vesztünk az eredeti ILP lehetséges megoldásaiból, azaz az egész koordinátájú pontokból. Az új folytonos LP optimuma , ami továbbra sem egész. Legyen az újabb feltételünk az .

A megoldás , ami egész koordinátájú. Az eredeti feladatnak lehetséges megoldása, így optimuma is egyben. Az optimum értéke 9.

A kezelhetőség kedvéért szükségünk van néhány megszorításra a megoldandó feladatban. A szokásos módon a feladat

valamint feltesszük, hogy minden komponense egész, és az -vel definiált poliéder korlátos.

A vágások precíz definíciójához az egész rész, illetve a törtrész fogalmát használjuk: egy valós szám egész része a legnagyobb -nél nem nagyobb egész, míg az törtrész az egyenlőséggel definiált. A törtrészt az egyszerűség kedvéért betűvel fogjuk jelölni. Tehát a tört rész mindig 1-nél kisebb nemnegatív szám. Például esetén és esetén

Gomory vágás

Tekintsük a tiszta integer lineáris programozási feladat standard alakját:

Megoldjuk a fenti feladatnak megfelelő folytonos feladatot szimplex módszerrel. Ha e folytonos feladat optimális megoldásában minden döntési változó egész, akkor az optimum egyben integer optimum is. Ha nem, akkor tekintsük az optimális szimplex táblának azt a sorát, amelyben a megoldás tört érték, legyen ez az indexhez tartozó sor. A szimplex táblának ezt a sorát forrás sornak nevezzük, mert a vágási feltételt ebből a sorból felírható egyenlet segítségével alkotjuk meg.

Az optimális szimplex tábla legyen a következő, amelyben a forrás sort fel is tüntettük, a táblában az értéknek törtek kell lennie.

Az eredeti feladat -edik egyenletének a pivotálások utáni transzformált változata, a forrás sorból olvasható ki, az egyenlet a következő alakban írható:

ahol a nembázis változók indexhalmazát jelenti, az és az az egyenletben szereplő változók. Az egyenletben szereplő együtthatókat () és a jobboldalt () írjuk fel egy egész szám és egy valódi tört összegeként.

Ennek megfelelően a fenti egyenlet az alábbiak szerint írható:

ahol a táblabeli értékek egész része, az a táblabeli értékek tört része, hasonlóan az az táblabeli érték egész része, az az táblabeli érték tört része. A fentiek miatt igaz, hogy és

Rendezzük át ezt az egyenletet úgy, hogy a baloldalon a felbontásból kapott egész adatok, a jobboldalon pedig a tört adatok legyenek:

Ha az egyenletben szereplő összes változóról feltesszük az egészértékű megkötést, akkor az egyenlet jobboldalának értéke egész szám. Mivel az egyenlőségnek teljesedni kell, ezért az egyenlet jobboldalának is egésznek kell lennie. Vizsgáljuk meg közelebbről a jobboldalt, amely a következő:

A szummás tag mindegyik tagja nemnegatív (mivel a tényezők is nemnegatívok), így maga a szumma is az, ebből pedig következik, hogy a fenti jobboldal kisebb vagy egyenlő -nél, tehát írható, hogy

Tehát a jobboldal, azaz az Ugyanakkor egyenlőnek kell lennie aa baloldallal, amiről tudjuk, hogy egész szám. Ezek alapján csak a egészek jöhetnek szóba.Annak tehát, hogy a feladat megoldása egész legyen, szükséges feltétele az alábbi

Ezt a feltételt hívjuk Gomory vágásnak. Egy nemnegatív hiányváltozó bevezetésével a következőképpen is írhatjuk a vágást:

Könnyen észrevehető, hogy a forrássorból levezetett egyenlet jobboldala, amely az egészértékűséget előírva csak értékeket vehet fel, tehát ebből következik, hogy a bevezetett nemnegatív hiányváltozóra is ugyanazok az előírások érvényesek, mint az döntési változókra, azaz és egész, így a vágással kiegészült feladat is tiszta integer feladat marad. Mivel az optimális megoldásban minden nembázis változó zérus, így a vágási feltételből az következik, hogy , ami ellentmondás, tehát az optimális megoldás (optimális csúcspont) nem lehet lehetséges megoldása a vágási feltétellel kiegészített folytonos feladatnak, azaz a vágás levágja az optimális csúcspontot.

A későbbiekben még fogunk látni más vágásokat is, azért, hogy ezeket egységes szerkezetben lássuk, célszerű átírni a vágást az alábbi alakra:

ahol

A vágás tehát olyan új egyenlőtlenséges feltétel, amelyben csak nembázis változók szerepelnek.

6.1. Megjegyzés.

A Gomory algoritmus fenti változata nem feltétlenül ér véget. Megmutatható, hogy például mind a szimplex, mind a duál szimplex algoritmusnak a lexikografikus változatát alkalmazzuk, akkor a termináció garantálható.

A Gomory algoritmus véges változatai által igényelt iterációk száma sem korlátozható a feladat méretével. Ezt Jeroszlov és Kortanek látta be 1969-ben, majd 1970-ben Rubin olyan, csupán két változót és egyetlen egyenlőtlenséget tartalmazó feladatokat konstruált, melyeknél bármely -re választható olyan, amely több, mint iterációt igényel.

További kellemetlenséget okoz, hogy a megoldandó feladat mérete minden iteráció után növekszik. Az új vágások a régiek egy részét szükségtelenné tehetik, így azok elhagyhatók, de nem egyszerű ezek nyomon követése sem.

Végül felmerül a numerikus stabilitás kérdése is, mert a kerekítések során esetleg felnövekedhetnek a hibák. Jelen esetben ez különösen komplikált, hiszen azt kell eldöntenünk, hogy egy adott érték egésze vagy sem. Ezt elkerülendő Gomory 1960-ban kidolgozott egy olyan változatot, amelyben a generáló elem lehet csak, így az együtthatók végig egészek az eljárás folyamán.

6.4. Példa. Oldjuk meg az alábbi programozási feladatot Gomory vágási módszerrel!

Ebből az alábbi standard alakú integer lineáris programozási feladatot kapjuk:

A folytonos feladatot megoldjuk szimplex módszerrel:

Ez optimális tábla, a megoldása: , és . Mivel az optimális megoldás nem egész, ezért vágni kell. Válasszuk ki forrássornak az bázisváltozó sorát, amelyből az alábbi vágási feltétel írható fel:

(amely tulajdonképpen az és helyettesítéssel az feltételt jelenti). Az hiányváltozó bevezetésével kapjuk, hogy:

Ezt a vágást, mint új feltételt beépítjük az optimális szimplex táblába.

A duál módszer végrehajtásával az alábbi optimális szimplex tábla adódik:

Mivel az optimális megoldás (, ) nem egész, ezért újabb vágást kell alkalmazni, legyen a forrás sor az változó sora, ekkor a második vágási feltétel (az változó bevezetésével)

Ezt az alábbi módon építhetjük be az előző optimális szimplex táblába:

Innen ismét duál-módszert használva adódik, hogy:

A második vágás után a folytonos optimum egészre adódott, így befejezzük az eljárást. Az eredeti feladat optimális megoldása:

Végezetül néhány megjegyzést teszünk a Gomory vágással kapcsolatban. Láttuk, hogy a forrás sor meghatározása nem egyértelmű, így más-más vágásokkal juthatunk az optimális megoldáshoz. Kívánatos lenne olyan vágásokat eszközölni, amely a legmélyebben belevág a folytonos halmazba. Ahhoz, hogy megállapíthassuk melyik a legmélyebb vágás, definiálnunk kell azt, hogy két vágás közül melyik a mélyebb. Tekintsünk egy optimális szimplex táblában két forrás sort, legyenek ezek az -edik és az -edik sor, ezekben felírt vágások:

és

Az -edik vágás akkor mélyebb az -edik vágásnál, ha és minden esetén fennáll, de legalább egy esetben a szigorú egyenlőtlenség áll fenn.

A mélység ezen definíciója sok esetben nem tud dönteni két vágás közül, ezért inkább az alábbi két tapasztalati módszer szerint döntenek a forrás sorról. Az egyik szerint azt a sort választják, ahol a megoldás törtrésze a legnagyobb, azaz

vagy pedig az alábbi szerint döntenek

ahol és a bázisváltozók indexét jelenti.

A második módszer a hatékonyabb, mivel sokkal közelebb van az eredeti mélységi definícióhoz.

Teljesen egész primál vágás

Tekintsük a normál tiszta integer lineáris programozási feladatot. Tegyük fel, hogy a feladat összes együtthatója és a jobboldala egész szám. A normál feladat azt jelenti, hogy maximum feladatról van szó, minden feltétel típusú és minden jobboldal nemnegatív. Az induló szimplex tábla tehát primál megengedett és minden adata egész szám.

Az induló szimplex táblában a szimplex módszer alapján kiválasztjuk a pivotelemet. Ha a pivotelem értéke 1, akkor a pivotálás elvégzése utáni szimplex tábla minden eleme egész marad. Amennyiben a pivotelem egynél nagyobb egész, akkor nem végezzük el a pivotálást, hanem meghatározunk egy vágást, amelyet beépítünk a szimplex táblába és utána végezzük el a pivotálást.

A vágást az alábbiak szerint határozzuk meg. Tekintsük forrás sornak a pivotsort, legyen ez az változóhoz tartozó sor, amelyből a szokásos módon írható fel a megfelelő egyenlet:

Osszuk el az egyenletet a pivotelem jelölttel és írjuk fel az osztás után kapott egyenletet az egész és a törtrészekre bontással:

Rendezzük a fenti egyenletet az alábbi formára:

Mivel az egyenletben szereplő összes változó nemnegatív, így a jobboldal kisebb vagy egyenlő -nél, tehát írható, hogy

Ha megköveteljük a változók egészértékűségét, akkor az egyenlőtlenség baloldalának egésznek kell lennie, de az egyenlőtlenség miatt csak nempozitív ( )lehet a baloldal, így az egészértékűség szükséges feltétele a következő egyenlőtlenség

Ezt az egyenlőlenséget nevezzük All integer vagy teljesen egész primál vágásnak. Az nemnegatív hiányváltozó bevezetésével a vágás

Könnyen ellenőrizhető, hogy is csak egész lehet, így a feladat tiszta integer feladat marad. A vágás beépítése után kapott szimplex táblában újra pivotelemet választunk, de az eredeti pivotoszlopban. Könnyen ellenőrizhető, hogy az új pivotelem sora az újonnan beépített sor lesz, a pivotelem értéke pedig lesz.

E módszernél tehát nem a folytonos feladat optimális megoldása ismeretében kezdjük el a vágásokat, hanem minden pivotáláskor, ha a pivotelem értéke nem .

6.5. Példa. Oldjuk meg az alábbi programozási feladatot All integer vágási módszerrel!

A hiányváltozókkal felírt tiszta integer feladat:

A folytonos feladatot megoldjuk szimplex módszerrel akarjuk megoldani.

Az első oszlopban akarunk pivotelemet választani, ami az 1-es lesz. Így ebben a lépésben nem kell alkalmazni a vágást. A következő tábla adódik

Most a második oszlopból kell pivotelemet választani, méghozzá a 3-ast. Tehát most vágni kell. A pivotsor az változó sora, tehát ez lesz a forrássor. A vágás

azaz

Mivel a vágás itt is csak nembázis változókat tartalmaz, ezért egyszerűen beépíthető a szimplex táblázatba az új feltétel. Az új szimplex tábla

A pivotálás végrehajtása után az alábbi szimplex tábla adódik:

A tábla optimális, így az eljárás befejeződött. Az eredeti feladat optimális megoldása:

Vegyes vágás

Az előző két alfejezetben tiszta integer lineáris programozási feladatokra vonatkozó vágásokat ismertettünk. Ebben az alfejezetben vegyes integer lineáris programozási feladatokra vonatkozó vágást, az ún vegyes vágást mutatjuk be.

Hasonlóan a Gomory vágásnál elmondottakhoz itt is meghatározzuk a folytonos feladat optimális megoldását és az optimális szimplex táblát. Legyen az bázisváltozó olyan, amelyre elő van írva az egészértékűség, de az optimális megoldás tört. Az bázisváltozó sora a forrássor, amelyből a már jól ismert egyenlet olvasható ki:

Az megoldásnak egész és tört részre való bontása és rendezés után kapjuk, hogy

Két esetet különböztetünk meg, egyik amikor az változó értékére az , a másik pedig amikor összefüggés áll fenn.

Az első esetben: , ekkor az egyenletből az alábbi egyenlőtlenség következik:

A második esetben: , ekkor pedig az egyenletből az alábbi egyenlőtlenség következik:

Mivel előre nem tudjuk, hogy a két eset közül melyik következik be, ezért a két feltételt megpróbáljuk egyetlen feltételbe egyesíteni, amelyből majd meghatározzuk a vágást. Ehhez definiáljunk két indexhalmazt, a nembázis változók indexeinek két diszjunkt halmazát, amelyek legyenek a következők:

Ekkor az első esetbeli egyenlőtlenségünk alakja:

Az egyenlőlenségben szereplő második tag az ismeretlenek nemnegativitása miatt pozitív vagy zérus, így ha ezt a tagot elhagyjuk, akkor is fennáll az egyenlőtlenség, azaz írható, hogy

Hasonlóan kezelve a második esetbeli egyenlőtlenséget, kapjuk, hogy

célszerűségi okokból szorozzuk be az mennyiséggel, ekkor

Mivel a és a egyenlőtlenségek egyszerre nem teljesedhetnek, azaz kölcsönösen kizárják egymást, a kettőt egyetlen egyenlőtlenségbe lehet összevonni az alábbiak szerint

Ezt az egyenlőtlenséget nevezzük vegyes vágásnak. A vegyes vágás a már korábban bevezetett egységesített vágási képlettel az alábbiak szerint fogalmazható meg:

ahol

6.6. Példa. Oldjuk meg az alábbi vegyes integer lineáris programozási feladatot vegyes vágás módszerrel!

A standard feladathoz bevezetett hiányváltozók lehetnek törtek is. A folytonos feladat induló és optimális szimplex táblája a következő

Csak az változó sora választható forrás sornak, mivel csak az változóra kötöttük ki az egész értékűséget és a megoldásban értéke tört. A vegyes vágás

Ne feledkezzünk meg, hogy itt a bevezetett nemnegatív hiányváltozóra már nem írható elő az egészértékűség. A vegyes vágás beépítése után kapott szimplex tábla

A duál módszer végrehajtása után az alábbi optimális szimplex tábla adódik:

Az optimális táblából látható, hogy az változóra előírt egészértékűségi feltétel teljesül, így az algoritmus befejeződött. Az eredeti feladat optimális megoldása:

Mélyebb vegyes vágás

A vegyes vágás esetén mélyebben belevághatunk a folytonos feltételi halmazba, ha az optimális szimplex tábla egyes nembázis változóira elő van írva az egészértékűség. A mélyebb vegyes vágás levezetése az alábbiak szerint történik. Tekintsük az optimális szimplex tábla forrás sorát és abból a már jól ismert egyenletet:

A mélyebb vegyes vágás levezetése sok hasonlóságot mutat a vegyes vágásnál látottakhoz. Most is definiáljuk a nembázis változók két indexhalmazát, de másféle módon.

Legyen azon nembázis változók indexeinek halmaza, amely nembázis változókra az egészértékűség ki van kötve, képletben

Legyen azon nembázis változók indexeinek halmaza, amely nembázis változókra az egészértékűség nincs kikötve, képletben

tehát .

Most vezessük be az bázisbeli egész megkötésű változó helyett a szintén egész megkötésű változót a következő módon

ahol rögzített egész számok. Tehát az változóhoz adjuk hozzá azon nembázis változók lineáris kombinációját, amelyekre az egészértékűség meg van kötve. A egész számok értékének megadására később térünk vissza. Mivel egészek, az változónak is egésznek kell lennie. Figyelembe véve a fentieket, a forrássorbeli egyenletet átrendezhetjük az alábbi módon

A vegyes vágáshoz hasonlóan szintén két esetet különböztetünk meg.

Első eset: , ekkor az egyenletből az alábbi egyenlőtlenség következik

Második eset: , ekkor pedig az egyenletből az alábbi egyenlőtlenség következik

Vezessük be az alábbi módon a következő indexhalmazokat:

Hasonlóan a vegyes vágásnál ismertetettekhez, elhagyható az egyenlőtlenségekből egy-egy tag, így esetenként az alábbi egyenlőtlenségek adódnak.

Az első esetben:

A második esetben:

amely az mennyiséggel megszorozva az alábbi alakot ölti

Mivel a két esetbeli egyenlőtlenségek egyszerre nem teljesedhetnek, azaz kölcsönösen kizárják egymást, a kettőt egyetlen egyenlőtlenségbe lehet összevonni az alábbiak szerint

Eddig a adott értékekről csupán annyit követeltünk meg, hogy egészek. Válasszuk a egész értékeket olyanra, hogy az változók együtthatói abszolút értékben minél kisebbek legyenek.

A , azaz a eset vizsgálata: Az változó együtthatója akkor a legkisebb, ha , ebben az esetben az együtthatója , függetlenül attól, hogy a táblázatbeli értékeknek milyen előjele van.

A , azaz a eset vizsgálata: Az változó együtthatója abszolút értékben akkor a legkisebb, ha , ebben az esetben az együtthatójának tényezője , függetlenül attól, hogy a táblázatbeli értékeknek milyen előjele van.

A fentiekből kiolvasható, hogy az egész megkötésű nembázis változó együtthatójának abszolút értéke az indexhalmazoktól függően:

Válasszuk az változó együtthatójának abszolút értékét a két érték közül a kisebbre. Könnyen ellenőrizhető, hogy ha , akkor a a kisebb érték, ha , akkor pedig a kisebb érték.

Összefoglalva tehát, a mélyebb vegyes vágás az alábbiak szerint írható fel:

ahol

6.7. Példa. Tekintsük egy vegyes integer feladat optimális szimplex táblájából egy részletet. Legyen az változókra megkötve az egészértékűség.

a) Határozzuk meg a vegyes vágást!

b) Határozzuk meg a mélyebb vegyes vágást!

A forrás sor adatainak a vágások meghatározásához szükséges törtrészei a következők:

a) A vegyes vágás:

azaz

b) A mélyebb vegyes vágás:

amelyből

7. fejezet - Gráfelméleti algoritmusok

7.1. A szélességi keresés

  1. éleit vizsgálja és rátalál minden -ből elérhető csúcsra.

  2. Kiszámítja az elérhető csúcsok legrövidebb (legkevesebb élből álló) távolságát -től.

  3. Létrehoz egy gyökerű ,,szélességi fát”, amelyben az -ből elérhető csúcsok vannak.

  4. A csúcsoknak szint tulajdonít (fehér, szürke, fekete). Kezdetben minden csúcs fehér, kivéve -et, amely szürke. Szürke lesz egy csúcs, ha elértük és fekete, ha megvizsgáltuk az összes belőle kiinduló élt.

  5. A szélességi fa kezdetben az csúcsból áll. Ez a gyökér.

  6. Ha egy fehér csúcshoz értünk az csúcsból, akkor azt felvesszük a fába éllel és lesz a szülője.

Attributumok

: az csúcs színe

: az csúcs elődje

táv : az távolsága -től

: a szürke csúcsok sora

7.1. Definíció. jelölje a legrövidebb úthosszat -ből -be, ha létezik út -ből -be, egyébként (s,v) legyen .

7.2. Lemma. Legyen digráf vagy gráf és tetszőleges csúcs. Ekkor bármely él esetén .

7.3. Lemma. Legyen gráf és tegyük fel, hogy a szélességi keresés algoritmust alkalmaztuk egy kezdőcsúccsal. Ekkor a szélességi keresés által kiszámított táv értékek minden csúcsra kielégítik a táv[v] egyenlőtlenséget.

7.4. Lemma. Tegyük fel, hogy a szélességi keresést alkalmaztuk a gráfra és a futás során a sor a csúcsokat tartalmazza. ( az első, az utolsó). Ekkor táv táv és táv táv bármely értékre.

7.5. Tétel. Legyen gráf és tegyük fel, hogy a szélességi keresés algoritmust alkalmaztuk egy kezdőcsúccsal. Ekkor a szélességi keresés minden -ből elérhető csúcsot elér és befejezéskor táv , . Továbbá bármely -ből elérhető csúcsra az -ből -be vezető legrövidebb utak egyikét megkapjuk, ha az -ből -be vezető legrövidebb utat kiegészítjük a () éllel.

7.6. Definíció. fát előd részfának nevezzük, ha

és

7.7. Definíció. A előd részfa szélességi fa, ha elemei az -ből elérhető csúcsok és bármely csúcsra egyetlen egyszerű út vezet -ből -be -ben

7.8. Lemma. A szélességi keresés olyan értékeket határoz meg, amelyekre a előd részfa egy szélességi fa.

Eljárás az -ből -be vezető legrövidebb út csúcsai kiírására:

7.2. A mélységi keresés

  1. éleit vizsgálja, mindig az utoljára elért, új kivezető élekkel rendelkező csúcsból kivezető, még nem vizsgált éleket deríti fel. Az összes ilyen él megvizsgálása után visszalép és azon csúcs éleit vizsgálja, amelyből -t elértük.

  2. Az összes csúcsot megvizsgálja.

  3. Létrehoz egy ,,mélységi erdőt”, amely az előd részgráf fáiból áll.

  4. A csúcsoknak szint tulajdonít (fehér, szürke, fekete). Kezdetben minden csúcs fehér, szürke lesz, mikor elértük, és fekete, mikor elhagytuk.

  5. Minden csúcshoz két időpontot rendel, az elérési és az elhagyási időpontot .

7.9. Definíció. A gráfot előd részgráfnak nevezzük, ha

7.10. Tétel. [Zárójelezés tétele]

Mélységi keresést alkalmazva egy (irányított, vagy iráyítatlan) gráfra a következő 3 feltétel közül pontosan 1 teljesül bármely és csúcsra:

a és a intervallumok diszjunktak,

a intervallum tartalmazza a intervallumot, és az csúcs a csúcs leszármazottja a mélységi fában,

a intervallum tartalmazza a intervallumot, és a csúcs az csúcs leszármazottja a mélységi fában.

7.11. Következmény. [Leszármazottak intervallumainak beágyazása]

A csúcs akkor és csak akkor leszármazottja az csúcsnak az irányított, vagy irányítatlan gráf mélységi erdejében, ha .

7.12. Tétel. [Fehér út tétele]

Egy gráfhoz tartozó mélységi erdőben a csúcs akkor és csak akkor leszármazottja az csúcsnak, ha elérésekor a időpontban a csúcs elérhető -ból olyan úton, amely csak fehér csúcsokat tartalmaz.

A mélységi keresés révén a mélységi kereséstől függően a bemeneti gráf éleit osztályozhatjuk. Éltípusok: egy él

  1. Fa él, ha a mélységi erdő éle.

  2. Visszamutató él, ha megelőzője -nak egy mélységi fában.

  3. Előre mutató él, ha leszármazottja -nak egy mélységi fában.

  4. Kereszt él, ha a fenti három osztályba nem sorolható be

Irányított gráf akkor és csak akkor körmentes, ha a mélységi keresés során nem találtunk visszamutató éleket.

7.13. Tétel. Egy irányítatlan gráf mélységi keresésekor bármely él vagy fa él, vagy visszamutató él.

Egy irányított gráf topologikus rendezése a csúcsainak sorba rendezése úgy, hogy ha -ben szerepel az él, akkor előzze meg -t a sorban

7.14. Tétel. A TOPOLOGIKUS_RENDEZÉS() egy írányított, körmentes gráf topologikus rendezését állítja elő.

7.3. Minimális feszítőfa

7.15. Definíció. Egy irányítatlan gráf feszítőfája a gráfnak az a részgráfja, amely fagráf és tartalmazza a gráf összes cúcspontját.

7.16. Definíció. A fa súlya a

számérték.

7.17. Definíció. Minimális feszítőfáról beszélünk, ha értéke minimális az összes feszítőfára nézve. A minimális feszítőfa nem feltétlenül egyértelmű.

7.18. Definíció. Legyen egy minimális feszítőfa egy része. -ra nézve biztonságos egy él, ha -hoz hozzávéve továbbra is valamely minimális feszítőfa része marad.

7.19. Definíció. Egy irányítatlan gráf vágása a kettéosztása egy és egy halmazra.

7.20. Definíció. Az él keresztezi az vágást, ha annak egyik végpontja -ben, másik végpontja -ben található.

7.21. Definíció. Egy vágás kikerüli az halmazt, ha az A egyetlen éle sem keresztezi a vágást.

7.22. Definíció. Egy él könnyű egy vágásban, ha a vágást keresztező élek közül neki van a legkisebb súlya.

7.23. Tétel. Legyen egy összefüggő, irányítatlan gráf súlyfüggvénnyel. Legyen egy olyan részhalmaza -nek, amelyik valamelyik minimális feszítőfájának is része. Legyen tetszőleges -t kikerülő vágása a -nek. Legyen könnyű él az vágásban. Ekkor az él biztonságos az -ra nézve.

7.24. Következmény. Legyen egy összefüggő, irányítatlan gráf gráf súlyfüggvénnyel. Legyen egy olyan részhalmaza -nek, amelyik valamelyik minimális feszítőfájának is része. Legyen egy összefüggő komponens a erdőben. Ha a -t és a valamely másik komponenesét összekötő könnyű él, akkor az él biztonságos az -ra nézve.

7.3.1. Kruskal-algoritmus

7.1. Példa.

7.3.2. Prim-algoritmus

7.2. Példa.

7.4. Legrövidebb utak

A csúcs legrövidebb út távolsága -től legyen , amelyet az -ből -be vezető egyes utak élszámáinak minimumaként definiálunk, ha van ilyen út, és , ha nem vezet út -ből -be.

7.25. Definíció. Egy hosszúságú -ből -be vezető utat és közötti legrövidebb útnak nevezzük.

7.26. Lemma. Legyen irányított vagy irányítatlan gráf és tetszőleges csúcs. Ekkor bármely élre:

Bizonyítás. Ha elérhető -ből, akkor is. Ebben az esetben, az -ből -be vezető legrövidebb út nem lehet hosszabb, mint ha az -ből -ba vezető legrövidebb utat kiegészítjük az éllel, így az egyenlőtlenség teljesül. Ha nem érhető el -ből, akkor , ezért az egyenlőtlenség biztosan igaz.

7.5. Adott csúcsból induló legrövidebb utak

Egy gépkocsivezető a lehető legrövidebb úton szeretne eljutni az egyik városból (A-ból) a másikba (B-be). Hogyan határozhatjuk meg ezt a legrövidebb utat, ha rendelkezünk az ország teljes autós térképével, amelyen minden, két szomszédos útkereszteződés közötti távolságot bejelöltek?

Egyik lehetséges megoldás az, ha módszeresen előállítjuk az összes, A-ból B-be vezető utat azok hosszával együtt, és kiválasztjuk a legrövidebbet. Könnyű azonban azt belátni, hogy még ha kört tartalmazó utakkal nem is foglalkozunk, akkor is több millió olyan lehetőség marad, amelyek többsége egyáltalán nem érdemel figyelmet. Például, egy C-n keresztül vezető A és B közötti út nyilvánvalóan szerencsétlen útvonalválasztás lenne, ha C túl hosszú kitérőt jelent.

A legrövidebb utak problémában adott egy élsúlyozott, irányított gráf, ahol a súlyfüggvény rendel az élekhez valós értékeket. A út súlya az utat alkotó súlyainak összege:

Definiáljuk az -ból -be vezető A legrövidebb út súlyát az alábbi módon:

Az csúcsból csúcsba vezető legrövidebb úton egy olyan utat értünk, amelyre teljesül.

Az A-ból B-be vezető utak példájában az autós térképet egy gráf segítségével modellezhetjük: a csúcsok jelentik a kereszteződéseket, az élek szimbolizálják a kereszteződések közötti útszakaszokat, az élek súlyai pedig az útszakaszok hosszaira utalnak. Célunk olyan legrövidebb útnak a megtalálása, amely A-ból adott indul ki, és B-be érkezik.

Az élsúlyok a távolságokétól eltérő metrikákat is kifejezhetnek. Gyakran használják idő, költség, büntetés, veszteség vagy más olyan mennyiség megjelenítésére, amely egy út mentén lineárisan halmozódik, és amelyet minimalizálni szeretnénk.

Fokozatos közelítés

Ennek a fejezetnek az algoritmusai a fokozatos közelítés módszerét alkalmazzák. Minden csúcsnál nyilvántartunk egy értéket, amely egy felső korlátot ad az kezdőcsúcsból a -be vezető legrövidebb út súlyára. A -t egy legrövidebb-út becslésnek nevezzük.

Kezdetben a legrövidebb-út becsléseket és a szülőkre mutató értékeket a következő futási idejű eljárás állítja be.

A kezdeti értékek beállítása után -re nil, és minden -re áll fenn.

Egy él segítségével történő közelítés technikáját alkalmazzák. Egy ellenőrzésből áll, amelyik összeveti a csúcshoz ez idáig legrövidebbnek talált utat az csúcson keresztül vezető úttal, és ha ez utóbbi rövidebb, akkor módosítja a és értékeket. A közelítő lépés csökkentheti a legrövidebb-út becslés értékét, és átállíthatja a mezőt az csúcsra. Az alábbi kód az él közelítő lépését írja le.

Ennek a fejezetnek mindegyik algoritmusa meghívja az Egy-forrás-kezdőérték eljárást, majd az élekkel egymás után végez közelítéseket. Sőt a közelítés az egyetlen olyan lépés, amely megváltoztatja a legrövidebb-út becsléseket és a szülő értékeket. A fejezet algoritmusai abban különböznek egymástól, hogy hányszor és milyen sorrendben végzik el az élekkel a Közelít műveletet. Dijkstra algoritmusa minden éllel pontosan egyszer közelít. A Bellman-Ford-algoritmus az egyes élekkel többször végez közelítést.

7.5.1. Bellman-Ford algoritmus

A Bellman-Ford-algoritmus az adott kezdőcsúcsból induló legrövidebb utak problémáját abban az általánosabb esetben oldja meg, amikor az élek között negatív súlyúakat is találhatunk. Adott egy súlyfüggvénnyel súlyozott irányított gráf, ahol a kezdőcsúcs . A Bellman-Ford-algoritmus egy logikai értéket ad vissza annak jelölésére, hogy van vagy nincs a kezdőcsúcsból elérhető negatív kör. Ha van ilyen kör, az algoritmus jelzi, hogy nem létezik megoldás. Ha nincs ilyen kör, akkor az algoritmus előállítja a legrövidebb utakat és azok súlyait.

A Bellman-Ford-algoritmus a fokozatos közelítés technikáját alkalmazza, bármelyik csúcsnál az kezdőcsúcsból odavezető legrövidebb út súlyára adott becslését ismételten csökkenti mindaddig, amíg az eléri annak tényleges értékét. Az algoritmus akkor és csak akkor tér vissza igaz értékkel, ha a gráf nem tartalmaz a kezdőcsúcsból elérhető negatív köröket.

A következő ábra a Bellman-Ford-algoritmus működését egy 5 csúcsból álló gráfon mutatja be. A és kezdeti beállítása után az algoritmus menetet végez a gráf éleivel. Minden menet a 2-4. sorok for ciklusának egy iterációja, amely a gráf minden élével egyszer végez közelítést. A (b)-(f) ábrák az algoritmus állapotait mutatják az élekkel végzett négy menet mindegyike után. menet után az 5-8. sorok negatív kört keresnek, és a megfelelő logikai értéket adják vissza.

A Bellman-Ford-algoritmus futási ideje , mivel az 1. sor előkészítése idejű, a 2-4. sorokban az élekkel végzett menet mindegyike ideig tart, és az 5-7. sorok for ciklusa idejű.

A kezdőcsúcs az csúcs. A értékeket beleírtuk a csúcsokba, és a vastagított élek jelzik a szülő értékeket: ha () él vastagított, akkor . (a) Az első menet előtti helyzet. (b)-(f) Az egymást követő menetek után kialakult helyzetek. Az (f) rész a végleges és értékeket mutatja. A Bellman-Ford-algoritmus ebben a példában igaz értékkel tér vissza.

7.27. Tétel. Bellman-Ford-algoritmus helyessége

Egy súlyozott, irányított gráfon futtassuk a Bellman-Ford eljárást, ahol a súlyfüggvény a , és a kezdőcsúcs az s. Ha nem tartalmaz -ből elérhető negatív köröket, akkor az algoritmus igaz értéket ad vissza, tovább minden csúcsra , és a szülő részgráf egy gyökerű legrövidebb-utak fa lesz. Ha -ben van egy -ből elérhető negatív kör, akkor az algoritmus hamis értékkel tér vissza.

7.5.2. Dijkstra algoritmusa

Dijkstra algoritmusa az adott kezdőcsúcsból induló legrövidebb utak problémáját egy élsúlyozott, irányított gráfban abban az esetben oldja meg, ha egyik élnek sem negatív a súlya. Ebben az alfejezetben ennek megfelelően feltesszük, hogy minden élre . A Dijkstra algoritmusának futási ideje, egy jó megvalósítás mellett, gyorsabb, mint a Bellman-Ford-algoritmusé.

A Dijkstra-algoritmus azoknak a csúcsoknak az halmazát tartja nyilván, amelyekhez már meghatározta az kezdőcsúcsból odavazető legrövidebb-út súlyát. Az algotimus minden lépésben a legkisebb legrövidebb-út becslésű csúcsot választja ki, beteszi az -t az -be, és minden -ból kivezető éllel egy-egy közelítést végez. Az alábbi megvalósításban egy minimum-elsőbbségi sort alkalmazunk a -beli csúcsok nyilvántartására, amelyeket azok táv értékeivel indexeltünk. Az algoritmus feltételezi, hogy a gráf egy szomszédsági listával van megadva.

A kezdőcsúcs a bal oldali csúcs. A legrövidebb-út becsléseket a csúcsok belsejében tüntettük fel, és vastagított élek jelzik a szülő csúcsokat: ha vastag, akkor . A sötétebb szürke színű csúcsok az S halmazban vannak, és a fehér színűek a prioritási sorban. (a) Ez a 4-8. sorok while ciklusának első iterációja előtti helyzet. A sötét színű csúcs a legkisebb értékű csúcs, és az 5. sor ezt választja ki csúcsként. (b)-(f) A while ciklus soron következő iterációi utáni helyzetek. Minden részben a sötétebb színnel jelölt csúcsot mint csúcsot választja ki a következő iteráció 5. sora. Az (f) rész a végleges táv és értékeket mutatja.

A Dijkstra-algoritmus az ábrán bemutatott módon végzi az élekkel a fokozatos közelítést. Az 1. sor a táv és a értékeinek szokásos kezdeti beállítását végzi, majd a 2. sor az halmazt teszi üressé. A 4-8. sorok while ciklusának minden iterációja előtt fennáll a invariáns állítás. A 3. sor a minimum-elsőbbségi sort készíti elő úgy, hogy az kezdetben minden -beli csúcsot tartalmazzon; mivel ekkor az még üres, az invariáns állítás a 3. sor után teljesül. A 4-8. sorok while ciklusában egy csúcsot veszünk ki az halmazból (legelőször ), és hozzáadjuk az halmazhoz, tehát az invariáns állítás továbbra is igaz marad. Az csúcs tehát a legkisebb legrövidebb-út becslésű csúcs a -ben. Ezután a 7-8. sorok közelítést végeznek az -ból kivezető élekkel, ezáltal módosítjuk a becslést és a szülőt, feltéve, hogy a -hez az -n keresztül most talált út rövidebb, mint az ott eddig nyilvántartott legrövidebb út. Figyelembe véve azt, hogy a 3. sor után már egyetlen csúcsot sem teszünk bele a -ba, valamint azt, hogy mindegyik csúcsot egyetlenegyszer veszünk ki a -ból és tesszük át az -be, a 4-8. sorok while ciklusa pontosan -szer hajtódik végre.

A Dijkstra-algoritmus mohó stratégiát alkalmaz, hiszen minden a ,,legkönnyebb”, a ,,legközelebbi” csúcsot választja ki a -ből, hogy azután betegye az halmazba. A mohó stratégiák általában nem mindig adnak optimális eredményt, de amint a következő tétel és annak következménye mutatja, a Dijkstra-algoritmus szükségszerűen a legrövidebb utakat állítja elő.

7.28. Tétel. Dijkstra-algoritmus helyessége

Ha Dijkstra algoritmusát egy nemnegatív súlyfüggvénnyel súlyozott, kezdőcsúcsú irányított gráfban futtatjuk, akkor annak a befejeződésekor minden csúcsra teljesül, hogy táv .

7.29. Következmény. Ha Dijkstra algoritmusát egy nemnegatív súlyfüggvénnyel súlyozott, irányított kezdőcsúcsú gráfban futtatjuk, akkor annak befejeződésekor a szülő részgráf egy gyökerű legrövidebb-utak fa lesz.

7.6. Legrövidebb utak minden csúcspárra

Ebben a fejezetben célunk egy gráf valamennyi rendezett csúcspárjára a két csúcs közti legrövidebb út megkeresése. Ha például egy autóstérképhez elkészítjük a városok egymástól mért távolságainak táblázatát, éppen ezt a feladatot oldjuk meg. Csakúgy, mint korábban egy súlyozott irányított gráfot jelöl, amelynek élhalmazán egy valós értékű súlyfüggvény van megadva. A gráf minden csúcspárjára keressük az -ból -be vezető legrövidebb (legkisebb súlyú) utat, ahol egy út súlya az úthoz tartozó élek súlyának az összege. Az eredményt általában táblázatos formában keressük; a táblázat -hoz tartozó sorában és -hez tartozó oszlopában álló elem az -ból -be vezető legrövidebb út hossza.

A csúcspárok közti legrövidebb utakat természetesen megkereshetjük úgy, hogy az előző fejezetben látott valamelyik egy kezdőcsúcsból kiinduló legrövidebb utakat kereső algoritmust egyenként végrehajtunk a lehetséges különböző gyökércsúcsot választva. Ha a távolságok nemnegatívak, Dijkstra algoritmusát alkalmazhatjuk.

Ha negatív élsúlyokat is megengedünk a gráfban, Dijkstra algortmusa nem alkalmazható, helyette a lassabb Bellman-Ford-algoritmust kell minden csúcsra egyszer végrehajtanunk. Célunk tehát, hogy a negatív élsúlyok esetére hatékonyabb algoritmusokat adjunk. Eközben megismerjük az összes csúcspár közti legrövidebb út probléma és a mátrixszorzás kapcsolatát is.

Az egy csúcsból kiinduló legrövidebb utakat megadó algoritmusok általában a gráf éllistás megadását igénylik. A bemenő adat tehát egy -es mátrix lesz. A mátrix egy csúcsú irányított gráf élsúlyait tartalmazza: , ahol

A gráfban megengedünk negatív súlyú éleket, azonban egyelőre feltesszük, hogy negatív összsúlyú körök nincsenek.

A fejezetbeli algoritmus kimenete az összes párra adott legrövidebb úthosszakat tartalmazó táblázat egy D -es mátrix lesz. A mátrix eleme az csúcsból a csúcsba vezető legrövidebb út súlyát tartalmazza. A végeredményként kapott értékek tehát megegyeznek a -vel, az csúcsból a csúcsba vezető legrövidebb út súlyával.

Csak akkor mondhatjuk, hogy a kitűzött feladatot megoldottuk, ha a legrövidebb utak súlya mellett magukat az utakat is meg tudjuk adni. E célból egy megelőzési mátrixot is meg kell adnunk, amelyben , ha vagy ha nem vezet és között út; ellenkező esetben a -t megelőző csúcs az egyik -ből -be vezető legrövidebb úton.

Mielőtt az algoritmust ismertetnénk, állapodjunk meg néhány, szomszédsági mátrixokkal kapcsolatos, jelölésben. Először is a gráfnak általában csúcsa lesz, azaz . Másodszor a mátrixokat nagybetűvel, egyes elemeiket pedig alulindexelt kisbetűvel fogjuk jelölni, tehát például és elemei lesznek. Bizonyos esetekben iterációk jelölésére a mátrixokat zárójelezett felsőindexszel látjuk el, úgy mint . Végül egy adott A -es mátrix esetén sorok-száma[A] tartalmazza értékét.

7.6.1. A Floyd-Warshall-algoritmus

A következőkben dinamikus programozási feladatként értelmezzük a legrövidebb utak keresését. Egy irányított gráfon a keletkező ún. Floyd-Warshall-algoritmus futási ideje . A bemenő gráfban megengedünk negatív élsúlyokat, negatív összsúlyú köröket azonban nem.

A legrövidebb utak szerkezete

Dinamikus programozásunk a legrövidebb utak ,,belső” csúcsait tekinti, ahol egy egyszerű út belső csúcsa minden -től és -től különböző csúcsa, azaz a halmaz minden eleme.

A szerkezet jellemzése a következő észrevételen alapul. Legyen a gráf csúcshalmaza , és tekintsük valamely -ra az részhalmazt. Legyen a legrövidebb -ből -be vezető olyan út, melynek belső csúcsait az részhalmazból választhatjuk. (A út egyszerű, hiszen nem tartalmaz negatív összsúlyú köröket.) A Floyd-Warshall-algoritmus a út és az olyan legrövidebb utak kapcsolatát alkalmazza, melynek belső csúcsait az részhalmazból választjuk. E kapcsolat két esetre osztható attól függően, hogy belső csúcsa-e -nek vagy sem:

  • Ha a útnak nem belső csúcsa, akkor a út minden belső csúcsa az halmaz eleme. Így a legrövidebb -ből -be vezető és belső csúcsként csak az halmaz elemeit használó út szintén legrövidebb út lesz, ha a belső csúcsok az halmazból kerülhetnek ki.

  • Ha belső csúcs a úton, akkor felbontjuk a utat két útra. A egy olyan legrövidebb út és között, melynek belső csúcsai az halmaz elemei. Sőt nem is lehet út belső csúcsa, így egyben olyan legrövidebb út is, melynek belső csúcsai -beliek. Hasonlóképpen egy legrövidebb, belső csúcsként csak -et használó -ból -be vezető út.

Az összes csúcspár közti legrövidebb utak rekurzív megadása

A fenti megfigyelés alapján egy rekurzióval adhatunk egyre javuló becsléseket a legrövidebb utak súlyára. Legyen a legrövidebb olyan -ből -be vezető út hossza, melynek minden belső csúcsa az halmaz eleme. A érték esetén egy olyan -ből -be vezető útnak, melyen a belső csúcsok sorszáma legfeljebb 0 lehet, egyáltalán nem lehet belső csúcsa. Egy ilyen útnak tehát legfeljebb egyetlen éle lehet és így . A további értékeket a következő rekurzió szolgáltatja:

A végeredményt a mátrix tartalmazza, hiszen az egyes legrövidebb utak belső csúcsai a halmaz elemei, és így minden esetén.

Az úthosszak kiszámítása alulról felfelé haladva

A 7.2 rekurzió segítségével a értékeket alulról felfelé, értéke szerinti növekvő sorrendben számíthatjuk. Az algoritmus bemenő adatai a 7.1 egyenlőség által definiált -es mátrix lesz, eredményül pedig a legrövidebb úthosszak mátrixát adja.

A Floyd-Warshall-algoritmus futási idejét a 3-6. sorok háromszorosan egymásba ágyazott FOR ciklusa határozza meg. A 6. sor minden egyes alkalommal időben végrehajtható, így a teljes futási idő . A megadott programkód tömör és csak egyszerű adatszerkezeteket igényel. A -jelölésbeli állandó tehát kicsi, és a Floyd-Warshall-algoritmus még közepesen nagy méretű gráfok esetén is hatékony.

A és mátrixok, ha a Floyd-Warshall-algoritmust az ábrán látható gráfon futtatjuk.

A legrövidebb utak megadása

A Floyd-Warshall-algoritmusban több módszer is kínálkozik arra, hogy a legrövidebb utak éleit is megkapjuk. Megtehető, hogy a legrövidebb úthosszak mátrixának ismeretében idő alatt megkonstruáljuk a { } megelőzési mátrixot. A { } megelőzési mátrix ismeretében pedig a Minden-párhoz-utat-nyomtat eljárás megadja a kívánt két csúcs közti legrövidebb út éleit.

A megelőzési mátrixot számíthajuk a Floyd-Warshall-algoritmus menetében a mátrixokkal egyidejűleg is. Pontosabban mátrixok egy sorozatát számíthatunk, melyre . E sorozatban -t úgy definiáljuk, mint egy olyan legrövidebb -ből -be vezető úton a -t megelőző csúcsot, melynek belső csúcsai a halmaz elemei.

Megadjuk a értékeit definiáló rekurziót. (A mátrixok számítása az ábra példájában követhető.) Ha , akkor -től -ig tartó úton nincs közbülső csúcs és így

A esetben pedig egy úton a -t megelőző csúcsnak választható ugyanaz a csúcs, amely -t egy legrövidebb -ból induló és belső csúcsként csak az halmaz elemeit használó úton előzi meg. Ha pedig a legrövidebb -ből -be vezető és az halmaz elemeit használó út -t nem tartalmazza, akkor a -t megelőző csúcs megegyezik a érték esetén választott megelőző csúccsal. Tehát mellett a rekurzív egyenlet

8. fejezet - Feladatok

  1. Határozzuk meg a másodrendű Taylor-sorfejtést az függvény esetén!

  2. Határozzuk meg kvadratikus közelítését!

  3. extr.

  4. extr.

  5. Határozzuk meg az és oldalú téglalap alakú kartonból készíthető maximális térfogatú, felül nyitott doboz adatait!

  6. extr.

  7. extr.

  8. extr

  9. Határozzuk meg azt a maximális területű téglalapot, amelynek kerülete 100 területegység!

  10. Határozzuk meg azt a maximális térfogatú téglatestet, amelynek felülete 600 területegység!

  11. Határozzuk meg azt a maximális felületű téglatestet, amelynek térfogata 1000 területegység!

  12. Egy téglalap alakú kertet akarunk készíteni egy fal mellett, így csak a kert 3 oldalát kell kerítéssel bekerítenünk. Mekkora a maximális méretű kert, ha 50m kerítés áll rendelkezésünkre?

  13. extr (majomnyereg).

  14. extr

  15. extr (keresztvályú).

  16. extr (Whitney-függvénye).

  17. extr

  18. extr

  19. extr.

  20. extr.

  21. Ábrázoljuk az

    függvényt a négyzeten! Mik a szélsőértékei?

  22. Adott az alábbi mátrix. Definitség szempontjából vizsgálja meg az mátrixot! A vizsgálatot főminor módszer teszttel végezze

  23. Adott az alábbi mátrix. Definitség szempontjából vizsgálja meg az mátrixot! A vizsgálatot a sajátértékek módszerével végezze

  24. Döntse el, hogy az mátrix feltételesen pozitív vagy negatív definit a mátrixra nézve!

  25. Határozzuk meg a maximális térfogatú sugarú és magasságú henger adatait, ha a henger felszíne ! Ellenőrizzük, hogy a kapott eredmény tényleg maximum pont-e?

  26. Határozzuk meg az függvény maximumát a feltétel mellett!

  27. Oldjuk meg az feladatot a feltétel mellett!

  28. Oldjuk meg az feladatot a

    feltételek mellett!

  29. Oldjuk meg az , feladatot!

  30. Oldjuk meg az , feladatot!

  31. A Kuhn-Tucker tétel segítségével igazoljuk, hogy a pont az

    konvex optimalizálási feladat optimális megoldása!

  32. Oldjuk meg az

    konvex optimalizálási feladatot!

  33. Adott az és az egyenes. Ezek az egyenesek a síkot négy részre bontják, tekintsük azt a tartományt, amely tartalmazza az pontot. Határozza meg a tartomány azon pontját, amely a legközelebb van az origóhoz. Ellenőrizze az elégséges feltétel segítségével, hogy a kapott pont valóban optimális!

  34. Minimalizálandó a

    függvény feltéve, hogy . Írja fel a Karush-Kuhn-Tucker feltételeket és határozza meg a KKT pontot! Ellenőrizze, hogy a KKT pont optimális megoldás-e!

  35. Minimalizálandó a

    függvény feltéve, hogy és . Írja fel a Karush-Kuhn-Tucker feltételeket és határozza meg a KKT pontot! Ellenőrizze, hogy a KKT pont optimális megoldás-e!

  36. Minimalizálandó a

    függvény feltéve, hogy és . Írja fel a Karush-Kuhn-Tucker feltételeket és határozza meg a KKT pontot!

  37. Határozzuk meg az , primál feladat duálisát és mutassuk meg, hogy a duális feladatnak nincsen véges optimuma!

  38. Határozzuk meg az függvény minimumhelyét!

  39. Határozzuk meg az függvény minimumhelyét!

  40. Határozzuk meg az függvény minimumhelyét!

  41. Határozzuk meg az függvény maximumhelyét és maximális értékét!

  42. Irjuk át a Broyden-módszert inverz alakba a Sherman-Morrison-Woodbury formula segitségével!

  43. Adjuk meg a BFGS eljárást az inverzet használó alakban!

  44. Hogyan módosul a BFGS eljárás vonalmenti minimalizálás használata esetén?

  45. Vizsgáljuk meg a SUMT módszer konvergenciáját az , feladat esetén!

  46. Oldjuk meg az egyváltozós optimalizálási feladatot Dichotomuus keresés módszerével, ha a bizonytalansági intervallum , , .

  47. Oldjuk meg az egyváltozós optimalizálási feladatot Dichotomuus keresés módszerével, ha a bizonytalansági intervallum , , , .

  48. Oldjuk meg az egyváltozós optimalizálási feladatot aranymetszéses keresés módszerével, ha a bizonytalansági intervallum , .

  49. Adott az bizonytalansági intervallum. Hány lépést kell kiszámolni az aranymetszéses keresés módszere esetén, hogy a minimumpont hibája kisebb legyen, mint ?

  50. Oldjuk meg az egyváltozós optimalizálási feladatot aranymetszéses keresés módszerével, ha a bizonytalansági intervallum , .

  51. Oldjuk meg az egyváltozós optimalizálási feladatot Fibonacci keresés módszerével, ha a bizonytalansági intervallum , és válasszuk az értékét -re.

  52. Oldjuk meg az egyváltozós optimalizálási feladatot Fibonacci keresés módszerével, ha a bizonytalansági intervallum , és válasszuk az értékét -ra.

  53. Adott az bizonytalansági intervallum. Mennyire kell választani értékét a Fibonacci módszernél, hogy a minimumpont hibája kisebb legyen, mint ?

  54. Oldjuk meg az egyváltozós optimalizálási feladatot Newton módszerrel, ha a kiinduló közelítő megoldás , .

  55. Oldjuk meg az alábbi optimalizálási feladatot Hooke-Jeeves módszerrel. Legyen az a startvektor és legyen a pontossági tűrés.

  56. Ellenőrizze le a Fletcher-Reeves módszerre felírt tételben megfogalmazott állítások helyességét.

  57. Határozzuk meg az kétváltozós optimalizálási feladatot gradiens módszerrel az kiindulópontból pontossággal.

  58. Határozzuk meg az kétváltozós optimalizálási feladatot konjugált gradiens módszerrel az kiindulópontból pontossággal.

  59. Az

    függvény minimumát szeretnénk meghatározni konjugált gradiens módszerrel. Tegyük fel, hogy néhány lépést elvégeztünk, az eredmények: , , . Határozza meg az közelítést és a hozzátartozó vektort!

  60. Határozzuk meg az kétváltozós optimalizálási feladatot egyrangú BFGS-módszerrel az kiindulópontból pontossággal, ha nem használjuk az iránymenti optimalizálást. A kiinduló mátrix legyen

  61. Határozzuk meg az kétváltozós optimalizálási feladatot kétrangú BFGS-módszerrel az kiindulópontból pontossággal, ha nem használjuk az iránymenti optimalizálást. A kiinduló mátrix legyen

  62. Határozzuk meg az kétváltozós optimalizálási feladatot egyrangú BFGS-módszerrel az kiindulópontból pontossággal, ha használjuk az iránymenti optimalizálást. A kiinduló mátrix legyen

  63. Határozzuk meg az kétváltozós optimalizálási feladatot kétrangú BFGS-módszerrel az kiindulópontból pontossággal, ha használjuk az iránymenti optimalizálást. A kiinduló mátrix legyen

  64. Határozzuk meg az kétváltozós optimalizálási feladatot egyrangú DFP-módszerrel az kiindulópontból pontossággal a vonalmenti minimalizálás használatával és anélkül is. A kiinduló mátrix legyen

  65. Határozzuk meg az kétváltozós optimalizálási feladatot kétrangú DFP-módszerrel az kiindulópontból pontossággal a vonalmenti minimalizálás használatával. A kiinduló mátrix legyen

  66. Oldjuk meg az alábbi optimalizálási feladatot Davidon-Fletcher-Powell módszerrel.

    A kiinduló mátrix legyen az egységmátrix, az pedig legyen a pont.

  67. Az alábbi függvény minimumát szeretnénk meghatározni.

    a) Adott az startvektor. Határozza meg a következő közelítést gradiens módszerrel!

    b) Adott az startvektor. Határozza meg a következő közelítést Newton I. módszerrel. Határozza meg a közelítést abban az esetben is, ha a Newton I. módszert összekapcsoljuk az iránymenti optimalizálással!

    c) Adottak az alábbi startelemek:

    Határozza meg az vektor és a mátrix következő közelítését, ha a BFGS (kvázi Newton I.) módszer egyrangú verzióját használja és nem alkalmaz iránymenti optimalizálást!

    d) Adottak az alábbi startelemek:

    Határozza meg az vektor és a mátrix következő közelítését, ha a DFP (kvázi Newton II.) módszer kétrangú verzióját használja és alkalmaz iránymenti optimalizálást!

  68. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel

  69. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel

  70. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel

  71. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel

  72. Oldjuk meg az alábbi optimalizálási feladatot büntetőfüggvényes módszerrel:

  73. Oldja meg az alábbi kifizetési mátrixszal adott mátrixjátékot!

  74. Oldja meg az alábbi kifizetési mátrixszal adott mátrixjátékot!

  75. Oldja meg az alábbi kifizetési mátrixszal adott mátrixjátékot!

  76. Oldja meg az alábbi kifizetési mátrixszal adott mátrixjátékot!

  77. Oldjuk meg az alábbi sémával adott mátrixjátékot:

  78. Oldjuk meg az alábbi sémával adott mátrixjátékot:

  79. Adott egy -es zérusösszegű játék a következő mátrixszal:

    Van-e minimax-maximin stratégia? Van-e a játéknak Nash-egyensúlypontja? Határozza meg a játékosok optimális stratégiáit!

  80. Milyen esetén lesz az alábbi mátrixjáték értéke ? Határozza meg azt az értéket, amelynél a játék igazságos!

  81. Két ember játszik. Az egyikük elrejt a kezében egy vagy két darab 100 Ft-os pénzérmét. A másik játékos találgat, hogy hány darabot rejtett-e el. Ha jól tippel, akkor övé a pénz, egyébként az első megtartja magának. Határozza meg a játékosok nyeregponti stratégiáit és a játék értékét!

  82. Tekintsük az alábbi tiszta integer lineáris programozási feladatot és oldjuk meg Dakin algoritmussal.

  83. Tekintsük az alábbi tiszta integer lineáris programozási feladatot és oldjuk meg Gomory vágást alkalmazva.

  84. Tekintsük az alábbi tiszta integer lineáris programozási feladatot és oldjuk meg ,,All integer" vágást alkalmazva.

  85. Adott az lineáris programozási feladat optimális szimplex táblája.

    a) Tegyük fel, hogy minden változóra érvényes az egészértékűségi megkötés. Írja fel a Gomory vágást, ha az bázisváltozó sorát választjuk forrás sornak! Építse be a vágást az optimális szimplex táblába! Jelölje ki a pivot elemet!

    b) Tegyük fel, hogy minden változóra érvényes az egészértékűségi megkötés. Döntse el, hogy melyik vágás a mélyebb, az vagy az bázisváltozó sorát választva forrás sornak!

    c) Tegyük fel, hogy csak az változókra érvényes az egészértékűségi megkötés. Írja fel a vegyes vágást, ha az bázisváltozó sorát választjuk forrás sornak! Építse be a vágást az optimális szimplex táblába! Jelölje ki a pivot elemet!

    d) Tegyük fel, hogy csak az változókra érvényes az egészértékűségi megkötés. Írja fel a mélyebb vegyes vágást, ha az bázisváltozó sorát választjuk forrás sornak! Építse be a vágást az optimális szimplex táblába! Jelölje ki a pivot elemet!

  86. Egy üzemben három terméket gyártanak, melyek megmunkálása két fázisban (marógép és köszörűgépen) történik. Az első termék marógépen történő megmunkálásának műveletigénye 2 perc/db, a köszörűgépen 3 perc/db. A második terméké rendre 1, 1 perc/db, a harmadik terméké pedig rendre 2, 1 perc/db. A marógép kapacitása 110 perc, a köszörűgépé pedig 85 perc. A termékek várható eladási egységára rendre 4, 2, 6 pénzegység/db és a tervezett árbevétel 130 pénzegység. A gépek állásidejének (kihasználatlan kapacitás) költsége rendre 1, 2 pénzegység/perc. Adja meg azt a termelési tervet (hány darabot kell gyártani a termékekből), amelynél a gépek állásidejéből eredő költség minimális, feltéve, hogy a gépek kapacitását nem lépjük túl és ár-bevételben pontosan a tervezett mennyiséget biztosítjuk.

  87. Egy üzemben kétféle terméket gyártanak. A két termék gyártása három gépen történik. Az első termék egy darabjának megmunkálásához szükséges gépidők rendre 3, 3, 2 óra; a második termék egységének gépidőszükséglete pedig rendre 4, 3, 1 óra. A rendelkezésre álló kapacitás gépenként 61, 50, 20 óra. A egyes termékek várható eladási egységára rendre 20, 15 pénzegység. Hány darab terméket gyártsunk, hogy a gépek kapacitását ne lépjük túl és a várható árbevétel maximális legyen? Az egész megoldást Gomory vágás módszerével keresse!

  88. Egy üzemben kétféle szivattyút gyártanak. A két szivattyú gyártása három részlegben történik. Az első fajta szivattyú egy darabjának megmunkálásához szükséges idők a részlegekben rendre 3, 3, 2 óra; a második szivattyú időszükséglete pedig rendre 4, 3, 1 óra. A rendelkezésre álló kapacitás részlegenként 121, 100, 40 óra. A egyes szivattyúk várható eladási egységára rendre 80, 60 pénzegység. Hány darab szivattyút gyártsunk, hogy a részlegek kapacitását ne lépjük túl és a várható árbevétel maximális legyen? Az egész megoldást Dakin módszerével keresse!

  89. Tegyük fel, hogy legfeljebb 30 millió Ft-ot akarunk befektetni. Négy beruházási/befektetési lehetőséget vizsgálunk, amelyekre vonatkozóan az alábbi ismereteink vannak. Az befektetési lehetőségek megvalósítási költsége rendre 10, 15, 8 és 9 millió Ft. Az egyes befektetési lehetőségek hozama rendre 12, 20, 8 és 11 millió Ft. Melyik beruházási lehetőséget tudjuk teljes mértékben megvalósítani a rendelkezésre álló pénzkeretből úgy, hogy a hozam maximális legyen?

  90. Tegyük fel, hogy legfeljebb 30 millió Ft-ot akarunk befektetni. Öt beruházási/befektetési lehetőséget vizsgálunk, amelyekre vonatkozóan az alábbi ismereteink vannak. Az befektetési lehetőségek megvalósítási költsége rendre 7, 10, 15, 8 és 9 millió Ft. Az egyes befektetési lehetőségek hozama rendre 10, 12, 20, 8 és 11 millió Ft. Melyik beruházási lehetőséget tudjuk teljes mértékben megvalósítani a rendelkezésre álló pénzkeretből úgy, hogy a hozam maximális legyen?

  91. Oldja meg az alábbi hátizsák feladatot!

  92. Oldja meg az alábbi hátizsák feladatot!

  93. Oldja meg az alábbi hátizsák feladatot!

  94. Határozza meg a következő gráf minimális feszítőfáját a Prim eljárással!

  95. Határozza meg a következő gráf minimális feszítőfáját a Kruskal eljárással!

  96. Adott egy digráf az 1, 2, 3, 4, 5, 6 csúcspontokkal az alábbi szomszédsági listával. Az 1-es csúcspontból kiindulva végezzünk el egy szélességi keresést! Hány él alkotja az eljárás által létrehozott szélességi fát? Mennyi a megtalált csúcsokba vezető legrövidebb utak összhossza?

  97. Adott egy digráf az 1, 2, 3, 4, 5, 6 csúcspontokkal az alábbi szomszédsági listával. A zárójelbe tett számok az utak hosszát jelölik. Az 1-es csúcspontból kiindulva végezzünk el a minimális út keresését Dijkstra eljárással!

  98. Adott egy digráf az 1, 2, 3, 4, 5, 6 csúcspontokkal az alábbi szomszédsági listával. A zárójelbe tett számok az utak hosszát jelölik. Az 1-es csúcspontból kiindulva végezzünk el a minimális út keresését Dijkstra eljárással!

  99. Adott egy digráf az 1, 2, 3, 4, 5, 6 csúcspontokkal az alábbi szomszédsági listával. A zárójelbe tett számok az utak hosszát jelölik. Az 1-es csúcspontból kiindulva végezzünk el a minimális út keresését Belmann-Ford eljárással!

  100. Adott egy digráf az 1, 2, 3, 4, 5 csúcspontokkal az alábbi szomszédsági listával. . A zárójelbe tett számok az utak hosszát jelölik. Határozzuk meg minden csúcsból minden csúcsba a minimális utat a Floyd-Warshall eljárással!

Irodalomjegyzék

[1] M. S. Bazaraa, C. M. Shetty. Nonlinear programming, theory and algorithms. John Wiley & Sons, New York. 1979.

[2] A. Berman. Cones, matrices and mathematical programming. Springer-Verlag, Berlin. 1973.

[3] J. M. Borwein, A. S. Lewis. Convex analysis and nonlinear optimization, theory and examples. Springer-Verlag, New York. 2000.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest. Algoritusok. Műszaki Könyvkiadó, Budapest. 1999.

[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Új algoritusok. Scolar Kiadó, Budapest. 2003.

[6] Cook, Cunningham, Pulleybank, Schrijver. Combinatorical Optimization. Wiley. 1998.

[7] M. Dormány. Gráfok operációkutatási alkalmazásai. Miskolci Egyetemi kiadó, Miskolc. 1976.

[8] M. Dormány. Operációkutatás. NME, Miskolc-Egyetemváros. 1985.

[9] M. Dormány. Nemlineáris programozás. NME, Miskolc-Egyetemváros. 1978.

[10] J. Fiala. Kombinatorikus Optimalizálás. Budapest. 2010.

[11] A. Frank. Operációkutatás. előadásjegyzet. 2003.

[12] J. B. G. Frenk. Convexity and optimization. (egyetemi jegyzet). Erasmus Universiteit Rotterdam, Rotterdam. 1993.

[13] J. B. G. Frenk, G. Kassay. On classes of generalized convex functions, Gordan-Farkas type theorems, and Lagrange duality. J. of Opt. Theory and Appl.. 102(2). 1999. 315–343.

[14] A. Galántai. Optimalizálási módszerek. Miskolci Egyetemi Kiadó, MIskolc-Egyetemváros. 2007.

[15] T. Király, L. Szegő. Online jegyzet az egészértékű programozáshoz. (egyetemi jegyzet). 2010.

[16] T. Király, O. Papp. Jegyzet az operációkutatás II. c. tantárgyhoz. (egyetemi jegyzet). 2010.

[17] B. Korte, J. Vygen. Combinatorical Optimization. Springer. 2000.

[18] A. Kósa. Optimumszámítási modellek. Műszaki Könyvkiadó, Budapest. 1979.

[19] M. Kovács. A nemlineáris programozás elmélete. TYPOTEX Kft., Budapest. 1997.

[20] T. Nagy. Matematikai programozás. Miskolci Egyetem, Miskolc-Egyetemváros. 1994.

[21] T. Nagy. Operációkutatás. Miskolci Egyetem, Miskolc-Egyetemváros. 2008.

[22] T. Nagy. Egészértékű programozás. (egyetemi jegyzet), Miskolci Egyetem. 2010.

[23] A. Prékopa. Lineáris programozás I.. Bolyai János Matematikai Társulat, Budapest. 1968.

[24] T. Rapcsák. Nemlineáris optimalizálás. Budapest. 2006.

[25] R. T. Rockafellar. Convex analysis. Princeton University Press, Princeton, New Jersey. 1970.

[26] C. Roos, T. Terlaky. Nonlinear optimization. (egyetemi jegyzet). TU Delft, Delft. 1998.

[27] A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, New York. 1986.

[28] B. Vizvári. Egészértékű programozás. TYPOTEX Kft., Budapest. 2006.