LOGO
Carrera:
INGENIERIA EN SISTEMAS
Asignatura:
INVESTIGACION DE OPERACIONES
Tema:
3. Programacin no lineal
Subtema:
3.1 Conceptos bsicos de problemas de
programacin no lineal
LOGO
DEFINICION
Programacin no lineal (PNL) es el proceso de resolucin
de un sistema de igualdades y desigualdades sujetas a
un conjunto de restricciones sobre un conjunto de
variables reales desconocidas, con una funcin
objetivo
a maximizar,
cuando
alguna
de
las
restricciones o la funcin objetivo no son lineales.
LOGO -- - CONCEPTOS BSICOS DE
PROGRAMACION NO LINEAL - - De una manera general, el problema de programacin no
lineal consiste en encontrar:
para maximizar
sujeta a
f(x),
y
donde f(x) y las
variables de decisin.
son funciones dadas de n
LOGO
Se puede expresar un problema de programacin no
lineal (PNL) de la siguiente manera:
Encuentre los valores de las variables que
LOGO
Como en la programacin lineal z es el funcional del
problema de programacin no lineal y
son las restricciones del problema de programacin no
lineal.
Un problema de programacin no lineal es un problema de
programacin no lineal no restringido.
El conjunto de puntos, tal que es un nmero real, es
entonces, es el conjunto de los nmeros reales.
[Link]
LOGO
Los siguientes subconjuntos de (llamados intervalos) sern
de particular inters:
Y en forma anloga a las definiciones de la programacin lineal.
La regin factible para el problema de programacin no lineal es
el conjunto de puntos que satisfacen las m restricciones de (1)
[Link]
LOGO
Carrera:
INGENIERIA EN SISTEMAS
Asignatura:
INVESTIGACION DE OPERACIONES
Tema:
3. Programacin no lineal
Subtema:
3.2 Ilustracin grafica de problemas de
programacin no lineal.
[Link]
LOGO
Cuando un problema de programacin no lineal tiene solo una
o dos variables, se puede representar grficamente.
Una representacin grafica de este tipo proporciona una visin
global de las propiedades de las soluciones optimas de
programacin lineal y no lineal.
La siguiente figura muestra un problema en el que la segunda y
tercera restricciones funcionales se sustituyen por la
restriccin no lineal 9x12 + 5x22 216. La solucin es (x1, x2)=
(2,6)
[Link]
LOGO
Se observa que se encuentra sobre la regin factible, pero no
es una solucin factible en vrtice (fev). La solucin optima
pudo haber sido una solucin fev con una funcin objetivo
diferente, pero que no necesite serlo significa que ya no se
puede aprovechar la gran simplicidad utilizada en programacin
lineal que permite limitar la bsqueda de una solucin optima
para las soluciones fev.
[Link]
LOGO
Ahora suponga que las restricciones lineales se conservan sin
cambio pero la funcin objetivo se hace no lineal.
[Link]
LOGO
Entonces la grafica de la figura anterior indica que la solucin
ptima es x1= 8/3 y x2= 5, que de nuevo se encuentra en frontera
de la regin factible. (el valor optimo de z es z =857 ; as en la
figura muestra el hecho de que el lugar geomtrico de todos los
puntos para los que z =857 tiene en comn con la regin
factible solo este punto, mientras que el lugar geomtrico de los
puntos con z mas grande no toca la regin factible en ningn
punto.)
por otro lado si,
[Link]
LOGO
Entonces en la siguiente figura se ilustra que la solucin optima
es (x1, x2)= (3,3), que se encuentra dentro de la frontera de la
regin factible. (se puede comprobar que esta solucin es
optima si se usa calculo para derivarla como un mximo global
no restringido; como tambin satisface las restricciones, debe
ser optima para el problema restringido.)
Por lo tanto es necesario que un algoritmo general para
resolver problemas de este tipo tome en cuenta todas las
soluciones en la regin factible, y no solo aquellas que estn
sobre la frontera.
Otra complicacin que surge en programacin no lineal es que
un mximo global (la solucin optima global).
[Link]
LOGO
[Link]
LOGO
Por ejemplo:
Consideremos la funcin de una sola variable graficada como
se muestra en la siguiente figura.
en el intervalo 0 x 5 esta funcin tiene tres mximos locales
x =0, x=2, x=4 pero solo uno de estos x=4 es un mximo
global. de igual manera, existen mnimos locales en x=1,3 y 5,
pero solo x=5 es un mnimo global.
[Link]
LOGO
En general, los algoritmos de programacin no lineal no pueden
distinguir entre un mximo local y mximo global (excepto si
encuentran otro mximo local mejor), por lo que es
determinante conocer las condiciones bajo las que se garantiza
que un mximo local es un mximo global en la regin factible.
Recuerde que en calculo, cuando se maximiza una funcin
ordinaria (doblemente diferenciable) de una sola variable f(x)
sin restricciones, esta garanta esta dada cuando
Una funcin de este tipo cuya curvatura siempre es hacia
abajo o que no tiene curvatura se llama cncava. cuando tiene
curvatura hacia arriba se llama funcin convexa.
[Link]
LOGO
Carrera:
INGENIERIA EN SISTEMAS
Asignatura:
INVESTIGACION DE OPERACIONES
Tema:
3. Programacin no lineal
Subtema:
3.3 Tipos de problemas de
programacin no lineal.
[Link]
LOGO
Los problemas de programacin no lineal se presentan de
muchas formas distintas. Al contrario del mtodo smplex para
programacin lineal, no se dispone de un algoritmo que resuelva
todos estos tipos especiales de problemas. En su lugar, se han
desarrollado algoritmos para algunas clases (tipos especiales)
de problemas de programacin no lineal.
Si la funcin objetivo f es lineal y el espacio restringido es un
politopo, el problema es de Programacin lineal y puede
resolverse utilizando alguno de los bien conocidos algoritmos
de programacin lineal.
[Link]
LOGO
Si la funcin objetivo es cncava (problema de maximizacin),
o convexa (problema de minimizacin) y el conjunto de
restricciones es convexo, entonces se puede utilizar el mtodo
general de Optimizacin convexa.
Existe una variedad de mtodos para resolver problemas no
convexos.
Uno de ellos consiste en utilizar formulaciones
especiales de problemas de programacin lineal. Otro mtodo
implica el uso de tcnicas de Ramificacin y poda, cuando el
problema se divide en subdivisiones a resolver mediante
aproximaciones que forman un lmite inferior del coste total en
cada subdivisin. Mediante subdivisiones sucesivas, se obtendr
una solucin cuyo coste es igual o inferior que el mejor lmite
inferior obtenido por alguna de las soluciones aproximadas.
[Link]
LOGO
Esta solucin es ptima, aunque posiblemente no sea nica. El
algoritmo puede ser parado antes, con la garanta de que la
mejor solucin ser mejor que la solucin encontrada en un
porcentaje acotado. Ello se utiliza en concreto en problemas
importantes y especialmente difciles y cuando el problema cuenta
con costes inciertos o valores donde la incertidumbre puede ser
estimada en un grado de fiabilidad apropiado.
Las condiciones de Karush-Kuhn-Tucker proporcionan
condiciones necesarias para que una solucin sea ptima.
las
[Link]
LOGO
Los tipos de problemas de programacin no lineal son:
Optimizacin no restringida.
Optimizacin linealmente restringida
Programacin cuadrtica
Programacin convexa
Programacin separable.
Programacin no convexa.
Programacin geomtrica.
Programacin fraccional.
Problema de complementariedad.
[Link]
LOGO
OPTIMIZACION NO RESTRINGIDA
Los problemas de optimizacin no restringida no tiene
restricciones, por lo que la funcin objetivo es
sencillamente
maximizar f(x)
sobre todos los valores
. la condicin
necesaria para que una solucin especifica x=x* sea
optima cuando f(x) es una funcin diferenciable es
LOGO
Cuando f(x) es cncava, esta condicin tambin es suficiente,
con lo que la obtencin de x* se reduce a resolver el sistema de
las n derivadas parciales iguales a cero. Pero cuando se trata de
funciones no lineales f(x), estas ecuaciones suelen ser no lineales
tambin, en cuyo caso es poco probable que se pueda obtener
una solucin analtica simultanea.
OPIMIZACION LINEAL RESTRINGIDA
los problemas de optimizacin linealmente restringida se
caracterizan por restricciones que se ajustan por completo a la
programacin lineal, de manera que todas las funciones de
restriccin
son lineales, pero la funcin objetivo es no
lineal. El problema se simplifica mucho si solo se tiene que tomar
en cuenta una funcin no lineal junto con una regin factible de
programacin lineal.
LOGO
PROGRAMACION CUADRATICA
Estos tipos de problemas tienen restricciones lineales, pero ahora
la funcin objetivo f(x) debe ser cuadrtica. Entonces, la nica
diferencia entre estos y un problema de programacin lineal es
que algunos trminos de la funcin objetivo incluyen el cuadrado
de una variable o el producto de dos variables.
Para este caso se han desarrollado muchos algoritmos, con la
suposicin adicional de que f(x) es cncava.
La programacin cuadrtica es muy importante, debido a que las
formulaciones de este tipo surgen de manera natural en muchas
aplicaciones.
LOGO
EJEMPLO:
Ilustracin de cmo
una solucin optima
puede estar en un
punto en el que la
derivada es negativa
en lugar de cero, por
que ese punto esta
en la frontera de una
restriccin de no
negatividad.
LOGO
PROGRAMACION CONVEXA
Esta clase de programacin abarca a una amplia clase de
problemas, estn todos los tipos anteriores cuando f(x) es
cncava. las suposiciones son
1. f(x) es cncava
2. Cada una de las
es convexa.
- PROGRAMACION SEPARABLE
ES UN CASO ESPECIAL DE PROGRAMACION CONVEXA, EN
DONDE LA SUPOCION ADICIONAL ES:
3. Todas las funciones f(x) y
son funciones separables.
Una funcin separable es una funcin en la que cada termino
incluye una sola variable, por lo que la funcin se puede
separar en una suma de funciones de variables individuales.
LOGO
por ejemplo,
si f(x) es una separable, se puede expresar como
En donde cada
incluye solo los trminos con
. en la
terminologa de programacin lineal, los problemas de
programacin separable satisfacen las suposiciones de
aditividad pero no las de proporcionalidad (para funciones
lineales).
es importante distinguir estos problemas de otros de
programacin separable se puede aproximar muy de cerca
mediante uno de programacin lineal y, entonces, se puede
aplicar el eficiente mtodo simplex.
LOGO
PROGRAMACION NO CONVEXA
La programacin no convexa incluye todos los problemas
programacin no lineal que no satisfacen las suposiciones
programacin convexa. en este caso cuando se tenga xito
encontrar un mximo local, no hay garanta de que sea tambin
mximo global.
de
de
en
un
Por lo tanto no se tiene un algoritmo que garantice encontrar una
solucin optima para todos estos problemas; pero existen algunos
algoritmos bastante adecuados para encontrar mximos locales, en
especial cuando las formas de las funciones no lineales no se
desvan demasiado de aquellas que se supusieron para
programacin convexa.
LOGO
PROGRAMACION GEOMETRICA
Estas surgen cuando la funcin objetivo y funciones de restriccin
son de la siguiente forma:
donde
en tales casos, las
representan las constantes fsicas y las xj
son las variables de diseo, estas funciones por lo general no son
cncavas ni convexas, por lo que las tcnicas de programacin
convexa no se pueden aplicar directamente a estos problemas de
programacin geomtrica.
LOGO
Sin embargo, existe un caso importante en el que el
problema se puede transformar en un problema de
programacin convexa equivalente.
Esto es cuando todos los coeficientes
en cada funcin
son estrictamente positivos, es decir, las funciones son
polinomios positivos generalizados (ahora llamados
posinomiales), y la funcin objetivo se tiene que minimizar.
el problema equivalente de programacin convexa con
variables de decisin
se obtiene entonces al
establecer
en todo el modelo original. ahora puede aplicarse un
algoritmo de programacin convexa.
