• Categories
• Programación lineal
• Transporte
• Física y matemáticas
• Matemática
• Ciencia

Citation preview

Capítulo Quince Problemas de transporte y asignación Objetivos de aprendizaje Al terminar este capítulo, deberá ser capaz de: 1. Describir las características de los problemas de transporte. 2. Elaborar un modelo de hoja de cálculo para el problema de transporte a partir de la descripción de un problema. 3. Hacer lo mismo para algunas variantes de problemas de transporte. 4. Dar el nombre de dos algoritmos que puedan resolver problemas de transporte muy grandes que estén lejos del alcance del Excel Solver. 5. Identificar varias áreas de aplicación de los problemas de transporte y sus variantes. 6. Describir las características de los problemas de asignación. 7. Identificar la relación entre los problemas de asignación y los problemas de transporte. 8. Elaborar un modelo de hoja de cálculo para un problema de asignación a partir de la descripción del problema. 9. Hacer lo mismo para algunas variantes de problemas de asignación. 10. Dar el nombre de un algoritmo que pueda resolver problemas de asignación muy grandes que estén fuera del alcance del Excel Solver.

Los problemas de transporte se presentaron en la sección 3.5, y en la sección 3.6 se hizo lo mismo con los problemas de asignación. Ambos tipos de problemas similares surgen con bastante frecuencia en una diversidad de contextos. Debido a su importancia, en el presente capítulo se abordarán estos problemas con mucho mayor detalle así como sus aplicaciones. Los problemas de transporte reciben este nombre porque muchas de sus aplicaciones incluyen determinar la forma de transportar productos en forma óptima. Sin embargo, se verá que algunas de sus aplicaciones importantes no tienen nada que ver con el transporte. Los problemas de asignación son más conocidos porque se aplican en lo referente a la asignación de personal a ciertas tareas. Sin embargo, también tienen otras diversas aplicaciones. Después de un caso estudio, en las secciones iniciales de este capítulo se describen las características de los problemas de transporte y sus variantes, se ilustra la elaboración de modelos en hojas de cálculo para dichos problemas y se recorre una diversidad de aplicaciones. En las siguientes secciones se hace lo mismo para los problemas de asignación.

15.1

UN CASO DE ESTUDIO: EL PROBLEMA DE DISTRIBUCIÓN DE P & T COMPANY Douglas Whitson está preocupado. Los costos han ido en aumento y los ingresos no han mantenido el paso. Si esta tendencia continúa, los accionistas van a estar muy descontentos con el próximo informe de ganancias. Como presidente y director ejecutivo de P & T Company, él sabe que el problema llega hasta él. Tiene que encontrar la forma de controlar los costos.

631

15-Hillier.indd 631

19/12/07 11:49:34

632

Capítulo Quince Problemas de transporte y asignación

De pronto, Douglas levantó el teléfono y llamó a su gerente de distribución, Richard Powers. Douglas (director ejecutivo): Richard. Soy Douglas Whitson. Richard (gerente de distribución): Hola, Douglas. Douglas: Oye, Richard. He estado revisando algunos datos de costos y un número me llamó la atención. Richard: ¿Sí? ¿Cuál? Douglas: Los costos de embarque de los guisantes: ¡178 000 dólares la última temporada! Yo recuerdo que hace unos cuantos años lo manejábamos en menos de 100 000 dólares. ¿Qué pasa aquí? Richard: Sí, tienes razón. Esos costos realmente han aumentado. Un factor es que nuestro volumen de embarque ha subido un poco. Sin embargo, lo principal es que las cuotas que cobran las compañías de transporte que hemos utilizado realmente se han disparado. Nos hemos quejado. Dijeron algo acerca de que su nuevo contrato con el sindicato que representa a los conductores subió sus costos de manera sustancial. Y sus costos de seguro también han subido. Douglas: ¿Han intentado cambiar de compañía de transporte? Richard: Sí. De hecho ya hemos elegido a otra compañía para la siguiente temporada de cosecha. Douglas: Bien. De manera que tus costos de embarque deberán bajar bastante para la siguiente temporada. Richard: Bueno, mi proyección es que deberán ser de unos 165 000 dólares. Douglas: Caramba. Todavía es demasiado alto. Richard: Parece ser lo mejor que podemos lograr. Douglas: Bueno, enfoquemos esto desde otro ángulo. ¿Ustedes llevan los guisantes desde nuestras tres plantas de enlatado hasta nuestros cuatro almacenes? Richard: Correcto. Douglas: ¿Cómo deciden cuánto mandará cada enlatadora a cada almacén? Richard: Tenemos una estrategia estándar que hemos utilizado durante muchos años. Douglas: ¿Esta estrategia reduce al mínimo su costo de embarque total? Richard: Creo que hace un buen trabajo respecto a eso. Douglas: Pero ¿utiliza un algoritmo para generar un plan de embarque que garantice minimizar el costo de embarque total? Richard: No, no puedo decir que haga eso. ¿Hay una forma de hacer eso? Douglas: Sí, entiendo que hay una técnica de ciencia administrativa para hacer eso. Es algo que aprendí cuando entrevisté a la nueva empleada, recién graduada de una maestría en administración de empresas, a quien contratamos el mes pasado, Kim Baker. Ella pensó que esa técnica podría aplicarse en nuestra compañía. Contratamos a Kim para ayudarnos a incorporar algunas de las mejores técnicas que se enseñan en las escuelas de negocios en la actualidad. Creo que debemos hacer que Kim revise tu plan de embarques y vea si puede mejorarlo. Richard: Suena razonable. Douglas: De acuerdo. Me gustaría que lo coordinaras con Kim y que me reporten lo que suceda a la brevedad. Richard: Así lo haremos La conversación termina.

Antecedentes P & T Company es una pequeña empresa de propiedad familiar. Recibe vegetales crudos, los procesa, los enlata en sus plantas y luego los distribuye para su venta. Uno de los productos principales de la compañía son los guisantes enlatados. Éstos se preparan en tres plantas de enlatado (cerca de Bellingham, Washington; Eugene, Oregon y Albert Lea, Minnesota) y luego se transportan por tráiler a cuatro almacenes de distribución en el oeste de Estados Unidos (Sacramento, California; Salt Lake City, Utah; Rapid City, Dakota del Sur y Albuquerque, Nuevo México), como se muestra en la figura 15.1.

15-Hillier.indd 632

19/12/07 11:49:36

15.1

FIGURA 15.1

Un caso de estudio: el problema de distribución de P & T Company 633

Enlatadora 1 Bellingham

Ubicación de las plantas de enlatado y de los almacenes para el problema de P & T.

Almacén 3 Rapid City

Enlatadora 2 Eugene

Almacén 1 Sacramento

Enlatadora 3 Albert Lea

Almacén 2 Salt Lake City

Almacén 4 Albuquerque

Enfoque actual de la empresa Por muchos años, la compañía ha utilizado la siguiente estrategia para determinar cuánta producción debe ser embarcada desde cada una de las plantas de enlatado para satisfacer las necesidades de cada uno de los almacenes.

Estrategia de embarque actual 1.

Como la enlatadora en Bellingham es la más alejada de los almacenes, envía su producción a su almacén más cercano, que es el de Sacramento, y cualquier excedente se embarca al almacén en Salt Lake City.

2.

El almacén en Albuquerque es el que se encuentra más lejos de las plantas de enlatado, por esa razón la enlatadora más cercana (la de Albert Lea) embarca su producción hacia allá y cualquier excedente va al almacén en Rapid City.

3.

Utilizan la enlatadora de Eugene para satisfacer las necesidades de los almacenes restantes.

Para la siguiente temporada de cosecha se ha realizado un cálculo de la producción de cada enlatadora y a cada almacén se le ha asignado cierta cantidad del total de suministros de guisantes. Esta información se proporciona en la tabla 15.1. Al aplicar la estrategia actual a los datos de la tabla 15.1 se obtiene el plan de embarque que se muestra en la tabla 15.2. Los costos de embarque por camión para la siguiente estación se muestran en la tabla 15.3.

TABLA 15.1 Datos de embarque para P & T Co.

Enlatadora Bellingham

Producción 75 cargas de tráiler

Almacén

80 cargas de tráiler 65 cargas de tráiler

Eugene

125 cargas de tráiler

Salt Lake City

Albert Lea

100 cargas de tráiler

Rapid City

70 cargas de tráiler

Total

300 cargas de tráiler

Albuquerque

85 cargas de tráiler

Total

15-Hillier.indd 633

Asignación

Sacramento

300 cargas de tráiler

19/12/07 11:49:36

634

Capítulo Quince Problemas de transporte y asignación

TABLA 15.2

Desde

Plan de embarque actual para P & T Co.

Hacia

Almacén Sacramento

Bellingham Enlatadora

Salt Lake City

Rapid City

Albuquerque

75

0

0

0

Eugene

5

65

55

0

Albert Lea

0

0

15

85

TABLA 15.3

Costo de embarque por carga de tráiler

Costos de embarque para P & T Co.

Desde Hacia

Almacén Sacramento

Salt Lake City

Rapid City

Albuquerque

$464

$513

$654

$867

Bellingham Enlatadora

Eugene

$352

$416

$690

$791

Albert Lea

$995

$682

$388

$685

Al combinar los datos de las tablas 15.2 y 15.3 se obtiene el costo de embarque total de acuerdo con el plan actual para la siguiente temporada: Costo de embarque total = 75(464 dólares) + 5(352 dólares)+ 65(416 dólares) + 55(690 dólares) + 15 (388 dólares) + 85(685 dólares) = 165 595 dólares Kim Baker volverá a examinar la estrategia de embarque actual para ver si puede desarrollar un nuevo plan de embarque que reduzca el costo total de embarque al mínimo absoluto.

El enfoque de la ciencia administrativa Kim reconoce de inmediato que este problema es sólo un ejemplo clásico de un problema de transporte. El planteamiento del problema en esta forma se hace de manera directa. Más aún, hay programas de computación disponibles para encontrar con rapidez una solución óptima en una computadora de escritorio. Esto le permite a Kim regresar al siguiente día con la administración para presentar un nuevo plan de embarque que reduciría el costo total del transporte en 13 000 dólares. Esta historia se desarrollará en la siguiente sección, después de que se proporcionen más conocimientos acerca de los problemas de transporte.

Preguntas de repaso

15.2

1.

¿Cuál es la preocupación específica que surge por parte del director ejecutivo de P & T Co., en este caso de estudio?

2.

¿Qué se le pide hacer a Kim Baker?

CARACTERÍSTICAS DE LOS PROBLEMAS DE TRANSPORTE El modelo para los problemas de transporte Para describir el modelo para los problemas de transporte, es necesario utilizar términos que sean menos específicos que los del problema de P & T Co. Los problemas de transporte en general se ocupan (en forma literal o figurada) de distribuir cualquier producto proveniente de cualquier grupo de centros de suministro, llamados fuentes (u orígenes), a cualquier grupo de centros de recepción, llamados destinos, en forma tal que se minimice el costo total de distribución. La equivalencia de términos entre la aplicación específica al problema de P & T Co. y el modelo general para cualquier problema de transporte se resume en la tabla 15.4.

15-Hillier.indd 634

19/12/07 11:49:36

15.2

Características de los problemas de transporte 635

Como se indica en las filas cuarta y quinta de la tabla, cada fuente tiene un cierto suministro (algunas veces llamado también oferta o recurso) de unidades que distribuir a los destinos y cada destino tiene una cierta demanda de unidades que se van a recibir de las fuentes. El modelo para un problema de transporte hace la siguiente suposición acerca de estos suministros y demandas.

TABLA 15.4 Terminología para un problema de transporte

Problema de P & T Co.

Modelo general

Cargas de tráiler de guisantes enlatados Enlatadoras Almacenes Producción de una enlatadora Asignación a un almacén Costo de embarque por carga de tráiler de una enlatadora a un almacén

Unidades de un producto Fuentes Destinos Suministro de una fuente Demanda en un destino Costo por unidad distribuida de una fuente a un destino

Suposición de requerimientos: cada fuente tiene un suministro fijo de unidades, éste debe distribuirse por completo a los destinos. En forma similar, cada destino tiene una demanda fija de unidades, ésta debe recibirse de las fuentes.

La suposición de que no hay un margen de tolerancia en las cantidades que se envían o reciben significa que debe haber un equilibrio entre el suministro total de todas las fuentes y la demanda total de todos los destinos. Propiedad de soluciones factibles: un problema de transporte tendrá soluciones factibles si y sólo sí la suma de sus suministros iguala la suma de sus demandas.

Afortunadamente estas sumas son iguales para P & T Co. ya que en la tabla 15.1 se indica que los suministros (producción) suman 300 cargas de tráiler y también las demandas (asignaciones). En algunos problemas reales, los suministros en realidad representan cantidades máximas (más que cantidades fijas) que se van a distribuir. En forma similar, en otros casos las demandas representan cantidades máximas (más que cantidades fijas) que se van a recibir. Esos problemas no encajan en el modelo de problema de transporte porque violan la suposición de los requisitos, así que son variantes de un problema de transporte. Por fortuna, es relativamente sencillo elaborar un modelo de hoja de cálculo para dichas variantes que el Excel Solver puede solucionar, como se ilustrará en la sección 15.3. La última fila de la tabla 15.4 se refiere a un costo por unidad distribuida. Esta referencia a un costo unitario implica la siguiente suposición básica para cualquier problema de transporte. Suposición de costo: el costo de distribuir unidades de una fuente en particular a un destino en particular es directamente proporcional al número de unidades distribuidas. Por lo tanto, este costo equivale al costo unitario de distribución multiplicado por el número de unidades distribuidas.

Los únicos datos que se necesitan para un modelo de problema de transporte son los suministros, las demandas y los costos unitarios. Éstos son los parámetros del modelo. Los parámetros para el problema de P & T Co. se muestran en la tabla 15.5 (incluida la descripción que implican los encabezados de columna y fila), la cual resume el modelo del problema. El modelo: cualquier problema (ya sea que incluya transporte o no) encaja en el modelo de un problema de transporte si 1) puede describirse por completo en términos de una tabla como la 15.5 que identifica todas las fuentes, destinos, suministros, demandas, costos unitarios y 2) satisface tanto la suposición de requisitos como la suposición de costos. El objetivo es minimizar el costo total de distribuir las unidades.

TABLA 15.5 Los datos del problema de P & T Co., formulados como un problema de transporte

Costo unitario Destino (almacén)

Sacramento

Salt Lake City

Rapid City

Albuquerque

Suministro

Fuente (enlatadora) Bellingham Eugene Albert Lea

$464 $352 $995

$513 $416 $682

$654 $690 $388

$867 $791 $685

75 125 100

80

65

70

85

Demanda

15-Hillier.indd 635

19/12/07 11:49:36

636

Capítulo Quince Problemas de transporte y asignación

Por lo tanto, formular un problema como uno de transporte sólo requiere llenar una tabla en el formato de la tabla 15.5. No es necesario escribir un modelo matemático formal (aunque más adelante se hará con fines de demostración). El problema de Big M Company que se presentó en la sección 3.5 es otro ejemplo de problema de transporte. En este ejemplo, las dos fábricas de la compañía necesitan enviar torrecillas a tres clientes y el objetivo es determinar cómo hacerlo para minimizar el costo total de embarque. En la tabla 3.9 se presentan los datos para este problema en el mismo formato de la tabla 15.5. Las fábricas son las fuentes, su producción son los suministros, los clientes son los destinos y los tamaños de sus pedidos son las demandas.

Uso de Excel para formular y resolver los problemas de transporte En la sección 3.5 se describe la formulación del modelo de hoja de cálculo para el problema de Big M. Ahora se hará lo mismo para el problema de P & T Co.

FIGURA 15.2 Formulación de hoja de cálculo del problema P & T Co., como un problema de transporte, incluida la celda objetivo TotalCost (J17) y las demás celdas de salida TotalShipped (H12:H14) y TotalReceived (D15:G15), así como las especificaciones que se necesitan para establecer el modelo. Las celdas cambiantes ShipmentQuantity (D12:G14) muestran el plan de embarque óptimo obtenido por el Solver. A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

B

C

D

E

F

G

H

I

J

Problema de distribución de P & T Co. Costo unitario Fuente (Enlatadora)

Cantidad de embarque (Cargas de tráiler) Fuente (Planta de enlatado)

Bellingham Eugene Albert Lea

Sacramento $464 $352 $995

Sacramento 0 Bellingham 80 Eugene 0 Albert Lea 80 Total recibido = Demanda 80

Destino (almacén) Salt Lake City Rapid City Albuquerque $513 $654 $867 $416 $690 $791 $682 $388 $685

Destino (almacén) Salt Lake City Rapid City Albuquerque Total embarcado 20 0 55 75 45 0 0 125 0 70 30 100 65 70 85 = = = 65 70 85

Suministro 75 125 100

= = =

Costo total 152 535

Nombre del rango

Celdas

Demanda Cantidad de embarque Suministro Costo total Total recibido Total embarcado Costo unitario

D17:G17 D12:G14 J12:J14 J17 D15:G15 H12:H14 D5:G7 H

15

C Total recibido

D =SUM(D12:D14)

E =SUM(E12:E14)

11

Total Embarcado

12

=SUM(D12:G12)

13

=SUM(D13:G13)

14

=SUM(D14:G14)

F =SUM(F12:F14)

G =SUM(G12:G14)

J 16 17

15-Hillier.indd 636

Costo total = SUMAPRODUCTO(Costo unitario, Cantidad embarque)

19/12/07 11:49:37

15.2

Características de los problemas de transporte 637

Las decisiones que se deben tomar son el número de camiones cargados de guisantes que se enviarán de cada enlatadora a cada almacén. Las restricciones en estas decisiones son que la cantidad total embarcada por cada enlatadora debe igualar su producción (el suministro) y la cantidad total recibida en cada almacén debe igualar su asignación (demanda). La medición general de desempeño es el costo total de embarque, así que el objetivo es minimizar esta cantidad. Esta información lleva al modelo de hoja de cálculo que se muestra en la figura 15.2 Todos los datos que se proporcionan en la tabla 15.5 se muestran en las siguientes celdas de datos: UnitCost (D5:G7), Supply (J12:J14) y Demand (D17:G17). Las decisiones acerca de las cantidades a enviar se dan en las celdas cambiantes, ShipmentQuantity (D12:G14). Las celdas de salida son TotalShipped (H12:H14) y TotalReceived (D15:G15), donde las funciones SUM que se introducen en estas celdas se muestran cerca de la parte inferior de la figura 15.2. Las restricciones, TotalShipped (H12:H14)= Supply (J12:J14) y TotaReceived (D15:G15) = Demand (D17:G17), se especifican en la hoja de cálculo y se incluyen en el cuadro de diálogo del Solver. La celda objetivo es TotalCost (J17), donde su función SUMAPRODUCTO se muestra en la esquina inferior derecha de la figura 15.2. El cuadro de diálogo del Solver especifica que el objetivo es minimizar esta celda objetivo. Una de las opciones seleccionadas del Solver (suponga no negativo) especifica que todas las cantidades de embarque deben ser no negativas. La otra (suponga un modelo lineal) indica que este problema de transporte también es de programación lineal (como se describe más adelante en esta sección). Para comenzar el proceso de resolver el problema, cualquier valor (como 0) puede introducirse en cada una de las celdas cambiantes. Luego de dar un clic en el botón Solve, el Solver utilizará el método símplex para solucionar el problema de transporte y determinar el mejor valor para cada una de las variables de decisión. Esta solución óptima se muestra en ShipmentQuantity (D12:G14) en la figura 15.2, junto con el valor resultante de 152 535 dólares en la celda objetivo de TotalCost (J17).

Representación de red de un problema de transporte Una buena forma de visualizar un problema de transporte en forma gráfica es utilizar su representación de red. Ésta ignora la disposición geográfica de las fuentes y los destinos. En su lugar, sólo alinea todas las fuentes en una columna a la izquierda (donde S1 es el símbolo de la fuente 1, etc.) y todos los destinos en una columna a la derecha (donde D1 es el símbolo para el destino 1, etc.). En la figura 15.3 se muestra la representación de red del problema P & T Co., en el que la numeración de las fuentes (enlatadoras) y destinos (almacenes) es la que se da en la figura 15.1. Las flechas muestran las rutas posibles para los camiones cargados con los guisantes enlatados; el número próximo a cada flecha es el costo de embarque (en dólares) por carga de tráiler para esa ruta. Como la figura también incluye los suministros y las demandas, engloba todos los datos que se proporcionan en la tabla 15.5. Por lo tanto, esta representación de red proporciona otra manera de resumir el modelo de un problema de transporte. Como el problema de Big M Company que se presentó en la sección 3.5 también es de transporte, tiene una representación de red como la de la figura 15.3, y se muestra en la figura 3.9. Demandas

FIGURA 15.3 La representación de red del problema de transporte de P & T Co., muestra todos los datos de la tabla 15.5 en forma gráfica.

Suministros Destinos Fuentes (Bellingham) 75

(Eugene) 125

(Albert Lea) 100

S1

S2

S3

464 513 654 867 351 416 690 791 995 682 388

D1

80 (Sacramento)

D2

65 (Salt Lake City)

D3

70 (Rapid city)

685

D4

15-Hillier.indd 637

(85 Albuquerque)

19/12/07 11:49:37

638

Capítulo Quince Problemas de transporte y asignación

Para problemas de transporte más grandes que el de P & T Co., no es muy conveniente dibujar la red completa y mostrar todos los datos. En consecuencia, la representación de red es principalmente una estrategia de visualización. Recuerde que en la sección 3.5 se describieron los probelmas de transporte como una categoría importante de los problemas de programación lineal que con frecuencia incluyen la distribución de productos a través de una red de distribución. Las redes de las figuras 3.5 y 15.3 son un tipo simple de red de distribución en la que cada línea de embarque va directamente de una fuente a un destino. Recuerde que en el capítulo 6 se presentaron algunos tipos relacionados de problemas de optimizacion de red que a veces también incluyen la distribución de productos a través de una red de distribución. De hecho, en la sección 6.1 se señala que los problemas de transporte son un tipo especial de problema de flujo de costo mínimo que por lo general incluye el movimiento de productos a través de una red de distribución.

El problema de transporte es de programación lineal Para demostrar que el problema de P & T Co. (o algún otro de transporte) es, de hecho, de programación lineal, se va a formular su modelo matemático en forma algebraica. Al utilizar la numeración de enlatadoras y almacenes que se da en la figura 15.1, xij será el número de cargas de tráiler que se embarcará desde la enlatadora i al almacén j para cada i = 1, 2, 3 y j = 1, 2, 3, 4. El objetivo es elegir los valores de estas 12 variables de decisión (la xij) de manera que Minimizar el costo = 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22 + 690x23 + 791x24 + 995x31 + 682x32 + 388x33 + 685x34, sujeto a las restricciones x11 + x12 + x13

+ x14 x21

+ x22

=

125

x31 + x32 + x33 + x34 =

100

+ x31 + x22

x12

75

+ x23 + x24

+ x21

x11

=

+ x32 + x23

x13 x14

+ x33 + x24

=

80

=

65

=

70

+ x34 =

85

y xij ≥ 0 (i = 1, 2, 3; j = 1, 2, 3, 4). Éste es sin duda un problema de programación lineal. P & T Co., siempre envía cargas de tráiler completas de guisantes enlatados, ya que cualquier cantidad inferior no resultaría económica. Esto implica que cada xij debe tener un valor entero (0, 1, 2,…). Para evitar obtener una solución óptima para este modelo que asigne valores fraccionarios a cualquiera de las variables de decisión, se podría agregar otro conjunto de restricciones que especifiquen que xij debe tener un valor entero. Esto convertiría este problema de programación lineal en uno de programación entera, que es más difícil de resolver. (Recuerde que los problemas de programación entera se analizaron en los capítulos 3 y 7.) Por fortuna, esta conversión no es necesaria por la siguiente propiedad de los problemas de transporte. Propiedad de soluciones con enteros: siempre que todos los suministros y demandas tengan valores enteros, está garantizado que cualquier problema de transporte con soluciones factibles tendrá una solución optima con valores enteros para todas sus variables de decisión. Por lo tanto, no es necesario agregar restricciones al modelo que especifiquen que las variables sólo tengan valores enteros.

Al tratar con problemas de transporte, por lo general los practicantes no se molestan en escribir el modelo de programación lineal completo en forma algebraica porque toda la información esencial

15-Hillier.indd 638

19/12/07 11:49:37

15.2

Características de los problemas de transporte 639

puede presentarse en forma mucho más compacta en una tabla como la 15.5 o en el modelo de hoja de cálculo correspondiente. Pero antes de terminar con este modelo de programación lineal, observe bien las restricciones funcionales en el lado izquierdo. Observe que cada coeficiente es 0 (así que la variable se elimina) o 1. También note el patrón distintivo para las ubicaciones de los coeficientes de 1, incluido el hecho de que cada variable tiene un coeficiente de 1 en exactamente dos restricciones. Estas características distintivas de los coeficientes tienen una función importante para resolver los problemas de transporte de una manera extremadamente eficiente.

Solución de problemas de transporte Como los problemas de transporte son de un tipo especial de programación lineal, pueden ser resueltos por el método símplex (el procedimiento que utiliza el Excel Solver para solucionar problemas de programación lineal). Sin embargo, debido al muy particular patrón de coeficientes en las restricciones funcionales que se señalaron antes, es posible agilizar en gran medida el método símplex para resolver problemas de transporte con mucha mayor rapidez. Esta versión agil del método símplex se llama método símplex de transporte. En ocasiones puede resolver grandes problemas de transporte más de 100 veces más rápido que el método símplex regular. Sin embargo, sólo es aplicable a este tipo de problemas. Al igual que un problema de transporte, otros problemas de flujo de costo-mínimo también tienen un patrón distintivo similar de coeficientes en sus restricciones funcionales. Por lo tanto, el método símplex puede agilizarse en gran medida en la misma forma que el método símplex de transporte para solucionar cualquier problema de flujo de costo mínimo (incluidos los de transporte) con mucha rapidez. Este método aerodinámico se llama método símplex de red. Los programas de cómputo de programación lineal con frecuencia incluye el método símplex y a veces también el método símplex de transporte. Cuando sólo está disponible el método símplex de red, proporciona una excelente alternativa para resolver los problemas de transporte. De hecho, en los últimos años el método símplex de red cada vez compite más con el método símplex de transporte. Luego de obtener una solución óptima para los problemas de transporte, por lo general se hace un análisis de que pasa si casi en la misma forma que se describió en el capítulo 5 para otros problemas de programación lineal. El método símplex de transporte o el de red puede obtener con facilidad el intervalo permisible para cada coeficiente en la función objetivo. Tratar con cambios en los lados derechos (suministros y demandas) es mucho más complicado ahora debido al requisito de que la suma de los suministros debe igualar la suma de las demandas. Así, cada cambio en un suministro debe ir acompañado por el cambio correspondiente en la demanda (o demandas) y viceversa. Como Excel Solver no se concibió para resolver los problemas de programación lineal en verdad grandes que con frecuencia surgen en la práctica, simplemente utiliza el método símplex para resolver los problemas de transporte y otros problemas de flujo de costo mínimo que se presentan en este texto (y algunos otros considerablemente más grandes), así que se continúa con el uso del Solver (o Premium Solver) y se renunciará a utilizar el método símplex de transporte o el método símplex de red.

Final del caso de estudio P & T Co. Ahora se puede resumir el final de la historia de cómo P & T pudo mejorar en forma sustancial el plan de embarques actual que se muestra en la tabla 15.2, que tiene un costo total de 165 595 dólares. Usted ya ha visto cómo Kim Baker pudo formular este problema como uno de transporte con sólo llenar la tabla que se presentó con el número 15.5. La elaboración correspondiente en una hoja de cálculo se mostró en la figura 15.2. Después, al aplicar el Solver se obtuvo la solución óptima que se mostró en ShiftmentQuantity (D12:G14) Note que esta solución óptima no es intuitiva. De las 75 cargas de tráiler que suministra Bellingham, 55 se envían a Albuquerque, aunque esto cuesta mucho más (867 dólares por carga de tráiler) que mandarlas a cualquier otro almacén. Sin embargo, este sacrificio para la enlatadora 1 permite embarques de bajo costo para las plantas de enlatado 2 y 3. Aunque sería difícil encontrar esta solución óptima en forma manual, el método símplex de Excel Solver lo encuentra con rapidez. Como se presenta en la celda objetivo TotalCost (J17), el costo total de embarque para este plan óptimo es Costo total de embarque = 20($513) + 55($867) + 80($352) + 45($416) + 70($388) + 30($685) = $152 535

15-Hillier.indd 639

19/12/07 11:49:37

640

Capítulo Quince Problemas de transporte y asignación

una reducción de 13 060 dólares con respecto al plan de embarque actual. Richard Powers está complacido de informar esta reducción al director ejecutivo, Douglas Whitson, quien los felicita a él y a Kim Baker por lograr estos ahorros significativos.

Una aplicación ganadora de un premio por un problema de transporte Excepto por su tamaño pequeño, el problema de P & T Co. es muy similar a los que enfrentan muchas corporaciones que deben embarcar productos de sus plantas de manufactura hacia sus clientes. Por ejemplo, considere un estudio de ciencia administrativa ganador de un premio que se realizó en Procter & Gamble (como se describió en el ejemplar de Interfaces de enero-febrero de 1997). Antes del estudio, la cadena de suministro de la compañía consistía de cientos de proveedores, más de 50 categorías de productos, más de 60 plantas, 16 centros de distribución y más de 1 000 zonas de clientes. Sin embargo, conforme la compañía se acercó más al perfil de las marcas globales, la administración se percató de que necesitaba consolidar las plantas para reducir los gastos de manufactura, mejorar la velocidad de puesta en el mercado y reducir la inversión de capital. Por lo tanto, el estudio se enfocó en rediseñar los sistemas de producción y distribución de la compañía para sus operaciones en América del Norte. El resultado fue una reducción en el número de plantas de Nortemérica en casi 20 por ciento, con un ahorro de más de 200 millones de dólares en costos antes de impuestos por año. Una parte importante del estudio giró alrededor de formular y resolver problemas de transporte para categorías de productos individuales. Para cada opción relacionada con las plantas que se mantendrían abiertas y otros aspectos, resolver el problema de transporte correspondiente a una categoría demostró que el costo de distribución residía en embarcar el producto en cuestión desde las plantas a los centros de distribución y las zonas de clientes. En el proceso de identificar el mejor sistema nuevo de producción se solucionaron numerosos problemas de transporte y distribución.

Preguntas de repaso

15.3

1.

Proporcione una descripción de los problemas de transporte en una frase.

2.

¿Qué datos se necesitan para elaborar el modelo de un problema de transporte?

3.

¿Qué debe hacerse para formular un problema como uno de transporte?

4.

¿Qué se requiere para que un problema de transporte tenga soluciones factibles?

5.

¿En qué circunstancias un problema de transporte tendrá en forma automática una solución óptima con valores enteros para todas sus variables de decisión?

6.

Nombre dos algoritmos que pueden resolver problemas de transporte con mucha mayor rapidez que el método símplex general.

VARIANTES DE MODELAJE DE LOS PROBLEMAS DE TRANSPORTE El caso de P & T es un ejemplo de un problema de transporte donde todo encaja en forma inmediata. La vida real rara vez es tan fácil. Con frecuencia surgen problemas de programación lineal que son casi problemas de transporte, pero una o más características no encajan del todo. Aquí se presentan las características que considerarán en esta sección. 1.

La suma de los suministros excede la suma de las demandas, así que cada suministro representa una cantidad máxima (no una cantidad fija) que se distribuirá desde esa fuente.

2.

La suma de los suministros es menor que la suma de las demandas, de manera que cada demanda representa una cantidad máxima (no una cantidad fija) que será recibida en ese destino.

3.

Un destino tiene una demanda mínima y una demanda máxima, de modo que puede recibirse cualquier cantidad entre estos dos valores.

4.

Ciertas combinaciones fuente-destino no se pueden utilizar para unidades de distribución.

5.

El objetivo es maximizar la utilidad total asociada con la distribución de unidades más que reducir el costo total.

Por cada una de estas características es posible reformular el problema en una manera inteligente para hacerlo encajar en el formato de uno de transporte. Cuando esto se hace con un problema

15-Hillier.indd 640

19/12/07 11:49:37

15.3

Variantes de modelaje de los problemas de transporte 641

realmente grande (por ejemplo, uno con muchos cientos o miles de fuentes y destinos) es muy útil porque el método símplex de transporte o el método símplex de red puede resolver el problema en este formato en mucho menos tiempo (tal vez más de 100 veces más rápido) que el que emplea el método símplex para resolver la formulación de programación lineal general. Sin embargo, cuando el problema no es realmente grande, el método símplex todavía es capaz de resolver la formulación de programación lineal general en un periodo razonable. Por lo tanto, un paquete de computación básico (como el Excel Solver) que incluya el método símplex pero no el método símplex de transporte o el método símplex de red puede aplicarse a esos problemas sin tratar de forzarlos en el formato de un problema de transporte. Éste es el enfoque que se utilizará. En particular, en esta sección se ilustra la formulación de modelos de hojas de cálculo para variantes de problemas de transporte que tienen algunas de las características que se enlistaron antes. El primer ejemplo se enfoca en las características 1 y 4. Un segundo ejemplo ilustrará las demás características.

Ejemplo 1: asignación de plantas a los productos Better Products Company ha decidido iniciar la producción de cuatro nuevos productos por medio de tres plantas que en la actualidad tienen una capacidad de producción en exceso. Los productos requieren un esfuerzo de producción por unidad similar, de modo que la capacidad de producción disponible de las plantas se mide por el número de unidades de cualquier producto que pueden fabricar al día, como se consigna en la columna de la extrema derecha de la tabla 15.6. La fila inferior da la tasa de producción que se requiere (número de unidades producidas por día) para cumplir con las ventas proyectadas. Cada planta puede fabricar cualquiera de los productos, excepto la planta 2 que no puede elaborar el producto 3. Sin embargo, los costos variables por unidad de cada producto difieren de planta en planta, como se muestra en el cuerpo principal de la tabla. La administración necesita ahora tomar una decisión acerca de cuáles plantas deben producir qué productos. La repartición de productos, es decir la fabricación del mismo producto en más de una planta, está permitida. (Regresaremos a este ejemplo en la sección 15.7 para considerar el caso en el que la repartición de producto está prohibida, lo que requiere un tipo distinto de formulación.)

Formulación de un modelo de hoja de cálculo El problema es casi un problema de transporte. De hecho, luego de sustituir la terminología convencional (suministro, demanda, etc.) por los títulos de las columnas y filas en la tabla 15.6, básicamente encaja en la formulación de un problema de transporte, como se muestra en la tabla 15.7. Pero hay dos formas en las que este problema se desvía de un problema de transporte.

TABLA 15.6 Datos del problema Better Products Co.

Costo unitario Producto: Planta 1 2 3 Producción requerida

1

2

3

4

$41 $40 $37

$27 $29 $30

$28 — $27

$24 $23 $21

20

30

30

40

3

4

TABLA 15.7 Datos para el problema de Better Products Co., formulados como una variante de un problema de transporte

15-Hillier.indd 641

Capacidad disponible 75 75 45

Costo unitario Destino (producto)

1

2

1 2 3

$41 $40 $37

$27 $29 $30

$28 — $27

$24 $23 $21

Demanda

20

30

30

40

Suministro

Fuente (planta) 75 75 45

19/12/07 11:49:38

642

Capítulo Quince Problemas de transporte y asignación

Una desviación (menor) es que un problema de transporte requiere un costo unitario por cada fuente-destino, pero la planta 2 no puede producir el producto 3, así que no hay un costo unitario disponible para esta combinación en particular. La otra desviación es que la suma de los suministros (75 + 75 + 45 = 195) excede la suma de las demandas (20 + 30 + 30 + 40 = 120) en la tabla 15.7. Así, como lo indica la propiedad de soluciones factibles (sección 15.2), el problema de transporte representado por la tabla 15.7 no tendría soluciones factibles. La suposición de requisitos (sección 15.2) especifica que se debe utilizar el suministro completo de cada fuente. En realidad, los suministros en la tabla 15.7 representan capacidades de producción que no necesitarán utilizarse en su totalidad para cumplir con la demanda de ventas para los productos. Así, estos suministros son límites superiores de las cantidades que se utilizarán. El modelo de hoja de cálculo para este problema, que se muestra en la figura 15.4, tiene el mismo formato que el de la figura 15.2 para el problema de transporte de P & T Co. con dos diferen-

FIGURA 15.4 Formulación de hoja de cálculo del problema Better Products Co., como una variante de un problema de transporte, incluida la celda objetivo TotalCost (I16) y las demás celdas de producción ProducedAtPlant (G11:G13) y ProductsProduced (C14:F14), así como las especificaciones necesarias para establecer el modelo. Las celdas cambiantes DailyProduction (C11:F13) muestran el plan de producción óptimo obtenido por el Solver. A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

B

C

D

E

F

G

H

I

Problema de planeación de producción de Better Products Co. Costo unitario Planta 1 Planta 2 Planta 3

Producción diaria Planta 1 Planta 2 Planta 3 Productos fabricados Producción requerida

Producto 1 $41 $40 $37

Producto 2 $27 $29 $30

Producto 3 $28 — $27

Producto 4 $24 $23 $21

Producto 1 0 0 20 20 = 20

Producto 2 30 0 0 30 = 30

Producto 3 30 0 0 30 = 30

Producto 4 0 15 25 40 = 40

Producidos Capacidad en planta