Programación lineal - Método Gráfico

ILUSTRACION GRÁFICA DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede re­presentar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de progra­mación lineal, de la sección 3.1. Se verán unos cuantos ejemplos, ya que una representación gráfica de este tipo proporciona una visión global de las propiedades de las soluciones ópti­mas de programación lineal y no lineal. Con el fin de hacer hincapié en las diferencias entre programación lineal y no lineal, se usarán algunas variaciones no lineales del problema de la Wyndor Glass Co.

La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que se ha­cen al modelo de la sección 3.1 son que la segunda y tercera restricciones funcionales se susti­tuyen por la restricción no lineal 9x{ + 5x₂ < 216. Compare las figuras 13.5 y 3.3. La solu­ción óptima sigue siendo (a^ , x₂) = (2,6). Todavía se encuentra sobre la frontera de la región factible, pero no es una solución factible en un vértice (FEV). La solución óptima pudo haber sido una solución FEV con una función objetivo diferente (verifique Z = 3x_x + x₂), pero que no necesite serlo significa que ya no se puede aprovechar la gran simplificación utilizada en programación lineal que permite limitar la búsqueda de una solución óptima para las solu­ciones FEV

Ahora suponga que las restricciones lineales de la sección 3.1 se conservan sin cambio, pero que la función objetivo se hace no lineal. Por ejemplo, si

entonces la representación gráfica en la figura 13.6 indica que la solución óptima es x_x – x₂ = 5, que de nuevo se encuentra en la frontera de la región factible. (El valor óptimo de Z es Z = 857; así, la figura 13.6 muestra el hecho de que el lugar geométrico de todos los puntos para los que Z = 857 tiene en común con la región factible sólo este punto, mientras que el lu­gar geométrico de los puntos con Z más grande no toca la región factible en ningún punto.) Por otro lado, si

 

entonces la figura 13.7 ilustra que la solución óptima es (*_l5 x₂ ) = (3,3), que se encuentra dentro de la frontera de la región factible. (Se puede comprobar que esta solución es óptima si se usa cálculo para derivarla como un máximo global no restringido; como también satisface las restricciones, debe ser óptima 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 región factible, y no sólo aquellas que están sobre la frontera.

  

Otra complicación que surge en programación no lineal es que un máximo local no nece­sariamente es un máximogbbal (la solución óptima global). Por ejemplo, considere la fun­ción de una sola variable graficada en la figura 13.8. En el intervalo 0 < x < 5, esta función tiene tres máximos locales — x=0,x=2,x=4—pero sólo uno de éstos—x – 4—es un má­ximo global. (De igual manera, existen mínimos locales en x = 1,3 y 5, pero sólo x = 5 es un mí­nimo global.)

En general, los algoritmos de programación no lineal no pueden distinguir entre un má­ximo local y un máximo global (excepto si encuentran otro máximo local mejor), por lo que es determinante conocer las condiciones bajo las que se garantiza que un máximo local es un máximo global en la región factible. Recuerde que en cálculo, cuando se maximiza una fun­ción ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta ga­rantía está dada cuando

 

Una función de este tipo cuya curvatura siempre es “hacia abajo” (o que no tiene curvatura) se llama función cóncava.¹ De igual manera, si se sustituye < por >, de manera que la función tiene siempre una curvatura “hacia arriba” (o no tiene curvatura), se llama función convexa.² (Así, una función lineal es tanto cóncava como convexa.) En la figura 13.9 se pueden ver ejemplos de esto. Note que la figura 13.8 ilustra una función que no es cóncava, ni convexa pues alterna sus curvaturas hacia arriba y hacia abajo.

Las funciones de variables múltiples también se pueden caracterizar como cóncavas o convexas si su curvatura es siempre hacia abajo o hacia arriba. Estas definiciones intuitivas se fundamentan en términos precisos que, junto con cierta profundización en los conceptos, se presentan en el apéndice 2. El apéndice 2 proporciona una prueba conveniente para verifi­car si una función de dos variables es cóncava, convexa o ninguna de las dos.

La siguiente es una forma conveniente de verificar esto para una función de más de dos variables cuando la función consiste en una suma de funciones más pequeñas cada una de sólo

una o dos variables. Si cada función más pequeña es cóncava, entonces la función completa es cóncava. De manera similar, la función completa es convexa si cada función más pequeña es convexa.

 

que es la suma de las dos funciones más pequeñas dadas en los paréntesis cuadrados. La pri­mera función más pequeña 4*! – x\ es una función de la variable x_x nada más, por lo que puede verse que es cóncava si se observa que su segunda derivada es negativa. La segunda función más pequeña -(x₂ – x¿ )² es una fimción de x₂ y por lo que se puede aplicar la prueba para funciones de dos variables dada en el apéndice 2. De hecho, este apéndice usa esta función en particular para ilustrar la prueba y encuentra que la función es cóncava. Como las dos funciones más pequeñas son cóncavas, la función completa f (jVj ,x₂,x₃) debe ser cóncava.

Si un problema de programación no lineal no tiene restricciones, el hecho de que la fun­ción objetivo sea cóncava garantiza que un máximo local es un máximoglobal. (De igual mane­ra, una función objetivo convexa asegura que un mínimo local es un mínimo global.) Si existen restricciones, entonces se necesita una condición más para dar esta garantía, a saber, que la re­gión factible sea un conjunto convexo. Como se analiza en el apéndice 2, un conjunto conve­xo es sencillamente un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en la colección. Así, la región fac­tible en el problema original de la Wyndor Glass Co. (vea la figura 13.6 o 13.7) es un conjun­to convexo. De hecho, la región factible para cualquier otro problema de programación lineal es un conjunto convexo. De igual manera, la región factible de la figura 13.5 también es un conjunto convexo.

En general la región factible para un problema de programación no lineal es un conjunto convexo siempre que todas las funciones g¡ (x) [para las restricciones g¿ (x) < b_{ ] sean conve­xas. Para el ejemplo de la figura 13.5, las dos g_t (x) son convexas, ya que g_x (x) = x_x (una fun­ción lineal es automáticamente cóncava y convexa) y g₂ (x) = 9x\ + 5x\ (tanto 9x\ como 5x₂ son funciones convexas, por lo que su suma es una función convexa). Estas dos funciones convexas g¡ (x) conducen a que la región factible de la figura 13.5 sea un conjunto convexo.

Ahora se analizará qué pasa cuando sólo una de estas funciones g¡ (x) es una función cón­cava. En particular, suponga que el único cambio que se hace al ejemplo de la figura 13.5 es

son funciones cóncavas. La nueva región factible mostrada en la figura 13.10 no es un conjun­to convexo. <Por qué? Porque contiene pares de puntos, como (0, 7) y (4, 3), tales que parte del segmento de recta que los une no está en la región factible. En consecuencia, no se puede garantizar que un máximo local sea un máximo global. De hecho, este ejemplo tiene dos má­ximos locales (0, 7) y (4, 3), pero sólo (0, 7) es un máximo global.

Entonces, para garantizar que un máximo local sea un máximo global para un problema de programación no lineal con restricciones (x) < b¡ (i = 1,2,…, m) y x > 0, la función obje­tivo /(x) debe ser cóncava y cada g_í (x) debe ser convexa. Un problema de este tipo se llama problema de programación convexa y es una de las clases más importantes de la programación no lineal que se estudiará en la siguiente sección.

MÁXIMOS Y MÍNIMOS

Loas máximos y mínimos de una función son los valores más grandes o más pequeños de ésta, ya sea en una región o en todo el dominio.

Los máximos y mínimos en una función f son los valores más grandes (máximos) o más pequeños (mínimos) que toma la función, ya sea en una región (extremos relativos) o en todo su dominio (extremos absolutos).

PUNTOS DE REFLEXIÓN

Se define un punto de inflexión como el punto en que la función pasa de ser convexa a cóncava o de cóncava a convexa.

En la siguiente gráfica podemos ver que cuando x = 0, la gráfica pasa de ser cóncava a ser convexa, por lo que podemos decir que el punto de inflexión esta en X = 0.

Una característica de los puntos de inflexión es que son los puntos donde la función derivada tiene máximos y mínimos. Si nos fijamos, cuando nos acercamos a un punto de inflexión la función cada vez crece más (o decrece menos), pero al sobrepasar el punto de inflexión la función empieza a crecer menos (o decrecer menos). Esto significa que justamente donde haya un punto de inflexión la derivada tendrá un máximo o un mínimo. Consecuentemente encontraremos los puntos de inflexión buscando ceros de la segunda derivada.

Vamos a ilustrar el proceso con un ejemplo para así dar una explicación simple y clara:

Consideraremos la función F(x) = x³ - 3x  (es la función representada en la anterior gráfica).

Sabemos ya calcular los máximos y los mínimos de la función f(x)  usando la primera derivada. La expresión de ésta es 3x² - 3  y justamente encontramos máximos y mínimos respectivamente en x = -14  y x = 1 .  Si representamos la gráfica de la derivada queda:

Observamos que justamente donde la derivada tiene un mínimo es donde la función tiene el punto de inflexión.

Para saber qué punto es vamos a derivar la función derivada e igualarla a cero: F´´(x) = 6x=0 = x = 0/6 = 0, y por tanto la función original en x = 0  tiene un punto de inflexión.

OPTIMIZACION CLÁSICA

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión.

Con el fin de ilustrar de forma adecuada la estructura y composición de un problema de optimización, introduciremos a continuación un sencillo ejemplo.

Ejemplo 1(Construcción de una caja con volumen máximo) Supongamos que queremos determinar las dimensiones de una caja rectangular de forma que contenga el mayor volumen posible, pero utilizando para ello una cantidad fija de material. El problema en forma abstracta se podría plantear en los siguientes términos Maximizar Volumen de la caja sujeto a Área lateral fija Con el fin de resolver este problema habrá que modelizarlo matemáticamente, es decir tendremos que expresarlo en términos matemáticos.

El primer paso para modelizar un problema de optimización es identificar y definir las variables que están implicadas en dicho problema, en este caso y puesto que estamos tratando de determinar el tamaño de una caja rectangular, la opción más clara es considerar como variables sus tres dimensiones rectangulares usuales (ancho, largo, alto) y que representamos con x, y, z. Con estas variables, la función para la que tenemos que encontrar el mejor valor será el volumen de la caja que puede expresarse como V (x, y, z) = xyz.

 A continuación debemos tener en cuenta las limitaciones existentes sobre el material. Como este material se utiliza para construir las paredes de la caja, necesitaremos considerar el área lateral de la misma, y si la caja tiene tapa, dicha área será A (x, y, z)= 2(xy + yz + zx).

Por último, teniendo en cuenta que las dimensiones de la caja no pueden ser negativas el problema puede expresarse matemáticamente como Maximizar xyz sujeto a 2 (xy + yz + zx) = A x, y, z ≥ 0.

 Fundamentos de Optimización 

En este ejemplo se distinguen tres elementos fundamentales: las variables del problema, una función de esas variables y un conjunto de relaciones que deben cumplir las variables del problema. Estos elementos se repetirán en todos los problemas de optimización y se definen formalmente a continuación:

1.- Variables de decisión: El primer elemento clave en la formulación de problemas de optimización es la selección de las variables independientes que sean adecuadas para caracterizar los posibles diseños candidatos y las condiciones de funcionamiento del sistema. Como variables independientes se suelen elegir aquellas que tienen un impacto significativo sobre la función objetivo.

Representaremos las variables independientes se representarán mediante vectores columna de Rn x = x1  . . .  + xn o vectores fila xt= (x1,...,xn) Aunque para los casos n = 1, 2 y 3 se emplearán las notaciones usuales de x, (x, y) y (x, y, z) respectivamente.

2.- Restricciones: Una vez determinadas las variables independientes, el siguiente paso es establecer, mediante ecuaciones o inecuaciones las relaciones existentes entre las variables de decisión. Estas relaciones son debidas, entre otras razones, a limitaciones en el sistema, a leyes naturales o a limitaciones tecnológicas y son las llamadas restricciones del sistema. Podemos distinguir dos tipos de restricciones:

(a) Restricciones de igualdad: Son ecuaciones entre las variables de la forma h (x) = h (x1,....xn)=0 donde g : A ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

(b) Restricciones de desigualdad: Son inecuaciones entre las variables de la forma g (x) = g(x1,....xn) ≤ 0 donde A : C ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

Observación: Solamente se han considerado restricciones de dos tipos: restricciones de igualdad del forma h (x1,....xn)=0 y restricciones de desigualdad de la forma g(x1,....xn) ≤ 0, debido a que siempre es posible, mediante una simple transformación, expresar el problema en términos de esta clase de restricciones.

Función objetivo: Finalmente, el último ingrediente de un problema de optimización es la función objetivo, también llamado índice de rendimiento o criterio de elección. Este es el elemento utilizado para decidir los valores adecuados de las variables de decisión que resuelven el problema de optimización. La función objetivo permite determinar los mejores valores para las variables de decisión. Independientemente del criterio seleccionado, dentro del contexto de la optimización matemática el adjetivo “mejor” siempre indica los valores de las variables de decisión que producen el mínimo o máximo valor (según el criterio utilizado) de la función objetivo elegida. Algunos de estos criterios pueden ser por ejemplo de tipo económico (coste total, beneficio), de tipo tecnológico (energía mínima, máxima capacidad de carga, máxima tasa de producción) o de tipo temporal (tiempo de producción mínimo) entre otros.

TIPOS DE PROBLEMA 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 de problemas de programación no lineal.

Optimización no restringida

Los problemas de optimización no restringida no tienen restricciones, por lo que la función

objetivo es sencillamente

Maximizar /(x)

sobre todos los valores x= (jíj, x2,…,xn). Según el repaso del apéndice 3 , la condición necesaria

para que una solución específica x = x* sea óptima cuando /(x) es una función diferenciable

es

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 Xj tiene una restricción de no negatividad, x- > 0, la condición necesaria

(y tal vez) suficiente anterior cambia ligeramente a  para cada j de este tipo.

Optimización linealmente restringida

se ajustan por completo a la programación lineal, de manera que todas las funciones de restricción

g¡ (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ática

De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora

la función objetivo /(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.

Programación convexa

La programación convexa abarca una amplia clase de problemas, entre ellos como casos especiales,

están todos los tipos anteriores cuando /(x) es cóncava. Las suposiciones son

1. /(x) es cóncava.

2. Cada una de las g¿(x) es convexa.

Programación separable

La programación separable es un caso especial de programación convexa, en donde la suposición

adicional es

3. Todas las funciones / ( x ) y g¡(x) son funciones separables.

Una función separable es una función en la que cada término incluye una sola variable, por lo

que la función se puede separar en una suma de funciones de variables individuales. Por ejemplo,

si /(x) es una función separable, se puede expresar como

en donde cada / • (Xj) incluye sólo los términos con Xj.En la terminología de programación

lineal los problemas de programación separable satisfacen las suposiciones

de aditividad pero no las de proporcionalidad (para funciones no lineales).

Programación no convexa

La programación no convexa incluye todos los problemas de programación no lineal que no satisfacen

las suposiciones de programación convexa. En este caso, aun cuando se tenga éxito

en encontrar un máximo local, no hay garantía de que sea también un máximo global. Por lo

tanto, no se tiene un algoritmo que garantice encontrar una solución óptima para todos estos

problemas; pero sí existen algunos algoritmos bastante adecuados para encontrar máximos locales,

en especial cuando las formas de las funciones no lineales no se desvían demasiado de

aquellas que se supusieron para programación convexa.

Programación geométrica

Cuando se aplica programación no lineal a problemas de diseño de ingeniería, muchas veces

la función objetivo y las funciones de restricción toman la forma

En tales casos, las ci y a ty representan las constantes físicas y las x} son las variables de diseño.

Estas funciones por lo general no son ni cóncavas ni convexas, por lo que las técnicas de programación

convexa no se pueden aplicar directamente a estos problemas deprogramacióngeométrica.

Sin embargo, existe un caso importante en el que el problema se puede transformar

en un problema de programación convexa equivalente. Este caso es aquel en el que todos los

coeficientes c¿ en cada función son estrictamente positivos, es decir, las funciones son polinomios

positivos generalizados (ahora llamados posinomiales), y la función objetivo se tiene que

minimizar. El problema equivalente de programación convexa con variables de decisión yx,

y2,…, yn se obtiene entonces al establecer

Xj = ey\ para;’ = l , 2 , . . . ,n

en todo el modelo original. Ahora se puede aplicar un algoritmo de programación convexa.

Se ha desarrollado otro procedimiento de solución para resolver estos problemas ác.programación

posinomial, al igual que para problemas de programación geométrica de otros tipos.

Problema de complementariedad

Cuando se estudie la programación cuadrática en la sección 13.7, se verá un ejemplo de cómo

la solución de ciertos problemas de programación no lineal se puede reducir a resolver el problema

de complementariedad. Dadas las variables wy,w2,…,wp y el problema

de complementariedad encuentra una s o l u c i o n a r á para el conjunto de restricciones

que también satisface la restricción de complementariedad,

wr z = 0 .

Aquí, w y z son vectores columna, F es una función con valores vectoriales dada y el superíndice

T denota la traspuesta . El problema no tiene función objetivo, de manera

que técnicamente no es un problema de,programación no lineal completo. Se llama

problema de complementariedad por las relaciones complementarias que establecen que una

de las dos

wi = Ó o zi = 0 (o ambas) para cada i = 1, 2.

DEFINICION

La programación no lineal forma parte de la investigación de operaciones y también, como la programación lineal, tiene como finalidad proporcionar los elementos para encontrar los puntos óptimos para una función objetivo. En este planteamiento, tanto la función objetivo como las restricciones son no lineales. Se presenta un problema de programación no lineal cuando tanto la función 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 aplicación de la programación no lineal es muy amplio, sin embargo, hasta la fecha los investigadores de esta rama del conocimiento no han desarrollado un método sistemático que sea práctico para su estudio. La programación no lineal también es conocida con el nombre de programación cuadrática, en virtud de que la mayor parte de los problemas que resultan contienen ecuaciones cuadráticas o de segundo grado.