Programación No Lineal (Sin Restricciones)

1. Cálculo de Derivadas Parciales

   
   

   Calculamos las primeras derivadas parciales de la función objetivo f(x, y), denotadas como f_x y f_y.

2. Obtención de Puntos Críticos

   Para encontrar los puntos críticos, igualamos ambas derivadas parciales a cero:

   • f_x(x, y) = 0
   • f_y(x, y) = 0

   Resolvemos este sistema de ecuaciones para obtener los valores de x e y. Si es posible, despejamos una variable de una ecuación y la sustituimos en la otra para encontrar los pares (x, y) que constituyen los puntos críticos.

3. Cálculo del Determinante de la Matriz Hessiana

   Construimos la matriz Hessiana H(x, y) y calculamos su determinante:

   H(x, y) =
   | f_xx   f_xy |
   | f_yx   f_yy |

   El determinante es Det(H(x, y)) = f_xxf_yy – f_xyf_yx.

   Una vez obtenida la expresión del determinante, sustituimos en ella cada uno de los puntos críticos hallados en el paso anterior para evaluar su naturaleza:

   • Si Det(H(x, y)) < 0: El punto crítico es un punto de silla.
   • Si Det(H(x, y)) > 0: Debemos evaluar la segunda derivada parcial f_xx en el punto crítico:
     • Si f_xx > 0: El punto crítico es un mínimo relativo.
     • Si f_xx < 0: El punto crítico es un máximo relativo.
   • Si Det(H(x, y)) = 0: El criterio no proporciona información concluyente. Se requieren métodos adicionales para determinar la naturaleza del punto.

4. Interpretación de Resultados

   En los casos donde el criterio de la Hessiana no es concluyente (Det(H) = 0), o si al evaluar las derivadas parciales se obtiene cero, se puede estar ante un punto de inflexión o un caso que requiere un estudio más profundo. Para los puntos identificados como máximos o mínimos relativos, el valor de la función objetivo f(x,y) en ese punto representa el valor óptimo local.

Programación No Lineal (Con Restricciones de Igualdad)

1. Construcción del Lagrangiano

   Construimos la función Lagrangiana, L(x, y, λ), a partir de la función objetivo f(x, y) y la restricción g(x, y) = c:

   L(x, y, λ) = f(x, y) – λ(g(x, y) – c)

   Donde λ (lambda) es el multiplicador de Lagrange.

2. Cálculo de Derivadas Parciales del Lagrangiano

   Calculamos las primeras derivadas parciales del Lagrangiano con respecto a x, y, y λ:

   • L_x(x, y, λ) = ∂L/∂x
   • L_y(x, y, λ) = ∂L/∂y
   • L_λ(x, y, λ) = ∂L/∂λ = -(g(x, y) – c)

3. Obtención de Puntos Críticos Condicionados

   Igualamos a cero las derivadas parciales para encontrar los posibles puntos críticos condicionados:

   1. L_x(x, y, λ) = 0
   2. L_y(x, y, λ) = 0
   3. g(x, y) = c (que es equivalente a L_λ = 0)

   Resolvemos este sistema de ecuaciones. A menudo, se despeja λ de (i) y (ii) y se igualan las expresiones. Luego, se sustituye en (iii) para encontrar los valores de x e y, y finalmente λ. Los pares (x, y, λ) resultantes son los posibles puntos críticos condicionados.

4. Condición de Regularidad

   Verificamos la condición de regularidad para cada posible punto crítico (x, y):

   Calculamos las derivadas parciales de la restricción: g_x(x, y) y g_y(x, y).

   • Si g_x(x, y) ≠ 0 o g_y(x, y) ≠ 0 en el punto (x, y), entonces el punto es un punto regular y cumple la condición de regularidad. Por lo tanto, es un punto crítico condicionado válido.
   • Si ambas g_x(x, y) = 0 y g_y(x, y) = 0 en el punto (x, y), el punto no es regular y el método de los multiplicadores de Lagrange no es aplicable directamente.

5. Cálculo del Determinante de la Matriz Hessiana Bordeada

   Para determinar la naturaleza de los puntos críticos condicionados (máximo o mínimo local), calculamos el determinante de la matriz Hessiana bordeada (D(x, y, λ)) en cada punto crítico. Para dos variables y una restricción, la matriz es:

   D(x, y, λ) =
   | 0   g_x   g_y |
   | g_x   L_xx   L_xy |
   | g_y   L_yx   L_yy |

   Donde L_xx, L_xy, L_yx, L_yy son las segundas derivadas parciales del Lagrangiano con respecto a x e y.

   Evaluamos el determinante en cada punto crítico condicionado (x*, y*, λ*):

   • Si Det(D(x*, y*, λ*)) > 0: El punto es un máximo local condicionado.
   • Si Det(D(x*, y*, λ*)) < 0: El punto es un mínimo local condicionado.
   • Si Det(D(x*, y*, λ*)) = 0: El criterio no proporciona información concluyente.

   El valor óptimo local condicionado se obtiene sustituyendo el punto (x*, y*) en la función objetivo original f(x, y).

6. Interpretación del Multiplicador de Lagrange (λ)

   El valor del multiplicador de Lagrange (λ) en el punto óptimo condicionado tiene una interpretación económica importante: representa la tasa de variación del valor óptimo de la función objetivo con respecto a un cambio marginal en la constante de la restricción (c).

   Por ejemplo, si la restricción es un coste (c), λ indica cuánto aumentaría o disminuiría la producción óptima si el coste se incrementara en una unidad. La relación se expresa como:

   f*(c₂) ≈ f*(c₁) + λ(c₂ – c₁)

   Donde f*(c) es el valor óptimo de la función objetivo para una restricción c.

Programación No Lineal (Con Restricciones de Desigualdad)

Para problemas de optimización con restricciones de desigualdad, se utilizan las Condiciones de Kuhn-Tucker.

1. Construcción del Lagrangiano

   Construimos la función Lagrangiana, L(x, y, λ), de manera similar al caso de restricciones de igualdad, pero considerando la desigualdad:

   • Si la restricción es g(x, y) ≤ c, entonces: L(x, y, λ) = f(x, y) – λ(g(x, y) – c)
   • Si la restricción es g(x, y) ≥ c, entonces: L(x, y, λ) = f(x, y) + λ(g(x, y) – c) (o se reescribe como -g(x,y) ≤ -c)

   Donde λ (lambda) es el multiplicador de Lagrange.

2. Condiciones Necesarias de Kuhn-Tucker

   Para encontrar los posibles puntos críticos condicionados, resolvemos el siguiente sistema de condiciones:

   1. L_x(x, y, λ) = 0 (Derivada parcial del Lagrangiano respecto a x)
   2. L_y(x, y, λ) = 0 (Derivada parcial del Lagrangiano respecto a y)
   3. λ ≥ 0 (Condición de no negatividad para λ, si se maximiza con g(x,y) ≤ c; si se minimiza con g(x,y) ≤ c, entonces λ ≤ 0)
   4. g(x, y) – c ≤ 0 (La restricción original debe cumplirse)
   5. λ(g(x, y) – c) = 0 (Condición de holgura complementaria)

   Para resolver (v), consideramos dos casos:

   • Caso 1: λ = 0 (La restricción no está activa o no es vinculante).

     Sustituimos λ = 0 en (i) y (ii) y resolvemos para x e y. Luego, verificamos si los puntos (x, y) obtenidos cumplen la restricción (iv).

   • Caso 2: g(x, y) – c = 0 (La restricción está activa o es vinculante).

     Sustituimos g(x, y) = c en (i) y (ii) y resolvemos el sistema para x, y, y λ. Luego, verificamos si el λ obtenido cumple la condición (iii).

   Los puntos (x, y, λ) que satisfacen todas las condiciones son los posibles puntos críticos condicionados.

3. Condición de Regularidad

   La condición de regularidad es la misma que para las restricciones de igualdad. Para cada posible punto crítico (x, y) donde la restricción es activa (g(x,y) = c), las derivadas parciales de la restricción, g_x(x, y) y g_y(x, y), no deben ser ambas cero. Si se cumple, el punto es regular.

4. Condiciones Suficientes de Kuhn-Tucker (Basadas en la Matriz Hessiana del Lagrangiano)

   Para determinar si un punto crítico condicionado es un máximo o mínimo local, se pueden utilizar las condiciones de segundo orden. Una forma simplificada (para funciones cóncavas/convexas) es examinar la matriz Hessiana del Lagrangiano, H_L(x, y), que contiene las segundas derivadas parciales de L con respecto a x e y:

   H_L(x, y) =
   | L_xx   L_xy |
   | L_yx   L_yy |

   Evaluamos esta matriz en cada punto crítico condicionado (x*, y*):

   • Si H_L(x*, y*) es definida negativa (sus autovalores son todos negativos), el punto es un máximo local condicionado.
   • Si H_L(x*, y*) es definida positiva (sus autovalores son todos positivos), el punto es un mínimo local condicionado.
   • Si H_L(x*, y*) es semidefinida negativa/positiva o indefinida, se requieren criterios adicionales o un estudio más profundo.

   Para verificar la definitud, se pueden calcular los autovalores de la matriz. Si, por ejemplo, para un problema de maximización, los autovalores son negativos, la matriz es definida negativa.

   El valor óptimo local condicionado se obtiene sustituyendo el punto (x*, y*) en la función objetivo original f(x, y).

Configuración de Problemas de Optimización Lineal (Ejemplo)

Cuando se trabaja con problemas de optimización lineal, como los de transporte o asignación, la formulación implica definir una función objetivo y un conjunto de restricciones.

1. Definición de Variables y Datos

   Se suelen organizar los datos en tablas. Por ejemplo, si tenemos variables de decisión como x_ij (cantidad transportada de origen i a destino j), se crea una tabla para los costes unitarios y otra para las variables.

2. Función Objetivo

   La función objetivo se construye sumando el producto de los costes unitarios por las variables correspondientes. Por ejemplo, para un problema de minimización de costes:

   Minimizar Z = 65x₁₁ + 50x₁₂ + … (y así sucesivamente para todas las combinaciones i,j)

3. Restricciones

   Las restricciones se derivan de las capacidades de los orígenes y las demandas de los destinos. Se expresan como ecuaciones o inecuaciones:

   • Restricciones de Oferta/Capacidad (por filas): La suma de las cantidades enviadas desde cada origen no puede exceder su capacidad. Por ejemplo:
     • x₁₁ + x₁₂ + x₁₃ + … ≤ Capacidad₁
     • x₂₁ + x₂₂ + x₂₃ + … ≤ Capacidad₂
     • …
   • Restricciones de Demanda (por columnas): La suma de las cantidades recibidas en cada destino debe satisfacer su demanda. Por ejemplo:
     • x₁₁ + x₂₁ + x₃₁ + … ≥ Demanda₁
     • x₁₂ + x₂₂ + x₃₂ + … ≥ Demanda₂
     • …
   • Restricciones de No Negatividad: Todas las variables de decisión deben ser no negativas.
     • x_ij ≥ 0 para todo i = 1, 2, 3 y j = 1, 2, 3, 4, 5 (según el ejemplo dado).