Determinarea planului optim

12.4. Determinarea planului optim

Prin luarea în considerare metodele de construire a programului de sprijin inițial poate fi obținut degenerate sau a unui program de sprijin non-degenerate. Construit plan de problemă de transport ca o problemă de programare liniară poate fi adusă la optim folosind metoda simplex. Cu toate acestea, datorită caracterului voluminos tabelelor simplex conținând mil necunoscut, și o cantitate mare de calcul metode de lucru mai simple, folosite pentru a obține planul optim. Metoda cea mai frecvent utilizate de potentiale (metoda de distribuție modificată) și metoda chiriilor diferențiate.

Metoda potențialelor. Principiul general de determinare a planului optim a problemei de transport a acestei metode este similară cu cea de rezolvare a unei metode liniare simplex problemă de programare, și anume: în primul rând, găsiți sprijinul planului problemă de transport, și apoi îmbunătățește treptat, până la planul optim.

Teorema12.2 (criteriul optimalitate). Pentru ca un plan valabil pentru transportul în problema transportului a fost optim dacă și numai dacă există astfel de numere și. că

Numărul și numit potențiale puncte de plecare și de destinație, respectiv.

Această teoremă ne permite să construim un algoritm pentru găsirea de soluții ale problemei de transport. El este după cum urmează. Să una din metodele discutate mai sus program de sprijin găsit. Pentru acest plan, în care m + n - potentiale 1, celulele de bază pot fi determinate și, astfel încât condiția (12.4). Deoarece sistemul (12.4) cuprinde m + n - 1 ecuații și m + n necunoscute, una dintre ele poate fi setat în mod arbitrar (de exemplu, egală cu zero). După aceea m + n - 1 ecuații (12.4) și potențialele determinate de valorile rămase sunt calculate pentru fiecare dintre celule disponibile. Dacă observați că. planul optim. În cazul în care cel puțin o celulă goală. planul nu este optim și poate fi îmbunătățită prin transferarea ciclului corespunzătoare acestei celule libere.

Masa ciclu mediu sarcina de transport, numit o linie întreruptă, ale căror vârfuri sunt situate în celulele ocupate din tabel și unități - de-a lungul rânduri și coloane, în care, la fiecare vârf al unui ciclu are loc exact două legături, dintre care unul este în linie, iar cealaltă - în coloana. În cazul în care linia întreruptă formând o buclă intersectează punctul de auto-intersecție nu sunt noduri.

Planul Procesul de îmbunătățire continuă atâta timp cât sunt îndeplinite condițiile (12,5).

Exemplu. Pe trei baze introduse de marfă omogenă, care este necesară pentru a transporta patru destinație. Tarife de trafic, stocurile și cerințele sunt enumerate în Tabelul 12.3. Planul de transport, astfel încât valoarea totală a acestora a fost minimă.