Formulacion de problemas

Vista previa del material en texto

Formulación de Problemas de de transporte, transbordo y asignación
INVESTIGACIÓN OPERATIVA I
Objetivos
Elaborar MPL aplicado a casos de transporte, transbordo y asignación
Caso 2. Una empresa de microbuses (CUSTERS) desea asignar para sus rutas desde tres ciudades a dos centros comerciales. La cantidad de micros que deben salir de las ciudades a los centros de abastos, es:
CIUDAD NUMERO DE
 MICROS
 CENTRO DEMANDA
 COMERCIAL
        
 1 	10
 2 	20
 3 	40
 25
 30
El costo de cada ruta es:
 
 C I U D A D 
 C.ABASTOS
 1 2 3
 1
 2
 24 21 37
 8 16 17
Determinar la cantidad de micros que debe surtir cada centro de distribución desde las ciudades, de tal forma que el costo total de transporte sea el menor posible.
SOLUCION
Relaciones entre almacén y centros de distribución:
A1
A2
A3
D1
D2
X11
X12
X21
X22
X31
X32
25
30
10
20
40
1.        VARIABLE DE DECISIÓN
Xij : Cantidad de micros asignados de la ciudad i al C. de abasto j
FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
D3
15
X13
X23
X33
 3.        RESTRICCIONES
      Del centro de oferta (Ciudad)
	X11 + X12 + X13 	= 10
	X21 + X22	 + X23 	= 20
	X31 + X32	 + X33 	= 40
      Del centro de demanda (Centro de abastos)
	X11 + X21 + X31	= 25
	X12 + X22 + X32 	= 30
	X13 + X23 + X33 	= 15
No Negatividad:
 				 
	Xij  0; i=1, 2 y 3; j= 1, 2 y 3
      Minimizar los costos de transporte:
 Min Z = 24 X11 + 8 X12 + 21 X21 + 16 X22 + 37 X31 + 17 X32
 2.       FUNCIÓN OBJETIVO
FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
sa.
	X11 + X12 + X13 	= 10
	X21 + X22 + X23 = 20
	X31 + X32 + X33 = 40
	X11 + X21 + X31	= 25
	X12 + X22 + X32 = 30
	X13 + X23 + X33 = 15
 	 Xij  0; i=1, 2 y 3; j= 1, 2 y 3
4. MODELO DE PROGRAMACIÓN LINEAL (MPL)
Min Z = 24 X11 + 8 X12 + 21 X21 + 16 X22 + 37 X31 + 17 X32
Transbordo.
El problema de trasbordo es una extensión del modelo de transporte, al cual se agregan nodos intermedios denominados nodos de trasbordo. A través de estos nodos intermedios existe la posibilidad de hacer envíos a los nodos de destino (demanda).
Definiremos los puntos de oferta como aquellos puntos desde donde sólo se puede despachar unidades.
Similarmente, un punto de demanda es un punto donde sólo se pueden recibir unidades. Un punto de transbordo es punto que puede recibir y enviar unidades a otros puntos.
Origen (n)
Destino (p)
Transbordo (m)
El MPL de Transbordo
Sea Xij=número de unidades enviadas desde el punto de oferta i al punto de demanda j usando nodos intermedios k. Con la oferta y la demanda equilibradas: 
	Min
	sa 
			 		 i=1,…,n
					k=1,…,m
			 		j=1,…,p
	
	fin
Caso 3. Enigma S.A. tiene plantas de producción en Lima y Tacna. Los productos fabricados en cualquiera de estas instalaciones pueden ser enviados a cualquiera de sus almacenes regionales en Ica y Arequipa. De los almacenes regionales, la empresa distribuye a detallistas al menudeo en Ayacucho, Huancayo, Cusco y Huánuco. En las siguientes tablas aparece el costo unitario de transporte de cada ruta de distribución.
	Planta	Almacén		Cantidad ofrecida
		Ica	Arequipa	
	Lima	2	3	600
	Tacna	3	1	400
	Almacén	Distribuidor al detalle			
		Ayacucho	Huancayo	Cusco	Huánuco
	Ica	2	6	3	6
	Arequipa	4	4	6	5
	Cantidad demandada	200	150	350	300
Elaborar la Red. Elaborar el MPL para determinar cuántos productos deben ser trasladados por cada ruta propuesta de tal manera que se cumpla con la cantidad demandada por cada distribuidor al menor costo posible. 
Caso 4. Una fábrica posee dos plantas de manufactura, una en Sta Anita y otra en El Callao. La planta de Sta Anita produce 150 unidades al día, la de El Callao 200 unidades al día. Los productos son enviados por avión a Tacna y Puno. 
En ambas ciudades, se requieren 130 unidades diarias. Existe una posibilidad de reducir costos enviando algunos productos en primer lugar a Arequipa o a Ayacucho y luego a sus destinos finales. 
		Hacia					
	Desde	Sta Anita	Callao	Arequipa	Ayacucho	Tacna	Puno
	Sta Anita	0	-	8	13	25	28
	Callao	-	0	15	12	26	25
	Arequipa	-	-	0	6	16	17
	Ayacucho	-	-	6	0	14	16
	Tacna	-	-	-	-	0	-
	Puno	-	-	-	-	-	0
La fábrica desea satisfacer la demanda minimizando el costo total de envío. En este problema, Sta Anita y Callao son puntos de oferta con 150 y 200 unidades respectivamente. Arequipa y Ayacucho son puntos de transbordo. Tacna y Puno son puntos de demanda de 130 unidades cada uno. 
Los costos unitarios de cada tramo factible se ilustran en la siguiente tabla:
Esquemáticamente, la situación es la siguiente:
¿Se tendría que modificar el esquema?
Elaborar el MPL
Sta Anita
Callao
Arequipa 
Ayacucho
 Tacna 
 Puno 
Asignación.
El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos destinados a la realización de tareas. Por ejemplo, los asignados pueden ser empleados a quienes se tiene que dar trabajo. La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no necesariamente tienen que ser personas. También, pueden ser maquinas, vehículos, plantas a los que se asignan tareas. 
Para que un problema se ajuste a la definición de problema de transporte se deben cumplir las siguientes suposiciones:
1) El número de asignados es igual al número de tareas. (este numero se denota por n).
2) Cada asignado se asigna a una tarea.
3) Cada tarea debe realizarla exactamente un asignado.
4) Existe un costo cij asociado con el asignado i ( i = 1,2...,n) que realiza la tarea j (j = 1,2...n).
5) El objetivo es determinar como deben hacerse las n asignaciones para minimizar los costos totales. 
Modelo del problema de asignación
El modelo matemático para el problema de asignación usa las variables de decisión: 
xij = 1, si el asignado i realiza la asignación j 
xij = 0, en caso contrario, 
Para i = 1,2..., n y j = 1,2...n. Entonces, cada xij es una variable binaria (toma valores 0 o 1). Estas variables representan decisiones de si o no: ¿Debe el asignado i realizar la tarea j?. Sea Z el costo total, el modelo del problema de asignación es:
Modelo del problema de asignación
Sujeto a:
	Observe que la estructura es similar al modelo de transporte. De hecho, el problema de asignación es solo un caso especial de los problemas de transporte, en donde los orígenes son ahora los asignados, y los destinos son las asignaciones o tareas y donde: Numero de orígenes (m) = numero de destinos (n). 
	Cada recurso ui = 1 
	Cada demanda vj = 1. 
Modelo del problema de asignación
Tabla de parámetros para el problema de asignación formulado como un problema de transporte. 
Caso 5. Asociar un trabajo a cada máquina de manera tal que minimice los costos que se presentan en la tabla:
SOLUCION
1.  DEFINICIÓN DE LAS VARIABLES DE DECISIÓN
xij = 1, si se le asigna la maquina i al trabajo j 
xij = 0, en caso contrario,
2.  FUNCIÓN OBJETIVO
      Minimizar los costos de asignación:
 Min Z = 14x11+5x12+8x13+7x14+2x21+12x22+6x23+ 5x24+7x31+8x32
 +3x33+9x34+2x41+4x42+6x43+10x44
 
FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
 3.   RESTRICCIONES
      De la máquina
	X11 + X12 + X13 + X14 	 = 1
	X21 + X22 + X23 + X24 = 1
	X31 + X32 + X33 + X34 = 1
	X41 + X42 + X43 + X44 = 1
      Del trabajo
	X11 + X21 + X31 + X41 	= 1
	X12 + X22 + X32 + X42 	= 1
	X13 + X23 + X33 + X43 	= 1
	X14 + X24 + X34 + X44 	= 1
 De asignación:
 				 
 Xij = 1 o 0; i=1, 2, 3 y 4; j= 1, 2, 3 y 4
GRACIAS
“Si cuidamos el Medio Ambiente, cuidamos nuestro futuro”
å
å
å
å
=
=
=
=
+
m
k
p
j
kj
kj
n
i
m
k
ik
ik
x
c
x
c
1
1
1
1
0
1
1
1
1
=
-
å
å
å
å
=
=
=
=
m
k
p
j
kj
n
i
m
k
ik
x
x
i
mk
ik
u
x
å
=
=
1
j
m
k
kj
v
x
=
å
=
1