probleme de transport ppt

7/21/2019 Probleme de Transport ppt

http://slidepdf.com/reader/full/probleme-de-transport-ppt 1/17

PROBLEME DETRANSPORT

CURSUL 12



Obiective: Acest capitol urmăreşte familiarizarea studenilor cu problemele de

transport! probleme ce prezintă o importana deosebită "n optimizarea numeroaselor proceseeconomice# O problemă de transport poate consta "n crearea unui plan de transport pentruunul sau mai multe produse de la unul sau mai multe centre furnizoare! "n scopul satisfaceriicerinelor unor consumatori si cel al minimizării c$eltuielilor de transport#

%roblemele de tip transport se "nt&lnesc "n multe procese economice! ca de e'emplu:

transporturi de bunuri( proiectarea de canale de ener)ie sau informaii sau de ce nu de canalede iri)a ii "n a)ricultură( proiectarea de depozite "n acelaşi spaiu productiv( repartiia optimăț

a sarcinilor de producie pe maşini! secii! "ntreprinderi! optimizarea unor probleme de producie şi stoca* etc#

Rezumat: +odelul matematic al problemelor de transport se "ncadrează "n modelul

problemelor de pro)ramare liniară# Av&nd "n vedere numărul mare de variabile! rezolvareaunei probleme de transport prin al)oritmul simple' este "n )eneral puin eficientă# ,e aceea! pentru rezolvarea problemelor de tip transport se folosesc te$nici speciale# Acest capitol estededicat prezentării acestor te$nici sub o formă mai simplă#



Modelul matematic pentru o problemă de transport

-iind date m centre de aprovizionare cu bunuri! notate ,i! .i/1!m0! şi n centre dedesfacere! notate C *! .*/1!n0! problema de transport este problema care caută să minimizezecostul total al transportului bunurilor de la centrele de aprovizionare ,i la centrele dedesfacere C *# ransportul se poate efectua de la oricare centru ,i către oricare centru C *!e'ist&nd un cost unitar ci*! al transportului unui bun de la centrul ,i către centrul C *# Astfel!

costul total al transportului este proporional cu cantitatea de bunuri transportate "ntre sursăşi destinaie#

Ĩntr-o problemă de transport, datele problemei sunt furnizate deobicei sub forma tabelului de mai jos:



&acă problema nu este ec'ilibrată, aceasta se poate ec'ilibra prinintroducerea unor centre (cti)e care să conducă la realizarea rela*iei# 2 $,prin adăuarea unor depozite sau centre (cti)e "i considerarea costurilorunitare de transport de la sau către acestea ca (ind nule &e exemplu,

dacă: atunci se adauă un depozit (cti), &m+1 care are undisponibil astfel nc.t:

iar costurile de transport de la ,m1

la C *

sunt nule: cm+1, j

= ! . */ 1!n0 O soluie posibilă.realizabilă0 a problemei! care conine cel mult .mn310 componente

strict pozitive! se numeşte soluţie de bază# Soluia de bază cu e'act .mn310 componente pozitive se numeşte soluie de bază nedeenerată! iar "n caz contrar! deenerată#

4n )eneral! pentru rezolvarea unei probleme de transport se parcur) etapele:a0 ,eterminarea .aflarea0 unei soluii iniiale .de bază! nede)enerată0(

b0 Ameliorarea ."mbunătăirea0 unei soluii(c0 Aflarea .determinarea0 soluiei optime#/roblema de transport (ind o problemă de proramare liniară se poaterezol)a cu ajutorul aloritmului 0implex &ar datorită structurii ei speciale,o astfel de problemă se poate rezol)a mai rapid "i mai simplu prinaloritmi speci(ci /entru aarea unei solu*ii ini*iale intr-o problemă de

transport se cunosc mai multe metode n cele ce urmează )om prezentatrei metode: metoda col*ului de 3ord-4est, metoda elementului minim si



!" METODA #OL$%L%! NORD& 'EST

Metoda colţului de nord-vest presupune parcurgereaurmătoarelor etape:1#Se porneşte din colul cel mai de nord3vest! respectiv din celula 5.i!*0 i/1 şi */16#2#Se atribuie acestei celule valoarea cea mai mică "ntre disponibilul şi necesarulcorespunzătoare centrelor ,i şi C *! respectiv valoarea 'i* / min.ai!b *0#7#Se reduce disponibilul .oferta0 şi necesarul .cererea0 de pe această linie şi coloană cu valoareaalocată celulei .i!*0# ,acă 'i* / a i atunci se suprimă linia i# ,acă 'i*/b *! se suprimă coloana *# 8a

rezulta un tabel cu o linie sau coloană mai puin# Se ale)e "n continuare următoarea celulă aflată"n colul cel mai de nord3vest! şi se repetă procedeul de la pasul 2! p&nă c&nd au fost satisfăcutetoate cerinele .restriciile0#

E(emplu )

Se dă problema de transport cu datele ini iale prezentate n tabelul 1:ț ȋ

Tabelul *



Se da necunoscutei '11 .situata in coltul din stan)a3sus0 valoarea: '11 / min .9! 120 / 9! restulnecunoscutelor coloanei 1 fiind nule .cantitatea necesara beneficiarului ;1 a fost asi)urata0#<n depozitul ,1 a mai ramas o cantitate disponibila e)ala cu: 12 = 9 / >#

?12 / min .>! @20 / > ?27 / min .@! @90 / @ ?7> / min .2! @0 / 2?22 / min .72! 110 / 72 ?2> / min .29! 70 / 7 ?7 / min .>! >0 / >

Solutia obtinuta este prezentata in tabelul 2#

S3a obtinut o solutie de baza admisibila cu sapte componente nenule:'11 / 9( '12 / >( '22 / 72( '27 / @( '2> / 7( '7> / 2( '7 / >( solutia este nede)enerata deoareceare m n 31 / 7 3 1 / @ componente nenule#



8aloarea functiei obiectiv pentru aceasta solutie admisibila de baza este: u#m#Observatie# +etoda coltului Bord38est opereaza numai cu valorile di si b *! fara a lua in

consideratie costurile unitare ci*# ste evident ca un cost total minim al transportului se vaobtine utilizand rutele cu costuri unitare mici# %e aceasta observatie se bazeaza metodeleurmatoare de determinare a unei solutii admisibile de baza pentru problema de transport#

!!" METODA ELEMENT%L%! M!N!M

+etoda constă "n a atribui! pe r&nd! valori variabilelor necunoscute! "ncep&nd cu aceeala care costul unitar ci* este minim#Apoi din cele rămase se lucrează tot cu aceea care corespunde costului minim# ,acă sunt maimulte costuri minime e)ale! atunci se va considera mai "nt&i acea variabilă care poate luavaloarea mai mare# 8aloarea variabilei se va afla ca şi la metoda colului de Bord38est!

consider&nd minimul dintre disponibil si necesar#%entru problema de transport data in tabelul 1! se aplica metoda elementului minim din

tabel pentru aflarea unei solutii admisibile de baza# Solutia obtinuta este prezentata in tabelul. 7 0:



8aloarea functiei obiectiv este:

u#m#



!!!" METODA D!+EREN$ELOR M!,TE

8alorile variabilelor se atribuie ca şi "n cazul metodelor precedente! dar ordinea de

atribuire se face după o altă re)ulă# %entru stabilirea ordinii de urmat se calculează! pentrufiecare linie! respectiv pentru fiecare coloană! diferena dintre cele mai mici douăelemente.costuri0# Apoi pe linia sau coloana cu diferena ma'imă se determină variabileledin căsuă cu cost minim# Apoi procedeul se repetă# La diferene ma'ime e)ale se considerămai "nt&i costul minim#La lucrul cu tabelul diferenele pe linii se trec "n dreapta tabelului! iar cele pe coloanededesubtul tabelului#

abelul initial al problemei de transport se completeaza cu o linie in partea de *os si cuo coloana in dreapta! in care se vor calcula diferenele .tabelul >0# ,iferenta cea mai mare intre costul unitar minim si urmatorul cost unitar! ca valoare! estecorespunzatoare coloanei 7 si este e)ala cu D .c77 = c27 / D0#



<n coloana 7 se cauta elementul minim! care este c27 si se da variabilei '27 valoarea:min.11! @0 / @# Restul variabilelor de pe coloana 7 sunt nule! iar coloana 7 se suprima#Cantitatea disponibila in depozitul ,2 se recalculeaza: 11 = @/ 7#

Se repeta procedeul in tabelul redus .tabelul 0! format prin eliminarea coloanei ;7#

,iferenta cea mai mare intre costul unitar minim si urmatorul cost unitar! ca valoare! estecorespunzatoare atat liniei 7 cat si coloanei ># Se ale)e una dintre ele! de e'emplu! ceacorespunzatoare liniei 7# Cel mai mic cost unitar de pe linia 7 este c71# Se da variabilei '71 valoarea: min.@! 90 / @#oate celelalte variabile de pe linia 7 sunt e)ale cu zero! deoarece a fost epuizata intrea)acantitate disponibila in depozitul ,7#

Se elimina linia 7 si se recalculeaza necesarul beneficiarului ;1: 9 = @ / 1#



abelul D

Se repeta procedeul! obtinandu3se! succesiv! tabelele @! 9! E#Solutia finala este prezentata in tabelul 1#

abelul @



abelul 9 abelul E

abelul 1



8aloarea functiei obiectiv pentru aceasta solutie admisibila de baza este: u#m# Comparand valorile functiei obiectiv! pentru cele trei metode utilizate! se constata cavaloarea minima este obtinuta in cazul aplicarii metodei diferentelor mi'te! iar valoareama'ima in cazul metodei coltului nord3 vest#

<n )eneral! nu se poate concluziona care dintre metode este recomandabil a fi folosita!ale)erea fiind influentata de datele initiale ale problemei de utilizat#



Ameliorarea (îmbunătaţirea) unei soluţii

/entru a elabora un mod de ameliorare a unei solu*iicorespunzătoare unei probleme de transport, adică de a trece de la osolu*ie de bază la una mai bună, )om recure la problema duală/roblema de transport are modelul matematic dat de #1$ /entru a scrie

duala trabuie să introducem )ariabilele duale u1, u2,, um ,corespunzătoare primelor m restric*ii, "i )1, )2,, )n corespunzătoareurmatoarelor n restric*ii 5b*inem: u1 + )1 6 c11, u1 + )2 6 c12, , u1 + )n 6 c1n, u2 + )1 6 c21, u2 + )2 6 c22, , u2 + )n 6 c2n,

um + )1 6 cm1, um + )2 6 cm2, , um + )n 6 cmn

ui, i = 1, m, ) j, j = 1, n, arbitrare

#max$ = a1u1 + a2u2 + + amum + b1)1 + b2)2 + + bn)n



7eoremele de dualitate ne asiură că o solu*ie 8#!$ = #xij#!$$ i= 1,m% j= 1,neste

optimă dacă )ariabilele duale )eri(că restric*iile:

. 2 0 ui v * / ci*! daca 'i*.0 F .'i*.0 este necunoscuta principala0

. 7 0 ui v * G ci*! daca 'i*.0 / .'i*

.0 este necunoscuta secundara0numite condiii de optimalitate pentru soluia unei probleme de transport#

-ie 8 = #xij$ i= 1,m% j= 1 o soluie iniială a problemei de transport#Căsuele din tabelul soluiei cu 'i* F le numim căsue ocupate! iar cele cu 'i* / le

numim căsue libere#Relaiile. 2 0 formează un sistem liniar de m n 3 1 ecuaii .corespunzătoare căsuelorocupate0 cu m n necunoscute# Se observă că acest sistem este compatibil nedeterminat#%entru aflarea unei soluii putem lua o necunoscută secundară e)ală cu ! de obicei vomale)e u1 / #

4alorile ăsite pentru u1, u2,, um "i )1, )2,, )n se trec pe marinea

tabelului solu*iei n mod corespunzător #de aceea se mai numesc si )alorimarinale$, iar sumele ui + ) j se scriu n col*ul din dreapta sus alcăsu*elor ocupate, alături de coe(cien*ii cij, adică structura unei astfel decasu*e ocupate arată astfel :



Se trece la verificarea condiiilor de optimalitate . 7 0 pentru căsuele libere# ,acă toate

condiiile . 7 0 sunt "ndeplinite! atunci soluia iniială este optimă# ,acă cel puin ocondiie . 7 0 nu este verificată! atunci se trece la procesul de ameliorare ."mbunătăire0 asoluiei#

Bumim ciclu corespunzător unei căsue libere o succesiune de căsue ocupate! douăcate două alăturate pe aceeaşi linie! sau respectiv pe aceeaşi coloană! cu treceri alternative pe linii si coloane! succesiunea "ncep&nd imediat după căsua liberă si termin&ndu3se "nvecinătatea aceleiaşi căsue libere#

4ntr3un ciclu marcăm alternativ cu si = căsuele! "ncep&nd cu căsua liberă# Semnelese trec "n colul din st&n)a *os al căsuei#Ciclul se ale)e pentru căsua liberă corespunzătoare diferenei Hi* / ci* = . ui v * 0 cea maimare "n valoare absolută dintre diferenele Hi* I #

%entru "mbunătairea soluiei se determină valoarea minimă J pe care o iau 'i* dincăsuele marcate cu 3 # Apoi! valoarea minimă J se adună la valorile 'i* din căsuelemarcate cu şi se scade din valorile 'i* din căsuele marcate cu 3 #

%rin acest proces se obine o nouă soluie a problemei de transport! mai bună dec&tcea de la care am plecat#

probleme de transport ppt

Documents