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
» PROBLEME DE TRANSPORT optimizata si analizata matematic


PROBLEME DE TRANSPORT optimizata si analizata matematic


PROBLEME DE TRANSPORT

In contextul problemelor de optimizare un loc special il ocupa problemele de transport, datorita multiplelor posibilitati de aplicare in diverse sectoare ale activitatii economico-sociale. In cvasitotalitatea activitatilor economice trebuie sa se apeleze la utilizarea unor algoritmi pentru rezolvarea problemelor de transport, deoarece transportul reperelor (produselor) de la furnizori (producatori) la beneficiari (consumatori) cu costuri cat mai reduse (eventual minime) nu poate fi realizat altfel decat facand apel la acesti algoritmi.

1. 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.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, .

1.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 (Pi , Cj) are capacitatea min(ai, bj), 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.

1.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 xpq valoarea maxima compatibila cu restrictiile din (1), adica:

.

Sunt posibile trei situatii:

(i). ap < bq, caz in care avem , toate celelalte elemente ele liniei p fiind nule, , deoarece disponibilul centrului Pp a fost epuizat. Noua valoare a lui bp va fi bp¬bp – ap, 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). bq < ap, deci , , solicitarea consumatorului Cq fiind satisfacuta, iar disponibilul in centrul Pp fiind ap¬ap-bq.

(iii). ap = bq, deci , , . In acest caz se obtine un program degenerat. Deseori daca se suprima linia p se inlocuieste bq cu bq+e, noul bq fiind bq¬(bq+e)-bq=e , iar daca se suprima coloana q se inlocuieste ap cu ap+e, noul ap fiind ap¬(ap+e)-ap=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.

1. 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  Daca  atunci scrie programul este optim

                                                                        altfel rezolva subproblema (IP).

1.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 (i1, j1). Variabila xkl 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  Se determina valoarea variabilei xpq, 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 xpq 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 xpq, 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 Pm+1, caruia i se atribuie un disponibil egal cu excedentul cererii fata de oferta, adica:

            .

            Costurile , asociate variabilelor xm+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 Cn+1, caruia i se atribuie un consum egal cu excedentul ofertei fata de cerere, adica:

            .

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

            2. PROBLEME GENERALIZATE DE TRANSPORT

            Prezentam in continuare cateva dintre cele mai reprezentative generalizari ale problemei de transport, mentionand de fiecare data aspectele deosebite pe care le ridica rezolvarea celor trei subprobleme mentionate mai sus si care le disting de problema standard.

2.1. PPOBLEMA DE TRANSPORT CU CENTRE INTERMEDIARE

Presupunem ca produsele realizate de  producatori   in cantitatile respectiv, sunt transportate la   depozite   de capacitati ,  produse ce urmeaza a fi transportate la consumatori  , care solicita cantitatile  , respectiv.

Daca  sunt costurile de transport ale unei unitati de produs de la  la  , iar  sunt costurile unitare de transport de la  la  se cere sa se determine un plan optim de transport, adica valorile necunoscutelor  ce reprezinta cantitatile de produs ce urmeaza a fi transportate de la producatorii  la depozitele  si ale necunoscutelor  ce reprezinta cantitatile de produs ce urmeaza a fi transportate de la depozitele  la consumatorii .

            Modelul problemei formulate este:

                                                              (6)

                              

            Modelul (6) este echivalent cu doua modele de tipul (1) si admite solutii in ipoteza ca sunt satisfacute conditiile:

                       (7)

            Cele doua modele echivalente cu modelul (6) sunt (8) si (9).

                                                                                 (8)

           

                                                                                (9)

           

            2.2. PROBLEMA DE TRANSPORT CU CAPACITATI LIMITATE

            In multe situatii economice concrete capacitatile rutelor de transport sunt limitate, limitarile fiind impuse din diverse considerente tehnico-economice.

            Modelul unei asemenea probleme este urmatorul:

                                                    (10)          Echivalentul relatiei (2) care asigura existenta programelor pentru problema (10) sunt, de aceasta data, relatiile (11):

                                                                        (11)

In acest caz subproblemele DPBI si TOPB comporta modificari, in timp ce subproblema IP ramane neschimbata.

Subproblema DPBI consta in atribuirea variabilei xpq a valorii cu mentiunea ca variabila xpq este considerata variabila de baza numai in cazul in care sau .

Datorita restrictiilor este posibil ca vectorul  sa nu fie program, deoarece este posibil ca disponibilul de produs sa nu fie complet epuizat, sau necesarul de produs sa nu fie complet satisfacut. Se poate arata ca in conditiile (7) pornind de la programul se poate determina un program de baza. Presupunem ca in centrul de productie Pk a ramas neexpediata cantitatea de produs K, iar in centrele de consum Ch si Cl sunt necesare cantitatile H respectiv L. Deoarece cererea este egala cu oferta rezulta ca K = H + L.

2.3. MODELE TRIDIMENSIONALE DE TRANSPORT

           Problemele de organizare optima a transporturilor necesare pentru aprovizionarea consumatorilor cu mai multe produse diferite conduc la modele matematice ale caror variabile sunt marcate cu trei indici. Presupunem ca producatorii  dispun de produsele  ,  solicitate de consumatorii . Daca se cunosc cantitatile:

 cantitatea totala de produse expediate de producatorul

 , consumatorului ;

cantitatea de produse , necesare consumatorului ;

 cantitatea de produse  , disponibile la producatorul ;

si se noteaza cu:

 costul transportului unei unitati de produs  de la producatorul  la consumatorul ;

 cantitatea din produsul  primita de consumatorul  de la producatorul ; modelul standard al problemei de transport tridimensionale este urmatorul:

                       

                                         (12)

            Problema de transport al carei model este (12) admite programe daca sunt indeplinite conditiile (13):

                                       (13)

    

                                                                                                                 



loading...




Copyright © 2017 - Toate drepturile rezervate

Matematica


Statistica


Ecuatia si inecuatia de gradul I
Ecuatia caracteristica
Functii surjective
Proiect didactic “micul oras” - activitate matematica
Algoritmi de sortare
Aplicatii ale trigonometriei sferice in geodezie si astronomie
Minimizarea functiilor booleene cu ajutorul diagramelor veitch-karnaugh
Despre analiza de regresie
Probabilitati: definire, probabilitati conditionate, variabile aleatoare continue si discrete. Legea numerelor mari, teorema limita centrala, inegalit
Functii convexe, concave












loading...