Az utazási ügynök problémája (1
3. Adja meg a definíció: egy részhalmaza, útvonalak, az alsó határ értékét az útvonalat, így állandó, csökkentett mátrix köitséghátrány „mert nem használták a” legjobb útvonal.
4. Abban az esetben, ha az utazási ügynök problémáját az ágakkal kötött módszerrel oldjuk meg, az előző döntési lépéshez való visszatérés, visszaadjuk a fát?
5. Miért nevezik a fióktelep és a határmódot "hatékony keresési módnak"?
A közlekedési probléma (TOR) a lineáris programozási problémák egy speciális osztályához tartozik. A TZ matematikai modelljének sajátossága, valamint az LP problémák megoldásának általános módszerei lehetővé teszik a speciális számítási módszerek alkalmazását. A TZ nyilatkozata a Hitchcockhoz tartozik.
A probléma leírása. Egyetlen termék m termelési pontjai (raktárak) vannak, az i. A termék fogyasztásának n pontja van, a bj értéke - a fogyasztás mennyisége (benyújtott termékigénylés) a j-os fogyasztási ponton.
A termelési pontok bizonyos közlekedési díjakkal rendelkező utak hálózatához kapcsolódnak a fogyasztási pontokhoz. A termék egy egységének (rakomány) szállítása az i-edik termelési ponttól a j-os fogyasztási pontig: cij. Szükséges megtalálni az optimális szállítási tervet olyan termékek számára, amelyekben a szállítási költségek minimálisak, a termékeket teljesen kivitték a termelési pontokból, és a termékek iránti kereslet teljes mértékben elégedett.
A probléma matematikai modellje. Változóként a közlekedési mátrix elemeit választjuk ki:
Legyen - az i-edik termelési helyről exportált termékek egységeinek száma a j-os fogyasztási pontig.
Az első m korlátok meghatározzák a feltételt: az egész termék az i. Például (1. ábra), az első előállítási ponttól az a1 termelési térfogattal, a termék az 1.-n. Fogyasztási pontra szállítható. A szállítás volumene ismeretlen, és a következőket tartalmazza: - az első gyártási ponttól az első melegítési pontig szállított tételek száma; - az első termelési helytől a második fogyasztási pontig szállított termékek egységeinek száma; - az első gyártási ponttól az n-edik fogyasztási pontig szállított termékek egységeinek száma. Az összes szállított tétel összegének meg kell egyeznie az a1 értékkel. .
A következő n korlátozások meghatározzák a feltételt: minden j-os fogyasztási pontot az összes szükséges termékkel szállítanak.
A probléma mérete :. A közlekedési probléma egy speciális eset a lineáris programozási probléma, amelyben minden korlát az egyenlőség típusától függ. Az LP probléma megoldásának általános esetével ellentétben a szállítási probléma optimális megoldása mindig fennáll
Az oldat módszerei. Lineáris programozási probléma esetén a simplex megoldható a simplex módszerrel []. Kialakultak a közlekedési probléma megoldásának speciális (hatékonyabb) módszerei is: az általánosított magyar módszer []; az északnyugati sarok módszere, a támogatási terv megállapításának minimális eleme; az optimális terv megtalálásának lehetőségei [].
Nyitott és zárt közlekedési feladatok. Kétféle TK létezik: nyitott TK és zárt TK.
A szállítási problémát zártnak hívják, ha az egyensúlyi feltétel teljesül. a teljes termelési mennyiség megegyezik a fogyasztás teljes mennyiségével:
Megjegyezzük, hogy a matematikai modell () egy zárt közlekedési feladatot határoz meg.
Nyitott TK két változatban adható meg.
Az első lehetőség. A teljes termelési volumen kevesebb, mint a teljes fogyasztás:
A közlekedési probléma megoldása érdekében a nyílt szállítási feladatot egy zártra kell csökkenteni, amelyhez egy m + 1-es fiktív gyártási pontot vezetünk be,
A második lehetőség. A teljes termelési volumen több, mint a teljes fogyasztás:
A zárt típusra vonatkozó információkért adja meg az n + 1 fiktív fogyasztási pontot a fogyasztás mennyiségével:
A szállítási feladat állapotát szállítótáblázatban kell megadni (1. táblázat):
A szállítási tervmátrix elemeit (sejteket, táblacellákat) alapszinten hívják. ha eltérnek a nullától; az asztal nulla celláit szabadon hívják.
A szállítási terv megengedett. ha megfelel az egyensúlyi feltételeknek (): minden ajánlat teljesül, minden készlet kimerült.
Egy megvalósítható terv referencia terv. ha ebben nem több, mint r = m + n-1 alapszállítás nullától különbözik, és a többi kocsi nulla. Ha a nem nulla forgalom kevesebb, mint r = m + n-1. akkor egy ilyen tervet degenerált támogatási tervnek neveznek.
Az optimális szállítási terv az a terv, amely a megengedett szállítási tervek közül a legalacsonyabb költséggel jár.
Az északnyugati sarok módja.
A szállítási feladat feltétele a szállítási táblázat (1. táblázat).
1. lépés: Ellenőrizze, hogy teljesül-e az egyensúlyi feltétel (). Ha az egyensúlyi feltétel nem teljesül, vagyis a feladat nyitva van, akkor zártnak minősül.
2. lépés: Hozzon létre egy táblázatot szállítási tervet (táblázat. 2), melyek tele vannak csak a termelés mennyisége és a fogyasztás volumene. Ezután a bal felső (északnyugati) saroktól kezdve töltse fel a szállítási táblázatot. Töltés közben a vonal mentén haladjon jobbra és lefelé az oszlopon. A sejt található NE-metszéspontja az első sor és az első oszlop, feltöltött mák-maximum SZOLGÁLATI lehetséges darabszám megengedett og korlátozását a kereslet-kínálat :.
Engedje meg például, hogy az első gyártó (szállító) ajánlata teljesen kimerült. Az első sor többi cellája tele van nullával, és az első oszlop mentén mozog. A sejteket kereszteződésénél található az első oszlop és a második sor kerül helyezése-maximális lehetséges darabszám megengedett korlátok a kereslet és kínálat :. Ha például, akkor. Az első fogyasztó igénye kielégítő. A visszamaradó sejteket az első oszlopot feltöltöttük nullákkal és mozognak a második sorban a jobb. Kitöltésével a sejt a kereszteződésekben a második sorban és a második oszlop, továbblép a következő töltési Thr-Tey második sor sejtek, vagy a második oszlopban. A folyamat mindaddig folytatódik, amíg a javaslatok kimerülnek, és a kereslet teljesen kielégül. Az utolsó töltött sejt az n-edik oszlopban és az m-es sorban van.
1. példa A referencia terv meghatározása az északnyugati sarok módszerével a Táblázatban megadott szállítási feladathoz. 3
a termelés fogyasztásának volumene
Az első lépésben ellenőrzik a mérlegfeltételeket. A teljes termelési mennyiség: 200 + 40 + 110 = 350 hagyományos egység; a fogyasztás teljes térfogata egyenlő: 120 + 50 + 190 + 110 = 470. Ezért a T3 nyitott. Csökkentése zárt típusúvá, szükség van egy negyedik termelési pont bevezetésére, amelynek termelési térfogata: = 470-350 = 120 hagyományos egység. Mivel a termelési pont fiktív, a termékek szállításának költsége ettől a ponttól a fogyasztási pontokig nulla (4. táblázat).
a termelés fogyasztásának volumene
A második lépésben hozzon létre egy üres táblázatot a szállítási tervről, és töltse fel (5. táblázat).
a termelés fogyasztásának volumene
Az első cellát helyezzük: (5. táblázat). Az első fogyasztó alkalmazása teljes mértékben elégedett, az első oszlop fennmaradó cellái tele vannak nullákkal. A termelés többi része az első bekezdésben: 200-120 = 80 hagyományos rakományegység.
Ezután haladjon az első sor mentén jobbra, és töltse ki a cellát (1,2) :. A második fogyasztó alkalmazása teljes mértékben elégedett, a második oszlop többi cellája nulla. A termelés többi része az első bekezdésben megegyezik: 80-50 = 30 hagyományos rakományegység.
A nagy mennyiség miatt ez az anyag több oldalra kerül:
1 2 3 4 5 6 7
Iratkozzon fel hírlevelünkre:
Érdekes hírek
Fontos témák
Szolgáltatás Vélemények Pandia.ru