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

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}

e

\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}

e

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)

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)

Advertisements

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
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 etiquetas , , , . ligação permanente.

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

  1. 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.

  2. foreigner diz:

    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.

  3. 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.

  4. thiago diz:

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

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

  6. Marlon George diz:

    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)

    • 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).

  7. Allyne diz:

    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.

    • 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.

  8. Allyne diz:

    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

    • 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

Deixe uma Resposta

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

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s