Post on 01-Dec-2015
description
CO - Cursul 2
Cap.1. Programare liniară
1
CercetCercetări Operaări Operaţţionaleionale
Universitatea POLITEHNICA din Bucureşti
Autor curs: Conf. dr. ing. mat. Ovidiu Blăjină
CO - Cursul 2
Cap.1. Programare liniară
2
Capitolul 1
PROGRAMARE LINIARĂ(II)
CO - Cursul 2
Cap.1. Programare liniară
3
3. Metoda SIMPLEX4. Postoptimizare 5. Optimizare parametrică6. Programare în numere întregi
CO - Cursul 2
Cap.1. Programare liniară
4
3. Metoda SIMPLEX3.1. Fundamente teoretice3.2. Algoritmul simplex3.3. Metoda coeficienţilor de penalizare
CO - Cursul 2
Cap.1. Programare liniară
5
3.1. Fundamente teoreticeCea mai utilizată metodă pentru rezolvarea
problemelor de PL este metoda simplex datorată matematicianului american G. B. Dantzig (1947).
Metoda simplex permite cercetarea sistematică a mulţimii soluţiilor admisibile de bază ale unui model de problemă de PL în forma standard. Presu-punând cunoscută o astfel de soluţie iniţială, se construiesc succesiv soluţii realizabile de bază din ce în ce "mai bune" pînă la obţinerea soluţiei optime.
Metoda oferă şi un criteriu de recunoaştere a optimului infinit.
CO - Cursul 2
Cap.1. Programare liniară
6
Prezentarea metodei simplex se va referi la modelul de PL în forma standard de minimizare:
⎪⎩
⎪⎨
⎧
≥=0
min T
xbAx
xc
unde x, c ∈ Rn, b ∈ Rm, A ∈ Mm × n , cu rang A = m < n.Fie B o bază primal admisibilă extrasă din
matricea A şi xB = B-1b soluţia de bază iniţială asociată.Coeficienţii numerici ai problemei corespunză-
tori bazei B se înscriu în tabelul simplex asociat bazei B, de forma:
CO - Cursul 2
Cap.1. Programare liniară
7
CO - Cursul 2
Cap.1. Programare liniară
8
Tabelul simplex conţine: - în prima coloană, variabilele de bază (V.B.); - în a doua coloană, valorile variabilelor de bază
(V.V.B.); - în următoarele n coloane, vectorii , j = 1,..., n. - pe ultima linie, valoarea funcţiei obiectiv în baza B, notată cu ; diferenţele .
La aplicarea algoritmului metodei simplex, fiecărei baze B îi corespunde un tabel simplex de acest tip.
Bjy
Bz njcz jBj ,1 ,- =
CO - Cursul 2
Cap.1. Programare liniară
9
3.2. Algoritmul simplexAlgoritmul simplex pentru problema de minimizare:Pasul 1. Se determină o bază primal admisibilă iniţială B. Pasul 2. Se calculează , , , , j = 1,..., n .Pasul 3. Dacă , atunci STOP: este program optim; altfel se determină mulţimea
Bx Bz Bjy j
Bj cz −nj,cz j
Bj ,1 0 =∀≤−
{ }0 >−∈=+ jBj czJjJ
şi se trece la pasul 4.Pasul 4. Se determină indicele k ∈ J+ cu criteriul de intrare în bază:
CO - Cursul 2
Cap.1. Programare liniară
10
kBkj
BjJj
czcz −=−+∈
)( max
Dacă ≤ 0, atunci STOP: problema are optim infinit; altfel se determină indicele l ∈ I cu criteriul de ieşire din bază:
Bky
Blk
Bl
Bik
Bi
yIi y
xyx
Bik
=⎟⎟⎠
⎞⎜⎜⎝
⎛
>∈
min0
Pasul 5. Fie baza B’ obţinută din B prin înlocuirea coloanei A(l) cu coloana A(k) . Se trece la pasul 2, înlocuind peste tot baza B cu baza B’ .
CO - Cursul 2
Cap.1. Programare liniară
11
Algoritmul simplex pentru problema de maximizare:Pasul 3. Dacă , atunci STOP: este program optim; altfel se determină mulţimea (nevidă)
nj,cz jBj ,1 0 =∀≥−
{ }0 <−∈=− jBj czJjJ
şi se trece la pasul 4.Pasul 4. Se determină indicele k ∈ J- cu criteriul de intrare în bază:
kBkj
BjJj
czcz −=−−∈
)( min
Dacă ≤ 0, atunci STOP: problema are optim infinit; altfel se determină indicele l ∈ I cu criteriul de ieşire din bază.
Bky
CO - Cursul 2
Cap.1. Programare liniară
12
Observaţie: Elementul se numeşte pivot.Formulele de schimbare a bazei sunt echiva-
lente cu următoarele reguli de transformare ale tabelului simplex asociat bazei B:
a) elementele situate pe linia pivotului se împart lapivot;
b) elementele situate pe coloana pivotului devinzero, cu excepţia pivotului, care devine 1;
c) celelalte elemente ale tabelului simplex se tran-sformă după formula dreptunghiului. Se consideră dreptunghiul imaginar a cărui diagonală este deter-minată de elementul de transformat şi de pivot:
Blky
CO - Cursul 2
Cap.1. Programare liniară
13
Formula dreptunghiului:
Blk
Bik
Blj
Blk
BijB
ij yyyyy
y−
=′
CO - Cursul 2
Cap.1. Programare liniară
14
CO - Cursul 2
Cap.1. Programare liniară
15
Process
Construieşte tabelul simplex iniţial
Process
Cât timp există valori pozitive (negative) pe linia diferenţelor execută
Determină coloana pivotului
Există valori pozitive încoloana pivotului ?
Determină linia pivotuluiProcessCalculează
noul tabel simplex
Nu existăsoluţie optimă finită
STOP
Prezintă tabelul simplex final (ce conţine soluţia optimă)
Da Nu
CO - Cursul 2
Cap.1. Programare liniară
16
Exemplu. Să se rezolve cu algoritmul simplex problema de PL:
⎪⎪
⎩
⎪⎪
⎨
⎧
≥≥≥≤−+−≥++−
≤+−+−
0 0, ,0 63 4 2 1 2 2
4 2 3 )53(4min
321
321
321
321
321
xxxxxxxxxxxx
xxx
Soluţie. Se aduce problema la forma standard. Pentru aceasta se introduc variabilele de compensare x4 , x5 , x6 nenegative în cele trei restricţii. Se înmulţeşte cea de-a doua restricţie cu -1 şi obţinem:
CO - Cursul 2
Cap.1. Programare liniară
17
⎪⎪
⎩
⎪⎪
⎨
⎧
=≥=+−+=+−−=++−
+−
6 1 ,0 6 3 4 2
1 2 2 4 2 3
)53(4min
6321
5321
4321
321
,ixxxxx
xxxxxxxxxxx
i
Matricea sistemului de restricţii a formei de mai sus a problemei este:
⎥⎥
⎦
⎤
⎢⎢
⎣
⎡
−−−
−=
100342010212001123
A
cu m = 3, n = 6, rang (A) = 3 < 6.
CO - Cursul 2
Cap.1. Programare liniară
18
Se poate forma o bază, B, cu ultimele trei coloane ale matricei A, aceasta fiind matricea unitate:
⎥⎥
⎦
⎤
⎢⎢
⎣
⎡=
100010001
B
Pentru a putea aplica algoritmul simplex se verifică, în prealabil, dacă baza B este primal admisibilă. Într-adevăr, B fiind matrice unitate, avem B-1 = B, iar > 0.
Se construiesc tabelele simplex (v. fig. urm.).Problema admite soluţia optimă finită: x1= 0;
x2= 1,5; x3= 0; x4= 7; x 5= 2,5; x6= 0; zmin= -4,5.
[ ]T 1 614=== − bbBxB
CO - Cursul 2
Cap.1. Programare liniară
19
CO - Cursul 2
Cap.1. Programare liniară
20
Exemplu. Să se rezolve problema de PL:
⎪⎪⎩
⎪⎪⎨
⎧
≥≤−+−≤+−
++
0 , , 4 2 2 2 )23(max
321
321
321
321
xxxxxxxxx
xxx
Soluţie. Se aduce problema la forma standard, prin introducerea variabilelor de compensare x4 , x5:
⎪⎪⎩
⎪⎪⎨
⎧
=≥=+−+−=++−
++
5 ,1 0, 4 2 2 2
)23(max
5321
4321
321
ixxxxx
xxxxxxx
i
CO - Cursul 2
Cap.1. Programare liniară
21
Cu ultimele două coloane din matricea siste-mului de restricţii (ecuaţii) se poate forma baza B, respectiv, matricea unitate.
Baza B este o bază primal admisibilă deoarece; aşadar, se poate aplica algorit-
mul simplex.Tabelele simplex corespunzătoare sunt prezen-
tate în figurile următoare. În ultimul tabel se constată că există zk - ck < 0; J-
= {1, 2}, deci soluţia obţinută nu este optimă. Pe de altă parte, toţi coeficienţii yi1 de pe coloana variabilei x1 sunt nepozitivi. Rezultă că problema dată are optim infinit (nu are soluţie optimă finită).
[ ] 042 T 1 >==− bbB
CO - Cursul 2
Cap.1. Programare liniară
22
CO - Cursul 2
Cap.1. Programare liniară
23
3.3. Metoda coeficienţilor de penalizarePentru a putea începe aplicarea algoritmului
simplex este necesar a fi îndeplinite două condiţii:problema să fie în formă standard;să dispunem de o soluţie de bază iniţială.
Pentru cea de-a doua condiţie, alegerea la întâmplare a unei baze formate din m vectori oarecare dintre vectorii coloană ai matricei A poate conduce la soluţii de bază nerealizabile cu care aplicarea algoritmului simplex nu poate începe.
Determinarea unei soluţii de bază iniţială se poate realiza cu metoda coeficienţilor de penalizare.
CO - Cursul 2
Cap.1. Programare liniară
24
Fie problema de PL de minimizare:
⎪⎪
⎩
⎪⎪
⎨
⎧
≥≥+++
≥++++++=
0 ,...,
c z [min]
1
2211
11212111
2211
n
mnmnmm
nn
nn
xxbxaxaxa
bxaxaxaxcxcx
LLLLLLLLLLLLLL
L
L
Presupunem că toţi termenii liberi sunt pozitivi: b1 ≥ 0,..., bm ≥ 0 şi că matricea A nu conţine nici un vector coloană unitar.
Prin adăugarea variabilelor de compensare (nenegative) cu semnul "-“ în fiecare restricţie, se obţine sistemul de restricţii în forma standard:
(3.1)
CO - Cursul 2
Cap.1. Programare liniară
25
⎪⎪⎩
⎪⎪⎨
⎧
=−+++
=−+++=−+++
+
+
+
mmnnmnmm
nnn
nnn
bxxaxaxa
bxxaxaxabxxaxaxa
LLLLLLLLLLLLLLLL
L
L
2211
222222121
111212111
Considerând ca soluţie iniţială de bază:x1 = x2 = ... = xn = 0, xn +1 = -b1 , xn +2 = -b2 ,...,
xn + m = = -bmaceasta nu este realizabilă (admisibilă) şi nu satisface condiţiile algoritmului simplex.
Pentru a obţine o soluţie admisibilă de bază se introduce în fiecare restricţie câte o variabilă artificială (nenegativă) xn + m +1 , xn + m + 2 , ..., xn + 2m ,
CO - Cursul 2
Cap.1. Programare liniară
26
⎪⎪⎩
⎪⎪⎨
⎧
=+−+++
=+−+++=+−+++
++
+++
+++
mmnmnnmnmm
mnnnn
mnnnn
bxxxaxaxa
bxxxaxaxabxxxaxaxa
22211
2222222121
1111212111
LLLLLLLLLLLLLLLLLLLL
L
L
Se modifică şi funcţia obiectiv a problemei iniţiale (3.1) prin introducerea acestor variabile artificiale cu coeficientul de penalizare +M.
Se consideră că M are o valoare pozitivă foarte mare (practic infinit). Rezultă problema extinsă (3.2) de mai jos:
cu semnul "+":
CO - Cursul 2
Cap.1. Programare liniară
27
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≥=+−+++
=+−+++=+−++++++++=
+++++
++
+++
+++
+++
0 ,..., , ,..., , ,..., ,
[min]
21121
22211
2222222121
1111212111
2111
mnmnmnnn
mmnmnnmnmm
mnnnn
mnnnn
mnmnnn
xxxxxxxbxxxaxaxa
bxxxaxaxabxxxaxaxaMxMxxcxcz
LLLLLLLLLLLLLLLLLLLL
L
L
LL
(3.2)
Soluţia iniţială de bază pentru problema (3.2) poate fi: x1 = x2 = ... = xn = xn +1 = xn +m = 0, xn +m +1 == -b1 , xn +m +2 = -b2 , xn +2m = -bm
Soluţia conţine variabilele artificiale, dar este convenabilă pentru aplicarea algoritmului simplex problemei (3.2).
CO - Cursul 2
Cap.1. Programare liniară
28
Se rezolvă problema extinsă (3.2) fiind posibile următoarele cazuri:
1) Problema (3.2) are optim infinit. Atunci şi problema (3.1) are optim infinit.
2) Problema (3.2) are optim finit, dar în soluţia optimă cel puţin o variabilă artificială are o valoare nenulă (pozitivă). Atunci problema (3.1) nu are soluţie.
3) Problema (3.2) are optim finit şi în soluţia optimă toate variabilele artificiale au valoarea nulă. Atunci această soluţie, din care se ignoră variabilele artificiale, este soluţia optimă a problemei (3.1).
CO - Cursul 2
Cap.1. Programare liniară
29
Fie problema de PL de maximizare:
⎪⎪
⎩
⎪⎪
⎨
⎧
≥=+++
=++++++=
0 ,...,
c z [max]
1
2211
11212111
2211
n
mnmnmm
nn
nn
xxbxaxaxa
bxaxaxaxcxcx
LLLLLLLLLLLLLL
L
L
Presupunem că toţi termenii liberi sunt pozitivi: b1 ≥ 0,..., bm ≥ 0 şi că matricea A nu conţine nici un vector coloană unitar.
Pentru a obţine o soluţie admisibilă de bază se introduce în fiecare restricţie din (3.3) câte o variabilă artificială (nenegativă), xn +1 , xn + 2 ,..., xn + m , cu semnul "+".
(3.3)
CO - Cursul 2
Cap.1. Programare liniară
30
Se modifică funcţia obiectiv a problemei (3.3)prin introducerea acestor variabile artificiale cu coeficientul de penalizare -M.
Rezultă problema extinsă:
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≥=++++
=++++=++++
−−−++=
++
+
+
+
++
0 ,..., , ,..., ,
[max]
121
2211
222222121
111212111
111
mnnn
mmnnmnmm
nnn
nnn
mnnnn
xxxxxbxxaxaxa
bxxaxaxabxxaxaxa
MxMxxcxcz
LLLLLLLLLLLLLLLL
L
L
LL
(3.4)
Se rezolvă problema (3.4) fiind posibile aceleaşi cazuri, relative la problema (3.3), ca cele prezentate anterior la problema de minimizare (3.1).
CO - Cursul 2
Cap.1. Programare liniară
31
Observaţii:1) Indiferent de tipul problemei (minimizare sau
maximizare), dacă matricea restricţiilor nu conţine vectori unitari, atunci numărul variabilelor artificiale introduse va fi egal cu m. 2) Dacă, la aplicarea algoritmului simplex pentru rezolvarea problemei extinse, o variabilă artificială iese din bază, ea nu va mai intra niciodată în bază, fapt care justifică eliminarea (eventuală) din calculele ulterioare a coloanei variabilei respective.
CO - Cursul 2
Cap.1. Programare liniară
32
Exemplu. Să se rezolve problema de PL cu metodacoeficienţilor de penalizare:
⎪⎪⎩
⎪⎪⎨
⎧
≥≥++≥−+++
0 , , 6
103 )74(3min
321
321
321
321
xxxxxxxxx
xxx
Soluţie. Se aduce mai întâi problema la forma standard prin introducerea în restricţii a variabilelor de compensare x4 şi x5.
Se adaugă variabilele artificiale x6 şi x7; ele se introduc în restricţii cu coeficientul 1 şi în funcţia obiectiv cu coeficienţii de penalizare +M:
CO - Cursul 2
Cap.1. Programare liniară
33
⎪⎪⎩
⎪⎪⎨
⎧
=≥=+−++=+−−+
++++
7 ,1 ,0 6 10 3 )74(3min
75321
64321
76321
ixxxxxx
xxxxxMxMxxxx
i
Soluţia iniţială de bază este x1 = x2 = x3 = x4 = x5 = 0, x6 = 10, x7 = 6. Primul tabel simplex al problemei extinse corespunzător acestei baze este:
CO - Cursul 2
Cap.1. Programare liniară
34
CO - Cursul 2
Cap.1. Programare liniară
35
Deoarece zk - ck≤ 0, k = 1,..., 7 ⇒ tabelul simplex de mai sus conţine soluţia optimă a problemei extinse, în care variabilele artificiale x6 şi x7 au valoarea zero.
Soluţia optimă a problemei iniţiale: x1 = 4, x2 = 2, x3 = 0. Valoarea optimă a funcţiei obiectiv zopt = 20.
CO - Cursul 2
Cap.1. Programare liniară
36
4. Postoptimizare
CO - Cursul 2
Cap.1. Programare liniară
37
În modelul unei probleme de PL
ce poate caracteriza activitatea unui agent economic,intervin mai multe mărimi considerate constante în momentul elaborării: A - matricea coeficienţilor sistemului de restricţii; b - vectorul termenilor liberi; c - vectorul coeficienţilor funcţiei obiectiv.
Dinamica accentuată a economiei de piaţă implică, adeseori, schimbări ale condiţiilor care stau la baza elaborării modelului.
⎪⎩
⎪⎨
⎧
≥=0
(max)min T
xbAx
xc
CO - Cursul 2
Cap.1. Programare liniară
38
Exemple: modificarea preţurilor la resurse, a tarifelor sau cererii la activităţile desfăşurate, a unor capacităţi de producţie, a cantităţilor disponibile de resurse; introducerea în fabricaţie a unor noi produse.
Din punct de vedere matematic, astfel de schimbări implică modificări ale elementelor unei probleme de PL:
modificarea vectorului b; modificarea vectorului c; introducerea unei variabile suplimentare;introducerea unui grup de restricţii în sistemul derestricţii iniţial;modificarea unei linii/coloane din matricea A.
CO - Cursul 2
Cap.1. Programare liniară
39
Postoptimizarea (reoptimizarea) unei probleme de PL constă în recalcularea soluţiei optime a problemei în cazul unor modificări de tipul menţionat.
Întrebarea care se pune este dacă soluţia optimă îşi păstrează caracterul de optimalitate după modifică-rile survenite. Se impune, aşadar, în primul rând, o verificare a soluţiei în noile condiţii. Dacă soluţia nu mai este optimă, determinarea unei noi soluţii se face, nu refăcând calculele de la început, ci pornind de la o soluţie de bază mai apropiată de soluţia optimă, uneori chiar de la soluţia optimă a problemei iniţiale, pentru micşorarea volumului de calcule necesare.
CO - Cursul 2
Cap.1. Programare liniară
40
5. Optimizare parametrică
CO - Cursul 2
Cap.1. Programare liniară
41
Problema de programare liniară în care cel puţin unul din elementele sale - matricea coeficien-ţilor sistemului de restricţii A, vectorul termenilor liberi b, vectorul coeficienţilor funcţiei obiectiv c -depinde, liniar sau neliniar, de unul sau mai mulţi parametri reprezintă o problemă de programare liniară parametrică.
Optimizarea parametrică studiază, ca şi postop-timizarea, problemele de programare liniară cu coeficienţi variabili. Dacă postoptimizarea cores-punde variaţiei discrete a coeficienţilor, optimizarea parametrică vizează variaţia continuă a coeficienţilor.
CO - Cursul 2
Cap.1. Programare liniară
42
Rezolvarea problemelor de programare liniară parametrică implică parcurgerea a două etape:
1) Determinarea soluţiei optime pentru o valoare determinată a parametrului sau a unui sistem de valori dacă este vorba de mai mulţi parametri.
2) Studiul sensibilităţii soluţiei optime determinate la variaţia parametrului (parametrilor).
Acest studiu constă în stabilirea intervalelor (domeniilor) de optimalitate a unei soluţii, respectiv, a mulţimii valorilor parametrilor pentru care soluţia determinată îşi păstrează caracterul de optimalitate.
CO - Cursul 2
Cap.1. Programare liniară
43
6. Programare în numere întregi6.1. Consideraţii generale6.2. Exemple de probleme economice6.3. Metoda branch and bound
CO - Cursul 2
Cap.1. Programare liniară
44
6.1. Consideraţii generaleÎn problemele de programare liniară studiate
anterior variabilele au fost supuse condiţiei de nenegativitate, având o variaţie continuă.
O serie de situaţii din domeniul economic impun cerinţa ca variabilele să nu poată lua decât valori din anumite mulţimi discrete. Astfel de restricţii de discontinuitate apar atunci când variabilele sunt exprimate în unităţi de măsură indivizibile (număr de bucăţi etc.).
Problemele de optimizare cu restricţii de discon-tinuitate aparţin domeniului programării discrete.
CO - Cursul 2
Cap.1. Programare liniară
45
Marea majoritate a problemelor de programare discretă întâlnite în practică impun ca variabilele (o parte sau toate) să aibă valori întregi. Vorbim în aceste cazuri de programare în numere întregi.
Problemele în care doar o parte din variabile au valori întregi sunt denumite probleme mixte sau parţial întregi, iar cele în care toate variabilele au valori întregi se numesc probleme total întregi.
În cele ce urmează ne vom limita la studiul problemelor de programare în numere întregi, ceea ce nu reprezintă o restrângere a generalităţii deoarece cazurile generale discrete pot fi aduse la această formă.
CO - Cursul 2
Cap.1. Programare liniară
46
Astfel, presupunem că, într-o problemă, o variabilă oarecare x poate lua numai un număr finit de valori: a1, a2 ,..., ak . Variabila x se poate rescrie sub forma:
∑=
=k
iiiax
1δ ∑
=
=k
ii
11δ
ceea ce conduce la o problemă cu variabile întregi.Observaţie. În orice problemă de programare discretă funcţia obiectiv şi restricţiile, chiar dacă sunt expri-mate prin forme liniare, datorită caracterului discon-tinuu al variabilelor nu mai sunt, din punct de vedere matematic, funcţii liniare. Din acest motiv, programa-
, cu şi δi = 0 sau 1
CO - Cursul 2
Cap.1. Programare liniară
47
rea discretă este tratată ca un caz special de programare liniară.
Utilizarea variabilelor întregi conduce la o creştere a flexibilităţii modelării fenomenelor, dar şi a complexităţii modalităţilor specifice de rezolvare.
În acest scop, cele mai des utilizate sunt:• metodele planului de secţiune;• metodele de ramificare şi mărginire (tip branch
and bound).
CO - Cursul 2
Cap.1. Programare liniară
48
6.2. Exemple de probleme economice
Exemplu. Problemă de încărcareSe consideră cazul încărcării unui camion cu n
tipuri de colete cu marfă, de masă mi (i = 1,..., n) şi valoare vi (i = 1,..., n). Camionul admite o încărcare maximă C.
Să se stabilească modul optim de alegere a încărcăturii camionului astfel încât valoarea totală a coletelor transportate să fie maximă.
Se notează cu xi numărul de colete de tipul i ce urmează a fi încărcate în camion.
Funcţia obiectiv este valoarea totală a coletelor
CO - Cursul 2
Cap.1. Programare liniară
49
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
=∈=≥
≤
=
∑
∑
=
=
niZxnix
Cxm
xvz
i
i
n
iii
n
iii
,1 , ,1 ,0
[max]
1
1
S-a obţinut un model de problemă de optimizare total discretă, în care variabilele pot lua numai valori întregi.
tranportate, care trebuie maximizată.Modelul matematic al problemei are forma:
CO - Cursul 2
Cap.1. Programare liniară
50
Exemplu. Problemă de investiţiiO firmă intenţionează să facă investiţii pentru
retehnologizare. Ea are posibilitatea să aleagă din noferte de proiecte. Fiecare proiect va aduce un profit ci (i =1,..., n). Se mai cunosc costul investiţiei în fiecare proiect ai (i =1,..., n) şi suma maximă dispo-nibilă S pentru investiţii.
Să se stabilească programul optim de investiţii care să conducă la un profit total maxim.
Se definesc variabilele bivalente:
⎩⎨⎧= altfel 0,
ales este proiectul dacă 1, ixi
CO - Cursul 2
Cap.1. Programare liniară
51
Modelul matematic al problemei are forma:
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
==
≤
=
∑
∑
=
=
nix
Sxa
xcz
i
n
iii
n
iii
,1 1,sau 0
[max]
1
1
Modelul de problemă de optimizare obţinut poartă numele de model de programare zero-unu.
CO - Cursul 2
Cap.1. Programare liniară
52
Exemplu. Problemă de costuriConducerea unei firme doreşte minimizarea
cheltuielilor de fabricaţie pentru cele n tipuri de produse ale sale. Fiecare tip de produs j (j = 1,…, n)are un cost unitar de producţie cj (costul materialelor, manoperei etc.) şi un cost de pregătire a fabricaţiei qj .
Pentru fiecare tip de produs j se cunosc cererea minimă a pieţii aj şi capacitatea proprie maximă de fabricaţie bj .
Să se stabilească programul de fabricaţie al firmei, optim din punct de vedere al cheltuielilor sale totale.
CO - Cursul 2
Cap.1. Programare liniară
53
Fie xj cantitatea de produs j (j = 1,..., n) ce urmează a se fabrica.
Se mai definesc variabilele bivalente:
⎩⎨⎧ >
=altfel 0,
0 dacă 1, jj
xy
care indică dacă produsul j intră sau nu în fabricaţie.Funcţia obiectiv este reprezentată de cheltuielile
totale de fabricaţie ale firmei şi trebuie minimizată:
( )∑=
+=n
jjjjj yqxcz
1 [min]
Restricţiile privind cererea pieţii:
CO - Cursul 2
Cap.1. Programare liniară
54
njax jj ,1 , =≥
Restricţiile privind capacitatea de producţie:njbx jj ,1 , =≤
Definiţia variabilei yj se poate reformula:
njy
bx
y
j
j
jj ,1 ,
1} ,0{
=
⎪⎩
⎪⎨
⎧
∈
≥
Se obţine un model de optimizare mixt, în care o parte din variabile au valori pozitive, iar celelalte nu pot lua decât valori întregi (sunt variabile bivalente):
CO - Cursul 2
Cap.1. Programare liniară
55
( )
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
=∈
=≥
=≤
+=∑=
njynjax
njybx
yqxcz
j
jj
jjj
n
jjjjj
,1 1}, {0, ,1 ,
,1 ,
[min] 1
CO - Cursul 2
Cap.1. Programare liniară
56
Exemplu. Problema comis voiajoruluiUn comis voiajor trebuie să viziteze n localităţi
L1 , ..., Ln . El va porni din localitatea L1 şi se va reîntoarce acolo după ce va trece prin toate loca-lităţile câte o singură dată. Se cunosc distanţele dij dintre oricare două localităţi Li şi Lj .
Să se aleagă traseul optim de vizitare al celor n localităţi care să minimizeze lungimea totală a traseului parcurs de către comis voiajor.
Se definesc variabilele bivalente:
⎩⎨⎧
=altfel 0,
la din deplasarea include traseuldacă 1, jiij
LLx
CO - Cursul 2
Cap.1. Programare liniară
57
Funcţia obiectiv este lungimea totală a traseului parcurs şi care trebuie minimizată:
∑∑= =
=n
i
n
jijij xdz
1 1 [min]
Condiţia ca traseul să se îndreapte exact spre o singură altă localitate după plecarea din localitatea Li:
nixn
jij ,1 ,1
1==∑
=
Condiţia ca traseul să treacă prin fiecare localitate o singură dată este echivalentă cu faptul că în fiecare localitate Lj se poate ajunge numai din o singură altă localitate:
CO - Cursul 2
Cap.1. Programare liniară
58
njxn
iij ,1 ,1
1==∑
=
O soluţie a problemei este admisibilă dacă fiecare i (i = 1,…, n) ocupă o singură dată prima poziţie şi o singură dată a doua poziţie, ca indice al variabilei. În caz contrar, soluţia nu este acceptabilă deoarece se formează două subtrasee neconectate. Pentru elimi-narea acestora, se impune condiţia:
jin,i, jnnxuu ijji ≠=−≤+− , 2 ,1
în care intervin variabilele:n,iui 2 0, =≥ , ui ∈Z
CO - Cursul 2
Cap.1. Programare liniară
59
Modelul matematic al problemei are forma:
2, , ,0 1, , 1}, {0,
, 2, ,1
,1 ,1
,1 ,1
[min]
1
1
1 1
⎪⎪⎪⎪⎪⎪
⎩
⎪⎪⎪⎪⎪⎪
⎨
⎧
=∈≥
=∈
≠=−≤+−
==
==
=
∑
∑
∑∑
=
=
= =
niZuunjix
jini, jnnxuu
nix
njx
xdz
ii
ij
ijji
n
jij
n
iij
n
i
n
jijij
CO - Cursul 2
Cap.1. Programare liniară
60
6.3. Metoda branch and boundProcedeul acestei metode poate fi descris sub
forma unei diagrame arborescente.Metoda generează nodurile arborelui până când
toate căile ajung în noduri terminale. Pentru fiecare nod există două ramuri de verificat. Dacă nici una dintre ramuri nu ajunge într-un nod terminal, atunci metoda urmează cel mai favorabil nod, nodul de pe cealaltă ramură, fiind considerat independent.
Se consideră problema de programare în numere întregi mixte:
CO - Cursul 2
Cap.1. Programare liniară
61
⎪⎪⎩
⎪⎪⎨
⎧
∈∈≥=
=
Tjxx
bAxxcz
j Z, 0
[max] T
Algoritmul metodei branch and bound:Pasul 1 (Soluţia iniţială)
Se rezolvă problema de programare liniară obţinută din problema în numere întregi iniţială, prin omiterea condiţiilor de integritate. Dacă toate valorile soluţiei
Z, , atunci avem soluţia optimă a problemei iniţiale, STOP; altfel se trece la pasul 2.
∈jx Tj∈∀
CO - Cursul 2
Cap.1. Programare liniară
62
Pasul 2 (Selectarea variabilelor de ramificare)Se alege din ultimul tabel simplex de la pasul 1,
dintre acele variabile xj , j ∈ T, care nu au valori întregi, variabila de bază xl având partea fracţionară, fl , cea mai mare, pentru generarea restricţiilor de ramificare.
Deoarece variabila xl trebuie să aibă valori întregi, şi ea trebuie să satisfacă fie condiţia:lll fxx += ][
][ ll xx ≤ (7.1) fie
1][ +≥ ll xx (7.2)
CO - Cursul 2
Cap.1. Programare liniară
63
Pasul 3 (Generarea unor noi noduri)Se formează două noi probleme de programare în
numere întregi, relative la nodul considerat la pasul 2.O problemă este formată prin adăugarea restricţiei (7.1), iar cealaltă prin adăugarea restricţiei (7.2).
Se rezolvă fiecare problemă cu algoritmul simplex. Pasul 4 (Testarea nodurilor terminale)
Fiecare din nodurile generate la pasul 3 poate fi un nod terminal dacă: problema reprezentată de acel nod nu are soluţii admisibile sau toate variabilele xj ,j ∈ T, au valori întregi.
CO - Cursul 2
Cap.1. Programare liniară
64
În primul caz, se etichetează nodurile ca noduri terminale şi se trece la pasul 5.
În al doilea caz, se compară, mai întâi, valorile funcţiei obiectiv cu valoarea curentă cea mai bună. Dacă valoarea funcţiei obiectiv pentru noul nod este mai bună, ea devine cea mai bună valoare; se trece la pasul 5.Pasul 5 (Selectarea nodurilor)
a) Dacă ambele noduri de la pasul 4 sunt terminale, atunci următorul nod considerat este următorul din lista nodurilor independente. Dacă nodul independent are o valoare a funcţiei obiectiv mai mare decât cea
CO - Cursul 2
Cap.1. Programare liniară
65
mai bună valoare curentă, atunci, cu acest nod, se trece la pasul 2; altfel se verifică următorul nod dinlista celor independente. Când lista nodurilor independente este epuizată, valoarea curentă cea maibună este soluţia optimă, STOP.
b) Dacă doar un nod la pasul 4 este terminal, atunci se utilizează nodul neterminal şi se trece la pasul 2.
c) Dacă ambele noduri la pasul 4 sunt neterminale, atunci se alege nodul cu valoarea funcţiei obiectivmai mare. Celălalt nod se adaugă la lista nodurilor independente.
CO - Cursul 2
Cap.1. Programare liniară
66
Exemplu. Să se rezolve problema de programare în numere întregi:
⎪⎪
⎩
⎪⎪
⎨
⎧
∈≥≤+≤++
Zxxxx
xxxx
xx
21
21
21
21
21
, 0 ,
48 3 8 30 5 2
)3(7max
Soluţie. Se rezolvă cu algoritmul simplex problema de PL obţinută din cea iniţială prin renunţarea la condiţiile de integritate şi se obţine tabelul simplex final:
CO - Cursul 2
Cap.1. Programare liniară
67
Se constată că ∉ Z, ∉ Z. Se aplică metoda branch and bound.
Părţile fracţionare sunt: f1 = 7/17, f2 = 4/17. Deoarece f1 > f2 , se alege ca variabilă de ramificare x1, căreia i se aplică condiţiile: x1 ≤ 4 şi x1 ≥ 5 .
1x 2x
CO - Cursul 2
Cap.1. Programare liniară
68
1774117721775
2
1
/z/x/x
===1
(Tab.7.9)
5206522
42
1
/z/x
x
===
41 ≤x
4338
52
1
===
z/x
x
51 ≥x
(Tab.7.12) (Tab.7.13)32
Valoarea funcţiei obiectiv din nodul 3 este mai mare decât cea din nodul 2 (43 > 206/5). Ca urmare, nodul 2 se introduce în lista nodurilor independente. În nodul 3 se aplică condiţiile: x2 ≤ 2 şi x2 ≥ 3.
CO - Cursul 2
Cap.1. Programare liniară
69
1774117721775
2
1
/z/x/x
===1
(Tab.7.9)
5206522
42
1
/z/x
x
===
41 ≤x
4338
52
1
===
z/x
x
51 ≥x
(Tab.7.12) (Tab.7.13)32
41712
4212
1
/zx
/x
===
22 ≤x
Nu existăsoluţie
admisibilă
32 ≥x
(Tab.7.16) (Tab.7.15)54
terminalNod
CO - Cursul 2
Cap.1. Programare liniară
70
În nodul 3, x1 are o valoare întreagă, dar, în nodul 4, x1 nu mai are valoare întreagă. În nodul 4 se aplică condiţiile: x1 ≤ 5 şi x1 ≥ 6 şi se obţine:
CO - Cursul 2
Cap.1. Programare liniară
71
1774117721775
2
1
/z/x/x
===1
(Tab.7.9)
41712
4212
1
/zx
/x
===
22 ≤x
Nu existăsoluţie
admisibilă
32 ≥x
(Tab.7.16) (Tab.7.15)54
5206522
42
1
/z/x
x
===
41 ≤x
4338
52
1
===
z/x
x
51 ≥x
(Tab.7.12) (Tab.7.13)32
4125
2
1
===
zxx
51 ≤x
4206
2
1
===
zxx
61 ≥x
(Tab.7.18) (Tab.7.19)76
Soluţia optimă