Problema transportului

Problema transportului

O problema de transport, echilibrata, corespunzatoare tabelului (T) (vezi II.2), are forma:

numita si forma standard.

In cazul in care avem , atunci in tabelul (T) introducem coloana (m+1)-a cu

introducem linia (n+1)-a cu

Din (27) si (28) avem relatii cu necunoscute. Din (29) rezulta ca intre ecuatiile (27) si (28) mai exista cel putin o relatie si atunci rangul matricii sistemului (27) + (28) este ce mult

Definitia II.8.1. Daca rangul matricii sistemului (27)+(28) este m+n-1, iar un program de baza are exact m+n-1 componente pozitive (restul nule) atunci programul se numeste nedegenerat.

O problema de transport se poate rezolva prin metoda simplex dar exista si metode specifice.

Pentru inceput vom prezenta doua metode specifice pentru obtinerea unui program de baza; in cazul unui exemplu concret:

1* - Metoda coltului N-V (nord-vest)

2* - Metoda elementului minim din linie sau coloana.

Problema: Din trei depozite trebuie transportata acelasi tip de marfa la trei magazine . Costurile unitare de transport, disponibilul (D) si necesarul (N) sunt date in tabelul:

Observam ca problema este echilibrata.

Metoda .In coltul din N-V se trece Deoarece necesarul s-a epuizat se trece 0 (sau se lasa libere, sau se hasureaza) celelalte casute de pe prima coloana. Iar devine. Obtinem tabelul:

Cu coloanele , ramase procedam la fel. In coltul N-V (casuta (1,2) din tabel) inscriem Deoarece disponibiluls-a epuizat se trece 0 in restul casutelor de pe prima linie; iar necesarul a devenit . Obtinem tabelul:

Cu casutele ramase libere se procedeaza ca mai sus si se obtine, in final, programul de baza:

80 20 0

0 90 30

0 0 70

care este nedegenerat (are componente; in cazul de fata m=3, n=3).

Metoda Metoda minimului pe linie:

Cautam costul minim din prima linie; il gasim pe pozitia In casuta respectiva , trecem . Deoarece s-a epuizat hasuram celelalte casute ale coloanei ; iar a devenit 100-20=80.

Tabelul s-a transformat in:

In tabelul ramas, compus din coloanele si cautam din nou cel mai mic cost de pe prima linie: gasim . In casuta corespunzatoare trecem Deoarece s-a epuizat, hasuram casutele libere din prima linie, iar a devenit 100-20=80. Obtinem tabelul:

In continuare procedam la fel si obtinem programul de baza:

80 0 20

0 110 10

0 0 70

care este diferit de cel obtinut prin metoda coltului N-V. Lucrurile se petrec la fel daca cautam costul minim de transport de pe o coloana.

De regula in rezolvarea unei probleme de transport, dupa ce i s-a determinat un program de baza, se foloseste duala sa:

Conform teoremelor dualitatii avem:

pentru orice pereche de solutii duale X,Y.

in cazul in care avem optim.

Inlocuind in valorile cu expresiile date de modelul primal ((27), respectiv (28)), gasim:

Inegalitatea devine:

sau:

Daca X este optim finit pentru problema primala avem si inegalitatea (32) se transforma in egalitate. Cum ajungem la concluzia:

Tot de aici reiese ca daca pentru un avem atunci X nu este optim.

Cum sunt in numar de m+n-1 atunci (33) reprezinta m+n-1 relatii cu m+n necunoscute (sunt in numar de n, iar in numar de m). Tinand seama si de forma sistemului (33) este suficient sa facem pentru a obtine restul necunoscutelor.

Conditia ca X sa fie optim revine la faptul ca pentru nebazici.

Notand conditia ca X sa fie optim devine pentru nebazici. Daca nu toti pentru nebazici, se trece la imbunatatirea programului:

Se alege .

Variabila corespunzatoare, nebazica se introduce in baza. Pe linia r, dintr-un bazic trebuie scazut un , pentru a nu modifica disponibilul si atunci pe coloana k, la un bazic trebuie adaugat pentru a nu modifica necesarulsi in consecinta pe linia p la un trebuie scazut pentru a nu modifica disponibilul .

Notand , se formeaza astfel un ciclu:

Alegand se obtine o noua solutie de baza. Se calculeaza din nou , s.a.m.d., pana in momentul in care nu mai avem .

Toate aceste rezultate se pun intr-un tabel specific pe care il prezentam in contextul problemei exemplu anterioare.

In caseta avem programul de baza determinat cu metoda coltului N-V. Corespunzator acestuia sistemul devine:

Punand u₁=0 obtinem valori pe care le-am trecut in prima coloana, respectiv prima linie din caseta . Apoi casutele din aceasta caseta, corespunzatoare programului de baza se hasureaza, iar celelalte se completeaza cu valorile corespunzatoare. Se calculeaza valorile care au fost trecute in casutele corespunzatoare.

Observam ca , deci nu este solutie optima si trebuie imbunatatita.

Formam ciclul cu si gasim Scriem un nou tabel cu noua solutie gasita pe care am notat-o .

Am obtinut nebazici, deci solutia X₁ este optima. Observam ca ea coincide cu solutia de baza determinata cu ajutorul metodei costului minim pe linie.

Propunem spre rezolvare urmatoarele probleme de transport:

1.

Observatie: Solutia de baza obtinuta cu metoda coltului N-V este:

care are 5 componente nenule.

Cum m+n-1=3+4-1=6 rezulta ca este degenerata. Se cauta alta solutie de baza cu metoda costului minim pe linie, obtinandu-se:

2.

Observatie: Mai intai trebuie transpus acest tabel. Se va gasi solutia de baza:

.

3.

4.

Observatie: Deoarece (D) > (N) problema este neechilibrata. Introducem un consumator fictiv: