Optimização « problemas

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)

	Eduardo Lazarini no Matemática, papel e caneta, e …
	mario dumbo hossi no Descobrir a Moeda Falsa
	Américo Tavares no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	anonimo no Dodecaedro e outros poliedros…
	Elias_Brasil no Probabilidades com cartas
	Pedro Cunha no Caderno
	Andrea no Matemática, papel e caneta, e …
	alessandro no Caderno

Category Archive

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

Nota teórica

Américo Tavares

Bem-vindo(a)!

Últimos Comentários e respostas

Arquivos

Últimos Artigos

Categorias (Temas)

Acompanhamento via RSS de Blogues com Matemática

… em português

A MATEMÁTICA ANDA POR AÍ

Disquisitiones Mathematicae

Geometria

morfismo

… não portugueses

Gaussianos

Gower’s Weblog

The Unapologetic Mathematician

Todd and Vishal’s blog

What’s new

Weblog de Pierre Bernard

Ligações (Links)

Matemática

Matemática/Computação

Matemática/Problemas

Matemática/Publicações, bibliotecas online

Meu blogue auxiliar

Outros: ciências, tecnologia e economia, etc.

N.º de Visualizações (início: Out. 2007)

Acompanhe este blogue via RSS

COMENTÁRIOS