MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 818 6140

E-MAIL cef@ime.usp.br

MAC 325 - Otimização Combinatória 1998 - MAC 5781

Projeto de Otimização Combinatória - Entrega 16 de novembro

Implementação do Método Simplex para Redes

O objetivo deste projeto é a implementação do Método Simplex para Redes em uma linguagem de programação estruturada. O programa deverá ler um arquivo de entrada com o seguinte formato:

#vértices #arcos
demanda do primeiro vértice
$⋮$
demanda do último vértice
vértice de partida vértice de chegada custo do primeiro arco
$⋮$
vértice de partida vértice de chegada custo do último arco

Seu programa deverá identificar problemas inviáveis, ilimitados, com solução ótima e decomponíveis. Neste último caso, não é necessário resolver os subproblemas.

Na página da disciplina (link projeto) você encontra alguns exemplos de arquivos de entrada assim como testes usados pelos seus colegas. Faça outros testes, com vários tamanhos diferentes. Teste pelo menos para um exemplo de grande porte ($\ge 1000$ vértices e $\ge 100000$ arcos). Para verificar se o resultado de seu programa está correto, você pode utilizar o programa CPLEX (ou o soplex para os que preferirem), que resolve problemas de programação linear. Junto com os testes você encontra o programa msr2lp.c que transforma um arquivo como descrito acima em um arquivo ``.lp'', como o CPLEX (soplex) espera. Para transformar o arquivo você executa:

msr2lp < ``arquivo de entrada'' > <arquivo de saída>.lp

Então você poderá executar o CPLEX na rebutosa, seguindo a receita abaixo:

[rebutosa:/home/mac/cef/www/mac325/proj] > cplex 
 
Welcome to CPLEX Linear Optimizer 3.0
  with Mixed Integer & Barrier Solvers
Copyright (c) CPLEX Optimization, Inc., 1989-1994
CPLEX is a registered trademark of CPLEX Optimization, Inc.
 
Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.
 
CPLEX> read <arquivo>.lp
Problem '<arquivo>' read.
Read Time =   0.09 sec.
CPLEX> optimize

A seguir ele dará o valor da solução ótima para que você compare com o resultado de seu programa.