Metodo Simplex

Prof. Célio Moliterno

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.

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

X0 C0

XT

CT

A B

C C A T T

0 -

C B T

0 -

Prof. Célio Moliterno

PESQUISA OPERACIONAL

Exemplo:

Minimizar: z = 80x1 + 60x2

Sujeito a : 0,20x1 + 0,32x2
0,25

x1 + x2 = 1

com: 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 C
[ 80 , 60 , 0 , M ]T

A 








1 1 0 1

0,20 0,32 1 0

B









1

0,25

X0









x

x

4

3

C C A T T

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








1 1 0 1

0,20 0,32 1 0

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

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

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

C B T

0 - = - [ 0 , M ]








1

0,25

= - M

Prof. Célio Moliterno

PESQUISA OPERACIONAL

QUADRO SIMPLEX

Exercício:

Maximizar: z = x1 + 9x2 + x3

sujeito a: x1 + 2x2 + 3x3
9

3x1 + 2x2 + 2x3
15

com: todas as variáveis não negativas

Passando para forma Matricial

X
[ x1 , x2 , x3 , x4 , x5 ]T C
[ 1 , 9 , 1 , 0 , 0 ]T

A 








3 2 2 0 1

1 2 3 1 0

B









15

9

X0









x

x

5

4

X1 X2 X 3 X 4

80 60 0 M

X3 0

X4 M

0,25

1

0,20 0,32 1 0

1 1 0 1

80-M 60-M 0 0 -M

Prof.