Metodo simplex

PESQUISA OPERACIONAL

MÉTODO SIMPLEX QUADRO SIMPLEX
O Método Simplex é um procedimento matricial para resolver o modelo de programação linear na forma normal. Começando com X0 , o método localiza sucessivamente outras soluções básicas viáveis acarretando melhores valores para a função objetivo até ser obtida a solução ótima. Para os problemas de minimização, o método simplex utiliza o Quadro abaixo.

XT CT X0 C0
T

A

B
T 0

C −C

A

−C0 B

T

Para os problemas de maximização o Quadro acima é aplicado desde que os elementos da linha inferior sejam colocados com sinal invertido. Uma vez obtida esta ultima linha do Quadro, a segunda linha e a segunda coluna do Quadro, correspondentes a CT e C0, respectivamente, tornam-se supérfluas e podem ser eliminadas.

CT : vetor linha dos custos correspondentes. X : é o vetor coluna de incógnitas (incluindo variáveis de folga, excesso e artificiais). A : é a matriz de coeficientes das equações de restrições. B : é o vetor coluna dos valores à direita das equações representando as restrições. X0: é o vetor coluna de variáveis de folga e artificiais C0 : é o vetor coluna de custo associado com as variáveis em X0

Prof. Célio Moliterno

PESQUISA OPERACIONAL Exemplo:
Minimizar: z = 80x1 + 60x2 Sujeito a : com: 0,20x1 + 0,32x2 0,25 x2 = 1 x1 + x1 e x2 não negativos

Adicionando uma variável de folga x3 e uma variável artificial x4, respectivamente, as primeira e segunda restrições. Minimizar: z = 80x1 + 60x2 + 0x3 + Mx4 0,20x1 + 0,32x2 + x3 = 0,25 x1 + x2 +x4 = 1 com todas as variáveis não negativas Passando para forma normal matricial
X [ x1 , x2 , x3 , x4 ] T 0,20 0,32 1 0 1 1 0 1 C [ 80 , 60 , 0 , M ]T 0,25 1

A

B

X0

x x

3 4

C −C

T

T 0

A = [ 80 , 60 , 0 , M ] – [ 0 , M ]

0,20 0,32 1 0 1 1 0 1

[ 80 , 60 , 0 , M ] – [ 0 + M , 0 + M , 0 , M ] [ 80 , 60 , 0 , M ] – [ M , M , 0 , M ]

[ 80 – M , 60 – M , 0 , 0 ]
−C0 B = -[0,M]
T

0,25 =-M 1

Prof. Célio Moliterno