4 a 7 de novembro de 2003, Natal-RN
A pesquisa Operacional e os Recursos Renováveis
ADAPTAÇÃO DO PROLIN (SISTEMA PARA PROGRAMAÇÃO LINEAR)
PARA USO VIA WEB
Alexandre Sant’Anna dos Santos
Universidade Federal Viçosa - UFV
Departamento de Informática – DPI
CEP: 36570-000 Viçosa - MG
[email protected]
Resumo: A Universidade Federal de Viçosa oferece três disciplinas de Pesquisa Operacional na
graduação e várias na pós-graduação, com destaque para a disciplina Programação Linear e suas
aplicações. Com isso, torna-se imprescindível o uso de ferramentas computacionais nesta área, sendo
muito desejável o acesso a tais ferramentas por meio da rede interna. Para um melhor aproveitamento
do estudante nessas disciplinas, é desejável que tais ferramentas sejam bem documentadas e de fácil
acesso. Neste contexto, encaixa-se o PROLIN (Sistema para PROgramação LINear), desenvolvido
para a resolução de problemas genéricos de Programação Linear. Implementado em 1987 por uma
equipe da Universidade Federal de Viçosa, utiliza o Simplex Revisado como algoritmo-base. Com
vistas em um melhor aproveitamento do código desenvolvido em FORTRAN e da eficiência
demonstrada pelo PROLIN criou-se, com o presente trabalho, uma interface para o seu uso via
Internet, utilizando-se a linguagem de programação PHP. Com o mínimo possível de alterações em
seu código original, o PROLIN tornou-se acessível via Internet, configurado para problemas de
Programação Linear com até 50 restrições e 100 variáveis nesta versão acadêmica. Juntamente com
esta adaptação, um site completo foi desenvolvido com o intuito de facilitar o uso do PROLIN, como
reforço ao processo de ensino-aprendizagem no contexto acadêmico.
Palavras -chave: Programação Linear via INTERNET - Ensino de Programação Linear - PROLIN.
Abstract: The Federal University of Viçosa offers three graduate and several post-graduate courses
based on Operations Research, with emphasis on Linear Programming topics and their applications.
Therefore the use of computational tools is indispensable, being even more desirable the access of
such tools over a network. For the student to take greater advantage of these courses, we need tools
that are well documented and easy to use. In this context, there is the PROLIN (LINear
PROgramming) tool, developed for the resolution of generic linear programming problems. It was
coded in 1987 in this university, using the revised simplex method as its base algorithm. Taking
advantage of the software already developed in FORTRAN, with its correctness and efficiency, in this
work we created an interface for its use over the Internet. For this we used the PHP programming
language. Making only minor changes in PROLIN’s original code, it is accessible on the web,
configured to solve linear programming problems with up to 50 constraints and 100 variables in this
version. Together with this adaptation, a complete site was developed with the intention of facilitating
the use of such tool, offering a better learning curve inside the academic context.
Keywords: Linear Programming on the web - Linear Programming teaching - PROLIN.
1. Introdução
Em meados da década de 90, houve um crescimento amplo de ferramentas disponibilizadas na
Internet para uso via navegador web. A interação entre cliente-servidor é mediada pelo mais básico
dos componentes web: navegadores que interpretam HyperText Markup Language (HTML),
servidores para requisições e envios de respostas HyperText Transfer Protocol (HTTP) e o uso de
solucionadores para os problemas requisitados pelo usuário. Estes solucionadores são o que se
denominam linguagens dinâmicas para a web que têm sido amplamente usadas, principalmente para o
e-commerce. A vantagem oferecida por estas linguagens é que elas podem acessar recursos avançados
do computador servidor e disponibilizar o conteúdo para o cliente de maneira rápida e dinâmica.
Isto possibilitou grande facilidade para o usuário, uma vez que através de um browser simples,
ele tem acesso a uma variada gama de serviços na Internet. Atualmente, é possível fazer, através da
web, reservas de hotéis, compras dos mais variados artigos, dentre outras possibilidades.
Muitas foram as ferramentas de Pesquisa Operacional desenvolvidas para a web. Algumas
delas estão na forma de applet JAVA (o navegador faz o download do aplicativo do servidor e executa
o programa no cliente, através de um plugin), outras estão na forma direta para download (para serem
instaladas no cliente para uso individual) e existem aquelas que estão no padrão de formulário HTML
(o cliente, através de um browser, envia uma requisição com seu problema através de dados diretos,
em arquivo ou por e-mail e recebe uma resposta do aplicativo na mesma hora).
2. Programação Linear
Trata-se de uma técnica tradicional de Pesquisa Operacional e que tem sido empregada em
muitos campos da atividade humana. Um Problema de Programação Linear (PPL) envolve a
otimização de uma função linear denominada função objetivo, condicionada ao atendimento de
restrições também caracterizadas pela linearidade das funções envolvidas.
Apesar das pressuposições inerentes à linearidade das funções presentes num modelo de
Programação Linear, inúmeros problemas reais têm sido modelados com sucesso e resolvidos por
meio desta ferramenta. GOLDBARG e LUNA (2000) oferecem uma ampla exposição sobre a origem,
o processo de modelagem, os fundamentos teóricos e as aplicações da Programação Linear [1].
3. PROLIN
O Sistema para Programação Linear - PROLIN, desenvolvido para a resolução de problemas
genéricos de Programação Linear, utiliza o Simplex Revisado como algoritmo-base, adaptando-o para
lidar com variáveis ou com restrições limitadas. Em sua versão para micros, está limitado a um
máximo de 100 (cem) restrições e 500 (quinhentas) variáveis, não se incluindo, entre essas, as
variáveis de folga e as artificiais [2].
O PROLIN (Sistema para PROgramação LINear) é uma ferramenta desenvolvida na UFV em
1987. O PROLIN foi implementado na linguagem de programação FORTRAN 77 para o ambiente
DOS/16bits (portanto, rápido e eficiente). O funcionamento do programa é bem simples. Depois de
executado, o programa pede o nome do arquivo de entrada (contendo os dados do problema) e o nome
do arquivo de saída (onde serão gravados os relatórios a respeito da solução do problema de
Programação Linear ou mensagens de erros encontrados durante a execução do programa). A tela
inicial do programa pode ser visualizada na figura abaixo:
figura 1 – Tela para entrada dos arquivos do PROLIN
Após esta etapa, o programa pede o drive do disco onde o usuário deseja gravar o arquivo
temporário gerado pelo programa. Esta etapa pode ser visualizada na figura abaixo:
2552
figura 2 – Tela para fornecimento do drive para o arquivo de trabalho
Para finalizar, o programa exibe uma tela se a busca da solução ótima teve sucesso ou não e o
resultado em arquivo.
4. Adaptação do PROLIN
Como se percebe, esta forma de utilização não é amigável, tornando-se necessária a adaptação
do PROLIN para uso via web, a fim de que o seu uso fosse estimulado no meio acadêmico, motivo
principal de seu desenvolvimento. Como uma ferramenta sem interface gráfica, o PROLIN caiu em
desuso pelos estudantes da UFV e, também, pelos professores das disciplinas de Pesquisa Operacional.
Para estimular o uso do programa como ferramenta acadêmica tornou-se necessário agregar-lhe valor,
tornando-a atrativa, tanto na facilidade de uso quanto na sua interface gráfica e na facilidade de acesso
a esta ferramenta.
4.1 Definição do compilador
A versão original do PROLIN foi desenvolvida e compilada para a plataforma Windows,
utilizando o ambiente de programação Microsoft Fortran PowerStation. A fim de disponibilizá-lo para
uso via navegador web, foi necessária que se fizesse, primeiro, a adaptação do código fonte do
programa para que ele fosse compilado no sistema operacional do servidor que iria hospedá-lo. Os
servidores visados para hospedar o PROLIN (servidores do Departamento de Informática da UFV)
têm, como sistema operacional o LINUX, necessitando, então que o código fonte do programa
PROLIN fosse adaptado para compilação nesta plataforma.
Antes de tudo, foi preciso também definir o compilador a ser utilizado para que o mínimo de
alterações fosse necessário no código-fonte do programa diminuindo, assim, os riscos de introdução de
erros de programação e de incompatibilidade entre os dialetos da linguagem FORTRAN 77 utilizados
entre os compiladores. O compila dor definido foi o g77 da GNU[3]. Além do uso gratuito, o
compilador da GNU possibilita a compilação para diversas plataformas (portabilidade entre Sistemas
Operacionais), aceitando um dialeto do FORTRAN 77 bem próximo ao definido pelo ANSI
FORTRAN 77. A escolha deste compilador facilitou a adaptação do código fonte do PROLIN, uma
vez que poucas rotinas foram alteradas.
4.2 Alterações no código fonte do PROLIN original.
Como programa monousuário, o PROLIN teve que sofrer algumas alterações para que fosse
utilizado via web, sendo adaptada a sua interação com o usuário. A este é dada a opção de digitar o
modelo do Problema de Programação Linear (PPL) no próprio site ou de fornecer o nome do arquivo
contendo o modelo. Caso o usuário opte por entrar diretamente com o problema no site, uma rotina à
parte foi implementada para a criação automática de arquivos e a nomeação dos mesmos, tomando
como base o número de sessão do usuário, a fim de evitar conflito com nomes de arquivos no servidor.
Mesmo porque no ambiente web, deve-se considerar a possibilidade de existirem diversos usuários
2553
utilizando o sistema simultaneamente; logo, um mecanismo foi implementado para evitar conflitos.
Como exemplo, pode-se citar dois estudantes submetendo problemas diferentes ao mesmo tempo para
o PROLIN. O resultado poderia ser uma solução inconsistente para ambos os modelos submetidos
pois, considerando o processamento concorrente no servidor, o programa poderia sobrepor os arquivos
temporários gerados de um problema com os do outro, gerando inconsistência ou, até mesmo, erro de
processamento no servidor.
Logo, o PROLIN foi parametrizado para receber o nome de três arquivos. Primeiro, o arquivo
contendo o modelo; segundo, o arquivo temporário a ser utilizado pelo programa para geração das
matrizes temporárias utilizadas no processamento; e, por último, o arquivo para armazenar o resultado
do processamento.
Uma outra alteração efetuada foi na dimensão dos problemas aceitos pelo PROLIN. A fim de
se evitar sobrecarga no servidor, o PROLIN foi limitado para problemas com até 50 restrições e 100
variáveis, o que é satisfatório para o uso acadêmico da ferramenta.
4.3 Definição de um novo formato de modelagem de dados
O formato de entrada de dados exigido pelo PROLIN, em sua versão original, é extremamente
rígido no que se refere, principalmente, ao posicionamento de variáveis, restrições e coeficientes no
arquivo. Por exemplo, o usuário é obrigado a definir um titulo e depois o objetivo do problema
(maximizar ou minimizar determinada função objetivo). Logo após, ocorre a definição das restrições,
onde o nome da restrição fica na primeira posição (até a oitava coluna da linha), o sinal (menor, maior
ou livre) da coluna 10 à 18 e o valor limite, caso haja, (da coluna 20 à 28). Este tipo de entrada de
dados é totalmente complicado para quem está começando a aprender Programação Linear, visto que o
usuário não consegue visualizar a equação que modelou antes de digitar o problema. Outra
dificuldade está no fato do usuário ter que se preocupar com o posicionamento dos itens no arquivo, o
que é muito desconfortável.
Com o objetivo de diminuir o tempo de aprendizado do formato de modelagem de dados pelo
estudante, um novo formato de entrada de dados foi definido para o PROLIN. Este formato é muito
semelhante ao usado na literatura de Pesquisa Operacional para PPL e, também, ao formato adotado
por programas já existentes no mercado. Isso reduz a quase zero o tempo necessário para que o usuário
aprenda o formato de modelagem de dados, o que estimula o uso da ferramenta. Logo abaixo, seguese uma descrição do novo formato de modelagem:
[Objetivo]
<qualificador> [<obj>] : <coef1><var1> [<+|-> <coef2><var2> ... <+|-> <coefN><varN>]
[<sinal> <valor>]
[<obj> <sinal> <valor> ]
Sujeito
[<rest1> :] <coef1><var1> [<+|-> <coef2><var2> ... <+|-> <coefN><varN>] <sinal> <valor>
...
[<restN> :] <coef1><var1> [<+|-> <coef2><var2> ... <+|-> <coefN><varN>] <sinal> <valor>
[(<rest1> | < var1>) <sinal> <valor> ]
...
[(<restN> | < varN>) <sinal> <valor>]
Combinar
[<restC1> :] <coef1><rest1> [<+|-> <coef2><rest2> ... <+|-> <coefN><restN>]
<sinal> <valor>
...
[<restCN> :] <coef1><restN> [<+|-> <coef2><rest2> ... <+|-> <coefN><restN>]
<sinal> <valor>
[(<restC1>) <sinal> <valor> ]
...
[(<restCN>) <sinal> <valor>]
[fim]
2554
Exemplo:
max 2x + y
s.a.
x + y <= 10
3x + 5y <= 30
fim
Como observado na descrição do formato de modelagem, o problema fica dividido em 3
seções. A primeira para definição da função objetivo, a segunda para definição das restrições e a
terceira seção para definição das restrições combinadas. O usuário não é obrigado a dar nomes às
restrições e a definição dos limites das variáveis e restrições também é opcional. Caso o usuário não
informe todos os parâmetros, o sistema usa uma atribuição automática.
4.4 Implementação do conversor
O pobre tratamento de formatação de texto pela linguagem FORTRAN 77 fez com que fosse
implementado um conversor de formatos, em uma outra linguagem de programação,. Isso significa
que, antes do modelo ser submetido ao programa, uma rotina implementada em PHP é acionada para
convertê-lo no formato de modelagem do PROLIN original. Durante a conversão, problemas de
entrada de dados são verificados para evitar a geração de um arquivo de dados inconsistente.
4.5 Funcionamento do PROLIN
Para se adequar o PROLIN à Web, utilizou-se a linguagem de programação para a Internet
PHP[4]. Foram implementadas rotinas de manipulação e criação de arquivos, de conversão do
formato de dados e de formatação dos resultados. Ao submeter o modelo do PPL pela web, a rotina de
manipulação e criação de arquivos é acionada. Após esta etapa, o formato do problema é convertido
pela rotina de conversão e, então, o PROLIN é acionado pelo aplicativo. Quando a execução do
PROLIN é finalizada, a rotina de formatação dos resultados é acionada para formatar o resultado da
solução do problema, sendo resposta enviada ao usuário (figura 3). Cabe ressaltar que qualquer erro
ocorrido em qualquer uma das etapas, o usuário é devidamente avisado e instruído através de uma
resposta devidamente formatada para este fim.
Servido r
Problema
Usuário
Resultado Formatado
Apache(Http)
Aplicativo PHP
Manipulação dos Arquivos
Conversor de Formatos
PROLIN
Formatação do Resultado
Figura 3 – Funcionamento do PROLIN na web
O resultado retornado é bem completo, possibilitando ao usuário uma rica interpretação e
permite que se faça inferências sobre o modelo submetido. O resultado é dividido em seis seções, cada
uma com suas características. Abaixo segue uma descrição das características de cada seção do
resultado retornado.
4.5.1 Identificação do problema:
TÍTULO: nesse campo, tem-se o conteúdo associado à palavra-chave TÍTULO.
2555
OBJETIVO DO PPL: tem-se o objetivo do problema e o nome da função a ser otimizada.
* ÓTIMA - quando o PPL tiver solução determinada
* INVIÁVEL - quando a solução do PPL for indefinida. Nesse caso, o ESTADO será precedido
de mensagem identificando a origem da inviabilidade, sendo a execução interrompida.
NÚMERO DE ITERAÇÕES: número total de vezes que se utilizou o SIMPLEX para se atingir
a solução ótima.
VALOR DA SOLUÇÃO: valor da função objetivo na solução ótima.
4.5.2 Características das variáveis:
NÚMERO: coluna de numeração interna seqüencial das variáveis definidas para o problema;
NOME: coluna contendo os nomes usados na definição das variáveis;
ESTADO: coluna contendo o estado das variáveis na solução ótima.
LIMITE INFERIOR: coluna contendo os valores definidos ou assumidos para os limites
inferiores das variáveis.
NÍVEL ÓTIMO: coluna contendo os valores assumidos pelas variáveis na solução ótima.
LIMITE SUPERIOR: coluna contendo os valores definidos ou assumidos para os limites
superiores das variáveis.
CUSTO ASSOCIADO: coluna contendo os coeficientes das variáveis na função objetivo.
CUSTO REDUZIDO: coluna contendo a taxa de variação no valor ótimo da função objetivo
(VALOR DA SOLUÇÃO) ocasionada pela variação de uma unidade na variável
correspondente.
4.5.3 Características das restrições.
NÚMERO: coluna contendo a numeração associada à ordem de entrada das restrições.
NOME: coluna contendo os nomes usados na definição das restrições.
ESTADO: coluna contendo o ESTADO das restrições na solução ótima, relacionando o NÍVEL
ÓTIMO com os valores dos limites inferior e superior.
LIMITE INFERIOR: coluna contendo os limites inferiores definidos ou assumidos para os
valores associados às restrições.
NÍVEL ÓTIMO: coluna contendo os valores associados às restrições na solução ótima.
NÍVEL SUPERIOR: coluna contendo os limites superiores definidos ou assumidos para os
valores associados às restrições.
FOLGA ASSOCIADA: coluna contendo a diferença existente entre o LIMITE (superior ou
inferior) e o NÍVEL ÓTIMO associados à restrição.
PREÇO - SOMBRA: coluna contendo a taxa de variação no valor da função objetivo
ocasionada por uma variação unitária na quantidade associada à restrição (disponibilidade do
recurso).
4.5.4 Análise de sensibilidade para os custos (Vetor c).
As colunas NÚMERO, NOME, ESTADO e CUSTO ASSOCIADO seguem as definições dadas
nos itens anteriores.
INTERVALO DE VALIDADE PARA OS CUSTOS:
* NÍVEL MÍNIMO - nesta coluna, tem-se como informação, o nível mínimo que o coeficiente
de custo associado a uma variável pode assumir, sem que os ESTADOS da solução e das
variáveis se modifiquem, ou
seja, de forma que variáveis básicas continuem básicas e
variáveis não básicas continuem não básicas. Qualquer variação nos custos que exceda este
limite poderá provocar uma mudança nos conjuntos de nas variáveis básicas e de não-básicas.
* NÍVEL MÁXIMO - de forma inteiramente análoga, tem-se o limite máximo que o
coeficiente de custo associado a uma variável pode assumir.
2556
4.5.5 Análise de sensibilidade para as variáveis.
As colunas NÚMERO, NOME, ESTADO e NÍVEL ÓTIMO seguem as definições dadas nos
itens anteriores.
VARIAÇÃO NO VALOR DA SOLUÇÃO POR UNIDADE DE
* DECRÉSCIMO - essa coluna nos fornece a variação no VALOR DA SOLUÇÃO devido a
um decréscimo unitário no NÍVEL ÓTIMO da variável em questão.
* ACRÉSCIMO - da mesma forma que a coluna anterior, esta fornece a variação por unidade
de acréscimo.
INTERVALO DE VALIDADE
* NÍVEL MÍNIMO -Valor mínimo que a variável pode assumir de forma que a variação no
VALOR DA SOLUÇÃO dada pela coluna DECRÉSCIMO seja válida.
* NÍVEL MÁXIMO -Valor máximo que a variável pode assumir de forma que a variação no
VALOR DA SOLUÇÃO dada pela coluna ACRÉSCIMO seja válida.
4.5.6 Análise de sensibilidade para as restrições.
As colunas NÚMERO, NOME, ESTADO e NÍVEL ÓTIMO seguem as definições dadas nos
itens anteriores.
VARIAÇÕES NO VALOR DA SOLUÇÃO POR UNIDADE DE
* DECRÉSCIMO - esta coluna nos fornece a variação no VALOR DA SOLUÇÃO devido a
um decréscimo unitário no NÍVEL ÓTIMO da restrição em questão, ou seja, a taxa de
variação da função objetivo ocasionada por uma variação para menos no NÍVEL ÓTIMO
associado à restrição.
* ACRÉSCIMO - da mesma forma que a coluna anterior, esta fornece a variação por unidade
de acréscimo.
INTERVALO DE VALIDADE
* NÍVEL MÍNIMO -Valor mínimo que a restrição (variável linha) pode assumir de forma que
a variação no VALOR DA SOLUÇÃO, dada pela coluna DECRÉSCIMO, seja válida.
* NÍVEL MÁXIMO -Valor máximo que a restrição (variável linha) pode assumir de forma
que a variação no VALOR DA SOLUÇÃO, dada pela coluna ACRÉSCIMO, seja válida.
4.6 Construção do site
O site do PROLIN (figura 4) foi desenvolvido para dar suporte e orientar o usuário para o uso
do programa. Contém seções de exemplos, onde o usuário pode acompanhar exemplos práticos desde
a definição do problema até a sua modelagem, possibilitando uma rápida visualização de como utilizar
o programa. Além do mais, contém uma seção onde se pode ter acesso aos manuais, caso uma consulta
mais detalhada seja desejada.
2557
figura 4 – Tela inicial do site do PROLIN
5. Resultados
O PROLIN está disponível em um site com manuais, exemplos e informações técnicas sobre o
mesmo. O site está hospedado em um servidor da Empresa Júnior de Informática (No Bugs),
localizada no Departamento de Informática da UFV, podendo ser acessado no endereço
www.prolin.ufv.br.
Para verificar a eficiência do uso do PROLIN via web, foram selecionados 4 problemas
diversificados com dimensões razoáveis (até 20 restrições e 80 variáveis). O observado é que o tempo
de resolução destes problemas foi bem reduzido, da ordem dos centésimos de segundo, o que
demonstra a eficiência do sistema. A determinação do tempo de resolução foi baseada na própria
resposta do PROLIN, que já calcula o tempo de resolução dos problemas, assim como o tempo para
as análises de sensibilidade.
Outros testes também foram realizados com problemas com erros no formato, para que se
identificasse alguma falha do código do aplicativo em PHP, de conversão dos dados do problema.
Foram submetidos ao PROLIN vários problemas com os mais diversos tipos de erros de formato. Com
isto, foi possível a correção de algumas distorções não percebidas antes, o que melhorou o sistema em
termos de identificação de erros.
6. Conclusões
As ferramentas de Pesquisa Operacional, geralmente, consomem muitos recursos do
computador e são de alta complexidade, o que requer uma linguagem eficiente e rápida. Quando se
decidiu pela adaptação do PROLIN (implementado na linguagem FORTRAN 77) para uso via web,
preferiu-se manter o programa nesta linguagem, devido à rapidez e à eficiência da mesma para
processamento numérico.
O público alvo para utilizar o PROLIN, nesta versão web, são estudantes de graduação e pósgraduação que precisam utilizar uma ferramenta simples e acessível para resolver problemas genéricos
de Programação Linear. O PROLIN está disponível, hoje, para trabalhar com até 50 restrições e 100
variáveis, um número razoável para o referido público.
7. Referê ncias Bibliográficas
[1] GOLDBARG, M.C. e LUNA, H. P. L., Otimização Combinatória e Programação Linear. Rio de
Janeiro: Editora Campus Ltda, 2000.
2558
[2] RIBEIRO, .A. A .S.; SANTOS, H .N.; OLIVEIRA, A. M.; CUNHA, M.S., Sistema para
Programação Linear - PROLIN - IV Encontro Regional de Matemática Aplicada e Computacional.
SBMAC. Anais, Belo Horizonte, MG, 1987.
[3] GNU Fortran, http://gcc.gnu.org/onlinedocs/gcc-3.1/g77. Acesso em11/11/2001.
[4] The PHP group, http://www.php.net. Acesso em 20/05/2002.
2559