Optimização por método generalizando o de Lagrange

Maio 4, 2008

Optimização por método generalizando o de Lagrange

Filed under: Análise Matemática,Caderno,Cálculo,Exercícios Matemáticos,Matemática,Optimização,Problemas,Teorema / Teoria — Américo Tavares @ 11:07 am
Tags: Caderno, Matemática, Optimização, Problema

pdf: ver caderno

Considere o seguinte problema de optimização.

Usando as condições suficientes de optimalidade encontre o par $\left( x^{\ast },y^{\ast}\right)$ onde a função $g$

$g\left( x,y\right) =\left( x+2\right) \left( y+1\right)$

sujeita à restrição

$4x+6y=130$

tem um máximo.

[Adaptado de um problema do exame de 28 de Janeiro de 2006 de Métodos Numéricos I, do Curso de Informática de Gestão da Universidade do Minho.]

$\bigskip$

Resolução

$\bigskip$

O problema de optimização corresponde a determinar o mínimo da função $f=-g$

$f\left( x,y\right) =-\left( x+2\right) \left( y+1\right)$

sujeita à restrição

$c\left( x,y\right) =0$

em que

$c\left( x,y\right) =4x+6y-130.$

$\bigskip$

Nota teórica

Se $\left( x^{\ast },y^{\ast }\right)$ satisfizer as duas condições seguintes é um mínimo:

(i) o par $\left( x^{\ast },y^{\ast }\right)$ verifica simultaneamente as $n$ equações

$\nabla f\left( x^{\ast },y^{\ast }\right) -\nabla c\left( x^{\ast },y^{\ast}\right) \lambda ^{\ast }=0$

e as $m$ equações

$c\left( x^{\ast },y^{\ast }\right) =0$

(ii) Se para todo o $s$ tal que $\left( \nabla c\right) ^{T}s=0$ $\left( \text{com }s\neq 0\right)$ ,

$s^{T}\nabla _{xx}^{2}L\left( x^{\ast },\lambda ^{\ast }\right) s>0$ ,

em que

$\nabla _{xx}^{2}L\left( x,y\right) =\nabla ^{2}f\left( x\right)-\displaystyle\sum_{i=1}^{m}\lambda _{i}\nabla ^{2}c_{i}\left( x\right)$ .

A função Lagrangeana $L\left( x,y\right)$ é a função

$L\left( x,\lambda \right) =f\left( x\right) -c\left( x\right) ^{T}\lambda =f\left( x\right) -\displaystyle\sum_{i=1}^{m}c_{i}\left( x\right) \lambda _{i}$

e as matrizes $c\left( x\right)$ e $\lambda ,$ respectivamente

$c\left( x\right) =$ $\begin{pmatrix}c_{1}\left( x\right)\\\vdots\\c_{m}\left( x\right ) \end{pmatrix}$

$\lambda =\begin{pmatrix}\lambda _1\\\vdots\\\lambda_m\end{pmatrix}$

$\bigskip$

* * *

Vamos ver: tem-se

$\displaystyle\nabla f=\begin{pmatrix}\dfrac{\partial f}{\partial x} \\\dfrac{\partial f}{\partial y}\end{pmatrix}=\begin{pmatrix}-y-1\\-x-2\end{pmatrix}$

$\displaystyle\nabla c=\begin{pmatrix}\dfrac{\partial c}{\partial x}\\\dfrac{\partial c}{\partial y}\end{pmatrix}=\begin{pmatrix}4\\6\end{pmatrix}$

$\displaystyle\lambda =\left( \lambda \right)$

A condição (i) é equivalente ao sistema

$-y-1-4\lambda =0$

$-x-2-6\lambda =0$

$4x+6y=130$

A matriz ampliada deste sistema, após troca de linhas, vem

$\begin{pmatrix}4&6&0&|&130\\-1&0 &-6&|&2\\ 0 &-1&-4&|&1\end{pmatrix}$ $\Leftrightarrow$ $\begin{pmatrix}4&6&0&|&130\\ 0&3/2&-6&|&69/2\\ 0&0&-8&|& 24\end{pmatrix}$

cuja solução é

$x=\dfrac{130-66}{4}=16$

$y=\left( \dfrac{69}{2}-18\right) \times \dfrac{2}{3}=11$

$\lambda =-3$

Por conseguinte, $\left( x^{\ast },y^{\ast }\right) =\left( 16,11\right)$ satisfaz (i). Quanto a (ii), tem-se

$\nabla ^{2}f=$ $\begin{pmatrix}\dfrac{\partial ^{2}f}{\partial x^{2}}&\dfrac{\partial ^{2}f}{\partial y\partial x} \\\dfrac{\partial ^{2}f}{\partial x\partial y} &\dfrac{\partial ^{2}f}{\partial y^{2}}\end{pmatrix}=$ $\begin{pmatrix}0&-1\\-1&0\end{pmatrix}$

$\nabla ^{2}c=$ $\begin{pmatrix}\dfrac{\partial ^{2}c}{\partial x^{2}}&\dfrac{\partial c}{\partial y\partial x}\\\dfrac{\partial ^{2}c}{\partial x\partial y}&\dfrac{\partial ^{2}c}{\partial y^{2}}\end{pmatrix}=$ $\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}$

Logo

$\nabla _{xx}^{2}L\left( x,y\right) =\nabla ^{2}f\left( x\right) -\lambda\nabla ^{2}c=\nabla ^{2}f=$ $\begin{pmatrix}0&-1\\-1&0\end{pmatrix}$

Como

$\left( \nabla c\right) ^{T}s=0\Leftrightarrow\begin{pmatrix}4&6\end{pmatrix}\begin{pmatrix}s_{1}\\s_{2}\end{pmatrix}=0\Leftrightarrow 4s_{1}+6s_{2}=0\Leftrightarrow s_{2}=-\dfrac{2}{3}s_{1}$

$s^{T}\nabla _{xx}^{2}L\left( x^{\ast },\lambda ^{\ast }\right) s=\begin{pmatrix}s_{1}&s_{2}\end{pmatrix}\begin{pmatrix}0&-1\\-1&0\end{pmatrix}\begin{pmatrix}s_{1}\\s_{2}\end{pmatrix}=\begin{pmatrix}-s_{2} & -s_{1}\end{pmatrix}\begin{pmatrix}s_{1}\\s_{2}\end{pmatrix}$

$s^{T}\nabla _{xx}^{2}L\left( x^{\ast },\lambda ^{\ast }\right)s=-2s_{1}s_{2}=-2s_{1}\left( -\dfrac{2}{3}s_{1}\right) =\dfrac{4}{3}s_{1}^{2}$

é claro que, se $s\neq 0,$ $s^{T}\nabla _{xx}^{2}L\left( x^{\ast },\lambda ^{\ast }\right)s>0$ e a condição (ii) é também verificada.

Assim, $\left( x^{\ast },y^{\ast}\right) =\left( 16,11\right)$ é mínimo de $f\left( x,y\right) .$

$\bigskip$

Referência: Lino Costa, Métodos Numéricos I, Licenciatura Informática de Gestão, Universidade do Minho, 2005/2006

ADENDA DE 26-5-2008: O leitor foreigner comentou ontem

(…) [1.] Neste caso basta exprimir y em função de x graças à restrição e procurar o máximo de um vulgar polinómio do segundo grau.

[2.] Este método tem ainda a vantagem de provar correctamente que o máximo existe, o que não é claro com o método de Lagrange (o conjunto definido pela restrição não é compacto). (…)

$\bigskip$

No meu comentário digo: [1.] No enunciado do exame referido era expressamente pedida a resolução da questão pelo método ~~dos multiplicadores de Lagrange~~ indicado [editado em 2-5-2009] — coisa que não disse no modo como a apresentei. (…) [2.] Quanto à existência do máximo, é uma óptima questão a que levanta (…)

$\bigskip$

Aproveito para apresentar a resolução indicada pelo leitor em [1.]

De $4x+6y=130$ , tira-se

$y=\dfrac{130-4x}{6}$ ,

o que substituindo em $g\left( x,y\right) =\left( x+2\right) \left( y+1\right)$

dá

$g\left( x,y\right)=g\left( x\right)=\left( x+2\right) \left( \dfrac{130-4x}{6}+1\right)=\dfrac{64}{3}x-\dfrac{2}{3}x^{2}+\dfrac{136}{3}$

donde

$g^{\prime }\left( x\right) =\dfrac{64}{3}-\dfrac{4}{3}x$

e $g^{\prime }\left( x\right) =0$ , para $x=16$ , sendo $g^{\prime }\left( x\right) >0$ , para $x<16$ e $g^{\prime }\left( x\right) <0$ , para $x>16$ , logo $g\left( 16\right)$ é máximo de $g(x) .$ Para $x=16$

$y=\dfrac{130-4x}{6}=\dfrac{130-4\times 16}{6}=11.$

Assim, em função das duas variáveis, $g\left( x,y\right)$ tem um máximo em $\left( x,y\right) =\left( 16,11\right) .$ Simples! $\blacktriangleleft$

Edição de 2 e 17-5-2009: alterado título do post e no caderno (ver meu comentário de 29-4-2009)

Gostar disto:

Be the first to like this artigo.

Comentários (11)

11 Comentários »

Uma aplicação espectacular do método dos coeficientes indeterminados de Lagrange é a determinação da distribuição com o máximo valor da entropia de Shannon, sujeita às restrições (em geral lineares) impostas pelas medidas realizadas (determinados momentos que são conhecidos). Por esta técnica se promove a inversão do problema da probabilidade, isto é, parte-se do conhecimento dos momentos para se identificar a distribuição de probabilidade em vez do contrário. O seu inventor, o Físico britânico Edward Jaynes, fundamentou a validade do método – divulgado como “da máxima entropia” – naquilo que designou por “grau de informação” associada à medida, consistindo esta na “incerteza eliminada pela experiência”. Qualquer outra distribuição que, mesmo sendo compatível com o conjunto de medidas conhecidas, não corresponda à que exibe o máximo valor de entropia exigiria, afirma Jaynes, uma informação (ou seja um conhecimento) não evidenciado pela experiência, pelo que deve ser rejeitada. Estas ideias estão apresentadas na sua obra “Probability, the Logic of Science”, publicada postumamente.

Comentário por António Ferrão — Maio 11, 2008 @ 6:53 pm | Responder
Neste caso basta exprimir y em função de x graças à restrição e procurar o máximo de um vulgar polinómio do segundo grau.

Este método tem ainda a vantagem de provar correctamente que o máximo existe, o que não é claro com o método de Lagrange (o conjunto definido pela restrição não é compacto).

Só se deve utilizar artilharia pesada quando de facto ela é necessária!

Um abraço e Parabéns pelo site.

Comentário por foreigner — Maio 25, 2008 @ 5:00 pm | Responder
Caro foreigner

No enunciado do exame referido era expressamente pedida a resolução da questão pelo método ~~dos multiplicadores de Lagrange~~ indicado [editado em 2-5-2009] — coisa que não disse no modo como a apresentei. Sei que a disciplina fornecia métodos algoritmicos, passe o pleonasmo, a alunos de informática. No exame não poderiam, por uma questão de tempo, chegar a soluções para funções que fossem de difícil diferenciação e só podiam usar uma simples máquina de calcular básica. Mas na vida destes profissionais, o espírito até será o oposto, digo eu: abordar, através do computador, expressões complexas, e envolvendo um maior número de variáveis.

Quanto à existência do máximo, é uma óptima questão a que levanta, mas tal não era discutido nesse curso, tanto quanto sei. Ainda bem que refere esta questão teórica, que já está fora dos meus conhecimentos. Penso voltar a este assunto posteriormente, quando me inteirar dele.

Obrigado!

PS. corrigi este meu comentário para ficar mais claro.

Comentário por Américo Tavares — Maio 25, 2008 @ 5:27 pm | Responder
Como port uma resolução é pto de mín e na outra é pto de máx?

Comentário por thiago — Setembro 1, 2008 @ 2:17 pm | Responder
Caro thiago,

O máximo da função $g$ é um mínimo da função $f$ , simétrica de $g$ em relação ao eixo dos $x$ , pelo que tem inteira razão.

Adicionalmente, e isto já não tem a ver com o seu comentário, digo que a função real $g(x)=(x+2)((130-4x)/6))$ da variável real $x$ tem como máximo $g(16)=216$ . No caso de $x,y$ estarem relacionadas pela condição $4x+6y=130$ , $g(x,y)=(x+2)(y+1)$ , função real mas das duas variáveis reais $x,y$ , tem como máximo $g(16,11)=216$ . Se não houvesse a restrição $4x+6y=130$ , $g(x,y)=(x+2)(y+1)$ não tinha sequer máximo em $\mathbb{R}^{2}$ .

Comentário por Américo Tavares — Setembro 1, 2008 @ 3:51 pm | Responder
Um método mais simples:

V(x, y, λ) = F(x, y) – λR(x, y)
F(x, y) = (x+2)(y+1)
R = 4x + 6y = 130
V = (x+2).(y+1) – λ(4x + 6y – 130)
Achando as derivadas parciais de x , y e λ, temos:
∂V/∂x = (y + 1) – 4λ = 0 = (y+1) = 4λ (1)
∂V/∂y = (x + 2) -6λ = 0 = (x +2) = 6λ (2)
∂V/∂λ = (-4x-6y +130) = 0 4x + 6y = 130 (3)
Dividindo (1)/(2), temos:
4x + 8 = 6y + 6
X = (6y-2)/4
Substituindo em (3), vem:
4( (3y-1)/2) + 6y = 130
6y – 2 + 6y = 130
Y = 11
Calculando x, vem
X = 4( (3y-1)/2), onde x = 16
Assim, (x*, y* ) = (16;11) é mínimo de F(x,y)

Comentário por Marlon George — Abril 7, 2009 @ 11:49 pm | Responder
- Caro Marlon George
  
  Embora com atraso respondo agora ao seu comentário.
  
  O método que expõe é realmente mais simples e corresponde a considerar apenas a condição (i).
  A condição (ii) permite garantir que o extremo é um mínimo, uma vez que tem em conta as derivadas parciais de 2ª ordem.
  
  Além disso a exposição do post é mais geral, aplicando-se a um número arbitrário de variáveis e restrições, embora seja um pouco mais complicada.
  
  Por outro lado o que método que usou é que é conhecido por método dos multiplicadores de Lagrange (ver Wikipedia/Wikipédia
  http://en.wikipedia.org/wiki/Lagrange_multipliers
  http://pt.wikipedia.org/wiki/Multiplicadores_de_Lagrange) e não o do post!
  
  Obrigado por ter comentado.
  
  PS. de 2-5-2009: alterei o título do post para o adequar melhor ao método usado e retirei deste comentário o link para a Wikipedia relativo a restrições do tipo desigualdade (no post são do tipo igualdade).
  
  Comentário por Américo Tavares — Abril 29, 2009 @ 5:12 pm
Pelo o que eu entendi dessa questão que o ponto máximo é de g(16,11) = 216, e o ponto mínimo f(16,11/), também é 216.

Pois tenho uma dúvida da qual o senhor pode se tirar nessa questão que irei apresentar:

Sejam M e m, respectivamente, os valores máximo e mínimo da função de produção f(x,y) = 2x^2 + 3y^2, sujeita a restrição orçamentária x + y = 10, com x> ou = 0 e y> ou = 0. A soma M e m é igual a:

a) 380
b)360
c) 400
d) 420
e) 500

Aguardo dia resposta.
P.S. Parabéns pelo site.

Comentário por Allyne — Novembro 27, 2009 @ 6:20 pm | Responder
- Talvez fosse lapso seu (falta do sinal menos):
  
  O valor do mínimo de $f\left( x,y\right)$ é $f\left( 16,11\right) =-\left( 16+2\right) \left( 11+1\right) =-216$ .
  
  Sugiro que utilize o método explicado por foreigner se tiver dúvidas em relação ao método geral indicado na nota teórica.
  
  Obrigado pela sua apreciação.
  
  Comentário por Américo Tavares — Novembro 27, 2009 @ 7:02 pm
Então, quer dizer que a soma de um ponto máximo e um ponto mínimo se anula?

Obrigada pela sua resposta.
Abraço

Comentário por Allyne — Novembro 29, 2009 @ 8:21 pm | Responder
- Sim, mas de funções simétricas. Note que as funções $f$ e $g$ são simétricas em relação ao plano $xy$ .
  
  Assim, o máximo da função $g$ ocorre no mesmo par $(x,y)$ onde a função $f$ tem o mínimo, porque, em geral
  $f(x,y)=-(x+2)(y+1)=-g(x,y)$ . Logo
  $f(16,11)=-(16+2)(11+1)=-216=-g(16,11)$ ,
  tendo-se assim $f(16,11)=-216$ como valor do mínimo de $f$ e
  $g(16,11)=216$ como valor do máximo de $g$ , quando ambas as funções estão sujeitas à mesma restrição $4x+6y=130$ .
  
  Abraço
  
  Comentário por Américo Tavares — Novembro 29, 2009 @ 9:15 pm

RSS feed para os comentários a este artigo. TrackBack URI

Deixar uma resposta Cancelar resposta

Escreva o seu comentário aqui...

Fill in your details below or click an icon to log in:

Email (obrigatório) (Address never made public)

Nome (obrigatório)

Website

You are commenting using your WordPress.com account. ( Log Out / Modificar )

You are commenting using your Twitter account. ( Log Out / Modificar )

You are commenting using your Facebook account. ( Log Out / Modificar )

Cancelar

Connecting to %s

	Victor Costa (@_viic… em Um integral real calculado pel…
	Américo Tavares em Resolução da equação do 3.º gr…
	deny em Resolução da equação do 3.º gr…
	Américo Tavares em Probabilidades com cartas
	MOISES CARDOSO CAMPO… em Probabilidades com cartas
	Américo Tavares em Equação quártica simétric…
	Almir Sotero em Equação quártica simétric…
	Américo Tavares em Os números da forma n^4 + 4 sã…

Problemas Teoremas

Maio 4, 2008