PROLIN: Um Sistema para Programação Linear*

Contato
Heleno do Nascimento Santos
UFV
Campus Universitário
36.571-000 - Viçosa - MG
e-mail: hna@dpi.ufv.br

Autoria
Heleno do Nascimento Santos - UFV
Carlos Antônio A.S. Ribeiro - UFV
Antônio Moisés de Oliveira - UFV
Marcelo Silva Cunha - UFV

*Esta pesquisa foi patrocinada pela Universidade Federal de Viçosa.

PALAVRAS CHAVE: Programação Linear, Otimização, Sistemas Computacionais.

RESUMO
Este artigo apresenta um novo método para se obter uma solução básica viável inicial, sendo o principal ponto no desenvolvimento de um eficiente código computacional, com base no Simplex Revisado, para a solução de problemas de Programação Linear. O algoritmo foi implementado sobre um computador IBM PC compatível, usando o FORTRAN 77 e gerando um código denominado PROLIN. O principal objetivo desse desenvolvimento foi a apresentação dos resultados de uma forma amigável, com uma análise de pós-otimização compreensível. Os resultados são apresentados tendo-se em mente a formulação original do modelo feita pelo usuário.

ABSTRACT
This paper presents a new method to obtain an initial feasible basic solution and the main criteria adopted on the development of an efficient revised simplex algorithm for the solution of linear programming problems. The algorithm was implemented on personal computer using FORTRAN 77, generating a code named PROLIN. The major purpose on the development was the presentation of the results, mainly with the post-optimal analisys results, in order to facilitate its understanding. This is reached presenting the results keeping in mind the original user formulation.

1. Introdução

Inúmeros problemas práticos de otimização nas áreas de adiministração, economia e engenharia podem ser resolvidos com o uso das técnicas de Programação Linear. A disponibilidade de um "software" com interfaces amigáveis e que possa ser utilizado por professores, estudantes e profissionais na área de otimização é algo muito desejado. Segundo consulta a diversos usuários de Programação Linear, uma dificuldade apontada na utilização de códigos computacionais nesta área reside no entendimento dos resultados oriundos da Análise de Sensibilidade. A exposição dos resultados numa forma mais fácil de ser compreendida pelos usuários foi um dos motivos que levaram os autores ao desenvolvimento deste trabalho.

2. Objetivos

O PROLIN é um "software" para resolver problemas de Programção Linear, sendo desenvolvido com três objetivos. O primeiro foi tornar mais fácil a tarefa de interpretar os resultados computacionais associados à solução de um problema de Programação Linear . O segundo foi a aplicação e o desenvolvimento de técnicas capazes de reduzir o esforço computacional exigido pelo Simplex no alcance da solução ótima, se existente. Finalmente. o terceiro objetivo foi disponibilizar um programa que pudesse ser incorporado a outros códigos com propósitos diferenciados.

3. Metodologia

O PROLIN usa a estrutura básica do Simplex Revisado adaptado ao uso de variáveis e restrições canalizadas [1]. Com o objetivo de assegurar a convergência do algoritmo, usa-se a regra anticiclagem de Brand [7]. O armazenamento da matriz básica é feito segundo a forma produto da inversa, adaptada para proceder reinversões periódicas da matriz básica. com o aumento da eficiência computacional e da precisão numérica do algoritmo [2], [5] e [6].

A fim de otimizar o código computacional, aumentando sua capacidade de resolver problemas de grande porte, foram utilizadas também as técnicas de subotimização e de canalização de variáveis e restrições, quando pertinentes.

Desenvolveu-se um novo procedimento de obtenção de uma base inicial com o uso do conceito de variável artificial única [1] e [6]. O algoritmo proposto tem a seguinte estrutura:

1. fixação de cada variável natural em um de seus limites, inferior ou superior. Se existir uma variável livre, seu valor deve ser fixado no nível zero;
2. avaliação do RHS com base nos valores assumidos pelas variáveis naturais no Passo 1;
3. criação de vetores-coluna associados com uma única variável artificial para cada conjunto de restrições ">=" e "<=". Estes vetores serão preenchidos com zeros e uns. Usa-se zero se a restrição for atendida e 1, caso contrário. Para o conjunto de restrições do tipo "<=" , sua única variável artificial será ilimitada inferiormente e seu limite superior será zero. Para o tipo ">=", tais limites serão zero e infinito, respectivamente;
4. após a avaliação do RHS, serão introduzidas as variáveis de folga, conforme apresentado no Quadro 1.

QUADRO 1: Determinação dos Intervalos de Variação da Variáveis de Folga Conforme o Tipo de Restrição.

Tipo	LB	UB	Intervalo de Variação
<= <= >= >= free	-INF LB(i) RHS(i) RHS(i) -INF	RHS(i) INF INF UB(i) INF	[0, INF) [0, (RHS(i) - LB(i))] (-INF,0] [(RHS(i) - UB(i)), 0] (-INF, INF)

onde:
(i) é índice de linha no quadro simplex;
LB(i) é o valor do limite inferior da i-ésima restrição
UB(i) é o valor do limite superior da i-ésima restrição
RHS(i) é o valor dado pelo usuário para o i-ésimo elemento do vetor RHS
INF representa um valor infinitamente grande.

5. Definição do intervalos associados às variáveis artificiais, com base nos seguintes critérios:

a) para o conjunto de restrições do tipo "=", a variável artificial associada pertencerá ao intervalo [0, INF) se b(i) for maior ou igual a zero. Caso contrário, pertencerá ao (-INF, 0];
b) se o valor calculado para b(i) não satisfaz o intervalo de variação estabelecido para a respectiva variável de folga, uma variável artificial será introduzida no Quadro Simplex. Seu intervalo de variação será [0, INF) se b(i) for maior ou igual a zero, sendo (-INF, 0], caso contrário;

Para cada nova variável de folga ou variável artificial que entra no Quadro Simplex, haverá um vetor coluna com zeros e tendo um no respectivo índice de linha. Isto permite uma maneira eficiente de se obter uma solução básica viável inicial. Uma vez atualizado o quadro Simplex verifica-se se existe variável artificial entre as básicas. Se sim, introduz-se uma função objetivo artificial , com seus coeficientes de custo convenientemente estabelecidos. Faz-se então um pivoteamento para cada variável artificial única, a fim de se obter uma solução básica viável inicial. Toda variável livre é forçada a entrar na base, uma vez que ela será sempre básica na solução ótima, se existente.

Após estas considerações importantes, o algoritmo continua como qualquer procedimento Simplex Duas Fases. Na Fase I as variáveis artificiais serão levadas a zero e eliminadas. Somente na Fase II a solução ótima do problema será obtida, se existente. Se alguma variável artificial permanece com valor diferente de zero ao fim da Fase I indica a inexistência de solução ótima para o problema original. Se alguma variável artificial permanece básica no nível zero é indício de solução ótima degenerada, Neste caso, faz-se sua eliminação, retirando-se a respectiva linha e coluna do Quadro Simplex antes de dar início à Fase II.

Terminada a Fase II e encontrada uma solução ótima, procede-se uma Análise de Semsibilidade, caso o usuário a solicite, sendo esta estruturada de uma maneira muito rica em informações.

Devido a alta incidência de erros na codificação dos dados , o "software" é dotado de uma rotina para checar a consistência dos dados apontando a causa de possíveis erros no modelo.

4. Resultados e Discussão

As técnicas aplicadas no desenvolvimento do código computacional PROLIN possibitaram o alcance dos objetivos propostos. Tem-se um produto de fácil uso e eficiente, em uso desde março de 1986 no meio acadêmico da Universidade Federal de Viçosa, já tendo sido utilizado como parte integrante de "softwares" desenvolvidos com outras finalidades como, por exemplo, sistemas especialistas.

A eficiência do algoritmo implementado pode ser confirmada pelos testes comparativos com outros códigos de Programação Linear. A principal causa desse sucesso foi a técnica utilizada para gerar uma base canônica inicial, o que reduziu os esforços computacionais e os requerimentos de memória, evitando que se recalcule o RHS pelo método Simplex padrão. Uma outra razão foi o uso do Sinplex Revisado com a técnica de sub-otimização.

Atualmente, um esforço está sendo feito no DPI/UFV no sentido de adequar o código computacional à interface gráfica windows, a fim de tornar o seu uso mais atraente para o usuário.

5. Bibliografia

[1] BAZARAA, M.S. & JARVIS, J.J. Linear Programming and Networks Flows, John Wiley & Sons, New York, 1977, 565 pp..
[2] BRAGA, L.P.W. e MACULAN FILHO, N., Aspectos Computacionais em Programação Linear. Revista Brasileira de Computação, 1, 1981, pp. 19-32.
[3] BREGALDA, P.F.; OLIVEIRA, A.A. F. de; BORNSTEIN, C.T. Introdução à Programação Linear, Editora Campus, Rio de Janeiro, 1988, 329 pp..
[4] BREMELLER, A.; ALLAN, R.N. and HAMAN, Y.M., Sparsity. Pitman Publishing, London, 1976, 177 p.
[5] DANTIZG, G.B., Linear Programming and Extensions. Princeton University Press, New Jersey, 1963, 627 p..
[6] LASDON, L.S., Optimization Theory for Large Systems. The McMillan Company, London, 1970, 523 p.
[7]. PAPADIMITRIOU, C.H. & STEIGLITZ, K. Combinatorial Optimization: Algorithms and Complexity, Prentice Hall Inc., New Jersey, 1982, 496 pp..