TRANSPORTE Y

ASIGNACION

INTRODUCCIÓN

La programación lineal es un caballo de batalla en el mundo de los modelos cuantitativos. Su capacidad

para manejar cientos de miles de variables de decisión y restricciones, y la enorme cantidad de
interacciones que implican estos números hacen que la PL sea una herramienta importante para la
resolución de gran variedad de problemas.

En este capítulo nos concentramos en algunas aplicaciones de la programación lineal. En particular

consideramos dos modelos específicos. El primero es el modelo de transporte, con este modelo la
gerencia se propone determinar la manera de asignar el menor costo de transportación posible. Este
modelo es importante porque tiene muchas aplicaciones exitosas y porque puede resolverse con rapidez
y eficiencia.

Luego tenemos los modelos de asignación, este modelo permite determinar la asignación óptima de los
agentes de ventas a los territorios, de los puestos de trabajo a las máquinas o de los editores a los libros
en producción. El modelo mismo constituye un tipo especial de modelo de transporte.

MODELOS DE TRANSPORTE

El modelo de transporte es una clase especial de problema de programación lineal. Trata la situación en
la cual se envía un bien de los puntos de origen (por ejemplo, fábricas, almacenes y otros), a los puntos
de destinos (por ejemplo bodegas, puntos de expendio, etc.). El objetivo es determinar las cantidades
enviadas desde cada punto de origen hasta cada punto de destino, que minimicen el costo total del envío,
al mismo tiempo que satisfagan tanto los límites de la oferta como los requerimientos de la demanda. El
modelo supone que el costo de envío en una ruta determina es directamente proporcional al número de
unidades enviadas en esa ruta. En general, el modelo del transporte se puede ampliar a otras áreas,
además del transporte directo de un bien, incluyendo, entre otras, control de inventarios, horarios de
empleo y asignación de personal.

El problema general está representado en la red en la Fig 1. Hay m puntos de origen y n puntos de
destino, cada uno representado por un nodo. Los arcos (representados en esta figura por flechas) que
unen los puntos de origen con los puntos de destino representan las rutas entre los puntos de origen y de
destino. El arco (i,j) que une el punto de origen i con el punto de destino j, incluye dos fragmentos de
información: (1) el costo de transporte por unidad, Cij, y (2) la cantidad enviada, Xij. La cantidad de la
oferta en el punto de origen i es ai y la cantidad de la demanda en el punto de destino j es bj. El objetivo
del modelo es determinar las Xij desconocidas que minimizarán el costo total del transporte, mientras
satisfacen todas las restricciones de la oferta y de la demanda.

Fig 1: Representación del modelo de transporte

Recuerda que:

La meta de un modelo de transporte es minimizar el costo total de envío de un producto (o

producto) desde los puntos de existencia hasta los puntos de demanda bajo las siguientes
restricciones:
1. Cada punto de demanda recibe su requerimiento.
2. Los embarques desde un punto de suministro (existencia) no exceden su capacidad
disponible.

Existen los siguientes métodos de resolución:

 Método de la esquina Noroeste
 Método de Aproximación de Vogel
 Método de Pasos Secuenciales
 Método de Distribución Modificada

Los dos primeros métodos dan una solución factible, y a partir de esta solución factible, aplicando sobre
ella cualquiera de los otros dos métodos, obtenemos la solución óptima.

PROBLEMA DE ASIGNACION

“La mejor persona para el trabajo” es una descripción apropiada de los que trata de lograr el modelo de
asignación. La situación se ilustra con la asignación de trabajadores a los empleos donde cualquier
empleado puede desempeñar cualquier trabajo, aun cuando con diversos grados de habilidad. Un empleo
que es igual a la habilidad de un trabajador cuesta menos que uno en el cual el operador no es hábil. El
objetivo es determinar la asignación óptima (la menos costosa) de trabajadores a puestos.

.
En la Fig 2 se representa el modelo general de asignación con n trabajadores y n trabajos:

Fig 2: Representación del modelo de asignación

El elemento Cij representa al costo de asignar al empleado i al trabajo j (i,j = 1, 2, …, n). No hay pérdida
en la generalidad al suponer que el número de trabajadores siempre es igual al número de empleos,
porque siempre podemos añadir trabajadores ficticios o empleos ficticios para efectuar este resultado.

El modelo de asignación en realidad es un caso especial del modelo de transporte, en el cual los
trabajadores representan los puntos de origen y los empleos representan los puntos de destino. La
cantidad de oferta en cada punto de origen y la cantidad de la demanda en cada punto de destino son
exactamente iguales a 1. El costo de “transportar” al trabajador i al empleo j es Cij. En efecto, el modelo
de asignación se puede resolver directamente como un modelo regular de transporte. Sin embargo, el
hecho de que todas las cantidades de la oferta y la demanda igualan a 1 ha llevado al desarrollo de un
algoritmo de solución simple, llamado el método húngaro. Aunque el nuevo método parece estar
totalmente no relacionado con el modelo de transporte, en realidad el algoritmo está arraigado en el
método simplex, igual que el modelo de transporte.

PROBLEMAS PARA RESOLVER:

Problema Nº 1. La Empresa “Estrella del Oriente” tiene cuatro plantas ensambladoras en Europa; están
ubicados en las ciudades 1, 2 , 3 y 4. Las máquinas que se ensamblan en estas plantas utilizan motores
diesel tipo ET-6 fabricados en Estados Unidos, los cuales llegan a tres puertos, denominados A, B y C.
Los planes de producción del tercer trimestre ya han sido formulados. Los requerimientos, o sea la
demanda en destinos, de motores diesel ET-6 son las siguientes:
Cuadro: Demanda de motores diesel ET-6
Planta Cantidad de motores
1 400
2 900
3 200
4 500
La cantidad disponible de motores diesel tipo ET-6 en los puertos a tiempo para usarse en el tercer
trimestre se muestran a continuación:

.
 Cuadro: Disponibilidad de motores diesel ET-6
Puerto Cantidad de motores
A 500
B 700
C 800
Determinar cuántos motores se deben enviar de cada puerto a cada planta, siendo que los motores se
envían a través de los transportes comunes y se paga un cargo por motor, siendo los costos pertinentes:
Cuadro: Costo unitario de transporte
Del Puerto ..... a la Planta 1 Planta 2 Planta 3 Planta 4
A $12 $13 $4 $6
B $6 $4 $10 $11
C $10 $9 $12 $4

Problema Nº 2. La Johnson Electric produce motores eléctricos pequeños para cuatro fabricantes de
instrumentos, en cada una de sus plantas. Los costos de producción por unidad varían según las
ubicaciones debido a diferencias en el equipo de producción y en el rendimiento de los obreros. Los
costos de producción por unidad y la capacidad mensual (oferta) se presentan a continuación:
Cuadro: Datos de las plantas
Planta Costo unitario ($) Capacidad mensual
A $17 800
B 20 600
C 24 700
Los pedidos de clientes (en unidades) que deben producirse el siguiente mes es:
Cuadro: Demanda de motores (unidades)
Cliente Demanda Cliente Demanda
1 300 3 400
2 500 4 600
Cuadro: Costo de transporte por unidad
Desde \ A 1 2 3 4
A $3 $2 $5 $7
B 6 4 8 3
C 9 1 5 4
Indique cuántas unidades debe producir y enviar Jhonson Electric a las fábricas de instrumentos.

Problema Nº 3. Una tienda de departamento quiere comprar las siguientes cantidades de vestidos
de mujer:
Tipo de vestido A B C
Cantidad 60 25 30
Tres diferentes fabricantes someten propuestas para proveer no más de las cantidades que aparecen a
continuación (todos los tipos de vestidos combinados)
Fabricante X Y Z
Cantidad 100 15 40

.
La tienda estima que los costos unitarios de cada prenda son:
Fábrica ! Vestidos A B C
X $11 $14 $17
Y $12 $13 $18
Z $10 $14 $19
Determinar el plan de adquisiciones más ventajosa para la tienda

Problema Nº 4. Minimice el siguiente problema de transporte:

Cuadro: Oferta Cuadro: Demanda Cuadro: Costo de transporte
unitario
Origen Oferta Destinos Demanda De A A A A
(unidades) (unidades) Nro. 1 Nro. 2 Nro. 3 Nro. 4
A 70 Nro. 1 55 A $ 19 $ 23 $ 25 $ 17
B 80 Nro. 2 75 B $ 21 $ 26 $ 18 $ 23
C 30 Nro. 3 45 C $ 20 $ 22 $ 21 $ 24
D 20 Nro. 4 25 D $ 25 $ 24 $ 23 $ 21
¿Cuánto deberá asignarse a cada destino?

Problema Nº 5. Un sistema de distribución semanal, de una empresa, para un producto tiene las
siguientes características (en unidades):

Planta Capacidad Centro Demanda

semanal distribuidor semanal
Cotoca 75 Mutualista 50
Warnes 100 Ramada 50
Abasto 100

La siguiente tabla da las pérdidas estimadas, por centro de distribución, por quedarse corto en los envíos.
Además se tiene los costos unitarios de transporte de las plantas a los centros distribuidores.

Centro de Pérdida Costo de transporte ($/unidad)

distribución ($/unidad) Desde Hacia
Mutualista 2 Mutualista Ramada Abasto
Ramada 3 Cotoca 3 2 1
Abasto 2 Warnes 4 5 6

Determinar un plan de envío óptimo de las plantas a los centros de distribución.

Problema Nº 6. La empresa Rayo de Luz tiene pedidos para tres productos similares:
Producto Pedidos (unidades)
A 2000
B 500
C 1200
Existen disponibles tres máquinas para las operaciones de manufactura. Las tres pueden fabricar todos
los productos con la misma tasa de producción. Sin embargo, debido a diferencias en los porcentajes de

.
defectos de cada producto en cada máquina, los costos unitarios de los productos varían dependiendo de
la máquina que se utiliza. Las capacidades de las máquinas para la siguiente semana, y los costos
unitarios, son los siguientes:
Máquina Capacidades (unidades)
I 1500
II 1500
III 1000

Producto
A B C
I $ 1.00 $ 1.20 $ 0.90
Máquina II $ 1.30 $ 1.40 $ 1.20
III $ 1.10 $ 1.00 $ 1.20
Utilice el modelo de transporte para desarrollar un programa de producción de costos mínimos para los
productos y las máquinas.

Problema Nº 7. Aplíquese el método de asignación para minimizar el siguiente problema:

W X Y Z
A 15 18 16 10
B 14 17 17 8
C 15 19 23 17
D 20 14 16 17
¿Cuál es el costo de la solución óptima?

Problema Nº 8. La Compañía B&R, con oficinas centrales en Santa Cruz, desea asignar a tres recién
graduados de universidad que acaba de contratar: Juan, Saúl y Víctor a sus oficinas regionales. Pero la
empresa también está abriendo una oficina en Warnes y quiere enviar ahí a alguno de los tres si resulta
más económico que moverlos a Cotoca, La Guardia o Montero. Costará $1000 asignar a José en
Warnes, $800 asignar a Saúl también en Warnes, y $1500 mover a Víctor.
Los costos de enviar a los graduados a las oficinas son:

Persona Of. Cotoca Of. La Guardia Of. Montero

José $ 800 $ 1100 $ 1200
Saúl $ 500 $ 1600 $ 1300
Victor $ 500 $ 1000 $ 2300
¿Cuál es la asignación óptima de su personal a las oficinas?

Problema Nº 9. Sam tiene cuatro fosas de reparaciones en su taller de mantenimiento y tres trabajos
para asignárselos. Debido a diferencias en el equipo disponible, la gente asignada a cada fosa y las
características del trabajo, cada uno de éstos requiere diferente cantidad de tiempo en cada fosa. En el
siguiente cuadro se da los tiempos estimados para cada trabajo en cada fosa. San quiere minimizar el
tiempo total requerido. Use el método húngaro para obtener la solución óptima de este problema. ¿Hay
soluciones óptimas alternativas?

Fosa \ Trabajo 1 2 3
A 24 45 25
B 33 48 23

.
 C 24 52 20
D 30 56 21

Problema Nº 10. Un corredor de bienes raíces planea la venta de cuatro lotes de terreno y ha recibido
ofertas individuales de cuatro clientes. Debido a la cantidad de capital que se requiere, estas ofertas se
han hecho en el entendimiento de que ninguno de los cuatro clientes comprará más de un lote. Las
ofertas se muestran en el siguiente cuadro (en $*1000):

Comprador \ Lote 1 2 3 4 5
A 16 15 25 19 20
B 19 17 24 15 25
C 15 15 18 - 16
D 19 - 15 17 18

El corredor de bienes raíces quiere maximizar su ingreso total a partir de esas ofertas, ¿cómo deberá
realizar las ventas?

Problema Nº 11. La cadena “El Pollo Gordo” tiene tres restaurantes en el país, los cuales usan vasos
desechables estándares. Se ha invitado a tres proveedores para competir por la concesión de surtir estos
vasos. Sus propuestas son:

Proveedor Precio Capacidad mes

(por cada 1000) (unidades)
A $ 0.90 30000
B $ 1.00 75000
C $ 1.10 135000
El costo de transporte (en dólares/1000 vasos) varía desde cada proveedor a cada restaurante.
Al restaurante
De Nro. 1 Nro. 2 Nro. 3
A $ 0.80 $ 0.10 $ 0.30
B $ 0.50 $ 0.20 $ 0.50
C $ 0.20 $ 0.40 $ 0.20

Las necesidades mensuales de vasos para los tres restaurantes son 40000, 60000 y 120000,
respectivamente.
¿Cuántos vasos deben comprarse de cada proveedor para cada restaurante?

Problema Nº 12. Los cuatro hijos de Mario Saucedo, Mauricio, Karen, Sergio y Verónica, quieren
ganar algún dinero para cubrir sus gastos personales durante un viaje organizado por la escuela al
zoológico local. El señor Saucedo eligió cuatro tareas para sus hijos: podar el césped, pintar la cochera,
lavar el automóvil de la familia y preparar un resumen de un documental. Para evitar las competencias
anticipadas entre hermanos, les pidió que presentaran licitaciones (secretas) para lo que ellos creían que
era un pago justo para cada una de las cuatro tareas. Quedaba entendido que los cuatro hijos aceptarían
la decisión de su padre en lo concerniente a quién desempeñaría cada tarea. La tabla siguiente resume
las licitaciones recibidas.

Podar Pintar Lavar Resumir

Mauricio $15 $10 $8 $9

.
 Karen $10 $16 $7 $10
Sergio $16 $13 $10 $16
Verónica $13 $15 $8 $12

Basándose en esta información, ¿cómo debe asignar las tareas el señor Saucedo?

Problema Nº 13. Una determinada empresa se desenvuelve en el negocio de reparación máquinas

lavadoras y secadoras domésticas. La compañía da servicio a clientes en toda la ciudad. Tiene cinco
empleados de servicio que viven en diferentes lugares de la ciudad. Con el objeto de ahorrar tiempo de
manejo y costos al inicio de cada día, el personal de servicio se dirige directamente de sus casas a los
lugares donde se les requiere. La tabla presenta las distancias asociadas con los primeros cinco trabajos
que deben llevarse a cabo. A cada empleado de servicio se le paga por conducir; por ello, la empresa
desea minimizar la distancia extra de traslado.
Empleado de Número de trabajo
servicio 1 2 3 4 5
1 20 14 6 10 22
2 16 8 22 20 10
3 8 6 24 14 12
4 20 22 2 8 6
5 4 16 22 6 24
¿Cuál será la asignación óptima de tal forma de minimizar los costos de transporte de los empleados?

.
 SUPLEMENTO 4
USO DEL OPTIMIZADOR INVOP

Para los problemas de transporte y de asignación se utilizan optimizadores, entre los varios que existen
en el mercado esta el INVOP.

Problema Nº 1. Problema de transporte: Sea el Problema Nro. 1 de Transporte (Pag. 61):

.
Sergún la resolución del programa INVOP, la solución óptima está dada de la siguiente forma:

De Puerto A Planta
Cantidad de Costo Importe
motores unitario
A 1 300 $ 12 $ 3600
A 3 200 $4 $ 800
B 2 700 $4 $ 2800
C 1 100 $ 10 $ 1000
C 2 200 $9 $ 1800
C 4 500 $4 $ 2000
COSTO TOTAL DE TRANSPORTE $ 12000

El costo total de enviar los motores desde los puertos hasta las plantas es de $12000.

.
Problema Nº 2. Problema de transporte: Sea el Problema Nro. 2 de Transporte

Obsérvese que el programa aumentó una columna ficticia (Dest 5), este aumento se realiza para poder
igualar la oferta y la demanda, condición necesaria para poder plantear la solución.
La solución óptima está dada de la siguiente forma:

De Planta A Cliente Cantidad de Costo Importe

motores eléctricos unitario
A 1 300 $ 20 $ 6000
A 2 100 $ 19 $ 1900
A 3 400 $ 22 $ 8800
B 4 600 $ 23 $ 13800
C 2 400 $ 25 $ 10000
COSTO TOTAL DE TRANSPORTE $ 40500

El costo total de fabricar y enviar los motores eléctricos desde las plantas hasta los clientes es de
$40500. Debe hacerse notar que las plantas A y B trabajarán a toda capacidad y la planta C sólo
fabricará 400 motores eléctricos, cantidades que cubren la demanda de los clientes.

.
Problema Nº 6. Problema de asignación: Sea el Problema Nro. 7 de Asignación (Pag. 62):

La solución óptima está dada de la siguiente forma:

Enviar A Importe
A Y $ 16
B Z $ 8
C W $ 15
D X $ 14
COSTO TOTAL DE ASIGNACION $ 53

El costo total de asignar orígenes a destinos es de $53.