01 - Introducao

Prévia do material em texto

Programac¸a˜o Linear
Alexandre Salles da Cunha
DCC-UFMG, Marc¸o 2010
Alexandre Salles da Cunha Programac¸a˜o Linear
Vamos considerar o seguinte problema
Pedro deseja saber conhecer o m´ınimo orc¸amento que precisa gastar
diariamente para satisfazer suas necessidades dia´rias de nutrientes, a
saber:
Prote´ınas: 55 g
Ca´lcio: 800 mg
Energia: 2000 Kcal.
Para obter estas fontes de nutrientes, Pedro dispo˜e dos seguintes
alimentos:
Alimento Tamanho da Energia Proteina Ca´lcio Prec¸o da
porc¸a˜o (kcal) (g) (mg) porc¸a˜o
(centavos)
Cereais 28 g 110 4 2 3
Frango 100 g 205 32 12 24
Ovos 2 grandes 160 13 54 13
Leite 237 cc 160 8 285 9
Carne porco 260 g 260 14 80 19
Alexandre Salles da Cunha Programac¸a˜o Linear
O problema a resolver
Dentre todas as dietas (combinac¸o˜es de alimentos) que garantam a
satisfac¸a˜o da ingesta˜o m´ınima de nutrientes, apresente uma cujo custo
seja m´ınimo.
Identificar uma estrutura linear entre o custo e a satisfac¸a˜o das
necessidades nutricionais com a ingesta˜o de nutrientes.
Formular um Problema de Otimizac¸a˜o adequado.
Resolver o Problema.
Alexandre Salles da Cunha Programac¸a˜o Linear
Formulando o problema
Separando os dados do problema dos valores atribu´ıdos a` instaˆncia do
problema.
Conjunto de nutrientes a satisfazer: I .
Necessidade dia´ria de cada nutriente: {di : ∀i ∈ I}
Conjunto de alimentos considerados na dieta: J
Prec¸o da porc¸a˜o do alimento j : pj
Quantidade do nutriente i fornecido por porc¸a˜o do alimento j :
{Qij ,∀i ∈ I ,∀j ∈ J}
Alexandre Salles da Cunha Programac¸a˜o Linear
Formulando o problema
1 Varia´veis de decisa˜o: xj ira´ representar a quantidade de porc¸oes do
alimento j que devera´ ser ingerida diariamente.
2 Func¸a˜o objetivo: minimizar o custo da dieta:
min
∑
j∈J
pjxj
3 Restric¸o˜es do problema:
1 Satisfac¸a˜o das necessidades dia´rias de cada nutriente:
∑
j∈J
Qijxj ≥ di , ∀i ∈ I
2 Na˜o negatividade da quantidade ingerida de cada alimento:
xj ≥ 0, ∀j ∈ J.
Alexandre Salles da Cunha Programac¸a˜o Linear
Resolvendo o Problema
Trata-se de um Problema de Programac¸a˜o Linear
Para fins ilustrativos, usaremos o pacote GLPK para sua resoluc¸a˜o e a
linguagem de modelagem AMPL do GLPK.
glpsol --model dieta.mod --output dieta.out
Alexandre Salles da Cunha Programac¸a˜o Linear
Soluc¸a˜o do problema da dieta
Status: OPTIMAL Objective: CustoTotal = 67.09635836 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 CustoTotal B 67.0964
2 MinNutrientes[Energia]
NL 2000 2000 0.0269739
3 MinNutrientes[Proteina]
B 78.6336 55
4 MinNutrientes[Calcio]
NL 800 800 0.0164357
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x[Cereal] B 14.2443 0
2 x[Frango] NL 0 0 18.2731
3 x[Ovos] NL 0 0 7.79665
4 x[Leite] B 2.70706 0
5 x[Porco] NL 0 0 11.6745
Alexandre Salles da Cunha Programac¸a˜o Linear
Resolvendo um pequeno problema graficamente
max x1 + x2
x1 + 2x2 ≤ 3
2x1 + x2 ≤ 3
x1, x2 ≥ 0
Alexandre Salles da Cunha Programac¸a˜o Linear