Problema standard de transport (bidimensionala)

PROBLEMA STANDARD DE TRANSPORT (BIDIMENSIONALA

Problema standard de transport este intalnita uneori sub denumirea de problema Hitchcock-Koopmans, deoarece a fost enuntata de F.L.Hitchcock in 1941 si completata de Koopmans in 1947.

1. FORMULAREA PROBLEMEI

Presupunem ca se dau m centre de productie (producatori) in care exista un anumit produs in cantitatile , produs care trebuie transportat la n centre de consum (consumatori) , necesarul de consum fiind respectiv , iar costul unitar de transport de la centru de productie la centru de consum fiind ; se cere sa se determine un plan optim de transport, adica se cer cantitatile (necunoscute) de produs ce trebuie transportate de la centrul la centrul pentru fiecare pereche de indici .

Se presupune de asemenea ca cererea este egala cu oferta, iar costul transportului este proportional cu cantitatea de produs transportata pe fiecare ruta (,), sau mai scurt notata, .

2. MODELUL PROBLEMEI

Problema mai sus formulata se modeleaza astfel:

(1)

cu conditiile:

. (2)

Observatii: (i). Problema de transport (1) este o veritabila problema de programare liniara sub forma standard. Aceasta are forma (3):

(3)

unde:

;

;

.

Datorita numarului mare de variabile, chiar in cazul problemelor de dimensiuni relativ mici, nu este recomandata utilizarea algoritmului simplex pentru rezolvare, motiv pentru care vom prezenta un algoritm special de rezolvare.

Vom nota cu P multimea programelor problemei (1), adica:

P = }

si cu S multimea programelor optime ale problemei (1), adica:

S =.

(ii). Matricea M are rangul m+n-1.

Intr-adevar, rang(M) si m+nmn daca , deci

rang(M)m+n. Matricea M este de tipul (m+n, mn). Deoarece suma primelor m linii este egala cu suma ultimelor n linii rezulta ca rang(M)m+n-1. Din matricea M se poate forma o matrice patrata nesingulara de ordin m+n-1, daca suprimam linia m+1 si luam din matricea ramasa coloanele 1, n+1, 2n+1, .,(m-1)n+1, 2, 3, 4, ., n. Produsul elementelor de pe diagonala principala este 1, iar elementele de sub diagonala principala sunt nule.

(iii). Un program de baza al problemei (1) este nedegenerat daca are m+n-1 componente nenule; in caz contrar, deci daca are mai putin de m+n-1 componente nenule este degenerat. Sistemul de valori:

;

este un program al problemei (1), dar nu este program de baza.

(iv). Problema standard de transport poate fi abordata in termenii teoriei digrafurilor, asociindu-i acesteia urmatoarea retea de transport:

Figura 1.

in care fiecare arc (P_i , C_j) are capacitatea min(a_i, b_j), caz in care rezolvarea problemei de transport se reduce la determinarea fluxului maxim in reteaua de transport asociata, care corespunde cheltuielilor minime de transport.

(v). Analog rezolvarii oricarei probleme de programare matematica, rezolvarea problemei de transport (1) necesita rezolvarea urmatoarelor trei subprobleme:

- determinarea unui program de baza initial (DPBI);

- testarea optimalitatii unui program de baza (TOPB);

- imbunatatirea unui program (in cazul in care nu este optim) (IP).

Daca cele trei subprobleme sunt rezolvate atunci algoritmul de rezolvare pentru problema de transport (1) este urmatorul:

Pasul 1. Se rezolva subproblema DPBI;

Pasul 2. Se rezolva subproblema TOPB;

Pasul 3. Daca programul este optim atunci STOP.

altfel se rezolva subproblema IP; treci la pasul 2.

3. METODE PENTRU DETERMINAREA UNUI PROGRAM DE BAZA INITIAL

Exista mai multe metode pentru determinarea unui program de baza initial. Dintre acestea mentionam:

- metoda coltului nord-vest (G. Dantzig);

- metoda costului minim (H. S. Houthakker);

- metoda elementului minim pe linie;

- metoda elementului minim pe coloana;

- metoda diferentelor maxime.

In continuare ne vom ocupa de primele doua metode si recomandam celor interesati utilizarea celei de a doua metode, deoarece aceasta urmareste transportul de produs, cu prioritate, pe rutele cu costuri unitare de transport mici.

Pentru determinarea unui program de baza initial se utilizeaza prezentarea restrictiilor din modelul (1) sub forma unui tabel tabel standard de m+1 linii si n+1 coloane de forma urmatoare:

O pereche de indici , sau cu alte cuvinte, un element (dreptunghi) al tabelului de mai sus va fi numita (numit) celula.

Esenta ambelor metode consta in urmatoarele: se alege o celula (p, q) si se atribuie variabilei x_pq valoarea maxima compatibila cu restrictiile din (1), adica:

.

Sunt posibile trei situatii:

(i). a_p < b_q, caz in care avem , toate celelalte elemente ele liniei p fiind nule, , deoarece disponibilul centrului P_p a fost epuizat. Noua valoare a lui b_p va fi b_p b_p - a_p si se alege o noua celula din zona necompletata a tabelului cu care se procedeaza la fel, pana cand tabelul este complet. Datorita conditiei (2) epuizarea disponibilului producatorilor si satisfacerea solicitarilor consumatorilor sunt simultane.

(ii). b_q < a_p, deci , , solicitarea consumatorului C_q fiind satisfacuta, iar disponibilul in centrul P_p fiind a_p a_p-b_q

(iii). a_p = b_q, deci , , . In acest caz se obtine un program degenerat. Deseori daca se suprima linia p se inlocuieste b_q cu b_q+e noul b_q fiind b_q (b_q+e)-b_q e iar daca se suprima coloana q se inlocuieste a_p cu a_p+e noul a_p fiind a_p a_p+e a_p e

In fiecare din cele trei situatii programul obtinut este program de baza.

Ceea ce diferentiaza cele doua metode este celula cu care incepe determinarea valorilor variabilelor de baza si apoi celula cu care se continua algoritmul de determinare a valorilor variabilelor de baza, dupa ce o valoare a fost determinata. In metoda coltului nord-vest se incepe cu celula (1, 1) situata in coltul nord-vest al tabelului si se continua cu celula situata in coltul nord-vest al tabelului necompletat, in timp ce la metoda costului minim se incepe cu determinarea valorii variabilei de baza corespunzatoare costului minim din matricea costurilor unitare de transport si se continua cu celula corespunzatoare costului minim din tabelul necompletat.

4. TESTAREA OPTIMALITATII UNUI PROGRAM DE BAZA

Pentru testarea optimalitatii unui program al problemei de transport se face apel la teorema Kuhn-Tucker pentru problema de programare liniara, care furnizeaza conditii necesare si suficiente pentru optimalitatea unui program.

Problema duala problemei de transport (1) este problema (4).

               (4)

Cuplul de programe duale si pentru cuplul de probleme de programare liniara duale (1)-(4) este optim daca si numai daca sunt satisfacute conditiile (5).

                          (5)

Observatie. Din ultimul grup de relatii Kuhn-Tucker din (5) rezulta ca:

.

Daca este un program al problemei (1) atunci primele trei grupe de relatii din (4) sunt indeplinite. Notand prin:

rezulta ca:

,

iar conditia de optim a programului devine:

Algoritmul pentru testarea optimalitatii unui program este urmatorul:

Pasul 1. Se determina multimea ;

Pasul 2. Se rezolva sistemul (cel putin o variabila are valoare fixata);

Pasul 3. Se calculeaza valorile: ;

Pasul 4. Daca atunci scrie programul este optim

altfel rezolva subproblema (IP).

5. IMBUNATATIREA UNUI PROGRAM

Pentru imbunatatirea unui program utilizam conceptul de ciclu in tabelul asociat acestei subprobleme, care este tabelul obtinut din tabelul utilizat pentru determinarea unui program de baza din care se suprima ultima linie si ultima coloana, deci din tabelul de forma:

Definim ciclul ca fiind succesiunea de celule (din tabelul precedent) avand  una din urmatoarele forme:

sau

Conceptul de ciclu este esential pentru determinarea celulei care intra in baza si a celei care paraseste baza. Analog criteriului de intrare in baza de la algoritmul simplex, de aceasta data se determina celula corespunzatoare "celei mai pozitive diferente" , care in cazul de fata corespunde celulei (k, l) situata in ciclu pe pozitia (i₁, j₁). Variabila x_kl devine variabila de baza (in celula (k, l) se va transporta produs in vederea imbunatatirii programului), produs ce poate proveni din celulele din ciclu situate pe pozitii pare, presupunand ca numerotarea celulelor se face incepand cu celula (k, l), indiferent daca parcurgem ciclul pornind pe linie sau pe coloana. Pentru a ramane in multimea P a programelor este posibil sa transportam cel mult cantitatea:

.

Cu acestea algoritmul pentru rezolvarea subproblemei (IP) este urmatorul:

Pasul 1. Se calculeaza ;

Pasul 2. Se determina ciclul format din celula (k, l) si alte celule corespunzatoare variabilelor de baza;

Pasul 3. Se numeroteaza celulele ciclului incepand cu celula (k, l);

Pasul 4. Se determina valoarea variabilei x_pq, adica valoarea ;

Pasul 5. Se modifica valorile variabilelor ciclului astfel:

.

Pasul 6. STOP.

Observatii. (i). Noul program de baza este constituit din variabilele bazei precedente (cu valorile variabilelor de baza modificate pentru celulele ciclului) cu exceptia variabilei x_pq care paraseste baza, la care se adauga variabila .

(ii). In cazul in care, in cadrul unei iteratii, si alte valori ale variabilelor de baza (in afara de ) sunt nule, noul program este degenerat.

(iii). Daca x^* este un program de baza al problemei de transport, iar este programul care se obtine din x* prin intrarea in baza a variabilei x_pq, relatia dintre valorile functiilor obiectiv pentru aceste programe este:

,

unde:

.

(iv). Conditia (2) nu restrange generalitatea problemei de transport; daca aceasta este o inegalitate, adica are forma:

, (2')

ceea ce exprima faptul ca cererea totala este mai mare decat disponibilul total si corespunde modelului:

(1')

care se poate reduce la modelul standard, introducand un centru de productie fictiv P_m+1, caruia i se atribuie un disponibil egal cu excedentul cererii fata de oferta, adica:

.

Costurile , asociate variabilelor x_m+1,j, pot fi nule sau egale cu penalizarile centrelor de consum in cazul nesatisfacerii cererii.

Analog se standardizeaza problema de transport:

(1'')

care se poate reduce la modelul standard, introducand un centru de consum fictiv C_n+1, caruia i se atribuie un consum egal cu excedentul ofertei fata de cerere, adica:

.

Costurile , asociate variabilelor x_i,n+1, pot fi nule sau egale cu cheltuielile de depozitare (stocaj) in centrele de productie .