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

11. (*) 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.

Ejemplo142

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

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,

1: 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$ . ”
2: 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.

Ejemplo143

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)$ . Dado que el vértice $(4, 4)$ satisface $2 (4) + 3 (4) = 20 > 6$ y $3 (4) + 2 (4) = 20 > 12,$ queda fuera de la región factible, por encima de ambas restricciones. 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, y la restricción activa resulta ser $3 x + 2 y = 12 .$

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. Notemos que la lagrangiana se ha escrito de modo que cada término

c_{i} - g_{i} (x_{1}, \dots, x_{n})

es no negativo en la región factible (para el problema de maximización, donde

g_{i} \leq c_{i}

), lo cual es consistente con exigir

y_{i} \geq 0 .

∙

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$

Nota: Para el problema de minimización con restricciones

g_{i} \geq c_{i},

la condición

L_{y_{i}} = c_{i} - g_{i} \leq 0

expresa precisamente que

g_{i} \geq c_{i},

es decir, que el punto pertenece a la región factible. La condición de complementariedad

y_{i} L_{y_{i}} = 0

indica que si la restricción

i

-ésima no está activa (i.e.,

g_{i} > c_{i}

, slack estricto), entonces necesariamente

y_{i} = 0 .

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 22 — 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.

Ejemplo144

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

Solución. : Ya sabemos que $w$ podría alcanzar un mínimo global en $P = (\frac{28}{13}, \frac{36}{13}) .$

Para aplicar las condiciones de Kuhn-Tucker, reescribimos las restricciones en la forma $g_{i} \geq c_{i}$ requerida para un problema de minimización:

2 x + 3 y \geq 6 y - 3 x - 2 y \geq - 12 .

Verificamos a continuación si $P$ satisface las condiciones de Kuhn-Tucker; las condiciones a.) y b.) del teorema ya se cumplen pues las $g_{i}$ son lineales y $w$ es un paraboloide (convexa, y por tanto cóncava cambiando el signo; en este caso la versión de minimización aplica directamente).

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

x, y \geq 0

claramente se cumplen para el punto

P

. Verificamos las condiciones 3. y 4. evaluando en

P

L_{y_{1}} (P) = 6 - \frac{56}{13} - \frac{108}{13} = \frac{78 - 164}{13} = - \frac{86}{13} < 0 ✓

L_{y_{2}} (P) = - 12 + \frac{84}{13} + \frac{72}{13} = - 12 + \frac{156}{13} = 0 \leq 0 ✓

Observemos que $L_{y_{2}} (P) = 0$ indica que la restricción $3 x + 2 y \leq 12$ está activa en $P$ , mientras que $L_{y_{1}} (P) < 0$ indica que la primera restricción no está activa (tiene holgura estricta). Por la condición de complementariedad $y_{1} L_{y_{1}} = 0,$ esto obliga a $y_{1} = 0 .$

Ahora, de las condiciones 5. y 6., como $x, y > 0$ en $P$ , se requiere $L_{x} (P) = 0$ y $L_{y} (P) = 0,$ lo que conduce al sistema:

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

que son no negativas como se pedía. Con estos valores, verificamos que se cumplen todas las condiciones de Kuhn-Tucker. El siguiente cuadro resume el estado de cada restricción:


Restricción	Valor en $P$	Activa	Multiplicador

$2 x + 3 y \geq 6$	$\frac{56 + 108}{13} = \frac{164}{13} > 6$ (holgura)	No	$y_{1} = 0$


$3 x + 2 y \leq 12$	$\frac{84 + 72}{13} = \frac{156}{13} = 12$	Sí	$y_{2} = \frac{16}{13} > 0$

Por tanto, en

P = (\frac{28}{13}, \frac{36}{13})

la función objetivo

w

alcanza un mínimo global.

Ejercicios

Resuelva los siguientes ejercicios usando el método gráfico. Aplique, si se puede, las condiciones de Kuhn-Tucker.

11.1Maximizar

w = x^{2} + y^{2},

sujeto a las condiciones

2 x + 3 y \geq 6, - 3 x - 2 y \geq - 12, x, y \geq 0 .

La región factible es la misma del ejemplo anterior: está acotada y sus vértices son

(0, 2), (4, 0)

(12 ∕ 5, 6 ∕ 5) .

Evaluando

w

en cada vértice:

w (0, 2) = 4, w (\frac{12}{5}, \frac{6}{5}) = \frac{180}{25} = \frac{36}{5}, w (4, 0) = 16 .

El máximo es

w = 16

P = (4, 0) .

Las condiciones de Kuhn-Tucker no son aplicables para garantizar un máximo global: el teorema exige que

f

sea cóncava en el octante no negativo, pero

w = x^{2} + y^{2}

es convexa. En este caso el máximo se determina directamente comparando los valores en los vértices de la región factible (región poligonal acotada).

11.2Maximizar

z = 3 x + 2 y

, sujeta a las restricciones

- 3 x + 2 y \leq 6

- 4 x + 9 y \leq 36, x, y \geq 0

La región factible es no acotada. En la dirección del gradiente

\nabla z = (3, 2)

podemos tomar

y = 0

y hacer

x \to + \infty :

ambas restricciones se satisfacen pues

- 3 x \leq 6

- 4 x \leq 36

para todo

x \geq 0

. Luego

z = 3 x \to + \infty

y el problema no tiene solución óptima finita. Las condiciones de Kuhn-Tucker no son aplicables.

11.3Maximizar

z = 4 x + 3 y

, sujeta a las restricciones

2 x + 3 y \leq 18

4 x + 2 y \leq 10, x, y \geq 0

Los vértices de la región factible son:

(0, 0), (5 ∕ 2, 0)

(0, 5) .

(La intersección de las dos rectas da

x = - 3 ∕ 4 < 0,

fuera del octante no negativo.) Evaluando:

z (0, 0) = 0, z (\frac{5}{2}, 0) = 10, z (0, 5) = 15 .

El máximo es

z = 15

P = (0, 5) .

Las condiciones de Kuhn-Tucker sí son aplicables:

z

es lineal (cóncava) y las restricciones son lineales. La lagrangiana es

L = 4 x + 3 y + y_{1} (18 - 2 x - 3 y) + y_{2} (10 - 4 x - 2 y) .

En $P = (0, 5)$ : la restricción $4 x + 2 y \leq 10$ está activa ( $4 (0) + 2 (5) = 10$ ) y la primera no ( $2 (0) + 3 (5) = 15 < 18$ ), por lo que $y_{1} = 0 .$ De $L_{x} (P) = 4 - 2 y_{1} - 4 y_{2} = 0$ se obtiene $y_{2} = 1;$ de $L_{y} (P) = 3 - 3 y_{1} - 2 y_{2} = 1 \geq 0$ se verifica la condición. Todas las condiciones de Kuhn-Tucker se satisfacen con $y_{1} = 0, y_{2} = 1,$ confirmando el máximo global en $P$ .

11.4Minimizar

z = {(x - 1)}^{2} + {(y - 2)}^{2}

, sujeta a las restricciones

- 3 x + 2 y \leq 6

- 4 x + 9 y \leq 36, x, y \geq 0

El punto

(1, 2)

satisface todas las restricciones:

- 3 (1) + 2 (2) = 1 \leq 6, - 4 (1) + 9 (2) = 14 \leq 36, x, y \geq 0 .

Es un punto interior de la región factible, y en él se tiene

z = 0,

que es el valor mínimo absoluto de

z

. Por tanto, el mínimo global es

z = 0

P = (1, 2) .

En un punto interior con

z_{min} = 0,

todas las restricciones tienen holgura estricta, de modo que los multiplicadores son

y_{1} = y_{2} = 0

y las condiciones de Kuhn-Tucker se reducen a

\nabla z (P) = 0,

que se cumple pues

P

es el vértice del paraboloide.

11.5Minimizar

z = 3 x^{2} + {(y - 1)}^{2}

, sujeta a las restricciones

- 3 x - y \leq 6

- 4 x + y \leq 6, x, y \geq 0

El punto

(0, 1)

satisface todas las restricciones:

- 3 (0) - 1 = - 1 \leq 6, - 4 (0) + 1 = 1 \leq 6, x, y \geq 0 .

Es un punto interior y

z (0, 1) = 0

es el mínimo absoluto de

z

. El mínimo global es

z = 0

P = (0, 1) .

Análogamente al ejercicio anterior, todas las restricciones tienen holgura en

P

, los multiplicadores son

y_{1} = y_{2} = 0,

y las condiciones de Kuhn-Tucker se reducen a

\nabla z (P) = 0,

que se cumple pues

P

es el mínimo del paraboloide.

11.6Minimizar

z = - x^{4}

, sujeta a las restricciones

x \leq 6

x \geq - 2

La región factible es el intervalo

[- 2, 6] .

Como

z = - x^{4}

es decreciente en

| x |

, el mínimo se alcanza donde

| x |

es máximo, es decir en

x = 6 :

z (6) = - 6^{4} = - 1296 .

Las condiciones de Kuhn-Tucker no son aplicables para garantizar un mínimo global:

z = - x^{4}

es cóncava (no convexa), por lo que el teorema no se puede invocar. El mínimo se determina directamente evaluando los extremos del intervalo:

z (- 2) = - 16

z (6) = - 1296,

concluyendo que el mínimo global es

z = - 1296

x = 6