PL Entera Mod transp asig y trasb, redes

Vista previa del material en texto

Programación Lineal Entera (PLE)
Son programas lineales en los cuales algunas o todas las variables están restringidas a valores enteros. 
Ejemplos: Asignación de máquinas Actividades
	 Personas	 Tareas
	 Aviones 		 Rutas	
Programación Entera 	Mixta (variables enteras y continuas)
			Pura (variables enteras)
Algoritmos de solución de la PLE
1. Resolver el problema considerando que las variables son continuas.
2. Empezando en esta solución óptima continua, añadir restricciones que modifiquen iterativamente el espacio a fin de obtener un extremo óptimo que satisfaga los requerimientos enteros.
Métodos clásicos:
1. Método de Ramificación y Acotamiento
2. Método de Plano Cortante
1. Ej. Max z = 5x1 + 4 x2
 s.a x1 + x2  5
	10 x1 + 6 x2  45
	x1, x2  0 y entero
Solución óptima continua PL0: x1 = 3.75, x2 = 1.25; z = 23.75
Seleccionar una variable cuyo valor en PL0 no es entero, ej x1 ,entonces la región 3 < x1 < 4 no contiene valores enteros de x1 y por tanto se puede eliminar.
Entonces Espacio PL1= Espacio PL0 + (x1  3)
	 Espacio PL2 =Espacio PL0 + (x1  4) 	
Como las restricciones agregadas se excluyen mutuamente, PL1 y PL2 se deben tratar como PL separados. Concepto de ramificación
Se deben examinar ambos problemas. La solución de PL1 es x1 = 3, x2 = 2 y z =23, que satisface los requerimientos enteros. 
Se debe acotar: no investigar más a PL1, porque no incluye ninguna solución mejor de PLE. z =23 constituye una cota inferior
LP0
x1 = 3.75, x2 = 1.25, z = 23.75
 x1  3			 x1 4
 LP1			 LP2
x1 =3, x2 =2, z =23	 x1 =4, x2 = 0.83, z = 23.33
 optimo
	 x2  0		x2  1
		 
			LP3	 LP4
	x1 = 4.5, x2 = 0, z =22.5	 Sin solución
 x1  4			x1  5			 Infactible
LP5			LP6
x1 = 4, x2 = 0, z = 20	Sin solución
Límite inferior
Programación Lineal Entera Binaria
Aplicaciones: Decisiones si(1) o no (0), tales como realizar o no una inversión, restricciones de una u otra, cargo fijo o costo de preparación.
Limitación en el numero de alternativas seleccionadas
Se puede utilizar para limitar el numero de proyectos o elementos seleccionados de un grupo. 
Si se requiere elegir no mas de dos proyectos, seria: 
x1 + x2+ x3 ≤ 2
Si se requiere forzar la selección a exactamente dos proyectos seria:
x1 + x2+ x3 = 2
Selecciones dependientes
En ocasiones, la selección de un proyecto depende de la selección de otro proyecto:
x1 ≤ x2, la decisión de x1 depende de la de x2
si x2 = 0; obliga a x1 = 0
Programación Lineal Entera Binaria
Ej. Una compañía quiere construir una fábrica en una de dos ciudades y un depósito en la ciudad que construya la fábrica
Capital disponible total: 25 (UM)
yi = 1 (si); yi = 0 (no) 	i= 1,2,3,4
Las dos primeras decisiones son mutuamente excluyentes 		 	  yi  1 i=1,2
Las decisiones 3 y 4 son contingentes con la 1 y 2 respectivamente.		 y3  y1
	 y4  y2			
	Decisión		
	Var. Decisión 	Beneficio (UM) 	Capital Requerido (UM)
	Fca. en ciudad 1	 y1	7	20
	Fca. en ciudad 2	 y2	5	15
	Depósito en ciudad 1	y3	4	12
	Depósito en ciudad 2	y4	3	10
Finalmente obtenemos:
Max z = 7 y1 + 5 y2 + 4 y3 + 3 y4
s.a 
 20 y1 + 15 y2 + 12 y3 +10 y4  25
 y1 + y2		  	1
 - y1 + y3  0
 - y2 + y4  	0
 yi = 0 o 1
Solución….
Y2 = 1, se construye la fabrica en la ciudad 2
Y4 = 1, se construye el almacén en la ciudad 2
Y1; Y3 = 0, no se construye la fabrica , ni el almacén en la ciudad 1
Z = 8 millones
Otras aplicaciones
Restricciones de una u otra
Solo una restricción se debe cumplir, por ej. Se quiere usar solo uno de dos tipos de recursos,
	
3 x1 + 2 x2  18; o bien 	x1 + 4 x2  16
Se replantean como:
 3 x1 + 2 x2  18 3 x1 + 2 x2  18 + M
x1 + 4 x2  16 + M x1 + 4 x2  16 
equivalente a:
3 x1 + 2 x2  18 + y M
 x1 + 4 x2  16 + (1-y) M 
 
Con y = 0 o 1
que se agregan al problema original.
Funciones de N valores posibles
Ej. 	3 x1 + 2 x2 = 6 ó 12 ó 18
es equivalente a: 
3 x1 + 2 x2 = 6 y1 + 12 y2 + 18 y3
y1 + y2 + y3 = 1 yi= 0 o 1 
Problema de Costo Fijo
	Kj + cj xj	 xj > 0
cj(xj) = 0		xj = 0
Min Z =  j =1…n cj xj, no lineal en xj debido a la discontinuidad en el origen.
Se puede plantear:
Min Z =  j =1…n ( cj xj + Kj yj) 
s.a 0  xj  Myj
 yj = 0 o 1 	si xi ≥ 1 ; entonces obliga a yi debe ser 1 
			si xi = 0 ; entonces yi puede ser 0 o 1, se hace 0 por 				objetivo de z (min)
Ejemplo de Problema con costo Fijo
Una empresa planea construir por lo menos una nueva planta, y esta considerando 
tres ciudades, una vez construida la planta , la misma debe tener capacidad por lo 
menos de producir anualmente 38.000 unidades 
Formulación 
Si x1 = 0; (no se construyo la planta en Bayton); entonces x4 = 0 (no se produce en Bayton)
Si x1 = 1; (se construyo la planta en Bayton); entonces x4 puede ser cualquier valor entre 0 y 21.000
Solución optima:
Transporte – Asignación -Trasbordo
Transporte
Caso particular de programación lineal y entera.
Busca el “COSTO MINIMO” para transportar unidades desde varias fuentes (fábricas) a varios destinos (almacenes).
Ejemplo
	Destinos
Orígenes
Demanda
Datos; Ofertas, Demandas y costo de transporte unitario.
Objetivo: Determinar la cantidad que se enviará de cada origen a cada destino, minimizando el costo total de transporte.
Se debe cumplir
 1) Que el costo del transporte sea directamente proporcional al 
 número de unidades transportadas.
 2)  cantidad ofertada =  cantidad demandada (no siempre se cumple)
Si 2) ; no se cumple se agregan orígenes o destinos ficticios para que se cumpla
Variables: xij Unidades Transportadas desde nodo i al nodo j .
Planteo del problema:				Forma estándar
 Min z = 4x11 + 3x12+ 5x21 + 2x22
 sa. x11 + x12 		  30
 x21 + x22  130
 x11 + x21 ≥ 60
 x12 + x22 ≥ 100 
 xi j  0, enteros V i j; Solución …
EL PROBLEMA
Una empresa energética dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.
 
Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.
Restricciones de oferta o disponibilidad, las cuales son de signo ≤:
 
X1,1 + X1,2 + X1,3 + X1,4 ≤ 80
X2,1 + X2,2 + X2,3 + X2,4 ≤ 30
X3,1 + X3,2 + X3,3 + X3,4 ≤ 60
X4,1 + X4,2 + X4,3 + X4,4 ≤ 45
 
Restricciones de demanda, las cuales son de signo ≥:
 
X1,1 + X2,1 + X3,1 + X4,1 ≥ 70
X1,2 + X2,2 + X3,2 + X4,2 ≥ 40
X1,3 + X2,3 + X3,3 + X4,3 ≥ 70
X1,4 + X2,4 + X3,4 + X4,4 ≥ 35
 
La función objetivo, en la cual se relaciona el costo correspondiente a cada ruta.
 
ZMIN = 5X1,1 + 2X1,2 + 7X1,3 + 3X1,4 + 3X2,1 + 6X2,2 + 6X2,3 + 1X2,4 + 6X3,1 + 1X3,2 + 2X3,3 + 4X3,4 + 4X4,1 + 3X4,2 + 6X4,3 + 6X4,4
Solución óptima 
Este problema presenta una solución óptima alternativa, aquí los resultados.
Problemas de Asignación
Caso particular de transporte con variables binarias
Cada recurso se asigna de un único modo a una actividad en particular.
 Empleados Tareas
 Máquinas Sitios
cada uno tiene su costo asociado
Objetivo: determinar asignaciones para minimizarel Costo Total
						Forma estándar
Ejemplo 
Asignación
 Min z = 3x11 + 4x12+ 5x21 + 6x22
 sa. x11 + x12 	  1
 x21 + x22  1
 x11 + x21 ≥ 1
 x12 + x22 ≥ 1 
 xi j  0, enteros V i j y binario
VARIABLES DE DECISIÓN
Las variables de decisión de este tipo de problemas es igual a las variables de cualquier modelo de transporte tradicional, es decir variables Xi,j donde i {Equipo de mantenimiento 1,2,3} y j {Máquina 1,2,3}, y corresponden a variables binarias en las cuales el valor 1 significa la asignación de un equipo de mantenimiento a una máquina en particular.
RESTRICCIONES
Dado que un equipo de mantenimiento no puede ser
 asignado a más de una maquinaria, esta 
característica debe de restringirse mediante las
siguientes inecuaciones.
 X1,1 + X1,2 + X1,3   1
X2,1 + X2,2 + X2,3   1
X3,1 + X3,2 + X3,3   1
 Además debe restringirse el hecho de que cada máquina solo requiere de un equipo de mantenimiento, por ende
 
X1,1 + X2,1 + X3,1  ≥ 1
X1,2 + X2,2 + X3,2  ≥ 1
X1,3 + X2,3 + X3,3  ≥ 1
 
 
Xi,j ≥ 0
Xi,j ∈ {Z}
FUNCIÓN OBJETIVO
ZMIN = 10X1,1 + 9X1,2 + 5X1,3 + 9X2,1 + 8X2,2 + 3X2,3 + 6X3,1 + 4X3,2 + 7X3,3
 
Trasbordo
Un problema de transporte solamente permite envíos que van directamente desde un punto de oferta hacia un punto de demanda. En muchas situaciones se permiten envíos entre puntos de oferta o entre puntos de demanda; también puede haber puntos (llamados de trasbordo) a través de los cuales se puede transbordar bienes en su viaje desde un punto de oferta hacia un punto de demanda. Problemas de envío, con algunas o las estas características son problemas de trasbordo.
Se define :
Punto de oferta al que puede enviar, pero no puede recibir, bienes hacia otro punto.
Punto de demanda, es el que puede recibir, pero no puede enviar, bienes de otros
Punto de trasbordo es el que puede recibir y enviar bienes de otros puntos.
Existe la posibilidad de resolver un modelo de transbordo mediante las técnicas tradicionales de resolución de modelos de transporte y este procedimiento se basa en la preparación del tabulado inicial haciendo uso de artificios conocidos con el nombre de amortiguadores, los cuales deben ser iguales a la sumatoria de las ofertas de los nodos de oferta pura y de coeficiente cero (0) en materia de costos.
Ejemplo
Una vez renombrado cada nodo definiremos las 
variables:
 
XA,C = Cantidad de unidades enviadas desde P1 hacia T1
XA,D = Cantidad de unidades enviadas desde P1 hacia T2
XB,C = Cantidad de unidades enviadas desde P2 hacia T1
XB,D = Cantidad de unidades enviadas desde P2 hacia T2
XC,D = Cantidad de unidades enviadas desde T1 hacia T2
XC,E = Cantidad de unidades enviadas desde T1 hacia D1
XC,F = Cantidad de unidades enviadas desde T1 hacia D2
XD,F = Cantidad de unidades enviadas desde T2 hacia D2
XD,G = Cantidad de unidades enviadas desde T2 hacia D3
XE,F = Cantidad de unidades enviadas desde D1 hacia D2
XF,G  = Cantidad de unidades enviadas desde D2 hacia D3
RESTRICCIONES
Existen en este modelo 3 tipos de restricciones y están estrechamente relacionadas con los tipos de nodos existentes, para un nodo oferta pura existe la restricción de oferta; para un nodo demanda pura existe la restricción de demanda, y para un nodo transitorio y/o transitorio de demanda existe la restricción de balance. Recordemos que los nodos transitorios son aquellos que tienen rutas (arcos o flechas) de entrada y salida, y si además este presenta un requerimiento de unidades se denomina transitorio de demanda.
       
FUNCIÓN OBJETIVO
En este caso la definición de la función objetivo se limita a la consignación de cada ruta con su respectivo costo bajo el criterio "minimizar".
 
ZMIN = 3XA,C + 4XA,D  + 2XB,C + 5XB,D + 7XC,D + 8XC,E + 6XC,F  + 4XD,F + 9XD,G + 5XE,F + 3XF,G
Restricciones de Oferta Pura:
XA,C + XA,D = 1000
XB,C + XB,D = 1200
 
Restricciones de demanda Pura:
 XD,G + XF,G = 500
 
Restricciones de balanceo para nodos únicamente transitorios:
Con estas restricciones aseguramos que todas las unidades que
 lleguen sean iguales a las unidades que salgan.
 
XA,C + XB,C - XC,D - XC,E - XC,F = 0
XA,D + XB,D + XC,D - XD,F - XD,G = 0
 
Restricciones de balanceo para nodos transitorios con requerimientos:
Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a la sumatoria de las unidades que salen más los requerimientos del nodo (demanda).
 XC,E - XE,F = 800
XC,F + XD,F + XE,F - XF,G = 900
Problema de Flujo en Redes de Costo Mínimo (MCNFP)
Todos los problemas de transporte, asignación, trasbordo, camino más corto, flujo máximo son casos especiales de este problema. 
Sea:
xij= número de unidades de flujo enviado del nodo i al nodo j a través del arco (i, j)
bi = oferta neta (salida - entrada) al nodo i.
cij = costo de transportar una unidad de flujo del nodo i al nodo j a través del arco (i, j)
Lij = Cota inferior para el flujo a través del arco (i,j). Si no existe cota inferior Li j= 0
Ui j = Cota superior para el flujo a través del arco (i,j). Si no existe cota superior Ui j = 
Entonces el PL es:
		Min  ci j xi j (para todos los arcos)
	s.a 
	 xij -  xki = bi (1) para cada nodo i en la red, ecuaciones de equilibrio de flujo (ef)
	L ij  xij  Uij (2) para todo arco en la red, restricciones de capacidad. 	
Ejemplo de Problemas de Redes de Costo mínimo
Cada hora, 900 autos entran a la siguiente red, (desde 1 a 6). El tiempo que tardan esta especificado en la tabla. La cantidad máxima de autos que pueden pasar durante una hora, esta especificada el gráfico.
 Xij, : numero de autos por hora, que cruzan el arco del nodo i al j
Cada valor en el arco indica la cantidad de autos que pueden circular
Función Objetivo
900
900
 Alm 1 Alm 2 Oferta 
Fábrica 1 4 3 30 
Fábrica 2 5 2 130 
 60 100 
 
 
	
	Alm 1
	Alm 2
	Oferta
	Fábrica 1
	4
	3
	30
	Fábrica 2 
	5
	2
	130
	
	60
	100
	
 Máquina 1 Máquina 2 
 
Hombre1 3 4 1 
 
Hombre2 5 6 1 
 
 1 1 
 
	
	Máquina 1
	Máquina 2
	
	Hombre1
	3
	4
	1
	
	
	
	
	Hombre2
	5
	6
	1
	
	
	
	
	
	1
	1
	
 Máquina 1 Máquina 2 
 
Hombre1 3 4 1 
 
Hombre2 5 6 1 
 
 1 1 
 
	
	Máquina 1
	Máquina 2
	
	Hombre1
	3
	4
	1
	
	
	
	
	Hombre2
	5
	6
	1
	
	
	
	
	
	1
	1
	
T1T2D1D2D3
P134MMM1000
P225MMM1200
T10786MB
T2M0M49B
D1MM05MB
D2MMM03B
BB800+B900+B500
B=´1000+1200=2200
1
5
4
3
2
6
800
600
600
400
100
300
400
600
600
ArcoTiempo (minutos)
(1,2)10
(1,3)50
(2,5)70
(2,4)30
(5,6)30
(4,5)30
(4,6)60
(3,5)60
(3,4)10
X
12
X
13
X
24
X
25
X
34
X
35
X
46
X
45
X
56
id
Restriccion
1
1
0
0
0
0
0
0
0
=
900
Nodo 1
-1
0
1
1
0
0
0
0
0
=
0
Nodo 2
0
-1
0
0
1
1
0
0
0
=
0
Nodo 3
0
0
-1
0
-1
0
1
1
0
=
0
Nodo 4
0
0
0
-1
0
0
-1
0
1
=
0
Nodo 5
0
0
0
0
0
0
0
-1
-1
=
-900
Nodo 6
1
0
0
0
0
0
0
0
0
=
800
Arco (1,2)
0
1
0
0
0
0
0
0
0
=
600
Arco (1,3)
0
0
1
0
0
0
0
0
0
=
600
Arco (2,4)
0
0
0
1
0
0
0
0
0
=
100
Arco (2,5)
0
0
0
0
1
0
0
0
0
=
300
Arco (3,4)
0
0
0
0
0
1
0
0
0
=
400
Arco (3,5)
0
0
0
0
0
0
1
0
0
=
600
Arco (4,5)
0
0
0
0
0
0
0
1
0
=
400
Arco (4,6)
0
0
0
0
0
0
0
0
1
=
600
Arco (5,6)
Todas las variables son no negativas
Min Z =
10X
12
+
50X
13
+
70X
24
+
30X
25
+
30X
34
+
30X
35
+
60X
46
+
60X
45
+
10X
56
≤
≤
≤
≤
≤
≤
≤
≤
≤