Verificați pentru optimitatea planului de suport nondegenerat prin metoda potențialelor (al doilea punct al algoritmului)

Verificați pentru optimitatea planului de suport nondegenerat prin metoda potențialelor (al doilea punct al algoritmului)


1 Analizăm fiecare potențial furnizor un potențial și fiecare potențial potențial.





Apoi, fiecare celula ocupata va corespunde ecuatiei

Deoarece toate celulele ocupate trebuie să fie m + n - 1, adică este mai mică decât numărul de potențiale, apoi pentru a găsi că este necesar să se rezolve un sistem de ecuații m + n - 1 cu m + n necunoscute. Sistemul este dependent de liniaritate și pentru a găsi o soluție particulară, unul dintre potențiale trebuie să aibă o valoare numerică arbitrară, atunci potențialele rămase sunt determinate în mod unic. De exemplu, potențialul rândurilor și coloanelor pentru planul de susținere inițial găsit în ultimul exemplu prin metoda elementului minim se determină din soluția sistemului







Sistemul este dependent de liniaritate, pentru a găsi una dintre soluțiile particulare pe care le oferim unuia dintre potențiale o valoare numerică, de exemplu, atunci



  1. Pentru a studia planul de optimitate pentru fiecare celulă liberă, presupunem estimări din formula

;

a) dacă toate estimările sunt pozitive, atunci planul de suport găsit este optim și unic;

b) dacă, împreună cu estimările pozitive, există estimări zero, planul de sprijin găsit este optim, dar nu unic;

c) dacă estimarea a cel puțin unei celule libere este negativă, atunci planul de suport nu este optim, poate fi îmbunătățit prin încărcarea acestei celule. Dacă există mai multe astfel de celule, atunci cea mai promițătoare pentru încărcare este celula cu cea mai mică estimare. De exemplu, avem estimări pentru celule. Aici cel mai mare potențial (promițător pentru descărcare) este celula.

Tranziția la cel mai slab plan de sprijin (al treilea punct al algoritmului)


Îmbunătățirea planului de transport din cauza celule download cu o evaluare negativă la acest lucru pentru celula gratuit cele mai promițătoare construit un ciclu închis cu noduri celule încărcate. Vârfurile ale ciclului ecusoane condiționat atribuite: celule libere - plus următoarele, în sensul acelor de ceasornic sau în sens antiorar, ocupat celula - un minus următor - din nou, în plus, etc. Alimentării în ciclul celulelor cu „negativ“, cel mai mic volum de noduri de marfă selectate și este mutat de celulele acestui ciclu se adaugă la alimentarea în vârfurile „pozitive“ și se scade din sursa de la vârfuri „negative“, rezultând într-un echilibru ciclu nu este deranjat.
Ciclul de conversie

În general, ciclul de recalculare este o linie închisă închisă formată din legături care se intersectează în unghi drept. Fiecare legătură conectează două celule dintr-un rând (coloană). Ciclul include o celulă liberă, restul celulelor din ciclu sunt ocupate. Există întotdeauna un număr par de celule într-un ciclu. Pentru o celulă liberă, puteți construi întotdeauna un singur ciclu.

Dacă se formează un ciclu din celulele ocupate, planul de transport nu este o referință. Ciclul este construit numai pentru o celulă liberă.

De exemplu, găsim estimări ale celulelor libere ale planului inițial de susținere construit în ultimul exemplu prin metoda elementului minim. Folosind potențialele de rânduri și coloane de mai sus, se calculează estimările celulelor libere:

De la estimare, planul găsit nu este optim. Poate fi îmbunătățită prin încărcarea acestei celule.

Să compunem ciclul de recalculare în raport cu celula () (vezi Tabelul 19).







Articole similare

Trimiteți-le prietenilor: