lucrare ii co

8/16/2019 Lucrare II CO

1/4

1. Ce se înţelege prin « Problema atribuirii sarcinilor »? Formularea matematică.

Atribuirea optima a n sarcini la n specialist stiind ca:• unui specialist i se atribuie o singur ă sarcină,• sarcina este executată de un singur specialist,• profitul executării sarcinii j de către specialistul i este cij .Atribuirea este optimă dacă profitul obţinut este maxim .Trebuie sa determinam xij, i =1, n , j =1, n astfel incat:

xij trebuie sa ia valori 0 sau 12. Ce se înţelege prin “problema de transport”? Formularea matematică.

Problema de transport are totdeauna o solutie admisibila, anume:

si care este o solutie marginita de ai si bj. Exista in total n+m restrictii m ecuatii coresprestrictiilor date de centrele de aprovi!ionare si cele n ecuatii coresp restrictiilor date decentrele de consum" la care se adauga conditia de ec#ilibru

$e aici re!ulta ca una dintre restrictii este redundanta. %rice restrictie se poate exprima infunctie de celelalte m+n&1 ramase.

. !crieti “problema duală” asociată unei probleme de transport"

max ∑aiui+∑ b jv j"

ui + vi '( cij , 1'(i'(m , 1'(j'(n ui , vi &oarecare

#. Ce algoritmi pot $i $olosiţi pentru re%ol&area Problemei atribuirii sarcinilor ?


2/4

Pentru re!olvarea problemei de atribuire se poate folosi algoritmul de transportsau algoritmul primal−dual pentru problema de programare liniar ă.

'. Ce se înţelege prin “Problemă de programare liniară în numere întregi” ?

Formularea matematică a acesteia.

)n multe probleme de optimi!are se cere ca solu*ia s fie n numere ntregi. $e exemplu

ntr&o problem de produc*ie, unde se caut numrul optim de produse ce trebuie

reali!ate, acest numr este din ra*iuni practice ntreg -

∈∈∈

∈

=⋅

⋅′

nmnm Z c Z b Z M A

b A

,",

minmax"

,

n N x

x

x c

(. Ce metodă se poate aplica pentru re%ol&area “Problemei de programare liniară înnumere întregi”?

Pentru re!olvarea acestor probleme este adecvat metoda ranc# and ound.

). Care este principiul “*etodei +ranc, and +ound”?-tapa . /e determin o solu*ie a problemei de programare liniar fr a se *ine seama derestric*iile de integritate.-tapa a /a. 0ami$icarea. ranc#" /e alege o variabil i se divide spa*iul solu*iilor ndou subspa*ii. /e selectea! pentru investiga*ie un subspa*iu o ramur".-tapa a /a. *ărginirea. ound" /e gsete o margine pentru problema definit desubspa*iul selectat ramura selectat". )n ca!ul nostru se folosete solu*ia problemei de programare liniar ca margine. %bservm c marginea repre!int limita superioar, n problema de max, respectiv inferioar n problem de min, pentru toate solu*iile posibile pe acea ramur.-tapa a /a. Comparare. /e compar marginea ob*inut pe ramur considerat cu cea mai bun solu*ie 2 ob*inut p3n n aceast etap.

$ac marginea ob*inut nu este mai bun 2 dec3t cea mai bun solutie 2 re*inut p3n n

aceast etap, aceast ramur se abandonea! i se trece la investigarea altor ramuri care nuau fost nc investigate.

$ac marginea ob*inut este mai bun 2 dec3t cea mai bun solu*ie 2 re*inut p3n naceast etap i dac solu*ia este ntreag, atunci aceast margine devine cea mai bunsolu*ie 2 i se trece la investigarea altor ramuri care nu au fost nc investigate.


3/4

$ac marginea ob*inut este mai bun 2 dec3t cea mai bun solu*ie 2 re*inut p3n naceast etap i dac solu*ia nu este ntreag, atunci se continu investigarea pe aceastramur fiind anse s se gsesc o sol*ie mai bun 2. /e reia Etapa a 44&a.

-tapa a /a. Completare. 53nd toate ramurile au fost examinate, cea mai bunsolu*ie 2 este cea optima. /top -

/e poate ntocmi un arbore al metodei ranc# and ound pentru a urmri parcurgereasubspa*iilor solu*iilor, aa cum se va vedea n exemplele pre!entate n continuare.

. Ce se înţelege prin “0eţea de transport”?

3e$iniţie. O reţea de transport este un graf orientat ponderat,( )cu X G ,,=

, fără bucle, unde

fiecărui arc i se asociază un număr0" ≥uc

, numit capacitatea arcului u. n plus, o astfel dereţea !erifică "i următoarele ipoteze #

a$ %xistă un singur nod X s∈

, care nu are predecesori, toate celelalte a!&nd cel puţin un predecesor. Acest nod se nume"te sursă sau intrarea 'n reţea(

b$ %xistă unn singur nod X d ∈

, care nu are succesori, toate celelate a!&nd cel puţin un succesor. Acest nod se nume"te destinaţie sau ie"irea din reţea.

4. Ce este un $lu5 într/o reţea de transport?

3e$iniţie. )n flux f 'ntr*o reţea de transport este o funcţie care asociază fiecărui arc) u∈

o cantitate0" ≥u f

care reprezintă cantitatea de produs ce pote fi transportată prin arcul u, pro!enind de la sursa s către destinţia d.

16. Ce se înţelege prin $lu5 compatibil? 3ar prin $lu5 complet?

3e$iniţie. )n flux f este compatibil cu reţeaua( )cu X G ,,=

, dacă pentru

( )""0, ucu f ) u ≤≤∈∀

. Altfel spus, pentru fiecare arc u fluxul care 'l tra!ersează nutrebuie să depă"ească capacitatea arcului u.

3e$iniţie. 6n flux f este complet dacă pentru orice drum plec&nd de la sursa s ladestinaţia d există cel puţin un arc saturat, adică fluxul care 'l tra!ersează este egal cucapacitatea arcului.


4/4

11. C7nd un arc este saturat?fu"(cu"fu" &fluxulcu" 7 capacitatea

12. Ce se înţelege prin $lu5 ma5im într/o reţea de transport ?

+roblema de flux maxim consta in a gasi care e cantitatea maximă de flux care poatecircula de la sursa s la destinaţia d.

1. Ce se înţelege prin « lanţ care măre8te $lu5ul » într/o reţea de transport ?

3e$iniţie. )n lanţ care măre"te fluxul este un lanţ pentru care arcele 'n sens direct nu auatins limita lor maximă "i arcele 'n sens indirect au fluxul care le tra!ersează nenul.

1#. Ce algoritm se poate $olosi pentru determinarea $lu5ului ma5im într/o reţea detransport?

Algoritmul cel mai cunoscut pentru re!olvrea acestei probleme este algoritmul 8ord&8ul9erson.

1'. -&idenţiaţi c7te&a domenii de aplicare ale reţelelor de transport"

Astfel de probleme se nt3lnesc n: curgerea fluidelor n transportul curentului prin re*elede curent electric, dar i prin liniile de asamblare transportul anumitor produse intre mai

multe destinatii

lucrare ii co

Documents