rangel-cnmac2022-aula1

Prévia do material em texto

Introdução à construção de modelos de 
otimização matemática
MC 04 -1
Socorro Rangel 
(socorro.rangel@unesp.br)
Departamento de Matemática - UNESP
• Dia 1
• Problemas de otimização Matemática
• Ferramentas Computacionais: AMPL, Julia/JuMP, FICO-Mosel
• Dia 2
• O problema do Caixeiro Viajante
• Problemas integrados de dimensionamento e sequenciamento de 
lotes
• Dia 3
• O problema da Mochila
• Problemas de Corte e Empacotamento (PCE)
SocorroRangel
Sumário
Problemas de otimização
Otimização Combinatória (Nemhauser e Wolsey, 1989)
• Seja 𝑁 = 1,… , 𝑛 um conjunto finito e 
seja 𝑐 = 𝑐1, … , 𝑐𝑛 ∈ 𝑅
𝑛.
• Para todo 𝐹 ⊆ 𝑁 defina 𝑐 𝐹 = 𝑗∈𝐹 𝑐𝑗 .
• Suponha que temos uma coleção de 
subconjuntos ℱ ∈ 𝑁. Um Problema de 
Otimização Combinatória (POC) pode 
ser definido de acordo com (1).
Otimização Matemática (Bertsekas, 2016 )
• Em (2) supomos que 𝑓: 𝑅𝑛 → 𝑅 é uma função 
contínua e diferenciável
• Se em (2) 𝑓 é linear e 𝑋 é um poliedro 
dizemos que temos um Problema de 
Otimização Linear (POL), caso contrário 
temos um Problema de Otimização Não-
linear.
• 𝑓 𝑥 é chamada de função objetivo. 
• 𝑋 é chamada de região viável ou factível e 
𝑥 ∈ 𝑋 é uma solução viável ou factível. Uma 
solução viável que minimiza o valor de 𝑓(𝑥) é 
chamada de solução ótima. 
𝒎𝒊𝒏 𝒇 𝒙
𝒔𝒖𝒋𝒆𝒊𝒕𝒐 𝒂 𝒙 ∈ 𝑿 (𝟐)
𝑚𝑖𝑛 𝑐 𝐹
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝐹 ∈ ℱ (1)
SocorroRangel
Problemas de otimização matemática Linear
Contínua: 𝑥 ∈ 𝑋 Inteira: 𝑥 ∈ 𝑋 ∩ 𝑍𝑛
Qual é a melhor formulação 
(modelo de otimização matemática)?Adaptado de Wolsey (2021)
min𝑓 𝑥 = 
𝑗=1
𝑛
𝑐𝑗𝑥𝑗: 𝐴𝑥 = 𝑏, 𝑥 ≥ 0}, 𝑋 = {𝑥 ∈ 𝑅
𝑛: 𝐴𝑥 = 𝑏}
a) b) c)
SocorroRangel
Solução de Problemas de otimização Linear 
Contínua
min 𝑓 𝑥1, 𝑥2 =
𝑠. 𝑎
−𝑥1
50𝑥1
3𝑥1
−0,64𝑥2
+31𝑥2 ≤ 250
−2𝑥2 ≥ −4
𝑥1, 𝑥2 ≥ 0
SocorroRangel
• Método simplex (Dantzig, 1947; Arenales
e outros 2015)
Definido como um dos:
Top 10 Algorithms, The Best of the 
20th Century
(Siam News, v.33, n.4, 2000)
Geometria: Ponto extremo
Algebra: Solução Básica Factível
• Método de pontos interiores (Gonzaga, 
1989; Wright, 1997)
𝛻𝑓(𝑥)
𝒇 𝒙 = 𝟎
𝑥∗ = (1,94; 4,92)
𝑓 𝑥∗ = −5,09
𝛻𝑓(𝑥)
𝒇 𝒙 = 𝟎
𝒇 𝒙 =-5,09
Adaptado de Wolsey (2021)
Solução de Problemas de 
otimização Linear inteira
min𝑓 𝑥1, 𝑥2 =
𝑠. 𝑎
−𝑥1
50𝑥1
3𝑥1
−0,64𝑥2
+31𝑥2 ≤ 250
−2𝑥2 ≥ −4
𝑥1, 𝑥2 ≥ 0 e inteiro
𝑓 𝑥∗ = (5,0) = −5
𝑓 𝑥𝑅𝐿
∗ = (1,94; 4,92) = −5,09
𝑓 𝑥 = (2,4 ) = -4,56
𝛻𝑓(𝑥)
𝒙𝟏 ≤ 1 𝒙𝟐 ≥ 𝟐
𝛻𝑓(𝑥) Método de planos de corte Método 
Branch and bound
Branch and cut
LI1 ≤ LI2 ≤ ⋯𝐿𝐼𝑘 ≤ 𝑓 𝑥
∗ ≤ 𝐿𝑆𝑟 ≤ ⋯𝐿𝑆2 ≤ 𝐿𝑆1
𝐿𝑆𝑟 − 𝐿𝐼𝑘 ≤ 𝜖  ótimo
−5,09 ≤ 𝑓 𝑥∗ ≤ −4,56
SocorroRangel
Adaptado de Wolsey (2021)
ExercíciosSocorroRangel
Exercício 1 (Adaptado de Wolsey, 2021)
Exercício 2 (Wolsey, 2021) Repita o Exercício 1 considerando que:
PHPSimplex
𝑃1: 𝑍
∗ =
5
3
𝑃3: 𝑍
∗ = 1 𝑃1 ∩ 𝑃3
Inequações Válidas: 
Procedimento Chvátal-Gomory
𝑃2: 𝑍
∗ =
3
2
http://www.phpsimplex.com/simplex/grafico1.php?l=pt&metodo=grafico&v=2&rt=1&Submit=Continuar
Processo de Construção de um Modelo 
Matemático
Por que usar modelos matemáticos 
de otimização para auxiliar a 
tomada de decisão? 
• Solução matemática X 
solução empírica
• Melhor entendimento da 
empresa ou processo
• Ferramenta de apoio a 
tomada de decisão
Simplificação
Implementação da 
Solução
Sistema 
Real
Definição e 
Descrição do Problema
Solução do Modelo
Revisão
Decisão 
Teórica x
Política
Modelo Matemático
Revisão
SocorroRangel
Elementos de um modelo de otimização
RESTRIÇÕES
Identificar quais as restrições que limitam as decisões 
a serem tomadas
(Definir Conjunto de Equações ou Inequações)
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)
• elementos conhecidos: o que se
sabe sobre o problema?
• elementos desconhecidos: O que 
se pretende determinar?
min (função objetivo)
s.a
(restrições principais -
equações ou inequações)
(domínio das variáveis de 
decisão)
SocorroRangel
O problema da Dieta
Tabela 1 – Valor nutritivo e custo dos alimentos
alimento tamanho
da porção
energia
(kcal)
Proteína
(g)
cálcio
(mg)
preço p/
porção
(centavos)
arroz 100g 170 3 12 14
ovos 2un 160 13 54 13
leite 237ml 160 8 285 9
feijão 260g 337 22 86 19
Neste problema temos:
elementos conhecidos: valor nutritivo dos
alimentos, custo dos alimentos, valor mínimo de
nutrientes
elementos desconhecidos: quanto comprar de cada
alimento
Critério de otimização: custo total mínimo
restrições: a dieta deve fornecer uma quantidade
mínima de nutrientes.
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. A recomendação médica é 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. (Adaptado do problema de Stigler - (e.g. Namem, e 
Bornstein, 2004))
SocorroRangel
Um modelo de otimização linear contínua 
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 
alimentos
Variáveis de decisão
Suposição 1: Divisibilidade
Defina então
𝑥𝑗 ∈ 𝑅+ : = número de porções 
adquirida do alimento j para ser usada 
na dieta.
Critério de otimização
Obter a dieta de menor custo possível.
Suposição 2: 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
Suposição 3: Aditividade
gasto total com arroz e ovos é dado pôr:
14 x1 +13 x2
ovos arroz feijão leite 
𝒎𝒊𝒏 𝒇 𝒙 = 𝟏𝟒𝒙𝟏 + 𝟏𝟑𝒙𝟐 + 𝟗𝒙𝟑 + 𝟏𝟗𝒙𝟒
SocorroRangel
Restrições: Obter quantidade mínima de nutrientes:
energia:
1 porção de arroz ==> 170 kcal, 𝑥1 porções de arroz ==> 170 𝑥1
1 porção de ovos ==> 160 kcal, 𝑥2 porções de ovos ==> 160 𝑥2
1 porção de leite ==> 160 kcal, 𝑥3 porções de leite ==> 160 𝑥3
1 porção de feijão ==>337 kcal, 𝑥4 porções de feijão ==> 337 𝑥4
quantidade total de energia >= quantidade mínima necessária
Proporcionalidade e aditividade
2000337160160170 4321  xxxx
SocorroRangel
Um modelo de otimização linear contínua 
para o Problema da Dieta 
Solução ótima - Método Simplex (e.g, Dantig e Tappa, 1997)
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?
SocorroRangel
Um modelo de otimização linear contínua 
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.
Limitando a quantidade de leite na dieta:
No máximo 2 porções
𝒙𝟑 ≤ 𝟐
Para saber mais: Namem, A.A.A. e Bornstein, C., Uma Ferramenta para Avaliação de Resultados
de Diversos Modelos de Otimização de Dietas, Pesquisa Operacional, v.24, n.3, p.445-465, 2004
Ainda precisa ser reformulado....
SocorroRangel
Um modelo de otimização linear contínua 
para o Problema da Dieta 
ExercíciosSocorroRangel
Profa. Patrícia Constante Jaime (FSP-USP)
(https://www.youtube.com/watch?v=kcDyPTx0xsU)
• Que outros alimentos você pensa que a Paula deve incluir na dieta?
• Como obter uma solução melhor para o problema?
"Guia Alimentar da População Brasileira“
(https://bvsms.saude.gov.br/bvs/publicacoes/guia_alimentar_populacao_brasileira_2ed.pdf)
“... variedades dentro deum mesmo grupo de alimentos implicam maior diversidade no aporte de nutrientes. ... 
Agradam também aos sentidos na medida em que permitem diversificar sabores, aromas, cores e texturas ...”
Grupo das frutas
Opções de almoço
https://www.youtube.com/watch?v=kcDyPTx0xsU
https://bvsms.saude.gov.br/bvs/publicacoes/guia_alimentar_populacao_brasileira_2ed.pdf
SocorroRangel Tabela de Nutrientes
• necessidade de energia varia com sexo, 
idade, peso/altura, e a realização de 
atividades físicas
• Pela legislação brasileira, as recomendações 
de energia e nutrientes apresentadas nos 
rótulos dos alimentos têm como referência 
8.400 kJ ou 2000 kcal/dia uma pessoa de 
tamanho mediano, com atividade física baixa, 
no caso de homens, e atividade moderada, no 
caso de mulheres.
• Indicação: ingerir diariamente, em média: 60 g 
de proteínas, 60 g e lipídios (gordura), 310 g 
de carboidratos e 25 g de fibra alimentar.
Exemplo: “Para ingerir 60 g de proteína podem ser 
consumidos 1 xicara de leite, 1 fatia de queijo, 1 
concha de feijão, 1 bife e 1 filé frango ao longo do dia. 
Isso também já fornece cerca de 50 g de lipídios 
(gordura), sem contar o óleo e azeite utilizados no 
preparo das refeições.”
Adaptado de FoRC (http://alimentossemmitos.com.br/confira-a-quantidade-de-nutrientes-que-sua-dieta-deve-conter)
http://alimentossemmitos.com.br/proteinas
http://alimentossemmitos.com.br/lipidios
http://alimentossemmitos.com.br/carboidratos
http://alimentossemmitos.com.br/fibra-alimentar
http://alimentossemmitos.com.br/confira-a-quantidade-de-nutrientes-que-sua-dieta-deve-conter
SocorroRangel Ferramentas Computacionais
• Específicas
• Modelagem:
• AMPL, LINGO, MPL, FICO-MOSEL, 
JuMP, Python-MIP, PyOMO
• Resolução
• GUROBI, CBC, LINGO, CPLEX, 
FICO (XPRESS-MP)
• Gerais
• Sistemas Algébricos de Cáculo
• MATLAB, OCTAVE
• Planilhas de cálculo
• EXCEL, LOTUS 123
Vantagens e Desvantagens
•Custo
•Qualidade
•Documentação
•Comunicação com outras 
ferramentas
•Interface
•Análise de sensibilidade
•Estrutura do problema 
SocorroRangel
AMPL
SET
define um índice;
PARAM
define uma estrutura (vetor ou matriz) que irá 
armazenar os elementos conhecidos do 
exemplar, fornecidos no arquivo 
nomemodelo.dat;
VAR
define variáveis de decisão;
MINIMIZE (ou MAXIMIZA)
define a função-objetivo e o critério de 
otimização
SUBJECT TO
define um conjunto de restrições
FICO-MOSEL
MODEL nome do model
Instruções para compilação
Definição de parâmetros
Definição do modelo
Definição de procedimentos
END-MODEL
Julia/JuMP
Definição de pacotes 
nome=model(with optimizer(nomesolver))
@variable(nome, nomevar, tipo: bin ou int)
@constraint(nome, restrições)
@objective(nome, min ou max, função objetivo)
Definição de procedimentos
Sistemas Algébricos de Modelagem
SocorroRangel Sistemas Algébricos de Modelagem: AMPL
#Arquivo dieta.dat
set alimento := arroz ovos leite feijao;
set nutriente := energia proteina
caloria;
param preco := 
arroz 14
ovos 13
leite 9
feijao 19;
param nivel :=
energia 2000 
proteina 65 
caloria 800;
param quant:
arroz ovos leite feijao :=
energia 170 80 130 100
proteina 3 6 6.1 6
caloria 12 25 232 28;
#variável de decisão:quanto comprar de cada alimento
var comprar {j in alimento} >=0;
#definição função-objetivo e critério de otimização
minimize custo_total: sum {j in alimento} preco[j] *comprar[j];
#Níveis mínimos de nutrientes devem ser satisfeitos
subject to N_ {i in nutriente}:
sum {j in alimento} quant[i,j] * comprar[j] >= nivel[i];
# Arquivo: dieta.mod
# Definição dos índices
set alimento;
set nutriente;
# Estruturas para receber dados do exemplar
param preco {alimento};
param nivel {nutriente};
param quant {nutriente, alimento};
#Arquivo dieta.run
model dieta.mod;
data dieta.dat; 
option solver ...
Definição de 
procedimentos...
SocorroRangel Sistemas Algébricos de Modelagem: Julia/JuMP
# Arquivo: dieta.jl
# Definição dos pacotes
using JuMP, Cbc
# Dados
#Definição da instância
nutrientes = [170 160 160 337;
3 13 8 22;
12 54 285 86]
minimo_de_nutrientes = [2000, 65, 800]
precos = [14, 13, 9, 19]
# Definição do número de alimentos e nutrientes
n = length(precos)
m = length(minimo_de_nutrientes) 
# Criação do modelo.
dieta = Model(Cbc.Optimizer)
# Definição das variáveis
@variable(dieta, qtds_alimentos[j=1:n] >= 0)
# Definição da função objetivo
@objective(dieta, Min, sum(precos[j] * qtds_alimentos[j] for j = 1:n))
# Definição das restrições
for i in 1:m
@constraint(dieta, sum(nutrientes[i, j] * qtds_alimentos[j] for j = 1:n) >= minimo_de_nutrientes[i])
end
Para saber mais
Modelagem:
WILLIAMS, H. Model Bulding In Mathematical Programming. 5a. ed. John Wiley & Sons, 2013.
RANGEL, S. Introdução à construção de modelos de otimização linear e inteira. 2. ed. São Carlos-SP: SBMAC 
2012. 82 p. (disponível em http://www.sbmac.org.br/arquivos/notas/livro_18.pdf)
Métodos de Solução
ARENALES, M. et al. Pesquisa Operacional. 2a. ed. Rio de Janeiro: Elsevier, 2015.
DANTZIG, G. B.; THAPPA, M. Linear Programming 1: Introduction. [S.l.]: Springer, 1997.
FRIEDLANDER, A. Elementos de programação nâo-linear. Editora da UNICAMP, 1994. Disponível em:
<https://www.ime.unicamp.br/ friedlan/livro.htm>.
GOLDBARG, M.; LUNA, H. Otimização Combinatória e Programação Linear. 2a. ed. [S.l.]: Elsevier, 2005.
RIBEIRO, A. A.; KARAS, E. W. Otimização contínua: aspectos teóricos e computacionais. São Paulo: Cengage
Learning, 2014.
WOLSEY, L. A. Integer Programming. 2a. ed. New York: John Wiley & Sons, 2021.
O Problema da dieta
NAMEM, A.; BORNSTEIN, C. Uma ferramenta para avaliação de resultados de diversos modelos de otimização 
de dietas. Pesquisa Operacional, v. 24, n. 3, p. 445–465, 2004.
BRASIL. Ministério da Saúde. Guia alimentar para a população brasileira. 2a. Edição, 2014.
SocorroRangel
Seu comentário é importante.
https://forms.gle/2ezKqRuw8KHvEWs99
http://www.sbmac.org.br/arquivos/notas/livro_18.pdf
https://forms.gle/2ezKqRuw8KHvEWs99