El problema de la mezcla de productos con elasticidad en los precios (I)

En problemas de mezcla de productos, como el de la Wyndor Glass Co. de la sección 3.1 la meta es determinar la mezcla óptima de niveles de producción para los productos de una empresa, dadas las limitaciones sobre los recursos necesarios para producirlos, con el fin 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 obitiene es lineal. Sin embargo, en muchos problemas de mezclas de productos, ciertos factores introducen no linealidades en la función objetivo. Por ejemplo, un fabricante grande puede encontrar precios elásticos mediante los cuales la cantidad que se puede vender de un producto ya en relación inversa con el precio que se cobra. Así la curva precio-demanda puede parecerse a la que se muestra en la figura 14.1, en donde p(x) es el precio que se necesita para poder vender x unidades. Si el costo unitario de producir el artículo está fijo en c (véase la línea punteada en la figura 14.1), entonces la ganancia de la empresa por producir y vender x unidades está dada por una función no lineal.

Algunas aplicaciones

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

Programación no lineal (II)

No se dispone de un algortimo que resuelva todos los problemas especificos que se ajustan a este formato. Se han hecho grandes logros en lo que se refiere a algunos importantes casos especiales 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.

Programación no lineal (I)

El papel fundamental que juega la programación lineal en la investigación de operaciones se refleja en el hecho de que es el tema central de siete capítulos de este libro, además de que se aborta en algunos otros. 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, es frecuente que no sea 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 problemade programación no lineal consiste en encontrar x = (x1, x2,......xn) para

Maximizar f(x).

sujeta a    gi(x) ≤ bi, para i = 1,2,......m

x ≥ 0,

en donde f(x) y las gi(x) son funciones dadas de n variables de decisión.

Conclusión Programación Entera (III)

Para vencer estas dificultades de redondeo, se ha logrado un progreso considerable en él desarrollo de algoritmos heurísticos eficientes. Incluso con problemas de PE muy grandes, estos algoritmos encontrarán con rapidez soluciones factibles muy buenas que no son necesariamente óptimas, pero que casi siempre son mejores que las que se encuentran por redondeo.

Recientemente se han llevado a cabo muchas investigaciones con el fin de desarrollar algoritmos para programación entera no lineal, área cuyo estudio continúa muy activo.

Conclusión Programación Entera (II)

Aparentemente ha surgido una nueva etapa en la metodología de solución de problemas de PE, con una serie de artículos publicados en la década de 1980. El nuevo enfoque algorítmico involucra la combinación de preprocesado automático del problema, generación de cortaduras y las técnicas de ramificación y acotamiento. Continúa la investigación en esta área.

A veces los problemas prácticos de PE son tan grandes que no se pueden resolver ni con los últimos algoritmos. En estos casos, es común aplicar el método símplex nada más a la soltura de PL y después redondear la solución a una solución entera factible. Este enfoque no suele ser satisfactorio porque puede ser difícil (o imposible) encontrar una solución etera factible de esta manera. Y aun encontrándola, puede estar muy alejada del óptimo. Esto es cierto en especial cuando se manejan variables binarias e incluso variables enteras generales con valores pequeños.

Conclusión Programación Entera (I)

Los problemas de programación entera surgen con frecuencia cuando los valores de algunas o todas las varibles de decisión deben restringirse a valores enteros. Existen también muchas aplicaciones que necesitan decisiones de sí o no - incluyendo las relaciones combinatorias que se puedan expresar en términos de tales decisiones - que se pueden representar por variables binarias (0-1). Estos problemas son más difçiles de lo que serían sin la restricción de valores enteros, de manera que los algoritmos disponibles para programación entera, en general, son mucho menos eficientes que el método símplex. Los factores que determinan el tiempo de cálculo son el número de variables enteras y la estructura del problema. Para un número fijo de variables enteras, casi siempre es más fácil resolver problemas de PEB que problemas con variables enteras generale, pero agregar variables continuas (PEM) puede no significar un incremento en el tiempo de cálculo. Para problemas especiales de PEB que contienen alguna estructura especial que se puede aprovechar mediante un algoritmo especial, es posible resolver problemas muy grandes (muy por encima de mil variables binarias) en forma rutinaria. Puede ser que otros problemas mucho más pequeños sin estructura especial no e puedan resolver.

En la actualidad es común que se disponga de paquetes de computadora para algoritmos de programación entera en el software de programación matemática. EStos algoritmos casi siempre se basan en la técnica de ramificación y acotamiento o en alguna variación de ésta.

Programación Entera Desarrollos recientes (IX)

Irónicamente, los primeros algoritmos desarrollados para programación entera binaria, incluso el celebrado algoritmo que publicó Ralph Gomory en 1958, estaban basados en cortadura (excepto para algunos tipos especiales de problemas). No obstante, estos algoritmos se apoyaban únicamente en las cortaduras. Ahora se sabe que una combinación acertada de la cortaduras y de la técnicas de ramificación y acotamiento (junto con el preprocesado automático del problema) proporciona un enfoque algorítmico poderoso para resolver problemas de PEB de gran escala.

Programación Entera Desarrollos recientes (VIII)

Esta nueva restricción es una cortadura "Corta" la solución óptima de la soltura de PL (5/6, 1, 0, 1), pero no elimina ninguna solución entera factible. Si se agrega tan sólo esta cortadura al modelo original, se mejora el desempeño de algoritmo de ramificación y acotamiento de PEB de la sección 13.4 (véase la figura 13.7) en dos formas. Primero, la solución óptima para la nueva (y más estrecha) soltura de PL sería (1, 1, 1/5, 0), con Z = 15(1/5) de manera que la cotas para los nodos de todo el problema, x1 = 1 y x2 = 1, serían ahora de 15 en lugar de 16. Segundo, se necesitaría una iteración menos, porque la solución óptima de la soltura de PL en el nodo x3 = 0 sería (1, 1, 0, 0), que proporciona una nueva solución de apoyo con Z* = 14. Por tanto, en la tercera iteración (véase la figura 13.6) se sondearía este nodo por la prueba 3 y el nodo x2 = 0 se sondearía por la prueba 1, indicando que esta nueva solución de apoyo es la solución óptima para el problema de PEB original.


El nuevo enfoque algorítmico presentado en las referencias selectas 1,4 y 13 implica la generación de muchas cortaduras en forma parecida antes de aplicar las técnicas de ramificación y acotamiento. Los resultados al incluir cortaduras pueden ser importantes para estrechar las solturas de PL. Por ejemplo, para el problema de prueba con 2756 variables binarias del artículo de 1983, se generaron 326 cortaduras. El resultado fue que la distancia entre el valor de Z de la solución óptima de la soltura de PL del problema completo de PEB y el valor de Z de la solución óptima del problema se redujo en un 98%. En casi la mitad de los problemas se obtuvieron resultados similares.

Programación Entera Desarrollos recientes (VII)

Para ilustrar la cortadura, considérese el problema de programación entera pura de la California Manufacturing Co. que e presentó en la sección 13.1 y que se usó para ilustrar la técnica de ramificación y acotamiento de PEB en la sección 13.4. La solución óptima de su soltura de PL está dada en la figura 13.3 como (x1, x2, x3, x4) = (5/6, 1, 0, 1). Una de las restricciones funcionales es

6x1 + 3x2 + 5x3 + 2x4 ≤ 10

Ahora nótese que las restricciones binarias y esta restricción juntas implican que

x1 + x2 +x4 ≤ 2.

Programación Entera Desarrollos recientes (VI)

Hacerlo tiene la ventaja importante de estrechar la soltura de PL (lo que elimina algunas de sus soluciones factibles) sin eliminar ninguna solución factible del problema de PEB. Otra técnica es preparar un "gatillo" que va a fijar el valor de una o más variables, después que se ha dado cierto valor a otra variable durante el desarrollo del algoritmo. Por ejemplo, para el grupo de variables que representan un conjunto de alternativas mutuamente excluyentes, en cuanto una de las variables se iguala a 1, el resto se puede fijar 0. Un gatillo de este tipo se puede preparar también para las restricciones que representan decisiones continuas y para otras restricciones con forma similar.

Se ha comprobado que el uso de la computadora para llevar a cabo estas ideas y otras parecidas en forma automática es de gran ayuda para acelerar un algoritmo. Sin embargo, una técnica todavía más importante es la generación de planos cortantes. Una cortadura para un problema de PE es una nueva restricción que elimina algunas soluciones factibles de la soltura de PL original, incluso su solución óptima. El propósito de agregar una nueva restricción con esta propiedad es estrechar la soltura de PL, estrechando con esto la cota obtenida en el paso de acotamiento de la técnica de ramificación y acotamiento. Al estrechar la soltura de PL se incrementa la posiblidad de que su solución óptima sea factible (y por lo tanto óptima) para el problema de PE, con lo que e mejoraría la prueba de sondeo 3.

Programación Entera Desarrollos recientes (V)

El procesado automático del problema incluye una "inspección por computadora" de la formulación del problema de programación entera proporcionada por el usuario, con el fin de detectar algunas reformulaciones que hacen que el problema se resuelva con más rapidez, sin eliminar ninguna solución factible. Algunas ideas son muy sencillas, como se ilustrará con variables binarias puras. Es posible fijar el valor de una variable en 0 o en 1 debido a alguna restricción, por ejemplo,

3x1 + 2x2 ≤ 2 ⇒ x1 = 0
3x3 - 2x4 ≤ -1 ⇒ x3 = 0 y x4 = 1

de manera que se puede eliminar la variable del modelo (después de sustituir su valor fijo). una restricción funcional puede ser redundante a las restriciones binarias, por ejemplo,

3x1 + 2x2 ≤ 6,


y puede eliminarse. Es posible estrechar una restricción funcional reduciendo algunos de sus coeficientes, debido a las restricciones binarias, por ejemplo,

4x1 + 5x2 + x3 ≥ 2 ⇒ 2x1 + 2x2 + x3 ≥ 2

Programación Entera Desarrollos recientes (IV)

Aunque está más allá del alcance de este libro describir con detalle el nuevo enfoque algorítmico, se dará una idea global breve. ( Se anima al lector a que la las referencias 1, 4 y 13 para mayor información).

Este enfoque utiliza una combinación de los tres tipos de técnicas: 1) preprocesado automático del problema, 2) generación de planos cortantes o cortaduras y 3) técnicas de ramificación y acotamiento. El lector está familiarizado con la técnicas de ramificación y acotamiento  y no se profundizará más en las versiones más elaboradas que se incorporan aquí. A continuación e da una introducción conceptual sobre los otros dos tipo de técnicas que usan.

Programación Entera Desarrollos recientes (III)

Es necesario agregar una nota de precaución. No está claro qué tan consistente es el éxito de este enfoque algorítmico al resolver una amplia variedad de problemas de este tipo de gran escala. Los problemas más grandes de PEB pura que se han resuelto tenían matrices A no densas, es decir, el procentaje de coeficientes en las restricciones funcionales, que eran distintos de cero, era bastante pequeño (quizá menos del 5%). De hecho, el enfoque depende fuertemente de esta densidad. (Por fortuna, este tipo de poca densidad es frecuente en los problemas prácticos) Más aún, existen otros factores importantes, además de la densidad y el tamaño que afectan la dificultad de la solución de los problemas de PE. Parece que las formulaciones de PE de tamaño bastante grande deben todavía hacerse con mucho cuidado.

Por otro lado, cada nuevo cambio algorítmico en investigación de operaciones genera siempre una renovación en la actividad de investigación para desarrollar y refinar el nuevo enfoque. Sin duda se verán más frutos de la intensificación de esta actividad en programación entera durante la siguiente década. Quizá a través de la investigación se puedan disminuir las diferencias que existen en cuanto a la eficiencia entre lo algoritmos de programación entera y los de programación líneal.

Programación Entera Desarrollos recientes (II)

Más tarde llegó el siguiente cambio, a mediados de la década de 1981, según se publicó en tres artículos en 1983, 1985 y 1987. (Véanse las referencias 1, 4 y 13). En el artículo de 1983, Harlan Crowder, Ellis Johnson y Manfred Padberg presentaron un nuevo enfoque algoritmico para resolver problemas de PEB pura que había resuelto con éxito problemas sin una estructura especial aparente, con hasta 2756 variables! Este artículo ganó el Lancaster Prize otorgado por la Operations Research Society of America a la publicación más notable en investigación de operaciones durante 1983. En el artículos de 1985, Ellis Johnson, Michael Kostreva y Uwe Suhl refinaron este enfoque algorítmico.

Sin embargo, estos dos artículos se limitana PEB pura. ES bastante común que en los problemas de PE que surgen en la práctica todas las variables restringidas a valores enteros sean binarias, pero muchos de estos problemas son de PEBmixta. Lo que e necesitaba con desesperación era una forma de extender este mismo tipo de algoritmo a la PEBmixta. Esto ocurrió en el artículo de 1987 publicado por Tony Van Roy y Laurence Wolsey de Bélgica. Una vez más, se resolvían con éxito problemas de tamaño muy grande (hasta cerca de mil variables binarias y un gran número de variable continuas). Una vez más, este artículo ganó un prestigiado premio, el Orchard-Hays Price otorgado por la Mathematical Programming Society.

Programación Entera Desarrollos recientes (I)

La programación entera ha sido un área emocionante de investigación de operaciones durante los últimos años por los dramáticos adelantos hechos en su metodología de solución.
Para dar una mejor perspectiva sobre este progreso, considérense los antecedentes históricos. A fines de la década de 1960 y principios de la de 1970 hubo un cambio grande con el desarrollo y refinamiento del enfoque de ramificación y acotamiento. Después, todo siguió igual; se podían resolver en forma muy eficiente problemas relativamente pequeños (muy por debajo de las cien variables) pero aún un pequeño aumento en el tamaño del problema podía causar una explosión en el tiempo de cálculos más allá de los límites factibles. Se hacían pocos progresos para vencer este crecimiento exponencial en el tiempo de computación; cuando el tamaño del problema aumentaba, muchos problemas importantes que surgían en la práctica no se podían resolver.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (X)

El subproblema 6 se sondea de inmediato con la prueba 2. El subproblema 5 también se puede sondear con la prueba 3, porque la solución óptima de esta soltura de PL tiene valores enteros (x1`= 0, x2 = 0, x3 = 2) para las tres variables restringidas a enteros. (No importa que x4 = 1/2, ya que x4 no está restringida a enteros). Esta solución factible para el problema original se convierte en la primera solución de apoyo (incumbente):

Incumbente = (0, 0, 2, 1/2) con Z* = 13(1/2)

Con esta Z* se vuelve a realizar la prueba de sondeo 1 al otro subproblema (subproblema 4) y pasa la prueba, ya que su cota de 12(1/6) es ≤ Z*.

Esta iteración tuvo éxito en sondear de la tres maneras posibles. Lo que es más, ya no hay subproblemas restantes, por lo tanto la solución incumbente actual es óptima.

Solución óptima = (0, 0, 2, 1/2), con Z* = 13(1/2).

EStos resultados se resumen en el árbol de soluciones de la figura 13.10.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (IX)

Iteración 3

De los dos subproblemas restantes (3 y 4) que se crearon al mismo tiempo, se selecciona el que tiene la cota más grande (subproblema 3, con 14(1/6) > 12(1/6) para la siguiente ramificación). Como x1 = 5/6 tiene un valor no entero en la solución óptima de la soltura de PL de su subproblema, x1 se convierte en la variable de ramificación. (Obsérvese que x1 es ahora una variable de ramificación recurrente, pues también se seleccionó en la iteración 1.) Esto conduce a los siguientes subproblemas:

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (VIII)

Al resolver las solturas de PL se obtienen los siguientes resultados:

Soltura de PL del subproblema 3: (x1, x2, x3, x4) = (5/6, 1, 11/6, 0), con Z = 14(1/6)

Cota para el subproblema 3: Z ≤ 14(1/6)

Soltura de PL del subproblema 4: (x1, x2, x3, x4) = (5/6, 2, 11/6, 0), con Z = 12(1/6)
Cota para el subproblema 4: Z ≤ 12(1/6)

Como ambas soluciones existen (soluciones factibles) y tienen valores no enteros para variables restringidas a enteros, ninguno de los subproblemas se sondea. (La prueba I no es operativa, puesto que todavía Z* = - ∞, hasta que se encuentre la primera solución de apoyo.)

El árbol de solución hasta este punto se da en la figura 13.9.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (VII)

Subproblema 4:

problema original más las restricciones adicionales:


x1 ≤ 1
x2 ≥ 2

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (VI)

Subproblema 3: problema original más las restricciones adicionales:

x1 ≤ 1

x2 ≤ 1

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (V)

ITERACION 2

Con sólo un subproblema restante que corresponde al nodo x1 ≤ 1 en la figura 13.8, la siguiente ramificación se hace desde ahí. Al examinar la solución óptima de la soltura de PL que se da en seguida, en este nodo revela que la variable de ramificación es x2, ya que x2 = (6/5) es la primera variable restringida a enteros que no tienen un valor entero. Al agregar una de las restricciones, x2 ≤ 1 o x2 ≥ 2, se crean los dos nuevos subproblemas que siguen.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (IV)

De nuevo se elimina el conjunto de restricciones a valores enteros y se resuelven las solturas de PL de estos dos subproblemas; los resultados son:

Soltura de PL del subproblema 1: (x1, x2, x3, x4) = (1, 6/5, 9/5, 0), con Z = 14(1/5).

Cota para el subproblema 1: Z ≤ 14(1/5).

Soltura de PL del subproblema 2: no tiene soluciones factibles

Este resultado para el subproblema 2 significa que queda sondeado por la prueba 2. Igual que en el caso del problema completo, el subproblema 1 no pasa las pruebas de sondeo. En la figura 13.8 se resumen todos estos resultados en el árbol de solución.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (III)

Iteración I

En esta solución óptima de la soltura de PL la primera variable restringida a enteros que tiene un valor no entero es x1 = (5/4), entonces ésta se convierte en la variable de ramificación. Al ramificar desde el nodo de todo el problema (soluciones factibles de todo) con esta variable se crean los siguientes dos subproblemas:

Subproblema 1: problema original más la restricción adicional:

x1 ≤ 1.

Subproblema 2: problema original más la restricción adiciona:

x1 ≥ 2.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (II)

Paso Inicial

Después de establecer Z* = -∞, se forma la soltura de PL de este problema eliminado el conjunto de restricciones xj es entero para j = 1, 2, 3. Si se apliac el método símplex a esta soltura de PL, la solución óptima es

Soltura de PL de todo el problema: (x1, x2, x3, x4) = (5/4, 3/2, 7/4, 0), con Z = 14(1/4)

Como tiene soluciones factibles y esta solución óptima tiene valores no enteros para sus variables restringidas a enteros, se sondea todo el problema y el algoritmo continua con al primera iteración completa.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (I)

Ahora se ilustrará este algoritmo mediante su aplicación al siguiente problema de PEM:

Nótese que el número de variables restringidas a enteros es I = 3, de manera que x4 es la única variable continua.

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (IV)

Prueba de optimalidad:  el proceso se detiene cuando no hay subproblemas restantes; la solución incumbente actual es óptima. De otra manera, se realiza otra iteración.

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (III)

Sondeo: para cada nuevo subproblema  se aplican las pruebas de sondeo que se dan en seguida y se descartan aquellos subproblemas que quedan sondeados por cualquiera de las pruebas:

Prueba 1: su cota ≤ Z*, donde Z* es el valor de Z en la solución de apoyo actual.
Prueba 2:su soltura de PLno tiene soluciones factibles
Prueba 3: la solución óptima para su soltura de PL tiene valores enteros para todas sus variables restringidas a enteros. (Si esta solución esmejor que la de apoyo, se convierte en la nueva solución de apoyo y se vuelve a aplicar la prueba 1 con la nueva Z* a todos los subproblemas no sondeados.)

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (II)

Ramificación: para cada subproblema se obtiene su cota aplicando el método sinplex (o el método símplex dual si se reoptimiza) a su soltura de PL y utilizando el valor de Z para la solución óptima resultante.

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (I)

1. Ramificación: entre los subproblemas restantes (no sondeados), se selecciona el de más reciente creación. (Los empates se rompen con la cota más grande). Entre las variables restringidas a enteros, que tienen valores no enteros en la solución óptima de la soltura de PL del subproblema, se elige la primera en el orden natural, como la variable de ramificación. Sea xj esta variable y x*j su valor en esta solución. Se ramifica desde el nodo del subproblema para crear dos nuevos subproblemas agregando las restricciones respectivas xj ≤ [x*j] y xj ≥ [x*j] +1.

Resumen del algoritmo de ramifiación y acotamiento de PEM (I)

Paso inicial

Se establece Z* = -∞. Se aplica los pasos de acotamiento y de sondeo y la prueba de optimalidad que se describen a continuación al problema completo. Si no queda sondeado, se clasifica este problema como el único "subproblema" restanta para realizar la primera interación completa.