KURZUS: Alkalmazott operációkutatás

MODUL: I. modul: Az operációkutatás tárgya és módszerei

5. lecke: Szállítási feladat lineáris programozási modellje és megoldása

Tanulási útmutató

A szállítási feladat értelmezése, matematikai modellje és megoldása a tankönyv 4.1. és 4.2. fejezetében található.

Nagyon fontos, hogy megismerje és rögzítse a szakirodalomban használatos fogalmakat, jelöléseket. A modell skaláris formája, a tömör vektormátrix szimbólumokkal adott formája a tankönyvben található. A lineáris programozás lényegének és modelljének megértése után ez is könnyen érthető lesz. Ha mégis gondot jelent, akkor tanulmányozza át a tankönyvben található példát. A lényeg az, hogy minden körülmények között fel tudja írni az ilyen szöveges feladat modelljét.

Eddig azt az esetet tárgyaltuk, hogy a feladók készlete megegyezett a megrendelők igényével. Ez általában nem teljesül.

Tegyük fel, hogy a tankönyv 4.2. fejezetében található példában a második feladónak 40 tonna a készlete és azt, hogy az első feladótól a 2. megrendelőnek technikai okok miatt nem lehet szállítani. Viszont szeretnénk, ha a 3. feladótól minden árut elszállítanánk (hiszen az a sógorom!).

Ekkor biztos, hogy valamelyik feladónál marad áru, ezért nem egyenlőség formájában kell megfogalmazni a feltételi egyenleteket!

Így tehát a modell:

Feladókra: x 11 + x 12 + x 13 + x 14 50 x 21 + x 22 + x 23 + x 24 40 x 31 + x 32 + x 33 + x 34 = 20

(Az utolsó sorban azért =, mert mindet el kell szállítani.)

Rendelőkre x 11 + x 21 + x 31 = 40 x 12 + x 22 + x 32 = 30 x 13 + x 23 + x 33 = 20 x 14 + x 24 + x 34 = 10

Itt minden igény teljesíthető, hiszen a készlet több mint az igény!

Valamint x 12 =0, mert az első feladó nem szállíthat a 2. megrendelőnek.

Célfüggvény:

8 x 11 +10 x 12 +9 x 13 +2 x 14 + x 21 +6 x 22 +4 x 23 +10 x 24 +3 x 31 +4 x 32 +5 x 33 + x 34 min.

Ha az igény nagyobb, mint a készlet, akkor az igényt kifejező relációk (azaz a rendelőkre felírtak) lesznek értelműek!

A szállítási feladat speciális lineáris programozási feladat, ezért az Excel-táblázaton az adatokat és a változókat is érdemes tömören, mátrix formában kijelölni. A következő Excel-képernyő mutatja ezt a célszerű elhelyezést.

Az F oszlop celláiba az adott sor összege kerül, ezt az F2 cellába beírjuk, majd a többibe átmásoljuk (F3, F4, F6).

A 6. sor celláiba az adott oszlop összege kerül, pl. a B6 cellába =SZUM(B2:B4).

A célfüggvény képletét a G7 cellába írjuk be: =SZORZATÖSSZEG(B2:E4;$B$10:$E$12).

Korlátozó feltételek (egyenként kell felvenni őket):

  • $B$6:$E$6=$B$7: $E$7
  • $C$2=0
  • $F$26: $F$4<=$G$27: $G$4

Ezután kell meghívni a Solver programot és értelemszerűen elhelyezni a modell elemeit.

Ne feledkezzünk meg az x12=0 egyenlőségről és a beállításokról sem! Azaz a korlátozó feltételeknél a C2 cellát egyenlővé kell tenni nullával.

A megoldás gombra kattintva kapjuk meg az eredményt.

Tevékenységek
  • Figyelmesen olvassa el a tankönyv 91. oldalát. Rögzítse a jelöléseket.
  • Tanulmányozza a szállítási feladatot, gyakorolja a modell felírását!
  • Gyakorolja a modell elhelyezését az Excel táblázatkezelőn, majd oldja meg Solver segítségével. Mindig ellenőrizze, hogy a számítógép segítségével kapott megoldás lehet-e az eredeti feladat optimális megoldása, ugyanis több helyen lehet hibát ejteni az adat bevitel és a modell felírása során!
Követelmények
  • Fel tudja írni a szövegesen adott szállítási feladat matematikai modelljét.
  • A szállítási feladat adott modelljét célszerűen el tudja helyezni az Excel táblázatkezelőn.
  • Solver segítségével meg tudja határozni adott szállítási feladat optimális megoldását.
Önellenőrző feladatok

1. Tegyük fel, hogy három feladóhelyen (F1...F3) 100, 120 és 150 tonna áru van. Négy megrendelőhöz (R1...R4) kell szállítani rendre 80, 110, 90, 120 tonnát. A 3. feladótól az 1. megrendelőnek technikai okok miatt nem lehet szállítani, továbbá a 2. megrendelő igényét (hiszen a sógorom) teljesen ki kell elégíteni.

A szállítási költségek mátrixa a következő (100 Ft/tonna):

R1R2R3R4
F182417
F271432
F3125159

a) Írja fel a feladat lineáris programozási modelljét! Vegyen elő egy lapot ott írja fel a feltételi egyenleteket és a célfüggvényt. Ezt használja a kérdések megválaszolására.

Ha kisebb-egyenlő, vagy nagyobb-egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=.
b) Írja fel a feladókra vonatkozó feltételek együttható mátrixát, relációjeleket és a jobb oldalt!
EgyütthatókRelációkJobb oldal
1. feladóx11x12x13x14
2. feladóx21x22x23x24
3. feladóx31x32x33x34
Ha kisebb egyenlő, vagy nagyobb egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=.
c) Írja fel az igénylőkre vonatkozó feltételrendszer együttható mátrixát, a relációjeleket és a jobb oldalt!
Együttható mátrixRelációJobb oldal
1. megrendelőx11x21x31
2. megrendelőx12x22x32
3. megrendelőx13x23x33
4. megrendelőx14x24x34

Nyisson meg egy Excel-táblát! Helyezze el a költségmátrixot a C5:F7 tartományban. A változók értékei a C11:F13 tartományban legyenek olvashatók. A költségfüggvény (célfüggvény) legyen a D16 cellában. A többi szükséges lépést Önre bízzuk. Ha kész, hívja meg a Solver programot, és oldja meg a feladatot!

Az optimális megoldást írja a következő Xij mátrixba.
d) Adja meg az összes költség értékét!

Az összes költség:

2. Egy vállalkozás 3 telephelyen azonos terméket gyárt. Az egyes telephelyekről a termékeket kamionnal szállítják a megrendelőkhöz. A cég szeretné a szállítási költségeket minimalizálni. A telephelyek kapacitását és a megrendelők igényét az alábbi táblázat tartalmazza:

TelephelyABCDTermelés
Szállítási költség (eFt/km)
I.4551658865
II.35417076115
III.10059396985
Igény70627058kamion

A III. telephelyről a B megrendelőhöz nem tudnak szállítani.

Hívja meg a Solver programot, jelölje be a kért adatokat és a szükséges beállításokat.

a) Írja fel a feladat lineáris programozási modelljét! Vegyen elő egy lapot, ott írja fel a feltételi egyenleteket és a célfüggvényt. Ezt használja a kérdések megválaszolására.

Ha kisebb-egyenlő, vagy nagyobb-egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=.
b) Írja fel a feladókra vonatkozó feltételek együttható mátrixát, relációjeleket és a jobb oldalt!
EgyütthatókRelációkJobb oldal
1. telephelyx11x12x13x14
2. telephelyx21x22x23x24
3. telephelyx31x32x33x34
Ha kisebb egyenlő, vagy nagyobb egyenlő relációt kell írnia, akkor azt így adja meg: <=, illetve >=.
c) Írja fel az igénylőkre vonatkozó feltételrendszer együttható mátrixát, a relációjeleket és a jobb oldalt!
Együttható mátrixRelációJobb oldal
1. megrendelőx11x21x31
2. megrendelőx12x22x32
3. megrendelőx13x23x33
4. megrendelőx14x24x34

Nyisson meg egy Excel-táblát! Helyezze el a költségmátrixot és a Solver programmal oldja meg a feladatot!

Az optimális megoldást írja a következő Xij mátrixba.
d) Adja meg az összes költség értékét!

Az összes költség:

Végezze el az érzékenységvizsgálatot, és nyissa meg az érzékenységvizsgálat munkalapot!

d) Írja be az árnyékár értékeit a megfelelő helyre!
Árnyékár
1. telephely
2. telephely
3. telephely
A megrendelő
B megrendelő
C megrendelő
D megrendelő