io equipob informe programacion no lineal
TRANSCRIPT
-
UNIVERSIDAD ESTATAL DE GUAYAQUIL
FACULTAD DE INGENIERA INDUSTRIAL
INGENIERA EN TELEINFORMTICA
INVESTIGACIN DE OPERACIONES
PROGRAMACION NO LINEAL
DOCENTE:
Ing. Jos Avad
ALUMNOS:
Jair Aguilar
Josu Alcvar
Briggite Aucapia
Guillermo Carrin
Jess Vargas
Marlon Yuquilema
6to. Semestre A
Ao Lectivo:
-
2014 Guayaquil Ecuador
Tabla de Contenido
INTRODUCCIN ..................................................................................................................... 1
Conceptos bsicos de problemas de programacin no lineal. .................................................... 1
Programacin no lineal .......................................................................................................... 1
Qu es una funcin ................................................................................................................. 1
El mtodo Simplex ................................................................................................................. 1
Un algoritmo .......................................................................................................................... 1
Regin de Factibilidad Ilimitada ............................................................................................ 1
Redundancia Entre las Restricciones ..................................................................................... 2
La teora de la produccin ...................................................................................................... 2
La tecnologa .......................................................................................................................... 2
Las funciones de produccin .................................................................................................. 2
La mono tonicidad .................................................................................................................. 2
La convexidad ........................................................................................................................ 2
Programacin No Lineal ............................................................................................................ 3
Programacin no lineal ( ........................................................................................................ 3
Definicin ............................................................................................................................... 4
Definicin ............................................................................................................................... 5
Definicin ............................................................................................................................... 5
El problema de programacin no lineal ................................................................................. 6
-
2 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Problema de programacin No lineal general ........................................................................ 6
Relacin entre el problema de programacin no lineal y el proceso real. ............................. 7
TIPOS DE PROBLEMAS DE PROGRAMACIN NO LINEAL. .......................................... 8
Optimizacin no restringida. .................................................................................................. 9
Optimizacin linealmente restringida. ................................................................................. 11
Programacin cuadrtica ...................................................................................................... 12
Programacin convexa. ........................................................................................................ 12
Programacin separable. ...................................................................................................... 13
Programacin no convexa. ................................................................................................... 14
Programacin geomtrica. .................................................................................................... 15
Optimizacin de programacin no lineal con Solver .............................................................. 16
Construccin de un problema de optimizacin. ................................................................... 20
Datos del modelo de trabajo ................................................................................................. 21
CONCLUSIN ........................................................................................................................ 22
REFERENCIAS BIBLIOGRAFICAS ..................................................................................... 23
-
INTRODUCCIN
En este documento se da a conocer un poco ms sobre la programacin no lineal forma parte de
la investigacin de operaciones y tambin, como la programacin lineal, tiene como finalidad
proporcionar los elementos para encontrar los puntos ptimos para una funcin objetivo. En este
planteamiento, tanto la funcin objetivo como las restricciones son no lineales.
Se presenta un problema de programacin no lineal cuando tanto la funcin objetivo que debe
optimizarse, como las restricciones del problema, o ambas, tienen forma de ecuaciones
diferenciales no lineales, es decir, corresponden a ecuaciones cuyas variables tienen un
exponente mayor que 1.
El campo de aplicacin de la programacin no lineal es muy amplio, sin embargo, hasta la fecha
los investigadores de esta rama del conocimiento no han desarrollado un mtodo sistemtico que
sea prctico para su estudio. La programacin no lineal tambin es conocida con el nombre de
programacin cuadrtica, en virtud de que la mayor parte de los problemas que resultan
contienen ecuaciones cuadrticas o de segundo grado.
Muchas veces se presentan casos en que se deben maximizar funciones no lineales que presentan
restricciones lineales; esto es posible resolverlo, siempre y cuando se admita la hiptesis de que
la utilidad marginal no es constante, en este caso, la funcin objetivo deja de ser lineal.
-
2 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Las ventajas ms importantes de la programacin no lineal son dos:
1. En algunas ocasiones la distribucin ptima del presupuesto excluye cualquiera de los bienes
considerados en el presupuesto general; esta situacin se refleja en cualquiera de las restricciones
del modelo.
2. La programacin no lineal aporta mayor informacin que la contenida en el anlisis marginal.
No slo define el objetivo, sino que tambin seala la orientacin especfica para lograr el
objetivo.
Autores
Aguilar J., Carrin A., Vargas J., Aucapia B., Alcvar J., Yuquilema M.
Ingeniera en teleinformtica
-
1 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Conceptos bsicos de problemas de programacin no lineal.
Programacin no lineal: 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.
Qu es una funcin: una funcin es una cosa que hace algo. Por ejemplo, una mquina de moler
caf es una funcin que transforma los granos de caf en polvo. La funcin (objetivo) traza,
traduce el dominio de entrada (denominado regin factible) en un rango de salida con dos
valores finales denominados valores mximo y mnimo.
El mtodo Simplex: es un algoritmo de solucin muy utilizado para resolver programas lineales.
Es la solucin algortmica inicial para resolver problemas de Programacin Lineal (PL). Este es
una implementacin eficiente para resolver una serie de sistemas de ecuaciones lineales.
Mediante el uso de una estrategia ambiciosa mientras se salta desde un vrtice factible hacia el
prximo vrtice adyacente, el algoritmo termina en una solucin ptima.
Un algoritmo: es una serie de pasos para cumplir con una tarea determinada.
Regin de Factibilidad Ilimitada: Tal y como se mencion anteriormente, aprenda que una
solucin ilimitada requiere una regin de factibilidad cerrada ilimitada. La situacin inversa de
-
2 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
este enunciado podra no ocurrir. Por ejemplo, el siguiente problema de PL tiene una regin de
factibilidad cerrada ilimitada, sin embargo, la solucin es limitada.
Redundancia Entre las Restricciones: Redundancia significa que algunas de las restricciones
no son necesarias dado que existen otras ms severas.
La teora de la produccin: implica el anlisis de un tipo especfico de restriccin sobre el
comportamiento de la empresa, el impuesto por la tecnologa, as como la investigacin de los
procesos de toma de decisiones de la empresa.
La tecnologa: es simplemente el medio (o el mtodo) por el cual uno o ms factores pueden
convertirse en produccin(es).
Las funciones de produccin: relacionan los factores (frecuentemente denominados factores de
produccin, o simplemente inputs) con la produccin. Se pueden representar grficamente o
matemticamente.
La mono tonicidad: simplemente significa que si una empresa aumenta el uso de un factor,
obtendr al menos tanta produccin.
La convexidad: implica que si tenemos dos combinaciones de factores para producir una cierta
cantidad de produccin, la combinacin de stos producir al menos tanta produccin.
-
3 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Programacin No Lineal
Programacin no lineal (PNL), Concepto: 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 un funcin objetivo a maximizar (o minimizar), cuando alguna de las
restricciones o la funcin objetivo no son lineales.
Una suposicin importante de programacin lineal es que todas sus funciones (funcin
objetivo y funciones de restriccin) son lineales. Aunque, en esencia, esta suposicin se cumple
para muchos problemas prcticos, con frecuencia no es as. De hecho muchos economistas han
encontrado que cierto grado de no linealidad es la regla, y no la excepcin, en los problemas de
planeacin econmica, por lo cual, muchas veces es necesario manejar problemas de
programacin no lineal, lo cual vamos a analizar enseguida.
De la manera general el problema de programacin no lineal consiste en encontrar:
X=(X1, X2, X3, X4, XN) para
Maximizar f(X), sujeta a
Gi(X)0,
Donde f(X) y gi(x) son funciones dadas de n variables de decisin.
-
4 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Definicin
Se puede expresar un problema de programacin no lineal (PNL)de la siguiente
manera:
Encuentre los valores de las variables que
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.
Los siguientes subconjuntos de (llamados intervalos) sern de particular inters:
-
5 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Y en forma anloga a las definiciones de la programacin lineal.
Definicin
La regin factible para el problema de programacin no lineal es el conjunto de
puntos que satisfacen las m restricciones de (1).
Definicin
Por supuesto, si son funciones lineales, entonces (1) ser un problema de programacin
lineal y puede resolverse mediante el algoritmo simplex
Un modelo de Programacin Lineal (PNL) es aquel donde las variables de decisin se
expresan como funciones no lineales ya sea en la funcin objetivo y/o restricciones de un modelo
-
6 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
de optimizacin. Esta caracterstica particular de los modelos no lineales permite abordar
problemas donde existen economas o deseconomas de escala o en general donde los supuestos
asociados a la proporcionalidad no se cumplen.
El problema de programacin no lineal
En ingeniera, economa, as como en otros campos, el analista se encuentra
habitualmente enfrentando con el problema de optimizar determinadas funciones, llamadas
funciones objetivo, que representan costes, rendimientos, etc., sujetas a ciertas restricciones. La
mayora de estos problemas de optimizacin, cuando se formulan de forma matemtica, se
pueden agrupar en una categora denominada problemas de programacin no lineal.
Problema de programacin No lineal general
En un sentido amplio, el problema de programacin no lineal general tiene como finalidad
encontrar un extremo de la funcin objetivo que est sujeta a restricciones de igualdad y/o
desigualdad, pudiendo ser stas, lineales y/o no lineales. Sin embargo, es habitual al hablar del
problema de programacin no lineal general, excluir especficamente de toda consideracin, los
siguientes casos especiales:
a) Cuando las variables estn restringidas a valores enteros (programacin no lineal entera).
b) Cuando las restricciones incluyen el parmetro tiempo formando ecuaciones diferenciales
(control optimo, optimizacin dinmica).
-
7 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Relacin entre el problema de programacin no lineal y el proceso real.
En determinados problemas de optimizacin, tales como el de mnimos cuadrados
(minimizar la suma de los cuadrados de las desviaciones entre la respuesta observada y la
prediccin), la elaboracin del problema de programacin no lineal se realiza fcilmente a partir
del problema fsico a resolver. Pero en otros casos esto no es as.
En la optimizacin de un proceso real los parmetros y/o las variables estn relacionados
por leyes fsicas, tales como conservacin de la masa o energa, que pueden ser incorporadas en
el problema de programacin o lneas como restricciones de igualdad.
Una de las caractersticas que hace que los problemas de optimizacin no lineal sean
muchos ms difciles de resolver que los problemas lineales, es que la solucin ptima no tiene
por qu estar en un punto extremo de la regin de factibilidad que determinan las restricciones
del problema. Puede encontrarse en los bordes de dicha regin o en su interior. Sin embargo, la
gran desventaja de los mtodos de optimizacin no lineales es que generalmente, encuentran un
ptimo local o relativo, mas no el ptimo global o absoluto.
Asimismo, otro problema grave que se presenta, es que no existe mtodo alguno en la
optimizacin no lineal, que detecte sistemticamente a todos los mnimos o mximos locales.
Ms bien estos se encuentran por el mtodo de prueba y error. Afortunadamente, para problemas
basados en procesos reales, la funcin objetivo tiene, normalmente, un buen comportamiento y
un nico extremo. Por lo tanto, para los casos ms prcticos, no es tan problemtico el uso de
procedimientos numricos, que proporcionan una solucin local.
-
8 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
TIPOS 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.
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.
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 las condiciones necesarias para
que una solucin sea ptima.
Los tipos de problemas de programacin no lineal son:
Los problemas de programacin no lineal se presentan de muchas formas distintas. Al contrario
del mtodo simplex para programacin lineal, no se dispone de un algoritmo que resuelva todos
-
9 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
estos tipos especiales de problemas. En su lugar, se han desarrollado algoritmos para algunas
clases (tipos especiales) de problemas de programacin no lineal.
Optimizacin no restringida.
Los problemas de optimizacin no restringida no tienen restricciones, por lo que la
funcin objetivo es sencillamente Maximizar f(X)
Sobre todos los valores X=(X1, X2,...., XN). Segn el repaso del apndice 3, la condicin
necesaria para que una solucin especfica X=X* sea ptima cuando f(X) es una funcin
diferenciable es:
f = 0 en X=X*, para j=1,2,..., n.
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 ecuaciones obtenidas al establecer las n derivadas
parciales iguales a cero. Por desgracia 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 simultnea. Qu se puede hacer en este caso? Las secciones
anteriores describen procedimientos algortmicos de bsqueda para encontrar X*, primero para
n=1 y luego para n>1. Estos procedimientos tambin tienen un papel importante en la solucin
de varios tipos de problemas con restricciones, que se describen en seguida. La razn es que
muchos algoritmos para problemas restringidos estn construidos de forma que se adaptan a xj
versiones no restringidas del problema en un parte de cada iteracin.
-
10 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Cuando una variable Xj tiene una restriccin de no negatividad, xj=>0, la condicin
necesaria (y tal vez) suficiente anterior cambia ligeramente a f
Para cada j de este tipo. Esta condicin se ilustra en l figura siguiente, donde la solucin ptima
de un problema con una variable es X=0 aun cuando la derivada ah es negativa y no cero.
Como este ejemplo tiene una funcin cncava para maximizar sujeta a una restriccin de
no negatividad, el que su derivada sea menor a 0 en X=0, es una condicin necesaria y suficiente
para que x=0 sea ptima.
Un problema que tiene algunas restricciones de no negatividad y que no tiene
restricciones funcionales es un caso especial (m=0) de la siguiente clase de problemas.
-
11 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Optimizacin linealmente 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 gi(X) son lineales, pero la funcin objetivo es no lineal.
-
12 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
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. Se han desarrollado varios
algoritmos especiales basados en una extensin del mtodo simplex para analizar la funcin
objetivo no lineal. Un caso especial importante descrito a continuacin es la programacin
cuadrtica.
Programacin cuadrtica
De nuevo los problemas de programacin cuadrtica 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.
Se han desarrollado muchos algoritmos para este caso, con la suposicin adicional de que
f(X) es cncava. La programacin cuadrtica es muy importante, en parte porque las
formulaciones de este tipo surgen de manera natural en muchas aplicaciones. Por ejemplo, el
problema de la seleccin de una cartera con inversiones riesgosas se ajusta a este formato. Sin
embargo, otra razn por la que es importante es que al resolver problemas generales de
optimizacin linealmente restringida se puede obtener la solucin de una sucesin de
aproximaciones de programacin cuadrtica.
Programacin convexa.
La programacin convexa abarca una amplia clase de problemas, entre ellos como casos
especiales, estn los tipos anteriores cuando f(x) es cncava. Las suposiciones son:
-
13 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
1. F(X) es cncava.
2. Cada una de las gi(X) es convexa.
Como se dijo anteriormente, estas suposiciones son suficientes para asegurar que un
mximo local es un mximo global, en secciones posteriores se ver que la condiciones
necesarias y suficientes para obtener tal solucin optima son una generalizacin natural de la
condiciones que se acaban de exponer para la optimizacin no restringida y su extensin a la
inclusin de restricciones de no negatividad.
Programacin separable.
La programacin separable es un caso especial de programacin convexa, en donde las
suposiciones adicionales es:
3.- todas las funciones f(X) y gj(X) son funciones separables.
Una funcin separable es una funcin en la que cada trmino incluye una sola variable,
por lo que la funcin se puede separar en una suma de funciones de variables individuales. Por N
ejemplo, si f(X) es una funcin separable, se puede expresar como F(X)= fj(Xj), en donde
cada fj(Xj) incluye solo los trminos con Xj. En la terminologa de programacin lineal, los
problemas de programacin separable satisfacen las suposiciones de auditividad pero no las de
proporcionalidad (para funciones no lineales). Para ilustrar, la funcin objetivo considerada en la
siguiente figura:
F(X1, X2)=126X19x21 + 182X213X22
Es una funcin separable porque puede ser expresada como
-
14 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
F(X1, X2)= F(X1) + F(X2)
Donde F1(X1)= 126X19x21 y F(X2)= 182X213X22
Son cada una funciones de una sola variable x1y x2, respectivamente. Usando el mismo
razonamiento, se puede verificar que la funcin considerada en la figura siguiente, tambin es
una funcin separable.
Es importante distinguir estos problemas de otros de programacin convexa, pues
cualquier problema de programacin separable se puede aproximar muy de cerca mediante uno
de programacin lineal y, entonces, se puede aplicar el eficiente mtodo simplex.
Programacin no convexa.
La programacin no convexa incluye todos los problemas de programacin no lineal que
no satisfacen las suposiciones de programacin convexa. En este caso, aun cuando se tenga xito
en encontrar un mximo local, no hay garanta de que sea tambin un mximo global. Por lo
tanto, no se tiene un algoritmo que garantice encontrar una solucin optima para todos estos
-
15 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
problemas; pero si existen algunos algoritmos bastantes 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. Ciertos tipos de problemas de
programacin no convexa se pueden resolver sin mucha dificultad mediante mtodos especiales.
Dos de ellos, de gran importancia.
Programacin geomtrica.
Cuando se aplica programacin no lineal a problemas de diseo de ingeniera, muchas
veces la funcin objetivo y las funciones de restriccin toman la forma
En donde
Tales casos, las ci y aij representan las constantes fsicas y las xj son las variables de
diseo. Estas funciones por lo general no son ni cncavas ni convexas, por lo que las tcnicas de
programacin convexa no se pueden aplicar directamente a estos problemas de programacin
geomtrica. Sin embargo, existe un caso importante en el que el problema se puede transformar
en un problema de programacin convexa equivalente. En este caso es aquel en el que todos los
coeficientes c1 en cada funcin son estrictamente positivos, es decir, las funciones son
polinomios positivos generalizados (ahora llamados posinomiales), y la funcin objetivo se tiene
-
16 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
que minimizar. El problema equivalente de programacin convexa con variables de decisin y1,
y2,..., yn se obtienen entonces al establecer
En todo el modelo original. Ahora se puede aplicar un algoritmo de programacin convexa.
Optimizacin de programacin no lineal con Solver
El algoritmo utilizado por el Solver es el Gradiente Reducido Generalizado (GRG), en la
versin GRG2, cuya estructura matemtica puede ser analizada en Abadie(1978); Lasdon,
Waren, Jain y Ratner(1978); Lasdon y Waren(1978); y Ros(1988). Bsicamente, al igual que
otros algoritmos de programacin no lineal, parte de una solucin factible conocida como punto
inicial. El algoritmo intenta entonces moverse, a partir de este punto, en una direccin a travs de
la regin factible, de tal forma que el valor de la funcin objetivo mejore. Tomando un salto o
movimiento determinado en dicha direccin factible, se pasa a una nueva solucin factible
mejorada. De nuevo, el algoritmo identifica una nueva direccin factible, si existe, y un salto
determinado avanzando hacia una nueva solucin factible mejorada. El proceso contina hasta
que el algoritmo alcanza un punto en el cual no existe una direccin factible para moverse que
mejore el valor de la funcin objetivo. Cuando no hay posibilidad de mejora, o el potencial para
tal mejora es arbitrariamente pequeo, el algoritmo finaliza. Ahora bien, en ese momento la
solucin es un ptimo local, y por tanto no necesariamente global. En este sentido, es preciso
-
17 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
tener en cuenta dos caractersticas de las soluciones obtenidas al resolver un programa no lineal
con Solver:
1. El algoritmo puede finalizar en un ptimo local que puede no ser el ptimo global del
problema.
2. El ptimo local en que finaliza el algoritmo depende del punto inicial.
Si bien la posibilidad de terminar en un ptimo local no es deseable, en el caso de la
programacin entera ya habamos comentado la posibilidad de aceptar soluciones sub ptimas si
estaban dentro del grado de tolerancia aceptable. Desgraciadamente, en los programas no lineales
no se puede determinar fcilmente el grado de alejamiento entre el ptimo local y el global, dado
que no existe un mtodo genrico para obtener cotas del valor de la funcin objetivo.
Sin embargo, muchos programas no lineales tienen ptimos locales nicos que, por definicin,
necesariamente deben ser globales. Por ejemplo, las siguientes condiciones garantizan, si existe,
que el ptimo es global:
a. Funcin objetivo de mximo y cncava, o el logaritmo de la funcin objetivo cncava,
con restricciones lineales.
b. Funcin objetivo de mnimo y convexa, con restricciones lineales.
No obstante, en general, no conoceremos si la solucin obtenida es un ptimo global.
Como consecuencia, se suele intentar la prueba de iniciar el algoritmo desde diferentes puntos
para determinar si el problema tiene diferentes soluciones ptimas. Este procedimiento suele
revelar la existencia de un determinado ptimo global, si existe, pero no es un mtodo de total
fiabilidad.
-
18 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Dado el carcter de las soluciones de los programas no lineales es importante tener en
cuenta los mensajes que proporciona el Solver:
a. Solver ha encontrado la solucin. Todas las restricciones y condiciones de
optimalizacin estn satisfechas. En este caso habr encontrado un ptimo local,
que no necesariamente ser global. Matemticamente, este mensaje indica que las
condiciones de Karush-Kuhn-Tucker para ptimos locales han sido satisfechas.
Salvo en un problema con un solo ptimo global, se debera ejecutar el Solver
desde diferentes puntos iniciales para incrementar la seguridad sobre la globalidad
del ptimo.
b. Solver ha convergido hacia la solucin actual. Todas las restricciones estn
satisfechas. En este caso el valor de la funcin objetivo cambia muy lentamente en
las ltimas iteraciones. La opcin Convergencia controla este proceso. El
algoritmo termina si el cambio relativo en el valor de la funcin objetivo durante
varias iteraciones es menor que el factor de convergencia. Si se intuye que Solver
finaliza demasiado rpido o que el punto obtenido no es ptimo, ser preciso
reducir la convergencia para evitar soluciones subptimas.
c. Solver no puede mejorar la solucin actual. Todas las restricciones estn
satisfechas. Este mensaje indica que el modelo presenta degeneracin y que el
algoritmo ha entrado en un ciclo. La degeneracin puede ser evitada en muchos
casos eliminando restricciones redundantes.
Tambin es importante tener en cuenta que Solver presenta dificultades en muchos
casos para empezar a aplicar el algoritmo cuando se inicializa en un punto de valor nulo para
todas las variables. Por tanto, es aconsejable comenzar por una solucin no nula. Adems, en la
-
19 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
mayora de los casos, cuanto ms cercanos sean los valores iniciales al ptimo ms rpido ser el
proceso de resolucin.
El proceso de solucin del GRG, al igual que otros muchos algoritmos de programacin
no lineal, calcula valores de la primera derivada parcial de la funcin objetivo y de las
restricciones en cada iteracin. La opcin Derivadas fija cmo se realiza dicho clculo. La
alternativa progresiva considera conjuntamente el punto de la iteracin anterior y el actual, con
lo cual reduce el tiempo de computacin requerido por la diferenciacin finita (este tiempo se
estima que puede llegar a suponer el 50 por ciento del tiempo total de resolucin). La opcin
central tan solo considera el punto actual, lo cual conlleva un mayor tiempo de clculo que
puede sin embargo resultar adecuado si las derivadas cambian rpidamente ya que permite
realizar un menor nmero de iteraciones. En problemas cuadrticos, la diferenciacin central
produce valores de las derivadas exactos, lo cual permite mejorar la exactitud del resultado y
reducir el nmero de iteraciones, aunque stas tendrn un tiempo de ejecucin que puede llegar a
duplicar el de diferenciacin progresiva.
El mtodo del GRG realiza asimismo una reduccin del problema original a otro sin
restricciones resolviendo un sistema de ecuaciones para ciertas variables bsicas en trminos del
resto no bsicas. Entonces, se elige una direccin de bsqueda (un vector n-dimensional donde n
es el nmero de variables no bsicas) a lo largo de la cual se establece una mejora de la funcin
objetivo. La opcin Hallar por fija el criterio para determinar esta direccin de bsqueda. El
mtodo de Newton consiste realmente en el mtodo cuasi-Newton BFGS (Broyden, Fletcher,
Goldfarb, Shanno). En lugar de utilizar la matriz hessiana, utiliza una aproximacin de dicha
matriz, lo cual requiere una importante capacidad de almacenaje que sin embargo se compensa
por los buenos resultados que genera. La alternativa es el mtodo del gradiente conjugado, que
-
20 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
no requiere el almacenamiento de la matriz hessiana sino tan solo de algunos vectores.
Normalmente requiere de ms iteraciones que el mtodo cuasi-Newton, siendo recomendable en
el caso de problemas de gran tamao. En el caso del Solver, la eleccin de una u otra opcin no
resulta relevante dado que es capaz de cambiar automticamente de uno a otro mtodo en
funcin de la capacidad de almacenamiento disponible, sea cual sea la opcin elegida.
Por ltimo, una vez elegida la direccin, el algoritmo realiza una bsqueda a travs de
dicha direccin variando la amplitud del desplazamiento para la mejora del objetivo reducido.
Las estimaciones iniciales de los valores de las variables que experimentan un cambio
tienen un impacto significativo sobre la efectividad del mtodo. La opcin Estimacin indica
cmo se realiza dicho proceso. La alternativa lineal utiliza una extrapolacin lineal a partir de la
tangente a la funcin objetivo reducido. La alternativa cuadrtica extrapola a travs de un ajuste
cuadrtico de dicha funcin en el punto actual. Salvo que la funcin objetivo reducida se ajuste a
un modelo cuadrtico, y si no se tiene ninguna informacin especial a cerca del comportamiento
de la misma, la alternativa lineal es la ms segura, si bien la ms lenta.
Construccin de un problema de optimizacin.
La introduccin del problema de optimizacin, se puede sintetizar en cuatro fases:
a) Organizar los datos del modelo en la hoja de trabajo. Si bien son mltiples las posibles
formas de disear el formato y colocacin de los datos de entrada, es recomendable
seguir los mismos principios que en toda aplicacin con hoja de clculo: pensar en la hoja
como un informe que explique el problema, identificar los datos introducidos, colocar
comentarios, introducir todos los datos iniciales del problema y construir a partir de los
-
21 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
mismos el modelo de optimizacin con el objeto de facilitar el anlisis de sensibilidad,
utilizar tcnicas de diseo para presentar el modelo, etc.
b) Reservar una celda para cada variable de decisin. Siguiendo el esquema de un programa
matemtico, es recomendable que inicien la hoja de trabajo. Debern estar vacas o con
datos numricos, nunca frmulas, y a ser posible con notas o comentarios.
c) Crear una celda para la funcin objetivo prximo a las que recogen las variables. La
frmula que incorpora deber crearse a partir de las celdas descritas en el punto anterior.
d) Para cada restriccin, crear una celda que recoja la frmula de su parte izquierda, y a la
derecha de dicha celda colocar el trmino independiente.
Datos del modelo de trabajo
Tema: La rentabilidad.
La rentabilidad Rt, se calcula mediante la expresin conformada por los siguientes
componentes:
La rentabilidad: Rt=
Donde
es la variacin del precio de la accin en el mercado accionario
Pt= es el precio de la accin en el momento t. Pt-1= es el precio de la accin en el
mercado en un perodo anterior. Dt: es el pago de dividendos por cada accin. Ct: Es la
prima por nueva emisin de acciones.
-
22 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
El precio de la accin se calcula a travs del precio promedio ponderado diario
(PPP), utilizando la informacin de cantidad y volumen del mercado al contado
transmitido por la bolsa en la que se encuentra inscrita la accin.
Dnde: Vi = Volumen de acciones transadas en la ronda "i" de negociacin en el da. Pi =
Precio de la accin transada en la ronda "i" de negociacin. i = 1, 2,3,..., N nmero de rondas
de negociacin.
CONCLUSIN
A lo largo del estudio de este captulo acerca de la Programacin No Lineal, podemos concluir
que es una parte de la Investigacin Operativa cuya misin es proporcionar una serie de
resultados y tcnicas tendentes a la determinacin de puntos ptimos para una funcin (funcin
objetivo) en un determinado conjunto (conjunto de oportunidades), donde tanto la funcin
objetivo, como las que intervienen en las restricciones que determinan el conjunto de
oportunidades pueden ser no lineales.
La programacin lineal ha demostrado ser una herramienta sumamente poderosa, tanto en la
modelizacin de problemas de la vida real como en la teora matemtica de amplia aplicacin.
Sin embargo, muchos problemas interesantes de optimizacin son no lineales. El estudio de estos
problemas implica una mezcla diversa de algebra lineal, calculo multivariado, anlisis numrico
y tcnicas de computacin. Entre las reas especiales importantes se encuentra el diseo de
-
23 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
algoritmos de computacin (incluidas las tcnicas de puntos interiores para programacin lineal),
la geometra y el anlisis de conjuntos convexos y funciones, y el estudio de problemas
especialmente estructurados, tales como la programacin cuadrtica. La optimizacin no lineal
proporciona informacin fundamental para el anlisis matemtico, y se usa extensamente en las
ciencias aplicadas (en campos tales como el diseo de ingeniera, el anlisis de regresin, el
control de inventario, y en la exploracin geofsica).
REFERENCIAS BIBLIOGRAFICAS
Ackoff, Sasieni, Fundamentos de investigacin de operaciones, Mxico, Limusa, 1982.
Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover
Publishing.
Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and
algorithms. John Wiley & Sons.
Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific.
Gallagher, Charles A., Hugh J. Watson, Mtodos cuantitativos para la toma de decisiones
en administracin, EUA, McGraw-Hill, 1980.
Hopeman, Richard J., Administracin de produccin y operaciones, Mxico, Cecsa,
1987.
Kaufmann, A., Mtodos y modelos de la investigacin de operaciones, Mxico,
Continental, 1980.
-
24 PROGRAMACIN NO LINEAL
UNIVERSIDAD ESTATAL DE GUAYAQUIL | INVESTIGACIN DE OPERACIONES
Libro de INVESTIGACIN DE OPERACIONES DE HAMDY A.TAHA.
Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer.
Schroeder, Roger G., Administracin de operaciones, concepto y casos contemporneos,
Mxico, McGraw Hill, 2005.
Schroeder, Roger G., Administracin de operaciones, toma de decisiones en la funcin de
operaciones, Mxico, McGraw-Hill, 1983.
Thierauf, Robert J., Toma de decisiones por medio de investigacin de operaciones,
Mxico, Limusa, 1983.