Metodo simplex duas faces

Notas de aula de Programação Matemática. c Mestrado em Engenharia Mineral/Escola de Minas/UFOP.

Método Simplex das Duas Fases

1 Descrição do método
Suponhamos inicialmente que tenham sido efetuadas transformações no PPL, de modo que tenhamos bi ≥ 0, para todas as restrições. Para cada igualdade i introduziremos uma variável articial não-negativa xa . Também em cada desigualdade do tipo ≥ adicionarei mos, além da variável de folga, uma variável articial não-negativa, isto é : n j=1

  aij xj = bi ↔    aij xj ≥ bi ↔ 

aij xj j=1 xa ≥ 0 i n j=1

n

+ xa = bi i

n j=1

aij xj − xn+i + xa = bi i

xn+i ≥ 0, xa ≥ 0 i

A fase I do método visa a obtenção de uma solução básica viável inicial para o PPL original P. Com a introdução das variáveis articiais, temos um novo PPL P', diferente de P, mas com uma solução básica viável inicial fácil de ser obtida. Para tanto, basta considerar como variáveis básicas: (a) as variáveis de folga associadas às restrições do tipo ≤, (b) as variáveis articiais correspondentes às demais restrições. A seguir, devemos caminhar de SBV (Solução Básica Viável) em SBV de P' até se obter uma SBV de P. A questão é saber quando teremos uma solução básica viável de P. Para cumprir esse objetivo, trabalharemos na primeira fase com uma função objetivo articial, a saber, Qa (x) = xa , a qual deve ser minimizada. Como xa ≥ 0 ∀ i, o i i menor valor possível será obtido para xa = 0 ∀i . i Terminando a Fase I, abandonamos Qa (x) e passamos a trabalhar com a função objetivo dada no problema original. i 1.1 Exemplo 1
Aplicar o método simplex ao seguinte PPL :

Maximizar sa:

Q(x)= 6x1 - x2 4x1 + x2 2x1 + 3x2 x1 x2 x1 ≥ 0 ; x2

≤ 21 ≥ 13 = -1 ≥0

2

Marcone Jamilson Freitas Souza

Introduzindo as variáveis de folga e as variáveis articiais, obtém-se:

Minimizar sa:

Q'(x)= -6x1 + x2 4x 1 2x 1 −x1 + x2 + x3 + 3x2 - x4 + x2 x1 , x2 , x3 , x4 , xa , xa ≥ 0 1 2 = = = 21 13 1

+

xa 1 +

xa 2

Temos