Condiciones de Kuhn-Tucker

En programación matemática, las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son condiciones necesarias y suficientes para que la solución de un problema de programación matemática séa óptima. Es una generalización del método de los Multiplicadores de Lagrange.

Optimización con restricciones de desigualdad: las condiciones de kuhn-tucker

Muchos modelos en economía son, naturalmente, formulados, como problemas de optimización con restricciones de desigualdad.

Consideremos, por ejemplo, el problema de la elección del consumidor. No hay ninguna razón para insistir en que un consumidor pasa toda su riqueza, por lo que su problema de optimización se formula con restricciones de desigualdad:

_x max u (x) en p · x ≤ w y x ≥ 0.

En el carácter de la función y los valores de u p y w, podemos tener p x · w <dependiendo o p · x = w a una solución de este problema.

Un enfoque para la solución de este problema comienza por determinar cuál de estas dos condiciones se cumple en una solución.  En problemas más complejos, con más de una restricción, este enfoque no funciona bien.  Consideremos, por ejemplo, un consumidor que se enfrenta a dos limitaciones (tal vez tiempo y dinero).  Tres ejemplos se muestran en la figura siguiente, que debe convencer de que no podemos deducir de propiedades simples de u solo que de las limitaciones, en su caso, están satisfechos con la igualdad en una solución.

  Se considera un problema de la forma 

 Máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m, 

 Donde f y g j para j = 1, ..., m son funciones de n variables, x = (x 1, ..., x n), y c j para j 1, ..., m son constantes = . 

 Todos los problemas que hemos estudiado hasta ahora podrán ponerse en esta forma. 

 La igualdad de las limitaciones 

 Presentamos dos restricciones de desigualdad para cada restricción de igualdad.  Por ejemplo, el problema 

 máximo x f (x) en h (x) = 0 

 se puede escribir como 

 máximo x f (x) en h (x) ≤ 0 y - h (x) ≤ 0. 

 Restricciones de no negatividad 

 Para un problema con una restricción k x ≥ 0 dejamos g j (x) = - x k y c j = 0 para algún j. 

 Minimización de los problemas 

 Por un problema de minimización se multiplica la función objetivo por -1: 

 min x h (x) en g j (x) ≤ c j para j = 1 ,..., m 

 es el mismo que 

 máximo x f (x) en g j (x) ≤ c j para j = 1 ,..., m, 

 donde f (x) = - h (x). 

 Para empezar a pensar en cómo resolver el problema general, en primer lugar de un asunto con una única restricción (m = 1).  Podemos escribir un problema como 

 máximo x f (x) en g (x) ≤ c. 

 Hay dos posibilidades para la solución de este problema.  En las siguientes figuras, las curvas cerradas negro son los contornos de f, los valores del aumento de la función en la dirección indicada por las flechas azules.  La línea roja-pendiente hacia abajo es el conjunto de puntos x g satisface (x) = c, el conjunto de puntos x g satisface (x) se encuentran por debajo de c ≤ y el de la izquierda de la línea, y los que g satisface (x) ≥ c están por encima ya la derecha de la línea. 

En cada panel de la solución del problema es el punto x *.  En el panel izquierdo de la restricción se une a la solución: un cambio en los cambios de c la solución.  En el panel de la derecha, la restricción es holgura en la solución: pequeños cambios en la letra c no tienen efecto en la solución. 
 al igual que antes, definir la función de Lagrange L por 
 L (x) = f (x) - λ (g (x) - c). 
 Luego de nuestro análisis anterior de los problemas con restricciones de igualdad y sin restricciones. 

• si g (x *) = c (como en la mano izquierda) y la restricción satisface una condición de regularidad, a continuación L (x *) = 0 para todo lo que 
• si g (x *) <c (como en el panel de la derecha-mano), entonces f i (x *) = 0 para todo i. 

 Ahora, me dicen que en el primer caso (es decir, si g (x *) = c) tenemos λ ≥ 0.  Supongamos, por el contrario, que λ <0.  Entonces se sabe que una pequeña disminución en la c eleva el valor máximo de f.  Es decir, en movimiento * x dentro de la restricción aumenta el valor de f, lo que contradice el hecho de que x * es la solución del problema. 

 En el segundo caso, el valor de λ no entra en las condiciones, por lo que puede elegir cualquier valor para él.  Teniendo en cuenta la interpretación de λ, el establecimiento de λ = 0 tiene sentido.  Bajo este supuesto tenemos f i (x) = L 'i (x) para todo x, de modo que' i L (x *) = 0 para todo i. 

Así, en ambos casos tenemos "i L (x *) = 0 para todo i, λ ≥ 0, y g (x *) ≤ c.  En el primer caso tenemos g (x *) = c, y en el segundo caso λ = 0. 

 Podemos combinar los dos casos por escrito las condiciones que 

 L i '(x *) = 0 para j = 1, ..., n 

 λ ≥ 0, g (x *) ≤ c, y, o bien λ = 0 y g (x *) - c = 0. 

 Ahora, el producto de dos números es cero si y sólo si al menos uno de ellos es cero, por lo que alternativamente puede escribir estas condiciones, 

 L i '(x *) = 0 para j = 1, ..., n 

 λ ≥ 0, g (x *) ≤ c, y λ [g (x *) - c] = 0. 

 El argumento que han dado sugiere que si x * resuelve el problema y la restricción satisface una condición de regularidad, entonces x * debe cumplir estas condiciones. 

 Tenga en cuenta que las condiciones no se descarta la posibilidad de que tanto λ = 0 y g (x *) = c. 

 Las desigualdades λ ≥ 0 y g (x *) ≤ c se denominan condiciones de holgura complementaria, la mayoría en una de estas condiciones es floja (es decir, no una igualdad). 

 Por un problema con muchas limitaciones, a continuación, como antes se introduce un multiplicador para cada restricción y obtener la condiciones de Kuhn-Tucker, que se define de la siguiente manera. 

 Definición 

 Las condiciones de Kuhn-Tucker para el problema 

 máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m 

 se 

 L i '(x) 

 = 0 para i = 1 ,..., n 

 0 λ ≥ j, j g (x) y c ≤ λ j j [j g (x) - c j] 

 = 0 para j = 1, ..., m, 

 donde 

 L (x) = f (x) - Σ j = 1 λ m j (j g (x) - c j). 

 Estas condiciones se nombran en honor de Harold W. Kuhn, miembro emérito del Departamento de Matemáticas de Princeton, y Albert W. Tucker , quien formuló por primera vez y estudió las condiciones. 

 En las siguientes secciones discutir los resultados que especifican la relación precisa entre las soluciones de las condiciones de Kuhn-Tucker y las soluciones del problema.  El siguiente ejemplo ilustra la forma de las condiciones en un caso concreto. 

Ejemplo 

 Considere el problema 

 máximo x 1, x 2 [- (x 1 - 4) 2 - (x 2 - 4) 2] con sujeción a x 1 + x 2 ≤ 4 y x 1 + 3 x 2 ≤ 9, 

 se ilustra en la siguiente figura. 

 Hemos 

 L (x 1, x 2) = - (x 1 - 4) 2 - (x 2 - 4) 2 - λ 1 (x 1 + x 2 - 4) - λ 2 (x 1 + 3 x 2 - 9) . 

 Las condiciones de Kuhn-Tucker son 

 2 (x 1 - 4) - λ 1 - λ 2 

 = 

 0 

 -2 (X 2 - 4) - λ 1 - 2 3λ 

 = 

 0 

 x 1 + x 2 ≤ 4, λ 1 ≥ 0 y λ 1 (x 1 + x 2 - 4) 

 = 

 0 

 x 1 + 3 x 2 ≤ 9, λ 2 ≥ 0, y λ 2 (x 1 + 3 x 2 - 9) 

 = 

 0. 

por ultimo se explicara un breve resumen de los beneficios que trae la optimización a la toma de decisiones dentro de las organizaciones:

si bien para comenzar debemos saber que la optimización es el proceso de modificar un sistema para mejorar su eficiencia o también el uso de los recursos disponibles. una organización necesita de una buena optimizacion ya que se debe actualizar y mejoras a nivel productivo y de sus sistemas y así estar a la vanguardia tecnología y realizar los procesos de una forma eficiente y eficaz entre los procesos a optimizar en una organizacion estan:

• maximizar la tasa de producción
• minimizar el costo de operación
• maximizar la utilidad
• minimizar el desperdicio de información
• maximizar las ganancias

¿Porque se deben optimizar los procesos productivos de una organización?

La competitividad en los procesos organizacionales debe ser el objetivo principal a conseguir y para ello es necesario el control y la consideración de aspectos clave que nos permitan alcanzar una planificación ajustada a la producción. La producción ajustada nos debe permitir la utilización eficiente de los recursos reduciendo tiempos de preparación, minimizando errores, eliminando tiempos de espera logrando un flujo continuo en la línea, minimizando los transportes internos y evitando retrasos. Otro de los aspectos relevantes es la reducción de stock. Cabe destacar que la acumulación de inventarios supone un coste notable en la contabilidad de las empresas y conseguir aprovisionar lo que se va a manufacturar sin que ello suponga retrasos en la línea de producción es sin duda uno de los grandes retos.

El principal beneficio de un estudio de esta naturaleza es el incremento en eficiencia y la consecuente reducción en costos y/o aumento de las utilidades. Un beneficio indirecto, pero de gran trascendencia, es el mucho mejor entendimiento del sistema derivado del proceso de construcción del modelo de optimización.

Toma de decisiones organizacionales

En el proceso de toma de decisiones dentro de una empresa se pasa por distintas fases que suelen seguir un esquema similar a: recogida de información, fijación de objetivos, toma de la decisión, acción o ejecución de la decisión y, por último, retroalimentación o feedback, que nos permite controlar cómo están siendo los resultados que se están obteniendo con la acción ejecutada respecto a los objetivos fijados. dentro de la toma de decisiones surge la necesidad de optimizar estos procesos para así haber mejor entendimiento de la información y  tener como resultado un mejoramiento continuo en la organización. 

aplicación de la condiciones de kuhn-tucker

La toma de decisiones organizacionales, se fundamenta matemáticamente el teorema de suficiencia de kuhn-tucker los problemas de restricción de desigualdad pueden ajustarse mejor a situaciones reales, puede pensarse que una restricción de igualdad significa agotar completamente cierto recurso. dentro de la solución de los problemas están:

• diagnostico del problema 
• investigación u obtencion de informacion
• desarrollo de alternativas
• experimentación
• análisis de restricciones
• evaluación de alternativas
• formulación del plan
• ejecución y control
• fijación de objetivos
• objetivos que se contradicen 
• jerarquía de objetivos horizonte de planeacion

para obtener mas información y ejercicios revisar el link:

www.mty.itesm.mx/etie/deptos/m/ma00.../m130-16.pdf 

Matriz Jacobiana

Matriz Jacobiana

La matriz Jacobiana es una matriz formada por las derivadas parciales de

primer orden de una función. Una de las aplicaciones más interesantes de esta

matriz es la posibilidad de aproximar linealmente a la función en un punto. En

este sentido, el Jacobiano representa la derivada de una función multivariable.

Supongamos F: Rn → Rm es una función que va del espacio euclidiano n-

dimensional a otro espacio euclidiano m-dimensional. Esta función está

determinada por m funciones reales: y1(x1,..., xn),..., ym(x1,..., xn). Las

derivadas parciales de estas (si existen) pueden ser organizadas en una matriz

m por n, la matriz Jacobiana de F:

Matriz Jacobiana

Ejemplo 1. La matriz jacobiana de la función F : R³ → R³ definida como:

es:

No siempre la matriz jacobiana es cuadrada. Véase el siguiente ejemplo.

Ejemplo 2. Supóngase la función F : R³ → R⁴, cuyas componentes son:

Aplicando la definición de matriz jacobiana:

Determinante jacobiano

Si m = n, entonces F es una función que va de un espacio n-dimensional a otro. En este caso la matriz jacobiana es cuadrada y podemos calcular su determinante, conocido como el determinante jacobiano o simplemente jacobiano.

El determinante jacobiano en un punto dado nos da información importante sobre el comportamiento de F cerca de ese punto. Para empezar, una función F es invertible cerca de p si el determinante jacobiano en p es no nulo. Más aún, el valor absoluto del determinante en p nos da el factor con el cual F expande o contrae su volumen cerca de p.

Ejemplos

Ejemplo 1. El determinante jacobiano de la función F : R³ → R³ definida como:

es:

El teorema de la función inversa garantiza que la función es localmente invertible en todo el dominio excepto quizá donde x₁ = 0 ó x₂ = 0 (es decir, los valores para los que el determinante se hace cero). Si imaginamos un objeto pequeño centrado en el punto (1,1,1) y le aplicamos F, tendremos un objeto aproximadamente 40 veces más voluminoso que el original.

Ejemplo 2. Cambiando un poco la función anterior por ésta:

El determinante jacobiano quedará:

En este caso existen más valores que anulan al determinante. Por un lado , y por otro:

con k = 0,1,2...

El método jacobiano es simplemente un determinante que sirve para pasar o transformar de un sistema de coordenas a otro. Tambien se llama determinante funcional.

Por ejemplo para pasar de un sistema rectangular a polar, de un sistema de coordenadas rectangulares a un sistema de coordenadas esfericas, entre otros.

METODO DE LAGRANGE

Definición del metodo de Lagrange

Método utilizado en la optimización para encontrar los máximos y mínimos de funciones de varias variables sujetas a restricciones su creador fue Joseph Louis Lagrange nombrado el metodo en honor a el.

 Este método reduce el problema restringido con n variables a uno sin restricciones de n + k variables, donde k es igual al número de restricciones, y cuyas ecuaciones pueden ser resueltas más fácilmente. Estas nuevas variables escalares desconocidas, una para cada restricción, son llamadas multiplicadores de Lagrange. El método dice que los puntos donde la función tiene un extremo condicionado con k restricciones, están entre los puntos estacionarios de una nueva función sin restricciones construida como una combinación lineal de la función y las funciones implicadas en las restricciones, cuyos coeficientes son los multiplicadores. La demostración usa derivadas parciales y la regla de la cadena para funciones de varias variables. Se trata de extraer una función implícita de las restricciones, y encontrar las condiciones para que las derivadas parciales con respecto a las variables independientesde la función sean iguales a cero.

Consideremos un caso bidimensional. Supongamos que tenemos la función, f (x, y), y queremos maximizarla, estando sujeta a la condición:

donde c es una constante. Podemos visualizar las curvas de nivel de f dadas por

para varios valores de d_n, y el contorno de g dado por g(x, y) = c. Supongamos que hablamos de la curva de nivel donde g = c. Entonces, en general, las curvas de nivel de f y g serán distintas, y la curva g = c por lo general intersecará y cruzará muchos contornos de f. En general, moviéndose a través de la línea g=c podemos incrementar o disminuir el valor de f. Sólo cuando g=c (el contorno que estamos siguiendo) toca tangencialmente (no corta) una curva de nivel de f, no se incrementa o disminuye el valor de f. Esto ocurre en el extremo local restringido y en los puntos de inflexión restringidos de f.

Un ejemplo familiar puede ser obtenido de los mapas climatológicos, con sus curvas de nivel de presión y temperatura (isóbaras e isotermas respectivamente): el extremo restringido ocurrirá donde los mapas superpuestos muestren curvas que se tocan.

Geométricamente traducimos la condición de tangencia diciendo que los gradientes de f y g son vectores paralelos en el máximo. Introduciendo un nuevo escalar, λ, resolvemos

[f(x, y) - λ (g(x, y) − c)] = 0

para λ ≠ 0.

Una vez determinados los valores de λ, volvemos al número original de variables y así continuamos encontrando el extremo de la nueva ecuación no restringida.

de forma tradicional. Eso es,  para todo (x, y) satisfaciendo la condición porque  es igual a cero en la restricción, pero los ceros de F(x, y) están todos en .

Este metodo sirve para optimizar