Investigación de operaciones
martes, 3 de diciembre de 2024
TEORIA DE INVENTARIOS
lunes, 2 de diciembre de 2024
ejercicio de programación no lineal
viernes, 22 de noviembre de 2024
martes, 19 de noviembre de 2024
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:
- No convexidad: Una función no convexa puede tener varios puntos donde parece "mínima" o "máxima", complicando encontrar el óptimo global.
- Dependencia del inicio: Los métodos iterativos pueden converger a diferentes soluciones dependiendo de los valores iniciales.
- 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)=x2+y2, sujeto a x+y≥1 y x,y≥0.
- La función objetivo x2+y2 es una parábola en 3D (forma de cuenco).
- La restricción x+y≥1 forma una línea en el plano xy.
- 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:
- Curvas de nivel: Representan los valores constantes de la función objetivo en un plano xy.
Ejemplo: Si f(x,y)=x2+y2, las curvas de nivel son círculos centrados en el origen. - Superficie de la función objetivo: En 3D, f(x,y) se visualiza como una superficie curva.
- En z=x2+y2, cada punto en la superficie representa un valor de la función para una combinación de x,y.
- Restricciones: Las restricciones se visualizan como áreas válidas (factibles).
- Ejemplo: x2+y2≤1 (un círculo) limita la región factible.
Ejemplo gráfico detallado:
Problema:
Maximizar f(x,y)=2x+y, sujeto a:
- x2+y2≤4 (círculo de radio 2).
- y≥x.
Región factible:
- La restricción x2+y2≤4 define un círculo.
- La restricción y≥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.
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.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)=x3−3x2+2x.
- f′(x)=3x2−6x+2, igualando a 0: x=1,x=32.
- Usando f′′(x)=6x−6, se determina que x=1 es un mínimo y x=32 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)=x2+y2, sujeto a x+y=1.
- Usando Lagrange:
L=x2+y2+λ(x+y−1).
Resolviendo, se obtiene x=y=0.5.
- Usando Lagrange:
3. Problemas convexos vs. no convexos:
- Convexos: Tienen una única solución óptima global (son más fáciles de resolver).
Ejemplo: f(x)=x2+y2. - No convexos: Pueden tener múltiples óptimos locales.
Ejemplo: f(x)=x4−x2.
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:
- Primera derivada: Identifica posibles puntos críticos.
- 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)=x3−6x2+9x.
- Primera derivada: f′(x)=3x2−12x+9, igualando a 0: x=1,x=3.
- 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
Método de Lagrange:
Se introduce un multiplicador (λ) para manejar restricciones igualitarias.- Optimiza L(x,y,λ)=f(x,y)+λ⋅g(x,y).
Kuhn-Tucker (KKT):
Extensión de Lagrange para desigualdades. Útil en problemas con restricciones complejas.Método de gradiente descendente:
Encuentra mínimos ajustando iterativamente los valores en la dirección de mayor descenso.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.
jueves, 14 de noviembre de 2024
martes, 12 de noviembre de 2024
jueves, 7 de noviembre de 2024
TEORIA DE INVENTARIOS
4.1 NATURALEZA E IMPORTANCIA DE LOS INVENTARIOS El inventario es el conjunto de mercancías o artículos que tienen las empresas para come...
-
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 pos...
-
Problema camino mas corto Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de halla...
-
Un terreno rectangular limita en uno de sus lados con un rio, se tiene 300 metros de alambre para cercar los 3 lados. ¿Cuál es el area maxim...


