PROGRAMAREA LINIARA TIP TRANSPORT

PROGRAMAREA LINIARA TIP TRANSPORT

Un caz particular al programarii liniare este atunci cnd activitatile si resursele se exprima in unitati de masura de acelasi fel , caz in care problema se numeste tip transport.

Modelul matematic al problemei de transport este :

Daca egalitatea nu este satisfacuta se adauga, pentru echilibrare, un consumator respectiv un producator suplimentar care are coeficientii de cost zero.

Remarcam ca functia obiectiv cere numai minim .

Modelul este denumit tip Transport pentru ca ofera solutii unor probleme formulate astfel:

Se dau:

cantitatile disponibile la furnizori pentru un produs omogen:

necesarul de aprovizionat al consumatorilor aceluiasi produs;

costurile unitare de transport intre furnizori si consumatori.

Se cere sa se intocmeasca un program de transport care sa satisfaca necesarul consumatorilor cu un cost total minim.Dat fiind aplicatiile numeroase si importante ale modelului in optimizarea transportului feroviar, vom studia cateva metode pentru calcularea optimumului.

Metoda Nord Vest pentru aflarea unei solutii initiale de baza .

Se da in tabel necesarul si disponibilul unui produs omogen precum si costurile unitare de transport sau distantele dintre furnizori si consumatori.

Se cere gasirea unei repartizari ca pe total costul sa fie minim .

Se porneste din campul din colt stanga sus ( pe o harta coltul N-V ) si se aloca valoarea minima dintre disponibil si necesar, in cazul nostru valoarea minima dintre 5 si 7. S-a satisfacut necesarul si au mai ramas 2 unitati disponibile , se face acelasi rationament pentru campul alaturat si asa mai departe obtinandu-se alocarea din tabel.

Costul total dupa alocarea obtinuta adica valoarea functiei obiectiv este :

f=5x19 + 2x30 + 6x40 + 3x40 + 4x70 + 14x20 = 1015

Metoda elementului minim al matricei costurilor consta in executarea alocarilor in campurile in ordinea crescatoare a costurilor .

Metoda nu da o solutie optima ci una imbunatatita fata de metoda NV.

Valoarea functiei obiectiv este :

f = 7x40 + 7x10 + 2x70 + 3x40 + 8x8 + 7x20 = 814

Exemplu Laborator 1: Metoda diferentelor maxime sau Vogel (nu garanteaza optimul)

1. Se scade pe fiecare linie elementul de valoare minima Cij din elementul imediat urmator ca marime si se adauga ca o coloana suplimentara ;

2. Se face aceeasi operatie pe coloane obtinandu-se o noua linie ;

3. Se alege din linie si coloana diferentelor de acelasi grad diferenta maxima si se cauta valoarea minima Cij din matrice careia i se atribuie Xij=min.(ai ;bj ) Coloana sau linia unde necesarul sau disponibilul s-a epuizat se scot din calculele urmatoare .

4. Se reincepe ciclul cu calculul noilor diferente de ordin superior .

Recalculam functia obiectiv :

f= 5x19 + 2x10 + 7x40 + 2x60 + 8x8 + 10x20 = 779

Exemplu Laborator:

Metoda ciclurilor sau distributiva garanteaza obtinerea solutiei optime.

De obicei se porneste de la o solutie obtinuta prin metoda Vogel care se verifica si eventual se imbunatateste prin metoda ciclurilor astfel ca pentru rezolvare sunt pasi de calcul mai putini. Din ratiuni didactice in cele ce urmeaza vom folosi o solutie obtinuta prin metoda elementului minim al matricii costurilor. f= 7x10 + 2x70 + 7x40 + 3x40 + 8x8 + 7x20 = 814

Numarul furnizorilor m=3, numar de clienti n=4

Regula: La fiecare pas de calcul trebuie ca numarul de alocari nenule sa fie m+n-1(se scade 1 deoarece variabilele sunt legate deja prin ec. de echilibru). In cazul in care numarul de alocari nenule este mai mic decat m+n-1 solutia este degenerata si nu se vor putea inchide toate ciclurile.

Metoda de ridicare a degenerarii se va expune ulterior.

In continuare se calculeaza evolutia valoarii functiei obiectiv alocand cate o unitate in campurile fara alocare din matricea costurilor.

Pentru a pastra echilibrul alocarilor pe linii si coloane se scad si se aduna cate o unitate din alocari creindu-se ciclurile dupa cum urmeaza. Sensul de parcurgere al ciclurilor este indiferent.

Se poate imbunatati solutia repartizand cantitati in campurile 1,1 si 2,2. Avantajos este campul (1,1) deoarece d11 < d22. (converge mai rapid catre optim). Alocarea se face dupa regula:

Se aloca minimumul gasit cu semn negativ pe ciclul a carui suma este negativa. Ciclul ales este iar noua matrice devine:

Valoarea functiei obiectiv devine astfel:

f= 5x19 + 4x10 + 2x70 + 7x40 + 8x8 + 10x20 = 781

Se fac din nou alocari in campurile care nu fac parte din solutie.

Se mai poate aloca in campul (2,2) asa cum se vede schematic pe ciclul:

Noua solutie este :

f= 5x19 + 2x10 + 2x30 + 7x40 + 6x8 + 12x20 = 743

Se evalueaza din nou alocari in campurile nealocate :

Solutia nu se mai poate imbunatati deoarece noile alocari sunt toate pozitive . Valoarea functiei obiectiv pentru solutia optima este deci:

Z = 5x19 + 2x10 + 2x30 + 7x40 + 6x8 + 12x20 = 743

PROBLEMA DEGENERARII

Metoda ciclurilor cere ca la fiecare pas de calcul numarul alocarilor nenule trebuie sa fie m+n-1 (minus 1 arata ca variabilele sunt legate si prin conditia de echilibru, deci nu sunt total independente) .

Daca numarul alocarilor nenule este mai mic decat m+n-1 atunci solutia este degenerata cu consecinta ca nu se vor putea inchide toate ciclurile si deci nu se poate continua algoritmul in vederea obtinerii solutiei optime.

Iesirea din degenerare se face prin alocari suplimentare nule, denumite zeroruri esentiale, in campurile de costuri minime ramase nealocate. Zerorurile esentiale sunt socotite ca alocari nenule.

Alocari de zerouri esentiale se face pana cand se satisface conditia ca numarul de alocari nenule sa fie egal cu m+n-1.

In metoda ciclurilor, la realocarile pe ciclul de valoarea negativa, se vor mentine zerouri esentiale in campurile care raman fara alocare astfel ca noua solutie obtinuta sa nu fie degenerata.

Exemplu, sa presupunem ca pe parcursul aplicarii metodei ciclurilor se obtine solutia intermediara de forma:

Evaluam campurile nealocate:

O alocare in campul d24 mai poate imbunati solutia dupa schema:

In noua solutie apare o alocare noua in campul 2,4 si dispar alocarile din campurile 2,1 si 3,4. Solutia obtinuta astfel este degenerata. Pentru evitarea degenerarii, se pastreaza un zero esential in campul 3,4.

Ridicarea degenerarii se mai poate face si prin adaugarea la coloana de disponibil a unei valori mici ( (epsilon) astfel ca in solutia perturbata sa gasim campul unde trebuie sa se faca alocarea unui zero esential.

Exemplu: sa presupunem ca dupa o alocare obtinuta prin metoda elementului minim al matricii costurilor obtinem:

Solutia obtinuta este degenerata deoarece sunt numai 5 alocari fiind necesare 6. Se adauga cantitati infinit mici, (epsilon) la coloana de disponibil echilibrand pe linia de necesar obtinandu-se matricea:

Se incearca din nou sa se gaseasca o solutie initiala de baza prin metoda elementului minim al costurilor si se obtine:

Se egaleaza infinitul mic cu zero si se obtine matricea

Se observa ca in ultima matrice sunt 6 alocari deci s-a rezolvat degenerarea aparand un zero esential in campul 3,4.

Exemplu Laborator 2: Metoda acoperirii zerourilor.

Metoda permite obtinerea unei solutii optime fara a fi necesara o solutie initiala de baza. Reluam acelasi exemplu :

Se scad minorantii ( valorile minime) pe linii si coloane in matricea costurilor si se obtine M2 si M3.

Inventariem toate modurile distincte de a taia liniile si coloanele care contin zerouri cu un numar minim de linii .

Enumerarea modurilor de taiere a liniilor se face similar ca inventarierea multimii partilor unei multimi.

Se fac sumele necesarului si disponibilului pentru toate modurile de taiere a zerourilor inventariate mai inainte.

Se taie liniile si coloanele din Sk min. Adica S1 .

Se cauta elementul minim dintre cele netaiate (cazul de fata 12)

- se aduna la elementele dublu taiate;

- se scade din cele netaiate;

- restul ramin neschimbate .

Inventariem din nou modurile cum se pot taia zerourile si calculam sumele SK .

In matricea M5 numai pozitiile campurilor ce contin zero sunt relevante deoarece numai in aceste campuri se fac alocari. Se aloca cantitati incepand cu zero-urile unice pe linii sau pe coloane, dupa regula Xij =min (ai ,bj).

Revenim la matricea initiala a costurilor pe care se pune alocarea optima.

Valoarea optima a functiei obiectiv este:

fmin = 5x19 + 2x10 + 2x30 + 7x40 + 6x8 + 12x20 = 743

In cazul cand problema nu este echilibrata adica total necesar este diferit de total disponibil adica:

In acest caz se introduce un necesar fictiv si apare o noua coloana cu coeficientii tehnici zero care echilibreaza necesarul cu disponibilul .

La aceasta matrice se gaseste solutia cu unul din algoritmii cunoscuti.

Se introduce un disponibil fictiv sub forma unei linii suplimentare cu coeficientii tehnici nuli rezolvandu-se similar.

DIRIJAREA VAGOANELOR GOALE

Este cunoscut ca in majoritatea statiilor de cale ferata nu exista echilibru intre numarul vagoanelor descarcate cu cele incarcate sau chiar daca acest echilibru exista, vagoanele descarcate sunt de o categorie iar pentru incarcare este necesara o alta categorie. Exemplu in statie se descarca vagoane materiale de constructii din vagoane descoperite si se incarca ceriale in vagoane acoperite, deci este excedent de vagoane descoperite si necesar de vagoane acoperite.

Se impune deci o dirijare a vagoanelor goale excedentare pentru a acoperi deficitulin alte statii. Cursa goala a vagonului nu este productiva deci trebuie redusa la minimum posibil .

Se procedeaza astfel:

-Se imparte reteaua de caleferata in zone (cca 120) ;

-Se stabileste pentru fiecare categorie de vagon volumul de incarcari si descarcari pe decada , luna etc.

Dk , Ik , k=1,2,.120

Daca :

Dk > Ik zona k este excedentara in vag.goale

deci

Dk-Ik = bj j=1,2,m

Dk < Ik zona k este deficitara in vag.

Ik-Dk =ai I=1,2,.n

Cunoastem distantele kilometrice intre zone :

Evident ca trebuie sa se realizeze relatia :

La CFR s-au obtinut rezultate in acest domeniu pentru o dirijare cadru decadica. Pentru o dirijare mai operativa sunt necesare mijloace mai eficace de urmarire a vagoanelor precum sistemele informatice in timp real.

BIBLIOGRAFIE

1. Dinescu C., Savulescu B., Metode matematice si aplicatii pentru optimizarea problemelor din economie. Ed. Didactica si Pedagogica Bucuresti 1976.

2. Dinescu C., Savulescu B., Initiere in matematica aplicata. Ed. Albatros, Bucuresti 1984.

3. Ionescu H, Dinescu C, Burlacu V., Teoria grafelor cu aplicatii in economie, Editura stiintifica, Bucuresti, 1969.

4. Ionescu H, Dinescu C, Savulescu B, Probleme ale cercetarii operationale. Ed. Didactica si Pedagogica Bucuresti 1972.

5. Kaufmann A., Metode si modele ale cercetarii operationale Vol 1 si 2, Ed. Stiintifica, Bucuresti, 1967.

6. Malita M, Zidaroiu C. Matematica organizarii. Editura tehnica. Bucuresti 1975.

7. Pop D-tru., Elemente de programare liniara cu aplicatii, Editura militara, Bucuresti, 1972.

8. Postelnicu T, Dinescu C, Savulescu B, Matematici speciale aplicate in economie, Ed. Didactica si Pedagogica, Bucuresti 1977.

9. Vaduva I, Dinescu C, Savulescu B, Modele matematice de organizare si conducerea productiei, vol.1 si 2, Ed. Didactica si Pedagogica Bucuresti. 1974.

EMBED Equation.3

EMBED Equation.3

CONSUMATORDisponibilFURNIZOR1234ai119305010727030406093408702018Necesar bj5871434

5(19)2(30)76(30)3(40)94(70)14(20)185871434

---7(10)72(70)-7(40)-93(40)8(8)-7(20)185871434

{2}{1}{5}123455(19)30502(10)7, 29940400{4}70307(40)2(60)9, 21020202020408(8)7010(20)18, 101220[50]00{3}58714, 4, 234121[22]10102[21]01010300101040010[50]500[40]60

---7(10)72(70)-7(40)-93(40)8(8)-7(20)185871434

EMBED Equation.3

3(19)30504(10)72(70)307(40)609408(8)7010(20)1858714

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

5(19)30502(10)7702(30)7(40)609406(8)7012(20)1858714

EMBED Equation.3

20(4)155(6)701040(8)10(10)50151830(12)802520(8)2024106848

EMBED Equation.3

EMBED Equation.3

20(4)155(6)70104010(10)5015(8)1830(20)802520(0)2024106848

Disp193050107(M1)703040609408702018Nec58714

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

M4

EMBED Equation.3

M5

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

5(19)30502(10)7702(30)7(40)609406(8)7012(20)1858714

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

193050100127030406009408702001858714539

EMBED Equation.3

EMBED Equation.3

20(4)155(6)70104010(10)5015(8)1830(8)8025202024106848

201557010+4010501518+3080252020+241068+348+

20(4+)155(6)7010+4010(10)5015(8+)18+30(20-)802520(2)20+241068+348+

20(4)155(6)70104010(10)5015(8)1830(20)802520(0)2024106848

18R.Cazacu, CIT- Note de Curs

Rev.20-Apr-05 (6,7)

_1116396736.unknown

_1142328839.unknown

_1143978608.unknown

_1143978733.unknown

_1143980752.unknown

_1142330160.unknown

_1118220286.unknown

_1118220336.unknown

_1118047466.unknown

_1118216726.unknown

_1118049777.unknown

_1118046142.unknown

_1116316335.unknown

_1116317055.unknown

_1116319667.unknown

_1116322388.unknown

_1116322899.unknown

_1116320248.unknown

_1116319483.unknown

_1116316527.unknown

_1116312502.unknown

_1116315554.unknown

_1116311001.unknown