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( \frac{69}{2}-18\right) \times \frac{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}=-\frac{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( -\frac{2}{3}s_{1}\right) =\frac{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)