Meghatározása az optimális terv

12.4. Meghatározzuk az optimális terv

Figyelembe véve a módszereket építésének kezdeti támogatási program lehet beszerezni degenerált vagy nem-degenerált támogatási program. Beépített közlekedési probléma terv, mint egy lineáris programozási feladat lehet hozni az optimális felhasználásával a szimplex módszer. Azonban, mivel a bulkiness simplex tartalmazó táblák mn ismeretlen, és a nagy mennyiségű számítási munka egyszerűbb előállítási módszerekkel az optimális terv. A leggyakrabban használt módszer a potenciálok (módosított terjesztési módszer) és a módszer a differenciál bérleti.

A módszer a potenciálok. Az általános elv meghatározása az optimális terv a közlekedési problémát ez a módszer hasonló a megoldása lineáris programozási feladat szimplex módszer, nevezetesen: először, meg a támogatást a közlekedési probléma terv, majd fokozatosan javul, amíg az optimális tervet.

Teorema12.2 (optimalitás kritérium). Ahhoz, hogy egy érvényes terv közlekedés közlekedési problémát optimális volt akkor és csak akkor, ha létezik ilyen számok és. hogy

A szám és az úgynevezett potenciális indulási és érkezési sorrendben.

Ez a tétel lehetővé teszi számunkra, hogy egy olyan algoritmust, hogy megoldásokat találjunk a közlekedési problémát. Ő a következő. Legyen az egyik fent felsorolt ​​módszerek talált támogatást programot. Ez a terv, amelyben m + n - 1, a kiindulási sejtek meghatározható potenciálokat és így, hogy a (12.4). Mivel a rendszer (12.4) tartalmaz, m + n - 1 egyenletek és m + n ismeretlennel, egyikük lehet önkényesen (például zérus). Ezután az m + n - 1 egyenletek (12.4), és a potenciálok által meghatározott fennmaradó értékeket az egyes rendelkezésre álló sejtek. Ha úgy találja, hogy. az optimális terv. Ha legalább egy üres cellát. A terv nem optimális, és javítható át a ciklus ennek megfelelő sejtmentes.

Ciklus asztal szállítási feladat környezetben, úgynevezett szaggatott vonal, amelynek csúcsai találhatók a megszállt sejtekben az asztal és az egységek -, valamint a sorok és oszlopok, ahol minden csúcsa egy ciklus következik be pontosan két link, melyek közül az egyik a sorban, és a többi - az oszlop. Ha a szaggatott vonal hurok képzése metszi a lényeg az önálló kereszteződés nem csúcsot.

Folyamat fejlesztési tervet mindaddig folytatódik, amíg a feltételek teljesülnek (12,5).

Példa. A három alap lépett homogén rakomány, amely szükséges ahhoz, hogy a négy helyre. Vám- forgalom, a készletek és a követelmények táblázatban vannak felsorolva 12.3. Szállítás tervet annak érdekében, hogy azok összértéke minimális volt.