Baixe o app para aproveitar ainda mais
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.
Compartilhar