MODELOS DE REDES
Se utilizan para resolver problemas de
Asignacion de recursos
Programación de horarios
Problemas de transporte
Programación de la producción
PROBLEMA DE TRANSBORDO
Una compañía puede fabricar un producto en dos líneas de producción diferentes. Cada línea envía lo
producido al centro de calidad A o B según convenga. Finalmente desde control de calidad se remite a
cualquiera de las cuatro líneas de empaque de la empresa. La línea de producción uno tiene una
capacidad de producción de 80 unidades por hora y la línea dos puede producir un máximo de 60
unidades por hora. Las líneas de empaque atienden los siguientes volúmenes por hora
Línea de empaque uno 30
Línea de empaque dos 20
Línea de empaque tres 40
Línea de empaque cuatro 40
La tabla muestra los tiempos en minutos que se requieren para los distintos traslados entre los variados
procesos por cada unidad de producto
Producción Numero de
empaque
P1 P2 Control de L1 L2 L3 L4
calidad
10 12 C1 24 22
9 11 C2 14 23 20 23
Adicionalmente se conoce que el centro de calidad uno se demora 4 min para revisar un articulo,
mientras que calidad dos tarda 6 min, como debe organizarse el flujo de materiales de manera que se
minimice el tiempo total incurrido de producción.
Variables
Xij=cantidad de unidades a enviar del nodo i a nodo j
I= 1,2,3,4 j= 3,4,5,6,7,8
FO= minimizar tiempos de traslado
Min Z= 10 min (13unidades) + 9x14+ 12x23+11x24+24x35+22x37+19x45+23x46+20x42+23x45
Restricciones de capacidad de producción
Línea de producción uno= x15 + x14 menor o igual a 80
Línea de producción dos= x23 + x24 menor o igual a 60
Restricciones de trasbordo
Control de calidad uno x13 + x23 = x35 + x37
X14 + x24 + = x45 + x46 + x47 + x48
Restricción de demanda
Línea de empaque uno = X35 + x45 mayor o igual a 30
Línea de empaque dos= X46 mayor o igual a 20
Línea de empaque tres= X37 + x47 mayor o igual a 40
Línea de producción cuatro= X48 mayor o igual a 40
PROBLEMÁTICA DE ASIGNACION DE RECURSOS No. 1
Es un caso especial del problema de transporte. El problema consiste en optimizar recursos por
asignación de personal, ocurre cuando se necesitan asignar desde “m” centros una oferta de una unidad
hacia “n” destinos y este requiere de una unidad. Es decir, la oferta y la demanda sea igual a 1.
Suponer que una compañía tiene 3 empleados que pueden ser asignados a 3 solicitudes de reparación
distintas. Las ordenes de reparación implican que los empleados viajen directamente hasta el domicilio
del cliente. La empresa cubre los gastos de combustible del vehiculo de los operarios y desea minimizar
este gasto al máximo.
L tabla muestra la distancia en km desde el lugar donde se localiza el empleado hasta el domicilio del
cliente
cliente
Empleado 1 2 3
1 10 22 14
2 20 10 8
3 14 12 6
0 No se asigna al empleado “i” para atender al cliente “j”
Xij=
1 si se asigna al empleado “i” para atender al cliente “j”
i = [1,2,3] empleados
j = [1,2,3] clientes
Función objetivo: minimizar distancias
Min z= 10x11+22x12+14x13+20x21+10x22+8x23+14x31+12x32+6x33
Empleado 1 Empleado 2 Empleado 3
Restricción de oferta:
Empleado 1: X11+x12+x13=1
Empleado 2: X21+x22+x23=1
Empleado 3: X31+x32+x33=1
Restricción de demanda:
Cliente 1: X11+x21+x31=1
Cliente 2: X12+x22+x32=1
Cliente 3: X13+x23+x33=1
FO: 26 km
X11= 1
X12=1
X33=1
Un hospital debe de programar la asignacion de enfermeras con la atención de clientes. Suponer que el
horario de trabajo de una enfermera es de 8 horas continuas y que cada una puede comenzar a trabajar
al inicio de los primeros 5 turnos.
Periodo Turno del dia Numero requerido de
enfermeras
1 8:00 – 10:00 10
2 10:00 – 12:00 8
3 12:00 – 2:00 9
4 14:00 – 16:00 11
5 16:00 – 18:00 13
6 18:00 – 20:00 8
7 20:00 – 22:00 5
8 22:00 – 24:00 3
Xi = capacidad de enfermeras a asignar para cambiar el periodo i
i = [1,2,3,4,5,6,7,8]
min z= Exi
min= x1+x2+x3+x4+x5+x6+x7+x8
Restricciones
8 10 12 14 16 18 20 22 24
10 8 9 11 13 8 5 3
x1>=10
x1+x2>=8
x1+x2+x3>=9
x1+x2+X3+x4>=11
x2+x3+x4+x5>=13
x3+x4+x5>=8
x4+x5>=5
x5>=3
FO: 23 enfermeras
X1=10
X4=1
X5=12
Un restaurante opera los 7 dias de la semana, los meseros son contratados para trabajar 6 horas diarias.
Los contratos especifican que cada mesero debe trabajar 5 dias consecutivos y descansar 2. Cada
mesero recibe el mismo salario semanalmente. Los requerimientos del personal se muestran en la
siguiente tabla:
DIAS REQUERIMIENTO MINIMO DEL PERSONAL
(hrs)
Lunes 150
Martes 200
Miercoles 400
Jueves 300
Viernes 700
Sábado 800
Domingo 300
MODELO DE RED POR LA RUTA MAS CORTA
El problema consiste en encontrar la ruta más económica o con la mínima distancia. La variable es
binaria y se tiene un origen y un destino. Las trayectorias pueden ser en una sola dirección o
bidireccionales.
17
7
2
15 6 5 6
8 4
6
1 4 2
10
3 5
4
0 No sigue la trayectoria de nodo “i” al nodo “j”
Xij
1 Si sigue la trayectoria de nodo “i” al nodo “j”
I = 1,2,3,4,5,6 origen
J= 2,3,4,5,6,7 destino
Función objetivo: minimizar distancia de nodos
Min15x12+10x13+8x32+4x35+6x24+17x27+2x56+6x67+4x45+5x47
Restricción para el nodo origen: Nodo origen 1
X12+x13=1
Restricción para el nodo destino: Nodo destino 7
X27+x47+x67=1
Restricción para nodos intermedios
nodo 2: X12+x32=X24+x27
Entra sale
X12+x32-x24-x27=0
Nodo 3: X13=x32+x35
X13-x32-x35=0
Nodo 4: x24=x47+x45
X24-x47-x46=0
Nodo 5: x35+x45=x56
X35+x45-x56=0
Nodo 6: x56-x67=0
Fo: 22
X13 1.000000
X35 1.000000
X56 1.000000
X67 1.000000
MODELO DE REDES PARA EL PROBLEMA DE FLUJO MAXIMO
Se utiliza para redes en donde los arcos tienen capacidad de flujo (kij). El objetivo es maximizar el flujo
entre los nodos y encontrar la trayectoria que asegure el flujo máximo.
8 0
2 4
0 6 3 7
1 0
10 0 3 0 F
6 7
2
1
10 4 2 0
1 4 2
0 3 12 0 5 8
Función objetivo: maximizar el flujo
Max10x12+0x21+10x13+0x31+8x24+0x24+0x42+6x26+0x62+1x23+1x32+4x36+4x63+2x65+2x56+3x64+3
x46+2x67+0x76+7x47+0x74+8x57+0x75+12x35+0x53
Restricciones
Nodo origen uno: F=X12+X13
F-X13-X13=0
Nodo destino siete: x47+x37+x67=f
X47+x57+x67-f=0
Nodos intermedios
Nodo dos: x12+x32=x23+x24+x26
X12+x32-x23-x24-x26=0
Nodo tres: x13+x23+x63=x32+x36+x35
X13+x23+x63-x32-x36-x35=0
Nodo cuatro: x24+X64=x46+x47
X24+x64-x46-x47=0
Nodo 5: x65+x35=x52+x56
X65+x35-x57-x56=0
Nodo 6: x26+x36+x56+x46=x63+x65+x67+x64
X26+x36+x56+x46-x63-x65-x67-x64=0
Restricciones de capacidad de flujo
X12<=10 nodo 1
X13<=10
X23<=1
X26<=6 nodo 2
X24<8
X32<=1
X36<=4 nodo 3
X35<=12
X46<=3 nodo 4
X47<=7
X57<=8 nodo 5
X56<=2
X64<=3
X63<=4
X65<=2 nodo 6
X67<=2
PROBLEMA DE COSTO MINIMO
Al igual que el problema de flujo máximo presenta capacidades de flujo entre cada arco, y al igual que el
problema de transporte puede presentar multiples orígenes con multiples destinos.
El problema consiste en minimizar el costo total sujeto a la disponibilidad y la demanda de algunos
nodos, considerando las capacidades de flujo para cada arco.
2,4
2 4 (5)
4,15
6,10
2,4 2,4
(20) 2,15
4,8 3,5 (15)
3 5
1,4
[Costo, capacidad de flujo]
0 no sigue la trayectoria de origen “i” al destino “j”
Xij
1 Si sigue la trayectoria de origen “i” al destino “j”
i: 1,2,3,4,5
j:2,3,4,5
Función objetivo: minimizar el costo total
Min 4x12+4x13+2x23+1x34+6x25+2x24+3x35+1x53+2x45
Restricciones de origen:
Nodo uno: 20=x1+x13
20-x12-x13=0
Restricción nodo destino:
Nodo cuatro: X24+x34=5+x45
X24+x34-x45-5=0
Nodo cinco: x25+x35+x45=15+x53
X25+x35+x45-x53-15=0
Nodos intermedios
Nodo dos:x12=x23+x24+x25
X12-x23-x24-x25=0
Nodo tres: x13+x23+x53=x34+x35
X13+x23+x53-x34-x35=0
X12<=15
X13<=8
X24<=4
X25<=10
X34<=15
X35<=5
X53<=4
PROBLEMAS DE REDES PARA EL PROBLEMA DE LA RUTA CRÍTICA APLICADO EN LA PLANIFICACION DE
PROYECTOS
12
3 8 5 6
10
0 7
1
2 4
Función objetivo
Min x13+9x12+7x34+8x35+10x45+12x56
Restriccion nodo uno
X12+x13=1
Restricción nodo destino x56=1
Nodos intermedios
PROBLEMA DE TRANSPORTE PARA EQUILIBRIO DE CARGA
Se utiliza para modelos en donde se debe de equilibrar la carga en un contenedor debido a restricciones
de peso y espacio y en donde se debe de equilibrar la carga para evitar accidentes durante el traslado.
Una empresa que se dedica a transporte aéreo de mercancías cuenta con un avión que tiene tres
compartimientos: frontal, central y trasero. Por motivos técnicos se debe tener una proporción similar
entre el peso ocupado con respecto a su capacidad en cada compartimiento. Las capacidades de peso y
espacio (volumen) se muestran en la siguiente tabla:
Bodega/compartimiento Peso (toneladas) Volumen (m3)
Frontal 5 1000
Central 15 9000
Trasero 8 6000
La empresa quiere transportar la mercancía de cuatro clientes pudiendo aceptar cualquier fracción de
los cuatro pedidos. La siguiente tabla muestra la información relacionada con el peso, volumen y utilidad
de las mercancías:
Cliente Peso (tonelada) Volumen (m3) Utilidad
($/tonelada)
1 10 1000 250000
2 12 3000 400000
3 8 2400 300000
4 14 7000 500000
Xij: cantidad en toneladas a transportar del cliente “i” en el compartimiento “j”
I: cliente 1,2,3,4
J: compartimiento 1 frontal ,2 central ,3 trasero
Función objetivo: maximizar la utilidad
Cliente uno: Max250000x11+250000x12+250000x13+
Cliente dos: Max40000x21+400000x22+400000x23+
Cliente tres: Max300000x31+300000x32+300000x33+
Cliente cuatro: Max500000x41+500000x42+500000x43
Restricciones de peso (compartimiento)
Frontal (j=1)
X11+x21+x31+x41<=5
X12+x22+x32+x42<=15
X13+x23+x33+x43<=8
Restricciones de volumen (compartimiento)
Cliente Vol/peso (m3/ton)
1 100 m3/ton
2 250 m3/ton
3 300 m3/ton
4 500 m3/ton
Frontal: 100X11+250x21+300x31+500x41<=1000m3
Central: 100X12+250x22+300x32+500x42<=9000
Trasero: 100X13+250x23+300x33+500x43<=6000
Restricciones de capacidad de carga por cliente “i”
Cliente uno: x11+x12+x13<=10
Cliente dos: x21+x22+x23<=12
Cliente tres: x31+x32+x33<=8
Cliente cuatro: x41+x42+x43<=14
Restricciones de balance para la proporción de uso de la capacidad de peso en cada compartimiento
Frontal (5ton) Central (15
Trasero (8ton)
ton)
F=C
X11+x21+x31+x41 = x12+x22+x32+x42
5 15
3X11+3x21+3x31+3x41-x12-x22-x32-x42=0
C=T
X12+x22+x32+x42 = x13+x23+x33+x43
15 8
0.53x12+0.53x22+0.53x32+0.53x42-x13-x23-x33-x43=0
MODELO DE REDES PARA PROGRAMACION DE HORARIOS
Informacion requerida
1. Numero de identificacion unica del maestro “i”
2. Clave de la materia “j” que se desea impartir
3. Nivel de preferencia del maestro “i” para impartir la materia “j”
4. Clave del horario “k” en el cual se desea impartir
5. Nivel de preferencia del maestro “i” para impartir en el horario “k”
Información o datos de entrada
Aij: preferencia del maestro “i” por la entrada “j”
Bik: preferencia del maestro “i” por el horario “k”
Ck: disponibilidad de aulas en el horario “k”
Dj: demanda de grupos requeridos para la materia “j”
0 el maestro “i” no imparte la materia “j” en el horario “k”
Xijk=
1 el maestro “i” si imparte la materia “j” en el horario “k”
I= maestros (1-30)
J= materia (1-23)
K= horario (1-4)
Función objetivo:
Restricciones de disponibilidad de aulas por materia (Ck)
K= 8:00 pm – Ck-5
30 23
∑i+1 ∑j=1
X114+x124+x134+x144<=5
X214+x224+x234+x244<=5
Restricciones de demanda de grupos requeridos para la material “j”
J= io
Dj = 30
J=3 io
30
∑i=1 4∑k=4 >= Dj
X131+x132+x133+x134
Variables de desviación
Los valores de las variables de desviación corresponden a la incidencia de aquellos casos en los cuales no
va a ser posible coincidir con la preferencia de los maestros en cuanto a su materia, asi como la
preferencia por su horario.
