Problema clasica de transport

Master ML + IMFP

Tema 3 - curs

Problema clasica de transport

O problema de transport consta in determinarea unui plan de transport pentru un produs omogen, de la anumite centre producatoare, in scopul satisfacerii cerintelor unor consumatori si minimizarii cheltuielilor de transport.

Se considera ca exista un numar D_i de furnizori (depozite) care poseda produsul respectiv in cantitati egale cu d_i, i = 1, 2, . , m si n centre beneficiare B_j ,

j = 1, 2, . , n, care solicita acest produs in cantitatile necesare, bj.

Se presupune ca o unitate de produs transportata de la depozitul D_i la beneficiarul B_j costa c_ij unitati banesti.

Se cere sa se determine planul optim de transport, adica ce cantitati x_ij de produs trebuie sa fie transportate de la fiecare depozit la fiecare beneficiar, astfel incat sa fie respectate conditiile:

sa fie satisfacuta in cea mai mare masura cererea de produse in centrele beneficiare;

cheltuielile totale de transport sa fie minime.

Datele initiale ale unei probleme de transport se prezinta intr-un tabel de forma tabelului 1

Tabelul 1

Modelul matematic al acestei probleme de transport este urmatorul:

(1)

Modelul (1) este modelul unei probleme de programare liniara, la care se mai poate adauga conditia de nenegativitate pentru d_i, b_j, c_ij,

Definitia 1. Problema de transport se numeste echilibrata daca:

(2)

In caz contrar, problema se numeste neechilibrata.

Orice problema de transport neechilibrata se poate transforma intr-o problema echilibrata astfel:

a.    daca , se introduce un beneficiar fictiv B_n+1, pentru care necesarul va fi: , iar costurile unitare de transport vor fi egale cu zero;

b.    daca , se introduce un depozit fictiv D_m+1, pentru care disponibilul va fi: iar costurile unitare de transport vor fi egale cu zero;

Definitia 2. O problema de transport are forma standard daca

Modelul matematic al unei probleme de transport in forma standard este:

(3)

Rezolvarea unei probleme de transport se face numai pentru forma standard, adica numai pentru problema de transport echilibrata.

Definitia 3. O matrice ale carei componente satisfac sistemul de restrictii si conditiile de nenegativitate ale modelului matematic (3) se numeste solutie admisibila a problemei de transport.

Daca, in plus, matricea X minimizeaza functia obiectiv a modelului matematic (3) ea se numeste solutie optima sau plan de transport optim pentru problema data.

Se demonstreaza ca o problema de transport echilibrata admite cel putin o solutie admisibila si ca rangul matricei C a coeficientilor necunoscutelor din sistemul de restrictii al modelului matematic este: rang C = m + n -1. Acest lucru inseamna ca exista m + n -1 vectori coloana liniari independenti ce vor forma o baza a spatiului R^m+n+1. Prin urmare va existe cel putin o solutie admisibila de baza, cu cel mult m + n -1 componente pozitive. Daca solutia admisibila de baza are exact m + n -1 componente pozitive, ea se numeste solutie admisibila de baza nedegenerata. Daca solutia admisibila de baza are mai putin de m + n -1 componente pozitive, ea se numeste solutie admisibila de baza degenerata.

Definitia 4. O problema de transport se numeste degenerata daca ea admite o solutie admisibila de baza degenerata.

Desi sunt indeplinite toate conditiile care permit aplicarea algoritmului simplex pentru rezolvarea problemei de transport, exista un algoritm de rezolvare specific, mult mai usor de aplicat. Acest algoritm presupune doua etape:

Etapa I. Determinarea unei solutii admisibile de baza.

Etapa a II-a. Imbunatatirea solutiei de baza in pasi succesivi, pana la aflarea solutiei optime.

Metode pentru determinarea unei solutii admisibile de baza

Deoarece fiecare variabila corespunde unei rute (este cantitatea de produs transportata pe aceasta ruta), iar fiecare ruta corespunde unei perechi furnizor-beneficiar, vom identifica fiecare variabila x_ij cu ruta (i, j).

A gasi o solutie de baza nedegenerata inseamna a gasi cel mult m + n - 1 rute, din cele m n posibile, pe care sa transportam cantitatea disponibila. Rutele vor fi organizate intr-un tabel asemanator celui in care se prezinta datele problemei de transport, fiecarei rute asociindu-se o casuta (i, j):

In cazul problemei de transport, gasirea unei solutii initiale de baza nu este dificila, existand o multime de metode in acest scop, care incearca nu numai aflarea acesteia, ci chiar gasirea uneia cat mai buna.

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

Se considera problema de transport echilibrata si se construieste tabelul cu datele problemei: cantitatile disponibile di, cantitatile necesare bj, costurile unitare de transport c_ij, cu i = 1, 2, . , m si j = 1, 2, . , n.

Procedeul porneste cu determinarea necunoscutei aflate in casuta din coltul staga-sus (coltul Nord-Vest) a tabelului ca valoare minima intre cantitatile disponibila si necesara corespunzatoare: x₁₁ = min (d₁, b₁).

Daca min (d₁, b₁) = d₁, se anuleaza valorile necunoscutelor din toate celelalte casute ale primei linii a tabelului (cantitatile nule se marcheaza cu o linie orizontala) si se recalculeaza cantitatea necesara beneficiarului B₁: .

Daca min (d₁, b₁) = b₁, se anuleaza valorile necunoscutelor din toate celelalte casute ale primei coloane a tabelului si se recalculeaza cantitatea ramasa disponibila in depozitul D₁:.

Se renunta la linia/coloana pentru care se completeaza cantitatea disponibila/necesara.

Se continua procedeul cu alocarea unei valori casutei situate in coltul Nord-Vest a tabelului ramas, tinand cont de cantitatile disponibile si necesare recalculate, pana la alocarea totala a cantitatilor d_i si b_j.

La epuizarea elementelor de comparat, se obtine o solutie admisibila de baza.

Exemplu Se da problema de transport cu datele initiale prezentate in tabelul 2.

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

Tabelul 2

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 x₃₄ valoarea: . Cantitatea ramasa disponibila in depozitul D₃ este: . A mai ramas de stabilit valoarea unei singure necunoscute: . Solutia obtinuta este prezentata in tabelul 3.

Tabelul 3

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 D₁.

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

Solutia obtinuta este prezentata in tabelul 4.

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 (d₂, b₃) = 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 B₁ 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 x32 valoarea:

Tabelul 4

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 xi1 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₁.

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.

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.

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

Metoda potentialelor pentru determinarea solutiei optime

Fie problema de transport in forma standard:

(4)

Se scrie duala acestei probleme astfel: fiecarei restrictii de tipul (2a) i se asociaza o variabila si fiecarei restrictii de tipul (2b) variabila . Cum fiecare variabila apare o singura data in (2a) si o singura data in (2b), duala va avea forma:

(5)

Duala unei probleme de transport sugereaza ca se incearca transportarea unor cantitati de bunuri astfei incat diferenta dintre pretul unitar u_i la sursa (depozit) si pretul unitar la destinatie v_j sa nu depaseasca costul unitar de transport c_ij , intre punctul de plecare si cel de sosire.

Notand , respectiv componentele solutiilor optime ale celor doua probleme, din teoria ecarturilor complementare, rezulta:

(6)

Pornind de la o solutie de baza nedegenerata, unde exista m + n - 1 componente x_ij > 0, solutia va fi optima daca:

(7)

pentru toate rutele (i, j) pentru care x_ij > 0.

Relatiile (7) reprezinta un sistem de m + n - 1 ecuatii cu m + n necunoscute u_i si v_j, care se rezolva dand uneia dintre necunoscute o valoare arbitrara, de exemplu u₁ = 0.

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 u_i si fiecarei coloane cate o variabila v_j. 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 x_ij > 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 x_ij si se determina valoarea minima, notata , 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 "-". 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.

Exemplu Sa se afle costul minim de transport pentru problema ale carei date initiale sunt date in tabelul 2.

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

Tabelul 5

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

Se ataseaza fiecarei linii a tabelului 1.49 o variabila u_i si fiecarei coloane o variabila v_j si se scrie sistemul u_i + v_j = ci_j, 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 xij aflate in casutele notate"+" si se scade din cantitatile xij 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. 1.49), care nu apartin circuitului considerat. Noua solutie admisibila de baza este prezentata in tabelul 6.

Tabelul 6

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.

Exemplu Se da problema de transport prezentata in tabelul urmator :

Pentru aflarea unei solutii admisibile de baza se aplica metoda elementului minim in tabel. Solutia obtinuta (tab.7) 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 7

Se aduna la fiecare cantitate disponibila d_i o valoare , considerata foarte mica. Pentru echilibrarea problemei adunam la cantitatea necesara unui beneficiar (de exemplu beneficiarului B₄).

Problema reformulata este prezentata in tabelul 8.

Tabelul 8

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

Tabelul 9

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 10 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 10