ÍNDICE

ÍNDICE....................................................................................................................................................................1

I. INTRODUCCIÓN...............................................................................................................................................2

3.1 PLANTEAMIENTO DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL.......................................2

PROBLEMA DE MEZCLA DE PRODUCTOS CON ELASTICIDAD EN LOS PRECIOS.......................................................2TIPOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL......................................................................3OPTIMIZACIÓN NO RESTRINGIDA...........................................................................................................................3OPTIMIZACIÓN LINEALMENTE RESTRINGIDA.........................................................................................................4PROGRAMACIÓN CUADRÁTICA..............................................................................................................................4

3.2 OPTIMIZACIÓN CLÁSICA...........................................................................................................................4

3.2.1. MÁXIMOS Y MÍNIMOS (PROBLEMAS DE EXTREMOS NO RESTRINGIDOS)..............................................43.2.2 PUNTOS DE INFLEXIÓN.........................................................................................................................5

3.3 PROBLEMAS NO RESTRINGIDOS.............................................................................................................6

OPTIMIZACIÓN NO RESTRINGIDA DE UNA VARIABLE..........................................................................6OPTIMIZACIÓN NO RESTRINGIDA DE VARIAS VARIABLES.................................................................7

Procedimiento de búsqueda del gradiente.......................................................................................................83.3.1 MULTIPLICADORES DE LAGRANGE...................................................................................................83.3.2 INTERPRETACIÓN ECONÓMICA........................................................................................................10

CONCLUSIONES Y RECOMENDACIONES..................................................................................................11

BIBLIOGRAFÍA....................................................................................................................................................11

1

UNIDAD IIIPROGRAMACIÓN NO LINEAL

I. INTRODUCCIÓN

La programación lineal tiene un papel fundamental en la investigación de operaciones (IO). Una suposición importante de programación lineal es que todas sus funciones (función objetivo y funciones de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para muchos problemas prácticos, con frecuencia no es así. De hecho, muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas de planeación económica, por lo cual, muchas veces es necesario manejar problemas de programación no lineal, que es el área que se examinará en seguida.De una manera general, el problema de programación no lineal consiste en encontrar x=(x1,x2,...,xn) para

Maximizar f(x), sujeta agi(x)<=bi, para i =1, 2,...,m,

y x>=0,

Donde f(x) y las gi(x) son funciones dadas de n variables de decisión.No se dispone de un algoritmo que resuelva todos los problemas específicos que se ajustan a este formato. Sin embargo, se han hecho grandes logros en lo que se refiere a algunos casos especiales importantes de este problema, haciendo algunas suposiciones sobre las funciones, y la investigación sigue muy activa. Esta área es amplia y aquí no se cuenta con el espacio suficiente para un estudio completo. Se presentarán algunos ejemplos de aplicación y después se introducirán algunas ideas básicas para resolver ciertos tipos importantes de problemas de programación no lineal.

3.1 PLANTEAMIENTO DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL

Los siguientes ejemplos ilustran unos cuantos de los muchos tipos importantes de problemas a los que se ha aplicado la programación no lineal.

Problema de mezcla de productos con elasticidad en los preciosEn problemas de mezcla de productos, la meta es determinar la mezcla óptima de los niveles de producción para los productos de una empresa, dadas las limitaciones sobre los recursos necesarios para producirlos, con el objeto de maximizar la ganancia total de la empresa. En algunos casos existe una ganancia unitaria fija asociada a cada producto, con lo que la función objetivo que se obtiene es lineal. Sin embargo, en muchos problemas de mezcla de productos, ciertos factores introducen no linealidades en la función objetivo.Por ejemplo, un fabricante grande puede encontrar elasticidad en los precios mediante los cuales la cantidad que se puede vender de un producto tiene una relación inversa con el precio cobrado. Así, la curva precio-demanda para un producto puede parecerse a la mostrada en la figura, donde p{x) es el precio que se necesita para poder vender x unidades. Entonces la ganancia de la empresa por producir y vender x unidades es el ingreso por las ventas xp(x) menos los costos de producción y distribución. Por lo tanto, si el costo unitario de producir y distribuir el artículo está fijo en el, entonces la ganancia de la empresa por producir y vender x unidades está dada por una función no lineal

P(x)=xp(x)-cx,

2

Si cada uno de los n productos de la empresa tiene una función parecida para la ganancia, por ejemplo Pj (xj) por producir y vender Xj unidades del producto f(j=1,2,...,n), entonces la función objetivo global es

, una suma de funciones no lineales.

Otra razón por la que pueden surgir no linealidades en la función objetivo es que el costo marginal de producir otra unidad más de un producto dado puede variar con el nivel de producción. Por ejemplo, el costo marginal puede disminuir cuando aumenta el nivel de producción, gracias al efecto de curva de aprendizaje (mayor eficiencia con más experiencia). Por otro lado, pueden aumentar a causa de ciertas medidas especiales, como tiempos extra o instalaciones de producción más costosas, necesarias para aumentar la producción.La no linealidad también puede surgir en las funciones de restricción en forma bastante parecida. Por ejemplo, si existe una restricción de presupuesto sobre el costo total de producción, la función de costo será no lineal si el costo marginal de producción varía como se acaba de describir. Para restricciones sobre otro tipo de recursos, será no lineal siempre que el uso del recurso correspondiente no sea estrictamente proporcional a los niveles de los respectivos productos.

TIPOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL

Los problemas de programación no lineal se presentan de muchas formas distintas. Al contrario del método símplex para programación 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 programación no lineal. Se introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.

Optimización no restringidaLos problemas de optimización no restringida no tienen restricciones, por lo que la función objetivo es sencillamenteMaximizar f(x)Sobre todos los valores x= (x1, x2,…, xn). La condición necesaria para que una solución específica x= x* sea óptima cuando f(x) es una función diferenciable es

en x= x* para j= 1, 2,..., n.

3

Cuando f(x) es cóncava, esta condición también es suficiente, con lo que la obtención 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 también, en cuyo caso es poco probable que se pueda obtener una solución analítica simultánea

Cuando una variable X: tiene una restricción de no negatividad, x¡ >= 0, la condición necesaria (y tal vez) suficiente anterior cambia ligeramente a

donde a) en x = x* si xj*=0 y b) = 0 en x = x* si xj*>0

para cada j de este tipo. Donde la solución óptima de un problema con una sola variable es x = 0 aun cuando la derivada ahí es negativa y no cero. Como este ejemplo tiene una función cóncava para maximizar sujeta a una restricción de no negatividad, el que su derivada sea menor o igual a 0 en x = 0, es una condición 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.

Optimización linealmente restringidaLos problemas de optimización linealmente restringida se caracterizan por restricciones que se ajustan por completo a la programación lineal, de manera que todas las funciones de restricción g i(x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho si sólo se tiene que tomar en cuenta una función no lineal junto con una región factible de programación lineal. Se han desarrollado varios algoritmos especiales basados en una extensión del método símplex para analizar la función objetivo no lineal.Un caso especial importante descrito a continuación es la programación cuadrática.

Programación cuadráticaDe nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la función objetivo f(x) debe ser cuadrática. Entonces, la única diferencia entre éstos y un problema de programación lineal es que algunos términos de la función objetivo incluyen el cuadrado de una variable o el producto de dos variables.La programación cuadrática es muy importante, en parte porque las formulaciones de este tipo surgen de manera natural en muchas aplicaciones. Sin embargo, otra razón por la que es importante es que al resolver problemas generales de optimización linealmente restringida se pueda obtener la solución de una sucesión de aproximaciones de programación cuadrática.

3.2 OPTIMIZACIÓN CLÁSICA

La teoría de optimización clásica considera el uso del cálculo diferencial para determinar puntos de máximos y mínimos (extremos) para funciones restringidas y no restringidas. Los métodos expuestos pueden no ser adecuados para cálculos numéricos eficientes. Sin embargo, la teoría subyacente proporciona la base para visualizar la mayoría de los algoritmos de programación no lineal

3.2.1. MÁXIMOS Y MÍNIMOS (Problemas de extremos no restringidos)

Un punto extremo de una función f(x) define un máximo o un mínimo de la función. Matemáticamente, un punto x0 = (x1,...xj,...xn) es un máximo si

4

f(X0+h) <=f(X0)para toda h = (h1,….hj, ,...hn) y es suficientemente pequeña para toda j. En otras palabras, X0 es un valor máximo si el valor de f en cada punto de la proximidad de X0 no es mayor que f(x). En forma parecida, X0 es un mínimo si para h, tal como se definió anteriormente,

F(x6)=max{f(x1), f(x3), f(x6)}

La figura ilustra los máximos y mínimos de una función f (x) de una sola variable dentro del intervalo [a, b]. [El intervalo a<= x <= b no significa que no haya restricciones sobre f(x)]. Los puntos x1, x2, x3, x4, x5, x6 son extremos de f(x), esto incluye a x1, x3, x6, como máximos, y x2 y x4 como mínimos ya que f(x6) es un máximo global o absoluto, mientras que f(x1) y f(x3) son máximos locales o relativos. De igual manera f(x4) es un mínimo local y f(x2) es un minino global.Aunque x1 (en la figura) es un punto máximo, se diferencia de los otros máximos locales porque el valor de f correspondiente a por lo menos un punto en el entorno de x1 es igual a f(x1). En este aspecto, x1 se llama máximo débil comparado con x3, por ejemplo, donde f(x3) define un máximo fuerte. Un máximo débil por consiguiente, implica (un numero infinito) de máximos alternativos. Pueden obtenerse resultado similares para el mínimo débil en x4, En general, X0 es un máximo débil si f(X0+h) <=f(X0), y un máximo fuerte si f(X0+h) <f(X0), donde h es tal como se definió anteriormente.Una observación interesante acerca de los extremos en la figura es que la primera derivada de f(pendiente) se anula en estos puntos. Sin embargo, esta propiedad no es única de los extremos. Por ejemplo, la pendiente de f(x) en x5 es cero.

3.2.2 PUNTOS DE INFLEXIÓN

Debido a que una primera derivada (generalmente, el gradiente) que se hace cero tiene un papel importante en la identificación de los máximos y mínimos, es esencial definir de manera separada puntos tales como x5. Estos puntos se conocen como de inflexión [o en casos especiales de silla]. SI un punto con pendiente (gradiente) cero no es un extremo (máximo o mínimo), entonces debe ser, automáticamente, un punto de inflexión.

5

3.3 PROBLEMAS NO RESTRINGIDOS

OPTIMIZACIÓN NO RESTRINGIDA DE UNA VARIABLE

La optimización no restringida con una sola variable x (n = 1), en donde la función diferenciable f(x) que debe maximizarse es cóncava. Así, la condición necesaria y suficiente para que una solución particular x = x* sea óptima (un máximo global) es

en x = x*,

Si en esta ecuación se puede despejar de modo directo, el problema llegó a su fin; pero si f(x) no es una función sencilla y su derivada no es una función lineal o cuadrática, tal vez sea imposible resolver la ecuación analítica. De ser así, el procedimiento de búsqueda en una dimensión proporciona una forma sencilla de obtener una solución numérica.Procedimiento de búsqueda en una dimensión

Al igual que otros procedimientos de búsqueda para programación no lineal, éste trata de encontrar una serie de soluciones prueba que conduzcan hacia una solución óptima. En cada iteración, se comienza con la solución prueba actual para llevar a cabo una búsqueda sistemática, que culmina con la identificación de una nueva solución prueba mejorada (se espera que sustancialmente mejorada).

Problema de programaciónno restringida de una variable cuando la función es cóncava.

La idea que fundamenta el procedimiento de búsqueda en una dimensión es muy intuitiva; se basa en el hecho de que la pendiente (derivada) sea positiva o negativa en una solución prueba indica definitivamente si la mejora está a la derecha o a la izquierda, respectivamente. Así, si la derivada evaluada para un valor específico de x es positiva, entonces x* debe ser más grande que esta x (vea la figura 2), con lo que x se convierte en una cota inferior para las soluciones prueba que en adelante se tomarán en cuenta. Por el contrario, si la derivada es negativa, entonces x* debe ser más chica que esta x, y x se convierte en una cota superior. Una vez identificadas ambas cotas, cada nueva solución prueba que se selecciona entre ellas proporciona una nueva cota más estrecha de uno de los dos tipos, cerrando la búsqueda cada vez más. Siempre y cuando se use una regla razonable para elegir cada solución prueba en esta forma, la sucesión de soluciones prueba debe converger a x*. En la práctica, esto significa continuar la sucesión, hasta que la distancia entre las cotas sea lo suficientemente pequeña como para que la siguiente solución prueba se encuentre dentro de una tolerancia de error de x* especificada.

En seguida se resume este proceso completo, usando la notaciónx' = solución prueba actual,x = cota inferior actual sobre x*,x = cota superior actual sobre x*,

6

= tolerancia del error para x*.

Aunque existen varias reglas razonables para elegir cada nueva solución prueba, la que se usa en el siguiente procedimiento es la regla del punto medio (tradicionalmente llamada de búsqueda de Bolzano), que dice que se seleccione el punto medio entre las dos cotas actuales.Resumen del procedimiento de búsqueda en una dimensión

Paso inicial: se selecciona . Se encuentran x y iniciales por inspección (o encontrando valores respectivos de x en los cuales la derivada sea positiva y luego negativa). Se elige una solución prueba

inicial, 2´

xxx

Paso iterativo:

Se evalúa dx

xdf )(

en x=x'.

Si 0

)(

dx

xdf

se hace x = x'.

Si 0

)(

dx

xdf

se hace x = x'.

Se elige una nueva 2´

xxx

Regla de detención: si 2 xx , de manera que la nueva x' se encuentra a una distancia de x* menor que , el proceso termina. De otra manera, se regresa al paso iterativo.

OPTIMIZACIÓN NO RESTRINGIDA DE VARIAS VARIABLES

Ahora considere el problema de maximizar una función cóncava f (x) de variables múltiples, x = (xj, x2,..., xn), en la que no se tienen restricciones sobre los valores factibles. Suponga de nuevo que la condición necesaria y suficiente para la optimalidad, dada por el sistema de ecuaciones que se obtiene al establecer las respectivas derivadas parciales iguales a cero), no se puede resolver en forma analítica, por lo que debe emplearse un procedimiento de búsqueda numérico. Ahora se tienen innumerables direcciones posibles hacia dónde moverse: corresponden a las tasas proporcionales posibles a las cuales las respectivas variables pueden cambiar. La meta es alcanzar eventualmente un punto en el que todas las derivadas parciales sean (en esencia) 0. Por tanto, la extensión del procedimiento de búsqueda en una dimensión requiere emplear los valores de las derivadas parciales para seleccionar la dirección específica en la que conviene moverse. Esta selección implica el uso del gradiente de la función objetiva como se describirá en seguida.Como se supone que la función objetivo f(x) es diferenciable, posee un gradiente denotado por en cada punto x. En particular, el gradiente en un punto específico x = x' es el vector cuyos elementos son las derivadas parciales respectivas evaluadas en x = x', entonces

en x=x´

7

El significado del gradiente es que el cambio (infinitesimal) en x, que maximiza la tasa a la que f(x) aumenta, es el cambio que es proporcional a . Para expresar geométricamente esta idea, la "dirección" del gradiente, , se interpreta como la dirección del segmento de recta dirigido (flecha) que va del origen (0, 0,..., 0) al punto ( ), donde se evalúa en xj = x'j. Entonces, se puede decir que la tasa a la que aumenta f(x) se maximiza si los cambios (infinitesimales) en x se hacen en la dirección del gradiente . Como el objetivo es encontrar la solución factible que maximice f(x), parece adecuado intentar moverse lo más posible en la dirección del gradiente.

Procedimiento de búsqueda del gradienteDebido a que el problema en cuestión no tiene restricciones, esta interpretación del gradiente sugiere que un procedimiento de búsqueda eficiente debe moverse en la dirección del gradiente hasta que (en esencia) alcance una solución óptima x*, en la que Vf (x*) = 0. Sin embargo, no resultaría práctico cambiar x continuamente en la dirección de , ya que esta serie de cambios requeriría una reevaluación continua de y el cambio en la dirección de la trayectoria. Entonces, una mejor forma de hacerlo es continuar el movimiento en una dirección fija a partir de la solución prueba actual, sin detenerse, hasta que f(x) deje de aumentar. Este punto de detención sería la siguiente solución prueba, por lo que se debe volver i calcular el gradiente para determinar la nueva dirección de movimiento. Con este enfoque, cada iteración incluye cambiar la solución prueba actual x' como sigue:Se modifica , en donde t que se maximiza ; es decir,

Note que es sencillamente f(x) en donde

xj para j=1,2,…,n.

y estas expresiones para la xj incluyen sólo constantes y t, de manera que f(x) se convierte en una función de una sola variable t.] Las iteraciones de este procedimiento de búsqueda del gradiente

continúan hasta que dentro de una pequeña tolerancia £, o sea, hasta que para j= 1,

2,..., nPor lo general, la parte más difícil del procedimiento de búsqueda del gradiente es encontrar t*, el valor de t que maximiza f en la dirección del gradiente, en cada iteración. Como x y tienen valores fijos para la maximización y como f(x) es cóncava, este problema se debe ver como el de maximizar una función cóncava de una sola variable t. En efecto, se puede resolver con el procedimiento de búsqueda en una dimensión (en donde la cota inferior inicial sobre t debe ser no negativa por la restricción de t >=0). De otra manera, si f es una función simple, es posible que se pueda obtener una solución analítica estableciendo la derivada con respecto a t igual a cero y despejando.

3.3.1 MULTIPLICADORES DE LAGRANGE (Optimización restringida con restricción de igualdad)

Ahora considere el problema de encontrar el mínimo o máximo de la función f (x), sujeta a la restricción de que x debe satisfacer todas las ecuaciones

en donde m<n. Por ejemplo, si n = 2 y m = 1, el problema podría ser:Maximizar x2 , sujeta a .En este caso, (x1,x2) está restringido a encontrarse sobre el círculo de radio 1, cuyo centro está en el origen, de forma que la meta es encontrar

8

el punto sobre este círculo que proporcione el mayor valor de . Es sencillo resolver este ejemplo después de bosquejar un enfoque general del problema.

Un método clásico para manejar este problema es el método de los multiplicadores de Lagrange. Este procedimiento comienza por plantear la función lagrangiana.

en donde las nuevas variables se llaman multiplicadores de Lagrange. Note el hecho fundamental de que para los valores factibles de x,

para toda ientonces . Por lo tanto, se puede demostrar que si es un mínimo o má-ximo local o global para la función no restringida , x* es el punto crítico correspondiente para el problema original. Como resultado, el método se reduce ahora al análisis de por el proce-dimiento descrito para optimización no restringida. Se igualan a cero las n + m derivadas parciales,

para j=1,2,…,n,

, para i=1,2,…,m

y entonces se obtienen los puntos críticos al despejar de estas ecuaciones. Observe que las últimas m ecuaciones son equivalentes a las restricciones del problema original, de manera que sólo se consideran las soluciones factibles. Después del análisis adicional para identificar el máximo o mínimo global de , el valor de x que resulta es la solución deseada para el problema original.Desde un punto de vista práctico y de cálculo, el método de los multiplicadores de Lagrange no es un procedimiento eficaz en particular. Con frecuencia es en esencia imposible resolver las ecuaciones para obtener los puntos críticos. Es más, aun cuando sea posible obtenerlos, el número de puntos críticos puede ser tan grande (a menudo infinito) que no será práctico intentar la identificación de un máximo o un mínimo global. Sin embargo, para ciertos tipos de problemas pequeños, algunas veces puede usarse este método con éxito.A manera de ilustración, considere el ejemplo presentado antes. En este caso

, de manera que

,

La primera ecuación implica que = 1, o x1 = 0. Si = 1, entonces las otras dos ecuaciones implican que x2 = 1 y x1= 0. Si x1 = 0, entonces la tercera ecuación implica que x2 = ±1- Así, los dos puntos críticos para el problema original son (x1,x2) = (0, 1)y (0, -1). Así, es evidente que estos dos puntos son los respectivos máximo y mínimo globales.

3.3.2 INTERPRETACIÓN ECONÓMICA

9

Los multiplicadores de Lagrange tienen una interpretación económica interesante e importante. Como antes dijimos, estos multiplicadores en PNL tienen casi la misma interpretación que los precios sombra en la PL. En otras palabras, en el punto óptimo, el valor del multiplicador de Lagrange es la tasa de cambio instantánea del VO(el valor óptimo de la función objetivo), cuando el í-ésimo LD(valor en solución), bi aumenta, permaneciendo iguales todos los demás datos. Otra forma de expresar este concepto en términos de economía, es que el i-esimo multiplicador de Lagrange refleja el valor marginal del i-ésimo recurso. Por consiguiente, sus unidades son

Unidades de la función objetivoUnidades del LD de la restricción i

Por ejemplo, un fabricante desea minimizar el costo total de un producto, el objetivo estaba expresado en dólares, bajo la restricción de que la producción total, digamos en toneladas, de dos productos debía ser igual a K. Así pues, las unidades del multiplicador de Lagrange para esta restricción son dólares por tonelada, y el valor de la misma es el costo marginal instantáneo de producción correspondiente a la R-ésima unidad.Sin embargo, los números correspondientes a la sensibilidad tienen un significado un poco más restringido que en el Informe de sensibilidad de PNL. Para modelos de PNL, el multiplicador de Lagrange de una restricción es la tasa de cambio inicial (es decir, instantánea) en el valor óptimo de la función objetivo, cuando el LD de la restricción aumenta. Igual que los precios sombra en la PL, un multiplicador de Lagrange positivo indicaría que al aumentar el LD se "beneficiaría" inicialmente el valor de la función objetivo en un modelo Max, e inicialmente se "perjudicaría” el valor de la función objetivo en un modelo Min. Un multiplicador de Lagrange negativo indicaría que al aumentar el LD se "perjudicaría” inicialmente el valor de la función objetivo en un modelo Max, y se "beneficiaría" inicialmente el valor de la función objetivo en un modelo Min. Beneficiar significa un aumento en el objetivo si es un modelo Max, y una disminución en el objetivo si es un modelo Min. En forma similar, perjudicar significa una disminución en el objetivo de un modelo Max y un aumento del objetivo en un modelo Min. Sin embargo, a diferencia de lo que aprendimos en el caso de la programación lineal, no es posible decir sobre qué rango de aumento o disminución del LD es válido dicho multiplicador de Lagrange. De hecho, en el caso más ordinario, el propio multiplicador de Lagrange cambia en cuanto se modifica el LD, por lo cual el incremento y el decremento permisibles son cero. Sin embargo, esto no les impide utilizar el multiplicador de Lagrange para estimar qué pasaría con el valor óptimo si cambiara el LD.En forma similar, los valores de gradiente reducido incluidos en el Informe de sensibilidad de PNL de Solver tienen una interpretación análoga a la de los valores de costo reducido del Informe de sensibilidad de PL. El gradiente reducido de una variable está relacionado con las restricciones que imponen un límite o acotamiento superior o inferior para las variables de decisión. Un gradiente reducido negativo para una variable de decisión indica que aumentar la variable “perjudicara” inicialmente el valor de la función objetivo en un modelo Max. Mientras que un gradiente reducido positivo para una variable indica que aumentar dicha variable "perjudicará" inicialmente el valor de la función objetivo en un modelo Min. Si una variable de decisión está en su acotamiento superior, el gradiente reducido deberá ser no negativo para que la solución sea óptima en un modelo Max: por lo contrario, disminuir la variable mejoraría el valor de la función objetivo. Sí una variable de decisión está en su acotamiento inferior, el gradiente reducido no sería positivo en un modelo Max; y, por lo contrario, aumentar la variable mejoraría la función objetivo. (Las conclusiones opuestas son aplicables a los modelos Min.) Si una variable de decisión está entre sus acotamientos superior e inferior, el gradiente reducido deberá ser cero para que la solución sea óptima.

10

CONCLUSIONES Y RECOMENDACIONES

La investigación de operaciones tiene como uno de sus temas fundamentales el tratar los problemas de índole lineal, donde variables y funciones objetivo tienen esta restricción, pero, en la vida no solo nos encontramos con este tipo de problemas, sino que nos encontramos con otra variedad que requieren encontrar una solución de optimización, hablamos de los problemas no lineales. Aquí es donde una de las múltiples herramientas de la Investigación de Operaciones hace aparición, me refiero a la Programación No Lineal. Su manera de atacar este tipo de problemas es diferente a la lineal, en aquella programación podemos ver que con el simple uso del método simplex, encontramos la solución de optimización al problema lineal que lo requiera, aun con lo laborioso que eso implique. En la Programación no Lineal descubrimos que el hecho de tratar de resolver problemas con distinto grado, requiere métodos y algoritmos diferentes y avocados a resolver problemas con los grados para los que fueron diseñados.

Los algoritmos los podemos clasificar en dos ramas: los algoritmos de optimización no restringidos, y los de optimización restringida, y estos últimos a su vez, con una sola variable, y con múltiples variables.

En los Algoritmos de optimización no restringidos, como su nombre lo dice, no tienen restricciones, solamente se trata de maximizar la función objetivo, sobre todos las variables que se sujetan a esta función, si esta es lineal es suficiente con que sea cóncava y resolver el sistema de todas las derivadas parciales de las variables igualadas a cero, pero si no son lineales, hay que implementar algoritmos de búsqueda, que puede ser en una dirección o en mas de una (multidimensional), por medio de procedimiento de búsqueda en una dimensión y para el ultimo el procedimiento de búsqueda del gradiente.

Para los algoritmos de optimización no restringidos, nos encontramos con los linealmente restringidos y los cuadráticos, los dos poseen restricciones lineales, pero en el primero la función objetivo no es Lineal, y en el segundo caso, la función objetivo es cuadrática, ya que incluye el producto de dos variables o el cuadrado de una de ellas.Este tipo de problemas se ataca con una extensión del método simplex para poder analizar la función objetivo no lineal.

Uno de los elementos mas importantes dentro de la optimización restringida son los multiplicadores de Lagrange, ya que cuando nos encontramos en el punto óptimo, el valor del multiplicador de Lagrange funciona indicando la tasa de cambio instantánea del valor óptimo de la función objetivo, cuando el í-ésimo LD, que es el valor en solución, bi aumenta, permaneciendo iguales todos los demás datos.

BIBLIOGRAFÍAHillier Frederick S. y Gerald J. LiebermanInvestigación de operacionesSéptima EdiciónEdit. McGraw-Hill México 2003Págs. 654-656,664-667,670-676,1166-1167

Hamdy A, TahaInvestigación de OperacionesQuinta EdiciónEdit. AlfaOmega México 1995Págs.837-839

G. D. Eppen, Jeffrey H. Moore y C. P. SCHMIDTInvestigación de Operaciones en la ciencia AdministrativaQuinta EdiciónEdit. Prentice Hall México 2000Págs. 337-338

11