P og amação Linea In ei a
R
Ru
ui
i
A
Al
l
e
es
s
C
Ca
a
a
a
i
in
na
a
D
De
el
lg
ga
ad
do
o
S
Se
e
e
em
mb
b
o
o
d
de
e
1
19
99
97
7
APRESENTAÇÃO
Es e ex o conc e iza uma ideia que já em alguns anos, mas que inha sendo
adiada de ido a a aze es de di e sa na u eza.
Dois ac os oco idos no ano lec i o de 1996/97 o am de e minan es na conc e-
ização des e p ojec o: (i) a adopção, nas disciplinas de In es igação Ope acional de
ambas as licencia u as, de um li o (In es igação Ope acional, de L. Valada es Ta a es
e al., McG aw-Hill, 1996) que, embo a cob indo a ma é ia de P og amação Linea e de
Filas de Espe a, é omisso no que oca à P og amação Linea In ei a e às Cadeias de
Ma ko ; (ii) a con a ação da licenciada Ca a ina Delgado como assis en e es agiá ia
das e e idas disciplinas.
O ac o de os alunos dispo em de elemen os de es udos (no li o adop ado) sob e
alguns pon os do p og ama o nou mais p emen e a conclusão des es ex os com o
objec i o de uma in eg al cobe u a do p og ama. A disponibilidade da licenciada
Ca a ina Delgado oi na ealidade c ucial (sem o seu abalho e o seu en usiasmo c eio
que os ex os não e iam icado p on os), e o seu con ibu o jus i ica plenamen e a co-
au o ia que lhe é de ida, pois a ela se de em a p imei a e são dos ex os, odos os
exemplos p o usamen e ilus ados, e a inclusão de uma maio a iedade de p oblemas
ípicos de P og amação In ei a.
Res a-nos deseja que os alunos, des ina á ios úl imos des es abalhos, deles
possam i a i a o desejado p o ei o. Todas as c í icas e suges ões são ben indas,
sal agua dando que odos os e os e imp ecisões que os ex os possam e são da in ei a
esponsabilidade dos au o es.
Faculdade de Economia do Po o, Se emb o de 1997
P o . Dou o Rui Al es
ÍNDICE
1. INTRODUÇÃO ..................................................................................................... 1
2. CONDIÇÕES EXPRESSAS ATRAVÉS DE VARIÁVEIS BINÁRIAS ............. 2
2.1. Gene alidades ......................................................................................................... 2
2.2. Res ições Mu uamen e Exclusi as ....................................................................... 2
2.3. Respei a k de m Res ições ............................................................................... 2
2.4. Funções com N Valo es Possí eis ....................................................................... 3
2.5. Res ições Condicionadas ...................................................................................... 4
2.6. Rep esen ação de Cus os Fixos .............................................................................. 4
2.7. Máximo de N Va iá eis ....................................................................................... 5
3. ALGUNS PROBLEMAS TÍPICOS DE PI ........................................................... 5
3.1. P oblema de A ec ação .......................................................................................... 5
3.2. P oblema do Caixei o Viajan e .............................................................................. 6
3.3. P oblema da Mochila ............................................................................................. 8
3.4. P oblema da Cobe u a e da Pa ição de Conjun os ............................................... 9
3.5. P oblema de Selecção de P ojec os ...................................................................... 10
3.6. P oblema de Localização ..................................................................................... 11
4. MÉTODOS DE RESOLUÇÃO ........................................................................... 12
4.1. Gene alidades ....................................................................................................... 12
4.2. Mé odo dos Planos de Co e ................................................................................ 14
4.3. Mé odo de Pa ição e A aliação Sucessi as ........................................................ 17
5. BIBLIOGRAFIA ................................................................................................. 22
1
1. INTRODUÇÃO
Um p oblema de P og amação Linea In ei a (PLI) é um p oblema de P og ama-
ção Linea (PL) em que odas ou alguma(s) das suas a iá eis são disc e as ( êm de as-
sumi alo es in ei os). Quando odas as a iá eis es ão sujei as à condição de in e-
g alidade es amos pe an e um p oblema de P og amação Linea In ei a Pu a (PLIP); e se
apenas algumas o es ão a a-se de um p oblema de P og amação Linea In ei a Mis a
(PLIM). Embo a a P og amação In ei a (PI) inclua ambém a P og amação Não-Linea
In ei a, em p a icamen e odos os modelos da ida eal se p ese a a es u u a linea das
unções, pelo que quase não exis e di e ença en e a PI e a PLI.
Os modelos de PLI se ão en ão do ipo dos modelos de PL, sujei os a es ições
adicionais indicando que algumas ou odas as a iá eis são disc e as, con o me se pode
e no exemplo seguin e:
Exis e um caso especial de a iá eis in ei as: as a iá eis biná ias que apenas po-
dem oma os alo es 0 (ze o) ou 1 (um). Quando odas as a iá eis de um modelo são
biná ias, o modelo diz-se de P og amação In ei a Biná ia. As a iá eis biná ias são
mui o ú eis pa a exp imi em si uações dico ómicas (sim ou não, aze ou não aze , e c.),
con o me se e á nos pon os 2 e 3.
Es e ex o encon a-se o ganizado da seguin e o ma: no pon o 2 são es udadas
di e sas condições que podem se exp essas com o auxílio de a iá eis biná ias e no
pon o 3 são ap esen ados alguns p oblemas ípicos de P og amação In ei a. O pon o 4 é
dedicado a passa em e is a os mé odos de esolução de modelos de PLI, sendo dada
a enção especial ao mé odo de pa ição e a aliação sucessi as. Finalmen e, no pon o 5 é
lis ada a bibliog a ia consul ada pa a a elabo ação do ex o e conside ada mais ele an e
nes a ma é ia.
max F = 4x1-5x2
suj. a: 2x1+3x2 ≤ 8
5x1+2x2 ≤ 11
x1, x2 ≥ 0 e in ei as
O co esponden e p oblema de PL ( elaxação do PI, dado que se “ala ga” o
domínio das a iá eis de decisão de |N0 pa a |R) é:
max F = 4x1-5x2
suj. a: 2x1+3x2 ≤ 8
5x1+2x2 ≤ 11
x1, x2 ≥ 0
(PI)
(PL)
2



3 x1 + 4 x2 ≤ 12 + M y
5 x1 + 2 x2 ≤ 10 + M (1-y)
2. CONDIÇÕES EXPRESSAS ATRAVÉS DE VARIÁVEIS BINÁRIAS
2.1. GENERALIDADES
Con o me oi e e ido no pon o 1, as a iá eis biná ias são mui o ú eis pa a e-
p esen a si uações dico ómicas, podendo desempenha dois papéis dis in os: (i) como
a iá eis p incipais ou de decisão (decisões do ipo aze ou não aze , cons ui ou não
cons ui , e c.); (ii) como a iá eis auxilia es, sendo u ilizadas pa a exp imi ce as
condições.
As si uações em que as a iá eis biná ias são u ilizadas como a iá eis de decisão
são ap esen adas no pon o 3. Nes e pon o e emos a sua u ilização pa a exp imi
di e sas condições, ais como es ições mu uamen e exclusi as, unções com á ios
alo es possí eis, es ições condicionadas, ep esen ação de cus os ixos, e c.
2.2. RESTRIÇÕES MUTUAMENTE EXCLUSIVAS
A si uação no mal de qualque p oblema de PI ou de PLI é a de as es ições se em
sa is ei as simul aneamen e (daí ala -se no sis ema de es ições, a ando-se de um
sis ema de (in)equações simul âneas).
Pode acon ece , con udo, que haja duas es ições mu uamen e exclusi as, ou seja,
das duas apenas uma em de se espei ada. Exis e aqui uma dico omia (uma es ição
ou a ou a), que pode se exp essa po ecu so a uma a iá el biná ia. Vejamos o
seguin e exemplo pa a duas es ições do ipo ≤:
De inindo a a iá el biná ia y∈{0, 1}, e ede inindo as es ições como se segue
(sendo M um núme o ão g ande quan o se quei a), as duas es ições cons a ão do
modelo mas apenas uma das duas se á ga an idamen e espei ada (dependendo do alo
que a a iá el y assumi ).
É ácil deduzi como de e iam se ede inidas as es ições se as mesmas ossem
do ipo ≥. Se uma ou ambas as es ições o em do ipo = podem as mesmas se desdo-
b adas em duas desigualdades simul âneas (≤ e ≥), aplicando-se en ão os p incípios
enunciados.
3 x1 + 4 x2 ≤ 12
ou5 x1 + 2 x2 ≤ 10

3
2.3. RESPEITAR k DE m RESTRIÇÕES
No caso an e io p e endia-se espei a uma de duas es ições (podendo as es-
ições se do ipo ≤ ou do ipo ≥). Uma ex ensão dessa si uação consis e em e de es-
pei a k de m es ições (k<m). Nes e caso de em-se de ini an as a iá eis biná ias
quan as as es ições, com o seguin e signi icado (pa a o caso das es ições se em do
ipo Gj(x) ≤ 0):
As es ições de em se ede inidas de modo semelhan e ao ap esen ado no pon o
2.2., ou seja,
e pa a ga an i que apenas k es ições êm de se sa is ei as ac escen a-se a condição
km
my
jj−=
∑
=1.
2.4. FUNÇÕES COM N VALORES POSSÍVEIS
Habi ualmen e as es ições apenas êm um alo pa a o e mo independen e. Se
hou e N alo es possí eis pa a o e mo independen e, essa es ição pode se esc i a
com ecu so a N a iá eis biná ias, como se pode e no seguin e exemplo:
De inem-se as a iá eis biná ias yk ais que:
yk
k
N
=
∑=
11, com cada yk ∈ {0, 1}
A es ição se á en ão al e ada pa a ax
ij
jj
∑
= by
ik k
k
N⋅
∑
=1
yj=





0, se es ição j é álida (Gj(x) ≤ 0)
1, se não (Gj(x)
≤
M
→
es ição edundan e)
G1(x) ≤ M y1
G2(x) ≤ M y2
…
Gm(x) ≤ M ym
Res ição j: ax
ij
jj
∑
= bi1 ou bi2 ou … biN
4
2.5. RESTRIÇÕES CONDICIONADAS
Suponhamos que a es ição 1 só se pode e i ica se a es ição 2 se e i ica , ou
seja, es ição 1 ⇒ es ição 2. Es a si uação é acilmen e esol ida se lemb a mos que
uma implicação pode se semp e ep esen ada po uma disjunção,
pelo que [ es ição 1 ⇒ es ição 2] é equi alen e a [não- es ição 1 ou es ição 2].
T a a-se en ão de exp imi es ições mu uamen e exclusi as, con o me oi já is o no
pon o 2.1.
2.6. REPRESENTAÇÃO DE CUSTOS FIXOS
Ou a si uação que pode se exp essa a a és de a iá eis biná ias é a ep esen a-
ção de cus os ixos. Suponhamos que o cus o de p odução de um ce o p odu o em
duas componen es: um cus o ixo (independen e da quan idade p oduzida) e um cus o
a iá el que é p opo cional à quan idade ab icada. T a a-se de uma si uação di e en e
da habi ual, na qual o cus o ixo é inco ido mesmo que não haja p odução; aqui, se não
hou e p odução o cus o é ze o (em inglês é chamado de “ ixed cha ge” pa a o dis ingui
de “ ixed cos ”). Como exemplo podemos conside a a si uação em que o cus o ixo
co esponde ao cus o de p epa ação das máquinas, que não depende da quan idade que
ai se ab icada mas só é inco ido se hou e p odução.
Suponhamos que a quan idade a ab ica é ep esen ada pela a iá el x. De inimos
a a iá el biná ia
pelo que a unção cus o se esc e e á
CT = (CM + CP x) y , ou CT = CM y + CP x
É necessá io ac escen a uma es ição pa a ga an i que quando x > 0 en ão y = 1
e que quando y = 0 en ão x = 0:
x ≤≤ M y, com M mui o g ande
A p óp ia na u eza da unção objec i o az com que se x = 0 en ão y = 0, uma ez
que se p e ende minimiza o cus o.
y=





1, se hou e p odução (x>0)
0, se não hou e p odução (x=0)
=





0, se x = 0
CM + CP x , se x > 0
A⇒⇒ B ⇔ ~A∨∨B
5
2.7. MÁXIMO DE N VARIÁVEIS
O máximo de N a iá eis, Xmax = max {X1, X2, …, XN} pode se exp esso eco -
endo-se a N a iá eis biná ias. De inem-se as a iá eis biná ias yk, k=1,…,N, ais que:
e ac escen a-se a condição
yk
k
N
=
∑=
11, com cada yk ∈ {0, 1}
que ga an e que Xmax apenas assume um alo . As es ições seguin es
(1) Xmax ≥ Xk ∀k=1..N
(2) Xmax ≤ Xk +M (1- yk)
ga an em que Xmax i á igual ao máximo das a iá eis conside adas.
3. ALGUNS PROBLEMAS TÍPICOS DE PI
3.1. PROBLEMA DE AFECTAÇÃO
O P oblema de A ec ação (em inglês, Assignmen P oblem) é conhecido po es e
nome po se a ep esen ação de inúme as si uações em que é necessá io a ec a pessoas
a luga es, a a e as ou a zonas de abalho, máquinas a a e as, e c. Apa ece mui as
ezes como se a asse de um p oblema de PL mas, como e emos, as suas a iá eis de
decisão são biná ias.
Suponhamos que se p e ende a ec a n indi íduos a n a e as, sabendo que a
medida de e iciência de a ec a o indi íduo i à a e a j é cij (que an o pode ep esen a
um luc o como um cus o). P e ende-se de e mina a a ec ação dos indi íduos às a e as
de modo a op imiza a e iciência o al.
As a iá eis de decisão são as seguin es:
yk=





1, se Xk é máximo
0, se Xk não é máximo
Xij=




1, se o indi íduo i o a ec ado à a e a j
0, se o indi íduo i não o a ec ado à a e a j
i=1, .., n j= 1,.., n
6
O modelo de PLI é como se segue :
T a a-se, como se pode e , de um modelo mui o simples e cujo sis ema de es i-
ções em uma es u u a pa icula com ce as p op iedades. Si uações em que o núme o
de indi íduos é di e en e do núme o de a e as podem ambém se ep esen adas.
Um p oblema que seja ep esen ado po um modelo com es a es u u a chama-se
p oblema de a ec ação, independen emen e da si uação que es i e a se conside ada.
Con o me e emos mais adian e, os p oblemas de a ec ação dispõem de um mé odo de
esolução p óp io g aças à sua es u u a especial.
3.2. PROBLEMA DO CAIXEIRO VIAJANTE
O P oblema do Caixei o Viajan e (em inglês, T a eling Salesman P oblem) é ou o
ipo de p oblema que pode se ep esen ado po um modelo de PLI. Es e p oblema é
acilmen e is o numa ede, em que as cidades co espondem aos nós ou é ices e os
a cos ep esen am as ligações en e as cidades. Consis e em encon a um ci cui o que
liga odas as cidades, ou seja, um conjun o de a cos que, pa indo de um de e minado
é ice, passa po odos os ou os uma e uma só ez e e mina no é ice de pa ida.
Conhecendo-se a dis ância ou o cus o en e cada pa de cidades ( é ices), p e ende-se
de e mina o ci cui o óp imo.
As a iá eis de decisão são as seguin es:
O modelo de PLI é como se segue:
Xij=




1, se a cidade j é isi ada imedia amen e após a cidade i
0, se a cidade j não é isi ada imedia amen e após a cidade i
i=1, .., n j= 1,.., n
min ou max cX
ij ij
ji ⋅
∑∑




 → op imiza a e iciência o al
suj. a:
1. cada indi íduo só pode es a a ec ado a uma a e a:
Xij
j
∑
=∀=
1, i: i 1,2,3,4
2. cada a e a só de e se desempenhada po um indi íduo:
Xij
ij
∑
=∀1, j: =A, B, C, D
Xij∈{0, 1}
13
2ª) A solução óp ima do p oblema de PL após o a edondamen o pode não se
admissí el pa a o modelo de PLI (embo a o modelo de PLI enha soluções).
Conside e-se o seguin e modelo cuja ep esen ação g á ica se encon a na
Figu a 4.1:
3ª) A solução in ei a ( esul an e do a edondamen o da solução óp ima do p o-
blema de PL) pode es a ela i amen e “a as ada” da solução óp ima do
p oblema de PLI (sendo o “a as amen o” medido em e mos da unção objec-
i o). Conside e-se o seguin e modelo cuja ep esen ação g á ica es á na
Figu a 4.2:
max F = 11 x1 + 10 x2
suj. a: 2.75 x1+10 x2 ≤ 21
- 2 x1 + 6 x2 ≥ 3
x1, x2 ≥ 0 e in ei as
max F = 35 x1 + 70 x2
suj. a: 3 x1 + 7 x2 ≤ 17
14 x1 -11 x2 ≤ 18.2
x1, x2 ≥ 0 e in ei as
1230 x1
x2
0
1
2
sen ido do
c escimen o de
F(x1, x2)
Solução óp ima do
p oblema de PL
(2.63, 1.38)(2.63, 1.38)
Figu a 4.1 - Nenhuma das qua o soluções ob idas po a edondamen o é possí el

14
Conclui-se assim pela necessidade de mé odos que examinem apenas uma pa e do
conjun o de soluções admissí eis e que ap o ei em as an agens do algo i mo Simplex.
Exac amen e com es as ca ac e ís icas, exis em dois mé odos: o Mé odo dos Planos de
Co es (Cu ing Planes) e o Mé odo de Pa ição e A aliação Sucessi as (B anch and
Bound). De ac o, ambos u ilizam o algo i mo Simplex pa a chega à solução óp ima de
p oblemas de PL cuja egião admissí el ai sendo sucessi amen e eduzida a é se
alcança a solução do p oblema de PLI. Es es mé odos são ge ais, pois podem se
aplicados a qualque modelo de PLI.
Exis em ambém mé odos especí icos, que apenas pe mi em esol e o ipo de
p oblemas pa a os quais o am concebidos. É o caso, po exemplo, do Mé odo Húnga o
pa a o P oblema de A ec ação. Es e mé odo i a pa ido da es u u a especial do
p oblema, sendo po isso mais e icien e que os mé odos ge ais.
Finalmen e, exis em ambém mé odos heu ís icos pa a ce os ipos de p oblemas.
Es es algo i mos são bas an e e icien es pa a ce os p oblemas mui o di íceis de esol e ,
embo a a solução po eles encon ada não seja ga an idamen e óp ima. Exis em, po
exemplo, á ias heu ís icas pa a o P oblema do Caixei o Viajan e. Hoje em dia, g aças
aos a anços da ecnologia in o má ica e a um con inuado es o ço de melho ia de
e iciência dos algo i mos, é possí el esol e de o ma óp ima p oblemas cada ez
maio es.
4.2. MÉTODO DOS PLANOS DE CORTE
O mé odo dos Planos de Co e (Cu ing Planes, em inglês) oi o p imei o mé odo a
se desen ol ido e de e-se a Gomo y (1958). Consis e em in oduzi sucessi amen e
no as es ições na elaxação linea do PLI, es ições essas que co am o conjun o das
soluções possí eis eliminando algumas delas e a p óp ia solução óp ima do PL (po isso
se chamam planos de co e), sem con udo elimina qualque solução in ei a.
sen ido do c escimen o
de F(x1, x2)
Solução
a edondada
F(2, 1)=140F(2, 1)=140
Solução óp ima do
p oblema de PL
F(2.4, 1.4)=182F(2.4, 1.4)=182
Figu a 4.2 - A solução in ei a (ob ida po a edondamen o) não é a solução óp ima do p oblema de PLI
1230 x1
x2
0
1
2
SOLUÇÃO INTEIRA ÓPTIMA
F(1, 2)=175F(1, 2)=175
15
Conside emos o seguin e exemplo. An ónio, p op ie á io da emp esa de b inque-
dos “Toys ’ ’ Tony”, decidiu c ia uma secção de b inquedos adicionais de madei a,
começando po apenas dois ipos de b inquedos: pequenos ca alos de baloiço (luc o
uni á io de 2400$) e comboios an igos (luc o uni á io de 1500$). Cada ca alo eque
uma ho a de abalho e 9 m2 de madei a, enquan o que cada comboio eque uma ho a
de abalho e 5 m2 de madei a. Supondo que es ão disponí eis 6 ho as de abalho e 45
m2 de madei a, que quan idades ab ica de o ma a maximiza o luc o?
Va iá eis de Decisão:
x1= núme o de ca alos de baloiço ab icados
x2= núme o de comboios ab icados
O p imei o passo consis e na esolução da elaxação linea do PLI, que co es-
ponde ao quad o simplex da Figu a 4.3 e à ep esen ação g á ica da Figu a 4.4:
Figu a 4.4 - Resolução da elaxação linea do p oblema de PLI
Solução óp ima do
p oblema de PL
F(3.75, 2.25)=12375
x2
5
3
2
1
6
4
7
9
8
6
5
4
3
2
1
x1
x1x2 1 2
x110-1.25 0.25 3.75
x20 1 2.25 -0.25 2.25
-F 0 0 375 0.75 -12375
Figu a 4.3 - Quad o SIMPLEX óp imo pa a a elaxação linea do p oblema de PLI
O p oblema (de PI) se á:
max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1, x2 ≥ 0 e in ei os
16
Como na solução óp ima da elaxação linea os alo es das a iá eis não são in-
ei os, há que ge a um plano de co e. Pa a al, bas a conside a a es ição do quad o
simplex óp imo da elaxação linea cujo e mo independen e enha a pa e accioná ia
mais p óxima de 0.5, e eesc e e essa es ição sepa ando a pa e in ei a da pa e ac-
cioná ia. No exemplo conside ado, qualque das es ições pode se conside ada, uma
ez que as pa es accioná ias de 3.75 e de 2.25 se encon am igualmen e p óximas de
0.5. Escolhendo a p imei a es ição x1-1.25 1+0.25 2 = 3.75 e eesc e endo-a sob a
o ma [memb o com coe icien es in ei os = memb o com coe icien es accioná ios] ica-
se com x1-2 1-3 = 0.75-0.75 1-0.25 2. O no o plano de co e a ac escen a ao modelo
aduz a es ição memb o com coe icien es accioná ios ≤ 0 , ou seja,
0.75 - 0.75 1 - 0.25 2 ≤≤ 0
3 x1 +2 x2 ≤≤15
O no o modelo de PL a esol e é en ão
max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
3 x1 +2 x2 ≤≤15 (plano de co e)
x1, x2 ≥ 0
Como se pode analisa na Figu a 4.5 a no a es ição “co ou” o conjun o das
soluções possí eis, eliminando a solução óp ima da elaxação linea , mas não eliminando
qualque solução in ei a. Como a solução óp ima des e no o modelo de PL é in ei a, ela
é a solução óp ima do PLI. Se a solução encon ada ainda não osse in ei a, ge a -se-ia
no o co e, e assim sucessi amen e.
⇓
⇑
(pela de inição das a iá eis de olga,
1
=6-x
1
-x
2
e
2
=45-9x
1
-5x
2
)
Figu a 4.5 - Aplicação do plano de co e: a esolução do no o p oblema de PL conduz à solução óp ima
do p oblema de PLI inicial (5, 0)
x2
5
3
2
1
6
4
7
9
8
6
5
4
3
2
1
x1
Solução óp ima do no o
p oblema
F(5, 0)=12000
Solução óp ima do
p oblema de PL
F(3.75, 2.25)=12375
17
Qualque co e ge ado po es e mé odo em, en ão, duas p op iedades:
1ª) Qualque solução possí el do PLI sa is az o co e.
2ª) A solução óp ima da elaxação linea não sa is az o co e.
Demons a-se (Gomo y, 1958) que se a inge a solução óp ima do PLI após um
núme o ini o de co es. Apesa des a p op iedade o mé odo dos planos de co e caiu
em desuso, sendo mui o pouco u ilizado de ido ao abalho compu acional en ol ido na
esolução de p oblemas de g andes dimensões. Embo a o núme o de co es seja ini o, o
seu núme o pode se mui o ele ado (cen enas ou milha es); de cada ez que se ge a um
no o co e ac escen a-se uma no a es ição ao modelo o iginal, o que signi ica que a
complexidade desse modelo é semp e c escen e, podendo o abalho compu acional i a
o na -se p oibi i o apesa de se dispo de um algo i mo de esolução mui o e icien e
como é o simplex. Ou a des an agem des e mé odo (quando compa ado com o mé odo
de pa ição e a aliação sucessi as) é que se se in e ompe o mé odo an es de ele chega
ao im não se dispõe de qualque solução in ei a, ainda que não seja óp ima.
4.3. MÉTODO DE PARTIÇÃO E AVALIAÇÃO SUCESSIVAS
O mé odo “B anch and Bound” (li e almen e, mé odo de ami icação e limi ação)
consis e na pa ição ( ami icação) sucessi a do conjun o de soluções possí eis do
p oblema de PLI em subconjun os e na limi ação (a aliação) do alo óp imo da unção
objec i o (limi e in e io se se a a de maximização, ou supe io se se a a de mini-
mização), de modo a exclui os subconjun os que não con enham a solução óp ima.
Pa indo da cons a ação de que
se, na solução óp ima da elaxação linea dum p oblema de PLI, as
a iá eis omam alo es in ei os, en ão essa solução é a solução
óp ima do PLI,
começa-se po esol e a elaxação linea do PLI inicial: se as a iá eis que no p oblema
de PLI são in ei as omam, na solução óp ima do PL, alo es in ei os, en ão oi
encon ada a solução óp ima do PLI; caso con á io, di ide-se o p oblema de PL em
dois, a a és da in odução de es ições adicionais que azem a pa ição do conjun o das
soluções possí eis. Vão-se en ão esol endo sucessi os p oblemas de PL, es abele-
cendo-se limi es pa a o alo óp imo da unção objec i o e, assim, eliminando di e sos
sub-conjun os, a é se alcança a solução óp ima do PLI.
Ilus a-se seguidamen e es e mé odo e omando o exemplo já usado an e io men e,
no qual An ónio, p op ie á io da emp esa de b inquedos “Toys ’ ’ Tony”, decidia c ia
uma secção de b inquedos adicionais de madei a, começando po pequenos ca alos de
baloiço e comboios an igos. As a iá eis e o modelo, a ás de inidos, e am os seguin es:
Va iá eis de Decisão:
x1= núme o de ca alos de baloiço ab icados
x2= núme o de comboios ab icados
18
O p imei o passo consis e na esolução da elaxação linea do PLI, o que oi ei o
g a icamen e na Figu a 4.6:
Desde já se sabe que o alo óp imo da unção objec i o não pode excede 12375.
Como na solução óp ima des e p oblema x1 e x2 não são in ei as, há a necessidade de
e ec ua a sua pa ição, dando o igem a dois no os subp oblemas (A e B), pela in o-
dução de no as es ições de eliminação de soluções não-in ei as: x1 ≤ 3 e x1 ≥ 4 (Figu a
4.7). Pode -se-ia escolhe aze a pa ição segundo a a iá el x2.
A: max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1≤3
x1, x2 ≥ 0
B: max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1≥4
x1, x2 ≥ 0
x2
5321 64
7
9
8
6
5
4
3
2
1
x1
Solução óp ima do
p oblema de PL
F(3.75, 2.25)=12375
Figu a 4.6 - Resolução da elaxação linea do p oblema PLI
max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1, x2 ≥ 0 e in ei os

19
A solução óp ima do subp oblema A é in ei a, o que signi ica que se encon ou
uma solução in ei a cujo alo da unção objec i o é 11700. O alo óp imo da unção
objec i o es a á comp eendido en e es es dois limi es, 11700 ≤ F ≤ 12375. Como a
solução óp ima do subp oblema B não é in ei a e o alo da unção objec i o é 12300
(>11700), es e subp oblema pode con e uma solução in ei a melho que a do subp o-
blema A; logo, é necessá io e ec ua a sua pa ição, dando o igem aos subp oblemas B1 e
B2, pela in odução das es ições x2 ≥ 2 e x2 ≤ 1 (Figu a 4.8).
Os no os subp oblemas são da o ma:
B1:max F= 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1≥4
x2≥2
x1, x2 ≥ 0
B2:max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1≥4
x2≤1
x1, x2 ≥ 0
Figu a 4.7 - P imei a pa ição: in oduzindo, no p oblema de PL inicial, a es ição x1 ≤ 3 ob ém-se o
subp oblema A(cuja solução óp ima é in ei a) e in oduzindo a es ição x1 ≥ 4 ob ém-se o
subp oblema B (cuja solução óp ima ainda não é in ei a, pelo que se em de con inua a
pa ição).
x2
5321 64
7
9
8
6
5
4
3
2
1
x1
A
B
Solução óp ima do
subp oblema B
F(4, 1.8)=12300
Solução óp ima do
subp oblema A
F(3, 3)=11700
20
O subp oblema B1 não em soluções possí eis, sendo po isso excluído. O sub-
p oblema B2, pelas mesmas azões do subp oblema B, é objec o de pa ição e dá o igem
aos subp oblemas B21 e B22, pela in odução das es ições x1 ≤ 4 e x1 ≥ 5 (Figu a 4.9):
B21:max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1 ≥ 4
x2 ≤ 1
x1 ≤ 4
x1, x2 ≥ 0
B22:max F = 2400 x1 +1500 x2
suj. a: x1 + x2 ≤ 6 (ho as de abalho)
9x1 + 5 x2 ≤ 45 (madei a)
x1 ≥ 4
x2 ≤ 1
x1 ≥ 5
x1, x2 ≥ 0
x1 = 4
x1 ≥ 5
Figu a 4.8 - Segunda pa ição: in oduzindo, no subp oblema B, a es ição x2 ≥ 2 icamos com o sub-
p oblema B1(solução impossí el) e in oduzindo a es ição x2 ≤ 1 icamos com o
subp oblema B2 (solução ainda não é in ei a, pelo que se em de con inua a pa ição).
x2
5321 64
7
9
8
6
5
4
3
2
1
x1
A
B2
Solução óp ima do
subp oblema B2
F(4.4, 1)=12167
Solução óp ima do
subp oblema A
F(3, 3)=11700
21
Que o subp oblema B21 que o subp oblema B22 êm soluções in ei as. O alo
óp imo da unção objec i o do subp oblema B21 é 11100, meno que 11700, ou seja, pio
do que a solução de que já dispúnhamos. O alo óp imo da unção objec i o do
subp oblema B22 é 12000, logo ac ualizamos os limi es e e emos 12000 ≤ F ≤ 12000. A
sequência o al das pa ições é pa icula men e e iden e no seguin e diag ama, es-
u u ado em o ma de á o e (Figu a 4.10):
(x1, x2)= (3.75, 2.25)
F = 12375
BA
B2
B1
B22
B21
x1≤ 3
x1≥≥ 4
x2≥≥ 2
x2≤ 1
x1≤ 4
x1≥≥ 5
(x1, x2)= (4, 1.8)
F
B
= 12300
(x1, x2)= (3, 3)
F
A
= 11700
(x1, x2)= (4.44, 1)
F
B2
= 12167
Subp oblema
impossí el
(x1, x2)= (5, 0)
F
B22
= 12000
(x1, x2)= (4, 1)
F
B21
= 11100
SOLUÇÃO ÓPTIMA
Figu a 4.10 - Á o e inal do mé odo “B anch and Bound” pa a o exemplo ap esen ado
Figu a 4.9 - Te cei a pa ição: in oduzindo, no subp oblema B2, a es ição x1 ≥ 5 icamos com o sub-
p oblema B21 e in oduzindo a es ição x1 ≤ 4 icamos com o subp oblema B22: odas as
soluções são já in ei as, não ha endo a necessidade de e ec ua mais nenhuma pa ição.
A solução óp ima do p oblema de PLI é (x1, x2) = (5, 0).
x2
5321 64
7
9
8
6
5
4
3
2
1
x1
ASolução óp ima do
subp oblema B22
F(5, 0)=12000
Solução óp ima do
subp oblema A
F(3, 3)=11700
Solução óp ima do
subp oblema B21
F(4, 1)=11100
22
À medida que se ai “descendo” na á o e da Figu a 4.10 ão-se ac ualizando os
limi es in e io e supe io ao alo óp imo da unção objec i o (F*). No nó inicial ( aiz
da á o e), 0 ≤ F* ≤ 12375. Ao ní el dos subp oblemas A e B, 11700 ≤ F* ≤ 12300.
No ní el imedia amen e in e io , 11700 ≤ F* ≤ 12167. Po im, no qua o e úl imo ní el,
12000 ≤ F* ≤ 12000. Podemos en ão conclui que (x1, x2) = (5, 0), F* = 12000 é a
solução óp ima, não azendo sen ido e ec ua qualque no a pa ição.
Vemos assim que:
(1) É e ec uada a pa ição de um subp oblema em cuja solução óp ima exis a pelo
menos uma a iá el que, sendo uma a iá el in ei a no PLI inicial, assuma
alo es não-in ei os, se esse subp oblema pude con e uma solução in ei a
melho do que a já exis en e.
(2) São logo eliminados os subp oblemas que não enham soluções possí eis ou
que não possam con e uma solução possí el melho do que a já exis en e.
Pa a além de se , de um modo ge al, menos abalhoso esol e um modelo de PLI
a a és des e mé odo do que a a és do mé odo dos planos de co e, ele ap esen a a
an agem de se possí el in e ompe o mé odo an es de encon a a solução óp ima e de
dispo de uma solução in ei a, em elação à qual se pode e uma ideia de quão p óxima
es a á da solução óp ima g aças aos limi es que se ão de e minando.
5. BIBLIOGRAFIA
Ga inkel, Robe S. and Geo ge L. Nemhause (1972), In ege P og amming, John
Wiley & Sons, Inc.
Hadley, Geo ge (1974), Linea P og amming, Eigh h P in ing, Addison-Wesley.
Hadley, Geo ge (1972), Nonlinea and Dynamic P og amming, Second P in ing,
Addison-Wesley.
Hillie , G. and J. Liebe man (1995), In oduc ion o Ope a ions Resea ch, Six h Edi ion,
McG aw-Hill.
Ramalhe e, Manuel, Jo ge Gue ei o e Alípio Magalhães (1984), P og amação Linea ,
Vol. I e Vol. II, Edi o a McG aw-Hill de Po ugal.
Wins on, Wayne L. (1994), Ope a ions Resea ch – Applica ions and Algo i hms, Thi d
Edi ion, Duxbu y P ess.
Wu, Nesa and Richa d Coppins (1981), Linea P og amming and Ex ensions, McG aw-
Hill.