Faculdade de Engenha ia da Uni e sidade do Po o
Licencia u a em Engenha ia Elec o ´
ecnica e de Compu ado es
Exe c´ıcios de
In es iga¸c˜ao Ope acional
An ´
onio Miguel Gomes
Jo˜
ao Cla o
Jos´
e Ca los dos San os Al es
Jos´
e Fe nando Oli ei a
Jos´
e Soei o Fe ei a
Ma ia An ´
onia Ca a illa
c
2003, 2001, 1999
1
Exe c´ıcios de Fo mula¸c˜ao
Enunciados
Exe c´ıcios de Fo mula¸c˜ao
Enunciados 2
P oblema 1
“Publica¸c˜oes Pol´emicas” ai publica uma au obiog a ia de um pol´ı ico con o e so, e
admi e que a 1aedi¸c˜ao ai se endida po comple o se n˜ao hou e a asos. Foi decidido
que e s˜oes de Luxo (L) e No mal (N) ˜ao apa ece simul aneamen e e s˜ao conhecidas as
seguin es condicionan es do p ojec o:
(a) O depa amen o de imp ess˜ao pode p oduzi no m´aximo 10000 c´opias (incluindo
e s˜oes L e N).
(b) O depa amen o de encade na¸c˜ao pode conclui 12000 c´opias N ou 8000 c´opias L se
abalha em cada um des es ipos isoladamen e. Se p oduzi as duas e s˜oes, pode
p oduzi p opo ¸c˜oes daquelas quan idades que o alizem 1.
(c) O a maz´em pode despacha um m´aximo de 15000 c´opias N ou 9000 c´opias L, ou
p opo ¸c˜oes que o alizem 1.
(d) J´a exis em pedidos de 2000 e s˜oes N e 1000 e s˜oes L, que de e ˜ao se sa is ei os
na 1aedi¸c˜ao.
(e) Pelo menos 1
4do o al das c´opias de e ´a se em e s˜ao de Luxo (L).
O luc o esul an e da enda de uma c´opia N ´e de 600$00 e de uma c´opia L ´e de 720$00.
“Publica¸c˜oes Pol´emicas” p e ende sabe qual o n´ume o de c´opias de cada ipo a p oduzi
de modo a ob e o maio luc o poss´ı el.
(a) Fo mule es e p oblema como P og ama¸c˜ao Linea .
(b) Resol a-o g a icamen e, ilus ando o conjun o das solu¸c˜oes admiss´ı eis.
(c) Resol a pelo m´e odo Simplex uma e s˜ao simpli icada do p oblema, em que n˜ao se
conside am as condi¸c˜oes (d) e (e).
Qual o signi icado que a ibui ao alo das a i´a eis de olga?
A solu¸c˜ao ob ida se ´a a solu¸c˜ao ´op ima do p oblema inicial?
(d) Subs i ua a condi¸c˜ao (e) pela seguin e:
Se hou e p odu¸c˜ao de c´opias na e s˜ao L en ˜ao o seu n´ume o de e ´a se supe io a
2000.
Como inclui ia es a condi¸c˜ao no modelo o mulado, man endo a sua es u u a linea
(in ei a)?
Jus i ique.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Enunciados 3
P oblema 2
Conside e o seguin e P oblema de Dis ibui¸c˜ao que consis e na de e mina¸c˜ao de uma
es a ´egia ´op ima de dis ibui¸c˜ao que sa is a¸ca a p ocu a e, ao mesmo empo, espei e as
capacidades e limi a¸c˜oes exis en es:
Uma emp esa em duas ´ab icas e qua o a maz´ens e ende p odu os a seis clien es
que podem se abas ecidos a pa i dos a maz´ens ou di ec amen e das ´ab icas. A emp esa
supo a os cus os de dis ibui¸c˜ao ap esen ados nas abelas 1 e 2. Os a¸cos indicam que a
en ega co esponden e n˜ao se ealiza.
O igens
Des inos B agan¸ca ´
E o a
A maz´ens ( ´ab ica) ( ´ab ica)
Coimb a 0.5 —
Fa o 1.0 0.2
Lisboa 0.8 0.6
Po o 0.4 0.8
Tabela 1: Cus os de dis ibui¸c˜ao (em 1000$ po on.)
O igens
Des inos B agan¸ca ´
E o a Coimb a Fa o Lisboa Po o
Clien es ( ´ab ica) ( ´ab ica) (a maz´em) (a maz´em) (a maz´em) (a maz´em)
C1 1.0 2.0 — 1.0 — —
C2 — — 1.5 0.5 1.5 —
C3 1.5 — 0.5 0.5 2.0 0.2
C4 2.0 — 1.5 1.0 — 1.5
C5 — — — 0.5 0.5 0.5
C6 1.0 — 1.0 — 1.5 1.5
Tabela 2: Cus os de dis ibui¸c˜ao (em 1000$ po on.)
Nas abelas 3 e 4 es ˜ao ep esen adas as capacidades mensais m´aximas das ´ab icas e
dos a maz´ens. Na abela 5, ap esen a-se a p ocu a ´ıpica mensal dos clien es.
F´ab ica Capacidade
( oneladas)
B agan¸ca 150 000
´
E o a 200 000
Tabela 3: Capacidade m´axima mensal de p odu¸c˜ao das ´ab icas
O objec i o da emp esa ´e a de e mina¸c˜ao dum plano ´op imo de dis ibui¸c˜ao que min-
imize os cus os em ques ˜ao.
Cons ua um modelo de P og ama¸c˜ao Linea pa a es e p oblema.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Enunciados 4
A maz´em Capacidade
( oneladas)
Coimb a 70 000
Fa o 50 000
Lisboa 100 000
Po o 40 000
Tabela 4: Capacidade m´axima mensal de o necimen o dos a maz´ens
Clien e P ocu a mensal
( oneladas)
C1 50 000
C2 10 000
C3 40 000
C4 35 000
C5 60 000
C6 20 000
Tabela 5: P ocu a ´ıpica mensal dos clien es
P oblema 3
Um p odu o em ab ico esul a duma mon agem cons i u´ıda po duas pe¸cas, AeB. Pa a
a elabo a¸c˜ao dessas pe¸cas eco e-se a uma m´aquina M1 e a cinco m´aquinas M2. A
p odu i idade de cada m´aquina ela i amen e `as duas pe¸cas ´e a indicada na abela 1:
Pe¸ca M1 M2
A3 20
B5 15
Tabela 1: Tempo de p odu¸c˜ao (em minu os po pe¸ca) das pe¸cas AeBnas m´aquinas M1
eM2
A ca ga das m´aquinas M2 ´e epa ida igualmen e pelas 5 m´aquinas. O objec i o
do p oblema ´e sabe como se pode ob e o m´aximo de mon agens comple as po dia.
Conside e que um dia co esponde a 8 ho as de abalho.
(a) Ap esen e um modelo ma em´a ico pa a es e p oblema.
(b) Conside e ago a a si ua¸c˜ao em que amb´em se p e ende man e uma u iliza¸c˜ao equili-
b ada en e as m´aquinas de modo que nenhuma delas seja u ilizada mais 30 minu os
po dia do que qualque ou a das m´aquinas.
Se ´a poss´ı el esol e es e no o p oblema po P og ama¸c˜ao Linea ? Jus i ique.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de Fo mula¸c˜ao
Enunciados 5
P oblema 4
Fo mule o seguin e p oblema como um p oblema de P og ama¸c˜ao Linea :
Com is a `a o ganiza¸c˜ao de um hospi al conside am-se as seguin es condi¸c˜oes:
(a) h´a nclasses de doen es, com i= 1,2,...,n, designando cada classe;
(b) cada classe ´e di idida em doen es que pagam e doen es que n˜ao pagam;
(c) cada doen e da classe i eque ij unidades de se i¸co ipo j,j= 1,2,...,m;
(d) cada unidade de se i¸co j eque akj unidades de ecu so ipo k,k= 1,2,...,l;
(e) pa a um dado pe ´ıodo de empo exis em kunidades dispon´ı eis do ecu so k;
( ) h´a um limi e supe io ui, sob e o n´ume o de doen es na classe i, a se em a ados;
(g) bem como um limi e in e io li, no n´ume o de doen es na classe i, a se em a ados;
(h) po ou o lado, a p opo ¸c˜ao de doen es que n˜ao pagam, da classe i, n˜ao se ´a supe io
a i;
(i) os doen es que pagam, paga ˜ao pjpo cada unidade de se i¸co ipo j;
(j) ´e cko cus o uni ´a io do ecu so ipo k;
(k) h´a cus os ixos e subs´ıdios, aeb, espec i amen e;
(l) exige-se um n´ı el m´ınimo, e, pa a o luc o;
(m) a ibui-se um peso wia cada classe de doen es i, que e lec e a impo ˆancia dessa
classe pa a o hospi al;
(n) o objec i o ´e maximiza a soma pesada de odos os doen es a ados, espei ando as
es i¸c˜oes indicadas.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Enunciados 6
P oblema 5
Uma companhia de na ega¸c˜ao possui um na io com 3 po ˜oes de ca ga (`a p oa, `a ´e e
ao cen o) possuindo os limi es de capacidade ap esen ados na abela 1:
Po ˜ao Tonelagem Volume
( oneladas) (m3)
P oa 2000 100000
Cen o 3200 14000
R´e 1800 80000
Tabela 1: Limi es de capacidade (em onelagem e em olume) de cada um dos po ˜oes
`
A emp esa s˜ao o e ecidas as ca gas da abela 2, cada uma das quais pode se acei e
pa cial ou o almen e:
Ca ga Peso Volume po onelada Luc o
( oneladas) ( m3
onelada ) ( escudos
onelada )
A7000 60 20
B6500 50 24
C4000 25 16
Tabela 2: Peso, olume e luc o associados a cada ca ga
A im de p ese a o equil´ıb io do na io, de e man e -se a p opo ¸c˜ao en e o peso em
cada po ˜ao e o olume espec i o. Admi a que em cada po ˜ao podem se anspo adas
pa es de ca gas di e en es. P e ende-se maximiza o luc o da emp esa, ela i o `a u iliza¸c˜ao
des e na io.
Cons ua um modelo de P og ama¸c˜ao Linea pa a o p oblema ap esen ado.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Enunciados 7
P oblema 6
Duas ´ab icas, AeB, si uadas em locais di e en es p oduzem ambas os p odu os P1eP2.
A ´ab ica A em 3 m´aquinas e a ´ab ica B em 2 m´aquinas. Todas as m´aquinas azem
os p odu os P1eP2. Depois de ab icados, os p odu os podem se anspo ados en e as
´ab icas de modo a sa is aze a p ocu a. O n´ume o de unidades p oduzidas po dia, os
cus os de p odu¸c˜ao e de anspo e, a p ocu a dos p odu os e o n´ume o de dias em que
cada m´aquina es ´a dispon´ı el po mˆes es ˜ao indicados nas abelas 1 e 2.
(a) Ap esen e um modelo ge al (usando a i´a eis indexadas e coe icien es con enien es
a de ini ) que pe mi a de e mina os esquemas de u iliza¸c˜ao das m´aquinas em cada
´ab ica e de dis ibui¸c˜ao dos p odu os en e as ´ab icas, a que co esponda um cus o
o al m´ınimo.
(b) Conc e ize o modelo pa a o caso desc i o.
(c) Re i a-se `a esolu¸c˜ao do p oblema em ques ˜ao.
F´ab ica A B
M´aquina M1M2M3M1M2
Disponibilidade (dias) 30 28 24 26 28
P odu o P1P2P1P2P1P2P1P2P1P2
P odu¸c˜ao po dia 40 35 42 38 40 37 41 37 42 40
Cus o po dia 100 102 104 106 98 104 102 105 103 106
Tabela 1: Capacidades de p odu¸c˜ao das ´ab icas
P odu o P1P2
F´ab ica A B A B
P ocu a 1200 800 1500 1100
Cus o de anspo e A→B= 4 B→A= 4 A→B= 3 B→A= 4
po unidade
Tabela 2: P ocu a e cus os de anspo e dos p odu os
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Enunciados 8
P oblema 7
A Supe boa em 3 ´ab icas de ce eja e 10 pon os p incipais de dis ibui¸c˜ao.
Em cada mˆes a ´ab ica ip oduz no m´aximo aikl de ce eja em egime no mal, com
um cus o icon os
kl ,i= 1,2,3. Qualque ´ab ica amb´em pode abalha em egime ex-
ao din´a io, p oduzindo nessa si ua¸c˜ao um m´aximo de bikl com um cus o sicon os
kl , com
si> i.
O cus o de anspo e da ´ab ica ipa a o pos o j,j= 1,...,10 ´e de cij con os
kl . Toda
a ce eja p oduzida num dado mˆes pode se anspo ada, no mesmo mˆes, pa a os pos os
de dis ibui¸c˜ao.
No pos o ja p ocu a ´e de djkl. A p ocu a pode ´a n˜ao se sa is ei a, con udo, cada
kl dis ibu´ıdo no pos o j ende αjcon os e cada kl que ique po dis ibui penaliza a
emp esa em βjcon os.
Se a quan idade de ce eja anspo ada pa a o pos o jexcede a p ocu a nesse pos o,
o excesso pode se endido pa a um a maz´em ao p e¸co de γjcon os
kl , com γj< αj, em
quan idades ilimi adas.
(a) Ap esen e um modelo ma em´a ico pa a o p oblema da de e mina¸c˜ao da es a ´egia
´op ima mensal de p odu¸c˜ao, anspo e e enda da emp esa.
(b) Re i a-se ao ipo de modelo que ap esen ou.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 15
P oblema 3
(a) •Va i´a eis de decis˜ao
xA1quan idade de pe¸cas do ipo Aa p oduzi na m´aquina M1;
xA2quan idade de pe¸cas do ipo Aa p oduzi na m´aquina M2;
xB1quan idade de pe¸cas do ipo Ba p oduzi na m´aquina M1;
xB2quan idade de pe¸cas do ipo Ba p oduzi na m´aquina M2.
•Fun¸c˜ao objec i o
P e ende-se maximiza o n´ume o de mon agens comple as:
max Z= min(xA1+xA2, xB1+xB2)
Es a un¸c˜ao objec i o pode se linea izada, ac escen ando mais uma a i´a el
auxilia e duas es i¸c˜oes:
max Z=Y
xA1+xA2≥Y
xB1+xB2≥Y
•Modelo
max Z=Y(1.1)
Sujei o a:
3xA1+ 5xB1≤8×60 (minu os) (1.2)
20xA2+ 15xB2≤8×60 ×5 (minu os) (1.3)
xA1+xA2−Y≥0 (1.4)
xB1+xB2−Y≥0 (1.5)
xA1, xA2, xB1, xB2≥0 (1.6)
Onde 1.2 e 1.3 co espondem `as es i¸c˜oes de capacidade das m´aquinas 1 e 2
espec i amen e (h´a 5 m´aquinas ipo 2). As es i¸c˜oes 1.4 e 1.5 s˜ao as es i¸c˜oes
auxilia es pa a linea iza¸c˜ao da un¸c˜ao objec i o. Po ´ul imo, as es i¸c˜oes 1.6
exigem que odas as a i´a eis sejam maio es ou iguais a ze o.
(b) A es i¸c˜ao (n˜ao linea ) que modeliza a si ua¸c˜ao p e endida nes a al´ınea ´e a seguin e:

(3xA1+ 5xB1)−20xA2+ 15xB2
5
≤30
Simpli icando ob ´em-se:
|3xA1+ 5xB1−4xA2−3xB2| ≤ 30 (1.7)
Pa a ob e um modelo de P og ama¸c˜ao Linea , se ´a necess´a io ans o ma a e-
s i¸c˜ao 1.7 em duas es i¸c˜oes linea es:
3xA1+ 5xB1−4xA2−3xB2≤30 (1.8)
−3xA1−5xB1+ 4xA2+ 3xB2≤30 (1.9)
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 16
P oblema 4
•´
Indices
iclasses de doen es i∈[1,...,n];
j ipo de se i¸co j∈[1,...,m];
k ecu so k∈[1,...,l].
•Va i´a eis de decis˜ao
xin´ume o de doen es da classe ique pagam;
yin´ume o de doen es da classe ique n˜ao pagam.
•Fun¸c˜ao objec i o
Com a un¸c˜ao objec i o, equa¸c˜ao 1.1, p e ende-se modeliza as condi¸c˜oes (m) e (n)
do enunciado.
max Z=
n
X
i=1
wi(xi+yi) (1.1)
•Res i¸c˜oes
∀kX
i,j
ijakj(xi+yi)≤ k(1.2)
∀ixi+yi≤ui(1.3)
∀ixi+yi≥li(1.4)
∀i i(xi+yi)≥yi(1.5)
∀ixi, yi≥0 (1.6)
X
i

X
j
ijpj−X
j,k
ijakjck
xi−
X
i

X
j,k
ijakjck
yi+b−a≥e(1.7)
As es i¸c˜oes 1.2 ga an em que n˜ao s˜ao u ilizados mais ecu sos do ipo kdo que os
dispon´ı eis, sa is azendo as condi¸c˜oes (c), (d) e (e) do enunciado. As es i¸c˜oes 1.3
e 1.4 ga an em que n˜ao se ˜ao ul apassados que os limi es in e io es que os limi es
supe io es dos n´ume o de doen es de cada classe i, sa is azendo as condi¸c˜oes ( ) e
(g) do enunciado. As es i¸c˜oes 1.5 ga an em que se e i ica a condi¸c˜ao e e ida na
al´ınea (h) do enunciado. A es i¸c˜ao 1.7 ga an em que n˜ao se e ´a um luc o in e io
ae(condi¸c˜ao (l) do enunciado). Po ´ul imo a es i¸c˜ao 1.6 ga an e que odas as
a i´a eis s˜ao maio es ou iguais a ze o.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 17
P oblema 5
•´
Indices
i ipo de ca ga (A, B e C) i∈[1,2,3];
j ipo de po ˜ao (P, C, R) j∈[1,2,3].
•Va i´a eis de decis˜ao
xij quan idade de ca ga ia anspo a no po ˜ao j(em oneladas).
•Fun¸c˜ao objec i o
P e ende-se maximiza o luc o com o anspo e das ca gas iem odos os po ˜oes j,
o que co esponde `a soma do luc o ob ido com o anspo e da ca ga A, com o luc o
com anspo e da ca ga B e da ca ga C.
max Z= 20 X
j
x1j+ 24 X
j
x2j+ 16 X
j
x3j(1.1)
•Res i¸c˜oes
X
j
x1j≤7000 (1.2)
X
j
x2j≤6500 (1.3)
X
j
x3j≤4000 (1.4)
X
i
xi1≤2000 (1.5)
X
i
xi2≤3200 (1.6)
X
i
xi3≤1800 (1.7)
60x11 + 50x21 + 25x31 ≤100000 (1.8)
60x12 + 50x22 + 25x32 ≤14000 (1.9)
60x13 + 50x23 + 25x33 ≤80000 (1.10)
60x11+50x21+25x31
Pixi1=100000
2000 (1.11)
60x12+50x22+25x32
Pixi2=14000
3200 (1.12)
60x13+50x23+25x33
Pixi3=80000
1800 (1.13)
∀i,j xij ≥0 (1.14)
As es i¸c˜oes 1.2, 1.3 e 1.4 ga an em que n˜ao se anspo a mais ca ga do que a
que exis e de cada um dos ipos. As es i¸c˜oes 1.5, 1.6 e 1.7 ga an em que n˜ao se
ul apassa a onelagem m´axima pe mi ida em cada um dos po ˜oes. As es i¸c˜oes 1.8,
1.9 e 1.10 ga an em que n˜ao se ul apassa a capacidade ( olume) m´axima pe mi ida
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 18
em cada um dos po ˜oes. As es i¸c˜oes 1.11, 1.12 e 1.13 ga an em que se man ´em
a p opo ¸c˜ao en e o peso em cada po ˜ao e a espec i a capacidade. Po im, as
es i¸c˜oes 1.14 ga an em que odas as a i´a eis de decis˜ao s˜ao maio es ou iguais a
ze o.
•Modelo
O modelo ap esen ado (equa¸c˜oes 1.1 a 1.14) pode se eesc i o da seguin e o ma:
max Z= 20 X
j
x1j+ 24 X
j
x2j+ 16 X
j
x3j
X
j
x1j≤7000
X
j
x2j≤6500
X
j
x3j≤4000
X
i
xi1≤2000
X
i
xi2≤3200
X
i
xi3≤1800
60x11 + 50x21 + 25x31 ≤100000
60x12 + 50x22 + 25x32 ≤14000
60x13 + 50x23 + 25x33 ≤80000
10x11 −25x31 = 0
178x12 + 146x22 + 66x32 = 0
100x13 + 72x23 + 37x33 = 0
∀i,j xij ≥0
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 19
P oblema 6
(a) •´
Indices
i ´ab icas (AeB)i∈[1,2];
jm´aquinas (M1,M2,M3)j∈[1,2,3];
kp odu os (P1eP2)k∈[1,2].
•Va i´a eis de decis˜ao
xijk n´ume o de dias de p odu¸c˜ao du an e um mˆes do p odu o k, na ´ab ica i,
m´aquina j;
yik quan idade do p odu o ka anspo a a pa i da ´ab ica i;
zik quan idade do p odu o ka anspo a pa a a ´ab ica i.
•Coe icien es
cijk cus o di´a io de p odu¸c˜ao do p odu o k, na ´ab ica i, m´aquina j;
pijk p odu¸c˜ao di´a ia do p odu o k, na ´ab ica i, m´aquina j;
mij disponibilidade (em dias) da m´aquina jda ´ab ica i;
dik p ocu a na ´ab ica ido p odu o k;
sik cus o de anspo e, a pa i da ´ab ica ido p odu o k;
ik cus o de anspo e, pa a a ´ab ica ido p odu o k.
•Modelo
Objec i o
min Cus o =X
i,j,k
cijkxijk +X
i,k
sikyik +X
i,k
ikzik (1.1)
∀i,k Pjpijkxijk −yik +zik =dik (1.2)
∀i,j Pkxijk ≤mij (1.3)
∀i,j,k xijk, yik, zik ≥0 (1.4)
As es i¸c˜oes 1.2 ga an em que a p ocu a do p odu o kna ´ab ica i´e sa is ei a.
As es i¸c˜oes 1.3 s˜ao es i¸c˜oes de capacidade (disponibilidade) das m´aquinas.
Finalmen e as es i¸c˜oes 1.4 ga an em que odas as a i´a eis omam alo es
maio es ou iguais a ze o.
(b) Conc e ize ago a o modelo gen´e ico ap esen ado, de al o ma que co esponda `a
si ua¸c˜ao desc i a no enunciado.
(c) Ao esol e a al´ınea an e io , e e com ce eza que a a o caso das a i´a eis x231 e
x232, dado que essas a i´a eis o am de inidas no modelo gen´e ico, mas na ealidade
n˜ao exis e nenhuma m´aquina 3 na ´ab ica 2. H´a ´a ias o mas de esol e es a
ques ˜ao:
•quando se ”conc e iza”o modelo, pode-se n˜ao de ini as a i´a eis em causa ( e
esolu¸c˜ao do exe c´ıcio 2);
•pode-se associa um alo nulo `a p odu¸c˜ao nessa m´aquina n˜ao exis en e (p23k=
0) (se ´a que ´e su icien e?);
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 20
•pode-se associa um cus o in ini o (mui o g ande) `a p odu¸c˜ao nessa m´aquina
n˜ao exis en e (c23k=∞), dado que se a a de um p oblema de minimiza¸c˜ao e
nessa si ua¸c˜ao as a i´a eis se ˜ao nulas na solu¸c˜ao inal;
•podem-se ac escen a es i¸c˜oes do ipo x23k= 0.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 21
P oblema 7
•´
Indices
i ´ab icas i∈[1,...,3];
jpos os de enda j∈[1,...10].
•Va i´a eis de decis˜ao
y1iquan idade de kl de ce eja a p oduzi em i, em egime no mal;
y2iquan idade de kl de ce eja a p oduzi em i, em egime ex ao din´a io;
qij quan idade de kl de ce eja a anspo a da ´ab ica ipa a o pos o de enda j.
•Coe icien es
aiquan idade m´axima de kl de ce eja a p oduzi em egime no mal na ´ab ica i;
icus o de p odu¸c˜ao de 1 kl de ce eja em egime no mal;
biquan idade m´axima de kl de ce eja a p oduzi em egime ex ao din´a io na
´ab ica i;
sicus o de p odu¸c˜ao de 1 kl de ce eja em egime ex ao din´a io;
cij cus o de anspo e de 1 kl de ce eja da ´ab ica ipa a o pos o j;
djp ocu a no pos o j(em kl);
αjp e¸co de enda de 1 kl de ce eja no pos o j(em con os);
βjcus o po pe da de enda de cada kl de ce eja no pos o j(em con os);
γjp e¸co de enda a um a maz´em de 1 kl de ce eja em excesso no pos o j.
•Va i´a eis auxilia es
Vai se necess´a io conside a duas a i´a eis auxilia es que co espondam ao excesso
e `a escassez de ce eja no pos o de enda j.
ujexcesso de ce eja no pos o j, em kl;
jescassez de ce eja no pos o j, em kl.
•Fun¸c˜ao objec i o
P e ende-se com a un¸c˜ao objec i o encon a o alo m´aximo pa a o luc o, sa is-
azendo as es i¸c˜oes impos as. O alo do luc o ob ´em-se (ob iamen e) sub aindo
as despesas das ecei as.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 22
–Recei as
Venda de ce eja di ec amen e no pos o ((p ocu a no pos o j- escassez no pos o
j)×p e¸co de enda no pos o j)
X
j
(dj− j)αj(1.1)
Venda de ce eja ao a maz´em (excesso de ce eja no pos o j×p e¸co de enda
do pos o jao a maz´em)
X
j
ujγj(1.2)
–Despesas
Despesa com p odu¸c˜ao de ce eja em egime no mal e com p odu¸c˜ao de ce eja
em egime ex ao din´a io.
X
i
( iy1i+siy2i) (1.3)
Despesa com anspo e de ce eja da ´ab ica ipa a o pos o j.
X
i,j
cijqij (1.4)
Despesa com pe da de enda de ce eja no pos o j.
X
j
jβj(1.5)
A un¸c˜ao objec i o se ´a en ˜ao:
max X
j
((dj− j)αj+ujγj− jβj)−X
i
( iy1i+siy2i)−X
i,j
cijqij (1.6)
•Res i¸c˜oes
∀iy1i≤ai(1.7)
∀iy2i≤bi(1.8)
∀iPjqij ≤y1i+y2i(1.9)
∀jPiqij −dj=uj− j(1.10)
∀i,j qij ≥0 (1.11)
∀juj, j≥0 (1.12)
∀iy1i, y2i≥0 (1.13)
Conside ando que, al como ´e a i mado no enunciado, o cus o de p odu¸c˜ao de ce eja
em egime no mal ´e in e io ao cus o de p odu¸c˜ao de ce eja em egime ex ao din´a io
( i< si), e dado que o p oblema ´e de maximiza¸c˜ao de luc os (minimiza¸c˜ao de cus os)
n˜ao se ´a necess´a io ga an i , a pa i das es i¸c˜oes impos as, que s´o se come¸ca
a p oduzi em egime ex ao din´a io depois de e p oduzido oda a quan idade
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 23
poss´ı el em egime no mal. Nesse caso as es i¸c˜oes 1.7 e 1.8 s˜ao su icien es pa a
ga an i as es i¸c˜oes impos as no enunciado.
As es i¸c˜oes 1.9 ga an em que a quan idade anspo ada de uma ´ab ica pa a odos
os a maz´ens n˜ao excede a quan idade p oduzida nessa ´ab ica.
As es i¸c˜oes 1.11 e 1.13 ga an em que as a i´a eis s˜ao maio es ou iguais a ze o.
As es i¸c˜oes 1.10 e 1.12 s˜ao de idas `as a i´a eis auxilia es c iadas. Repa e-se que
assim uma quan idade de ce eja num pos o de enda que seja posi i a, nega i a ou
nula, se ´a ep esen ada pela di e en¸ca de duas a i´a eis ≥0. Ques ˜oes em abe o:
–Se ´a que es a ep esen a¸c˜ao ´e ´unica?
–Jus i ique po que az˜ao a imposi¸c˜ao des as es i¸c˜oes modeliza o excesso ou a
escassez de ce eja num de e minado pos o.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fo mula¸c˜ao
Resolu¸c˜oes 24
P oblema 8
•´
Indices
egime da cul u a – i∈ {1,2}(in ensi o ou n˜ao)
des ino da colhei a – j∈ {1,2}( enda di ec a ou alimen a¸c˜ao de c ia¸c˜ao)
•Dados
Cul u a de ce eais
400ha – N´ume o m´aximo de hec a es a a enda .
240ha – Limia de mudan¸ca de cus o de a endamen o do hec a e.
Cus ha≤240ha – Cus o de a endamen o do hec a e abaixo ou igual ao limia (15eu os).
Cus ha>240ha – Cus o de a endamen o do hec a e acima do limia (25eu os).
MdOi– Quan idade de m˜ao de ob a necess´a ia po hec a e e po ano no egime
i.(5pessoa×ho a
ha×ano ,7pessoa×ho a
ha×ano )
Cus Ma i– Cus o dos ma e iais necess´a ios po hec a e e po ano no egime
i.(50 eu os
ha×ano ,90 eu os
ha×ano )
Colhei ai– Colhei a po hec a e e po ano no egime i.
(2.8kl
ha×ano ,4.0kl
ha×ano )
12.5pessoa×ho a
kl – Quan idade de m˜ao de ob a pa a colhei a.
62.5eu os
kl – P e¸co de enda dos ce eais.
C ia¸c˜ao
1350m2– N´ume o m´aximo de m2de espa¸co cobe o pa a c ia¸c˜ao.
1kl
unidade – Quan idade de kl de ce eais necess´a ios po unidade de c ia¸c˜ao.
20pessoa×ho a
unidade – Quan idade de m˜ao-de-ob a necess´a ia po unidade de c ia¸c˜ao.
4m2
unidade – Quan idade de ch˜ao cobe o necess´a io po unidade de c ia¸c˜ao.
87.5eu os
kl – Cus o dos ce eais comp ados no ex e io .
200unidades – Limia de mudan¸ca de p e¸co de enda de unidade de c ia¸c˜ao.
VendUC≤200unidades – P e¸co de enda de cada unidade de c ia¸c˜ao abaixo ou igual
ao limia (175eu os).
VendUC>200unidades – P e¸co de enda de cada unidade de c ia¸c˜ao acima do limia
(160eu os).
Pessoal - ecu so necess´a io pa a ce eais e pa a c ia¸c˜ao
4000pessoa ×ho a – N´ume o m´aximo de pessoa ×ho a g ´a is po ano.
3000pessoa ×ho a – Limia de mudan¸ca de cus o po pessoa-ho a.
Cus Pess≤3000pessoa×ho a – Cus o de con a a¸c˜ao de uma pessoa×ho a abaixo ou
igual ao limia (4eu os).
Cus Pess>3000pessoa×ho a – Cus o de con a a¸c˜ao de uma pessoa ×ho a acima do
limia (7eu os).
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 31
P oblema 1
max F= 10x1+ 7x2
suj. a:
2x1+x2≤5000
4x1+ 5x2≤15000
x1, x2≥0
O p oblema p opos o ´e um p oblema de p og ama¸c˜ao linea : a un¸c˜ao objec i o e as
es i¸c˜oes s˜ao un¸c˜oes linea es das a i´a eis de decis˜ao x1ex2. Es e exemplo simples se ´a
usado pa a ilus a a aplica¸c˜ao do m´e odo Simplex pa a esol e p oblemas de p og ama¸c˜ao
linea . Embo a a esolu¸c˜ao p ´a ica de p oblemas des e ipo seja (semp e) ei a eco endo
a p og amas de compu ado que pe mi em ob e a solu¸c˜ao de p oblemas com milha es
de es i¸c˜oes e a i´a eis, ´e con enien e a comp eens˜ao do uncionamen o da ´ecnica pa a
acili a a in e p e a¸c˜ao dos esul ados ob idos.
Pa a se aplica o m´e odo Simplex, ´e necess´a io que o p oblema sa is a¸ca os equisi os
seguin es ( o ma s anda d):
(a) Todas as a i´a eis s˜ao n˜ao nega i as (s´o podem assumi alo es posi i os ou nulos);
(b) Todas as es i¸c˜oes s˜ao equa¸c˜oes (ou es i¸c˜oes do ipo ’=’);
(c) Todos os e mos independen es s˜ao posi i os.
No nosso exemplo, a p imei a e ´ul ima condi¸c˜ao s˜ao sa is ei as. Pa a ep esen a o
p oblema na o ma s anda d ´e necess´a io ans o ma as duas inequa¸c˜oes em equa¸c˜oes.
Pa a isso, s˜ao in oduzidas no p imei o memb o das inequa¸c˜oes no as a i´a eis ( amb´em
n˜ao nega i as) com coe icien e +1. Es as a i´a eis ep esen am a “ olga”en e o p imei o e
o segundo memb o das inequa¸c˜oes, chamando-se po isso a i´a eis de olga e ep esen ando-
se po s(de slack).
max F= 10x1+ 7x2
suj. a:
2x1+x2+s1= 5000
4x1+ 5x2+s2= 15000
x1, x2, s1, s2≥0
A aplica¸c˜ao do m´e odo Simplex eque o conhecimen o de uma solu¸c˜ao b´asica ad-
miss´ı el inicial, que se i ´a de pon o de pa ida pa a o p ocesso i e a i o. Em p oblemas
que apenas con enham es i¸c˜oes do ipo ≤, a in odu¸c˜ao das a i´a eis de olga conduz
a uma solu¸c˜ao b´asica admiss´ı el inicial imedia a: azem-se nulas as a i´a eis o iginais
do p oblema (no nosso exemplo x1ex2), e as a i´a eis de olga icam iguais aos e mos
independen es das equa¸c˜oes espec i as:
(x1, x2, s1, s2) = (0,0,5000,15000)
No e-se que es a solu¸c˜ao inicial co esponde `a o igem da egi˜ao de solu¸c˜oes admiss´ı eis,
o que ´e semp e e dade se odas as es i¸c˜oes de um p oblema o em do ipo ≤com e -
mos independen es posi i os. Nes e caso a o igem ´e uma solu¸c˜ao b´asica admiss´ı el ob ida
imedia amen e com a in odu¸c˜ao das a i´a eis de olga em odas as es i¸c˜oes. O m´e odo
Simplex pode se aplicado manualmen e eco endo a um quad o onde se ep esen am de
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 32
o ma condensada odos os pa ˆame os do p oblema (ma iz dos coe icien es, e mos inde-
penden es e un¸c˜ao objec i o). Sob e esse quad o s˜ao aplicadas ans o ma¸c˜oes alg´eb icas
de aco do com de e minadas eg as, que conduzem `a ob en¸c˜ao da solu¸c˜ao ´op ima.
a i´a eis b´asicas x1x2s1s2 e mos independen es
↓ ↓
s12 1 1 0 5000
s24 5 0 1 15000
−F10 7 0 0 0
% ↑
cus os ma ginais sim´e ico do alo
da un¸c˜ao objec i o
Uma i e a¸c˜ao consis e em oca uma a i´a el da base: das a i´a eis n˜ao b´asicas
escolhe-se uma pa a en a pa a a base (i ´a passa de ze o a um alo posi i o-e en ualmen e
nulo), e das a i´a eis b´asicas ´e seleccionada uma pa a sai da base. Es a ope a¸c˜ao co -
esponde a “sal a ”pa a uma solu¸c˜ao b´asica admiss´ı el izinha (ou adjacen e). Ma em-
a icamen e alando, duas solu¸c˜oes adjacen es s˜ao aquelas que di e em de apenas uma
a i´a el b´asica; geome icamen e s˜ao dois “can os”da egi˜ao de solu¸c˜oes admiss´ı eis que
es ˜ao unidos po um “lado”do polied o que ep esen a no espa¸co essa egi˜ao. As solu¸c˜oes
b´asicas de um p oblema co espondem a odas as in e sec¸c˜oes en e as es i¸c˜oes, con-
side ando amb´em as es i¸c˜oes xi≥0. De en e es as, s˜ao admiss´ı eis aquelas que s˜ao
ep esen adas apenas po a i´a eis n˜ao nega i as:
a i´a eis b´asicas x1x2s1s2 e mos independen es
↓ ↓
⇔s12 1 1 0 5000 5000
2(meno quocien e)
s24 5 0 1 15000 15000
4
−F10 7 0 0 0
%↑
cus os ma ginais o mais sim´e ico do alo
posi i o da un¸c˜ao objec i o
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 33
•C i ´e io de en ada na base:
En a na base a a i´a el que i e um coe icien e mais posi i o na linha F. Es es
coe icien es (cus os ma ginais) ep esen am o peso ela i o das a i´a eis n˜ao b´asicas
(nes e caso x1ex2), no alo da un¸c˜ao objec i o. Podemos dize assim que, en ando
a a i´a el x1pa a a base, o alo de Fc esce 10 unidades po unidade de c escimen o
x1. No e-se que is o apenas ´e e dade se na linha Fexis i em coe icien es nulos sob
as a i´a eis b´asicas (po quˆe?). Na ealidade, a linha de F´e conside ada como sendo
uma equa¸c˜ao adicional, onde F ep esen a uma a i´a el que nunca sai da base:
F= 10x1+ 7x2
pode se ep esen ada como a equa¸c˜ao seguin e:
−F+ 10x1+ 7x2+ 0s1+ 0s2= 0
Esc i o des a o ma, Fapa ece com o coe icien e -1; da´ı a az˜ao de o alo que
apa ece no 2omemb o da linha Fse igual ao sim´e ico do alo da un¸c˜ao objec i o.
Sendo in e p e ada como uma equa¸c˜ao, podemos semp e elimina a i´a eis (usando
ope a¸c˜oes de pi o agem ap op iadas) po o ma a que os coe icien es de Fsob as
a i´a eis b´asicas sejam semp e nulos.
Pa a um p oblema de minimiza¸c˜ao o c i ´e io de en ada na base se ´a ob iamen e o
con ´a io: en a na base a a i´a el n˜ao b´asica que p o oca um maio dec escimen o
no alo de F, ou seja, a que i e um coe icien e mais nega i o na linha F.
•C i ´e io de sa´ıda da base:
Sai da base a a i´a el xk(b´asica na equa¸c˜ao i) que i e um coe icien e bi
aij meno
(sendo xja a i´a el que en ou pa a a base).
As duas equa¸c˜oes ep esen adas no quad o acima podem-se esc e e (x2= 0, n˜ao
b´asica):
2x1+s1= 5000
4x1+s2= 15000
ou: s1= 5000 −2x1
s2= 15000 −4x1
En ando x1pa a a base, isso signi ica que x1 ai passa de ze o pa a um alo posi-
i o. A a i´a el a sai da base ai se aquela que p imei o se anula , limi ando assim
o c escimen o de x1(no e-se que odas as a i´a eis en ol idas s´o podem assumi
alo es posi i os ou nulos).
Pela 1aequa¸c˜ao, x1pode subi a ´e 5000
2= 2500 pa a s1se anula (sai da base); pela
segunda equa¸c˜ao, o alo m´aximo pa a x1´e 15000
4= 3750. Logo, a a i´a el a sai
da base se ´a s1, pois quando x1c esce ´e s1que p imei o se anula, impondo assim o
limi e no c escimen o da a i´a el x1em 2500. Como eg a p ´a ica, bas a calcula os
quocien es en e os e mos independen es e os coe icien es da ma iz sob a a i´a el
que ai en a pa a a base, e i ando da base a a i´a el b´asica da equa¸c˜ao que i e
o meno quocien e.
Analisemos com mais de alhe a 1aequa¸c˜ao acima:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 34
5000 ( e mo independen e) ´e o alo que a a i´a el b´asica s1 oma a na i e a¸c˜ao
an e io .
2 (coe icien e da ma iz sob x1) ´e o sim´e ico do peso da a i´a el x1nessa equa¸c˜ao.
Po ou as pala as, podemos dize que s1dec esce 2 unidades po unidade de
c escimen o de x1, anulando-se (i. e. saindo da base) quando x1a inge 5000
2.
Podem assim se i adas algumas conclus˜oes in e essan es, em un¸c˜ao do alo dos
coe icien es da ma iz, aik, sob a a i´a el que oi escolhida pa a en a pa a a base,
xk:
aik >0xbi, a a i´a el b´asica na equa¸c˜ao i, dec esce aik unidades po unidade de
c escimen o de xk, impondo assim um limi e supe io a xkigual a bi
aik (bi´e
o e mo independen e da equa¸c˜ao i).
aik = 0 xbi, a a i´a el b´asica na equa¸c˜ao i, n˜ao ˆe al e ado o seu alo , quando xk
en a pa a a base. Isso signi ica que xbi nunca sai ´a da base pois n˜ao limi a
de o ma alguma o c escimen o de xk.
aik <0xbi, a a i´a el b´asica na equa¸c˜ao i, c esce aik unidades po unidade de c esci-
men o de xk. Assim, do mesmo modo que pa a o caso an e io , xbi n˜ao limi a
o c escimen o de xk, logo nunca sai ´a da base.
a i´a eis b´asicas x1··· xk··· xmb
↓
xb1··· ··· a1k··· ··· b1
.
.
..
.
..
.
..
.
..
.
..
.
..
.
.
⇔xbi ··· ··· aik ··· ··· bi
.
.
..
.
..
.
..
.
..
.
..
.
..
.
.
xbn ··· ··· ank ··· ··· bn
−F··· ··· k··· ··· −F0

Com base no que se disse, podemos conclui o seguin e: se odos os coe icien es
da a i´a el que se escolheu pa a en a pa a a base o em nega i os ou nulos, isso
signi ica que nenhuma das a i´a eis b´asicas dec esce com o c escimen o da no a
a i´a el candida a a b´asica. Assim, se es a a i´a el pode c esce sem que qualque
das b´asicas se anule, en ˜ao pode-se conclui que o p oblema n˜ao em uma solu¸c˜ao
´op ima limi ada. Si ua¸c˜oes des as oco em quando a egi˜ao de solu¸c˜oes admiss´ı eis
´e um dom´ınio abe o no sen ido de c escimen o da un¸c˜ao objec i o.
Con inuando com a esolu¸c˜ao do exemplo dado:
base x1x2s1s2b
x111
2
1
202500 2500
1
2
= 5000
⇔s20 3 −2 1 5000 5000
3= 1666.7
−F0 2 −5 0 −25000

J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 35
base x1x2s1s2b
x11 0 5
6−1
6
5000
3
x20 1 −2
3
1
3
5000
3
−F0 0 −11
3−2
3−85000
3
Solu¸c˜ao ´op ima encon ada:
N˜ao exis e nenhuma a i´a el n˜ao b´asica (s1ou s2, nes e caso) que enha um coe icien e
posi i o na linha F. Se uma dessas a i´a eis i esse um coe icien e nulo, isso signi ica a
que ela pode ia en a pa a a base sem al e a o alo da un¸c˜ao objec i o F(chamam-
se a es as solu¸c˜oes al e na i as `a solu¸c˜ao ´op ima encon ada). No e-se que as solu¸c˜oes
al e na i as assim ob idas s˜ao igualmen e ´op imas, j´a que man ˆem o mesmo alo pa a a
un¸c˜ao objec i o F.
O alo da solu¸c˜ao ´op ima pa a es e p oblema se ia F=85000
3e os alo es das a i´a eis
de decis˜ao se iam:
x1=5000
3, x2=5000
3
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 36
P oblema 2
(a)
x1x2x3x4
⇔x35 20 1 0 400
x410 15 0 1 450
−z45 80 0 0 0

x1x2x3x4
x25
20 11
20 020
⇔x4125
20 0−15
20 1150
−z25 0 −4 0 −1600

x1x2x3x4
x20 1 2
25 −1
25 14
x11 0 −3
25
4
25 24
−z0 0 −1−4−2200
Solu¸c˜ao ´op ima: (x1, x2)∗= (24,14) com z∗= 2200
(b) Como a solu¸c˜ao ´op ima e ´a que es a necessa iamen e num ´e ice da egi˜ao ad-
miss´ı el e, olhando pa a a igu a abaixo, se cons a a que apenas um ´e ice (o que
co esponde `a ac ual solu¸c˜ao ´op ima) em x1ex2es i amen e posi i os, en ˜ao pa a
esponde a es a pe gun a e emos apenas que e en e que alo es pode a ia c1
de modo a que a solu¸c˜ao ´op ima con inue no mesmo ´e ice. Como a solu¸c˜ao ´op ima
sal a ´a de ´e ice quando as linhas de n´ı el da un¸c˜ao objec i o o em pa alelas `a e-
s i¸c˜ao (R1) ou `a es i¸c˜ao (R2), is o ´e, quando c1
80 =5
20 ou c1
80 =10
15 , isso conduz-nos
a:
20 ≤c1≤160
3
20
30
(24,14)
R1
R2
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 37
P oblema 3
max F= 2x1+x2
suj. a:
x1+x2≥2
x1+x2≤4
x1, x2≥0
Em p imei o luga ´e necess´a io ep esen a o p oblema na o ma s anda d, in oduzindo
a i´a eis de olga pa a ans o ma as inequa¸c˜oes em equa¸c˜oes. A a i´a el de olga da
p imei a es i¸c˜ao em coe icien e -1 po que a inequa¸c˜ao ´e do ipo ≥(no e-se que odas as
a i´a eis s˜ao posi i as).
max F= 2x1+x2
suj. a:
x1+x2−s1= 2
x1+x2+ + s2= 4
x1, x2, s1, s2≥0
Nes e caso j´a n˜ao se ob ´em a solu¸c˜ao b´asica inicial azendo as a i´a eis de olga iguais
aos e mos independen es. Apesa dessa se uma solu¸c˜ao b´asica, n˜ao ´e admiss´ı el e como
al n˜ao pode se usada como pon o de pa ida pa a o m´e odo Simplex.
Se ˜ao ap esen ados dois m´e odos pa a esol e es a ques ˜ao, que pe mi em usa o
p ´op io Simplex pa a encon a uma solu¸c˜ao b´asica admiss´ı el inicial. Os m´e odos s˜ao:
•m´e odo das duas ases
•m´e odo das penalidades
An es de aplica qualque um dos m´e odos, ´e no en an o necess´a io ac escen a a i´a eis
(chamadas a i´a eis a i iciais) nas es i¸c˜oes que n˜ao ˆem a i´a eis b´asicas.
In oduzindo uma a i´a el a i icial na 1aequa¸c˜ao:
x1+x2−s1+a1= 2
x1+x2+ + s2= 4
x1, x2, s1, s2, a1≥0
Seguidamen e, ambos os m´e odos usam o m´e odo Simplex pa a anula ( e i a da base)
essas a i´a eis a i iciais. Quando isso acon ece, a solu¸c˜ao que en ˜ao se em ´e uma solu¸c˜ao
b´asica admiss´ı el do p oblema o iginal, que ´e usada como solu¸c˜ao de pa ida pa a aplica
o m´e odo Simplex.
Desc i¸c˜ao sucin a dos dois m´e odos:
M´e odo das duas ases
1a ase minimiza a un¸c˜ao objec i o a i icial W=Pai; o objec i o des a p imei a ase
´e e i a odas as a i´a eis a i iciais da base, si ua¸c˜ao em que Wa inge o alo
m´ınimo de ze o. A solu¸c˜ao b´asica admiss´ı el assim ob ida ´e uma solu¸c˜ao b´asica
admiss´ı el inicial pa a se aplica o m´e odo Simplex ao p oblema o iginal.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 38
2a ase Usando como solu¸c˜ao b´asica inicial a ob ida na p imei a ase, esol e o p oblema
no malmen e usando o algo i mo do simplex, depois de elimina do quad o a linha
co esponden e `a un¸c˜ao objec i o a i icial W, e as colunas ela i as `as a i´a eis
a i iciais, ai.
M´e odo das penalidades
A un¸c˜ao objec i o max F= 2x1+x2´e subs i u´ıda pela un¸c˜ao objec i o max F=
2x1+x2−MPai, onde M em um alo mui o ele ado. Dado que se a a de um p oblema
de maximiza¸c˜ao, a melho ia da un¸c˜ao objec i o implica que as a i´a eis a i iciais passem
a ale ze o (sejam e i adas da base). A solu¸c˜ao b´asica assim ob ida ´e uma solu¸c˜ao b´asica
admiss´ı el pa a o p oblema o iginal.
Aplicando o M´e odo das duas ases ao exemplo ap esen ado:
1a ase:
P e ende-se minimiza W=Pai=a1. Como nos in e essa exp imi o Wapenas em
un¸c˜ao de a i´a eis n˜ao b´asicas (po quˆe?), amos subs i ui cada a i´a el a i icial pela
exp ess˜ao que a ep esen a apenas em un¸c˜ao de a i´a eis n˜ao b´asicas.
Da 1aequa¸c˜ao (onde a1´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
x1+x2−s1+a1= 2
pode-se esc e e a1em un¸c˜ao de a i´a eis n˜ao b´asicas:
a1= 2 −x1−x2+s1
Assim, a un¸c˜ao objec i o a i icial a minimiza se ´a:
W=a1= 2 −x1−x2+s1
O p imei o quad o Simplex es ´a ep esen ado a segui . Dado que se p e ende minimiza
W, e emos que escolhe pa a en a na base a a i´a el com coe icien e mais nega i o na
linha W. Dado que as a i´a eis x1ex2 ˆem o mesmo coe icien e (-1), podemos escolhe
uma das duas a i´a eis pa a en a na base.
base x1x2s1s2a1b
⇔a11 1 −1 0 1 2 2
1
s21 1 0 1 0 4 4
1
−F2 1 0 0 0 0
−W−1−1 1 0 0 −2 (sim´e ico de W)

base x1x2s1s2a1b
x11 1 −1 0 1 2
s20 0 1 1 −1 2
−F0−1 2 0 −2−4
−W0 0 0 0 1 0
O quad o ap esen ado co esponde ao im da 1a ase do m´e odo das duas ases, dado
que a un¸c˜ao objec i o W oi minimizada a ´e ze o (a1= 0). A solu¸c˜ao b´asica admiss´ı el
assim ob ida ´e uma solu¸c˜ao b´asica admiss´ı el inicial pa a se aplica o m´e odo Simplex ao
p oblema o iginal.
2a ase:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 39
Nes a ase p e ende-se maximiza a un¸c˜ao objec i o inicial, F, omando como quad o
de pa ida o ´ul imo quad o da 1a ase, depois de elimina a linha co esponden e a We
as colunas ela i as `as a i´a eis a i iciais.
base x1x2s1s2b
x11 1 −1 0 2
⇔s20 0 1 1 2
−F0−1 2 0 −4

No e-se que x1nunca pode ia sai da base! En ando s1pa a a base, x1c esce 1
unidade po unidade de c escimen o de s1, logo nunca se i ia anula (e consequen emen e
sai da base). s2sai da base limi ando o c escimen o de s1em 2
1= 2.
base x1x2s1s2b
x11 1 0 1 4
s10 0 1 1 2
−F0−1 0 −2−8
N˜ao exis e nenhuma a i´a el n˜ao b´asica (x2ou s2, nes e caso) que enha um coe icien e
posi i o na linha F. O alo da solu¸c˜ao ´op ima pa a es e p oblema se ia F= 8 e os alo es
das a i´a eis de decis˜ao se iam:
x1= 4, x2= 0, s1= 2, s2= 0
Aplicando o M´e odo das penalidades ao exemplo ap esen ado:
Como nos in e essa exp imi Fapenas em un¸c˜ao de a i´a eis n˜ao b´asicas (po quˆe?),
amos subs i ui cada a i´a el a i icial pela exp ess˜ao que a ep esen a apenas em un¸c˜ao
de a i´a eis n˜ao b´asicas.
Da 1aequa¸c˜ao (onde a1´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
x1+x2−s1+a1= 2
pode-se esc e e a1em un¸c˜ao de a i´a eis n˜ao b´asicas:
a1= 2 −x1−x2+s1
Assim, a un¸c˜ao objec i o a maximiza se ´a:
F= 2x1+x2−Ma1
= 2x1+x2−M(2 −x1−x2+s1)
=−2M+ (2 + M)x1+ (1 + M)x2−Ms1
E o quad o seguin e ´e o p imei o quad o simplex.
No a: A linha dos cus os ma ginais es ´a di idida em duas com a ´unica inalidade de
simpli ica os c´alculos. A soma das duas linhas ´e que ep esen a o cus o ma ginal (p.ex.:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 40
2 + M).
base x1x2s1s2a1b
⇔a11 1 −1 0 1 2 2
1
s21 1 0 1 0 4 4
1
−F2 1 0 0 0
M M −M2M

A pa i des e quad o, n˜ao ´e necess´a io man e a coluna co esponden e a a1, dado que
a1j´a saiu da base.
base x1x2s1s2b
x11 1 −1 0 2
⇔s20 0 1 1 2
−F0−1 2 0 −4

base x1x2s1s2b
x11 1 0 1 4
s10 0 1 1 2
−F0−1 0 −2−8
N˜ao exis e nenhuma a i´a el n˜ao b´asica (x2ou s2, nes e caso) que enha um coe icien e
posi i o na linha F. O alo da solu¸c˜ao ´op ima pa a es e p oblema se ia F= 8 e os alo es
das a i´a eis de decis˜ao se iam:
x1= 4, x2= 0, s1= 2, s2= 0
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 47
P oblema 8
max F=x+ 2y+ 3z
suj. a:
x−y≥0
y+z≤2
−x+z= 0
x∈ <
y , z ≥0
Como a a i´a el x n˜ao ´e limi ada apenas a alo es n˜ao nega i os, ´e necess´a io subs i u´ı-
la pela di e en¸ca de duas a i´a eis n˜ao nega i as:
x=x1−x2
x1, x2≥0
A ep esen a¸c˜ao do p oblema na o ma s anda d (depois de in oduzidas as a i´a eis
a i iciais) se ´a en ˜ao:
max F=x1−x2+ 2y+ 3z
suj. a:
x1−x2−y−s1+a1= 0
y+z+s2= 2
−x1+x2+z+a2= 0
x1, x2, y , z , s1, s2, a1, a2≥0
Aplicando o M´e odo das duas ases ao exemplo ap esen ado:
1a ase:
P e ende-se minimiza W=Pai=a1+a2. Como nos in e essa exp imi o Wapenas
em un¸c˜ao de a i´a eis n˜ao b´asicas (po quˆe?), amos subs i ui cada a i´a el a i icial pela
exp ess˜ao que a ep esen a apenas em un¸c˜ao de a i´a eis n˜ao b´asicas.
Da 1aequa¸c˜ao (onde a1´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
x1−x2−y−s1+a1= 0
pode-se esc e e a1em un¸c˜ao de a i´a eis n˜ao b´asicas:
a1=−x1+x2+y+s1
Da 3aequa¸c˜ao (onde a2´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
−x1+x2+z+a2= 0
pode-se esc e e a2em un¸c˜ao de a i´a eis n˜ao b´asicas:
a2=x1−x2−z
Assim, a un¸c˜ao objec i o a i icial a minimiza se ´a:
W=a1+a2=−x1+x2+y+s1+x1−x2−z=y+s1−z
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 48
O p imei o quad o Simplex es ´a ep esen ado a segui . Dado que se p e ende minimiza
W, e emos que escolhe pa a en a na base a a i´a el com coe icien e mais nega i o na
linha W, nes e caso se ´a z.
base x1x2y z s1s2a1a2b
a11−1−1 0 −1 0 1 0 0
s20 0 1 1 0 1 0 0 2
⇔a2−1 1 0 1 0 0 0 1 0
−F1−1 2 3 0 0 0 0 0
−W001−1 1 0 0 0 0

No e-se que embo a Wseja j´a ze o (a solu¸c˜ao b´asica ´e degene ada po que a1ea2s˜ao
iguais a ze o), ainda h´a a i´a eis a i iciais na base que de em sai pa a se ob e uma
solu¸c˜ao b´asica inicial do p oblema o iginal.
base x1x2y z s1s2a1a2b
⇔a11−1−1 0 −1 0 1 0 0
s21−1 1 0 0 1 0 −1 2
z−1 1 0 1 0 0 0 1 0
−F4−4 2 0 0 0 0 −3 0
−W−1 1 1 0 1 0 0 1 0

base x1x2y z s1s2a1a2b
x11−1−1 0 −1 0 1 0 0
⇔s20 0 2 0 1 1 −1−1 2
z0 0 −1 1 −1 0 1 1 0
−F0 0 6 0 4 0 −4−3 0
−W0 0 0 0 0 0 1 1 0

No e-se que embo a a solu¸c˜ao ac ual ep esen ada no quad o acima seja degene ada
(x1= 0 e z= 0), o p ocesso i e a i o n˜ao en a em ciclo, uma ez que a p ´oxima solu¸c˜ao
´e necessa iamen e n˜ao degene ada. Com e ei o, en ando ypa a a base as a i´a eis x1e
z ˜ao c esce (coe icien es a13 ea33 iguais a -1) uma unidade po unidade de c escimen o
de y, passando de ze o pa a um alo posi i o.
2a ase:
Nes a ase p e ende-se maximiza a un¸c˜ao objec i o inicial, F, omando como quad o
de pa ida o ´ul imo quad o da 1a ase, depois de elimina a linha co esponden e a We
as colunas ela i as `as a i´a eis a i iciais.
base x1x2y z s1s2b
x11−1 0 0 −1
2
1
21
⇔y0 0 1 0 1
2
1
21
z0 0 0 1 −1
2
1
21
−F0 0 0 0 1 −3−6

J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 49
base x1x2y z s1s2b
x11−1 1 0 0 1 2
s10 0 2 0 1 1 2
z0 0 1 1 0 1 2
−F0 0 −2 0 0 −4−8
Solu¸c˜ao ´op ima encon ada.
Analisemos ago a cuidadosamen e as es i¸c˜oes do p oblema:
x−y≥0
y+z≤2
−x+z= 0
x∈ <
y , z ≥0
Da e cei a equa¸c˜ao pode-se e i a que z=x. Dado que z≥0 en ˜ao x≥0. Podemos
assim esc e e o p oblema equi alen e ao p oblema dado, mas de esolu¸c˜ao mui o mais
simples (j´a na o ma s anda d):
max F=x+ 2y+ 3z= 4x+ 2y
suj. a:
x−y−s1+a1= 0
x+y+s2= 2
x , y , s1, s2, a1≥0
1a ase:
P e ende-se minimiza W=Pai=a1. Como nos in e essa exp imi o Wapenas em
un¸c˜ao de a i´a eis n˜ao b´asicas (po quˆe?), amos subs i ui cada a i´a el a i icial pela
exp ess˜ao que a ep esen a apenas em un¸c˜ao de a i´a eis n˜ao b´asicas.
Da 1aequa¸c˜ao (onde a1´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
x−y−s1+a1= 0
pode-se esc e e a1em un¸c˜ao de a i´a eis n˜ao b´asicas:
a1=−x+y+s1
Assim, a un¸c˜ao objec i o a i icial a minimiza se ´a:
W=a1=−x+y+s1
O p imei o quad o Simplex es ´a ep esen ado a segui . Dado que se p e ende minimiza
W, e emos que escolhe pa a en a na base a a i´a el com coe icien e mais nega i o na
linha W, nes e caso se ´a x.
base x y s1s2a1b
⇔a11−1−1 0 1 0
s21 1 0 1 0 2
−F4 2 0 0 0 0
−W−1 1 1 0 0 0

J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 50
base x y s1s2a1b
x1−1−1 0 1 0
⇔s20 2 1 1 −1 2
−F0 6 4 0 −4 0
−W0 0 0 0 1 0

2a ase:
base x y s1s2b
x1 0 −1
2
1
21
⇔y0 1 1
2
1
21
−F0 0 1 −3−6

base x y s1s2b
x1 1 0 1 2
s10 2 1 1 2
−F0−2 0 −4−8

Solu¸c˜ao ´op ima: x=z= 2, y= 0, s1= 2, s2= 0, F= 8.
Aplicando o M´e odo das penalidades ao exemplo ap esen ado:
Como nos in e essa exp imi Fapenas em un¸c˜ao de a i´a eis n˜ao b´asicas (po quˆe?),
amos subs i ui cada a i´a el a i icial pela exp ess˜ao que a ep esen a apenas em un¸c˜ao
de a i´a eis n˜ao b´asicas.
Da 1aequa¸c˜ao (onde a1´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
x1−x2−y−s1+a1= 0
pode-se esc e e a1em un¸c˜ao de a i´a eis n˜ao b´asicas:
a1=−x1+x2+y+s1
Da 3aequa¸c˜ao (onde a2´e a i´a el b´asica e as ou as a i´a eis s˜ao n˜ao b´asicas):
−x1+x2+z+a2= 0
pode-se esc e e a2em un¸c˜ao de a i´a eis n˜ao b´asicas:
a2=x1−x2−z
Assim, a un¸c˜ao objec i o a maximiza se ´a:
F=x1−x2+ 2y+ 3z−M(a1+a2)
=x1−x2+ 2y+ 3z−M(−x1+x2+y+s1+x1−x2−z)
=x1+x2+ (2 −M)y+ (3 + M)z−Ms1
E o quad o seguin e ´e o p imei o quad o simplex.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 51
No a: A linha dos cus os ma ginais es ´a di idida em duas com a ´unica inalidade de
simpli ica os c´alculos. A soma das duas linhas ´e que ep esen a o cus o ma ginal (p.ex.:
2−M).
base x1x2y z s1s2a1a2b
a11−1−1 0 −1 0 1 0 0
s20 0 1 1 0 1 0 0 2
⇔a2−1 1 0 1 0 0 0 1 0
−F1−1 2 3 0 0 0 0 0
0 0 −M+M−M0 0 0 0

base x1x2y z s1s2a1a2b
⇔a11−1−1 0 −1 0 1 0 0
s21−1 1 0 0 1 0 −1 2
z−1 1 0 1 0 0 0 1 0
−F4−4 2 0 0 0 0 −3 0
+M−M−M0−M0 0 −M0

base x1x2y z s1s2a1a2b
x11−1−1 0 −1 0 1 0 0
⇔s20 0 2 0 1 1 −1−1 2
z0 0 −1 1 −1 0 1 1 0
−F0 0 6 0 4 0 −4−3 0
0 0 0 0 0 0 −M−M0

No e-se que embo a a solu¸c˜ao ac ual ep esen ada no quad o acima seja degene ada
(x1= 0 e z= 0), o p ocesso i e a i o n˜ao en a em ciclo, uma ez que a p ´oxima solu¸c˜ao
´e necessa iamen e n˜ao degene ada. Com e ei o, en ando ypa a a base as a i´a eis x1e
z ˜ao c esce (coe icien es a13 ea33 iguais a -1) uma unidade po unidade de c escimen o
de y, passando de ze o pa a um alo posi i o.
base x1x2y z s1s2b
x11−1 0 0 −1
2
1
21
⇔y0 0 1 0 1
2
1
21
z0 0 0 1 −1
2
1
21
−F0 0 0 0 1 −3−6

base x1x2y z s1s2b
x11−1 1 0 0 1 2
s10 0 2 0 1 1 2
z0 0 1 1 0 1 2
−F0 0 −2 0 0 −4−8
Solu¸c˜ao ´op ima encon ada.
Analisemos ago a cuidadosamen e as es i¸c˜oes do p oblema:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de M´e odo Simplex
Resolu¸c˜oes 52
x−y≥0
y+z≤2
−x+z= 0
x∈ <
y , z ≥0
Da e cei a equa¸c˜ao pode-se e i a que z=x. Dado que z≥0 en ˜ao x≥0. Podemos
assim esc e e o p oblema equi alen e ao p oblema dado, mas de esolu¸c˜ao mui o mais
simples (j´a na o ma s anda d):
max F=x+ 2y+ 3z= 4x+ 2y
suj. a:
x−y−s1+a1= 0
x+y+s2= 2
x , y , s1, s2, a1≥0
F= 4x+ 2y−M(a1)
= 4x+ 2y−M(−x+y+s1)
= (4 + M)x+ (2 −M)y−Ms1
base x y s1s2a1b
⇔a11−1−1 0 1 0
s21 1 0 1 0 2
−F4 2 0 0 0 0
+M−M−M0 0 0

A a i´a el a i icial oi e i ada da base.
base x y s1s2b
x1−1−1 0 0
⇔s20 2 1 1 2
−F0 6 4 0 0

base x y s1s2b
x1 0 −1
2
1
21
⇔y0 1 1
2
1
21
−F0 0 1 −3−6

base x y s1s2b
x1 1 0 1 2
s10 2 1 1 2
−F0−2 0 −4−8

Solu¸c˜ao ´op ima: x=z= 2, y= 0, s1= 2, s2= 0, F= 8.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

3
Exe c´ıcios de P og ama¸c˜ao In ei a
Enunciados
Exe c´ıcios de P og ama¸c˜ao In ei a
Enunciados 54
P oblema 1
Conside e 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
Resol a o p oblema g a icamen e, u ilizando o algo i mo de “B anch-and-Bound”.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Enunciados 55
P oblema 2
Foi u ilizado o algo i mo de “B anch-and-Bound”pa a esol e um p oblema de p o-
g ama¸c˜ao in ei a (minimiza¸c˜ao), endo sido ge ados e esol idos os seguin es subp ob-
lemas:
A B C D E F G H I
x15 513
18 −3 31
2−5 3 −
x22 24
9−3 3 −25
831
8−
Z−20 −232
3SSA −21 −22 SSA −231
8−215
8SSA
Rep esen e a ´a o e de p oblemas co esponden e a es a esolu¸c˜ao, indicando nos amos
a es i¸c˜ao adicionada em cada ami ica¸c˜ao, e diga qual ´e a solu¸c˜ao ´op ima.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Enunciados 56
P oblema 3
Conside e um p oblema de maximiza¸c˜ao exclusi amen e com a i´a eis in ei as. Resol-
endo o p oblema a a ´es de “B anch-and-Bound”, ob ´em-se, num dado es ´agio, a seguin e
´a o e:
PL1
(solução não in ei a)
Z = 100
PL2
(solução não in ei a)
Z = 85
PL3
(solução não in ei a)
Z = 91
PL6
(solução in ei a)
Z = 70
PL7
(solução não in ei a)
Z = 79
PL8
(sem soluções)
PL9
(solução não in ei a)
Z = 65
PL4
(solução in ei a)
Z = 60
PL5
(solução não in ei a)
Z = 75
(a) Qual ´e, nes a al u a, o melho limi e supe io sob e a solu¸c˜ao in ei a ´op ima?
(b) Qual ´e, nes a al u a, o melho limi e in e io sob e a solu¸c˜ao in ei a ´op ima?
(c) Indique que n´os j´a o am explo ados e explique po quˆe.
(d) Indique os n´os que ainda n˜ao o am explo ados e explique po quˆe.
(e) J´a oi a ingida a solu¸c˜ao ´op ima do p oblema in ei o? Po quˆe?
( ) Qual o alo m´aximo do e o absolu o sob e a solu¸c˜ao ´op ima in ei a, se o algo i mo
o e minado nes e pon o?
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 63
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
Figu a 5: Resolu¸c˜ao g ´a ica do p oblema PL02.
PL0
(solução não in ei a)
x = 3.5
y = 3.5
F = 35
PL01
(solução não in ei a)
x = 3
y = 3.6
F = 34.5
PL02
(sem soluções)
x <= 3 x >= 4
Figu a 6: ´
A o e do B&B
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 64
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
Figu a 7: Resolu¸c˜ao g ´a ica do p oblema PL011.
max F= 3x+ 7y
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≤3
Na igu a 7 pode-se e i ica que a solu¸c˜ao do p oblema PL011 se ob ´em calculando a
in e sec¸c˜ao das ec as:
x= 3
y= 3
Essa in e sec¸c˜ao az-se no pon o (x, y) = (3,3). O alo da un¸c˜ao objec i o nesse
pon o ´e F= 30. Apesa de se a p imei a solu¸c˜ao in ei a ob ida a ´e en ˜ao, n˜ao se pode
con udo a i ma que ela ´e a solu¸c˜ao ´op ima do p oblema de PI, dado que ainda n˜ao se
explo ou a solu¸c˜ao do p oblema PL012. Pode no en an o egis a -se es a solu¸c˜ao in ei a
como a melho ob ida a ´e aqui.
Dado que se a a de um p oblema de maximiza¸c˜ao, o alo co esponden e da un¸c˜ao
objec i o ´e conside ado como um limi e in e io pa a o alo ´op imo de F. Du an e a
aplica¸c˜ao do algo i mo, qualque solu¸c˜ao (in ei a ou n˜ao) que se ob enha com um alo
pa a o objec i o in e io a 30 pode se imedia amen e desp ezada, pois exis e j´a uma
solu¸c˜ao in ei a com esse alo .
P osseguindo, esol a-se o p oblema PL012:
max F= 3x+ 7y
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 65
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
Figu a 8: Resolu¸c˜ao g ´a ica do p oblema PL012.
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
Na igu a 8 pode-se e i ica que a solu¸c˜ao do p oblema PL012 se ob ´em calculando a
in e sec¸c˜ao das ec as:
4
7x+ 2y= 9
y= 4
Essa in e sec¸c˜ao az-se no pon o (x, y) = (7
4,4) ≈(1.7,4). O alo da un¸c˜ao objec i o
nesse pon o ´e F=133
4≈33.2.
Na igu a 9 es ´a ep esen ada a ´a o e do B anch-and-Bound cons u´ıda a ´e ao mo-
men o.
Uma ez que a solu¸c˜ao ob ida ´e n˜ao in ei a, ´e necess´a io compa a o alo da un¸c˜ao
objec i o com o seu ac ual limi e in e io , F, que nes e momen o es ´a ixado em 30. Como
´e supe io , isso signi ica que na egi˜ao admiss´ı el des e p oblema pode exis i ainda uma
solu¸c˜ao in ei a com um alo pa a a un¸c˜ao objec i o supe io ao ac ual limi e in e io .
Po es e mo i o ´e necess´a io p ossegui , ge ando dois no os p oblemas a pa i de PL012,
in oduzindo as es i¸c˜oes x≤1 e x≥2.
P oblema PL0121:
max F= 3x+ 7y
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 66
PL0
(solução não in ei a)
x = 3.5
y = 3.5
F = 35
PL01
(solução não in ei a)
x = 3
y = 3.6
F = 34.5
PL02
(sem soluções)
PL011
(solução in ei a)
x = 3
y = 3
F = 30
PL012
(solução não in ei a)
x = 1.7
y = 4
F = 33.2
x <= 3 x >= 4
y <= 3 y >= 4
Figu a 9: ´
A o e do B&B
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
Figu a 10: Resolu¸c˜ao g ´a ica do p oblema PL0121.
suj. a:
x≤3.5
5x−4y≤10
4
7x+ 2y≤9
x , y ≥0
x≤3
y≥4
x≤1
Na igu a 10 pode-se e i ica que a solu¸c˜ao do p oblema PL0121 se ob ´em calculando
a in e sec¸c˜ao das ec as:
4
7x+ 2y= 9
x= 1
Essa in e sec¸c˜ao az-se no pon o (x, y) = (1,59
14 )≈(1,4.2). O alo da un¸c˜ao objec i o
nesse pon o ´e F=133
4≈32.5≥30 ( alo supe io ao da melho solu¸c˜ao in ei a ob ida a ´e
ao momen o).
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 67
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
Figu a 11: Resolu¸c˜ao g ´a ica do p oblema PL0122.
P oblema PL0122:
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
Analisando a igu a 11, pode-se conclui acilmen e que o p oblema PL0122 n˜ao em
qualque solu¸c˜ao admiss´ı el.
Na igu a 12 es ´a ep esen ada a ´a o e do B anch-and-Bound cons u´ıda a ´e ao mo-
men o.
Pa indo do p oblema PL0121 e in oduzindo duas no as es i¸c˜oes em y,y≤4 e
y≥5, ob ˆem-se dois no os p oblemas, PL01211 e PL0122.
P oblema PL01211:
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
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 68
PL0
(solução não in ei a)
x = 3.5
y = 3.5
F = 35
PL01
(solução não in ei a)
x = 3
y = 3.6
F = 34.5
PL02
(sem soluções)
PL011
(solução in ei a)
x = 3
y = 3
F = 30
PL012
(solução não in ei a)
x = 1.7
y = 4
F = 33.2
PL0121
(solução não in ei a)
x = 1
y = 4.2
F = 32.5
PL0122
(sem soluções)
x <= 3 x >= 4
y <= 3 y >= 4
x <= 1 x >= 2
Figu a 12: ´
A o e do B&B
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
Figu a 13: Resolu¸c˜ao g ´a ica do p oblema PL01211.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 69
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
Figu a 14: Resolu¸c˜ao g ´a ica do p oblema PL01212.
Na igu a 13 pode-se e i ica que a solu¸c˜ao do p oblema PL01211 se ob ´em calculando
a in e sec¸c˜ao das ec as:
x= 1
y= 4
Essa in e sec¸c˜ao az-se no pon o (x, y) = (1,4). O alo da un¸c˜ao objec i o nesse
pon o ´e F= 31.
P oblema PL01212:
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
Analisando a igu a 14, pode-se conclui acilmen e que o p oblema PL01212 n˜ao em
qualque solu¸c˜ao admiss´ı el. Assim, a solu¸c˜ao do p oblema PL01211 ´e a solu¸c˜ao ´op ima
(in ei a) do p oblema dado.
Na igu a 15 es ´a ep esen ada oda a ´a o e do B anch-and-Bound, cons u´ıda pa a
esolu¸c˜ao des e p oblema.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 70
PL0
(solução não in ei a)
x = 3.5
y = 3.5
F = 35
PL01
(solução não in ei a)
x = 3
y = 3.6
F = 34.5
PL02
(sem soluções)
PL011
(solução in ei a)
x = 3
y = 3
F = 30
PL012
(solução não in ei a)
x = 1.7
y = 4
F = 33.2
PL0121
(solução não in ei a)
x = 1
y = 4.2
F = 32.5
PL0122
(sem soluções)
PL01211
(solução in ei a óp ima)
x = 1
y = 4
F = 31
PL01212
(sem soluções)
x <= 3 x >= 4
y <= 3 y >= 4
x <= 1 x >= 2
y <= 4 y >= 5
Figu a 15: ´
A o e do B&B
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 71
B
Z = -23 2/3
x1 = 5 13/18
x2 = 2 4/9
x1 <= 5 x1 >= 6
G
Z = -23 1/8
x1 = 5
x2 = 2 5/8
C
sem solução admissí el
A
Z = -20
x1 = 5
x2 = 2
solução in ei a
E
Z = -22
x1 = 3 1/2
x2 = 3
x2 <= 2 x2 >= 3
F
sem solução admissí el
H
Z = -21 5/8
x1 = 3
x2 = 3 1/8
x1 <= 3 x1 >= 4
I
sem solução admissí el
D
Z = -21
x1 = 3
x2 = 3
solução in ei a
x2 <=3 x2 >= 4
P oblema com
meno alo de Z
P oblema
com x1 <= 5
e meno alo de Z
A ami icação só
pode se em x2 pois
x1é in ei o O ac o de não ha e nenhum
subp oblema com x1>=6 implica que
a in odução dessa es ição esul ou
num p oblema sem solução
admissí el.
O ac o de não ha e nenhum
subp oblema com x2>=3 e x1>=4
implica que a in odução dessa
es ição esul ou num p oblema sem
solução admissí el.
P oblema
com x1<=3 e x2>=3
e meno alo de Z
Solução in ei a e melho
do que a ob ida em A
solução óp ima
Figu a 1: ´
A o e do B&B
P oblema 2
Pa a ob en¸c˜ao da ´a o e de p oblemas (1)co esponden e aos subp oblemas ap esen ados
no enunciado, ´e necess´a io e em con a que o alo da un¸c˜ao objec i o “pio a”`a medida
que se desce na ´a o e ( em um maio alo nes e caso, dado que se a a de um p oblema
de minimiza¸c˜ao), dado que a descida na ´a o e co esponde `a in odu¸c˜ao de es i¸c˜oes
adicionais.
A p imei a ami ica¸c˜ao e e que se ei a em x1, dado que:
•em nenhum dos es an es subp oblemas exis e uma solu¸c˜ao com x1∈]5,6[ (con-
sequˆencia de se e impos o x1≤5 e x1≥6);
•se a ami ica¸c˜ao i esse sido em x2, odos os es an es subp oblemas e iam que e
x2≤2 ou x2≥3, mas o subp oblema G con adiz essa assump¸c˜ao.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de P og ama¸c˜ao In ei a
Resolu¸c˜oes 72
P oblema 3
(a) O melho limi e supe io sob e a solu¸c˜ao in ei a ´op ima no momen o de esolu¸c˜ao
e a ado na ´a o e ´e dado pela solu¸c˜ao do p oblema PL5 e ´e igual a 75. Qualque
solu¸c˜ao in ei a que su ja a pa i da explo a¸c˜ao desse n´o e ´a um alo da un¸c˜ao
objec i o ≤75
(b) Os limi es in e io es s˜ao dados po alo es de solu¸c˜oes admiss´ı eis ( a i´a eis j´a in-
ei as) que ainda se desconhece se s˜ao ou n˜ao ´op imas. Nes e caso emos j´a 2 solu¸c˜oes
in ei as, pa a PL6 e pa a PL4. A que em o maio alo da un¸c˜ao objec i o o nece
o melho limi e in e io , 70 nes e caso.
(c) J´a o am explo ados os n´os P L1, P L2, PL3 e P L7 po que j´a ˆem amos.
Os n´os P L4 e PL6 j´a o am explo ados po que de am o igem a solu¸c˜oes in ei as.
O n´o P L8 j´a es ´a explo ado po que co esponde a um p oblema sem solu¸c˜ao ad-
miss´ı el.
O n´o P L9 j´a oi explo ado po que pode se co ado. Co esponde a um p oblema
com solu¸c˜ao ´op ima n˜ao in ei a e com um alo pa a a un¸c˜ao objec i o in e io ao
alo da solu¸c˜ao in ei a do p oblema P L6.
(d) O n´o P L5 ainda n˜ao oi explo ado, dado que co esponde a um p oblema com solu¸c˜ao
´op ima n˜ao in ei a, mas com um alo pa a a un¸c˜ao objec i o supe io ao alo da
melho solu¸c˜ao in ei a ob ida a ´e ao momen o (p oblema PL6).
(e) N˜ao se sabe ainda se j´a oi ob ida a solu¸c˜ao ´op ima do p oblema in ei o, po que ainda
h´a n´os po explo a (P L5). S´o quando os melho es limi es in e io es e supe io es
coincidi em ´e que se pode a i ma que a melho solu¸c˜ao in ei a ob ida ´e a ´op ima.
( ) O alo m´aximo do e o absolu o sob e a solu¸c˜ao ´op ima in ei a, se o algo i mo o
e minado nes e pon o se ´a 5, is o ´e, a di e en¸ca en e os melho es limi es supe io
e in e io .
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
4
Exe c´ıcios de T anspo es
Resolu¸c˜oes

Exe c´ıcios de T anspo es
Resolu¸c˜oes 80
P oblema 1
Solu¸c˜ao inicial pela eg a dos cus os m´ınimos:
A B C D F
1 – – – – 15 15
23450
2 5 – – 15 – 20
32520
3 3 10 12 – – 25
41230
8 10 12 15 15
A cidade F ´e uma cidade ic ´ıcia in oduzida pa a equilib a a o e a com a p ocu a,
is o ´e, pa a coloca o p oblema na o ma “s anda d”.
Pa a que exis am 7 a i´a eis b´asicas (n´ume o de o igens + n´ume o de des inos - 1)
´e ainda necess´a io p omo e uma a i´a el n˜ao b´asica a b´asica. A a i´a el x1A oi en ˜ao
conside ada como b´asica com o alo de ze o. A escolha de x1Aem conc e o seguiu a eg a
de o g a o ep esen an i o das a i´a eis b´asicas de e se conexo e sem ciclos.
Resol endo:
0 -3 -2 -1 -2
2 0+θ– – – 15-θ
2 4 3 4 4 4 5 0
3 5 – – 15 –
3 2 2 4 5 2 -1 0
4 3-θ10 12 – θ
4 1 2 0 3 -2 0
θ= min{3,15}= 3
0 -1 0 -1 -2
2 3+θ– – – 12-θ
2 2 3 2 4 4 5 0
3 5-θ– – 15 θ
3 0 2 2 5 2 -1 0
2 – 10 12 – 3
4 1 2 2 3 0
θ= min{5,12}= 5
0 -1 0 0 -2
2 8 – – – 7
2 2 3 2 4 3 5 0
2 – – – 15 5
1 3 1 2 3 5 2 0
2 – 10 12 – 3
2 4 1 2 1 3 0
Cus o = 80
Solu¸c˜ao ´op ima: 1 8
−→ A; 3 10
−→ B; 3 12
−→ C; 2 15
−→ D
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de T anspo es
Resolu¸c˜oes 81
P oblema 2
(a) Fo mula¸c˜ao como p oblema de anspo es:
L1 L2 L3 RP1 RP2 X
P1/F1 77 94 74 0 ∞0 120
P1/F2 77 95 81 0 ∞0 120
P2/F1 72 89 69 ∞0 0 80
P2/F2 92 110 96 ∞0 0 80
50 70 60 120 80 20 400
Pi/Fj – quan idade expo ada a pa i da ´ab ica Pi a a ´es da on ei a Fj.
X – coluna in oduzida pa a equilib a a o e a com a p ocu a. Co esponde `as
quan idades que ica ˜ao nas ´ab icas.
RPi – Res i¸c˜ao espei an e `a ´ab ica Pi e que ga an e que o soma ´o io do que
a a essa as duas on ei as, indo da ´ab ica Pi, n˜ao excede a o e a em Pi.
(b) Solu¸c˜ao inicial pela eg a dos cus os m´ınimos:
30 – 60 10 100 90 30 0
23 40 20 0
20 70 – – 90 70 0
34 52 38 0
50 70 60 10
20 0 0 0
0
Aplicando o algo i mo de anspo es:
0 18 -3 -23
23 30+θ– 60 10-θ
23 -1 40 20 0
34 20-θ70 – θ
34 52 7 38 -11 0
θ= 10
0 18 -3 -34
23 40-θ θ 60 –
23 -1 40 20 11 0
34 10+θ70-θ– 10
34 52 7 38 0
θ= 40
0 18 -2 -34
22 – 40 60 –
1 23 40 20 12 0
34 50 30 – 10
34 52 6 38 0
Quad o ´op imo
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de T anspo es
Resolu¸c˜oes 82
Solu¸c˜ao ´op ima:
De Pa a Quan idade
F1 L1 0
L2 40
L3 60
F2 L1 50
L2 30
L3 0
Cus o ´op imo = 6060
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de T anspo es
Resolu¸c˜oes 83
P oblema 3
1.08
1.095
1.110
1.125
1.11
1.125
1.14
1.10
1.115
1.13
1
2
3
4
1
2
3
4
En ega
P odução
25
35
30
10
10
15
25
20
Mˆes de en ega
1234X
1 1.080 1.095 1.110 1.125 0 25
Mˆes de 2 ∞1.110 1.125 1.140 0 35
p odu¸c˜ao 3 ∞ ∞ 1.100 1.115 0 30
4∞ ∞ ∞ 1.130 0 10
10 15 25 20 30 100
(segue-se a esolu¸c˜ao pelo algo i mo de anspo es)
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de T anspo es
Resolu¸c˜oes 84
P oblema 4
(a) Fo mula¸c˜ao como p oblema de anspo es:
Des inos
2a3a4a5a6aX
No os 10 10 10 10 10 0 60+50+80+40+50
O igens Usados na 2a∞ ∞ 2 2 2 0 60
Usados na 3a∞ ∞ ∞ 2 2 0 50
Usados na 4a∞ ∞ ∞ ∞ 2 0 80
60 50 80 40 50 190
(b) ···
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

5
Exe c´ıcios de A ec a¸c˜ao
Enunciados
Exe c´ıcios de A ec a¸c˜ao
Enunciados 86
P oblema 1
Exis em qua o desenhado es pa a desenha qua o p ojec os. Embo a odos possam
cump i essas a e as, as suas e iciˆencias ela i as a iam de abalho pa a abalho.
Com base em desempenhos j´a conhecidos, p oduziu-se a seguin e abela de cus os:
D1D2D3D4
P18799
P25278
P36149
P42326
O objec i o ´e a ec a os desenhado es aos ´a ios p ojec os de modo a minimiza o
cus o o al de desenho.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Enunciados 87
P oblema 2
Uma ´ab ica possui qua o locais (1,2,3,4) pa a ecebe ˆes m´aquinas no as (A,B,C).
O local 4 ´e demasiado pequeno pa a con e a m´aquina A. O cus o da manipula¸c˜ao dos
ma e iais que s˜ao p ocessados nas m´aquinas, em cen enas de escudos/ho a, en ol endo
cada m´aquina com as espec i as posi¸c˜oes, ´e o seguin e:
1 2 3 4
A 5 1 3 x
B 3 1 4 3
C 3 3 4 2
P e ende-se de e mina que local ocupa ´a cada uma das no as m´aquinas, com o ob-
jec i o de minimiza o cus o o al de manipula¸c˜ao dos ma e iais.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Enunciados 88
P oblema 3
Dois jo ens ec´em-casados, Romeu e Julie a, que em di idi as a e as dom´es icas en e
si, de o ma a que cada um enha o mesmo n´ume o de a e as (duas pa a cada um) e de
o ma a que o empo o al gas o po semana seja man ido no m´ınimo.
(a) Conside ando a abela seguin e, onde se encon am os empos que cada um deles
gas a a execu a cada uma das a e as, esol a o p oblema des e casal.
Comp as Cozinha Limpeza Roupa
Romeu 2 6 4 3
Julie a 1.5 8.5 5.5 4
(b) Conside e ago a que, ap´os uma negocia¸c˜ao assaz di ´ıcil, Romeu conseguiu com que a
es i¸c˜ao das duas a e as pa a cada um osse le an ada, is o ´e, odas as combina¸c˜oes
do n´ume o de a e as a ibu´ıdas a cada um s˜ao poss´ı eis.
Re o mule o p oblema a endendo a es a no a si ua¸c˜ao.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 95
P oblema 3
(a) Quad o inicial:
Comp as Cozinha Limpeza Roupa
Romeu 1 2 6 4 3
Romeu 2 2 6 4 3
Julie a 1 1.5 8.5 5.5 4
Julie a 2 1.5 8.5 5.5 4
Sub ac¸c˜ao em cada linha do meno ele-
men o dessa linha
0 4 2 1
0 4 2 1
0 7 4 2.5
0 7 4 2.5
Sub ac¸c˜ao em cada coluna do meno el-
emen o dessa coluna
0 0 0 0
0 0 0 0
0 3 2 1.5
0 3 2 1.5
1ai e a¸c˜ao (3 <4)
0 0 0 0
0 0 0 0
0 3 2 1.5
0 3 2 1.5
Solu¸c˜ao ´op ima (4 = 4)
1.5 0 0 0
1.5 0 0 0
0 1.5 0.5 0
0 1.5 0.5 0
O cus o da solu¸c˜ao ´op ima (soma dos empos) ´e 15.5.
Uma poss´ı el solu¸c˜ao ´op ima se ia:
•Romeu ⇐⇒ cozinha
•Romeu ⇐⇒ limpeza
•Julie a ⇐⇒ comp as
•Julie a ⇐⇒ oupa
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 96
(b) Quad o inicial:
Comp as Cozinha Limpeza Roupa Nada 1 Nada 2 Nada 3 Nada 4
Romeu 1 2 6 4 3 0 0 0 0
Romeu 2 2 6 4 3 0 0 0 0
Romeu 3 2 6 4 3 0 0 0 0
Romeu 4 2 6 4 3 0 0 0 0
Julie a 1 1.5 8.5 5.5 4 0 0 0 0
Julie a 2 1.5 8.5 5.5 4 0 0 0 0
Julie a 3 1.5 8.5 5.5 4 0 0 0 0
Julie a 4 1.5 8.5 5.5 4 0 0 0 0
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 97
P oblema 4
Quad o inicial.
P oblema de maximiza¸c˜ao.
Ac escen ou-se um a i˜ao ic ´ıcio pa a
que n´ume o de a i˜oes = n´ume o de des-
inos.
Des ino A1A2A3Fic ´ıcio
Mon e Ca lo 8 11 10 ?
Ilhas Can´a ias 10 9 9 ?
Bia i z 9 4 8 ?
Ilhas G egas 6 7 5 ?
P oblema de minimiza¸c˜ao.
Complemen o pa a o m´aximo 11 dos el-
emen os da ma iz.
Des ino A1A2A3Fic ´ıcio
Mon e Ca lo 3 0 1 ?
Ilhas Can´a ias 1 2 2 ?
Bia i z 2 7 3 ?
Ilhas G egas 5 4 6 ?
Pa a e i a que A1ou A3sejam a ec os
`as Ilhas G egas, coloca-se ∞no cus o
dessa a ec a¸c˜ao.
Pa a ob iga que um dos a i˜oes eais
´a pa a Bia i z, impede-se que o a i˜ao
ic ´ıcio seja a ec o a Bia i z, colocando
∞no cus o dessa a ec a¸c˜ao.
3 0 1 0
1 2 2 0
273∞
∞4∞0
Sub ac¸c˜ao em cada coluna do meno el-
emen o dessa coluna
Sub ac¸c˜ao em cada linha do meno ele-
men o dessa linha
2 0 0 0
0 2 1 0
061∞
∞4∞0
1ai e a¸c˜ao (3 <4)
2 0 0 0
0 2 1 0
0 6 1 ∞
∞4∞0
Solu¸c˜ao ´op ima (4 = 4)
3001
0 1 0 0
050∞
∞3∞0
O alo (luc o) da solu¸c˜ao ´op ima ´e 29 M$.
Uma poss´ı el solu¸c˜ao ´op ima se ia:
•A1⇐⇒ Ilhas Can´a ias
•A2⇐⇒ Mon e Ca lo
•A3⇐⇒ Bia i z
•Fic ´ıcio ⇐⇒ Ilhas G egas
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 98
P oblema 5
(a) A ibui os luga es aos candida os po o ma a maximiza a sa is a¸c˜ao global das
p e e ˆencias:
Quad o inicial.
Associa um alo ze o `as a ec a¸c˜oes
ind .
P oblema de maximiza¸c˜ao.
Luga es
Candida os 1 2 3 4 5
1 -5 +8 -1 0 +4
2 -4 +2 +2 +3 +2
3 0 0 -5 -1 +3
4 -3 +3 +2 -2 -1
5 -1 +5 0 +3 +5
Soma +5 a odos os elemen os, pa a que
odos os elemen os ≥0.
P oblema de maximiza¸c˜ao.
Luga es
Candida os 1 2 3 4 5
1 0 13 4 5 9
2 1 7 7 8 7
3 5 5 0 4 8
4 2 8 7 3 4
5 4 10 5 8 10
P oblema de minimiza¸c˜ao.
Complemen o pa a o m´aximo 13 dos el-
emen os da ma iz.
13 0 9 8 4
12 6 6 5 6
8 8 13 9 5
11 5 6 10 9
9 3 8 5 3
Sub ac¸c˜ao em cada linha do meno ele-
men o dessa linha
Sub ac¸c˜ao em cada coluna do meno el-
emen o dessa coluna
10 0 8 8 4
4 1 0 0 1
0 3 7 4 0
3 0 0 5 4
3 0 4 2 0
1ai e a¸c˜ao (5 = 5)
Solu¸c˜ao ´op ima
10 0 8 8 4
41001
03740
30054
30420
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 99
O alo da solu¸c˜ao ´op ima ´e 18.
Uma poss´ı el solu¸c˜ao ´op ima se ia:
•Candida o1⇐⇒ Luga 2
•Candida o2⇐⇒ Luga 4
•Candida o3⇐⇒ Luga 1
•Candida o4⇐⇒ Luga 3
•Candida o5⇐⇒ Luga 5
(b) A esolu¸c˜ao do p oblema de modo a que o candida o menos sa is ei o seja “colo-
cado”com o m´ınimo de “incon eniˆencia”, co esponde a esol e um p oblema de-
nominado “Bo leneck Assignmen P oblem”.
Conside e-se en ˜ao uma a ec a¸c˜ao inicial
igual `a a ec a¸c˜ao ´op ima ob ida na al´ınea
(a):
-5 +8 -1 0 +4
-4 +2 +2 +3 +2
0 0 -5 -1 +3
-3 +3 +2 -2 -1
-1 +5 0 +3 +5
Min{0,8,2,3,5}= 0
Fa¸ca-se en ˜ao a seguin e subs i ui¸c˜ao:
• alo es >0→0
• alo es ≤0→1
1 0 1 1 0
1 0 0 0 0
1 1 1 1 0
1 0 0 1 1
1 0 1 0 0
Dado que a p imei a coluna do quad o s´o em alo es = 1, a a ec a¸c˜ao ´op ima pa a
o “Bo leneck Assignmen P oblem”´e a ob ida na al´ınea (a).
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 100
P oblema 6
Pa a esol e o p oblema p opos o, ´e necess´a io come¸ca po de e mina , pa a cada ae o-
po o, que oo de e ealiza um a i˜ao que enha chegado no oo x. O objec i o se ´a a
minimiza¸c˜ao do empo de espe a em cada ae opo o.
Te -se-˜ao en ˜ao que esol e 3 p oblemas de a ec a¸c˜ao (um pa a cada ae opo o). Esses
p oblemas pode ˜ao se esol idos com quad os independen es ou en ˜ao com um quad o
´unico:
Voo de Voo de pa ida
chegada 1 2 3 4 5 6 7 8 9 10
1∞∞∞∞∞16 23 3 ∞ ∞
2∞∞∞∞∞15 22 2 ∞ ∞
3∞∞∞∞∞10 17 21 ∞ ∞
4∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 7 15
5∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 5 13
6 2 3 8 13 15 ∞∞∞∞∞
7 19 20 1 6 8 ∞∞∞∞∞
8 15 16 21 2 4 ∞∞∞∞∞
9 22 23 4 9 11 ∞∞∞∞∞
10 14 15 20 1 3 ∞∞∞∞∞
Sub ac¸c˜ao em cada coluna
do meno elemen o dessa
coluna
Sub ac¸c˜ao em cada linha
do meno elemen o dessa
linha
∞ ∞ ∞ ∞ ∞ 5 5 0 ∞ ∞
∞ ∞ ∞ ∞ ∞ 5 5 0 ∞ ∞
∞ ∞ ∞ ∞ ∞ 0 0 19 ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0
0 0 7 12 12 ∞ ∞ ∞ ∞ ∞
17 17 0 5 5 ∞ ∞ ∞ ∞ ∞
12 12 19 0 0 ∞ ∞ ∞ ∞ ∞
17 17 0 5 5 ∞ ∞ ∞ ∞ ∞
12 12 19 0 0 ∞ ∞ ∞ ∞ ∞
1ai e a¸c˜ao (8 <10)
∞ ∞ ∞ ∞ ∞ 5 5 0 ∞ ∞
∞ ∞ ∞ ∞ ∞ 5 5 0 ∞ ∞
∞ ∞ ∞ ∞ ∞ 0 0 19 ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0
0 0 7 12 12 ∞ ∞ ∞ ∞ ∞
17 17 0 5 5 ∞ ∞ ∞ ∞ ∞
12 12 19 0 0 ∞ ∞ ∞ ∞ ∞
17 17 0 5 5 ∞ ∞ ∞ ∞ ∞
12 12 19 0 0 ∞ ∞ ∞ ∞ ∞
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 101
2ai e a¸c˜ao (9 <10)
∞ ∞ ∞ ∞ ∞ 0 0 0 ∞ ∞
∞ ∞ ∞ ∞ ∞ 0 0 0 ∞ ∞
∞ ∞ ∞ ∞ ∞ 0 0 24 ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0
0 0 12 12 12 ∞ ∞ ∞ ∞ ∞
12 12 0 0 0 ∞ ∞ ∞ ∞ ∞
12 12 24 0 0 ∞ ∞ ∞ ∞ ∞
12 12 0 0 0 ∞ ∞ ∞ ∞ ∞
12 12 24 0 0 ∞ ∞ ∞ ∞ ∞
3ai e a¸c˜ao (10 = 10)
Solu¸c˜ao ´op ima.
∞∞∞∞∞ 0 0 0 ∞ ∞
∞∞∞∞∞ 0 0 0 ∞ ∞
∞∞∞∞∞ 0 0 24 ∞ ∞
∞∞∞∞∞∞∞∞ 0 0
∞∞∞∞∞∞∞∞ 0 0
0 0 24 24 24 ∞ ∞ ∞ ∞ ∞
00000∞ ∞ ∞ ∞ ∞
0 0 24 0 0 ∞ ∞ ∞ ∞ ∞
00000∞ ∞ ∞ ∞ ∞
0 0 24 0 0 ∞ ∞ ∞ ∞ ∞
Uma poss´ı el solu¸c˜ao ´op ima se ´a:
•Voo de chegada 1 ⇐⇒ Voo de pa ida 8
•Voo de chegada 2 ⇐⇒ Voo de pa ida 7
•Voo de chegada 3 ⇐⇒ Voo de pa ida 6
•Voo de chegada 4 ⇐⇒ Voo de pa ida 9
•Voo de chegada 5 ⇐⇒ Voo de pa ida 10
•Voo de chegada 6 ⇐⇒ Voo de pa ida 1
•Voo de chegada 7 ⇐⇒ Voo de pa ida 3
•Voo de chegada 8 ⇐⇒ Voo de pa ida 4
•Voo de chegada 9 ⇐⇒ Voo de pa ida 2
•Voo de chegada 10 ⇐⇒ Voo de pa ida 5
Cons uindo uma “cadeia”po conca ena¸c˜ao das solu¸c˜oes encon adas ob ´em-se:
1 =⇒8 =⇒4 =⇒9 =⇒2 =⇒7 =⇒3 =⇒6 =⇒1
5 =⇒10 =⇒5
O plano di´a io dos oos es ´a ep esen ado na igu a seguin e:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de A ec a¸c˜ao
Resolu¸c˜oes 102
12345678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24
B A C
Voo
6AVoo
1B B Voo
8A A Voo
4
CVoo
9A
AVoo
2B
B A
Voo
7
Voo
3B
CVoo
10 A A Voo
5
C
Voo
5
Tu no 1
Tu no 2
Tu no 3
Tu no 4
Tu no 5
Ae opo o de
pa ida
Ae opo o de
chegada
XVoo
zY
Núme o do
oo
S˜ao po an o necess´a ios 5 a i˜oes. Con udo, pa a que se e i ique o “encadeamen o”´op imo
encon ado, 4 a i˜oes de e ˜ao oda nos u nos 1 a 4 e o 5oa i˜ao de e aze o u no 5, num
ciclo de 4 dias (Ai, a i˜ao i).
Dia
Tu no 1 2 3 4 5 . . .
1A1A4A3A2A1...
2A2A1A4A3A2...
3A3A2A1A4A3...
4A4A3A2A1A4...
5A5A5A5A5A5...
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
6
Exe c´ıcios Fluxo M´aximo
Enunciados
Exe c´ıcios Fluxo M´aximo
Enunciados 104
P oblema 1
De ˆes dep´osi os A, B e C, dispondo espec i amen e de 20, 10 e 35 oneladas de um
dado p odu o, p e ende-se aze chega a ˆes des inos D, E e F, espec i amen e 25, 20 e
20 oneladas do p odu o. As disponibilidades de anspo e em cami˜ao en e os di e en es
pon os, s˜ao as seguin es:
D E F
A 15 10 —
B 5 — 10
C 10 5 5
Es abele¸ca o melho plano de anspo es.
(Suges ˜ao: conside e um n´o ic ´ıcio ag egando a o e a e um n´o ic ´ıcio ag egando a
p ocu a).
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fluxo M´aximo
Resolu¸c˜oes 111
P oblema 2
A ede inicial es ´a ep esen ada na igu a seguin e.
(10,0)
2
(10,0)
1(15,0) 3 5 (20,0) 6
(20,0)
4
(5,0)
(5,0)
=0 =0
(15,0)
(12,0)
Seguindo o algo i mo de luxo m´aximo, seleccionou-se um caminho n˜ao sa u ado en e
o n´o de en ada e o n´o de sa´ıda. O caminho seleccionado oi 1 →4→5→6. Esse
caminho em uma capacidade m´axima de 15 (capacidade do amo com meno capacidade
4→5). Na igu a seguin e o amo 4 →5 oi ep esen ado a a¸co mais g osso e somou-se
15 ao luxo de en ada e de sa´ıda.
(10,0)
2
(10,0)
1(15,0) 3 5 (20,15) 6
(20,15)
4
(5,0)
(5,0)
=15 =15
(15,15)
(12,0)
O caminho n˜ao sa u ado seleccionado a segui oi 1 →2→6. Esse caminho em uma
capacidade m´axima de 10 (capacidade dos amos com meno capacidade 1 →2 e 2 →6).
Na igu a seguin e os amos com meno capacidade 1 →2 e 2 →6 o am ep esen ados a
a¸co mais g osso e somou-se 10 ao luxo de en ada e de sa´ıda.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de Fluxo M´aximo
Resolu¸c˜oes 112
(10,10)
2
(10,10)
1(15,0) 3 5 (20,15) 6
(20,15)
4
(5,0)
(5,0)
=25 =25
(15,15)
(12,0)
O caminho n˜ao sa u ado seleccionado a segui oi 1 →3→5→6. Esse caminho em
uma capacidade m´axima de 5 (capacidade do amo com meno capacidade →5→6). Na
igu a seguin e o amo com meno capacidade 5 →6 o am ep esen ados a a¸co mais
g osso e somou-se 5 ao luxo de en ada e de sa´ıda.
(10,10)
2
(10,10)
1(15,5) 3 5 (20,20) 6
(20,15)
4
(5,0)
(5,0)
=30 =30
(15,15)
(12,5)
O caminho n˜ao sa u ado seleccionado a segui oi 1 →4→6. Esse caminho em uma
capacidade m´axima de 5 (capacidade dos amos com meno capacidade 1 →4 e 4 →6).
Na igu a seguin e os amos com meno capacidade 1 →4 e 4 →6 o am ep esen ados a
a¸co mais g osso e somou-se 5 ao luxo de en ada e de sa´ıda.
(10,10)
2
(10,10)
1(15,5) 3 5 (20,20) 6
(20,20)
4
(5,5)
(5,0)
=35 =35
(15,15)
(12,5)
Co e mínimo
Na igu a an e io es ´a ep esen ado um co e m´ınimo (que sepa a o almen e a en ada
da sa´ıda). Pode-se en ˜ao a i ma que o luxo m´aximo nes a ede ´e 35.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Fluxo M´aximo
Resolu¸c˜oes 113
P oblema 3
(15,5)
2
1(20,20) 3
5
(15,9)
7
(10,9)
4
(10,10)
(2,2)
(5,5)
(5,3)
6
(15,15)
(3,3)
(4,2)
(4,4)
Co e mínimo
34 34
Na igu a an e io es ´a ep esen ado um co e m´ınimo (que sepa a o almen e a en ada
da sa´ıda). Pode-se en ˜ao a i ma que o luxo m´aximo nes a ede ´e 34.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
7
Exe c´ıcios de Caminho M´ınimo
Enunciados
Exe c´ıcios de Caminho M´ınimo
Enunciados 115
P oblema 1
Conside e a seguin e ede:
15
1
2
3
4
5
6
9
2
3
16
21
7
4 6
(a) Usando o algo i mo de Dijks a, de e mine a dis ˆancia m´ınima do n´o 1 ao n´o 6 e
indique o espec i o caminho.
(b) Pode, apenas a pa i dos c´alculos ei os em (a), dize qual ´e a dis ˆancia m´ınima do
n´o 1 ao n´o 4? Jus i ique.
(c) Pode ia, nas mesmas ci cuns ˆancias, indica qual a dis ˆancia m´ınima en e os n´os 2
e 6? Jus i ique.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Caminho M´ınimo
Enunciados 116
P oblema 2
A esquad a da PSP de Cedo ei a (Po o) ecebeu um pedido mui o u gen e pa a in e i
numa en a i a de assal o numa ou i esa ia localizada numa ua p ´oxima.
O Comando Ope acional deseja conhece qual se ´a o melho ajec o a oma , po
o ma a minimiza o empo da iagem a ´e ao objec i o p e endido. Usando um mapa
daquela zona da cidade, ep esen ado esquema icamen e na igu a, e conhecidos os empos
(m´edios, em segundos) necess´a ios pa a pe co e cada um dos o¸cos de ua ep esen ados,
u iliza am en ˜ao o algo i mo de Dijks a pa a de e mina esse caminho mais cu o (e,
en e an o os lad ˜oes...).
Coloque-se no luga do Comando, e, pa indo da ede ap esen ada, encon e esse cam-
inho m´ınimo.
1
2
3
4
8
10
12
PSP 13
14
6
6
8
12
11
9
8
16
7
8
5
9
5
10
7
13
10
11
9 4
3
14 Ou i esa ia10 9 4
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de Caminho M´ınimo
Enunciados 117
P oblema 3
Conside e um abulei o com 3 ×4 quad ´ıculas. Cada quad ´ıcula con ´em um n´ume o:
0 4 3 6
7 8 6 8
2 3 1 8
O objec i o do jogo consis e em desloca um pe˜ao desde o can o supe io esque do a ´e
ao can o in e io di ei o, a a ´es de uma sequˆencia de mo imen os pa a a di ei a ou pa a
baixo, de o ma a minimiza o soma ´o io dos pon os co esponden es `as quad ´ıculas po
onde se passou.
(a) Fo mule es e jogo como um p oblema de caminho m´ınimo.
(b) Resol a-o, usando uma das ´ecnicas es udadas na cadei a.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Caminho M´ınimo
Enunciados 118
P oblema 4
O S . Ven de Do , ´ecnico de endas, ai comp a um ca o no o. Dadas as ca ac e ´ıs icas
da p o iss˜ao do S . Ven de Do , o e´ıculo so e ´a uma u iliza¸c˜ao mui o g ande, o que implica
que, apesa de o S . Ven de Do se i e o ma daqui a 3 anos, possa se economicamen e
mais a o ´a el oca de ca o ao im de 1 ou 2 anos, em ez de o man e du an e os 3 anos.
Is o sob e udo po que os cus os de u iliza¸c˜ao e manu en¸c˜ao c escem mui o apidamen e
com o en elhecimen o dos e´ıculos.
O S . Ven de Do sen ou-se `a sua sec e ´a ia e calculou o cus o o al, p e¸co de um
ca o no o menos o que o s and d´a pelo usado, mais os cus os de u iliza¸c˜ao e manu en¸c˜ao
(o icina...), de comp a um ca o no o no ano ie oc´a-lo no im do ano j(o ano 0 ´e ago a).
Na abela seguin e es ˜ao ep esen ados (em milha es de escudos) os cus os calculados pelo
S . Ven de Do .
i
0 1 2
1 800
j 2 1800 1000
3 3100 2100 1200
Assim, po exemplo, oca o ca o ago a comp ado ( im do ano 0) no im do ano 1 e
depois man e o ca o comp ado no im do ano 1 a ´e ao im do ano 3, co esponde a um
cus o de 800 + 2100 = 2900.
O S . Ven de Do em que decidi quan as ezes de e oca de ca o (se alguma) de
o ma a minimiza a sua despesa o al com ca os du an e es es 3 anos.
(a) Fo mule es e p oblema como um p oblema de caminho m´ınimo.
(b) Resol a o p oblema u ilizando o algo i mo de Dijks a.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Caminho M´ınimo
Enunciados 119
P oblema 5
OPa´ıs Azul oi subi amen e a acado pelas opas do Pa´ıs Ve de. O Es ado-Maio das
Fo ¸cas Azuis euniu de imedia o pa a decidi sob e as mo imen a¸c˜oes de opas que se
de iam e ec ua , de modo a aze en e `a in as˜ao das Fo ¸cas Ve des.
O Es ado-Maio das Fo ¸cas Azuis oi in o mado que o a aque se es a a a p ocessa em
3 en es dis in as, com nomes de c´odigo β1,β2eβ3. Chegou-se de imedia o `a conclus˜ao
que se ia necess´a io anspo a duas di is˜oes de comba e pa a β1, uma di is˜ao pa a β2e
uma ou a pa a β3. As Fo ¸cas Azuis dispunham nessa al u a de 5 di is˜oes de comba e nas
cidades mais p ´oximas da on ei a a acada, duas aqua eladas em α1(em c´odigo, cla o!),
duas em α2e uma aqua elada em α3. Essas di is˜oes pode iam se anspo adas pa a os
locais em pe igo, con udo os A i˜oes Ve des j´a sob e oa am o Pa´ıs Azul, e a mo imen a¸c˜ao
das di is˜oes e ia que se aze com o meno isco humano poss´ı el.
Ap´os uma ´apida inspec¸c˜ao do mapa do e i ´o io ez-se o esquema da igu a seguin e,
onde se ep esen am as es adas que podem se u ilizadas pelas di is˜oes de comba e
das Fo ¸cas Azuis (os alo es ep esen ados nos o¸cos dos pe cu sos s˜ao dis ˆancias em
kil´ome os).
α11
α2
α3
β1
β2
β3
1
2
2
3
3
1
1
4 2
5
3
2
4
Os gene ais das Fo ¸cas Azuis, pe i os em In es iga¸c˜ao Ope acional, p ecisa am de
decidi de que aqua elamen o de iam segui as di is˜oes necess´a ias em β1,β2eβ3. O
objec i o e a a minimiza¸c˜ao das pe das humanas, elacionado di ec amen e com o pe igo
de bomba deamen o.
Du an e a euni˜ao do Es ado-Maio das Fo ¸cas Azuis, o gene al de 20 es elas Foj
(em c´odigo, como n˜ao podia deixa de se ) disse: “O pe igo de bomba deamen o das
di is˜oes em mo imen o pode se conside ado como di ec amen e p opo cional `a dis ˆancia
en e cada αe cada β. Nesse caso de em-se usa essas dis ˆancias como o pe igo que uma
di is˜ao co e ao se anspo ada de αipa a βie aplica um algo i mo de a ec a¸c˜ao pa a
esol e o p oblema”. O gene al Jac ac escen ou: “Pod´ıamos amb´em usa um algo i mo
de anspo es pa a esol e o p oblema, conside ando amb´em as dis ˆancias como uma
medida pa a o pe igo”. Po im, o gene al Soj o denou “A di is˜ao que sob a ica no
aqua elamen o espec i o”.
Siga as ins u¸c˜oes dos gene ais Foj,Jac eSoj e in o me-nos quais o am as decis˜oes
omadas pelo Es ado-Maio das Fo ¸cas Azuis,po que n´os somos as Fo ¸cas Ve des!!!!
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
7
Exe c´ıcios de Caminho M´ınimo
Resolu¸c˜oes
Exe c´ıcios de Caminho M´ınimo
Resolu¸c˜oes 127
P oblema 5
Numa p imei a ase, ai se necess´a io de e mina os caminhos m´ınimos en e os αie os
βj, pa a depois usa esses alo es an o no algo i mo de a ec a¸c˜ao suge ido pelo gene al
Foj como no algo i mo de anspo es suge ido pelo gene al Jac.
(a) De e mina¸c˜ao dos caminhos m´ınimos en e α1e os βj:
N´os
i e α11 2 β1β2β3
0 0∗∞ ∞ ∞ ∞ ∞
1 0∗1∗3∞ ∞ ∞
2 0∗1∗2∗3 5 ∞
3 0∗1∗2∗3∗5 4
4 0∗1∗2∗3∗5 4∗
5 0∗1∗2∗3∗5∗4∗
Resul ados:
•caminho α1→1→β1, com “cus o”3;
•caminho α1→1→β2, com “cus o”5;
•caminho α1→1→2→β3, com “cus o”4.
(b) De e mina¸c˜ao dos caminhos m´ınimos que pa em de α2:
N´os
i e α21 2 β1β2β3
0 0∗∞ ∞ ∞ ∞ ∞
1 0∗2∗2∞ ∞ ∞
2 0∗2∗2∗4 6 ∞
3 0∗2∗2∗4∗6 5
4 0∗2∗2∗4∗6 5∗
5 0∗2∗2∗4∗6∗5∗
Resul ados:
•caminho α2→1→β1, com “cus o”4;
•caminho α2→1→β2, com “cus o”6;
•caminho α2→2→β3, com “cus o”5.
(c) De e mina¸c˜ao dos caminhos m´ınimos que pa em de α3:
N´os
i e α31 2 β1β2β3
0 0∗∞ ∞ ∞ ∞ ∞
1 0∗∞1∗∞ ∞ 4
2 0∗∞1∗4 6 3∗
3 0∗∞1∗4∗6 3∗
4 0∗∞1∗4∗6∗3∗
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de Caminho M´ınimo
Resolu¸c˜oes 128
Resul ados:
•caminho α3→2→β1, com “cus o”4;
•caminho α3→2→β2, com “cus o”6;
•caminho α3→2→β3, com “cus o”3.
(a) Seguindo a suges ˜ao do gene al Foj: “O pe igo de bomba deamen o das di is˜oes em
mo imen o pode se conside ado como di ec amen e p opo cional `a dis ˆancia en e
cada αe cada β. Nesse caso de em-se usa essas dis ˆancias como o pe igo que uma
di is˜ao co e ao se anspo ada de αipa a βie aplica um algo i mo de a ec a¸c˜ao
pa a esol e o p oblema”.
U ilizem-se en ˜ao os alo es ob idos pelo algo i mo de caminho m´ınimo, pa a o algo-
i mo de a ec a¸c˜ao. O des ino X no quad o abaixo co esponde `a o dem do gene al
Soj “A di is˜ao que sob a ica no aqua elamen o espec i o”.
Di is˜oes necess´a ias
Di is˜oes β1β1β2β3
dispon´ı eis 1 2 3 4 X
α11 3 3 5 4 0
α12 3 3 5 4 0
α23 4 4 6 5 0
α24 4 4 6 5 0
α35 4 4 6 3 0
1 2 3 4 X
1 0 0 0 1 0
2 0 0 0 1 0
3 1 1 1 2 0
4 1 1 1 2 0
5 1 1 1 0 0
4 a¸cos <5
1234X
1 0 0 0 1 1
2 0 0 0 1 1
3 0 0 0 1 0
4 0 0 0 1 0
5 1 1 1 0 1
5 a¸cos, solu¸c˜ao ´op ima com cus o 3 +
3 + 6 + 3 + 0 = 15.
A conclus˜ao des e es udo ´e a seguin e:
•as duas di is˜oes aqua eladas em α1de em i pa a β1(passando po 1);
•uma das di is˜oes aqua eladas em α2de e i pa a β2(passando po 1) e a ou a
de e-se man e em α1;
•a di is˜ao aqua elada em α3de e i pa a β3(passando po 2).
O cus o (pe igo) o al da solu¸c˜ao se ´a 15.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Caminho M´ınimo
Resolu¸c˜oes 129
(b) Seguindo a suges ˜ao do gene al Jac: “Pod´ıamos amb´em en a usa um algo i mo
de anspo es pa a esol e o p oblema, usando amb´em as dis ˆancias como uma
medida pa a o pe igo”.
U iliza¸c˜ao dos alo es ob idos pelo algo i mo de caminho m´ınimo, pa a o algo i mo
de anspo es:
3
4
4
5
6
4
5
3
0
0
06
α1
α2
α3
1 1 12
2
2
1
β1β2β3X
Ob en¸c˜ao da solu¸c˜ao inicial pela eg a dos cus os m´ınimos:
2
1
0
1
0
1
0
1
0
/
/
/ / /
2 1 0
2 1 0
1 0
/ /
/ /
/
1
1
--
--
1
--
--
--
1
1
--
0
3
4
4
5
6
6
4
5
3
0
0
0
P imei o quad o do algo i mo de anspo es:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Caminho M´ınimo
Resolu¸c˜oes 130
3
4
3
020-3
1+θ
1-θ
--
--
1
--
--
--
1
1-θ
θ
0
3
4
4
5
6
6
4
5
3
0
0
01 1
1
1-1
0
Do quad o an e io e i a-se que θ= 1 e pode-se ob e segundo quad o do algo i mo
de anspo es:
2
0
--
--
1
--
--
--
1
--
1
0
0 2 -1 -4
3
4
4
3
4
4
5
6
6
4
5
3
0
0
00 0
1
2
0 1
A conclus˜ao des e es udo ´e igual `a ob ida pelo algo i mo de a ec a¸c˜ao (como se ia
de espe a ):
•as duas di is˜oes aqua eladas em α1de em i pa a β1(passando po 1);
•uma das di is˜oes aqua eladas em α2de e i pa a β2(passando po 1) e a ou a
de e-se man e em α1;
•a di is˜ao aqua elada em α3de e i pa a β3(passando po 2).
O cus o (pe igo) o al da solu¸c˜ao se ´a 2 ×3 + 1 ×6 + 1 ×0 + 1 ×3 = 15.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
8
Exe c´ıcios de CPM e PERT
Enunciados
Exe c´ıcios de CPM e PERT
Enunciados 132
P oblema 1
O banco TTM (Tos ˜ao a Tos ˜ao se az um Milh˜ao) decidiu ans e i e amplia a sua
sede e se i¸cos cen ais pa a a cidade do Po o. Es e p ojec o oi di idido em a e as,
endo as suas p ecedˆencias sido es abelecidas e os empos de execu¸c˜ao m´edios, e seus
des ios-pad ˜ao, es imados:
Ac i idade Desc i¸c˜ao Du a¸c˜ao Des io- Ac i idades
m´edia Pad ˜ao imedia amen e
(semanas) (semanas) pos e io es
LO Ob en¸c˜ao de licen¸cas de ob as 5 1 OA, ME RTF
OA Ob as de al e a¸c˜ao do edi ´ıcio 21 2 II
ME Medi¸c˜ao do espa¸co 1 0 PAI, PAM
RTF Rec u amen o e eino dos uncion´a ios 21 1 M
PAI Planeamen o e aquisi¸c˜ao de in a-es u u as 24 1 II
II Ins ala¸c˜ao de in a-es u u as 7 1 IM
PAM Planeamen o e aquisi¸c˜ao de mobili´a io 10 1 IM
IM Ins ala¸c˜ao de mobili´a io 1 0 M
M Mudan¸ca 2 0 —
(a) Desenhe a ede de ac i idades co esponden e ao p ojec o.
(b) Calcule as olgas o ais e li es e de e mine o caminho c ´ı ico.
(c) Qual ´e a p obabilidade de o p ojec o se a asa 2 semanas ou mais?
(d) Du an e a execu¸c˜ao do p ojec o conclui-se que as ac i idades OA e PAM so e ˜ao
a asos de 4 e 8 semanas, espec i amen e. Se ´a necess´a io al e a a execu¸c˜ao dessas
ac i idades pa a que a da a p e is a pa a a conclus˜ao do p ojec o n˜ao seja comp o-
me ida? Jus i ique.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de CPM e PERT
Enunciados 133
P oblema 2
No quad o seguin e es ˜ao ep esen adas as ac i idades que cons i uem um de e minado
p ojec o. Pa a cada uma ´e o necida a sua du a¸c˜ao e as ac i idades que lhe s˜ao imedia a-
men e pos e io es:
Ac i idade Du a¸c˜ao Ac i idades
m´edia imedia amen e
(semanas) pos e io es
A 2 G
B 4 —
C 7 E, I, B
D 3 A, F
E 3 G
F 3 I, B
G 4 H
H 5 —
I 9 H
Desenhe a ede de ac i idades associada a es e p ojec o e de e mine o caminho c ´ı ico
e as olgas o ais e li es de odas as ac i idades do p ojec o.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de CPM e PERT
Enunciados 134
P oblema 3
Conside e o seguin e p ojec o:
Ac i idade Du a¸c˜ao Des io- Ac i idades
m´edia Pad ˜ao imedia amen e
(semanas) (semanas) p eceden es
A 8 3 D
B 1 0 H
C 5 1 —
D 8 2 —
E 10 3 C, D
F 6 2 H
G 4 1 B, I, J
H 5 1 A, E
I 9 2 D
J 2 0 A, E
(a) T ace a ede de ac i idades pa a es e p ojec o.
(b) De ina o caminho c ´ı ico (em e mos de du a¸c˜oes m´edias).
(c) De ina as olgas m´edias ( o al e li e) das ac i idades H, J e I.
(d) De e mine a p obabilidade de o p ojec o es a conclu´ıdo an es da semana 27 (admi a
que o p ojec o a anca no in´ıcio da semana 0). C i ique a es ima i a da p obabilidade
ob ida.
(e) Qual a p obabilidade de o p ojec o es a conclu´ıdo en e o in´ıcio da semana 27 e o
im da semana 30?
( ) Que da a de conclus˜ao do p ojec o de e ´a se p opos a, pa a que haja apenas 5%
de p obabilidade de n˜ao a cump i ?
(g) No im da semana 13, o es ado de execu¸c˜ao das di e en es ac i idades ´e o seguin e:
•ac i idades comple as: C e D
•ac i idades em execu¸c˜ao:
–E ( alo espe ado da du a¸c˜ao es an e: 1 semana)
–A ( alo espe ado da du a¸c˜ao es an e: 1 semana)
–I ( alo espe ado da du a¸c˜ao es an e: 8 semana)
–ac i idades n˜ao iniciadas: as es an es
Rede ina a ede. Indique sob e a ede os alo es espe ados das da as de in´ıcio mais
cedo e das da as de im mais a de pa a as ac i idades n˜ao e minadas, bem como
o(s) caminho(s) c ´ı ico(s), na no a si ua¸c˜ao.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de CPM e PERT
Enunciados 135
P oblema 4
Um dado p ojec o en ol e as 9 ac i idades que se ca ac e izam na abela seguin e:
Ac i idade Du a¸c˜ao Des io- Ac i idades
m´edia Pad ˜ao imedia amen e
(semanas) (semanas) an e io es
A 10 2 —
B 7 1 —
C 16 3 —
D 12 1 A
E 5 1 B
F 12 2 B
G 8 2 E, D
H 10 2 F, E, D
I 8 2 G, H
(a) De ina os n´ume os de o dem das ac i idades, desenhe a ede co esponden e e de-
e mine o caminho c ´ı ico.
(b) Calcule as olgas m´edias o al e li e das ac i idades F, B e D. Qual o in e esse
desses alo es no con olo de um p ojec o?
(c) Calcule a p obabilidade de o p ojec o n˜ao es a comple o ao im de 50 semanas. Que
con ian¸ca em no alo encon ado?
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
8
Exe c´ıcios de CPM e PERT
Resolu¸c˜oes
Exe c´ıcios de CPM e PERT
Resolu¸c˜oes 143
No ação: -Nós
-Ac i idades i j
Designação (dij)
i
C(5)
1
3
245
6
D(8)
A(8)
H(5)
B(1)
E(10) 7
J(2)
I(9)
G(4)
F(6)
(b) Na igu a seguin e es ˜ao ep esen adas as olgas o ais e li es de cada uma das
ac i idades. O caminho c ´ı ico co esponde `as ac i idades D→E→H→Fe em
uma du a¸c˜ao m´edia de 29 semanas.
ESi. LF.j
No ação: -Nós
-Ac i idades
-Ac i idades c í icas
i j
Designação (d
ij)
FTij/FLij
i j
i
C(5)
3/3
1
3
245
6
D(8)
0/0
A(8)
2/2
H(5)
0/0
B(1)
1/0
E(10)
0/0 7
J(2)
5/4
I(9)
8/7
G(4)
1/1
F(6)
0/0
0 0
8 8 18 18 23 23 29 29
24 258 8
(c) Ve igu a an e io .
(d) A du a¸c˜ao o al do p ojec o ´e igual `a soma das du a¸c˜oes das ac i idades do caminho
c ´ı ico:
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

Exe c´ıcios de CPM e PERT
Resolu¸c˜oes 144
DT=D1+D2+D3+...+Dn= 29
Como as du a¸c˜oes das ac i idades s˜ao a i´a eis alea ´o ias, DT amb´em se ´a uma
a i´a el alea ´o ia com m´edia µTdada po :
µT=µ1+µ2+µ3+...+µn= 8 + 10 + 5 + 6 = 29
Admi indo que as du a¸c˜oes das ac i idades s˜ao a i´a eis alea ´o ias independen es, a
a iˆancia da du a¸c˜ao o al σ2
Tse ´a:
σ2
T=σ2
1+σ2
2+σ2
3+...+σ2
n= 22+ 32+ 12+ 22= 18
Du a¸c˜ao o al do p ojec o pode se desc i a po uma dis ibui¸c˜ao no mal com m´edia
µTe a iˆancia σ2
T.
Nes e caso e emos en ˜ao:
P(D≤27) = PZ≤27−µT
σT=P(Z≤27−29
4.24 ) = P(Z≤ −0.47) ≈0.5−0.1808 ≈
0.32
A p obabilidade de o p ojec o es a conclu´ıdo an es da semana 27 ´e de ap oximada-
men e 30%.
Foi di o que a du a¸c˜ao do caminho c ´ı ico inha uma dis ibui¸c˜ao que endia pa a a
dis ibui¸c˜ao no mal. Isso signi ica que a sua dis ibui¸c˜ao n˜ao se ´a exac amen e no -
mal, al como n´os a conside amos. Es amos pois pe an e uma poss´ı el on e de e o
pa a a es ima i a da p obabilidade encon ada. Ou o p essupos o que pode alsea
os esul ados ´e de que a du a¸c˜ao do p ojec o ´e a du a¸c˜ao do caminho c ´ı ico encon-
ado. O a es e ´e o caminho c ´ı ico quando as ac i idades demo am exac amen e a
sua du a¸c˜ao m´edia. Se isso n˜ao acon ece pode o caminho c ´ı ico se al e ado e a
du a¸c˜ao do p ojec o n˜ao co esponde `a du a¸c˜ao do caminho c ´ı ico “m´edio”.
(e) A p obabilidade de o p ojec o es a conclu´ıdo en e o in´ıcio da semana 27 e o im da
semana 30 ´a a p obabilidade de a du a¸c˜ao do p ojec o es a en e 27 e 31.
P(27 ≤D≤31) = P27−29
4.24 ≤Z≤31−29
4.24 =P(−0.47 ≤Z≤0.47) = 2 ×0.1808 ≈
0.36
( ) De em-se p opo 36 semanas a ´e `a conclus˜ao do p ojec o, pa a que haja apenas 5%
de p obabilidade de n˜ao cump imen o.
P(D≥d) = 0.05 ≡PZ≥d−29
4.24 = 0.05 ≡d−29
4.24 = 1.645 ≡d= 36 semanas
(g) A si ua¸c˜ao in e m´edia e e ida no enunciado, es ´a ep esen ada na igu a seguin e.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de CPM e PERT
Resolu¸c˜oes 145
ESi. LF.j
No ação: -Nós
-Ac i idades
-Ac i idades c í icas
i j
Designação (dij)
i j
i
3
245
6
A*(1)
H(5)
B(1)
E*(1) 7
J(2)
I*(8)
G(4)
F(6)
0 0 1 1 6 6 12 12
8 80 0
Os caminhos c ´ı icos co espondem `as ac i idades E→H→F,A→H→Fe
I→Ge ˆem uma du a¸c˜ao m´edia de 12 semanas
A semana 0 des a ede co esponde `a semana 14 da ede inicial, o que signi ica que
o p ojec o pode e mina no in´ıcio da semana 26 (ou im da semana 25), es ando 3
semanas adian ado ace `a p e is˜ao inicial.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de CPM e PERT
Resolu¸c˜oes 146
P oblema 4
(a) Pa a desenha a ede de ac i idades ´e necess´a io come¸ca po a ibui um n´ume o
de o dem a cada ac i idade, seguindo o algo i mo dado nas aulas e´o icas:
Ac i . imedia amen e pos e io es N´ume o
Ac i idade A B C D E F G H I de o dem
A x 1
B x x 1
C 1
D x x 2
E x x 2
F x 2
G x 3
H x 3
I 4
Seguidamen e, desenham-se 4+1 = 5 linhas e icais e cons oi-se a ede pa indo do
im pa a o p inc´ıpio. O in´ıcio de cada ac i idade coincide com a linha e ical co e-
sponden e ao seu n´ume o de o dem. Es a ase do desenho da ede es ´a ep esen ada
na igu a seguin e.
1 2 3 4 5
A
B
C
D
E
F
G
H
I
Simpli icando a ede ap esen ada na igu a an e io , ob ´em-se a ede ep esen ada
na igu a seguin e.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de CPM e PERT
Resolu¸c˜oes 147
A(10)
B(7)
C(16)
D(12)
E(5)
F(12)
G(8)
H(10)
I(8)
No ação: -Nós
-Ac i idades i j
Designação (d
ij)
i
O caminho c ´ı ico co esponde `as ac i idades A→D→H→Ie em uma du a¸c˜ao
m´edia de 40 semanas.
A(10)
B(7)
C(16)
D(12)
E(5)
F(12)
G(8)
H(10)
I(8)
No ação: -Nós
-Ac i idades
-Ac i idades c í icas
i j
Designação (dij)
i
0 0
ESi. LF.j
10 10
710
22 22 32 32 40 40
22 22
i j
(b) Na igu a seguin e es ˜ao ep esen adas as olgas o ais e li es de cada uma das
ac i idades.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de CPM e PERT
Resolu¸c˜oes 148
A(10)
0/0
B(7)
3/0
C(16)
D(12)
0/0
E(5)
10/10
F(12)
3/3
G(8)
2/2
H(10)
0/0
I(8)
0/0
No ação: -Nós
-Ac i idades
-Ac i idades c í icas
i j
i
0 0
ESi. LF.j
10 10
710
22 22 32 32 40 40
22 22
i j
Designação (dij)
FTij/FLij
(c) A du a¸c˜ao o al do p ojec o ´e igual `a soma das du a¸c˜oes das ac i idades do caminho
c ´ı ico:
DT=D1+D2+D3+...+Dn= 40
Como as du a¸c˜oes das ac i idades s˜ao a i´a eis alea ´o ias, DT amb´em se ´a uma
a i´a el alea ´o ia com m´edia µTdada po :
µT=µ1+µ2+µ3+...+µn= 10 + 12 + 10 + 8 = 40
Admi indo que as du a¸c˜oes das ac i idades s˜ao a i´a eis alea ´o ias independen es, a
a iˆancia da du a¸c˜ao o al σ2
Tse ´a:
σ2
T=σ2
1+σ2
2+σ2
3+...+σ2
n= 22+ 12+ 22+ 22= 13
Du a¸c˜ao o al do p ojec o pode se desc i a po uma dis ibui¸c˜ao no mal com m´edia
µTe a iˆancia σ2
T.
Nes e caso e emos en ˜ao:
P(D≥51) = PZ≥51−µT
σT=P(Z≥51−40
3.61 ) = P(Z≥3.05) ≈1−0.5−0.4989 ≈
0.0011
A p obabilidade de o p ojec o n˜ao es a conclu´ıdo ao im de 50 semanas ´e de ap ox-
imadamen e 1%.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a

9
Exe c´ıcios de Teo ia da Decis˜ao
Enunciados
Exe c´ıcios de Teo ia da Decis˜ao
Enunciados 150
P oblema 1
Uma emp esa de au om´o eis apos a numa no a pe¸ca pa a ca os. Como al e na i a `a i&d
po con a p ´op ia, a di ec¸c˜ao da emp esa admi e a possibilidade de se liga a uma i ma
de consul o ia em engenha ia. A abela 1 ap esen a os luc os espe ados, em alo ac ual,
pa a os p ´oximos 5 anos, con o me o sucesso alcan¸cado:
Luc os G ande sucesso Sucesso mode ado Sem sucesso
(M$) (p1) (p2) (p3)
D(desen ol imen o p ´op io) 300 40 -60
C(em colabo a¸c˜ao com ou a emp esa) 200 30 -20
Tabela 1: Luc os espe ados (em alo ac ual) pa a os p ´oximos 5 anos, con o me o sucesso
alcan¸cado
Com base em es udos de iabilidade e consul a a g upos de ma ke ing e de desen-
ol imen o, encon a am-se as p obabilidades de p1= 0.2, p2= 0.4 e p3= 0.4, pa a as
oco ˆencias conside adas.
(a) Qual a decis˜ao a que co esponde ao m´aximo alo espe ado? Ap esen e uma ´a o e
de decis˜ao.
(b) Qual a decis˜ao a oma caso se u ilize o c i ´e io maximin?
(c) De e mine o ganho espe ado com in o ma¸c˜ao ce a, e explique o seu signi icado.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Teo ia da Decis˜ao
Enunciados 151
P oblema 2
Um ges o ai decidi sob e quan as m´aquinas de um dado ipo comp a , que s˜ao unda-
men ais pa a a p odu¸c˜ao de um ce o a igo. Ap´os uma an´alise inicial, a ques ˜ao esume-se
a duas al e na i as: comp a 1 m´aquina ou comp a 2 m´aquinas. Se 1 m´aquina o com-
p ada e a p ocu a do a igo o ele ada, a 2am´aquina ainda pode ´a se comp ada mais
a de. Con udo, o cus o po m´aquina se ´a meno se as 2 o em comp adas ao mesmo
empo. As p obabilidades es imadas pa a a p ocu a do a igo s˜ao: p ocu a baixa 0.30 e
p ocu a al a 0.70. O alo ac ual associado aos esul ados de comp a de 2 m´aquinas no
in´ıcio ´e de 750c, se a p ocu a o baixa, e de 1300c se o al a a p ocu a do a igo.
O alo co esponden e pa a uma m´aquina sob p ocu a baixa ´e de 900c. Se a p ocu a
o al a h´a 3 hip´o eses: nada aze esul a no alo de 900c; subcon a a da ´a 1100c;
comp a a 2am´aquina pe mi i ´a ob e 1000c. Quan as m´aquinas de e ˜ao se comp adas
no in´ıcio?
No a: U ilize uma ´a o e de decis˜ao pa a analisa o p oblema.
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a
Exe c´ıcios de Teo ia da Decis˜ao
Enunciados 152
P oblema 3
Uma g ande companhia de ene gia o e ece $60 000 ao p op ie ´a io de de e minado local,
pelos di ei os de explo a¸c˜ao do g´as na u al e op¸c˜ao pa a desen ol imen o u u o. A op¸c˜ao,
se conc e izada, ´e equi alen e a um adicional de $600 000 ao p op ie ´a io, mas somen e
oco e ´a se o g´as na u al o descobe o du an e a ase de explo a¸c˜ao. O p op ie ´a io, endo
que o in e esse da companhia ´e uma boa indica¸c˜ao de que o g´as exis e, es ´a dispos o a
desen ol e o emp eendimen o ele mesmo. Pa a isso, ´e necess´a io con a a especialis as
em explo a¸c˜ao e desen ol imen o. O cus o inicial ´e de $100 000, os quais se ˜ao pe didos se
nenhum g´as o encon ado. Se o g´as o descobe o, en e an o, o p op ie ´a io es ima ´a
um luc o de $2 milh˜oes.
As al e na i as de decis˜ao do p op ie ´a io s˜ao D1(acei a a o e a da companhia de
ene gia) e D2(explo a e desen ol e ele p ´op io). Os es ados na u ais s˜ao S1(n˜ao exis e
g´as na e a) e S2(exis e g´as na e a). Os ganhos (em milha es de $) do p op ie ´a io, pa a
cada combina¸c˜ao de e en os, s˜ao dados na abela 1. O p op ie ´a io es ima a p obabilidade
de encon a g´as igual a 0.6.
S1S2
D160 660
D2-100 2000
Tabela 1: Ganhos (em milh˜oes de $ pa a cada combina¸c˜ao de e en os)
De e mine as decis˜oes ecomendadas pelos seguin es c i ´e ios:
(a) Maximin
(b) M´edia
(c) M´aximo alo espe ado
J.C.Al es, M.A.Ca a illa, J. Cla o, A.M.Gomes, J.A.Fe ei a, J.F.Oli ei a