Forma general de un P.P.N. L.
Max(Min) f(x1, , x2, . . . , xn)
s.a. g1(x1, x2, . . . , xn)(≤, =, ≥)b1
g2(x1, x2, . . . , xn)(≤, =, ≥)b2
gm(x1, x2, . . . , xn)(≤, =, ≥)bm
Como en Programación lineal la función f(x1, , x2, . . . , xn) es la función objetivo del P.N.L. y gi(x1, x2, . . . , xn)(≤, =, ≥)bi , i = 1, . . . , m son las restricciones del mismo. Además se supone que estas funciones son diferenciables.
Notar que las características y propiedades de los P.N.L. son distintas a las de P.L. y los algoritmos de optimización son también diferentes a los utilizados en P.L.
Tipos de Problemas de Programación No lineal
- Sin restricciones: Estos problemas son un programa matemático para los que las variables de decisión no están restringidas. Su formulación es de la siguiente forma:
Max (Min) f(x1, , x2, . . . , xn)
Este tipo de
problemas aparecen de forma natural en distintas áreas de la ciencia tales como
Estadística y Econometría. Otro aspecto importante de este tipo es que, en
ocasiones, un P.N.L. con restricciones se puede resolver a partir de un sin
restricciones.
Ejemplo: Se poseen los siguientes datos sobre una población animal,
yi a lo largo de cinco años. Se quiere ajustar a un modelo y = aebt
| ti | 1 | 2 | 4 | 5 | 8 |
| yi | 4 | 4 | 6 | 11 | 22 |
La función a optimizar es F(a, b) = 1/2 ∑ 5, i=1 (aebti − yi) 2
. En este caso seria Mina,b F(a, b).
Notemos que el método de mínimos cuadrados responde a una formulación no lineal sin restricciones; esto es, La función y = ax + b se ajusta a los datos (xi , yi), i = 1, . . . , n minimizando la expresión Mina,b S(a, b) = ∑ n, i=1 (yi − (a + bxi))2
Si un problema de programación no lineal no tiene restricciones, el hecho de que la función objetivo sea cóncava garantiza que un máximo local es un máximo global. (De igual manera, una función objetivo convexa asegura que un mínimo local es un mínimo global). Si existen restricciones, entonces se necesita una condición más para dar esta garantía, a saber, que la región factible sea un conjunto convexo. Un conjunto convexo es sencillamente un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en la colección. La región factible para cualquier otro problema de programación lineal es un conjunto convexo.
- Con restricciones: La formulación de este tipo de problemas responde a la formulación general presentada al comienzo de esta sección. El estudio del problema con restricciones comenzó abordando solamente el problema con restricciones de igualdad, teniendo sus orígenes en el siglo XVIII. El problema con restricciones de desigualdad tiene una historia más reciente, de hecho hasta los años cincuenta del pasado siglo no se tratan éstos.
Notemos que los problemas con restricciones de desigualdad permiten reflejar la realidad en términos matemáticos mejor que los problemas con restricciones de igualdad, ya que no “limitan” tanto la elección de los valores de las variables de decisión.
Los problemas con restricciones de igualdad suelen considerarse como poco realistas debido a lo restrictivo de su planteamiento. Sin embargo, el estudio de ellos se considera interesante ya que es de utilidad en distintas áreas de conocimiento como Economía, Estadística...
Ejemplo: Una compañía planea gastar 10000 euros en publicidad. Se sabe que un minuto de publicidad en televisión cuesta 3000 euros y 1000 euros en la radio. Si la empresa compra x minutos de publicidad en televisión e y minutos en la radio, su ingreso, en euros, esta dado por −2x2 − y2 + xy + 8x + 3y. ¿Como puede la empresa maximizar sus ingresos?
El objetivo es maximizar los ingresos, Z(x, y) = −2x2 − y2 + xy + 8x + 3y
Restricciones del problema:
- Gastar 10000 euros en publicidad en los dos medios, 3000x + 1000y = 10000.
Por tanto:
Este problema es un problema no lineal con restricciones de igualdad (lineal)
Notemos que el método de mínimos cuadrados responde a una formulación no lineal sin restricciones; esto es, La función y = ax + b se ajusta a los datos (xi , yi), i = 1, . . . , n minimizando la expresión Mina,b S(a, b) = ∑ n, i=1 (yi − (a + bxi))2
Si un problema de programación no lineal no tiene restricciones, el hecho de que la función objetivo sea cóncava garantiza que un máximo local es un máximo global. (De igual manera, una función objetivo convexa asegura que un mínimo local es un mínimo global). Si existen restricciones, entonces se necesita una condición más para dar esta garantía, a saber, que la región factible sea un conjunto convexo. Un conjunto convexo es sencillamente un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en la colección. La región factible para cualquier otro problema de programación lineal es un conjunto convexo.
- Con restricciones: La formulación de este tipo de problemas responde a la formulación general presentada al comienzo de esta sección. El estudio del problema con restricciones comenzó abordando solamente el problema con restricciones de igualdad, teniendo sus orígenes en el siglo XVIII. El problema con restricciones de desigualdad tiene una historia más reciente, de hecho hasta los años cincuenta del pasado siglo no se tratan éstos.
Notemos que los problemas con restricciones de desigualdad permiten reflejar la realidad en términos matemáticos mejor que los problemas con restricciones de igualdad, ya que no “limitan” tanto la elección de los valores de las variables de decisión.
Los problemas con restricciones de igualdad suelen considerarse como poco realistas debido a lo restrictivo de su planteamiento. Sin embargo, el estudio de ellos se considera interesante ya que es de utilidad en distintas áreas de conocimiento como Economía, Estadística...
Ejemplo: Una compañía planea gastar 10000 euros en publicidad. Se sabe que un minuto de publicidad en televisión cuesta 3000 euros y 1000 euros en la radio. Si la empresa compra x minutos de publicidad en televisión e y minutos en la radio, su ingreso, en euros, esta dado por −2x2 − y2 + xy + 8x + 3y. ¿Como puede la empresa maximizar sus ingresos?
Las variables de decision del problema son:
x : minutos que compra la empresa en television
y : minutos que compra la empresa en radio
El objetivo es maximizar los ingresos, Z(x, y) = −2x2 − y2 + xy + 8x + 3y
Restricciones del problema:
- Gastar 10000 euros en publicidad en los dos medios, 3000x + 1000y = 10000.
Por tanto:
M a Z(x, y) = −2x2 − y2 + xy + 8x + 3y
s.a. 3000x + 1000y = 10000
Este problema es un problema no lineal con restricciones de igualdad (lineal)
No hay comentarios:
Publicar un comentario