| Cím: | Lineáris programozás II. | ||
| Szerző(k): | Prékopa András | ||
| Füzet: | 1979/május, 193 - 202. oldal |  PDF | MathML |
|
| Témakör(ök): | Szakmai cikkek | ||
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. II. rész Az előző részben ismertettünk néhány feladatot a lineáris programozás köréből. Továbbá vázoltuk a Dantzig-féle megoldási módszert. Most a szendvicses példa (lásd I. rész 147. oldal) megoldását mutatjuk be. Az eredeti feladat négy egyenlőtlenséges feltételéhez segédváltozókat vezetünk be úgy, hogy a négy feltétel mindegyikében egyenlőség álljon fenn. Az új feladat a következő: E feladatnak nyilván akkor és csak akkor van megengedett megoldása és véges optimuma, ha az eredeti feladatnak, és az optimumértékek (a célfüggvények értékei az optimális megoldásokon) egyenlők. Segédváltozóinknak "fizikai'' jelentést is tulajdoníthatunk. Ezek megadják a megmaradó vaj, sonka, franciasaláta és sajt mennyiségét. Segédváltozóink még abban is segítenek bennünket, hogy máris van egy kifejezett változó rendszerünk. A (6) feladatot előbb az (5) feladatnak megfelelő alakra hozzuk: Az optimális megoldás a következő: , , , , , . Eszerint a vajat és a sonkát teljesen felhasználjuk, franciasalátából marad 7.5 dkg, sajtból pedig 10 dkg. Vegyük észre, hogy az egymást követő táblák tetején mindig az összes változó szerepel ugyanabban a sorrendben, míg a bal oldalon a bejövő változó mindig a kimenő változó helyére kerül, a többi változó azonban helyben marad. A lexikográfikus módszer Az előző szakaszban tárgyalt megoldási módszer esetében nincs garanciánk arra, hogy véges sok lépéssel eljutunk az 1. vagy a 2. tételnek megfelelő állapothoz. Ismeretesek olyan példák, melyekben néhány lépés után visszajutunk ugyanazokhoz a bázisváltozókhoz, amelyekből kiindultunk. Azt mondjuk, hogy ekkor az eljárás ciklizál. A későbbiekben ismertetni fogjuk Beale [1] példáját, amely megmutatja, hogy a ciklizálás lehetséges, előbb azonban a ciklizálás elkerülésére vonatkozó módszert tárgyaljuk. Mint a bevezetőben említettük, a módszer lényegében Charnes-tól származik, ám annak egy elegánsabb változata. A ciklizálásra akkor kerülhet sor, amikor a kimenő változó meghatározása nem egyértelmű, mert a megalkotott hányadosok minimuma több sor esetében is fellép. Ilyen esetben a következő táblában a bal oldalon álló oszlopban legalább egy zérus keletkezik. Az ezt követő táblában a bal felső sarokban álló elem biztosan változatlan marad és ha ez sorozatosan előfordul, fennáll a ciklizálás veszélye. Mielőtt a módszert ismertetnénk, bevezetjük a lexikográfikusan pozitív (L-pozitív) rendezett szám -es fogalmát. Minthogy értéke a tárgyalás során mindig ismert lesz és a rendezett szám -eseink egymás mellé egy sorban elhelyezett számokból állnak majd, elég lesz egyszerűen csak L-pozitív sorokról beszélni. Egy sort akkor nevezünk -pozitívnak, ha az elemek között van zérustól különböző, és balról jobbra haladva az első nem zérus elem pozitív. Ilyen pl. az alábbi, öt elemből alkotott sor: Egy kifejezett alakú lineáris programozási feladathoz tartozó táblát lexikográfikusan pozitívnak (L-pozitívnak) nevezünk, ha annak második és ez alatti összes többi sora -pozitív. Ebben a cikkben az eddig felírt valamennyi tábla -pozitív. A ciklizálás elkerülésére vonatkozó ún. lexikográfikus szabály (L-szabály) a bejövő változó ismeretében mindig egyértelműen dönt a bal szélső kimenő változó felől. A bejövő változóra vonatkozó szabály változatlan, tetszés szerint választhatunk egy negatív elemet a felső sorban, a bal szélső elemtől eltekintve. A kiválasztott elemnek megfelelő változó bejön. Ezután a táblában a most kiválasztott elem alatti pozitív (zérus nem lehet!) elemekkel rendre elosztjuk azokat a sorokat, amelyekben ezek a pozitív elemek állnak (vigyázzunk, a teljes sorokat kell osztani, a bal szélső elemek most nem hagyhatók el!), majd vesszük az így kapott sorok közül azt, amelyik a lexikográfikusan legkisebb. Az ennek a sornak megfelelő változó fog kimenni, ebben áll az -szabály. Az -szabállyal kapcsolatban megemlítjük, hogy véges sok különböző, de ugyanannyi elemből álló sor között mindig van egy és csakis egy lexikográfikusan legkisebb, ami azt jelenti, hogy ezt a továbbiak akármelyikéből elemenként levonva, mindig -pozitív sort kapunk. Ennek az állításnak a belátását az olvasóra bízzuk. A mi vizsgálatainkban csakis olyan tábla fordul elő, amelynek a második és ez alatti sorai páronként nem arányosak, ugyanis ha kifejezett változó, akkor abban a sorban, amely mellett van, található egy 1-es olyan helyen, hogy annak oszlopában minden egyéb elem zérussal egyenlő. Az -szabály alkalmazásakor megkívánjuk, hogy -pozitív táblából induljunk ki. Ez könnyen elérhető, ha változóinkat átszámozzuk oly módon, hogy a bázisváltozók az elsők legyenek, tehát számú bázisváltozó esetén éppen legyenek azok. Ez esetben ugyanis a bal oldalon a bázisváltozók melletti számok közül ha egyesek zérussal egyenlők is, soraikban az első nem zérus elem -gyel lesz egyenlő, tehát a tábla -pozitív lesz. Könnyen belátható, hogy ha -pozitív táblából indulunk ki és a kimenő változó meghatározására mindig az -szabályt alkalmazzuk, akkor minden további tábla -pozitív lesz, a legfelső sor pedig állandóan lexikográfikusan növekszik. Ezt nemsokára Beale példáján szemléltetjük, ahonnan az állítás általános érvénye világosan látszik majd. Most csupán leszögezzük, hogy a legfelső sor állandó -növekedése miatt egyetlen bázisváltozó-rendszer sem térhet vissza (mert akkor a legfelső sor is visszatérne, ám egy sor nem lehet egyenlő egy nála lexikográfikusan nagyobb sorral), ahonnan következik, hogy véges sok lépés után az eljárás véget ér, vagy az 1., vagy a 2. tételnek megfelelő állapot elérésével. Ezt az eredményt tételszerűen is megfogalmazzuk az alábbi módon: 3. tétel. A lexikográfikus módszer véges sok lépéssel véget ér. Most pedig bemutatjuk Beale példáját. Előbb a lexikográfikus módszert alkalmazzuk, hogy lássunk erre vonatkozó példát. Azután pedig megmutatjuk, hogy az eljárás ciklizálhat, amennyiben csupán az előző szakaszban ismertetett módszert alkalmazzuk. A lineáris programozási feladat (az általunk megkívánt alakban) a következő: A felső sorban -et kiválasztva, alatta két helyen találunk pozitív számot, ezek: 1/4 és 1/2. Azt a sort, amelyikben 1/4 áll, végigosztjuk 1/4-del, azt a sort pedig, amelyikben 1/2 áll, végigosztjuk 1/2-del. Ilyenformán az alábbi sorokat kapjuk: Lássuk most egy kicsit részletesebben, hogy miért növekszik a felső sor lexikográfikusan és miért lesz -pozitív az új tábla? Az új felső sort úgy kapjuk meg, hogy a mostani felső sorból levonjuk sorának a számmal elemenként vett szorzatát, azaz hozzáadjuk a felső sorhoz sorának 3/2-szeresét. Minthogy sora -pozitív, ebből azonnal adódik, hogy a felső sort ezáltal lexikográfikusan megnöveltük. A lexikográfikus növekedés abból adódik, hogy a negatív áll a felső sorban a sarokelem felett. Ha a sarokelem oszlopában máshol negatív szám állna, akkor az új táblában ugyanezen megfontolás alapján a megfelelő sor lexikográfikusan megnőne, tehát az új táblában ez a sor -pozitív maradna. Ez az eset most nem fordul elő, csak a teljesség kedvéért említjük. Ha a sarokelem oszlopában valamelyik szám 0, akkor az a sor, amelyikben ez a 0 áll, nem változik. Eszerint ez a sor is -pozitív marad. Esetünkben ilyen az változó sora. Az új táblázatban sora oly módon kapható meg a régi táblabeli -höz tartozó sorból, hogy ezt 1/2-vel végigosztjuk. Az új sor tehát -pozitív. Végül ami sorát illeti az új táblában, ez éppen az -szabály alkalmazása miatt lesz -pozitív. Ugyanis új sora egyenlő az alábbival: ez pedig -pozitív, minthogy (8)-ban a felső és az alsó sor különbsége -pozitív. (Amikor valamely sor zárójele elé egy számot írunk, ez azt jelenti, hogy a sor minden eleme ezzel a számmal végigszorzandó.) Ezek után a másik tábla a következő: Vegyük észre, hogy a felső sor lexikográfikusan nagyobb, mint az 1. tábla felső sora. A 2. táblában az -szabály nem jut szerephez, mert egyedül jöhet be és egyedül mehet ki. A harmadik és egyben optimális megoldást szolgáltató tábla így alakul: Az optimális megoldás tehát a következő: , , , , , , . A ciklizálás lehetőségét az alábbi táblák sorozata mutatja: Nemrég napvilágot látott egy új szabály a ciklizálás elkerülésére, az angol Bland [2] dolgozatában. Eszerint ciklizálás akkor sem fordul elő, ha mind a bejövő, mind a kimenő változót az arra alkalmasak közül úgy választjuk, hogy indexük a lehető legkisebb legyen. Bland tárgyalásmódját nem ismertetjük, mert egyrészt bonyolultabb a miénknél, másrészt további előismereteket tételez fel Induló bázisváltozók keresése A szendvicskészítés példájában könnyű volt induló bázisváltozókat találni. A bevezetett segédváltozók megfeleltek e célra. Nem mindig van ilyen könnyű dolgunk. Ha a (6) feladatban a jobb oldalon akár csak egy szám is negatív volna, máris bajban volnánk, hiszen kikötöttük, hogy a nem bázisváltozókat zérussal egyenlővé téve, a bázisváltozók számára adódó értékek nemnegatívak legyenek. Az induló bázisváltozók keresésének általános módszere az ún. kétfázisú módszer. Olyan feladatból indulunk ki, amelyben a változók nemnegativitási feltételein kívül minden további feltétel egyenlőséges. Ilyen pl. az alábbi feladat: A kétfázisú módszer első fázisában önkényesen bevezetünk minden egyenlőséges feltételhez a bal oldalon egy további változót, ezeket mesterséges változóknak nevezzük. Ezután előírjuk, hogy ezek is nemnegatívak legyenek és megfogalmazzuk azt a feladatot, amely a mesterséges változók összegének minimalizálásában áll, vagy ami ugyanaz, maximalizálandó a mesterséges változók összegének -szerese. A fenti feladat esetében ily módon a következőkre jutunk: Optimális megoldáshoz és egyben új bázisváltozókhoz érkeztünk. A 3. tábla alapján a feladat egyenlőséges feltételeinek új, a korábbiakhoz egyenértékű alakja a következő: Az eredeti változókat a mesterséges változókkal szemben "fizikai változóknak'' is szokás nevezni. A kétfázisú módszerrel kapcsolatban még a következőket fontos tudni. Ha az első fázis befejeződik és az optimumérték 0-tól különbözőnek adódik, akkor ez azt jelenti, hogy az eredeti feladatnak nincs megengedett megoldása. Ha az első fázis végén az optimumérték 0-val egyenlő, de marad mesterséges változó a bázisváltozók között, akkor az utolsó táblában a bal oldali oszlopban a mesterséges változók melletti számok szükségszerűen 0-val egyenlők. Ilyenkor először is a bázison kívüli mesterséges változókat a feladatból egyszerűen elhagyjuk. A bázisban bennmaradt mesterséges változókat pedig megpróbáljuk egymás után fizikai változókra kicserélni. A csere után ezeket a mesterséges változókat is egyszerűen elhagyjuk majd. Ha pl. az első fázis végén a bázison kívüli , , mesterséges változók elhagyása után az alábbi feltételekre jutottunk: ahol a bázisban bennmaradt mesterséges változó, akkor a legalsó sor segítségével elimináljuk pl. -et a felső három sorból. Ezáltal kimegy a bázisból, pedig bejön. Ilyen csere csak akkor nem volna lehetséges, ha az utolsó sorban és együtthatói zéróval lennének egyenlők. Képzeljük el, hogy ez következett be. Ekkor azt a konzekvenciát vonjuk le, hogy az eredeti, mesterséges változókkal még el nem látott feladatban az utolsó feltétel az első három feltétel alkalmas konstansszorosainak összegeként áll elő, vagyis az utolsó feltétel felesleges. Általában, ha az mesterséges változó nem távolítható el a bázisból egy fizikai változó behozatalával, akkor az eredeti feladatban felesleges az a feltétel, amelyhez az -et vezettük be. Az első fázis végén tehát a felesleges egyenlőségeket is felfedezzük. |