FACULTAD DE CIENCIAS EMPRESARIALES Y ECONÓMICAS
CARRERA DE ADMINISTRACIÓN
Programación Lineal - Problemas
de transporte y asignación
AUTORES:
GUTIERREZ/VILLAVERDE/HERBERTH EDUARDO
LINARES/BARBERO/MANUELA
MACHUCA/DE PINA/JUAN MANUEL
REYES/JUSCAMAITA/DANIEL RAFAEL
MODELOS PARA LA TOMA DE DECISIONES
El problema de Transporte
• El problema de transporte trata de la distribución de bienes de varios
puntos de oferta (orígenes) hacia varios puntos de demanda
(destinos).
• Generalmente se proporciona la capacidad de bienes en cada origen
y los requerimientos en cada destino.
• Típicamente el objetivo es la minimización de los costos totales de
transporte y producción.
• El problema de asignación es un caso especial del problema de
transporte, en el que las cargas de los orígenes a los destinos son
unitarias.
Ejemplo problema
transporte
• Problema de transporte en forma de red.
Fábricas Almacenes
(orígenes) (Destinos)
100 Unidades Lima Callao 300 Unidades
300 Unidades San Borja San Miguel 200 Unidades
300 Unidades Santa Anita Jesus Maria 200 Unidades
Capacidade Rutas de despacho Requerimientos
s
Casos
•Especiales
Suministro total no igual a la demanda total. Uso de origen ficticio con
variables de escape.
• Maximización de la función objetivo.
• Capacidades de ruta o mínimos de ruta.
• Rutas inaceptables.
Otras
variantes
•Problemas de Trasbordo: son problemas de transporte en los que
se agregan puntos de trasbordo. Los puntos de trasbordo son puntos
que pueden tanto recibir mercadería de otros puntos como enviar
mercadería a otros puntos.
•Problemas de Asignación: son problemas balanceados de
transporte en los cuales todas las ofertas y todas las demandas son
iguales a 1.
Problema de Trasbordo
• Se reconoce mediante el uso de nodos intermedios o transitorios para
el envío de recursos entre las distintas fuentes (oferta) y destinos
(demanda)
• Se construye una red con orientación desde las fuentes (nodos de
inicio) hacia los destinos (nodos de llegada), utilizando
amortiguadores (nodos transitorios) que permiten recibir y transferir
recursos. Las flechas que unen los nodos de la red representan los
eventuales flujos de recursos en la secuencia de distribución
Esquema de Trasbordo
• Un esquema simple del modelo de transbordo se expresa
como una red de modelo de asignación:
F1
A1 D1
F2
A2 D2
F3
Nodos puros Nodos de Nodos puros
de Oferta Transbord de
o Demanda
Ejemplo de Trasbordo
• Dos fábricas de automóviles, P1 y P2, están conectadas a tres
distribuidores, D1, D2 y D3, por medio de dos centros de tránsito,
T1 y T2, de acuerdo con la red que se muestra en la siguiente
diapositiva
• Las cantidades de la oferta en las fábricas P1 y P2, son de 1000 y
1200 automóviles, y las cantidades de la demanda en las
distribuidoras D1, D2 y D3, son de 800, 900 y 500 automóviles. El
costo de envío por automóvil (en cientos de US$) entre los pares
de nodos, se muestra en los arcos de conexión de la red
Red de
asignación
D1 800
8
1000 3
P1 T1 6 5
4
2 4 D2 900
5
1200 P2 T2 9 3
D3 500
Problema PL
• Red para plantear el PL:
D1 800
XP1T1
1000
XD1D
P1 T1
D2 900
XP2T2
1200 P2
XD2D
T2
D3 500
Formulació
n
FO Mín Z =
3XP1T1 + 4XP1T2 + 2XP2T1 + 5XP2T2 + 8XT1D1
+ 6XT1D2 + 4XT2D2 + 9XT2D3 + 5XD1D2 +
3XD2D3
s.a. : 1000 = XP1T1 + XP1T2
1200 = XP2T1 + XP2T2
XP1T1 + XP2T1 = XT1D1 + XT1D2
XP1T2 + XP2T2 = XT2D2 + XT2D3
XT1D1 = XD1D2 + 800
XT1D2 + XT2D2 + X
XD1D2> 0= XD2D3 + 900
ij
XT2D3 + XD2D3 = 500
Problema de
asignación
• El problema de asignación se refiere a una clase de problemas que
involucran la determinación de la forma más eficiente de asignar
recursos a tareas.
• Frecuentemente el objetivo es minimizar los costos totales o costos
totales de ejecutar las tareas requeridas.
• Un problema importante de asignación consiste en asignar un
trabajador o una tarea a un proyecto o una máquina.
Problema de asignación: Sastrería
Pérez
Juan Pérez tiene cinco sastres libres y cuatro trajes para hacer. El tiempo estimado
(en horas) que tomaría a cada sastre para hacer cada terno se muestra en el cuadro.
(Una 'X' indica que el trabajo no puede ser asignado a ese sastre)
Sastre
Terno 1 2 3 4 5
Terno de Novio 19 23 20 21 18
Traje de Payaso 11 14 X 12 10
Uniforme de Marino 12 8 11 X 9
Traje de Torero X 20 20 18 21
Formular un PL para determinar la asignación sastre-traje que minimice el
tiempo total estimado en hacer los cuatros trajes.
Ejemplo: Sastrería
Pérez
• Definición de las variables de decisión.
= 1 si el traje es asignado al sastre j
xij
= 0 de otra manera.
Numero de variables de decisión =
[(numero de trajes)(numero de sastres)]
- (numero de asignaciones no
posibles)
= [4(5)] - 3 = 17
Ejemplo: Sastrería
Pérez
• Definición de la función objetivo
Minimizar el tiempo total usado en hacer los ternos:
Min Z= 19x11 + 23x12 + 20x13 + 21x14 + 18x15 +
11x21
+ 14x22 + 12x24 + 10x25 + 12x31 + 8x32
+ 11x33
+ 9x35 + 20x42 + 20x43 + 18x44 + 21x45
Ejemplo: Sastrería
Pérez
• Definición de las restricciones
Exactamente un sastre por traje:
1) x11 + x12 + x13 + x14 +
x15 = 1
2) x21 + x22 + x24 + x25 =
1
3) x31 + x32 + x33 + x35 =
1
4) x42 + x43 + x44 + x45 =
1
Ejemplo: Sastrería
Pérez
• Definición de restricciones (continuación)
No mas que un traje por sastre:
5) x11 + x21 + x31 < 1
6) x12 + x22 + x32 + x42 < 1
7) x13 + x33 + x43 < 1
8) x14 + x24 + x44 < 1
9) x15 + x25 + x35 + x45 < 1
> 0 para i = 1, . . ,4 y j = 1, . . ,5
xij
