Modelos de transporte,

asignación y redes

OBJETIVOS DE APRENDIZAJE

Después de estudiar este capítulo, el alumno será capaz de:

1. Estructurar problemas de PL para los modelos de 3. Utilizar PL para modelar problemas de la ruta
transporte, transbordo y asignación. más corta y del flujo máximo.
2. Resolver problemas de localización de instalaciones 4. Resolver problemas de árboles de expansión
y otras aplicaciones con modelos de transporte. mínima.

CONTENIDO DEL CAPÍTULO

9.1 Introducción 9.5 Problema del flujo máximo

9.2 El problema de transporte 9.6 Problema de la ruta más corta
9.3 El problema de asignación 9.7 Problema del árbol de expansión mínima
9.4 El problema de transbordo

Resumen • Glosario • Problemas resueltos • Autoevaluación • Preguntas para análisis y problemas • Estudio de caso:
Andrew-Carter, Inc. • Estudio de caso: Northeastern Airlines • Estudio de caso: Problemas de tránsito en la Southwestern
University • Estudios de caso en Internet • Bibliografía
Apéndice 9.1: Uso de QM para Windows

323
324 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

9.1 Introducción
En el capítulo 8 vimos ejemplos de una serie de prol lemas administrativos que podrían plantearse me-
diante la programación lineal (PL) y, en este capítulo, studiaremos aún más ejemplos de este tipo. Sin em-
bargo, todos los problemas de este capítulo pueden pl atearse como redes y usando también programación
lineal. El uso de redes ayuda a visualizar y a compre der el problema de administración. Estos modelos
incluyen problemas de transporte, transbordo y asignación, el problema del flujo máximo, el problema de
la ruta más corta y el problema del árbol de expansión mínima. En este capítulo, el principal medio para
resolver estos problemas es el uso de software de programación lineal. No obstante, para tomar ventaja
de la estructura única de algunos de estos problemas, se han desarrollado algoritmos especializados para
resolver problemas muy grandes de manera más rápi a y eficiente. Dichos algoritmos se presentan en el
módulo 8 del sitio web que acompaña a este texto.
El problema básico de transporte se relaciona c n la búsqueda de la mejor manera (por lo general,
al menor costo) de distribuir bienes que provienen' d fuentes como fábricas, en varios destinos finales,
como puntos de venta. Si existen puntos intermedios, or ejemplo, centros de distribución regionales, hacia
donde deben ir los artículos antes de ser enviados a su' destino final, entonces el problema de transporte se
convierte en un problema de transbordo. El problema de asignación consiste en encontrar la mejor forma
(por lo general, al menor costo) de asignar individuos o piezas de equipo a varios proyectos o trabajos. La
manera de realizar esta asignación es uno a uno; en otras palabras, a cada persona se le asigna un solo tra-
bajo, y cada trabajo solamente necesita una persona as gnada a él.
La técnica de flujo máximo encuentra el flujo áximo de cualquier cantidad o sustancia a través
de una red. Esta técnica puede determinar, por ejem lo, el número máximo de vehículos (automóviles,
camiones, etcétera) que pueden circular a través de urja red de carreteras de un lugar a otro. La técnica de
la ruta más corta puede encontrar cuál es la trayectoria de menor longitud a través de una red. Por ejem-
plo, esta técnica puede encontrar la ruta más corta de una ciudad a otra, a través de una red de carreteras.
La técnica del árbol de expansión mínima determina la ruta a través de la red que conecta todos los puntos
y minimiza la distancia total. Cuando los puntos representan casas en un vecindario, la técnica del árbol
de expansión mínima se utiliza para determinar cómo conectar todas las casas a la energía eléctrica, al
sistema de agua, etcétera, de manera que se minimice la distancia total, la longitud de las líneas eléctricas
o las tuberías de agua.
Aunque en este capítulo se presentan muchos ejemplos diferentes, existe cierta terminología común a
Los círculos en las redes se denominan todos los modelos de redes. Los puntos de la red se c noten como nodos y las líneas de la red que conec-
nodos. Las líneas que los conectan se tan los nodos se denominan arcos. Regularmente los odos se grafican como círculos, aunque a veces se
llaman arcos. usan cuadrados o rectángulos para representarlos.

EN ACCIÓN Optimización en UPS

desarrollar modele s de optimización y mejorar la eficiencia, la com-

T NT Express es una de las empresas de entrega de paquetería más
grandes del mundo. Los 77,000 empleados de la compañía manejan
pañía enseñó a su empleados los conceptos básicos de administra-
ción de operacionls y ciencias de la administración, para que todos
más de 4 millones de paquetes cada semana, con cerca de 30,000 reconocieran las oportunidades de mejora a través de la utilización
camiones y otros vehículos y aproximadamente 50 aviones. El man- de esas técnicas.
tenimiento de un alto nivel de servicio al cliente, conservando cos- El resultado d e la implementación de tales prácticas en TNT Ex-
tos bajos mediante operaciones eficientes, es una tarea de enormes press representó u n ahorro en costos de 207 millones de euros entre
proporciones. En 2005 el director de operaciones de TNT Express 2008 y 2011. Otros beneficios incluyen una reducción de las emi-
consideró el uso de modelos de investigación de operaciones para siones de CO2 de us vehículos por 283 millones de kilogramos, un
mejorar la red de entregas por carretera en Italia. La incorporación mejor trabajo en r d con otros empleados de la empresa y un senti-
de modelos de optimización en todos los aspectos de la cadena de miento de empod Iramiento, dado que ahora los trabajadores sienten
suministro de la compañía le generó una disminución en costos que pueden obten r apoyo de sus colegas fuera de sus unidades ope-
de más de 6 por ciento. rativas o incluso fu ra de su propio país. Los modelos de optimización
Se desarrollaron varias iniciativas para mejorar la cadena de realmente entrega on un paquete de beneficios a TNT Express.
suministro. Se creó la Academia de Optimización Global (GO) para
enseñar a los empleados los principios de la optimización. Se desa-
rrollaron Comunidades de Práctica (CoPs) y los empleados clave se Fuente: Basado en I Fleuren. C. Goossens, M. Hendricks, M.-L. Lombard y
reúnen tres veces al año para discutir y compartir sus mejores prác- J. Poppelaars. "Supp y Chain Wide Optimization at TNT Express", Interfaces
ticas con los proveedores y miembros de la academia. Además de 43, 1 (enero/febrero e 2013): 5-20.
 9.2 EL PROBLEMA DE TRANSPORTE 325

9.2 El problema de transporte

El problema de transporte se ocupa de la distribución de bienes desde varios puntos de suministro (orí-
genes o fuentes) hasta una serie de puntos de demanda (destinos). Por lo general, se tiene una capacidad
(oferta) de bienes en cada fuente, un requisito (demanda) de bienes en cada destino y un costo de envío
por unidad desde cada fuente hasta cada destino. En la figura 9.1 se muestra un ejemplo. El objetivo de este
problema es programar los envíos de manera que se minimicen los costos totales de transporte. En ocasio-
nes, también se incluyen los costos de producción.
Los modelos de transporte también pueden utilizarse cuando una empresa está tratando de decidir
dónde ubicar una nueva planta. Antes de la apertura de un almacén, una fábrica u oficina de ventas nuevos,
una buena práctica es considerar varios sitios alternativos. Las buenas decisiones financieras relativas a la
ubicación de una instalación también intentan minimizar los costos totales de transporte y producción para
todo el sistema.

Programación lineal para el ejemplo de transporte

La corporación Executive Furniture se enfrenta al problema de transporte mostrado en la figura 9.1. La
compañía desea minimizar los costos de transporte, al tiempo que satisface la demanda en cada destino
y no supera la oferta de cada fuente. Al formular esto como un problema de programación lineal, hay
tres restricciones de oferta (una para cada fuente) y tres restricciones de demanda (una para cada destino).
Las decisiones a tomar son el número de unidades que deben enviarse en cada ruta, así que hay una varia-
ble de decisión por cada arco (flecha) en la red. Sean
xu = número de unidades enviadas desde la fuente i hasta el destino]
donde

i = 1, 2, 3, con 1 = Des Moines, 2 = Evansville y 3 = Fort Lauderdale

j = 1, 2, 3, con 1 = Albuquerque, 2 = Boston y 3 = Cleveland

La formulación de PL es

Minimizar el costo total = 5X11 + 4X12 + 3X13 + 8X21 + 4X22

3X23 9X31 7X32 5X33
sujeto a
X11 + X12 + X13 100 (oferta de Des Moines)
X21 +X22 +X23 300 (oferta de Evansville)
X31 + X32 X33 300 (oferta de Fort Lauderdale)
+ X21 + X31 = 300 (demanda de Albuquerque)
X12 ± X22 -4- X32 = 200 (demanda de Boston)
X13 + X23 + X33 = 200 (demanda Cleveland)
O para toda i y j

La solución se encuentra mediante el uso de software de computadora, y la solución óptima de envíos

es la siguiente:
100 unidades de Des Moines a Albuquerque
200 unidades de Evansville a Boston
100 unidades de Evansville a Cleveland
200 unidades de Ft. Lauderdale a Albuquerque
100 unidades de Ft. Lauderdale a Cleveland
El costo total es de $3,900. En la siguiente sección se ilustrará la forma en que se encontró esta solución.

Resolución de problemas de transporte mediante

el uso de software de computadora
La solución a este problema de transporte, planteado como un problema de PL, se determina utilizando
Solver en Excel 2013, como se ilustró en el capítulo 7, mediante el uso de QM para Windows o emplean-
do Excel QM en Excel 2013. Cuando se utiliza Excel 2013 y Solver, las restricciones pueden introducirse
en filas como se indicó en el capítulo 7. Sin embargo, la estructura especial de este problema permite una
326 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

FIGURA 9.1
Fuente Destino
Representación en red
de un problema de Oferta Demanda
transporte, con costos,
demandas y ofertas $5
Des Moines Albuquerque
100 300
(Fuente 1) (Destino 1)
:4

S3

$8

Evansville Boston
300 200
(Fuente 2) (Destino 2)

S3

300
Fort Lauderdale
(Fuente 3)
9

/\ $5
Cleveland
(Destino 3)
200

entrada más sencilla y más intuitiva en Excel 2013 con Solver, y para este ejemplo se utilizará Excel QM
con la finalidad de ilustrar esto.
El programa 9.1 presenta los datos de entrada y la solución a este ejemplo. Haga clic en la pestaña
de Excel QM y seleccione el menú Alphabetical de la barra de Excel QM. Cuando aparezca el menú, des-
plácese hacia abajo y elija Transportation. En la ventana de entrada que se abre, introduzca el número de
orígenes o fuentes (3 en este ejemplo), el número de destinos (3 para este ejemplo), seleccione Minimize
y haga clic en OK. Aparecerá una hoja de cálculo, donde se introducen los costos, las ofertas y demandas
mostradas en la tabla de datos. Luego haga clic en la pestaña Data, seleccione Solver de la barra Data y
haga clic en Solve en la ventana de entrada de Solver. No es necesario escribir ninguna fórmula ni cambiar
ninguno de los parámetros.

Un modelo general de PL para problemas de transporte

En este ejemplo, había 3 fuentes y 3 destinos. El PL tenía 3 X 3 = 9 variables y 3 + 3 = 6 restriccio-
nes. En general, para un problema de transporte con m fuentes y n destinos, el número de variables es
mn, y el número de restricciones es m + n. Por ejemplo, si hay 5 restricciones (es decir, m = 5) y 8 varia-

PROGRAMA 9.1 De la barra de Excel QM, seleccione De la pestaña Data, seleccione'

Solución para la el menú (Alphabetical o By Chapter). Solver y haga clic en Solve.
Elija Transportation en el menú
corporación Executive Faca on roma, om mrsciver vi me
desplegable y, después, introduzca
Furniture en Excel 2013 105 3 orígenes (fuentes) y los 3 destinos. ,.)fotnsuuctwts.
usando Excel QM
COSTS Albuquerque Boston rieveland Supply
10 Des Moines 5 4 3 1 100
Evansville a 4 3 I 300
Ft. lauderdale 9 7 5 300
13 Demancl 300 200 200 700 \ 700 -------.....
14
Complete la tabla con los costos,)
Shipments
Shipments Albuquerque
las ofe1tas y las demandas.
Des Moines
F van vIlle
100 100
300
F
' 3 Ft. Lauderdale 100 300
2C [Minn Total 200 200 700\700 La solución se
21 muestra aquí.
22 ; Total Cosí 3900 I
 92 EL PROBLEMA DE TRANSPORTE 327

El número de variables y restricciones bles (es decir, n = 8), el problema de programación lineal tendría 5 (8) = 40 variables y 5 + 8 = 13
para un problema típico de restricciones.
transporte se puede encontrar El uso de subíndices dobles en las variables facilita la expresión de la forma general del problema
a partir del número de fuentes de programación lineal para un problema de transporte, con m fuentes y n destinos. Sean
y destinos.
= número de unidades enviadas desde la fuente i hasta el destino j
cy = costo de una unidad desde la fuente i hasta el destino j
= oferta en la fuente i
di = demanda en el destino j
El modelo de programación lineal es
n m
Minimizar el costo = E Ecijx,y
.m1 i=1

sujeto a

= 1,2, ... ,m
J=1
= j = 1, 2, . . . , n
i=i
xu O para toda i y j

Análisis de la localización de instalaciones

El método de transporte ha demostrado ser especialmente útil para ayudar a una empresa a decidir dónde
ubicar una fábrica o almacén nuevos. Dado que una nueva localización es un tema de gran importancia
La localización de una nueva financiera para una empresa, por lo general se deben considerar y evaluar varios sitios alternativos. Aunque
instalación dentro de un sistema se toma en cuenta una amplia gama de factores subjetivos, como la calidad de la oferta de mano de obra, la
de distribución general se apoya presencia de sindicatos, la actitud y aceptación de la comunidad, y los servicios públicos y las instalaciones
en el método de transporte. recreativas y educativas para los trabajadores, una decisión final también implica minimizar los costos
totales de envío y de producción. Lo anterior significa que cada ubicación alternativa de las instalaciones
debería analizarse en el marco de un sistema de distribución general.
Para determinar cuál de los dos sitios se debe seleccionar para una nueva planta de producción, se
desarrollarán modelos de programación lineal para dos problemas de transporte, uno para cada ubicación.
Si se estuvieran considerando tres o más lugares, se desarrollaría un problema de transporte como modelo
de programación lineal para cada uno de éstos. En cada modelo se utilizan las fuentes y los destinos exis-
tentes, y se incluye también una nueva fuente. Con esto se encuentra el costo mínimo para el sistema de
distribución, si se agrega una fuente al sistema. Lo anterior se repite para la segunda fuente, y los costos
mínimos de estos dos problemas se compararán para encontrar cuál es mejor. El método descrito se ilustra
en el siguiente ejemplo.
La compañía Hardgrave Machine produce componentes de computadora en sus plantas de Cincinnati,
Salt Lake City y Pittsburgh. Dichas plantas no han sido capaces de -mantenerse al día con la demanda de
pedidos en cuatro almacenes que posee Hardgrave en Detroit, Dallas, Nueva York y Los Ángeles. Como
resultado, la compañía ha decidido construir una nueva planta para ampliar su capacidad productiva. Los
dos sitios que se están considerando son Seattle y Birmingham; ambas ciudades son atractivas en términos
de la oferta de mano de obra y de servicios públicos, y la facilidad de financiamiento de la fábrica.
En la tabla 9.1 se presentan los costos y los requisitos de producción para cada una de las tres plantas
existentes, la demanda en cada uno de los cuatro almacenes, y los costos de producción estimados para las
nuevas plantas propuestas. Los costos de transporte desde cada planta hasta cada almacén se resumen en
la tabla 9.2.
La pregunta importante que Hardgrave enfrenta ahora es la siguiente: ¿Cuál de las nuevas ubicaciones
generará el menor costo para la compañía, en combinación con las plantas y los almacenes existentes?
Tenga en cuenta que el costo de cada ruta individual de una planta a un almacén se encuentra mediante la
suma de los costos de envío (en el cuerpo de la tabla 9.2) más los costos unitarios de producción respecti-
vos (de la tabla 9.1). Por lo tanto, el costo total de producción más el costo de envío de un componente de
Para encontrar la nueva planta computadora desde Cincinnati hasta Detroit es de $73 ($25 por el envío más $48 por la producción).
con el menor costo del sistema, Con la finalidad de determinar cuál de las nuevas plantas (Seattle o Birmingham) presenta el menor
resolvemos dos problemas de costo total para todo el sistema de distribución y producción, se resuelven dos problemas de transporte:
transporte. uno para cada una de las dos combinaciones posibles. El primer problema de programación lineal será para
328 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

TABLA 9.1
DEMANDA
Datos de la demanda y •MENSUAL PLANTA E OFERTA COSTO DE PRODUCIR
la oferta de Hardgrave N (UNIDADES) PRODUCCI N MENSUAL UNA UNIDAD (S)

Detroit 10,000 Cincinnati 15,000 48

Dallas 12,000 Salt Lake Ci :y 6,000 50
Nueva York 15,000 Pittsburgh 14,000 52
Los Ángeles 9,000 35,000
46,000
Oferta necesaria para la nueva planta = 46,000 — 35,000 = 11,000 unidades mensuales

ESTINIACIÓN DE COSTOS DE PRODUCCIÓN

POR UNIDAD EN LAS PLANTAS PROPUESTAS
Seattle $53
Birmingham $49

TABLA 9.2 NUEVA LOS

Costos de envío ----4141114111101
lliblimilam._ 1111111 DETROIT DAI .LAS YORK ÁNGELES
de Hardgrave
ICINCfNNATI
" . $25 S55 $40 $60
35 30 50 40
,I
SALT LAKE MY
- -
' PMSBURGH 36 45 26 66
SEATTLE 60 38 65 27
35 30 41 50
BIRMINGHAM

la ubicación de Seattle, y el segundo será para Birmingham. Al evaluar la ubicación en Seattle, las varia-
bles se definen como sigue:
= número de unidades enviadas de la fuente i al destino j
donde
i = 1, 2, 3, 4 con 1 = Cincinnati, 2 = Salt Lake City, 3 = Pittsburgh y 4 = Seattle
j = 1, 2, 3, 4 con 1 = Detroit, 2 = Dallas. 3 = Nueva York y 4 = Los Ángeles
La formulación del problema de programación lineal tiene un objetivo de minimizar el costo total: costo de
transporte más costo de producción.
Minimizar el costo total = 73X11 + 103X12 + 88X13 + 108X14 + 852(21 + 80X22 + 100X23
+ 90X24 + 88X31 + 97X32 + 782(33 + 11844 + 113X41 + 91X42 + 118X43 + 80X44
sujeto a
xi I + x21 + X31 + X41 = 10,000 demanda en Detroit
X12 + X22 + X32 + X42 = 12,000 demanda en Dallas
X13 + X23 + X33 + X43 = 15,000 demanda en Nueva York
X14 + X24 + X34 + X44 = 9,000 demanda en Los Ángeles
X11 + X12 + X13 + X14 5 15,000 oferta de Cincinnati
X21 + X22 + X23 + X24 S 6,000 oferta de Salt Lake City
X31 + X32 + X33 + X34 14,000 oferta de Pittsburgh
X41 + X42 + X43 + X44 5- 11,000 oferta de Seattle
Todas las variables O
Al resolver esto, se encuentra que el costo total con localización de Seattle es de $3,704,000.
 9.2 EL PROBLEMA DE TRANSPORTE 329

Para el segundo modelo de transporte, el problema de programación lineal se modifica y la ubicación

de Birmingham sustituye la de Seattle. Ahora en el problema de programación lineal, i = 4 representa
Birmingham en vez de Seattle, la última restricción es para Birmingham en lugar de Seattle, y los costos
de estas cuatro variables en la función objetivo ahora son 84 para X41, 79 para X42, 90 para X43 y 99 para
X44. No hay ningún otro cambio en el problema. Cuando éste se resuelve, el costo total con la ubicación
de Birmingham es de $3,741,000. Por lo tanto, los resultados de la localización de Seattle tienen un menor
costo total y sería la ubicación seleccionada con base en el costo.
En este ejemplo se usará Excel QM, y el programa 9.2 presenta la solución al problema con la ubi-
cación de Seattle. Para introducir el problema, haga clic en la pestaña de Excel QM, seleccione el menú
Alphabetical de la barra de Excel QM y, cuando aparezca el menú, desplácese hacia abajo para elegir
Transportation. Se abrirá una ventana de entrada y sólo debe introducir el número de orígenes (fuentes), el
número de destinos, seleccionar Minimize y hacer clic en OK. En seguida se despliega una hoja de cálculo
donde puede introducir las cifras de los costos, las ofertas y las demandas mostradas en la tabla de datos
del programa 9.2. Una vez que se hayan introducido todos los datos, haga clic en la pestaña Data, elija
Solver y haga clic en Solve en la ventana de entrada de Solver. No es necesario introducir ningún dato
adicional en Solver. Los envíos de la solución óptima se muestran en la tabla Shipments. El programa 9.3
muestra los resultados de Excel QM para la ubicación de Birmingham.

PROGRAMA 9.2 De la barra de Excel QM, seleccione Después de introducir los costos, haga
Solución para 1 Ha el menú (Alphabetical o By Chapter). en la pestaña Data y seleccione Solver.
localización de la Seleccione Transportation en el menú Luego haga clic en Solve.
llar
desplegable y, luego, ingrese los 3
instalación (Seattle) orígenes (fuentes) y los 4 destinos.
on me tinten. del on Solver m the Dala

en Excel 2013 usando instruchons

Excel QM 8 Data
9 COSTS De olt Dalias New Yo os 42.4.• es Sapply
10 Cmcinnati 73 103 88 108 15000
11 Salt Lake City 85 80 100 6000
12 Pittsburgh 88 97 78 118 14000
13 Seattle , 11.3 91 113 80 11000
14 Demonial 110013 9000._.1 46000 \ 46030
15
16I Shipments (-Complete la tabla con los costos,
17 Shipments Detroit Dallas New York las ofertas y las demandas.
12 Cancinnati 10000 4000 1000
19 Salt Lake Caty 6000
20 Pittsburgh 14000 14000
21 Seattle 2000 9000 11000
—1
22 Column Total 10000 12913.-- 46000 \ 46000
23
1
El costo está aquí.
24 Total Cost 3704000

PROGRAMA 9.3 A c E G H
1 Hardgrave Machine
Solución para
localización de la 3 Transportation

:. Enter thc transportallon nabo hire Manen arel

instalación (Birmingham) Anarysis Group and iten efHt SOLVE
Then no to the DATA Tab on the ribbon. Met on Solve7Ini; Datan

en Excel 2013 usando 6 11SOLVell Is not on Iba Data Tala Men Peaso son the Help Se (Sotuer} for in:gradan&

Excel QM 8 Data
9 CC6TS Detroit Dallas teso York Los Angel es Supply —1
10... .. Cincinnati 73 103 88 108 15000 —1
---1
11 Salt Lake City 85 80 100 90 6000 _J
12 Plttsburgh 88 97 78 118 14000 1
13 Birmingham 84 79 90 99 11000
14 Densand , 10000 .....32000-... 15000 1 _ .90011, ._:I 46000 \ 46000
15 :
16 Shipments
--1
17 Shipments Detroit Dallas New York Los Angeles Row Total 1
18 Caneinnati 10000 1000 4000 15000
19 Salt Lake City 1000 5000 6000
20 Pittsburgh 14000 14000
21 Birmingham 11000 11000
22 Column Total 10000 12,P" ""-^...---4000 46000 \ 46000 1
23 /
- El costo está aquí. 7--
24 Total Cosí 3741000-4 ,
330 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

HISTORIA Cómo iniciaron los métodos de transporte

de manera indepe -diente la segunda contribución importante, un in-

E , uso de modelos de transporte para minimizar el costo de en-
vío desde varias fuentes hasta una serie de destinos fue propuesto
forme titulado "L.3 utilización óptima del sistema de transporte". En
1953 A. Chames y W. W. Cooper desarrollaron el método del tram-
por primera vez en 1941. Este estudio, llamado "La distribución de polín, un algoritm o que se analiza a detalle en este capítulo. En 1955
un producto desde varias fuentes hasta diversas localidades" fue es- se creó el método de distribución modificada (MODI), un enfoque
crito por F. L. Hitchcock. Seis años después, T. C. Koopmans realizó computacional rri¿' s rápido.

9.3 El problema de asignación

El problema de asignación se refiere al tipo de problema de PL que implica la determinación de la asig-
nación más eficiente de personas a proyectos, personal de ventas a territorios, auditores a empresas que
serán auditadas, contratos a licitantes. trabajos a máquinas, equipos pesados (como grúas) a tareas de cons-
trucción. etcétera. Con la mayor frecuencia, el objetivo es minimizar los costos totales o el tiempo total de
ejecución de las tareas requeridas. Una característica importante de los problemas de asignación es que
sólo se asigna un trabajo o un trabajador a una máquina o un proyecto.
Un problema de asignación es En la figura 9.2 se presenta una representación en red de un problema de asignación. Observe que esta
equivalente a un problema de red es muy parecida a la red de un problema de transporte. De hecho, un problema de asignación puede
transporte, donde tanto la oferta verse corno un tipo especial de problema de transporte, en el cual la oferta de cada fuente y la demanda en
como la demanda son iguales a 1. cada destino deben ser iguales a uno. Cada persona sólo podrá asignarse a un puesto de trabajo o proyecto,
y cada trabajo sólo requiere una persona.

Problema de programación lineal para un ejemplo de asignación

La red de la figura 9.2 representa un problema que enfrenta el taller Mr. Fix-It, que acaba de recibir tres
nuevos proyectos de reparación que deben completarse con rapidez: 1. una radio, 2. un horno tostador y
3. una mesa de café. Tres reparadores, cada uno con diferentes habilidades, están disponibles para realizar
los trabajos. El dueño del taller estima el costo por pago de salarios, si los trabajadores se asignan a cada
uno de los tres proyectos. Los costos difieren debido a las habilidades de cada trabajador para cada una de

FIGURA 9.2
Persona Proyecto
Ejemplo de un problema
de asignación en el Oferta 1 Demanda
formato de una red de
transporte $11
Adams Proyecto 1
1 1
,..._
(Fuente 1) (Destino 1)

S8

Brown Proyecto 2
(Fuente 2) (Destino 2)
$1

Cooper Proyecto 3
1
(Fuente 3) S (Destino 3)
 9.3 EL PROBLEMA DE ASIGNACIÓN 331

las tareas. El propietario desea asignar los trabajos de modo que se minimice el costo total; cada trabajo
debe tener una persona asignada al mismo, y cada persona sólo puede ser asignada a una tarea.
Para la formulación de esto como un problema de programación lineal, se puede utilizar la forma ge-
neral del problema de transporte. En la definición de variables, sean

En un modelo de asignación se usan {1 si la persona i es asignada al proyecto j

=
variables especiales 0-1 0 en caso contrario

donde
i = I, 2, 3, con 1 = Adams, 2 = Brown y 3 = Cooper
j = 1, 2, 3, con 1 = Proyecto 1, 2 = Proyecto 2 y 3 = Proyecto 3

La formulación de PL es

Minimizar el costo total = 11X11 + 14X12 + 6X13 + 8X21 + 10X22

+ 11X23 + 9X31 + 12X32 + 7X33

sujeto a

X11 + X12 +X13 *5 1

X21 + X22 + X23 5 1
X31 + X32 + X33 5- 1
X11 + X21 + X31 = 1
X12 + X22 + X32 = 1
X13 + X23 -E X33 = 1
= O o 1 para toda i y j

La solución se muestra en el programa 9.4. De acuerdo con ésta, x13 = 1, por lo que Adams se asigna
al proyecto 3; X22 = 1, por lo que Brown se asigna al proyecto 2, y x31 = 1, por lo que Cooper se asigna al
proyecto 1. Todas las demás variables son O. El costo total es de $25.
Este problema podría introducirse en Excel, Excel QM o QM para Windows como un problema de
programación lineal, o podría ingresarse como un problema de transporte con todas las ofertas y demandas
iguales a 1. Sin embargo, tanto Excel QM como QM para Windows tienen un módulo para este problema
de asignación. En Excel QM, desde el menú Alphabetical en la barra de Excel QM, seleccione Assignment.
Se abrirá la ventana de inicialización, donde puede escribir el número de tareas para después seleccionar
Minimization. Haga clic en OK y se abrirá una hoja de trabajo para que ingrese los costos como se muestra
en la tabla de datos del programa 9.4. Después, seleccione Solver de la barra Data y haga clic en Solve en
la ventana de entrada de Solver. Los resultados se muestran en el programa 9.4.

PROGRAMA 9.4 (-De la barra de Excel QM, seleccioné

Solución de asignación el menú (Alphabetical o By Chapter).
para el taller Mr. Fix-It Elija Assignment en el menú (Después de introducir los costos, haga
desplegable y, luego, ingrese el clic en la pestaña Data y seleccione Solver.
en Excel 2013 usando
Knúmero de asignaciones (3). Luego haga clic en Solve.
Excel QM on on Tn me Dala Analysts Group andlben
6 dhelc SOLVE.
II SOL VElt ts sol on the Esta T ab Non picase see ¡be 'lob) tic (Solver)
3 Dat.
9 cosrs Pro,tt Proittt2 P.o,ect3
10 Marro
11 Croan
12 "Llene la tabla con los costos,
13
14 assignments — las ofertas y las demandas.
15 ShIornents 1,[Link] 1 Proiect 2 Proieet 3 Roya Total
16 Adernt. 1
17 Brown 1
18 Cooper 1
19 Cokonn Toba 1
20 1 El costo está aquí. I i
21 SedCe* zs
332 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

El software para el problema de asignación supe ne que el problema está equilibrado, es decir, que el
número de fuentes (o personas) es igual al número d destinos (o trabajos). Si el problema no está equili-
brado, se agrega una fuente ficticia o un destino fic • cio al problema para que cumpla esta condición. En
algunos casos, se usa más de una fuente o un destino ficticio. Debido a que este elemento no es una asig-
nación real y sólo indicará cuál fuente o destino caree e de una asignación, todos los costos serán iguales a
cero. El problema resuelto 9-2 al final del capítulo ilu strará este caso.
En el problema de asignación, se requiere que la variables sean 0 o 1. Debido a la estructura especial
de este problema con coeficientes de restricción como O o 1, y todos los valores del lado derecho iguales
a 1, éste puede resolverse como un problema de programación lineal. La solución a tal problema (si acaso
existe) siempre indicará variables iguales a O o 1. Hay otros tipos de problemas donde es recomendable
utilizar las variables 0-1, pero la solución a estos problemas usando los métodos normales de programación
lineal no necesariamente contiene sólo ceros y unos. En tales casos, deben emplearse métodos especiales
para forzar que las variables sean O o 1; lo anterior se estudiará como un tipo especial de problema de pro-
gramación entera que se incluye en el capítulo 10.

9.4 El problema de transbordo

En un problema de transporte, si los artículos transportados deben pasar por un punto intermedio (llamado
punto de transbordo) antes de llegar a su destino final, el problema se denomina problema de transbordo.
Por ejemplo, una empresa podría estar fabricando un producto en varias plantas para enviarlo a un conjunto
Un problema de transporte con de centros de distribución regionales. Desde estos centros, los artículos se envían a puntos de venta que
puntos intermedios es un problema son los destinos finales. En la figura 9.3 se proporciona una representación en red de un problema de trans-
de transbordo. bordo. En este ejemplo, hay dos fuentes, dos puntos de transbordo y tres destinos finales.

Problema de programación lineal para un ejemplo de transbordo

Frosty Machines produce barredoras de nieve en sus fábricas ubicadas en Toronto y Detroit. Las barredoras
se envían a centros de distribución regionales en Chicago y Búfalo, donde son entregadas a tiendas mino-
ristas en Nueva York, Filadelfia y San Luis, como se ilustra en la figura 9.3.
Las ofertas disponibles en las fábricas, las demandas en el destino final y los costos de envío se mues-
tran en la tabla 9.3. Tenga en cuenta que las barredoras de nieve no pueden enviarse directamente desde
Toronto o Detroit a cualquiera de los destinos finales, sino que primero deben ir a Chicago o a Búfalo. Ésta
es la razón por la que Chicago y Búfalo aparecen no sólo como destinos, sino también como fuentes.
A Frosty le gustaría minimizar los costos de transporte asociados con el envío de las barredoras sufi-
cientes para satisfacer las demandas de los tres destinos, siempre y cuando no supere la oferta de cada fá-
brica. Por lo tanto, tenemos restricciones de oferta y demanda similares a las de un problema de transporte,
pero también tenemos una restricción para cada punto de transbordo que indica que cualquier cosa enviada

FIGURA 9.3 Punto de transbordo

Representación en Oferta Demanda
red del ejemplo de
transbordo
450
800

350

700

300
 9.4 EL PROBLEMA DE TRANSBORDO 333

TABLA 9.3 Datos de transbordo para Frosty Machine

DE: CHICAGO BÚFALO YORK FILADELFIA SAN LUIS OFERTA

Toronto $4 $7 800
Detroit $5 $7 700
Chicago — — $6 $4 $5
Búfalo — — $2 $3 $4
Demanda — — 450 350 300

desde éstos hasta un destino final debe haberse recibido en ese punto de transbordo desde una de las fuen-
tes. El enunciado verbal de este problema sería el siguiente:
Minimizar el costo
sujeto a

1. El número de unidades enviadas desde Toronto no es más de 800

2. El número de unidades enviadas desde Detroit no es más de 700
3. El número de unidades enviadas a Nueva York es de 450
4. El número de unidades enviadas a Filadelfia es de 350
5. El número de unidades enviadas a San Luis es de 300
6. El número de unidades salidas de Chicago es igual al número de unidades recibidas en Chicago
7. El número de unidades salidas de Búfalo es igual al número de unidades recibidas en Búfalo

En el problema de programación Las variables de decisión deberían representar el número de unidades enviadas desde cada fuente hasta
lineal se utilizan restricciones cada punto de transbordo y el número de unidades salidas de cada punto de transbordo hacia cada destino
de transbordo especiales. final, porque éstas son las decisiones que la gerencia debe tomar. Las variables de decisión son
Xii = número de unidades enviadas desde la ubicación (el nodo) i hasta la ubicación (el nodo)j

donde

i=1,2,3,4
j = 3, 4, 5, 6, 7

Los números son los nodos mostrados en la figura 9.3, y hay una variable para cada arco (ruta) en la figura.
El modelo de PL es
Minimizar el costo total = 4X13 + 7X14 + 5X23 + 7X24 + 6X35 + 4X36
+ 5X37 + 2X45 + 3X46 + 4X47
sujeto a

X13 + X14 5 800 (oferta en Toronto [nodo 1])

X23 + X24 -"5. 700 (oferta en Detroit [nodo 2])
X35 + X45 = 450 (demanda en Nueva York [nodo 5])
X36 + X46 = 350 (demanda en Filadelfia [nodo 6])
X37 + X47 = 300 (demanda en San Luis [nodo 7])
X13 + X23 = X35 + X36 + X37 (envío a través de Chicago [nodo 3])
X14 + X24 = X45 + X46 + X47 (envío a través de Búfalo [nodo 4])
xii O para toda i y j

En el programa 9.5, se muestra la solución encontrada utilizando Solver en Excel 2013 y Excel QM. El
costo total es de $9,550 por el envío de 650 unidades de Toronto a Chicago, 150 unidades de Toronto a
Búfalo, 300 unidades de Detroit a Búfalo, 350 unidades de Chicago a Filadelfia, 300 unidades de Chicago
a San Luis y 450 unidades de Búfalo a Nueva York.
334 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

PROGRAMA 9.5 A B C t.%

De la barra de Excel QM, seleccione el
menú (Alphabetical o By Chapter). Elija Linear
Solución en Excel QM 1 Frosty Machines
2 Enter the values ti, the shaded oree Then thy lo the DI Programming en el menú desplegable.
para el problema de 3 Linoar, Integar and! 1:013ta5RAnisa:70(17:21111.: elick :OL,[Link] the, Después, complete el número de restricciones
transbordo de Frosty (7), el número de variables (10), seleccione
Machine en Excel 2013 ( Después de introducir los datos, haga clic Minimize y haga clic en OK.
en la pestaña Data y seleccione Solver.
Luego, haga clic en Solve. reeter than a equal to

10 --...
11 X13 X14 X23 824 X35 X36 x37 X45 X46 V.7
12 5' 3 4 5,0 R'iS

:uando se abra la hoja de trabajo, complete 700

, .1 , 4so
a tabla con los coeficientes de la función 1 = 350
objetivo y las restricciones. Escriba sobre el 1 : = I 300

símbolo "<" para cambiarlo. -1

-: .1 -1 1 n crthiri n está aquí¡
21 Results
22 Variables I 650 150 o 300 o 350 300 450 o o
9550 /
23 Objective 1

MODELADO EN EL MUNDO REAL Traslado de caña de azúcar en Cuba

Definición del problema

Definición
del problema El mercado del azúcar ha estado en crisis desde hace más de una década. Los bajos precios del azúcar y la
disminución de la demanda se han sumado a un mercado ya inestable. Los productores de azúcar necesitaban
minimizar los costos. Se enfocaron en el costo unitario que más contribuye al costo total de la manufactura de
azúcar en bruto, es decir, los costos del transporte de la caña de azúcar.

Desarrollo de
Desarrollo de un modelo
un modelo Para resolver este problema, los investigadores desarrolla ron un problema de programación lineal con algunas
variables de decisión enteras (como el número de camio nes) y algunas variables (lineales) continuas (por ejem-
plo, las toneladas de caña de azúcar).

Adquisición de
Adquisición de datos de entrada
datos de entrada En el desarrollo del modelo, las entradas recopiladas fueron las demandas operativas de los ingenios azuca-
reros involucrados, las capacidades de las instalaciones de almacenamiento intermedias, los costos de trans-
porte por unidad de cada ruta y las capacidades de producción de los distintos campos de caña de azúcar.

Pruebas a la solución
Pruebas
a la solución Los investigadores involucrados primero probaron u a versión pequeña de su formulación matemática
usando una hoja de cálculo. Después de observar res ultados alentadores, implementaron la versión com-
pleta de su modelo en una computadora de gran ca pacidad. Los resultados para este modelo grande y
complejo (con cerca de 40,000 variables de decisión y 1 0,000 restricciones) se obtuvieron en sólo unos cuan-
tos milisegundos.

Análisis
Análisis de resultados
de resultados La solución obtenida contenía información sobre la ciar tidad de caña entregada a cada ingenio azucarero, el
campo donde se debería recoger la caña y los medios de transporte (camión, tren, etcétera), y varios otros
atributos operacionales vitales.

Implementación
Implementación de resultados
de resultados Aunque la resolución de grandes problemas como éste con algunas variables enteras, habría sido imposible
hace tan sólo una década, ahora puede encontrarse un a solución con toda seguridad. Con la finalidad de im-
plementar los resultados obtenidos, los investigadores esarrollaron una interfaz más sencilla para que los ad-
ministradores no tuvieran ningún problema al usar este modelo como una ayuda para tomar sus decisiones.

Fuente: Basado en E. L. Milan. S. M. Fernandez y L. M. la Aragones. "Sugar Canc Transportation in Cuba: A Case
Study". European Journal of Operational Research, 174. I (2006): 374-386.
 9.5 PROBLEMA DEL FLUJO MÁXIMO 335

9.5 Problema del flujo máximo

El problema del flujo máximo implica la determinación de la cantidad máxima de material que puede
fluir de un punto (la fuente) a otro (el destino) en una red. Los ejemplos de este tipo de problema incluyen
la determinación del número máximo de automóviles que pueden transitar a través de un sistema de carre-
teras, la cantidad máxima de líquido que fluye a través de una serie de tubos, el número máximo de llama-
das a teléfonos celulares que pueden pasar a través de una serie de torres celulares y la máxima cantidad
de datos que pueden fluir a través de una red computacional.
Para encontrar el flujo máximo desde la fuente o el inicio de una red hasta el destino o final de dicha
red, se utilizan dos métodos comunes: la programación lineal y la técnica del flujo máximo. Primero se
presentará un ejemplo y se demostrará el uso de la programación lineal para este tipo de problema.

Ejemplo
Waukesha, un pequeño pueblo en Wisconsin, está en proceso de desarrollar un sistema de caminos en
su zona centro. A Bill Blackstone, uno de los planeadores de la ciudad, le gustaría determinar el número
máximo de automóviles que pueden transitar a través de la ciudad de oeste a este. La red de caminos se
muestra en la figura 9.4. Las calles se indican mediante sus arcos respectivos. Por ejemplo, el arco que va
del nodo 1 al nodo 2 es el arco 1-2. El arco en la dirección inversa (del nodo 2 al nodo 1) es el arco 2-1. Los
números para los nodos indican el número máximo de automóviles (en cientos de automóviles por hora)
que pueden fluir desde los diversos nodos a lo largo de los respectivos arcos. El flujo máximo a lo largo del
arco 1-2 es 3, mientras que el flujo a lo largo del arco 1-3 es 10. A los planeadores de la ciudad les gustaría
saber la capacidad del sistema de caminos actual en la dirección de oeste a este.
El problema del flujo máximo puede plantearse como un problema de programación lineal, el cual se
considera un tipo especial de problema de transbordo con una fuente, un destino y un número de puntos
de transbordo. La cantidad enviada a través de la red se llama flujo. El objetivo es maximizar el flujo
a través de la red. Hay dos tipos de restricciones divididas en conjuntos. El primero de ellos restringe
la cantidad de flujo en cualquier arco a la capacidad de ese arco. El segundo conjunto de restricciones
indica que la cantidad de flujo que sale de un nodo será igual a la cantidad que fluye hacia ese nodo. Estas
restricciones son las mismas que las de un problema de transbordo.
Las variables se definen como:

= flujo del nodo i al nodo j

Se agrega un arco adicional a la red, que va desde el destino (nodo 6) de nuevo hasta la fuente (nodo 1).
El flujo a lo largo de este arco representa el flujo total en la red. El primer conjunto de restricciones en el
problema de programación lineal son los flujos máximos a lo largo de cada arco en cada dirección. Éstos
se agrupan con base en el nodo desde el que se origina el flujo. Las últimas seis restricciones limitan el

FIGURA 9.4
Capacidad en cientos
Red de caminos en el de automóviles por hora
ejemplo de flujo máximo
de Waukesha
Punto
este
Punto
oeste
336 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

flujo de salida de un nodo para igualar el flujo hacia e nodo (es decir, el flujo hacia un nodo menos el flujo
de salida de ese nodo debe ser igual a cero). El probl a de programación lineal es

Maximizar el flujo = X61

sujeto a
Xi2 3 X155 10 X14 5 2 Capacidades para los arcos desde el nodo 1

X21 5- 1 X24 5- 1 X26 2 Capacidades para los arcos desde el nodo 2

X34 3 X35 2 Capacidades para los arcos desde el nodo 3

X42 5 1 X43 5 1 X6 1 Capacidades para los arcos desde el nodo 4

X53 5- 1 X56 1 Capacidades para los arcos desde el nodo 5

X62 5 2 X64 5 1 Capacidades para los arcos desde el nodo 6

(X21 + X61) — (X12 + X13 + X14) Flujos entrantes = Flujos salientes del nodo 1

(X12 + X42 + X62) — (X21 + X24 + X26) = O Flujos entrantes = Flujos salientes del nodo 2
(X13 + X43 + X53 ) — (X34 + X35 ) = O Flujos entrantes = Flujos salientes del nodo 3

(X14 + X24 + X34 + X64) — (X42 + X43 ± X46) = Flujos entrantes = Flujos salientes del nodo 4
(X35) — (X56 + X53 ) = 0 Flujos entrantes = Flujos salientes del nodo 5

(X26 + X46 + X56) (X61 ± X62 + X64) = 0 Flujos entrantes = Flujos salientes del nodo 6
Xii O

Ahora el problema está listo para resolverse mediante el módulo de programación lineal de QM para
Windows o utilizando Solver en Excel 2013. Sin embargo, el programa 9.6 ilustra la solución encontrada
con Excel QM. Para lograr esto, en la barra de Excel QM, seleccione Network Analysis as LP y, luego, elija
Maximal Flow. En la ventana de inicialización que se abre, introduzca el número de nodos (6) y haga clic
en OK. Se desplegará una hoja de trabajo como la mostrada en el programa 9.6. Introduzca los datos de las
capacidades de arco y, en seguida, haga clic en Solver en la barra de Data. Haga clic en Solve en la ventana
de entrada de Solver, y los resultados (flujos) se presentarán en la hoja de trabajo.

4 A
PROGRAMA 9.6 —1-De la barra de Excel QM, seleccione el menú-
Watikesha
Solución de Excel 2013 2 _.......__ __ (Alphabetical o By Chapter). Elija Network
3 Maximal How Analysis as LP y Maxímal Flow en el menú
del flujo máximo
desplegable. Luego, llene el número de ramas
para Waukesha 5
o arcos (6). Haga clic en OK.
usando Excel QM
8 Data-Are eapiwities
9 FrorrAto Node 1 Node 2 Node 3 Node 4 Node 5 Node 6
Nodet 0 3 lo 2 o o
Nade 2 1 1 2 Cuando se abra la hoja de
Nodo 3 o 3 2 0 trabajo, introduzca los flujos
Nodo 4 o o en la tabla.
Node 5 o o o
Nade 6 999999 0 1
16
al,. V CIIMI ya ,J1.1.4 a 11,11.41,1%.•

es utilizado por Excel QM. . ....... ..... .... —I-- I

20 From \to Node 1 Node 2 Node 3 Node 4 Nade 5 Node 6 Outflow
21 Node 1 2 1 2
22 Node 2 I 2 2
23 Node 3 2 i 2
24 Node 4 I 1 1
25 Node 5 2 2
26 1 Node 6 2 2 1 5
27 Inflow 2 2 7 1 7 5
29 Outflow __......;........ 2 2 (' Despues de introducir los datos, haga '''''
29 clic en la pestaña Data y seleccione Solver.
30
;\ Luego haga clic en Salve.
31 Max Flor, 5
 9.6 PROBLEMA DE LA RUTA MÁS CORTA 337

9.6 Problema de la ruta más corta

El objetivo del problema de la ruta más corta es encontrar la menor distancia desde una ubicación hasta
otra. En una red, esto suele implicar la determinación de la ruta más corta desde un nodo hasta cada uno
de los otros nodos. El problema anterior puede plantearse como un problema de programación lineal con
variables 0-1, o bien, podría plantearse y resolverse mediante un algoritmo especializado que se presenta
en el módulo 8. El siguiente ejemplo es un problema típico de la ruta más corta.
Cada día, Ray Design, Inc., debe transportar camas, sillas y otros artículos de mobiliario desde la
fábrica hasta el almacén. Esto implica pasar por varias ciudades, y no hay carreteras interestatales directas
para facilitar la entrega. Ray desearía encontrar la ruta con la distancia más corta. La red de carreteras se
muestra en la figura 9.5.
El problema de la ruta más corta puede considerarse como un tipo especial de problema de trans-
bordo con una fuente que tiene una oferta de 1, un destino con una demanda de 1 y cierta cantidad de
puntos de transbordo. Este tipo de problema puede plantearse como un problema de programación
lineal con variables 0-1. Ray está tratando de decidir cuáles de las rutas (arcos) a elegir serán parte del
sistema de suministro. Por lo tanto, las variables de decisión indicarán si un arco en específico se elige
para formar parte de la ruta tomada. Para el ejemplo de Ray Design, Inc., el objetivo es minimizar la
distancia (el costo) total desde el inicio hasta el final. Las restricciones especifican que el número de
unidades (ya sea O o 1) que entran en un nodo debe ser igual al número que sale de ese nodo. Las varia-
bles se definen como

= 1 si se selecciona el arco del nodo i al nodo j y xo = 0 en caso contrario

Como el punto de inicio es el nodo 1, no incluiremos variables que vayan desde el nodo 2 o 3 hasta
el nodo 1. Del mismo modo, puesto que el nodo 6 es el destino final, no incluiremos ninguna variable que
inicie en el nodo 6. Si se toma esto como un problema de transbordo, el nodo origen (nodo 1) debe tener
una unidad enviada desde él. Esto sería,

X12 + X13 = 1

El nodo de destino final (nodo 6) debe tener una unidad enviada hacia él, lo cual se escribe como

X46 + X56 = 1

Cada nodo intermedio tendrá una restricción para indicar que la cantidad que entra en el nodo debe ser
igualar la cantidad que sale de éste (es decir, el flujo de entrada a un nodo menos su flujo de salida debe
ser igual a cero). Para el nodo 2, esto sería

X12 + X32 = X23 + X24 + X25

Lo anterior se simplifica como

X12 + X32 — X23 — X24 — X25 = 0

Las otras restricciones se construyen de manera similar. El problema de programación lineal es

Minimizar la distancia = 100X12 + 200X13 + 50X23 + 50X32 + 200X24 + 200X42 + 100X,5

100X52 + 40X35 + 40X53 + 150X45 + 150X54 + 100X46 + 100X56

sujeta a

X12 + X13 = 1 Nodo 1

XI 2 + X32 X23 X24 X25 = 0 Nodo 2
X13 + X23 — X32 — X35 = Nodo 3
X24 + X54 X42 — X45 X44 =0 Nodo 4

X25 + X35 + X45 — X52 -- X53 — X54 X56 = O Nodo 5

X46 X56 = 1 Nodo 6
Todas las variables = 0 o 1
338 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

FIGURA 9.5

Caminos de la planta
de Ray al almacén

PROGRAMA 9.7 A
De la barra de Excel QM, seleccione el y
t Ray Design
Solución en Excel 2013 menú (Alphabetical o By Chapter). Elija
Shortest Path Network Analysis as LP y Shortest Route
para Ray Design, Inc.
Er4ei tne distante; luan neer en el menú desplegable. Después, llene
usando Excel QM notoo, orce on Soban ira the I el número de ramas o arcos (6). Haga
7 , 5 SGIVER 15 not on the Dati
t„ clic en OK.
4 Data - Distante Table ''
FronAto City 1 City 2 City 3 CIty 4 City 5
O 1 100 200 o
r uando se abra la hoja
14 CIty 1 1 1
CIty 2 100 I 0 50 200 1 100 1 1
e cálculo,introduzca las
11
12 City 3 200 1 50 0 0 l 43 Ó 1 istancias en la tabla. }
13 City 4 0 i 200 0 0 150 100
14 City 5 0 I 100 40 150 0 100
15 City 6 0 1 0 0 100 100 0
16: 1 o 0 o o -1
17 Stait=1,Finish.-1
18
19 Flows
20 From \ to CIty 1 City 2 City 3 City 4 City 5 City 6 Outflow
21 aty 1 1 1
22 aty 2 1 1
23 City 3 1 1
24 City 4
25 City 5 1
26 Oty 6
27 Inflow 1

28 Outflow 1 (Después de introducir los datos, haga

29 Net Outflow 1
clic en la pestaña Data y seleccione Solver.
30
31 titAinimum distante 290
1 Luego haga clic en Solve.

Aunque este problema podría resolverse como un problema de programación lineal, la forma más
fácil de obtener la solución es mediante Excel QM. Para resolver un problema de la ruta más corta, de la
barra de Excel QM seleccione Network Analysis as LP y, luego, elija Shortest Path. En la ventana de ini-
cialización que se abre, introduzca el número de nodos (6) y haga clic en OK. Se desplegará una hoja de
trabajo como la mostrada en el programa 9.7. Introduzca los datos de las distancias y, luego, haga clic en
Solver en la barra de Data. Haga clic en Solve en la ventana de entrada de Solver, y los resultados (flujos)
se presentarán en la hoja de trabajo. En el programa 9.7, se observa que

X12 = X23 = X35 == X96 = 1

Así que Ray viajará de la ciudad 1 a la ciudad 2 y, 1 ego, a la ciudad 3, y después a la ciudad 5, y de ahí
a la ciudad 6, su destino final. La distancia total es d 290 millas.

9.7 Problema del árbol de expansión mínima

El problema del árbol de expansión mínima consiste en conectar todos los puntos de una red mientras
se minimiza la distancia total de estas conexiones. Algunos ejemplos comunes son las compañías telefó-
nicas o de cable que intentan conectar las casas de nn vecindario, y los administradores de una red que
 9.7 PROBLEMA DEL ÁRBOL DE EXPANSIÓN MÍNIMA 339

tratan de minimizar el cable necesario para conectar varias computadoras en red. Aunque se han usado
modelos de programación lineal para resolver esto, hay ciertas propiedades del problema que lo hacen
bastante complejo. Por fortuna, hay otro método más sencillo para encontrar la solución a un problema
de este tipo, y se muestra a continuación. La técnica del árbol de expansión mínima se presentará me-
diante el siguiente ejemplo.
Consideremos la empresa constructora Lauderdale, que actualmente está desarrollando un proyecto
de viviendas de lujo en Panama City Beach, Florida. Melvin Lauderdale, propietario y presidente de la
constructora Lauderdale, debe determinar la forma menos costosa en que se puede suministrar agua y elec-
tricidad a cada casa. La red de casas se muestra en la figura 9.6.
Como se observa en la figura 9.6, hay ocho casas en el golfo. En la red se muestra la distancia entre
cada casa en cientos de pies. Por ejemplo, la distancia entre las casas 1 y 2 es de 300 pies. (El número 3 se
encuentra entre los nodos 1 y 2). Ahora, la técnica del árbol de expansión mínima se utiliza para determinar
la distancia más corta que se puede utilizar para conectar todos los nodos. El enfoque se describe de la
siguiente manera:

Existen cuatro pasos para resolver Pasos para la técnica del árbol de expansión mínima
un árbol de expansión mínima.
1. Seleccione cualquier nodo de la red.
2.. Conecte ese nodo al nodo más cercano que minimiza la distancia total.
3. Considerando todos los nodos que están conectados ahora, encuentre y conecte el nodo más cercano
que no lo esté. Si hay un empate en el nodo más cercano, seleccione uno de ellos arbitrariamente.
Un empate sugiere que puede haber más de una solución óptima.
4. Repita el tercer paso hasta conectar todos los nodos.

Paso 1: Seleccionamos el nodo 1. Ahora, resolveremos la red de la figura 9.6 para Melvin Lauderdale. Comenzamos seleccionando
Paso 2: Conectamos el nodo 1 al arbitrariamente el nodo 1. Como el nodo más cercano es el tercer nodo a una distancia de 2 (200 pies),
nodo 3. conectamos el nodo 1 al nodo 3. Esto se muestra en la figura 9.7.
Considerando los nodos 1 y 3, buscamos el próximo nodo más cercano. Éste es el nodo 4, que es
el más cercano al nodo 3. La distancia es de 2 (200 pies). Una vez más, conectamos estos nodos (vea el
inciso (a) de la figura 9.8).
Continuamos buscando el nodo sin conexión más cercano a los nodos 1, 3 y 4. Éste es el nodo 2 o el
nodo 6, pues cada uno está a una distancia de 3 desde el nodo 3. Elegimos el nodo 2 y lo conectamos
al nodo 3 (vea el inciso (b) de la figura 9.8).

FIGURA 9.6
Red para la empresa
constructora Lauderdale

Golfo
340 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

FIGURA 9.7
Primera iteración para
la empresa constructora
Lauderdale

FIGURA 9.8 Segunda y tercera iteraciones

(a) Segunda iteración (b) Tercera iteración

Paso 3: Conectamos el siguiente Continuamos con el proceso. Hay otro empate para la siguiente iteración con una distancia mínima de
nodo más cercano. 3 (del nodo 2 al nodo 5 y del nodo 3 al nodo 6). Tenga en cuenta que no consideramos del nodo 1 al nodo 2
con una distancia de 3, debido a que los nodos 1 y 2 ya están conectados. Seleccionamos arbitrariamente
Paso 4: Repetimos el proceso. el nodo 5 y lo conectamos al nodo 2 (vea el inciso (a) de la figura 9.9). El siguiente nodo más cercano es el
nodo 6, conéctelo al nodo 3 (vea el inciso (b) de la fi ura 9.9).
En esta etapa, nos quedan sólo dos nodos sin co ectar. El nodo 8 es el más cercano al nodo 6, con una
distancia de 1, y lo conectamos (vea el inciso (c) del figura 9.9). Después, el nodo 7 restante se conecta al
nodo 8 (vea el inciso (d) de la figura 9.9).
La solución final se observa en la séptima y úl ima iteración. Los nodos 1, 2, 4 y 6 están todos co-
nectados al nodo 3. El nodo 2 está conectado al nodo 5. El nodo 6 está conectado al nodo 8, y el nodo 8
está conectado al nodo 7. Ahora, todos los nodos están conectados. La distancia total se encuentra su-
mando las distancias de los arcos utilizados en el árbol de expansión. En este ejemplo, la distancia es de
2 + 2 + 3 + 3 + 3 + 1 + 2 = 16 (o 1,600 pies). Lo anterior se resume en la tabla 9.4.
 9,7 PROBLEMA DEL ÁRBOL DE EXPANSIÓN MÍNIMA 341

FIGURA 9.9 Últimas cuatro iteraciones para la compañía constructora Lauderdale

(a) Cuarta iteración (b) Quinta iteración

(c) Sexta iteración (c1) Séptima iteración

El problema del árbol de expansión mínima se resuelve con Excel QM o QM para Windows. Para uti-
lizar Excel QM en Excel 2013, seleccione el menú Alphabetical de la barra, desplácese hacia abajo hasta
Network Analysis y elija Minimal Spanning Tree. En la ventana de inicialización de la hoja de cálculo que
se abre, introduzca el número de ramas o arcos (13 en este ejemplo). Cuando se abra la hoja de cálculo,

TABLA 9.4 Resumen de los pasos en el problema del árbol de expansión mínima
para la empresa Lauderdale

NODOS NODO
NODOS SIN SIN CONECTAR ARCO LONGITUD DISTANCIA
PASO CONECTADOS CONECTAR MÁS CERCANO SELECCIONADO DEL ARCO TOTAL

1 1 2, 3, 4,5, 6, 7, 8 3 1-3 2 2
2 I, 3 2, 4, 5, 6, 7, 8 4 3-4 2 4
3 1, 3, 4 2, 5, 6, 7, 8 2o6 3-2 3 7
4 1, 2, 3, 4 5, 6, 7, 8 5o6 2-5 3 10
5 1, 2, 3, 4, 5 6,7,8 6 3-6 3 13
6 1, 2. 3, 4, 5, 6 7, 8 8 6-8 1 14

7 1, 2, 3, 4, 5, 6, 8 7 7 8-7 2 16
342 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

La localización de instalaciones conduce a una mejora

A EN ACCIÓN en la confiabilidad de la cadena de suministro

peor? La respuest está en el área del problema de la localización de

L as cadenas de suministro son, en su nivel físico, una red inter-
conectada de rutas de reparto (carreteras, puentes, vías de navega-
instalaciones: ¿Qt é almacenes deberían entregar a qué tiendas para
enfrentar ese pro blema? Al analizar el problema de transporte elimi-
ción, etcétera) compuesta de múltiples fuentes (almacenes, fábricas, nando las fuentes actuales, una por una, los analistas pudieron medir
refinerías, etcétera) y varios destinos (tiendas, puntos de venta, otros el impacto de dicl a interrupción. Los investigadores concluyeron que
almacenes, etcétera), a lo largo de la cual viajan productos y materias deberían planears e con antelación "asignaciones de respaldo" de los
primas. En la mayoría de los casos, la asignación de destinos específi- almacenes a las ti, ndas, para ayudar a mitigar el impacto de las posi-
cos a determinadas fuentes es conocida y bastante constante. bles catástrofes. ! iempre vale la pena planear con anticipación!
Los investigadores, mientras ayudan a planear las situaciones de
emergencia en las empresas, han estudiado el problema de la interrup- Fuente: Basado en L. Snyder y M. Daskin. Models for Facility
ción de la cadena de suministro. ¿Qué pasaría si una de las fuentes Location: The Exp, cted Failure Cost Case". Transporta:ion Science 39. 3
fallara catastróficamente debido a un terremoto, un tornado o algo (2005): 400416.

PROGRAMA 9.8 A e c
(De la barra de Excel QM, seleccione el
1 Lauderdale Construction
Ejemplo del árbol de 2 menú (Alphabetwai o By Chapter). Elija
3 Network Analysis Network Analysis y Minimum Spanning
expansión mínima
Efiletrtai nade, en Tree en el menú desplegable. Después,
para la constructora Salve
complete el número de ramas o arcos (13).
Lauderdale node lj
K._Haga clic en OK.
Después de introducir los'. Results
idatos,haga clic en Solve. Endnode, Cost Inciude Cosi
10 --imanen 1 2 1
Cuando se abra la hoja de trabajo,
11 Brandi 2 1 3 2
12 Branch 3 1 4 5 introduzca el nodo de inicio, el nodo
13 Branch 4 2 3 3 final y el flujo para cada arco.
14 Branch 5 2 5 3 T .1
15 Branch 6 3 4 2- 2
16 Branch 7 3 5 5
17 Branch 8 3 6 3 3
18 Branch 9 3 7 7
19 Branch 10 t 4 1 6 6
20 Branch 11 5 7 4
21 Branch 12 6 8
22 Branch 13 7 8 2 1 2
23
24 Sum 16

introduzca en cada arco el nodo inicial, el nodo final y la distancia entre ambos (es decir, la longitud del
arco) como se indica en el programa 9.8. Haga clic en el botón So/ve que aparece en la hoja de cálculo, y
la solución se mostrará como en el programa 9.8. El problema también podría resolverse en QM para Win-
dows seleccionando el módulo de redes e introduciendo un nuevo problema como un árbol de expansión
mínima. La entrada es muy similar a la de Excel QM.

Resumen

En este capítulo exploramos varios problemas que se plantean común- para todos, excepto para el árbol de expansión mínima, destacando el
mente como redes, con nodos y arcos que representan una variedad de hecho de que la programación lineal puede ser benéfica en muchas
situaciones. Éstos fueron los problemas de transporte, de asignación. áreas diferentes. Los programas de computadora que toman ventaja
de transbordo, de flujo máximo. de la ruta más corta y del árbol de de la estructura especial de estos problemas pueden ayudar a resolver
expansión mínima. Se desarrollaron modelos de programación lineal grandes problemas de redes de manera muy eficiente.
 PROBLEMAS RESUELTOS 343

Glosario

Análisis de localización de instalaciones Una aplicación del Problema de asignación Un tipo especial de problema de redes
método de transporte para ayudar a una empresa a decidir donde los costos se minimizan, mientras se asignan personas a
dónde debe ubicar una nueva fábrica, un nuevo almacén u otra trabajos (u otras tareas). La manera establecer estas relaciones es
instalación. uno a uno.
Arco Una línea en una red que puede representar un camino o una Problema de la ruta más corta Un problema de redes con el obje-
ruta. Un arco o una rama se utilizan para conectar los nodos de tivo de encontrar la distancia más corta desde una ubicación hasta
una red. otra pasando por nodos intermedios.
Destino Una ubicación de demanda en un problema de transporte. Problema de transporte Un caso específico de PL relacionado con
Destino final El nodo final o el nodo destino en una red. la programación de envíos desde fuentes hasta destinos, de modo
Fuente Un origen o una ubicación de oferta en un problema de que se minimicen los costos de transporte totales.
transporte. Además, el origen o nodo de inicio en una red de flujo Problema del árbol de expansión mínima Un problema de redes
máximo. con el objetivo de minimizar la distancia o el costo total requeri-
Nodo Un punto en una red, con frecuencia se representa mediante dos para conectar todos los nodos en una red.
un círculo, y está al principio o al final de un arco. Problema del flujo máximo Un problema de redes con el objetivo
de determinar la cantidad máxima que puede fluir desde el origen
o la fuente hasta el destino final.

Problemas resueltos

Problema resuelto 9-1

Don Yale, presidente de la compañía Hardrock Concrete, tiene plantas en tres localidades y en la actualidad está
trabajando en tres grandes proyectos de construcción, ubicados en diferentes sitios. En la tabla adjunta, se propor-
cionan el costo de envío por camión cargado de concreto, la capacidad de la planta y los requisitos del proyecto.
Formule el problema de transporte de Hardrock como un problema de programación lineal y resuélvalo
usando software.

[ A PROYECTO PROYECTO PROYECTO CAPACIDADES

DE A R C DE PLANTA
."PLANTA 1 $10 $4 $11 70
:PLANTA 2 $12 $5 $8 50
PLANTA 3 $9 $7 $6 30
FREQIIISIT 40 50 60 150

Solución
Defina las variables como
Xy = número de unidades enviadas de la planta i al proyecto/
donde
i = 1, 2, 3 con 1 = planta 1, 2 = planta 2 y 3 = planta 3
j = 1, 2, 3 con 1 = proyecto A, 2 = proyecto B y 3 = proyecto C
La formulación del problema de programación lineal es

Minimizar el costo total = 10X11 + 4X12 + 11X13 + 12X21 + 5X22 + 8X23 9X31 7X32 6X33

sujeto a
+ X21 + X31 = 40 Requisitos del proyecto A
x12 + x22 ± X32 = 50 Requisitos del proyecto B
X13 + X23 + x33 = 60 Requisitos del proyecto C
x11 + x12 + X13 70 Capacidad de la planta 1
x21 + x22 + X23 50 Capacidad de la planta 2
X31 + X32 X33 30 Capacidad de la planta 3
Todas las variables n
344 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

La salida de computadora que se encuentra mediante el so de Excel QM presenta la solución óptima. De la

planta 1 se envían 20 unidades al proyecto A y 50 unidades al royecto B. De la planta 2 se envían 50 unidades al
proyecto C. De la planta 3 se envían 20 unidades al proyecto y 10 unidades al proyecto B. El costo total de esta
solución es $1,040. Aunque no se muestran en la salida de co putadora, hay soluciones óptimas alternativas para
este problema.

Programa para A a c E F o H
i 1
Solved Problem 9-1 i ¡
el problema
resuelto 9-1
1
2
Transportaton _
n... -.
1L:
Enter 5, transporlenor data in the nusded area The" soto ine DATA Tab on ese &bort
Oda ezsayan Cm* and lencine sotve_ ,- -, ..
r, cl 4 Sobo,

C SOt VER n not en ese Data Taa nen pleesenee tse Helio tile . ' ' '

8 Data
9 COSTS Project 1 Project 2 Project 3 Supply
--+
10 Plant 1 10 4 11 70
11 Plant 2 12 5 8 50
12 Plant 3 9 7 6 30
13 Demand 50 60 150 \ 150
14 ,
Ir
15 Shipments L
16 ShIpments Project 1 Project 2 Project 3 Roer Total
17 Ptant 1 20 SO 70 1--
i
18 Ptant 2 50 50 i

19 Ptant 3 20 10 30 i

20 Colman Total 40 SO 60 150 \ 150

21
22 Total Cost 1040 1

Problema resuelto 9-2

Prentice Hall, Inc., una empresa editorial con sede en Nueva Jersey, quiere asignar a tres graduados universitarios
que fueron contratados recientemente, Jones, Smith y Wilson a los distritos de ventas regionales en Omaha, Dallas
y Miami. Pero la empresa también tiene una vacante en Nueva York y enviaría a uno de los tres contratados, si esto
fuera más económico que un movimiento a Omaha, Dallas o Miami. Costaría $1,000 reubicar iones a Nueva York,
$800 reubicar a Smith ahí y $1,500 mudar a Wilson. ¿Cuál esl la asignación óptima de personal a las oficinas?

OFICINA
CONTRATADO OMAHA MIAMI DALLAS

JONES $800 $1,100 $1,200

SMITH S500 $1,600 $1,300
WIISON $500 51,000 $2,300

Debido a que hay tres nuevas contrataciones y cuatro oficinas si se incluye Nueva York, el problema no está equi-
librado. Es imposible que las cuatro ciudades tengan una persona asignada (es decir, no existe una solución fac-
tible). Por lo tanto, se agrega una fuente ficticia (contratación nueva), y los costos son cero para este elemento
ficticio. Por consiguiente, las variables podrían omitirse de la función objetivo, pero se incluyen por exhaustividad
del procedimiento.
Defina las variables como

Xij = 1 si el nuevo contratado i se asigna a la oficina/

donde

= 1, 2, 3, 4 con 1 = Jones, 2 = Smith, 3 = Wilson y 4 = contratado ficticio

j = 1, 2, 3, 4 con 1 = Comalia, 2 = Miami, 3 = Dallas y 4 = NuevaYork
 AUTOEVALUACIÓN 345

La formulación del problema de programación lineal es

Minimizar el costo total = 800X11 + 1100X12 + 1200X13 + 1000X14 + 500X21 + 1600X22

1300X23 800X24 + 500X31 + 1000X32 + 2300X33 + 1500X34 + OX41 + OX42 + OX43 + OX44
sujeto a
X11 + X21 + X31 + X41 5- 1 Oficina de Omaha
X12 + X22 + X32 + X42 1 Oficina de Miami
X13 + X23 + X33 + X43 1 Oficina de Dallas
X14 + X24 + X34 + X44 5- 1 Oficina de Nueva York
X11 + X12 + X13 + X14 = 1 Jones
X21 +X22 +X23 +X24 = 1 Smith
X31 + X32 + X33 + X34 = 1 Wilson
X41 + X42 + X43 + X44 = 1 Contratado ficticio
Todas las variables -?—•

A continuación, se muestra la solución óptima que se encontró con Excel QM: Jones se asigna a Miami
(X12 = 1), Smith se asigna a Nueva York (X24 = 1), Wilson se asigna a Omaha (X31 = 1) y nadie (ficticio) se asigna
a Dallas (X43 = 1). El costo total es de $2,400.

Programa para A e E

el problema Solved Problem 9-2'•

2
resuelto 9-2 3 Assknment
4 am assignritl"e sudo:late:1 7 hen poto the DATA
5 n. click en. SgAtIr in Otal>ata Analysis Group diu.1 Hico dick $01.1)E.
6 LVER iL 1101 on Iba Dala Tab then picase son liso He1P ale iSeivall lar
7
8
9 Omaha Miami Dallas NY
10 Jones 800 1100 1200 1000
11
12
Smith
Wilson
ice 1600 1300 800

13 Du 1
14
15 Í Assignments
16 ShIpments Omaha Miami Dallas NY Row Total
17 --1
lonas 1 1
18 Smith 1. 1
19 Wilson 1 1
20 Dummy 1 1
21 Column Total 1 1 1 1 4
22
23 Total Cost 2400

Autoevaluación

• Antes de realizar la autoevaluación, consulte los objetivos de aprendizaje al comienzo del capítulo, las notas en los márgenes y el glosario
al final del capítulo.
• Consulte las soluciones en la parte final del libro para corregir sus respuestas.
• Vuelva a estudiar las páginas que correspondan a todas las preguntas que respondió incorrectamente o al material del que no se sienta seguro.

1. Si un problema de transporte tiene 4 fuentes y 5 destinos, su 2. Un problema de asignación puede verse como un problema de
problema de programación lineal tendrá transporte con
a. 4 variables y 5 restricciones. a. un costo de $1 para todas las rutas de envío.
b. 5 variables y 4 restricciones. b. todas las ofertas y demandas iguales a 1.
c. 9 variables y 20 restricciones. c. sólo restricciones de demanda.
d. 20 variables y 9 restricciones. d. sólo restricciones de oferta.
346 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

3. Una empresa está evaluando la apertura de un nuevo centro 6. En un mod lo típico de la ruta más corta, el objetivo es
de producción, y tiene tres lugares bajo consideración. Para este a. • • • el número de nodos en la ruta.
problema de localización de instalaciones, ¿cuántos modelos b. el tiempo o la distancia para ir de un punto a otro.
de transporte se deben desarrollar y resolver? c. minimizar el número de arcos en la ruta.
a. 1 d. viajar a ravés de todos los nodos de la mejor manera posible.
b. 2 7. Una gran ciudad está planeando unos Juegos Olímpicos, que
c. 3 se realizarán dentro de unos pocos años. Se evalúa el sistema
d. 4 de transporte para determinar la expansión que se requiere para
4. Se asignarán cuatro grúas a cinco trabajos de construcción. manejar el gran número de visitantes a los juegos. ¿Cuál de los
Uno de los trabajos se retrasará hasta que una de las grúas siguientes modelos es más probable que sea útil para que los
esté disponible después de terminar la primera tarea. planeadores de la ciudad determinen la capacidad del sistema
Se usará una modelo de asignación. Para permitir que actual?
el software especializado encuentre una solución a este a. El modelo de transporte.
problema, b. El modelo del flujo máximo.
a. no debe hacerse nada en especial con el problema. e. El modelo de la ruta más corta.
b. debe usarse una grúa ficticia en el modelo. d. El modelo del árbol de expansión mínima
c. debe usarse un trabajo ficticio en el modelo. 8. El centro de cómputo de una gran universidad está instalando
d. deben usarse un trabajo y una grúa ficticios en el modelo. cables de fibra óptica hacia 15 edificios en el campus. ¿Cuál de
5. ¿Cuál modelo de red se utiliza para determinar la forma de los siguientes modelos podría utilizarse con la finalidad de
conectar todos los puntos de una red mientras se minimiza determinar la menor cantidad de cable necesario para conectar
la distancia total entre ellos? todos los edificios?
a. El modelo de asignación. a. El modelo de transporte.
b. El modelo del flujo máximo. b. El modelo del flujo máximo.
c. El modelo de la ruta más corta. c. El modelo de la ruta más corta.
d. El modelo del árbol de expansión mínima. d. El modelo del árbol de expansión mínima.

Preguntas para análisis y problemas

Preguntas para análisis Problemas*

9-1 ¿Es el modelo de transporte un ejemplo de la toma de de- • 9-7 La gerencia de la corporación Executive Furniture deci-
cisiones en condiciones de certidumbre o de la toma de dió ampliar la capacidad de producción en su fábrica
decisiones en condiciones de incertidumbre? ¿Por qué? de Des Moines y recortar la producción en sus otras
9-2 Explique cómo se determina el número de variables y de plantas. También reconoce un mercado cambiante para
restricciones que habría en un problema de transporte tan sus escritorios y ha modificado los requisitos en sus tres
sólo con conocer el número de fuentes y el número de almacenes.
destinos. La tabla que se muestra al final de la página contiene
9-3 Explique qué significa que un modelo de asignación esté los requisitos de cada uno de los almacenes, las capaci-
equilibrado. dades de cada una de las fábricas y el costo unitario de
9-4 Explique el propósito de las restricciones de transbordo envío desde cada fábrica hasta cada almacén. Encuentre
en el problema de programación lineal para un modelo de la manera de satisfacer los requisitos, dada la capacidad
transbordo. de cada fábrica, y al menor costo posible.
9-5 Describa un problema que pueda resolverse mediante el 1: 9-8 La compañía Hardrock Concrete tiene plantas en tres ubi-
3
modelo de la ruta más corta. cacames y en la actualidad está trabajando en tres grandes
9-6 Explique por qué el modelo del flujo máximo puede verse proyectos de construcción, cada uno situado en un sitio
como un modelo de transbordo. diferente. En la siguiente tabla, se proporcionan el costo

i
DE A ALBUQUERQUE BOSTON CLEVELAND CAPACIDAD
DES MOINES S5 S4 $3 300
EVANSVILLE 8 4 3 150
FORT LAUDERDALE 9 7 5 250
REQUISITOS 200 200 300

Nota: 9 significa que el problema puede resolverse con QM para Windows: significa que el problema puede resolverse con Excel QM, y significa que el problema
puede resolverse con QM para Windows y/o Excel QM.
 PREGUNTAS PARA ANÁLISIS Y PROBLEMAS 347

de envío por camión de concreto, la capacidad de la planta Para el lunes 16 de abril, las siguientes ciudades necesita-
y las necesidades diarias de los proyectos. rán vagones con carbón de la siguiente manera:
Formule esto como un problema de programación
lineal para determinar la manera de satisfacer las necesi- CIUDAD DEMANDA DE VAGONES
dades al menor costo posible. Resuelva usando cualquier
Coal Valley 30
software.
9-9 El propietario de Hardrock Concrete ha decidido aumentar Coaltown 45
la capacidad en su planta más pequeña (vea el problema Coal Junction 25
9-9). En vez de producir 30 cargas de concreto al día en la
Coalsburg 20
planta 3, la capacidad de esa planta se duplicará a 60 car-
gas. ¿Esto cambia el programa desarrollado previamente?
Mediante el uso de una tabla de distancias por ferrocarril
9-10 La compañía Saussy Lumber envía pisos de pino a tres
de ciudad a ciudad, el despachador construyó una tabla en
tiendas de suministros para construcción desde sus aserra-
millas para las ciudades anteriores. El resultado se mues-
deros en Pineville, Oak Ridge y Mapletown. Determine el
tra en la tabla correspondiente a este problema. Minimice
mejor programa de envíos para los datos dados en la tabla
las millas totales que deberán recorrer los vagones hasta
correspondiente a este problema.
sus nuevas ubicaciones; calcule el mejor envío de vagones
9-11 La compañía ferrocarrilera Krampf Lines se especializa de carbón.
en el manejo de carbón. El viernes 13 de abril, Krampf
tenía vagones vacíos en las siguientes ciudades, en las .74* 9-12 Un fabricante produce aparatos de aire acondicionado
para habitación en sus plantas de Houston, Phoenix y
cantidades indicadas:
Memphis. Éstos se envían a los distribuidores regionales
de Dallas, Atlanta y Denver. Los costos de envío varían,
CIUDAD OFERTA DE VAGONES
y la compañía desearía encontrar la manera de satisfacer
Morgantown 35 las demandas en cada uno de los centros de distribución,
Youngstown 60 al menor costo posible. Dallas necesita recibir 800 apara-
tos al mes, Atlanta requiere 600 y Denver necesita 200.
Pittsburgh 25
Houston dispone de 850 aparatos cada mes, Phoenix de

Tabla para el problema 9-8

A
DE PROYECTO A PROYECTO B PROYECTO C CAPACIDAD
PLANTA 1 $10 $4 $11 70
PLANTA 2 12 5 8 50
PLANTA 3 9 7 6 30
REQUISITOS 40 50 60

Tabla para el problema 9-10

TIENDA DE TIENDA DE TIENDA DE CAPACIDAD DEL

A
SUMINISTROS SUMINISTROS SUMINISTROS ASERRADERO
DE , 3
1 2 (TONELADAS)
PINEVILLE $3 S3 $2 25
OAK RIDGE 4 2 3 40
MAPLETOWN 3 2 3 30
DEMANDA DE LA TIENDA
DE SUMINISTROS 30 30 35

Tabla para el problema 9-11

A
1:1E----.---"'""2-- ---_,....„ COAL VALLEY
---7 COALTOWN COAL JUNCTION COALSBURG
MORGANTOWN 50 30 60 70
YOUNGSTOWN 20 80 10 90
PITTSBURGH 100 40 80 30
348 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

650 y Memphis de 300. El costo de envío por unidad de autor za que estas empresas unan sus excesos de oferta y
Houston a Dallas es de $8, a Atlanta es de $12 y a Denver los d'stribuyan a pequeñas empresas independientes que
es de $10. El costo por unidad de Phoenix a Dallas es de no tien generadores suficientemente grandes como para
$10, a Atlanta es de $14 y a Denver es de $9. El costo por manear la demanda. El exceso de oferta se distribuye con
unidad de Memphis a Dallas es de $11, a Atlanta es de $8 base en el costo por kilowatt-hora transmitido. La siguiente
y a Denver es de $12. ¿Cuántas unidades se deberían en- tabla muestra la demanda y la oferta en millones de kilowa-
viar de cada planta a cada centro de distribución regional? as-hura y el costo por kilowatt-hora transmitido a cuatro
¿Cuál es el costo total de esto? pequ ñas empresas eléctricas en las ciudades W, X, Y y Z:
14 •• 9-13 Finnish Furniture fabrica mesas en instalaciones ubicadas
en tres ciudades: Reno, Denver y Pittsburgh. Después, EXCESO
las mesas se envían a tres tiendas ubicadas en Phoenix, A
DE
Cleveland y Chicago. La gerencia desea desarrollar un 1TI"'- 1 \ .........
W X Y Z OFERTA
programa de distribución que satisfaga las demandas al
A 120 4¢ 9¢ 5¢ 55
menor costo posible. El costo de envío por unidad desde
cada una de las fuentes hasta cada uno de los destinos se B 8¢ 1¢ 6¢ 60 45
muestra en la siguiente tabla: C 10 120 40 70 30
DEMANDA DE ENERGÍA
NO SATISFECHA 40 20 50 20
DE A PHOENIX CLEVELAND CHICAGO
RENO 10 16 19 Encuentre el sistema de distribución de menor costo.
DENVER 12 14 13 • 9-15 Los ¡tres bancos de sangre en el Condado de Franklin
se coordinan a través de una oficina central que facilita
PITTSBURGH 18 12 12
la entrega de sangre a cuatro hospitales de la región. El
costo por enviar un contenedor estándar de sangre desde
Las ofertas disponibles son 120 unidades en Reno, 200 cada banco hasta cada hospital se indica en la tabla co-
en Denver y 160 en Pittsburgh. Phoenix tiene una deman- rrespondiente a este problema. También se da el número
da de 140 unidades, Cleveland de 160 unidades y Chica- quincenal de contenedores disponibles en cada banco y el
go de 180 unidades. ¿Cuántas unidades deberían enviarse número quincenal de contenedores de sangre necesarios
desde cada instalación de manufactura hasta cada una de en cada hospital. ¿Cuántos envíos deberían hacerse cada
las tiendas minoristas para minimizar el costo? ¿Cuál es el dos semanas desde cada banco de sangre hasta cada hospi-
costo total? tal para minimizar los costos totales de envío?
Gl• 9-14 El estado de Missouri tiene tres principales compañías ge- 24* 9-16 La compañía de bienes raíces B. Hall ha identificado
neradoras de electricidad (A, B y C). Durante los meses cuatro pequeños edificios de apartamentos en los cua-
de mayor demanda, la Autoridad Eléctrica de Missouri les le gustaría invertir. La señora Hall se ha acercado a

Tabla para el problema 9-15

DE
CoE \._...
‘ HOSPITAL 1 HOSPITAL 2 HOSPITAL 3 HOSPITAL 4 OFERTA
BANCO 1 $8 $9 $11 $16 50
BANCO 2 12 7 5 8 80
BANCO 3 14 10 6 7 120
DEMANDA 90 70 40 50

Tabla para el problema 9-16

PROPIEDAD (TASAS DE INTERÉS) (%)

COMPAÑÍA DE AHORRO LÍNEA DE CRÉDITO
Y CRÉDITO HILL ST. BANKS ST. PARK A . DRURY LANE MÁXIMA ($)
FIRST HOMESTEAD 8 8 10 11 80,000
COMMONWEALTH 9 10 12 10 100,000
WASHINGTON FEDERAL 9 11 10 9 120,000
PRÉSTAMO NECESARIO PARA
COMPRAR EL EDIFICIO $60,000 $40,000 $130,00Q $70,000
 PREGUNTAS PARA ANÁLISIS Y PROBLEMAS 349

tres sociedades de ahorro y crédito en busca de financia- puede ser satisfecha por la producción regular, el gerente
miento. Debido a que Hall ha sido un buen cliente en el de producción tiene otras tres opciones: 1. producir hasta
pasado y ha mantenido una alta calificación crediticia en 50 fregaderos más al mes en horas extras, pero a un costo
la comunidad, cada compañía de ahorro y crédito está de $130 por fregadero; 2. comprar un número limitado de
dispuesta a considerar el otorgamiento de la totalidad o fregaderos a un competidor amigable para su reventa (el
parte del préstamo hipotecario necesario para cada pro- número máximo de compras externas durante el periodo
piedad. Cada oficial de préstamo ha fijado diferentes ta- de 4 meses es de 450 fregaderos, a un costo de $150 cada
sas de interés en cada propiedad (la tasa se ve afectada uno), o 3. satisfacer la demanda usando su inventario dis-
por el vecindario del edificio, la condición de la propie- ponible. El costo mensual de mantener el inventario es de
dad y el deseo de la empresa de crédito de financiar edi- $10 por fregadero. No se permiten órdenes sin surtir (pen-
ficios de varios tamaños), y cada compañía de crédito ha dientes) por faltantes. El inventario disponible al principio
colocado un máximo al crédito total que puede otorgar a del mes uno es de 40 fregaderos. Configure este problema
Hall. Esta información se resume en la tabla de la página de "suavización de la producción" como un problema de
anterior. transporte para minimizar el costo.
Para Hall, cada edificio de apartamentos es igual- 31i 9-18 En la actualidad, Ashley's Auto Top Carriers tiene plantas
mente atractivo como inversión, así que ha decidido en Atlanta y Tulsa que abastecen a los principales centros
comprar todos los edificios posibles con el pago de in- de distribución en Los Ángeles y Nueva York. Debido a
terés total más bajo. ¿A cuáles compañías de crédito les una demanda en expansión, Ashley ha decidido abrir una
debería pedir un préstamo para comprar cuáles edificios? tercera planta y la elección se ha reducido a una de dos
Una misma propiedad puede ser financiada por una o más ciudades: Nueva Orleans o Houston. Los costos de pro-
compañías de ahorro y crédito. ducción y distribución relevantes, así como la capacidad
31? 9-17 El gerente de producción de la compañía J. Mehta está de planta y las demandas de distribución, se muestran en
planeando una serie de periodos de producción de un mes la tabla al final de esta página.
para fabricar fregaderos de acero inoxidable. La deman- ¿Cuál de las nuevas plantas posibles debería abrirse?
da para los próximos cuatro meses es la siguiente: 9-19 Marc Smith, vicepresidente de operaciones de HHN, Inc.,
un fabricante de gabinetes para conmutadores telefónicos,
DEMANDA DE FREGADEROS está restringido a cumplir los pronósticos a 5 años por la
MES DE ACERO INOXIDABLE capacidad limitada en las tres plantas existentes. Estas
tres plantas están en Waterloo, Pusan y Bogotá. Como su
1 120 asistente, usted ha recibido la información de que, debido
2 160 a las limitaciones de capacidad existentes y al mercado
3 240 mundial de gabinetes en expansión, HNN agregará una
nueva planta a las tres plantas existentes. El departamento
4 100
de bienes raíces ha recomendado a Marc dos sitios que
parecen particularmente buenos, debido a su situación
De manera normal, la compañía Mehta puede producir política estable y a un tipo de cambio tolerable: Dublín,
100 fregaderos de acero inoxidable al mes. Esto se hace Irlanda y Fontainebleau, Francia. Marc sugiere que usted
durante las horas regulares de producción a un costo de podría tomar los datos de la página siguiente y determinar
$100 por fregadero. Si la demanda en todo un mes no dónde se debería instalar la cuarta planta, con base en sus

Datos para el problema 9-18

A LOS CENTROS DE COSTO DE
DISTRIBUCIÓN LOS NUEVA PRODUCCIÓN::"
DE LAS PRODUCCIÓN
ÁNGELES YORK NORMAL
PLANTAS UNITARIO (S)

ATLANTA $8 $5 600 6
Plantas
existentes
4 7 900 5

NUEVA ORLEANB 5 6 500 4 (anticipado)

Ubicaciones
propuestas
HOUSTON 4 500 3 (anticipado)
PRONÓSTICO DE
LA DEMANDA
mi •
800 1,200 2,000

Indica que el costo de distribución (envio, manejo,

almacenamiento) será de $6 por unidad, si se envía
de Houston a Nueva York
350 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

Datos para el problema 9-19

UBICACIÓN DE A PLANTA
ÁREA DE MERCADO WATERLOO PUSAN BOGOTÁ FONTAINEBLEAU DUBLÍN

Canadá
Demanda 4,000
Costo de producción $50 $30 $40 $50 $45
Costo de transporte 10 25 20 25 25
Sudamérica
Demanda 5,000
Costo de producción 50 30 40 50 45
Costo de transporte 20 25 10 30 30
Cuenca del Pacífico
Demanda 10,000
Costo de producción 50 30 40 50 45
Costo de transporte 25 10 25 40 40
Europa
Demanda 5,000
Costo de producción 50 30 40 50 45
Costo de transporte 25 40 30 10 20
Capacidad 8.000 2.000 5.000 9,000 9,000

costos de producción y sus costos de transporte. ¿Qué si- 2: 9-21 Use los datos del problema 9.20 y los costos de produc-
X'
tio es el mejor? ción unitarios que se muestran en la siguiente tabla, para
9-20 La corporación Don Levine está considerando agregar una determinar qué ubicaciones generan el menor costo?
planta a sus tres instalaciones existentes en Decatur, Min-
neapolis y Carbondale. Se están considerando San Luis y LOCALIZACIÓN COSTOS DE PRODUCCIÓN
el Este de San Luis. Si se evalúan solamente los costos
unitarios de transporte como se muestra en las siguientes Decatur $50
tablas, ¿qué sitio es el mejor? Minneapolis 60
Carbondale 70
DE LAS PLANTAS EXISTENTES Este de San Luis 40
A DECATUR MINNEAPOLIS CARBONDALE DEMANDA San Luis 50

Blue Earth $20 $17 $21 250

Ciro 25 27 • 20 200 11 • 9-22 En una operación de taller, se pueden realizar cuatro tra-
bajos en cualesquiera de cuatro máquinas. En la siguiente
Des Moines 22 25 22 350
tabla, se presentan las horas requeridas para cada trabajo
Capacidad 300 200 150 en cada máquina. Al supervisor de planta le gustaría asig-
nar los trabajos de modo que se minimice el tiempo total.
Encuentre la mejor solución. ¿Qué asignaciones deberían
DE LAS PLANTAS PROPUESTAS hacerse?
A ESTE DE SAN LUIS SAN LUIS
MÁQUINA
Blue Earth $29 $27
TRAE O W X Y Z
Ciro 30 28
30 31 Al 10 14 16 13
Des Moines
150 150 A15 12 13 15 12
Capacidad
B2 9 12 12 11
B9 14 16 18 16
 PREGUNTAS PARA ANALISIS Y PROBLEMAS 351

Q- 9-23 Cuatro automóviles han entrado al taller de reparaciones CURSO

de Bubba para varios tipos de trabajos, que van desde un
ajuste de la transmisión hasta un trabajo de frenos. El nivel ESTADÍS- ADMINISTRA- FINAN-
de experiencia de los mecánicos es muy variado, y Bubba PROFESOR TICA CIÓN ZAS ECONOMÍA
quiere minimizar el tiempo requerido para completar todas Anderson 90 65 95 40
las tareas. Se ha estimado el tiempo en minutos para que 70 60 80 75
Sweeney
cada mecánico complete cada trabajo. Billy puede comple-
Williams 85 40 80 60
tar el trabajo 1 en 400 minutos, el trabajo 2 en 90 minutos,
el trabajo 3 en 60 minutos y el trabajo 4 en 120 minutos. McKinney 55 80 65 55
Taylor terminaría el trabajo 1 en 650 minutos, el trabajo 2
en 120 minutos, el trabajo 3 en 90 minutos y el trabajo 4 en g•- 9-27 El administrador del hospital general en St. Charles debe
ac
180 minutos. Mark puede terminar el trabajo 1 en 480 mi- nombrar a jefes de enfermería para cuatro departamentos
nutos, el trabajo 2 en 120 minutos, el trabajo 3 en 80 minu- de reciente creación: urología, cardiología, ortopedia y
tos y el trabajo 4 en 180 minutos. John completaría el obstetricia. En previsión de este problema de personal, ha
trabajo 1 en 500 minutos, el trabajo 2 en 110 minutos, el tra- contratado cuatro enfermeras: Hawkins, Condriac, Bardot
bajca en 90 minutos y el trabajo 4 en 150 minutos. Cada y Hoolihan. Debido a que cree en el enfoque del análisis
mecánico debería asignarse a sólo uno de los trabajos. cuantitativo para resolver problemas, el gerente entrevistó
¿Cuál es el tiempo total mínimo requerido para terminar a cada enfermera, considerado sus antecedentes, persona-
estas tareas? ¿Quién debería asignarse a cada trabajo? lidad y talento, y desarrolló una escala de costos que va
de O a 100 para utilizarla en la asignación. Un O para la
1: 9-24 Los equipos de arbitraje de béisbol se encuentran actual-
2 enfermera Bardot asignada a la unidad de cardiología im-
mente en cuatro ciudades donde están empezando series
plica que ella sería perfectamente adecuada para esa tarea.
de tres juegos. Cuando éstas terminen, se requiere que los
Por el contrario, un valor cercano a 100 implicaría que no
equipos de arbitraje trabajen en partidos de cuatro ciuda-
es adecuada en absoluto para ser jefa de esa unidad. La
des diferentes. En la siguiente tabla se muestran las dis-
tabla adjunta presenta las cifras completas de costos que
tancias (millas) desde cada una de las ciudades donde los
el gerente del hospital otorgó para todas las asignaciones
árbitros están trabajando actualmente hasta las ciudades
posibles. ¿Qué enfermera debería asignarse a qué unidad?
donde comenzarán los nuevos juegos:
A DEPARTAMENTO

DE KANSAS CITY CHICAGO DETROIT TORONTO ENFER- URO- CARDIO- OBSTE-

MERA LOGÍA LOGÍA ORTOPEDIA TRICIA
Seattle 1,500 1,730 1,940 2,070
Hawkins 28 18 15 75
Arlington 460 810 1,020 1,270
Condriac 32 48 23 38
Oakland 1,500 1,850 2,080 X 24 36
Bardot 51 36
Baltimore 960 610 400 330 Hoolihan 25 38 55 12
La X indica que el equipo de árbitros en Oakland no
puede enviarse a Toronto. Determine qué equipo debería 9-28 La compañía Gleaming acaba de desarrollar un nuevo
enviarse a cada ciudad para minimizar la distancia total líquido para lavar platos y está preparando una campaña
recorrida. ¿Cuántas millas se viajaría, si se realizaran estas promocional en televisión nacional. La compañía ha de-
asignaciones? cidido programar una serie de comerciales de un minuto
1: 9-25 En el problema 9-24 se encontró la distancia mínima durante la hora de máxima audiencia de las amas de casa
viajada. Para saber cuánto mejor es esta solución que las entre la 1 P.M. y las 5 P.M. Para alcanzar la mayor audien-
asignaciones que podrían haberse realizado, encuentre cia posible, Gleaming quiere programar un solo anuncio
las asignaciones que darían la distancia máxima recorrida. en cada una de cuatro cadenas televisivas y que un solo
Compare esta distancia total con la distancia que se en- anuncio aparezca durante cada uno de los cuatro bloques
de tiempo de una hora. En la siguiente tabla se presentan
contró en el problema 9-24.
los niveles de exposición para cada hora, que represen-
30
º: 9-26 Roscoe Davis, director del Departamento de Negocios tan el número de espectadores por $1,000 gastado. ¿En
de una universidad, ha decidido aplicar un nuevo método qué cadena debería programarse el anuncio cada hora para
para la asignación de profesores a los cursos del próximo ofrecer la máxima exposición a la audiencia?
semestre. Como criterio para juzgar quién debería im-
partir cada curso, el profesor Davis revisa evaluaciones
CADENA
de enseñanza en los últimos dos años (realizadas por los
estudiantes). Como cada uno de los cuatro profesores im- HORAS DE AUDIENCIA A B C INDEPENDIENTE
partió cada uno de los cuatro cursos en un momento u otro
durante el periodo de dos años, Davis puede otorgar una 1-2 P.M. 27.1 11.3
18.1 9.5
calificación en cada curso para cada profesor. Estos valo- 2-3 P.M. 18.9 15.5 17.1 10.6
res se muestran en la siguiente tabla. Encuentre la mejor 3-4 P.M. 19.2 18.5 9.9 7.7
asignación de los profesores a los cursos para maximizar 4-5 P.M. 11.5 21.4 16.8 12.8
la calificación general de la enseñanza.
352 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

Datos para el problema 9-29

PLANTA
DISPOSITIVOS
MÉDICOS 1 2 3 4 5 6 7 8
C53 $0.10 $0.12 $0.13 $0.11 $0.10 $0.06 S0.16 $0.12
C81 0.05 0.06 0.04 0.08 0.04 0.09 0.06 0.06
D5 032 0.40 0.31 0.30 0.42 0.35 0.36 0.49
D44 0.17 0.14 0.19 0.15 0.10 0.16 0.19 0.12
E2 0.06 0.07 0.10 0.05 0.08 0.10 0.11 0.05
E35 0.08 0.10 0.12 0.08 0.09 0.10 0.09 0.06
G99 0.55 0.62 0.61 0.70 0.62 0.63 0.65 0.59

Q. 9-29 La compañía de Patricia García está produciendo siete en astrofísica o en astromedicina. Uno de estos especialis-
nuevos productos médicos. Cada una de las ocho plan- tas será asignado a cada uno de los 10 vuelos programados
tas de García puede agregar un producto más a su actual para los próximos nueve meses. Los especialistas de la
línea de dispositivos médicos. En la tabla anterior, se misión son responsables de realizar experimentos cientí-
muestran los costos de producción unitarios para las di- ficos y médicos en el espacio, o bien, del lanzamiento, la
ferentes piezas en las ocho plantas. ¿Cómo debería García recuperación ola reparación de satélites. El mismo jefe de
asignar los nuevos productos a las plantas para minimizar personal de los astronautas es un ex miembro de la tripu-
los costos de producción? lación, con tres misiones en su haber, y debe decidir quién
9-30 Haifa Instruments, un productor israelí de unidades por- tiene que ser asignado y capacitado para cada una de las
tátiles de diálisis de riñón y otros productos médicos, de- diferentes misiones. Claramente, los astronautas con edu-
sarrolla un plan global de ocho meses. Se pronostica que cación médica son más adecuados para las misiones que
la demanda y la capacidad (en unidades) serán como se implican experimentos biológicos o médicos; mientras
indica en la siguiente tabla. que aquellos con títulos en ingeniería -u orientados a la
El costo de producción de cada unidad de diálisis física- son los más adecuados para otro tipo de misiones.
es de $1,000 en tiempo regular, $1,300 en horas extras y El jefe asigna a cada astronauta una calificación en una
$1,500 en un subcontrato. El costo por mantener una uni- escala de 1 a 10 para cada posible misión, un 10 implica
dad en inventario es de $100 al mes. No hay existencias de una aptitud perfecta para la tarea en cuestión y 1 es una
inventario ni al principio ni al final. carencia total de aptitud. Sólo se asigna un especialista a
cada vuelo, y ninguno se reasigna hasta que todos los de-
(a) Establezca un plan de producción, utilizando el mo-
delo de transporte, que minimice el costo. ¿Cuál es el más hayan volado al menos una vez.
costo de este plan? (a) ¿Quién debería asignarse a qué vuelo?
(b) A través de una mejor planeación, la producción en (b) La NASA acaba de saber que Anderson se casará en
tiempo regular puede ajustarse exactamente al mismo febrero y que se le ha concedido una gira publicitaria
valor de 275 por mes. ¿Esto altera la solución? en Europa durante ese mes. (Tiene la intención de lle-
(c) Si los costos de horas extras se elevan de $1,300 a var a su esposa y tomar el viaje doble como una luna
$1,400, ¿cambia esto su respuesta al inciso (a)? ¿Qué de miel). ¿Cómo cambia esto la programación final?
pasaría si se reducen a $1,200? (c) Cerio se ha quejado de que fue calificado errónea-
9-31 La tripulación de astronautas de la NASA incluye actual- mente en sus misiones de enero. Afirma que ambas
mente 10 especialistas de misión que poseen un doctorado calificaciones deberían ser 10; el jefe está de acuerdo

Datos para el problema 9-30

CAPACIDAD
FUENTE ENE. FEB. MAR. ABR. Y. JUN. JUL. AGO.
Mano de obra
Tiempo regular 235 255 290 300 290 300 290
Tiempo extra 20 24 26 24 130 28 30 30
Subcontrato 12 15 15 17 17 19 19 20
Demanda 255 294 321 301 330 320 345 340
 PREGUNTAS PARA ANÁLISIS Y PROBLEMAS 353

Datos para el problema 9-31

MISIÓN
ENE. ENE. FEB. FEB. MAR. ABR. MAY. JEN. AGO. SER
ASTRONAUTA 12 27 5 26 26 12 1 9 20 19

Vincze 9 7 2 1 I() 9 8 9 2 6
Veit 8 8 3 4 7 9 7 7 4 4
Anderson 2 1 10 10 1 4 7 6 6 7
Herbert 4 4 10 9 9 9 1 2 3 4
Schatz 10 10 9 9 8 9 1 1 1 1
Plane 1 3 5 7 9 7 10 10 9 2
Certo 9 9 8 8 9 1 1 2 2 9
Moses 3 2 7 6 4 3 9 7 7 9
Brandon 5 4 5 9 10 10 5 4 9 8
Drtina 10 10 9 7 6 7 5 4 8 8

y recalcula el programa. ¿Ocurren algunos cambios han evaluado las áreas con respecto a la deseabilidad de
en el progrania establecido en el inciso (b)? su asignación, como se muestra en la siguiente tabla. La
(d) ¿Cuáles son las fortalezas y las debilidades de este en- escala va de 1 (menos deseable) a 5 (más deseable). ¿Qué
foque para la programación? asignaciones deberían hacerse si se desea maximizar el to-
Q: 9-32 La Corporación XYZ está ampliando su mercado a fin tal de las calificaciones?
de incluir Texas. Cada vendedor es asignado a distribui- 9-33 La constructora Bechtold se encuentra en el proceso de
dores potenciales en una de cinco áreas diferentes. Se instalación de líneas eléctricas en un gran desarrollo ha-
prevé que el vendedor pasará de tres a cuatro semanas en bitacional. Steve Bechtold quiere minimizar la longitud
su área asignada. Se iniciará una campaña de marketing total de alambre utilizado, con la finalidad de minimizar
en todo el estado una vez que el producto se haya entre- sus costos. El desarrollo habitacional se muestra como una
gado a los distiibuidores. Los cinco vendedores que serán red. Cada casa ha sido numerada, y las distancias entre ca-
asignados a estas áreas (una persona en cada una de ellas) sas se dan en cientos de pies. ¿Qué recomienda usted?

Tabla para el problema 9-32

AUSTIN/SAN DALLAS/FT. EL PASO/OESTE HOUSTON/ CORPUS CHRISTI/VALLE

ANTONIO WORTH DE TEXAS GALVESTON DEL RÍO GRANDE
Erica 5 3 2 3 4
Louis 3 4 4 2 2
Maria 4 5 4 3 3
Paul 2 4 3 4 3
Orlando 4 5 3 5 4

Red para el problema 9-33

354 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

Red para el problema 9-34

9-34 La ciudad de Nueva Berlín está considerando hacer varias 9-36 En la siguiente red, se muestra el sistema de carreteras
de sus calles de un solo sentido (vea la red que se propor- alrededor del complejo hotelero en International Drive
ciona). Asimismo, debido al aumento de impuestos a la (nodo 1) hasta Disney World (nodo 11) en Orlando, Flo-
propiedad y a un dinámico plan de desarrollo vial, la ciu- rida. Los números junto a los nodos representan el flujo
dad de Nueva Berlín ha estado considerando el aumento de tránsito en cientos de automóviles por hora. ¿Cuál es
de la capacidad de dos de sus carreteras. Si se hace esto, el flujo máximo de autos desde el complejo hotelero hasta
el tránsito por el camino 1-2 (del nodo 1 al nodo 2) se in- Disney World?
crementaría de 2 a 5, y la capacidad de tránsito a lo largo
del camino 1-4 aumentaría de 1 a 3. ¿Cuál es el número Red para el problema 9-36
máximo de automóviles por hora que pueden viajar de
este a oeste con el sistema de carreteras actual? Si se rea-
lizan los aumentos de capacidad de los caminos 1-2 y 2-5,
¿cómo cambiaría el número de automóviles por hora que
pueden viajar de este a oeste?
9-35 El director de seguridad quiere conectar cámaras de video
de seguridad al sitio de control principal desde cinco ubi-
caciones potencialmente problemáticas. En forma ordina-
ria, el cable simplemente se tendería desde cada sitio hasta
el punto de control principal. Sin embargo, debido a que el
entorno es potencialmente explosivo, el cable se debe ten-
der en un conducto especial cuyo aire se purga continua-
mente. Este conducto es muy caro, pero suficiente para
manejar cinco cables (el máximo que podría necesitarse).
Utilice la técnica del árbol de expansión mínima para en- 9-37 Los números de la red que se muestra a continuación re-
contrar la ruta con la distancia mínima del conducto entre presentan los miles de galones por hora que fluyen a través
las ubicaciones indicadas en la figura. (Observe que no de una planta de procesamiento químico. Dos terminales de
tiene importancia cuál es el sitio principal de control). la planta de procesamiento químico, representadas por los

Red para el problema 9-35

Red para el problema 9-37
 PREGUNTAS PARA ANÁLISIS Y PROBLEMAS 355

nodos 6 y 7, han tenido problemas recientemente, y se está (b) Después de revisar los costos del cable y de la ins-
considerando repararlas. Sin embargo, las reparaciones re- talación, la constructora quisiera alterar los costos
querirían que estas terminales (nodos) se cerraran durante para la instalación de la TV por cable entre sus
una cantidad significativa de tiempo, y ningún material casas. Es necesario modificar las primeras ramas.
podría fluir hacia estos nodos o desde ellos, sino hasta Los cambios se resumen en la siguiente tabla.
completar los trabajos. ¿Qué impacto tendría el cierre de ¿Cuál es el impacto en los costos totales?
estos nodos sobre la capacidad de la red?
9-38 Las ciudades alemanas alrededor del Bosque Negro es- NODO DE NODO COSTO
tán representadas por los nodos de la red que se muestra RAMA INICIO FINAL (S100si
a continuación. Las distancias entre las ciudades se dan en
kilómetros. Encuentre la ruta más corta desde la ciudad 1 Rama 1 1 2 5
hasta la ciudad 16. Si ciertas inundaciones en las ciudades Rama 2 1 3
7 y 8 fuerzan el cierre de todos los caminos que conducen
hacia esas ciudades o que salen desde ellas, ¿cómo impac- Rama 3 1 4 1
taría esto a la ruta más corta? Rama 4 1 5
Rama 5 2 6 7
Red para el problema 9-38
Rama 6 3 7 5
Rama 7 4 7 7
Rama 8 5 8 4
Rama 9 6 7 1
Rama 10 7 9 6
Rama 11 8 9 2

ti 9-40 Para10 ircaminos

de Quincy a Old Bainbridge, George Olin tiene
posibles. Cada uno puede considerarse
como una rama en un problema de la ruta más corta.
(a) Determine la manera de llegar desde Quincy
(nodo 1) hasta Old Bainbridge (nodo 8) que mini-
mizará la distancia total recorrida. Las distancias
gi 9-39 La constructora Grey quisiera determinar la forma me-
se dan en cientos de millas.
nos costosa de conectar TV por cable en las casas que
está construyendo. Se han identificado 11 posibles ramas
o rutas que podrían utilizarse para conectar las casas. El NODO DISTANCIA
costo en cientos de dólares y las ramas se resumen en la DE NODO (EN CIENTOS
siguiente tabla. RAMA INICIO FINAL DE MILLAS)
(a) ¿Cuál es la forma menos costosa de llevar el cable a Rama 1 1 2 3
estas casas?
Rama 2 1 3 2
Rama 3 2 4 3
NODO DE NODO COSTO
RAMA INICIO FINAL ($100s) Rama 4 3 5 3
Rama 1 1 2 5 Rama 5 4 5 1
Rama 2 1 3 6 Rama 6 4 6 4
Rama 3 1 4 6 Rama 7 5 7 2
Rama 4 1 5 5
Rama 8 6 7
Rama 5 2 6 7
Rama 9 6 8 3
Rama 6 3 7 5
Rama 10 7 8 6
Ramal 4 7 7
Rama 8 5 8 4
(b) George Olin cometió un error al estimar las dis-
Rama 9 6 7 1 tancias de Quincy a Old Bainbridge. Las nuevas
Rama 10 7 9 6 distancias se dan en la siguiente tabla. ¿Qué im-
Rama 11 8 9 2 pacto tiene esto en la ruta más corta desde Quincy
hasta Old Bainbridge?
356 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

• 9-42 La si lente tabla representa una red donde los arcos se

NODO DISTANCIA
identi ican mediante sus nodos de inicio y final. Dibuje
DE NODO (EN CIENTOS
la red y utilice un árbol de expansión mínima para encon-
RAMA INICIO FINAL DE MILLAS)
trar la distancia mínima requerida para conectar todos los
Rama 1 1 nodos.
Rama 2 3 2
Rama 3 1 4 3 ARCO DISTANCIA
Rama 4 3 5 1 1-2 12
Rama 5 4 5 1 1-3 8
Rama 6 4 6 4 2-3 7
Ramal 5 7 2 2-4 10
Rama 8 6 7 2 3-4 9
Rama 9 6 8 3
3-5 8
Rama 10 7 8 6
4-5 8
2 : 9-41 South Side Oil and Gas, una nueva empresa en Texas, ha
24. 4-6 11
desarrollado una red de oleoductos para transportar petró- 5-6 9
leo desde sus campos de exploración hasta una refinería
y otros sitios. Hay 10 tuberías (ramas) en la red. En la si-
guiente tabla, se proporcionan el flujo de petróleo en cien- 3C• 9-43 La Northwest University se encuentra en el proceso de
completar una red de buses de computadora que conec-
tos de galones y la red de tuberías.
tarán las instalaciones informáticas en todo el campus.
(a) ¿Cuál es el máximo que puede fluir a través de la red? El objetivo principal es tender un cable principal desde
un extremo del campus hasta el otro (nodos 1 a 25) a tra-
NODO vés de duetos subterráneos. Estos ductos se muestran en
DE NODO CAPACIDAD la red; la distancia entre ellos se da en cientos de pies.
RAMA INICIO FINAL CAPACIDAD INVERSA FLUJO Por fortuna, estos ductos subterráneos tienen capacidad
Rama 1 1 2 10 4 10 restante a través de la cual se puede introducir el cable
Rama 2 1 3 8 2 5 del bus.
Rama 3 2 4 12 1 10 (a) Dada la red para este problema, ¿qué tan larga (en
Rama 4 2 5 6 6 0 cientos de pies) es la ruta más corta desde el nodo 1
5 hasta el nodo 25?
Rama 5 3 5 8 1
(b) Además de la red de buses de computadora, también se
Rama 6 4 6 10 2 10 e,stá planeando un nuevo sistema telefónico. El sistema
Rama 7 5 6 10 10 O telefónico usaría los mismos ductos subterráneos. Si
Rama 8 5 7 5 5 5 se instala el sistema telefónico, las siguientes rutas a
Rama 9 6 8 10 1 10 lo largo de los ductos estarían llenas y ya no podrían
7 8 10 1' 5 alojar la red de buses de computadora: 6-11,7-12 y
Rama 10
17-20. ¿Qué cambios (si los hubiera) tendrían que ha-
(b) South Side Oil and Gas debe modificar sus patrones cerse a la ruta utilizada para los buses de computadora,
de flujo en la red de tuberías. Los nuevos datos se en- si se instalara el sistema telefónico?
cuentran en la siguiente tabla. ¿Qué impacto tiene esto
en el flujo máximo a través de la red?

NODO Red para el problema 9-43

DE NODO CAPACIDAD
RAMA INICIO FINAL CAPACIDAD INVERSA FLUJO
Rama 1 1 2 10 4 10
Rama 2 1 3 8 2 5
Rama 3 2 4 12 1 10
Rama 4 2 5 0
Rama 5 3 5 8 1 5
Rama 6 4 6 10 2 10
Rama 7 5 6 10 10 O
Rama 8 5 7 5 5 5
Rama 9 6 8 10 1 10
Rama 10 7 8 10 1 5
 ESTUDIO DE CASO 357

(c) La universidad decidió instalar el nuevo sistema tele- para la primera red o la red original usó por completo
fónico antes que el cable para la red de computado- la capacidad a lo largo de su trayectoria. Ante esta
ras. Debido a la demanda inesperada de instalaciones situación, ¿cuál es el mejor camino para el segundo
informáticas, se requiere un cable adicional desde el cable de red?
nodo 1 hasta el nodo 25. Lamentablemente, el cable

Estudio de caso

Andrew-Carter, Inc.

Andrew-Carter, Inc. (A-C), es un importante productor canadiense Las capacidades de planta en unidades por semana son
y distribuidor de accesorios de iluminación al aire libre. Sus dis- Planta 1, en tiempo regular 27,000 unidades
positivos se distribuyen en toda América del Norte y ha tenido una
Planta 1, en tiempo extra 7,000 unidades
gran demanda durante varios años. La compañía opera tres plantas
que fabrican el aparato y lo envía a cinco centros de distribución Planta 2, en tiempo regular 20,000 unidades
(almacenes). Planta 2, en tiempo extra 5,000 unidades
Durante la actual recesión, A-C ha visto una caída importante en Planta 3, en tiempo regular 25,000 unidades
la demanda de sus dispositivos, puesto que el mercado de viviendas
ha disminuido. Con base en los pronósticos de las tasas de interés, Planta 3, en tiempo extra 6,000 unidades
el jefe de operaciones siente que la demanda de vivienda y, por lo Si A-C cierra cualquiera de sus plantas, sus costos semanales
tanto, de su producto se mantendrá deprimido en el futuro previsi- cambiarán, porque los costos fijos son menores para una planta no
ble. A-C está considerando el cierre de una de sus plantas, dado que operativa. En la tabla 9.5 se muestran los costos de producción de cada
ahora está operando con un exceso de capacidad prevista de 34,000 planta, tanto variables de tiempo regular y tiempo extra, como fijos
unidades por semana. Las demandas semanales pronosticadas para con la planta operando y cerrada. La tabla 9.6 muestra los costos de
el año próximo son envío desde cada planta hasta cada almacén (centro de distribución).
Almacén 1 9,000 unidades
Preguntas para análisis
Almacén 2 13,000 unidades
Almacén 3 11,000 unidades [Link]úe las diferentes configuraciones de plantas operando y ce-
rradas que satisfagan la demanda semanal. Determine qué confi-
Almacén 4 15.000 unidades
guración minimiza los costos totales.
Almacén 5 8,000 unidades 2. Analice las implicaciones del cierre de una planta.
Fuente: Profesor Michael Boleta, University of the Pacific.

TABLA 9.5 COSTO FIJO POR SEMANA

Andrew-Carter, Inc.,
costos de producción COSTO VARIABLE OPERANDO SIN OPERAR
variables y fijos por Núm. 1, tiempo regular $2.80/unidad $14,000 $6,000
semana
Núm. 1, tiempo extra 3.52
Núm. 2, tiempo regular 2.78 12,000 5,000
Núm. 2, tiempo extra 3.48
Núm. 3, tiempo regular 2.72 15,000 7,500
Núm. 3, tiempo extra 3.42
358 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

TABLA 9.6
AL CENTRÓ DE DISTRIBUCIÓN
Andrew-Carter, Inc.,
costos de distribución DE LA PLANTA WI W3 W4 W5
por unidad
Núm. 1 S0.50 $0.44 $0.49 50.46 $0.56
Núm. 2 0.40 0.52 0.50 0.56 0.57
Núm. 3 0.56 0.53 0.51 0.54 0.35

Estudio de caso

Northeastern Airlines

Northeastern Airlines es una aerolínea regional que da servicio a número de vuelos directos, lo cual significaría que una ciudad servida
nueve ciudades en los estados de la región de Nueva Inglaterra, así por Northeastern solamente podría tener vuelos directos a una sola
como a ciudades en Nueva York, Nueva Jersey y Pennsylvania. Aun- ciudad distinta. 1I,a compañía tiene previsto contratar a un consul-
que hay vuelos sin escalas para algunas de las rutas, con frecuencia se tor de análisis de marketing para determinar cómo se vería afectada la
requieren vuelos de conexión. La red muestra las ciudades servidas demanda por los vuelos más largos con más conexiones, y para pro-
y las utilidades por pasajero a lo largo de cada una de esas rutas. Las nosticar la demanda a lo largo de cada una de las rutas con base en
rutas de Boston a Providence y de Providence a Boston generan sólo un mapa modificado de las operaciones de vuelo. Antes de contratar
$9 de utilidad por pasajero después de todos los gastos. Para dar servi- al consultor, la empresa desea determinar la forma más rentable (con
cio a estas ciudades, Northeastern opera una flota de 16 jets Embraer base en la utilidad por pasajero) de continuar sirviendo a todas las
E-195 de 122 pasajeros. Estos aviones, que introdujo Embraer por pri- ciudades.
mera vez a finales de 2004, han ayudado a que Northeastem Airlines
siga siendo rentable durante varios años. Sin embargo, recientemente Preguntas para análisis
los márgenes de ganancia han estado cayendo y Northeastem se en-
1. Desarrolle un mapa de operaciones de vuelo que siga sirviendo
frenta a la perspectiva de reducir sus operaciones.
a cada una de las nueve ciudades, pero que maximice la utilidad
La gerencia de Northeastern Airlines ha considerado varias op-
por pasajero de la compañía (Sugerencia: Encuentre el árbol de
ciones para reducir costos y aumentar la rentabilidad. Debido a las re-
expansión máxima).
gulaciones de la Administración Federal de Aviación, la empresa debe
2. Comente cómo deberían asignarse los 16 jets.
continuar sirviendo a cada una de las nueve ciudades. Sin embargo, la
manera en que se da servicio a estas ciudades depende de la gerencia Gracias al profesor aizul Huq, de la Escuela de Negocios de la Ohio University,
de la aerolínea. Se ha hecho la sugerencia de proporcionar un menor por proporcionarnos este caso.

Área de servicio de
Northeastern Airlines Burlington, VT Orono, ME
Syracuse, NY 12 •
10
13

Nashua, NH

18

151
Boston, MA
16 17
Providence, RI
Hartford, CT
14
Newark, NJ
State College, PA
 ESTUDIO DE CASO 359

Estudio de caso

Problemas de tránsito en la Southwestern University

La Southwestern University (SWU), ubicada en la pequeña ciudad de que pueden pasar a través de los nodos 2, 3 y 4 es 35,000 por hora, y
Stephenville, Texas, está experimentando un mayor interés en su pro- la cantidad de automóviles que pueden pasar a través de los nodos 5, 6
grama de fútbol americano, ahora que ha contratado a un entrenador y 7 es aún mayor. Por lo tanto, el Dr. Lee ha sugerido que la capacidad
de renombre. El aumento en las ventas de boletos para la próxima actual es de 33,000 vehículos por hora. También ha recomendado que
temporada implica ingresos adicionales, pero también significa ma- se haga una petición al alcalde de la ciudad para que expanda una de
yores quejas debido a los problemas de tránsito asociados con los las rutas desde el estadio hasta la autopista para permitir un adicional
partidos de fútbol. Cuando se construya un nuevo estadio, esto sólo de 2,000 vehículos por hora. Recomienda ampliar la ruta más barata.
empeorará. Marty Starr, presidente de la SWU, ha pedido al Comité Si la ciudad decide no ampliar las carreteras, se considera que el pro-
de Planeación de la Universidad que estudie este problema. blema de tránsito sería una molestia, pero aun así sería manejable.
Con base en las proyecciones de tránsito, al Dr. Starr le gustaría Con base en la experiencia, se cree que mientras la capacidad de
que hubiera la capacidad suficiente para que 35,000 automóviles por las calles no sea 2,500 vehículos por hora inferior al número de autos
hora pudieran viajar desde el estadio hasta la autopista interestatal. que salen del estadio, el problema no es demasiado grave. Sin em-
Para aliviar los problemas de tránsito esperados, se está considerando bargo, la gravedad del problema crece dramáticamente por cada 1,000
la ampliación de algunas de las calles actuales que llevan de la uni- vehículos adicionales que se agregan a las calles.
versidad a la carretera interestatal, con la finalidad de aumentar su
capacidad. A continuación, se muestran las capacidades de las calles
actuales con el número de automóviles (en miles) por hora. Dado que Preguntas para análisis
el principal problema será después de cada partido, tan sólo se indican [Link] no hay ampliación, ¿cuál es el número máximo de autos que
los flujos desde el estadio. Estos flujos consideran que algunas calles en realidad puede viajar cada hora desde el estadio hasta la inte-
cercanas al estadio se transforman en calles de un solo sentido durante restatal? ¿Por qué este número no es igual a 33,000, como sugi-
un corto periodo después de cada juego,•con oficiales de policía que rió el Dr. Lee?
dirigen el tránsito. 2. Si los costos de ampliación son los mismos para cada una de las
Alexander Lee, miembro del Comité de Planeación de la Univer- calles, ¿cuál(es) de ellas recomendaría expandir para aumentar
sidad, ha dicho que una revisión rápida de las capacidades de tránsito la capacidad a 33,000? ¿Qué calles recomendaría ampliar con la
en el diagrama indica que el número total de automóviles por hora que finalidad de obtener una capacidad total del sistema de 35,000
pueden salir del estadio (nodo 1) es de 33,000. El número de autos autos por hora?

Caminos del estadio

a la interestatal

Estadio Interestatal
360 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

Estudios de caso en Internet

Visite nuestra página en Internet, [Link]ñ [Link]/render, y consulte estos estudios de caso
adicionales:
(1) Northwest General Hospital: Este caso implica la mejora del sistema de distribución de alimentos en
un hospital, con la finalidad de reducir las posibilidades de que los alimentos se enfríen antes de que
se sirvan a los pacientes.
(2) Custom Vans, Inc: Este caso se refiere a la búsqueda de la mejor ubicación para una planta que fabri-
cará duchas usadas en furgonetas personalizadas.
(3) Ranch Development Project: Este caso se refiere a la búsqueda de la forma menos costosa en que se
pueden brindar los servicios de agua y alcantarillad a los hogares de una nueva urbanización.
(4) Old Oregon Wood Store: Este caso implica la determinación de la mejor forma de asignar empleados
a los trabajos en una pequeña empresa de manufactura.
(5) Binder's Beverage: Este caso trata sobre la determinación de la ruta más corta entre una planta y un
almacén.

Bibliografía

Adlakha, V. y K. Kowalski. "Simple Algorithm for the Source-Induced Fixed-Charge Liu, Jinming y Fred bar. "Project Time—Cost Trade-off Optimization by Maximal
Transportation Problem", Journal of the Operational Research Society 55, Flow Theory", Journal of Construction Engineering & Management 130, 4
12 (2004): 1275-1280. (julio/agosto de 2004): 607-609.
Bowman, E. "Production Scheduling by the Transportation Method of Linear Liu, Shiang-Tai. —The Total Cost Bounds of the Transportation Problem with
Programming", Operations Research 4 (1956). Varying Dem1nd and Supply", Omega 31, 4 (2003): 247-251.
Dawid, Herbert, Johannes Konig y Christine Strauss. "An Enhanced Rostering Martello, Silvano. "Jen° Egervary: From the Origins of the Hungarian Algorithm
Model for Airline Crews", Computers and Operations Research 28, 7 to Satellite Communication", Central European Journal of Operations
(junio de 2001): 671-688. Research 18, 1 (2010): 47-58.
Hezarkhani, Behzad y Wieslaw Kubiak. "A Coordinating Contract for Transship- McKeown, P. y B. Workman. "A Study in Using Linear Prograrruning to Assign
ment In a Two-Company Supply Chain", European Journal of Operational Students to Schools", Interfaces 6, 4 (agosto de 1976).
Research 207, 1 (2010): 232-237. Render, B. y R. M. Stair. Introduction to Management Science. Boston: Allyn &
Jacobs, T., B. Smith y E. Johnson. "Incorporating Network Flow Effects tato the Bacon, Inc., 1992.
Airline Fleet Assignment Process", Transportation Science 42, 4(2008): Sancho, N. G. F. "On the Maximum Expected Flow in a Network", Journal of
514-529. Operational Research Society 39 (mayo de 1988): 481-485.
Johnsonbaugh, Richard. Discrete Mathematics, 5a. ed. Upper Saddle River, Sedeño-Noda, Antonio, Carlos González-Martín y Sergio Alonso. "A Generalization
Prentice Hall, 2001. of the Scaling Max-Flow Algorithm", Computers & Operations Research
Kawatra, R. y D. Bricker. "A Multiperiod Planning Model for the Capacitated 31, 13 (noviembre de 2004): 2183-2198.
Minimal Spanning Tree Problem", European Journal of Operational Troutt, M. D. y G. P. White. "Maximal Flow Network Modeling of Production
Researrh 121, 2 (2000): 412-419. Bottleneck Problems", Journal of the Operational Research Sociery 52, 2
Koksalan, Murat y Haldun Sural. "Efes Beverage Group Makes Location and (febrero de 2001): 182-187.
Distribution Decisions for lis Malt Plants", Interfaces 29, 2 (marzo-abril
de 1999): 89-103.

Apéndice 9.1: Uso de QM para Windows

QM para Windows tiene en su menú un módulo de transporte, así como un módulo de asignación.
Ambos son fáciles de usar en cuanto a la introducción de datos y sencillos de interpretar en términos
de sus salidas. En el programa 9.9A se muestra la pantalla de entrada para el ejemplo de transporte de
Executive Furniture. Es posible especificar la técnica de solución de inicio. Los resultados se muestran
en el programa 9.9B. El programa 9.10A muestra a pantalla de entrada para el ejemplo de asignación
del taller Fix-It. Basta con introducir los costos y hacer clic en Solve. El programa 9.10B presenta la
solución a este problema.
 APÉNDICE 9.1: USO DE QM PARA WINDOWS 361

PROGRAMA 9.9A ( En el menú desplegable Module,

Entrada de QM para seleccione Transportation.
Windows del ejemplo
de transporte de 11 Eza Eme Ve« Idadde Fut.», Dell
Executive Furniture UlrklEadVaariltilifil "VarBal" ts»°1›a`"
!!ate 12 uI .00 005-1 ajjja-a

Haga clic en New Problem y

cuando se abra la ventana, j"Después de introducir los
escriba el número de fuentes e Furniture corporation datos, haga clic en Solve.
y destinos. Haga clic en OI5.„.h que
Boston Cleveland SUPPLY
Des MOIllft5 5 4 3 100
Introduzca los costos,Ta'
a\ 4 3 300
ofertas y las demandas. 9 7 5 300
300

PROGRAMA 9.9B yac Ecbt VieM Module Fognat /coas rindo& Ilelp

Solución en QM para 1 0 la, fildilbeilnIZI " ..Iwasg* -§alz...kleeit....12.—

Windows del ejemplo
ii Arial . 12 , I 8 / º I lig Z IIII . • ft 0.0[71O Hl á - e'" ES 1
Objectne Statint astbod
de transporte de C Miciain
l'I Iffirairixe
lAry stagin wy.:d _d
Executive Furniture
Executive Furndure Corporation Solution
Optima' cost = Albuquerque Boston Cleveland
$3.900
Des Momes 100
EyansvIlle 200 100
Fort Lauderdale 100 [

PROGRAMA 9.10A En el menú desplegable Module,

Entrada en QM para seleccione Assignment.
Windows del ejemplo
de asignación para el ji Eüe Edit Vitroi Module Fognst Tools

11 E!! IJ 1 ea al g nxix
taller Fix-It
2 - a I .0[0:1 - 0.0 $
1

/..-Haga clic en New Problem y Después de introducir

cuando se abra la ventana, los datos, haga clic en
escriba el número de asignacioney Solve.

Project 1 Project2
11 14
Introduzca los 8 10 11
costos. 12 7
362 CAPÍTULO 9 • MODELOS DE TRANSPORTE, ASIGNACIÓN Y REDES

PROGRAMA 9.10B J file Etit Y.... Module Fornee joces ?fiador del ---1
ID »g él Ba 'al 111:111 " 1.1 ui a n* ze I co
Salida de QM para
Windows del ejemplo
E m.,
Otiedeve
.
" la I A. *0,
12.1 /I I 111llf II M I •Oto° ' P.'•.. 0.05-[ -
C 144Onize
de asignación del taller ' Aliirnize
Fix-It. "•--. Awgnrnent,
Fix-119)ap Solution
Optima' cost = Project 1 Project 2 I Projed 3
S25
Adams 11 14 Assign 6
Brown 8 Assign 10 11
Cooper Assign 9 12 7

—.