View
2.093
Download
1
Category
Preview:
Citation preview
OPTIMIZACIÓN
“CONDICIONES DE
KKT”
INTEGRANTES: HUGO GUZMAN TELLO
RODRIGO GUZMAN TELLO
INTRODUCCIÓN
La optimización, es considerada como la búsqueda
de la solución optima de problemas.
Se puede considerar como optimización de
condiciones de minimización de costos, horas de
ocio o maximización de beneficios, etc.
INTRODUCCIÓN
Cuando se trata un problema de
optimización, considera algunas etapas
propias, para obtener la o las soluciones
optimas, las cuales son:
Determinar el modelo matemático del problema a
resolver.
Resolver el problema utilizando técnicas
matemáticas.
El objetivo de la optimización matemática es
encontrar soluciones máximas o mínimas sujetas a
ciertas restricciones.
ANTECEDENTES HISTÓRICOS.
Albert William Tucker (28 de Noviembre
de 1905 – 25 de Enero de 1995) fue un
matemático estadounidense nacido en
Canadá que realizó importantes
contribuciones a la topología, teoría de
juegos y a la programación no lineal
Nació en Ontario, Canadá, y se graduó en
la Universidad de Toronto en 1928. En
1932, completó su doctorado en la
Universidad de Princeton bajo la
supervisión de Solomon Lefschetz
ANTECEDENTES HISTÓRICOS.
Harold William Kuhn (nacido en 1925) es
un matemático estadounidense que estudió
la teoría de juegos. Él ganó en 1980 el John
von Neumann Theory Prize junto con David
Gale y Albert W. Tucker. Fue un profesor
emérito de matemáticas en la Universidad
de Princeton, es conocido por las
“Condiciones Karush-Kuhn-Tucker”
ANTECEDENTES HISTÓRICOS.
Harold William Kuhn Él es conocido por su
asociación con John Forbes Nash, como
estudiante graduado compañero, un amigo
de toda la vida y colega, y una figura clave
para lograr que Nash a la atención del
comité del premio Nobel que llevó a 1994
Premio de Nash Nobel de Economía
ANTECEDENTES HISTÓRICOS.
William Karush (1 marzo 1917 a 22
febrero 1997) fue un profesor emérito de la
Universidad Estatal de California en
Northridge y es un matemático conocido por
su contribución las “Condisiones de Karush-
Kuhn-Tucker”.
CONCEPTOS FUNDAMENTALES.
Dentro de los problemas de programación nolineal, aparece una solución a dichosproblemas, conocido como “Condiciones deKarush-Kuhn-Tucker” el cual aplica un teoremaconocido como:
El teorema de Karush-Kuhn-Tucker, desde unpunto de vista práctico, los problemasplanteados con restricciones de desigualdadespueden recibir un mejor ajuste a las situacionesreales existentes. Con esto puede razonarseque una restricción de igualdad significa agotarcompletamente dicho recurso.
CONCEPTOS FUNDAMENTALES.
Las condiciones de Karush-Kunh-Tucker (KKT), son una generalización del método de los multiplicadores de Lagrange para restricciones de desigualdad.
Formulación.
Considere el problema de optimización:
Min f(x1, x2, . . . , xn)
Sujeto a: g1(x1, x2, . . . , xn) ≤ 0
g2(x1, x2, . . . , xn) ≤ 0 (1)
gm(x1, x2, . . . , xn) ≤ 0
CONCEPTOS FUNDAMENTALES.
El método de solución procede de la
siguiente manera. Cambiemos cada
restricción de desigualdad gi ≤ 0 a una
restricción de igualdad introduciendo una
variable si de la siguiente manera:
gi ≤ 0 → gi + si2 = 0
De acuerdo a la técnica de los
multiplicadores de Lagrange se construye la
función:
F(x, , s) = f(x) + (gi + si2) (2)
CONCEPTOS FUNDAMENTALES.
Los puntos que minimizan a f sujeta a las
restricciones gi ≤ 0 (1 ≤ i ≤ m) están dentro de los
puntos críticos de F:
Que hacen cero las derivadas parciales con respecto
a las variables xj (j = 1, . . . , n):
= + = 0
Que hacen cero las parciales con respecto a las
variables i (i = 1,….., m):
= gi + si2 = 0 ↔ gi ≤ 0
CONCEPTOS FUNDAMENTALES.
Que hacen cero las parciales con respecto a las
variables si (i = 1, . . . ,m):
= 2 i si = 0 ↔ I si = 0 ↔ i gi = 0
Lo anterior se resume en el siguiente teorema que indica
las condiciones que deben satisfacer los puntos que
minimizan la función sujeta a las restricciones.
CONCEPTOS FUNDAMENTALES.
Teorema
Suponga una formulación para el problema anterior
de minimización. Si x0 = (a1, a2, . , an) es un
óptimo, entonces deben existir números reales
llamados multiplicadores 1, 2,.., m no negativos
tales que (a1, a2, . . . , an, 1, . . . , m) es un
punto crítico para F. Es decir que se cumple:
CONCEPTOS FUNDAMENTALES.
Bloque I
+ + = 0 j= 1,2,…,n
Bloque II
Condición de holgura complementaria
i gi (x0) = 0 i = 1,2,…..,m (3)
Bloque III
gi ≤ 0 i = 1,2,…..,m
La forma de operar las condiciones KKT será lasiguiente: Como lo que buscamos es el punto x0 y deinicio se desconoce, entonces las ecuaciones de lascondiciones de los bloques I y II se piensan como unsistema de ecuaciones en las variables xj
´s y j
´s: Se
intentan resolver tal sistema de ecuaciones y encaso de encontrarse las soluciones se revisan una auna para ver cúal de ella cumple que los j
´s son no
negativos y que también se cumplen lasrestricciones gi ≤ 0en los puntos encontrados.Normalmente se realiza una tabla donde se hace laverificación.
USO DE LAS CONDICIONES KKT
USO DE LAS CONDICIONES KKT
Posible trabajar el problema de maximización
resolviendo el problema de minimización pero
conservando aquellos puntos que tengan los
valores de los multiplicadores no positivos.
Observamos que las tablas para minimización y
para maximización son idénticas salvo que los
valores de los multiplicadores están cambiados de
signo. Por tanto, la estrategia conveniente para
optimizar una función sujeta a restricciones de
desigualdad por el método de las condiciones de
KKT será:
USO DE LAS CONDICIONES KKT
1. Plantear el problema como si se tratará sólo de
minimización 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.
USO DE LAS CONDICIONES KKT
4. Para minimización: escoger dentro de aquellos
puntos que tienen multiplicadores no negativos
aquél que tienen la menor evaluación de la función
objetivo.
5. Para maximización: escoger dentro de aquellos
puntos que tienen multiplicadores no positivos
aquél que tienen la mayor evaluación de la función
objetivo.
EJERCICIO
KKT
1-. Sea el siguiente problema de minimización:
EJERCICIO
a. Desarrolle las condiciones de Karush-Kuhn-Tucker(KKT) para el problema
b. Revise el cumplimiento de las condiciones KKT paralos siguientes puntos:
(0,0); (2, 0); (0,2)
c. Qué podemos concluir para cada uno de estospuntos?
d. Muestre las restricciones, el conjunto de solucionesfactibles y la función objetivo gráficamente.
e. Determine un candidato para ser solución óptimaanalizando el grafico. Verifique si este candidato cumplecon las condiciones de KKT.
f. De la solución optima y el valor de la función objetivoasociado.
EJERCICIO
Solución:
a. Primero se lleva el problema a la forma estandar:
Ahora calculamos los gradientes de f y gi
EJERCICIO
Ahora calculamos los gradientes de f y gi
Así, se tiene que las condiciones de KKT son las
siguientes:
1
0;
0
1;
1*2
*2;
*2
1*2;
4*2
4*2
33
2
1
2
2
1
1
2
1gg
x
xg
x
xg
x
xf
1
0*
0
1*
1*2
*2*
*2
1*2*
4*2
4*2
43
2
1
2
2
1
1
2
1
x
x
x
x
x
x
EJERCICIO
b punto (0,0):
0*
011*
011*
13
2
2
2
12
2
2
2
11
x
xx
xx
EJERCICIO
Entonces,
Pero notemos que son linealmente
dependientes, al igual que y por lo tanto
basta con:
0
1
0
2y
2
0
1
0
EJERCICIO
De donde
Como son menores que 0, no cumplen KKT.
punto (2,0):
EJERCICIO
Entonces,
De donde
Como <0 entonces no cumple KKT. punto (0,2):4
EJERCICIO
Entonces
De donde
Como <0 entonces no cumple KKT.3
EJERCICIO
c.
(0,0) es un punto en el extremo del poliedro factible
que no cumple KKT, como la región es
convexa, quiere decir que (0,0) no es óptimo del
problema. Se puede observar que moviéndose en
cualquier punto al interior de la región factible, la
funcion objetivo mejora.
(2,0) y (0,2) son puntos que no cumplen KKT, lo
que indica que tienen alguna característica
particular en este caso, esto sucede porque no se
encuentran dentro del poliedro factible.
EJERCICIO
e. El candidato para ser solución óptima se
encuentra entre la intersección de las restricciones
más cercanas al (4,4).
Utilizando entonces g1 y g2 (restricciones activas)
para obtener el punto (x1, x2)
correspondiente, llegamos a que el candidato a
óptimo es el (1,1).
¿Cumple KKT?
Entonces,
De donde
Ambos son positivos, entonces se cumple KKT.
EJERCICIO
f. la solución óptima es el valor encontrado en la
parte anterior, como se observa gráficamente, la
región es convexa, pues los puntos que conforman
la línea que une a cualquier par de puntos dentro
de la región pertenecen a ella.
Así como la región es convexa, también lo son las
restricciones asociadas y función objetivos
asociadas. Luego el punto óptimo es: (x1, x2) =
(1,1).
Y la función objetivo: f(1,1)=9+9=18
FIN
Recommended