ejercicios no lineales

 

3.1 Conceptos básicos de problemas de programación no lineal

3.1 Conceptos básicos de problemas de programación no lineal 

La programación no lineal (PNL) estudia cómo encontrar el mejor resultado posible (óptimo) en problemas donde:

• La función objetivo no sigue una relación lineal entre variables.
• Las restricciones también pueden ser no lineales.

Diferencias clave con la programación lineal (PL):

Aspecto	PL	PNL
Función objetivo	Lineal	No lineal
Restricciones	Lineales	Lineales o no lineales
Solución	Generalmente única y en vértices	Puede haber múltiples óptimos (locales/globales).
Métodos de resolución	Simplex, gráficos	Gradientes, Lagrange, heurísticas.

Características de problemas PNL:

1. No convexidad: Una función no convexa puede tener varios puntos donde parece "mínima" o "máxima", complicando encontrar el óptimo global.
2. Dependencia del inicio: Los métodos iterativos pueden converger a diferentes soluciones dependiendo de los valores iniciales.
3. Superficies complejas: Las restricciones y la función objetivo generan geometrías complicadas, como superficies curvas o regiones irregulares.

Ejemplo básico:

Minimizar $f(x, y) = x^2 + y^2$, sujeto a $x + y \geq 1$ y $x, y \geq 0$.

1. La función objetivo $x^2 + y^2$ es una parábola en 3D (forma de cuenco).
2. La restricción $x + y \geq 1$ forma una línea en el plano $xy$.
3. El objetivo es encontrar el punto más cercano al origen que cumpla con las restricciones.

---

3.2 Ilustración gráfica de problemas de programación no lineal

En la programación no lineal, las gráficas son herramientas poderosas para comprender la relación entre la función objetivo y las restricciones.

Visualización de PNL en 2D y 3D:

1. Curvas de nivel: Representan los valores constantes de la función objetivo en un plano $xy$.
   Ejemplo: Si $f(x, y) = x^2 + y^2$, las curvas de nivel son círculos centrados en el origen.
2. Superficie de la función objetivo: En 3D, $f(x, y)$ se visualiza como una superficie curva.
   • En $z = x^2 + y^2$, cada punto en la superficie representa un valor de la función para una combinación de $x, y$.
3. Restricciones: Las restricciones se visualizan como áreas válidas (factibles).
   • Ejemplo: $x^2 + y^2 \leq 1$ (un círculo) limita la región factible.

Ejemplo gráfico detallado:

Problema:
Maximizar $f(x, y) = 2x + y$, sujeto a:

• $x^2 + y^2 \leq 4$ (círculo de radio 2).
• $y \geq x$.

1. Región factible:

   • La restricción $x^2 + y^2 \leq 4$ define un círculo.
   • La restricción $y \geq x$ es una región por encima de la línea $y = x$.
   • La intersección de estas restricciones es la región válida.

2. Curvas de nivel:
   Las líneas rectas de $2x + y = c$ (valores constantes de $f$) se desplazan en dirección del gradiente hasta tocar el borde de la región factible.

3. Solución óptima:
   Ocurre en el punto de tangencia entre la curva de nivel más alta y la región factible.

---

3.3 Tipos de problemas de programación no lineal

La programación no lineal se clasifica según las características de la función objetivo y las restricciones:

1. Problemas sin restricciones:

Aquí, la función objetivo se optimiza sin límites externos.

• Método típico: Derivadas para hallar puntos críticos y clasificar máximos/mínimos.
• Ejemplo: Minimizar $f(x) = x^3 - 3x^2 + 2x$.
  • $f'(x) = 3x^2 - 6x + 2$, igualando a 0: $x = 1, x = \frac{2}{3}$.
  • Usando $f''(x) = 6x - 6$, se determina que $x = 1$ es un mínimo y $x = \frac{2}{3}$ es un máximo.

2. Problemas con restricciones:

Se optimiza la función objetivo bajo condiciones específicas.

• Método típico: Lagrange, Kuhn-Tucker, penalización.
• Ejemplo: Maximizar $f(x, y) = x^2 + y^2$, sujeto a $x + y = 1$.
  • Usando Lagrange:
    $\mathcal{L} = x^2 + y^2 + \lambda (x + y - 1)$.
    Resolviendo, se obtiene $x = y = 0.5$.

3. Problemas convexos vs. no convexos:

• Convexos: Tienen una única solución óptima global (son más fáciles de resolver).
  Ejemplo: $f(x) = x^2 + y^2$.
• No convexos: Pueden tener múltiples óptimos locales.
  Ejemplo: $f(x) = x^4 - x^2$.

---

3.4 Optimización clásica

Puntos críticos:

Los puntos críticos son lugares donde la derivada de la función objetivo se anula ($f'(x) = 0$) o no existe. Se clasifican en:

• Máximos locales: El valor de la función es mayor que en puntos cercanos.
• Mínimos locales: El valor de la función es menor que en puntos cercanos.
• Puntos de silla: No es ni máximo ni mínimo; ocurre un cambio en la curvatura.

Métodos clásicos:

1. Primera derivada: Identifica posibles puntos críticos.
2. Segunda derivada: Evalúa la curvatura para clasificar el punto crítico:
   • $f''(x) > 0$: Mínimo local.
   • $f''(x) < 0$: Máximo local.
   • $f''(x) = 0$: Indeterminado (posible punto de inflexión).

Puntos de inflexión:

Un punto donde la función cambia de concavidad, identificado cuando la segunda derivada cambia de signo.

Ejemplo completo:

$f(x) = x^3 - 6x^2 + 9x$.

1. Primera derivada: $f'(x) = 3x^2 - 12x + 9$, igualando a 0: $x = 1, x = 3$.
2. Segunda derivada: $f''(x) = 6x - 12$.
   • $f''(1) = -6$: Máximo local en $x = 1$.
   • $f''(3) = 6$: Mínimo local en $x = 3$.

---

Métodos avanzados en PNL

1. Método de Lagrange:
   Se introduce un multiplicador ($\lambda$) para manejar restricciones igualitarias.

   • Optimiza $\mathcal{L}(x, y, \lambda) = f(x, y) + \lambda \cdot g(x, y)$.

2. Kuhn-Tucker (KKT):
   Extensión de Lagrange para desigualdades. Útil en problemas con restricciones complejas.

3. Método de gradiente descendente:
   Encuentra mínimos ajustando iterativamente los valores en la dirección de mayor descenso.

4. Algoritmos heurísticos:
   Métodos como optimización por enjambre de partículas (PSO) y algoritmos genéticos se usan para resolver problemas no convexos.

PROBLEMA DE CONSTRUCCION DE CASA

 

PERT-CPM PRESENTACION

 

ejercicio 2

 

ejemplo del metodo de la ruta mas corta

 

metodo de la ruta mas corta

Problema camino mas corto

Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.

Ejemplo

Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:

Se determinan las variables de decisión, en este caso:

• Xij: acción de desplazarse del pueblo i al j (0 indica que no hay desplazamiento y 1 que sí hay desplazamiento)

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen del balance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que nos devuelvan al punto de partida y los que provengan del punto de destino):

• Balance de caminos del pueblo 1: X12 + X13 = 1
• Balance de caminos del pueblo 2: X24 + X25 – X12 – X42 – X52 = 0
• Balance de caminos del pueblo 3: X34 + X36 – X13 – X43 – X63 = 0
• Balance de caminos del pueblo 4: X42 + X43 + X45 – X24 – X34 – X54 = 0
• Balance de caminos del pueblo 5: X52 + X54 + X57 – X25 – X45 =

Balance de caminos del pueblo 6: X63 + X67 – X36 = 0

Balance de caminos del pueblo 7: – X57 – X67 = -1

Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores, … En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:

• Xij ≥ 0
• Xij es booleano

Se determina la función objetivo:

• Minimizar Z = 12·X12 + 4·X13 + 5·X24 + 3·X25 + 2·X34 + 10·X36 + 5·X42 + 2·X43 + 10·X45 + 3·X52 + 10·X54 + 2·X57 + 10·X63 + 4·X67

ver video de problema de camino corto

•