Resolva pelo menos 4 iterações do problema de otimização linear abaixo, empregando o Método de Pontos Interiores Prima Afim Escala a partir das seguintes situações:
Observe que:
  • para esse método, todas as restrições devem estar na forma de igualdade. Logo deve-se acrescentar variáveis de folga/excesso às 3 primeiras restrições, e, assim, o problema passará a contar com 5 variáveis.
  • considerando as soluções iniciais indicadas para as duas variáveis originais ( x1 e x2 ), devese encontrar os valores respectivos para as demais variáveis (folga/excesso) que satisfaçam as restrições do problema.
& Maximizar z=3 x1+2 x2 & Sujeito a & x1+3 x2 & <= 16 x2 & >= 1 & x1 & <= 5 2 x1-x2 & =0 & x1, x2 >= 0
ll2 & 4 e alpha=0,5;

Passo 1

O enunciado pede pra maximizar z=3x₁+2x₂ sujeito a três inequações e uma igualdade, todas convertidas em igualdade com variáveis de folga/excesso. Vamos usar as variáveis x₃ (folga na 1ª), x₄ (excesso na 2ª) e x₅ (folga na 3ª). A igualdade 2x₁–x₂=0 permanece. Nosso problema em forma padrão (minimização) é: minimizar cᵀx com
[ A x = b, x ≥ 0 ],
onde
A = 1 & 3 & 1 & 0 & 00 & 1 & 0 & -1&01&0&0&0&12&-1&0&0&0, b=16150, c=-3-2000

Passo 2

A solução inicial dada é x⁰=(x₁,x₂)=(2,4), e das folgas:
x₃=16−(2+3·4)=2, x₄=4−1=3, x₅=5−2=3 → x⁰=(2,4,2,3,3)ᵀ.

Passo 3

A partir daqui aplicamos o método de pontos interiores primal afim-escala: cada iteração k faz
  1. montar Xᵏ=diag(xᵏ), Xᵏ²,
  2. definir g = A Xᵏ² c, M = A Xᵏ² Aᵀ,
  3. resolver Mλ = g
  4. calcular direção d = −Xᵏ² (c − Aᵀλ)
  5. θₘₐₓ = min{−xᵏᵢ/dᵢ | dᵢ<0}, θ = α·θₘₐₓ com α=0,5
  6. xᵏ⁺¹ = xᵏ + θ d mantém factibilidade.

Passo 4

1ª iteração:
X⁰²=diag(4,16,4,9,9), X⁰²c = (−12,−32,0,0,0)ᵀ,
g=A X⁰²c = (−108,−32,−12,8)ᵀ,
M=A X⁰²Aᵀ =
152&48&4&-4048&25&0&-164&0&13&8-40&-16&8&32

Passo 5

Resolvendo Mλ=g dá λ≈(−0.9204,−0.1184,−0.0578,−0.9449)ᵀ.
Então d=−X⁰²(c−Aᵀλ)≈(0.5280,1.045,−3.6816,1.0656,−0.5202)ᵀ.
θₘₐₓ = min{2/3.6816,3/0.5202}=0.5435 → θ=0.2718.
x¹=x⁰+θd≈(2.1435,4.284,1.000,3.2896,2.8587)ᵀ.

Passo 6

2ª iteração: recomputando
X¹²≈diag(4.596,18.353,1,10.819,8.173),
X¹²c≈(−13.788,−36.706,0,0,0)ᵀ,
g≈(−123.906,−36.706,−13.788,9.130)ᵀ,
M≈ 170.773&55.059&4.596&-45.86755.059&29.172&0&-18.3534.596&0&12.769&9.192-45.867&-18.353&9.192&36.737,

Exercícios relacionados