Probleme de transport

Probleme de transport

Problemele de transport sunt o forma particulara a problemelor de programare liniara pentru care metoda simplex poate fi adoptata, conditiilor particulare, avand ca rezultat un procedeu de rezolvare in principiu identic celui utilizat in cazul general. Primele rezultate au fost obtinute de Hitchcock, Kantorovici si Koopmans si ulterior de Dantzig. In practica o asemenea problema poate fi intalnita de exemplu sub forma urmatoare: un anumit produs se afla in cantitatile in punctele numite si surse. El trebuie transportat in punctele numite destinatii in cantitatile urmarind minimizarea cheltuielilor de transport cunoscand preturile unitare de transport de la sursa catre destinatia

Formularea matematica a problemei este:

unde am notat prin cantitatile transportate de la sursa catre destinatia

Relatiile (8.1) sunt impuse de faptul ca totalul transportat de la fiecare sursa sa nu depaseasca cantitatea existenta, conditiile (8.2) impun satisfacerea cererii iar (8.5.) apar naturale in contextul concret al problemei.

Prin transformari elementare acest tip de problema poate fi adus la forma echilibrata

Pentru rezolvarea problemelor de transport ca si in cazul problemelor generale de programare liniara, algoritmul de rezolvare are doua etape:

a)    aflarea unei solutii initiale realizabile de baza;

b)    imbunatatirea solutiei initiale pana la obtinerea solutiei optim.

Vom da in continuare doua procedee de obtinere a unei solutii initiale realizabile de baza.

1) Metoda diagonalei (metoda coltului nord-vest).

Cantitatile disponibile si cererile corespunzatoare se dispun pe laturile unui tabel iar celulelele din interiorul tabelului se rezerva pentru necunoscutele ( ) care trebuie determinate.

Componentele bazice ale solutiei se determina pe rand incepand cu si anume:

Se alege si vor fi considerate nebazice (deci vor fi egali cu zero) toate variabilele de pe aceiasi linie (sau coloana) cu x₁₁ conform urmatoarelor situatii:

a)    daca atunci iar , ;

b)    daca atunci si , ;

c)    daca atunci si toate celelalte componente de pe linia 1 si coloana 1 fiind considerate nebazice, deci, nule.

Concomitent se modifica si valorile lui si inlocuindu-se cu cu si cu

In pasul urmator procedeul se repeta pentru celulele ramase necompletate si se termina dupa pasi in fiecare pas completand o linie (situatia a) sau o coloana (situatia b) sau o linie si o coloana (situatia c).

De regula componentele nebazice nu se trec in tabel ci se hasureaza casuta respectiva.

Exemplu 8.1 . Interiorul tabelului contine preturile unitare de transport.

Pasul 1:     , am hasurat celulele cores-punzatoare variabilelor nebazice (pentru , ). Se recalculeaza care devine .

Pasul 2:     si hasuram celulele cores-punzatoare variabilelor nebazice (pentru , ). Se recalculeaza care devine

Pasul 3:     si hasuram celula corespun-zatoare lui care e nul. Recalculam care devine .

Pasul 4:     , hasuram celula lui care e nul si recalculam

Pasul 5:     si este evident ca

Tinand seama de costurile trecute in colturile de sus ale celulelor avem pentru valoarea f = 3

Deci am obtinut o solutie de baza nedegenerata

, , , , , , .

2. Metoda costurilor minime

Pentru determinarea solutiei de baza se iau in considerare costurile care ne indica ordinea de alegere a componentelor in fiecare pas.

In primul pas se determina componenta pentru care si se ia cu cele trei alternative ca la metoda diagonalei. Se repeta procedeul urmarind costurile minime pentru celulele necompletate.

Exemplu 8.2. Reluam datele din exemplul 8.1.

Pasul 1:     Pe prima linie a tabloului cel mai mic cost este deci luam , se hasureaza restul de celule din coloana lui si se recalculeaza care devine

Pasul 2:     Cautam deci x₂₁ = min = a₂ = 15 si hasuram celulele liniei doi. Recalculam , care devine

Pasul 3:     , deci , hasu-ram coloana lui si devine

Pasul 4:     , luam si devine Este evident acum ca si .

Avem pentru

, , , , , , .

Metoda costurile minime da in general o solutie initiala de baza mai buna decat metoda diagonalei, realizand o valoare a cheltuielilor de transport mai mica. Acest lucru e util deoarece numarul iteratiilor necesare pentru atingerea optimului va fi mai mic.

Pentru determinarea solutiei optime a unei probleme de transport se utilizeaza algoritmul bazat pe adoptarea metodei simplex la conditiile particulare ale problemei de transport.