Saltar para o conteúdo

Pesquisa operacional/Método Simplex

Origem: Wikilivros, livros abertos por um mundo aberto.

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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.
  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