Alte metode de optimizare a transporturilor

Alte metode de optimizare a transporturilor

O cantitate de marfa se gaseste depozitata în trei baze de desfacere A_i(i=1,2,3) în cantitatile : 110 t, 130 t, 170 t.Aceasta cantitate trebuie transportata la cinci centre B_j(j=1,2,3,4,5) care necesita urmatoarele cantitati: 50 t, 60 t, 80 t, 100 t, 120 t.

Cheltuielile de transport de la fiecare baza la fiecare centru sunt date de matricea :

C_ij=

Metoda coltului de N-V

Avem : min(110,50)=50 ; x₁₁=50  130-80=50

A₁-b₁=110-50=50;x₂₁=x₃₁=0  min(50,100);x₂₅=0

x₁₂=min(60,60);x₁₃=x₁₄=x₁₅=0  100-50=50

si x₂₂=x₃₂=0  min(50,170)=50;170-50=120

min(80,130)=80 ; x₃₃=0  min(120,140)=120

Solutia initiala posibila este:

f_ij=50x₁₁+20x₁₂+30x₁₃+70x₁₄+100x₁₅+70x₂₁+50x₂₂+40x₂₃+60x₂₄+

+80x₂₅+60x₃₁+30x₃₂+70x₃₃+50x₃₄+110x₃₅

Spre deosebire de procedeul nord - est , acest procedeu tine seama în determinarea solutiei initiale de costurile unitare c_ij .

Pentru exemplificare folosim datele din aplicatia anterioara pentru a₁ si b_j si construim urmatorul tabel :

Din matricea cu costuri unitare C_ij se alege în fiecare linie elementul cel mai mic , în casuta corespunzatoare se repartizeaza cea mai mica cantitate dintre cantitatile disponibile la expeditor si acele necesare la destinatar .

In linia întâi , elementul cel mai mic este c₁₂ =20 se va destina pentru . Rezulta ca x₂₂=x₃₂=0 si

a₁=a₁ - b₂=110 - 60 =50. Deci , în A₁ au mai ramas 50 t. Se cauta în linia intâi imediat superioara lui c₁₂ . Aceasta valoare este data de c₁₃ =30 . Se va destina pentru x₁₃ urmatoarea valoare minima x₁₃=min(a₁,b₃)=min(50,80)=50 si x₁₁=x₁₄=x₁₅=0 , deoarece A₁ a distribuit întreaga cantitate disponibila .

Centrul B₂ este satisfacut complet si nu va mai fi luat în considerare în repartitiile urmatoare . In continuare se procedeaza în acelasi mod cu celelalte linii ramase .

In a doua linie , elementul cel mai mic este c₂₃=40 . Se va destina pentru x₂₃=min(a₂,b₂')=min(130,30)=30 . Rezulta ca x₃₃=0 si a₂=a₂-b₂' =

=130 - 30=100 . Deoarece în A₂ au mai ramas t se cauta pe aceasta linie valoarea lui c_2j imediat superioara lui c₂₃ . Intrucât pe B₂ nu-l mai luam în considerare , aceasta valoare (100) este data de c₂₄=60 . Vom avea x₂₄=min(a₂',b₄)=min(100,100)=100 .

Rezulta ca x₂₅=0 . Se trece la a treia linie si se procedeaza în acelasi mod . Se considera c₃₁=60 , x₃₁=min(50,170)=50 si x₃₅=min(120,120)=120 .

Rezultatul acestei repartitii se poate urmari în tabelul urmator :

Valoarea lui f_ij=26100 , numarul necunoscutelor x_ij>0 este m+n - 1=7, deci s-a obtinut o solutie nedegenerata.

Asemanator cu procedeul elementului minim pe linie este si procedeul elementului minim pe coloana. Acest procedeu determina valorile necunoscutelor x_ij tinând seama de valorile elementelor c_ij aflate în fiecare coloana, alegând din ele pe cele cu min c_ij si destinându-le în casuta corespunzatoare pentru x_ij , valoarea min(a₁,b_j) .

Rezultatul aplicarii acestui preocedeu este dat în tabelul urmator :

Valoarea lui f_ij^c=25600 si s-a obtinut tot o solutie nedegenerata deoarece numarul necunoscutelor x_ij0 este m+n - 1=6 .

Procedeul elementului minim pe tabel

Metoda consta an repartizarea cantitatilor necesare beneficiarilor dupa criteriul elementului c_ij minim pe tabel .

Folosind acelasi tabel din problema precedenta (minimum pe linie) cu costurile unitare, se va proceda în felul urmator :

Se alege elementul c_ij dat de c₁₂=20. Se atribuie pentru x₁₂=min(110,60)60 . Cum B₂ a luat întreaga cantitate necesara , coloana respectiva nu se mai utilizeaza în repartitiile urmatoare .

In aceasta situatie rezulta ca x₂₂=x₃₂=0. In locul lui a₁ apare a₁=110 - 60

Elementul costului superior lui c₁₂ este c₁₃=30 . Vom avea acum x₁₃=min(a₁, b₃)=min(50, 80)=50 . De aici rezulta ca x₁₄=x₁₅=0 . Elementul superior lui c₁₃ este c₂₃=40 si de aici rezulta ca x₂₃=min(130,30)=30 si x₃₃=0, deoarece B₃ a fost satisfacut .

x₃₄=min(100, 100)=100 si x₂₄=0

Pentru costul c₃₄=60 se ia x₃₁=min(170, 50)=50 . Rezulta ca x₁₁=x₂₁=0 _, x₂₅=100 si x₃₅=20 .

In urma acestor operatii solutia problemelor de transport arata astfel :

Se obtine f_ij=22100

Cele patru procedee folosite au dus la solutii de baza nedenegerate .

Comparând rezultatele obtinute pentru functia obiectiv prin aplicarea procedeelor prezentate se constata :

Prin procedeul coltului NORD-EST se realizeaza un cost de f_ij=25600

Prin procedeul minimului pe linie , un cost de f_ij=26100

Prin procedeul minimului pe coloana un cost de f_ij=25600

Prin procedeul minimului pe tabel un cost de f_ij=22100