Ellenőrizze, hogy a nem támogatott támogatási sík optimális-e a potenciál módszerével (az algoritmus második pontja)
Ellenőrizze, hogy a nem támogatott támogatási sík optimális-e a potenciál módszerével (az algoritmus második pontja)
1 Minden potenciális szállítónak potenciális potenciált adunk, és mindegyik potenciális potenciált.
Ezután minden elfoglalt cella megfelel az egyenletnek
Mivel minden elfoglalt sejtnek m + n-1, azaz. egy kisebb, mint a potenciálszám, akkor meg kell találnunk egy olyan m + n - 1 egyenletrendszer megoldását, amely m + n ismeretlen. A rendszer lineárisan függ és egy adott megoldás megtalálása esetén az egyik potenciálnak tetszőleges numerikus értéket kell adnia, majd a fennmaradó potenciálokat egyedileg határozzák meg. Például a minimális elemes módszerrel az utolsó példában található kezdeti támogatási terv sorainak és oszlopainak potenciálját a rendszer megoldásából határozzuk meg
A rendszer lineárisan függ, hogy megtaláljuk az egyik konkrét megoldást, amellyel numerikus értéket adunk egy potenciálnak, például
Az optimális terv minden egyes szabad cellára történő becsléséhez a képlet szerinti becsléseket feltételezzük
;
a) ha minden becslés pozitív, akkor a támogatási terv optimális és egyedi;
b) ha pozitív becslések mellett nulla becslések vannak, akkor a támogatási terv optimális, de nem egyedi;
c) ha legalább egy szabad sejt értékelése negatív, akkor a támogatási terv nem optimális, akkor javítható ez a cella betöltése. Ha több ilyen sejt van, akkor a legígéretesebb a terhelés a legalacsonyabb becsléssel rendelkező sejt. Például becslésünk van a sejtek számára. Itt a legnagyobb potenciál (letöltés ígéretes) a sejt.
Átmenet a legszegényebb támogatási tervhez (az algoritmus harmadik pontja)
Javítani szállítási tervet miatt ingyenesen letölthető sejtet egy negatív értékelés erre a legígéretesebb szabad cella épített zárt ciklusban csúcsot a feltöltött sejteket. A tetejét a ciklus feltételesen hozzárendelt kitűzőit: szabad cella -, valamint a következő, az óramutató járásával megegyező vagy azzal ellentétes irányban, a forgalmas sejt - mínusz következő - ismét, plusz, stb Az ellátás a sejtekben ciklus „negatív” a legkisebb mennyiségű rakomány kiválasztott csúcsok, és mozgatja a sejtek ebben a ciklusban adunk a kínálat a „pozitív” csúcsok és levonjuk az ellátási „negatív” csúcsok, ami egy ciklus egyensúly nem zavarja.
Átváltási ciklus
Általánosságban elmondható, hogy az újratervezési ciklus egy derékszögben keresztező kapcsolatokból álló zárt, szakadt vonal. Minden egyes link egy sor (oszlop) két celláját köti össze. A ciklus tartalmaz egy szabad sejtet, a ciklus fennmaradó sejtjei elfoglalva vannak. Mindig van egy páros számú sejt egy ciklusban. Egy szabad cellához mindig egyetlen ciklust készíthet.
Ha a megszállt cellákból ciklus alakul ki, a szállítási terv nem hivatkozás. A ciklus csak egy szabad cellára épül.
Például a minimális elem módszerrel az utolsó példában elkészített eredeti támogatási terv szabad celláinak becsléseit találjuk. A fenti sorok és oszlopok potenciáljának felhasználásával kiszámítjuk a szabad sejtek becslését:
A becslés miatt a terv nem optimális. Ezt a cellát be lehet tölteni.
Tegyük fel az újratervezési ciklust a cellahoz képest () (lásd a 19. táblázatot).