Presentacin de PowerPoint

CURSO: INVESTIGACION OPERATIVA IIALUMNA: AMADO SALVADOR GINA V.MODELO DE PROGRAMACION NO LINEAL

PROGRAMACION NO LINEALINTRODUCCIONVENTAJASCARACTERISTICASFORMULACIN Y RESOLUCIN DE MODELOS MATEMTICOS CON RESTRICCIONES U OBJETIVOS NO LINEALES MTODO DE RECURRENCIA TIPOS DE PROBLEMAS DE PROGRAMACION NO LINEALINVESTIGACION OPERATIVA IIINTRODUCCION

La programacin no lineal y 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.

INVESTIGACION OPERATIVA IIVENTAJAS DE LA PROGRAMACION NO LINEALLas ventajas ms importantes de la programacin no lineal son dos:

INVESTIGACION OPERATIVA IITipos De Problemas De Programacion NoLinealINVESTIGACION OPERATIVA II Optimizacin no restringida. Optimizacin linealmente restringida. Programacin cuadrtica Programacin convexa. Programacin separable. Programacin no convexa. Programacin geomtrica. Programacin fraccional.

OPTIMIZACION NO RESTRINGIDAINVESTIGACION OPERATIVA IILos problemas de optimizacin no restringidanotienen restricciones, por lo que la funcin objetivo es sencillamenteMaximizar f(x)sobretodoslos valores x= (x1,x2,,xn). la condicinnecesariapara que una solucin especfica x = x* sea ptima cuando f(x) es una funcin diferenciable es

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.OPTIMIZACION NO RESTRINGIDAINVESTIGACION OPERATIVA IILa razn de estos procedimientos es que muchos algoritmos para problemasrestringidosestn construidos de forma que se adaptan a versionesno restringidasdel problema en una parte de cada iteracin.Cuando una variable Xj tiene una restriccin de no negatividad, x- > 0, la condicin necesaria (y tal vez) suficiente anterior cambia ligeramente a

para cada j de este tipo. Como este ejemplo tiene una funcin cncava para maximizar sujeta a una restriccin de no negatividad, el que su derivada sea menor o igual a 0 en # = 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.OPTIMIZACION LINEALMENTE RESTRINGIDAINVESTIGACION OPERATIVA II

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 g (x) son lineales, pero la funcin objetivo es no lineal. El problema se simplifica mucho si slo 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 smplex para analizar la funcin objetivo no lineal. Un caso especial importante descrito a continuacin es la programacin cuadrtica.PROGRAMACION CUADRATICAINVESTIGACION OPERATIVA IIDe nuevo los problemas de programacin cuadrtica tienen restricciones lineales, pero ahora la funcin objetivo /(x) debe ser cuadrtica. Entonces, la nica diferencia entre stos y un problema de programacin lineal es que algunos trminos de la funcin objetivo incluyen elcuadradode una variable o elproductode dos variables.

PROGRAMACION CONVEXAINVESTIGACION OPERATIVA II

La programacin convexa abarca una amplia clase de problemas, entre ellos como casos especiales, estn todos los tipos anteriores cuando /(x) es cncava. Las suposiciones son:

f(x) es cncava.Cada una de las g(x) es convexa

PROGRAMACION SEPARABLEINVESTIGACION OPERATIVA IILaprogramacin separablees un caso especial de programacin convexa, en donde la suposicin adicional esTodas las funciones f(x) yg(x)son funciones separables.Una funcin separable es una funcin en la quecada trminoincluyeuna sola variable, por lo que la funcin se puedesepararen una suma de funciones de variables individuales. Por ejemplo, si f(x) es una funcin separable, se puede expresar como

PROGRAMACION SEPARABLEINVESTIGACION OPERATIVA IIson cada tina funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la funcin considerada en la figura 13.7 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 smplex.

PROGRAMACION NO CONVEXAINVESTIGACION OPERATIVA II

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 ptima para todos estos problemas; pero s 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. Ciertos tipos especficos de problemas de programacin no convexa se pueden resolver sin mucha dificultad mediante mtodos especiales. Dos de ellos, de gran importancia, se presentarn ms adelante.PROGRAMACION GEOMETRICAINVESTIGACION OPERATIVA IICuando 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 tales casos, lasciy aty representan las constantes fsicas y lasx}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 geo- mtrica.Sin embargo, existe un caso importante en el que el problema se puede transformar en un problema de programacin convexa equivalente. Este caso es aquel en el quetodoslos coeficientescen cada funcin son estrictamente positivos, es decir, las funciones sonpolinomios positivos generalizados(ahora llamados posinomiales), y la funcin objetivo se tiene que minimizar

PROGRAMACION GEOMETRICAINVESTIGACION OPERATIVA II. El problema equivalente de programacin convexa con variables de decisin yx,y2,, ynse obtiene entonces al establecer en todo el modelo original. Ahora se puede aplicar un algoritmo de programacin convexa. Se ha desarrollado otro procedimiento de solucin para resolver estos problemasde programacin posinomial,al igual que para problemas de programacin geomtrica de otros tipos.

PROGRAMACION FRACCIONALINVESTIGACION OPERATIVA II

Suponga que la funcin objetivo se encuentra en la forma de una fraccin, esto es, la razn o cociente de dos funciones,

Estos problemas de programacin fraccional surgen, por ejemplo, cuando se maximiza la razn de la produccin entre las horas-hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de rendimiento), o el valor esperado dividido entre la desviacin estndar de alguna medida de desempeo para una cartera de inversiones (rendimiento/riesgo). Se han formulado algunos procedimientos de solucin especiales1 para ciertas formas de f1(x) y f2 (x)

PROGRAMACION FRACCIONALINVESTIGACION OPERATIVA II

Cuando se puede hacer, el enfoque ms directo para resolver un problema de programacin fraccional es transformarlo en un problema equivalente de algn tipo estndar que disponga de un procedimiento eficiente. Para ilustrar esto, suponga quef(x)es de la forma deprogramacin fraccional lineal

dondecydson vectores rengln,xes un vector columna yc0ydQson escalares. Tambin suponga que las funciones de restriccing(x)son lineales, es decir, las restricciones en forma matricial sonAx < byx > 0.Con algunas suposiciones dbiles adicionales, el problema se puede transformar en un problema equivalente deprogramacin linealsi se establece que se puede resolver con el mtodo smplex. En trminos generales, se puede usar el mismo tipo de transformacin para convertir un problema de programacin fraccional con/(x)cncava,f2(x)convexa yg(x)convexas, en un problema equivalente de programacin convexa.

PROGRAMACION FRACCIONALINVESTIGACION OPERATIVA II

CARACTERISTICAS DE LOS PROBLEMAS NO LINEALESLos problemas no lineales se caracterizan por tener relaciones no lineales; es decir, no existe una relacin directa y proporcional entre las variables que intervienen. Los problemas de programacin no lineal, tambin son llamados curvilneos, ya que el rea que delimita las soluciones factibles en un grfico se presenta en forma de curva. INVESTIGACION OPERATIVA II

CARACTERISTICAS DE LOS PROBLEMAS NO LINEALESLa funcin objetivo en la programacin no lineal, puede ser cncavo o convexo. Es cncavo cuando se trata de maximizar utilidades, contribuciones, etc. Es convexo cuando trata de minimizar recursos, costos, etc. Los problemas que contienen restricciones lineales, se resuelven de una forma ms sencilla que los problemas con restricciones no lineales.

INVESTIGACION OPERATIVA II

FORMULACIN Y RESOLUCIN DE MODELOS MATEMTICOS CON RESTRICCIONES U OBJETIVOS NO LINEALES. Una forma de resolver los problemas de programacin no lineal es convirtiendo los problemas de forma tal, que se pueda aplicar la programacin lineal. Los problemas de programacin no lineal abarcan problemas con funcin objetivo no lineal y restricciones no lineales, como se presenta en el ejemplo siguiente: INVESTIGACION OPERATIVA II

Como se puede observar, tanto la funcin objetivo como la restriccin presentan variables de segundo grado (potencia cuadrtica); por lo tanto, son no lineales. Para comenzar con la resolucin de un problema no lineal se representa la restriccin en un grfico, para ello, se utiliza el mismo procedimiento empleado en el mtodo grfico de programacin lineal (vase tema 2.3 Algoritmos de solucin).

INVESTIGACION OPERATIVA IIConsiderando la desigualdad 3 X2 + 2Y < 13, 950, se le asigna un valor de 0 a la variable Y, para encontrar el punto de X en el grfico. As mismo, se asigna un valor de 0 a la variable X, para encontrar el punto Y en el grfico: Despejando la variable X se procede de la forma siguiente:

INVESTIGACION OPERATIVA IIPara despejar la variable Y se procede como sigue:

INVESTIGACION OPERATIVA IIDe acuerdo con el procedimiento por el mtodo grafico de programacin lineal, se debe dibujar en un plano cartesiano cada una de las restricciones formuladas matemticamente, de esa forma se representa como se muestra en el grafico siguiente la restriccin considerada para este ejemplo:

INVESTIGACION OPERATIVA IIComo podemos observar, la restriccin se representa por una curva convexa, por lo que la funcin objetivo es cncava. Para graficar la funcin objetivo, se asigna un valor cualquiera a la variable X y a la contribucin; para este ejemplo, se asign un valor a X=40 y una contribucin de $1,000. Sustituyendo el valor de X en la funcin objetivo, se puede encontrar el valor de la variable Y, como se presenta a continuacin:

INVESTIGACION OPERATIVA IIUna vez obtenidos los valores de X, Y para la funcin objetivo, se pueden representar en un grfico y prolongarlo hasta tocar el punto ms lejano del rea de soluciones factibles, para hallar la solucin ptima.

INVESTIGACION OPERATIVA IILa solucin ptima para este ejemplo es X=30 y Y=75; sin embargo, puede calcularse matemticamente. Para ello, se debe encontrar la derivada de la funcin objetivo, como se muestra a continuacin: Se resuelve la ecuacin de la funcin objetivo para encontrar a travs de un procedimiento matemtico el valor de las variables, despejando las variables mediante el uso del lgebra y aplicando el clculo diferencial, como sigue:

INVESTIGACION OPERATIVA IIUna vez encontrada la derivada de la funcin objetivo, se procede a encontrar la derivada de la restriccin, como se muestra a continuacin:

INVESTIGACION OPERATIVA IIEl siguiente paso consiste en igualar los resultados de las dos derivadas, la derivada de la restriccin con la derivada de la funcin objetivo.

INVESTIGACION OPERATIVA IIEnseguida, se sustituye la ecuacin Y resultante en la ecuacin original de restriccin.

INVESTIGACION OPERATIVA IICon el resultado anterior de la ecuacin Y, sustituida en la ecuacin original de restriccin, se debe asignar un valor a X. Como se observa en el grfico anterior, la solucin ptima es X =30, por lo que sustituiremos ese valor en la ecuacin resultante:

INVESTIGACION OPERATIVA IIComo el valor de X=30 satisface la ecuacin, se puede considerar ese valor como un valor ptimo para el problema. Ese mismo valor puede sustituirse en la ecuacin de restriccin original, para encontrar el valor ptimo de la variable Y.

INVESTIGACION OPERATIVA IICon lo anterior, se tienen los valores ptimos de X e Y, por lo que ahora se procede a calcular la contribucin ptima, sustituyendo los valores encontrados en la funcin objetivo: INVESTIGACION OPERATIVA II

Se puede concluir que la empresa necesita producir 30 unidades del producto X y 75 unidades del producto Y para tener una contribucin mxima de $984.MTODO DE RECURRENCIA A menudo, las empresas tienen operaciones que son recurrentes; es decir, que vuelven a ocurrir una y otra vez, con diferentes valores cuantitativos dependiendo del tiempo en que suceden. Para estos casos, podemos predecir qu ocurrir en el futuro, si conocemos con exactitud los precedentes o antecedentes histricos. Por ejemplo: una empresa realiza un depsito de $5,000 en su cuenta bancaria, con intereses anuales del 10% y quiere conocer cunto dinero tendr en diez aos. Para conocer el monto en veinte aos, se debe formular un algoritmo, denominado relacin de recurrencia, que describa el problema en cuestin. Con clculos simples, sabemos que los montos son de: INVESTIGACION OPERATIVA II

Como se puede observar, calcular uno por uno es un proceso tedioso, por lo que es necesario formular una relacin de recurrencia, que con cambiar un dato, nos arroje el resultado deseado. Para este ejemplo, se aprecia que todas las ecuaciones tienen caractersticas comunes, que se pueden representar como:

Pn = Monto que se tiene en el ao nPn = Pn + (0.11) (Pn), entonces, el monto para 2 aos esP2= 5,500.00 = 5,500.00 + (5,500.00) (0.10) = $ 6,050.00INVESTIGACION OPERATIVA II

Para simplificar las operaciones en cada ecuacin, se puede realizar otro algoritmo:

P2 = 5,500.00 (1.10) = $ 6,050.00 P3 = 6,050.00 (1.10) = $ 6,655.00

Sin embargo, todava se tiene que calcular ao por ao, hasta llegar al ao 20, que es el que le interesa a la empresa. Se aprecia que 1.11, es constante para todos los aos, por lo que la relacin de recurrencia, queda de la siguiente forma:

Pn = 1000 * (1.11)n Para el ao 2 = P2 = 5,000.00 (1.10)2 = $ 6,050.00 Para el ao 20 = P20 = 5,000.00 (1.10)20 = $ 33,637.50

De esta forma, se pueden crear relaciones de recurrencia para cada problema de la empresa, siempre que se conozcan los precedentes y las operaciones ocurran recurrentemente. INVESTIGACION OPERATIVA II