Dacă una dintre condiții este îndeplinită pentru sarcina de transport
atunci modelul problemei se numește deschis. Pentru ca această sarcină să aibă o soluție, este necesar să o aducem la un tip închis, adică astfel încât egalitatea să fie satisfăcută.
Aceasta se face după cum urmează: dacă. apoi adăugați un consumator fictiv cu cerere (în tabelul de distribuție va exista o coloană suplimentară) dacă. apoi adăugați un furnizor fictiv cu o propunere (o linie suplimentară apare în tabelul de distribuție). În ambele cazuri, se presupune că tarifele sunt zero. Mai mult, problema este rezolvată în aceeași ordine care a fost considerată mai devreme.
Să scriem algoritmul pentru rezolvarea problemei de transport:
1) Verificați tipul de model TK.
2) Construirea planului inițial de sprijin (prin orice metodă).
3) Verificarea planului de degenerare.
4) Verificarea planului de optimitate prin metoda potențialului:
a) găsirea potențialelor din sistem
(pentru toate celulele umplut);
b) verificarea celei de a doua condiții de optimitate
(pentru toate celulele goale).
5) Trecerea la cel mai sărac plan de sprijin (dacă este necesar).
Un exemplu. În depozite există stocuri de același tip de bunuri în cantitatea a (35, 40, 40, 50), care trebuie livrate consumatorilor. Nevoile consumatorilor sunt date de vectorul b (31; 52; 17; 20). Matricea costurilor pentru livrarea unei unități de mărfuri de la furnizorul i către consumatorul j:
Faceți un plan de transport cu costuri minime de transport.
Soluția. Definiți tipul de model de problemă de transport. Capacitatea totală a furnizorilor: 35 + 40 + 40 + 50 = 165 (unități de mărfuri); Cererea totală a consumatorilor: 31 + 52 + 17 + 20 = 120 (unități de mărfuri).
pentru că . atunci avem un model tip deschis.
Introducem un consumator fictiv a cărui cerere este
165 -120 = 45 (unități de mărfuri).
Tarife 0.T. obținem un model tip închis, m = 4 este numărul de furnizori, n = 5 este numărul de consumatori. Poziția matricei de probleme. Construim planul inițial de susținere prin metoda elementului minim (cel mai mic cost).
Numărul de celule umplut din tabelul de distribuție 8 este egal cu rangul matricei problemă r = 8, prin urmare, planul de susținere este nondegenerat.
Costurile de transport corespunzătoare planului de sprijin:
Să studiem programul de asistență pentru optimalitate folosind metoda potențialului.
Completăm tabelul 1 cu o coloană și un rând de potențiale și. Vom găsi sistemul potențial utilizând prima condiție de optimitate: pentru celulele umplută cu livrări.
Din sistemul înregistrat găsim :. . . . . . . . .
Să verificăm îndeplinirea celei de a doua condiții de optimitate. Pentru toate celulele goale, trebuie îndeplinită următoarea inegalitate :.
(1; 1) 0 + 1 - 5 = -4 0;
(1; 2) 0 + 2 - 4 = -2 0;
(1; 5) 0-4-0 = -4 0;
(2; 3) 1 + 3 - 5 = -1 0;
(2; 4) 1 + 1 - 8 = -6 0;
(2; 5) 1 - 4 - 0 = -4 0;
(3; 1) 4 + 1 - 6 = -1 0;
(3; 2) 4 + 2 - 8 = -2 0;
(3, 3) 4 + 3 - 7 = 0 0;
(3; 4) 4 + 1 - 10 = -5 0;
(4; 1) 4 + 1 - 5 = 0 0;
(4; 4) 4 + 1 - 2 = 30.
pentru că în rândul celulelor libere există acelea în care nu este satisfăcută a doua condiție de optimitate, atunci planul nu este optim.
Vom face tranziția spre planul de susținere care nu este mai rău. Cele mai promițătoare pentru umplerea celulei (4; 4), deoarece aceasta corespunde celei mai mari estimări pozitive
Să găsim ciclul de redistribuire a încărcăturii pentru această celulă.
Celulei selectate i se atribuie semnul "+", apoi se alternează semnele. Printre vârfurile cu semnul "-" alegem cea mai mică livrare.
Redistribuim livrările pe un ciclu, astfel trecem la noul plan de bază.
Costurile de transport corespunzătoare planului de sprijin:
Să studiem programul de sprijin pentru optimitate. Să găsim valorile potențialelor folosind prima condiție de optimitate. Pentru celulele umplute cu consumabile.
Să verificăm îndeplinirea celei de a doua condiții de optimitate. Pentru toate celulele goale, trebuie îndeplinită următoarea inegalitate :.
Scriem celulele în care este încălcată condiția:
(1; 2) 0 + 5 - 4 = 1 0.
Vom face tranziția spre planul de susținere care nu este mai rău. Cele mai promițătoare pentru umplerea celulei (1; 2), deoarece Aceasta corespunde unui scor pozitiv de 1. Să găsim ciclul de redistribuire a încărcăturii pentru această celulă.
Numărul de celule umplut din tabelul de distribuție 8 este egal cu rangul matricei problemei r = 8, prin urmare, planul de susținere (tabelul 3) este nondegenerat.
Costurile de transport corespunzătoare planului de sprijin:
Să studiem programul de sprijin pentru optimitate.
Să găsim valorile potențialelor folosind prima condiție de optimitate. Pentru celulele umplute cu consumabile.
Să verificăm îndeplinirea celei de a doua condiții de optimitate. Pentru toate celulele goale, trebuie îndeplinită următoarea inegalitate :.
A doua condiție de optimitate este valabilă pentru toate celulele libere, de aceea planul este optim.
Cele mai mici costuri de transport.
O :; Planul optim de distribuție este prezentat în tabelul 3.
Lucrări de muncă independentă.
Faceți un plan de transport cu costuri minime de transport.
Articole similare
Trimiteți-le prietenilor: