Optimizacin

Condiciones de Karush-Kuhn-Tucker
Dr. E Uresti

ITESM

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 1/30

 Historia

Las condiciones necesarias que deben satisfacer Historia

Formulacion
los ptimos de problemas de optimizacin no lineal Uso
Ejemplo 1
con restricciones de desigualdad fueron Ejemplo 2
publicadas por primera vez (1939) en la tesis de Ejemplo 3
Ejercicios
Maestra de William Karush (1917-1997) (en aqul
entonces estudiante de matemticas de la
Universidad de Chicago) , aunque fueron
renombradas tras un artculo en una conferencia
de Harold W. Kuhn y Albert W. Tucker en 1951.
Las condiciones de Karush-Kuhn-Tucker (KKT)
son una generalizacin del mtodo de los
multiplicadores de Lagrange para restricciones de
desigualdad.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 2/30

 Formulacin

Considere el problema de optimizacin Historia

Formulacion
Uso
Min f (x1 , x2 , . . . , xn ) Ejemplo 1
Ejemplo 2
sujeto a Ejemplo 3
Ejercicios
g1 (x1 , x2 , . . . , xn ) 0
g2 (x1 , x2 , . . . , xn ) 0
.. (0.1)
.
gm (x1 , x2 , . . . , xn ) 0

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 3/30

 El mtodo de solucin procede de la siguiente Historia
Formulacion
manera. Cambiemos cada restriccin de Uso
Ejemplo 1
desigualdad gi 0 a una restriccin de igualdad Ejemplo 2
introduciendo una variable si de la siguiente Ejemplo 3
Ejercicios
manera:
gi 0 gi + s2i = 0
De acuerdo a la tcnica de los multiplicadores de
Lagrange se construye la funcin:
m
X
F (x, , s) = f (x) + i (gi + s2i )
i=1

Los puntos que minimizan a f sujeta a las

restricciones gi 0 (1 i m) estn dentro de los
puntos crticos de F :

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 4/30

 Que hacen cero las parciales con respecto a las variables xj
(j = 1, . . . , n):
m
F f X gi
= + i =0
xj xj i=1
xj
Que hacen cero las parciales con respecto a las variables i
(i = 1, . . . , m):
F
= gi + s2i = 0 gi 0
i
Que hacen cero las parciales con respecto a las variables si
(i = 1, . . . , m):
F
= 2 i si = 0 i si = 0 i g i = 0
si

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 5/30

 Teorema Historia
Formulacion
Suponga una formulacin para el problema anterior de Uso
Ejemplo 1
minimizacin. Si x0 = (a1 , a2 , . . . , an ) es un ptimo, Ejemplo 2
entonces deben existir nmeros reales llamados Ejemplo 3
Ejercicios
multiplicadores 1 , 2 ,. . . ,m no negativos tales que
(a1 , a2 , . . . , an , 1 , . . . , m ) es un punto crtico para F . Es
decir que se cumple:

Bloque I
(xo ) Pm gi (xo )
+ fx j
+ i=1 i xj
= 0 j = 1, 2 . . . , n
Bloque II: Condicin de Holgura Complementaria
(0.2)
i gi (xo ) = 0 i = 1, 2, . . . , m
Bloque III
gi 0 i = 1, 2, . . . , m

Observe que los valores de si se obtienen de la relacin

gi + s2i = 0 y de que gi 0.
Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 6/30
 Si ahora el problema es de maximizacin: Historia
Formulacion
Uso
Max f (x1 , x2 , . . . , xn )
Ejemplo 1
Ejemplo 2
sujeto a Ejemplo 3
Ejercicios
g1 (x1 , x2 , . . . , xn ) 0
g2 (x1 , x2 , . . . , xn ) 0
.. (0.3)
.
gm (x1 , x2 , . . . , xn ) 0
Para su solucin lo cambiamos a un problema de minimizacin
para f (x). En este caso la funcin F queda en la forma:

X
m
F (x, , s) = f (x) + i (gi + s2i )
i=1

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 7/30

 Teorema Historia
Formulacion
Suponga una formulacin para el problema anterior en el Uso
Ejemplo 1
caso de maximizacin. Si x0 = (a1 , a2 , . . . , an ) es un Ejemplo 2
ptimo, entonces deben existir nmeros reales llamados Ejemplo 3
Ejercicios
multiplicadores 1 , 2 ,. . . ,m no negativos tales que
(a1 , a2 , . . . , an , 1 , . . . , m ) es un punto crtico para F . Es
decir, que se cumple:

Bloque I
(xo ) Pm gi (xo )
fx j
+ i=1 i xj
= 0 j = 1, 2 . . . , n

Bloque II (0.4)
i gi (xo ) = 0 i = 1, 2, . . . , m
Bloque III
gi 0 i = 1, 2, . . . , m

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 8/30

 Uso de las Condiciones KKT

La forma de operar las condiciones de KKT ser la siguiente: Como Historia

Formulacion
lo que buscamos es el punto xo y de inicio se desconoce, entonces Uso
las ecuaciones de las condiciones de los bloques I y II se piensan Ejemplo 1
Ejemplo 2
como un sistema de ecuaciones en las variables xj s y j s: Se Ejemplo 3
Ejercicios
intenta resolver tal sistema de ecuaciones y en caso de encontrarse
las soluciones se revisan una a una para ver cual de ella cumple
que los j s son no negativos y que tambin se cumplen las
restricciones gi 0 en los puntos encontrados. Normalmente se
realiza una tabla donde se hace la verificacin.
Observe tambin es posible trabajar el problema de maximizacin
resolviendo el problema de minimizacin pero conservando
aquellos puntos que tengan los valores de los multiplicadores no
positivos.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 9/30

 Ejemplo 1

Encuentre los valores mnimo y mximo de la Historia

Formulacion
funcin f (x1 , x2 ) = 3 x1 x2 sujeta a las Uso
Ejemplo 1
restricciones 0 x1 , 0 x2 y 2 x1 + x2 2. Ejemplo 2
Ejemplo 3
Ejercicios

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 10/30

 Ejemplo 1

Encuentre los valores mnimo y mximo de la Historia

Formulacion
funcin f (x1 , x2 ) = 3 x1 x2 sujeta a las Uso
Ejemplo 1
restricciones 0 x1 , 0 x2 y 2 x1 + x2 2. Ejemplo 2
Solucion Ejemplo 3
Ejercicios
Primero cambiemos las restricciones a la forma
gi 0:
0 x1 g1 = x1 0
0 x2 g2 = x2 0
x1 + x2 2 g 3 = 2 x1 + x2 2 0

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 10/30

 Resolvamos el problema de minimizacin primeramente. En este caso las
condiciones son:

Bloque I
f (xo ) Pm gi (xo )
x1
+ i=1 i x1
= 1 + 2 1 2 =0

f (xo ) Pm gi (xo )
x2
+ i=1 i x1
= 1 + 1 3 =0
Bloque II: Condicin de Holgura Complementaria
1 g1 = 1 (2 x1 + x2 2) =0
2 g2 = 2 x1 =0
3 g3 = 3 x2 =0

x1 x2 1 2 3 g1 g2 g3 f
0 0 0 -1 -1 -2 0 0 3
1 0 1/2 0 -1/2 0 -1 0 2
0 2 1 1 0 0 0 -2 1

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 11/30

 Para determinar el mximo las condiciones quedan:

Bloque I
(xo ) Pm gi (xo )
fx + i=1 ix1
= 1 + 2 1 2 =0
Pm
1
(xo ) gi (xo )
fx 2
+ i=1 i x1
= 1 + 1 3 =0
Bloque II: Condicin de Holgura Complementaria
1 g1 = 1 (2 x1 + x2 2) =0
2 g2 = 2 x1 =0
3 g3 = 3 x2 =0

x1 x2 1 2 3 g1 g2 g3 f
0 0 0 1 1 -2 0 0 3
1 0 -1/2 0 1/2 0 -1 0 2
0 2 -1 -1 0 0 0 -2 1

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 12/30

 Observamos que las tablas para minimizacin y para maximizacin Historia
Formulacion
son idnticas salvo que los valores de los multiplicadores estn Uso
cambiados de signo. Por tanto, la estrategia conveniente para Ejemplo 1
Ejemplo 2
optimizar una funcin sujeta a restricciones de desigualdad por el Ejemplo 3
mtodo de las condiciones de KKT ser: Ejercicios
1. Plantear el problema como si se tratara solo de minimizacion y
resolver el sistema de ecuaciones correspondientes.
2. Eliminar aquellos puntos encontrados que no satisfacen las
restricciones gi 0.
3. Eliminar aquellos puntos que tienen a la vez multiplicadores
positivos y negativos.
4. Para minimizacin: escoger dentro de aquellos puntos que
tienen multiplicadores no negativos aqul que tienen la menor
evaluacin de la funcin objetivo.
5. Para maximizacin: escoger dentro de aquellos puntos que
tienen multiplicadores no positivos aqul que tienen la mayor
evaluacin de la funcin objetivo.
Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 13/30
 Ejemplo 2

Encuentre los mximos y mnimos absolutos de la Historia

Formulacion
funcin: Uso

f (x, y) = x2 + y 2 + y 1 Ejemplo 1
Ejemplo 2
Ejemplo 3
En la regin S definida por Ejercicios

2 2 2

S = (x, y) R |x + y 1

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 14/30

 Solucion
Utilizaremos las condiciones KKT para caracterizar los mximos y los mnimos.
Aqu g = g(x, y) = x2 + y 2 1 0. En la figura 1 aparecen los preparativos para la
solucin del problema, as como sus puntos crticos. El orden de las variables en la
matriz es x y t.

Figura 1: Preparativos y puntos crticos del ejemplo 2

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 15/30

 x y t g f
0 -1/2 0 -3/4 -5/4
0 -1 -1/2 0 -1
0 1 -3/2 0 1

Figura 2: Sustitucin de los puntos crticos en [x, y, t, g, f ]

Por lo tanto, f (x = 0, y = 1/2) = 5/4 es el mnimo de la funcin y

f (x = 0, y = 1) = 1 es el valor mximo.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 16/30

 Ejemplo 3
Un comerciante puede comprar hasta 17.25 onzas de un producto
qumico A a 10 dlares cada onza. Se puede convertir una onza del Historia
producto qumico A en una onza del producto I a un costo de 3 Formulacion
Uso
dlares a onza. Asimismo, una onza del qumico A se puede Ejemplo 1
convertir en una onza del producto II a un costo de 5 dlares la Ejemplo 2
Ejemplo 3
onza. Si se producen x1 onzas del producto I se vender a 30 x1 Ejercicios
dlares la onza, mientras que si se producen x2 onzas del producto
II se vender a 50 x2 dlares la onza. Determine cmo el
comerciante puede maximizar sus ganancias.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 17/30

 Ejemplo 3
Un comerciante puede comprar hasta 17.25 onzas de un producto
qumico A a 10 dlares cada onza. Se puede convertir una onza del Historia
producto qumico A en una onza del producto I a un costo de 3 Formulacion
Uso
dlares a onza. Asimismo, una onza del qumico A se puede Ejemplo 1
convertir en una onza del producto II a un costo de 5 dlares la Ejemplo 2
Ejemplo 3
onza. Si se producen x1 onzas del producto I se vender a 30 x1 Ejercicios
dlares la onza, mientras que si se producen x2 onzas del producto
II se vender a 50 x2 dlares la onza. Determine cmo el
comerciante puede maximizar sus ganancias.
Variables de Decision
x1 = Onzas del producto I producidas
x2 = Onzas del producto II producidas
Objetivo

Max z = x1 (30 x1 ) + x2 (50 x2 ) 3 x1 5 x2 10 (x1 + x2 )

Restricciones
x1 + x2 17.25, 0 x1 , 0 x2

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 17/30

 As:

f = x1 (30 x1 ) + x2 (50 x2 ) 3 x1 5 x2 10 (x1 + x2 ) Historia

Formulacion
g1 = x1 + x2 17.25 0 Uso
Ejemplo 1
g2 = x1 0 Ejemplo 2
Ejemplo 3
g3 = x2 0 Ejercicios

Las condiciones de KKT que debe satisfacer el ptimo son

(Observe que se uso el criterio para maximizar con f ; por tanto,
los multiplicadores no deben ser negativos):

Bloque I
f P3 gi
x + i=1 i x1
= 17 + 2 x1 + 1 2 = 0
P3
1
f gi
x 2
+ i=1 i x1
= 35 + 4 x2 + 1 3 = 0
Bloque II
1 (g1 ) = 1 (x1 + x2 17.25) = 0
2 (g2 ) = 2 x1 = 0
3 (g3 ) = 3 x2 = 0

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 18/30

 Resolviendo el sistema anterior con Maple obtenemos los siguientes puntos. En la
tabla se tabula cada una de las restricciones evaluada en el punto correspondiente.
Recuerde que las s deben ser no negativas y las restricciones deben cumplirse
(gi 0):

x1 x2 1 2 3 g1 (x) g2 (x) g2 (x) f (x)

0 0 0 -17. -35. -17.25 0 0 0
8.50 0 0 0 -35. -8.75 -8.50 0 72.25
17.25 0 -17.5 0 -52.5 0 -17.25 0 -4.3125
0 17.5 0 -17. 0 .25 0 -17.5 306.25
8.50 17.5 0 0 0 8.75 -8.50 -17.5 378.5
0 17.25 .500 -16.5 0 0 0 -17.25 306.1875
4.125 13.125 8.75 0 0 0 -4.125 -13.125 340.21875
Por consiguiente, el nico punto sobrevieviente es el del rengln 7: x1 = 4.125 y
x2 = 13.125 con una evaluacin de 340.21875.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 19/30

 Nota Historia
Si se utiliza LINGO para resolver el problema codificndolo como Formulacion
Uso
Ejemplo 1
Ejemplo 2
MAX=x1*(30-x1)+x2*(50-x2)-3*x1-5*x2-10*(x1+x2);
Ejemplo 3
x1+x2<=17.25; Ejercicios

se obtiene:
Local optimal solution found.
Objective value: 340.2188
Variable Value Reduced Cost
X1 4.12500 0.000000
X2 13.12500 0.0000000

Row Slack or Surplus Dual Price

1 340.2188 1.000000
2 0.0000000 -8.75000
Esto coincide con nuestro clculo.
Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 20/30
 Hagamos las operaciones utilizando la calculadora TI. En la figura 3 se muestran
las pantallas donde inician los preparativos: primeramente se limpian las variables
que sern usadas: x1, x2, t1 (en lugar de 1 ), t2 (en lugar de 2 ), y t3 (en lugar de
3 ). Es conveniente manejar las restricciones en la forma gi 0. Las variables g1,
g2 y g3 codificarn los lados izquierdos de las restricciones. Las ecuaciones del
bloque I se definirn utilizando variables e1 y e2 que representan los lados
izquierdos de ellas. As

f P3 gi
e1 = x1
i=1 ti x1
f P3 gi
e2 = x2
i=1 ti x2

Figura 3: Preparativos en la TI para el ejemplo 3

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 21/30
 En la figura 4 se muestran las ecuaciones del bloque II y la solucin del sistema
para los puntos crticos as como su conversin a matriz.

Sistema
e1 = 0
e3 = t1 g1 e2 = 0
e4 = t2 g2 e3 = 0
e5 = t3 g3 e4 = 0
e5 = 0
Para x1, x2, t1, t2, t3

Condiciones de Karush-Kuhn-Tucker
Figura Profr. E.del
4: Formacin del sistema para los puntos crticos Uresti - p. 22/30
ejemplo 3
 En la figura 5 se muestran las races del sistema que define los puntos crticos.
Observe que estas 7 races coinciden con los resultados de Maple. Recuerde que
en la primer columna aparece el valor de x1, en la segunda el de x2, en la tercera
el de t1, en la cuarta el de t2 y en la quinta el de t3. Como los valores de ti
esperados deben ser positivos esto descarta todos excepto los correspondientes a
los renglones 1 y 3: P (x1 = 4.125, x2 = 13.125, t1 = 8.75, t2 = 0, t3 = 0) y
Q(x1 = 8.5, x2 = 17.5, t1 = 0, t2 = 0, t3 = 0)

Figura 5: Puntos crticos del ejemplo 3

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 23/30

 Recuerde que algunos de estos puntos crticos pueden no cumplir las restricciones
y deben pasarse por la verificacin. En la figura 6 se muestran los vectores
[g1, g2, g3] resultantes de sustituir en las restricciones los puntos. Recuerde que las
restricciones son del tipo gi 0. Obervamos que el punto Q se descarta pues
g1(Q) = 8.75 > 0 y que el punto P las cumple. Por tanto, el nico punto mximo de
f sujeto a las restricciones es P (x1 = 4.125, x2 = 13.125, t1 = 8.75, t2 = 0, t3 = 0)
y que tiene una evaluacin de 340.219 

Figura 6: Verificacin de restricciones para el ejemplo 3

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 24/30

 Ejercicios

Los siguientes sern los ejercicios de tarea para Historia

Formulacion
este tema. Uso
Ejemplo 1
Ejemplo 2
Ejemplo 3
Ejercicios

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 25/30

 Ejercicio 1 Historia
Formulacion
Utilizando las condiciones de KKT resuelva el Uso
problema: Ejemplo 1
Ejemplo 2
Max z = x1 x2 Ejemplo 3
Ejercicios
sujeto a la condicin:
g1 (x1 , x2 ) = x1 2 + x2 2 1 0
Indique en orden los valores de x1 , x2 y de z.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 26/30

 Ejercicio 2 Historia
Formulacion
Utilice las condiciones de KKT para encontrar la Uso
solucin ptima del siguiente problema: Ejemplo 1
Ejemplo 2
Ejemplo 3
Min z = (x1 3)2 + (x2 5)2 Ejercicios

sujeto a:
g(x1 , x2 ) = x1 + x2 7 0
x1 0
x2 0
Indique en orden los valores de x1 , x2 y de z.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 27/30

 Ejercicio 3 Historia
Formulacion
Utilice las condiciones de KKT para encontrar la Uso
solucin ptima del siguiente problema: Ejemplo 1
Ejemplo 2
Ejemplo 3
Max z = (x1 1)2 + (x2 2)2 Ejercicios

sujeto a:
g1 (x1 , x2 ) = x1 + x2 1 = 0
g2 (x1 , x2 ) = x1 + x2 2 0
x1 0
x2 0
Indique en orden los valores de x1 , x2 y de z.
Sugerencia: Codifique la restriccin g1 = 0 mediante
las dos restricciones g1 0 y g1 0 (g1 0).

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 28/30

 Ejercicio 4 Historia
Formulacion
Una compaa de energa elctrica enfrenta demandas de energa Uso
durante los tiempos de carga mxima y no mxima. Si cobra un Ejemplo 1
Ejemplo 2
precio de p1 dlares el kilowatt-hora durante el tiempo de carga Ejemplo 3
mxima, entonces los clientes pedirn 60 0.5 p1 kwh de energa. Ejercicios

Si se cobra un precio de p2 dlares el kilowatt-hora, entonces los

clientes pedirn 40 p2 kwh. La compaa tiene que tener la
suficiente capacidad para satisfacer la demanda durante los dos
tiempos. A la compaa le cuesta 10 dlares al da mantener cada
kilowatt-hora de capacidad. Determine cmo la compaa puede
maximizar los ingresos diarios menos los costos de operacin.
Indique
la capacidad de la compaa en kwh,

el precio en dlares durante el tiempo de demanda mxima, y

el precio en dlares fuera de demanda mxima.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 29/30

 Ejercicio 5 Historia
Formulacion
Se disponen semanalmente de un total de 160 Uso
horas de mano de obra a 15 dlares la hora. Se Ejemplo 1
Ejemplo 2
puede conseguir mano de obra adicional a 25 Ejemplo 3
Ejercicios
dlares la hora. Se puede obtener capital en
cantidades ilimitadas a un costo de 5 dlares la
unidad de capital. Si se disponen de K unidades
de capital y de L horas de mano de obra, entonces
se pueden producir L1/2 K 1/3 mquinas. Se vende
cada mquina a 270 dlares. Cmo puede la
empresa maximizar sus ganancias? Indique
el total de horas de mano de obra a utilizar,

el total de unidades de capital, y

el total de mquinas a producir.

Condiciones de Karush-Kuhn-Tucker Profr. E. Uresti - p. 30/30