Metodo simplex duas faces

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2180 palavras )
  • Download(s) : 0
  • Publicado : 20 de abril de 2013
Ler documento completo
Amostra do texto
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 umnovo 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 quandoteremos 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 omé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

Temosentão o seguinte quadro:

VB x3 xa 1 xa 2

x1 4 2 -1 -6

x2 1 3 1 1

x3 1 0 0 0

x4 0 -1 0 0

xa 1 0 1 0 0

xa 2 0 0 1 0

b 21 13 1 Q'

O sistema anterior apresenta a seguinte solução básica, a saber: variáveis não-básicas, x1 = x2 = x4 = 0; e variáveis básicas, x3 = 21, xa = 13, xa = 1. Substituindo os valores 1 2 encontrados para x1 e x2 nas restrições do problema original,vericamos que algumas restrições são violadas. Iremos introduzir a função objetivo articial, que representa a soma das inviabilidades, a qual deve ser minimizada. Logo podemos montar o seguinte quadro:

(L1 ) (L2 ) (L3 ) (L4 ) (L5 )

VB x3 xa 1 xa 2

x1 4 2 -1 0 -6

x2 1 3 1 0 1

x3 1 0 0 0 0

x4 0 -1 0 0 0

xa 1 0 1 0 1 0

xa 2 0 0 1 1 0

b 21 13 Q.1 1 Qa Q'

Como xa e xa estãona base, devemos anular seus coecientes na função objetivo articial, 2 1 de forma a colocar a PPL na forma canônica. Para tanto, efetuamos a seguinte operação com linhas: L4 ← −L2 + L4 e L4 ← −L3 + L4 , que resultam no quadro a seguir:

(L1 ) (L2 ) (L3 ) (L4 ) (L5 )

VB x3 xa 1 xa 2

x1 4 2 -1 -1 -6

x2 1 3 1 -4 1

x3 1 0 0 0 0

x4 0 -1 0 1 0

xa 1 0 1 0 0 0

xa 2 0 0 1 0 0

b21 13 Q.2 1 a Q − 14 Q'

Note-se que na linha da função objetivo articial temos coecientes negativos, sendo o de x2 o menor deles. Assim, a variável x2 deve entrar na base e uma vez que o xa = min {21/1, 13/3, 1/1} = 1 , então xa deixará a base (L3 é a linha pivotal). 2 2 Desta forma, obtemos o quadro Q.3 a partir das seguintes operações: L1 ← −L3 + L1 ; L2 ← −3L3 + L2 ; L4 ← 4L3 + L4 e L5 ←−L3 + L5

(L1 ) (L2 ) (L3 ) (L4 ) (L5 )

VB x3 xa 1 x2

x1 5 5 -1 -5 -5

x2 0 0 1 0 0

x3 1 0 0 0 0

x4 0 -1 0 1 0

xa 1 0 1 0 0 0

xa 2 -1 -3 1 4 -1

b 20 10 Q.3 1 Qa − 10 Q'-1

Método Simplex das duas fases

3

Ainda há coeciente negativo na linha da função objetivo articial. Logo x1 deve entrar na base. Temos ainda que xa = min {20/5, 10/5} = 2, o que indica que xa...
tracking img