Problema de transport

Problema de transport

1. Metode pentru gasirea unei solutii admisibile de baza

Pentru determinarea unei solutii admisibile de baza pentru o problema de transport echilibrata, se folosesc, in principal, urmatoarele metode:

metoda coltului Nord-Vest;

metoda elementului minim pe linie;

metoda elementului minim pe coloana;

metoda elementului minim in tabel;

metoda diferentelor comparate.

In principiu, toate aceste metode urmeaza o schema comuna:

a.    se alege o ruta initiala, dupa o anumita regula;

b.   se transporta pe aceasta ruta maximul posibil, egal cu minimul dintre cantitatea care mai este disponibila la furnizorul corespunzator acestei rute si cantitatea care mai este necesara beneficiarului corespunzator rutei, in momentul alegerii rutei respective;

c.    dupa folosirea unei rute, fie se epuizeaza disponibilul furnizorului, fie se asigura intregul necesar beneficiarului, fie ambele si anumite rute nu mai pot fi folosite; ele se numesc rute blocate si se evidentiaza prin inscrierea unei liniute in casuta corespunzatoare.

d.   se alege urmatoarea ruta si se reia algoritmul de la pasul (b) pana cand nu mai ramane nici o ruta nefolosita sau neblocata.

Metoda coltului Nord-Vest

Exemplul 1. Se da problema de transport cu datele initiale prezentate in tabelul 1.

Se cere sa se afle o solutia admisibila de baza prin metoda coltului Nord-Vest.

Tabelul 1.

Problema este echilibrata:.

Se da necunoscutei x₁₁ (situata in coltul din stanga-sus) valoarea:

x₁₁ = min (80, 120) = 80, restul necunoscutelor coloanei 1 fiind nule (cantitatea necesara beneficiarului B₁ a fost asigurata).

In depozitul D₁ a mai ramas o cantitate disponibila egala cu:

Se elimina coloana 1 din tabel. Se da necunoscutei x₁₂ (prima din coltul stanga-sus) valoarea:, restul necunoscutelor din prima linie a tabelului fiind nule (s-a epuizat cantitatea disponibila in depozitul D₁). Se recalculeaza cantitatea necesara beneficiarului B₂:

Se elimina si linia 1 din tabel. Se da necunoscutei x₂₂ (situata in coltul N-V al tabelului ramas) valoarea:, toate celelalte necunoscute din a doua coloana a tabelului fiind nule (s-a epuizat si cantitatea necesara beneficiarului B₂). Cantitatea ramasa disponibila in depozitul D₂ este:

Se elimina si coloana 2 din tabel. Se da necunoscutei x₂₃ (situata in coltul N-V al tabelului ramas) valoarea:, ultima necunoscuta din coloana a treia fiind nula (s-a epuizat si cantitatea necesara beneficiarului B₃). Cantitatea ramasa disponibila in depozitul D₂ este: . Se elimina si coloana 3 din tabel.

Se da necunoscutei x₂₄ valoarea: , anulandu-se si ultima necunoscuta de pe linia 2.

Cantitatatea necasara beneficiarului B₄ se recalculeaza:

Se elimina si linia 2 din tabel. Se da necunoscutei x34 valoarea: . Cantitatea ramasa disponibila in depozitul D₃ este: . A mai ramas de stabilit valoarea unei singure necunoscute: . Solutia obtinuta este prezentata in tabelul 2.

Tabelul 2

S-a obtinut o solutie de baza admisibila cu sapte componente nenule:

x₁₁ = 80; x₁₂ = 40; x₂₂ = 32; x₂₃ = 75; x₂₄ = 3; x₃₄ = 25; x₃₅ = 45; solutia este nedegenerata deoarece are m + n -1 = 3 + 5 - 1 = 7 componente nenule.

Valoarea functiei obiectiv pentru aceasta solutie admisibila de baza este:

u.m.

Observatie. Metoda coltului Nord-Vest opereaza numai cu valorile d_i si b_j, fara a lua in consideratie costurile unitare c_ij. Este evident ca un cost total minim al transportului se va obtine utilizand rutele cu costuri unitare mici. Pe aceasta observatie se bazeaza metodele urmatoare de determinare a unei solutii admisibile de baza pentru problema de transport.

2. Metoda elementului minim pe linie

Metoda elementului minim pe linie (costului minim pe linie) consta in alegerea, pentru fiecare dintre liniile tabelului initial al problemei de transport, a celui mai mic cost unitar.

Se da variabilei corespunzatoare acestei pozitii valoarea cea mai mica intre cantitatea disponibila si cea necesara de pe linia si coloana aferente.

Se incepe cu prima linie de sus a tabelului: se alege si apoi

Se recalculeaza cantitatile disponibile si necesare: si

Daca a fost alocata intreaga cantitate disponibila pe prima linie, se suprima linia 1 sau coloana k careia ii corespunde diferenta nula (variabilele de pe linia sau coloana suprimata devin egale cu zero), apoi se trece la a doua linie si pe rand la urmatoarele, reluandu-se procedeul.

Daca nu a fost alocata intreaga cantiate disponibila pe prima linie, se cauta urmatorul element minim din aceasta linie, dand variabilei corespunzatoare valoarea egala cu diferenta de cantitate, pana la epuizarea intregii cantitati disponibile in depozitul D1.

Exemplul 2. Pentru problema de transport data in tabelul 1, se aplica metoda elementului minim pe linie pentru aflarea unei solutii admisibile de baza. Solutia obtinuta este prezentata in tabelul 3.

Pe prima linie a tabelului initial costul unitar cel mai mic este c₁₅ = 60. Se da variabilei x₁₅ valoarea: .Beneficiarului B₅ i s-a satisfacut cererea, restul necunoscutelor de pe coloana 5 sunt nule, iar coloana 5 se suprima. Se recalculeaza cantitatea ramasa in depozitul D₁:

In noul tabel, se continua procedeul alegand, tot de pe linia 1, costul unitar minim pentru casutele ramase (deoarece cantitatea aflata in depozitul D₁ nu a fost epuizata). Acest cost unitar minim este . Se da variabilei x₁₄ valoarea: se anuleaza variabilele de pe coloana 4 (cererea beneficiarului B₄ a fost satisfacuta), se elimina si coloana 4 din tabel si se recalculeaza cantitatea ramasa in depozitul D₁:

.

Aceata cantitate este valoarea ce se va da variabilei x₁₁, aflata pe pozitia corespunzatoare celui mai mic cost unitar de pe linia 1, in tabelul ramas. Se anuleaza restul variabilelor de pe linia 1 (a fost epuizata cantitatea disponibila in depozitul D₁), iar linia 1 se elimina. Se recalculeaza cantitatea necesara beneficiarului B₁: .

Se trece la linia a doua. Costul unitar cel mai mic este c₂₃ = 70. Se da variabilei x₂₃ valoarea: x₂₃ = min (d2, b3) = min (110, 75) = 75. Cererea beneficiarului B₃ a fost satisfacuta, restul variabilelor de pe coloana 3 sunt nule. Se recalculeaza cantitatea ramasa in depozitul D₂: . Se cauta urmatorul cost unitar minim de pe linia 2, care este c₂₁ = 100. Se da variabilei x₂₁ valoarea:. Variabila x₃₁ = 0 (cererea beneficiarului B1 a fost satisfacuta), coloana 1 se elimina. Se recalculeaza cantitatea disponibila in depozitul D₂:

Variabila x₂₂  = 2 si intreaga cantitate disponibila in depozitul D₂ a fost distribuita.

Se recalculeaza cantitatea necesara beneficiarului B₂: . Se elimina linia 2 din tabel si se trece la linia 3 dand singurei variabile ramase, variabila x₃₂ valoarea:

Tabelul 3

S-a obtinut o solutie admisibila de baza nedegenerata, valoarea functiei obiectiv fiind:

u.m.

3. Metoda elementului minim pe coloana

Se procedeaza in mod similar metodei anterioare, cu deosebirea ca se lucreaza pe coloanele tabelului initial al problemei de transport. Se incepe cu prima coloana din stanga. Se cauta si se da variabilei x_i1 valoarea:

Se recalculeaza cantitatile disponibile si necesare de pe linia i si coloana 1: si

Daca a fost alocata intreaga cantitate disponibila pe prima coloana, se suprima coloana 1 sau linia i careia ii corespunde diferenta nula (variabilele de pe linia sau coloana suprimata devin egale cu zero), apoi se trece la a doua coloana si pe rand la urmatoarele, reluandu-se procedeul.

Daca nu a fost alocata intreaga cantiate disponibila pe prima coloana, se cauta urmatorul element minim din aceasta coloana, dand variabilei corespunzatoare valoarea egala cu diferenta de cantitate, pana la epuizarea intregii cantitati necesare beneficiarului B₁.

Exemplul 3. Pentru problema de transport data in tabelul 1, se aplica metoda elementului minim pe coloana pentru aflarea unei solutii admisibile de baza.

Se analizeaza prima coloana a tabelului (cea din stanga) si se alege costul unitar minim, c₃₁ = 60.

, restul variabilelor fiind nule.

Se recalculeaza cantitatea necesara beneficiarului B₁: . Se aloca aceasta valoare variabilei pozitionate in casuta cu urmatorul cost unitar minim de pe coloana 1: . Variabila x₂₁ = 0 (a fost satisfacut necesarul beneficiarului B₁) si coloana 1 se elimina din tabel. Se recalculeaza cantitatea disponibila in depozitul D₁:

Se trece la a doua coloana a tabelului redus. Se cauta elementul minim, care este c₁₂ = 120. Variabilei corespunzatoare, x₁₂, i se da valoarea:

, restul variabilelor de pe coloana a doua fiind nule (a fost satisfacut necesarul beneficiarului B₂).

Se recalculeaza cantitatea ramasa in depozitul D₁:

Se trece la a treia coloana procedandu-se analog. Solutia obtinuta este prezentata in tabelul 4.

Tabelul 4

Pentru aceasta solutie admisibila de baza, functia obiectiv are valoarea:

u.m.

4. Metoda elementului minim din tabel

Metoda consta in alegerea celui mai mic cost unitar din tabelul initial al problemei de transport, variabilei corespunzatoare fiindu-i data o valoare egala cu cea mai mica dintre cantitatile disponibila si necesara de pe linia si coloana acestui cost unitar minim.

Se alege si se ia

Se recalculeaza cantitatile disponibile si necesare si se suprima din tabel linia sau coloana pe care aceste cantitati au fost completate.

In tabelul redus, se cauta din nou cel mai mic cost unitar, variabilei respective dandu-i-se o valoare egala cu cea mai mica dintre cantitatile disponibila si necesara ramase.

Se repeta procedeul pana cand toate cererile sunt satisfacute.

Exemplul 4. Pentru problema de transport data in tabelul 1, se aplica metoda elementului minim din tabel pentru aflarea unei solutii admisibile de baza. Solutia obtinuta este prezentata in tabelul 5.

Tabelul 5

Valoarea functiei obiectiv este:

u.m.

5. Metoda diferentelor comparate

Metoda consta in introducerea unor penalitati in cazul in care nu se foloseste casuta cu cel mai mic cost unitar cij. Aceste penalitati reprezinta diferenta dintre cel mai mic element (cost unitar) dintr-o linie sau coloana si urmatorul element ca valoare, din linia sau coloana respectiva. Pentru diferenta cea mai mare, de pe o linie sau de pe o coloana, se aloca variabilei corespunzatoare celui mai mic cost unitar, din acea linie sau coloana, o valoare egala cu valoarea minima dintre cantitatile disponibila si necesara. Se suprima linia sau coloana pe care nu se mai poate interveni si se repeta procedeul in tabelul redus.

Exemplul 5. Pentru problema de transport data in tabelul 1, se aplica metoda diferentelor comparate pentru aflarea unei solutii admisibile de baza.

Tabelul initial al problemei de transport se completeaza cu o linie in partea de jos si cu o coloana in dreapta, in care se vor calcula penalitatile (tabelul 6).

Diferenta cea mai mare intre costul unitar minim si urmatorul cost unitar, ca valoare, este corespunzatoare coloanei 3 si este egala cu 60 (c₃₃ - c₂₃ = 60).

In coloana 3 se cauta elementul minim, care este c₂₃ si se da variabilei x₂₃ valoarea:. Restul variabilelor de pe coloana 3 sunt nule, iar coloana 3 se suprima.

Cantitatea disponibila in depozitul D₂ se recalculeaza:

Se repeta procedeul in tabelul redus (tab.7), format prin eliminarea coloanei B₃. Diferenta cea mai mare intre costul unitar minim si urmatorul cost unitar, ca valoare, este corespunzatoare atat liniei 3 cat si coloanei 4.

Se alege una dintre ele, de exemplu, cea corespunzatoare liniei 3.

Cel mai mic cost unitar de pe linia 3 este c₃₁. Se da variabilei x₃₁ valoarea:

Toate celelalte variabile de pe linia 3 sunt egale cu zero, deoarece a fost epuizata intreaga cantitate disponibila in depozitul D₃.

Se elimina linia 3 si se recalculeaza necesarul beneficiarului B₁:

Se repeta procedeul, obtinandu-se, succesiv, tabelele 8, 9, 10.

Solutia finala este prezentata in tabelul 11.

Tabelul 6

Tabelul 7

Tabelul 8

Tabelul 9 Tabelul 10

Tabelul 11

Valoarea functiei obiectiv pentru aceasta solutie admisibila de baza este:

u.m.

Comparand valorile functiei obiectiv, pentru cele cinci metode utilizate, se constata ca valoarea minima este obtinuta in cazul aplicarii metodei diferentelor comparate, iar valoarea maxima in cazul metodei elementului minim pe linie.

In general, nu se poate concluziona care dintre metode este recomandabil a fi folosita, alegerea fiind influentata de datele initiale ale problemei de utilizat.

2. Metoda potentialelor pentru determinarea solutiei optime

Algoritmul de rezolvare a unei probleme de transport prin metoda potentialelor, pornind de la o solutie admisibila de baza nedegenerata, presupune urmatoarele etape:

Etapa 1. Se asociaza fiecarei linii a tabelului unei probleme de transport cate o variabila ui si fiecarei coloane cate o variabila vj. Pentru casutele care corespund variabilelor de baza se construieste sistemul: si se rezolva.

Etapa 2 Se calculeaza marimile.

a.    Daca , atunci solutia admisibila de baza este solutie optima a problemei date.

b.   Daca, solutia initiala nu este solutie optima si trebuie imbunatatita. Se trece la etapa 3.

Etapa 3. Se determina. Pornind din casuta (l, k) se construieste un circuit (un lant inchis) format din casute ale tabelului, care trece numai prin pozitii (i, j) carora le corespunde o cantitate xij > 0, prin treceri alternative pe linii si respectiv coloane, astfel incat sa se asigure intoarcerea in casuta (l, k) din care s-a pornit.

Se noteaza casutele din circuit, alternativ cu "+" si "-", intr-un sens oarecare (de exemplu invers trigonometric), incepand cu casuta (l, k).

Etapa 4. Pentru casutele notate "-"se examineaza cantitatile xij si se determina valoarea minima, notata , a acestor valori. Se aduna valoarea la cantitatile xij aflate in casutele notate"+" si se scade din cantitatile xij aflate in casutele notate "-". Se obtine o noua solutie admisibila de baza deoarece in casuta (l, k) a aparut o componenta pozitiva , iar una dintre componentele solutiei initiale a devenit nula. Se reia algoritmul de la etapa 1, pentru a verifica daca noua solutie este optima sau nu.

Exemplul 6 Sa se afle costul minim de transport pentru problema ale carei date initiale sunt date in tabelul 1.

Consideram solutia admisibila de baza obtinuta prin metoda elementului minim din tabel in exemplul 4. Solutia este prezentata in tabelul 12.

Tabelul 12

Etapa 1. Se verifica daca solutia admisibila de baza este solutie optima.

Se ataseaza fiecarei linii a tabelului 12 o variabila u_i si fiecarei coloane o variabila v_j si se scrie sistemul u_i + v_j = c_ij, considerand numai casutele (i, j) pentru care variabilele x_ij > 0:

Se rezolva sistemul pentru u₁ = 0. Rezulta:

Etapa 2. Se calculeaza:. Aceste valori se inscriu intr-o matrice, cu m linii si n coloane.

Observatie. Evident, pentru pozitiile (i, j) corespunzatoare componentelor nenule ale solutiei admisibile de baza,.

Matricea este urmatoarea:

Deoarece exista o valoare si anume, solutia admisibila de start nu este solutie optima si trebuie imbunatatita.

Etapa 3. Avand o singura valoare, ea este si valoarea maxima a diferentelorstrict pozitive. Vom forma un circuit incepand din casuta corespunzatoare acestei valori maxime, adica din casuta (2, 1), deplasandu-ne in sus pe coloana 1, pana la casuta (1, 1), apoi la dreapta pe linia 1 pana la casuta (1, 2), in jos pe coloana 2 pana la casuta (2, 2) si la stanga pe linia 2, inchizand circuitul in aceeasi casuta din care am pornit, casuta (2, 1).

Inscriem in casutele circuitului valorile componentelor solutiei initiale si notam colturile acestuia alternativ cu "+" si "-", in sens invers trigonometric, incepand cu casuta de pornire, casuta (2, 1).

Etapa 4. Pentru casutele notate "-"se examineaza cantitatile x_ij si se determina valoarea minima,, a acestor valori. Se aduna valoarea la cantitatile x_ij aflate in casutele notate"+" si se scade din cantitatile x_ij aflate in casutele notate "-".

si

S-a obtinut o noua solutie, noi valori avand componentele corespunzatoare casutelor circuitului. Raman nemodificate componentele corespunzatoare casutelor din tabelul initial (tab. 12), care nu apartin circuitului considerat.

Noua solutie admisibila de baza este prezentata in tabelul 13.

Tabelul 13

Se verifica daca aceasta noua solutie este solutie optima sau nu, reluand algoritmul de la etapa 1.

Se rezolva sistemul pentru u₁ = 0. Rezulta:

Matricea este urmatoarea:

Deoarece, solutia obtinuta este solutie optima pentru problema data.

Asadar:

Valoarea minima a costului total de transport este:

u.m.

Observatii

Daca pentru solutia optima exista, pentru (i, j) indici in afara bazei, se poate obtine o noua solutie optima plecand de la casuta (i, j) si aplicand etapele 3 si 4 ale algoritmului. In acest caz, problema are solutie optima multipla.

Daca in matricea Δ exista mai multe diferente pozitive, de valoare egala, vom alege, pentru a incepe circuitul, acea ruta careia ii corespunde in tabelul initial costul unitar cel mai mic.

Exista probleme practice ce conduc la un model al problemei de transport in care se cere maximizarea functiei obiectiv. Aflarea unei solutii admisibile de baza prin metodele: elementului minim pe linie, elementului minim pe coloana si elementului minim din tabel devin metodele elementului maxim: pe linie, pe coloana sau in tabel si se aplica pornind de la valoarea cea mai mare a coeficientului c_ij de pe linie, coloana sau tabel. Metoda coltului Nord-Vest se aplica fara nici o modificare.

Calculul diferentelor se face dupa relatia:

iar conditia de optim este aceeasi:

Exista situatii in care anumite rute intre furnizori si consumatori nu pot fi folosite, cel putin temporar. Rezolvarea acestor probleme se face cu un model de transport obisnuit, in care rutelor interzise li se asociaza costuri de transport foarte mari in raport cu costul rutelor utilizabile. Prin aceste costuri foarte mari, algoritmul de rezolvare este fortat sa ocoleasca rutele interzise.

In rezolvarea unei probleme de transport, poate apare o solutie admisibila de baza degenerata, caz in care nu se poate aplica metoda potentialelor pentru aflarea solutiei optime. Evitarea acestui lucru se face aplicand metoda perturbarii, ce consta in reformularea problemei, punand:

Cu aceste date se determina solutia initiala de baza ale carei componente depind de. Se pune conditia ca si se vor obtine componente bazice nule, care se trateaza ca si cand ar fi pozitive.

Exemplul 7. Se da problema de transport prezentata in tabelul 14:

Tabelul 14

Pentru aflarea unei solutii admisibile de baza se aplica metoda elementului minim in tabel. Solutia obtinuta (tab. 15) are 5 componente nenule, deci este o solutie degenerata, deoarece o solutie nedegenerata ar fi trebuit sa aiba m + n - 1 = 3 + 4 - 1 = 6 componente nenule.

Se aplica metoda perturbarii:

Tabelul 15

Se aduna la fiecare cantitate disponibila di o valoare , considerata foarte mica. Pentru echilibrarea problemei adunam la cantitatea necesara unui beneficiar (de exemplu beneficiarului B4). Problema reformulata este prezentata in tabelul 16.

Tabelul 16

Solutia initiala de baza se afla aplicand tot metoda elementului minim din tabel si este prezentata in tabelul 17.

Tabelul 17

Se da lui valoarea zero si se obtine o solutie cu componenta x₁₄ = 0, pe care o tratam ca si cand ar fi pozitiva. Solutia de baza obtinuta este prezentata in tabelul 18 si este considerata o solutie nedegenerata.

Se poate aplica, in aceste conditii, metoda potentialelor pentru a gasi solutia optima a problemei de transport data.

Tabelul 18