PO1_Aula_08

Prévia do material em texto

Pesquisa Operacional I 
(CEP/CT025) – Aula 08
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br 
9. Programação Inteira
9.1. Definições;
9.2. Aplicações;
9.3. Modelagem;
9.4. Modelagem de restrições especiais.
9.1. Definições
• Problemas em que pelo menos uma variável faz sentido apenas se 
tiver um valor inteiro (discreto);
• Também conhecida somente como Programação Inteira (PI);
• Discreto ≠ Contínua;
• Exemplo: alocar pessoa, máquinas e veículos;
• Igual ao problema de programação linear com um conjunto de 
restrições adicional (variável deve ter um valor inteiro);
9.1. Definições
• Se apenas algumas variáveis tiverem de ter valores inteiros: 
Programação Inteira Mista (PIM);
• Deve respeitar a hipótese da divisibilidade;
• Se todas as variáveis tiverem de ter valores inteiros: Programação 
Inteira Pura;
• Se a variável somente puder assumir os valores 0 ou 1 chamamos 
de variável binária, ou seja:
𝑥! = #1 se a decisão j for sim
0 se a decisão j for não
9.1. Definições
• Também conhecidas como variáveis 0-1;
• Problemas de PI que contêm apenas variáveis binárias: 
Programação Inteira Binária (PIB);
9.2. Aplicações
• Diversas aplicações em diferentes contextos:
• Problemas de programação linear com variáveis inteiras (ex: quantidade 
de unidades fabricadas de um determinado produto);
• Tomada de decisão (ex: investir em qual projeto);
• Ações sequenciais em redes;
• Problemas de transporte, etc.
9.2. Aplicações
• Exemplo 1: Uma empresa considera a possibilidade de expandir e 
construir uma nova fábrica em Parauapebas ou então em Marabá, 
ou quem sabe, até mesmo em ambas as cidades. A empresa 
também considera a possibilidade de construir no máximo um novo 
depósito, mas a escolha do local está restrita a uma cidade na qual a 
nova fábrica será construída. O Valor Presente Líquido (VPL) de cada 
uma dessas alternativas, assim como os respectivos investimentos 
são mostrados na tabela a seguir. Sabendo que a empresa possui um 
capital total de R$ 10 milhões, o objetivo é encontrar a combinação 
de alternativas que maximize o VPL.
9.2. Aplicações
Número de 
decisões Pergunta sim-ou-não Variável de 
decisão VPL Capital exigido
1 Construir a fábrica em
Parauapebas? 𝑥! R$ 9 milhões R$ 6 milhões
2 Construir a fábrica em Marabá? 𝑥" R$ 5 milhões R$ 3 milhões
3 Construir o depósito em
Parauapebas? 𝑥# R$ 6 milhões R$ 5 milhões
4 Construir o depósito em Marabá? 𝑥$ R$ 4 milhões R$ 2 milhões
Capital disponível: R$ 10 milhões
9.2. Aplicações
• Nesse problema todas as variáveis são binárias (PIB):
𝑥! = #1 se a decisão j for sim
0 se a decisão j for não (𝑗 = 1,2,3,4)
• A nossa função obje`vo é:
𝑍 = VPL total das decisões
9.2. Aplicações
• Com base no VPL para cada decisão, temos:
𝑍 = 9𝑥# + 5𝑥$ + 6𝑥% + 4𝑥&
• Como o capital disponível é de R$ 10 milhões:
6𝑥# + 3𝑥$ + 5𝑥% + 2𝑥& ≤ 10
9.2. Aplicações
• Além disso, um depósito (𝑥% ou 𝑥&) só pode ser construído se uma
fábrica (𝑥# ou 𝑥$) também for construída, respectivamente, logo:
𝑥% ≤ 𝑥# e 𝑥& ≤ 𝑥$
• Como a empresa deseja construir no máximo um depósito:
𝑥% + 𝑥& ≤ 1
9.2. Aplicações
• Finalmente, a modelagem fica:
𝑀𝐴𝑋 𝑍 = 9𝑥# + 5𝑥$ + 6𝑥% + 4𝑥&
𝑠. 𝑎.
6𝑥# + 3𝑥$ + 5𝑥% + 2𝑥& ≤ 10 (1)
𝑥% + 𝑥& ≤ 1 (2)
−𝑥# + 𝑥% ≤ 0 (3)
−𝑥$ + 𝑥& ≤ 0 (4)
𝑥! ≤ 1 (5)
𝑥! ≥ 0 (6)
𝑥! é inteira, para 𝑗 = 1,2,3,4 (7)
9.2. Aplicações
• Ou também:
𝑀𝐴𝑋 𝑍 = 9𝑥# + 5𝑥$ + 6𝑥% + 4𝑥&
𝑠. 𝑎.
6𝑥# + 3𝑥$ + 5𝑥% + 2𝑥& ≤ 10
𝑥% + 𝑥& ≤ 1
−𝑥# + 𝑥% ≤ 0
−𝑥$ + 𝑥& ≤ 0
𝑥! é binária, para 𝑗 = 1,2,3,4
9.2. Aplicações
• Exemplo bpico de muitas aplicações reais de programação inteira
com decisões do `po sim-ou-não;
• Restrição de alterna`vas mutuamente exclusivas (restrição 2);
• Restrições de decisões con`ngentes (restrições 3 e 4);
9.2. Aplicações
• Aplicação 1 – Análise de investimentos:
• Programação linear usada para tomar deciões sobre orçamento de 
capital com relação a quanto investir em vários projetos;
• Algumas decisões não envolvem quanto investir, mas sim se se deve
investir ou não uma quantia fixa;
• A gerência normalmente se depara com decisões sobre se deve ou não
realizar investimentos fixos;
• Em geral, decisões sobre orçamento de capital em relação a 
investimentos fixo são decisões sim-ou-não;
9.2. Aplicações
• Aplicação 1 – Análise de investimentos:
• Para cada decisão sim-ou-não: Devemos fazer certo investimento?
Sua variável de decisão = #1 se sim
0 se não
9.2. Aplicações
• Aplicação 2 – Escolher um local:
• Corporações abrem novas instalações em diversas partes do mundo;
• Antes de escolher determinado local, vários locais potenciais precisam
ser analisados e comparados;
• Cada local potencial envolve uma decisão do Lpo sim-ou-não;
• Para cada decisão sim-ou-não: Certo local deve ser escolhido para a 
localização de determinada nova instalação?
Sua variável de decisão = #1 se sim
0 se não
9.2. Aplicações
• Aplicação 3 – Desenho de redes de produção e distribuição:
• Fabricantes sofrem muita pressão compeLLva para que seus produtos
cheguem ao mercado de forma rápida e com baixos custos;
• Qualquer empresa que distribua seus produtos em uma área geográfica
extensa deve atentar ao seu desenho de rede de produção/distribuição;
• Esse desenho envolve responder os seguintes Lpos de decisão binários:
Ø Devemos manter aberta determinada fábrica?
Ø Devemos escolher certo local para uma nova fábrica?
Ø Devemos manter aberto dado centro de distribuição (CD)?
Ø Devemos escolher determinado local para um novo centro de 
distribuição?
9.2. Aplicações
• Aplicação 3 – Desenho de redes de produção e distribuição:
• Se cada área for atendida por um único centro de distribuição, temos 
outra decisão binária para cada combinação de área de mercado e CD:
Ø Determinado CD deve ser designado para atender certa área?
• Para cada uma das decisões binárias:
Sua variável de decisão = #1 se sim
0 se não
9.2. Aplicações
• Aplicação 4 – Despacho de mercadorias:
• Após desenhar e colocar em operação a rede de produção/distribuição, 
deve-se tomar decisões em relação a como despachar as mercadorias;
• Suponha que utilizem caminhões para fazer várias entregas para 
diferentes clientes;
• Torna-se necessário escolher uma rota (sequência de clientes) para 
cada caminhão;
9.2. Aplicações
• Aplicação 4 – Despacho de mercadorias:
• Cada candidato a uma rota deve responder à seguinte decisão:
Ø Devemos escolher certa rota para um dos caminhões?
• Para cada uma das decisões binárias:
Sua variável de decisão = #1 se sim
0 se não
• O objeLvo seria escolher as rotas que minimizassem o custo total para 
fazer as entregas;
9.2. Aplicações
• Aplicação 5 – Programação de aBvidades inter-relacionadas:
• Gerentes têm de programar diversos Lpos de aLvidades inter-
relacionadas;
Ø Quando devemos iniciar a produção para atender novos pedidos?
Ø Quando devemos iniciar a comercialização de novos produtos?
Ø Quando devemos fazer invesLmentos para expandir a produção?
• Para qualquer uma dessas aLvidades, a decisão sobre quando inciar 
pode ser expressa em termos de decisões sim-ou-não;
9.2. Aplicações
• Aplicação 5 – Programação de atividades inter-relacionadas:
• Deve haver uma variável para cada decisão em cada período possível no 
qual iniciar;
Ø Devemos iniciar certa atividade em determinado período:
Sua variável de decisão = #1 se sim
0 se não
• As variáveis relacionadas com uma atividade específica são alternativas
mutuamente excludentes (somente uma pode ter valor igual a 1).
9.2. Aplicações
• Aplicação 6 – Problema de designação de frotas:
• Dados diversos tipos diferentes de aeronaves existentes e uma 
programação de voo;
• O problema é alocar um tipo específico a cada trecho da programação 
de modo a maximizar o lucro e atender a programação definida;
• Se usar um avião muito pequeno em um trecho, pode deixar de atender 
possíveisclientes;
• Se usar um avião muito grande, sofrerá com despesas maiores do avião 
maior voando com assentos vazios;
9.2. Aplicações
• Aplicação 6 – Problema de designação de frotas:
• Para cada combinação Lpo de aeronave-trecho de voo, temos a 
seguinte decisão:
Ø Devemos alocar determinado Lpo de aeronave a certo trecho de voo?
Sua variável de decisão = #1 se sim
0 se não
9.2. Aplicações
• Aplicação 7 – Problema de escala de tripulação:
• Ao invés de alocar aviões a trechos de voo, alocamos sequências de 
trechos de voo a tripulações de pilotos e comissários;
• Para cada sequência viável de trechos de voo que parte de uma base de 
tripulação e retorna à mesma base::
Ø Determinada sequência de trechos de voo deveria ser alocada a uma
tripulação?
Sua variável de decisão = #1 se sim
0 se não
• O objeLvo é minimizar o custo total de disponibilizar tripulações que 
cubram cada trecho de voo programado.
9.3. Modelagem
9.3.1. Problema da mochila 0-1;
9.3.2. Problema de atribuição com variáveis inteiras;
9.3.3. Problema de cobertura;
9.3.4. Problema do caixeiro-viajante;
9.3.5. Problema de programação de produção
9.3.1. Problema da mochila 0-1
• Suponha que haja 𝑛 projetos para serem realizados;
• O 𝑗-ésimo projeto (𝑗 = 1,2, … , 𝑛) possui VPL de 𝑐! e requer 
investimento 𝑎'! (𝑖 = 1,2, … ,𝑚);
• Cada projeto é feito completamente ou não é feito;
• Para o período 𝑖 há disponibilidade orçamentária para realização 
dos projetos equivalente a 𝑏';
• O problema é escolher um grupo de projetos para serem realizados 
maximizando o VPL sem exceder o orçamento;
9.3.1. Problema da mochila 0-1
• Esse problema é conhecido como problema da mochila 0-1 
mul`dimensional;
• É um problema equivalente ao de decidir sobre o que deve ser 
colocado em uma mochila considerando-se as restrições de peso;
•Mul`dimensional refere-se ao caso com múl`plas restrições 𝑖;
• Para o caso de um único período o problema é denominado 
simplesmente problema da mochila 0-1;
9.3.1. Problema da mochila 0-1
• Vários problemas se encaixam na formulação descrita:
• Definição de carga de caminhões;
• Definição de pacotes a serem transportados em pallets;
• Orçamento de capital com variáveis inteiras.
9.3.1. Problema da mochila 0-1
• Formulação genérica do problema:
max𝑍 =&
!"#
$
𝑐!𝑥!
𝑠. 𝑎.
&
!"#
$
𝑎%!𝑥! ≤ 𝑏% 𝑖 = 1,2, … ,𝑚
𝑥! ∈ 0,1 (𝑗 = 1,2, … , 𝑛)
9.3.1. Problema da mochila 0-1
• Exemplo 01: A VVC, empresa de capital empreendedor, está 
avaliando oportunidades de investimento para os próximos três 
anos. A empresa tem um orçamento de 200 milhões, 250 milhões e 
150 milhões para os próximos três anos, respectivamente. A 
empresa deve definir onde os investimentos deve ser realizados de 
modo a maximizar o VPL, conforme a tabela a seguir.
9.3.1. Problema da mochila 0-1
Investimento
Investimento VPL 
investimentoAno 0 Ano 1 Ano 2
A 12 34 12 20
B 54 94 67 15
C 65 28 49 34
D 38 0 8 17
E 52 21 42 56
F 98 73 25 76
G 15 48 53 29
TOTAL 334 298 256 247
9.3.1. Problema da mochila 0-1
• Resumindo, a VVC quer saber se ela deve ou não inves`r em uma 
oportunidade de inves`mento;
• Chamaremos 𝑥! (𝑗 = 1,2, … , 𝑛) de realização no inves`mento 𝑗, ou 
seja:
𝑥! = #1 se sim
0 se não (𝑗 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹)
9.3.1. Problema da mochila 0-1
• De forma a garantir que para cada ano o investimento total não 
exceda o orçamento do ano:
12𝑥( + 54𝑥) + 65𝑥* + 38𝑥+ + 52𝑥, + 98𝑥- + 15𝑥. ≤ 200
34𝑥( + 94𝑥) + 28𝑥* + 21𝑥, + 73𝑥- + 48𝑥. ≤ 250
12𝑥( + 67𝑥) + 49𝑥* + 8𝑥+ + 42𝑥, + 25𝑥- + 53𝑥. ≤ 150
9.3.1. Problema da mochila 0-1
• A função objetivo estabelece que o VPL deve ser o maior possível:
max𝑍 = 20𝑥( + 15𝑥) + 34𝑥* + 17𝑥+ + 56𝑥, + 76𝑥- + 29𝑥.
• Todas as variaveis são binárias (inteiras):
𝑥! ∈ 0,1 (𝑗 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺)
9.3.1. Problema da mochila 0-1
• Resumindo:
max𝑍 = 20𝑥( + 15𝑥) + 34𝑥* + 17𝑥+ + 56𝑥, + 76𝑥- + 29𝑥.
s.a.
12𝑥( + 54𝑥) + 65𝑥* + 38𝑥+ + 52𝑥, + 98𝑥- + 15𝑥. ≤ 200
34𝑥( + 94𝑥) + 28𝑥* + 21𝑥, + 73𝑥- + 48𝑥. ≤ 250
12𝑥( + 67𝑥) + 49𝑥* + 8𝑥+ + 42𝑥, + 25𝑥- + 53𝑥. ≤ 150
𝑥! ∈ 0,1 (𝑗 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺)
9.3.2. Problema de atribuição com variáveis 
inteiras;
• Suponha que haja 𝑛 pessoas e 𝑚 ordens de produção a serem 
realizadas, em que 𝑛 ≥ 𝑚;
• Cada ordem pode ser feita por apenas uma pessoa e cada pessoa 
pode fazer no máximo uma ordem;
• O custo incorrido quando a pessoa 𝑗 faz a ordem 𝑖 é 𝑐'!;
• O problema consiste em alocar as pessoas às ordens de modo a 
minimizar o custo total para finalizar todas as ordens;
9.3.2. Problema de atribuição com variáveis 
inteiras;
• Seja 𝑥'! a variável que corresponde à alocar a pessoa 𝑗 à ordem 𝑖:
min𝑍 =b
!/#
0
b
'/#
1
𝑐'!𝑥'!
𝑠. 𝑎.
b
!/#
0
𝑥'! = 1 (𝑖 = 1,2, … ,𝑚)
b
'/#
1
𝑥'! ≤ 1 (𝑗 = 1,2, … , 𝑛)
𝑥'! ∈ 0,1 (𝑖 = 1,2, … ,𝑚; 𝑗 = 1,2, … , 𝑛)
9.3.2. Problema de atribuição com variáveis 
inteiras;
• Exemplo 02: A administração de manutenção de uma empresa
montadora de aparelhos eletrônicos chamada Philight está
interessada em alocar seu pessoal de manutenção para quebras
ocorridas no turno da noite. A tabela a seguir apresenta os custos 
relacionados com os quatro mecânicos de manutenção e as 
atividades a serem executadas. Cada atividade pode ser feita por 
apenas um mecânico e cada um deles deve realizar pelo menos uma
atividade. Determine a alocação de mecânicos que garanta que 
todas as atividades sejam realizadas utilizando os quatro mecânicos
ao menor custo possível.
9.3.2. Problema de atribuição com variáveis 
inteiras;
Atividade
Custo de manutenção por mecânico 𝒊
𝒊 = 𝟏 𝒊 = 𝟐 𝒊 = 𝟑 𝒊 = 𝟒
Injetora (𝑗 = 1) 70 58 97 38
Estufa (𝑗 = 2) 53 81 68 68
Torno CNC (𝑗 = 3) 88 16 57 86
Furadeira (𝑗 = 4) 15 9 18 11
Ar condicionado (𝑗 = 5) 17 5 3 15
Afinadora (𝑗 = 6) 13 26 11 15
9.3.2. Problema de atribuição com variáveis 
inteiras;
• Seja 𝑥'! a alocação do mecânico 𝑖 à atividade 𝑗;
• Há seis atividades a serem realizadas (𝑛 = 6) e quatro mecânicos 
(𝑚 = 4);
• Cada atividade pode ser feita por apenas um mecânico;
• Cada mecânico deve realizar pelo menos uma atividade;
9.3.2. Problema de atribuição com variáveis 
inteiras;
• A função obje`vo fica:
min𝑍
= 70𝑥## + 58𝑥$# + 97𝑥%# + 38𝑥&# +⋯+ 13𝑥#2 + 26𝑥$2 + 11𝑥%2
+ 15𝑥&2
9.3.2. Problema de atribuição com variáveis 
inteiras;
• As restrições para cada mecânico ficam:
𝑥## + 𝑥#$ + 𝑥#% + 𝑥#& + 𝑥#3 + 𝑥#2 ≥ 1 𝑚𝑒𝑐â𝑛𝑖𝑐𝑜 𝑖 = 1
𝑥$# + 𝑥$$ + 𝑥$% + 𝑥$& + 𝑥$3 + 𝑥$2 ≥ 1 𝑚𝑒𝑐â𝑛𝑖𝑐𝑜 𝑖 = 2
𝑥%# + 𝑥%$ + 𝑥%% + 𝑥%& + 𝑥%3 + 𝑥%2 ≥ 1 𝑚𝑒𝑐â𝑛𝑖𝑐𝑜 𝑖 = 3
𝑥&# + 𝑥&$ + 𝑥&% + 𝑥&& + 𝑥&3 + 𝑥&2 ≥ 1 𝑚𝑒𝑐â𝑛𝑖𝑐𝑜 𝑖 = 4
9.3.2. Problema de atribuição com variáveis 
inteiras;
• As restrições para cada atividade ficam:
𝑥## + 𝑥$# + 𝑥%# + 𝑥&# = 1 injetora
𝑥#$ + 𝑥$$ + 𝑥%$ + 𝑥&$ = 1 estufa
𝑥#% + 𝑥$% + 𝑥%% + 𝑥&% = 1 torno CNC
𝑥#& + 𝑥$& + 𝑥%& + 𝑥&& = 1 furadeira
𝑥#3 + 𝑥$3 + 𝑥%3 + 𝑥&3 = 1 ar condicionado
𝑥#2 + 𝑥$2 + 𝑥%2 + 𝑥&2 = 1 ajinadora
9.3.2. Problema de atribuição com variáveis 
inteiras;
• As variáveis são binárias:
𝑥'! ∈ 0,1 (𝑖 = 1,2,3,4; 𝑗 = 1,2,3,4,5,6)
9.3.3. Problema de cobertura
• Possui várias versões (como o problema de localização da fábrica);
• Trata de uma grande variedade de problemas reais, como a 
alocação de clientes a rotas de entrega, tripulação à voos etc.;
• Seja 𝑗 (𝑗 = 1,2, … , 𝑛) um local potencial para contruir uma fábrica e 
𝑖 (𝑖 = 1,2, … ,𝑚) um cliente qualquer que deve ser atendido;
• Se uma planta for instalada em 𝑗, a instalação custa 𝑐!;
• Cada cliente 𝑖 tem um perfil de demanda e o custo variável de envio 
da planta 𝑗 para o cliente 𝑖 é definido como ℎ'!;
9.3.3. Problema de cobertura
• A variável 𝑥! define se uma planta será construída ou não em 𝑗;
• A demanda do cliente 𝑖 atendida pela planta 𝑗 é definida por 𝑦'!;
• Uma planta qualquer tem capacidade 𝑢! e cada cliente tem uma 
demanda 𝑏';
• O interesse é definir onde instalar fábricas de modoque clientes 
sejam atendidos ao custo mínimo;
9.3.3. Problema de cobertura
min𝑍 =b
!/#
0
𝑐!𝑥! +b
'/#
1
b
!/#
0
ℎ'!𝑦'!
𝑠. 𝑎.
b
!/#
0
𝑦'! = 𝑏' 𝑖 = 1,2, … ,𝑚
b
'/#
1
𝑦'! − 𝑢!𝑥! ≤ 0	 (𝑗 = 1,2, … , 𝑛)
𝑥! ∈ 0,1 , 𝑦'! ≥ 0 (𝑖 = 1,2, … ,𝑚; 𝑗 = 1,2, … , 𝑛)
9.3.3. Problema de cobertura
• Os custos que não dependem da localidade da planta não são 
considerados (exemplo: custos fixos);
• A receita gerada independe da localidade (considera-se que toda 
produção é vendida);
9.3.3. Problema de cobertura
• Exemplo 03: A CEARS está avaliando localidades no Rio Grande do 
Sul para construir três novos armazéns agrícolas. A empresa já possui 
armazéns mas está precisando expandir a sua capacidade devido ao 
crescimento da demanda. A figura abaixo apresenta as localidades 
escolhidas como possíveis armazéns, juntamente com as cinco 
regiões de clientes que foram selecionadas. A tabela abaixo oferece 
os detalhes referentes aos clientes e armazéns. A capacidade e a 
demanda são referentes a um ano de operações. Os custos logís`cos 
referem-se ao custo por tonelada transportada. Quais as três 
melhores localidades com o menor custo possível?
9.3.3. Problema de cobertura;
Opções de 
localidade do 
armazém
Custo 
(milhões)
Capacidade 
(kt.)
Custo logístico entre armazém e destino
Uruguaiana Pelotas Caxias do Sul Passo Fundo Porto Alegre
𝒊 = 𝟏 𝒊 = 𝟐 𝒊 = 𝟑 𝒊 = 𝟒 𝒊 = 𝟓
Alegrete (𝑗 = 1) 7 600 2,10 6,30 7,80 6,30 7,50
Caçapava do Sul (𝑗 =
2) 5 750 5,70 2,70 4,50 4,50 3,78
Tupanciretá (𝑗 = 3) 9 350 5,40 5,58 4,38 2,88 4,80
Vacaria (𝑗 = 4) 6 450 10,20 6,54 1,14 2,40 3,00
Santa Rosa (𝑗 = 5) 4 400 5,58 7,86 6,00 3,48 6,84
Demanda total (milhar de tonelada) 150 450 300 250 500
9.3.3. Problema de cobertura
• Considere a variável 𝑥! a presença do armazém na localidade 𝑗;
• Temos que levar em conta os dois custos: de construção do 
armazém e de logística;
• O armazém 𝑗 pode encaminhar seus produtos para qualquer cliente 
𝑖, chamaremos 𝑦'! a quantidade de produtos enviadas de 𝑗 para 𝑖;
9.3.3. Problema de cobertura
• Função objetivo:
min𝑍
= 7000𝑥# + 5000𝑥$ + 9000𝑥% + 6000𝑥& + 4000𝑥3 + 2,10𝑦##
+ 6,30𝑦$# + 7,80𝑥%# + 6,30𝑦&# + 7,50𝑦3# +⋯+ 5,58y#3
+ 7,86y$3 + 6,00y%3 + 3,48y&3 + 6,84y33
9.3.3. Problema de cobertura
• Restrições de capacidade de armazém:
𝑦## + 𝑦$# + 𝑦%# + 𝑦&# + 𝑦3# ≤ 600𝑥#
𝑦#$ + 𝑦$$ + 𝑦%$ + 𝑦&$ + 𝑦3$ ≤ 750𝑥$
𝑦#% + 𝑦$% + 𝑦%% + 𝑦&% + 𝑦3% ≤ 350𝑥%
𝑦#& + 𝑦$& + 𝑦%& + 𝑦&& + 𝑦3& ≤ 450𝑥&
𝑦#3 + 𝑦$3 + 𝑦%3 + 𝑦&3 + 𝑦33 ≤ 400𝑥3
9.3.3. Problema de cobertura
• Restrições de demanda:
𝑦## + 𝑦#$ + 𝑦#% + 𝑦#& + 𝑦#3 = 150
𝑦$# + 𝑦$$ + 𝑦$% + 𝑦$& + 𝑦$3 = 450
𝑦%# + 𝑦%$ + 𝑦%% + 𝑦%& + 𝑦%3 = 300
𝑦&# + 𝑦&$ + 𝑦&% + 𝑦&& + 𝑦&3 = 250
𝑦3# + 𝑦3$ + 𝑦3% + 𝑦3& + 𝑦33 = 500
9.3.3. Problema de cobertura
• Restrição de quantidade de armazéns:
𝑥# + 𝑥$ + 𝑥% + 𝑥& + 𝑥3 = 3
• Restrições de tipo de variável:
𝑥! ∈ 0,1 𝑗 = 1,2,3,4,5
𝑦! ≥ 0 (𝑖 = 1,2,3,4,5; 𝑗 = 1,2,3,4,5)
9.3.4. Problema do caixeiro-viajante
• Problema clássico de PI;
• Seja um conjunto de nós 𝑉 = {1,2, … , 𝑛} e um outro de arcos 𝐴;
• Os nós representam as cidades e os arcos os pares ordenados de 
cidades entre as quais uma viagem é possível;
• Para o arco 𝑖, 𝑗 ∈ 𝐴, 𝑐'! é o tempo de viagem da cidade 𝑖 para a 
cidade 𝑗;
• O problema é achar uma rota que inicia e termina na mesma cidade 
que visita todas as cidades apenas uma vez com o menor tempo;
9.3.4. Problema do caixeiro-viajante
• Suponha que 𝑥'! = 1 represente que a cidade 𝑗 foi visitada 
imediatamente depois da cidade 𝑖;
• Se isso não acontecer, 𝑥'! = 0;
• Para evitar soluções incovenientes, podemos fazer 𝑐!! = ∞;
• A formulação para este modelo é:
9.3.4. Problema do caixeiro-viajante
min𝑍 =b
'/#
0
b
!/#
0
𝑐'!𝑥'!
𝑠. 𝑎.
b
'/#
0
𝑥'! = 1 𝑗 = 1,2, … , 𝑛 𝑠𝑎í𝑑𝑎
b
!/#
0
𝑥'! = 1 𝑖 = 1,2, … , 𝑛 𝑐ℎ𝑒𝑔𝑎𝑑𝑎
∑𝑥'! ≤ 𝑠 − 1 𝑆 ⊂ 𝑉 	(𝑠𝑢𝑏 − 𝑟𝑜𝑡𝑎𝑠)
𝑥'! ∈ 0,1 	 (𝑗 = 1,2, … , 𝑛; 𝑖 = 1,2, … , )
9.3.4. Problema do caixeiro-viajante
• Restrições de saída, de chegada e binárias garantem que cada um 
dos 𝑥'! é 0 ou 1;
• As restrições de saída garantem que para cada cidade haverá 
apenas uma rota de saída (e de forma análoga para as chegadas);
• As restrições do grupo sub-rotas garantem que a solução ótima não 
contenha sub-rotas;
• As variáveis 𝑢' e 𝑢! são auxiliares e não têm um significado físico;
9.3.4. Problema do caixeiro-viajante
• As restrições de sub-rotas também podem ser definidas de forma 
alternativa;
• Considere um subconjunto de cidades 𝑆 com 𝑠 cidades, em que 2 ≤
𝑠 ≤ 𝑛;
• A seguinte inequação garante que sub-rotas não são formadas:
∑𝑥'! ≤ 𝑠 − 1 𝑆 ⊂ 𝑉 	(𝑠𝑢𝑏 − 𝑟𝑜𝑡𝑎𝑠)
9.3.4. Problema do caixeiro-viajante
• Exemplo 4: Uma empresa oferece serviço de enfermagem na casa 
de pacientes. A figura a seguir oferece um mapa de uma região com 
as residências (𝑃1, 𝑃2, 𝑃3, 𝑃4) que devem ser visitadas por um 
enfermeiro. O nó “Sede” representa o ponto de onde o enfermeiro 
começa e termina a sua jornada diária. Os valores sobre os arcos 
representam as distâncias em quilômetros entre dois nós. Busca-se 
minimizar a distância total percorrida no dia de modo que o 
enfermeiro passe o máximo de tempo possível atendendo pacientes.
• 𝑥'! = 1 (em que 𝑖, 𝑗 ∈ 𝑃1, 𝑃2, 𝑃3, 𝑃4, 𝑆𝑒𝑑𝑒 e 𝑖 ≠ 𝑗) representa 
que o enfermeiro visitou o nó 𝑗 imediatamente após o nó 𝑖;
9.3.4. Problema do caixeiro-viajante
𝑥!",$ + 𝑥!%,$ + 𝑥!&,$ + 𝑥!',$ = 1
𝑥$,!" + 𝑥$,!% + 𝑥$,!& + 𝑥$,!" = 1
⋮
𝑥!",$ + 𝑥$,!" ≤ 1
⋮
𝑥!',!% + 𝑥!%,!' + 𝑥!',!&
+ 𝑥!&,!' + 𝑥!%,!&
+ 𝑥!&,!% ≤ 2
⋮
𝑥!',!% + 𝑥!%,!' + 𝑥!',!&
+ 𝑥!&,!' + 𝑥!',!"
+ 𝑥!",!' + 𝑥!%,!&
+ 𝑥!&,!% + 𝑥!%,!"
+ 𝑥!",!% + 𝑥!&,!"
+ 𝑥!",!& ≤ 3
⋮
9.3.4. Problema do caixeiro-viajante
Para
Sede 𝑃1 𝑃2 𝑃3 𝑃4
De
Sede ∞ 5,0 3,8 2,2 2,4
𝑃1 5,0 9𝐸 + 99 2,6 3,1 5,1
𝑃2 3,8 2,6 9𝐸 + 99 1,6 2,8
𝑃3 2,2 3,1 1,6 9𝐸 + 99 2,3
𝑃4 2,4 5,1 2,8 2,3 9𝐸 + 99
9.3.4. Problema do caixeiro-viajante
• Função objetivo:
𝑀𝐼𝑁	𝑍
= 5,0𝑥45657# + 3,8𝑥45657$ + 2,2𝑥45657% + 2,4𝑥45657& + 5,0𝑥7#4565
+ 2,6𝑥7#7$ + 3,1𝑥7#7% + 5,1𝑥7#7& + 3,8𝑥7$4565 + 2,6𝑥7$7#
+ 1,6𝑥7$7% + 2,8𝑥7$7& + 2,2𝑥7%4565 + 3,1𝑥7%7# + 1,6𝑥7%7$
+ 2,3𝑥7%7& + 2,4𝑥7&4565 + 5,1𝑥7&7# + 2,8𝑥7&7$ + 2,3𝑥7&7%
9.3.4. Problema do caixeiro-viajante
• Restrições saída:
𝑥45657# + 𝑥45657$ + 𝑥45657% + 𝑥45657& = 1
𝑥7#4565 + 𝑥7#7$ + 𝑥7#7% + 𝑥7#7& = 1
𝑥7$4565 + 𝑥7$7# + 𝑥7$7% + 𝑥7$7& = 1
𝑥7%4565 + 𝑥7%7# + 𝑥7%7$ + 𝑥7%7& = 1
𝑥7&4565 + 𝑥7&7# + 𝑥7&7$ + 𝑥7&7% = 1
9.3.4. Problema do caixeiro-viajante
• Restrições chegada:
𝑥7#4565 + 𝑥7$4565 + 𝑥7%4565 + 𝑥7&4565 = 1
𝑥45657# + 𝑥7$7# + 𝑥7%7# + 𝑥7&7# = 1
𝑥45657$ + 𝑥7#7$ + 𝑥7%7$ + 𝑥7&7$ = 1
𝑥45657% + 𝑥7#7% + 𝑥7$7% + 𝑥7&7% = 1
𝑥45657& + 𝑥7#7& + 𝑥7$7& + 𝑥7%7& = 1
9.3.4. Problema do caixeiro-viajante
• Restrições de sub-rotas:
• Sub-rota de 2 nós?
• Sub-rota de 4 nós?
• Sub-rota de 3 nós?
9.3.5. Problema de Escalonamento
de Pessoal
• Consiste em alocar um conjunto de funcionários entre diferentes 
horários de trabalho;
• Os postos de atendimento devem atender sua demanda 
respeitando as restrições do sistema;
• Como as variáveis de decisão devem assumir valores inteiros, 
corresponde a um problema de programação inteira;
• Aplicações: enfermeiras, correios, bancos, centrais de atendimento 
telefônico, escala de funcionários em empresas de transporte;
9.3.5. Problema de Escalonamento
de Pessoal
• Considere uma empresa com 𝑗 (𝑗 = 1,… , 𝑛) turnos de trabalho;
• A empresa possui um custo diário 𝑐! de alocar um funcionário em 
um turno 𝑗;
• Uma quantidade mínima 𝑏8 de funcionários deve estar disponível 
em um determinado período 𝑘 (𝑘 = 1,… ,𝑚);
• Busca-se determinar a escala de funcionários que iniciará o trabalho 
no turno 𝑗 de forma a minimizar o custo total de mão de obra;
9.3.5. Problema de Escalonamento
de Pessoal
min𝑍 =b
!/#
0
𝑐!𝑥!
𝑠. 𝑎.
b
!
𝑥! ≥ 𝑏8 	 (𝑗 ∈ 𝑘)	 𝑘 = 1,… ,𝑚
𝑥!≥ 0	 𝑒	𝑖𝑛𝑡𝑒𝑖𝑟𝑜	 (𝑗 = 1,2, … , 𝑛)
9.3.5. Problema de Escalonamento
de Pessoal
• Exemplo 5: O banco PRINCE abriu agências bancárias e precisa 
contratar mão de obra. A escala da força de trabalho que será 
contratada deve ser definida. Busca-se escalonar os novos 
funcionários em turnos de trabalho de 8h consecutivas, de forma a 
satisfazer o nível de serviço desejado com o menor custo possível. O 
período correspondente a cada turno, além do custo diário por 
funcionário é apresentado na Tabela 1. Para que o nível de serviço 
seja atendido é necessário um número mínimo de funcionários por 
período, conforme Tabela 2. Formule o problema de programação 
inteira para determinar a mão de obra a ser contratada por turno, 
com o menor custo possível, respeitando as restrições.
9.3.5. Problema de Escalonamento
de Pessoal
Tabela 1 Tabela 2
Turno Período Custo diário por funcionário Período Número de funcionários necessários
1 06:01 – 14:00 R$ 100,00 06:01 – 08:00 22
2 08:01 – 16:00 R$ 80,00 08:01 – 10:00 35
3 10:01 – 18:00 R$ 85,00 10:01 – 12:00 54
4 14:01 – 22:00 R$ 130,00 12:01 – 14:00 42
5 22:01 – 06:00 R$ 150,00 14:01 – 16:00 60
16:01 – 17:00 44
17:01 – 18:00 35
18:01 – 20:00 30
20:01 – 22:00 25
22:01 – 06:00 18
𝑀𝑖𝑛	𝑍 = 100𝑥' + 80𝑥% + 85𝑥& + 130𝑥" + 150𝑥(
𝑠. 𝑎.
𝑥' ≥ 22
𝑥' + 𝑥% ≥ 35
𝑥' + 𝑥% + 𝑥& ≥ 54
𝑥' + 𝑥% + 𝑥& ≥ 42
𝑥% + 𝑥& + 𝑥" ≥ 60
𝑥& + 𝑥" ≥ 44
𝑀𝑖𝑛	𝑍 = 𝑥!
9.3.5. Problema de Escalonamento
de Pessoal
• Função objetivo:
𝑀𝐼𝑁	𝑍 = 100𝑥# + 80𝑥$ + 85𝑥% + 130𝑥& + 150𝑥3
9.3.5. Problema de Escalonamento
de Pessoal
• Restrições:
𝑥# ≥ 22	 (06: 01	– 	08: 00)
𝑥# + 𝑥$ ≥ 35	 (08: 01	– 	10: 00)
𝑥# + 𝑥$ + 𝑥% ≥ 54	 (10: 01	– 	12: 00)
𝑥# + 𝑥$ + 𝑥% ≥ 42	 (12: 01	– 	14: 00)
𝑥$ + 𝑥% + 𝑥& ≥ 60	 (14: 01	– 	16: 00)
𝑥% + 𝑥& ≥ 44	 (16: 01	– 	17: 00)
𝑥% + 𝑥& ≥ 35	 (17: 01	– 	18: 00)
𝑥& ≥ 30	 (18: 01	– 	20: 00)
𝑥& ≥ 25	 (20: 01	– 	22: 00)
𝑥3 ≥ 18	 (22: 01	– 	06: 00)
9.3.6. Problema de Corte
• Em diversos processos industriais, itens são produzidos a partir do 
corte de peças maiores;
• Estas peças podem estar disponíveis em estoque ou são fabricadas 
na própria indústria ou, ainda, compradas de terceiros;
• Essas peças podem ter apenas uma dimensão relevante para o 
problema de corte (unidimensional);
• Exemplo: o comprimento, tais como barras de aço, bobinas de 
papel, rolos de filme;
9.3.6. Problema de Corte
• Elas também podem ter duas dimensões (comprimento e largura);
• Exemplo: placas de madeira, tecido, chapas de aço; 
• Podem ter até três dimensões, tais como blocos de matéria-prima 
para colchões e travesseiros. 
• Será apresentado o problema de corte unidimensional;
9.3.6. Problema de Corte
• O problema consiste em cortar barras disponíveis de tamanho único 
𝐿, para a produção de 𝑚 tipos de itens (barras de tamanhos 
menores) com tamanhos 𝑙#, 𝑙$, …, 𝑙1, e demandas, 𝑏#, 𝑏$, …, 𝑏1, 
respectivamente;
• O objetivo é minimizar o número de barras usadas, dado um 
limitante superior de barras disponíveis 𝑛;
9.3.6. Problema de Corte
• Seja	𝑦' 	tal	que = #1 se	a	barra	i	é	usada
0 caso	contrário	
• 𝑥'! = número de vezes que o item 𝑗 é cortado na barra 𝑖;
9.3.6. Problema de Corte
min𝑍 =b
'/#
0
𝑦'
𝑠. 𝑎.
b
'/#
0
𝑥'! ≥ 𝑏! 	 𝑗 = 1,… ,𝑚
	
b
!/#
1
𝑙!𝑥'! ≤ 𝐿𝑦' 	 𝑖 = 1,… , 𝑛
𝑥'! ≥ 0	 𝑒	𝑖𝑛𝑡𝑒𝑖𝑟𝑜, ∀𝑖, 𝑗	|	𝑦' ∈ 0,1 , ∀𝑖
9.4. Modelagem de restrições especiais
• Variáveis binárias podem ser muito úteis para formular restrições 
especiais;
• Estas restrições têm por objetivo representar uma condição real 
difícil de ser modelada;
9.4. Modelagem de restrições especiais
• Exemplos de restrições especiais são:
• Restrições “ou – ou então” para 2 ou mais restrições;
• Restrições “se – então”;
• Decisões mutuamente excludentes;
• Restrições limitantes de decisões;
• Restrições para assumir um único valor;
• Representação de variáveis inteiras;
9.4.1. Restrições “ou – ou então”
• Considere o caso de uma restrição do tipo ≤;
• Neste caso, o lado direito impõe um limite para o quanto o lado 
esquerdo pode aumentar;
• Se o lado direito for muito grande (ou infinito), a restrição sempre 
será atendida;
• Logo, ela passa a não ter efeito e é como se não existisse;
• Esse artifício é usado para modelagem de condições do tipo “ou – 
ou então”;
9.4.1. Restrições “ou – ou então”
• Suponha o caso de uma formulação em que apenas uma de duas 
restrições deve ser atendida;
• Seja 𝑀 um valor extremamente grande comparado à região de 
viabilidade do problema;
• Por exemplo, suponha que duas restrições sejam definidas como:
3𝑥# + 2𝑥$ ≤ 18 +𝑀𝑦
	
𝑥# + 4𝑥$ ≤ 16 +𝑀 1 − 𝑦
𝑦 ∈ 0,1
9.4.1. Restrições “ou – ou então”
• De forma geral:
𝑎'#𝑥# + 𝑎'$𝑥$ +⋯+ 𝑎'0𝑥0 ≤ 𝑏' +𝑀𝑦
𝑎8#𝑥# + 𝑎8$𝑥$ +⋯+ 𝑎80𝑥0 ≤ 𝑏8 +𝑀(1 − 𝑦)
𝑦 ∈ {0,1}
9.4.1. Restrições “ou – ou então”
• No caso de 𝑚 restrições em que 𝐾 são atendidas:
𝑎##𝑥# + 𝑎#$𝑥$ +⋯+ 𝑎#0𝑥0 ≤ 𝑏# +𝑀𝑦#
⋮
𝑎1#𝑥# + 𝑎1$𝑥$ +⋯+ 𝑎10𝑥0 ≤ 𝑏1 +𝑀𝑦1
𝑦# +⋯+ 𝑦1 = 𝑚 − 𝐾
𝑦' , … , 𝑦1 ∈ {0,1}
9.4.2. Restrições “se – então”
• Suponha que 𝑥! e 𝑥' sejam duas deciões representadas por variáveis 
binárias;
• Suponha que a decisão 𝑥! = 1 só pode acontecer caso a decisão 
𝑥' = 1 também precise ocorrer;
• Essa condição pode ser modelada com a simples inequação:
𝑥' − 𝑥! ≥ 0
9.4.2. Restrições “se – então”
• Essa inequação permite que 𝑥' seja 0 ou 1;
• Caso 𝑥% = 1	 → 𝑥! = 0 ou 𝑥! = 1;
• Caso 𝑥% = 0 → 𝑥! = 0.
9.4.3. Decisões mutuamente excludentes
• Em muitos casos ocorrem situações em que apenas uma de duas 
variáveis deve ser escolhida;
• A modelagem matemática precisa garantir que se uma variável for 
igual a 1, a outra precise obrigatoriamente ser 0;
• Decisões mutuamente excludentes podem ser modeladas como:
𝑥' + 𝑥! = 1
𝑥' , 𝑥! ∈ 0,1
9.4.3. Decisões mutuamente excludentes
• Esse problema pode ser adaptado para 𝑗 variáveis de decisão:
𝑥# +⋯+ 𝑥! = 1
𝑥#, … , 𝑥! ∈ 0,1
9.4.4. Restrições limitantes de decisões
• Em alguns casos desejamos limitar a quantidade de variáveis que 
pode ser escolhida;
• Nesse caso podemos ter uma situação em que nenhuma variável 
seja escolhida;
• No caso em que no máximo uma das duas decisões possa
acontecer, temos:
𝑥' + 𝑥! ≤ 1
𝑥' , 𝑥! ∈ 0,1
9.4.4. Restrições limitantes de decisões
• Uma variação desse problema inclui o caso em que no máximo 𝑁 
variáveis possam ser escolhidas de um total de 𝑗 variáveis;
• A modelagem matemática para esse caso é:
𝑥# +⋯+ 𝑥! ≤ 𝑁
𝑥#, … , 𝑥! ∈ 0,1
9.4.5. Restrições para assumir um único valor
• Em alguns casos desejamos que uma função assuma somente um 
de 𝑁 valores possíveis;
• Nesse caso, podemos utilizar variáveis binárias para realizar a 
modelagem matemática;
• Um exemplo dessa modelagem é:
3𝑥# + 2𝑥$ = 6𝑦# + 12𝑦$ + 18𝑦%
𝑦# + 𝑦$ + 𝑦% = 1
𝑦#, 𝑦$, 𝑦% ∈ 0,1
9.4.6. Representação de variáveis inteiras
• Variáveis binárias também podem ser utilizadas para representar 
variáveis inteiras genéricas;
• Considere uma variável inteira genérica 𝑥 tal que seus limites sejam:
0 ≤ 𝑥 ≤ 𝑢
• E 𝑁 seja definido como o inteiro tal que:
2? ≤ 𝑢 ≤ 2?@#
9.4.6. Representação de variáveis inteiras
• A representação genérica de 𝑥 é:
𝑥 =b
'/A
?
2'𝑦'
• Por exemplo, considere a restrição a seguir (𝑁 = 2):
𝑥# ≤ 5
𝑥# = 𝑦A + 2𝑦# + 4𝑦$
𝑦A, 𝑦#, 𝑦% ∈ 0,1
Pesquisa Operacional I 
(CEP/CT025) – Aula 08
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br