Lineáris programozás • • • •
Modellalkotás Grafikus megoldás Feladattípusok Szimplex módszer
Feladat: Egy gyár kétféle terméket gyárt (A, B):
/db
Eladási ár Technológiai önköltség Normaóraigény Alapanyag-szükséglet
A 1000 400 15 3
•Normaóra kapacitás: 1440/év •Beszerezhető alapanyag: 240/év •Fel nem osztott költségek: 3200/év •B-ből eladható: maximum 50/év
B 800 300 20 2
x, y ≥ 0 1000x+800y -400x-300y
•15x + 20y ≤ 1440 •3x + 2y ≤ 240 -3200 •y ≤ 50
Feladat: Határozzuk meg az évi maximális nyereséget biztosító termelési tervet! Modell: A-ból x-et termelünk, B-ből y-t.
Tehát a megoldandó a következő matematikai feladat: 15x + 20y ≤ 1440 3x + 2y ≤ 240 feltételek y ≤ 50 . x, y ≥ 0 . 1000x + 800y – 400x – 300y – 3200 = 600x + 500y – 3200 → max célfüggvény Ezzel ekvivalens feladat: ugyanezen feltételek mellett a 600x + 500y célfüggvény maximumát keressük. Megoldás: később.
Definíció. Az olyan feltételes szélsőérték-feladatokat, amelyben a feltételek lineáris egyenletek és egyenlőtlenségek, és egy lineáris függvény szélsőértékét keressük, lineáris programozási feladatnak nevezzük Általánosítások: Ha a feltételek lineárisak, de a célfüggvény nem, akkor nemlineáris programozási feladatról beszélünk. Pl. hiberbolikus programozási feladat célfüggvénye alakú.
a x+b c x+d
Azon pontok halmazát, amelyek koordinátái kielégítik a feltételrendszert, lehetséges megoldásoknak nevezzük. Azon lehetséges megoldásokat, ahol a célfüggvény értéke maximális/minimális, optimális megoldásoknak nevezzük.
Kétváltozós LP-feladat grafikus megoldása • Lineáris egyenlőtlenség megoldása
3x + 2y ≤ 6
Először ábrázoljuk a megfelelő egyenlet megoldásait, pl. tengelymetszet segítségével:
3 2
Utána el kell dönteni, hogy melyik félsík lesz az egyenlőtlenség megoldása. Ez legegyszerűbben behelyettesítéssel történhet. Pl. origó: 3·0 + 2·0 ≤ 6 teljesül Az a félsík a megoldás, amiben az origó van.
Egyenlőtlenség-rendszer megoldása: Tekintem az egyes félsíkok metszetét. Ez lehet: • Üres halmaz • Egyetlen pont • Szakasz • Félegyenes • Egyenes • Konvex sokszög • Nem korlátos konvex “sokszög”
1. feladat. Oldjuk meg az előzőleg felírt feladatot 15x + 20y ≤ 1440 1 3x + 2y ≤ 240 2 y ≤ 50 3 . x, y ≥ 0 . 600x + 500y → max
600x + 500y = c → max
1
6x + 5y = c/100 → max
2 50
3 Itt van az optimum! 80
Ha pontos az ábra (vagy számolás): x = 64, y = 24
2a. Oldjuk meg az alábbi LP- feladatot: 3x + 2y ≥ 6 1 -x + y ≤ 4 2 5x + 8y ≤ 40 3 x – 2y ≤ 4 4 . x, y ≥ 0 . 2x + y → max
3 1
2
4
2x + y = c → max y = -2x + c és c → max A –2 meredekségű egyenesek közül keressük azt, amelynek Itt van az optimum! van közös pontja a Optimum koordinátái: 3 és 4 tartománnyal, és c értéke egyenletből: maximális x = 10/9, y = 56/9
2b. Oldjuk meg az előző LP- feladatot 10x + 16y → max célfüggvénnyel! 2 3x + 2y ≥ 6 1 3 2 -x + y ≤ 4 5x + 8y ≤ 40 3 1 4 x – 2y ≤ 4 . x, y ≥ 0 . 10x + 16y → max 10x + 16y = c → max y = -5/8 x + c és c → max A –5/8 meredekségű egyenesek Itt van az optimum! közül keressük azt, amelynek van közös pontja a Optimum egy szakasz! tartománnyal, és c értéke Végtelen sok megoldás! maximális
4
2c. Oldjuk meg az előző LP- feladatot 10x + 16y → min célfüggvénnyel! 2 3x + 2y ≥ 6 1 3 2 -x + y ≤ 4 5x + 8y ≤ 40 3 1 4 x – 2y ≤ 4 . x, y ≥ 0 . 10x + 16y → min
4
10x + 16y = c → min y = -5/8 x + c és c → min A –5/8 meredekségű egyenesek Itt van az optimum! közül keressük azt, amelynek van közös pontja a Optimum koordinátái: x = 2, y = 0 tartománnyal, és c értéke minimális
2c. Oldjuk meg az előző LP- feladatot 10x –5y → min célfüggvénnyel! 2 3x + 2y ≥ 6 1 3 2 -x + y ≤ 4 5x + 8y ≤ 40 3 1 4 x – 2y ≤ 4 . x, y ≥ 0 . 10x – 5y → min 10x – 5y = c → min y = 2x – c és c → min y = 5/8 x + (– c) és - c → max
4
A 2 meredekségű egyenesek Itt van az optimum! közül keressük azt, amelynek van közös pontja a tartománnyal, és -c értéke Optimum koordinátái: x =0, y = 4 maximális
3a. Oldjuk meg az alábbi LP-feladatot! x + 2y ≥ 4 1 -x + y ≤ 4 2 x – 3y ≤ 3 3 . x, y ≥ 0 . 1 x + y → min
2
Végtelen tartomány! x + y = c → min y = -x + c és c → min A -1 meredekségű egyenesek közül keressük azt, amelynek Itt van az optimum! van közös pontja a tartománnyal, és c értéke Optimum koordinátái: x =0, y = 2 minimális
3
3b. Oldjuk meg az előző LP-feladatot az x + y → max célfüggvénnyel ! 2 x + 2y ≥ 4 1 -x + y ≤ 4 2 x – 3y ≤ 3 3 . x, y ≥ 0 . 1 x + y → max Végtelen tartomány!
3
x + y = c → max y = -x + c és c → max A -1 meredekségű egyenesek közül keressük azt, amelynek van közös pontja a A célfüggvény felülről nem tartománnyal, és c értéke korlátos a lehetséges megoldások maximális halmazán.
4. Oldjuk meg az alábbi LP-feladatot! x + 2y ≤ 6 1 -x + y ≥ 2 2 x – 3y ≥ 3 3 . x, y ≥ 0 . 1 x + y → min
2
3 Üres tartomány!
A feladatnak nincs lehetséges megoldása sem.
Láttuk, hogy egy lineáris programozási feladat esetén a következő lehetetőségek fordulhatnak elő: • a lehetséges megoldások halmaza üres; • van lehetséges megoldás, de a célfüggvény nem korlátos a lehetséges megoldások halmazán; • van lehetséges megoldás, és a célfüggvény korlátos is a kívánt irányból; ekkor kétféle eset lehetséges • egyetlen optimum van; • több (végtelen sok) optimum van.
1 Operációkutatás #, NYME KTK III. évf. nappali Lineáris programozás Dr. Takách Géza NyME FMK Informatikai Intézet
[email protected] http://inf.nyme.hu/˜takach 2004. o˝ sz
Lineáris programozás (2. rész) 1. rész: ld. PowerPoint prezentáció • Modellalkotás • Grafikus megoldás • Feladattípusok • Szimplex algoritmus
Feladattípusok A) Normál feladat a11 x1 .. . am1 x1 f (x)
=
c1 x1
+ ... +
a1n xn
+ . . . + amn xn x1 , . . . , xn + ... + cn xn
≤
b1
≤ bm ≥ 0 → max
ahol megköveteljük, hogy b1 , . . . , bm ≥ 0 teljesüljön. Mátrixos alak: Ax ≤ b x ≥ 0 f (x) = c∗ x → max Itt is megköveteljük, hogy b ≥ 0 teljesüljön. A vektorok közti ≤ és ≥ jelek komponensenkénti összehasonlítást jelentenek. Tehát e ≤ f azt jelenti, hogy minden i-re ei ≤ fi . A ∗ a transzponálást jelöli, azaz c∗ egy sorvektor. B) Módosított normál feladat (Lehet egyenlet is benne.) A1 x = b1 A2 x ≤ b2 x≥0 f (x) = c∗ x → max Itt is megköveteljük, hogy b1 ≥ 0 és b2 ≥ 0 teljesüljön.
2
C) Általánosított normál feladat (Lehet = és ≥ is benne.) A1 x = b1 A2 x ≤ b2 A3 x ≥ b3 x≥0 f (x) = c∗ x → max Itt is megköveteljük, hogy bi ≥ 0 (i = 1, 2, 3) teljesüljön. D) Standard feladat (Jobb oldalra nincs kikötés) Ax ≤ b x ≥ 0 f (x) = c∗ x → max
Állítás. Az A), B), és C) feladatok mindegyike ekvivalens egy standard feladattal. Bizonyítás. A) egy speciális standard feladat. B) A1 x = b1 A2 x ≤ b2
A1 x ≤ b1 A1 x ≥ b1 A2 x ≤ b2
⇔
⇔
A1 x ≤ b1 −A1 x ≤ −b1 A2 x ≤ b2
C) A1 x = b1 A2 x ≤ b2 A3 x ≥ b3
⇔
A1 x ≤ b1 −A1 x ≤ −b1 A2 x ≤ b2 −A3 x ≤ −b3
Állítás. Minden LP-feladat ekvivalens egy általánosított normál feladattal. Bizonyítás. 1) Ha az LP-feladatban szerepel egy x el˝ojelkötetlen változó, akkor annak minden el˝ofordulási helyére írjunk (y − z)-t, ahol y és z két új, nemnegatív változó. 2) Ha valamelyik feltétel jobb oldalán negatív szám áll, szorozzuk be −1-gyel. 3) Ha minimumfeladattal van dolgunk: f (x) → min, akkor ez ekvivalens a −f (x) → max feladattal.
♦
Általánosított normál feladat visszavezetése módosított normál feladatra: a ≥ jelek helyett = írható, ha a bal oldalból levonok egy új, pozitív változót. Pl.: 2x ≥ 5 → 2x − u = 5. A módosított normál feladat az úgynevezett kétfázisú szimplex módszerrel oldható meg, kés˝obb lesz. Definíció. Az Ax ≤ b, x ≥ 0 egyenletrendszer x lehetséges megoldásához tartozó eltérésvektor az az u vektor, amelyre Ax + u = b. Az eltérésvektor i-edik komponensét tehát úgy kapjuk, hogy megnézzük: a bal oldal értéke mennyivel kisebb a jobb oldalon álló bi -nél. Nyilvánvalóan u ≥ 0. Módosított normál feladatra ill. általános feladatra ld. könyvben! Definíció. Az Ax ≤ b x ≥ 0 f (x) = c∗ x → max
normál feladat kanonikus alakja az
3 Ax + u = b x ≥ 0, u ≥ 0 f (x) = c∗ x → max
feladat. Mátrixosan a11 x1 + . . . + .. . am1 x1 f (x)
=
c1 x1
a1n xn
+ u1
+ . . . + amn xn x1 , . . . , xn + ... + cn xn
+ um ≥
=
b1
=
bm
0 → max
ahol megköveteljük, hogy b1 , . . . , bm ≥ 0 teljesüljön. Ha bevezetjük a B = A|E és az y =
x jelölést, akkor az egyenletrendszer By = b alakú lesz. u
Ha felírjuk a By = b egyenletrendszer kib˝ovített mátrixát, s az oszlopvektorokat rendre x1 , . . . , xn , u1 , . . . , um jelöli, akkor az oszlopvektorok éppen az u1 , . . . , um bázisban vannak felírva. Elemi bázistranszformációval át lehet térni más bázisra. Definíció. Egy kanonikus alakú feladat bázismegoldásán azt értjük, hogy a bázisban nem szerepl˝o oszlopokhoz tartozó változók (szabad változók) értéke nulla, a bázisban szerepl˝o oszlopokhoz tartozó változók (bázisváltozók, kötött változók) értéke pedig a jobb oldalon álló szám. Lehetséges bázismegoldáson olyan bázismegoldást értünk, amelynek nincs negatív komponense. Ha egy lehetséges bázismegoldásból elhagyjuk az ui -ket, akkor az eredeti normál feladat lehetséges megoldását kapjuk. Normál feladat esetén a kiindulási u1 , . . . , um bázisnak megfelel˝o bázismegoldás: x1 = . . . = xn = 0, u1 = b1 , . . . , um = bm . Ez lehetséges bázismegoldás, mert bi ≥ 0. a11 x1 .. . am1 x1
+ ... +
a1n xn
+ . . . + amn xn x1 , . . . , xn
+ u1
= + um
≥
b1
= bm
0
Tétel. A kanonikus alakú LP feladatnak, s így a normál feladatnak is csak véges sok bázismegoldása van. Bizonyítás. Az (A|E) mátrix rangja = sorok száma = m, hiszen az egységmátrix rangja m. Az oszlopok száma: m + n. A bázismegoldások száma ≤ m+n m .
♦
Tétel. Egy standard feladat lehetséges megoldásai a lehetséges megoldások halmazának extremális pontjai. Fordítva, a lehetséges megoldások halmazának extremális pontjai a standard feladat bázismegoldásai. Definíció. Degenerált bázismegoldásban kevesebb nullától különböz˝o elem van, mint az együtthatómátrix rangja. Tehát a bázismegoldást adó táblázatban a bal oldalon nulla is szerepel.
Egyenletrendszer bázistáblázata Most az egyenletrendszer egy megoldása azonnal leolvasható, minket viszont az érdekel, hogy hogyan lehet áttérni egy másik (bázis)megoldásra. Nem akarunk mindig feleslegesen leírni egy egységmátrixot, ennek viszont az lesz az ára, hogy a táblázat fejléceibe mindig fel kell írni, hogy a sorok és oszlopok milyen vektorokhoz/változókhoz tartoznak. 2x + 4x −
2y y
+ +
3z 5z
≤ 2 ≤ 7
2x + 2y 4x − y
+ +
3z 5z
+ u1 + u2
= 2 = 7
2 2 3 1 0 4 −1 5 0 1
2 7
3 1 1 1 0 2 2 0 −5 −1 −2 1
1 3
u1 u2
x y z 2 2 3 4 −1 5
4
b 2 7
Áttérés az x, u2 bázisváltozókra: u1
x u2
y z 3 1 2 −2 −5 −1 1 2
b 1 3
A bázistáblás írásmódnál az elemi bázistranszformáció egy lépése a mátrixelemek szintjén a következ˝o: 1. kiválasztom a generálóelemet, g-t 2. A generálóelem feletti és melletti két változónevet felcserélem 3. generálóelem reciprokát veszem 4. generálóelem oszopát osztom g-vel és szorzom −1-gyel. 5. generálóelem sorát osztom a generálóelemmel 6. további elemek: téglalap szabály: g b
ab ··· a −→ t0 = t − . ··· t g
Lehetséges bázistranszformáció Ha azt akarjuk, hogy az elemi bázistranszformáció során lehetséges bázismegoldást adó új bázisra térjünk át, azaz a jobb oldalakon ne álljon negatív szám, akkor a generálóelemet nem lehet tetsz˝olegesen választani. Mivel a generálóelem sorát végigosztjuk a generálóelemmel, ennek a sornak a jobb oldala akkor marad nemnegatív, ha a generálóelem nemnegatív. Nulla sem lehet generálóelem, tehát α) a generálóelem csak pozitív szám lehet. Ha a generálóelem aij , akkor a k-adik sor jobb oldala (k 6= i esetén) b0k = bk −
bi akj . aij
Itt b1 , bk , aij ≥ 0, kérdés, hogy mikor lesz b0k ≥ 0? Két eset van: ha akj ≤ 0, akkor b0k ≥ bk ≥ 0 automatikusan teljesül. Ha viszont akj > 0, akkor b0k = bk −
bi akj >0 aij
⇒
bk bi > akj aij
teljesülnie kell. Tehát β) az adott j-edik oszlop pozitív elemeivel osztjuk a megfelel˝o jobb oldalakat, s a generálóelemet abból a sorból választjuk, ahol ez a hányados a legkisebb. Definíció. Az α és β tulajdonságokkal rendelkez˝o elemi bázistranszformációt lehetséges bázistranszformációnak nevezzük. Tétel. Egy lehetséges bázismegoldást adó bázistáblából el lehet jutni tetsz˝oleges más lehetséges bázismegoldást adó bázistáblához a lehetséges elemi bázistranszformáció véges sokszori alkalmazásával. (standard feladatra is igaz!)
5 A célfüggvény értékét jelöljük z-vel! Ekkor z = c∗ x, azaz c∗ x − z = c∗ x + (−z) = 0. Ez egy újabb egyenlet. Ha −z-t tekintjük változónak, akkor az egyenletrendszer kib˝ovített mátrixa: x1 . . . a11 . . . .. . am1 c1
... ...
xn a1n amn cn
u1 . . . um −z 1 ... 0 0 0 ... 0 ...
1 0
0 1
b b1 bm 0
Itt a bázis az ui és −z változókhoz tartozó oszlopok: x1 a11
... ...
xj a1j
... ...
xn a1n
b1
ui .. .
ai1
...
aij
...
ain
bi
um −z
am1 c1
. . . amn ... cn
bm 0
u1 .. .
. . . amj ... cj
b
A jobb alsó sarokban álló elem adja a bázismegolásban −z értéket. Ezt minimalizálni kell. Lehetséges elemi bázistranszformáció esetén a jobb alsó sarokban lév˝o elemb˝ol le kell vonni: bi cj aij Kell: −z csökkenjen, azaz cj > 0 legyen. γ) A generálóelemet pozitív célfüggvényegyüttható (cj ) felett kell választani ahhoz, hogy az új bázismegoldásnál a célfüggvény értéke nagyobb legyen. Hogyan érhet véget az algoritmus? Tétel. Ha egy standard feladat megoldása során az egyik bázistáblában van egy olyan oszlop (j-edik), ahol minden aij ≤ 0, azaz aj ≤ 0, de cj > 0, akkor a célfüggvény felülr˝ol nem korlátos a lehetséges megoldások halmazán. Bizonyítás. Legyen x az aktuális bázismegoldás, s adjunk λ > 0-t a j-edik komponenséhez: xλ = x + λej . Ez is lehetséges megoldás, ugyanis Axλ = A(x + λej ) = Ax + Aλej = Ax + λaj ≤ Ax ≤ b. A célfüggvény értéke f (xλ ) = c∗ xλ = c∗ (x + λej ) = c∗ x + c∗ λej = c∗ x + λcj = f (x) + λcj . Ha λ → ∞, akkor f (xλ ) → ∞.
♦
Ha nincs pozitív célfüggvényegyüttható, akkor γ) szerint a célfüggvényérték nem növelhet˝o lehetséges elemi bázistranszformációval. Belátható, hogy máshogyan sem: Tétel. Ha egy bázistáblában nincs pozitív célfüggvényegyüttható, akkor az aktuális bázismegoldás optimális. Bizonyítás. Kés˝obb. Szimplex algoritmus (végesség is!): TÁBLÁN!!!
1 Operációkutatás #, NYME KTK III. évf. nappali Lineáris programozás (3. rész) Dr. Takách Géza NyME FMK Informatikai Intézet
[email protected] http://inf.nyme.hu/˜takach 2004. o˝ sz
Konvex halmazok. Jelölje En az n-dimenziós Euklideszi teret. Tehát En elemei az n komponens˝u valós szám-n-esek, és egy vektor normája az alábbiak szerint definiált: q ||x|| = x21 + . . . + x2n Két pont távolságát helyvektoraik különbségének normájával fejezhetjük ki: d(A, B) = ||a − b||. Definíció. Az a pont ε sugarú környezete az ||a − a|| < ε képlettel definiált. Definíció. Az a és b pontok által meghatározott egyenes egyenlete: x = λa + (1 − λ)b
(λ ∈ R).
Ugyanígy néz ki az a és b pontok által meghatározott szakasz egyenlete is, csak ki kell kötni, hogy 0 ≤ λ ≤ 1. Definíció. Az a 6= 0 ponthoz tartozó sugár egyenlete: x = λa, λ > 0.
Definíció. Egy K ⊆ En halmaz konvex, ha bármely két pontja által meghatározott szakasz is része K-nak.(Ennek megfelel˝oen az üres halmaz, az egyetlen pontból álló halmazok, egy szakasz, egy félegyenes, egy egyenes is konvexek.) Definíció. Az a pont a H halmaz bels˝o pontja, ha a ∈ H, továbbá létezik a-nak olyan környezete, amely teljes egészében H-ban fekszik. Definíció. Az a pont a H halmaz határpontja, ha a-nak bármely környezete tartalmaz H-beli és H-n kívüli pontot is. Definíció. A H halmaz zárt, ha minden határpontja H-hoz tartozik. Definíció. Az a pont a H halmaz extremális pontja, ha a ∈ H, továbbá nincs olyan a-n átmen˝o szakasz, amely teljes egészében H-ban fekszik. Definíció. A H halmaz korlátos, ha van egy olyan k vektor, hogy tetsz˝oleges a ∈ H esetén |ai | < ki . Definíció. Konvex poliéderen olyan K ⊆ En konvex, zárt halmazt értünk, amely egyrészt korlátos, másrészt csak véges sok extremális pontja van. Definíció. n-dimenziós szimplexen olyan n-dimenziós konvex poliédert értünk, amelynek n + 1 extremális pontja van. Tétel. Az Ax ≤ b, x ≥ 0 standard feladat lehetséges megoldásainak halmaza konvex.
2
Bizonyítás. Az üres és egyelem˝u megoldáshalmaz definíció szerint konvex. Tegyük fel, hogy x1 és x2 is megoldások: Ax1 ≤ b, x1 ≥ 0
és
Ax2 ≤ b, x2 ≥ 0.
Lássuk be, hogy az általuk meghatározott szakasz x = λx1 + (1 − λ)x2 , λ ∈ [0, 1] is megoldás. λ, 1 − λ > 0 miatt x ≥ 0. Másrészt Ax = A [λx1 + (1 − λ)x2 ] = λ · Ax1 + (1 − λ) · Ax2 ≤ λb + (1 − λ)b = b. ♦
Dualitás Definíció. Az Ax ≤ b x ≥ 0 f (x) = c∗ x → max és az A∗ y ≥ c y ≥ 0 g(y) = b∗ y → min (standard) feladatok egymás duáljai. A kiinduló feladatot szokás primál feladatnak nevezni, míg az abból származtatottat duál feladatnak. A primál maximumfeladat eltérésvektorának szokásos jelölése u, a duál minimufeladaté w: Ax + u = b,
A∗ y − w = c.
Dualitás (folyt.) Részletesen kiírva: a1n xn
≤
b1
+ . . . + amn xn x1 , . . . , xn + ... + cn xn
≤ ≥ →
bm 0 max
≥
c1
a11 x1 + . . . + .. . am1 x1 f (x)
=
c1 x1
standard feladat duálja az a11 y1 + . . . + .. . a1n y1 g(y)
=
b1 y 1
am1 ym
+ . . . + amn ym y1 , . . . , y n + ... + bm y m
≥ cn ≥ 0 → min
feladat.
Primál-duál feladatpár lehetséges megoldásai Tétel. Ha a fenti primál-duál feladatpárnak x és y lehetséges megoldásai, akkor f (x) ≤ g(y). Bizonyítás. Ax ≤ b A∗ y ≥ c Azaz f (x) ≤ y ∗ Ax ≤ g(y).
⇒ y ∗ Ax ≤ y ∗ b = b∗ y = g(y) ⇒ y ∗ A ≥ c∗ ⇒ y ∗ Ax ≥ c∗ x = f (x) ♦
3 Következmény. 1. Ha a primál feladatnak van lehetséges megoldása és a célfüggvény nem korlátos felülr˝ol, akkor a duálnak nincs lehetséges megoldása. 2. Ha a duál feladat célfüggvénye nem korlátos alulról, akkor a primálnak nincs lehetséges megoldása 3. Ha f (x0 ) = g(y 0 ), akkor x0 a primál, y 0 a duál feladat optimális megoldása.
Módosított normál feladat duálja Belátható, hogy a módosított normál feladat duáljának felírásához nem kell áttérnünk a standard alakra, hanem a következ˝oképpen járhatunk el: • Ha valamelyik feltétel egyenl˝oség, akkor a duál feladatmegfelel˝o változójára nincs el˝ojelkorlát. • Ha valamelyik változóra nincs el˝ojelkorlát, akkor a duál feladat megfelel˝o feltétele egyenl˝oség.
LP alaptétele Ld. Csernyák 1.9. tétel, illetve táblán.
Duál feladat otimuma Az el˝oz˝oek szerint a primál és duál feladat optimális célfüggvényértéke megegyezik. Ennél több is igaz: a primál feladatot megoldva az optimális megoldást adó bázistáblából leolvasható a duál feladat optimális bázismegoldása: A célfüggvényegyütthatók ellentettjei adják a duál megoldásvektor és eltérésvektor nemnulla komponenseit. A duál feladat változói a primál feladat egyenleteinek felelnek meg, vagyis a primál eltérésváltozóknak (ui ). A bázisban nem szerepl˝o eltérésváltozók oszlopából olvashatók tehát le a duál megoldásvektor (y) nemnulla komponensei. A duál feladat egyenletei a primál feladat változóinak felelnek meg, vagyis a primál változóknak (xj ). A bázisban nem szerepl˝o xj változók oszlopából olvashatók tehát le a duál eltérésvektor (w) nemnulla komponensei.
Degeneráció Volt: Definíció. Degenerált bázismegoldásban kevesebb nullától különböz˝o elem van, mint az együtthatómátrix rangja. Tehát a bázismegoldást adó táblázatban a jobb oldalon nulla is szerepel. Új: Definíció. Egy normál feladat akkor nemdegenerált, ha az egyik lehetséges bázismegoldás sem degenerált. Ez nem dönthet˝o el mindig ránézésre! A degeneráltság hátránya: γ) szabály esetén ha a generálóelem sorában a jobb oldalon nulla áll, akkor a célfüggvényérték nem változik az átalakítás során. Nincs biztosítva az algortimus végessége, mert így felléphet ciklikusság is az algoritmusban! Van arra is módszer, hogy kivédjük a ciklikusságot, de ezt nem tanuljuk.
1 Operációkutatás #, NYME KTK III. évf. nappali Lineáris programozás (4. rész) Dr. Takách Géza NyME FMK Informatikai Intézet
[email protected] http://inf.nyme.hu/˜takach 2004. o˝ sz
Alternatív optimum Definíció. Alternatív optimumról beszélünk, ha egy feladatnak több optimális megoldás is van. Tétel. Az LP feladat alternatív optimumainak konvex lineáris kombinációja is alternatív optimum. Bizonyítás. A könyvbeli bizonyítás hiányos! 1. Lehetséges megoldások konvex lineáris kombinációja is lehetséges megoldás (1.1. Tétel) utána pedig 2. Ha néhány helyen ugyanakkora a függvényérték (mindenütt optimális), akkor a konvex lineáris kombinációjukban is (könyvbeli bizonyítás): Legyenek x0 és x” is optim’lis megold’sok, azaz z 0 = z” = zo . Legyen x = λx0 + (1 − λ)x” egy konvex lineáris kombinácijuk. c∗ x = c∗ λx0 + (1 − λ)x” = λc∗ x0 + (1 − λ)c∗ x” = λzo + (1 − λ)zo = zo . ♦
Alternatív optimális bázismegoldások Az optimális bázistáblában nincs negatív célfüggvényegyüttható. De lehet esetleg nulla célfüggvényegyüttható. Ez azt jelenti, hogy a duál feladat megfelel˝o optimális bázismegoldása degenerált. Ha nulla felett választunk generálóelemet (mert van felette pozitív elem), akkor a primál feladat egy másik optimális bázismegoldásába juthatunk el: xj xi
Látható, hogy −z-b˝ol le kell vonni
0·b g -t,
g
b
0
−z
azaz a célfüggvényérték nem változik.
Degenerált optimális bázismegoldás Ha a primál feladat optimális bázismegoldása degenerált, akkor megpróbálhatunk abban a sorban generálóelemet választani, ahol a jobb oldalon nulla áll. A generálóelem nem lehet nulla de α) és β) most figyelmen kívül hagyható, hiszen a jobb oldalakon most nem jöhet be negatív szám. Viszont arra kell ügyelni, hogy a célfüggvényegyütthatók között ne jelenjen meg pozitív szám a bázisátmenet után. Ekkor a duál feladat alternatív optimumát kapjuk. xj xi
g
0
c
−z
2
Alternatív optimum és degeneráció
Tétel. Egy LP feladatnak csak akkor lehet alternatív optimuma, ha a duál feladat optimális megoldása degenerált. Bizonyítás. Nem kell. Ebben benne foglaltatik az is, hogy a duál feladatnak is csak akkor lehet alternatív optimuma, mert a duál duálja a primál. Miért nem "akkor és csak akkor" tételünk van? Mert lehet egyszerre alternatív optimum és degeneráció: xj xi
g
0
0
−z
Alternatív optimum és degeneráció egyszerre xj xi
g
0
0
−z
Ekkor g-t választva ugyan eljutunk egy másik bázisegoldáshoz abban az értelemben, hogy más lesz a bázis, de a változók értéke ugyanaz marad a primál feladat degeneráltsága miatt. Eredetileg ugyanis xi = 0, mert bázisváltozó ugyan, de a jobb oldalon nulla áll, xj pedig azért nulla, mert nem bázisváltozó. A bázistranszformáció után ez éppen fordítva lesz.
Még egy lehet˝oség Ha az optimális bázismegoldásban van nulla célfüggvényegyüttható, felette nincs pozitív elem, de van nulla, akkor nincs ugyan más optimális bázismegoldás, mégis végtelen sok megoldás van: egy félegyenesen.
Kétfázisú szimplex módszer A normál feladatnak mindig van lehetséges megoldása, az a bázismegoldás, amikor az eltérésváltozók a bázisváltozók, az erdeti feladat változói mind nullák; ez a kiindulási bázistáblához tartozik. A normál feladatnak (lehetnek egyenl˝oségek is) már nem mindig van lehetséges megoldása. Ezért a szimplex módszert kiegészítjük egy olyan els˝o fázissal, ahol találunk egy lehetséges megoldást, s innen szokásos szimplex módszerrel folytatjuk. Tekintsük a A1 x = b1 A2 x ≤ b2 x≥0 f (x) = c∗ x → max
módosított normál feladatot (b1 , b2 ≥ 0), és írjuk fel hozzá az
3
A1 x ≤ b1 A2 x ≤ b2 x≥0 fˆ(x) = 1∗ A1 x → max normál feladatot. Itt 1 az a megfelel˝o méret˝u vektor, aminek minden komponense 1. Ha ezzel balról szorzok egy mátrixot, akkor az eredmény a mátrix sorainak összege. Tétel. A fenti módosított normál feladatnak pontosan akkor van lehetséges megoldása, ha a bel˝ole felírt normál feladat optimális megoldása: fˆ = 1∗ b1 . Bizonyítás. Az egyenletekb˝ol egyenl˝otlenségeket csináltunk a feltételrendszerben, bal oldalaikat pedig összeadtuk, ez lett a másodlagos célfüggvény. Ez az összeg mindig kisebb vagy egyenl˝o, mint a jobb oldalak összege, 1∗ b1 . Ha sikerül elérni az egyenl˝oséget, akkor mindegyik feltételben egyenl˝oség teljesül, vagyis az eredeti feladat lehetséges megoldását kapjuk. ♦ Feladatmegoldás. Azoknál a soroknál, ahol egyenl˝oség áll, az eltérésváltozókat kalappal látjuk el. A másodlagos célfüggvény sora a kalapos sorok összege lesz, a hozzá tartozó konstans most nem nulla, hanem az is a kalapos sorok jobb oldalainak összege. Ezt az els˝odleges célfüggvény alatti plusz egy sorba írjuk. Az algoritmus els˝o fázisában a másodlagos célfüggvényre nézve optimalizálunk. Ha sikerül elérni, hogy a jobb alsó konstans nulla legyen, akkor a másodlagos célfüggvény optimuma fˆ = 1∗ b1 , s így az eredeti feladat egy lehetséges megoldásánál tartunk. Az esetek többségében érdemes a kalapos változókat kihozni a bázisból az els˝o lépésben, hiszen azon eltéréseknek nullának kell lenniük egy lehetséges megoldásban. A második fázisban elhagyható a másodlagos célfüggvény sora, most az els˝odelges célfüggvényre nézve optimalizálok. A fentre került kalapos változók oszlopában azonban nem szabad generálóelemet választani, azon oszlopokban nem is kell nézni a célfüggvényegyütthatók el˝ojelét, amikor el kell dönteni, hogy a jelenlegi bázismegoldás optimális-e. Lehet hogy végül pozitív elem marad ott, ami a duál feladatra nézve azt jelenti, hogy annak a bázisváltozónak az értéke negatív. Ez nem gond, hiszen az egyenleteknek a duál feladatban el˝ojelkötetlen változók felelnek meg. Szokás a kalapos sorokat elhagyni a második fázisban, ha nem vagyunk kiváncsiak a duál feladat optimális megoldására. Figyelem! Itt is lehetnek alternatív optimális bázismegoldások! Általánosított normál feladat, illetve tetsz˝oleges LP feladat visszavezetése korábban már szerepelt.
