Enunciado do EP2

[Ernesto G. Birgin <egbirgin@ime.usp.br>]

Caros alunos:

A entrega do EP2 sera no dia 03/06/05/02 (daqui a 3 semanas e sem 
possibilidade de adiamentos) e o enunciado e o seguinte:

No EP3 (sim, no 3) vao ter que implementar um metodo para resolver um 
problema "parecido" com o problema de programacao linear, mas com um tipo 
adicional de restricoes: as variaveis tem que ser inteiras (e nao mais 
reais). Quem vai explicar esse metodo vai ser o Prof. Carlinhos, nas duas 
aulas da proxima semana. Semana na qual eu nao poderei comparecer as aulas. 
Esse metodo precisa resolver, a cada iteracao, um problema de programacao 
linear. E esse e o asunto deste EP2.

A ideia do EP2 e que voces se familiarizem com alguma rotina que implemente o 
metodo Simplex. Voces terao que procurar em algum lugar (Numerical Recipes, 
www.nr.com; Netlib, www.netlib.org; etc) uma rotina que implemente o metodo 
Simplex e utiliza-la para resolver os problemas que formularam no EP1.

Para isso, as etapas serao:

1) Escolher a rotina que implemente o metodo Simplex.

2) Implementar um programa principal que leia os dados de entrada (guardados 
num arquivo) de um problema no formato standard (n: numero de variaveis, m: 
numero de restricoes de igualdade, c: vetor de custos, A de mxn: matriz das 
restricoes de igualdade, b: vetor do lado direito das restricoes de 
igualdade).

3) Testar o programa com problemas simples que possam ser resolvidos 
graficamente.

4) Para 3 problemas do EP1, escolher as constantes e/ou dados que estiverem 
faltando para que o problema tenha um conjunto viavel nao-vazio.

5) Resolver os 3 problemas escolhidos do EP1.

6) Para verificar se os problemas de 5) estao sendo resolvidos corretamente, 
podem usar o LINDO (www.lindo.com) disponivel para Windows e Linux.

7) Tudo o anterior devera devera ser explicado e detalhado num relatorio. O 
relatorio (parte mais IMPORTANTE do EP pois mostra o que voces aprenderam) 
devera incluir explicacoes de como as coisas foram feitas, por que foi feita 
tal o qual escolha, quais dificultades foram encontradas a cada passo e, 
evidentemente, explicacoes de cada um dos 6 itens anteriores. 

Boa sorte e bom trabalho,
Ernesto.

-- 
Ernesto G. Birgin
Department of Computer Science IME-USP
http://www.ime.usp.br/~egbirgin