Aula 2 - Programação Matemática

Prévia do material em texto

PROGRAMAÇÃO MATEMÁTICA Professora Bianca Endo
biancaendo@uniararas.br
06.03.18 FHO - UNIARARAS 1
NA AULA PASSADA
Importância da Pesquisa Operacional
06.03.18 FHO - UNIARARAS 2
O PROCESSO DE MODELAGEM
Modelos: representações simplificadas de um problema real. 
06.03.18 FHO - UNIARARAS 3
Definição das variáveis
Relações matemáticas das restrições
Equação da função objetivo
Modelo completo!
O que queremos saber?
A que condições devemos obedecer?
Como o objetivo pode ser escrito em termos das variáveis?
MODELOS DE PROGRAMAÇÃO LINEAR - CARACTERÍSTICAS
Proporcionalidade: a quantidade de recurso consumido por uma dada atividade
deve ser proporcional ao nível dessa atividade na solução final do problema. Além
disso, o custo de cada atividade é proporcional ao nível de operação da atividade.
Não Negatividade: deve ser sempre possível desenvolver dada atividade em 
qualquer nível não negativo. 
Aditividade: o custo total é a soma das parcelas associadas a cada atividade.
Separabilidade: pode-se identificar de forma separada o custo (ou consumo de 
recursos) específico das operações de cada atividade.
Um modelo de Programação linear é um modelo matemático de otimização no 
qual todas as funções são lineares da variável contínua x.
06.03.18 FHO - UNIARARAS 4
MODELOS DE PROGRAMAÇÃO LINEAR - ELEMENTOS
Variáveis de decisão
Função objetivo
Restrições
Condição de não negatividade
06.03.18 FHO - UNIARARAS 5
FORMULAÇÃO ALGÉBRICA DE UM PPL
Forma geral
06.03.18 FHO - UNIARARAS 6
Otimizar: maximizar ou minimizar a função objetivo
Forma padrão
m = número de restrições
n = número de variáveis
Forma canônica
OPERAÇÕES ELEMENTARES
Operação 1: 
𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓 𝑥 = 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 −𝑓 𝑥
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑓 𝑥 = 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 −𝑓 𝑥
Operação 2:
𝑥𝑛 = 𝑥𝑛
1 − 𝑥𝑛
2 𝑒 𝑥𝑛
1 ≥ 0, 𝑥𝑛
2 ≥ 0
Operação 3:
𝑥1 + 𝑥2 +⋯+ 𝑥𝑛 ≤ 𝑏 é equivalente a 𝑥1 + 𝑥2 +⋯+ 𝑥𝑛 + 𝑥𝑛+1 = 𝑏
𝑥𝑛+1 é uma variável de folga
06.03.18 FHO - UNIARARAS 7
EXERCÍCIOS PARA PRATICAR
O problema da liga metálica
O problema da dieta
O problema da mistura de petróleo
O problema da competição entre os engenheiros
O problema do jantar de Nero
06.03.18 FHO - UNIARARAS 8
O PROBLEMA DA LIGA METÁLICA
Uma metalúrgica deseja maximizar sua receita bruta. A tabela abaixo ilustra a 
proporção de cada material na mistura para a obtenção das ligas passíveis de 
fabricação. O preço está cotado em Reais por tonelada da liga fabricada. Também 
em toneladas estão expressas as restrições de disponibilidade de matéria-prima. 
Formular o modelo de Programação Matemática. 
06.03.18 FHO - UNIARARAS 9
Liga especial de 
baixa resistência *
Liga especial de 
alta resistência *
Disponibilidade de 
matéria-prima
Cobre 0,5 0,2 16 ton
Zinco 0,25 0,3 11 ton
Chumbo 0,25 0,5 15 ton
Preço de venda (R$ 
por ton)
R$3000 R$5000 *Ton de minério/Ton 
de liga
O PROBLEMA DA DIETA
O objetivo do presente programa é determinar, em uma dieta para a redução calórica, as quantidades 
de certos alimentos que deverão ser ingeridos diariamente, de modo que determinados requisitos 
nutricionais sejam satisfeitos a custo mínimo. 
Suponha que uma certa dieta alimentar esteja restrita a leite desnatado, carne magra de boi, carne de 
peixe e uma salada. Sabe-se ainda que os requisitos nutricionais serão expressos em termos de vitaminas 
A, C e D e controlados por suas quantidades mínimas (em miligramas), uma vez que são indispensáveis à 
preservação da saúde da pessoa que estará se submetendo à dieta. A tabela abaixo resume a 
quantidade de cada vitamina em disponibilidade nos alimentos e a sua necessidade diária para a boa 
saúde de uma pessoa. Formular o problema para otimização dos recursos envolvidos. 
06.03.18 FHO - UNIARARAS 10
Vitamina Leite (litro) Carne (kg) Peixe (kg) Salada (100 g) Requisito nutricional mínimo
A 2 mg 2 mg 10 mg 20 mg 11 mg
C 50 mg 20 mg 10 mg 30 mg 70 mg
D 80 mg 70 mg 10 mg 80 mg 250 mg
Custo R$ 2 R$ 4 R$ 1,50 R$ 1
O PROBLEMA DA MISTURA DE PETRÓLEO
Uma refinaria processa vários tipos de petróleo. Cada tipo de petróleo possui uma 
planilha de custos diferente, expressando condições de transporte e preços na origem. 
Por outro lado, cada tipo de petróleo representa uma configuração diferente de 
subprodutos para a gasolina. Na medida em que um certo tipo de petróleo é utilizado 
na produção da gasolina, é possível a programação das condições de octanagem e 
outros requisitos. Esses requisitos implicam a classificação do tipo da gasolina obtida.
Supondo que a refinaria trabalhe com uma linha de quatro tipos diferentes de petróleo 
e deseje produzir as gasolinas amarela, azul e superazul, programar a mistura dos tipos 
de petróleo atendendo às condições que se seguem nas duas tabelas seguintes: 
06.03.18 FHO - UNIARARAS 11
O PROBLEMA DA MISTURA DE PETRÓLEO
06.03.18 FHO - UNIARARAS 12
Tipo de petróleo Quantidadé máxima disponível (Barril/dia) Custo por barril/dia (R$)
1 3500 19
2 2200 24
3 4200 20
4 1800 27
Tipo de gasolina Especificação Preço de venda R$/Barril
Superazul Não mais que 30% de 1
Não menos que 40% de 2
Não mais que 50% de 3
35
Azul Não mais que 30% de 1
Não menos que 10% de 2
28
Amarela Não mais que 70% de 1 22
Quantidade disponível de petróleo
Percentuais para limites de qualidade das gasolinas
O PROBLEMA DA COMPETIÇÃO ENTRE OS ENGENHEIROS
Duas equipes de fabricantes de carros de corrida estão praticamente disputando sozinhas o campeonato. A 
cada mês são disputadas três provas. A equipe vencedora é aquela que acumula o maior número de vitórias 
durante todas as corridas do ano. Assim que o campeonato se iniciou, a Equipe B passou a vencer a Equipe A 
em cerca de 60% das provas. O carro da Equipe B acabava sempre ultrapassando nas curvas o carro da 
equipe A. Tentando anular essa vantagem, os engenheiros da Equipe A desenvolveram um aerofólio especial 
para dar mais estabilidade ao carro nas curvas. Apesar de ficar com o carro mais pesado, o piloto da 
Equipe A podia, agora, usar sua habilidade e impedir a ultrapassagem do carro da Equipe B nas curvas, 
mantendo ou ganhando sua posição nas retas. Com a melhoria tecnológica, a Equipe A passou a vencer cerca 
de 80% das corridas. Vendo o desastre se aproximar, os engenheiros da Equipe B contra-atacaram criando 
um estabilizador de suspensão para melhorar a manobrabilidade nas curvas. O resultado anulou a 
habilidade do piloto da Equipe A em bloquear o carro da Equipe B nas curvas e esta passou a vencer cerca 
de 80 % das provas. Acuada e sem ter como aumentar mais a aderência do carro nas curvas, a Equipe A, em 
uma reunião de emergência, tentou uma estratégia suicida: retirar o aerofólio para ganhar com o alívio de 
peso e tentar compensar nas retas o que fatalmente perderia nas curvas. Surpreendentemente, com essa 
estratégia passou a ganhar 80% das provas, pois o estabilizador de suspensão especial dos carros da 
Equipe B era muito pesado e inútil nas retas, reduzindo sobremaneira o desempenho do carro fora das 
curvas. Imediatamente, a Equipe B retirou seu equipamento e as escuderias voltaram ao ponto de partida com 
vantagem novamente para a Equipe B.
06.03.18 FHO - UNIARARAS 13
O PROBLEMA DA COMPETIÇÃO ENTRE OS ENGENHEIROS
A essa altura do campeonato, as duas equipes estavam rigorosamente empatadas em número de 
vitórias. O chefe da Equipe A resolveu contratar um assessor de Pesquisa Operacional para decidir a 
melhor política para sua equipe e, quem sabe, dar-lhe o título daquele conturbado ano. Formule e 
solucione o problema de encontrar a política ótima de equipagem para o carro da Equipe A. Sabe-
se que a instalação do estabilizador especial e do aerofólio leva cerca de 4 horas e não podeser 
desfeita ao longo da corrida, e que os boxes de cada equipe podem ser fechados, de forma que a 
equipe concorrente não saiba qual configuração será adotada em uma corrida pela sua adversária.
06.03.18 FHO - UNIARARAS 14
O PROBLEMA DO JANTAR DE NERO
O imperador romano Nero, em um momento de inspiração, resolveu promover um jantar para 
eliminar seus “melhores” inimigos. Consultando seu médico de confiança, soube que ele 
dispunha de dois tipos de venenos, alfa e beta. Tratavam-se de fármacos próprios para serem 
misturados no molho de carneiro. Havia no estoque da farmácia do facultativo 0, 5 kg do 
veneno alfa e 2 kg do veneno beta. Para que os convidados não sentissem o gosto do veneno, 
era indispensável misturar em peso três porções do veneno alfa para cada porção de beta. 
Cada 12 gramas de alfa ou 6 de beta eram capazes de sozinhas liquidarem um homem. O 
efeito do veneno sobre as mulheres era cerca de 50% mais poderoso do que sobre os homens. 
Nero, satisfeito com a informação, deu suas ordens ao médico: prepare a mistura mais 
eficiente e elimine pelo menos 20 homens e 10 mulheres!
Elaborar o modelo de programação matemática que maximize o efeito do veneno sobre os 
prezados inimigos do imperador e evite que o médico perca o emprego e acabe queimado 
vivo no dito jantar. 
06.03.18 FHO - UNIARARAS 15
SÍNTESE DA AULA
Programação Linear:
 Modelagem
 Variáveis de decisão
 Função objetivo
 Restrições
 Resolução
 Validação
06.03.18 FHO - UNIARARAS 16