Conclusiones Problemas especiales de programación lineal

El problema de programación líneal abarca una gran variedad de tipos específicos de problemas. El método símplex general es un algoritmo poderoso que puede resolver versiones sorprendentemente grandes de cualquiera de estos problemas. Algunos de estos problemas tienen formulaciones tan sencillas que se pueden resolver de manera mucho más eficiente mediante versiones simplificadas del método símplex, que aprovechan su estructura especial. Estas versiones simplificadas pueden reducir mucho el tiempo de computadora que requieren los problemas grandes y algunas veces, de hecho, permiten que los problemas grandes se puedan resolver en una computadora. Esto es cierto en particular para problemas de transporte y trasbordo, para problemas de asignación y para problemas con muchas restricciones CSG y de cota superior. Para problemas multidivisionales en general, el tiempo de preparación es tan grande para el procedimiento simplificado que se recomienda usarlo en forma selectiva sólo en problemas grandes.

En la sección 10.6 se examinará la estructura especial de los problemas de transporte, trasbordo y asignación. Ahí se verá que estos problemas son casos especiales de una clase importante de problemas de programación líneal conocidos como el problema de flujo máximo. Este problema se interpreta como minimizar el costo del flujo de bienes a través de una red. La interpretación de red agregará una visión más amplia de la estructura de estos tres problemas.

Una gran parte de la investigación continúa dedicada al desarrollo de procedimientos de solución simplificados para los problemas de programación líneal de tipo especial, entre los que se cuentan algunos que no se presentaron aquí. Al mismo tiempo, existe un amplio interés en las aplicaciones de programación líneal para optimizar la operación de sistemas complicados de gran escala, incluso los sistemas sociales. Las formulaciones que resultan casi siempre tienen estructuras especiales que se pueden aprovechar. Reconocer y explotar estas estructuras especiales se ha convertido en un factor muy importante en la aplicación exitosa de la programación líneal.

Casos especiales importantes (II)

Tanto las restricciones de cota superior como las CSG ocurren debido a la naturaleza multidivisional del problema. Sin embargo, debe hacerse hincapié en que con frecuencia surgen también en muchos otros contextos. De hecho, ya  se han visto varios ejemplos que contienen restricciones de este tipo.

Nótese la tabla 7.6 que en realidad todas las restricciones del problema de transporte son restricciones CSG. ( La Tabla 7.6 se ajusta a la forma de la tabla 7.35 si se colocan las restricciones de recursos abajo de las restricciones de la demanda). A su vez, las restricciones de demanda se pueden interprestar como restricciones CSG pero sin manejar variables consecutivas.

Tanto las restricciones de terreno como las de cosecha en el problema de planeación regional de la confederación de Kibbutzim (veáse la sección 3.4) son restricciones CSG.

Las restricciones tecnológicas en el problema de contaminación del aire de la Nori &Leets Co. (Veáse la sección 3.4) son restricciones de cota superior al igual que dos de las tres restricciones funcionales en el problema de mezcla de productos de la Wyndor Glass Co. (Sec 31).

En vista de la frecuencia con que ocurren las restricciones CSG y de cota superior , se han desarrollado técnicas especiales para simplificar su manejo en el método símplex. (La técnica para las restricciones d ecota superior se describe en la sección 9.1 y la de las restricciones CSG es muy parecida.) Si se tienen muchas restricciones, estas técnicas pueden reducir en forma notable el tiempo de computación.

Casos especiales importantes (I)

Con frecuencia surgen formas todavía más simples de la estructura especial que se exhibe en la tabla 7.32. En la tabla 7.35 se muestran dos de ellas especialmente comunes.

La primera ocurre cuando algunas o todas las variables se pueden agrupar de manera que la suma de las variables en cada grupo no exceda una cota superior para ese grupo (o quizá deba ser igual a una constante especifica). Por lo general, las restricciones de esta forma.

Ejemplo Prototipo - Good Foods Corporation (II)

Nótese que la tabla correspondiente a los coeficientes de las restricciones, que se muestra en la tabla 7.34, tiene la estructura especial de los problemas multivisionales dada en la tabla 7.32. Sin duda, entonces, la Good Foods Co. puede resolver este problema ( o una versión más detallada) si emplea la versión simplificada del método símplex que proporciona el principio de descomposición.

Ejemplo Prototipo - Good Foods Corporation (I)

La Good Foods Corporation es una empresa grande que produce y distribuye productos alimenticios. Tiene tres divisiones principales: la división de alimentos procesados, la división de alimentos enlatados y la división de alimentos congelados. Como los costos y precios de venta cambian con frecuencia en la industria alimenticia, la Good Foods usa periódicamente un modelo de programación lineal de la compañia para revisar las tasas de producción de sus productos, con el objeto de utilizar sus capacidades disponibles de la manera más redituable posible. Este modelo es parecido al de la Wyndor Glass Co. (veáse la sección 3.1), pero de mayor escala, con cientos de restricciones y variables. (Como el espacio en el libro es limitado, se describirá una versión simplificada del problema que combina los productos o recursos por tipos).

La corpración cultiva sus propias papas y maíz de alta calidad, y estas dos materias primas básicas son las únicas de bajo abastecimiento que en la actualidad usan todas las divisiones.

Excepto por estos recursos organizacionales, cada división utiliza sus propios recursos y, por lo tanto, puede determinar sus tasas de producción en forma autónoma. En la tabla 7.33 se dan los datos de cada división y el subproblema correspondiente que incluye sólo sus recursos y productos (en donde Z representa la ganancia mensual en millones de dólares), junto con los datos de los recursos de la organización.

El problema de programación lineal que se obtiene para esta corporación es

Problemas multidivisionales (II)

Conceptualmente, esta versión simplificada del método símplex se puede interpretar como la posibilidad de dejar que cada división resuelva su subproblema  mande su solución como propuesta a la "coordinación general" (el problema maestro), en donde se negocian las propuestas de todas las divisiones  para encontrar una solución óptima para toda la organización. Si los subproblemas son de un tamaño razonable y el problema maestro no es demasiado grande (no más de 50 o 100 restricciones), este enfoque puede tener éxito al resolver algunos problemas multidivisionales extremadamente grandes. En particular, vale la pena aplicarlo cuando el número total de restricciones es bastante grande (por lo menos varios cientos ) y existen varios subproblemas, más que unos cuantos.

Problemas multidivisionales (I)

Otra clase importante de problemas de programación lineal son una estructura especial que se puede explotar consiste en los problemas multivisionales. Su característica especial es que se refieren a la coordinación de las decisiones de divisiones independientes de una empresa grande. Como las divisiones operan con bastante autonomía , el problema casi se puede descomponer en problemas separados, en donde cada división se aboca sólo a optimizar su propia operación; sin embargo,  se requiere alguna coordinación general con el fin de dividir mejor ciertos recursos organizacionales entre las divisiones.

Como resultado de esta característica especial, la tabla de coeficientes de restricciónes en los problemas multidivisionales tiene la estructura angular de bloque que se muestra en la tabla 7.32 (recuérdese que las áreas sombreadas de la tabla representan las únicas porciones de la tabla que tiene cualquier coeficiente aij distinto de cero.) Entonces, cada pequeño bloque contiene los coeficientes de las restricciones de un subproblema, a saber, el problema de optimizar la operación de una división específica. El bloque grande de la parte superior contiene los coeficientes de las restricciones de enlace para el problema maestro, es decir, el problema  de coordinar las actividades de las divisiones y la repartición de los recursos de la organización  entre ellas, con el objeto de  obtener una solución óptima global para toda la organización.

Por su naturaleza, los problemas multidivisionales suelen ser muy grandes y contienen muchos cientos y hasta miles de restricciones y variables. Puede ser necesario explotar su estructura  especial con el fin de poder resolverlos con un gasto razonable de tiempo de computadora, y a veces para poder siguiera resolverlos. El principio de descomposición (descrito en las referencias selectas 2 y 3 del final de este capítulo) proporciona una manera eficiente de explotar esta estructura especial.

Formulación de la opción 2 (III)

Como es usual, una manera de obtener esta solución óptima es convertir la tabla de costos de la tabla 7.31 a una tabla de costos y requerimientos equivalente para el problema de transporte (véase la tabla 7.28) y después aplicar el método símplex de transporte. Debido a que la tabla 7.31 contiene dosrenglones idénticos, este engoque se puede simplicadicar combinando los cinco asignados en tres orígenes con costos 2, 2 y 1, respecticamente. Esta simplificación también disminuirá el número de variables básicas degeneradas en todas las soluciones básicas factibles.

Ahora se debe comparar esta solución con la que se obtuvo para la opción 1, que incluye la separación del producto 4 entre las plantas 2 y 3. Las asignaciones son diferentes en las dos soluciones, pero el costo total es casi el mismo (Z=3270 para la opción 1 y Z=3290 para la opción 2.) Entonces, al tomar en cuenta los costos no evidentes asociados con la separación de productos, la gerencia decidió adoptar la solución de la opción 2.

Formulación de la opción 2 (II)

El número de asignados (ahora cinco) debe ser igual al número de asignaciones (ahora cuatro), así que se introduce una asignación ficticia (producto) como 5(D) en la tabla 7.31. El papel de esta asignación ficticia es proporcionar un segundo producto ficticio a cualquiera de las plantas 1 o 2, que recibe sólo un producto real. No se incurre en ningún costo por producir un producto ficticio así que, como siempre, los costos de la asignación ficticia son cero. La excepción es el costo M en el último renglón de la tabla 7.31. La razón es que la planta 3 debe recibir un producto real y el método de la M evita que se le asigne el producto ficticio a esta planta.

El resto de los costos en la tabla 7.31 no son los costos unitarios que se muestran en la tabla 7.29 o 7.30. Para un problema de asignación, el costo cij es el costo total asociado al hecho de que el asignado i realice la asignación j. En la tabla 7.31, el costo total (por día) para que la planta i fabrique el producto j es el costo de producción multiplicado por el número de unidades producidas (por día), donde estas dos cantidades a multiplicar se dan por separado en la tabla 7.29)Igual que en la tabla 7.30, la M evita la asignación no factible del producto 3 a la planta 2).

La solución óptima para este problema de asignación es

La planta 1 fabrica los productos 2 y 3
La planta 2 fabrica el producto 1,
La planta 3 fabrica el producto 4,

donde la asignación ficticia se da en la planta 2. El costo total es Z = 3290

Formulación de la opción 2 (I)

Sin la separación de productos, cada producto debe asignarse a una sola planta. Entonces, los productos se pueden interpretar como las asignaciones en un probema de asignación y las plantas como los asignados.

La gerencia ha especificado que debe asignarse al menos uno de los productos a cada planta. Se tienen más productos (cuatro) que plantas (tres), por lo que tendrá que asignar dos productos a una de las plantas. La planta 3 tiene apenas la capacidad adicional para producir un producto (véase la tabla 7.29), así, la planta 1 o bien la 2 fabricará el otro producto.

Para hacer posible la asignación de este producto adicional dentro de la formulación de un problema de asignación, las plantas 1 y 2 se dividen en dos asignados cada una, como se muestran en la tabla 7.31.

Formulación de la opción 1

Al permitir la separación de productos, la tabla 7.29 se puede convertir directamente a una tabla de costos y requerimientos para un problema de transporte. Las plantas se convierten en orígenes  y los productos en destinos (o viceversa); así, los recursos se interpretan como las capacidades de producción y las demandas como las tasas de producción requeridas. Sólo se tienen que hacer dos cambios en la tabla 7.29. Primero, como la planta 2 no puede fabricar el producto 3, se evita esa asignación dando un costo unitario muy grande, M. Segundo, La capacidad total (75+75+45 = 195) excede la producción total requerida (20+30+30+40 = 120) así que se necesita un destino ficticio con una demanda de 75 para balancear estas dos cantidades. La tabla de costos y requerimientos que resulta se muestra en la tabla 7.30/

L solución óptima de este problema de transporte tiene variables básicas (asignaciones) x12 = 30, x13 = 30, x15 = 15, x24 = 15, x25 = 60, x31 = 20 y x34 = 25, de manera que

La planta 1 produce todos los productos 2 y 3,
La planta 2 produce la mitad del producto 4,
La planta 3 produce la mitad del producto 4 y todo el producto 1.

El costo total es Z = 3270

Ejemplo - Asignación de productos a plantas (II)

La segunda opción impone una restricción que sólo puede aumentar el costo de una solución óptima según la tabla 7.29. Por otro lado, la ventaja clave de la opción 2 es que elimina algunos costos no evidentes asociados con la separación de productos que no se reflejan en la tabla 7.29, incluyendo costos adicionales de preparación, distribución y administración. Por todo esto, la gerencia quiere que se analicen ambas opciones antes de tomar la decisión final. Para la opción 2 se ha especificado además que debe asignarse al menos uno de los productos a cada planta.

Se formulará  y resolverá el modelo para cada opción, en donde la opción 1 lleva al problema de transporte y la opción 2 al problema de asignación.

Ejemplo - Asignación de productos a plantas (I)

La BETTER PRODUCTS COMPANY ha decidido iniciar la producción de cuatro nuevos productos utilizando tres plantas que por el momento tienen exceso de capacidad de producción. Los productos requieren un esfuerzo productivo comparable por unidad por lo que la capacidad de producción disponible en las plantas se mide por el número de unidades de cualquier producto que se pueden obtener por día, como se muestra en la última columna de la tabla 7.29. El último renglón da la producción diaria requerida para satisfacer las ventas proyectadas. Cada planta puede producir cualquiera de estos productos, excepto la planta 2 que no puede fabricar el producto 3. Sin embargo, el costo variable por unidad de cada producto difiere entre una planta y otra, como se muestra en el cuerpo de la tabla 7.29.

La gerencia necesita tomar la decisión de cómo dividir la producción entre las plantas. 

Tiene dos opciones:

Opción 1: permitir la separación de productos, de tal manera que el mismo producto se puede fabricar en más de una planta.

Opción 2: no autorizar la separación de productos.

Modelo del problema de asignación y procedimientos de solución (V)

No es coincidencia que esta solución óptima que proporciona el método símplex de transporte tenga tantas variables básicas degeneradas. Para cualquier problema de asignación, la formulación del problema de transporte que se muestra en la tabla 7.28a tiene m = n. Los problemas de transporte tienen (m+n-1) variables basicas (asignaciones); así, toda la solución básica factible para este tipo de problema de transporte tiene (2n-1) variables básicas, pero sólo n de estas xij = 1. Por esto, siempre habrá (n-1) variables básicas degeneradas (xij = 0) Como se dijo al final de la sección 7.2, las variables básicas degeneradas no causan mayor complicación en la ejecución del algoritmo. No obstante, con frecuencia causan que se realicen iteraciones de balde, en las que nada cambia (asignaciones iguales) excepto la etiqueta de que asignaciones de cero corresponden a variables básicas degeneradas en lugar de a variables no básicas. Estas iteraciones de balde son un gran incoveniente para aplicar el método símplex de transporte a este tipo de situaciones en las que siempre hay tantas variables básicas degeneradas.

Otro incoveniente del método símplex de transporte es que se trata meramente de un algoritmo de propósitos generales para resolver todos los problemas de transporte. Así, no toma en cuenta la estructura especial adiciona en este tipo especial de problemas (m=n, toda si = 1 y toda dj = 1). Aunque no se describrían aquí, se han desarrollado algoritmos especiales para simplificar el procedimiento de solución exclusivo para los problemas de asignación. Estos algortimos operan directamente sobre la tabla de costos y no se preocupan por las variables básicas degeneradas. Si se dispone de un paquete de computadora para alguno de estos algoritmos, será preferible usarlo en lugar del método símplex de transporte.

Modelo del problema de asignación y procedimientos de solución (IV)

Por lo general, los que aplican esta técnica a problemas de asignación específicos no se toman la molestia de escribir todo el modelo matemático. Es mucho más sencillo formularlo llenando la tabla de costos (por ejemplo, la tabla 7.27), con la identificación de los asignados y las asignaciones, a que esta tabla contiene todos los datos esenciales en una forma mucho más compacta.

Debido a que el problema de asignación es un tipo especial de problema de transporte, una forma conveniente de resolverlo es aplicar el método símplex de transporte que se describió en la sección 7.2. Este enfoque requiere que se convierta la tabla de costos a una tabla de costos y requerimientos para el problema de transporte equivalente, como se muestra en la tabla 7.28a.

Por ejemplo, la tabla 7.28b muestra la tabla de costos y requerimientos para la Job Shop Co. que se obtiene a partir de la tabla de costos en la tabla 7.27. Cuando se aplica el método símplex de transporte a esta formulación, la solución  óptima tiene variables básicas x13 = 0, x14 = 1, x23 = 1, x31 = 1, x41 = 0, x42 = 1, x43 =0. (En el problema 32 se le pide al lector que verifique esta solución). Las variables básicas degeneradas (xij = 0) y la asignación para la máquina ficticia no tienen significado para el problema original, de esta manera, las asignaciones reales son la máquina 1 al lugar 4, la máquina 2 al lugar 3 y la máquina 3 al lugar 1.

Modelo del problema de asignación y procedimientos de solución (III)

Ahora se hará una comparación de este modelo (sin la restricción binaria) con el modelo del problema de transporte que se presentó en la segunda subsección de la sección 7.1 (incluyendo la tabla 7.6). Obsérvese que sus estructuras son similares. De hecho el problema de asignación es sólo un caso especial de los problemas de transporte en donde los orígenes son ahora los asignados y los destinos son las asignaciones, y donde

número de orígenes (m) = número de destinos (n)
cada recurso si = 1,
cada demanda dj =1

Ahora se centrará la atención en la propiedad de soluciones enteras de la subsección del modelo de transporte. Como ahora toda si y dj son enteros (=1), esta propiedad significa que toda solución básica factible (incluso la óptima) es entera para un problema de asignación.

Las restricciones funcionales del modelo de asginación evitan que las variables sean mayores que uno y las restricciones de no negatividad evitan valores menores que cero. Por lo tanto, al eleminar la restricción binaria para poder resolver el problema de asignacion como un problema de programación líneal, la solución básica factible que se obtiene (incluyendo la solución óptima final) automáticamente satisfará la restricción binaria.

Modelo del problema de asignación y procedimientos de solución (II)

Las variables binarias son importantes en investigación de operaciones para representar las decisiones de si o no, como se verá en detalle en el capítulo de programación entera (cap 13). En este caso, las decisiones de si o no son: debe el asignado i realizar la actividad j?

Sea Z el costo total, el modelo de asignación es

El primer conjunto de restricciones funcionales especifica que cada asignado realiza exactamente una asignación, mientras que el segundo conjunto requiere que cada asignación sea realizada exactamente por un asignado. Si se elimina la restricción entre paréntesis de que xij sean binarias, resulta claro que el modelo es un problema especial de programación linea, por lo que se puede resolver de inmediato. Por fortuna, debido a las razones que se expondrán en seguida, se puede eliminar esta restricción. (Precisamente, el que se pueda eliminar es la razón por la que el problema de asignación se incluye en este capítulo y no en el de programación entera.

Modelo del problema de asignación y procedimientos de solución (I)

El modelo matemático para el problema de asignación utiliza las siguientes variables de decisión:

para i = 1,2, ..........., n y j = 1,2,........., n. Entonces, cada xij es una variable binaria (0 o 1).

Ejemplo Prototipo

La JOB SHOP COMPANY ha comprado tres máquinas nuevas de diferentes tipos. Existen cuatro sitios disponibles dentro del taller en donde se podría instalar una máquina. Algunos de ellos  son más adecuados que otros para una máquina en particular por su cercanía a los centros de trabajo que tendrían un flujo intenso de trabajo hacia estas máquinas y desde ellas. Por tanto, el objetivo es asignar las nuevas máquinas a los lugares disponibles de manera que se minimice el costo total del manejo de materiales. En la tabla 7.26 se proporciona el costo estimado por unidad de tiempo del manejo de los materiales en cuestión con cada una de las máquinas en los sitios respectivos. El lugar 2 no se considera adecuado para la máquina 2. No habrá flujo de trabajo entre las nuevas máquinas.

Para formular este problema como un problema de asignación debe introducirse una máquina ficticia para el lugar adicional. Además debe asignarse un costo muy grande M a la asignación de la máquina 2 en el lugar 2 para evitarla en la solución óptima. En la tabla 7.27 se muestra la tabla de costos del problema de asignación que resulta. Esta tabla de costos contiene todos los datos necesarios para resolver el problema. La solución óptima es asignar la máquina 1 al lugar 4, la máquina 2 al lugar 3 y la máquina 3 al lugar 1 con un costo total de 29. La máquina ficticia se asigna al lugar 2, con lo que esta localidad queda disponible para alguna asignación real futura. 

Se formulará el modelo matemático para el problema general de asignación y después se analizará cómo se obtiene esta solución.

Problema de asignación

El problema de asignación consiste en un tipo especial de problema de programación lineal en el que los recursos se asignan a las actividades sobre una base de uno-a-uno. Entonces, cada recurso o asignado (por ejemplo, un empleado, máquina o intervalo de tiempo) debe asignarse a una actividad en particular asignación (por ejemplo, una tarea, lugar o evento. Existe un costo cij asociado con el asignado i (i= 1,2,......,n) que realiza la asignación j (j = 1,2, ...., n), de manera que el objetivo es determinar cómo deben hacerse las asignaciones con el fin de minimizar los costos totales.