Enunciado_2010-1

Prévia do material em texto

Página 1 de 1 
Projeto – Programação Linear – 2010.1 
Dpto. Engenharia Elétrica, PUC-Rio. 
Professor: Alexandre Street (street@ele.puc-rio.br) 
As notas serão divulgadas no grupo (Internet): http://groups.yahoo.com/group/po_puc-rio 
 
Data de apresentação: dia 17 de junho de 2010 para a graduação e 18 de junho para a pós-graduação. 
 
TAREFA – 1 (7 pts) Implementar o método simplex revisado para resolver um problema de 
programação linear (PL) genérico, expresso na seguinte forma: 
 
ܯܽݔ݅݉݅ݖܽݎ ࢉ்࢞ (1)
Sujeito a: 
࡭࢞ ≤ ࢈ (2)
࢞ ≥ ૙. (3)
O seu algoritmo deve retornar os seguintes objetos: 
1. O valor ótimo da função objetivo. 
2. O ponto ótimo (࢞∗) que resolve o problema, caso exista. 
a. Caso o estado seja menor que 1, o valor de ࢞∗ deve representar a ultima solução da 
fase 1 em caso de inviabilidade e a direção extrema caso o problema seja ilimitado. 
3. O vetor de variáveis de folga das restrições (2). 
4. O vetor de variáveis duais associadas às restrições (2). 
5. O estado do algoritmo: -1 se o problema for inviável, 0 se ilimitado e 1 se existe ponto ótimo. 
6. Os vetores de índices relativos às variáveis básicas e não básicas ótimas. 
 
Resolver as seguintes instâncias: 
1. Problema da página 39 do livro texto (Chvátal), utilizado para exemplificar a necessidade da 
fase 1. 
7. Um problema que seja ilimitado de sua escolha. 
TAREFA – 2 (3 pts) Escolher um problema relevante e resolvê-lo para diferentes tamanhos de 
instância que variem de pequenas a grandes. Tente identificar o limite (em tamanho do problema) do 
seu algoritmo e o fator limitante. Os resultados de cada instância devem ser exibidos em uma tabela 
com as seguintes informações: coluna 1, número de variáveis (n), coluna 2, número de restrições (m), 
coluna 3, valor da função objetivo, coluna 4, número de iterações (trocas de base), coluna 5, tempo de 
execução do seu algoritmo, e por fim, coluna 6, tempo computacional que o linprog levou para 
resolver a mesma instância. Faça um gráfico exibindo as colunas de tempo (5 e 6) para todas as 
instâncias, colocando no eixo horizontal o tamanho da instância (݊݉) e no vertical os valores em 
segundos. Faça um segundo gráfico mostrando o número de iterações ao longo das instâncias. 
 
Apresentação: As duas tarefas devem ser apresentadas em slides (formato PDF) em não mais que 15 
minutos. O trabalho é individual e o código de todos os programas deve ser enviado por email até a 
data da apresentação. Os programas devem estar preparados para serem chamados na linha de 
comando do MATLAB e executarem as respectivas tarefas de maneira automática, sem a necessidade 
de se passar parâmetros. Para isso, criem procedures que executem as tarefas automaticamente.