Modelul matematic general al
problemelor de tip transport
in forma sa generala modelul problemei transporturilor se
refera la o problema echilibrata in care totalul necesarului la cei n
consumatori este egal cu totalul disponibilului la cei m furnizori adica : ∑ai =∑bj .Impunand
conditia de a satisface intgral necesarul bj al fiecaruia dintre cei j consumatori , se pot formula o
serie de restrictii de forma : ∑xij = bj (j = 1 ,2
. . , n) . Similar ,impunand conditia epuizarii disponibilului existent la fiecare furnizor se ajunge la m
restrictii de forma : ∑xij =ai (i = 1,2 . . ,
m) . Modelul mai trebuie completat cu
conditiile de nenegativitate : xij ≥ 0 ( i = 1,2,.m) si
(j =1,2,.n) si cu functia obiectiv : f(x) = ∑ ∑ cijxij
(min) sau (max) .Problema clasica de transport este de minimizare . In
raport cu semnificatia valorilor cij , functia obiectiv poate fi
insa si de minimizare . Sistemul de
ecuatii liniare contine m x n necunoscute si m + n - 4 ecuatii liniar
independente deoarece se respecta si conditia ∑ai =∑bj .Se ajunge astfel la un
sistem compatibil nedeterminat care
admite in principiu un nr foarte mare de solutii posibile obtinute prin rezolvarea sistemelor determinate
identificate prin atribuirea de valori arbitrare unui numar de (m-1) (n-1)
necumoscute .Se poate dovedi ca cel putin o solutie care minimizeaza valoarea
functiei obiectiv se gaseste prin rezolvarea unuia din sistemele determinate ce
se obtin din sistemul nedeterminat prin anularea a m x n -(m + n -1)
necunoscute .O solutie de baza nedegenerata are un nr m + n - 1 componente
strict pozitive si ( m-1 )(n-1 ) componente nule .Daca nr componentelor strict
pozitive e < de m + n - 1 spunem ca solutia este degenerata .Metode de determinare a unei solutii de baza
.O solutie de baza se poate obtine prin utilizarea unui algoritm ce consta in
alegera intamplatoare la ficare pas a unei variabile strict pozitive xij
careia i se atibuie valoarea maxima definita de relatiile : : ∑xij
= bj (j= 1 ,2 . . , n) . ∑xij =ai (i =
1,2 . . , m) .
adica xij =min .Toate
celelalte variabile de pe linia i sau coloana j vor lua valoarea xij
= 0 dupa cum ai≤bj sau bj≤ai Valorile
ai sau bj se recalculeaza si devin : a'i=ai
- bj daca bj<ai ; b'j=bj
- ai daca ai<bj . Aceasta metoda
poate fi particularizata prin alegera anumitor criterii de introducerea in
solutia de baza a valorilor xij strict pozitive .procedeul coltului de nord vest Criteriul de alegere la fiecare pas a variabilelor
strict pozitive care sa participe in solutia de baza este pozitionarea lor in
celula din coltul de nord vest fie in tabelul initial fie in tabelele reduse ce
rezulta prin eliminarea unei linii sau a
unei coloane dupa cu m ai<bj sau .bj < ai
.Totusi procedeul coltului de NV prezinta avantajul ca aplicarea lui are
un caracter mecanic ceea ce permite realizarea unui program de calcul simplu in
ipoteza prelucrarii electronice a datelor . Procedeul
elementului minim pe linie .Pentru introducera variabilelor strict pozitive
in solutia de baza se alege la fiecare pas al prelucrarii algoritmului pozitia
corespunzatoare elementului minim din fiecare linie .Daca ai>bj
se trece la pozitia corespunzatoare elementului imediat urmator ca
valoare de pe aceeasi linie ; astfel se trece la o alta linie pana la
atribuirea de valori tuturor celor m x n variabile .daca apar doua sau mai
multe valori min egale se prefera mai intai pozitia cer permite realiz pe ruta
respectiva a unui vol mai mare de transport .Avand la baza un criteriu economic
solutia initiala obtinuta e de obicei mai apropiata de cea optima comparativ cu
celelalte 2 procedee mentionate Procedeul
elementului minim pe coloana .Se aplica in mod similar cu observatia ca
analiza se realizeaza de data aceasta pe coloane. Procedeul elementului minim din tabel are drept criteriu de
introducere al variabilelor strict pozitive in solutia de baza elementul minim
din tabelul initial sau din tabelele reduse obtinute prin eliminarea la fiecare
pas a unei linii (daca ai<bj) sau a unei coloane (daca
bj<aj). Analiza facandu-se pe ansamblu, solutia astfel
obtinuta este de obicei mai avantajoasa decat cele furnizate prin procedeele
prezentate anterior. Variabilele strict pozitive s-au introdus in ordinea x22,x14,x21.
Se constata ca in aceasta aplicatie solutia obtinuta coincide cu cea furnizata
prin procedeul elementului minim pe linie.
Procedeul
diferentelor maxime . Pentru fiecare linie si coloana se face
diferenta dintre elementul imediat urmator ca valoare elementului minim si
elementul minim. La fiecare pas se identifica diferenta maxima repartizandu-se
in solutia de baza variabila corespunzatoare elementului minim care a generat
diferenta maxima. Daca doua sau mai multe diferente maxime sunt egale se ia in
considerare mai intai diferenta care provine din numere mai mici ; daca si
acestea sunt egale, se prefera pozitia care permite realizarea unui volum mai
mare de transport. Diferentele se recalculeaza la fiecare pas, fie pe linie,
fie pe coloana. Desi ceva mai laborios, procedeul duce la solutii initiale mai
apropiate de cea optima. Datorita caracterului obligat al repartizarii la
ultimul pas se poate intampla ca uneori solutia astfel obtinuta sa fie mai
dezavantajoasa decat cea obtinuta printr-un alt procedeu. Observatia este
valabila si pentru celelalte procedee prezentate, ierarhia lor apreciata pe
baza valorii functiei obiectiv, schimbandu-se de la o aplicatie la alta.
Algoritmi de
optimizare reprezinta numai solutii initiale, pornind de la care,
prin algoritmul de optimizare ales (metoda distributiva sau metoda distributiva
modificata) se obtine in mod iterativ, prin imbunatatiri succesive, solutia
optima.