Programacao Linear

Alexandre Salles da Cunha

DCC-UFMG, Marco 2010

Alexandre Salles da Cunha Programacao Linear

Vamos considerar o seguinte problema

Pedro deseja saber conhecer o mınimo orcamento que precisa gastardiariamente para satisfazer suas necessidades diarias de nutrientes, asaber:

Proteınas: 55 gCalcio: 800 mgEnergia: 2000 Kcal.

Para obter estas fontes de nutrientes, Pedro dispoe dos seguintesalimentos:

Alimento Tamanho da Energia Proteina Calcio Preco daporcao (kcal) (g) (mg) porcao

(centavos)

Cereais 28 g 110 4 2 3Frango 100 g 205 32 12 24Ovos 2 grandes 160 13 54 13Leite 237 cc 160 8 285 9

Carne porco 260 g 260 14 80 19

Alexandre Salles da Cunha Programacao Linear

O problema a resolver

Dentre todas as dietas (combinacoes de alimentos) que garantam asatisfacao da ingestao mınima de nutrientes, apresente uma cujo custoseja mınimo.

Identificar uma estrutura linear entre o custo e a satisfacao dasnecessidades nutricionais com a ingestao de nutrientes.

Formular um Problema de Otimizacao adequado.

Resolver o Problema.

Alexandre Salles da Cunha Programacao Linear

Formulando o problema

Separando os dados do problema dos valores atribuıdos a instancia doproblema.

Conjunto de nutrientes a satisfazer: I .

Necessidade diaria de cada nutriente: {di : ∀i ∈ I}

Conjunto de alimentos considerados na dieta: J

Preco da porcao do alimento j : pj

Quantidade do nutriente i fornecido por porcao do alimento j :{Qij ,∀i ∈ I ,∀j ∈ J}

Alexandre Salles da Cunha Programacao Linear

Formulando o problema

1 Variaveis de decisao: xj ira representar a quantidade de porcoes doalimento j que devera ser ingerida diariamente.

2 Funcao objetivo: minimizar o custo da dieta:

min∑

j∈J

pjxj

3 Restricoes do problema:1 Satisfacao das necessidades diarias de cada nutriente:

∑

j∈J

Qijxj ≥ di , ∀i ∈ I

2 Nao negatividade da quantidade ingerida de cada alimento:xj ≥ 0, ∀j ∈ J.

Alexandre Salles da Cunha Programacao Linear

Resolvendo o Problema

Trata-se de um Problema de Programacao Linear

Para fins ilustrativos, usaremos o pacote GLPK para sua resolucao e alinguagem de modelagem AMPL do GLPK.

glpsol --model dieta.mod --output dieta.out

Alexandre Salles da Cunha Programacao Linear

Solucao 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 Programacao Linear

Resolvendo um pequeno problema graficamente

max x1 + x2

x1 + 2x2 ≤ 3

2x1 + x2 ≤ 3

x1, x2 ≥ 0

Alexandre Salles da Cunha Programacao Linear