Programarea liniară tip transport

Un caz particular al programarii liniare este atunci când activitatile si resursele se exprima in unitati de masura de acelasi fel , caz in care problema se numeste “tip transport”.

Modelul matematic al problemei de transport este :

Daca egalitatea nu este satisfacuta se adauga, pentru echilibrare, un consumator respectiv un producator suplimentar care are coeficientii de cost zero.

Remarcam ca functia obiectiv cere numai minim .

Modelul este denumit “tip Transport” pentru ca ofera solutii unor probleme formulate astfel:

Se dau:

- cantitatile disponibile la furnizori pentru un produs omogen:

- necesarul de aprovizionat al consumatorilor aceluiasi produs;

- costurile unitare de transport intre furnizori si consumatori.

Se cere sa se intocmeasca un program de transport care sa satisfaca necesarul consumatorilor cu un cost total minim.

Dat fiind aplicatiile numeroase si importante ale modelului in optimizarea transportului feroviar, vom studia cateva metode pentru calcularea optimumului.

Metoda Nord Vest pentru aflarea unei solutii initiale de baza .

Se da in tabel necesarul si disponibilul unui produs omogen precum si costurile unitare de transport sau distantele dintre furnizori si consumatori.

Se cere gasirea unei repartizari ca pe total costul sa fie minim .

Se porneste din campul din colt stanga sus ( pe o harta coltul N-V ) si se aloca valoarea minima dintre disponibil si necesar, in cazul nostru valoarea minima dintre 5 si 7. S-a satisfacut necesarul si au mai ramas 2 unitati disponibile , se face acelasi rationament pentru campul alaturat si asa mai departe obtinandu-se alocarea din tabel.

Costul total dupa alocarea obtinuta adica valoarea functiei obiectiv este :

f=5x19 + 2x30 + 6x40 + 3x40 + 4x70 + 14x20 = 1015

Metoda elementului minim al matricei costurilor consta in executarea alocarilor in campurile in ordinea crescatoare a costurilor .

Metoda nu da o solutie optima ci una imbunatatita fata de metoda NV.

Valoarea functiei obiectiv este :

f = 7x40 + 7x10 + 2x70 + 3x40 + 8x8 + 7x20 = 814