Megfogalmazása lineáris programozási szállítási probléma
Elektronikus könyvtár „Computer” beállítása közlekedési problémát a lineáris programozás
Szimplex módszer megoldására lineáris programozási feladat egyetemes és alkalmazni, hogy megoldja az ilyen problémákat. Azonban vannak olyan speciális típusú lineáris programozási feladatok, amelyek miatt bizonyos funkciók szerkezetük, hogy az oldat egyszerűbb módszerek. Ezek közé tartoznak különösen az úgynevezett közlekedési problémát.
Klasszikus közlekedési problémát a lineáris programozás a következő.
Vannak m kiindulópontok: A1. A2. Am. felhalmozott nagy tartalékok a homogén termék (a rakomány) összegének rendre a1. a2. am egység. Ezen kívül vannak olyan n rendeltetési: B1. B2. Bn. kérelmezők rendre b1. b2. milliárd darabot értékesítettek.
Feltételezzük, hogy az összeg az összes ajánlatra összegével egyenlő az összes állomány:
Ismert költség CIJ áruszállítás egységek egyes kiindulási pontja Ai egyes rendeltetési helyekre Bj. Táblázat (mátrix) értékek Sij kocsi készlet:
Ez szükséges ahhoz, hogy a szállítási tervet, amelyben az összes kérés lenne teljesíteni, és hogy a teljes költség az összes forgalom minimális volt.
Ebben a készítményben a probléma hatékonysági mutató az a költség, a szállítási terv; így a feladat pontosabban nazyvayuttransportnoy feladata költség kritériumoknak.
Adjunk ennek a problémának a matematikai megfogalmazása. Let xij - mennyiségű rakomány küldött az i -edik indulási pontja Ai a j-edik rendeltetési Vj (i = 1 m; J = 1 n). Nem negatív változók x11. x12. XMN (amelyek száma nyilvánvalóan egyenlő m xn) meg kell felelniük az alábbi feltételeknek:
1. A teljes összeget küldött áruk egyes kiindulási ponton minden úti cél egyenlőnek kell lennie az állomány az áruk ezt a bekezdést. Ez ad nekünk a feltételeket m-egyenletek:
ahol a jel a kettős összeg azt jelzi, hogy az összegzési vége minden kombinációját indexek (i = 1 m; J = 1 n), azaz összes kombinációjára kiindulópontok a célpontok.
A funkció (3,31) lineáris megszorítások - egyenlőségek (3,29), (3,30) szintén lineáris. Előttünk - egy tipikus lineáris programozási probléma egyenlőség korlátok (OZLP).
Mint minden más lineáris programozási feladat, hogy meg lehetne oldani a szimplex módszer, de ez a probléma néhány szolgáltatás, amely lehetővé teszi, hogy oldja meg könnyebben. Az ok chtovse együtthatók a változók az egyenletekben (3,29) és a (3.30) egyenlő egy. Továbbá a szerkezet készlet közötti kapcsolatok szempontjából. Ez könnyű, hogy megbizonyosodjon arról, hogy nem minden az m + n egyenletei a probléma független. Valóban, összerakva az összes egyenletet (3,29) és az összes egyenlet (3.30), meg kell, hogy ugyanazt a dolgot, állapot (3,28). Így, a feltételeket (2) és (3) össze vannak kötve egy lineáris függés, és ezekből egyenletek valójában csak m + n -1, ahelyett, m + n lineárisan független. Ennélfogva, a rangot az egyenleteket (3,29) és a (3.30) egyenlő
és ezért lehetséges, hogy megoldja ezeket a egyenletek az m + n -1 alapváltozók, ezeket expresszáló szempontjából a fennmaradó szabad.
Számolja meg a szabad változók. Ez egyenlő:
Tudjuk, hogy a probléma a lineáris programozási optimális megoldás születik az egyik csúcsot SDT, ahol legalább (m -1) (n -1) xij értéket nullának kell lennie.
Egyetértünk a terminológiát. Xij értéket az egységek számát rakomány küldött Ai pont Bj hívjuk forgalmat.
Bármilyen értékkészlet (xij) (i = 1 m; J = 1 n) előhívja a forgalom. vagy csak terv.
Terv (xij) nevezzük elfogadható. ha teljesíti a feltételeket (3,29) (3,30) (az úgynevezett „mérleg feltételek”): minden alkalmazás teljesülnek, a készletek kimerültek.
Elfogadható tervet fogja hívni a referencia. ha vannak zéró legfeljebb r = m + n -1 alapvető szállítási xij. és a fennmaradó szállítás nulla.
Terv (xij) nevezzük optimális. ha ő, az összes támogatható tervek, így a legalacsonyabb költségek valamennyi szállításra.
Most viszont, hogy a bemutató egy közlekedési problémamegoldó módszerek (TOR). Ezek a módszerek nem igényelnek a manipuláció a szimplex asztalok, és csökkenteni egy egyszerű művelet közvetlenül az asztalra, ahol egy bizonyos sorrendben tartalmazza az összes feltételeit TOR. Fogjuk hívni egy ilyen közlekedési asztal asztal.
A közlekedési tábla felvett
- indulási és rendeltetési
- rendelkezésre álló készletek kiindulási pontok,
- benyújtott kérelmeket célpontok,
- szállítási költségek minden egyes származási minden hely.
A szállítás költségét, akkor kerül a jobb felső sarokban az egyes sejtek, így, hogy a nagyon cella elkészítéséhez a terv, hogy a közlekedési xij.
A mintát közlekedési tábla megadott tabl.3.8.
Az egyszerűség kedvéért mi kell érteni az indulás - szoftverek úticél - H A jobb felső sarokban az egyes sejtek viselik az áruszállítás egységek (terhelés) szoftver CD Ai Bj. A jobb oldali oszlopban vannak elhelyezve árukészletek mindegyik az alsó sorban - benyújtott kérelmeket minden H TK mennyiségű tartalék megegyezik a kérelmek összege; az összértéke rögzíti ezt az összeget a jobb alsó cella a táblázat.
Fent azt mutatták, hogy az egyenletek a rank-TK restrikciós rendszer r = m + n -1, ahol m - a sorok számát és n - számú szállítási táblázat oszlopainak. Ennélfogva, az egyes alátámasztó sík, beleértve az optimális, akkor különbözik nullától több mint m + n -1 forgalmat.
Cell (sejt) a táblázat, amely azt fogja rögzíteni ezeket a nullától eltérő szállítás, akkor az úgynevezett alap. és a többi (üres) ingyen.
Így a határozat lejött a következő TK. Megtalálni azokat értékeinek pozitív forgalomban, kerüljenek le az alap szállítási Táblázatcellák megfelelnek a következő feltételeknek:
- az összeg a forgalom minden sorban az asztal meg kell egyeznie az állomány a szoftver;
- az összeg a forgalom minden oszlopban egyenlőnek kell lennie az alkalmazás a PN;
- A teljes költség a szállítás - a minimum.
A jövőben az összes lépést, hogy megoldást találjanak a TOR fog korlátozódni a közlekedés az asztal átalakítás 3.8.
Leírásakor ezek az átalakulások célszerű használni a számozását táblázat sejtek (például számozás sakktábla sejtek). Cell (Ai, Bj), vagy, a rövid, a sejt (i, j) lesz az úgynevezett sejt, állva az i-edik sor és j-edik oszlopa a táblázat a közlekedés. Például, a bal felső cella lesz jelöljük (1,1) álló alatta (2.1), stb
3.5.2. Megtalálása támogatási program
közlekedési megoldást a problémára, valamint bármely lineáris programozási feladat, első lépésként találni az összehasonlító oldatban, vagy, ahogy mi mondjuk támogatási programot. Ezzel szemben az általános esetben OZLP tetszőleges korlátok és célfüggvény, az oldatot TK mindig fennáll.
Az építőiparban a támogatási programot.
Használjuk az úgynevezett „módon az észak-nyugati sarkában.” Magyarázza meg a legegyszerűbb módja az lenne, egy konkrét példát.
1. példa feltételek TK adott szállítási táblázat (lásd. Tabl.3.9)