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
ll1 & 2 e alpha=0,9;

Passo 1

O problema é uma PL de maximização de z = 3x1 + 2x2 sujeita a desigualdades e uma igualdade. Vamos usar o Método de Pontos Interiores Primal Afim-Escala, que exige: todas as restrições em forma de igualdade e uma solução inicial estritamente positiva.

Passo 2

Primeiro transformamos as desigualdades em igualdades com variáveis de folga/excesso:\
x0 = (x1,x2)=(1,2)\
Dado x^(0) = (1,2,9,1,4)^T, encontramos:
Assim a solução inicial é

Passo 3

A cada iteração montamos D = diag(x), calculamos
M = A D^2 A^T, y = M^-1(A D^2 c), g = c - A^T y, d x = alpha D^2 g, x^new = x + d x,
com alpha=0.9 e matriz A e vetor c=(3,2,0,0,0)^T definidos acima.

Passo 4

Iteração 1 (detalhada):
x^(0)=(1,2,9,1,4)
D^2=diag(1,4,81,1,16),
montamos
M=A D^2 A^T,;A D^2 c, resolvemos
yapprox(0.091,-2.099,0.0656,0.897)^T,
calculamos
g=c - A^T yapprox(1.0502,0.5247,-0.0910,2.0990,-0.0656)^T,
d x=0.9,D^2 gapprox(0.9452,1.8889,-6.6316,1.8891,-0.9449)^T,
e atualizamos
x^(1)approx(1.9452,3.8889,2.3684,2.8891,3.0551)^T,
com z^(1)=3cdot1.9452+2cdot3.8889approx13.6134

Passo 5

Iterações 2 a 4 (resultados aproximados):
Iteração k | x^(k)=(x1,x2,s1,s2,s3) | z^(k)=3x1+2x2
1 | (1.9452, 3.8889, 2.3684, 2.8891, 3.0551) | 13.6134
2 | (2.2330, 4.4660, 0.3670, 3.4660, 2.7670) | 15.6310
3 | (2.2740, 4.5480, 0.2280, 3.5480, 2.7260) | 15.9180
4 | (2.2857, 4.5714, 0.1429, 3.5714, 2.7143) | 16.0000

Resposta

Após 4 iterações, a solução aproximada é
x^(4)approx(2.2857,;4.5714,;0.1429,;3.5714,;2.7143)^T,
com valor objetivo z^(4)approx16

Exercícios relacionados