(*) Extremos globales. Condiciones de Kuhn-Tucker.

8. (*) Extremos globales. Condiciones de Kuhn-Tucker.

Haremos aquí, una pequeño acercamiento a la programación no lineal. Sea $w$ una función posiblemente no lineal,

$∙$ Un problema de maximización en programación no lineal, tiene la siguiente forma:

“Maximizar $w = f (x_{1}, x_{2}, . . . x_{n})$ sujeto a $g_{i} (x_{1}, . . ., x_{n}) \leq c_{i}, i = 1, 2, . . ., m$ con $x_{j} \geq 0, j = 1, 2, . . ., n$ . ”

$∙$ Un problema de minimización en programación no lineal, tiene la siguiente forma:

“Minimizar $w = f (x_{1}, x_{2}, . . . x_{n})$ sujeto a $g_{i} (x_{1}, . . ., x_{n}) \geq c_{i}, i = 1, 2, . . ., m$ con $x_{j} \geq 0, j = 1, 2, . . ., n$ .”

Solución gráfica. Para obtener una solución gráfica de un problema de programación no lineal (o lineal) sencillo, usamos las mismas ideas que se discutieron en la sección de multiplicadores de Lagrange. Las restricciones $g_{i} \leq 0$ y las condiciones de no negatividad, determinan una región factible para encontrar una solución. Nos movemos luego, sobre esta región o hacia esta región, sobre las curvas de nivel de $w,$ en la dirección en la que $w$ crece o decrece, según sea el problema (maximización o minimización).

Una vez encontrada una solución, el problema de determinar si es un máximo (o mínimo) global depende de que se satisfagan ciertas condiciones.

Ejemplo134

Minimizar $w = {(x - 4)}^{2} + {(y - 4)}^{2},$ sujeto a las condiciones $2 x + 3 y \geq 6, y 3 x + 2 y \leq 12, x, y \geq 0 .$

Solución. : Aquí las restricciones son lineales. La región factible es la región sombreada en las figuras. La función $w$ es un paraboloide con vértice en $(4, 4, 0)$ . La dirección de decrecimiento es hacia el vértice (entre más me acerco al centro, más pequeño se hace $w$ ). El punto $P,$ donde $w$ alcanza el mínimo local, se encontraría en el “punto más profundo” de la región factible en la dirección de decrecimiento.

Para calcular este punto, observamos que la recta de contacto es

3 x + 2 y = 12 .

La curva de nivel de contacto es

{(x - 4)}^{2} + {(y - 4)}^{2} = k .

Así que tenemos que calcular los puntos

P,

sobre esta curva de nivel, donde la recta tangente es

3 x + 2 y = 12,

o más precisamente, los puntos

P = (a, b),

sobre esta curva de nivel, donde la pendiente de la recta tangente es

- 3 ∕ 2

La pendiente de la recta tangente a la curva de nivel ${(x - 4)}^{2} + {(y - 4)}^{2} = k,$ en $P$ es

$y^{'} (a, b) = - 3 ∕ 2 = - \frac{F_{x} (P)}{F_{y} (P)} = - \frac{a - 4}{b - 4}$

y, puesto que $P$ está también sobre la recta $3 x + 2 y = 12,$ entonces tendríamos que $3 a + 2 b = 12 .$

Resolvemos entonces el sistema: ${\begin{matrix} - \frac{a - 4}{b - 4} & = & - 3 ∕ 2 \end{matrix}$ $⟹ a = \frac{28}{13}, b = \frac{36}{13}$ .

Condiciones de Kuhn-Tucker.

Consideremos el problema

“Maximizar $w = f (x_{1}, x_{2}, . . . x_{n})$ sujeto a $g_{i} (x_{1}, . . ., x_{n}) \leq c_{i}, i = 1, 2, . . ., m$ con $x_{j} \geq 0, j = 1, 2, . . ., n$ .”

Entonces, consideremos la función lagrangiana

L = f (x_{1}, . . . x_{n}) + \sum_{i = 1}^{m} y_{i} [c_{i} - g_{i} (x_{1}, . . ., x_{n})]

Las

y_{i}

son los multiplicadores de Lagrange.

∙

Las condiciones de Kuhn-Tucker para un máximo son

$L_{x_{j}} \leq 0, x_{j} \geq 0, x_{j} L_{x_{j}} = 0, j = 1, 2, . . . n$

$L_{y_{j}} \geq 0, y_{i} \geq 0, y_{i} L_{y_{i}} = 0, i = 1, 2, . . ., m$

∙

Las condiciones de Kuhn-Tucker para un mínimo son

$L_{x_{j}} \geq 0, x_{j} \geq 0, x_{j} L_{x_{j}} = 0, j = 1, 2, . . . n$

$L_{y_{j}} \leq 0, y_{i} \geq 0, y_{i} L_{y_{i}} = 0, i = 1, 2, . . ., m$

Bajo ciertas hipótesis, las condiciones de Kuhn-Tucker, son condiciones necesarias y suficientes para determinar si en un punto

P

, la función objetivo

w

alcanza un máximo o mínimo global.

Teorema 20 — (Versión para restricciones lineales)..

Dado el problema no lineal

“Maximizar (o Minimizar) $w = f (x_{1}, x_{2}, . . . x_{n})$ sujeto a $g_{i} (x_{1}, . . ., x_{n}) \leq c_{i}, i = 1, 2, . . ., m$ con $x_{j} \geq 0, j = 1, 2, . . ., n$ ,”
si se satisfacen las siguientes condiciones:

a.): las $g_{i}$ son lineales (diferenciables y convexas) en el octante no negativo,
b.): $f$ es diferenciable y cóncava en el octante no negativo,
c.): el punto $P$ satisface las condiciones de Kuhn-Tucker

entonces en $P$ , la función objetivo $w$ alcanza un máximo (o mínimo) global.

Para verificar que un punto $P$ satisface las condiciones de Kuhn-Tucker, se desarrollan estas condiciones, i.e. , se calculan las derivadas parciales $L_{x_{j}}$ y las $L_{y_{i}}$ , luego las $L_{x_{j}}$ se evalúan en $P$ y se debe verificar que existen $y_{1}, y_{2}, . . ., y_{n}$ tal que se satisface todo el conjunto de condiciones.

Ejemplo135

Minimizar $w = {(x - 4)}^{2} + {(y - 4)}^{2},$ sujeto a las condiciones $2 x + 3 y \geq 6, - 3 x - 2 y \geq - 12, x, y \geq 0 .$

Solución. : Ya sabemos que $w$ podría alcanzar un a mínimo global en $P = (\frac{28}{13}, \frac{36}{13}) .$ Ahora verificamos si satisface las condiciones de Kuhn-Tucker, pues las condiciones a.) y b.) ya se cumplen.

Sea $L = {(x - 4)}^{2} + {(y - 4)}^{2} + y_{1} (6 - 2 x - 3 y) + y_{2} (- 12 + 3 x + 2 y) .$ Como es un problema de minimización, las condiciones son

1.: $L_{x} = 2 (x - 4) - 2 y_{1} + 3 y_{2} \geq 0$
2.: $L_{y} = 2 (y - 4) - 3 y_{1} + 2 y_{2} \geq 0$
3.: $L_{y_{1}} = 6 - 2 x - 3 y \leq 0$
4.: $L_{y_{2}} = - 12 + 3 x + 2 y \leq 0$
5.: $x L_{x} = 2 x (x - 4) - 2 x y_{1} + 3 x y_{2} = 0$
6.: $y L_{y} = 2 y (y - 4) - 3 y y_{1} + 2 y y_{2} = 0$
7.: $y_{1} L_{y_{1}} = 6 y_{1} - 2 x y_{1} - 3 y y_{1} = 0$
8.: $y_{2} L_{y_{2}} = - 12 y_{2} + 3 x y_{2} + 2 y y_{2} = 0$

Las condiciones de no negatividad, claramente se cumplen para el punto

P

. Ahora debemos evaluar estas ocho condiciones en nuestro punto

P

y verificar que existen

y_{1}, y_{2}

tales que las condiciones se cumplen.

Al sustituir en las condiciones 5. y 6. obtenemos que $L_{x} (P) = 0$ y que $L_{y} (P) = 0,$ de donde se obtiene

${\begin{matrix} - 2 y_{1} + 3 y_{2} & = & 48 ∕ 13 \end{matrix}$ $⟹ y_{1} = 0, y_{2} = \frac{16}{13},$

que son no negativas como se pedía. Con estos valores de las $y_{i}$ y $P$ , se cumplen todas las condiciones de Kuhn-Tucker. Por tanto en $P$ la función objetivo $w$ alcanza un mínimo global.