Baixe o app para aproveitar ainda mais
Prévia do material em texto
Obtendo uma solução básica factível inicial Método Simplex duas fases Base inicial – FASE I • Como determinar uma partição básica factível inicial (A=(B, N)). • Algumas classes de problemas de otimização linear oferecem naturalmente a solução básica factível Minimizar f(x) = cTx sujeito a: Ax ≤ b x ≥ 0 em que b ≥ 0. Base inicial – FASE I Minimizar f(x) = cTx sujeito a: Ax ≤ b x ≥ 0 em que b ≥ 0. Após a introdução das variáveis de folga, digamos, xf, temos: Minimizar f(x) = cTx sujeito a: Ax + xf = b x ≥ 0, xf ≥ 0, A matriz dos coeficientes das restrições agora é dada por [A I] e uma partição básica factível é dada por: • B = I: as variáveis básicas são as variáveis de folga xB = xf • N = A: as variáveis não-básicas são as variáveis originais xN = x, e a solução básica factível é dada por: == ≥== . , 0xx 0bxx N B f • Suponha agora que as restrições são, originalmente, de igualdade: • Precisamos encontrar uma partição básica factível de A, isto é, uma partição da forma: tal que existe e Base inicial – FASE I Quantas partições existem ? • Tome A10 x 20 Precisamos identificar dez colunas L.I. de A para formar B, e o sistema Bxb = b, tem que ter xB ≥ 0. • Procedimento possível: – 1. Escolher dez (m) colunas – 2. Verificar se xB ≥0. – 3. Se não, escolher outras dez colunas e retornar ao passo 2. Quantas possíveis partições existem ? • Se formos testar partição a partição, quantos testes temos que fazer ? impraticável para problemas grandes! Introduzindo novas variáveis de folga • Quando tínhamos variáveis de folga, funcionava, pois: • Se não for o caso, podemos forçar variáveis de folga: uma partição [I N] onde as variáveis de folga começam como as variáveis básicas. Fase I • Obviamente, essas variáveis não podem aparecer na solução final (pois elas não existem - são variáveis artificiais). • Método duas-fases: resolvemos primeiro um problema: Fase I • Se conseguimos uma solução de custo zero para o problema acima (fase I), a base final não contém nenhuma variável artificial (por quê ?) • Neste caso, a base final do problema da fase I é uma base inicial para o problema real (fase II). Fase I • E se não conseguimos uma solução de custo zero ? (Isto é, na solução ótima da fase I, existe uma variável artificial na base). (Não existe solução factível para o nosso problema) Exemplo Forma padrão Qual o problema da fase I a resolver ? • Caso A: introduzimos uma variável artificial pra cada restrição: e minimizamos o custo destas variáveis. Qual o problema da fase I a resolver ? • Caso B: note que x4 já fornece uma coluna da matriz identidade. Assim, a rigor, precisamos apenas de uma variável artificial: e minimizamos o custo desta variável. Exemplo Obtenha a solução do problema original. Outra possibilidade • Em vez de resolver um problema auxiliar (fase I) para encontrar a base, simplesmente penalizamos as variáveis artificiais no problema original (fase II), de modo a garantir que elas sejam nulas na solução ótima: valor suficientemente grande para garantir que xvalor suficientemente grande para garantir que x55 nnãão aparece na soluo aparece na soluçãção o óótima.tima. Considere o Exemplo 3,2,1i,0x 4x3xx 3xxx x2xxf i 321 321 321 =≥ ≤+− =++ +−= 2 :asujeito )(minimizar x 4,...,1i,0x 4xx3xx 3xxx x0x2xxf i 4321 321 4321 =≥ =++− =++ ++−= 2 :asujeito )(minimizar x Forma Padrão Variável artificial apenas primeira restrição: Obter uma solução Inicial para o problema. 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :asujeito )(minimizar Exemplo 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :a sujeito )(minimizar Para resolver o problema artificial, aplicamos o método simplex. Fase I: Partição básica factível inicial: 41 =B 52 =B 11 =N 22 =N 33 =N = 01 10 B e − = 312 111 N 1a. Iteração 1. Solução básica: Resolva o sistema bxB =Bˆ , cuja matriz aumentada é 4 3 01 10 e obtenha a solução: = = 3 4 x x ˆ 5 4 Bx Exemplo 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :a sujeito )(minimizar 1. Teste de otimalidade: i) Vetor multiplicador: Resolva o sistema BT cλB = , cuja matriz aumentada é 1 0 01 10 e obtenha = 0 1 λ ii) Custos relativos 11 =N : 1ccˆ 1 T 11 −=−= aλ ← 1Nx = x1 entra na base 22 =N : 1ccˆ 2 T 22 −=−= aλ 33 =N : 1ccˆ 3 T 33 −=−= aλ Exemplo 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :a sujeito )(minimizar 1. Direção simplex: Resolva o sistema 1aBy = , cuja matriz aumentada é 2 1 01 10 e obtenha y = 1 2 1. Tamanho do passo 1 B i i B y x 2 1 3 , 2 4 min0y y x min 1i == = >=ε ( 1Bx = x4 sai da base) 2. Atualização 1B1 = 5B2 = 4N1 = 2N2 = 3N3 = = 02 11 B e − = 311 110 N Exemplo 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :a sujeito )(minimizar 2a. Iteração: 1B1 = 5B2 = 4N1 = 2N2 = 3N3 = 1. Solução básica: Resolva o sistema bxB =Bˆ : 4 3 02 11 e obtenha = 1 2 ˆ Bx 2. Teste de otimalidade i) Vetor multiplicador: Resolva o sistema BT cλB = : 1 0 01 21 e obtenha λλλλ = − 21 1 ii) Custos relativos 4N1 = : 21444 =−= aλTccˆ 22 =N : 23222 −=−= aλ Tccˆ ← 2Nx = x2 entra na base 3N3 = : 3 1 3 T 33 ccˆ =−= aλ Exemplo 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :a sujeito )(minimizar 1. Direção simplex: resolva o sistema 2aBy = : − 1 1 02 11 e obtenha − = 2 3 2 1 y 2. Tamanho do passo 2 B 3 2 2 3i i B y x ; 1 min0y y x min 2i == = >=ε ( 2Bx = x5 sai da base - Variável artificial ) 1. Atualização: 1B1 = 2B2 = 41 =N 5N 2 = 3N3 = − = 12 11 B Fim da FASE I Exemplo – FASE II 5,...,1i,0x 4xx3xx 3xxxx xx,...,xf i 4321 5321 551a =≥ =++− =+++ = 2 :a sujeito )(minimizar FASE I – Problema Artificial Fase II: Aplicar o método simplexa partir da base obtida na Fase I. A variável artificial (segunda variável não básica: N2 = 5) é descartada e os índices não básicos são redefinidos: N1 = 4, N2 = 3. Exercício Obtenha a uma base factível inicial do problema. 1 2 1 2 1 2 1 2 3 4 : 4 2 3 1 8 0 , 0 M i n i m i z e x x s u j e i t o a x x x x x x − + + ≤ + ≥ ≥ ≥
Compartilhar