Método simplex

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)  existe pelo 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 uma