Método simplex

Disponível somente no TrabalhosFeitos
  • Páginas : 22 (5497 palavras )
  • Download(s) : 0
  • Publicado : 8 de novembro de 2011
Ler documento completo
Amostra do texto
CAPÍTULO 3

Método Simplex

1. Soluções Básicas Admissíveis
Considere um problema de PL representado nas suas formas padrão e matricial. Uma base é um conjunto de m variáveis, tais que a matriz dos coeficientes do sistema de equações lineares (3.2) é não singular (isto é, cujo determinante é não nulo). Por outras palavras, é toda a submatriz quadrada regular (m×m) contida em A (m×n)  existepelo menos uma, já que car (A) = m < n. Então, pode-se rescrever a matriz A da seguinte forma : A= B

[

N

]

onde N é a submatriz formada pelas colunas de A que não estão na base B. Da mesma forma, se pode particionar o vector X em X = XB
e o vector C em C = CB

[

XN T

]

[

CN .

]

Portanto, o problema pode ser representado da seguinte forma : Maximizar

Z = CB

[ XB  CN ×   X N   

]

Sujeito a

[B

XB  N ×  = b ⇔ B XB + N XN = b X N   

]

X≥0

28

Método Simplex

Considere-se as seguintes definições :
variáveis básicas (VB) : as m variáveis que formam a base do sistema variáveis não básicas (VNB) : as restantes n-m variáveis solução básica (SB) : solução cujos valores das VNB são nulos (X com XN = 0 e XB = B-1 b)solução básica admissível (SBA) : SB com todas as VB não negativas (XB ≥ 0) SBA não degenerada : SBA em que as VB são estritamente positivas (XB > 0) SBA degenerada : SBA em que uma ou mais VB são nulas base admissível : uma base que corresponde a uma solução básica admissível

um ponto x ∈ X é ponto extremo se e só se constituir uma SBA do problema de PL o conjunto dos vértices de um politopo X= { x : A x = b, x ≥ 0, x ∈ Rn } corresponde ao conjunto
de soluções básicas admissíveis

o conjunto dos PE da região admissível corresponde ao conjunto das SBA e são ambos não vazios, desde que a região admissível seja não vazia. Cada SBA é equivalente a um PE, mas podem existir várias SBA correspondendo ao mesmo PE.
Propriedades dos pontos extremos admissíveis : 1. Se existe apenas umasolução óptima, então tem de ser um PE admissível. 2. Se existem várias soluções óptimas, então pelo menos 2 são PE admissíveis adjacentes. 3. Existe um número finita de PE admissíveis. 4. Se um PE admissível não tem PE admissíveis adjacentes melhores, então esse PE é óptimo.

As propriedades 1 e 2, implicam que a pesquisa de uma solução óptima pode ser reduzida, considerando apenas os PEadmissíveis; desta forma, existe um número finito de soluções a considerar (propriedade 3). A propriedade 4 fornece um teste de optimalidade muito conveniente.

2. Método Simplex
O método Simplex explora as 4 propriedades dos pontos extremos admissíveis apresentadas no sub-capítulo anterior (1), apenas examinando relativamente poucos PE admissíveis e parando logo que um deles passe o teste de optimalidade.Desta forma, o método Simplex move-se repetidamente (iterativamente) do PE admissível actual para um melhor PE admissível, até que a solução actual não tenha nenhum PE admissível adjacente melhor. Este processo é composto pelos seguintes passos :
1º) Iniciação : Começar com um PE admissível. Qualquer PE admissível pode ser adoptada como

solução inicial; no entanto, uma boa hipótese para a SBAinicial será considerar as slacks como VB e as originais como VNB.
2º) Iteração : Mover-se para um melhor PE admissível adjacente. (Repetir este passo quantas

vezes forem necessárias). Este movimento implica a conversão de uma VNB numa VB
Método Simplex

Algoritmo Primal Simplex (problema de maximização)

29

(chamada a variável básica de entrada) e, simultaneamente, a conversão deuma VB numa VNB (chamada variável básica de saída), para depois identificar a nova SBA.
3º) Teste de optimalidade : O PE admissível actual é óptimo se nenhum dos PE admissíveis seus

adjacentes são melhores.

3. Algoritmo Primal Simplex (problema de maximização)
Considere-se um problema de PL de maximização na sua forma padrão (Error! Reference
source not found.). Na resolução de um...
tracking img