Modelul matematic general al problemelor de tip transport

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 : ∑a_i =∑b_j .Impunand conditia de a satisface intgral necesarul b_j al fiecaruia dintre cei j consumatori , se pot formula o serie de restrictii de forma : ∑x_ij = b_j (j = 1 ,2 . . , n) . Similar ,impunand conditia epuizarii disponibilului existent la fiecare furnizor se ajunge la m restrictii de forma : ∑x_ij =a_i (i = 1,2 . . , m) . Modelul mai trebuie completat cu conditiile de nenegativitate : x_ij ≥ 0 ( i = 1,2,.m) si (j =1,2,.n) si cu functia obiectiv : f(x) = ∑ ∑ c_ijx_ij (min) sau (max) .Problema clasica de transport este de minimizare . In raport cu semnificatia valorilor c_ij , 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 ∑a_i =∑b_j .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 x_ij careia i se atibuie valoarea maxima definita de relatiile : : ∑x_ij = b_j (j= 1 ,2 . . , n) . ∑x_ij =a_i (i = 1,2 . . , m) .

adica x_{ij ­}=min .Toate celelalte variabile de pe linia i sau coloana j vor lua valoarea x_ij = 0 dupa cum a_i≤b_j sau b_j≤a_i Valorile a_{i ­}sau b_j se recalculeaza si devin : a'_i=a_i - b_j daca b_j<a_i ; b'_j=b_j - a_i daca a_i<b_{j .} Aceasta metoda poate fi particularizata prin alegera anumitor criterii de introducerea in solutia de baza a valorilor x_ij 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 a_i<b_j sau .b_j < a_{i .}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 a_i>b_j 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 a_i<b_j) sau a unei coloane (daca b_j<a_j). 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 x₂₂,x₁₄,x₂₁. 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.