Szállítási feladat_1.
Bevezetés, a vállalkozás bemutatása A vállalkozás 1992-ben alakult, mint egyszemélyes vállalkozás, majd évek során kinőtte magát, tevékenysége és vevőköre egyre kiszélesedett, így 2002-ben Kft-vé alakult át, de megmaradt családi vállalkozásnak, mivel tulajdonosai a család tagjai maradtak. Tevékenységük alapja az árusítás, mely során többfajta árucikk értékesítésével foglakoznak. Régóta foglalkoznak karórák, faliórák árusításával, de emellett nagy hozamot biztosító tevékenységük a törölközők és pólók géppel való hímzése is.
A probléma meghatározása A cég a törölközők szerzést 3 raktárból (feladóhelyről) végzi: Szolnok (F1), Szeged (F2), Budapest (F3). A cég ezen raktárakból kívánja megrendelőit ellátni törölközőkkel, esetünkben Szolnok (R1), Szeged (R2), Nyíregyháza (R3), és Miskolc (R4) megrendeléseit kívánja legalacsonyabb költséggel megoldani. A cég közúton furgonokkal hetente kétszer szállít. A megrendelései tehát:
Gazdasági modell felírása Feladóhelyek F1 Budapest F2 Szolnok F3 Szeged Összesen
Rendelkezésre álló (elszállítandó) mennyiség 80 70 50 200
Rendeltetési hely R1 Szolnok R2 Szeged R3 Nyíregyháza R4 Miskolc Összesen
Rendeltetési hely igényelt mennyisége (szükséglet) 20 30 50 100 200
A szállítási feladat zárt, mivel a rendelkezésre álló mennyiség = szükséglet mennyisége
(∑fi = ∑rj = 200). A költségek megállapítása a kilométerekkel arányosan történik. (A költség tartalmazza a fuvardíjat, és a benzinköltséget).
Budapest Szolnok Szeged
Szolnok 101 10 116
Szeged 172 116 15
Nyíregyháza 223 179 264
Miskolc 171 139 258
1
Kilométerskála alapján a szállítás költsége − 0-50-ig
1
− 50-120-ig
2
− 120-150-ig 3 − 150-200-ig 4 − 200-240-ig 5 − 240-300-ig 6
Rj Fi Budapest Szolnok Szeged Szükséglet
Szolnok
Szeged
Nyíregyháza
Miskolc
2 1 2 20
6 1 9 30
5 4 6 50
4 3 6 100
Elszállítandó mennyiség 80 70 50 200
A szállítási költséget az egyes feladóhelyek és rendeltetési helyek között az alábbi táblázat tartalmazza.
Rj
R1
R2
R3
R4
2 1 2 20
6 1 9 30
5 4 6 50
4 3 6 100
Fi F1 F2 F3 szükséglet
elszállítandó mennyiség 80 70 50 200
A táblázat belső részében költségmátrix van, amelynek az elemei azt mutatják meg, hogy az egyes telephelyről az egyes megrendelőhelyre mennyi pénzegységért szállítják el az áru egy egységét.
A célfüggvény felírása K = 2x11 + 6x12 + 5x13 + 4x14 + 1x21 + 1x22 + 4x23 + 3x24 + 2 x31 + 9 x32 + 6 x33 + 6x34 → min
Az egyenlet A célfüggvény a benne szereplő változóknak csak azon értékeire értelmezhető, amelyek eleget tesznek a következő feltételeknek: x11 + x12 +x13 + x14 = 80 x21 + x22 + x23 + x24 = 70
U
2
x31 + x32 + x33 + x34 = 50 x11 + x21 + x31 = 20 x12 + x22 + x32 = 30
V
x13 + x23 + x33 = 50
x14 + x24 + x34 = 100 A szállítási költséget az egyes helyek között az alábbi táblázat tartalmazza ezer db törölközőre vonatkozóan, ezer Ft-ban, táblázatban, majd költségmátrixba.
F1 F2 F3 fi
R1 2 1 2 20
R2 6 1 9 30
R3 5 4 6 50
R4 4 3 6 100
rj 80 70 50 200
fi: szükséglet az áruból rj: elszállítandó árumennyiség
2654 1143 2966
c=
Oszlopredukció Minden oszlopban ki kell vonni a legkisebb elemet az oszlop minden eleméből, így minden oszlopban van legalább egy nulla.
F1 F2 F3 fi
R1 1 0 1 20
R2 5 0 8 30
R3 1 0 2 50
R4 1 0 3 100
rj 80 70 50 200
Sorredukció Sorredukció szükséges az oszlopredukció elvégzése után, mivel nem minden sorban szerepel nulla érték.
F1 F2 F3 fi
R1 0 0 0 20
R2 4 0 7 30
R3 0 0 1 50
R4 0 0 2 100
rj 80 70 50 200
3
A probléma megoldása A probléma megoldása során Vogel-Korda módszert alkalmazunk, azaz soronként és oszloponként a két legkisebb elemet kivonjuk egymásból, vagyis differenciákat képzünk. Ezután a legnagyobb differencia sorába vagy oszlopába a legkisebb költséghelyre a lehető legnagyobb mennyiséget programozzuk. R1 F1 F2 F3 fj
0 0 20 0
R2 4 30 0
20
7 30 4
diff1
0
diff2 diff3 diff4 diff5
0
R3
R4
0 20 0 1
0
80
0
20
30
2 50 30 100 20 1
2
0
1
2
0
1
2
0
1
rj
diff1
diff2
diff3
diff4
80
0
0
70 40 20
0
0
0
0
50 20 200
1
1
1
1
diff5
1
A kapott eredménytáblázat Kötött ismeretlenek száma: m + n – 1 = 4 + 3 – 1 = 6
F1 F2 F3 fi
R1 0 0 0 20 20
R2 4 0 30 7 30
R3 0 0 20 1 30 50
R4 0 80 0 20 2 100
rj 80 70 50 200
Szállítási költség K = Kr + Ko + Ks
Kr = 0⋅20 + 0⋅30 + 0⋅20 + 1⋅30 + 0⋅80 + 0⋅20 = 30 eFt Ko = 1⋅50 + 1⋅60 + 4⋅40 + 3⋅50 = 420 eFt Ks = 1⋅100 + 1⋅40 = 140 eFt
K = 30 + 420 + 140 = 590 eFt
Optimális –e a megoldás? Az ellenőrzés potenciálok módszerével történik:
4
a kötött elemek száma ≥ sor + oszlop - 1 6
≥ 3 +
4
-1
(Ha nem állna fel az egyenlet, akkor be kellene vinni egy szabad elemet 0 értékű szállítással) kötött elemnél: cij = uj + vj szabad elemnél: cij = cij – (uj + vj)
Vj Ui U1 -1 U2 -1 U3 0
V1 0 0 0 0 20
V2 1 4 0 30 7
V3 1 0 0 20 1 30
V4 1 0 80 0 20 2
kötött elemnél: ui + vj = cij u1 + v4 = 0 u2 + v2 = 0 u2 + v3 = 0 u 2 + v4 = 0 u 3 + v1 = 0 u 3 + v3 = 1 szabad elemnél: δij = cij - (ui+vj) δ11 = 0 – (0-1) = 1 δ12 = 4 – (1-1) = 4 δ13 = 0 – (1-1) = 0 δ14 = 0 – (1-1) = 0 kötöttt elem δ21 = 0 – (0-1) = 1 δ22 = 0 – (1-1) = 0 kötött elem δ23 = 0 – (1-1) = 0 kötött elem δ24 = 0 – (1-1) = 0 kötött elem δ31 = 0 – (0+0) = 0 kötött elem δ32 = 7 – (0+1) = 6 δ33 = 1 – (0+1) = 0 kötött elem δ34 = 2 – (0+1) = 1 Ha van negatív elem a táblában, a szállítást javítani kell hurok módszerrel: a javítás úgy történik, hogy ahol negatív volt, azt kötött elemmé kell tenni, tehát egy kört kell az új taggal és a régi kötött elemekkel alkotni, majd a kör legkisebb értékű szállításával a kör összes szállítását rendre csökkenteni, majd növelni. De mivel nem kaptam negatív elemet az ellenőrzés során, így a szállítási feladat megoldása optimális, vagyis a legkisebb költséggel való szállítást kaptam eredményül.
5
Eredmény gazdasági értékelése Optimális szállítás megvalósulása esetén a költség 590 ezer Ft. Az optimális szállítások − Budapest → Miskolc
80.000 db törölköző
− Szolnok → Szeged
30.000 db törölköző
− Szolnok → Nyíregyháza
20.000 db törölköző
− Szolnok → Miskolc
20.000 db törölköző
− Szeged → Szolnok
20.000 db törölköző
− Szeged → Nyíregyháza
30.000 db törölköző
6
