Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme
Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
» Problema clasica de transport


Problema clasica de transport


Master ML + IMFP

Tema 3 - curs

Problema clasica de transport

O problema de transport consta in determinarea unui plan de transport pentru un produs omogen, de la anumite centre producatoare, in scopul satisfacerii cerintelor unor consumatori si minimizarii cheltuielilor de transport.

Se considera ca exista un numar Di de furnizori (depozite) care poseda produsul respectiv in cantitati egale cu di, i = 1, 2,…, m si n centre beneficiare Bj ,



j = 1, 2, …, n, care solicita acest produs in cantitatile necesare, bj.

Se presupune ca o unitate de produs transportata de la depozitul Di la beneficiarul Bj costa cij unitati banesti.

Se cere sa se determine planul optim de transport, adica ce cantitati xij de produs trebuie sa fie transportate de la fiecare depozit la fiecare beneficiar, astfel incat sa fie respectate conditiile:

-       sa fie satisfacuta in cea mai mare masura cererea de produse in centrele beneficiare;

-       cheltuielile totale de transport sa fie minime.

Datele initiale ale unei probleme de transport se prezinta intr-un tabel de forma tabelului 1

                                                                                                         Tabelul 1

Bj

Di

B1

B2

…

Bj

…

Bn

Disponibil, di

D1

c11

x11

c12

x12

…

c1j

x1j

…

c1n

x1n

d1

D2

c21

x21

c22

x22

…

c2j

x2j

…

c2n

x2n

d2

Di

ci1

xi1

ci2

xi2

…

cij

xij

…

cin

xin

di

Dm

cm1

xm1

cm2

xm2

…

cmj

xmj

…

cmn

xmn

dm

Necesar, bj

b1

b2

…

bj

…

bn

Modelul matematic al acestei probleme de transport este urmatorul:

                                                                    (1)

Modelul (1) este modelul unei probleme de programare liniara, la care se mai poate adauga conditia de nenegativitate pentru di, bj, cij, .

Definitia 1. Problema de transport se numeste echilibrata daca:

                                                                                   (2)

In caz contrar, problema se numeste neechilibrata.

Orice problema de transport neechilibrata se poate transforma intr-o problema echilibrata astfel:

a.    daca , se introduce un beneficiar fictiv Bn+1, pentru care necesarul va fi: , iar costurile unitare de transport vor fi egale cu zero;

b.    daca , se introduce un depozit fictiv Dm+1, pentru care disponibilul va fi:  iar costurile unitare de transport vor fi egale cu zero;

Definitia 2. O problema de transport are forma standard daca .

Modelul matematic al unei probleme de transport in forma standard este:

                                                                     (3)

Rezolvarea unei probleme de transport se face numai pentru forma standard, adica numai pentru problema de transport echilibrata.

Definitia 3. O matrice  ale carei componente satisfac sistemul de restrictii si conditiile de nenegativitate ale modelului matematic (3) se numeste solutie admisibila a problemei de transport.

 Daca, in plus, matricea X minimizeaza functia obiectiv a modelului matematic (3) ea se numeste solutie optima sau plan de transport optim pentru problema data.

Se demonstreaza ca o problema de transport echilibrata admite cel putin o solutie admisibila si ca rangul matricei C a coeficientilor necunoscutelor din sistemul de restrictii al modelului matematic este: rang C = m + n -1. Acest lucru inseamna ca exista m + n -1 vectori coloana liniari independenti ce vor forma o baza a spatiului Rm+n+1. Prin urmare va existe cel putin o solutie admisibila de baza, cu cel mult m + n -1 componente pozitive. Daca solutia admisibila de baza are exact m + n -1 componente pozitive, ea se numeste solutie admisibila de baza nedegenerata. Daca solutia admisibila de baza are mai putin de m + n -1 componente pozitive, ea se numeste solutie admisibila de baza degenerata.

Definitia 4. O problema de transport se numeste degenerata daca ea admite o solutie admisibila de baza degenerata.

Desi sunt indeplinite toate conditiile care permit aplicarea algoritmului simplex pentru rezolvarea problemei de transport, exista un algoritm de rezolvare specific, mult mai usor de aplicat. Acest algoritm presupune doua etape:

Etapa I. Determinarea unei solutii admisibile de baza.

Etapa a II-a. Imbunatatirea solutiei de baza in pasi succesivi, pana la aflarea solutiei optime.

Metode pentru determinarea unei solutii admisibile de baza

Deoarece fiecare variabila corespunde unei rute (este cantitatea de produs transportata pe aceasta ruta), iar fiecare ruta corespunde unei perechi furnizor-beneficiar, vom identifica fiecare variabila xij cu ruta (i, j).

A gasi o solutie de baza nedegenerata inseamna a gasi cel mult m + n – 1 rute, din cele mּn posibile, pe care sa transportam cantitatea disponibila. Rutele vor fi organizate intr-un tabel asemanator celui in care se prezinta datele problemei de transport, fiecarei rute asociindu-se o casuta (i, j):


Bj

Di

B1

B2

…

Bj

…

Bn

Disponibil, di

D1

d1

D2

d2

Di

di

Dm

dm

Necesar, bj

b1

b2

…

bj

…

bn

In cazul problemei de transport, gasirea unei solutii initiale de baza nu este dificila, existand o multime de metode in acest scop, care incearca nu numai aflarea acesteia, ci chiar gasirea uneia cat mai buna.

Pentru determinarea unei solutii admisibile de baza pentru o problema de transport echilibrata, se folosesc, in principal, urmatoarele metode:

-       metoda coltului Nord-Vest;

-       metoda elementului minim pe linie;

-       metoda elementului minim pe coloana;

-       metoda elementului minim in tabel;

-       metoda diferentelor comparate.

In principiu, toate aceste metode urmeaza o schema comuna:

a.    se alege o ruta initiala, dupa o anumita regula;

b.    se transporta pe aceasta ruta maximul posibil, egal cu minimul dintre cantitatea care mai este disponibila la furnizorul corespunzator acestei rute si cantitatea care mai este necesara beneficiarului corespunzator rutei, in momentul alegerii rutei respective;

c.    dupa folosirea unei rute, fie se epuizeaza disponibilul furnizorului, fie se asigura intregul necesar beneficiarului, fie ambele si anumite rute nu mai pot fi folosite; ele se numesc rute blocate si se evidentiaza prin inscrierea unei liniute in casuta corespunzatoare.

d.    se alege urmatoarea ruta si se reia algoritmul de la pasul (b) pana cand nu mai ramane nici o ruta nefolosita sau neblocata.

1.    Metoda coltului Nord-Vest

Se considera problema de transport echilibrata si se construieste tabelul cu datele problemei: cantitatile disponibile di, cantitatile necesare bj, costurile unitare de transport cij, cu i = 1, 2,…, m si j = 1, 2, …, n.

Procedeul porneste cu determinarea necunoscutei aflate in casuta din coltul staga-sus (coltul Nord-Vest) a tabelului ca valoare minima intre cantitatile disponibila si necesara corespunzatoare: x11 = min (d1, b1).

Daca min (d1, b1) = d1, se anuleaza valorile necunoscutelor din toate celelalte casute ale primei linii a tabelului (cantitatile nule se marcheaza cu o linie orizontala) si se recalculeaza cantitatea necesara beneficiarului B1: .

Daca min (d1, b1) = b1, se anuleaza valorile necunoscutelor din toate celelalte casute ale primei coloane a tabelului si se recalculeaza cantitatea ramasa disponibila in depozitul D1:.

Se renunta la linia/coloana pentru care se completeaza cantitatea disponibila/necesara.

Se continua procedeul cu alocarea unei valori casutei situate in coltul Nord-Vest a tabelului ramas, tinand cont de cantitatile disponibile si necesare recalculate, pana la alocarea totala a cantitatilor di si bj.

La epuizarea elementelor de comparat, se obtine o solutie admisibila de baza.

Exemplu Se da problema de transport cu datele initiale prezentate in tabelul 2.

Se cere sa se afle o solutia admisibila de baza prin metoda coltului Nord-Vest.     

                                                                                           Tabelul 2

Bj

Di

B1

B2

B3

B4

B5

di

D1

90

120

140

80

60

120

D2

100

140

70

120

90

110

D3

60

160

130

140

100

70

bj

80

72

75

28

45

Problema este echilibrata:.

Se da necunoscutei x11 (situata in coltul din stanga-sus) valoarea:

x11 = min (80, 120) = 80, restul necunoscutelor coloanei 1 fiind nule (cantitatea necesara beneficiarului B1 a fost asigurata).

In depozitul D1 a mai ramas o cantitate disponibila egala cu: .

Se elimina coloana 1 din tabel. Se da necunoscutei x12 (prima din coltul stanga-sus) valoarea:, restul necunoscutelor din prima linie a tabelului fiind nule (s-a epuizat cantitatea disponibila in depozitul D1). Se recalculeaza cantitatea necesara beneficiarului B2: .

Se elimina si linia 1 din tabel. Se da necunoscutei x22 (situata in coltul N-V al tabelului ramas) valoarea:, toate celelalte necunoscute din a doua coloana a tabelului fiind nule (s-a epuizat si cantitatea necesara beneficiarului B2). Cantitatea ramasa disponibila in depozitul D2 este:.

Se elimina si coloana 2 din tabel. Se da necunoscutei x23 (situata in coltul N-V al tabelului ramas) valoarea:, ultima necunoscuta din coloana a treia fiind nula (s-a epuizat si cantitatea necesara beneficiarului B3). Cantitatea ramasa disponibila in depozitul D2 este: . Se elimina si coloana 3 din tabel.

Se da necunoscutei x24 valoarea: , anulandu-se si ultima necunoscuta de pe linia 2.

Cantitatatea necasara beneficiarului B4 se recalculeaza: .

Se elimina si linia 2 din tabel. Se da necunoscutei x34 valoarea: . Cantitatea ramasa disponibila in depozitul D3 este: . A mai ramas de stabilit valoarea unei singure necunoscute: . Solutia obtinuta este prezentata in tabelul 3.

                                                                                            Tabelul 3

Bj

Di

B1

B2

B3

B4

B5

di

D1

90

80

120

40

140

-

80

-

60

-

120

D2

100

-

140

32

70

75

120

3

90

-

110

D3

60

-

160

-

130

-

140

25

100

45

70

bj

80

72

75

28

45

S-a obtinut o solutie de baza admisibila cu sapte componente nenule:

x11 = 80; x12 = 40; x22 = 32; x23 = 75; x24 = 3; x34 = 25; x35 = 45; solutia este nedegenerata deoarece are m + n -1 = 3 + 5 - 1 = 7 componente nenule.

Valoarea functiei obiectiv pentru aceasta solutie admisibila de baza este:

u.m.

Observatie. Metoda coltului Nord-Vest opereaza numai cu valorile di si bj, fara a lua in consideratie costurile unitare cij. Este evident ca un cost total minim al transportului se va obtine utilizand rutele cu costuri unitare mici. Pe aceasta observatie se bazeaza metodele urmatoare de determinare a unei solutii admisibile de baza pentru problema de transport.

2. Metoda elementului minim pe linie

Metoda elementului minim pe linie (costului minim pe linie) consta in alegerea, pentru fiecare dintre liniile tabelului initial al problemei de transport, a celui mai mic cost unitar.

 Se da variabilei corespunzatoare acestei pozitii valoarea cea mai mica intre cantitatea disponibila si cea necesara de pe linia si coloana aferente.

Se incepe cu prima linie de sus a tabelului: se alege si apoi .

Se recalculeaza cantitatile disponibile si necesare:  si.

Daca a fost alocata intreaga cantitate disponibila pe prima linie, se suprima linia 1 sau coloana k careia ii corespunde diferenta nula (variabilele de pe linia sau coloana suprimata devin egale cu zero), apoi se trece la a doua linie si pe rand la urmatoarele, reluandu-se procedeul.

Daca nu a fost alocata intreaga cantiate disponibila pe prima linie, se cauta urmatorul element minim din aceasta linie, dand variabilei corespunzatoare valoarea egala cu diferenta de cantitate, pana la epuizarea intregii cantitati disponibile in depozitul D1.

Exemplul Pentru problema de transport data in tabelul 2, se aplica metoda elementului minim pe linie pentru aflarea unei solutii admisibile de baza.

Solutia obtinuta este prezentata in tabelul 4.

Pe prima linie a tabelului initial costul unitar cel mai mic este c15 = 60. Se da variabilei x15 valoarea: .Beneficiarului B5 i s-a satisfacut cererea, restul necunoscutelor de pe coloana 5 sunt nule, iar coloana 5 se suprima. Se recalculeaza cantitatea ramasa in depozitul D1:

In noul tabel, se continua procedeul alegand, tot de pe linia 1, costul unitar minim pentru casutele ramase (deoarece cantitatea aflata in depozitul D1 nu a fost epuizata). Acest cost unitar minim este . Se da variabilei x14 valoarea: , se anuleaza variabilele de pe coloana 4 (cererea beneficiarului B4 a fost satisfacuta), se elimina si coloana 4 din tabel si se recalculeaza cantitatea ramasa in depozitul D1:

.

Aceata cantitate este valoarea ce se va da variabilei x11 , aflata pe pozitia corespunzatoare celui mai mic cost unitar de pe linia 1, in tabelul ramas. Se anuleaza restul variabilelor de pe linia 1 (a fost epuizata cantitatea disponibila in depozitul D1), iar linia 1 se elimina. Se recalculeaza cantitatea necesara beneficiarului B1:  .

Se trece la linia a doua. Costul unitar cel mai mic este c23 = 70. Se da variabilei x23 valoarea: x23 = min (d2, b3) = min (110, 75) = 75. Cererea beneficiarului B3 a fost satisfacuta, restul variabilelor de pe coloana 3 sunt nule. Se recalculeaza cantitatea ramasa in depozitul D2: . Se cauta urmatorul cost unitar minim de pe linia 2, care este c21 = 100. Se da variabilei x21 valoarea:. Variabila x31 = 0 (cererea beneficiarului B1 a fost satisfacuta), coloana 1 se elimina.

Se recalculeaza cantitatea disponibila in depozitul D2: .

Variabila x22  = 2 si intreaga cantitate disponibila in  depozitul D2 a fost distribuita.

Se recalculeaza cantitatea necesara beneficiarului B2: . Se elimina linia 2 din tabel si se trece la linia 3 dand singurei variabile ramase, variabila x32 valoarea: .

                                                                                         Tabelul 4

Bj

Di

B1

B2

B3

B4

B5

di

D1

90

47

120

-

140

-

80

28

60

45

120

D2

100

33

140

2

70

75

120

-

90

-

110

D3

60

-

160

70

130

-

140

-

100

-

70

bj

80

72

75

28

45

S-a obtinut o solutie admisibila de baza nedegenerata, valoarea functiei obiectiv fiind:

u.m.

3. Metoda elementului minim pe coloana

Se procedeaza in mod similar metodei anterioare, cu deosebirea ca se lucreaza pe coloanele tabelului initial al problemei de transport. Se incepe cu prima coloana din stanga. Se cauta si se da variabilei xi1 valoarea: . Se recalculeaza cantitatile disponibile si necesare de pe linia i si coloana 1:  si .

Daca a fost alocata intreaga cantitate disponibila pe prima coloana, se suprima coloana 1 sau linia i careia ii corespunde diferenta nula (variabilele de pe linia sau coloana suprimata devin egale cu zero), apoi se trece la a doua coloana si pe rand la urmatoarele, reluandu-se procedeul.

Daca nu a fost alocata intreaga cantiate disponibila pe prima coloana, se cauta urmatorul element minim din aceasta coloana, dand variabilei corespunzatoare valoarea egala cu diferenta de cantitate, pana la epuizarea intregii cantitati necesare beneficiarului B1.

4. Metoda elementului minim din tabel

Metoda consta in alegerea celui mai mic cost unitar din tabelul initial al problemei de transport, variabilei corespunzatoare fiindu-i data o valoare egala cu cea mai mica dintre cantitatile disponibila si necesara de pe linia si coloana acestui cost unitar minim.

Se alege  si se ia .

Se recalculeaza cantitatile disponibile si necesare si se suprima din tabel linia sau coloana pe care aceste cantitati au fost completate.

In tabelul redus, se cauta din nou cel mai mic cost unitar, variabilei respective dandu-i-se o valoare egala cu cea mai mica dintre cantitatile disponibila si necesara ramase.





5. Metoda diferentelor comparate

Metoda consta in introducerea unor penalitati in cazul in care nu se foloseste casuta cu cel mai mic cost unitar cij. Aceste penalitati reprezinta diferenta dintre cel mai mic element (cost unitar) dintr-o linie sau coloana si urmatorul element ca valoare, din linia sau coloana respectiva. Pentru diferenta cea mai mare, de pe o linie sau de pe o coloana, se aloca variabilei corespunzatoare celui mai mic cost unitar, din acea linie sau coloana, o valoare egala cu valoarea minima dintre cantitatile disponibila si necesara. Se suprima linia sau coloana pe care nu se mai poate interveni si se repeta procedeul in tabelul redus.

                 In general, nu se poate concluziona care dintre metode este recomandabil a fi folosita, alegerea fiind influentata de datele initiale ale problemei de utilizat.

Metoda potentialelor pentru determinarea solutiei optime

Fie problema de transport in forma standard:

                                                            (4)

Se scrie duala acestei probleme astfel: fiecarei restrictii de tipul (2a) i se asociaza o variabila si fiecarei restrictii de tipul (2b) variabila . Cum fiecare variabila apare o singura data in (2a) si o singura data in (2b), duala va avea forma:

                                                          (5)

Duala unei probleme de transport sugereaza ca se incearca transportarea unor cantitati de bunuri astfei incat diferenta dintre pretul unitar ui la sursa (depozit) si pretul unitar la destinatie vj sa nu depaseasca costul unitar de transport cij , intre punctul de plecare si cel de sosire.

Notand , respectiv  componentele solutiilor optime ale celor doua probleme, din teoria ecarturilor complementare, rezulta:

                                                (6)

Pornind de la o solutie de baza nedegenerata, unde exista m + n – 1 componente xij > 0, solutia va fi optima daca:

                                                                                   (7)

pentru toate rutele (i, j) pentru care xij > 0.

Relatiile (7) reprezinta un sistem de m + n – 1 ecuatii cu m + n necunoscute ui si vj, care se rezolva dand uneia dintre necunoscute o valoare arbitrara, de exemplu u1 = 0.

Algoritmul de rezolvare a unei probleme de transport prin metoda potentialelor, pornind de la o solutie admisibila de baza nedegenerata, presupune urmatoarele etape:

Etapa 1. Se asociaza fiecarei linii a tabelului unei probleme de transport cate o variabila ui si fiecarei coloane cate o variabila vj. Pentru casutele care corespund variabilelor de baza se construieste sistemul:  si se rezolva.

Etapa 2. Se calculeaza marimile.

a.    Daca , atunci solutia admisibila de baza este solutie optima a problemei date.

b.    Daca, solutia initiala nu este solutie optima si trebuie imbunatatita. Se trece la etapa 3.

Etapa 3. Se determina. Pornind din casuta (l, k) se construieste un circuit (un lant inchis) format din casute ale tabelului, care trece numai prin pozitii (i, j) carora le corespunde o cantitate xij > 0, prin treceri alternative pe linii si respectiv coloane, astfel incat sa se asigure intoarcerea in casuta (l, k) din care s-a pornit.

Se noteaza casutele din circuit, alternativ cu “+” si “-“, intr-un sens oarecare (de exemplu invers trigonometric), incepand cu casuta (l, k).

Etapa 4. Pentru casutele notate “-“se examineaza cantitatile xij si se determina valoarea minima, notata , a acestor valori. Se aduna valoarea  la cantitatile xij aflate in casutele notate”+” si se scade  din cantitatile xij aflate in casutele notate “-“. Se obtine o noua solutie admisibila de baza deoarece in casuta (l, k) a aparut o componenta pozitiva , iar una dintre componentele solutiei initiale a devenit nula. Se reia algoritmul de la etapa 1, pentru a verifica daca noua solutie este optima sau nu.

Exemplu Sa se afle costul minim de transport pentru problema ale carei date initiale sunt date in tabelul 2.

Consideram solutia admisibila de baza obtinuta prin metoda elementului minim din tabel. Solutia este prezentata in tabelul 5.

                                                                                       Tabelul 5

Bj

Di

B1

B2

B3

B4

B5

di

D1

90

10

120

37

140

-

80

28

60

45

120

D2

100

-

140

35

70

75

120

-

90

-

110

D3

60

70

160

-

130

-

140

-

100

-

70

bj

80

72

75

28

45

Etapa 1. Se verifica daca solutia admisibila de baza este solutie optima.

Se ataseaza fiecarei linii a tabelului 1.49 o variabila ui si fiecarei coloane o variabila vj si se scrie sistemul ui + vj = cij, considerand numai casutele (i, j) pentru care variabilele xij > 0:

    Se rezolva sistemul pentru u1 = 0. Rezulta:  

Etapa 2. Se calculeaza:. Aceste valori se inscriu intr-o matrice, cu m linii si n coloane.

Observatie. Evident, pentru pozitiile (i, j) corespunzatoare componentelor nenule ale solutiei admisibile de baza,.

Matricea este urmatoarea:

vj

ui

v1

v2

v3

v4

v5

u1

0

0

-90

0

0

u2

10

0

0

-20

-10

u3

0

-70

-110

-90

-70

Deoarece exista o valoare si anume, solutia admisibila de start nu este solutie optima si trebuie imbunatatita.

Etapa 3. Avand o singura valoare, ea este si valoarea maxima a diferentelorstrict pozitive. Vom forma un circuit incepand din casuta corespunzatoare acestei valori maxime, adica din casuta (2, 1), deplasandu-ne in sus pe coloana 1, pana la casuta (1, 1), apoi la dreapta pe linia 1 pana la casuta (1, 2), in jos pe coloana 2 pana la casuta (2, 2) si la stanga pe linia 2, inchizand circuitul in aceeasi casuta din care am pornit, casuta (2, 1).


Inscriem in casutele circuitului valorile componentelor solutiei initiale si notam colturile acestuia alternativ cu “+” si “-“, in sens invers trigonometric, incepand cu casuta de pornire, casuta (2, 1).


Etapa 4. Pentru casutele notate “-“se examineaza cantitatile xij si se determina valoarea minima,, a acestor valori. Se aduna valoarea  la cantitatile xij aflate in casutele notate”+” si se scade  din cantitatile xij aflate in casutele notate “-“.

si

S-a obtinut o noua solutie, noi valori  avand componentele corespunzatoare casutelor circuitului. Raman nemodificate componentele corespunzatoare casutelor din tabelul initial (tab. 1.49), care nu apartin circuitului considerat. Noua solutie admisibila de baza este prezentata in tabelul 6.

                                                                              Tabelul 6

Bj

Di

B1

B2

B3

B4

B5

di

D1

90

-

120

47

140

-

80

28

60

45

120

D2

100

10

140

25

70

75

120

-

90

-

110

D3

60

70

160

-

130

-

140

-

100

-

70

bj

80

72

75

28

45

Se verifica daca aceasta noua solutie este solutie optima sau nu, reluand algoritmul de la etapa 1.

  Se rezolva sistemul pentru u1 = 0. Rezulta:

Matricea este urmatoarea:

vj

ui

v1

v2

v3

v4

v5

u1

-10

0

-90

0

0

u2

0

0

0

-20

-10

u3

0

-60

-100

-80

-60

                 Deoarece, solutia obtinuta este solutie optima pentru problema data.

Asadar:                        

Valoarea minima a costului total de transport este:

u.m.

Observatii

1.    Daca pentru solutia optima exista, pentru (i, j) indici in afara bazei, se poate obtine o noua solutie optima  plecand de la casuta (i, j) si aplicand etapele 3 si 4 ale algoritmului. In acest caz, problema are solutie optima multipla.

2.    Daca in matricea Δ exista mai multe diferente pozitive, de valoare egala, vom alege, pentru a incepe circuitul, acea ruta careia ii corespunde in tabelul initial costul unitar cel mai mic.

3.    Exista probleme practice ce conduc la un model al problemei de transport in care se cere maximizarea functiei obiectiv. Aflarea unei solutii admisibile de baza prin metodele: elementului minim pe linie, elementului minim pe coloana si elementului minim din tabel devin metodele elementului maxim: pe linie, pe coloana sau in tabel si se aplica pornind de la valoarea cea mai mare a coeficientului cij de pe linie, coloana sau tabel. Metoda coltului Nord-Vest se aplica fara nici o modificare.

Calculul diferentelor se face dupa relatia:

 

iar conditia de optim este aceeasi: .

4.    Exista situatii in care anumite rute intre furnizori si consumatori nu pot fi folosite, cel putin temporar. Rezolvarea acestor probleme se face cu un model de transport obisnuit, in care rutelor interzise li se asociaza costuri de transport foarte mari in raport cu costul rutelor utilizabile. Prin aceste costuri foarte mari, algoritmul de rezolvare este fortat sa ocoleasca rutele interzise.

5.    In rezolvarea unei probleme de transport, poate apare o solutie admisibila de baza degenerata, caz in care nu se poate aplica metoda potentialelor pentru aflarea solutiei optime. Evitarea acestui lucru se face aplicand metoda perturbarii, ce consta in reformularea problemei, punand:

Cu aceste date se determina solutia initiala de baza ale carei componente depind de. Se pune conditia ca si se vor obtine componente bazice nule, care se trateaza ca si cand ar fi pozitive.

Exemplu Se da problema de transport prezentata in tabelul urmator :

Bj

Di

B1

B2

B3

B4

di

D1

4

2

5

4

100

D2

6

7

3

8

100

D3

3

5

4

5

100

bj

110

90

50

50

Pentru aflarea unei solutii admisibile de baza se aplica metoda elementului minim in tabel. Solutia obtinuta (tab.7) are 5 componente nenule, deci este o solutie degenerata, deoarece o solutie nedegenerata ar fi trebuit sa aiba m + n – 1 = 3 + 4 – 1 = 6 componente nenule.

Se aplica metoda perturbarii:

                                                                        Tabelul 7

Bj

Di

B1

B2

B3

B4

di

D1

4

10

2

90

5

-

4

-

100

D2

6

-

7

-

3

50

8

50

100

D3

3

100

5

-

4

-

5

-

100

bj

110

90

50

50

Se aduna la fiecare cantitate disponibila di o valoare , considerata foarte mica. Pentru echilibrarea problemei adunam  la cantitatea necesara unui beneficiar (de exemplu beneficiarului B4).

Problema reformulata este prezentata in tabelul 8.

                                                                        Tabelul 8

Bj

Di

B1

B2

B3

B4

di

D1

4

2

5

4

D2

6

7

3

8

D3

3

5

4

5

bj

110

90

50

Solutia initiala de baza se afla aplicand tot metoda elementului minim din tabel si este prezentata in tabelul 9.

                                                                        Tabelul 9

Bj

Di

B1

B2

B3

B4

di

D1

4

2

5

-

4

D2

6

-

7

-

3

50

8

D3

3

5

-

4

-

5

-

bj

110

90

50

Se da lui  valoarea zero si se obtine o solutie cu componenta x14 = 0, pe care o tratam ca si cand ar fi pozitiva. Solutia de baza obtinuta este prezentata in tabelul 10 si este considerata o solutie nedegenerata.

Se poate aplica, in aceste conditii, metoda potentialelor pentru a gasi solutia optima a problemei de transport data.

                                                                        Tabelul 10

Bj

Di

B1

B2

B3

B4

di

D1

4

10

2

90

5

-

4

0

100

D2

6

-

7

-

3

50

8

50

100

D3

3

100

5

-

4

-

5

-

100

bj

110

90

50

50



loading...




Copyright © 2017 - Toate drepturile rezervate

Matematica


Statistica


Metoda sirului lui Sturm
Legi ale numerelor mari si teorema limita centrala
Reducerea ecuatiei unei cuadrice la forma canonica
Istoria matematicii
Prisma
Rezolvarea numerica a ecuatiilor algebrice si transcendente
LUCRARE SCRISA LA MATEMATICA
Functii convexe, concave
Analiza factoriala a variantei
Colinearitate, concurenta, paralelism calcul vectorial in geometria plana












loading...