Pesquisa operacional

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 i . Também em cada desigualdade do tipo ¸ adicionaremos, além da variável de folga, uma variável articial não-negativa, isto é :
Pn
j=1 aijxj = bi $
8<
:
Pn
j=1 aijxj + xa i = bi xa i ¸ 0
Pn
j=1 aijxj ¸ bi $
8<
:
Pn
j=1 aijxj ¡ xn+i + xa i = bi xn+i ¸ 0; xa i ¸ 0
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) =
P
i xa i , a qual deve ser minimizada. Como xa i ¸ 0 8 i, o menor valor possível será obtido para xa i = 0 8i .
Terminando a Fase I, abandonamos Qa(x) e passamos a trabalhar com a função objetivo dada no problema original.
1.1 Exemplo 1
Aplicar o método simplex ao seguinte PPL :
Maximizar Q(x)= 6x1 - x2 sa: 4x1 + x2 · 21
2x1 + 3x2 ¸ 13 x1 - x2 = -1 x1 ¸ 0 ; x2 ¸ 0
2 Marcone Jamilson Freitas Souza
Introduzindo as variáveis de folga e as variáveis articiais, obtém-se:
Minimizar Q'(x)= -6x1 + x2 sa: 4x1 + x2 + x3 = 21
2x1 + 3x2 - x4 + xa
1 = 13
¡x1 + x2 + xa
2 = 1 x1, x2, x3, x4, xa
1 , xa
2 ¸ 0
Temos então o