Utilizarea aplicației EXCEL în vederea optimizării problemelor de transport

1. Introducere

Problemele de transport apar frecvent în situaţiile în care trebuie planificat modul de distribuire al bunurilor de la producători la consumatori. Obiectivul obişnuit al acestor probleme este minimizarea costurilor de transport.

Modelele de rezolvare a problemelor de transport reprezintă o variaţie a problemelor de programare liniară şi presupun următoarele considerente:

1) Obiectivul îl constituie minimizarea costurior totale de transport;

2) Costurile de transport sunt funcţii liniare în raport cu numărul de unităţi transportate;

3) Cererea şi oferta sunt exprimate în unităţi omogene;

4) Costurile de transport pe unitate nu variază cu cantitatea transportată.

2. Modelul matematic al problemei de transport

Problema de transport clasica se enunta dupa cum urmeaza.

Se considera un anumit tip de produs care poate fi livrat de m furnizori Fi in cantitatile ai , i=1,......,m. Produsul respectiv este solicitat de n beneficiari Bj , in cantitatile bj, j=1,.......,n. Cunoscând costul unitar de transport al produsului cij de la furniyorul Fi la beneficiarul Bj, se cere sa se intocmeasca planul optim de transport astfel incâat costul total al transportului sa fie minim.

Daca cantitatea totală de produs disponibilă la furnizori este egala cu cantitatea totală solicitată de beneficiari, adică

∑_(i=1)^m▒a_i = ∑_(j=1)^n▒b_j

atunci problema este echilibrată. Altfel problema este neechilibrată.

Se notează cu ¬¬xij cantitatea de produs transportată de la furniyorul Fi(i=1,.......,m) la beneficiarul Bj(j=1,......,n).

Modelul matematic al problemei de transport echilibrată este:

{█([min]z=∑_(i=1)^m▒∑_(j=1)^n▒〖c_ij x_ij 〗@∑_(j=1)^n▒x_ij =a_i,i=1,…,m@∑_(i=1)^m▒〖x_ij=b_j,j=1,…,n〗@x_ij≥0,i=1,…,m,j=1,…,n)┤

(2)

cua_i≥0,b_j≥0,c_ij≥0(i=1,…,m,j=1,…,n).

Modelul (2) este un caz particular de problemă de programe liniară. El poate fi rescris sub forma matriceală:

{█([min]z=c^γ x@Ax=b@x≥0)┤(3)

Unde: c∈R^mxn,c=[c_11,c_12,…,c_1n,c_21,…,c_2n,…,c_m1,…,c_mn ] 〖^T〗

x∈R^mxn,x=[x_11,x_12,…,x_1n,x_21,…,x_2n,…,x_m1,…,x_mn ] 〖^T〗

b∈R^(m+n),b=[a_1,a_2,…,a_m,b_1,b_2,…,b_n ] 〖^T〗

A∈M(m+n,mxn),A=[■(■(I@0)■(0@I)&⋯&■(0@0)@⋮&⋱&⋮@■(0@E)■(0@E)&⋯&■(I@E))]

În care I=[1,1,…,1]∈R^n,0=[0,0,…,0]∈R^n,E este matricea unitate de ordinul n, iar rang (A) = m + n – 1.

Dacă problema de transport este neechilibrată, pentru rezolvare trebuie în prealabil adusă la forma echilibrată. În acest scop, se adaugă, după caz, fie un furnizor fictiv F_(m+1), cu o cantitate de produs disponibilă, respectiv, necesară, egală cu valoarea diferenţei dintre cele două sume din relaţia (1), costurile unitare de transport corespunzătoare fiind nule.

Fiind o problemă de programare liniară, problema de transport echilibrată poate fi rezolvată cu ajutorul metodei simplex. Metoda specifică de rezolvare este metoda potenţialelor (algoritmul de transport). Acesta operează asupra problemei duale:

{█([max]w=∑_(i=1)^m▒〖a_i u_i+∑_(j=1)^n▒〖b_j v_j 〗〗@u_i+v_i≥c_ij,i=1,…,m,j=1,…,n)┤(4)

Găsirea unei soluţii de bază iniţială se poate face prin mai multe metode şi anume: metoda colţului de nord-vest; metoda elementului (costului unitar)minim de tabel; metoda diferenţelor maxime (Vogel); metoda elementului minim pe linie; metoda elementului minim pe coloană.

Problema de transport are întotdeauna soluţia optimă finită, unică sau nu.