14.5. 14.5. Példamegoldás

1. Példa:

Oldjuk meg az alábbi szállítási feladatot „magyar módszerrel”!

0. lépés: A kereslet és a kínálat egyensúlyban van, tehát a „magyar módszer” alkalmazható.

1. lépés: A kiinduló redukált költségtáblázat meghatározása sor- és oszlopredukcióval.

2. lépés: Az általános Kőnig feladat megkonstruálása, a kiinduló szállítás meghatározása, majd útkeresés cimkézéssel.

A pozitív redukált költség helyeken a letiltások (-) beírása után az induló szállítást az Észak-Nyugati sarok módszerrel határozzuk meg, majd a folyamnövelést címkézéssel végezzük.

Az általános Kőnig feladat nem oldható meg, azaz az összes árut nem lehet elszállítani. A Kőnig feladat megoldási lépéséből áttérünk az redukált költségtáblázat módosításának lépésére.

3. lépés: Lefedés és a költségredukció végrehajtása.

A baloldali táblázat a régi -t, a jobboldali pedig az új redukált költségtáblázatot mutatja. A Kőnig feladat utolsó címkézése alapján elvégezzük a lefedést. A címkézett oszlopokat és a címkézetlen sorokat fedjük le a redukált költségtáblázatban. Hogy egy helyen legyen a lefedés és a redukált költségek módosítása, ezért írtuk le mégegyszer a régi táblázatot.

Az számítása: .

Az új -t úgy számítjuk ki, hogy a fedetlen elemeket csökkentjük értékkel, a kétszer fedetteket növeljük értékkel, az egyszer fedett elemeket változatlanul hagyjuk. Innentől kezdve a 2. és a 3. lépések ismétlődnek addig, amíg valamelyik Kőnig feladat megoldható nem lesz.

4. lépés: Az új általános Kőnig feladat megoldása.

A letiltásokat az új redukált költségtáblázat alapján elvégezzük és egy induló szállítást határozunk meg. Ezt végezhetjük a jól ismert Észak-Nyugati sarok módszerrel, de az előző általános Kőnig feladat szállítása is használható. A példamegoldás során mi az utóbbit követjük, vagyis bemásoljuk az előző szállítást. A bemásolásnál legfeljebb zérus szállítást nem tudunk bemásolni. Ezután a szállítási táblázatban azo(ko)n a hely(ek)en üres cella fog lenni, ahol az számításánál a minimum eléretett. Ezekre a helyekre a táblázat szegélyei alapján beírjuk a szállítást. Ha pozitív szállítást tudtunk beírni, akkor a szállítást javítottuk. Ezt a fajta folyamnövelést triviális folyamnövelésnek vagy egyszerűbben triviális javításnak szoktuk nevezni, mivel minden nehézség nélkül elvégezhető. A példában a -tól az -hez 2-t szállíthatunk triviális módon.

Találtunk utat, az út mentén a szállítást növelhetjük. Az útkeresés az termelőtől indult ki és megérkeztünk a fogyasztóhoz. Az utat mint ismeretes a címkéken visszafelé haladva határozhatjuk meg, amely a következő:

Mint ahogy az általános Kőnig feladat tárgyalásánál láttuk, az utat nem írjuk le, hanem amikor az utat meghatározzuk a címkéken visszafelé haladva, egyszerre elvégezzük az út éleinek bejelölését, váltakozva a és a szimbólumok berajzolásával. Az út éleinek szabad kapacitását az út élei alatt tüntettük fel. A szállításon mennyiséggel javíthatunk. A ismeretében egyszerűen elvégezhető a szállítás javítása, szimbólumnál csökkentünk, szimbólumnál növelünk. Az alábbi táblázat a fent leírt javítást mutatja és újra kezdjük a címkézést, mivel még van elszállítandó mennyiség.

5. lépés: Lefedés és a költségredukció végrehajtása.

A könnyebb követhetőség kedvéért mégegyszer leírtuk a régi táblázatot. A későbbiekben az eredeti helyen végezzük el a régi táblázat lefedését.

6. lépés: Az új általános Kőnig feladat megoldása.

Az általános Kőnig feladatot megoldottuk, azaz sikerült elszállítani az összes árut a fogyasztókhoz. Ezzel a „magyar módszer” algoritmusa végetért. Az alábbiakban a primál feladat és a duál feladat optimális megoldását közöljük.

A primál feladat optimális megoldása:

Az optimális szállítást az alábbi táblázat tartalmazza. A zérusok kiírása helyett a jobb áttekinthetőség miatt (-) jeleket is használhatunk. Ez itt nem letiltást jelent, hanem optimális esetben ezekre a helyekre nem érdemes szállítani.

A minimális szállítási költség számítása:

A duál feladat optimális megoldása:

A teljesség kedvéért közöljük a szállítási feladat duáljának optimális megoldását. Ez egyfajta ellenőrzési lehetőség lehet, mivel a két célfüggvény optimális értéke megegyezik. Az eljárás során a duál változókat magába foglaló redukált költségtáblázattal dolgoztunk. Az definíciós összefüggés alapján könnyen vissza tudjuk számítani az és a duál változók optimális értékeit. Célszerű a fenti képlet helyett a képlet használata. A baloldal ismert, hisz az eredeti költségtáblázatot és a legutolsó redukált költségtáblázatot kell kivonni egymásból. A jobboldalból pedig látható, hogy a duálváltozók egyértelműen nem határozhatók meg, csak egy konstans erejéig. Válasszuk például az -t. Az alábbi táblázat árnyékolt részének celláin végighaladva először a , majd az duál változókat határozhatjuk meg az egyenlet cellánkénti megoldása utján. Természetesen más duál változót is megválaszthatunk önkényesen és az egyenleteket más cellákra is felírhatjuk.

A duál feladat célfüggvényének maximális értéke:

Látható, hogy a két feladat célfüggvényének optimális értéke megegyezik. Ez egyfajta ellenőrzést is szolgáltathat a megoldás helyességére.

A szállítási feladat dualitási tételében beláttuk, hogy a duál célfüggvény minden lépésben határozottan növekszik. Megmutatjuk, hogy lépésenként mekkora volt a növekmény. Először meg kell határoznunk az induló duál változókhoz tartozó célfüggvényértéket. Az induló duálváltozók pedig egyszerűen adódnak a sor- és oszlopredukcióból, hiszen . Tehát a és . A duál célfüggvény pedig

Észrevehetjük, hogy a kínálati mennyiségeket rendre össze kell szorozni a sorokat redukáló mennyiségekkel, majd a keresleti mennyiségeket is rendre össze kell szorozni az oszlopokat redukáló mennyiségekkel és ezeket a szorzatokat össze kell adni. Az induló duál célfüggvényérték tehát 124.

A 2. lépésben a Kőnig feladat nem volt megoldható, így a kiadódó halmazok: és . Ekkor . A célfüggvénynövekményt pedig az alábbi összefüggés adja:

Az új, javított célfüggvényérték: 132.

A 4. lépésben sem volt megoldható a Kőnig feladat, ekkor és . Ekkor . A célfüggvénynövekmény: 6. Az új, javított célfüggvényérték: 138. Több javítás nem volt, ez az optimális (maximális) duál célfüggvényérték.

2. példa:

Három raktárban (R) 10, 12 ill. 12 tonnányi bizonyos fajta anyagunk van. Az anyagokat öt felhasználó műhelybe (M) kell szállítani, amelyeknek rendre 4, 5, 7, 9, 7 tonna anyagra van szüksége. Az anyagok tonnánkénti szállítási költségét az alábbi táblázat tartalmazza. Feladatunk olyan szállítási program kidolgozása, hogy a műhelyek 32 tonna igényét kielégítsük és a szállítás költsége minél kisebb legyen. Feltesszük, hogy a szállítási költség arányos a szállított mennyiséggel. Az raktár nem szállíthat az műhelynek. Az raktárt ki kell üríteni.

Megoldás:

0. lépés: Átalakítás standard alakra:

A feladat nem standard szállítási feladat, mert az összkereslet (32) kisebb, mint az összkínálat (34). Be kell iktatni egy () műhelyt zérus szállítási egységköltségekkel és 2 kereslettel. Mivel az előírás szerint az raktárban nem maradhat áru, ezért innen csak valóságos műhelyekhez szállíthatunk, tehát le kell tiltani az viszonylatot. Ezt egy nagy költség használatával valósítjuk meg és M szimbólummal jelöljük a költséget. Hasonlóan tiltjuk le az viszonylatot is. A standard szállítási feladat ekkor a következő. Indulhat a megoldás a „magyar módszerrel”.

1. lépés: Sor- és Oszlop redukció:

Sorredukció:

Oszlopredukció:

2. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel

Nem találtunk utat.

3. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Most már nem írjuk le mégegyszer a táblázatot, hanem a helyén végezzük el a lefedést. Az új redukált költségtáblázat a következő:

4. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Nem találtunk utat.

5. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

6. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Nem találtunk utat.

7. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

8. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Vége az algoritmusnak, mert az összes árú el lett szállítva. A keresett szállítási programot a fenti táblázat mutatja. Ebből kiolvasható, hogy az raktárban marad 2 tonnányi elszállítatlan áru.

A minimális szállítási költség: 126.

3. példa:

Három termelőnél (T) összesen 18 mennyiségű áru van azonos eloszlásban. El kell szállítani ezeket az árukat a fogyasztókhoz, amelyeknek az igénye rendre 4, 7, 3, 6 mennyiség. Ismertek a termelők és a fogyasztók közötti távolságok valamilyen távolságegységben. Tudjuk azt, hogy a szállítási költség arányos a távolsággal, az arányossági tényező értéke 20. Mennyi a szállítási költség alsó és felső korlátja? Az fogyasztó teljes igényét ki kell elégíteni. Az fogyasztó nem igényel árut a termelőtől.

Megoldás:

A feltett kérdésre azonnal megadhatjuk a választ. A szállítási költség alsó korlátja 0 (nem lehet negatív a költség), a felső korlát pedig (9-nél nagyobb költséggel nem szállíthatunk). Ennél jobb felső korlát is adható . Itt az egyes termelőktől történő szállítás legnagyobb költségével számoltunk. Hasonlóan adható meg a jobb alsó korlát is, amely . Nyílvánvaló, hogy a legjobb korlátokat szeretnénk megismerni. A legnagyobb alsó korlát és a legkisebb felső korlát érdekli a szállíttatót, ami esetünkben a minimális ill. a maximális költségnek felel meg. Ehhez két feladatot kell megoldani, egyik a szállítási költséget minimalizáló, másik pedig maximalizáló szállítási feladat.

Ne feledkezzünk meg arról, hogy távolságadataink vannak, ebből költségtáblázatot úgy készítünk, hogy minden táblázatbeli adatot beszorozzuk az arányossági tényezővel. Erre azonban nincs szükség, elegendő az algoritmus lépéseit a távolságadatokkal elvégezni és a végén szorozzuk be a távolságokkal számított célfüggvényértéket 20-al.

(A) Minimum feladat:

0. lépés: Átalakítás standard alakra:

A feladat nem standard szállítási feladat, mert az összkínálat (18) kisebb, mint az összkereslet (20). Be kell iktatni egy () termelőt zérus szállítási egységköltségekkel és 2 kínálattal. Mivel az előírás szerint az fogyasztó teljes igényét ki kell elégíteni, ezért ide csak valóságos fogyasztóktól szállíthatunk, tehát le kell tiltani az viszonylatot. Hasonlóan tiltjuk le az viszonylatot is. A standard szállítási feladat ekkor a következő. Indulhat a megoldás a „magyar módszerrel”.

1. lépés: Sor- és Oszlop redukció:

Sorredukció:

Oszlopredukcióra most nincs szükség.

2. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel

Nem találtunk utat.

3. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Most már nem írjuk le mégegyszer a táblázatot, hanem a helyén végezzük el a lefedést. Az új redukált költségtáblázat a következő:

4. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

5. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

6. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

7. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

8. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Találtunk utat. A szállítás javítása, majd útkeresés címkézéssel:

Nem találtunk utat.

9. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

10. lépés: Általános Kőnig feladat megoldása:

A szabaddá vált viszonylatban triviális módon javíthatjuk a szállítást. Ezt mutatja a következő táblázat:

Vége az algoritmusnak, mert az összes árú el lett szállítva. A minimális költségű szállítás a fenti táblázat szerint valósítható meg. Ebből kiolvasható, hogy az fogyasztó igényét nem elégítettük ki.

A minimális szállítási költség: .

(B) Maximum feladat:

0. lépés: Átalakítás standard alakra:

A feladat nem standard szállítási feladat, egyrészt mert nem minimumot kell keresni, másrészt az összkínálat (18) kisebb, mint az összkereslet (20). Először minimumfeladattá alakítjuk a problémát úgy, hogy a táblázat minden elemét kivonjuk a táblázat legnagyobb eleméből (9). Ezután iktatjuk be a be a fiktív termelőt (). Ezt és a letiltásokat ugyanúgy végezzük mint a minimumfeladatnál. A standard szállítási feladat ekkor a következő. Indulhat a megoldás a „magyar módszerrel”.

1. lépés: Sor- és Oszlop redukció:

Sorredukció:

Oszlopredukcióra most nincs szükség.

2. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel

Nem találtunk utat.

3. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Most már nem írjuk le mégegyszer a táblázatot, hanem a helyén végezzük el a lefedést. Az új redukált költségtáblázat a következő:

4. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

5. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

6. lépés: Általános Kőnig feladat megoldása:

Útkeresés címkézéssel:

Nem találtunk utat.

7. lépés: Lefedés és a redukált költségtáblázat módosítása

Lefedjük a redukált költségtáblázatot és meghatározzuk értékét . Az új redukált költségtáblázat a következő:

8. lépés: Általános Kőnig feladat megoldása:

A szabaddá vált viszonylatban triviális módon javíthatjuk a szállítást. Ezt mutatja a következő táblázat:

Vége az algoritmusnak, mert az összes árú el lett szállítva. A maximális költségű szállítás a fenti táblázat szerint valósítható meg. Ebből kiolvasható, hogy az fogyasztó igényét nem elégítettük ki.

A maximális szállítási költség: .

Tehát a szállítási költség a intervallumban mozoghat.

4. példa:

Egy üzem három műhelyében (M) termel bizonyos terméket, amelyekből három megrendelő (F, fogyasztó) rendre 40, 20, 10 darab terméket igényel. A műhelyek termelési kapacitása rendre 20, 40, 30 darab termék. Az egyes műhelyek fajlagos termelési költsége rendre 100, 120, 110 Ft/db. A műhelyek és a megrendelők közötti fajlagos szállítási költségeket (Ft/db) az alábbi táblázat mutatja. Az megrendelő csak az vagy az műhely által gyártott terméket kívánja megvásárolni. Határozza meg a műhelyek optimális termelési tervét és az optimális szállítási tervet úgy, hogy a megrendelést minél kisebb összköltséggel (termelési + szállítási) biztosítsuk! Mennyi az üzem összes termelési ill. összes szállítási költsége?

Megoldás:

Ha a műhelyek teljes kapacitással termelnének, akkor a kínálatuk 90 lenne, míg a fogyasztók igénye csak 70. A műhelyek nem mindegyikének érdemes tehát teljes kapacitáson termelnie. A feladatot úgy oldjuk meg, hogy mindegyik műhely a „kapacitásán” termel, a bevezetett fiktív fogyasztó fogja majd biztosítani, hogy mely műhelyek mennyit termeljenek a valóságban. Az, hogy melyiknek mennyit érdemes termelni az a megrendelésen kívül a fajlagos termelési és szállítási költségektől függ. A célfüggvény tehát itt a két fajlagos költség összege lesz, amelyet egyszerűen beláthatunk. Ha például az -tól az -hez szállítandó mennyiség, akkor ez azt jelenti, hogy ezt a mennyiséget egyrészt le kell gyártani, másrészt el kell szállítani. A termelés költsége , a szállítás költsége pedig , a költségek összege . Hasonlóan a táblázat többi eleménél is a két fajlagos költséget össze kell adni. Az elmondottak alapján elkészíthetjük az eredeti feladat standard alakú szállítási feladatát, figyelembe véve a letiltási előírást is. Tehát be kell vezetni egy fiktív fogyasztót mennyiségű kereslettel. Mivel nincs különös előírás a műhelyekre olyan vonatkozásban, hogy valamelyiknek teljes kapacitással kell termelni, ezért a fikfív fogyasztóhoz tartozó költségek zérusok.

Innentől kezdve a „magyar módszer” szokásos lépései szerint haladunk a megoldásban. A megoldás során a gyorsítás végett a lefedendő táblázatot nem közöljük kétszer, hanem a helyén fedjük le. Ez zavarhatja az olvasót, hisz amikor még csak számolja az táblát az már le van fedve. Először tehát a sor- és oszlopredukciót végezzük el.

A redukált táblázat segítségével kijelöljük a szabad és a tiltott szállítási helyeket, majd Észak-Nyugati sarok módszerrel egy induló szállítást határozunk meg, amit címkézéssel próbálunk javítani.

Nem sikerült javítani, a címkézés alapján elvégezzük a lefedést és meghatározzuk az új redukált költségtáblázatot.

Az új redukált költségtáblázat alapján újra kijelöljük a szabad és a tiltott szállítási helyeket, majd az előző szállítás bemásolása után a szállításon címkézéssel próbálunk javítani.

Most sem sikerült javítani, a címkézés alapján az utolsó redukált költségtáblázatot lefedjük és egy újabb redukált költségtáblázatot állítunk elő.

Ehhez a redukált költségtáblázathoz tartozó szabad szállítási helyeken már sikerül elszállítani az összes terméket.

Az algoritmus befejeződött, az optimális megoldás az alábbiakban adható meg.

Mivel az műhely 20 terméket a fiktív megrendelőhöz szállít, ez azt jelenti, hogy az műhelynek nem kell teljes kapacitáson dolgoznia, neki 40-20=20 darab terméket kell termelnie, amelyeket az megrendelőhöz fog elszállítani. A másik két műhely nem szállít fiktív megrendelőnek, így azok a kapacitásuknak megfelelő mennyiségű (20 ill. 30) terméket gyártanak. Az műhely a termelését (20) az -hez, míg az műhely termeléséből (30) 20-at az -hez, 10-et az -hoz szállít.

Az üzem összes költsége: Ft.

Az üzem összes termelési költsége: Ft.

Az üzem összes szállítási költsége: Ft.