Slide 1
Op imiza¸c˜ao Combina ´o ia:
Modelos e Algo i mos
T anspa ˆencias de apoio `a lecciona¸c˜ao de aulas e´o icas
Ve s˜ao 1
c
°2001
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 1
Slide 2
Modelos de Op imiza¸c˜ao Combina ´o ia
Slide 3
P oblemas de Op imiza¸c˜ao
Ins ˆancia de um P oblema de Op imiza¸c˜ao
Uma ins ˆancia de um P oblema de Op imiza¸c˜ao ´e um pa (F, c), onde:
F´e um conjun o qualque (o dom´ınio das solu¸c˜oes admiss´ı eis)
c´e a un¸c˜ao cus o, e co esponde a um mapeamen o c:F → R
A solu¸c˜ao ´op ima se ´a um ∈ F al que:
∀y∈F c( )≤c(y)
Um P oblema de Op imiza¸c˜ao ´e um conjun o de Ins ˆancias de um
P oblema de Op imiza¸c˜ao
(in Papadimi iou, S eigli z pp.4)
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 2
Slide 4
Op imiza¸c˜ao Combina ´o ia OC
P oblemas de Op imiza¸c˜ao
com a i´a eis con ´ınuas
P oblemas Con ´ınuos
Solu¸c˜ao: conjun o de n´ume os e-
ais
com a i´a eis disc e as
P oblemas Combina ´o ios
Solu¸c˜ao: objec o pe encen e a um
conjun o ini o ou en ˜ao in ini o
enume ´a el, po exemplo in ei os,
conjun os, pe mu a¸c˜oes ou g a os.
Slide 5
P oblema da Mochila
“Knapsack P oblem”KP
Dados:
•um conjun o de ipos de objec os em que cada ipo em um alo e um
peso associados
•uma mochila com um limi e de peso anspo ´a el
P e ende-se enche a mochila, n˜ao ul apassando o limi e m´aximo de peso e
maximizando o alo o al dos objec os anspo ados.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 3
Slide 6
P oblema da Mochila (KP)
´
Indices
j ipo de objec o, j∈ {1,...,n};
Va i´a eis de decis˜ao
xjn´ume o de objec os do ipo ja coloca den o da mochila
Coe icien es
wjpeso de cada um dos objec os do ipo j;
cj alo de cada um dos objec os do ipo j;
blimi e m´aximo de peso a anspo a na mochila.
Fun¸c˜ao objec i o
max Z=Pn
j=1 cjxj
Res i¸c˜oes Pn
j=1 wjxj≤b
∀jxj≥0in ei o
Slide 7
P oblema da Mochila 0–1
“0–1 Knapsack P oblem”(0–1KP)
Dados:
•um conjun o de objec os di e en es em que cada objec o em um alo e
um peso associados
•uma mochila com um limi e de peso anspo ´a el
P e ende-se enche a mochila, n˜ao ul apassando o limi e m´aximo de peso e
maximizando o alo o al dos objec os anspo ados.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 4
Slide 8
P oblema da Mochila 0–1 (0–1KP) Modelo
´
Indices
jobjec o, j∈ {1,...,n};
Va i´a eis de decis˜ao
xj=






1 se objec o j
o colocado na mochila
0 se n˜ao
Coe icien es
wjpeso do objec o j;
cj alo do objec o j;
blimi e m´aximo de peso a anspo -
a na mochila.
Fun¸c˜ao objec i o
max Z=Pn
j=1 cjxj
Res i¸c˜oes
Pn
j=1 wjxj≤b
∀jxj∈ {0,1}
Slide 9
Ci cui os Hamil onianos
De ini¸c˜ao de Ci cui o Hamil oniano: Um ci cui o diz-se Hamil oniano,
se passa uma e uma s´o ez po odos os ´e ices de uma ede.
A designa¸c˜ao p o ´em do islandˆes Hamil on que, em 1857 p opˆos um jogo
denominado “A ound he Wo ld”. Nesse jogo, os ´e ices de um dodecaed o
de madei a ep esen a am as 20 cidades mais impo an es do mundo na
´epoca. O objec i o do jogo consis ia em encon a um pe cu so a a ´es dos
´e ices do dodecaed o, com in´ıcio e im no mesmo ´e ice (cidade) e que
passasse po cada ´e ice (cidade) apenas uma ez.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP

Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 5
Slide 10
P oblema do Caixei o Viajan e
“T a elling Salesman P oblem”(TSP)
O p oblema do caixei o iajan e ´e um p oblema de op imiza¸c˜ao associado `a
de e mina¸c˜ao dos ci cui os hamil onianos num g a o qualque .
P oblema do Caixei o Viajan e:
P e ende-se encon a o caminho mais cu o pa a um caixei o iajan e que
sai de uma cidade, isi a n ou as cidades e ol a `aquela de onde pa iu, sem
epe i nenhuma das cidades isi adas (Ci cui o Hamil oniano mais cu o).
Slide 11
P oblema do Caixei o Viajan e (TSP)
Fo mula¸c˜ao de Dan zig-Fulke son-Johnson
Fo mula¸c˜ao do TSP como um p oblema de p og ama¸c˜ao bin´a ia sob e um
g a o G= (V, A), onde V´e o conjun o de ´e ices (cidades) e A´e o conjun o
de a cos (pe cu sos di ec os en e duas cidades)
´
Indices
icidade, i∈ {1,...,n}
jcidade, j∈ {1,...,n}
Coe icien es
dij cus o associado ao pe cu so (a co)
en e cidade ie cidade j.
Va i´a eis de decis˜ao
xij =






1 se o pe cu so di ec o (a co) de i
pa a jes i e inclu´ıdo na solu¸c˜ao
0 se n˜ao
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 6
Slide 12
P oblema do Caixei o Viajan e (TSP)
Fo mula¸c˜ao de Dan zig-Fulke son-Johnson (con .)
Fun¸c˜ao objec i o
min
n
X
i=1
n
X
j=1
dijxij
Res i¸c˜oes
Pn
i=1 xij = 1 ∀j∈V
Pn
j=1 xij = 1 ∀i∈V
Pi,j∈Sxij ≤ |S|−1∀S⊂V
xij ∈ {0,1} ∀i,j∈V,i6=j
|S| ep esen a o n´ume o de ´e ices do subg a o S.
No e-se que em S≡Vn˜ao es ´a conside ado em S⊂V.
Slide 13
P oblema do Caixei o Viajan e (TSP)
Fo mula¸c˜ao de Dan zig-Fulke son-Johnson
Elimina¸c˜ao de subg a os
1
2
3
45
6
1
2
3
45
6
1
2
3
45
6
1
2
3
45
6
S={1,3,4}
x13 = 1 ≤ |S|−1 = 2
S={4,5,6}
x45 +x56 +x64 = 3 £|S|−1 = 2
1
2
3
45
6
1
2
3
45
6
S={1,2,3}
x23 +x31 = 2 ≤ |S|−1 = 2
S={4,5,6}
x45 +x56 = 2 ≤ |S|−1 = 2
e c . . .
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 7
Slide 14
Cobe u a de conjun os “Se Co e ing”
Dados:
•um conjun o de clien es
•um conjun o de a maz´ens
•uma ma iz de liga¸c˜oes clien es–a maz´ens
•cus os de abe u a de cada um dos a maz´ens
P e ende-se o nece odos os clien es, minimizando os cus os de abe u a
dos a maz´ens.
Slide 15
Cobe u a de conjun os Modelo
´
Indices
iclien e, i∈ {1,...,m};
ja maz´em, j∈ {1,...,n};
Va i´a eis de decis˜ao
xj=


1 se a maz´em j o abe o.
0 se n˜ao
Coe icien es
aij 1 se clien e ipode se o necido
pelo a maz´em j, 0 se n˜ao;
cjcus o associado `a abe u a do a -
maz´em j.
Fun¸c˜ao objec i o
min Z=Pn
j=1 cjxj
Res i¸c˜oes
∀iPn
j=1 aijxj≥1
∀jxj∈ {0,1}
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 8
Slide 16
Pa i¸c˜ao de conjun os “Se Pa i ioning”
Dados:
•um conjun o de clien es
•um conjun o de a maz´ens
•uma ma iz de liga¸c˜oes clien es–a maz´ens
•cus os de abe u a de cada um dos a maz´ens
P e ende-se o nece odos os clien es, minimizando os cus os de abe u a
dos a maz´ens. Cada clien e s´o pode ica ligado a um a maz´em.
Slide 17
Pa i¸c˜ao de conjun os “Se Pa i ioning” Modelo
´
Indices
iclien e, i∈ {1,...,m};
ja maz´em, j∈ {1,...,n};
Va i´a eis de decis˜ao
xj=


1 se a maz´em j o abe o.
0 se n˜ao
Coe icien es
aij 1 se clien e ipode se o necido
pelo a maz´em j, 0 se n˜ao;
cjcus o associado `a abe u a do a -
maz´em j.
Fun¸c˜ao objec i o
min Z=Pn
j=1 cjxj
Res i¸c˜oes
∀iPn
j=1 aijxj= 1
∀jxj∈ {0,1}
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 15
Slide 30
Classi ica¸c˜ao dos p oblemas
P oblemas de decis˜ao (sup˜oem apenas uma espos a do ipo SIM ou
N˜
AO).
Exemplo: Pa a uma dada ins ˆancia do TSP h´a algum ci cui o cujo cus o
(dis ˆancia o al pe co ida) seja in e io a K?
•Classe P– Conjun o de p oblemas de decis˜ao pa a os quais exis e um
algo i mo que co e em empo polinomial.
•Classe NP – Conjun o de p oblemas de decis˜ao pa a os quais n˜ao se
conhece um algo i mo polinomial mas que que pode se esol ido em
empo polinomial po uma abs ac¸c˜ao algo ´ı mica chamada “algo i mo
n˜ao de e min´ıs ico”.a
aInco po a ins u¸c˜oes do ipo “go o bo h label1, label2” o iginando um ´a o e de p o-
cessos a co e em pa alelo. O p imei o amo que esponde “SIM” p´a a a execu¸c˜ao e o
algo i mo esponde “SIM”. Se esse amo i e espondido ap´os um n´ume o polinomial de
passos, en ˜ao o algo i mo diz-se n˜ao-de e min´ıs ico
Slide 31
Classi ica¸c˜ao dos p oblemas (con .)
•Classe NP −comple a – Sub-conjun o de p oblemas da classe NP aos
quais qualque ou o p oblema da classe pode se eduzido.
Se qualque p oblema da classe NP pude se eduzido a um p oblema
Pen ˜ao diz-se que Ppe ence `a classe NP −comple a.
P oblemas de op imiza¸c˜ao (acha a melho solu¸c˜ao)
S˜ao na u almen e eduzidos a uma sequˆencia de p oblemas de decis˜ao:
epe e-se a pe gun a, com alo es sucessi amen e mais exigen es, a ´e a
espos a se n˜ao.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP

Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 16
Slide 32
Abo dagens `a esolu¸c˜ao de P oblemas de Op imiza¸c˜ao
Combina ´o ia
T´ecnicas exac as — ob ˆem e ga an em uma solu¸c˜ao ´op ima.
A ingi a solu¸c˜ao ´op ima pode se di ´ıcil (mui o demo ado), ou mesmo
imposs´ı el (o empo co esponden e `a ida passada do sis ema sola pode ia
n˜ao se su icien e) e nem seque se especialmen e impo an e pa a a
aplica¸c˜ao conc e a que se p e ende esol e .
↓
T´ecnicas ap oximadas ou m´e odos heu ´ıs icos — ou n˜ao ob ˆem a
solu¸c˜ao ´op ima ou, se a ob ˆem, n˜ao o sabem... Em compensa¸c˜ao s˜ao capazes
de ob e “boas” solu¸c˜oes mui o apidamen e.
Slide 33
Bibliog a ia
•Goldba g, Ma co Cesa e Luna, Hen ique Pacca (2000). O imiza¸c˜ao
Combina ´o ia e P og ama¸c˜ao Linea , Edi o a CAMPUS.
•Golden, B.L. and S ewa , W.R. (1985). Empi ical analysis o heu is ics
in The T a eling Salesman P oblem, John Wiley & Sons, Inc..
•Nemhause , Geo ge L. e Wolsey, Lau ence A. (1988). In ege and
Combina o ial Op imiza ion John Wiley & Sons, Inc..
•Papadimi io, Ch is us H. e S eigli z, Kenne h (1982). Combina o ial
Op imiza ion – Algo i hms and Complexi y P en ice Hall, Inc..
•Sousa, Jo ge Pinho (1991). Apon amen os de Op imiza¸c˜ao
Combina ´o ia.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 17
Slide 34
T´ecnicas exac as pa a esolu¸c˜ao de p oblemas
de op imiza¸c˜ao
Slide 35
T´ecnicas exac as
•Enume a¸c˜ao expl´ıci a — po de ini¸c˜ao de p oblema de Op imiza¸c˜ao
Combina ´o ia, ge ando ea aliando odas as solu¸c˜oes admiss´ı eis ´e
poss´ı el ob e a solu¸c˜ao ´op ima.
•Enume a¸c˜ao impl´ıci a — n˜ao se ge ando odas as solu¸c˜oes admiss´ı eis,
elas s˜ao no en an o conside adas e implici amen e a aliadas.
Exemplos: M´e odo de pesquisa em ´a o e com enume a¸c˜ao e limi a¸c˜ao
(“b anch and bound”); limi es supe io es e in e io es ao alo da solu¸c˜ao
´op ima.
•Fo mula¸c˜ao dos p oblemas em modelos de p og ama¸c˜ao in ei a
( a i´a eis de decis˜ao assumem alo es no conjun o dos n´ume os
in ei os), ou mesmo bin´a ia ( a i´a eis apenas com dois alo es poss´ı eis:
0 ou 1), e consequen e esolu¸c˜ao com algo i mos ap op iados.
No a: Es as o mula¸c˜oes podem amb´em se usadas pa a ob e limi es
pa a o alo da solu¸c˜ao ´op ima a a ´es de elaxa¸c˜oes.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 18
Slide 36
T´ecnicas exac as e elaxa¸c˜oes
Relaxa¸c˜ao — N˜ao conside a¸c˜ao de uma ou mais es i¸c˜oes do p oblema
o iginal PO, ans o mando-o num p oblema mais simples de esol e P R,
sabendo-se que os alo es ´op imos das un¸c˜oes objec i o obedecem `a
seguin e ela¸c˜ao (assumindo um p oblema de minimiza¸c˜ao):
?
P R ≤ ?
P O
( adu¸c˜ao: ao i a es i¸c˜oes a solu¸c˜ao s´o pode melho a , ou ica na
mesma).
Relaxa¸c˜ao linea – ans o ma¸c˜ao de um p oblema em n´ume os in ei os num
p oblema com a i´a eis eais (deixa-se cai a es i¸c˜ao “e in ei os” ou
“∈ N0”−→ u iliza¸c˜ao do m´e odo simplex pa a a sua esolu¸c˜ao em ez dos
mui o mais complexos (e ex ao dina iamen e mais demo ados) m´e odos de
pesquisa em ´a o e).
Slide 37
M´e odo de “b anch and bound”
Baseia-se na ideia de uma enume a¸c˜ao in eligen e das solu¸c˜oes candida as a
solu¸c˜ao ´op ima in ei a de um p oblema, e ec uando sucessi as pa i¸c˜oes do
espa¸co das solu¸c˜oes e co ando a ´a o e de pesquisa a a ´es da conside a¸c˜ao
de limi es calculados ao longo da enume a¸c˜ao.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 19
Slide 38
Rep esen a¸c˜ao g ´a ica
Conside e-se o seguin e p oblema
de P og ama¸c˜ao In ei a:
Maximiza :
F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0e in ei as
e a sua ep esen a¸c˜ao g ´a ica:
y
7
6
5
4
3
2
1
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
1 2 3 4 5 6 7 8 x
Solu¸c˜ao ´op ima in ei a: x= 1 e y= 4.
Slide 39
Resolu¸c˜ao da elaxa¸c˜ao linea
P oblema PL0:
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
Solu¸c˜ao ´op ima n˜ao in ei a:
x= 3.5 e y= 3.5; F= 35
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 20
Slide 40
Rami ica¸c˜ao em x:x≤3
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 3
Solu¸c˜ao (n˜ao in ei a):
x= 3 e y= 3.6; F= 34.5
Slide 41
Rami ica¸c˜ao em x:x≥4
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≥4
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 4
Sem solu¸c˜oes admiss´ı eis.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP

Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 21
Slide 42
Rami ica¸c˜ao em y:y≤3
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≤3
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 3
y = 3
Solu¸c˜ao (in ei a):
x= 3 e y= 3; F= 30
Ob en¸c˜ao de um limi e in e io ⇒
Solu¸c˜oes n˜ao in ei as com alo de F
in e io ou igual a 30 n˜ao p ecisam de
se explo adas!
Slide 43
Rami ica¸c˜ao em y:y≥4
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 3
y = 4
Solu¸c˜ao (n˜ao in ei a):
x= 1.7 e y= 4; F= 33.2
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 22
Slide 44
Rami ica¸c˜ao em x:x≤1
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
x≤1
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 1
y = 4
x = 3
Solu¸c˜ao (n˜ao in ei a):
x= 1 e y= 4.2; F= 32.5
Slide 45
Rami ica¸c˜ao em x:x≥2
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
x≥2
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 2
y = 4
x = 3
Sem solu¸c˜oes admiss´ı eis.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 23
Slide 46
Rami ica¸c˜ao em y:y≤4
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
x≤1
y≤4
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 1
y = 4
x = 3
Solu¸c˜ao (in ei a):
x= 1 e y= 4; F= 31
Melho solu¸c˜ao in ei a a ´e ao mo-
men o!
Slide 47
Rami ica¸c˜ao em y:y≥5
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
x≤1
y≥5
5x - 4y = 10
x = 3.5
4/7x + 2y = 9
Max F = 3x + 7y
y
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 x
x = 1
y = 4
x = 3
y = 5
Sem solu¸c˜oes admiss´ı eis.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 24
Slide 48
´
A o e de pequisa do “B anch-and-Bound”
Slide 49
Limi es
Limi es (in e io es e supe io es):
• o nam o algo i mo de “b anch & bound” mais e icien e ao pe mi i
desca a n´os da ´a o e de pesquisa ainda n˜ao comple amen e
explo ados, pela ce eza de que nunca o igina ˜ao solu¸c˜oes melho es do
que as que j´a emos.
•pe mi em “medi a dis ˆancia” (em e mos de alo da un¸c˜ao objec i o)
a que es amos da solu¸c˜ao ´op ima.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 31
Slide 62
Exemplo – um p oblema (simples) de planeamen o da
p odu¸c˜ao
Dados – 6 pe ´ıodos e 8 encomendas.
Objec i o – p oduzi o mais p ´oximo poss´ı el da da a de en ega.
123456
C 452521
Capacidade dispon´ı el C em cada
pe ´ıodo
123456
C
1
2
3
4
5
e12345678
qe11222333
de21312513
Encomendas e, com quan idades
qee da as de en ega de
3
1
6
2
45
78
Slide 63
Exemplo – con inua¸c˜ao
Va i´a eis de decis˜ao: xe ∈ {0,1}que alem 1 se a encomenda e´e p oduzida
no pe ´ıodo .
Res i¸c˜oes:
•Cada encomenda em que se p oduzida uma e uma s´o ez: P xe = 1
•As capacidades dos pe ´ıodos ˆem que se espei adas:
∀ Peqe×xe ≤C
Obse a¸c˜ao: h´a encomendas que, dadas as espec i as quan idades e as
capacidades dos pe ´ıodos, nunca pode ˜ao se p oduzidas em simul ˆaneo.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP

Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 32
Slide 64
Exemplo – con inua¸c˜ao
Reg as pa a a ge a¸c˜ao de desigualdades ´alidas:
1. No pe ´ıodo 1 (capacidade 4) n˜ao se podem p oduzi simul aneamen e
duas encomendas com quan idades 2 e 3, ou 3 e 3.
2. Nos pe ´ıodos 2 e 4 (capacidade 5) n˜ao se podem p oduzi
simul aneamen e duas encomendas com quan idades 3.
3. Nos pe ´ıodos 3 e 5 (capacidade 2) n˜ao se podem p oduzi
simul aneamen e duas encomendas com quan idades 2, duas encomendas
com quan idades 1 e 2, nem qualque encomenda com quan idade 3.
4. No pe ´ıodo 6 (capacidade 1) apenas se podem p oduzi encomendas com
quan idade 1.
Slide 65
Exemplo – conclus˜ao
Solu¸c˜ao da elaxa¸c˜ao linea do exemplo:
123456
C
1
2
3
4
5
3
1
6
2
4
5
7
8
7
5
8
3
Es a solu¸c˜ao iola uma desigual-
dade do ipo 1 e uma desigualdade
do ipo 2.
S˜ao en ˜ao desigualdades ´alidas:
x41 +x71 ≤1
x64 +x84 ≤1
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 33
Slide 66
Bibliog a ia
•Al es, Jos´e Ca los (1989). P o as de Ap id˜ao Cien ´ı ica e Capacidade
Pedag´ogica. FEUP.
•Ca a illa, Ma ia An ´onia (1996). Modelos e Algo i mos pa a o
Planeamen o Hie ´a quico da P odu¸c˜ao – Aplica¸c˜oes a um Caso de
Es udo, Tese de Dou o amen o, FEUP.
•Goldba g, Ma co Cesa e Luna, Hen ique Pacca (2000). O imiza¸c˜ao
Combina ´o ia e P og ama¸c˜ao Linea , Edi o a CAMPUS.
•Nemhause , Geo ge L. e Wolsey, Lau ence A. (1988). In ege and
Combina o ial Op imiza ion John Wiley & Sons, Inc..
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 34
Slide 67
Algo i mos pa a Resolu¸c˜ao Ap oximada de
P oblemas de Op imiza¸c˜ao Combina ´o ia
Slide 68
T´ecnicas ap oximadas pa a a esolu¸c˜ao de p oblemas de
Op imiza¸c˜ao Combina ´o ia
M´e odos Heu ´ıs icos
Tˆem como objec i o ob e mui o boas solu¸c˜oes de uma o ma e icien e. N˜ao
ob ˆem a solu¸c˜ao ´op ima, ou pelo menos n˜ao s˜ao capazes de ga an i que a
solu¸c˜ao boa que ob ˆem ´e de ac o a ´op ima.
Ca ac e ´ıs icas dos algo i mos heu ´ıs icos
•Tempos de execu¸c˜ao “cu os”
•Facilidade de implemen a¸c˜ao
•Flexibilidade
•Simplicidade
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 35
Slide 69
Tipos de algo i mos heu ´ıs icos
•Cons u i os – Cons oem uma solu¸c˜ao, passo a passo, segundo um
conjun o de eg as p ´e-es abelecido.
•de Melho amen os – Pa em de uma solu¸c˜ao admiss´ı el qualque e
p ocu am melho ´a-la a a ´es de sucessi as pequenas al e a¸c˜oes.
•Compos os – Tˆem p imei o uma ase cons u i a e depois uma ase de
melho amen os.
Es es ipos de heu ´ıs icas se ˜ao ap esen ados e exempli icados u ilizando
como caso de es udo o P oblema do Caixei o Viajan e.
Slide 70
Algo i mos (heu ´ıs icos) cons u i os
Cons oem uma solu¸c˜ao, passo a passo, segundo um conjun o de eg as
p ´e-es abelecido. Es as eg as es ˜ao elacionadas com:
•a escolha do sub-ciclo inicial (ou o pon o inicial) – inicializa¸c˜ao;
•um c i ´e io de escolha do elemen o seguin e a jun a `a solu¸c˜ao –
selec¸c˜ao;
•a selec¸c˜ao da posi¸c˜ao onde esse no o elemen o se ´a inse ido – inse ¸c˜ao.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 36
Slide 71
TSP – Vizinho mais p ´oximo
1. Inicializa¸c˜ao – Come¸ca com um ci cui o pa cial cons i u´ıdo po uma
cidade isozinha, escolhida a bi a iamen e;
2. Selec¸c˜ao – Seja (1,...,k) o pe cu so pa cial ac ual (k < n). Encon a a
cidade k+ 1, que ainda n˜ao az pa e do ci cui o e que es ´a mais
p ´oxima de k.
3. Inse ¸c˜ao – Inse i k+ 1 no im do ci cui o pa cial.
4. Se odas as cidades es ˜ao inse idas, PARAR, sen˜ao ol a a 2.
Slide 72
Vizinho mais p ´oximo – exemplo
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32Comp imen o o al do pe cu so: 19
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP

Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 37
Slide 73
TSP – Inse ¸c˜ao mais p ´oxima de cidade a bi ´a ia
1. Inicializa¸c˜ao – Come¸ca com um ci cui o pa cial cons i u´ıdo po uma
cidade isozinha, escolhida a bi a iamen e;
Encon a a cidade j al que cij (dis ˆancia de iaj) ´e m´ınima e o ma o
ci cui o pa cial (i, j).
2. Selec¸c˜ao – Dado um ci cui o pa cial, selecciona a bi a iamen e uma
cidade kainda n˜ao pe encen e ao ci cui o pa cial.
3. Inse ¸c˜ao – Encon a a a es a {i, j}no ci cui o pa cial que minimiza
cik +ckj −cij. Inse i ken e iej.
4. Se odas as cidades es ˜ao inse idas, PARAR, sen˜ao ol a a 2.
Slide 74
Inse ¸c˜ao mais p ´oxima de cidade a bi ´a ia – exemplo
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32
12
3
56
4
5
3
5
3
6
4
4
3
2
3
3
45
32Comp imen o o al do pe cu so: 17
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 38
Slide 75
TSP – Inse ¸c˜ao mais p ´oxima
1. Inicializa¸c˜ao – Come¸ca com um ci cui o pa cial cons i u´ıdo po uma
cidade isozinha, escolhida a bi a iamen e;
2. Selec¸c˜ao – Encon a as cidades kej(jpe encendo ao ci cui o pa cial
ekn˜ao pe encendo) al que ckj ´e minimizado.
3. Inse ¸c˜ao – Encon a a a es a {i, j}no ci cui o pa cial que minimiza
cik +ckj −cij. Inse i ken e iej.
4. Se odas as cidades es ˜ao inse idas, PARAR, sen˜ao ol a a 2.
Es a heu ´ıs ica em a a ian e “Inse ¸c˜ao mais dis an e” que subs i ui o
passo de selec¸c˜ao po :
2. Selec¸c˜ao – Encon a as cidades kej(jpe encendo ao ci cui o pa cial
ekn˜ao pe encendo) al que ckj ´e maximizado.
Slide 76
TSP – Inse ¸c˜ao mais ba a a
1. Inicializa¸c˜ao – Come¸ca com um ci cui o pa cial cons i u´ıdo po uma
cidade isozinha, escolhida a bi a iamen e;
2. Selec¸c˜ao – Encon a as cidades k,iej(iej o mando uma a es a do
ci cui o pa cial e kn˜ao pe encendo a esse ci cui o) al que
cik +ckj −cij ´e minimizado.
3. Inse ¸c˜ao – Inse i ken e iej.
4. Se odas as cidades es ˜ao inse idas, PARAR, sen˜ao ol a a 2.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 39
Slide 77
TSP – In ´oluc o con exoa
1. Inicializa¸c˜ao – Come¸ca com um ci cui o pa cial cons i u´ıdo pelo
in ´oluc o con exo de odas as cidades;
2. Inse ¸c˜ao – Pa a cada cidade kn˜ao inse ida no ci cui o pa cial,
encon a a a es a {i, j}do ci cui o pa cial que minimiza cik +ckj −cij.
3. Selec¸c˜ao – De en e odos os ios {i, j, k} o mados e a aliados no passo
2, de e mina o io {i?, j?, k?} al que ci?k?+ck?j?
ci?j?´e m´ınimo.
4. Inse i k?en e i?ej?.
5. Se odas as cidades es ˜ao inse idas, PARAR, sen˜ao ol a a 2.
aIn ´oluc o con exo do conjun o A– o ma con exa que con ´em no seu in e io ou on-
ei a odos os elemen os do conjun o A
Slide 78
TSP – Fus˜ao mais p ´oxima
1. Inicializa¸c˜ao – Come¸ca com nci cui os pa ciais cons i u´ıdos, cada um,
po uma cidade isozinha;
2. Selec¸c˜ao – Encon a as cidades iek(ipe encendo a um ci cui o
pa cial Cekpe encendo a um ou o ci cui o C0) al que cik ´e
minimizado.
3. Inse ¸c˜ao – Sejam i,j,kelcidades ais que a a es a {i, j} ∈ C,
{k, l} ∈ C0ecik +cjl −cij −ckl ´e minimizado.
Inse i {i, k}} e{j, l}} e e i a {i, j}} e{k, l}}.
4. Se exis i um ´unico ci cui o, PARAR, sen˜ao ol a a 2.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 40
Slide 79
O p oblema da ´a o e supo e de comp imen o m´ınimo
•De ini¸c˜oes (pa a g a os n˜ao o ien ados):
–uma ´a o e ´e um g a o conexo que n˜ao con ´em ciclos;
–um g a o diz-se conexo se exis i uma cadeia (sequˆencia de amos)
ligando qualque pa de n´os en e si.
•P oblema:
De e mina a ´a o e de comp imen o o al m´ınimo que supo e odos os
n´os da ede (i.e. que ligue odos os n´os da ede) (“minimal spanning
ee”).
•Aplica¸c˜oes:
– edes de comunica¸c˜oes;
– edes de dis ibui¸c˜ao de ene gia.
Slide 80
Algo i mo de P im (guloso – “G eedy P ocedu e”)
1. Selecciona um n´o a bi a iamen e, e lig´a-lo ao n´o mais p ´oximo;
2. Iden i ica o n´o ainda isolado que es eja mais p ´oximo de um n´o j´a
ligado, e liga es es dois n´os;
3. Se odos os n´os es i e em ligados en e si, PARAR, sen˜ao ol a a 2.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP
Op imiza¸c˜ao Combina ´o ia: modelos e algo i mos 47
Slide 93
Bibliog a ia
•Goldba g, Ma co Cesa e Luna, Hen ique Pacca (2000). O imiza¸c˜ao
Combina ´o ia e P og ama¸c˜ao Linea , Edi o a CAMPUS.
•Golden, B.L. and S ewa , W.R. (1985). Empi ical analysis o heu is ics
in The T a eling Salesman P oblem, John Wiley & Sons, Inc..
•Sousa, Jo ge Pinho (1991). Apon amen os de Op imiza¸c˜ao
Combina ´o ia.
Jos´e Fe nando Oli ei a, Ma ia An ´onia Ca a illa – FEUP