Köpeny. 4: Lineáris programozás
1 fejezet. 4: Lineáris programozó professzor Dr. Mutzel Petra Algoritmusmérnöki tanszék, LS11 Számítástudományi Kar, TU Dortmund 13./14. VO A&D WS 08// Petra Mutzel Alg. & Date WS 08/09 1
2 A VO szakirodalma V. Chvatal: Lineáris programozás D. Bertsimas: Lineáris programozás B. Vöcking: Crash Course Lineáris programozás, előadás-hatékony algoritmusok a Dortmundi Egyetemen SS2003 (lásd: Web) P. Mutzel: Script alkatrész optimalizálás (lásd: Web ) Petra Mutzel Alg. & Date WS 08/09 2
3 3.1 Bevezetési példa az olajfinomító áttekintése Példa étrendprobléma geometriai értelmezése Normál formák Simplex algoritmus kettősség motivációja 3.2 A Simplex Algorithm VO csütörtökön elmaradt Temetési szolgálat Prof. Wegener Petra Mutzel Alg. És Dat. WS 08/09 3 számára
4 Lineáris optimalizálási problémák Lineáris optimalizálási probléma (LP) meghatározása: Egy olyan vektor megtalálásának problémája, amely az összes feltételnek megfelelő vektor mellett Ax 5 példa Olajfinomító példa 2 Kőolaj krakkolási folyamata a következő hozammal és költségekkel: Krakkolási folyamat 1: 2S, 2M, 1L, költségek 3 EUR Crack process 2: 1S, 2M, 4L, ára 5 EUR Célok: legalább 3S, 5M, 4L (szállítási feltételek) előállítása a lehető legolcsóbb Petra Mutzel Alg. & Dat.
6 Példa olajfinomító A korlátozás alá eső célfüggvény határozza meg az oldat teret Mátrix jelölés: (tábla) Petra Mutzel Alg. És Dat. WS 08/09 6
7 y (0,6) Geometriai értelmezés célfüggvény = 0,9 * * 0,706 = 13,1 millió NB1 0,90 xy maximalizálása az NB1 alanyra vonatkoztatva: 0,42 xy = 0 NB5: y> = 0 (0,1,5) (0,1) (0,882,0,706 ) (0,0) Megengedett megoldások (1,0) NB2 (2,0) (3,0) x
8 Geometriai értelmezés LP Példa: Olajfinomító Petra Mutzel Alg. & Dat. WS 08/09 8
9 Példa diéta problémára Cél: Vásároljon a lehető legolcsóbban, hogy legalább 2000 kcal, 55 g fehérje, 800 g kalcium Vásárlási feltételek: Zabpehely 28 g-os kiszerelésben, a 110 kcal, 4 g fehérje, 2 mg kalcium 3 centes csirkében 100 g-os csomagolásban, 205 kcal-val, 32 g fehérje, 12 mg kalcium és 24 cent tojás dupla csomagolásban, 160 kcal, 13 g fehérje, 54 mg kalcium - 13 centi tej csomagonként 237 ml, 160 kcal, 8 g fehérje, 285 g kalcium és 9 cent között cseresznye torta 179 g-ban Csomagolás 420 kcal, 4 g fehérje, 22 mg kalcium 20 centes babban 260 g-os csomagolásban 19 cent, 260 kcal, 14 g fehérje, 80 mg kalcium 19 centben
10 LP maga a diétás probléma esetén További másodlagos feltétel: A zabpehely nem fogyasztható tej nélkül: Egy csomag zabpehelyhez fél csomag tej szükséges: 0,5 x 4 x 1 Petra Mutzel Alg. & Dat. WS 08/09 10
11 Lineáris optimalizálási problémák A lineáris optimalizálási problémák különböző megfogalmazásokban jelennek meg, és mind átalakíthatók egymásba: max vagy min c T x: Ax b min c T x: Ax b és x 0 min c T x: Ax = b és x 0 Normál forma: max c T x: Ax = b és x 0 Petra Mutzel Alg. És Dat. WS 08/09 11
12 Lineáris optimalizálási problémák LP a legáltalánosabb formájában: Minden vektorot (x, y), amely teljesíti az összes korlátot, az LP megvalósítható megoldásának nevezzük. Petra Mutzel Alg. & Dátum WS 08/09 12
13 Geometriai ábrázolás: megoldástér Az x = (x j) változó allokáció megfelel az n n dimenziós tér egy pontjának. Minden a it x b i korlátozás meghatároz egy fél teret. Ennek a féltérnek a határa az a it x = b i hipersík. A féltér a hipersík egyik oldalán lévő pontokból áll, beleértve a hiper sík pontjait is. A félterek minden korlátozás metszéspontja a megengedett megoldások tere. A megoldási tér sokszöget képez. A bekötött poliédereket politopoknak nevezzük. A sokszög által leírt ponthalmaz domború, vagyis minden egyes x, y P pontpár esetében az x és y közötti összekötő vonal összes pontja P.-ban van. Kivonat Vöckingből (lásd fent)
14 Geometriai ábrázolás: célfüggvény A z (x) = c T x célfüggvény irányt mutat R n-ben. Ezt az irányt a kezdőponttól kezdődő és a c ponton áthaladó sugár segítségével tudjuk elképzelni. Legyen H egy hipersík, amely merőleges a célfüggvény sugarára, vagyis van olyan z R érték, hogy H =. A H minden pontjának ugyanaz a z objektív függvényértéke, amelyet z (h) -nek nevezünk. Azt az LP-t, amelynek z (x) célfüggvény-értékét a korlátok felfelé korlátozzák (max z (x) -nél), korlátozott LP-nek nevezzük. Egyébként az LP korlátlan. Kivonat Vöckingből (lásd fent)
15 Geometriai ábrázolás: sarokmegoldások Mind a n lineárisan független hipersík metszi a metszéspontot. A P polihedron oldat metszéspontjait P csúcsainak nevezzük. Két sarok szomszédos, ha pontosan egy hipersíkban különböznek egymástól. A szomszédos sarkok egy él által vannak összekötve egymással. Az él megfelel e sarkok n-1 közös hipersíkjának metszéspontjának. Kivonat Vöckingből (lásd fent)
16 Geometriai ábrázolás: optimális megoldás Korlátozott LP max c T x s.t. A b, x 0 tengely z objektív funkcióval és a P. poliéderrel. H egy z-re merőleges hipersík, amely metszi a P Képzeljük el, hogy H felfelé tolódik (vagyis a célfüggvény irányába). Ennek eredményeként z (h) folyamatosan növekszik. Pontosan úgy mozgatjuk H-t, hogy ne legyen többé pont H felett. Legyen H * az így kapott hipersík. Ekkor a H * P tartalmazza az LP optimális megoldásait. A konvexitás miatt ezen pontok közül legalább az egyik P. sarka. Tehát mindig van egy sarok optimális célértékkel. Legyen kivonat a Vöckingből (lásd fent)
17 Geometriai ábrázolás: Optimális sarok Legyen v a P poliéder tetszőleges sarka. Legyen H v a v-n átmenő z-re merőleges hipersík. Legyen e az egyik él, amely v esélyes. Ha e H v felett fut, akkor a célérték javul, ha v-ből indul és e mentén fut. Egy ilyen élt javító élnek nevezünk. Ha v-nek nincs javuló éle, akkor nem mozgathatjuk H v-t anélkül, hogy elhagynánk P-t (a konvexitás miatt). Tehát H v = H * és így v optimális. A következők érvényesek itt: A globális optimum megfelel egy lokálisan optimális saroknak. Kivonat Vöckingből (lásd fent)
18 Összefoglaló tétel: Max c T x s.t forma minden behatárolt LP esetén. A b, x 0 tengely a P oldhatára mellett legalább egy P csúcsa van, amely az optimális célfüggvény értékét (az optimális sarok) veszi fel. Az a sarok, ahol nincs javuló beesési él, optimális sarok.
19 Lineáris programozás A lineáris program P elfogadhatósági tartományának három különböző lehetősége van: P = nincs egyetlen megengedett megoldás LP oldhatatlan P és inf nem létezik (pl. 0x -1) LP megoldható, de nincs optimális P megoldás és min létezik LP megoldható, és véges megoldása van x * c T x * = min Petra Mutzel Alg. és Dat. WS 08/09 19
20 A lineáris programozás kettőssége Előnyös, ha meg lehet határozni a lineáris programok határait. A (2) - (4) pontokat kielégítő pont kielégíti az egyenlőtlenséget is: 2 (2) + (3) A legjobb határokat keressük: Kettősség Petra Mutzel Alg. & Dátum WS 08/09 20
21 A lineáris programozás kettőssége Elsődleges program: Kettős program: Petra Mutzel Alg. & Dat. WS 08/09 21
22 A lineáris programozás kettőssége Primal program (P): Dual program (D): Gyenge kettősségi tétel: Legyen x érvényes pont a (P), y pedig (D). Ezután: y T b c T x Következmény: Ha (P) nincs korlátozva, akkor (D) megoldhatatlan. Petra Mutzel Alg. & Dátum WS 08/09 22
23 A lineáris programozás kettőssége Primal program (P): Kettős program (D): Erős kettősségi tétel: Legyen x * megengedett pont a (P) számára és y * megengedett a (D) számára. Ezután: y * T b = c T x * mindkét megoldás x * és y * optimális Részletek: később az előadásban Petra Mutzel Alg. & Dat. WS 08/09 23
24 3.2 A Simplex algoritmus A gyakorlatban a lineáris programokat a Simplex algoritmus segítségével oldják meg [Dantzig 1955]. Max 3x 1 + 2x 2 + 2x 3 Figyelembe véve x 1 + x 3 8 x 1 + x 2 7 x 1 + 2x 2 12 x 1, x 2, x 3 0 Petra Mutzel Alg. & Dat. WS 08/09 24
25 A szimplex algoritmus vizualizálása Max z = 3x 1 + 2x 2 + 2x 3 x 3 (0,0,8) (0,6,8) Optimális! (2,5,6) z = 28 z = 0 (0,6,0) x 2 (7,0,1) z = 23 (2,5,0) x 1 (7,0,0) z = 21.
26 Simplex algoritmus Adva: LP megoldási polihedron P (1) Találjon meg egy tetszőleges P. sarkot (kezdő sarok) v. (2) Ha nincs javuló élesés a v stophoz: v optimális. (3) A v bármely javuló élének szekvenciája. Ha e nincs korlátozva, azaz nincs más végpont-megállója: Az LP nincs korlátozva. (4) Legyen u az e másik végpontja. Állítsa be v = u. Ugrás (2)
27 Nyitott kérdések a szimplex algoritmusról Hogyan találja meg a P kezdeti v sarkát? A nem negatív a ij és bi normál formában megengedett LP-k esetében az origó (0. pont) mindig a P. csomópontja. Ellenkező esetben az előfeldolgozást (1. fázis) használják, amely a P-n kívüli kereszteződésnél és hasonló alapvető cserelépéseken keresztül indulhat egy sarokba fut P-ben. Hogyan menthető a sokszög? A korlátozások által leírt egyenletrendszert tábla formájában menti a rendszer. Minden egyes szimplex lépésben megváltozik a tabló, és az aktuális sarok kimenő élei kiszámíthatók a tablóból. Tesztelje, hogy az aktuális sarok optimális-e? Ha nem, melyik fokozó élt választja? Véget ér az algoritmus? lásd előadás: ugyanaz
28 Definíciók Adjuk meg az Ax = b egyenletrendszert A R m n, m értékkel. 29 Definíciók Ha A B szabályos (= invertálható), akkor A B-t B alapmátrixának vagy bázisának, B-t pedig B index indexnek vagy A bázisának nevezzük; analóg az A N, N nem bázis index vektorral. Az x R n vektort x N = 0, x B = AB -1 b-vel nevezzük Ax = b alapmegoldásának az A B alaphoz. Ha AB bázis, akkor a változókat xj, j B, alapváltozóknak és az xj, j N Nem alapváltozók. Ha A B az alap és A B -1 b 0 érvényes, akkor A B, B és a megfelelő x bázisoldatot megengedettnek, különben nem megengedettnek nevezzük. Az A B alapú megvalósítható x bázisoldatot nem degeneráltnak nevezzük, ha (x B) i = (A B -1 b) i> 0 az összes i B esetében, különben degenerálódik.
30 Simplex egyenlet séma és Simplex tabló max c T x s.t. Ax = b, x 0 max c B c N T x B x N s.t. (AB, AN) x B = b, x B 0 x N x NAB x B + AN x N = bx B = AB 1 b AB 1 AN x N Célfüggvény értéke: z = c BT x B + c NT x N = c BT (AB 1 b AB 1 AN x N) + c NT x N = = c TBA 1 B b + (c TN c TBA 1 BAN) x N Simplex egyenlet séma: x B = A 1 B b A 1 BAN x N z = c TBA 1 B b + (c TN c TBA 1 BAN) x N
31 Simplex-egyenlet és Simplex-tábla Simplex-egyenlet-séma: x B = AB 1 b AB 1 AN x N z = c BTAB 1 b + (c NT c BTAB 1 AN) x N Célfüggvényérték Simplex táblázat: az alapváltozók értékei - c BTAB 1 b AB 1 bc NT c BTAB 1 ANAB 1 AN csökkentett költségek
32 Simplex-egyenlet séma és Simplex Tableau-tétel: Legyen A B megvalósítható alap x alapoldattal, A = A 1 B A N, b = A 1 B b és c T = c T N c T B A 1 B A N a csökkentett költségek. (a) Ha c T x 0, akkor x optimális (b) Legyen q s N, ha c s> 0. (b1) Ha A s 0, akkor c T x P = (A, b): = korlátlan. (b2) Ha A S 0, akkor legyen λ 0 = min b i i = 1,2. m, a értéke> 0 a és r értéke < 1,2. m>úgy, hogy b r = λ 0, a rs> 0 a rs, akkor A B B = -val (p 1. p r-1, q s, p r + 1. p m) megvalósítható alap az x és c T x c T x megoldásokkal. (b3) Ha a (b2) feltételezései érvényesek, és A B nem degenerált, akkor c T x> c T x érvényes. Bizonyítás: következő VO Di példa, lásd a táblázatot