Investigação Operacional I
Guia de Utilização do Software
José Manuel Vasconcelos Valério de Carvalho
Universidade do Minho
2007
Guia de Utilização do Software
Este documento apresenta diversas informações sobre a utilização dos seguintes packages de programação matemática:
- Problemas de Programação Linear: LP_SOLVE
- Problemas de Optimização em Rede: RELAX
Estes packages usam ficheiros de dados como input. Para construir o ficheiro de dados pode ser usado qualquer processor de texto, desde que o ficheiro seja guardado como um ficheiro de texto, apenas com caracteres ASCII. No caso do WORD, deve ser usada a opção GUARDAR COMO ficheiro do tipo TEXT ONLY (*.TXT), podendo o utilizador escolher o nome que pretende dar ao ficheiro.
Ficheiros do tipo *.DOC não podem ser utilizados, porque contêm um cabeçalho com caracteres invisíveis para o utilizador que os programas interpretam como dados do problema.
Os resultados dos programas são, por defeito, apresentados no écran, podendo, no entanto, ser redireccionados para um ficheiro, através da opção >ficheiro.
Em alternativa ao programa LP_SOLVE, existem também disponíveis na rede algumas versões educacionais de packages de resolução de problemas de programação linear. Cita-se, a título ilustrativo, o LINDO, que pode ser obtido em www.lindo.com. A dimensão das instâncias que podem ser resolvidas com estes packages é limitada, mas suficiente para resolver os problemas propostos.
No Laboratório do DPS, existem 10 licenças do package de programação linear, CPLEX (versão 6.5), que permitem resolver instâncias de muito maior dimensão.
Todos estes packages aceitam ficheiros de dados no formato MPS.
Existe também material disponível no endereço http://OpsResearch.com/ , local que fornece inúmeras informações de interesse sobre o domínio da Investigação Operacional.
Problemas de Programação Linear: LP_SOLVE
Autoria
O package foi desenvolvido por Michel Berkelaar, michel@es.ele.tue.nl. Há informações em
http://www.cs.sunysb.edu/~algorith/implement/lpsolve/implement.shtml
Recomenda-se a
utilização da versão LPSolve IDE (Integrated Development Interface)
http://web.mit.edu/lpsolve_v5507/doc/IDE.htm
que permite
aceder a todas as funcionalidades do lpsolve através de uma interface gráfica
(para Windows).
Objectivo
Este programa determina a solução óptima de um problema de programação linear. Os dados de entrada podem ser números reais ou inteiros.
Problemas de Optimização em Rede: RELAX
Autoria
O programa RELAX foi desenvolvido por Dimitri Bertsekas e Paul Tseng do Laboratory for Information and Decision Systems and the Operations Research Center, MIT, e encontra-se acessível em
http://elib.zib.de/pub/Packages/mathprog/mincost/relax-4/
Objectivo
Este programa determina a solução óptima de um problema de optimização em rede.
Definição do Input
O package aceita dados de input, a partir de um ficheiro de texto, com o formato que a seguir se descreve:
Os dados de entrada devem ser números inteiros.
- Definição da Rede
Nas duas primeiras linhas:
n
m
sendo n o número de vértices do grafo e m o número de arcos.
- Definição dos Arcos da Rede
Nas restantes m linhas, é feita uma listagem dos m arcos, no seguinte formato:
org
dst custo cap
sendo org o vértice de origem do arco, dst o vértice de destino, e custo o respectivo custo unitário de transporte. A capacidade do arco (limite superior para o fluxo que nele pode ser transportado), cap, também deve ser indicada.
Notas importantes:
- não podem aparecer na lista dois arcos com a mesma origem e o mesmo destino.
- os vértices devem ser numerados consecutivamente, com números a partir de 1.
- Definição das Ofertas e das Procuras em cada Vértice da Rede
A definição das ofertas e das procuras em cada vértice do grafo é feita usando arcos fictícios unindo os vértices do grafo e dois vértices suplementares: o vértice n+1, que serve como um supernodo que concentra as ofertas, e o vértice n+2, um supernodo que concentra as procuras.
Para estabelecer o valor da oferta no vértice i, deve ser criado um arco fictício entre o vértice n+1 e o vértice i, com uma capacidade igual à oferta real no vértice i e um custo unitário de transporte nulo.
Do mesmo modo, para definir o valor da procura no vértice j, deve ser criado um arco fictício entre o vértice j e o vértice n+2, com uma capacidade igual à procura real no vértice j e um custo unitário de transporte igualmente nulo.
Exemplo:
Ao problema com duas origens e dois destinos da Figura, em que a capacidade de todos os arcos é igual a 1000, corresponde o ficheiro de input abaixo apresentado:
4
8
1 3 11 1000
1 4 12 1000
2 3 13 1000
2 4 14 1000
5 1 0 15
5 2 0 25
3 6 0 20
4 6 0 20
Exemplo: No ficheiro RELAX.INP, está definido um problema com 7 vértices e 14 arcos. Existe uma oferta de 20 unidades no vértice 1 e uma procura de 20 unidades no vértice 7. Nos restantes vértices, há conservação de fluxo.
Execução do Programa
Para executar o programa, fazer
- RELAX <RELAX.INP >RELAX.OUT
Informações Adicionais
Informações adicionais sobre este programa, nomeadamente sobre a estratégia do algoritmo, as estruturas de dados utilizadas e o desempenho computacional, podem ser obtidas no artigo:
Dimitri Bertsekas e Paul Tseng, “The
relax codes for linear minimum cost network flow problems”, Annals of
Operations Research 13, 125-188, 1988.