1
Operációkutatás NYME KTK, gazdálkodás szak, levelez˝o alapképzés 2002/2003. tanév, II. évf. 2.félév El˝oadó: Dr. Takách Géza NyME FMK Információ Technológia Tanszék 9400 Sopron, Bajcsy Zs. u. 9. GT fszt. 3. (99) 518 640 (30) 5600 785
[email protected] http://titanic.nyme.hu/˜takach
2. konzultáció: 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ánisí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ésve ktor 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!
3
Definíció. Az Ax ≤ b x ≥ 0 f (x) = c∗ x → max normál feladat kanonikus alakja az 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 .
♦
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 + 4x −
2y 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.
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 normál 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.
