Introdução à Programação Linear

Prévia do material em texto

Pesquisa Operacional I
Modelagem Matemática
Prof. Renan José dos Santos Viana
Sala: CCE 303-B
renanjviana@gmail.com
Baseado no material produzido pelo prof. José Elias C. Arroyo
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Revisão da Aula Anterior
• Programação Matemática:
– Programação linear
– Programação inteira
– Programação não-linear
– ...
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Revisão da Aula Anterior
• Fases da PO:
1. Definição do problema
2. Construção do modelo
3. Resolução do modelo
4. Validação do modelo
5. Implantação da solução
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Revisão da Aula Anterior
• Fases:
1. Definição do problema
2. Construção do modelo
3. Resolução do modelo
4. Validação do modelo
5. Implantação da solução
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
1- Utilização de algoritmos ou métodos 
de resolução.
2- Análise de sensibilidade.
Conteúdo desta Aula
• Introdução à Programação Linear (PL).
• Resolução de problemas de PL pelo Método Gráfico.
• Introdução ao Método Simplex para resolução de
problemas de PL.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• O termo programação significa planejamento.
• O termo Linear é relativo a funções, equações ou
inequações lineares.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Programação Linear (PL) ou também Otimização
Linear consiste na otimização (minimização ou
maximização) de uma função linear enquanto
satisfaz um conjunto de restrições representadas por
equações e/ou inequações lineares.
• As restrições representam, geralmente, limitações de
recursos disponíveis (capital, mão de obra, matéria
prima, etc.) ou exigências que devem ser cumpridas
(satisfazer demandas, etc.).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Um problema de programação linear é um problema
de otimização para o qual:
– Tentamos maximizar (ou minimizar) uma função linear de
variáveis de decisão. Esta função é chamada de função objetivo.
– Os valores das variáveis de decisão devem satisfazer um
conjunto de restrições. Cada restrição deve ser uma equação
linear ou uma inequação linear.
– Uma restrição de sinal é associada a cada variável. Para
qualquer variável 𝑥𝑖 , a restrição de sinal deve ser: ou não-
negativa (𝑥𝑖 ≥ 0) ou irrestrita em sinal (pode assumir tanto
valores positivos quanto negativos, ou zero).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Passos fundamentais para resolver um problema de
PL:
– Modelagem do problema.
– Utilização de um método de solução.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Observações:
– A solução é do modelo, não do problema original.
– Se o modelo for muito simples, a solução pode não fazer
sentido na prática.
– Se o modelo for muito complexo, pode ser difícil encontrar
sua solução.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• Variáveis de decisão:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• Variáveis de decisão:
– São as variáveis cujos valores devem ser calculados.
– Representam as quantidades de atividades/itens/produtos
a serem realizadas/alocados/produzidos.
– O conjunto das variáveis de decisão forma uma solução do
problema.
– Podem ser contínuas, discretas ou binárias.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• Função objetivo:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• Função objetivo:
– Função matemática que determina o valor alvo que se
pretende alcançar ou a qualidade da solução.
– É uma meta (critério) do problema a ser otimizada.
– Mede o “valor” da solução.
– Exemplos: minimizar os custos, minimizar o tempo de
produção, maximizar o lucro da produção, etc.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• Restrições:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• Restrições:
– São as condições do problema a serem satisfeitas pelas
soluções.
– Restringem os valores das variáveis de decisão.
– Exemplos:
• Os produtos devem ser produzidos utilizando somente os recursos
disponíveis (capital, matéria prima e etc.).
• O produto fabricado deve atender alguns requisitos mínimos
(segurança, necessidade nutricional, etc.).
• A produção de um produto deve atender o mínimo de unidades
exigido pelo mercado (demanda de mercado e etc.).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Componentes de um Modelo PL
• A função objetivo e as restrições são expressões
lineares (funções) definidas em termos das variáveis
de decisão.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Problema de programação linear (n variáveis e m
restrições):
Max/Min 𝑓(𝑥1, … 𝑥𝑛) = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛
Sujeito a:
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≥ (≤,=) 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 +⋯+ 𝑎2𝑛𝑥𝑛 ≥ ≤,= 𝑏2
... ... ... ... ... ...
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≥ ≤,= 𝑏𝑚
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Problema de programação linear:
Max/Min 𝑓(𝑥1, … 𝑥𝑛) = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛
Sujeito a:
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≥ (≤,=)𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 +⋯+ 𝑎2𝑛𝑥𝑛 ≥ ≤,= 𝑏2
... ... ... ... ... ...
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≥ ≤,= 𝑏𝑚
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Função Objetivo
Programação Linear
• Problema de programação linear:
Max/Min 𝑓(𝑥1, …𝑥𝑛) = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛
Sujeito a:
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≥ (≤,=)𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 +⋯+ 𝑎2𝑛𝑥𝑛 ≥ ≤,= 𝑏2
... ... ... ... ... ...
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≥ ≤,= 𝑏𝑚
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Restrições
Técnicas
Função Objetivo
Programação Linear
• Problema de programação linear:
Max/Min 𝑓(𝑥1, … 𝑥𝑛) = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛
Sujeito a:
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≥ (≤,=)𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 +⋯+ 𝑎2𝑛𝑥𝑛 ≥ ≤,= 𝑏2
... ... ... ... ... ...
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≥ ≤,= 𝑏𝑚
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Restrições
Técnicas
Restrições de não-negatividade
Função Objetivo
Programação Linear
• 𝒇: Função objetivo (Função critério)
• 𝒄𝒊: coeficientes da função objetivo (lucro/custo), i = 1,...,n
• 𝒙𝒊: variáveis de decisão, i = 1,...,n
• 𝒂𝒋𝒊: coeficientes tecnológicos, i = 1,...,n e j = 1,...,m
• 𝒃𝒋: constantes do lado direito, j = 1,...,m
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Programação Linear
• Modelo de PL na forma matricial:
Minimizar ou Maximizar 𝑓 𝑥 = 𝑐𝑥
Sujeito a: 𝐴𝑥 ≤ 𝑏
𝑥 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Uma fábrica produz 4 tipos de cadeiras.
• São usados 2 tipos de materiais: lâminas de madeira
e tecido (recursos escassos).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
50 lâminas/semana 75 metros/semana
Problema de PL
• A fábrica precisa decidir quais modelos de cadeira
deve produzir e quantas unidades de cada um, de tal
maneira que o lucro seja maximizado.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Variáveis de decisão:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Variáveis de decisão:
𝑥𝑖 = Quantidade (unidades) de cadeiras produzidas do modelo i
(𝑖 = 1,2,3,4).
Estas variáveis de decisão devem ser não negativas (𝑥𝑖 ≥ 0, 𝑖 =
1,2,3,4).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Função objetivo:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Função objetivo:
Maximizar o lucro total gerado pela fabricação de todas as
cadeiras.
Maximizar Lucro total = 𝟏𝟓𝟎𝒙𝟏 + 𝟑𝟎𝟎𝒙𝟐 + 𝟑𝟎𝟎𝒙𝟑 + 𝟐𝟎𝟎𝒙𝟒
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Restrições:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Restrições:
Disponibilidade de matéria prima (Recursos Disponíveis).
O total de lâminas de madeira utilizado na fabricação de todos
os modelos de cadeira não deve ultrapassar 50 lâminas.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Restrições:
Disponibilidade de matéria prima (Recursos Disponíveis).
O total de lâminas de madeira utilizado na fabricação de todos
os modelos de cadeira não deve ultrapassar 50 lâminas.
𝟏𝒙𝟏 + 𝟒𝒙𝟐 + 𝟑𝒙𝟑 + 𝟏𝒙𝟒 ≤ 𝟓𝟎
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Restrições:
Disponibilidade de matéria prima (Recursos Disponíveis).
O total de tecido utilizado na fabricação de todos os modelos de
cadeira não deve ultrapassar 75 metros.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
• Restrições:
Disponibilidade de matéria prima (Recursos Disponíveis).
O total de tecido utilizado na fabricação de todos os modelos de
cadeira não deve ultrapassar 75 metros.
𝟏𝒙𝟏 + 𝟏𝒙𝟐 + 𝟏𝒙𝟑 + 𝟐𝒙𝟒 ≤ 𝟕𝟓
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de PL
𝑥𝑖 = Quantidade (unidades) de cadeiras produzidas do modelo i
(𝑖 = 1,2,3,4).
Maximizar 150𝑥1 + 300𝑥2 + 300𝑥3 + 200𝑥4
Sujeito a:
1𝑥1 + 4𝑥2 + 3𝑥3 + 1𝑥4 ≤ 50
1𝑥1 + 1𝑥2 + 1𝑥3 + 2𝑥4 ≤ 75
𝑥1, 𝑥2, 𝑥3, 𝑥4 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Restrições Técnicas
Restrições de não-negatividade
Função Objetivo 
ou Função Lucro
Variáveis de Decisão
Propriedades do Modelo de PL
• Proporcionalidade: Requer que a contribuição de cada
variável de decisão, tanto na função objetivo quanto nas
restrições, seja diretamente proporcional ao valor da
variável.
• Aditividade: Requer que a contribuição total de todas as
variáveis da função objetivo e das restrições seja a soma
direta das contribuições individuais de cada variável.
• Certeza: Todos os coeficientes da função objetivo e das
restrições do modelo de PL são determinísticos, ou seja,
são constantes conhecidas.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Propriedades do Modelo de PL
• Proporcionalidade: Na realidade,
– Assumimos que as fábricas obtêm lucro proporcional à
quantidade produzida.
– Na prática, é difícil que isso aconteça.
– Por exemplo: Conceder algum tipo de desconto quando as
vendas ultrapassarem certas quantidades.
– Mas isso resultaria em um modelo mais difícil (complexo)
de ser solucionado (provavelmente não de PL).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Propriedades do Modelo de PL
• Aditividade: Na realidade,
– Assumimos que o lucro é a soma dos lucros individuais
(não há sinergia ou efeito de substituição).
– Na prática, os produtos podem competir no mercado (a
venda de um atrapalha a venda do outro).
– Ou podem depender um do outro (conjunto mesa +
cadeiras).
– Mas isso resultaria em um modelo mais difícil (complexo)
de ser solucionado (provavelmente não de PL).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Propriedades do Modelo de PL
• Certeza: Na realidade,
– Assumimos que o lucro e o uso de recursos são conhecidos
e exatos (não são variáveis aleatórias).
– Na prática, isso é raro.
– O mais provável é que sejam representados por uma
distribuição de probabilidade.
– Mas isso resultaria em um modelo mais difícil (complexo)
de ser solucionado (provavelmente não de PL).Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Tipos de Soluções
• Uma solução do modelo é composta por um
conjunto formado por valores das variáveis de
decisão 𝑥 = 𝑥1, … , 𝑥𝑛 e pode ser de três tipos:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Tipos de Soluções
• Uma solução do modelo é composta por um
conjunto formado por valores das variáveis de
decisão 𝑥 = 𝑥1, … , 𝑥𝑛 e pode ser de três tipos:
– Solução factível ou viável: é uma solução que satisfaz
todas as restrições do modelo, inclusive as restrições de
não-negatividade.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Tipos de Soluções
• Uma solução do modelo é composta por um
conjunto formado por valores das variáveis de
decisão 𝑥 = 𝑥1, … , 𝑥𝑛 e pode ser de três tipos:
– Solução factível ou viável: é uma solução que satisfaz
todas as restrições do modelo, inclusive as restrições de
não-negatividade.
– Solução infactível ou inviável: é uma solução que não
satisfaz pelo menos uma das restrições do modelo.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Tipos de Soluções
• Uma solução do modelo é composta por um
conjunto formado por valores das variáveis de
decisão 𝑥 = 𝑥1, … , 𝑥𝑛 e pode ser de três tipos:
– Solução factível ou viável: é uma solução que satisfaz
todas as restrições do modelo, inclusive as restrições de
não-negatividade.
– Solução infactível ou inviável: é uma solução que não
satisfaz pelo menos uma das restrições do modelo.
– Solução ótima é uma solução viável que determina o valor
máximo (Maximização) ou o valor mínimo (Minimização)
da função objetivo do modelo.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Tipos de Soluções
• Uma solução 𝑥∗ é ótima se:
– 𝑓 𝑥∗ ≤ 𝑓 𝑥 , para toda solução factível 𝑥 (ou seja, para
𝑥∗ obtêm-se o menor valor de 𝑓) no caso de minimização.
– 𝑓 𝑥∗ ≥ 𝑓 𝑥 , para toda solução factível 𝑥 (ou seja, para
𝑥∗ obtêm-se o maior valor de 𝑓) no caso de maximização.
• O conjunto de todas as soluções viáveis compõem a
região viável ou espaço viável de soluções.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• A Reddy Mikks produz tintas para interiores e exteriores
com base em duas matérias-primas, M1 e M2, A tabela
abaixo apresenta os dados básicos do problema:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Toneladas de matéria-prima por 
tonelada de
Tinta para 
exteriores
Tinta para 
interiores
Disponibilidade 
máxima diária 
(ton)
Matéria-prima 
M1
6 4 24
Matéria-prima
M2
1 2 6
Lucro por 
tonelada ($ 
1.000)
5 4
Problema: Companhia Reddy Mikks
• Uma pesquisa de mercado indica que a demanda
diária de tintas para interiores não pode ultrapassar
a de tintas para exteriores por mais de 1 tonelada.
Além disso, a demanda máxima diária de tinta para
interiores é de 2 toneladas.
• A Reddy Mikks quer determinar o mix ótimo (o
melhor) de produtos de tintas para interiores e
exteriores que maximize o lucro total diário.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• Variáveis de decisão do modelo são definidas como:
– 𝑥1: toneladas de tinta para exteriores produzidas 
diariamente.
– 𝑥2: toneladas de tinta para interiores produzidas 
diariamente.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• Variáveis de decisão do modelo são definidas como:
– 𝑥1: toneladas de tinta para exteriores produzidas 
diariamente.
– 𝑥2: toneladas de tinta para interiores produzidas 
diariamente.
• Representando o lucro total diário (em milhares de 
dólares) por 𝑧, o objetivo da empresa é (função 
objetivo do modelo):
– Maximizar 𝑧 = 5𝑥1 + 4𝑥2
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• As restrições que limitam a utilização da matéria-prima e
a demanda do produto são construídas da seguinte
maneira:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• As restrições que limitam a utilização da matéria-prima e
a demanda do produto são construídas da seguinte
maneira:
– A utilização por dia da matéria-prima M1 é de 6t por tonelada de tinta
para exteriores e de 4t por tonelada de tinta para interiores. Como a
disponibilidade diária da matéria-prima M1 está limitada a 24t, a
restrição é definida como: 𝟔𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐𝟒.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• As restrições que limitam a utilização da matéria-prima e
a demanda do produto são construídas da seguinte
maneira:
– A utilização por dia da matéria-prima M1 é de 6t por tonelada de tinta
para exteriores e de 4t por tonelada de tinta para interiores. Como a
disponibilidade diária da matéria-prima M1 está limitada a 24t, a
restrição é definida como: 𝟔𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐𝟒.
– A utilização por dia da matéria-prima M2 é de 1t por tonelada de tinta
para exteriores e de 2t por tonelada de tinta para interiores. Como a
disponibilidade diária da matéria-prima M2 está limitada a 6t, a
restrição é definida como: 𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟔.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
– A primeira restrição relacionada à demanda estipula que o
excesso da produção diária de tintas para interiores em relação
à de tintas para exteriores, 𝑥2 − 𝑥1, não deve ultrapassar 1t
(limite de mercado), sendo assim definida como: 𝑥2 − 𝑥1 ≤ 1.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
– A primeira restrição relacionada à demanda estipula que o
excesso da produção diária de tintas para interiores em relação
à de tintas para exteriores, 𝑥2 − 𝑥1, não deve ultrapassar 1t
(limite de mercado), sendo assim definida como: 𝑥2 − 𝑥1 ≤ 1.
– A segunda restrição relacionada à demanda estipula que a
demanda diária máxima de tinta para interiores está limitada a
2t (limite de demanda), sendo assim definida como 𝑥2 ≤ 2.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
– A primeira restrição relacionada à demanda estipula que o
excesso da produção diária de tintas para interiores em relação
à de tintas para exteriores, 𝑥2 − 𝑥1, não deve ultrapassar 1t
(limite de mercado), sendo assim definida como: 𝑥2 − 𝑥1 ≤ 1.
– A segundarestrição relacionada à demanda estipula que a
demanda diária máxima de tinta para interiores está limitada a
2t (limite de demanda), sendo assim definida como 𝑥2 ≤ 2.
– As variáveis 𝑥1e 𝑥2não podem assumir valores negativos.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• O modelo completo da Reddy Mikks é:
Maximizar 𝑧 = 5𝑥1 + 4𝑥2
Sujeito a:
6𝑥1 + 4𝑥2 ≤ 24 (1)
𝑥1 + 2𝑥2 ≤ 6 (2)
−𝑥1 + 𝑥2 ≤ 1 (3)
𝑥2≤ 2 (4)
𝑥1, 𝑥2 ≥ 0 (5)
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• Quaisquer valores de 𝑥1 e 𝑥2 que satisfazem todas as
cinco restrições constituem uma solução viável. Caso
contrário, a solução é inviável.
• A meta do problema é achar a melhor solução viável, ou
a solução ótima, que maximize o lucro total.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• Exemplo de soluções:
– Solução (𝑥1, 𝑥2) = (3, 1), viável.
6 × 3 + 4 × 1 ≤ 24 (1)
3 + 2 × 1 ≤ 6 (2)
−3 + 1 ≤ 1 (3)
1≤ 2 (4)
3 , 1 ≥ 0 (5)
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema: Companhia Reddy Mikks
• Exemplo de soluções:
– Solução (𝑥1, 𝑥2) = (4, 1), inviável.
6 × 4 + 4 × 1 ≤ 24 (1)
4 + 2 × 1 ≤ 6 (2)
−4 + 1 ≤ 1 (3)
1≤ 2 (4)
4 , 1 ≥ 0 (5)
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Matéria-prima M1 
insuficiente
Problema: Companhia Reddy Mikks
• O problema Reddy Mikks tem um número infinito de
soluções viáveis.
• Impossível a resolução do problema por enumeração.
• Utilizar um procedimento sistemático que localizará a
solução ótima em um número finito de etapas.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Uma marcenaria deseja estabelecer uma programação
diária da produção. São fabricados apenas dois produtos:
mesas e armários, ambos de um só modelo. Vamos
considerar que a marcenaria tem limitações diárias nos
seguintes recursos: madeira e mão-de-obra.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Quantidade de recurso por 
unidade
Mesa Armário Disponibilidade
Madeira 2𝑚2 3𝑚2 12𝑚2
Mão-de-obra 2h/H 1h/H 8 horas/ 
Homem
Lucro R$ 40 R$ 10
Problema da Marcenaria
• O problema do fabricante é encontrar o programa de
produção que maximiza a margem de contribuição
total para o lucro.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Variáveis de decisão:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Variáveis de decisão:
𝑥1 = quantidade de mesas produzidas diariamente
𝑥2 = quantidade de armários produzidas diariamente
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Variáveis de decisão:
𝑥1 = quantidade de mesas produzidas diariamente
𝑥2 = quantidade de armários produzidas diariamente
• Função objetivo:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Variáveis de decisão:
𝑥1 = quantidade de mesas produzidas diariamente
𝑥2 = quantidade de armários produzidas diariamente
• Função objetivo:
Maximizar 𝑓 𝑥1, 𝑥2 = 40𝑥1 + 10𝑥2
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Variáveis de decisão:
𝑥1 = quantidade de mesas produzidas diariamente
𝑥2 = quantidade de armários produzidas diariamente
• Função objetivo:
Maximizar 𝑓 𝑥1, 𝑥2 = 40𝑥1 + 10𝑥2
• Sujeito a:
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Variáveis de decisão:
𝑥1 = quantidade de mesas produzidas diariamente
𝑥2 = quantidade de armários produzidas diariamente
• Função objetivo:
Maximizar 𝑓 𝑥1, 𝑥2 = 40𝑥1 + 10𝑥2
• Sujeito a:
2𝑥1 + 3𝑥2 ≤ 12 Disponibilidade de madeira
2𝑥1 + 1𝑥2 ≤ 8 Disponibilidade de mão-de-obra
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
Maximizar 𝑓 𝑥1, 𝑥2 = 40𝑥1 + 10𝑥2
• Sujeito a:
2𝑥1 + 3𝑥2 ≤ 12
2𝑥1 + 1𝑥2 ≤ 8
𝑥1 ≥ 0, 𝑥2 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Se a marcenaria fabricar por dia 2 mesas e 2
armários, o lucro seria:
𝑓 2, 2 = 40 × 2 + 10 × 2 = 𝑅$ 100
• Note que a solução é viável pois satisfaz todas as
restrições do modelo:
2 × 2 + 3 × 2 = 10 ≤ 12
2 × 2 + 1 × 2 = 6 ≤ 8
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Se a marcenaria fabricar por dia 3 mesas e 3
armários, o lucro seria:
𝑓 3, 3 = 40 × 3 + 10 × 3 = 𝑅$ 150
• Note que a solução é inviável pois viola as duas
restrições de disponibilidade de recursos do modelo:
2 × 3 + 3 × 3 = 15 ≤ 12
2 × 3 + 1 × 3 = 9 ≤ 8
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Se a marcenaria fabricar por dia 2 mesas e 3
armários, o lucro seria:
𝑓 2, 3 = 40 × 2 + 10 × 3 = 𝑅$ 110
• Note que a solução é inviável pois viola a 1° restrição
de disponibilidade de recurso do modelo:
2 × 2 + 3 × 3 = 13 ≤ 12
2 × 2 + 1 × 3 = 7 ≤ 8
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Marcenaria
• Se a marcenaria fabricar por dia 3 mesas e 2
armários, o lucro seria:
𝑓 3, 2 = 40 × 3 + 10 × 2 = 𝑅$ 140
• Note que a solução é viável pois satisfaz todas as
restrições do modelo:
2 × 3 + 3 × 2 = 12 ≤ 12
2 × 3 + 1 × 2 = 8 ≤ 8
• Note que esta solução é melhor do que a primeira.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Refinaria
• A refinaria de petróleo Recap destila óleo cru proveniente de duas
fontes, Arábia e Venezuela e produz três produtos: gasolina,
querosene e lubrificantes. Os óleos têm diferentes composições
químicas e fornecem diferentes quantidades de destilados por
barril processado. Cada barril de óleo cru da Arábia dá 0,3 barril de
gasolina, 0,4 de querosene e 0,2 de lubrificante. Para o óleo da
Venezuela estas quantidades são respectivamente: 0,4, 0,2 e 0,3.
Há 10% de resíduos.Os óleos diferem em custo e disponibilidade. A
Recap pode comprar até 9000 barris da Arábia a $20 o barril e até
6000 barris da Venezuela a $15 o barril. Contratos da Recap com
distribuidores exigem que ela produza 2000 barris de gasolina,
1500 barris de querosene e 500 de lubrificantes por dia. Como
cumprir os contratos gastando o mínimo? (qual o mix de compra
dos óleos).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Refinaria
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a Produtos Arábia (barril) Venezuela (barril) Demanda (barris)
Gasolina 0,3 0,4 2.000
Querosene 0,4 0,2 1.500
Lubrificante 0,2 0,3 500
Custo por barril R$ 20 R$ 15
Oferta (barris) 9.000 6.000
Problema da Refinaria
• Variáveis de decisão:
𝑥1 = quantidade de barris de óleo/dia vindos da Arábia.
𝑥2 = quantidade de barris de óleo/dia vindos da Venezuela.
• Função objetivo:
Minimizar z = 20𝑥1 + 15𝑥2
• Restrições:
0,3𝑥1 + 0,4𝑥2 ≥ 2000 barris (Demanda gasolina)
0,4𝑥1 + 0,2𝑥2 ≥ 1500 barris (Demanda querosene)
0,2𝑥1 + 0,3𝑥2 ≥ 500 barris (Demanda lubrificantes)
𝑥1 ≤ 9000 barris (Oferta Arábia)
𝑥2 ≤ 6000 barris (Oferta Venezuela)
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Refinaria
Minimizar z = 20𝑥1 + 15𝑥2 (custo total)
Sujeito a:
0,3𝑥1 + 0,4𝑥2 ≥ 2000
0,4𝑥1 + 0,2𝑥2 ≥ 1500
0,2𝑥1 + 0,3𝑥2 ≥ 500
𝑥1 ≤ 9000
𝑥2 ≤ 6000
𝑥1 ≥ 0
𝑥2 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Dieta
• O objetivo do problema é determinar a quantidade
de determinados alimentos a serem usados em uma
dieta (ou ração).
• A dieta deve conter as quantidades mínimas
(necessárias) de determinados nutrientes.
• O custo total dos alimentos utilizados na dieta deve
ser minimizado.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Dieta
• Na tabela abaixo estão os alimentos que podem ser
utilizados em um dieta, o preço dos alimentos, a
quantidade de nutrientes contidos em 100 gramas
de cada alimento e a necessidade mínima de cada
nutriente na dieta.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Dieta
𝑥𝑖 = quantidade do alimento i a ser inserida na dieta, (𝑖 =
Carne, Arroz, Feijão, Açúcar, Alface, laranja).
Min z = 0,5𝑥1 + 0,18𝑥2 + 0,2𝑥3 + 0,16𝑥4 + 0,3𝑥5 + 0,1𝑥6
Sujeito a:
225𝑥1 + 364𝑥2 + 337𝑥3 + 385𝑥4 + 15𝑥5 + 42𝑥6 ≥ 3200
7𝑥1 + 0𝑥2 + 2𝑥3 + 0𝑥4 + 87𝑥5 + 13𝑥6 ≥ 750
0𝑥1 + 0𝑥2 + 3𝑥3 + 0𝑥4 + 12𝑥5 + 59𝑥6 ≥ 70
2,9𝑥1 + 1,3𝑥2 + 7,6𝑥3 + 0,1𝑥4 + 1,3𝑥5 + 0,7𝑥6 ≥ 10
11𝑥1 + 9𝑥2 + 86𝑥3 + 0𝑥4 + 43𝑥5 + 34𝑥6 ≥ 650
𝑥𝑖 ≥ 0, ∀ 𝑖 = 1,… 6
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Transporte
• Considere uma companhia distribuidora de bebidas que tem 2
centros de produção: Araraquara e São José dos Campos – e 3
mercados consumidores principais: São Paulo, Belo Horizonte
e Rio de Janeiro. Na tabela a seguir são mostrados os custos
unitários de se transportar uma caixa de bebida de cada
centro de produção para cada mercado consumidor, as
demandas diárias de cada mercado e a número de caixas
disponíveis diariamente em cada centro de produção. Deseja-
se minimizar o custo total de transporte de bebidas dos
diversos centros de produção em quantia suficiente para
suprir as demandas dos mercados.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Transporte
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Transporte
𝑥𝑖𝑗 = Quantidade de caixas a ser enviada do centro de produção 𝑖
para o mercado 𝑗. Sendo 𝑖 = 1 (Araraquara), 𝑖 = 2 (S.J. Campos), j= 1
(SP), j= 2 (BH), j= 3 (RJ).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Transporte
𝑥𝑖𝑗 = Quantidade de caixas a ser enviada do centro de produção 𝑖
para o mercado 𝑗. Sendo 𝑖 = 1 (Araraquara), 𝑖 = 2 (S.J. Campos), j= 1
(SP), j= 2 (BH), j= 3 (RJ).
Min 𝑓 𝑥11…𝑥23 = 4𝑥11 + 2𝑥12 + 5𝑥13 + 11𝑥21 + 7𝑥22 + 4𝑥23
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Transporte
𝑥𝑖𝑗 = Quantidade de caixas a ser enviada do centro de produção 𝑖
para o mercado 𝑗. Sendo 𝑖 = 1 (Araraquara), 𝑖 = 2 (S.J. Campos), j = 1
(SP), j = 2 (BH), j = 3 (RJ).
Min 𝑓 𝑥11…𝑥23 = 4𝑥11 + 2𝑥12 + 5𝑥13 + 11𝑥21 + 7𝑥22 + 4𝑥23
Sujeito a:
𝑥11 + 𝑥12 + 𝑥13 ≤ 800 (oferta Araraquara)
𝑥21 + 𝑥22 + 𝑥23 ≤ 1000 (oferta S.J. Campos)
𝑥11 + 𝑥21 ≥ 500 (demanda SP)
𝑥12 + 𝑥22 ≥ 400 (demanda BH)
𝑥13 + 𝑥23 ≥ 900 (demanda RJ)
𝑥11, 𝑥12, 𝑥13, 𝑥21, 𝑥22, 𝑥23 ≥ 0
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Alocação de Recursos
• Um gerente está executando o planejamento da produção de
3 produtos em 4 máquinas. Todos os produtos podem ser
fabricados por todas as maquinas.
• Há uma demanda (pedidos) de 4000, 5000, 3000 unidades
para os produtos 1, 2 e 3, respectivamente. As máquinas
utilizadas na produção estão disponíveis por uma quantidade
determinada de horas e cada unidade de um produto requer
uma quantidade fixa de horas em cada máquina de acordo
com a tabela a seguir.
• Deseja-se minimizar o custo total de produção.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Alocação de Recursos
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Alocação de Recursos
• Variáveis de decisão:
𝑥𝑖𝑗 = Quantidade do produto 𝑖 produzido na máquina 𝑗
(unidades).
(𝑖 = 1,2,3; 𝑗 = 1,2,3,4).
• Função objetivo (Custo total de produção):
Min 𝑓 = 4𝑥11 + 4𝑥12 + 5𝑥13 + 7𝑥14 + 6𝑥21 + 7𝑥22 + 5𝑥23 +
6𝑥24 + 12𝑥31 + 10𝑥32 + 8𝑥33 + 11𝑥34
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema de Alocação de Recursos
• Restrições:
Demanda de produtos
𝑥11 + 𝑥12 + 𝑥13 + 𝑥14 ≥ 4000 (Produto 1)
𝑥21 + 𝑥22 + 𝑥23 + 𝑥24 ≥ 5000 (Produto 2)
𝑥31 + 𝑥32 + 𝑥33 + 𝑥34 ≥ 3000 (Produto 3)
Capacidade de produção das máquinas
0,3𝑥11 + 0,2𝑥21 + 0,8𝑥31 ≤ 1500 (Maquina 1)
0,25𝑥12 + 0,3𝑥22 + 0,6𝑥32 ≤ 1200 (Maquina 2)
0,2𝑥13 + 0,2𝑥23 + 0,6𝑥33 ≤ 1500 (Maquina 3)
0,2𝑥14 + 0,25𝑥24 + 0,5𝑥34 ≤ 2000 (Maquina 4)
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Mistura de Petróleo
• Uma refinaria processa vários tipos de petróleo. Cada tipo de
petróleopossui 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 de gasolina obtida.
• Supondo que a refinaria trabalhe com uma linha de quatro tipos
diferentes de petróleo e deseja produzir três tipos de gasolina,
programar a mistura de tipos de petróleo atendendo às condições
que seguem nas tabelas a seguir.
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Mistura de Petróleo
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Tipo de Petróleo Qtd Disponível (Barril/dia) Custo por Barril/dia (R$)
1 3.500 19
2 2.200 24
3 4.200 20
4 1.800 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
Problema da Mistura de Petróleo
• Variáveis de decisão:
𝑥𝑖𝑗 = número de barris de petróleo do tipo 𝑗 (𝑗 = 1,2,3,4), que
serão destinados à produção da gasolina 𝑖 (𝑖 = A - gasolina
Amarela, Z - gasolina Azul, S - gasolina SuperAzul).
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Mistura de Petróleo
• Função objetivo:
Maximizar 𝑧 = 22 × 𝑥𝐴1 + 𝑥𝐴2 + 𝑥𝐴3 + 𝑥𝐴4
+28 × 𝑥𝑍1 + 𝑥𝑍2 + 𝑥𝑍3 + 𝑥𝑍4
+35 × (𝑥𝑆1 + 𝑥𝑆2 + 𝑥𝑆3 + 𝑥𝑆4)
−19 × (𝑥𝐴1 + 𝑥𝑍1 + 𝑥𝑆1)
−24 × 𝑥𝐴2 + 𝑥𝑍2 + 𝑥𝑆2
−20 × (𝑥𝐴3 + 𝑥𝑍3 + 𝑥𝑆3)
−27 × (𝑥𝐴4 + 𝑥𝑍4 + 𝑥𝑆4)
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Mistura de Petróleo
• Restrições:
Restrições associadas à quantidade de petróleo disponível:
𝑥𝐴1 + 𝑥𝑍1 + 𝑥𝑆1 ≤ 3500
𝑥𝐴2 + 𝑥𝑍2 + 𝑥𝑆2 ≤ 2200
𝑥𝐴3 + 𝑥𝑍3 + 𝑥𝑆3 ≤ 4200
𝑥𝐴4 + 𝑥𝑍4 + 𝑥𝑆4 ≤ 1800
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Problema da Mistura de Petróleo
• Restrições:
Restrições associadas às especificações da mistura:
𝑥𝑆1 ≤ 0.3 𝑥𝑆1 + 𝑥𝑆2 + 𝑥𝑆3 +𝑥𝑆4
𝑥𝑆2 ≥ 0.4 𝑥𝑆1 + 𝑥𝑆2 + 𝑥𝑆3 +𝑥𝑆4
𝑥𝑆3 ≤ 0.5 𝑥𝑆1 + 𝑥𝑆2 + 𝑥𝑆3 +𝑥𝑆4
𝑥𝑍1 ≤0,3 𝑥𝑍1 + 𝑥𝑍2 + 𝑥𝑍3 +𝑥𝑍4
𝑥𝑍2 ≥0,1 𝑥𝑍1 + 𝑥𝑍2 + 𝑥𝑍3 +𝑥𝑍4
𝑥𝐴1 ≤ 0,7 𝑥𝐴1 + 𝑥𝐴2 + 𝑥𝐴3 +𝑥𝐴4
Restrições de não-negatividade
𝑥𝑖𝑗 ≥ 0, ∀ 𝑖 = 𝐴, 𝑍, 𝑆 , 𝑗 = {1,2,3,4}
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a
Perguntas
Universidade Federal de Viçosa
Departamento de Informática
U
FV
 -
D
e
p
ar
ta
m
en
to
 d
e
 In
fo
rm
át
ic
a