Apostila de Pesquisa Operacional II

Prévia do material em texto

Coronel Fabriciano 
Agosto de 2009 
Professor: Aloísio de Castro Gomes Júnior Versão 1.0 
 
 
 
 
 
 
1.1. Principais Características de PPI 
 
Exemplo 1: Seja o seguinte PPL: 
 
Uma confeitaria produz dois tipos de bolos de sorvete: chocolate e creme. Cada lote de bolo de 
chocolate é vendido com um lucro de 3 u.m. e os lotes de creme com um lucro de 1. Contratos 
com várias lojas impõem que seja produzido no mínimo 10 lotes de bolos de chocolate por dia 
e que o total de lotes fabricados nunca seja inferior a 20. O mercado só é capaz de consumir 
40 lotes de bolo de creme e 60 de chocolate. 
 
As máquinas de preparação de sorvete disponibilizam 180 horas de operação, sendo que cada 
lote de bolo de chocolate consome 2 horas de trabalho e cada lote de bolo de creme 3 horas. 
 
Determinar o esquema de produção que maximize os lucros com a venda dos bolos de sorvete. 
 
Modelando: 
 
1. Escolha da Variável de Decisão 
 
𝑥𝑖 ≡ Quantidade de lotes do bolo de sorvete do tipo 𝑖 = 
1 = 𝑐𝑕𝑜𝑐𝑜𝑙𝑎𝑡𝑒
2 = 𝑐𝑟𝑒𝑚𝑒
 fabricados. 
 
 
2. Elaboração da Função Objetivo 
 
𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 3𝑥1 + 𝑥2 
 
3. Formulação das Restrições Tecnológicas 
 
3.1. Restrição associada à disponibilidade de maquinaria. 
 
2𝑥1 + 3𝑥2 ≤ 180 
 
3.2. Restrição do número de lotes de bolos de creme no mercado 
 
𝑥2 ≤ 40 
 
3.3. Restrição do número de lotes de bolos de chocolate no mercado 
 
𝑥1 ≤ 60 
 
3.4. Restrições associadas aos contratos com as lojas 
 
𝑥1 ≥ 10 
 
𝑥1 + 𝑥2 ≥ 20 
Pesquisa Operacional para a Engenharia II 3 
 
 
4. Restrições de Não-negatividade e integralidade 
 
𝑥1, 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠 
 
Neste caso, as variáveis são consideradas inteiras, pois não se pode vender partes de um lote 
de produto. 
 
Resumindo-se tem o seguinte modelo: 
 
𝑚𝑎𝑥 𝑍 = 3𝑥1 + 𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 2𝑥1 + 3𝑥2 ≤ 180
𝑥1 ≤ 60
𝑥2 ≤ 40
𝑥1 ≥ 10
𝑥1 + 𝑥2 ≥ 20
𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
A resolução gráfica do problema é apresentada na Fig. 1. 
 
 
Figura 1: Solução Gráfica do Problema da Confeitaria 
 
Fazendo-se a análise dos pontos candidatos a solução ótima, obtém-se os dados apresentados 
na Tab. 1. 
 
 
 
A 
B 
C D 
E 
F 
1X
2X10 20 30 40 50 60 
10 
30 
40 
50 
Pesquisa Operacional para a Engenharia II 4 
 
Tabela 1: Soluções Candidatas a solução ótima 
Pontos Examinados Coordenadas (𝒙𝟐, 𝒙𝟏) Valor da Função 
A (40,10) 70 
B (40,30) 130 
C (20,60) 200 
D (0,60) 180 
E (0,20) 60 
F (10,10) 40 
 
Todos os pontos candidatos a solução ótima do problema apresentam coordenadas inteiras. 
Mas na maioria dos problemas isto não acontece. Vamos pegar outro exemplo. 
 
Exemplo 2: Seja o seguinte PPI: 
 
 
𝑚𝑎𝑥 𝑍 = 𝑥1 + 19𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 𝑥1 + 20𝑥2 ≤ 50
𝑥1 + 𝑥2 ≥ 20
𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
Sabe-se que a solução contínua deste PPI é: 
 
𝑥1
∗ = 18,89
𝑥2
∗ = 1,58
𝑍∗ = 48,82
 
 
Tentativa de arredondamento dos valores das variáveis 
 
1ª Possibilidade: 
 
𝑥1
∗ = 19
𝑥2
∗ = 2
 
 
Solução inviável: viola a 1ª restrição do problema 
 
2ª Possibilidade: 
 
𝑥1
∗ = 19
𝑥2
∗ = 1
𝑍∗ = 38
 
 
3ª Possibilidade: 
 
𝑥1
∗ = 18
𝑥2
∗ = 2
 
 
Solução inviável: viola a 1ª restrição do problema 
 
 
Pesquisa Operacional para a Engenharia II 5 
 
4ª Possibilidade: 
 
𝑥1
∗ = 18
𝑥2
∗ = 1
𝑍∗ = 37
 
 
Conclusão (errada): 
 
A melhor possibilidade é a 2ª com 𝑍∗ = 38, 𝑥1
∗ = 18 e 𝑥2
∗ = 1. 
 
Na verdade, a solução ótima deste problema é 𝑍∗ = 48, 𝑥1
∗ = 10 e 𝑥2
∗ = 2. 
 
Portanto o erro cometido ao se arredondar as variáveis é de aproximadamente 21 % 
 
Observações: 
 
 Em inúmeras situações, as variáveis de decisão não poderão admitir um valor contínuo: 
Problemas envolvendo pessoas, configurações, objetos físicos, etc. 
 
 Tratar problemas que possuem esta natureza inteira empregando os métodos já 
estudados não é indicado. 
 
 Estes problemas devem ser tratados empregando-se técnicas específicas. 
 
A Fig.2 apresenta uma situação comum, quando se este resolvendo PPI. Neste caso, a solução 
ótima do problema relaxado encontra-se distante da solução ótima do PI. 
 
 
Figura 2: Situação Comum Encontrada na Resolução de PPI 
 
Tipos de Problemas de Programação Inteira: 
 
 Programação Inteira (PI): quando todas as variáveis só podem assumir valores 
inteiros. 
 
 Programação Inteira Mista (PIM): quando existem variáveis inteiras e reais no 
mesmo problema. 
 
1X
2X
Solução 
ótima 
do problema 
relaxado 
Solução ótima 
do PI 
Pesquisa Operacional para a Engenharia II 6 
 
1.2. Modelagem de PPI 
 
A seguir são apresentados alguns exemplos de PPI e PPIM. 
 
Exemplo 1: Uma empresa siderúrgica possui três usinas e cada uma delas requer uma 
quantidade mensal mínima de minério para operar. A empresa usa minério de 3 minas. Cada 
uma das minas tem uma capacidade máxima de produção mensal estabelecida. Por imposições 
contratuais, o custo do minério é composto por um custo fixo mensal para cada mina (este 
valor é pago se for usado minério da mina), mais um custo de transporte (R$/t) que varia de 
acordo com a distância entre as minas e usinas, conforme tabela a seguir: 
 
 Usina 
Mina 1 2 3 
Cap. Máx. 
(t) 
Custo Fixo 
(R$) 
1 10 7 6,5 11500 50000 
2 8 9 10,8 16500 40000 
3 13 16 12,6 13000 30000 
Requisições 
(t/mês) 
12300 15400 13300 
 
Estabeleça uma estratégia ótima para usinas minimizarem seus gastos com a utilização do 
minério. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 2: O administrador de um hospital deseja determinar o escalonamento de 
enfermeiros. Para isso ele organiza um sistema de plantão dividindo o dia em 8 períodos de 3 
horas. A tabela a seguir mostra o número mínimo de enfermeiros que devem estar presentes 
em cada horário. 
 
Horário 24-3 3-6 6-9 9-12 12-15 15-18 18-21 21-24 
Nº enf. 30 20 40 50 60 50 40 40 
 
Cada enfermeiro cumpre um plantão normal de 6 horas, que pode começar apenas no início de 
cada turno. Alguns enfermeiros podem ser solicitados para estender o plantão por mais 3 
horas seguidas. A hora extra custa 50% mais cara. Em cada plantão, não mais que 40% dos 
enfermeiros podem fazer hora extra. Como o administrador deve escalar os enfermeiros? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 8 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 3: A LCL Tecnologia tem que planejar seus gastos em Pesquisa e Desenvolvimento 
para os próximos cinco anos. A empresa pré-selecionou quatro projetos e deve escolher dentre 
estes quais priorizar. Os dados relevantes ao problema encontram-se a tabela a seguir. Nela 
também se encontra a disponibilidade de capital a ser alocado em cada um dos anos, bem 
como o valor presente líquido de cada projeto. Como todos os projetos apresentam VPL 
positivos, todos seriam candidatos. Vale notar que existeuma limitação no valor a ser 
investido anualmente. 
 
Dados relativos à alocação de recursos em projetos 
 Capital Requerido em mil R$ 
Projeto 
VPL 
(mil R$) 
Ano 1 Ano 2 Ano 3 Ano 4 Ano 5 
1 105,99 70 15 0 20 20 
2 128,90 80 20 25 15 10 
3 136,14 90 20 0 30 20 
4 11,38 50 30 40 0 20 
Capital Disponível 200 70 70 70 70 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 9 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 4: A LCL Equipamentos Ltda. produz três tipos de furadeiras, que necessitam de 
tempos diferentes na linha de montagem. Para que cada tipo de furadeira seja fabricada, um 
custo de preparação da fábrica é incorrido (ajustes que devem ser efetuados na linha de 
montagem). Suponha que todas as furadeiras do mesmo tipo serão produzidas de uma só vez 
(apenas uma preparação por tipo). Os dados relevantes à análise do problema encontram-se 
na tabela a seguir. Ache as quantidades a serem fabricadas para maximização do lucro do 
próximo mês. 
 
Dados relevantes ao problema de preparação de linhas de montagem 
 
Tipo 1 Tipo 2 Tipo 3 
Total 
Disponível 
Montagem 2h 3h 2,5h 600h 
Pintura 3h 2h 2,5h 500h 
Lucro unitário R$ 50,00 R$ 60,00 R$ 65,00 
Preparação R$ 5.000,00 R$ 4.000,00 R$ 3.000,00 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 10 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 5: A LCL Motores recebeu recentemente uma encomenda para produzir três tipos de 
motores. Cada tipo de motor necessita de um determinado número de horas de trabalho no 
setor de montagem e acabamento. A LCL pode terceirizar parte de sua produção. A tabela a 
seguir resume essas informações: 
 
Modelo 1 2 3 Total (h) 
Demanda (unidades) 3000 2500 500 
Montagem (h/unidade) 1,1 1,9 0,7 6.000 
Acabamento (h/unidade) 2,5 0,8 4,0 10.000 
Custo de Produção 50 90 120 
Terceirização 65 92 140 
 
Elabore o modelo de programação matemática que minimize os custos de produção. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 11 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.2.1 Casos Especiais 
 
I) Restrições ou-ou 
 
Exemplo 6: A Jobco usa uma única máquina para processar três tarefas. Os tempos de 
processamento, bem como os prazos de execução (em dias) para cada tarefa são 
apresentados na tabela a seguir. Os prazos de execução de cada tarefa são medidos a partir 
de zero, o tempo de início presumido da primeira tarefa. 
 
Tempos de Processamento e Prazos de Execução 
Tarefa 
Tempo de 
Processamento (dias) 
Prazo de 
Execução (dias) 
Multa por atraso 
(US$ / dia) 
1 5 25 19 
2 20 22 12 
3 15 35 34 
 
O objetivo do problema é determinar a seqüência que resulte na multa mínima por atraso para 
o processamento das três tarefas. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 12 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
II) Restrições do tipo: “pelo menos k de r restrições devem ser válidas” 
 
Exemplo 7: Supor que as restrições abaixo são mutuamente excludentes, isto é, apenas uma 
deve ser verificada: 
 
𝑥1 + 𝑥2 + 𝑥3 ≤ 10
4𝑥1 + 𝑥2 − 𝑥3 ≤ 12
𝑥2 + 2𝑥3 ≤ 8
3𝑥1 − 𝑥2 + 𝑥3 ≤ 8
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 13 
 
III) Linearização de PPI’s 
 
 
𝑍 = 𝑥1𝑥2 …𝑥𝑛 com 𝑥𝑗 ∈ 0, 1 ∀𝑗 = 1,2, … , 𝑛 é equivalente a: 
 
𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 − 𝑧 ≤ 𝑛 − 1
𝑧 ≤ 𝑥𝑗 ∀ 𝑗 = 1, … , 𝑛
𝑧 ≥ 0
𝑥𝑗 ∈ {0,1} ∀ 𝑗 = 1, … , 𝑛
 
 
 
Exemplo 8: Aplicar esta propriedade para linearizar o problema abaixo: 
 
𝑀𝑎𝑥 𝑍 = 3𝑥1 + 2𝑥2 + 𝑥3 − 9𝑥1𝑥2 + 4𝑥1𝑥2𝑥3
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 𝑥𝑗 ∈ {0,1} ∀ 𝑗 = 1, … , 𝑛
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.3. Método de Branch-and-Bound 
 
O método denominado de Branch-and-Bound (B&B) baseia-se na idéia de desenvolver uma 
enumeração inteligente dos pontos candidatos à solução ótima inteira de um problema. O 
termo branch (ramificação) refere-se ao fato de que o método efetua partições no espaço de 
soluções. O termo bound ressalta que a prova de otimalidade da solução utiliza-se de limites 
calculados ao longo da enumeração. 
 
Seja o seguinte exemplo: 
 
Exemplo 1: Seja o seguinte PPI: 
 
𝑚𝑎𝑥 𝑍 = 5𝑥1 + 4𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 𝑥1 + 𝑥2 ≤ 5
10𝑥1 + 6𝑥2 ≤ 45
𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
Pesquisa Operacional para a Engenharia II 14 
 
 
Região de Soluções Viáveis do PPLI (pontos da grade) e do PR (área sombreada) 
 
 
Solução ótima do problema relaxado (PR): 
 
PPL1: 𝑥1 = 3,75; 𝑥2 = 1,25 e 𝑍 = 23,75 
 
 
Ramificação: 
 
𝑥1 ≤ 3 (PPL2) e 𝑥1 ≥ 4 (PPL3) 
 
 
Região de soluções do PPL2 e do PPL3 
1 
1X
2X
2 5 4 
1 
2 
3 
4 
5 
6 
𝑥1 ≤ 3 𝑥1 ≥ 4 
3 
1 
1X
2X
2 5 4 
1 
2 
3 
4 
5 
6 
𝑍 = 23,75 
Ótimo (contínuo) 
𝑥1 = 3,75; 𝑥2 = 1,25 
Pontos Inteiros Viáveis 
3 
Pesquisa Operacional para a Engenharia II 15 
 
 
 
 
Utilização da variável de ramificação 𝑥1 
 
Como no PPL4 o maior valor possível de Z é 22,5, a solução do PPL2 é a solução ótima do PPI. 
 
 
 
 
Árvore B&B alternativa para o exemplo dado 
 
 
 
Pesquisa Operacional para a Engenharia II 16 
 
O Algoritmo B&B 
 
Inicialização: Considerando um problema de maximização, estabeleça um limite inferior inicial 
𝑍 = −∞ para o valor dos coeficientes da função objetivo ótima do PPLI. 
 
Etapa 1: Selecione um PPL(i), o próximo subproblema a ser examinado. Resolva o PPL(i) e 
tente interpretá-la usando uma de três condições: 
 
a) O valor ótimo de 𝑍 do PPL(i) não pode dar um valor objetivo melhor que o limite inferior 
atual. 
 
b) O PPL(i) dá uma solução inteira viável melhor que o limite inferior atual. 
 
c) O PPL(i) não tem nenhuma solução viável. 
 
Surgirão dois casos: 
 
1) Se o PPL(i) for interpretada e uma solução melhor for encontrada, atualize o limite inferior. 
Se todos os sub-problemas tiverem sido descartados, pare; o PPLI ótimo está associado com o 
limite inferior finito atual. Se não existir nenhum limite inferior finito, o problema não tem 
solução viável. Senão determine, determine 𝑖 = 𝑖 + 1, e repita a etapa 1. 
 
2) Se o PPL(i) não for interpretado, vá para a etapa 2 para ramificar. 
 
Etapa 2 (Ramificação): Selecione uma das variáveis inteiras 𝑥𝑗 , cujo valor ótimo 𝑥𝑗
∗ na 
solução do PPL(i) não seja inteiro. Elimine a região: 
 
 𝑥𝑗
∗ < 𝑥𝑗 < 𝑥𝑗
∗ + 1 
 
(na qual 𝑣 define o maior inteiro ≤ 𝑣), criando dois sub-problemas de PL que correspondem a: 
 
𝑥𝑗 ≤ 𝑥𝑗
∗ e 𝑥𝑗 ≥ 𝑥𝑗
∗ + 1 
 
Determine 𝑖 = 𝑖 + 1, e vá para a etapa 1. 
 
As etapas dadas se aplicam a problemas de maximização. Para minimização, substituímos o 
limite inferior por um limite superior (cujo valor inicial é 𝑍 = ∞). 
 
 
Exemplo 2: Seja o seguinte PPI: 
 
min 𝑍 = 4𝑥1 + 3𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 8𝑥1+ 3𝑥2 ≥ 24
5𝑥1 + 6𝑥2 ≥ 30
1𝑥1 + 2𝑥2 ≥ 9
𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
 
Pesquisa Operacional para a Engenharia II 17 
 
Resolvendo pelo Método B&B: (Busca em Largura) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resolvendo pelo Método B&B: (Busca em Profundidade): 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
𝑍 = 17,54 
PPL1 
𝑥1 = 1,62; 𝑥2 = 3,69; 
LIA = 17,54 
LSA=+∞ 
𝑍 = 20 
PPL2 
𝑥1 = 1; 𝑥2 = 5,33; 
LSA=+∞ 
𝑍 = 18,5 
PPL3 
𝑥1 = 2; 𝑥2 = 3,5; 
LSA=+∞ 
𝑥1 ≤ 1 𝑥1 ≥ 2 
PPL4 
Não há soluções 
viáveis 
LSA=+∞ 
𝑍 = 21 
PPL5 
𝑥1 = 0,75; 𝑥2 = 6; 
LSA=+∞ 
𝑍 = 21 
PPL6 
𝑥1 = 3; 𝑥2 = 3; 
LSA=21 
𝑍 = 20 
PPL7 
𝑥1 = 2; 𝑥2 = 4; 
LSA=20 
𝑥2 ≤ 5 𝑥2 ≥ 6 𝑥2 ≤ 3 𝑥2 ≥ 4 
    
𝑍 = 17,54 
PPL1 
𝑥1 = 1,62; 𝑥2 = 3,69; 
LIA = 17,54 
LSA=+∞ 
𝑍 = 20 
PPL5 
𝑥1 = 1; 𝑥2 = 5,33; 
LSA=20 
𝑍 = 18,5 
PPL2 
𝑥1 = 2; 𝑥2 = 3,5; 
LSA=+∞ 
𝑥1 ≤ 1 𝑥1 ≥ 2 
𝑍 = 21 
PPL3 
𝑥1 = 3; 𝑥2 = 3; 
LSA=21 
𝑍 = 20 
PPL4 
𝑥1 = 2; 𝑥2 = 4; 
LSA=20 
𝑥2 ≤ 3 𝑥2 ≥ 4 
  
 
Pesquisa Operacional para a Engenharia II 18 
 
1.3. Exercícios 
 
(1) A Arte & Design Ltda. produz três tipos de estantes, que necessitam de tempos diferentes 
na linha de montagem. Para que cada tipo de estante seja fabricada, um custo de preparação 
da fábrica é incorrido. Suponha que todas as estantes do mesmo tipo serão produzidas de uma 
só vez (apenas uma preparação por tipo). A tabela a seguir resume os dados relevantes para a 
análise do problema: 
 
 
 Tipo 1 Tipo 2 Tipo 3 
Total 
Disponível 
Montagem 2h 5h 3,5h 400h 
Pintura 3h 2h 1,5h 800h 
Preço Unitário R$ 40,00 R$ 30,00 R$ 25,00 - 
Custo de 
Preparação 
R$ 5.000,00 R$ 2.000,00 R$ 5.000,00 - 
 
Sabendo que o mercado está disposto a absorver toda a produção da Arte & Design Ltda. e 
que as quantidades são necessariamente inteiras, determine quantas estantes de cada tipo 
devem produzidas para que a empresa maximize o seu resultado. 
 
 
(2) A SuperTech S/A está planejando os seus gastos em Pesquisa e Desenvolvimento para o 
próximo ano. A empresa selecionou quatro alternativas de projetos e deve escolher quais 
priorizar. Os dados do problema encontram-se na tabela a seguir: 
 
 Capital Requerido em mil R$ 
Projeto 
Valor 
Presente 
(mil R$) 
Ano 1 Ano 2 Ano 3 Ano 4 Ano 5 
1 100,05 70 15 0 20 20 
2 170,90 80 20 25 15 10 
3 130,14 90 30 0 40 20 
4 147,30 50 20 80 0 20 
Capital Disponível 150 80 90 100 70 
 
 
(3) Uma empresa de eletrodomésticos fabrica 3 produtos: relógios, rádios e torradeiras. Estes 
produtos têm os seguintes requerimentos: 
 
PRODUTOS 
CUSTO 
(R$) 
MÃO-DE-OBRA 
(HORAS) 
Relógio 7,00 2 
Rádio 10,00 3 
Torradeira 5,00 1 
 
A demanda máxima diária de relógios, rádios e torradeiras são, respectivamente, 200, 300 e 
150 unidades. O orçamento previsto de gastos diários é de no máximo R$ 2.000,00, bem 
como a disponibilidade máxima de mão-de-obra é de 600 horas por dia. O espaço disponível 
para estocagem é de no máximo 500 unidades. Os preços de vendas são de R$15,00 cada 
relógio, R$20,00 cada rádio e R$ 12,00 cada torradeira. Qual o “mix” de produção diária que 
maximiza o lucro total da empresa? 
 
 
Pesquisa Operacional para a Engenharia II 19 
 
(4) A companhia Coelho S.A. fabrica motores para brinquedos e pequenos aparelhos. O 
departamento de marketing está prevendo vendas de 6100 unidades do motor Roncam no 
próximo semestre. Esta é uma nova demanda e a companhia terá que testar sua capacidade 
produtiva. O motor Roncam é montado a partir de três componentes: o corpo, a base e a 
blindagem. Alguns destes componentes podem ser comprados de outros fornecedores, se 
houver limitações da Coelho S.A. Os custos de produção e os custos de aquisição em 
R$/unidade estão resumidos na tabela a seguir. 
 
Componente Custo de Aquisição 
(em R$) 
Custo de Produção 
(em R$) 
Corpo 10 8 
Base 20 20 
Blindagem 16 10 
 
A fábrica da Companhia Coelho S.A. tem três departamentos. O requisito de tempo em 
minutos que cada componente consome em cada departamento está resumido na próxima 
tabela. O tempo disponível na companhia para cada componente está listado na última linha. 
 
Componente 
Tempo de 
Preparação 
(em minutos) 
Tempo de 
Molde 
(em minutos) 
Tempo de 
Fabricação 
(em minutos) 
Corpo 2 4 2 
Base 5 2 4 
Blindagem 4 5 5 
Disponibilidade 49200 49200 49200 
 
Elabore um modelo, baseado em programação linear, que otimize o custo envolvido no 
atendimento ao pedido de vendas dos brinquedos. 
 
Sugestão: 
 
ijx
= a quantidade de componentes 






blindagemaforcomponenteoSe,3
baseaforcomponenteoSe,2
corpooforcomponenteoSe,1
i
a serem 
utilizados no modo 




fabricadoforcomponenteoSe,
adquiridoforcomponenteoSe,
F
A
j
. 
 
(5) Um fabricante de tiras metálicas recebeu um pedido para produzir 2000 tiras de tamanho 
2 cm  4 cm e 1000 tiras de 4 cm  7 cm. As tiras podem ser produzidas a partir de chapas 
maiores disponíveis nos tamanhos de 10 cm  3000 cm e 11 cm  2000 cm. O departamento 
técnico encarregado de planejar o atendimento ao pedido decidiu que os padrões de corte 
mostrados na figura a seguir são adequados para produzir as tiras encomendadas. Formule um 
modelo de programação linear que permita minimizar o material usado (ou minimizar as 
perdas) no atendimento à encomenda. 
 
 
Pesquisa Operacional para a Engenharia II 20 
 
 
(6) O departamento de polícia de uma cidade tem as necessidades mínimas apresentadas na 
tabela a seguir. Cada policial trabalha oito horas consecutivas. Os policiais devem iniciar o 
trabalho no início de um dos períodos mostrado na tabela. Monte um modelo de PL que 
minimize a quantidade diária de policiais. 
 
Período 1 2 3 4 5 6 
Horário 2-6 6-10 10-14 14-18 18-22 22-2 
Necessidade de Policiais 20 50 60 80 60 40 
 
(7) Uma grande fábrica de móveis dispõe em estoque de 250 metros de tábuas, 600 metros 
de pranchas e 500 metros de painéis de conglomerado. A fábrica normalmente oferece uma 
linha de móveis composta por um modelo de escrivaninha, uma mesa de reunião, um armário 
e uma prateleira. Cada tipo de móvel consome uma certa quantidade de matéria-prima, 
conforme a tabela a seguir. A escrivaninha é vendida por 100 unidades monetárias (u.m.), a 
mesa por 80 u.m., o armário por 120 u.m. e a prateleira por 20 u.m. Pede-se exibir um 
modelo de Programação Linear que maximize a receita com a venda dos móveis. 
 
 Quantidade de material em metros consumidos 
por unidade de produto 
Disponibilidade 
do Recurso (m) 
Escrivaninha Mesa Armário Prateleira 
Tábua 1 1 1 4 250 
Prancha 0 1 1 2 600 
Painéis 3 2 4 0 500 
Valor de 
Revenda (u.m.) 
100 80 120 20 
 
 
 
(8) Resolva os seguintes PPI através do método de B&B. Sempre selecione a variável 𝑥1 como 
a variável de ramificação no nó 0. Apresente a árvore obtida pelo método. (Utilize o software 
LINDO para encontrar a solução dos PPL(i)): 
 
 
8.1) 
max 𝑍 = 5𝑥1 + 8𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 𝑥1 + 𝑥2 ≤ 6
5𝑥1 + 9𝑥2 ≤ 45
𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
8.2) 
min 𝑍 = 5𝑥1 + 4𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 3𝑥1 + 2𝑥2 ≥ 5
2𝑥1 + 3𝑥2 ≥ 7
𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
8.3) 
max 𝑍 = 2𝑥1 + 3𝑥2
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 5𝑥1 + 7𝑥2 ≤ 35
4𝑥1 + 9𝑥2 ≤ 36𝑥1 , 𝑥2 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
8.4) Uma empresa produz três tipos de artigos A1, A2 e A3. As exigências de matéria-prima, 
espaço para estocagem, taxa de produção, assim como os lucros por artigo, são apresentados 
na tabela a seguir: 
 
Pesquisa Operacional para a Engenharia II 21 
 
Artigos A1 A2 A3 
Matéria prima (Kg/artigo) 2 2 1,3 
Espaço (m3/artigo) 2 2,5 2 
Taxa de produção (artigo / hora) 15 33 10 
Lucro (US$ / artigo) 5 6,5 5 
 
A quantidade total de matéria prima disponível por dia para todos os 3 artigos é de 180 Kg, o 
espaço disponível é de 230 m3 e utilizam-se 7h30min por dia para a produção. 
 
Quantas unidades de cada artigo devem ser produzidas por dia para se maximizar o lucro? 
 
 
(9) Resolva o seguinte PPI através do Método B&B, usando o LINGO: 
 
Obs.: Comece sempre pela variável de menor índice para fazer a ramificação. 
 
a) Fazendo uma busca em largura. 
b) Fazendo uma busca em profundidade. (Comece pelo lado esquerdo). 
 
 
max 𝑍 = 5𝑥1 + 7𝑥2 + 5,5𝑥3
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 2𝑥1 + 2𝑥2 + 1,3𝑥3 ≤ 190
2𝑥1 + 2,5𝑥2 + 2𝑥3 ≤ 250
4𝑥1 + 2𝑥2 + 6𝑥3 ≤ 450
𝑥1 , 𝑥2 , 𝑥3 ≥ 0 𝑒 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 22 
 
 
 
 
 
 
 
2.1. Notação e definições 
 
A) Grafos e Redes Direcionadas 
 
Um grafo direcionado 𝐺 = (𝑁, 𝐴) consiste de um conjunto de 𝑁 nós e outro 𝐴 de 
arcos. Os arcos são pares ordenados de nós distintos. 
 
A Figura 1 mostra um grafo direcionado onde: 
 
𝑁 = {1, 2, 3, 4, 5}  Conjunto de nós 
 
𝐴 = {(1,2), (1,3), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}  Conjunto de Arcos 
 
 
Figura 1: Grafo direcionado 
 
Quando o grafo é não direcionado, chamamos o conjunto de arcos de conjunto 
de arestas. 
 
Arcos  ligações de transporte de produtos. 
 
Nós  plantas, armazéns, clientes, pontos de ligação. 
 
𝑛 = número de nós da rede. 
 
𝑚 = número de arcos (ou arestas) da rede. 
 
 
1 
2 
3 
4 
5 
Pesquisa Operacional para a Engenharia II 23 
 
B) Caminho / Circuito / Ciclo / Árvore 
 
Caminho é uma seqüência alternada de nós e arcos, sem repetição de nós. 
(Figura 2) 
 
 
 
Figura 2: Exemplo de um Caminho 
 
Circuito é um caminho direcionado fechado. (Figura 3) 
 
 
 
Figura 3: Exemplo de um Circuito 
 
Ciclo é um caminho fechado. (Figura 4) 
 
 
 
Figura 4: Exemplo de um Ciclo 
 
 
 
1 
2 3 
4 
1 
2 3 
4 
1 
2 3 
4 
Pesquisa Operacional para a Engenharia II 24 
 
Árvore é um grafo conectado sem ciclos. (Figura 5) 
 
 
Figura 5: Exemplo de uma Árvore 
 
 
Problemas das Pontes de Königberg 
 
A cidade de Königberg, na Rússia, tem sete pontes que conectam quatro 
seções (como mostrado na Figura 6). 
 
Problema: percorrer as quatro seções e voltar ao local de partida cruzando 
cada ponte exatamente uma vez. Não havia limites no número de vezes que 
qualquer uma das quatro seções poderia ser visitada. 
 
A solução deste problema baseado em redes (EULLER) é que o trajeto 
desejado de ida e volta era impossível, devido a cada um dos quatros nós da 
rede estarem associados com um número ímpar de arcos, o que não permitia a 
entra e a saída distintas. 
 
 
Figura 6: Problema da Cidade de Königberg 
 
 
1 
2 3 4 
5 6 
Pesquisa Operacional para a Engenharia II 25 
 
2.2. Matriz de Incidência 
 
A estrutura de uma rede pode ser armazenada em matriz 𝑛 × 𝑚, que tem uma 
linha para cada nó e uma coluna para cada arco, dita matriz de incidência nó-
arco. 
 
A coluna correspondente ao arco (𝑖, 𝑗) tem apenas dois elementos não-nulos: 
+1 na linha do nó 𝑖 e −1 na linha do nó 𝑗. 
 
Geralmente um problema de fluxo em redes é dado pelo seguinte modelo de 
PL: 
 
𝑚𝑖𝑛 𝑍 = 𝐶𝑥
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 𝐴𝑥 = 𝑏
0 ≤ 𝑥 ≤ 𝑢
 
 
Onde: 
 
𝐶= vetor de custos nos arcos 
𝑥= vetor de fluxo nos arcos (variável de decisão) 
𝐴 = matriz de incidência nó-arco 
𝑏 = vetor de produção/demanda nos nós 
𝑢 =vetor de capacidade nos arcos 
 
 
Para cada nó 𝑖 temos se: 
 
𝑏𝑖 > 0  𝑖 é nó produtor 
𝑏𝑖 < 0  𝑖 é nó consumidor 
𝑏𝑖 = 0  𝑖 é nó de transbordo 
 
Exemplo 1: 
 
 
Rede para o exemplo 1 
 
Onde: em cada arco temos (custo, capacidade) e o custo é dado por unidade 
de fluxo que passa pelo arco. 
 
Construir o modelo de PL através da matriz de incidência nó-arco. 
1 
2 4 
3 
{4} {0} 
{-3} {-1} 
(15,40) 
(10,16) 
(1
0
,1
0
) 
(1
5
,1
0
) (
2
0
,1
0
) 
(5,15) 
Pesquisa Operacional para a Engenharia II 26 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Obs.: A matriz de incidência tem 2 × 𝑚 elementos não nulos dentre 𝑛 × 𝑚 
posições. 
 
De maneira geral, o problema de fluxo com custo mínimo (PFCM) pode ser 
formulado como: 
 
𝑚𝑖𝑛 𝑍 = 𝐶𝑖𝑗 𝑥𝑖𝑗
(𝑖 ,𝑗 )∈𝐴
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 𝑥𝑖𝑗
𝑗∈𝑁
− 𝑥𝑗𝑖
𝑗∈𝑁
= 𝑏𝑖 ∀𝑖 ∈ 𝑁 (1)
0 ≤ 𝑥𝑖𝑗 ≤ 𝑢𝑖𝑗 ∀(𝑖, 𝑗) ∈ 𝐴
 
Pesquisa Operacional para a Engenharia II 27 
 
 
Onde: 
 𝑏𝑖
𝑖∈𝑁
= 0 
 
A restrição (1) representa a Lei de Conservação de fluxo nos nós. Para nós de 
transbordo temos (fluxo que entra) =  (fluxo que sai). 
 
 
2.3. Problemas Clássicos de Fluxo em Redes 
 
A) Problema de Caminho Mínimo (PCM) 
 
O Problema de caminho mínimo determina o caminho mais curto entre um 
destino 𝑡 e uma origem 𝑠 em uma rede de transporte. 
 
Obs.: Fazendo-se 𝑏𝑠 = 1, 𝑏𝑡 = −1 e 𝑏𝑖 = 0 ∀ 𝑖 ≠ 𝑠, 𝑖 ≠ 𝑡, temos um PCM 
representado como um problema de fluxo com custo mínimo (PFCM). 
 
 
Exemplo 1: A fábrica de artigos LCL Adornos e Tecidos localizada em Lambari-
MG, deve entregar uma grande quantidade de peças na cidade de Baependi-
MG. A empresa quer saber qual o caminho mais curto que seu caminhão de 
entregas deve fazer para minimizar a distância total percorrida. A Figura 1 
mostra ilustra o mapa rodoviário entre as cidades em forma de rede. Construir 
um modelo matemático para resolver o problema. 
 
 
Figura 1: Representação em rede do exemplo da LCL Adornos e Tecidos 
 
Na rede da Figura 1, temos: 
 
Nó Cidade 
s Lambari 
A Três Corações 
B São Lourenço 
C São Thomé das Letras 
D Caxambu 
t Baependi 
 
s 
B 
A 
D 
C 
t {1} {-1} 
44 27 
50 
37 
41 45 
4 
Pesquisa Operacional para a Engenharia II 28 
 
Sugestão: use a matriz de incidência nó-arco para criar o modelo matemático 
para o exemplo anterior. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
O Algoritmo de Dijkstra 
 
O Algoritmo de Dijkstra foi desenvolvido para determinar o caminho mais curto 
entre o nó de origem e qualquer outro nó da rede. 
 
O algoritmo de Dijktra pode ser definido da seguinte maneira: 
 
Passo 1: Inserir o nó de origem na tabela de distâncias mínimas. Sua 
distância até o nó de origem é 0. 
 
Passo 2: Colocamos na tabela auxiliar todos os nós atingidos por este nó. Para 
os nós incluídos na tabela auxiliar, o nó de onde vem o caminho é o nó recém 
inserido na tabela de distâncias mínimas. A distância do nó de origem é a 
distância do arco percorrido somada com a distância do nó recém inserido na 
tabela de distâncias mínimas até a origem. 
 
Pesquisa Operacional para a Engenharia II 29 
 
Passo 3: O próximo nó a entrar na tabela de distâncias mínimas será o nó, 
entre os nós não marcados com um X, de menor distância até a origem. 
Marca-se estenó com um X. Caso este nó já esteja inserido na tabela de 
distâncias mínimas, devemos retornar ao passo 3. 
 
Passo 4: Após inserir o nó na tabela de distâncias mínimas, volta-se ao passo 
2 até que todos os nós do grafo tenham sido inseridos na tabela de distâncias 
mínimas. 
 
Passo 5: A tabela de distâncias mínimas indica a distância do caminho mínimo 
de cada nó até o nó de origem, e o nó de onde vem o caminho mínimo. 
 
 
Observações: 
 
1) Se todos os nós da tabela auxiliar já tiverem sido marcados e alguns nós 
ainda não tiverem sido incluídos na tabela de distância mínima, isto indica que 
não há caminho do nó de origem até os nós que não foram incluídos. 
 
2) O algoritmo de Dijkstra não é válido caso existam arcos com valores 
negativos. 
 
 
Exemplo 2: 
 
Determine o menor caminho entre as cidades de Lambari e Baependi (Exemplo 
1) usando o algoritmo de Dijkstra. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 30 
 
Compare o resultado obtido com o modelo de PL e o resultado obtido pelo 
algoritmo. 
 
Exemplo 3: 
 
Determine o menor caminho entre os nós 𝑠 e 𝑡 na rede abaixo usando o 
algoritmo de Dijkstra. 
 
 
Figura 2: Rede para exemplo 3. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
s 
B 
A 
E 
D 
t {1} {-1} 
5 
2 
12 
4 
8 6 
12 
C 
4 
2 
3 
1 
6 
Pesquisa Operacional para a Engenharia II 31 
 
B) Problema de Fluxo Máximo (PFM) 
 
O Problema de fluxo máximo consiste em enviar o máximo de fluxo de um 
dado nó origem 𝑠 até um nó destino 𝑡, em uma rede capacitada. 
 
Algumas Aplicações: 
 
- Maximizar o fluxo através da rede de suprimentos de uma empresa partindo 
de seus fornecedores para chegar a suas fábricas. 
- Maximizar o fluxo de petróleo através de um sistema de tubulações; 
- Maximizar o fluxo de veículos através de uma rede de transportes; 
- Maximizar o fluxo de água através de um sistema de aquedutos. 
 
Exemplo 1: Um produtor de gás natural tem uma rede de tubulações 
conforme apresenta na figura a seguir. As capacidades de cada parte da rede 
estão representadas em bilhões de litros por dia. Um problema ocorreu no 
ponto 𝑡, de modo que deseja-se fornecer a maior quantidade de gás possível 
da produção ao ponto 𝑡. Portanto, o problema é encontrar a máxima 
capacidade da rede entre 𝑠 e 𝑡 de modo que a máxima quantidade seja 
fornecida de 𝑠 para 𝑡. 
 
 
Figura 1: Representação em rede do exemplo 1 
 
Construir o modelo matemático deste problema, usando a matriz de incidência 
para isto. 
 
Obs.: Acrescentando um arco de 𝑡 para 𝑠 com capacidade infinita e com custo -
1 tem um PFM representado como um problema de fluxo com custo mínimo 
(PFCM). 
 
 
 
 
 
 
 
 
 
s 
B 
A 
t 
18 
4 
10 
15 
10 
Pesquisa Operacional para a Engenharia II 32 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 2: Dada a rede abaixo, construir o modelo matemático que 
possibilita determinar o fluxo máximo entre os nós 𝑠 e 𝑡. 
 
 
Figura 2: Representação em rede do exemplo 2 
 
 
 
 
 
 
 
 
 
s 
C 
A 
t 
4 
7 
5 
3 
5 
D 
E 
B 
2 
4 
4 
9 
6 
1 
Pesquisa Operacional para a Engenharia II 33 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercícios: 
 
A) Problema de Fluxo com Custo Mínimo 
 
 
(1) Modelar os problemas abaixo utilizando a matriz de incidência nó-arco: 
 
 
Rede para o Exercício (1) 
 
 
1 3 2 
0,85 
4 6 5 
{+3} {+2} {-4} 
{-4} {+5} {-2} 
(5) 
(2) 
(1) 
(2) (2) 
(1) 
(4) 
(1) 
(3) 
Pesquisa Operacional para a Engenharia II 34 
 
(2) Seja a matriz de incidência nó-arco abaixo. Construir a rede associada com esta matriz. 
 
 
𝐴 =
 
 
 
 
 
 
+1 +1 0 0 0 0 0 0
−1 0 +1 +1 +1 0 0 0
0 −1 −1 0 0 +1 0 0
0 0 0 0 −1 −1 +1 0
0 0 0 −1 0 0 0 +1
0 0 0 0 0 0 −1 −1 
 
 
 
 
 
 e 𝑏 =
 
 
 
 
 
 
4
3
2
0
−4
−5 
 
 
 
 
 
, 𝐶 = 2 4 5 6 3 1 5 7 
 
Onde 𝐶 é o vetor de custos dos arcos. 
 
 
B) Problema de Caminho Mínimo 
 
(3) Utilize o algoritmo de Dijkstra para determinar o caminho mínimo das redes abaixo: 
 
 
 
Rede 3.1 
 
 
 
Rede 3.2 
 
S 
B 
C 
T 
E 
D 
5 
1 
7 
2 
6 
4 
2 
A 
3 
7 
9 
5 
6 
7 
6 
7 
1 
S 
C 
B T 
E 
D 
5 
3 
8 
2 
6 
4 
2 
10 
A 
1 
7 
3 
1 
12 
7 
Pesquisa Operacional para a Engenharia II 35 
 
 
C) Problema de Fluxo Máximo 
 
(4) A empresa distribuidora de gás LCL GasoBras Ltda. deseja determinar a quantidade 
máxima de metros cúbicos por segundo de gás que pode bombear da estação de Campos-RJ 
para o centro consumidor do Rio de Janeiro, através de uma rede de gasodutos existentes. A 
Figura 12.1 ilustra a estrutura da rede de distribuição e apresenta a capacidade de fluxo 
máximo nos trechos (em metros cúbicos por segundo). 
 
 
 
Figura 12.1: Rede de Gasodutos que ligam Campos ao RJ 
 
Modele o problema anterior como um problema de fluxo com custo mínimo. 
 
(5) A Oleobrás dispõe de uma série de oleodutos que servem para transportar óleo do campo 
produtor para as refinarias. Considere o esquema abaixo onde são mostradas as possíveis 
ligações entre o campo C e a refinaria R, onde os círculos numerados são estações de 
bombeamento e os valores sobre os arcos indicam o fluxo máximo de óleo que pode ser 
bombeado entre as duas estações. 
 
 
Figura 13.1: Rede para o exercício (5) 
 
Formule o problema de maneira a determinar o fluxo máximo de óleo que pode chegar a 
refinaria R. 
 
(6) A empresa de logística Best Way S/A deseja saber a tonelagem máxima de material que 
ela pode transportar do Porto A para o Porto E através de vias fluviais. O diagrama abaixo 
apresenta os portos intermediários e a tonelagem máxima que pode sair de um porto para 
outro. Modele o problema. 
 
C 
2 
1 
R 
3 
4 
8 
10 
4 
6 
5 
3 
2 
7 
6 
12 
S 
B 
A 
T 
30 
20 
40 
30 
30 
C 
D 
20 
40 
Campos 
RJ 
Pesquisa Operacional para a Engenharia II 36 
 
 
Figura 14.1: Rede para o Exercício (6) 
 
 
(7) Mais exercícios podem ser encontrados nos livros citados na bibliografia. 
 
 
A 
C 
B 
F 
D 
E 
60 
65 
95 
45 
35 
15 
40 
90 
30 
Pesquisa Operacional para a Engenharia II 37 
 
 
 
 
 
 
 
 
3.1. Definição 
 
De maneira geral, o problema da mochila pode ser definido da seguinte forma: 
 
“Preencher uma mochila sem ultrapassar um determinado limite de peso, otimizando o valor 
do produto carregado.” 
 
O Problema da Mochila tem aplicação direta em diversos tipos de problemas, tais como: 
 
- Investimento de Capital; 
- Problema de corte e empacotamento; 
- Carregamento de Veículos. 
 
3.2. Formulação Matemática do Problema 
 
a) Existe apenas um item de cada objeto: 
 
(𝒊) Variáveis de Decisão: 
 
𝑥𝑗 ≡ 
1, se o objeto 𝑗 for colocado na mochila
0, caso contrário
 
 
(𝒊𝒊) Dados do Problema: 
 
𝐼 ≡ conjunto de objetos; 
𝐶 ≡ capacidade da mochila; 
𝑤𝑗 ≡ peso relativo do objeto 𝑗; 
𝑃𝑗 ≡ Valor de retorno proporcionado pelo objeto 𝑗; 
 
(𝒊𝒊𝒊) Função Objetivo:Objetivo: Maximizar a importância dos objetos levados na mochila 
 
𝑚𝑎𝑥 𝑍 = 𝑃𝑗𝑥𝑗
𝑗 ∈ 𝐼
 
 
Pesquisa Operacional para a Engenharia II 38 
 
 
(𝒊𝒗) Restrições: 
 
𝒊𝒗. 𝟏) Capacidade da mochila: 
 
 𝑤𝑗𝑥𝑗
𝑗 ∈ 𝐼
≤ 𝐶 
 
𝒊𝒗. 𝟐) Integralidade e não-negatividade: 
 
𝑥𝑗 𝜖 {0, 1} ∀𝑗 ∈ 𝐼 
 
b) Existem vários itens de cada objeto: 
 
 
(𝒊) Variáveis de Decisão: 
 
𝑥𝑗 ≡ quantidade de objetos do tipo 𝑗 a serem levados. 
 
 
(𝒊𝒊) Dados do Problema: 
 
Os mesmos do problema anterior, incluindo-se o dado abaixo: 
 
𝑑𝑗 ≡ quantidade de objetos do tipo 𝑗 disponíveis. 
 
 
(𝒊𝒊𝒊) Modelo Matemático: 
 
O modelo apresentado a seguir, este modelo é idêntico ao exemplo anterior com a inclusão do 
conjunto de restrições (b.3). 
 
 
Max 𝑍 = 𝑃𝑗𝑥𝑗
𝑗 ∈ 𝐼
(b.1)
Sujeito a: 𝑤𝑗𝑥𝑗
𝑗 ∈ 𝐼
≤ 𝐶 (𝑏. 2)
𝑥𝑗 ≤ 𝑑𝑗 ∀𝑗 ∈ 𝐼 (𝑏. 3)
𝑥𝑗 ∈ ℤ
+ ∀𝑗 ∈ 𝐼 (𝑏. 4)
 
 
 
c) Problema da Mochila 0-1 Múltipla 
 
 
(𝒊) Variáveis de Decisão: 
 
𝑥𝑖𝑗 ≡ quantidade de objetos do tipo 𝑗 a serem alocados na mochila 𝑖. 
 
 
(𝒊𝒊) Dados do Problema: 
 
Além dos dados apresentados no modelo do item a, temos: 
 
𝑀 ≡ conjunto de mochilas 
𝐶𝑖 ≡ capacidade da mochila 𝑖. 
Pesquisa Operacional para a Engenharia II 39 
 
 
(𝒊𝒊𝒊) Modelo Matemático: 
 
Max 𝑍 = 𝑃𝑗𝑥𝑖𝑗
𝑖∈𝑀𝑗∈ 𝐼
(c.1)
Sujeito a: 𝑤𝑗𝑥𝑖𝑗
𝑗 ∈ 𝐼
≤ 𝐶𝑖 ∀𝑖 ∈ 𝑀 (𝑐. 2)
 𝑥𝑖𝑗
𝑖∈ 𝑀
 ≤ 1 ∀𝑗 ∈ 𝐼 (𝑐. 3)
𝑥𝑖𝑗 ∈ {0,1} ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐼 (𝑐. 4)
 
 
 
O conjunto de restrições (c.3) garante que um mesmo objeto 𝑗 seja alocado a mais de uma 
mochila. 
 
Pesquisa Operacional para a Engenharia II 40 
 
 
 
 
 
 
Dado um conjunto de 𝑛 cidades e uma matriz de distâncias 𝑑𝑖𝑗 entre elas, o Problema do 
Caixeiro Viajante (PCV), ou Traveling Salesman Problem (TSP), consiste em estabelecer uma 
rota para um Caixeiro, iniciando seu percurso em uma cidade, chamada cidade origem, passar 
por todas as demais 𝑛 − 1 cidades uma única vez e retornar à cidade origem percorrendo a 
menor distância possível. 
 
Exemplo: 
 
 
Cidade 1 2 3 4 5 6 
1 0 2 1 4 9 1 
2 2 0 5 9 7 2 
3 1 5 0 3 8 6 
4 4 9 3 0 2 5 
5 9 7 8 2 0 2 
6 1 2 6 5 2 0 
 
A representação gráfica para este problema é apresentada abaixo: 
 
 
 
 
Pesquisa Operacional para a Engenharia II 41 
 
Uma possível solução para este exemplo seria 𝑆 = (1 4 2 5 3 6), esta solução é 
representada abaixo: 
 
 
 
Para esta solução a distância total percorrida é 𝑑𝑖𝑠𝑡 = 𝑑14 + 𝑑42 + 𝑑25 + 𝑑53 + 𝑑36 + 𝑑61 = 4 + 9 + 7 +
8 + 6 + 1 = 35 𝑢. 𝑑. 
 
Se 𝑑𝑖𝑗 = 𝑑𝑗𝑖 diz-se que o PCV é simétrico. Caso contrário ele é dito assimétrico. 
 
Para o PCV simétrico há 𝑛 − 1 ! 2 soluções possíveis. Portanto, para 𝑛 = 20 há 6 × 1016 soluções 
possíveis. Supondo que um computador avalie uma solução (rota) em 10−8 segundos, seriam 
necessários 6 × 108 segundos ou 168.951 horas ou 7.039 dias ou 19 anos para se encontrar uma 
solução por enumeração completa de todas as possíveis soluções. 
 
 
4.1. Modelagem Matemática 
 
(𝑖) Variáveis de decisão 
 
 𝑥𝑖𝑗 ≡ 
1, se o arco (𝑖, 𝑗) for utilizado, ou seja, é feita uma viagem da cidade 𝑖 para a cidade 𝑗
0, caso contrário
 
 𝑓𝑖𝑗 ≡ quantidade de fluxo enviada da cidade 𝑖 para a cidade 𝑗. 
 
(𝑖𝑖) Dados do Problema 
 
 𝐶 ≡ conjunto de cidades; 
 𝑑𝑖𝑗 ≡ distância entre a cidade 𝑖 e a cidade 𝑗. 
 
(𝑖𝑖𝑖) Função Objetivo: Minimizar a distância total percorrida 
 
Min 𝑍 = 𝑑𝑖𝑗 𝑥𝑖𝑗
𝑗 ∈𝐶𝑖∈𝐶
 
 
(𝑖𝑣) Restrições: 
 
a) A cada cidade 𝑘 só chega um arco: 
 
 𝑥𝑖𝑘
𝑖∈𝐶
= 1 ∀𝑘 ∈ 𝐶 
 
Pesquisa Operacional para a Engenharia II 42 
 
 
b) De cada cidade k só sai um arco: 
 
 𝑥𝑘𝑗
𝑗 ∈𝐶
= 1 ∀𝑘 ∈ 𝐶 
 
c) Exceto para a cidade origem (primeira cidade), o fluxo que chega a uma cidade 𝑘 
menos o que sai de 𝑘 é igual a 1: 
 
 𝑓𝑖𝑘
𝑖∈𝐶
− 𝑓𝑘𝑗
𝑗 ∈𝐶
= 1 ∀𝑘 ∈ 𝐶 | 𝑘 ≠ 𝑂𝑟𝑖𝑔𝑒𝑚 
 
d) O fluxo máximo que passa em um arco usado no percurso é inferior a 𝑛 − 1, onde 𝑛 é o 
número de cidades: 
 
𝑓𝑖𝑗 ≤ 𝑛 − 1 𝑥𝑖𝑗 ∀𝑖 ∈ 𝐶, ∀𝑗 ∈ 𝐶 
 
e) Integralidade e não-negatividade: 
 
𝑥𝑖𝑗 ∈ 0, 1 ∀𝑖 ∈ 𝐶, ∀𝑗 ∈ 𝐶 
𝑓𝑖𝑗 ≥ 0 ∀𝑖 ∈ 𝐶, ∀𝑗 ∈ 𝐶 
 
 
4.2. Heurísticas Construtivas para o PCV 
 
4.2.1. Heurística do Vizinho Mais Próximo 
 
Nesta heurística, parte-se da cidade origem e adiciona-se a cada passo a cidade 𝑘 ainda não 
visitada cuja distância à última cidade visitada é a menor possível. O procedimento de 
construção termina quando todas as cidades forem visitadas, situação na qual é feita a ligação 
entre a última cidade visitada e a cidade origem. 
 
Exemplo: Considerando o exemplo mostrado anteriormente, determine uma solução para este 
problema usando a Heurística do Vizinho mais Próximo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 43 
 
4.2.2. Heurística de Bellmore e Nemhauser: 
 
Nesta heurística, adicionamos à rota corrente a cidade 𝑘 ainda não visitada que esteja mais 
próxima dos extremos da sub-rota, isto é, a cidade 𝑘 se liga a uma cidade que esteja em uma 
extremidade da sub-rota ou à outra extremidade. 
 
Exemplo: Considerando o exemplo mostrado anteriormente, determine uma solução para este 
problema usando a Heurística de Bellmore e Nemhauser. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4.2.3. Heurística da Inserção mais Barata 
 
Nesta heurística, parte-se de uma sub-rota inicial envolvendo três cidades e, a cada passo, 
adiciona-se uma cidade k ainda não visitada entre as cidades i e j da sub-rota cujo custo de 
inserção 𝑠𝑖𝑗
𝑘 dado pela fórmula a seguir seja a menor possível. 
 
𝑠𝑖𝑗
𝑘 = 𝑑𝑖𝑘 + 𝑑𝑘𝑗 − 𝑑𝑖𝑗 
 
As figuras a seguir ilustram a inserção da cidade 𝑘 entre as cidades 𝑖 e 𝑗. 
 
Pesquisa Operacional para a Engenharia II 44 
 
 
 
A sub-rota inicial pode ser construída por um procedimento construtivo qualquer. 
 
Exemplo: Considerando o exemplo mostrado anteriormente, determine uma solução para este 
problema usando a Heurística de Inserção mais Barata. Obs.: Use a heurística do vizinho mais 
próximo para obter a sub-rota inicial. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4.3. Variantes do PCV 
Pesquisa Operacional para a Engenharia II 45 
 
 
Problema dos 𝒎-Caixeiros Viajantes: Neste problema há 𝑚-caixeiros e se deseja minimizar 
a distância total percorrida por todos eles. 
 
Problema do Caixeiro Viajante com Coleta Seletiva de Prêmios: um caixeiro viajante 
que coleta um prêmio, não-negativo, em cada cidade 𝑘 que ele visita e paga uma penalidade 
𝛾𝑘 para cada cidade 𝑘 que não visita, com um custo 𝑐𝑖𝑗 de deslocamento entre as cidades 𝑖 e 𝑗. 
O problema encontra-se em minimizar o somatório dos custos da viagem e penalidades, 
enquanto inclui na sua rota um número suficiente de cidades que o permita coletar um prêmio 
mínimo, 𝑝𝑚𝑖𝑛 , pré-estabelecido. 
 
Problema do Caixeiro Viajante com Janela de Tempo: neste problema o caixeiro viajante 
deve visitar as cidades dentro de um determinado intervalo de tempo, chamado de janela de 
tempo. 
 
4.4. Aplicações 
 
- Roteamentos de Veículos; 
 
- Roteamentode entrega postal; 
 
- Programação de transportes em células de manufatura; 
 
- Programação de máquinas em manufatura; 
 
- Otimização de perfurações de furos em placas de circuito impresso; 
 
- Produção de Aço, entre outras. 
 
Para mais informações consulte Goldbarg e Luna, 2005. 
 
4.5. Exercícios 
 
(1) Um vendedor de livros mora em Basin deve visitar uma vez por mês quatro clientes 
localizados em Wald, Bon, Mena e Kiln. A tabela abaixo dá as distâncias em quilômetros entre 
as diferentes cidades. 
 
Cidade Basin Wald Bon Mena Kiln 
Basin 0 120 220 150 210 
Wald 120 0 80 110 30 
Bon 220 80 0 160 185 
Mena 150 110 160 0 190 
Kiln 210 30 185 190 0 
 
O objetivo é minimizar a distância total percorrida pelo vendedor. 
 
Encontre uma rota para o vendedor usando: 
 
a) A heurística do vizinho mais próximo 
b) A heurística de Bellmore e Nemhauser 
c) A heurística de Inserção mais barata. Gere a sub-rota inicial pela heurística do vizinho 
mais próximo. 
 
 
Pesquisa Operacional para a Engenharia II 46 
 
(2) Para os problemas a seguir determine uma rota possível para o caixeiro viajante através: 
 
(i) do método da inserção mais barata (Gere a sub-rota inicial pela heurística do vizinho mais 
próximo.), 
(ii) do método vizinho mais próximo e 
(iii) da heurística de Bellmore e Nemhauser. 
 
2.1) 
cidade 1 2 3 4 5 
1 0 8 16 9 30 
2 8 0 15 5 22 
3 16 15 0 20 24 
4 9 5 20 0 25 
5 30 22 24 25 0 
 
a) Considere a cidade 3 como origem. 
b) Considere a cidade 5 como origem. 
 
2.2) 
cidade 1 2 3 4 5 6 
1 0 5 3 5 2 7 
2 5 0 8 9 5 9 
3 3 8 0 5 4 5 
4 5 9 5 0 4 11 
5 2 5 4 4 0 9 
6 7 9 5 11 9 0 
 
a) Considere a cidade 4 como origem. 
b) Considere a cidade 1 como origem. 
 
(3) Uma empresa localizada no ponto 1 da cidade de Coronel Fabriciano, precisa fazer a 
entrega de seus produtos em outros 6 pontos da cidade, indicados no mapa a seguir. 
 
 
 
Determine uma possível rota para o veículo da empresa, usando os três métodos heurísticos 
mostrados. 
 
 
1 
2 
3 
4 
5 
6 
7 
Pesquisa Operacional para a Engenharia II 47 
 
A distância (em km) entre as localidades é apresentada na tabela a seguir. 
 
Local 1 2 3 4 5 6 7 
1 0 - - - - - - 
2 1,6 0 - - - - - 
3 1,5 0,7 0 - - - - 
4 0,9 2,3 2,0 0 - - - 
5 1,8 2,6 2,1 5,4 0 - - 
6 1,5 2,5 2,0 2,5 1,9 0 - 
7 0,8 1,6 0,9 1,6 4,2 1,6 0 
 
 
Pesquisa Operacional para a Engenharia II 48 
 
 
 
 
 
 
 
Seja um conjunto de consumidores {1, 2, … , 𝑛} e um frota ilimitada de veículos, sediada em 
único depósito (ou centro de distribuição) 0. Para cada par (𝑖, 𝑗) é dado um custo 𝑐𝑖𝑗 . No 
problema básico de roteamento de veículos, a frota é homogênea, isto é, os veículos têm a 
mesma capacidade (𝑐𝑎𝑝). O PRV consiste em encontrar as rotas de custo mínimo para os 
veículos satisfazendo as seguintes condições: 
 
(𝑖) Toda rota começa e termina no depósito; 
 
(𝑖𝑖) A demanda 𝑞𝑖 de todos os consumidores deve ser atendida; 
 
(𝑖𝑖𝑖) Em toda rota, a demanda 𝑞𝑖 atendida não pode ultrapassar a capacidade 𝑐𝑎𝑝 do 
veículo. 
 
Exemplo: 
 
 
 
 
Pesquisa Operacional para a Engenharia II 49 
 
 
Uma possível solução para este problema seria: 
 
 
 
 
Rota Localidades (clientes) atendidos 
Demanda 
atendida 
1 CD – 1 – 3 – 9 – CD 35 
2 CD – D – C – A – 8 – D 32 
3 CD – 7 – B – CD 30 
4 CD – E – 6 – 4 – CD 32 
5 CD – 2 – 5 – CD 33 
 
 
5.1. Modelagem Matemática 
 
(𝑖) Variáveis de decisão 
 
𝑥𝑖𝑗 ≡ 
1, se o arco (𝑖, 𝑗) for utilizado, ou seja, é feita uma viagem do cliente 𝑖 para o cliente 𝑗
0, caso contrário
 
 
𝑓𝑖𝑗 ≡ quantidade de fluxo enviada do nó 𝑖 para o nó 𝑗. 
 
(𝑖𝑖) Dados do Problema 
 
𝐶 ≡ conjunto de consumidores; 
𝑉 ≡ conjunto de consumidores e o centro de distribuição, isto é, 𝑉 = {0, 1, 2, … , 𝑛} 
𝑐𝑖𝑗 ≡ custo de transporte entre o consumidor 𝑖 e o consumidor 𝑗. 
Pesquisa Operacional para a Engenharia II 50 
 
𝑞𝑘 ≡ demanda do consumidor 𝑘. No caso do depósito tem-se 𝑞0 = 0. 
𝑐𝑎𝑝 ≡ capacidade de cada veículo. 
 
(𝑖𝑖𝑖) Função Objetivo: Minimizar o custo total de transporte 
 
Min 𝑍 = 𝑐𝑖𝑗 𝑥𝑖𝑗
𝑗 ∈𝑉𝑖∈𝑉
 
 
O objetivo de reduzir custos poderá ser conseguido através da redução de: 
 
 Prazos de entrega (serviços de emergência, produtos perecíveis, etc...) 
 
 Caminhos a percorrer (combustível, manutenção, tempo de operação, ...) 
 
 Alocação de mão-de-obra 
 
 Riscos de acidentes ou avarias 
 
 Número de Veículos.. 
 
(𝑖𝑣) Restrições: 
 
f) À cada nó 𝑘, exceto aquele referente ao depósito 0, só chega um arco: 
 
 𝑥𝑖𝑘
𝑖∈𝑉
= 1 ∀𝑘 ∈ 𝐶 
 
g) De cada nó 𝑘, exceto aquele referente ao depósito 0, só sai um arco: 
 
 𝑥𝑘𝑗
𝑗 ∈𝑉
= 1 ∀𝑘 ∈ 𝐶 
 
h) No depósito 0, o número de arcos que saem é igual ao número de arcos que chegam: 
 
 𝑥0𝑗
𝑗 ∈𝑉
− 𝑥𝑖0
𝑖∈𝑉
= 0 
 
i) Exceto para o nó referente ao depósito, o fluxo que chega ao nó 𝑘 menos o que sai de 𝑘 
é igual à demanda associada ao 𝑘-ésimo nó: 
 
 𝑓𝑖𝑘
𝑖∈𝑉
− 𝑓𝑘𝑗
𝑗 ∈𝑉
= 𝑞𝑘 ∀𝑘 ∈ 𝐶 
 
j) O fluxo máximo que passa em um arco usado no percurso é inferior a 𝑐𝑎𝑝: 
 
𝑓𝑖𝑗 ≤ (𝑐𝑎𝑝)𝑥𝑖𝑗 ∀𝑖 ∈ 𝑉, ∀𝑗 ∈ 𝑉 
 
k) Integralidade e não-negatividade: 
 
𝑥𝑖𝑗 ∈ 0, 1 ∀𝑖 ∈ 𝑉, ∀𝑗 ∈ 𝑉 
 
𝑓𝑖𝑗 ≥ 0 ∀𝑖 ∈ 𝑉, ∀𝑗 ∈ 𝑉 
 
5.2. Aplicações do PRV 
 
Pesquisa Operacional para a Engenharia II 51 
 
Entre as principais aplicações, podemos destacar: 
 
 Distribuição de jornais 
 
 Distribuição de Manufaturados 
 
 Distribuição de produtos diversos 
 
 Distribuição de bebidas 
 
 Transporte escolar 
 
 Serviços de emergência 
 
 Roteamento de fluxo de informações em computadores 
 
5.3. Problemas de Roteamento de Veículos 
 
 PRV com janela de tempo; 
 
 PRV com frota heterogênea; 
 
 PRV com múltiplos depósitos; 
 
 PRV com coleta e entrega simultâneas; 
 
 PRV periódico; 
 
 PRV com entrega dividida, etc... 
 
 
5.4. Métodos Heurísticos para o PRV 
 
5.4.1. Heurísticas Construtivas 
 
A) Heurística do Vizinho mais Próximo 
 
Nesta heurística, a idéia é começar com um veículo no depósito e ir para o cliente mais 
próximo que ainda possa ser visitado sem desrespeitar as restrições do problema. Caso o 
veículo não possa atender mais clientes, deve-se retornar ao depósito e recomeçar o 
procedimento com outro veículo. O procedimento pára quando todos os clientes forem 
atendidos. 
 
Exemplo 1: Considere a matriz de custos a seguir, onde o depósito é referenciado pelo 
número 0, e as demandas de cada uma das 5 cidades. Sabendo que os veículos têm 20 
unidades de capacidade, determine as rotas de custo mínimo para os veículos. 
 
Cliente 0 1 2 3 4 5 Demanda 
0 0 6 7 8 9 10 0 
1 6 0 3 2 1 4 5 
2 7 3 0 5 3 4 9 
3 8 2 5 0 8 1 6 
4 9 1 3 8 0 5 4 
5 10 4 4 1 5 0 7 
 
 
 
Pesquisa Operacional para a Engenharia II 52 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
B) Heurística de Clarke e Wright 
 
Este método começa com um veículo atendendo um cliente e retornando ao depósito. A figura 
a seguir ilustra essa situação, onde se mostram duas rotas, uma atendendo ao cliente 𝑖 e a 
outra ao cliente 𝑗. 
 
 
 
 
A seguir, são feitas todas as possíveis combinações entre duas rotas de modo que um veículopossa ser eliminado e a distância de viagem, reduzida. Isto é, deve ser calculada a economia 
𝑠𝑖𝑗 entre todos os pares (𝑖, 𝑗) de clientes onde 𝑖 é um cliente da extremidade de uma rota e 𝑗 
uma extremidade de uma outra rota, conforme equação a seguir: 
 
𝑠𝑖𝑗 = 𝑑𝑖0 + 𝑑0𝑗 − 𝑑𝑖𝑗 
 
Pesquisa Operacional para a Engenharia II 53 
 
A figura seguinte ilustra a junção das duas rotas, uma envolvendo o cliente 𝑖 e o outro, o 
cliente 𝑗. 
 
 
 
É importante observar que as combinações de rotas são feitas apenas entre os clientes das 
extremidades das rotas. Além disso, só podem ser combinadas rotas que atendam às 
restrições de capacidade dos veículos envolvidos (e outras restrições porventura existentes, 
por exemplo, janelas de tempo). 
 
Calculadas todas as possíveis combinações (tarefa que é executada uma única vez), é 
realizada aquela combinação que produz a maior economia possível satisfazendo, 
naturalmente, as restrições estabelecidas. 
 
Exemplo 2: Resolva o Exemplo 1, usando a Heurística de Clarke e Wright. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 54 
 
5.5. Exercícios 
 
(1) Para os problemas a seguir determine uma rota possível para o caixeiro viajante através: 
 
(i) do método vizinho mais próximo e 
 
(ii) da heurística de Clarke e Wright 
 
 
 
1.1) 
Cliente 0 1 2 3 4 5 Demanda 
0 0 4 5 7 6 8 0 
1 4 0 8 16 9 30 10 
2 5 8 0 15 5 22 8 
3 7 16 15 0 20 24 5 
4 6 9 5 20 0 25 14 
5 8 30 22 24 25 0 15 
Capacidade do Veículo = 30 
 
 
1.2) 
Cliente 0 1 2 3 4 5 Demanda 
0 0 5 3 5 2 7 0 
1 5 0 8 9 5 9 14 
2 3 8 0 5 4 5 10 
3 5 9 5 0 4 11 8 
4 2 5 4 4 0 9 9 
5 7 9 5 11 9 0 12 
Capacidade do Veículo = 30 
 
 
(3) Uma empresa tem seu centro de distribuição localizado no ponto 1 da cidade de Coronel 
Fabriciano, precisa fazer a entrega de seus produtos em outros 6 pontos da cidade, indicados 
no mapa a seguir. Determine uma possível rota para os veículos da empresa, usando os dois 
métodos heurísticos mostrados. 
 
A distância (em km) entre as localidades e suas respectivas demandas são apresentada na 
tabela a seguir. 
 
Cliente 1 2 3 4 5 6 7 
Demanda 
(Pallets) 
1 0 - - - - - - 10 
2 1,6 0 - - - - - 12 
3 1,5 0,7 0 - - - - 15 
4 0,9 2,3 2,0 0 - - - 8 
5 1,8 2,6 2,1 5,4 0 - - 14 
6 1,5 2,5 2,0 2,5 1,9 0 - 20 
7 0,8 1,6 0,9 1,6 4,2 1,6 0 30 
 
Sabe-se, ainda, que cada veículo da empresa pode levar até 40 pallets dos produtos. 
 
Pesquisa Operacional para a Engenharia II 55 
 
 
 
 
 
1 
2 
3 
4 
5 
6 
7 
Pesquisa Operacional para a Engenharia II 56 
 
 
 
 
 
 
 
Definição: 
 
Consiste em designar um conjunto de operações a um determinado recurso e determinar a 
seqüência de processamento destas operações em cada recurso, bem como o instante de início 
e término do processamento de cada operação, dado um período do horizonte de 
planejamento (tipicamente uma semana). 
 
Exemplo: 
 
Considere uma fábrica que produz embalagens de papel para cimento, carvão, comida para 
cachorro entre outros. A matéria-prima básica para uma dada operação são rolos de papel. O 
processo de produção consiste em três estágios: a impressão do logo, a colagem dos lados da 
embalagem e a costura de uma ou ambas as pontas da embalagem. 
 
Cada estágio consiste de um número de máquinas que não são necessariamente idênticas. As 
máquinas em cada estágio podem diferir levemente na velocidade em que elas operam, o 
número de cores que elas podem imprimir ou o tamanho da embalagem que elas podem 
produzir. Cada ordem de produção indica uma dada quantidade de uma embalagem específica 
que é produzida e um prazo final de entrega, indicando quando a mesma deve ser finalizada. 
 
Os tempos de processamento para as diferentes operações são proporcionais ao tamanho da 
ordem de produção, isto é, o número de embalagens a serem produzidas. Um atraso nas 
entregas implica em uma penalidade de forma a perder freguesia e a magnitude da penalidade 
depende da importância da ordem de produção ou do cliente e do tempo de atraso da entrega. 
Um dos objetivos do seqüenciamento do sistema é minimizar o somatório destas penalidades. 
 
Quando a máquina é mudada de um tipo de embalagem para outro um tempo de preparação 
da máquina (setup) é necessário. O tamanho deste tempo de preparação da máquina depende 
das similaridades entre as duas ordens de produção consecutivas (o número de cores em 
comum, as diferenças entre os tamanhos das embalagens, entre outros). Um importante 
objetivo da programação da produção é a minimização do tempo total gasto em preparação de 
máquinas. 
 
6.1. Principais Elementos 
 
A) Recursos 
 
Um bem ou serviço, cuja disponibilidade é limitado ou não. 
 
Ex.: 
 Máquinas; 
 Matérias primas; 
 Mão de obra. 
 
 
Pesquisa Operacional para a Engenharia II 57 
 
B) Tarefas ou Operações 
 
Trabalho elementar cuja realização necessita de um certo número de unidades de tempo e/ou 
recursos. 
 
Ex.: 
 Impressão do desenho da embalagem; 
 Colagem dos lados da embalagem; 
 Costura da embalagem. 
 
As tarefas podem ser: 
 
Preemptiva: Quando a execução pode ser interrompida e ser reiniciada algum tempo mais 
tarde. 
 
Não preemptiva: uma vez iniciada, a execução não pode ser interrompida. 
 
C) Job: 
 
Representa uma seqüência conhecida de uma ou mais operações (tarefas) que representam 
uma seqüência tecnológica de fabricação de um produto. 
 
Os tempos de processamento também são associados às tarefas que compõem um job. Assim, 
num contexto de manufatura de produtos, um job pode representar a fabricação de um 
produto ou de um lote de família de produtos que possuem a mesma seqüência tecnológica de 
fabricação. Em algumas situações práticas, o conceito de tarefa coincide com o conceito de 
job, que é o caso, por exemplo, do problema de uma máquina. 
 
 
6.2. Principias Estruturas e Notações 
 
A) Dados Gerais 
 
Tempo de Processamento ( 𝒑𝒊𝒋 ): representa o tempo de processamento do job 𝑖 no recurso 
𝑗, ou seja, o intervalo de tempo no qual a tarefa é executada no recurso. 
 
Data de disponibilidade ( 𝒓𝒋 ): é a data na qual a tarefa 𝑗 estará disponível para começar a 
ser processada. 
 
Prazo de entrega ( 𝒅𝒋 ): é a data na qual o job 𝑗 deve ser finalizado. O job pode ser 
finalizado depois desta data, incorrendo em penalidades por atraso da produção. 
 
Prazo final de entrega ( 𝒅 𝒋 ): é a data final na qual o job 𝑗 deve ser finalizado, de maneira 
nenhuma o job poderá ser finalizado depois desta data 
 
Prioridade ( 𝒘𝒋 ): este dado diferencia uma tarefa da outra quanto à sua prioridade. 
 
Tempo de Preparação ( 𝒔𝒊𝒋 ): é o tempo necessário para preparar o recurso quando o job 𝑗 é 
processado imediatamente depois do job 𝑖. 
 
 
 
Pesquisa Operacional para a Engenharia II 58 
 
Estes dados podem ser visualizados no diagrama de Gantt a seguir: 
 
 
 
 
B) Variáveis Associadas às operações: 
 
𝑡𝑗 ≡ Data de início de execução 
 
𝐶𝑗 ≡ Data de conclusão 
 
𝐹𝑗 = 𝐶𝑗 − 𝑟𝑗 ≡ Tempo de fluxo (lead time) 
 
𝐿𝑗 = 𝐶𝑗 − 𝑑𝑗 ≡ Demora 
 
𝐷𝑗 = 𝑚𝑎𝑥{0, 𝐶𝑗 − 𝑑𝑗 } ≡ Atraso 
 
𝐸𝑗 = 𝑚𝑎𝑥{0, 𝑑𝑗 − 𝐶𝑗 } ≡ Antecipação 
 
 
C) Variáveis Gerais: 
 
Makespan ( 𝑪𝒎𝒂𝒙 ): maior data de conclusão, equivale a data de conclusão do último job a 
deixar o sistema. 
 
𝐶𝑚𝑎𝑥 = 𝑚𝑎𝑥{𝐶𝑗 }Demora Máxima ( 𝑳𝒎𝒂𝒙 ) 
 
𝐿𝑚𝑎𝑥 = 𝑚𝑎𝑥{𝐿𝑗 } 
 
Tempo médio de Fluxo ( 𝑭 ): 
 
𝐹 =
1
𝑛
 𝐹𝑖
𝑛
𝑖=1
 
 
 
D) Critérios de Otimização 
 
 Minimizar o makespan; 
 
 Minimizar o tempo médio de fluxo; 
 
 Minimizar a demora máxima; 
R
e
c
u
rs
o
 
Job 𝑖 Job 𝑗 
𝑠𝑖𝑗 𝑝𝑗 
𝑟𝑗 𝑑𝑗 𝑑 𝑗 Tempo 
Pesquisa Operacional para a Engenharia II 59 
 
 
 Minimizar o atraso máximo; 
 
 Minimizar os custos com antecipação e atraso da produção; 
 
 Etc. 
 
E) Principais Tipos de Problema 
 
(𝒊) Uma máquina: todos os produtos são processados em uma única máquina especializada 
 
 
 
(𝒊𝒊) Máquinas Paralelas: Alguns produtos passam por processos que podem ser realizados 
por uma máquina pertencente a um conjunto de máquinas idênticas ou não. As máquinas 
podem ser idênticas (possuem a mesma velocidade) ou diferentes (possuem diferentes 
velocidades). 
 
 
 
(𝒊𝒊𝒊) Job Shop: Um conjunto de máquinas executa um determinado número de operações 
sobre um conjunto de jobs, cada job possui sua própria seqüência tecnológica de produção. 
 
 
 
 
Pesquisa Operacional para a Engenharia II 60 
 
(𝒊𝒊𝒊) Flow Shop: É um caso particular do problema de Job Shop. Neste caso, todos os jobs 
possuem a mesma seqüência tecnológica de produção. 
 
 
 
F) Classificação de Graham et al. para os PPP ( 𝜶/𝜷/𝜸 ) 
 
 𝛼: descreve os tipos de recursos 
 
 𝛽: descreve as características das operações e recursos 
 
 𝛾: descreve o critério de otimização do problema 
 
Ex.: 
 
1 / 𝑟𝑗 / 𝐶𝑚𝑎𝑥 
 
Problema de seqüenciamento em uma máquina com uma data de disponibilidade para cada 
operação e minimizar o makespan como critério de otimização. 
 
G) Regras de Sequenciamento 
 
FIFO (First in – First out): Nesta regra as tarefas são sequenciadas de acordo com a data de 
chegada, ou seja, a primeira que chega é a primeira a ser processada. 
 
MTP (Menor tempo de processamento): Nesta regra as tarefas são seqüenciadas em ordem 
crescente do tempo de processamento. 
 
MDE (Data de Entrega mais cedo): Nesta regra as tarefas são seqüenciadas em ordem 
crescente da data de entrega desejada. 
 
 
6.3. Problema de Sequenciamento em uma Máquina (Single Machine Scheduling) 
 
 
Aplicado em situações onde o conjunto de máquinas pode ser tratado como uma máquina, ou 
quando se deseja determinar a sequência de produção da máquina gargalo do sistema. 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 61 
 
Sejam os seguintes dados de uma programação em uma máquina: 
 
 
 
 
 
Exemplo 1: Problema 1/𝑟𝑖 / 𝐶max - Problema de uma máquina, com data de liberação dos jobs 
e tendo o makespan como critério de otimização. 
 
Neste tipo de problema, uma sequência ótima é obtida pelo ordenamento dos jobs de acordo 
com a data de liberação (ordem crescente). 
 
Então para o exemplo dado, a sequência ótima seria: 
 
 
 
A representação gráfica é feita pelo Diagrama de Gantt e é apresentada a seguir: 
 
 
 
Sendo o Makespan igual a 37 u.t. 
 
Exemplo 2: Problema 1//𝐿𝑚𝑎𝑥 – Problema de uma máquina, tendo como critério de otimização 
a minimização do atraso máximo. 
 
Neste tipo de problema, uma sequência ótima é obtida pelo ordenamento dos jobs de acordo 
com o prazo de entrega (ordem crescente). 
 
Usando os dados do exemplo dado e considerando que 𝑟𝑖 = 0 ∀𝑖, ou seja, todos os jobs estão 
disponíveis para processamento na data 0. Então a sequência ótima deste problema é: 
 
Pesquisa Operacional para a Engenharia II 62 
 
 
 
A representação gráfica é feita pelo Diagrama de Gantt e é apresentada a seguir: 
 
 
 
Sendo o Atraso Máximo (𝐿𝑚𝑎𝑥 ) igual a 5 u.t. e o makespan (𝐶𝑚𝑎𝑥 ) igual a 37 u.t. 
 
 
6.3.1. Outras Características 
 
 
Outros critérios de otimização que podem ser usados: 
 
 Minimização do Atraso Total; 
 
 Minimização do Atraso e Antecipação; 
 
 Minimização do Tempo de Fluxo. 
 
Além disso, podem ser incorporadas outras características, tal como o Tempo de Preparação 
da Máquina (Setup). Este tempo pode ser dependente da sequência ou não. No segundo caso, 
este tempo é incorporado ao tempo de processamento. 
 
 
6.3.2. Exercícios 
 
 
(1) Sejam os seguintes dados sobre a programação em uma máquina: 
 
JOB J1 J2 J3 J4 J5 J6 
Data de Liberação (ri) 2 0 4 10 8 7 
Tempo de Processamento (pi) 5 4 8 7 6 3 
Prazo de Entrega (di) 18 19 20 21 15 28 
 
 
 
Pesquisa Operacional para a Engenharia II 63 
 
Determine a sequência de produção das seguintes formas: 
 
a) Menor data de entrega 
 
b) Menor tempo de processamento 
 
Calcule para ambos os casos: 
 
i) a data de início do processamento (t); 
ii) a data de conclusão da operação (C); 
iii) o tempo de fluxo (F); 
iv) a demora (L); 
v) o atraso (T) e 
vi) a antecipação (E). 
 
Determine, ainda, o makespan (Cmax) do problema, o atraso máximo, a demora máxima, o 
tempo médio e máximo de fluxo. 
 
c) Considerando que todos os Jobs estão disponíveis na data 0 (Problema 1//Lmax), determine 
qual seria a seqüência ótima de produção que minimiza a demora máxima. 
 
d) Considerando que não exista um prazo de entrega, determine qual seria a seqüência ótima 
de produção que minimiza o makespan (Problema 1/rj/Cmax). 
 
e) Construa o diagrama de Gantt, para as soluções (a), (b), (c) e (d) do problema. 
 
 
(2) Sejam os seguintes dados sobre a programação em uma máquina: 
 
JOB J1 J2 J3 J4 J5 J6 
Data de Liberação (ri) 4 1 5 0 3 2 
Tempo de Processamento (pi) 3 5 4 6 4 8 
Prazo de Entrega (di) 12 9 15 14 12 18 
 
Determine a sequência de produção das seguintes formas: 
 
a) Menor data de entrega 
 
b) Menor tempo de processamento 
 
Calcule para ambos os casos: 
 
i) a data de início do processamento (t); 
ii) a data de conclusão da operação (C); 
iii) o tempo de fluxo (F); 
iv) a demora (L); 
v) o atraso (T) e 
vi) a antecipação (E). 
 
Determine, ainda, o makespan (Cmax) do problema, o atraso máximo, a demora máxima, o 
tempo médio e máximo de fluxo. 
 
c) Considerando que todos os Jobs estão disponíveis na data 0 (Problema 1//Lmax), determine 
qual seria a seqüência ótima de produção que minimiza a demora máxima. 
 
Pesquisa Operacional para a Engenharia II 64 
 
d) Considerando que não exista um prazo de entrega, determine qual seria a seqüência ótima 
de produção que minimiza o makespan (Problema 1/rj/Cmax). 
 
 
e) Construa o diagrama de Gantt, para as soluções (a), (b), (c) e (d) do problema. 
 
 
6.4. Problema de Flow Shop (Flow Shop Scheduling) 
 
 
Um conjunto de 𝑛 jobs devem ser processados em um conjunto conhecido de 𝑚 máquinas. 
 
 
 
6.4.1. O Problema F2//𝑪𝒎𝒂𝒙 
 
 
Neste exemplo, temos um conjunto de 𝑛 jobs que devem ser processados em 2 máquinas. 
Uma sequência ótima para este problema é obtida através do algoritmo de Johnson, descrito a 
seguir. 
 
Sejam: 
 
 𝑎𝑖 = tempo de processamento do job 𝑖 na máquina 1; 
 𝑏𝑖 = tempo de processamento do job 𝑖 na máquina 2; 
 𝑈 = { 𝐽𝑖 ∶ 𝑎𝑖 ≤ 𝑏𝑖}; 
 𝑉 = { 𝐽𝑖 ∶ 𝑎𝑖 > 𝑏𝑖}. 
 
Algoritmo de Johnson 
 
 Ordene 𝑈 em ordem crescente de 𝑎𝑖. 
 Ordene 𝑉 em ordem decrescente de 𝑏𝑖. 
 A solução ótima é dada pelo conjunto ordenado 𝑈 seguido do conjunto ordenado 𝑉. 
 
 
Exemplo: 
 
Seja o seguinte problema: 
 
 
 
Deseja-se saber qual é a sequência ótima que minimize o makespan do problema. 
 
 
 
Pesquisa Operacionalpara a Engenharia II 65 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Para obter o makespan, deve-se construir o diagrama de gantt do problema: 
 
 
 
Makespan = ___________________ 
 
6.4.2. O Problema F3//𝑪𝒎𝒂𝒙 
 
Neste exemplo, temos um conjunto de 𝑛 jobs que devem ser processados em um conjunto de 
3 máquinas. Uma sequência ótima pode ser obtida fazendo-se uma adaptação do algoritmo de 
Johnson. Esta adaptação é mostrada a seguir. 
 
Sejam: 
 
 𝑎𝑖 = tempo de processamento do job 𝑖 na máquina 1; 
 𝑏𝑖 = tempo de processamento do job 𝑖 na máquina 2; 
 𝑐𝑖 = tempo de processamento do job 𝑖 na máquina 3; 
 
Se uma das condições a seguir for satisfeita, o algoritmo de Johnson adaptado pode ser 
aplicado. 
 
Condição 1: max 𝑏𝑖 ≤ min{𝑎𝑖} 
0 5 10 15 20 25 30 35 40 45
M1
M2
Pesquisa Operacional para a Engenharia II 66 
 
Condição 2: max 𝑏𝑖 ≤ min{𝑐𝑖} 
 
Algoritmo de Johnson Adaptado: 
 
 Crie duas máquinas fictícias MF1 e MF2; 
 Para a máquina fictícia 1 (MF1), faça: 𝑝 𝑖,𝑀𝐹1 = 𝑎𝑖 + 𝑏𝑖; 
Para a máquina fictícia 2 (MF2), faça: 𝑝 𝑖,𝑀𝐹2 = 𝑏𝑖 + 𝑐𝑖; 
Sequenciar as máquinas fictícias utilizando o algoritmo de Johnson original; 
Reescrever o problema original. 
 
 
 
Exemplo: 
 
Seja o seguinte problema: 
 
 
 
Determinar a sequência dos jobs de forma a minimizar o makespan do problema. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional para a Engenharia II 67 
 
 
Reescrevendo o problema e usando o gráfico de Gantt para determinar o makespan tem-se: 
 
 
 
Makespan = _______________ 
 
 
6.4.3. Exercícios 
 
(1) Sejam os seguintes dados sobre a programação em duas máquinas, sabe-se que todos os 
Jobs têm a mesma sequência tecnológica de fabricação: 
 
a) 
 
 J1 J2 J3 J4 J5 J6 J7 
M1 4 6 3 5 4 7 5 
M2 6 4 5 7 2 5 3 
 
b) 
 
 J1 J2 J3 J4 J5 J6 J7 J8 
M1 5 6 7 8 4 2 5 7 
M2 4 8 5 6 3 5 3 9 
 
Determine a sequência ótima de produção usando o Algoritmo de Johnson e determine o valor 
do makespan através do Diagrama de Gantt. 
 
(2) Sejam os seguintes dados sobre a programação em três máquinas, sabe-se que todos os 
Jobs têm a mesma sequência tecnológica de fabricação: 
 
a) 
 
 J1 J2 J3 J4 J5 J6 J7 
M1 4 6 7 5 4 7 5 
M2 3 4 3 2 2 1 3 
M3 4 8 5 6 3 5 3 
 
b) 
 
 J1 J2 J3 J4 J5 J6 
M1 4 6 3 5 4 7 
M2 1 4 5 3 2 4 
M3 5 6 7 8 5 6 
 
Determine a sequência ótima de produção usando o Algoritmo de Johnson adaptado e 
determine o valor do makespan através do Diagrama de Gantt. 
 
0 5 10 15 20 25 30
M1
M2
M3
Pesquisa Operacional para a Engenharia II 68 
 
 
6.5. Problema de Job Shop (Job Shop Scheduling) 
 
 
Um conjunto de máquinas executa um determinado número de operações sobre um conjunto 
de jobs, sendo que cada job possui sua própria seqüência tecnológica de produção. 
 
 
 
Exemplo: 
 
Sejam as seguintes informações sobre um problema de job shop com três máquinas, 6 jobs e 
16 operações: 
 
 
 
(𝑖) Sequenciar estes jobs usando a regra de sequenciamento FIFO 
 
 
Pesquisa Operacional para a Engenharia II 69 
 
 
Nesta primeira sequência temos as seguintes informações sobre cada job: 
 
JOB 𝑪𝒊 𝒅𝒊 𝑻𝒊 𝑬𝒊 𝑭𝒊 
A 16 10 6 0 16 
B 14 13 1 0 14 
C 19 12 7 0 19 
D 19 18 1 0 19 
E 14 14 0 0 14 
F 22 15 7 0 22 
Total 22 0 104 
Médio 3,6 0 17,3 
Máximo 7 0 22 
 
Pode-se observar que temos 5 ordens atrasadas, o atraso total foi de 22 u.t. e o fluxo médio 
foi de 17,3 u.t. e o makespan (𝐶𝑚𝑎𝑥 ) é igual a 22 u.t. 
 
(𝑖𝑖) Sequenciar estes jobs usando a regra de sequenciamento MDE 
 
 
 
Nesta sequência temos as seguintes informações sobre cada job: 
 
JOB 𝑪𝒊 𝒅𝒊 𝑻𝒊 𝑬𝒊 𝑭𝒊 
A 9 10 0 1 9 
B 11 13 0 2 11 
C 15 12 3 0 15 
D 22 18 4 0 22 
E 11 14 0 3 11 
F 22 15 7 0 22 
Total 14 6 90 
Médio 2,3 1 15 
Máximo 7 3 22 
 
Pode-se observar que temos 3 ordens atrasadas, o atraso total foi de 14 u.t. e o fluxo médio 
foi de 15 u.t. e o makespan (𝐶𝑚𝑎𝑥 ) é igual a 22 u.t., tem-se ainda uma antecipação total de 6 
u.t. 
 
 
Pesquisa Operacional para a Engenharia II 70 
 
 
(𝑖𝑖𝑖) Sequenciar estes jobs usando a regra de sequenciamento MTP 
 
 
 
 
Nesta sequência temos as seguintes informações sobre cada job: 
 
JOB 𝑪𝒊 𝒅𝒊 𝑻𝒊 𝑬𝒊 𝑭𝒊 
A 9 10 0 1 9 
B 11 13 0 2 11 
C 20 12 8 0 20 
D 19 18 1 0 19 
E 14 14 0 0 14 
F 19 15 4 0 19 
Total 13 3 92 
Médio 2,2 0,5 15,3 
Máximo 8 2 20 
 
Pode-se observar que temos 3 ordens atrasadas, o atraso total foi de 13 u.t. e o fluxo médio 
foi de 15,3 u.t. e o makespan (𝐶𝑚𝑎𝑥 ) é igual a 20 u.t., tem-se ainda uma antecipação total de 3 
u.t. 
 
Se levarmos em consideração o modelo matemático do problema (disponível em ARENALES et 
al., 2007) e usando como critério de otimização a minimização do makespan, tem-se que a 
solução deste problema é: 
 
 
Pesquisa Operacional para a Engenharia II 71 
 
 
Nesta sequência temos as seguintes informações sobre cada job: 
 
JOB 𝑪𝒊 𝒅𝒊 𝑻𝒊 𝑬𝒊 𝑭𝒊 
A 17 10 7 0 17 
B 19 13 6 0 19 
C 15 12 3 0 15 
D 19 18 1 0 19 
E 14 14 0 0 14 
F 19 15 4 0 19 
Total 21 0 103 
Médio 3,5 0 17,2 
Máximo 7 0 19 
 
Pode-se observar que temos 5 ordens atrasadas, o atraso total foi de 21 u.t. e o fluxo médio 
foi de 17,2 u.t. e o makespan (𝐶𝑚𝑎𝑥 ) é igual a 19 u.t. 
 
 
6.5.1. O Problema J2//𝑪𝒎𝒂𝒙 
 
 
O algoritmo de Johnson pode ser modificado para resolver o problema de job shop com duas 
máquinas. Para isto, siga os seguintes passos: 
 
 
Particione o conjunto de 𝑛 jobs em quatro tipos: 
 
 Tipo A: jobs processados somente na máquina 1; 
 
 Tipo B: jobs processados somente na máquina 2; 
 
 Tipo C: jobs processados primeiro na máquina 1; 
 
 Tipo D: jobs processados primeiro na máquina 2; 
 
Para obter a sequência ótima, faça: 
 
 Sequencie os jobs do tipo A e B em qualquer ordem – Sequências obtidas: 𝑆𝐴 e 𝑆𝐵; 
 
 Sequencie os jobs do tipo C e D de acordo com o algoritmo de Johnson para o problema 
F2//𝐶𝑚𝑎𝑥 - Sequências obtidas: 𝑆𝐶 e 𝑆𝐷; 
 
A sequência total ótima é dado por: 
 
 Máquina 1: 𝑆𝐶 , 𝑆𝐴 , 𝑆𝐷 
 
 Máquina 2: 𝑆𝐷 , 𝑆𝐵 , 𝑆𝐶 
 
 
Exemplo: 
 
Seja os dados a seguir: 
 
Pesquisa Operacional para a Engenharia II 72 
 
 
 
Determinar a sequência otimiza de forma a minimizar o makespan do problema. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Para obter o makespan deve-se construir o gráfico de Gantt. 
 
 
 
Makespan: ______________ 
0 5 10 15 20 25 30 35 40 45 50
M1
M2
Pesquisa Operacional para a Engenharia II 73 
 
Exercício: Seja os dados a seguir: 
 
 
 
Determinar a sequência otimiza de forma a minimizar o makespan do problema. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Para obter o makespan deve-se construir o gráfico de Gantt. 
 
 
 
Makespan: ______________ 
 
0 5 10 15 20 25 30 35 40 45 50
M1
M2
Pesquisa Operacional para a Engenharia II 74 
 
6.5.2. Exercícios: 
 
(1) Sejam as seguintes informações sobre um processo produtivo: