Introdução à Construção de
Modelos de Otimização Linear
Contínua e Inteira
Maria do Socorro Nogueira Rangel
DCCE
Departamento de Ciências da Computação e Estatística
e-mail: [email protected]
Apoio
:
http://www.dcce.ibilce.unesp.br/~socorro/
Sumário
 Construção de Modelos
 Ferramentas Computacionais
 Modelos de Otimização Linear e Inteira
2
Construção de Modelos
Motivação
"Existem duas maneiras de aumentar a eficiência de
uma loja, empresa, ou indústria. Uma delas requer
a melhoria tecnológica, isto é, atualização dos
equipamentos, mudança no processo tecnológico,
descoberta de novos e melhores tipos de matéria
prima. A outra maneira, até hoje muito menos
utilizada, envolve melhorias na organização do
planejamento e da produção. Isto é, melhorias no
processo de distribuição do trabalho entre as
máquinas da empresa, distribuição de matéria
prima, combustível, entre outros fatores."
(Kantarovich (1939) in Dantzig, 1963, pg 22)
3
Construção de Modelos
Motivação
 Por que usar modelos matemáticos para
auxiliar a tomada de decisão?
– Solução matemática X solução impírica
– Melhor entendimento da empresa
– Ferramenta de apoio a tomada de decisão
4
Construção de Modelos
Processo de Construção de um Modelo Matemático
Sistema Real
Simplificação
Definição e
Descrição do Problema
Revisão
Modelo Matemático
Solução do Modelo
Decisão
Teórica x Política
Implementação da Solução
5
Construção de Modelos
Elementos de um modelo de otimização
DECISÕES
Identificar as possíveis soluções
(Definir Variáveis de Decisão)
OBJETIVOS
Definir critérios de avaliação capazes de indicar que
uma decisão é preferível a outras
(Definir Função Objetivo)
RESTRIÇÕES
Identificar quais as restrições que limitam as decisões
a serem tomadas
(Definir Conjunto de Equações ou Inequações)
6
Construção de Modelos
Forma Geral de um Modelo de Otimização
min (ou max)
(função objetivo)
sujeito a
(restrições principais - equações ou
inequações)
(tipo das variáveis de decisão)
7
Construção de Modelos
Classes de Modelos de
Otimização
•
•
•
•
Contínuo
Inteiro
Não linear
Misto
8
Construção de Modelos
Modelo de Otimização
Linear Contínuo
min(ou max) z  c1 x1  c2 x2  ...  cn xn
sujeito a
a11x1  a12 x2  ...  a1n xn ~ b1
a22 x1  a22 x2  ...  a2 n xn ~ b2
...
am1 x1  am 2 x2  ...  am nxn ~ bm
Forma Padrão:
max z  c t x
s.a
Ax  b
x   n
x1 , x2 ,...xn  0
onde ~ pode ser , , ou 
9
Construção de Modelos
Modelo de Otimização
Linear Inteiro
min(ou max)z  c1 x1  c2 x2  ...  cn xn
sujeito a
a11 x1  a12 x2  ...  a1n xn ~ b1
a22 x1  a22 x2  ...  a2 n xn ~ b2
...
am1 x1  am 2 x2  ...  amn xn ~ bm
Forma Padrão:
max z  c t x
s.a
Ax  b
x  Z n
x1 , x2 ,...xn  0, inteira
onde ~ pode ser , , ou 
10
Construção de Modelos
Modelo de Otimização
Linear Misto
min(ou max)z  c1 x1  c2 x2  ...  cn xn
sujeito a
a11 x1  a12 x2  ...  a1n xn ~ b1
a22 x1  a22 x2  ...  a2 n xn ~ b2
...
am1 x1  am 2 x2  ...  amn xn ~ bm
x1 , x2 ,...xn  0; x1 , x2 ,...x p  Z ;
x p 1 , x p  2 ,...xn  
onde ~ pode ser , , ou 
11
Construção de Modelos
Modelo de otimização
Não Linear
min(ou max ) z  f ( x1 , x2 ,... xn )
sujeito a
g1 ( x1 , x2 ,... xn ) ~ b1
g 2 ( x1 , x2 ,... xn ) ~ b2
...
g m ( x1 , x2 ,... xn ) ~ bm
onde ~ pode ser , , ou 
e f(.), g i (.) são funções contínuas
12
Construção de Modelos
Construção de um modelo
 Descreva com a maior riqueza de detalhes
o problema a ser tratado
 Identifique a classe do modelo matemático
mais apropriado (linear, não linear, inteiro,
misto)
 Defina as variáveis , a função objetivo, e as
restrições. Se necessário, simplifique o
problema. (Processo Iterativo)
13
Construção de Modelos
Exemplo Linear - O Problema da Dieta
Problema: Paula deseja saber quanto gastar para fazer uma dieta
alimentar que forneça diariamente toda a energia, proteína e cálcio que ela
necessita. Seu médico recomendou que ela se alimente de forma a obter
diariamente no mínimo 2000 kcal de energia, 65g de proteína e 800 mg de
cálcio.
O Valor nutritivo e o preço (por porção) de cada alimento que ela esta
considerando
comprar
é
dado
na
Tabela
1
abaixo.
Tabela 1 – Valor nutritivo e custo dos alimentos
alimento
arroz
ovos
leite
feijão
tamanho energia Proteína cálcio
da porção (kcal)
(g)
(mg)
100g
2un
237ml
260g
170
160
160
337
3
13
8
22
12
54
285
86
preço p/
porção
(centavos)
14
13
9
19
14
Construção de Modelos
Construindo um modelo para o Problema da Dieta
Neste problema temos:
elementos conhecidos: valor nutritivo dos alimentos, custo
dos alimentos
elementos desconhecidos: quanto consumir de cada alimento
objetivo a ser alcançado: obter uma dieta de baixo custo
restrições: a dieta deve fornecer uma quantidade mínima de
nutrientes.
15
Construção de Modelos
Construindo um modelo para o Problema da Dieta
Índices
A dieta deve ser feita a partir de 4 itens:
arroz, ovos, leite, feijão.
Faça j = 1,2,3,4 representar respectivamente cada um
dos itens
VARIÁVEIS DE DECISÃO
Defina então:
xj
= número de porções adquirida do alimento j
para ser usada na dieta
16
Construção de Modelos
Construindo um modelo para o Problema da Dieta
Objetivo
Obter a dieta de menor custo possível.
Proporcionalidade:
1 porção de arroz ==> 14 centavos,
2 porções de arroz ==> 28 centavos,
x1 porções de arroz ==> 14* x1 centavos.
gasto associado a compra de ovos: 13 * x2
Aditividade
gasto total com arroz e ovos é dado pôr:
14 x1 +13 x2
17
Construção de Modelos
Construindo um modelo para o Problema da Dieta
Custo total da dieta é então:
z  14x1  13x2  9x3  19x4
Custo do:
arroz
ovos
leite
feijão
Objetivo
Obter a dieta de menor custo possível.
min z  14x1  13x2  9x3  19x4
18
Construção de Modelos
Construindo um modelo para o Problema da Dieta
Restrições
Obter quantidade mínima de nutrientes:
energia:
1 porção de arroz ==> 170 kcal,
x1 porções de arroz ==> 170 x1
1 porção de ovos ==> 160 kcal, x2 porções de ovos ==> 160 x2
1 porção de leite ==> 160 kcal,
x3 porções de leite ==> 160 x3
1 porção de feijão ==>337 kcal,
x4 porções de feijão ==> 337 x4
quantidade total de energia >= quantidade mínima necessária
Proporcionalidade e aditividade
Temos então:
170x1  160x2  160x3  337 x4  2000
Tipo das variáveis
x j  0, x j  
Divisibilidade
19
Construção de Modelos
Modelo de Otimização Linear Contínuo
Para o Problema da Dieta
min z  14 x1  13 x 2  9 x 3  19 x 4
(restrições)
sujeito a:
170
(função-objetivo)
x1  160 x 2  160 x3  337 x 4  2000 (energia)
3 x 1  13 x 2  8 x 3  22 x 4  65 (proteína)
12 x 1  54 x 2  285 x 3  86 x 4  800 ( cálcio)
x
j
 0 , j  1, 2 ,3 , 4
(tipo das
variáveis)
20
Construção de Modelos
Solução Para o Problema da Dieta
Função Objetivo: 112.500000000
VARIAVEL
VALOR
X1
0.00 (arroz)
X2
0.00 (ovos)
X3
12.50 (leite)
X4
0.00 (feijão)
Isto é consumir 12.5* 237ml = 2,9625 l de leite
e gastar com a dieta 112,5 u.m.
Esta solução é aceitável?
21
Construção de Modelos
Novo Modelo Para o Problema da Dieta
Se limitarmos a quantidade de leite na dieta:
No máximo 2 porções
min z  14 x1  13 x 2  9 x 3  19 x 4
sujeito a:
170
x1  160 x 2  160 x3  337 x 4  2000
3 x 1  13 x 2  8 x 3  22 x 4  65
12 x 1  54 x 2  285 x 3  86 x 4  800
x
j
 0 , j  1 , 2 , 3, 4
x3<= 2
22
Construção de Modelos
Nova Solução Para o Problema da Dieta
Função Objetivo: 112,72
VARIAVEL
VALOR
X1
0,00 (arroz)
X2
0.00 (ovos)
X3
2.00 (leite)
X4
4.99 (feijão)
Isto é consumir:
2* 237ml = 474 ml de leite
4,99*260g = 1297,4 g de feijão
e gastar com a dieta 112,72 u.m.
23