AULA 3 - Otimização em sistemas de produção (23pág)

Prévia do material em texto

1 
 
Otimização em sistemas 
de produção 
DESCRIÇÃO 
Recursos computacionais (algoritmos e softwares) para uma revolução no âmbito da pesquisa operacional (PO), com 
eficiência na aquisição e no tratamento dos dados nos sistemas logísticos de produção. 
 
PROPÓSITO 
Aprender a aplicar técnicas para a otimização em sistemas de produção, fundamental para a obtenção de resultados 
eficientes na área da logística. 
 
PREPARAÇÃO 
Antes de iniciar o estudo deste conteúdo, tenha em mãos uma calculadora, preferencialmente que execute cálculo de 
exponenciais. Como apoio para a solução dos problemas que serão apresentados, se possível, tenha um computador 
com aplicativo Microsoft Excel ou ApacheOpenOffice. 
 
INTRODUÇÃO 
A constante evolução no campo da pesquisa operacional (PO) tem desenvolvido importantes adventos nos ramos de 
metodologia e de aplicação de redes modelos de otimização de dados. Variadas inovações algorítmicas tiveram um 
grande impacto na área, assim como ideias da ciência da computação sobre estruturas e manipulação eficiente de 
dados. Consequentemente, algoritmos e softwares estão disponíveis e sendo usados rotineiramente para resolver 
grandes problemas que seriam de complexa resolução há duas ou três décadas. 
 
Entenderemos, ao longo deste estudo, como identificar os problemas de produção e os problemas de escala, e quais 
métodos podemos usar para resolvê-los. 
 
MÓDULO 1 
Identificar os problemas de produção 
 
CONCEITOS DE MODELO DE DECISÃO 
Os problemas de tomada de decisão podem ser classificados em duas categorias: modelos dedecisão determinísticos e 
probabilísticos. Em modelos determinísticos, boas decisões trazem bons resultados, você consegue o que espera, 
portanto, o resultado é determinístico, livre de risco. O resultado de uma decisão depende muito da influência de 
fatores incontroláveis e da quantidade de informação que o tomador de decisão possui para prever esses fatores. 
 
Aqueles que gerenciam e controlam sistemas de homens e equipamentos enfrentam o problema contínuo de melhorar 
o desempenho do sistema. O objetivo pode ser reduzir o custode operação, mantendo um nível aceitável de serviço e o 
lucro das operações atuais, fornecer um nível mais alto de serviço sem aumentar o custo, manter uma operação 
lucrativa enquanto atende os regulamentos governamentais impostos, ou "melhorar" um aspecto da qualidade do 
produto sem reduzir a qualidade em outro. Para identificar métodos de melhoria da operação do sistema, deve-se 
construir uma representação sintética ou modelo do sistema físico, que pode ser usado para descrever o efeito de uma 
variedade de soluções propostas. 
 
Um modelo é uma representação que captura "a essência" da realidade. Uma fotografia é um modelo da realidade 
retratada na imagem. A pressão arterial pode ser usada como um modelo da saúde de um indivíduo. Uma campanha 
piloto de vendas pode ser usada para modelar a resposta de indivíduos a um novo produto. Em cada caso, o modelo 
captura algum aspecto darealidade que tenta representar. 
 
Uma vez que um modelo captura apenas certos aspectos da realidade, pode ser inadequado para uso em uma 
aplicação específica, pois pode capturar os elementos errados da realidade. Temperatura é um modelo de condições 
climáticas, mas pode ser inapropriado se alguém estiver interessado em pressão barométrica. A fotografia de uma 
2 
 
pessoa é um modelo desse indivíduo, mas fornece poucas informações sobre seu desempenho acadêmico. Uma 
equação que prevê as vendas anuais de determinado produto é um modelo desse produto, mas tem pouco valor se 
estivermos interessados no custo de produção por unidade. Assim, a utilidade do modelo depende do aspecto da 
realidade que ele representa. 
 
Se um modelo captura os elementos apropriados da realidade, mas o faz de maneira distorcida ou enviesada, ele não 
será útil. Uma equação que prevê o volume de vendas mensal pode ser exatamente o que o gerente de vendas está 
procurando, mas pode levar a sérias perdas se produzir consistentemente altas estimativas de vendas. Um termômetro 
com leitura muito alta ou muito baixa seria de pouca utilidade em diagnósticos médicos. Um modelo útil é aquele que 
captura os elementos adequados da realidade com precisão aceitável. 
 
A OTIMIZAÇÃO MATEMÁTICA É O RAMO DA CIÊNCIA COMPUTACIONAL QUE BUSCA 
RESPONDER À PERGUNTA “O QUE É MELHOR?” PARA 
PROBLEMAS EM QUE A QUALIDADE DA RESPOSTA PODE 
SER EXPRESSA COMO UM VALOR NUMÉRICO. 
 
Tais problemas de otimização surgem em diversos ramos: Negócios, Economia, Finanças, Gestão, Química, Ciência dos 
Materiais, Física, Astronomia, Biologia Estrutural e Molecular, Engenharia, Ciência da Computação, Medicina e 
Arquitetura. A gama de técnicas disponíveispara resolvê-los é quase tão ampla. 
 
Um modelo de otimização matemática consiste em uma função objetivo e um conjunto de restrições expressos na 
forma de um sistema de equações ou desigualdades, e esses modelos são usados extensivamente em quase todas as 
áreas de tomada de decisão, como projeto de engenharia e seleção de portfólio financeiro. 
 
Se o modelo matemático é uma representação válida do desempenho do sistema, conforme demonstrado pela 
aplicação das técnicas analíticas apropriadas, então, a solução obtida do modelo também deve ser a solução para o 
problema do sistema. A eficácia de qualquer técnicade otimização se deve, em grande parte, ao grau de representação 
do modelo sobre o sistema estudado. Os problemas de otimização são onipresentes na modelagem matemática de 
sistemas do mundo real e cobrem um amplo conjunto de aplicações: Economia, Finanças, Química, Ciência dos 
Materiais, Astronomia, Física, Biologia Estrutural e Molecular, Engenharia, Ciência da Computação e Medicina. 
 
A modelagem de otimização requer tempoapropriado. 
 
A seguir, o procedimento geral a ser usado no processo de modelagem: 
 
 Descrever o problema. 
 Prescrever uma solução. 
 Controlar o problema avaliando e atualizando a solução ótima continuamente, enquanto altera os parâmetros 
e estrutura do problema. Claramente, sempre há ciclos de feedback entre essas etapas gerais. 
 
 FORMULAÇÃO MATEMÁTICA DO PROBLEMA 
Assim que você detectar um problema, pense e entenda-o para descrevê-lo adequadamente por escrito. Desenvolva 
um modelo matemático ou estrutura para representar a realidade a fim de conceber ou utilizar um algoritmo de 
solução de otimização. A formulação do problema deve ser validada antes de ser oferecida uma solução. Uma boa 
formulação matemática para otimização deve ser inclusiva – inclui o que pertence ao problema – e exclusiva – elimina 
o quenão pertence ao problema. 
 
 ENCONTRE UMA SOLUÇÃO IDEAL 
Esta é a identificação de um algoritmo de solução e seu estágio de implementação. O único bom plano é um plano 
implementado que permanece implementado! 
 
Interpretações gerenciais da solução ideal: Depois de reconhecer o algoritmo e determinar o módulo de software 
apropriado a ser aplicado, utilize-o para obter a estratégia ideal. Em seguida, a solução será apresentada ao tomador de 
decisão no mesmo estilo e linguagem usados pelo tomador de decisão. Isso significa fornecer interpretações gerenciais 
da solução estratégica em termos leigos, não apenas entregar ao tomador de decisão uma impressão docomputador. 
3 
 
 ANÁLISE PÓS-SOLUÇÃO 
Essas atividades incluem a atualização da solução ideal para controlar o problema. Neste mundo em constante 
mudança, é crucial atualizar periodicamente a solução ideal para qualquer problema de otimização. Um modelo que 
era válido pode perder a validade devido a mudanças nas condições, tornando-se uma representação imprecisa da 
realidade e afetando adversamente a capacidade decisiva do tomador de decisão. O modelo de otimização que você 
cria deve ser capaz de lidar com as mudanças. 
 
 IMPORTÂNCIA DO FEEDBACK E CONTROLE 
É necessário enfatizar a importância de pensar sobre os aspectos de feedback e controle de um problema de 
otimização. Seria umerro discutir o contexto do processo de modelagem de otimização e ignorar que uma solução 
imutável para um problema de decisão nunca deve ser esperada. A própria natureza do ambiente da estratégia ideal 
está mudando e, portanto, o feedback e o controle são partes importantes do processo de modelagem de otimização. 
 
O processo acima é descrito como os estágios de Análise, Projeto e Controle de Sistemas no fluxograma a seguir, 
incluindo as atividades de validação e verificação: 
 
 
PROGRAMAÇÃO LINEAR 
A programação linear (PL) costuma ser o tópico favorito de professores e alunos. A capacidade de introduzir a PL 
usando uma abordagem gráfica, a relativa facilidade do método de solução, a ampla disponibilidade de pacotes de 
software para PL e os numerosos aplicativos tornam a PL acessível até mesmo para alunos com conhecimentos 
matemáticos relativamente limitados. Além disso, a PL oferece uma excelente oportunidade para introduzir a ideia de 
análise what-if,devido às poderosas ferramentas para análise pós-otimização desenvolvidas para o modelo dePL. 
 
A programação linear é um procedimento matemático para determinar 
a alocação ótima de recursos escassos e que encontrou aplicação prática em quase todas as 
facetas dos negócios, da propaganda ao planejamento da produção. 
 
Problemas de transporte, distribuição e planejamento de produção agregada são os objetos mais típicos da análise por 
meio de PL. Na indústria do petróleo, por exemplo, um gerente de processamento de dados em uma grande empresa 
petrolífera estimou recentemente que de 5% a 10% do tempo do computador da empresa era dedicado ao 
processamento de PL e demodelos semelhantes aos de PL. 
 
Ao formular um problema de tomada de decisão como um programa linear, você deve verificaras seguintes condições: 
 
1. A função objetivo deve ser linear, por isso, verifique se todas as variáveis têm potência de 1 esão adicionadas 
ou subtraídas (não divididas ou multiplicadas). 
 
2. O objetivo deve ser a maximização ou a minimização de uma função linear e deve representar a meta do 
tomador de decisão. 
 
3. As restrições também devem ser lineares e sempre fechadas, das seguintes formas: ≥, ≤ ou =. 
4 
 
Veja a seguir um modelo de PL: 
 
Maximizar 𝒙𝟏 + 𝟏, 𝟓𝒙𝟐 
Sujeito a: 
2x1 + x2 ≤ 40 Restrição de mão de obra 
x1 + 2x2 ≤ 50 Restrição de material 
x1, x2 Não negativo 
 
VEJAMOS UM EXEMPLO DE UM PROBLEMA DE MISTURA 
A YDVQS Pizza é uma fabricante de pizzas congeladas. A empresa obtém um lucro líquido de R$1,00 para cada pizza 
regular e R$1,50 para cada pizza de luxo produzida. A empresa tem atualmente 150kg de mistura de massa e 50kg de 
mistura de cobertura. Cada pizza regular usa 1kg de mistura de massa e 0,125kg de mistura de cobertura. Cada pizza de 
luxo usa 1kg de mistura de massa e 0,25kg de mistura de cobertura. Com base na demanda anterior por semana, 
YDVQS pode vender pelo menos 50 pizzas regulares e pelo menos 25 pizzas de luxo.O problema é determinar o número 
de pizzas regulares e de luxo que a empresa deve produzir para maximizar o lucro líquido. Formule este problema como 
um problema de LP. 
 
Sejam x1 e x2 o número de pizzas regulares e de luxo, então a formulação PL é: 
 
Maximizar 𝒙𝟏 + 𝟏, 𝟓𝒙𝟐 
Sujeito a: 
x1 + x2 ≤ 150 Restrição de mistura de massa 
0,125 x1 + 0,5 x2 ≤ 50 Restrição de mistura de cobertura 
x1 ≥ 50 
x2 ≥ 25 
x1 ≥ 0, x2 ≥ 0 Não negativo 
 
ALGORÍTMO BRANCH AND BOUND (B&B) 
Um algoritmo B&B para um problema de minimização/minimização consiste, portanto, em trêscomponentes principais: 
 
 Bounding function 
Cálculo dos limites inferiores e/ou superiores para o valor da função objetivo do subproblema. 
 
 Strategy for selecting 
Uma estratégia para selecionar o subespaço de soluções a ser investigado na iteração atual. 
 
 Branching rule 
Regra de ramificação a ser aplicada se um subespaço, após a investigação, não puder ser descartado, 
subdividindo-o em dois ou mais subespaços a serem investigados em iteraçõessubsequentes 
 
As etapas do método branch and bound para determinar uma solução inteira ótima para um modelo de maximização 
(com ≤ restrições) podem ser resumidas da forma a seguir: 
 
1. Encontre a solução ótima para o modelo de programação linear com as restrições de númerointeiro relaxadas. 
 
2. Na raiz, nó 0, a solução relaxada deve ser o limite superior; a solução inteira arredondada, olimite inferior. 
 
3. Selecione a variável com a maior parte fracionária para ramificação. Crie duas restrições para essa variável, 
refletindo os valores inteiros particionados. O resultado será uma nova restrição ≤ e uma nova restrição ≥. 
 
4. Crie dois nós, um para a restrição ≤ e outro para a restrição ≥. 
 
5. Resolva o modelo de programação linear relaxado com a nova restrição adicionada em cadaum desses nós. 
5 
 
6. A solução relaxada é o limite superior em cada nó, e a solução inteira máxima existente (em qualquer nó) é o 
limite inferior. 
 
7. Se o processo produzir uma solução viável inteira com o maior valor limite superior dentrequalquer nó final, a 
solução inteira ideal foi atingida. Se uma solução inteira viável não aparecer, ramifique o nó com o maior limite 
superior. 
 
8. Volte ao passo 3. 
 
Vamos a um exemplo simples para entender o método: deve-se encontrar a solução para o seguinte problema: 
 
 
Olhando a restrição, vamos fazer x1 = 0 e determinar o valor de x2, e posteriormente x2 = 0 e determinar x2: 
 
 
Resolvendo o problema relaxado, tem-se: 
 
 Valor ótimo da solução: 39,06. 
 Valores das variáveis x1 = 1, 86 e x2 = 0. 
Logo, o valor de x1 não é inteiro, então dividimos o problema em dois subproblemas: 
 
 Um em que consideramos o valor de x1 ≥ 2, que vamos chamar de subproblema A. 
 Outro em que consideramos x1 ≤ 1, chamado de subproblema B. 
Subproblema A Subproblema B 
 
Subproblema A Subproblema B 
Max Z = 21x1 + 11x2 Max Z = 21x1 + 11x2 
Sujeito a: Sujeito a: 
7x1 + 4x2 ≤ 13 7x1 + 4x2 ≤ 13 
x1 ≥ 2 x1 ≤ 1 
x1, x2 ≥ 0 x1, x2 ≥ 0 
 
Não encontramos solução factível ao resolver o problema A: na restrição 7 × 2 = 14, não é menor do que 13. Então, 
aplicando o critério para poda, podemos eliminá-lo (teste de sondagem 1, o problema relaxado é infactível). 
 
Resolvendo o subproblema B, se temos x1 = 1, então x2 = 1, 5 e Z = 37, 5. Agora x2 não é inteiro, logo, 
6 
 
particionamos o problema em dois, considerando o subproblema C com a variável x2 ≤ 1 e o subproblema D com x2 
≥ 2. 
 
Subproblema C Subproblema D 
Max Z = 21x1 + 11x2 Max Z = 21x1 + 11x2 
Sujeito a: Sujeito a: 
7x1 + 4x2 ≤ 13 7x1 + 4x2 ≤ 13 
x1 ≤ 1 x1 ≤ 1 
x2 ≤ 1 x2 ≥ 1 
x1, x2 ≥ 0 x1, x2 ≥ 0 
 
A solução do subproblema C é igual a 32, x1 = 1 e x2 = 1, as duas variáveis são inteiras, logo, considerando o teste de 
sondagem (TS2), esse problema pode ser sondado por otimalidade. 
 
Resolvendo o subproblema D, temos Z = 37, x1 = 0, 72 e x2 = 2. Note que a variável x1 novamente não é inteira, 
então particionamos o subproblema, gerando dois novos subproblemas como mostramos a seguir: 
 
Subproblema E Subproblema F 
Max Z = 21x1 + 11x2 Max Z = 21x1 + 11x2 
Sujeito a: Sujeito a: 
7x1 + 4x2 ≤ 13 7x1 + 4x2 ≤ 13 
x1 ≤ 1 x1 ≤ 1 
x2 ≥ 2 x2 ≥ 1 
x1 ≤ 0 x1 ≥ 1 
x1, x2 ≥ 0 x1, x2 ≥ 0 
 
O subproblema F é infactível, logo, podemos usar T S1 e eliminá-lo. O subproblema E tem solução igual a 35,75, x1 = 
0 e x2 = 3,25. 
 
Subproblema G Subproblema H 
Max Z = 21x1 + 11x2 Max Z = 21x1 + 11x2 
Sujeito a: Sujeito a: 
7x1 + 4x2 ≤ 13 7x1 + 4x2 ≤ 13 
x1 ≤ 1 x1 ≤ 1 
x2 ≥ 2 x2 ≥ 2 
x1 ≤ 0 x1 ≤ 0 
x2 ≤ 3 x2 ≥ 4 
x1, x2 ≥ 0 x1, x2 ≥ 0 
 
No subproblema G, temos então x1 = 0 e x2 = 3, obtendo Z = 33. O problema H, com x4 = 4, é infactível. 
Obtemos a solução ótima no problema G. 
 
UTILIZANDO O SOLVER 
Para o Solver, vamos montar a planilha: 
7 
 
Captura de tela do Software Excel 
 
 Captura de tela do Software Excel 
 
 
As células têm o seguinte significado: 
D4:E4→ varáveis do problema 
F7 → =SOMARPRODUTO(D7:E7;D4:E4) 
G7 → limite da restrição 
D9 → =21*D4+11*E4 — função objetivo 
O Solver será: 
Definir objetivo → $D$9 
Para → Max 
Alterando células variáveis → $D$4:$E$4 
Restrição 1 → D4:E4 = número inteiro 
Restrição 1 → $F$7 ≤ $G$7 
Método de solução → LP Simplex 
 
 
 
 
Clicando em “Resolver” obtemos: 
8 
 
 
 
PROBLEMA DE ESCALA 
A otimização do cronograma é o processo de garantir que cada tarefa ou ação individual em um cronograma esteja 
alinhada com o seu objetivo final e pode ser usada por indivíduos e empresas para manter suas prioridades na 
vanguarda, ao definir os horários para a realização das tarefas. As empresas de entrega costumam usar a otimização do 
cronograma para garantir que uma rota de entrega seja planejada com a menor quilometragem possível e, portanto, 
como menor custo de combustível. 
 
Organizações cujos funcionários trabalham em vários turnos precisam programar trabalhadores suficientes para cada 
turno diário. Normalmente, os horários terão restrições, como "nenhum funcionário deve trabalhar em dois turnos 
consecutivos". Encontrar um cronograma que satisfaça todas as restrições pode muitas vezes ser computacionalmente 
complexo. 
 
Muitas empresas de logística fornecem serviços em massa aos clientes, mas, atualmente, também atendem uma 
crescente demanda por serviços de logística customizados e consideram modificar o modo de serviço. Especialmente, 
essas empresas tentam fornecer serviços de logística de customização em massa em vez de serviços de logística em 
massa. Otempo de conclusão é um índice importante para a qualidade desse serviço e o problema de programação de 
tempo é um dos principais da área. Inúmeras empresas de logística têm se dedicado a melhorar o desempenho da 
programação de tempo. 
 
Em produção, em logística, em serviços etc., é importante que se organize uma 
escala de trabalho a fim de obter uma maior eficiênciado processo. A alocação de máquinas ou 
de pessoas é de suma importância para a manutenção da rentabilidade do negócio. 
 
PARA MELHOR ENTENDER SUA IMPORTÂNCIA,VAMOS VER O SEGUINTE EXEMPLO 
O administrador de um hospital deseja otimizar o número de enfermeiros montando uma escala de trabalho para o 
primeiro turno. O hospital funciona sete dias por semana e o primeiro turno é das 8h às 14h. Cada enfermeiro trabalha 
cinco dias consecutivos e folga dois, com um salário semanal de R$800,00. Caso trabalhe no sábado, recebe um 
acréscimo de 10% no salário; caso trabalhe no domingo, de 25%. A tabela a seguir apresenta a necessidade mínima 
diária de profissionais. Quanto será o gasto semanal com salários? 
 
Dia seg ter qua qui sex sáb dom 
Número de enfermeiros 51 58 62 41 32 19 23 
 
Vamos inicialmente montar a escala de funcionários, informando que, caso trabalhe emdeterminado dia, o valor será 1, 
e caso contrário, 0. Veja a escala: 
 
 
 
 
Inicia o 
trabalho na (o) 
 seg ter qua qui sex sáb dom 
Seg 1 1 1 1 1 0 0 
ter 0 1 1 1 1 1 0 
qua 0 0 1 1 1 1 1 
qui 1 0 0 1 1 1 1 
sex 1 1 0 0 1 1 1 
sáb 1 1 1 0 0 1 1 
dom 1 1 1 1 0 0 1 
9 
 
Captura de tela do Software Excel 
Vamos, então, montar a planilha para a otimização do custo: 
 
 
A formulação será: 
K5:K11 → variáveis de decisão (número de funcionários que iniciam no dia) 
D12 → = SOMARPRODUTO(D5:D11;$K$5$K$11) 
(número de funcionários trabalhando no dia) 
E16 → = SOMARPRODUTO (K5:K11;L5:L11) (função objetivo) 
Podemos então montar o solver: 
Definir objetivo → $E$16 
Para → Min 
Alterando células variáveis → $K$5:$K$11 
Restrição 1 → $K$5:$K$11 = número inteiro 
Restrição 2 → $D$13:$J$13 ≥ =$D$12:$J$12 
Método de solução → LP Simplex 
 
 
10 
 
Necessidade no sábado 
Turnos Números de 
motoristas 
1 26 
2 22 
3 16 
 
Necessidade no domingo 
Turnos Números de 
motoristas 
1 16 
2 16 
3 16 
 
Necessidade na 6ª feira 
Turnos Números de 
motoristas 
1 26 
2 32 
3 18 
 
Captura de tela do Software Excel 
E obtemos a seguinte solução: 
 
 
Na solução obtida, 39 começam na segunda, 4 na quarta e 19 no sábado, atendendo anecessidade mínima diária. 
 
MÃO NA MASSA 
 
1. Uma cidade do interior paulista é atendida por uma empresa de transportes urbanos que transporta, em média, 
30.00 pessoas por dia. A finalidade do caso é determinar a escala dos motoristas de forma a atender as necessidades 
dos usuários e que também leve em conta um regime de trabalho razoável. As necessidades de motoristas, por turno, 
estão nas tabelas que se seguem: 
 
Turnos Horário 
1 6 a 12h 
2 12 a 18h 
3 18 a 24h 
 
 
1. Considerando que os motoristas não podem trabalhar mais do que 6 horas por dia e têm descanso de 2 dias 
consecutivos por semana, formule e resolva o problema objetivando minimizar a quantidade de motoristas que a 
empresa deve contratar. Desconsidere a possibilidade de o funcionário trocar de turno. Quantos funcionários a 
empresa deverá contratar? 
 
a) 100 
b) 120 
c) 80 
d) 90 
e) 75 
 
2. A YDVQS Motores recebeu recentemente uma encomenda para entregar três modelos diferentes de motores. Cada 
motor necessita de determinado número de horas de trabalho nos setores de montagem e de acabamento. Para 
atender a encomenda, a YDVQS pode também terceirizar parte de sua produção. 
11 
 
A tabela a seguir resume as informações sobre a demanda de cada modelo de motor, o tempo necessário para 
montar uma unidade de cada modelo, a quantidade de horas disponíveis no setor de montagem, o tempo necessário 
para dar acabamento a uma unidade de cada modelo, a quantidade de horas disponíveis no setor de acabamento, o 
custo de produção e o custo de terceirização de uma unidade de cada modelo. Qual será o custo total da estratégia 
ótima a ser adotada pela empresa de forma a atender os pedidos? 
 
Modelo 1 2 3 Total 
Demanda 3.000 2.500 500 6.000 
Montagem 1 2 0,5 6.000 
Acabamento 2,5 1 4 10.000 
Custo de produção R$ 50,00 R$ 90,00 R$ 120,00 
Terceirizado R$ 65,00 R$ 92,00 R$ 140,00 
 
a) R$ 457.000,00 
b) R$ 439.000,00 
c) R$ 435.000,00 
d) R$ 495.000,00 
e) R$ 385.000,00 
 
3. Considere o seguinte problema de programação inteira: 
 
Max Z = 6x1 + 11x2 
Sujeito a: 
5x1 + 3x2 ≤ 17 
x1, x2 ≥ 0 e inteiro 
 
A solução ótima será obtida para 
 
a) x1 = 0 e x2 = 5. 
b) x1 = 3 e x2 = 0. 
c) x1 = 1 e x2 = 4. 
d) x1 = 2 e x2 = 3. 
 
4. Uma empresa de construção civil compra mensalmente tijolos em paletes e prevê, para os próximos 6 meses, a 
procura média de 50, 30, 40, 20, 40 e 20 paletes, respectivamente. O fornecedor satisfaz, em prazo máximo de 48 
horas, encomendas tipificadas de 10, 20, 30, 40 ou 50 paletes com custo unitário de 3u.m. (unidades monetárias) e 
oferece os seguintes descontos de quantidade: 
 
Encomenda 
(paletes) 
Desconto na aquisição 
(u.m.) 
10 3% 
20 5% 
30 10% 
40 20% 
50 30% 
 
Mensalmente, a diferença entre o estoque e a procura não deve exceder 40 paletes por questões de armazenagem. O 
custo de encomenda é de 12u.m. O custo de estoque por mês é de 0.2u.m./palete incidindo sobre o estoque no final 
de cada mês. Admitindo que a gestão se inicia com estoque nulo e se pretende que também termine com estoque 
nulo no final do sexto mês, qual o custo total da compra mediante a política ótima de gestão do estoque? 
 
a) 530 
b) 280 
c) 577 
d) 384 
e) 306 
12 
 
5. A YDVQS Trading Ltda. possui um armazém com capacidade de armazenamento de 300.000 toneladas de grãos. No 
início do mês de janeiro, a YDVQS tinha 17.000 toneladas de grãos de trigo armazenadas. Em cada mês, é possível 
comprar ou vender trigo a preços prefixados pelo governo em qualquer quantidade desejada. Por questões fiscais, só 
é possível vender em cada mês o que estava estocado no início deste mês, ou seja, no fim do mês anterior. 
 
Mês Preço de venda Custo de compra 
Janeiro R$ 3,00 R$ 5,00 
Fevereiro R$ 4,00 R$ 7,00 
Março R$ 8,00 R$ 2,00 
Abril R$ 2,00 R$ 5,00 
Maio R$ 4,00 R$ 3,00 
Junho R$ 5,00R$ 3,00 
 
Considerando que a YDVQS Trading vai planejar suas operações de compra e venda nos próximos seis meses de forma 
a maximizar o lucro, qual será o valor do lucro? 
 
a) 51.000 
b) 535.000 
c) 874.000 
d) 951.000 
e) 1.058.000 
 
6. O administrador de um hospital deseja determinar a escala dos enfermeiros. Para isso, ele organiza um sistema de 
plantão dividindo o dia em 6 períodos de 4 horas. A tabela a seguir mostra o número mínimo de enfermeiros que 
devem estar presentes em cada horário. 
 
Horário 8h-12h 12h-16h 16h-20h 20h-24h 0h-04h 4h-8h 
Número de enfermeiros 51 58 62 41 32 19 
 
Cada enfermeiro cumpre um plantão normal de 8 horas, que pode começar apenas no início de um desses períodos. 
No horário de 8h a 20h, o enfermeiro recebe R$100,00 por hora de trabalho e R$125,00 por hora no horário noturno, 
de 20h a 8h. Como o administrador deve escalar os enfermeiros de forma a minimizar o custo com a mão de obra? 
 
a) R$125.200 
b) R$132.800 
c) R$175.700 
d) R$148.300 
e) R$ 158.900 
 
TEORIA NA PRÁTICA 
O problema a ser analisado é retirado da prática de usinagem de uma empresa de fabricação de máquinas CNC. 
Existem vários processos diferentes e para cada um deles é preciso obedecer a diferentes restrições tecnológicas. Para 
cada operário, existem várias operações aserem realizadas em máquinas diferentes, e cada operação corresponde a um 
tempo de processamento predefinido. 
 
É evidente que apenas um dos processos pode ser realizado uma única vez na mesma máquina. O ótimo da 
programação deve dar a distribuição dos tempos de operação, o início da operação e os momentos finais de cada 
processo entre as máquinas, reduzindo o tempo de processamento e o tempo ocioso. As máquinas disponíveis estão 
em número limitado e não são substituíveis entre si. Todos os processos devem ser realizados e estar disponíveis no 
momento prefixado para a montagem. 
 
Existem cinco processos (D1, D2, D3, D4 e D5) que realizam diferentes operações (O1, O2, ..., O8) com tempos de 
duração de processamento específicos em quatro máquinas de processamento (M1, M2, M3 e M4). Existem também 
ordens predefinidas do processamento. 
13 
 
Todas as informações necessárias são mostradas a seguir. 
 
Processamento 
N° Processo Operação técnica Tempo de 
processamento (h) 
Máquina 
1 
D1 
01 8 M1 
02 6 M2 
03 6 M4 
2 
D2 
01 8 M1 
04 8 M3 
02 8 M2 
03 4 M3 
3 
D3 
05 4 M1 
06 1 M2 
07 2 M3 
4 
D4 
05 6 M1 
07 8 M3 
5 
D5 
04 6 M1 
08 8 M5 
 
Nota: O processo D5 pode ser executado a qualquer momento — não precisa ser necessariamente o último —, desde 
que as máquinas M3 e M4 não estejam ocupadas. 
 
Os principais problemas relacionados ao processamento são os seguintes: 
 
 A montagem é feita em algumas empresas externas e o momento entrega deve ser definido. As entregas 
anteriores ocuparam o armazém e não foram eficientes em termos de custos. As entregas atrasadas 
influenciam o processo de montagem e afetam os custos. 
 
 Apenas um processo pode ser executado em uma única máquina por vez. A máquina estará disponível para o 
próximo processo após a conclusão do anterior. Cada um dos processos está alocado a cada máquina, 
conforme demonstrado previamente. 
 
A sequência de processamento será? 
 
VERIFICANDO O APRENDIZADO 
 
1. A Companhia Brasileira de Café, presente em três plantações bem localizadas, tritura os grãos de café até se 
tornarem pó. Semanalmente, o café em pó é embarcado com destino a quatro armazéns em diferentes cidades, para 
torrefação, distribuição e exportação. O custo de transporte em unidades monetárias (u.m.) de uma tonelada de café 
da plantação i para o armazém j é apresentado a seguir. 
 
 
Armazéns 
Plantações 
1 2 3 4 
1 9 8 3 4 
2 7 6 2 1 
3 5 4 7 9 
 
As capacidades semanais das plantações 1, 2 e 3 são 40, 60 e 80 toneladas respectivamente, enquanto as 
necessidades dos armazéns 1, 2, 3 e 4 são 50, 40, 30 e 60 toneladas respectivamente. O objetivo da companhia 
consiste em determinar as quantidades de café que devem ser transportadas de cada uma das plantações para cada 
um dos armazéns minimizando o custo total de transporte. A parte da função objetivo sobre o Armazém 1 será igual 
a: 
14 
 
a) 9x11 + 8x12 + 3x13 + 4x14 
b) 9x11 + 7x21 + 3x13 + 4x31 
c) 7x11 + 6x12 + 2x13 + x14 
d) 8x11 + 7x21 + 5x13 
 
2. Métodos de resolução utilizam modelos matemáticos para representar problemas e auxiliar no processo de tomada 
de decisão. O estudo de um problema por meio da pesquisa operacional pode ser dividido em fases. Sobre tais fases é 
correto afirmar que: 
 
a) A primeira etapa é a resolução de um modelo matemático para qualificar o problema em questão. 
b) Variações no resultado do modelo podem ser realizadas para adequá-lo às modificações de última hora. 
c) Os resultados do modelo podem ser implantados diretamente no problema real, sem passarem por 
qualquer validação. 
d) Uma das fases do estudo é a formulação de um modelo matemático baseado no escopo do problema a ser 
resolvido. 
e) A validação de um modelo matemático não é uma etapa do processo de solução de um problema. 
 
 
MÓDULO 2 
Reconhecer os problemas de escala de produção 
 
VARIAÇÕES DE DEMANDA 
Na vida real, os requisitos de oferta e demanda raramente serão iguais, devido às variações na produção da parte do 
fornecedor e na previsão da parte do cliente. As variações na produção podem ocorrer por causa de escassez de 
matéria-prima, problemas de mão de obra, planejamento inadequado e agendamento. As variações da demanda 
podem acontecer em razão de mudanças na preferência do cliente, mudanças nos preços e introdução de novos 
produtos pelos concorrentes. 
 
Esses desequilíbrios podem ser facilmente resolvidos pela introdução de fontes e destinos fictícios (dummy). Se a oferta 
total for maior que a demanda total, um destino fictício (coluna fictícia) com demanda igual ao excedente de oferta é 
adicionado. Se a demanda total for maior que a oferta total, uma fonte fictícia (linha fictícia) com oferta igual ao 
excedente de demanda é adicionada. O custo de transporte unitário para a coluna e linha fictícias é definido como zero, 
porque nenhuma remessa é realmente feita no caso de origem e destino fictícios. 
 
DEMANDA MENOR QUE OFERTA 
Vamos verificar se o problema de transporte mostrado a seguir é equilibrado. Caso não seja, vamos converter o 
problema desequilibrado em um problema de transporte equilibrado. 
 
 
SOLUÇÃO: 
Para o problema em questão, a oferta total não é igual à demanda total. 
15 
 
Oferta = 200 + 100 + 400 = 700 
Demanda = 200 + 100 + 300 = 600 
 
O problema apresentado é um problema de transporte desequilibrado. Para convertê-lo em umproblema equilibrado, 
adicione um destino fictício (coluna fictícia). A demanda do destino fictício é igual a: 
 
 
Assim, um destino fictício é adicionado à tabela com uma demanda de 100 unidades. A destinação dummy (4) é 
apresentada na tabela, que foi convertida em um problema de transporte balanceado. A unidade custos de transporte 
de destinos fictícios é definida como zero. 
 
 
DEMANDA MAIOR QUE OFERTA 
Acompanhe agora o problema apresentado a seguir: 
 
Para o problema em questão, a oferta total não é igual à demanda total. 
Oferta = 200 + 300 + 300 = 800 
Demanda = 100 + 200 + 450 + 250 = 1.000 
 
Aqui, uma origem fictícia é adicionada à tabela com uma oferta de 200 unidades. A origem dummy (4) é apresentada na 
tabela, que foi convertida em um problema de transporte balanceado. A unidade custos de transporte de destinos 
fictícios é definida como zero. 
16 
 
 
 
SOLUÇÃO INICIAL VIÁVEL 
 
 ETAPA 1: FORMULE O PROBLEMA. 
Formule o problema fornecido e configure-o em uma forma de matriz. Verifique se o problema éum problema 
de transporte equilibrado ou desequilibrado. Se for desequilibrado, adicione origem fictícia (linha) ou destino 
fictício (coluna) conforme necessário. 
 
 ETAPA 2: OBTENHA A SOLUÇÃO VIÁVEL INICIAL.A solução viável inicial pode ser obtida por qualquer um dos três métodos a seguir: 
 
1. Método do Canto Noroeste (NWC). 
2. Método mínimo de linha e coluna (RCMM). 
3. Método de aproximação de Vogel (VAM). 
 
No cálculo do custo de transporte da solução viável básica inicial por meio da aproximação de Vogel, o VAM será o 
mínimo quando comparado aos outros dois métodos que fornecem o valormais próximo da solução ótima ou o valor da 
própria solução ótima. Os algoritmos para todos os três métodos são conhecidos. 
 
ALGORITMO PARA MÉTODO DO CANTO NOROESTE 
O método tem as seguintes etapas na busca da solução: 
 
1. Selecione a célula do canto noroeste, superior esquerdo, da tabela e aloque o máximo unidades possíveis 
entre os requisitos de oferta e demanda. Durante a alocação, o custo de transporte não é levado em 
consideração. 
 
2. Exclua a linha ou coluna que não tem valores (totalmente esgotados) para oferta ou demanda. 
 
3. Agora, com a nova tabela reduzida, selecione novamente a célula do canto noroeste e aloque os valores 
disponíveis. 
 
4. Repita as etapas (2) e (3) até que todos os valores de oferta e demanda sejam zero. 
 
5. Obtenha a solução básica viável inicial. 
17 
 
ETAPA 1 
 
 
ETAPA 2 
 
 
 
ETAPA 3 
 
18 
 
ETAPA 4 
 
 
ETAPA 5 
 
 
ETAPA 6 
 
19 
 
Captura de tela do Software Excel 
ETAPA 7 
 
 
O custo total será: 
100 x 10 + 100 x 16 + 100 x 12 + 200 x 13 + 250 x 13 + 50 x 4 + 200 x 0 = 9.850 
 
RESOLVENDO NO SOLVER 
Vamos montar a planilha para encontrar a solução: 
 
 
A formulação será: 
 
 
Para a montagem do Solver, teremos: 
20 
 
Captura de tela do Software Excel 
Captura de tela do Software Excel 
Definir objetivo → $I$15 
Para → Min 
Alterando células variáveis → $F$4:$F$19 
Restrição 1 → $H$4:$H$11 = $I$4:$I$11 
Método de solução → LP Simplex 
 
 
Obtendo a seguinte solução: 
 
 
Observe que o Solver sempre encontrará a solução ótima. 
21 
 
1. Encontre a solução viável básica inicial para o problema de transporte, apresentado a seguir, usando o método do 
Canto Noroeste. 
 
 
De 
Para 
Disponível A B C 
I 50 30 220 1 
II 90 45 170 3 
III 250 200 50 4 
Requerido 4 2 2 
 
a) 930 
b) 820 
c) 680 
d) 530 
 
 
2. Um fabricante de batatas fritas possui três fábricas e quatro depósitos. O custo de transporte das fábricas para os 
armazéns, a disponibilidade da fábrica e os requisitos dos armazéns são apresentados a seguir: 
 
 
Fábrica 
Depósitos 
Capacidade D1 D2 D3 D4 
F1 7 4 3 5 235 
F2 6 8 7 4 280 
F3 5 6 9 10 110 
Armazenagem 125 160 110 230 
 
A solução utilizando o método do Canto Noroeste dará um custo de transporte igual a 
 
a) 3.075 
b) 3.584 
c) 4.065 
d) 5.038 
 
3. A YDVQS Co. produz um único produto em três fábricas para quatro clientes. As três fábricas vão produzir 60, 80 e 
40 unidades, respectivamente, durante o próximo período. A firma fez um compromisso de vender 40 unidades ao 
cliente 1, 60 unidades ao cliente 2, e pelo menos 20 unidades para o cliente 3. Ambos os clientes 3 e 4 também 
desejam comprar o máximo possível das unidades restantes. O lucro associado ao envio de uma unidade da planta i 
para venda ao cliente j é dado pela seguinte tabela: 
 
 Cliente 
 1 2 3 4 
 
Fábrica 
1 800 700 500 200 
2 500 200 100 300 
3 600 400 300 500 
 
A administração deseja saber quantas unidades vender aos clientes 3 e 4 e quantas unidades enviar de cada fábrica 
para cada cliente para maximizar o lucro. O lucro esperado será igual a 
 
a) 50.000 
b) 70.000 
c) 80.000 
d) 90.000 
22 
 
4. Considere o problema de transporte com a seguinte tabela de parâmetros. 
 
 Destino 
Capacidade 1 2 4 
Origem 1 15 9 13 7 
2 11 -- 17 5 
3 9 11 9 3 
Demanda 7 3 5 
 
Os valores da origem e destino referem-se ao lucro gerado pela entrega. Utilizando o método do Canto Noroeste, 
obteremos o seguinte lucro: 
 
a) 223 
b) 348 
c) 187 
d) 245 
 
5. Uma empreiteira, Susan Meyer, tem que transportar cascalho para três empreendimentos que está construindo. 
Ela pode comprar até 18 toneladas em uma mina de cascalho no norte da cidade e 14 toneladas de uma no sul. Ela 
precisa de 10, 5 e 10 toneladas nos locais 1, 2 e 3, respectivamente. O preço de compra por tonelada em cada mina e 
o custo de transporte por tonelada são fornecidos na tabela a seguir. 
 
 Custo por tonelada transportada 
Preço por tonelada 1 2 3 
Norte 100 190 160 300 
Sul 180 110 140 420 
Necessidade 10 5 10 
 
Qual será o custo mínimo desse transporte? 
 
a) 3750 
b) 3550 
c) 7500 
d) 11050 
 
 
e) 12050 
 
6. A Indústria YDVQS fabrica um único produto em quatro localidades, Curitiba, Campinas, Itabuna e Campos. O custo 
unitário de produção de cada localidade é respectivamente $35,50, $37,50, $39,00 e $36,25, e a capacidade anual de 
produção de cada planta é 18.000, 15.000, 25.000 e 20.000 unidades. A empresa está planejando estabelecer sete 
centros de distribuição para atender a sua demanda. O custo unitário de transporte entre cada um dos locais é 
apresentado na tabela a seguir, bem como a demanda de cada região: 
 
Custo unitário de transporte para o centro de distribuição 
Fábrica SP RJ SA RE BH CO PA 
Curitiba $ 2,50 $ 2,75 $ 1,75 $ 2,00 $ 2,10 $ 1,80 $ 1,65 
Campinas $ 1,85 $ 1,90 $ 1,50 $ 1,60 $ 1,00 $ 1,90 $ 1,85 
Itabuna $ 2,30 $ 2,25 $ 1,85 $ 1,25 $ 1,50 $ 2,25 $ 2,00 
Campos $ 1,90 $ 0,90 $ 1,60 $ 1,75 $ 2,00 $ 2,50 $ 2,65 
Demanda 8.500 14.500 13.500 12.600 18.000 15.000 9.000 
 
A empresa deseja determinar como atender a demanda de cada local com o menor custo de fabricação e de 
transporte, mas como a demanda geral excede a capacidade de fabricação, deseja ter certeza de que pelo menos 80% 
das ordens recebidas por cada centro de distribuição sejam atendidas. Como você solucionaria este problema? Qual 
será o custo mínimo de transporte? 
23 
 
a) 3.011.360,00 
b) 2.901.500,00 
c) 2.596.620,00 
d) 3.128.540,00 
 
VERIFICACANDO O APRENDIZADO 
 
1. Há um problema de distribuição de produtos de uma origem para destinos diferentes, apresentado na tabela a 
seguir: 
 
 
Origem 
Destinos 
Capacidade 1 2 3 
1 65 45 8 200 
2 30 10 15 100 
3 12 40 55 400 
Demanda 200 100 300 
 
A solução inicial pelo método do Canto Noroeste será igual à: 
 
a) da origem 1 para o destino 1, 65. 
b) da origem 1 para o destino 1, 200. 
c) da origem 1 para o destino 3, 300. 
d) da origem 2 para o destino 2, 100. 
e) da origem 3 para o destino 3, 200. 
 
2. Considerando o problema de distribuição de produtos de uma origem para destinos apresentado na tabela a seguir, 
qual será o custo total de transporte? 
 
 
Origem 
Destinos 
Capacidade 1 2 3 
1 65 45 8 200 
2 30 10 15 100 
3 12 40 55 400 
Demanda 200 100 300 
 
 
a) 9500 
b) 8700 
c) 10300 
d) 6600 
 
 
CONCLUSÃO 
Considerações finais 
Redes de algum tipo surgem em uma ampla variedade de contextos e as representações de rede são muito úteis para 
retratar as relações e conexões entre os componentes de sistemas. Frequentemente, o fluxo de algum tipo deve ser 
enviado através de uma rede, portanto, uma decisão precisa ser tomada sobre a melhor maneira de fazer isso. O 
algoritmo apresentado e o Solver são ferramentas poderosas para tomar tais decisões.