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
 Alm 1 Alm 2 Oferta 
Fábrica 1 4 3 30 
Fábrica 2 5 2 130 
 60 100 
 
 
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 minimizar el Costo Total
Forma estándar
Ejemplo Máquina 1 Máquina 2 
 
Hombre1 3 4 1 
 
Hombre2 5 6 1 
 
 1 1 
 
Asignación
 Máquina 1 Máquina 2 
 
Hombre1 3 4 1 
 
Hombre2 5 6 1 
 
 1 1 
 
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.
T1 T2 D1 D2 D3
P1 3 4 M M M 1000
P2 2 5 M M M 1200
T1 0 7 8 6 M B
T2 M 0 M 4 9 B
D1 M M 0 5 M B
D2 M M M 0 3 B
B B 800+B 900+B 500
B= ´1000+1200= 2200
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
1
5
4
3
2
6
800
600
600
400
100
300 400
600
600
Arco Tiempo (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
X12 X13 X24 X25 X34 X35 X46 X45 X56 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 = 10X12 + 50X13 + 70X24 + 30X25 + 30X34 + 30X35 + 60X46 + 60X45 + 10X56
900
900
≤
≤
≤
≤
≤
≤
≤
≤
≤