Modelos de Programação Linear – Problema da Dieta

Junho 10, 2010

Esse é o primero post da série de modelagem de programação linear e programação linear inteira. Pretendo abordar vários problemas de otimização combinatória e apresentar uma modelagem de programação linear. Sempre que possível, apresentarei modelagens alternativas e explicarei a diferença entre elas. Para quem não conhece o assunto, considere ler as referências [1,2]. Para um conteúdo mais avançado, considere a leitura também de [3].

O problema mais básico para se modelar como programação linear é o problema da dieta, que pode ser enunciado como segue:

Considere três tipos de alimentos a, b, c, cada um com diferentes proporções dos nutrientes i, j, k por unidade. Na nossa dieta, devemos consumir uma quantidade mínima de cada nutriente, denotado aqui por . Vamos denotar por a quandidade do nutriente i em uma unidade do alimento a, nomeando de forma semelhante as quantidades para as outras combinações de alimento e nutriente. Considere que a unidade de cada tipo de alimento tem um custo associado, . Queremos escolher uma combinação de alimentos de forma a minimizar o custo.

Antes de mais nada, precisamos definir as variáveis do modelo. No caso será a quandidade de cada alimento na combinação: . Temos o seguinte modelo

sujeito a:

(1)

(2)

(3)

(4)

A restrição (4) nos garante que só teremos quantidade não negativas de cada alimento na mistura final, o que é razoável.

De maneira geral, o problema da dieta para um conjunto de alimentos A e um conjunto de nutrientes N pode ser escrito como

sujeito a:

Referências
[1] Otimização Combinatória
[2] Programação Linear
[3] http://www.dcc.unicamp.br/~cid/cursos/MO420/Material-didatico/

Anúncios

Olimpíada Brasileira de Informática

Junho 7, 2010

A Olimpíada Brasileira de Informática, ou OBI, é uma competição voltada para alunos do ensino fundamental e ensino médio, além de alunos no primeiro ano de faculdade. Há várias divisões e a principal delas consiste em selecionar os melhores alunos para representar o Brasil na Olimpíada Internacional de Informática (IOI).

Para tanto são realizadas duas fases. A Unicamp sempre tem alunos que participam e este ano não foi exceção. Participaram da primeira fase cerca de 10 calouros (o número não é tão alto devido à restrição de que um aluno universitário só é elegível caso tenha cursado o 3º ano do ensino médio no ano anterior). Desse número, 4 conseguiram avançar para a segunda fase.

Os melhores da segunda fase (entre 10 e 15 alunos) são convidados para participar de um treinamento da Unicamp (veja a lista). O evento deste ano foi realizado na semana passada e eu trabalhei como monitor, fiscalizando as provas e ajudando na confecção de enunciados e soluções para as mesmas. Dois alunos da Unicamp foram convidados para esse treinamento, a Patrícia e o Thiago, porém este último não apareceu e a Patrícia foi embora mais cedo e não participou das provas.

No final a classificação ficou com o Felipe de João Pessoa em primeiro, seguido do Renato de São Paulo, o Caique de Fortaleza e o André de São Paulo. Eles irão representar o Brasil em Warteloo, Canadá. Parabéns a todos!