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

Posted on Maio 4, 2008 por Américo Tavares

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)

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer

Ver todos os posts de Américo Tavares →

Esta entrada foi publicada em Análise Matemática, Caderno, Cálculo, Exercícios Matemáticos, Matemática, Optimização, Problemas, Teorema / Teoria com as tags Caderno, Matemática, Optimização, Problema. ligação permanente.

11 respostas a Optimização por método generalizando o de Lagrange

António Ferrão diz:

Maio 11, 2008 às 6:53 pm

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.

Responder
foreigner diz:

Maio 25, 2008 às 5:00 pm

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.

Responder
Américo Tavares diz:

Maio 25, 2008 às 5:27 pm

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.

Responder
thiago diz:

Setembro 1, 2008 às 2:17 pm

Como port uma resolução é pto de mín e na outra é pto de máx?

Responder
Américo Tavares diz:

Setembro 1, 2008 às 3:51 pm

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}$ .

Responder
Marlon George diz:

Abril 7, 2009 às 11:49 pm

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)

Responder
- Américo Tavares diz:
  
  Abril 29, 2009 às 5:12 pm
  
  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).
Allyne diz:

Novembro 27, 2009 às 6:20 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.

Responder
- Américo Tavares diz:
  
  Novembro 27, 2009 às 7:02 pm
  
  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.
Allyne diz:

Novembro 29, 2009 às 8:21 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

Responder
- Américo Tavares diz:
  
  Novembro 29, 2009 às 9:15 pm
  
  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

Deixar uma resposta Cancelar resposta

Escreva o seu comentário aqui...

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Email (obrigatório) (O endereço nunca será tornado público)

Nome (obrigatório)

Website

Está a comentar usando a sua conta WordPress.com ( Log Out / Modificar )

Está a comentar usando a sua conta Twitter ( Log Out / Modificar )

Está a comentar usando a sua conta Facebook ( Log Out / Modificar )

Cancelar

Connecting to %s

	Aline em Problema simples resolvido sob…
	Américo Tavares em Método de eliminação de Gauss…
	Marcos Silva em Método de eliminação de Gauss…
	Lucas em Derivadas: a total de uma funç…
	Jaime Varela em B. Demidovitch — Problem…
	Américo Tavares em Substituição de Euler para pri…
	Jorge ernesto sandra… em Substituição de Euler para pri…
	Sebastião Vieira do… em Exercício de aplicação dos teo…