Programação Linear 01

Prévia do material em texto

ENP153 –Programação Linear
Aula 01 – Princípios Básicos da Modelagem de Problemas
O QUE É A PESQUISA OPERACIONAL?
 Pesquisa Operacional (P.O.) nada mais é que um método científico
para a tomada de decisões.
 Esta tem como objetivo a estruturação dos processos, propondo
um conjunto de alternativas e ações, fazendo a previsão e a
comparação de valores.
PARA QUE RAIOS ELA SERVE?
 Por ser uma ferramenta matemática aplicada, a P.O. nos dá
condições para:
i. Solucionar problemas reais
ii. Tomar decisões embasadas em fatos, dados e correlações
quantitativas
iii. Conceber, planejar, analisar, implementar, operar e controlar
sistemas por meio da tecnologia bem como de métodos de outras
áreas do conhecimento
iv. Minimizar custos e maximizar o lucro
v. Encontrar a melhor solução para um problema, ou seja, a solução
ótima
QUE TIPO DE PROBLEMAS ELA SOLUCIONA?
 Atualmente, sua principal utilização é como ferramenta nos
processos de tomada de decisão no ambiente empresarial e nos
negócios, tanto no setor privado como no setor público.
i. Otimização de recursos
ii. Roteirização
iii. Localização
iv. Carteiras de investimento
v. Alocação de pessoas
vi. Previsão de planejamento
vii. Alocação de verbas de mídia
viii. Determinação de mix de produtos
ix. Escalonamento e planejamento da produção
x. Planejamento financeiro
xi. Análise de projetos e etc
COMO É REALIZADO A APLICAÇÃO?
UNIVERSO REAL
Problemas
Decisões
UNIVERSO SIMBÓLICO
Modelagem
Resultados
ATIVIDADES CRÍTICAS
Estudo do problema Seleção do método
ONDE EU ENTRO NISSO TUDO?
MÉTODOS DE SOLUÇÃO
Simulação por Experimentação
Heurísticas e Metaheurísticas
Modelagem Matemática
Programação Dinâmica
Programação Estocástica
Programação Evolucionária
MÉTODOS DE SOLUÇÃO
Simulação por Experimentação
Heurísticas e Metaheurísticas
Modelagem Matemática
Programação Dinâmica
Programação Estocástica
Programação Evolucionária
SOLUÇÃO POR MODELAGEM MATEMÁTICA
Otimização Linear
Otimização Linear Inteira
Otimização Quadrática
Mínimos Quadrados Não Linear
Otimização Não Linear Irrestrita
Otimização Não Linear Com Limites Superior e Inferior
Otimização Não Linear Restrira
SOLUÇÃO POR MODELAGEM MATEMÁTICA
Otimização Linear
Otimização Linear Inteira
Otimização Quadrática
Mínimos Quadrados Não Linear
Otimização Não Linear Irrestrita
Otimização Não Linear Com Limites Superior e Inferior
Otimização Não Linear Restrira
OTIMIZAÇÃO LINEAR (PROGRAMAÇÃO LINEAR)
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
OTIMIZAÇÃO LINEAR (PROGRAMAÇÃO LINEAR)
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
função objetivo
OTIMIZAÇÃO LINEAR (PROGRAMAÇÃO LINEAR)
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
restrições do problema
OTIMIZAÇÃO LINEAR (PROGRAMAÇÃO LINEAR)
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
variável de decisão
FUNÇÃO OBJETIVO
 Função das variáveis de otimização a ser minimizada ou
maximizada.
 Exemplos:
 Minimizar custos de um sistema de manufatura
 Minimizar desvio de tensão em barramentos de um sistema elétrico
 Maximizar fluxo de uma rota em uma rede logística
RESTRIÇÕES DO PROBLEMA
 Conjunto de funções que definem o conjunto viável de soluções.
 Exemplos:
 Limite de utilização de recursos em um sistema de manufatura
 Capacidade máxima de um veículo em um problema de transporte
de produtos
VARIÁVEIS DE DECISÃO
 São os parâmetros cujos valores devem ser estabelecidos para a 
resolução de um problema.
 Exemplos:
 Quantidade a ser produzida em um sistema de produção
 Valor a ser transportado por um determinado veículo para um 
determinado cliente, em um sistema de transporte
 Valores a serem utilizados por reagentes em um problema de 
mistura
O QUE É MODELAR UM PROBLEMA?
 Modelar um problema significa representar a realidade ou
sistemas originais através de outros sistemas de substituição,
sendo estes estruturados e comparáveis ao sistema original.
 Na programação linear, esta substituição é realizada
representando o sistema original por meio de modelo, composto
por equações matemáticas.
O QUE É UM MODELO?
 Os modelos são representações simplificadas do problema real,
tendo estes que preservar as características essenciais do
problema que se deseja resolver.
 Um modelo reflete a essência do problema, representando as
relações de interdependência existentes entre as componentes do
objeto de estudo.
INCERTEZA NO MOMENTO DE MODELAGEM
MODELAGEM DE UM PROCESSO
TIPOS DE SOLUÇÕES
TIPOS DE SOLUÇÕES
conjunto de soluções viáveis
TIPOS DE SOLUÇÕES
solução ótima
OTIMIZAÇÃO LINEAR (PROGRAMAÇÃO LINEAR)
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
PROCESSO DE MODELAGEM
 Um nutricionista estabelece que você deve consumir uma
quantidade mínima de três tipos de vitaminas (10 de A, 30 de B e
18 de C) diariamente, onde estas são encontradas em cinco
alimentos (A1, A2, A3, A4 e A5). As concentrações das vitaminas
em cada alimento, e o custo de cada unidade de alimento podem
ser visto na tabela a seguir:
 Deseja-se encontrar a quantidade a ser consumida de cada
alimento de modo que todos os nutrientes diários sejam
atendidos e que se obtenha o menor custo possível.
A1 A2 A3 A4 A5
A 0 1 5 4 3
B 2 1 0 3 2
C 3 1 0 9 0
Custo 4 2 1 10 5
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
 2º PASSO: identificar as restrições do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
 2º PASSO: identificar as restrições do problema
 3º PASSO: identificar as variáveis do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
 2º PASSO: identificar as restrições do problema
 3º PASSO: identificar as variáveis do problema
 4º PASSO: identificar os parâmetros do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
→ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑜 𝑐𝑢𝑠𝑡𝑜 𝑑𝑎 𝑑𝑖𝑒𝑡𝑎
 2º PASSO: identificar as restrições do problema
 3º PASSO: identificar as variáveis do problema
 4º PASSO: identificar os parâmetros do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
→ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑜 𝑐𝑢𝑠𝑡𝑜 𝑑𝑎 𝑑𝑖𝑒𝑡𝑎
 2º PASSO: identificar as restrições do problema
→ 𝑑𝑒𝑣𝑒 − 𝑠𝑒 𝑐𝑜𝑛𝑠𝑢𝑚𝑖𝑟 𝑢𝑚𝑎 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑚í𝑛𝑖𝑚𝑎 𝑑𝑒 𝑛𝑢𝑡𝑟𝑖𝑒𝑛𝑡𝑒𝑠
 3º PASSO: identificar as variáveis do problema
 4º PASSO: identificar os parâmetros do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
→ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑜 𝑐𝑢𝑠𝑡𝑜 𝑑𝑎 𝑑𝑖𝑒𝑡𝑎
 2º PASSO: identificar as restrições do problema
→ 𝑑𝑒𝑣𝑒 − 𝑠𝑒 𝑐𝑜𝑛𝑠𝑢𝑚𝑖𝑟 𝑢𝑚𝑎 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑚í𝑛𝑖𝑚𝑎 𝑑𝑒 𝑛𝑢𝑡𝑟𝑖𝑒𝑛𝑡𝑒𝑠
 3º PASSO: identificar as variáveis do problema
→ 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑎 𝑠𝑒𝑟 𝑐𝑜𝑛𝑠𝑢𝑚𝑖𝑑𝑎 𝑑𝑒 𝑐𝑎𝑑𝑎 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
 4º PASSO: identificar os parâmetros do problema
PROCESSO DE MODELAGEM
 1º PASSO: identificar o objetivo do problema
→ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑜 𝑐𝑢𝑠𝑡𝑜 𝑑𝑎 𝑑𝑖𝑒𝑡𝑎
 2º PASSO: identificar as restrições do problema
→ 𝑑𝑒𝑣𝑒 − 𝑠𝑒 𝑐𝑜𝑛𝑠𝑢𝑚𝑖𝑟 𝑢𝑚𝑎 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑚í𝑛𝑖𝑚𝑎 𝑑𝑒 𝑛𝑢𝑡𝑟𝑖𝑒𝑛𝑡𝑒𝑠
 3º PASSO: identificar as variáveis do problema
→ 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑎 𝑠𝑒𝑟 𝑐𝑜𝑛𝑠𝑢𝑚𝑖𝑑𝑎𝑑𝑒 𝑐𝑎𝑑𝑎 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
 4º PASSO: identificar os parâmetros do problema
→ 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑛𝑢𝑡𝑟𝑖𝑒𝑛𝑡𝑒𝑠 𝑝𝑜𝑟 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
→ 𝑐𝑢𝑠𝑡𝑜 𝑑𝑒 𝑐𝑎𝑑𝑎 𝑎𝑙𝑖𝑚𝑒𝑛𝑡𝑜
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 1º PASSO: definir o conjunto de variáveis
 Já sabemos que as variáveis são definidas como a quantidade de
cada alimento a ser consumido, para que se obtenha a quantidade
mínima de cada nutriente.
 Deve ser decidido pelo modelo a quantidade a ser consumida para
cada alimento, ou seja, um valor de consumido diário será definido
de modo independente. Deste modo, deve-se utilizar uma variável
para cada alimento.
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 1º PASSO: definir o conjunto de variáveis
 Já sabemos que as variáveis são definidas como a quantidade de
cada alimento a ser consumido, para que se obtenha a quantidade
mínima de cada nutriente.
 Deve ser decidido pelo modelo a quantidade a ser consumida para
cada alimento, ou seja, um valor de consumido diário será definido
de modo independente. Deste modo, deve-se utilizar uma variável
para cada alimento.
 Variáveis do problema: 𝑥𝐴1, 𝑥𝐴2, 𝑥𝐴3, 𝑥𝐴4 𝑒 𝑥𝐴5
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 2º PASSO: definir os conjuntos de parâmetros
 Já sabemos que as quantidades de nutrientes e os custos são os
parâmetros do problema estudado, logo deve-se separar os
parâmetros de acordo com suas relações.
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 2º PASSO: definir os conjuntos de parâmetros
 Já sabemos que as quantidades de nutrientes e os custos são os
parâmetros do problema estudado, logo deve-se separar os
parâmetros de acordo com suas relações.
 Valores de nutrientes para o alimento A1
0 1 5 4 3
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 2º PASSO: definir os conjuntos de parâmetros
 Já sabemos que as quantidades de nutrientes e os custos são os
parâmetros do problema estudado, logo deve-se separar os
parâmetros de acordo com suas relações.
 Valores de nutrientes para o alimento A1
0 1 5 4 3
 Valores de nutrientes para o alimento A2
2 1 0 3 2
 (...)
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 3º PASSO: construir a função objetivo
 Como já definimos, o objetivo do problema é minimizar o custo
relacionado ao consumo dos alimentos. Deste modo, a função do
problema pode ser descrito como:
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 3º PASSO: construir a função objetivo
 Como já definimos, o objetivo do problema é minimizar o custo
relacionado ao consumo dos alimentos. Deste modo, a função do
problema pode ser descrito como:
𝑀𝐼𝑁 4𝑥𝐴1 + 2𝑥𝐴2 + 𝑥𝐴3 + 10𝑥𝐴4 + 5𝑥𝐴5
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 Sabemos que deve ser consumido uma quantidade mínima de
nutrientes (10 de A, 30 de B e 18 de C). Primeiramente, sabemos que:
𝑎𝑙𝑔𝑢𝑚𝑎 𝑐𝑜𝑖𝑠𝑎 ≥ 10
𝑎𝑙𝑔𝑢𝑚𝑎 𝑐𝑜𝑖𝑠𝑎 ≥ 30
𝑎𝑙𝑔𝑢𝑚𝑎 𝑐𝑜𝑖𝑠𝑎 ≥ 18
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 Sabemos que deve ser consumido uma quantidade mínima de
nutrientes (10 de A, 30 de B e 18 de C). Primeiramente, sabemos que:
𝑎𝑙𝑔𝑢𝑚𝑎 𝑐𝑜𝑖𝑠𝑎 ≥ 10
𝑎𝑙𝑔𝑢𝑚𝑎 𝑐𝑜𝑖𝑠𝑎 ≥ 30
𝑎𝑙𝑔𝑢𝑚𝑎 𝑐𝑜𝑖𝑠𝑎 ≥ 18
 Mas o que seria o “alguma coisa”?
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 O que deve ser maior que a quantidade mínima a ser consumida é a
quantidade de nutrientes por alimento multiplicado pela quantidade
de alimento que será consumido. Correto?!?
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 O que deve ser maior que a quantidade mínima a ser consumida é a
quantidade de nutrientes por alimento multiplicado pela quantidade
de alimento que será consumido. Correto?!?
 Desde modo, o que deve ser maior que 10 (valor mínimo do
nutriente A) é a quantidade de alimentos a serem consumidos
multiplicados pelo valor de nutrientes A existentes em cada
alimento. Ou seja:
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 O que deve ser maior que a quantidade mínima a ser consumida é a
quantidade de nutrientes por alimento multiplicado pela quantidade
de alimento que será consumido. Correto?!?
 Desde modo, o que deve ser maior que 10 (valor mínimo do
nutriente A) é a quantidade de alimentos a serem consumidos
multiplicados pelo valor de nutrientes A existentes em cada
alimento. Ou seja:
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 Deste modo, realizando o mesmo processo para todos os nutrientes,
temos que:
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 Deste modo, realizando o mesmo processo para todos os nutrientes,
temos que:
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 Deste modo, realizando o mesmo processo para todos os nutrientes,
temos que:
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
2𝑥𝐴1 + 𝑥𝐴2 + 3𝑥𝐴4 + 2𝑥𝐴5 ≥ 30
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
 4º PASSO: construir as restrições do problema
 Deste modo, realizando o mesmo processo para todos os nutrientes,
temos que:
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
2𝑥𝐴1 + 𝑥𝐴2 + 3𝑥𝐴4 + 2𝑥𝐴5 ≥ 30
3𝑥𝐴1 + 𝑥𝐴2 + 9𝑥𝐴4 ≥ 18
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
𝑀𝐼𝑁 4𝑥𝐴1 + 2𝑥𝐴2 + 𝑥𝐴3 + 10𝑥𝐴4 + 5𝑥𝐴5
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
𝑀𝐼𝑁 4𝑥𝐴1 + 2𝑥𝐴2 + 𝑥𝐴3 + 10𝑥𝐴4 + 5𝑥𝐴5
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
2𝑥𝐴1 + 𝑥𝐴2 + 3𝑥𝐴4 + 2𝑥𝐴5 ≥ 30
3𝑥𝐴1 + 𝑥𝐴2 + 9𝑥𝐴4 ≥ 18
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
𝑀𝐼𝑁 4𝑥𝐴1 + 2𝑥𝐴2 + 𝑥𝐴3 + 10𝑥𝐴4 + 5𝑥𝐴5
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
2𝑥𝐴1 + 𝑥𝐴2 + 3𝑥𝐴4 + 2𝑥𝐴5 ≥ 30
3𝑥𝐴1 + 𝑥𝐴2 + 9𝑥𝐴4 ≥ 18
TRANSFORMANDO AS DEFINIÇÕES EM UM MODELO
𝑀𝐼𝑁 𝑐𝑇𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑁𝑥𝑁
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
𝐴𝑥 ≥ 𝑏
𝑥 ≥ 0
𝑥 ∈ 𝑅𝑁
𝑀𝐼𝑁 4𝑥𝐴1 + 2𝑥𝐴2 + 𝑥𝐴3 + 10𝑥𝐴4 + 5𝑥𝐴5
𝑥𝐴2 + 5𝑥𝐴3 + 4𝑥𝐴4 + 3𝑥𝐴5 ≥ 10
2𝑥𝐴1 + 𝑥𝐴2 + 3𝑥𝐴4 + 2𝑥𝐴5 ≥ 30
3𝑥𝐴1 + 𝑥𝐴2 + 9𝑥𝐴4 ≥ 18
𝑥𝐴1, 𝑥𝐴2, 𝑥𝐴3, 𝑥𝐴4, 𝑥𝐴5 ≥ 0