Pesquisa operacional/Método Simplex: diferenças entre revisões

Origem: Wikilivros, livros abertos por um mundo aberto.
[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
m +cat; +interwiki: en
Linha 161: Linha 161:
* '''Solução ilimitada:''' Solução na qual a '''Solução Ótima''' tende à infinito.
* '''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.
* '''Solução Ótima:''' Solução para as equações que otimiza o valor da função objetivo.


<!-- CATGORIAS -->
[[Categoria:Pesquisa operacional]]

<!-- INTERWIKIS -->
[[en:Operations Research/The Simplex Method]]

Revisão das 15h59min de 28 de março de 2008

O Método Simplex é u 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.

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

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. O único tipo de ineqüação permitido são aquelas que atestam que todas as variáveis deveem ser não-negativas (ou seja, podem ser positivas ou nulas).

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

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

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

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

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

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

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

Exemplo 5: Um Modelo mais Complexo

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 x_{2} 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 x_{4} na primeira inequação e uma variável de excesso chamada x_{5} 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

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