Modelul Matematic al Problemei de Transport Echilibrate

Problema de transport echilibrata este o problema de programare liniara in care se cauta valorile variabilelor xij, i=1,m,j=1,n ce satisfac relatiile:

si minimizeaza forma liniara:

unde ai, bj, cij si xij, i=1,m, j=1,n au semnificatiile specificate anterior si verifica urmatoarele conditii:

Conditia (6) este numita conditia de echilibru. Modelul (1)+(2)+(3)+(5)+(6) este echivalentul formei standard din programarea liniara.

Propr.1 O problema de transport echilibrata este un caz particular de problema de programare liniara care are cel putin o solutie admisibila.

Intr-adevar, daca luam atunci se observa ca:

Pe de alta parte, din (1) + (2) rezulta ca , ( ) si . Dar min , altfel nu s-ar verifica restrictiile. In consecinta, orice problema de transport de tipul (1)+…+(6) admite solutie optima finita.

Propr.2 rangA=m+n-1

Matricea A, a sistemului (1)+(2) are m+n linii si m*n coloane, fiecare din acestea avind doua elemente egale cu 1 si restul egale cu 0.

Rang A min(m+n,m*n) = m+n < m*n, m N{0,1,2}, n N{0,1,2}.

Din relatia (6) rezulta ca intre ecuatiile sistemului (1)+(2) mai ai exista o relatie, deci cele m+n restrictii ale problemei nu sunt independente rangA m+n-1 o solutie admisibila de baza are cel mult m+n-1 componente pozitive. In ipoteza ca problema de transport este nedegenerata, o solutie admisibila de baza va avea m+n-1=rangA componente strict pozitive.

Din formula matematica a problemei de transport problema se poate rezolva prin metoda simplex sau alte metode specifice programarii liniare. Aplicarea algoritmului simplex in acest caz particular in care numarul restrictiilor este m+n si numarul variabilelor m*n presupune efectuarea unui numar foarte mare de calcule. In consecinta, exploatind forma lor particulara, pe baza teoremelor fundamentale ale programarii liniare si a dualitatii s-au elaborat procedee specifice de rezolvare a acestora. Cu toate acestea aflarea solutiei optime impune parcurgerea a doua mari etape ca la orice problema de programare liniara:

Etapa I: Generarea unei solutii admisibile de baza.

Etapa II: Verificarea optimalitatii solutiei gasite si, daca este nevoie, imbunatatirea ei pana cand se afla solutia optima finita.

EtapaI. Determinarea unei solutii admisibile de baza, pe care o vom numi in continuare solutie initiala, poate fi facuta prin metodele cunoscute din programarea liniara sau, mai simplu, prin metode specifice din care mentionam:

- metoda diagonalei (Dantzig);

- metoda elementului minim pe linie;

- metoda elementului minim pe coloana;

- metoda elementului minim pe tabel;

- metoda diferentelor maxime sau metoda lui Vogel;

Deoarece aceste metode nu cer o teoretizare speciala, vor fi expuse odata cu aplicarea lor in cazul unei probleme cu m=3 si n=4. Pentru a intelege rapid aceste metode, elementele modelului vor fi asezate intr-un tabel cu dubla intrare cu m+2=5 linii si n+2=6 coloane si anume:

C1 C2 C3 C4 Disponibil

D1 5

7

11

4

400t

D2 10

9

5

6

250t

D3 7

8

8

9

300t

Necesar 200t 270t 330t 150t 950t

Fiecare casuta ( i,j ), i {1,..,m}, j {1,..,n}, din cele m*n de acest tip existente in tabelul 1, corespunde rutei dintre depozitul Di in care sunt stocate ai unitati de marfa (vezi coloana disponibilului) si centru consumator Cj care solicita bj unitati din aceeasi marfa (vezi linia necesarului). Pe aceasta ruta este cunoscut costul transportului pe unitatea de produs exprimat in unitati monetare si I se ataseaza variabila xij ce reprezinta cu catva aproviziona Di pe Cj. Se cere sa se stabileasca acele valori ale variabilelor xij, care satisfac restrictiile:

si minimizeaza forma liniara:

Din punct de vedere economic solutia optima reprezinta un plan de aprovizionare a celor patru centre consumatoare, optim sub aspectul pretului. Optimizarea planurilor de transport al marfurilor omogene poate fi facuta si dupa alte criterii de rentabilitate cum ar fi:

- distanta parcursa sa fie minima;

- minimizarea consumului total de combustibil etc;

Vom prezenta trei din cele cinci metode amintite