Programação Linear Inteira

Prévia do material em texto

Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Programação Linear Inteira
Prof. Fernando Augusto Silva Marins
Departamento de Produção
Faculdade de Engenharia – Campus de Guaratinguetá
UNESP
www.feg.unesp.br/~fmarins
fmarins@feg.unesp.br
1
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Introdução
Problemas de Programação Linear onde todas ou algumas variáveis 
devem ter valores inteiros - Programação Linear Inteira - PLI.
Classificação:
(a) PLI puro (só variáveis inteiras) ou PLI misto (variáveis inteiras e 
variáveis xi  0).
(b) Com variáveis inteiras binárias (0 ou 1) ou com variáveis inteiras 
em geral (0, 1, 2, 3, 4,...).
2
Métodos:
(a) Arredondamento ou truncagem dos valores não inteiros: podem 
produzir soluções distantes da ótima, ou mesmo que não sejam 
viáveis (ver exemplo adiante).
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo-Arredondamento
Arredondamento gerando solução inviável. 
Seja o modelo de PLI:
Resolução gráfica: PL Relaxado = PLI sem integralidade das soluções
3






Inteiros0,X,X
(2) 3/2X-2X
(1) 3/2X+X-
:as. 2X+3X= Z
21
21
21
21Max
Arredondando o valor 
ótimo = (3; 4,5) obtido para 
o problema de PL relaxado
 dois valores de soluções 
inviáveis, (3; 4) ou (3; 5) 
para o PLI.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Introdução
(b) Métodos de otimização da PLI: têm o inconveniente de o tempo 
de resolução crescer drasticamente com o aumento do número de 
variáveis inteiras do modelo.
4
Aplicações:
(1) Problema de investimento.
(2) Problemas com custo fixo.
(3) Problema de alocação de armazéns.
(4) Problemas de sequenciamento de tarefas.
(5) Roteamento de veículos, linearização de função objetivo com 
produto de variáveis, problema do caixeiro viajante, problemas de 
“matching”, de “covering”, de “partitioning”, e de “packing”).
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Aplicações da PLI
- Formulações de PLI para problemas de decisão tipo “sim ou não”, 
“ou – ou”, “há restrições de que k em n tenham que se manter”, “há
funções com n valores possíveis”, “há custo fixo de preparação”. 
5






nãofor iDecisãoase,0
simfor iDecisãoase,1
- Exemplo de decisões “sim ou não”: executar o projeto?, fazer o 
investimento?, instalar a empresa naquela cidade?
Solução usar variável binária Yi=
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Aplicações da PLI
Grupos de alternativas mutuamente exclusivas – somente uma 
decisão no grupo pode ser “sim”. fazer:
-Se exatamente uma decisão no grupo tiver que ser “sim”.
-Se quando muito uma decisão no grupo tiver que ser “sim”
6
1
i
iY 
1
i
iY 
JYKY 
Decisões contingentes – dependem de decisões anteriores. exemplo: 
decisão k é contingente na decisão j, se a decisão k puder ser 
“sim”somente se a decisão j for “sim”. fazer:
ou seja, quando YJ = 1 dá escolha livre para YK, mas se YJ
= 0 força YK = 0.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo
• Uma indústria quer se expandir, construindo nova fábrica ou em 
Los Angeles ou em São Francisco. Também será considerada a 
construção de um novo depósito na cidade que for selecionada 
para receber a nova fábrica. O valor presente líquido de cada 
alternativa está na tabela abaixo. A última coluna dá o capital 
requerido para os investimentos, sendo o capital total disponível 
$25 milhões. Achar a combinação viável de alternativas que 
maximize o valor presente líquido total.
7
IDENTIFICAÇÃO DA 
DECISÃO
QUESTÃO
“SIM OU NÃO”
VARIÁVEL
DE
DECISÃO
VALOR PRESENTE 
LÍQUIDO
CAPITAL REQUERIDO
1 FÁBRICA EM L.A.? Y1 7.000.000,00 20.000.000,00
2 FÁBRICA EM S.F.? Y2 5.000.000,00 15.000.000,00
3 DEPÓSITO EM L.A.? Y3 4.000.000,00 12.000.000,00
4 DEPÓSITO EM S.F.? Y4 3.000.000,00 10.000.000,00
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Resolução do Exemplo
Variável de Decisão: i= (1,2,3, 4)
Y1 + Y2 = 1 – alternativas mutuamente exclusivas
- Alternativas contingentes nas decisões 1 e 2.
8






Nãofor iDecisãoase,0
Simfor iDecisãoase,1
02Y4Y
01Y3Y


Modelo completo: Max Z = 7Y1 + 5Y2 + 4Y3 + 3Y4
sujeito a: 20Y1 + 15Y2 + 12Y3 + 10Y4  25
Y1 + Y2 = 1
-Y1 + Y3  0
-Y2 + Y4  0
Yi  {0,1}, inteiros para i = 1,2,3,4.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Aplicações da PLI
Restrições “ou - ou”: escolher entre 2 recursos qual usar para um 
dado propósito, de modo que seja necessário que uma das duas 
restrições de disponibilidade de recursos se mantenha válida.
Exemplo: seja M = número suficientemente grande.
9
 


















1ou 0Y
.MY-1164XX
Y.M182X3X
164XXou 
182X3Xou 
21
21
21
21
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Aplicações da PLI
Generalizando: caso em que “há restrições de que K em N 
tenham que se manter” – dado um conjunto de N restrições 
possíveis, apenas é requerido que K destas restrições devam ser 
válidas (no slide anterior tinha-se K = 1 e N = 2).
Sejam as restrições:
10
 
 
 
 
 
 
0,1Y K,NY com 
 
MYbX,...,X,XF
.................................................
MYbX,...,X,XF
MYbX,...,X,XF
X,...,X,XF
......................................
X,...,X,XF
X,...,X,XF
i
N
1i
i
NNn21N
22n212
11n211
n21N
2n212
1n211






























Nb
b
b
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Aplicações da PLI
Há funções com N valores possíveis – situação em que é
requerido que uma dada função assuma qualquer um de N 
valores dados:
    
0,1Y1,Y com 
YbX,...,X,XFbou ....bou bX,...,X,XF
i
N
1i
i
N
1i
iin21N21n21






Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Aplicações da PLI
Há custo fixo de preparação – custo total é a soma de um custo 
variável relacionado ao nível da atividade e o custo de preparação 
requerido para iniciar a atividade. 
Exemplo: Min Z, com :
Solução:
12
     
 
0X se 0,
0 X se ,XCK
XF onde
 ,XF...XFXFZ
j
jjjj
jj
nn2211










 
n...,2,1,j paraM.YX e
0X se0,
0X se,1
Y,YKXCZ
 jj
j
j
j
n
1j
jjjj









 

Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Investimento
• Uma companhia está planejando o seu investimento em n 
projetos para os próximos t períodos. No período i o capital 
disponível = Bi e cada projeto requer um certo investimento em 
cada período desde que ele tenha sido selecionado. Neste caso, 
seja aij o valor do investimento requerido pelo projeto j no 
período i. O valor do projeto é medido em termos dos fluxos de 
caixa em cada período descontada a inflação = valor presente 
líquido (VPL). Seja vj o VPL do projeto j. O problema é
selecionar os projetos que receberão investimento deforma a 
maximizar o valor total (VPL). 
13
Variáveis de decisão: xj = 


contráriocaso0,
oselecionadfor jprojetoose,1
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Investimento
Função objetivo: Max
Restrições:
14
N1,...,=jcomBinária,VariávelX
T,...1,=i para,BX
j
N
1=j
ij ijA
v j Xj
j = 1
N

Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Custo fixo
• Considere um problema de planejamento da produção de n 
produtos onde para o produto j há um custo de preparação kj, 
independente da quantidade produzida, e um custo variável cj por 
unidade produzida. Deseja-se maximizar o retorno líquido da 
venda dos produtos. Admita que toda unidade do produto j requer
aij unidades do recurso i e há m recursos disponíveis. Sabe-se que 
o produto j, com potencial de vendas dj, é vendido por $ pj por 
unidade, e não mais de bi unidades do recurso i estão disponíveis 
(i = 1, ..., m).
• Variáveis de decisão:
15
jprodutodoproduzidaQuantidade=
contráriocaso0,
produzidofor jprodutoose1,
=
j
j
X



Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Custo fixo
Função objetivo: Max Z=
Restrições:
16
 pj X - K + C Xj j j j j
j = 1
N
j = 1
N

j. todopara1,ou 0= e 0X
N...,1,=ipara d
M...,1,=iparabX
jj
jj
1
ij






j
N
j
ij
X
A
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo – Expansão de Atividades
Uma empresa está planejando expandir suas atividades abrindo dois 
novos armazéns, sendo que há três locais sob estudo para a 
instalação destes armazéns (ver figura adiante). quatro clientes 
devem ter atendidas suas demandas: d1, d2, d3, e d4. Admita que 
quaisquer dois locais são suficientes para atender toda a demanda 
existente, mas o local 1 só pode atender clientes 1, 2 e 4; o local 3 
pode atender os clientes 2, 3 e 4; enquanto o local 2 pode atender 
todos os clientes. O custo unitário de transporte do local i ao cliente 
j é dado por cij. Para cada local as informações são as seguintes:
17
LOCAL CAPACIDADE INVESTIMENTO INICIAL CUSTO UNITARIO 
OPERAÇÃO
1 A1 $ K1 $ P1
2 A2 $ K2 $ P2
3 A3 $ K3 $ P3
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo – Expansão de Atividades
Deseja-se selecionar os locais apropriados para instalar os armazéns 
que minimize o custo total de investimento, operação e 
transporte.
Variáveis de decisão:
18
j.ClienteaoilocaldoenviadaQuantidade=
contráriocaso0,
escolhidofor ilocalose1,
=
ij
i
X



Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo – Expansão de Atividades
Função objetivo:
Restrições:
19
Minimizar Z = K1 1 + P1 (X11 + X12 + X14 ) + C11 X11 + C12 X12 + C14 X14 + K22 + P2(X21
+ X22 + X23 + X24) + C21X21 + C22X 22+ C23X23 + C24 X24+ + K3 3 + P3 (X32 + X33 + X34 ) 
+ C32 X32 + C33 X33 + C34 X34






















j)(i, todopara0,
32,1,=iparainteiro e 10
D=X+X+X
D=X+X
D=X+X+X
D=X+X
2 ++
A X+X+X
A X+X+X+X
A X+ X+X
ii
4342414
33323
2322212
12111
321
33343332
2224232221
11141211
ijX





Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Sequenciamento de Tarefas
Três produtos A, B e C serão produzidos usando quatro máquinas. a
sequência tecnológica e os tempos de processamento (Ai, Bj, Ck) 
são mostrados abaixo:
20
Cada máquina pode processar um produto de cada vez. Cada produto 
requer um conjunto diferente de ferramentas, de modo que cada 
máquina termina o processamento de um produto antes de iniciar o 
processamento de um outro produto.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Sequenciamento de Tarefas
Deseja-se que o tempo para terminar o produto B não seja maior que 
d horas após o início das atividades de processamento. O 
problema é determinar a sequência na qual os vários produtos 
devem ser processados nas máquinas de modo que se complete a 
fabricação de todos os produtos no menor tempo possível. 
21
Variáveis de decisão:
XAj é o tempo (em horas), a partir do início dos trabalhos nas 
máquinas, quando o processamento do produto A é iniciado na 
máquina j, para j = 1, 3, 4. 
Analogamente, XBj para j = 1, 2, 4 e XCj para j = 2, 3.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Sequenciamento de Tarefas
Restrições pela seqüência tecnológica para produto A:
Similarmente tem-se para os produtos B e C:
22
XA1 + A1  XA3 (1)
XA3 + A3  XA4 (2)
XB1 + B1  XB2 (3)
XB2 + B2  XB4 (4)
XC2 + C2  XC3 (5)
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Restrições de não interferência nas máquinas: 
(não são lineares)
Máquina 1 pode trabalhar no produto A ou no B, ou vice versa, em 
qualquer momento: 
Usando uma variável auxiliar binária inteira 0  1  1, e um 
número M suficientemente grande, pode-se linearizar a restrição 
não-linear do tipo “ou” acima: 
Observe que se 1 = 0  A precede B, e 
se 1 = 1  B precede A
23
xA1 + A1  xB1 ou xB1 + B1  xA1.
xA1 + A1 - xb1 M 1 (6) e 
xB1 + B1 - xa1  M (1 - 1) (7). 
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Restrições de não interferência nas máquinas:
Analogamente tem-se para as outras máquinas e produtos:
XB2 + B2 - XC2 M 2 (8) 
XC2 + C2 - XB2  M (1 - 2) (9)
XA3 + A3 - XC3 M 3 (10) 
XC3 + C3 - XA3  M (1 - 3) (11)
XA4 + A4 - XB4 M 4 (12) 
XB4 + B4 - XA4  M (1 - 4) (13)
0  2  1, 0  3  1, 0  4  1, inteiros.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Sequenciamento de Tarefas
Restrição adicional de término do produto B:
Função objetivo:
Instante de término das fabricações dos produtos
Produto A é XA4+A4, 
Produto B é XB4+B4, 
Produto C é XC3+C3.
Artifício para linearizar a função objetivo: Acrescentar ao modelo as 
restrições de (15) a (17) 
25
 Função objetivo linear: Min Y.
XB4 + B4  D
 Min Max (XA4 + A4 , XB4 + B4 , XC3 + C3 ).
Y  XA4 + A4 (15)
Y  XB4 + B4 (16)
Y  XC3 + C3 (17)
Observe-se que esta função objetivo não é linear.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Sequenciamento de Tarefas
• Modelo Final:
26
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Orçamento
Deseja-se investir $14.000. Foram identificadas 4 oportunidades de 
investimentos: Investimento 1 requer $5.000 e tem um valor 
presente de $8.000; Investimento 2 requer $7.000 e tem um valor 
presente de $11.000; Investimento 3 requer $4.000 e tem um valor
presente de $6.000, e Investimento 4 requer $3.000 e tem um valor 
presente de $4.000. Em quais investimentos deve-se aplicar o 
capital disponível de modo a maximizar o valor presente total?
Modelo
Variáveis de Decisão: 
Xi = 1, se o investimento i for escolhido 
Xi = 0, caso contrário.
Max Z = 8X1 + 11X2 + 6X3 + 4X4
Sujeito a: 5X1 + 7X2 + 4X3 + 3X4  14, Xj  {0,1}
27
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Orçamento
Solução ignorando as restrições de integralidade: 
X1 = 1, X2 = 1, X3 = 0,5, X4 = 0, Z = $22.000
Arredondando: X3 = 0 e Z = $19.000
Solução ótima inteira: X1 = 0, X2 = X3 = X4 = 1 e Z = $21.000.
Suponha que hárestrições adicionais: 
Pode-se investir em apenas 2 negócios: X1 + X2 + X3 + X4  2;
Se investir no negócio 2, deve-se investir no 4 também: X2 – X4  0;
Se investir no negócio 1, não pode-se investir no 3: X1+ X3  1.
28
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Multiperíodo
Deseja-se investir $14.000, $12.000 e $15.000 em cada mês do 
próximo trimestre. Foram identificadas 4 oportunidades de 
investimento: Investimento 1 requer $5.000, $8.000 e $2.000 no 
mês 1, 2 e 3, respectivamente, e tem um valor presente de $8.000; 
Investimento 2 requer $7.000 no mês 1 e $10.000 no mês 3, tendo 
um valor presente de $11.000; Investimento 3 requer $4.000 no 
período 2 e $6.000 no período 3, tendo um valor presente de 
$6.000; Investimento 4 requer $3.000, $4.000 e $5.000, tendo 
valor presente de $4.000. Como realizar o investimento?
Variável de decisão:
29






contrário caso0,
i projeto no investir se1,
jX
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Multiperíodo
Max Z = 8X1 + 11X2 + 6X3 + 4X4
Sujeito a: 5X1 + 7X2 + 3X4  14
8X1 + 4X3 + 4X4  12
2X1 + 10X2 + 6X3 + 4X4  15
Xj  {0, 1}
30
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo – Problema da Mochila
Um estudante dispõe de uma mochila com capacidade para 14 kg e 
tem quatro itens para colocar nela, com pesos e valores 
(utilidade) diferenciados: Item 1 – peso de 5 kg e valor de 8; Item 
2 – peso 7 e valor 11, Item 3 – peso 4 e valor 6, Item 4 – peso 3 e 
valor 4. 
Deseja maximizar a soma dos valores dos itens colocados na 
mochila.
Modelo: 
Max Z = 8X1 + 11X2 + 6X3 + 4X4
Sujeito a:
5X1 + 7X2 + 4X3 + 3X4  14
Xj  {0, 1}, Inteiros
31
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo – “Grouping problems”
• Há um conjunto de m objetos que devem ser agrupados em 
subconjuntos de modo a otimizar algum objetivo.
32
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - “SET COVERING ”
Uma cidade está revendo a localização de seus Grupamentos de 
Bombeiros - GB. A cidade é dividida em distritos, como no mapa 
abaixo. Um GB pode ser colocado em cada distrito e é capaz de 
atender todo distrito vizinho (adjacente no mapa). O objetivo é
minimizar o número de GB necessários.
33
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - “SET COVERING ”
Modelo: Deseja-se achar o subconjunto de distritos j que cobrem 
toda a cidade.
Variáveis de decisão:
Min Z = X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X10 + X11
Sujeito a:
X1 + X2 + X3 + X4  1; X1 + X2 + X3 + X5  1; 
X1 + X2 + X3 + X4 + X5 + X6  1; X1 + X3 + X4 + X6 + X7  1; 
X2 + X3 + X5 + X6 + X8 + X9  1; 
X3 + X4 + X5 + X6 + X7 + X8  1; X4 + X6 + X7 + X8  1; 
X5 + X6 + X7 + X8 + X9 + X10  1; X5 + X8 + X9 + X10 + X11  1; 
X8 + X9 + X10 + X11  1; X9 + X10 + X11  1; Xj  {0,1}, Inteiros
34






contrário caso0,
i distrito no GB colocar1,
jX
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo “Set packing problem”
Cada elemento do conjunto deve aparecer em no máximo 1 
subconjunto. as restrições serão do tipo “” .
Uma empresa da área financeira tem vários tipos de serviços 
(objetos) que ela deseja agrupar (empacotar) e vender. Um dos 
aspectos de um pacote é que ele deve conter uma combinação de 
objetos cujos valores totalizam no mínimo 1 milhão de dólares. 
Sejam os dados abaixo: (valores em $1.000)
Deseja-se maximizar o número de pacotes que podem ser formados.
35
Objeto A B C D E F G H I
valor 910 870 810 640 550 250 120 95 55
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo “Set packing problem”
Modelo
Variáveis de Decisão: 
AB – Pacote com A e B; 
BGH – Pacote com B, G e H, ...; 
todas variáveis assumindo o valor 1, se o Pacote for escolhido; e 
0, no caso contrário.
Max (Z = número de pacotes selecionados) 
sujeito a: cada objeto aparece em no máximo 1 pacote selecionado.
36
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo “Set packing problem”
Max Z = AB + AC + AD + AE + AF + AG + AH + BC + BD + BE 
+ BF + CD + CE + CF + BGH + BGI + BHI + CGH + DFG + 
DFHI + EFGH
Sujeito a: 
AB + AC + AD + AE + AF + AG + AH  1
BC + BD + BE + BF + BGH + BGI + BHI  1
AC + BC + CD + CE + CF + CGH  1
AD + BD + CD + DE + DFG + DFHI  1
AE + BE + CE + DE + EFGH  1
AF + BF + CF + DFG + DFHI + EFGH  1
AG + BGH + BGI + CGH + DFG + EFGH  1
AH + BGH + BHI + CGH + DFHI + EFGH  1
BGI + BHI + DFHI  1 37
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo “Partitioning problems”
Cada elemento do conjunto deve aparecer em exatamente 1 
subconjunto. as restrições serão do tipo “=“.
“Airline Crew Scheduling”: Ao lado dos custos com combustíveis, 
os custos com pessoal são os maiores para uma Companhia 
Aérea: salário do Comandante = $150.000/ano. 
O uso efetivo das tripulações pode ter um impacto grande nos custos 
totais. Há, contudo, um grande número de restrições sobre como 
as tripulações podem ser escaladas (Regras da FAA e dos 
Sindicatos). 
A American Airline aplicou técnicas de PO para escalar suas 
tripulações. No modelo usado, uma variável binária tipo 0 ou 1, 
foi criada para cada programação de vôo viável para cada 
tripulante da empresa.
38
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo “Partitioning problems”
Assim, uma programação onde uma tripulação sai de Pittsburgh às 
7:15AM na 3a. feira, chega em NY às 8:30, deixa NY às 9:00, 
chega em Atlanta às 11:00, deixa Atlanta às 12:00 e chega em 
Pittsburgh às 2:30 corresponderia à uma variável binária X1. O 
custo de colocar esta variável no valor 1 (ou seja, a tripulação vai 
voar a programação em questão) seria baseado no contrato com o 
Sindicato e outras regras.
Há um número muito grande de variáveis nesse modelo, mas as 
restrições são muito simples. Para cada voo (“leg”) é necessário 
escolher uma programação que inclua este voo, assim as 
restrições seriam do tipo:
X1 + X4 + X55 + X5534 + ...= 1, se as programações 1, 4, 55, 5534 e 
outras incluem o vôo das 7:15AM de Pittsburgh para NY.
39
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo – Problema do Caixeiro Viajante
(Simétrico) Há n cidades para serem visitadas, elas são numeradas 
de 1 a n. Para cada par de cidades (i, j) conhece-se Cij = custo 
para ir de i para j = custo de ir de j para i. 
Qual é o roteiro de vistas mais econômico? 
Modelo 
Variáveis de Decisão: 
Xij = 1, se o vendedor viajou da cidade i para a j (ou vice-versa); e 
= 0, caso contrário.
40
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Exemplo - Problema do Caixeiro Viajante
Min Z= 
Restrições:
Todas cidades devem ser visitadas formando um circuito de n cidades.
Restrições de eliminação de sub-rotas, estabelecem que para todo 
subconjunto de cidades S, o roteiro do vendedor deve entrar e sair 
deste sub-conjunto de cidades:
Observação: Para 20 cidades: tem-se 524.288 restrições; 
Para 300 cidades:
1.018.517.988.167.243.043.134.222.844.204.689.080.525.734.196.8
32.968.125.318.070.224.677.190.649.881.668.353.091.698.688 
restrições!!!!!!!!!!
41
NS para2,
Si Sj
ijX 
 
 
ij
n
i
n
j
ij XC 
 1 1
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Métodos de solução de problemas de 
PLI
Há dois métodos gerais:
1. Método de planosde corte (“cutting plane”) - PC
2. Método tipo “branch and bound”- B&B
Muitos códigos computacionais comerciais usam o B&B, alguns 
aplicam o PC como ajuda adicional.
42
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte
Descrição do método PC:
1. Inicialização:
Resolver o PLI relaxado - PLIR, isto é, sem as restrições de 
integralidade.
2. Fazer o Teste de otimalidade:
Se a solução ótima do PLIR for inteira então a solução ótima do 
PLI foi encontrada - Parar.
Caso contrário, acrescentar uma nova restrição (corte) ao PLIR.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte
Corte Fracionário de Golmory para PLI puro:
44
básicas-nãoVariáveisdasConjunto=
a deaFracionári Parte=
,b deaFracionári Parte=f
onde f-Xf
kj
kk
Nj
kjkj
N
f kj



Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte
Detalhamento do Corte Fracionário de Gomory
Se na tabela ótima do PLIR há uma variável básica XK = bK que não 
corresponda a um valor inteiro.
Sejam:
N = conjunto das variáveis não básicas
I(XK) = nk = parte inteira da variável básica XK (maior inteiro  XK)
fK = parte fracionária de XK
Exemplos: XK = 5/3 = 1 + 2/3  I(XK ) = nk = 1, fk = 2/3
XK = -5/3 = -2 + 1/3  I(XK) = nk = -2, fk = 1/3
45
 fK = XK - I(XK ) = XK - nk com 0  fk < 1
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte
46
Observação: Os cortes adicionados conservam todas as 
soluções inteiras do problema
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte
3. Melhoria da solução: aplicar o Método Dual Simplex à nova 
solução.
4. Passo geral: repetir os Passos 2 e 3 até achar uma solução 
ótima inteira.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte -
Exemplo
48
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte -
Exemplo
49
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte -
Exemplo
50
Aplicando o Método Simplex ao PLIR tem-se a tabela ótima
abaixo, onde x3 , x4, x5 são variáveis de folga
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte -
Exemplo
51
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método de Planos de Corte -
Exemplo
52
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B
Método “Branch & Bound”: procedimento eficiente de enumeração 
das possíveis soluções viáveis inteiras.
Seja o PLI : Max Z = CX sujeito a: {AX = b, X  0, Xj inteiro para 
j  I, com I = conjunto das variáveis inteiras}.
Etapas:
1. Resolva o PLI sem as restrições de integralidade. Denote por PL-
1 com solução ótima = z1:
Se todo xj for inteiro para j  i  solução ótima para o PLI. Parar!
Caso contrário: há xj fracionário para j  i, e z1 = um limitante 
superior (“upper bound”) para o valor da função objetivo ótima 
do PLI.
53
x
Sticky Note
parei aqui
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B
2. Particionar (“branch”) a região viável do PL-1 com respeito a 
algum xj fracionário para j  I, procurando achar soluções inteiras 
que serão limitantes inferiores (“lower bound”) para o z do PLI:
Suponha que xj foi selecionada para a partição e que j é o seu valor 
(fracionário). 
Criar dois novos problemas, PL-2 e PL-3, introduzindo as restrições
xj  j e xj  j , respectivamente, onde j é o maior inteiro 
menor que j e j é o menor inteiro maior que j
54
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B
Usar o Método Dual Simplex para encontrar as soluções ótimas de 
PL-2 e PL-3. Admita que estas soluções ainda são fracionárias.
Selecionar PL-2 ou PL-3 para desenvolver uma nova ramificação com 
a introdução de uma nova restrição, como foi feito anteriormente: 
Continuar o processo até obter uma solução inteira para algum 
dos PL’s criados. o valor ótimo da função objetivo desta solução 
inteira é um limitante inferior (“lower bound”) para o valor máximo 
de z para o PLI original.
Admitir como explorados (“fathomed”) aqueles PL’s cujos 
valores de z não são melhores que o “lower bound” conhecido, ou que 
sejam inviáveis, ou ainda que já tenham solução ótima inteira.
55
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B
56
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B
Continuar este processo de “Branch & Bound”até que todos os PL’s 
tenham sido explorados.
O PL com o maior valor de z corresponde a solução ótima do PLI.
Observações:
1. A solução de PL-4 é inteira  há limitante inferior para o valor 
máximo do valor da função objetivo do PLI = z4  a solução ótima 
do PLI terá um valor de z z4. não é necessário explorar o nó 4 pois 
qualquer PLI subseqüente terá solução menor que z4 .
2. Nó 5 também não será explorado pois o PL-5 é inviável.
3. Os nós 6 e 7 podem ser explorados. Suponha que z6 < z4 e z7 > z4
 nó 6 não necessita ser explorado, pois nenhum PL abaixo deste 
nó 6 produzirá um valor de função objetivo melhor que z4. O nó 7 
deve ser escolhido e o processo deve continuar..
57
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B
Observações gerais:
1. Regras para particionar o PL-1: selecionar a variável inteira com o 
maior valor fracionário; ou aquela que representa uma decisão 
importante no modelo, ou aquela com o maior coeficiente (em 
módulo) na função objetivo, ou a variável com menor índice.
2. Regras para escolher entre PL-2 e PL-3 para exploração: escolher 
o PL com o maior valor de z (para maximização), escolher o PL 
que foi resolvido mais recentemente (“last-in-first-out rule”).
3. A eficiência do método B&B depende da identificação rápida dos 
PL’s explorados. O conhecimento de um limitante inferior inicial 
para o PLI é bastante útil.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B - Exemplo
Max Z = 3 X1 + 2 X2 s.a: 
Fazer PL-1 = modelo sem restrições inteiras. 
Aplicando o Método Simplex neste modelo relaxado tem-se: 
Max Z = z0 = 9, com x1 = 2 e x2 = 1,5.
59









Inteiros0,X,
3,5X+X
2X
2X
21
21
2
1
X
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B - Exemplo
Criar dois novos problemas (Partição):
Soluções ótimas: 
PL - 2: Max Z = z2 = 8, com x1 = 2, x2 = 1 
PL-3: Max Z = z3 = 8,5, com x1 = 1,5, x2 = 2.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B - Exemplo
A solução do PL-2 já é inteira  deve-se explorar o nó 3.
Para o PL-3: valor máximo de Z = 8,5 > 8 = novo limitante inferior 
para Z.
Adicionar no PL-3 as restrições: 
x1  1 ou x1  2 obtendo-se dois novos problemas: 
PL-4 e PL-5.
Soluções ótimas:
PL-4: Max Z = z4 = 7, com x1 = 1, x2 = 2 
PL-5: inviável
62
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B - Exemplo
63
Conclusão: 
A solução inteira ótima do PL-2 será a solução ótima do PLI 
original: Max Z = 8, x1 = 2, x2 = 1.
Pesquisa Operacional Aplicada à Produção - UNESP/ Campus de Guaratinguetá
Método B&B – Exemplo - Resumo
64
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Método B&B – Exemplo - Árvore
65