investigación de operaciones
Conceptos introductorios
DEFINICIÓN
Se puede expresar un problema de programación no lineal (PNL)de la siguiente manera:
Encuentre los valores de las variables que
máximo (o mínimo)
sujeto a: (1)
Como en la programación lineal zes el funcional del problema de programación no lineal y
;… ;
son las restricciones del problema de programación no lineal.
Un problema de programación no lineal es un problema de programación no lineal no restringido.
El conjunto de puntos , tal que es un número real, es
, entonces, es el conjunto de los números reales.
Los siguientes subconjuntos de (llamados intervalos) serán departicular interés:
Y en forma análoga a las definiciones de la programación lineal.
DEFINICIÓN
La región factible para el problema de programación no lineal es el conjunto de puntos que satisfacen las m restricciones de (1).
Supóngase que (1) es un problema de maximización.
DEFINICIÓN
Cualquier punto en la región factible, para el cual se tiene que para todos los puntos Xde la región factible, es una solución óptima para el problema de programación no lineal.
(Para un problema de minimización, es la solución óptima si para toda X factible.
Por supuesto, si son funciones lineales, entonces (1) será un problema de programación lineal y puede resolverse mediante el algoritmo simplex.
Ejemplos de Programación No Lineal
Ejemplo N° 1
A una compañía le cuesta cUM por unidad fabricar un producto. Si la compañía cobra p UM por unidad de producto, los clientes pedirán unidades. Para maximizar las ganancias, ¿qué precio tendría que poner la compañía?
Solución
La variable de decisión de la empresa es p
Dado que la ganancia de la empresa es , la empresa querrá resolver el siguiente problema de maximización sin restricción:
Ejemplo N° 2
Si seutilizan K unidades de capital y L unidades de trabajo, una compañía puede producir KL unidades de un bien manufacturado. Se puede conseguir el capital a 4 UM/unidad y el trabajo a 1 UM/unidad. Se dispone de un total de 8 UM para contratar capital y trabajo. ¿Cómo puede la compañía maximizar la cantidad de bienes que se pueden fabricar?
Solución
Sea
K = unidades de capital contratadas y
L =unidades de trabajo compradas
entonces K y L deben satisfacer
Por lo tanto, la compañía quiere resolver el siguiente problema de maximización restringido:
Por ejemplo, considérese el PNL siguiente:
donde se representa en la figura:
La solución óptima para este PNL es .
Por supuesto, no se encuentra sobre la frontera de la región factible.
Extremos Locales
DEFINICIÓNPara cualquier problema de programación no lineal (una maximización), un punto factible es un máximo local si para un suficientemente pequeño, cualquier punto factible con satisface
En resumen, un punto es un máximo local si
para todo factible que esté cerca de
Análogamente, un punto es un mínimo local si
para todo que esté cerca de
Un punto que es un máximo local o unmínimo local, se llama un extremo local, o relativo.
Diferencia con programación lineal: Para la programación no lineal, puede ser que un máximo local no sea una solución óptima.
Por ejemplo, considérese el siguiente problema de programación no lineal:
donde se da en la Figura 2.
Figura 2 — UN MÁXIMO LOCAL PUEDE NO SER LA SOLUCIÓN ÓPTIMA PARA UN PROBLEMA DE PROGRAMACIÓN NO LINEALLos puntos A, B y C son todos máximos locales, pero el punto C es la única solución óptima para el problema de programación no lineal.
Diferencia con programación lineal: A diferencia de un problema de programación lineal, un problema de programación no lineal puede no satisfacer las suposiciones de PROPORCIONALIDAD y de ADITIVIDAD.
Por ejemplo, en el Ejemplo N° 2, un aumento de L en 1,...
Regístrate para leer el documento completo.