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 ( e ), devese encontrar os valores respectivos para as demais variáveis (folga/excesso) que satisfaçam as restrições do problema.
e alpha=0,5;
Passo 1
Reescrever o problema em forma de igualdade adicionando variáveis de folga/excesso. Para isso introduzimos s1,s2,s3>=0 de modo que:
O vetor de custos fica c=[3,2,0,0,0]^T e a matriz A tem 4 linhas (as igualdades) e 5 colunas (as variáveis).
Passo 2
Definir solução inicial factível primal-dual. Como dado temos x^0=(x1,x2)=(1,2). Das igualdades obtemos
s1=16-1-3cdot2=9, s2=2-1=1, s3=5-1=4, 2cdot1-2=0
Logo x^0=(1,2,9,1,4)^T>0. Escolhemos também um y^0 e definimos o resíduo dual z^0=c-A^Ty^0>0 de forma que todos os componentes fiquem positivos (por exemplo y^0=(-1,1,-1,0) gera z^0>0).
Passo 3
Descrever a iteração do Método Afim-Scaling. Numa iteração k montamos:
X^k=diag(x^k) e (X^k)^2.
Montar M=A(X^k)^2A^T e b'=A(X^k)^2c.
Resolver M,w=A(X^k)^2c para w.
Calcular o resíduo d^k=(c-A^T w) e a direção afim
p^k=(X^k)^2d^k
5) Atualizar x^k+1=x^k+alpha,p^k,
com alpha=0.5, garantindo x^k+1>0.
Passo 4
Calcular explicitamente a primeira iteração e apresentar os quatro primeiros pontos aproximados.
Após montar M e resolver para w (cálculo detalhado omitido por extensão), obtém-se as atualizações:
Iteração 1: x^1approx(1.5255,;3.055,;5.384,;2.051,;3.475)^T.
Em seguida aplica-se o mesmo procedimento para as iterações 2, 3 e 4, chegando aos pontos aproximados:
Iteração 2: x^2approx(1.980,;3.860,;4.156,;2.190,;3.615)^T,
Iteração 3: x^3approx(2.307,;4.182,;2.941,;2.438,;4.160)^T,
Iteração 4: x^4approx(2.514,;4.379,;2.050,;2.561,;4.267)^T.
Resposta
Os quatro primeiros pontos interiores gerados são aproximadamente: