3.1 Conceptos básicos de problemas de programación no lineal
La Programación no Lineal (PNL) es una parte de la Investigación Operativa cuya misión es proporcionar una serie de resultados y técnicas tendentes a la determinación de puntos óptimos para una función (función objetivo) en un determinado conjunto (conjunto de oportunidades), donde tanto la función objetivo, como las que intervienen en las restricciones que determinan el conjunto de oportunidades pueden ser no lineales.
Evidentemente, la estructura del problema puede ser muy variada, según las funciones que en él intervengan (a diferencia de la Programación Lineal (PL) donde la forma especial del conjunto de oportunidades y de la función objetivo permiten obtener resultados generales sobre las posibles soluciones y facilitan los tratamientos algorítmicos de los problemas).
Ello ocasiona una mayor dificultad en la obtención de resultados, que se refleja también en la dificultad de la obtención numérica de las soluciones. En este sentido, hay que distinguir entre las diversas caracterizaciones de óptimo, que sólo se emplean como técnicas de resolución en problemas sencillos, y los métodos numéricos iterativos, cuyo funcionamiento se basa en estas caracterizaciones, para la resolución de problemas más generales.
CONCEPTOS BASICOS
La programación lineal da respuesta a situaciones en las que se exige maximizar o minimizar funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.
Su empleo es frecuente en aplicaciones de la industria, la economía, la estrategia militar, etc. Función objetivo
En esencia la programación lineal consiste en optimizar (maximizar o minimizar) una función objetivo, que es una función lineal de varias variables:
f(x,y) = ax + by. Restricciones
La función objetivo está sujeta a una serie de restricciones, expresadas por inecuaciones lineales: a1x + b1y ≤ c1 a2x + b2y ≤c2 … … … anx + bny ≤cn
Cada desigualdad del sistema de restricciones determina un semiplano. Solución factible
El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un recinto, acotado o no, que recibe el nombre de región de validez o zona de soluciones factibles. Solución óptima
El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso). Valor del programa lineal
El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.
PASOS PARA RESOLVER UN PROBLEMA DE PROGRAMACIÓN LINEAL
REPORT THIS AD
REPORT THIS AD
1. Elegir las incógnitas.
2. Escribir la función objetivo en función de los datos del problema.
3. Escribir las restricciones en forma de sistema de inecuaciones.
4. Averiguar el conjunto de soluciones factibles representando gráficamente las restricciones.
5. Calcular las coordenadas de los vértices del recinto de soluciones factibles (si son pocos).
6. Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de ellos presenta el valor máximo o mínimo según nos pida el problema (hay que tener en cuenta aquí la posible no existencia de solución si el recinto no está acotado).
3.2 Ilustración 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 representar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de programació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 óptimas 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 hacen al modelo de la sección 3.1 son que la segunda y tercera restricciones funcionales se sustituyen por la restricción no lineal 9x{ + 5x2 < 216. Compare las figuras 13.5 y 3.3. La solución óptima sigue siendo (a^ , x2) = (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 = 3xx + x2), 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 soluciones 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 xx – x2 = 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 lugar 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 x2 ) = (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 necesariamente es un máximogbbal (la solución óptima global). Por ejemplo, considere la funció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 función ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta garantí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.1 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.2 (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 verificar 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 primera función más pequeña 4*! – x\ es una función de la variable xx 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 -(x2 – x¿ )2 es una fimción de x2 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 ,x2,x3) debe ser cóncava.
Si un problema de programación no lineal no tiene restricciones, el hecho de que la función objetivo sea cóncava garantiza que un máximo local es un máximoglobal. (De igual manera, 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 región factible sea un conjunto convexo. Como se analiza en el apéndice 2, un conjunto convexo 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 factible en el problema original de la Wyndor Glass Co. (vea la figura 13.6 o 13.7) es un conjunto 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 convexas. Para el ejemplo de la figura 13.5, las dos gt (x) son convexas, ya que gx (x) = xx (una función lineal es automáticamente cóncava y convexa) y g2 (x) = 9x\ + 5x\ (tanto 9x\ como 5x2 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óncava. 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 conjunto 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 objetivo /(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.
3.3 Tipos De Problemas De Programacion 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.
Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de Programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.
Si la función objetivo es cóncava (problema de maximización), o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces se puede utilizar el método general de Optimización convexa
Existe una variedad de métodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones especiales de problemas de programación lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior que el mejor límite inferior obtenido por alguna de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede ser parado antes, con la garantía de que la mejor solución será mejor que la solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difíciles 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 solución sea óptima.
Los tipos de problemas de programación no lineal son: Optimización no restringida. Optimización linealmente restringida. Programación cuadrática Programación convexa. Programación separable. Programación no convexa. Programación geométrica. Programación fraccional. Problema de complementariedad.
ALGORITMOS SIN RESTRICCIÓN
En esta sección se presentarán dos algoritmos para el problema no restringido: el algoritmo de búsqueda directa y el algoritmo de gradiente.
Método de búsqueda directa
Los métodos de búsqueda directa se aplican principalmente a funciones estrictamente unimo- dales de una variable. Aunque puede parecer trivial el caso, la sección 21.1.2 muestra que la optimización de funciones de una variable juega un papel clave en el desarrollo de los algoritmos de varias variables, más generales.
La idea de los métodos de búsqueda directa es identificar el intervalo de incertidum- bre que comprenda al punto de solución óptima. El procedimiento localiza el óptimo estrechando en forma progresiva el intervalo de incertidumbre hasta cualquier grado de exactitud que se desee.
En esta sección se presentan dos algoritmos estrechamente relacionados: los métodos de búsqueda dicótomo y de sección dorada (o áurea). Ambos buscan la maximización de una función unimodal/(x) en el intervalo a ^ x < b, que se sabe que incluye el punto óptimo x*. Los dos métodos comienzan con /0 = (a, b) que representa el intervalo inicial de incertidumbre.
Paso general i. Sea /, _ , = (xD xR) el intervalo actual de incertidumbre (en la iteración 0, xL = a y xR = b). A continuación se definen xx y x2 tales que
xj^ ^ ^ x2 ^ xr
El siguiente intervalo de incertidumbre, /z, se define como sigue: Si f(xx) > /(x2), entonces xL < x* < x2. Se definen xR = x2 e /, = (xL, x2) (véase la figura 21.2[a]). Si f(xx) < f(x2\ entonces xx < x* < xR. Se definen xL = xx e I¡ = (xh xR) (véase la figura 21.1 [b]). . Si f{x\) = /(jc2), entonces xx < x* < x2. Se definen xL = x2 e /, = (xb x2).
La manera en que se determinan xx y x2 garantiza que /, < /,_ p como se demostrará en breve. El algoritmo termina en la iteración ksilk< A, donde A es un grado de exactitud definido por el usuario. *
La diferencia entre los métodos dicótomo y de sección dorada estriba en la forma en que se calculan xx y x2. La tabla siguiente presenta las fórmulas.
En el método dicótomo los valores jc, y x2 se encuentran simétricos respecto del punto medio del actual intervalo de incertidumbre. Esto significa que
La aplicación repetida del algoritmo garantiza que la longitud del intervalo de incertidumbre se acercará al nivel de exactitud deseado, A.
En el método de la sección dorada la idea es de mayor involucramiento. Se puede apreciar que cada iteración del método dicótomo requiere calcular los dos valores/(jc,) y f(x2), Pe” ro termina por descartar alguno de ellos. Lo que propone el método de la sección dorada es ahorrar cálculos mediante el reuso del valor descartado en la iteración inmediata siguiente. Para definir 0 < a < 1
Cuando el intervalo de incertidumbre /, en la iteración i es igual a (jc¿, x2) o a (xu xR). Considere el caso en que /, = (jcl, x2), lo cual significa que xx está incluido en /,. En la iteración /+1, seleccione x2 igual a jc, de la iteración /, lo cual lleva a la siguiente ecuación:
x2(iteración i+l) = x{(iteración i)
Comparado con el método dicótomo, el método de la sección dorada converge más rápidamente hacia el nivel deseado de exactitud. Adicionalmente, cada iteración en el método de la sección dorada requiere la mitad de los cálculos, en virtud de que recicla siempre un conjunto de los cálculos correspondientes a la iteración inmediata anterior. EJEMPLO
El máximo valor de f(x) ocurre en x = 2. La siguiente tabla muestra los cálculos para las iteraciones 1 y 2, usando el método dicotomo y el de la sección dorada. Supondremos que A = 0.1.
Al continuar de la misma forma, el intervalo de incertidumbre terminará por estrecharse hasta la tolerancia A deseada.
La plantilla ch21DichotomousGoldenSection.xls de Excel está diseñada para manejar cualquiera de estos dos métodos en forma automática. Los datos son/(*), a,b y A. La función f{x) se captura en la celda E3 como sigue:
= IF(C3< = 2,3*C3, (-C3+20)/3)
OPTIMIZACIÓN NO RESTRINGIDA
Los problemas de optimización no restringida no tienen restricciones, por lo que la función objetivo es sencillamente
Maximizar f(x)
sobre todos los valores x= (x1, 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 f(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. ¿Qué se puede hacer en ese caso? Las secciones 13.4 y 13.5 describen procedimientos algorítmicos de búsqueda para encontrar x* primero para n = 1 y luego para n > 1. Estos procedimientos también tienen un papel importante en la solución de varios tipos de problemas con restricciones, que se describirán en seguida. La razón es que muchos algoritmos para problemas restringidos están construidos de forma que se adaptan a versiones no restringidas del problema en una parte de cada iteración.
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. Esta condición se ilustra en la figura 13.11, 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 # = 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 RESTRINGIDA
Los 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¡ (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 f(x) es cóncava. 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
Todas las funciones f(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 f(x) es una función separable, se puede expresar como
son cada tina funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura 13.7 también es una función separable.
Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método símplex.
son cada tina funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura 13.7 también es una función separable.
Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método símplex.
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. En la sección 13.10 se presenta uno de estos algoritmos.
Ciertos tipos específicos de problemas de programación no convexa se pueden resolver sin mucha dificultad mediante métodos especiales. Dos de ellos, de gran importancia, se presentarán más adelante.
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óngeo- mé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
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 de programación posinomial, al igual que para problemas de programación geométrica de otros tipos.1
PROGRAMACIÓN FRACCIONAL
Suponga que la función objetivo se encuentra en la forma de una fracción, esto es, la razón o cociente de dos funciones,
Estos problemas de programación fraccional surgen, por ejemplo, cuando se maximiza la razón de la producción entre las horas-hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de rendimiento), o el valor esperado dividido entre la desviación estándar de alguna medida de desempeño para una cartera de inversiones (rendimiento/riesgo). Se han formulado algunos procedimientos de solución especiales1 para ciertas formas de f1(x) y f2 (x)
Cuando se puede hacer, el enfoque más directo para resolver un problema de programación fraccional es transformarlo en un problema equivalente de algún tipo estándar que disponga de un procedimiento eficiente. Para ilustrar esto, suponga que f(x) es de la forma de programación fraccional lineal
donde c y d son vectores renglón, x es un vector columna y c0 y dQ son escalares. También suponga que las funciones de restricción g¡ (x) son lineales, es decir, las restricciones en forma matricial son Ax < b y x > 0.
Con algunas suposiciones débiles adicionales, el problema se puede transformar en un problema equivalente de programación lineal si se establece
que se puede resolver con el método símplex. En términos generales, se puede usar el mismo tipo de transformación para convertir un problema de programación fraccional con /¡(x) cóncava, f2 (x) convexa y g¡ (x) convexas, en un problema equivalente de programación convexa.
3.4 Optimización 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.
Puntos de Inflexió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.
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).
A continuación tenemos un vídeo acerca de lo que es optimización clásica
Principales usos y beneficios del diagrama de Pert
¿Conoces el origen del diagrama de PERT? A finales de la década de los 50, la marina de los Estados Unidos se encontraba en el proceso de elaboración de una nueva flota de submarinos. Pese al riguroso trabajo de planificación de las etapas previas, el grupo de ingenieros y responsables carecía de una herramienta para realizar el seguimiento oportuno de las tareas.
Con el paso de los días, la construcción de las nuevas piezas se complicó debido a que sólo los líderes conocían los detalles y la evolución del proyecto. Los otros, funcionarios y operarios, se limitaban a seguir órdenes. Ante esta perspectiva, los responsables se vieron obligados a replantear la gestión del proyecto. La idea era integrar de la mejor forma a los agentes y recursos que formaban parte en las tareas. Sin embargo, no podían imaginar que estaban a punto de proponer un nuevo paradigma de gestión: el modelo PERT.
¿Dónde y cómo puedo aplicar el diagrama PERT?
PERT es la forma abreviada con la que se designa el Project Evaluation and Review Techniques o, lo que es lo mismo, Técnicas de Evaluación y Revisión de Proyectos. Se trata de un modelo de seguimiento y gestión aplicado en principio al sector de las tecnologías, pero que con el paso del tiempo se hizo extensivo a otras áreas.
Visto de cerca, el diagrama es en realidad una malla compuesta por las distintas tareas de un proyecto y sus respectivos plazos. Está planteado de esta forma para visualizar la importancia de las labores interconectadas. De acuerdo a esta característica, PERT es una herramienta especialmente valiosa para gestionar proyectos complejos, a largo plazo y en los que interactúen muchos actores.
Además, viene muy bien para clarificar los plazos y la evolución de aquellas tareas que se lleven a cabo de forma simultánea. Su objetivo es la integración. Para aplicar un diagrama de este tipo, primero se deben tener claros algunos aspectos de su configuración. Veamos algunos de ellos.
El cuadro está compuesto por nodos. Éstos, a su vez, se conectan a través de líneas continuas. Las líneas son las actividades del proyecto, a las cuales se añade una variable que es el tiempo estimado de ejecución.
Sólo hay un vértice de inicio y otro de final. Estos dos puntos son los que marcan el principio y el desenlace del proyecto. Si hubiese más de un vértice en cada caso, estaríamos hablando de más de un proyecto.
Además del tiempo estimado para realizar una tarea, cada actividad puede ir acompañada de otras variables, como por ejemplo la duración esperada, el tiempo de inicio y de final más temprano, y la holgura.
Beneficios más notorios del diagrama PERT
Tal como hemos adelantado, el principal aporte de este modelo es haber proporcionado una visión integral de los procesos. De ahí se derivan otros beneficios prácticos que se pueden apreciar en la elaboración de cualquier proyecto:
Mejora la planificación del proyecto y la toma de decisiones.
Mayor integración y presentación de datos.
Optimiza la evaluación de los tiempos de ejecución.
Da a cada actividad un tratamiento individual y otro integrado.
Facilita la identificación de puntos críticos.
Promueve la elaboración de un plan maestro para cada proyecto.
Cómo usar el diagrama de PERT
La perspectiva sobre los procesos que permite adquirir el diagrama de PERT hace posible al Project Manager mejorar su interpretación visual de las actividades en curso. A partir de este enfoque global, la gestión se ve optimizada, mientras que la toma de decisiones se agiliza y gana en precisión.
El diagrama de PERT es un importante aliado cuando se trata de impulsar la propia eficiencia ejecutiva y la del proyecto, sean cuales sean las características de la iniciativa en curso. Uno de los motivos es su versatilidad.
No sólo se trata de una herramienta fácil de aprender y no demasiado complicada de aplicar, sino que, además, resulta insustituible como apoyo a la función de planificación.
Si no fuera por la visibilidad a que da acceso, ¿de qué otro modo se podrían fijar objetivos? ¿Cómo sería posible llevar el control del progreso de proyecto?
La combinación de tareas, reunidas en un mismo espacio, donde se cuenta con información sobre sus fechas de inicio y fin, es la mejor garantía de aumento del rendimiento. Pero hay que saber cómo aplicarlo.
El diagrama de PERT no tiene secretos para quienes siguen los siguientes pasos en su aplicación:
Definición del propósito de la iniciativa.
Determinación de las actividades a realizar y su duración estimada.
Identificación de las dependencias entre actividades previa a su representación gráfica, donde se unirán con flechas.
Determinación de las fechas de inicio y fin de cada actividad, concretando las más tempranas que se estimen realistas y determinación de la versión más tardía posible de las mismas fechas.
Cálculo de la ruta crítica y el margen de tiempo libre disponible asociado a cada actividad.
Establecimiento del camino crítico para el proyecto.
El algoritmo de Dijkstra te permite calcular la ruta más corta entre un nodo (tú eliges cuál) y todos los demás nodos en el grafo. Encontrarás una descripción del algoritmo al final de esta página, pero ¡vamos a estudiarlo con un ejemplo explicado! Calcularemos la distancia más corta entre el nodo C y los demás nodos del grafo:
Durante la ejecución del algoritmo, iremos marcando cada nodo con su distancia mínima al nodo C (nuestro nodo elegido). Para el nodo C, esta distancia es 0. Para el resto de nodos, como todavía no conocemos esa distancia mínima, empieza siendo infinita (∞):
También tendremos un nodo actual. Inicialmente, el nodo actual será C (nuestro nodo elegido). En la imagen, marcaremos el nodo actual con un punto rojo.
Ahora, revisaremos los vecinos de nuestro nodo actual (A, B y D) en cualquier orden. Empecemos con B. Sumamos la mínima distancia del nodo actual (en este caso, 0) con el peso de la arista que conecta al nodo actual con B (en este caso, 7), y obtenemos 0 + 7 = 7. Comparamos ese valor con la mínima distancia de B (infinito); el valor más pequeño es el que queda como la distancia mínima de B (en este caso, 7 es menos que infinito):
Bien. Ahora revisaremos al vecino A. Sumamos 0 (la distancia mínima de C, nuestro nodo actual) con 1 (el peso de la arista que conecta nuestro nodo actual con A) para obtener 1. Comparamos ese 1 con la mínima distancia de A (infinito) y dejamos el menor valor:
OK. Repetimos el procedimiento para D:
Genial. Hemos revisado todos los vecinos de C. Por ello, lo marcamos como visitado. Representemos a los nodos visitados con una marca de verificación verde:
Ahora debemos seleccionar un nuevo nodo actual. Ese nodo debe ser el nodo no visitado con la menor distancia mínima, es decir, el nodo con el menor número y sin marca de verificación verde. En este caso, ese nodo es A. Vamos a marcarlo con el punto rojo:
Ahora, repetimos el algoritmo. Revisamos los vecinos de nuestro nodo actual, ignorando los visitados. Esto significa que solo revisaremos B.
Para B, sumamos 1 (la distancia mínima de A, nuestro nodo actual) con 3 (el peso de la arista conectando a A con B) para obtener 4. Comparamos ese 4 con la distancia mínima de B (7) y dejamos el menor valor: 4.
Después, marcamos A como visitado y elegimos un nuevo nodo: D, que es el nodo no visitado con la menor distancia mínima.
Repetimos el algoritmo de nuevo. Esta vez, revisamos B y E.
Para B, obtenemos 2 + 5 = 7. Comparamos ese valor con la distancia mínima de B (4) y dejamos el menor valor (4). Para E, obtenemos 2 + 7 = 9, lo comparamos con la distancia mínima de E (infinito) y dejamos el valor menor (9).
Marcamos D como visitado y establecemos nuestro nodo actual en B.
Casi terminamos. Sólo debemos verificar E. 4 + 1 = 5, que es menos que la distancia mínima de E (9), así que dejamos el 5. Marcamos B como visitado y establecemos E como el nodo actual.
E no tiene vecinos no visitados, así que no verificamos nada. Lo marcamos como visitado.
Como no hay nodos no visitados, ¡terminamos! La distancia mínima de cada nodo ahora representa la mínima distancia entre ese nodo y el nodo C (el nodo que elegimos como nodo inicial).
Aquí está una descripción del algoritmo:
Marca el nodo inicial que elegiste con una distancia actual de 0 y el resto con infinito.
Establece el nodo no visitado con la menor distancia actual como el nodo actual A.
Para cada vecino V de tu nodo actual A: suma la distancia actual de A con el peso de la arista que conecta a A con V. Si el resultado es menor que la distancia actual de V, establécese como la nueva distancia actual de V.
