Modele de Optimizare

Dr. Miguel Jiménez C.

 Introducere în Optimizare
• Qué optimizar,Porqué optimizar,Cómo optimizar
• În prezent, la nivel mondial, a crescut nevoia de
introduce ț i în cercetări modelele ș i instrumentele
matematica avansată (Rodríguez, 2001).
• Utilizarea ș i interpretarea adecvată a acestor tehnici permit luarea de
decizii optime.
• Abordarea Optimizării este aceeaș i cu cea a metodei ș tiinț ifice ș i
clar este acelaș i din Cercetarea Operaț iunilor. În special,
procesul începe cu observaț ia atentă ș i formularea
del problema y sigue cu construc ț ia unui model ș tiinț ific
(în general matematic) care încearcă să abstractizeze esen ț a lui
problema real.
 Fazele unui studiu de Optimizare
• Formularea ș i definirea problemei

• Construirea modelului
• Soluț ia modelului.

• Validarea modelului
• Implementarea rezultatelor
 Modele Combinatorii: Unde:m= numărul de elemente, n= orden

!
nu
Combinatii: =,
( ) =
!( − )!
nu
Influenț ează
ordonarea? Variaț ii: , = ( −1 ) ( − 2 …
) ( − +1)
Se repetă
nu vreo?

și și Variatiicurepetitie: , =
Toț i
elemente?
nu = !
și Permutaciones:
Se repetă
vreo?

și Permutări cu
Exemple:
repetición:
1) Câte steaguri cu 2 culori pot fi formate dacă avem la dispoziț ie 3 culori? 3,2 =3 ( 2 )=6,
2) În câte moduri diferite pot fi răspunse 2 întrebări de tip test cu 3 opț iuni de răspuns fiecare (a, b, , =3 2=9
c)? a, b a, c a, a b, a b, c b, b c, a c, b c, c

3) În câte feluri se pot aș eza Luis, Ana ș i Pedro pe o bancă? 3 =3!=3 x 2 x 1 =6 ["LAP","LPA","PAL","PLA","APL","ALP"]
3!
4) Câte cuvinte diferite, cu sau fără sens, pot fi formate din literele cuvântului „OSO”?
2,1
3 = =3 , OSO, OOS, SOO
2!1!
4!
5) În câte moduri pot fi grupati LEO, JUAN, ANA ș i EVA pentru o pereche de lucru? 4,2= =6, ["LJ","LA","LE","JA","JE","AE"]
2 ! (4 − 2 ) !
 Modelare Matematică
Modele ș i metode frecvente ale I.O
• Modele de Programare Lineară
• Modele de Programare întreagă
• Modele de Programare Binara
• Modele de Programare Mixte

Modeluri combinatorice (NP Hard)

• Model TSP
• Modelul mTSP (Rutarea Vehiculelor)
• Model JSSP
Structura modelelor de optimizare
Definiț ia Variabilelor de Decizie:
Variabilele decizionale sunt necunoscutele (sau deciziile) care trebuie determinate prin rezolvarea modelului, sunt diferitele
activităț ile la care se dedică afacerea. Parametrii sunt valorile cunoscute care leagă variabilele de
decizie cu restricț iile ș i funcț ia obiectiv. Parametrii modelului pot fi deterministici sau probabilistici,
variabilele de decizie pot asuma valori întregi sau continue.

Definiț ia restricț iilor sau limitărilor

Limitările tehnologice, economice ș i altele ale sistemului, modelul trebuie să includă restricț ii (implicite sau explicite)
care restricț ionează variabilele de decizie la un interval de valori fezabile.

Definiț ia Funcț iei Obiectiv

Determină măsura de eficienț ă a sistemului ca o funcț ie matematică a variabilelor de decizie; poate fi de
maximizare sau minimizare. Soluț ia optimă va fi aceea care va produce cea mai bună valoare a funcț iei obiectiv.
supusă restricț iilor.

Matematic vorbind: ó = 1 1 + 2 2 + ⋯+
.
11 1+ doisprezece +⋯+ ( ≤1, = ,≥ )
2 1
21 1+ 22 2 +⋯ + 2 ( ≤ , =, ≥ ) 2

⋮
1 1 + 2 2 + ⋯+ (≤ , =,≥)
≥0, (=
0,1 ) , ≥0yentero
 Consideraț ii de avut în vedere în
modele de Programare Liniară
1) A foloseș te 3 ore pe unitate ș i B foloseș te 2 ore pe unitate. Dacă trebuie folosite toate cele 100 de ore disponibile, restricț ia 3 +2 =100
va fi

2) Cu toate acestea, în majoritatea situaț iilor de afaceri, nu este obligatoriu să se folosească toate resursele; mai degrabă
la limitación es que se use, cuando mucho, lo que se tiene disponible:
3 +2 ≤100

3) A trebuie să fie cel puț in de două ori mai mare decât B, acest lucru poate fi scris ca: ≥2 ó -2 ≥0

4) Se doreș te ca A să fie cel puț in la fel de mare ca B - 2, ≥ -2 − ≥−2 − + ≤2

deci:
 Model de Planificare a Producț iei
Cererea pentru un produs în fiecare dintre cele 4 luni următoare este următoarea: luna 1, 2 unităț i; luna 2, 3 unităț i; luna 3, 6 unităț i; luna 4,
presupunând că capacitatea de producț ie ș i stocare este nelimitată, ș i că costul de producț ie pe unitate în orice perioadă este de 1,00 $ ș i preț ul
de vânzare în orice perioadă este de 3,00 $; totodată, costul de stocare pe unitate este de 1,00 $, determinaț i planul de producț ie ș i de
stocare pentru întreg orizontul de planificare.
Definirea variabilelor de Decizie:
= Îț i mulț umesc că eș ti aici ș i că eu sunt atât de fericit că am reuș it să mă întorc.=¿ 1,2,3,4, v t .

Calculul profitului pe perioadă: t =−2 1 − 2 −0 3 + 4 +28

.
C1= 1(x1) + 1(2 + x1– 2)
U1= x1+ 6 2+ 1 =2
Eu1= 3(x1) + 3(2)
=3
1 + 2

C2= 1(x2) + 1(x1+ x2– 3) 1+ 2-3+ 3 =6

U2= – x1+ x2+ 3
Eu2= 3(x2) 1+ 2+ 3- 9 + 4 =1

C3= 1(x3) + 1(x1+ x2- 3 + x3 - 6

Eu1= 3(x3)
U3= – x1- x2 + x3 + 9 ≥0 y întreg
C4= 1(x4) + 1(x1+ x2+ x3 – 9 + x4 - 1)
U4= – x1– x2 – x3 + x4 + 10
Eu4= 3(x4)
Ut= – 2x1– x2 – 0x3 + x4 + 28
Celda E3: =SUMAPRODUCTO(A2:D2;A3:D3)+28 Adăugaț i restricț ia
Celda E5: =SUMAPRODUCTO($A$3:$D$3;A5:D5) $A$3:$D$3 = întreg
Celda E6: =SUMAPRODUCTO($A$3:$D$3;A6:D6) un Solver

Celda E7: =SUMAPRODUCTO($A$3:$D$3;A7:D7)

Celula E8: =SUMAPRODUCTIE($A$3:$D$3;A8:D8)
 Rezultatul Solver
1 =0
2 =3
3 =6
4 =1

t =26

Venituri = 12(3) = 36
Costos = 10(1) =10
Utilitate = 36 – 10 = 26

Celda E3: =SUMAPRODUCTO(A2:D2;A3:D3)+28

Celda E5: =SUMAPRODUCTO($A$3:$D$3;A5:D5)
Celula E6: =SUMPRODUCT($A$3:$D$3;A6:D6)
Celda E7: =SUMAPRODUCTO($A$3:$D$3;A7:D7)
Celda E8: =SUMAPRODUCTO($A$3:$D$3;A8:D8)
 Modelul dietei
Problema dietei constă în determinarea cantităț ilor de diferiț i nutrienț i care trebuie ingerate pentru a asigura anumite condiț ii de nutriț ie ș i
minimizarea costului de achiziț ie al nutrienț ilor. Se consideră un caz cu cinci nutrienț i ș i cu minimul recomandat pentru nutrienț ii digestibili
(ND), proteine digerabile (PD), calciu (Ca) ș i fosfor (P) date în tabelul care urmează:
Tabela: Conț inuturi nutritive ale cinci alimente: ND, PD, Ca ș i P
Nutrienț i Cantidad requerida Mazăre A Ovăz Porumb B Salvado Linaza
ND 74.2 78.6 70.1 80.1 67.2 77.0
PD 14.7 6.50 9.40 8.80 13.7 30.4
Ca 0.14 0.02 0,09 0.03 0.14 0.41
P 0.55 0,27 0.34 0.30 1.29 0.86
Preț uri unitare ale alimentelor 1.0 0.5 2.0 1.2 3.0

Definiț ia variabilelor de Decizie:

= Textul nu poate fi tradus deoarece nu este recunoscut ca fiind în limbaj român sau în orice altă limbă cunoscută.=1,2,3,4y5, v tí .
Definiț ia Funcț iei Obiectiv:
t = 1 +0.5 2 +2 3 +1.2 4 +3 5
∗
=$0.793
t
. 1 =0
78.6
2 =1.530
6.50 3 =0

0.02 .023
0.27 5 =0

≥0
 Modelul de producț ie ș i inventar
Aceste modele au, de obicei, o cerere dinamică, adică variază în fiecare perioadă pe parcursul unui orizont de planificare, care poate fi
luni, săptămâni, etc. În fiecare perioadă se cunoaș te capacitatea de producț ie, capacitatea de stocare, costurile fixe care sunt independente de
cantitatea produsă, totuș i acest cost este zero dacă nu se produce într-o anumită perioadă. În plus, se cunoaș te costul unitar de producț ie în fiecare
perioada ș i costul de stocare pe unitate pe perioadă. În acest model, este necesar să se elaboreze planul de producț ie cu costul total de producț ie ș i de
stoc minim. Să presupunem că avem informaț iile în Tabelul care urmează ș i, în plus, se cunoaș te că există cinci unităț i la începutul tuturor
perioade ș i că cererile trebuie îndeplinite la timp, Care este planul de producț ie cu costuri minime?
Perioadă dn CPn CAn cfn canăn hn
1 7 12 7 1 3 2 1

2 5 9 9 2 5 1 2

3 9 3 6 3 4 3 3

4 2 7 4 1 3 1 4

5 6 8 5 2 2 2 5

1 =vor fi doar un grup de cuvinte, în mijlocul lor.=1 , 2 , 3 , 4 , 5

Calculând costurile în fiecare perioadă: = + +h ( + − )

=1+3
1 1 +2(5+ 1 - 7 ) ¿1+5 1 -4
2 =2+5 2 +1( 1- 2 + 2- 5 ) ¿2+1 1 +6 2 -7
3 =3+ 4 3 +3 ( 1+ 2-7+ 3- 9 ) ¿ 3+3 1 +3 2 +7 3 -48
4 =1+3 4 +1( 1+ 2+ 3-16+ 4 -2) ¿ 1+1 1+1 2+1 3 +4 4 -18
5 = 2+2 +
5 2 ( +1 +2 +
3 −418+ −6 5 ) ¿ 2+2 1 +2 2 +2 3+2 4 +4 5 -48
: t =1+2+3+1+2+12 1 +12 2 +10 3 +6 4 +4 -125
5
 t =1y1+2y2+ 3y3 +1y4 +2y5+12 1 +12 2 +10 3 +6 4 +4 5 -125
.
5+ 1− 7 ≤ 7
Restricciones de capacidad de + − ≤
1- 2 + 2−5≤9
almacenamiento:
1+ 2-7+ 3− 9 ≤ 6

1+ 2+ 3-16+ 4− 2 ≤ 4

1 + 2 + 3 + 4 −18+ 5−6≤5

5+ 1≥ 7
1- 2 + 2≥ 5
Restricț ii de atenț ie a cererilor: + ≥
1+ 2-7+ 3≥ 9

1+ 2+ 3-16+ 4≥ 2

1+ 2+ 3+ 4 −18+ 5> = 6

1≤12 ani 1
2≤ 9 y 2

3≤ 3 y 3
Restricț ii de capacitate de producț ie: ≤ (y )
4≤ 7 y 4

5≤ 8 y 5

y =0,1
≥0, y întreagă
 Soluț ie
y1 y2 y3 y4 y5 X1 X2 X3 X4 X5
1 2 3 1 2 12 12 10 6 4
1 1 1 1 1 4 9 3 2 6 106

1 4 <= 9
1 1 13 <= 16
1 1 1 16 <= 22
1 1 1 1 18 <= 22
1 1 1 1 1 24 <= 29
1 4 >= 2
1 1 13 >= 7
1 1 1 16 >= 16
1 1 1 1 18 >= 18
1 1 1 1 1 24 >= 24
-12 1 -8 <= 0
-9 1 0 <= 0
-3 1 0 <= 0
-7 1 -5 <= 0
-8 1 -2 <= 0
 Modelo Agropecuario

O familie de fermieri deț ine 100 de hectare de teren ș i dispune de 30000 de dolari pentru investiț ie. Membrii săi pot produce un total de 3500.
ore-om de muncă în timpul lunilor de iarnă (din mijlocul lui septembrie până în mijlocul lui mai), 4000 ore-om
în timpul verii. Dacă nu sunt necesare orele de muncă, membrii cei mai tineri ai familiei vor folosi pentru a lucra într-o
ferma vecină pentru 4,00 $/oră, în timpul lunilor de iarnă, ș i 4,50 $/oră, în timpul verii.
Venitul din numerar poate fi obț inut din trei culturi ș i două tipuri de animale: vaci de lapte ș i găini ponătoare. Nu este necesar
a investi în culturi. Cu toate acestea, fiecare vacă va necesita un efort financiar de 900 dolari, iar fiecare găină va necesita 7 dolari. Fiecare vacă va necesita 1,5
hectare de teren, 100 ore-om de muncă în timpul lunilor de iarnă ș i alte 50 de ore-om în timpul verii. Fiecare vacă
va produce un venit anual net în numerar de 800 $ pentru familie. Valorile corespunzătoare pentru găini sunt: nu există pământ, 0,6
ore de muncă pe timpul verii ș i un venit anual net în numerar de 5 dolari. Cotetul poate găzdui un maximum de 300 de găini ș i
dimensiunea grajdului limitează turma la un maxim de 32 de vaci. Orele de muncă ș i veniturile estimate pe ha plantate în fiecare dintre
cele trei culturi sunt prezentate în următorul tabel.

Distribuț ia Orelor Om (H-H) ș i Venituri estimate pe Ha. Familia dore ș te să ș tie câte hectare trebuie
Soya Porumb Avena a se planta în fiecare dintre culturi ș i câte vaci
H-H Iarnă : 20 35 10 găinile trebuie să aibă pentru a maximiza venitul
H-HVară : 50 75 40 net de efectiv. Determina ț i un model de
Venit Net în numerar pe Ha (US$) : 375 550 250 programare liniară pentru această problemă.
 Cerinț e de resurse pentru Cerinț e de resurse
Disponibilitatede
Resurse unitatedevaciș i găini por Ha de Cultvo
Resurse
Vaci Găini Soya Porumb Avena
Terenuri 1.5 0 Xs Xm Xa 100 ha
Bani 900 7 0 0 0 30 000 US$
HH-Iarnă 100 0 20 35 10 3500 H-H
HH-Verano 50 0,6 50 75 40 4000 H-H
Ingreso Neto US$ 800 5 375 550 250
Limitări <=32 <=300
Xv Xg

Función Objetivo:
Variabile de decizie:
Max I = 800Xv + 5Xg + 375Xs + 550Xm + 250Xa + 4Xi + 4.5Xve
Xv: N° de vaci de administrat (întreagă) s.a.
Xg: N° de găini de administrat (întreagă) 1.5Xv + 0Xg + Xs + Xm + Xa ≤ 100
Xs: cantitate de Has dedicată cultivării de soia (cont.) 900Xv + 7Xg ≤ 30000
Xm: cantitate de Has dedicate cultivării porumbului (cont.) 100Xv + 0Xg + 20Xs + 35Xm + 10Xa + Xi = 3500
Xa: cantitate de Has dedicate cultivării de Ovăz (cont.) 50Xv + 0.6Xg + 50Xs + 75Xm + 40Xa + Xve = 4000
Xi: cantitatea de H-H de iarnă care se vinde (cont.) Xv ≤ 32
Xve: cantitatea de H-H de vară care se vând (cont.) Xg ≤ 300
 Model Vârfuri ș i Sfori
Acest sistem constă din mai multe cabluri ș i grinzi conectate într-un mod particular. Câmpurile
cargas x1 ș i x2 acț ionează în punctul mediu al grinzilor 1 ș i 3 respectiv.
cuerdas A ș i B pot suporta o încărcătură maximă de 300; C ș i D, 200; iar E ș i F, 100.
Problema constă în determinarea încărcării totale admisibile pe care o poate suporta.
sistem în echilibru, sub echilibru de forț e ș i momente, dacă se presupune că
greutatea sforilor ș i a grinzii este neglijabilă.

1. t +t = 2 2

∑
2 t = −=
=0
2
2. t +t =t 2 2 2
t =t −t =
3. t +t = 1 +t +t 8

4. 5 2=10t
2
t =
Acesta este un exemplu( ) 2 3
( )( )
6 6
∑˙ : y
=0 5. 6 t =8 t
6. 10t =5 1+2 t +10t
t =t =
8 8
2
=
2
2

1 2 2
1 2
Din ecuaț ia 3 ș i ecuaț ia 6, se obț ine: t = + yt = +
2 10 2 5
 Model Vigas ș i Cârje
Acest sistem constă din mai multe frânghii ș i grinzi conectate într-un mod particular.
încărcările x1 ș i x2 acț ionează în punctul mijlociu al grinzilor 1 ș i 3, respectiv.
sforile A ș i B pot suporta o sarcină maximă de 300; C ș i D, 200; iar E ș i F, 100.
Problema constă în determinarea încărcăturii totale admisibile pe care o poate suporta.
sistemă fără colaps, sub echilibru de forț e ș i momente, dacă se presupune că
Greutatea corzilor ș i a grinzii este neglijabilă.

t =
2
t =
2
t =
1
+
2
= 1 + 2
2 2 2 10
.
2 3 2 12 2
t = t = t = + 2 ≤100
8 8 2 5 2
2 ≤200 ≤200
2
8
3 2
≤200
8
+ ≤300
1 2
2 10
22
1
+ ≤300
2 5