Pesquisa operacional/Método Simplex

O Método Simplex é um algoritmo bastante popular para resolver problemas numéricos de Programação Linear. O jornal Computing in Science and Engineering o considerou um dos 10 mais importantes algoritmos descobertos no século[1].

Através dele, podemos obter a solução ótima de um problema de Programação Linear de forma eficiente.

A Forma Padrão da Programação Linear

editar

O primeiro passo para se resolver um problema de acordo com o algoritmo Simplex é escrevendo o problema na forma padrão:

Máx/Mín   sujeito à:

 

 

.

.

.

 

 

Perceba que a forma padrão que estamos mostrando agora é diferente dos modelos de programação linear vistos no capítulo anterior. Na forma padrão, temos um conjunto de equações, e não apenas uma. A única inequação permitida é aquela que atesta a não negatividade das variáveis de decisão (ou seja, podem ser positivas ou nulas).

Transformando um Modelo de Programação Linear na Forma Padrão

editar

Normalmente, os modelos que criamos não estão na forma padrão. Temos que fazer algumas manipulações algébricas para resolver este problema. Veja os exemplos abaixo:

Exemplo 1: O Modelo tem Desigualdade do Tipo Menor ou Igual

editar

Tome o seguinte modelo:

Máx  

 

 

Como deixar este modelo na forma padrão? É muito simples! Basta adicionar uma variável de folga chamada   e transformar o modelo acima em:

Máx  

 

 

Exemplo 2: O Modelo tem Desigualdade do Tipo Maior ou Igual

editar

Vamos agora tomar um modelo semelhante ao anterior:

Máx  

 

 

Para deixar este exemplo na forma padrão, fazemos algo parecido com o que fizemos no Exemplo 1. Inserimos variáveis de excesso:

Máx  

 

 

Exemplo 3: O Modelo possui Variáveis sem Restrição de Sinal

editar

Mais um exemplo semelhante:

Máx  

 

 

Perceba que desta vez, a variável   não possui restrição de sinal. Ela pode ser tanto positiva como negativa. Para resolver isso, precisamos eliminar a variável incômoda. Podemos simplesmente substituí-la por uma operação de subtração entre duas variáveis não negativas:

Máx  

 

 

Agora é só colocar uma variável de excesso da mesma forma que fizemos no Exemplo 2 e este modelo estará na forma padrão.

Exemplo 4: Uma Equação ou Inequação possui o Lado Direito Negativo

editar

Para que um modelo esteja na forma padrão, o valor à direita de uma equação ou inequação deve ser sempre não-negativo. Então, caso haja equações do tipo:

 

 

A primeira coisa que devemos fazer é multiplicar os dois lados da equação e inequação por (-1):

 

 

Exemplo 5: Um Modelo mais Complexo

editar

Tome o seguinte modelo de Programação Linear:

MÁX   sujeito às restrições:

 

 

 

 

A primeira coisa que deve-se notar é que a variável   não possui nenhuma restrição de sinal. Ela pode ser tanto negativa como positiva ou nula. Teremos que nos livrar desta variável incômoda assim como no Exemplo 3:

MÁX   sujeito às restrições:

 

 

 

 

Agora vamos inserir uma variável de folga chamada   na primeira inequação e uma variável de excesso chamada   na segunda inequação:

MÁX   sujeito às restrições:

 

 

 

 

Agora o único inconveniente são a inequação 2 e a equação 3 que possuem o lado direito negativo. Vamos multiplicá-los por (-1);

MÁX   sujeito às restrições:

 

 

 

 

Voilá! O modelo já está na forma padrão!

Algumas Definições Úteis

editar

Antes de prosseguirmos, é importante que você se acostume com algumas definições que serão usadas nos futuros exemplos e explicações:

  • Função Objetivo: A função inicial que deve ser otimizada em um problema de Programação Linear.
  • Região factível: Conjunto de todas as soluções possíveis para um problema de Programação Linear. Se for um conjunto vazio, o programa linear é dito impossível ou inviável.
  • Solução Básica: Uma solução obtida quando assumimos que um número igual à diferença entre o número de variáveis e o número de equações corresponde à quantidade de variáveis iguais a 0.
  • Solução Factível: É qualquer solução encontrada que satisfaça as equações e inequações do modelo padrão de um problema de Programação Linear.
  • Solução ilimitada: Solução na qual a Solução Ótima tende à infinito.
  • Solução Ótima: Solução para as equações que otimiza o valor da função objetivo.

Referências

editar
  1. Ver Guest Editors' Introduction: The Top 10 Algorithms Jack Dongarra and Francis Sullivan, Comput. Sci. Eng. 2, 22 (2000). Disponível no site do jornal