![]() | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
Istorie | Literatura | Matematica | Psihologie |
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+n
mn 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)
Copyright © 2023 - Toate drepturile rezervate