Cercetari Operationale si Teoria Deciziei
Problema de tip transport. Algoritmul de transport pentru problema echilibrata
Notatii: (conform cu notatiile anterioare)
m numarul de centre de aprovizionare (depozite) 
,
, (sau 
furnizorul i),
n numarul de centre de consum (puncte de lucru,
magazine) 
,
,
cantitatea de produs
omogen care se afla la depozitul , 
disponibilul,
cantitatea ceruta
la centrul de consum (sau beneficiarul 
), 
necesarul,
cantitatea
necunoscuta de produs ce va fi transportata de la depozitul la centrul de consum ,
,
,
costul transportului
unei unitati din produsul considerat de la depozitul la centrul de consum(se face ipoteza ca acest cost nu depinde de
cantitatea transportata pe ruta respectiva),
, 
.
Conditii
; 
conditia de
balansare sau de echilibru.
Modelul matematic: (program de transport)
|
|
|
Observatii
Problema de transport are totdeauna o
solutie admisibila: 
.
Teorema (Luenberger): Problema de transport are totdeauna solutie si o restrictie este redundanta. Inlaturand oricare dintre restrictii, cele n+m-1 ramase formeaza un sistem liniar independent .
Organizarea datelor se face tabelar, in tabloul de transport:
|
Bene- ficiari |
|
|
|
|
|
|
Disponibil D |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Necesar N |
|
|
|
|
|
|
|
Tabel 1.
Practica ofera probleme economice in
care se pot intalni situatiile: oferta depaseste cer 424h75e erea (
), cererea depaseste oferta (
) – caz in care se ajusteaza cererea, problema
echilibrata (
).
Algoritmul de transport pentru problema echilibrata (cuprinde doua etape):
Se
determina o solutie de baza initiala
avand cel mult (m+n-1)
componente nenule, iar celelalte nule. (Daca are exact m+n-1
componente nenule aceasta se va numi solutie de baza
nedegenerata). Determinarea acestei solutii se poate face prin mai
multe metode:
-metoda coltului de nord-vest:
se incepe distribuirea de la depozitul
(furnizorul 
) la beneficiarul 
, continuand distribuirea tinand seama de partenerii
ramasi in discutie, dupa satisfacerea necesarului primilor
beneficiari si distribuirea cantitatilor de la primele depozite
-metoda elementului minim pe linie,
-metoda elementului minim pe coloana:
se
atribuie, cand este posibil, cantitatea ceruta acelui beneficiar 
de la acel depozit 
pentru care costul 
este minim. In acest
caz componenta solutiei de baza initiala este 
. Se elimina din transport depozitul sau beneficiarul dupa cum minimul
dintre 
si 
este sau . Se continua studiul cu tabelul ramas pana la
obtinerea solutiei de baza initiale
-metoda elementului minim din tabel,
-metoda diferentelor maxime.
a. este solutie
optima daca 
, 
matricea costurilor de
transport, 
matricea „costurilor
umbra” (variabilele duale 
si 
se determina din sistemul liniar 
, 
indici
corespunzatori din baza 
(metoda
potentialelor)).
b. Daca exista indici pentru care 
atunci solutia nu
este optima. Imbunatatirea solutiei care nu este
optima se face printr-un algoritm de redistribuire a
cantitatilor aprovizionate de beneficiari de la depozitele indicate
de : -se aloca o cantitate 
in locul din in care apare 
cel mai mare in
valoare absoluta.
-se construieste o noua
solutie: se recalculeaza valorile lui functie de
marimea lui 
, astfel
|
|
|
|
|
|
Tabel 2.
marimea lui fiind 
.
-pentru noua solutie se calculeaza
valorile si si se
verifica optimalitatea.
Aplicatie:
O
intreprindere de rafinare a uleiului de floarea soarelui are trei depozite , 
, 
de unde
aprovizioneaza patru beneficiari , 
, 
, 
Necesarul zilnic al
celor patru beneficiari precum si costul de transport este dat prin
Tabelul 3.:
|
Beneficiari |
|
|
|
|
Disponibil D |
|
|
| ||||
|
| |||||
|
| |||||
|
Necesar N |
Tabel 3.
Rezolvare:
I. Determinarea solutiei de baza
Metoda nord-vest: Solutia
de baza :
Tabel 4. |
Tabel 5. |
Metoda minimului costului: Solutia de baza:
|
Tabel 6. |
Tabel 7 |
II. Determinarea solutiei de optim:
Pornim de la solutia initiala de baza:
|
Tabel 8. |
Acestei solutii ii corespunde sistemul liniar:
,
,
,
,
,
.
Alegem 
. Obtinem 
, 
,
,
,
,
.
Tabel 9. |
Tabel 10. |
,
, 
.
|
|
| ||||||||
|
|
|
| |||||||
Tabel 11.
Sistemul liniar corespunzator:
,
,,,,.
|
| ||||
Tabel 2.17.
Tabel 2.18.
Solutia este optima, valoarea minima fiind:
.
Rezolvarea problemei de transport utilizand pachetul de programe MatLab:
Fisierul probt.m
function [f,g]=probt2(x);
c=[3 1 2 4;2 5 1 6;7 3 3 1];
a=[20;10;30];
b=[12;9;18;21];
f=sum(sum(c.*x));
g=[sum(x(1,:))-a(1);sum(x(2,:))-a(2);sum(x(3,:))-a(3);
sum(x(:,1))-b(1);sum(x(:,2))-b(2);sum(x(:,3))-b(3);
sum(x(:,4))-b(4)];
Fisierul transpt.m
options(1)=1;
options(13)=5;
x0=[12 8 0 0;0 1 9 0;0 0 9 21];
VMI=zeros(3,4);
VMS=[];
[x,options]=constr('probt2',x0,options,VMI,VMS);
x
options(8)
Solutie:
x =
11.0000 9.0000 0.0000 0.0000
1.0000 -0.0000 9.0000 0.0000
-0.0000 -0.0000 9.0000 21.0000
ans = 101.
Probleme propuse
Doua depozite
au 100 t respectiv 140 t de marfa ce trebuie transportata la trei
magazine care au nevoie respectiv de cantitatile 70t, 80t, 90t.
Matricea costurilor de transport este: 
. Sa se prezinte un plan de transport care sa
prezinte un minim de cheltuieli.
Sa se rezolve urmatoarele probleme de tip transport:
|
Beneficiari |
|
|
|
Disponibil D |
|
| ||||
|
| ||||
|
| ||||
|
Necesar N |
Tabel 1.
|
Beneficiari |
|
|
|
Disponibil D |
|
| ||||
|
| ||||
|
| ||||
|
Necesar N |
Tabel 2.
Consideram un
consumator avand functia de utilitate 
de forma 
. a. Determinati curbele de indiferenta
corespunzatoare valorilor 
, 
, b. Determinati indicatorii marginali, de elasticitate,
si de substituire, c. Formulati modelul matematic de maximizare a
utilitatii sub restrictie bugetara, venitul consumatorului
fiind V si preturile celor doua bunuri 
si 
, d. Se modifica preturile pe piata a
celor doua bunuri cu 
si 
si venitul
consumatorului 
. Cum se modifica decizia optima in
urmatoarele situatii: - creste cu 0,5 si nu se modifica si V; - creste cu 0,5, scade cu 20%; - creste cu
0,5, V creste cu 10%. Caz
particular: 
,
, 
, 
,
u.m. (RON), 
u.m., 
u.m..
|
, 
, 
(PPL) 
, 
, 
.
=
