Clase 19 Modelos de redes

Vista previa del material en texto

Optimización Clase 19: Modelos de Redes
Profesor: José Manuel Izquierdo
Definición de Conceptos
Optimización, Modelos de Redes, Mayo-2018 2
Los modelos de redes son representaciones gráficas resumidas en una unidad denominada
GRAFO que contiene la interacción de 3 elementos gráficos: Nodos, Arcos y Flujos. Esta
representación gráfica se traduce en un modelo matemático que mediante el empleo de
matrices y vectores busca construir y determinar la interacción y equilibrios que definen el
problema.
La optimización de modelos de redes tiene un amplio uso en la industria del transporte,
telecomunicaciones, finanzas, servicios básicos (electricidad, agua, gas), recursos humanos,
etc.
��
��
��
�
��
��
Nodo Arco �	
 Flujo
Nodos Arcos Flujos
Ciudades Carreteras Vehículos
Centrales G. Líneas Elec. Electricidad
Puertos Rutas Naves
Central. Telef. Líneas Telef. Llamadas
Gerencias Promoción Personas
Bancos Bloomberg Depósitos
Definición de Conceptos: Flujos
Optimización, Modelos de Redes, Mayo-2018 3
Flujos
Internos
Flujos Externos
(Salida)
Flujos Externos
(Entrada)
Análisis de Flujos
��
�� ������� �� ������ = ������,����
��
�� ������� �� ������� = �����,�����
��
�� � ����� �� ������� = +"�����
��
�� � ����� �� ������ = −$�����
������,���� + $����� = �����,����� + "�����
������,���� − �����,����� = "����� −$�����
Definición de Conceptos: Equilibrios
Optimización, Modelos de Redes, Mayo-2018 4
 ��
��� %������� �� &������
 −��
��� %������� �� '������� 
= ��
��� ' ������ '�������/&������
 ) �*
�
+�
− ) �	*
�
	+�
= ,*
���-� -. 	�	�	� /�0
�;��-� -. ��	�� /�0
�
Determinación de flujos
Equilibrios Nodales
3� 4
� ����� � 
� ���� �� �5
�� � �� 4
� ���� �� ����
��
��
��
�
��
��
��
Entradas Salidas
�	,* �*,
Proveedor Neto ) �*
 > ) �	*
�
	+�
�
+�
,* > 0
Cliente Neto ) �*
 < ) �	*
�
	+�
�
+�
,
 < 0
Transbordo Neto ) �*
 = ) �	*
�
	+�
�
+�
,
 = 0
Definición de Restricciones
Optimización, Modelos de Redes, Mayo-2018 5
Restricciones de Capacidad de los Arcos 
Restricciones de Capacidad de los Nodos 
Ejercicio de transporte de hidrocarburos
Optimización, Modelos de Redes, Mayo-2018 6
Sociedad Nacional del Oleoducto (SONACOL) es la empresa encargada en Chile del
transporte de petróleo en oleoductos. La empresa cuenta con una red de oleoductos que
conectan las dos refinerías de ENAP (Concón y Talcahuano) con los principales centros de
consumo en Chile (Santiago y Valparaíso). Dicha red se encuentra resumida en el siguiente
Grafo, donde por razones de aseguramiento de la continuidad del suministro cuenta con una
estación de transferencia de petróleo en la localidad de Polpaico.
El transporte de petróleo debe realizarse a través de la red de SONACOL, donde se tienen
los siguientes costos por tramo de red de oleoducto, los cuales de miden en $ por m³
transportado, información que se resume en la tabla adjunta. La capacidad de las refinerías
de ENAP consta de 700 (m³/dia) en Concón y de 900 (m³/dia), mientras que la demanda por
petróleo en Santiago y Valparaíso es de 1.100 y 500 (m³/dia) respectivamente.
Su misión es desarrollar un modelo de optimización que le permita a SONACOL minimizar
sus costos operacionales de transporte de petróleo de manera de satisfacer la demanda de
sus clientes.
Ejercicio de transporte de hidrocarburos
Optimización, Modelos de Redes, Mayo-2018 7
Matriz de Costos:
O/D CC Stgo PP Valpo Thno
CC -- 8 6 1 --
Stgo -- -- -- -- --
PP -- 2 -- -- --
Valpo -- -- -- -- --
Thno 14 15 12 --
Matriz de Capacidad: O/D CC Stgo PP Valpo Thno
CC -- 400 300 390 --
Stgo -- -- -- -- --
PP -- 600 -- -- --
Valpo -- -- -- -- --
Thno 630 370 290 --
Representación gráfica: Red unidireccionada
Optimización, Modelos de Redes, Mayo-2018 8
Función objetivo 9�� :���� = ) ) �	,
 · <	,
9�� :����� = 8���,>��� + 6 ���,@@ + ���,A��@� + 2�@@,>��� + 14��E��,>��� + 15��E��,@@ + 12��E��,A��@� 
Equilibrios nodales y restricciones de capacidad
Optimización, Modelos de Redes, Mayo-2018 9
Nodo Concón
Flujo Interno de Entradas Nodo Concón (fie)
��� = 0
Flujo Interno de Salidas Nodo Concón (fis)
��� = ���, >��� + ���, @@ + ���, A��@�
Entradas/(Salidas) Externas Nodo Concón (fese)
���� = ,�� = +700
Equilibrio de flujos Neto Nodo Concón 
(Salidas-Entradas)
��� − ��� = ���� → ���, >��� +���, @@ + ���, A��@� − (0) = +700
Restricciones de capacidad de arcos
0 ≤ ���, >��� ≤ 400
0 ≤ ���, @@ ≤ 300
0 ≤ ���, A��@� ≤ 390
Equilibrios nodales y restricciones de capacidad
Optimización, Modelos de Redes, Mayo-2018 10
Nodo Santiago
Flujo Interno de Entradas Nodo Santiago (fie)
��� = 0
Flujo Interno de Salida Nodo Santiago (fis)
��� = ���, >��� + �@@, >��� + ��E�� , >���
Entradas/(Salidas) Externas Nodo Santiago (fese)
���� = ,>��� = −1.100
Equilibrio de flujos Neto Nodo Concón 
(Salidas-Entradas)
Restricciones de capacidad de arcos ��� − ��� = ���� → 0 − ���, >��� − �@@, >��� − ��E�� ,>��� = −1.100
Equilibrios nodales y restricciones de capacidad
Optimización, Modelos de Redes, Mayo-2018 11
Nodo Polpaico
Flujo Interno de Entradas Nodo Polpaico (fie)
��� = �@@, >���
Flujo Interno de Salidas Nodo Polpaico (fis)
��� = ���, @@ + ��E��, @@
Entradas/(Salidas) Externas Nodo Polpaico (fese)
���� = ,@@ = 0
Equilibrio de flujos Neto Nodo Polpaico
(Salidas-Entradas)
Restricciones de capacidad de arcos ��� − ��� = ���� → �@@ >��� − ���, @@ − ��E�� ,@@ = 0
0 ≤ �@@, >��� ≤ 600
Equilibrios nodales y restricciones de capacidad
Optimización, Modelos de Redes, Mayo-2018 12
Nodo Valparaíso
Flujo Interno de Entradas Nodo Valparaíso (fie)
��� = 0
Flujo Interno de Salidas Nodo Valparaíso (fis)
��� = ���, A��@� + ��E��, A��@�
Entradas/(Salidas) Externas Nodo Valparaíso (fese)
���� = ,A��@� = −500
Equilibrio de flujos Neto Nodo Valparaíso 
(Salidas-Entradas)
Restricciones de capacidad de arcos ��� − ��� = ���� → 0 − ���, A��@� − ��E��,A��@� = −500
Equilibrios nodales y restricciones de capacidad
Optimización, Modelos de Redes, Mayo-2018 13
Nodo Talcahuano
Flujo Interno de Entradas Nodo Talcahuano (fie)
��� = 0
Flujo Interno de Salidas Nodo Talcahuano (fis)
��� = ��E��, A��@� + ��E��, @@ + ��E��, >���
Entradas/(Salidas) Externas Nodo Talcahuano (fese)
���� = ,�E�� = +900
Equilibrio de flujos Neto Nodo Talcahuano 
(Salidas-Entradas)
Restricciones de capacidad de arcos
��� − ��� = ���� → ��E��, A��@� + ��E��, @@ + ��E��, >��� = +900
0 ≤ ��E��, @@ ≤ 370
0 ≤ ��E��, A��@� ≤ 290
0 ≤ ��E��, >��� ≤ 630
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 14
Función objetivo:
9�� :����� = 8���,>��� + 6 ���,@@ + ���,A��@� + 2�@@,>��� + 14��E��,>��� + 15��E��,@@ + 12��E��,A��@� 
Restricciones:
i) Equilibrios Nodales
���, >��� + ���, @@ + ���, A��@� = +700
−���, >��� − �@@, >��� − ��E�� ,>��� = −1.100
�@@, >��� − ���, @@ − ��E��,@@ = 0
−���, A��@� − ��E��,A��@� = −500
��E��, A��@� + ��E��, @@ + ��E��, >��� = +900
ii) Capacidades de los Arcos
���, >��� ≤ 400
���, @@ ≤ 300
���, >��� ≤ 390
�@@, >��� ≤ 600
��E��, @@ ≤ 370
��E��, A��@� ≤ 290
��E��, >��� ≤ 630
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 15
���,>���, ���,@@, ���,A��@�, �@@,>���, ��E��,>��� , ��E��,@@, ��E��,A��@� ≥ 0
Restricciones:
iii) No Negatividad
Resultados
Optimización, Modelos de Redes, Mayo-2018 16
Variables:
Función Objetivo
Celda objetivo (Mín)
Celda Nombre Valor original Valor final
$C$4 Costos 0 15.730
O/D CC Stgo PP Valpo Thno
CC -- 310 0 390 --
Stgo -- -- -- -- --
PP -- 160 -- -- --
Valpo -- -- -- -- --
Thno 630 160 110 --
Resultados: Restricciones
Optimización, Modelos de Redes, Mayo-2018 17
Restricciones
Celda Nombre Valor de la celda Fórmula Estado Demora
$C$13 cap cc,stgo 310 $C$13<=$E$13 No vinculante 90
$C$14 cap cc,pp 0 $C$14<=$E$14 No vinculante 300
$C$15 cap cc,valpo 390 $C$15<=$E$15 Vinculante 0
$C$16 cap pp,stgo 160 $C$16<=$E$16 No vinculante 440
$C$17 cap thno,pp 160 $C$17<=$E$17 No vinculante 210
$C$18 cap thno,valpo 110 $C$18<=$E$18 No vinculante 180
$C$19 cap thno, stgo 630 $C$19<=$E$19 Vinculante 0
$C$8 eq n cc 700 $C$8=$E$8 Vinculante 0
$C$9 eq n stgo -1.100 $C$9=$E$9 Vinculante 0
$C$10 eq n pp 0 $C$10=$E$10 Vinculante 0
$C$11 eq n valpo -500 $C$11=$E$11 Vinculante 0
$C$12 eq n thno 900 $C$12=$E$12 Vinculante 0
Resultados: Sensibilidad
Optimización, Modelos de Redes, Mayo-2018 18
Celdas de variables
Final Reducido Objetivo Permisible Permisible
Celda Nombre Valor Coste Coeficiente Aumentar Reducir
$I$5 -- Stgo 310 0 8 0 2
$J$5 -- PP 0 0 6 1E+30 0
$K$5 -- Valpo 390 0 1 2 1E+30
$I$7 -- -- 160 0 2 2 0
$I$9 Thno -- 630 0 14 3 1E+30
$J$9 Thno -- 160 0 15 2 3
$K$9 Thno -- 110 0 12 1E+30 2
Restricciones
Final Sombra Restricción Permisible Permisible
Celda Nombre Valor Precio Lado derecho Aumentar Reducir
$C$13 cap cc,stgo 310 0 400 1E+30 90
$C$14 cap cc,pp 0 0 300 1E+30 300
$C$15 cap cc,valpo 390 -2 390 110 90
$C$16 cap pp,stgo 160 0 600 1E+30 440
$C$17 cap thno,pp 160 0 370 1E+30 210
$C$18 cap thno, valpo 110 0 290 1E+30 180
$C$19 cap thno, stgo 630 -3 630 160 210
$C$8 eq n cc 700 8 700 0 310
$C$9 eq n stgo -1100 0 -1100 1E+30 0
$C$10 eq n pp 0 2 0 0 160
$C$11 eq n valpo -500 5 -500 0 160
$C$12 eq n thno 900 17 900 0 160
Ejercicio múltiple de transporte de hidrocarburos
Optimización, Modelos de Redes, Mayo-2018 19
Considere ahora una matriz de 9 nodos donde transportar gas desde el nodo i al nodo j se
tiene que pagar un Costo Variable de CVi,j por cada m³ transportado más el pago de un
Cargo Fijo CFi,j en $ por la mera utilización del ducto que une los nodos i,j. Adicionalmente la
red de gaseoductos consta de una capacidad limitada de transporte de gas donde cada tramo
i,j consta de una Capacidad Capi,j. de (m³/día)
A fin de simplificar el modelo considere que el Cargo Fijo CFi,j equivale a la misma cantidad
en dinero que la Capacidad del tramo Capi,j.en (m³/día).
Desarrolle un modelo de optimización que permita minimizar los costos totales de transporte
de gas en un día cualquiera considerando que en los nodos 1 y 7 se inyectan a la red la
cantidad 17 y 20 m³, los cuales son entregados a los clientes en los nodos 3,6 y 9 quienes
consumen 10,17 y 10 m³ respectivamente.
Modelo de Optimización: Red bidireccionada
Optimización, Modelos de Redes, Mayo-2018 20
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 21
O/D 1 2 3 4 5 6 7 8 9
1 -- 8 10 5 -- -- 8 -- --
2 7 -- 7 -- 6 -- -- -- --
3 -- 5 -- -- -- 8 -- -- --
4 -- -- -- -- 4 -- 4 -- --
5 -- 7 -- 2 -- 9 -- 9 --
6 -- -- -- -- 8 -- -- -- --
7 -- -- -- -- -- -- -- 1 --
8 -- -- -- -- 7 -- 3 -- 10
9 -- -- -- -- -- -- -- -- --
Matriz de Costos Variables :P	,
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 22
O/D 1 2 3 4 5 6 7 8 9
1 -- 30 5 13 -- -- 23 -- --
2 25 -- 20 -- 21 -- -- -- --
3 -- 15 -- -- -- 29 -- -- --
4 -- -- -- -- 10 -- 33 -- --
5 -- 25 -- 11 -- 60 -- 39 --
6 -- -- -- -- 23 -- -- -- --
7 -- -- -- -- -- -- -- 20 --
8 -- -- -- -- 39 -- 17 -- 20
9 -- -- -- -- -- 17 -- -- --
Matriz de Costos Fijos :�	,
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 23
O/D 1 2 3 4 5 6 7 8 9
1 -- 30 5 13 -- -- 23 -- --
2 25 -- 20 -- 21 -- -- -- --
3 -- 15 -- -- -- 29 -- -- --
4 -- -- -- -- 10 -- 33 -- --
5 -- 25 -- 11 -- 60 -- 39 --
6 -- -- -- -- 23 -- -- -- --
7 -- -- -- -- -- -- -- 20 --
8 -- -- -- -- 39 -- 17 -- 20
9 -- -- -- -- -- 37 -- -- --
Matriz de Capacidad :�Q�<����	,
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 24
Flujos Externos
Flujos Externos de Entrada ��* Flujos Externos de Salida ��*
Nodo RST
1 +17
2 0
3 0
4 0
5 0
6 0
7 +20
8 0
9 0
Nodo RsT
1 0
2 0
3 -10
4 0
5 0
6 -17
7 0
8 0
9 -10
Modelo de Solución problema general de red de gas
Optimización, Modelos de Redes, Mayo-2018 25
Definición de Variables:
�	,
: ��
�� ����� �� ���� �� ���5�� � �� ���� �� ������� � � = 1 → � = 9; � = 1 → � = 9
 	,
: W����,�� ,������ ��,�� �� 
����X�<�ó� ��� ���Z� ����<�� ����� ���� ���<�� � ���� ������� �
 	,
 = 1 �� �� 
����X� �� �
�� ����<�� ����� ���� �� ���<�� � � ���� �� ������� �; 0 �� �� �� 
����X�
Función objetivo:
9�� :�����[������ = ) ) �	,
 · :P	,
�+\
+�
�+\
	+�
+ ) ) 	,
 · :�	,
�+\
+�
�+\
	+�
:���� P����,�� = ) ) �	,
 · :P	,
�+\
+�
�+\
	+�
:���� ���� = ) ) 	,
 · :�	,
�+\
+�
�+\
	+�
Modelo de Solución
Optimización, Modelos de Redes, Mayo-2018 26
Nodo Genérico K Flujo Interno de Salidas Nodo K (fis)
��� = ) �*,
 *+�→�+\
�+\
+�
Flujo Interno de Entradas Nodo K (fie)
��� = ) �	,* *+�→�+\
�+\
	+�
Equilibrio de flujos Neto Nodo K 
(Salidas-Entradas)
Entradas/(Salidas) Externas Nodo K (fese)
���� = ��* + ��* � = 1 → � = 9
) �*,
 −
�+\
+�
) �	,* =
�+\
	+�
��* + ��* � = 1 → � = 9
Restricciones de capacidad y utilización de arcos
�*,
 ≤ <�Q�<����*,
 � = 1 → � = 9; � = 1 → � = 9
Restricciones de Equilibrio Binario
�*,
 ≤ <�Q�<����*,
 · 	,
 � = 1 → � = 9
� = 1 → � = 9
Modelo de Solución: Método de Floyd
Optimización, Modelos de Redes, Mayo-2018 27
Para las rutas directas que en realidad no existen, por ejemplo ir directamente del nodo 1
al nodo 9, modifique la matrices de costos y capacidades de arcos, de manera que en la
matriz de costos donde no existe ruta directa,. Para el caso de la matriz de costos cree
una ruta ficticia directa cuyo costo es infinito, lo cual se traduce en la práctica un número
extremadamente grande por ejemplo ir directamente desde el nodo 1 al nodo 9 costaría
999, de esta manera al momento de resolver el problema el utilizar esta nueva ruta sería
tan altamente costosa que el algoritmo de solución inmediatamente la descartaría y
buscaría una solución de mínimo costo a través de combinaciones de rutas directas que
si existen.
Si el problema de optimización considera restricciones de capacidades en los arcos, en la
matriz de restricciones de capacidad de los arcos para las rutas directas entre nodos que
no existen modifique el contenido de la capacidad y hágalo valer 0, de esta forma el
método de solución no asignará flujo alguno a esta ruta ficticia puesto que al verificar la
capacidad disponible de flujo entre estos 2 arcos estará obligado a asignar un valor de 0
para cumplir con la restricción. De esta manera el método de solución solamente buscará
soluciones posibles a través de combinaciones de rutas directas cuya capacidad no sea
nula.
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 28
O/D 1 2 3 4 5 6 7 8 9
1 9999 8 10 5 9999 9999 8 9999 9999
2 7 9999 7 9999 6 9999 9999 9999 9999
3 9999 5 9999 9999 9999 8 9999 9999 9999
4 9999 9999 9999 9999 4 9999 4 9999 9999
5 9999 7 9999 2 9999 9 9999 9 9999
6 9999 9999 9999 9999 8 9999 9999 9999 9999
7 9999 9999 9999 9999 9999 9999 9999 1 9999
8 9999 9999 9999 9999 7 9999 3 9999 10
9 9999 9999 9999 9999 9999 37 9999 9999 9999
Matriz de Costos Variables Redefinida para Algoritmo de Floyd :P	,
Modelo de Optimización
Optimización, Modelos de Redes, Mayo-2018 29
O/D 1 2 3 4 5 6 7 8 9
1 0 30 5 13 0 0 23 0 0
2 25 0 20 0 21 0 0 0 0
3 0 15 0 0 0 29 0 0 0
4 0 0 0 0 10 0 33 0 0
5 0 25 0 11 0 60 0 39 0
6 0 0 0 0 23 0 0 0 0
7 0 0 0 0 0 0 0 20 0
8 0 0 0 0 39 0 17 0 20
9 0 0 0 0 0 17 0 0 0
Matriz de Capacidad redefinida para Algoritmo de Floyd :�Q�<����	,
Modelo de Solución: Método de Floyd
Optimización, Modelos de Redes, Mayo-2018 30
Función objetivo:
Restricciones:
i) Equilibrios Nodales
) �*,
 −
�+\
+�
) �	,* =
�+\
	+�
��* + ��* � = 1 → � = 9
ii) Capacidades de los Arcos y Equilibrio Binario
�	,
 ≥ 0 	,
 ]������{0; 1} � = 1 → � = 9
� = 1 → � = 9
9�� :�����[������ = ) ) �	,
 · :P	,*
�+\
+�
�+\
	+�
+ ) ) 	,
 · :�	,*
�+\
+�
�+\
	+�
�*,
 ≤ <�Q�<����*,
 · 	,
 � = 1 → � = 9
� = 1 → � = 9
iii) No Negatividad y Variables Binarias
Modelos de Redes: Análisis de pérdidas
Optimización, Modelos de Redes, Mayo-2018 31
En muchasactividades de transporte y procesos productivos se producen pérdidas de
recursos ya sea por ejemplo filtraciones, robos, obsolescencia, pudriciones, entre otros. Ante
esta realidad los modelos de redes deben ser capaces de representar matemáticamente
estos fenómenos de manera de poder ajustar el proceso de maximización o minimización
cuando corresponda.
El modelamiento matemático de pérdidas en flujo de redes se subdivide en dos grandes
categorías: Pérdidas en los arcos que conectan los nodos y pérdidas en los nodos
propiamente tales, ejemplos del primer tipo de pérdidas serían filtraciones en ductos de agua,
robos a camiones, productos que no alcanzan cierto nivel de calidad entre etapas
productivas, etc, mientras que ejemplos de pérdidas en los nodos pueden encontrarse casos
tales como: Obsolescencia o pudriciones de mercaderías almacenadas en una bodega, robos
al interior de estas, daños al proceso productivo en estaciones de trabajo, entre otros.
Una vez identificada si la pérdida se produce en los arcos o si ocurren en los nodos, es
necesario saber si se pide o no realizar una gestión de dichas pérdidas a fin de calibrar el
modelo matemático, en base a lo anterior el análisis de estas situaciones se detallan en los
siguientes ejemplos.
Análisis de pérdidas en los arcos: Sin gestión de pérdidas
Optimización, Modelos de Redes, Mayo-2018 32
Considere una red de 3 nodos 1, 2 y 3, donde el flujo entre los nodos 2 y 3 existe una pérdida
equivalente al 10% del flujo que sale desde el nodo 2 al nodo 3
i) Equilibrio Nodo 2
��, ` − ��,� = 0
ii) Equilibrio Nodo 3
0 − 0,9��, ` − ��,` = −$
Análisis de pérdidas en los arcos: Con gestión de pérdidas
Optimización, Modelos de Redes, Mayo-2018 33
Considere una red de 3 nodos 1, 2 y 3, donde el flujo entre los nodos 2 y 3 existe una pérdida
equivalente al 10% del flujo que sale desde el nodo 2 al nodo 3
Análisis de pérdidas en los arcos: Con gestión de pérdidas
Optimización, Modelos de Redes, Mayo-2018 34
i) Equilibrio Nodo 2 ii) Equilibrio Nodo 3 iii) Equilibrio Nodo P
- Equilibrio de Pérdida��,a��,` = 1090
��� = ��,` + ��,a 
��� = ��,� 
���� = 0 
 ��� − ��� = ���� → ��,` + ��,a − ��,� = 0
 
��� = 0 
 ��� = ��,` + ��,` 
���� = −$ 
 0 − ��,` − ��,` = −$ 
 
��� = 0 
 ��� = ��,a 
���� = −b 
 ��� − ��� = ���� → 0 − ��,a = −b
 
Análisis de pérdidas en los nodos: Con gestión de pérdidas
Optimización, Modelos de Redes, Mayo-2018 35
Considere una red de 4 nodos 1, 2,3 y 4, donde el nodo 2 presenta una pérdida equivalente
al 15% de la cantidad recibida
Análisis de pérdidas en los nodos: Con gestión de pérdidas
Optimización, Modelos de Redes, Mayo-2018 36
i) Equilibrio Nodo 2
 ��� = ��,` + ��,a ��� = ��,� + �c,� ���� = 0 ��� − ��� = ���� → ��,` + ��,a − ��,� − �c,� = 0 
- Equilibrio de Pérdida��,a = 0,15 ��,� + �c,�
i) Equilibrio Nodo P
 ��� = 0 ��� = ��,a ���� = −b ��� − ��� = ���� → 0 − ��,a = −b 
Ejemplo de Aplicación de Modelos de Redes
Ejercicio modificado del propuesto por profesor Marco Caserta IE Business School Optimización, Modelos de Redes, Mayo-2018 37
Coopedala es una Cooperativa Agrícola dedicada al desarrollo de la agricultura en la X
Región de los Lagos y cuenta con 4 puntos de venta de forraje para animales ubicados en las
comunas de Osorno, Llanquihue, Puerto Varas y Puerto Montt, a fin de proveer de mejor
manera a sus puntos de venta, la empresa cuenta con 3 centros de acopio ubicados en los
kilómetros 950, 999, y 1.030 de la ruta 5 sur, según el modelo de negocios no está permitido
que un punto de venta abastezca a otro punto de venta, ni acumular productos de un período
para otro.
La demanda en toneladas por productos agrícolas en cada unos de los centros de venta se
resume en la tabla N1, al igual que la capacidad de almacenamiento de sus 3 centros de
acopio en toneladas, y el respectivo costo de transporte por tonelada.
Su misión es determinar la programación de despachos desde los centros de acopio a los
puntos de venta de manera que Coopedala minimice sus costos de envío.
Ejemplo de Aplicación de Modelos de Redes Transporte
Optimización, Modelos de Redes, Mayo-2018 38
Costo ($) Osorno (Ve) Llanquihue (Vf) P. Varas (Vg) P. Montt (Vh)i� 950 (b�) 10.260 54.435 68.023 87.465
i� 999 (b�) 60.025 2.400 21.250 45.375
i` 1.030 (b̀ ) 93.080 40.872 16.900 3.220
Capacidad Tons.
i� 950 (b�) 700
i� 999 (b�) 900
i` 1.030 (b̀ ) 600
Total 2.200
Venta Tons.
Osorno (Ve) 600
Llanquihue (Vf) 400
P. Varas (Vg) 500
P. Montt (Vh) 700
Total 2.200
Ejemplo de Aplicación de Modelos de Redes Transporte
Optimización, Modelos de Redes, Mayo-2018 39
Fenómeno a Estudiar: Minimización de costos totales de transporte mediante la
visualización de un Grafo que representa al problema, teniendo
en cuenta restricciones de capacidad de almacenaje y ventas
Variables: 	,
 como la cantidad de toneladas de producto que se
transportan del Almacen/Proveedor i al lugar donde se realiza la
Venta j
Parámetros: <	,
 costo por tonelada de producto transportado desde el
Almacen/Proveedor Pi al lugar donde se realiza la Venta j
:�Q	 capacidad instalada para almacenar del 
Almacen/Proveedor Pi i=1-3 proveedores (950, 999, 1.030)
j�Z
 demanda por productos en el cento de ventas Vj, j=1-4 
centros de ventas (Osorno, Llanquihue, P. Varas, P. Montt)
Ejemplo de Aplicación de Modelos de Redes Transporte
Optimización, Modelos de Redes, Mayo-2018 40
b	+�
b	+�
b	+`
P
+�
P
+�
P
+`
P
+c
:�Q� = 700 = ) �,
�+c
+�
:�Q� = 900 = ) �,
�+c
+�
:�Q` = 600 = ) `,
�+c
+�
j�Z� = 600 = ) 	,�
�+`
	+�
j�Z� = 400 = ) 	,�
�+`
	+�
j�Z` = 500 = ) 	,`
�+`
	+�
 	
<	
j�Zc = 700 = ) 	,c
�+`
	+�
n=3 Proveedores (i) (Salidas) m=4 Clientes(j) (Entradas)
Ejemplo de Aplicación de Modelos de Redes de Transporte
Optimización, Modelos de Redes, Mayo-2018 41
Representación Matricial del Problema:
��
��� 	,
 Osorno (Ve) Llanquihue (Vf) P. Varas (Vg) P. Montt (Vh) Total
i� 950 (b�) �,� �,� �,` �,c ) �,
 = 700�+c
+�
i� 999 (b�) �,� �,� �,` �,c ) �,
 = 900
�+c
+�
i` 1.030 (b̀ ) `,� `,� `,` `,c ) `,
 = 600
�+c
+�
Total ) 	,� = 600�+`	+� ) 	,� = 400
�+`
	+� ) 	,`
�+`
	+� = 500 ) 	,`
�+`
	+� = 700 ) ) 	,
 =
�+c
+�
�+`
	+� 2.200
Ejemplo de Aplicación de Modelos de Redes de Transporte
Optimización, Modelos de Redes, Mayo-2018 42
) 	,
 =�+c
+� :�Q	 � = 1 → 3 k
 �,� + �,� + �,` + �,c = 700 �,� + �,� + �,` + �,c = 900
 `,� + `,� + `,` + `,c = 600
 
Función Objetivo: 9�� :����� = ) ) <	,
�+c
+�
 	,
�+`
	+�
9�� 
10.260 �,� + 54.435 �,� + 68.023 �,` + 87.465 �,c
+60.025 �,� + 2.400 �,� + 21.250 �,` + 45.375 �,c
+93.080 `,� + 40.872 `,� + 16.900 `,` + 3.220 `,c
Restricciones: i) Capacidad
) 	,
 =�+`	+� j�Z
 � = 1 → 4 
 �,� + �,� + `,� = 600 �,� + �,� + `,� = 400 �,` + �,` + `,` = 500 �,c + �,c + `,c = 700
ii) Demanda
iii) No Negatividad 	,
 ≥ 0 � = 1 → 3, j = 1 → 4
Ejemplo de Aplicación de Modelos de Redes de Transporte
Optimización, Modelos de Redes, Mayo-2018 43
Solución:
��
��� 	,
 Osorno (Ve) Llanquihue (Vf) P. Varas (Vg) P. Montt (Vh) Total
i� 950 (b�) �,� = 600 �,� = 0 �,` = 0 �,c = 100 ) 	,� = 700�+c
+�
i� 999 (b�) �,� = 0 �,� = 400 �,` = 500 �,c = 0 ) 	,� = 900
�+c
+�
i` 1.030 (b̀ ) `,� = 0 `,� = 0 `,` = 0 `,c = 600 ) 	,� = 600
�+c
+�
Total ) 	,� = 600�+`	+� ) 	,� = 400
�+`
	+� ) 	,`
�+`
	+� = 500 ) 	,c
�+`
	+� = 700 ) ) 	,
 =
�+c
+�
�+`
	+� 2.200
:����� = 10.260(600) + 54.435(0) + 68.023(0) + 87.465(100)+60.025(0) + 2.400(400) + 21.250(500)+ 45.375(0)+93.080(0) + 40.872(0) + 16.900(0) + 3.220(600) = $28.419.500
Reformulación del problema con Exceso de Capacidad
Optimización, Modelos de Redes, Mayo-2018 44
El problema anterior, se reformula debido al hecho que el cliente de Puerto Montt
inesperadamente modificó su pedido reduciéndolo de 700 ton a 500 ton . El problema
surge del hecho de que los centros de distribución no pueden almacenar el exceso de
oferta y lo que sobre debe ser desechado con un costo específico.
Capacidad Tons.i� 950 (b�) 700
i� 999 (b�) 900
i` 1.030 (b̀ ) 600
Total 2.200
Venta Tons.
Osorno (Ve) 600
Llanquihue (Vf) 400
P. Varas (Vg) 500
P. Montt (Vh) 500
Total 2.000
Costo ($) Osorno (Ve) Llanquihue (Vf) P. Varas (Vg) P. Montt (Vh) Desecho (Vn)i� 950 (b�) 10.260 54.435 68.023 87.465 20.200
i� 999 (b�) 60.025 2.400 21.250 45.375 3.050
i` 1.030 (b̀ ) 93.080 40.872 16.900 3.220 2.900
Reformulación del problema con Exceso de Capacidad
Optimización, Modelos de Redes, Mayo-2018 45
b	+�
b	+�
b	+`
P
+�
P
+�
P
+`
P
+c
:�Q� = 700 = ) �,
�+n
+�
:�Q� = 1.100 = ) �,
�+n
+�
:�Q` = 600 = ) `,
�+n
+�
j�Z� = 600 = ) 	,��+`	+�
j�Z� = 400 = ) 	,��+`	+�
j�Z` = 500 = ) 	,`�+`	+�
 	
<	
j�Zc = 500 = ) 	,c�+`	+�
n=3 Proveedores (i) (Salidas) m=5 Clientes(j) (Entradas)
P
+n j�Zn = ) :�Q	 −�+`	+� ) j�Z
 = ) 	,n
�+`
	+�
�+c
+�
Reformulación del problema con Exceso de Capacidad
Optimización, Modelos de Redes, Mayo-2018 46
) 	,
 =�+n
+� :�Q	 � = 1 → 3 
Función Objetivo: 9�� :����� = ) ) <	,
�+n
+� 	,
�+`
	+�
Restricciones: i) Capacidad
) 	,
 =�+`	+� j�Z
 � = 1 → 4
ii) Demanda
iii) No Negatividad 	,
 ≥ 0 � = 1 → 3, j = 1 → 5
) 	,n =�+`	+� ) :�Q	 − ) j�Z
 
c
+�
�+`
	+�
Reformulación del problema con Exceso de Capacidad
Optimización, Modelos de Redes, Mayo-2018 47
Solución:
��
��� 	,
 Osorno (Ve) Llanq. (Vf) P. Varas (Vg) P. Montt (Vh) Desecho (Vn) Total
i� 950 (b�) �,� = 600 �,� = 0 �,` = 0 �,c = 0 �,n = 100 ) �,
 = 700�+n
+�
i� 999 (b�) �,� = 0 �,� = 400 �,` = 400 �,c = 0 �,n = 100 ) �,
 = 900
�+n
+�
i` 1.030 (b̀ ) `,� = 0 `,� = 0 `,` = 100 `,c = 500 `,n = 0 ) `,
 = 600
�+n
+�
Total ) 	,� = 600�+`	+� ) 	,� = 400
�+`
	+� ) 	,`
�+`
	+� = 500 ) 	,c
�+`
	+� = 500 ) 	,n
�+`
	+� = 200 ) ) 	,
 =
�+c
+�
�+`
	+� 2.000
:����� = 10.260 600 + 54.435 0 + 68.023 0 + 87.465 0 + 20.200(100)+60.025 0 + 2.400 400 + 21.250 400 + 45.375 0 + 3.050(100)+93.080 0 + 40.872 0 + 16.900 0 + 3.220 500 + 2.900(0) = $21.241.000
Reformulación del problema con Exceso de Demanda
Optimización, Modelos de Redes, Mayo-2018 48
El problema anterior nuevamente se reformula debido al hecho que por un incidente el
centro de Acopio en el Km 99 disminuye su capacidad de 900 ton a 750 ton. Esto implica
en la práctica que la empresa debe de adquirir las toneladas faltantes a un proveedor
externo, teniendo que pagar los costos asociados al transporte del tercero a los cliente de
Coopedala para cumplir con el pedido original de 2.200 tons
Capacidad Tons.i� 950 (b�) 700
i� 999 (b�) 750
i` 1.030 (b̀ ) 600
Total 2.050
Venta Tons.
Osorno (Ve) 600
Llanquihue (Vf) 400
P. Varas (Vg) 500
P. Montt (Vh) 700
Total 2.200
Costo ($) Osorno (Ve) Llanquihue (Vf) P. Varas (Vg) P. Montt (Vh)i� 950 (b�) 10.260 54.435 68.023 87.465
i� 999 (b�) 60.025 2.400 21.250 45.375
i` 1.030 (b̀ ) 93.080 40.872 16.900 3.220
ic Exter. (bc) 30.200 42.500 54.900 71.150
Ejemplo de Aplicación de Modelos de Redes Transporte
Optimización, Modelos de Redes, Mayo-2018 49
b	+�
b	+�
b	+`
P
+�
P
+�
P
+`
P
+c
:�Q� = 700 = ) �,
�+c
+�
:�Q� = 750 = ) �,
�+c
+�
:�Q` = 600 = ) `,
�+c
+�
j�Z� = 600 = ) 	,��+c	+�
j�Z� = 400 = ) 	,��+c	+�
j�Z` = 500 = ) 	,`�+`	+�
 	
<	
j�Zc = 700 = ) 	,c�+`	+�
n=3 Proveedores (i) (Salidas) m=4 Clientes(j) (Entradas)
:�Qc = ) j�Z
 − ) :�Q	�+`	+� = ) c,
�+c
+�
�+c
+� b	+c
Reformulación del problema con Exceso de Demanda
Optimización, Modelos de Redes, Mayo-2018 50
) 	,
 =�+c
+� :�Q	 � = 1 → 3 
Función Objetivo: 9�� :����� = ) ) <	,
�+c
+� 	,
�+c
	+�
Restricciones: i) Capacidad
) 	,
 =�+c	+� j�Z
 � = 1 → 4
ii) Demanda
iii) No Negatividad 	,
 ≥ 0 � = 1 → 4, j = 1 → 4
) c,
 =�+c
+� ) j�Z
 − ) :�Q	
�+`
	+�
�+c
+�
Reformulación del problema con Exceso de Demanda
Optimización, Modelos de Redes, Mayo-2018 51
Solución:
:����� = 10.260 600 + 54.435 0 + 68.023 0 + 87.465 100+60.025 0 + 2.400 400 + 21.250 350 + 45.375 0+93.080 0 + 40.872 0 + 16.900 0 + 3.220 600
+30.200 0 + 42.500 0 + 54.900 50 + 71.150(100)
= $33.151.750
��
��� 	,
 Osorno (Ve) Llanquihue (Vf) P. Varas (Vg) P. Montt (Vh) Total
i� 950 (b�) �,� = 600 �,� = 0 �,` = 100 �,c = 0 ) �,
 = 700�+c
+�
i� 999 (b�) �,� = 0 �,� = 400 �,` = 350 �,c = 0 ) �,
 = 750
�+c
+�
i` 1.030 (b̀ ) `,� = 0 `,� = 0 `,` = 0 `,c = 600 ) `,
 = 600
�+c
+�
ic Exter. (bc) c,� = 0 c� = 0 c,` = 50 c,c = 100 ) c,
 = 150
�+c
+�
Total ) 	,� = 600�+c	+� ) 	,� = 400
�+c
	+� ) 	,`
�+c
	+� = 500 ) 	,c
�+c
	+� = 700 ) ) 	,
 =
�+c
+�
�+`
	+� 2.200
Optimización Clase 19: Modelos de Redes
Anexo de Ejercicios
Ruta más corta de origen 1 a destino n
Ejercicio propuesto por profesor M. Rojas, U. Andes Optimización, Modelos de Redes, Mayo-2018 53
Suponga que la red corresponde a una pequeña parte de un pueblo, donde los nodos son los cruces entre
caminos y los arcos son los caminos que unen dichos cruces; suponga que usted conoce el valor exacto de
la distancia (en kilómetros) que existe entre un cruce y otro, dicho valor es �	
. Con �, �	 ∈ ^1,… , �_ (b.2)
a. Formule un modelo de optimización que le permita encontrar la ruta más corta desde el nodo 1 al nodo
�.
b. Suponga ahora que dado lo complejo de los caminos (algunos son de tierra, otros tienen barro, etc.)
usted en el tramo � # � puede andar a una velocidad W	
 (con �, �	 ∈ ^1,… , �_). Señale los cambios que
habría que hacerle al modelo en a) para que se permita encontrar esta vez la ruta más que le permite
llegar desde el nodo 1 al nodo n en el menor tiempo posible
1
n
Ruta más corta de origen 1 a destino n: Solución
Optimización, Modelos de Redes, Mayo-2018 54
a. Formule un modelo de optimización que le permita encontrar la ruta más corta desde el nodo 1 al nodo
�.
Definición de Variables:
�	
 = ]������ 0; 1 �	
 = 1 �� �� <��� �ó� ����� �� ���� �� ���5�� � <�� ������� � Q������<� � 
�� �
�� �� Z���Z� <���� �	
 = 0 �� �� <��� �ó� �� Q������<� � �
�� �� Z���Z� <���� 
Nodo 1:
��
�� ������� �� ������ (���) = ) ��,
�
+���
�� ������� �� �������(���) = 0
��
�� � ����� �� ������� v ��������(����) = +1
��� − ��� = ���� → ) ��,
�
+� = +1������<<�ó�: ��,� = 0
Ruta más corta de origen 1 a destino n: Solución
Optimización, Modelos de Redes, Mayo-2018 55
a. Formule un modelo de optimización que le permita encontrar la ruta más corta desde el nodo 1 al nodo
�.
Nodo T = f. . w # e:
��
�� ������� �� ������ (���) = ) �*,
�
+�
��
�� ������� �� �������(���) = ) �	,*�	+���
�� � ����� �� ������� v ��������(����) = 0
��� − ��� = ���� → ) �*,
 − ) �	,*�	+�
�
+� = 0
������<<�ó�: �*,* = 0
Ruta más corta de origen 1 a destino n: Solución
Optimización, Modelos de Redes, Mayo-2018 56
a. Formule un modelo de optimización que le permita encontrar la ruta más corta desde el nodo 1 al nodo
�.
Nodo w:
��
�� ������� �� ������ (���) = 0
��
�� ������� �� �������(���) = ) �	,��	+���
�� � ����� �� ������� v �������� ���� = −1
��� − ��� = ���� → − ) �	,��	+� = −1������<<�ó�: ��,� = 0
Función Objetivo:
9�� ������<�� = ) ) �	,
 · �	,
�
+�
�
	+�
�	,
 ]������ 0; 1 � = 1. . � � = 1. . �
Ruta más corta de origen 1 a destino n: Solución
Optimización, Modelos de Redes, Mayo-2018 57
b. Suponga ahora que dado lo complejo de los caminos (algunos son de tierra, otros tienen barro, etc.)
usted en el tramo � # � puede andar a una velocidad W	
 (con �, � ∈ {1, … , �}). Señale los cambios que
habríaque hacerle al modelo en a) para que se permita encontrar esta vez la ruta más que le permite
llegar desde el nodo 1 al nodo n en el menor tiempo posible
W���<���� = ������<�����ZQ� → ���ZQ� = ������<��W���<����
9�� ���ZQ� = ) ) �	,
 · �	,
W	,
�
+�
�
	+�
Función Objetivo:
Producción de ampolletas
Ejercicio propuesto por profesor M. Rojas, U. Andes Optimización, Modelos de Redes, Mayo-2018 58
Una empresa manufacturera produce ampolletas y las distribuye a 5 mayoristas a un precio de entrega de
$ 250 por unidad. Las proyecciones de ventas indican que las ventas para el próximo mes serán de 2.700,
2.600, 9.000, 4.500 y 3.600 ampolletas a los distribuidores mayoristas 1-5, respectivamente.
La compañía cuenta con tres plantas productivas de capacidades de producción de 5.500, 9.000 y 11.250
ampolletas en las plantas 1, 2 y 3, respectivamente. Los costos unitarios de producir cada ampolleta son $
200 en la planta 1, $ 100 en la planta 2 y $ 180 en la planta 3.
El costo de transporte de envío en $ por ampolleta desde una planta a un distribuidor mayorista se muestra
a continuación
Planta\Mayorista 1 2 3 4 5
Planta 1 $5 $7 $11 $15 $16
Planta 2 $8 $6 $10 $12 $15
Planta 3 $10 $9 $9 $10 $16
Formule un modelo de optimización que maximice la utilidad cumpliendo los requerimientos de demanda
de los mayoristas. (c.1)
Producción de ampolletas: Solución
Optimización, Modelos de Redes, Mayo-2018 59
Definición de Variables:
 	 = <������� �� �ZQ������� � Q���
<�� �� �� Q����� �; � = 1 Q����� 1; � = 2 Q����� 2; � = 3 Q����� 3�@	,�
 = <������� �� �ZQ������� � �����Q����� ����� �� Q����� � �� Z�v������ �; � = 1 Z�v������ 1;� = 2 Z�v������ 2; j = 3 mayorista 3; j = 4 mayorita 4; j = 5 mayorista 5
Grafo:
Producción de ampolletas: Solución
Optimización, Modelos de Redes, Mayo-2018 60
Equilibrios nodales y restricciones:
Nodo Planta 1 (P1)
��� = �@�,�� + �@�,�� + �@�,�` + �@�,�c + �@�,�n��� = 0���� = + ���� − ��� = ���� → �@�,�� + �@�,�� + �@�,�` + �@�,�c + �@�,�n = + �<�Q�<���� Q����� 1 → � ≤ 5.500
Nodo Planta 2 (P2)
��� = �@�,�� + �@�,�� + �@�,�` + �@�,�c + �@�,�n��� = 0���� = + ���� − ��� = ���� → �@�,�� + �@�,�� + �@�,�` + �@�,�c + �@�,�n = + �<�Q�<���� Q����� 2 → � ≤ 9.000
Producción de ampolletas: Solución
Optimización, Modelos de Redes, Mayo-2018 61
Equilibrios nodales y restricciones:
Nodo Planta 3 (P3)
��� = �@`,�� + �@`,�� + �@`,�` + �@`,�c + �@`,�n��� = 0���� = + `��� − ��� = ���� → �@`�� + �@`,�� + �@`,�` + �@`,�c + �@`,�n = + `<�Q�<���� Q����� 3 → ` ≤ 11.250
Nodo Mayorista 1 (M1)
��� = 0��� = �@�,�� + �@�,�� + �@`,������ − 2.700��� − ��� = ���� → 0 − �@�,�� − �@�,�� − �@`,�� = −2.700
Producción de ampolletas: Solución
Optimización, Modelos de Redes, Mayo-2018 62
Equilibrios nodales y restricciones:
Nodo Mayorista 2 (M2)
��� = 0
��� = �@�,�� + �@�,�� + �@`,������ − 2.600��� − ��� = ���� → 0 − �@�,�� − �@�,�� − �@`,�� = −2.600
Nodo Mayorista 3 (M3) ��� = 0��� = �@�,�` + �@�,�` + �@`,�`���� − 9.000
��� # ��� = ���� → 0 # �@�,�` − �@�,�` − �@`,�` = −9.000
Producción de ampolletas: Solución
Optimización, Modelos de Redes, Mayo-2018 63
Equilibrios nodales y restricciones:
Nodo Mayorista 4 (M4)
��� = 0
��� = �@�,�c + �@�,�c + �@`,�c���� − 4.500��� − ��� = ���� → 0 − �@�,�c − �@�,�c − �@`,�c = −4.500
Nodo Mayorista 5 (M5) ��� = 0��� = �@�,�n + �@�,�n + �@`,�n���� − 3.600��� − ��� = ���� → 0 − �@�,�n − �@�,�n − �@`,�n = −3.600
Producción de ampolletas: Solución
Optimización, Modelos de Redes, Mayo-2018 64
Función Objetivo y restricciones:
:���� Q���
<<�ó� = 200 � + 100 � − 180 ` :���� �����Q���� = ) ) �@	;�
 · <�	
n
+� 
`
	+�
9� }������� = 250 ) 	 − 200 � − 100 � − 180 ` − ) ) �@	;�
 · <�	
n
+� 
`
	+�
`
	+�
 	 ≥ 0 �@	,�
 ≥ 0 	 , �@	,�
∃� � = 1. . 3 � = 1. . 5
%�5����� Q�� P���� = 250 � + � + `
Ejemplo: Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 65
Chile Expreso es una empresa de logística que se dedica al transporte de encomiendas, para
lo cual cuenta con 2 centros de acopio donde se reciben los productos y 5 oficinas
comerciales las cuales entregan las encomiendas a los clientes.
Los centros de acopio de encomiendas se encuentran ubicados en las comuna de Lampa en
las inmediaciones del Aeropuerto SCL mientras que el segundo centro de acopio se localiza
en la comuna de Independencia el cual recibe las encomiendas desde los puertos de
Valparaíso y San Antonio. Las oficinas comerciales se encuentran ubicadas en las comunas
de Quilicura, Providencia, La Reina, Stgo. Centro y Maipú Tanto los centros de acopio como
las oficinas de ventas no pueden acumular encomiendas de un día para otro.
El requerimiento de encomiendas para el día Martes 6 de Octubre de 2015 indica lo siguiente:
200 encomiendas llegarán vía aérea al centro de acopio de Lampa, mientras que 500
encomiendas llegarán vía terrestre al centro de acopio de Independencia. Los
requerimientos de clientes para ese día son los siguientes: Providencia 150, La Reina 125,
Maipú 195, Quilicura 90, Stgo C. 140.
La Matriz de costo de transporte calibrada para el día Martes 6 de Octubre indica los
siguientes precios por ruta y no existe restricciones de capacidad de transporte por ruta.
Su misión es determinar la asignación de transporte de encomiendas de manera de poder
cumplir con los requerimientos de los clientes a mínimo costo considerando que no hay
restricciones de capacidad a través de la rutas de transporte ni de proceso de encomiendas
en los nodos (c.1)
Ejemplo: Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 66
$/Encomienda Independencia Providencia La Reina Maipu Lampa Quilicura Stgo. Centro
Independencia -- 2.800 -- -- -- 900 600
Providencia 2.750 -- 1.970 -- -- -- 750
La Reina -- 2.001 -- 4.150 -- -- 1.020
Maipu -- -- 4.001 -- 3.970 -- 4.120
Lampa -- -- -- 3.965 -- 2.950 4.125
Quilicura 895 -- -- -- 3.005 -- 2.005
Stgo. Centro 605 745 999 4.220 4.435 2.105 --
Proveedores bj
Independencia 500
Lampa 200
Clientes bj
Providencia -150
La Reina -125
Maipú -195
Quilicura -90
Stgo. Centro -140
Ejemplo de Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 67
Fenómeno a Estudiar: Minimización de costos totales de transporte mediante la
visualización de un Grafo que representa al problema, teniendo
en cuenta restricciones de capacidad de almacenaje y ventas,
cada centro de acopio y oficina de ventas es un nodo del grafo
Variables: 	,
 : Cantidad de encomiendas que se transportan desde el nodo
i con destino al nodo j
Parámetros: <	,
: Costo de transportar una encomienda desde el nodo i con
destino el nodo j
,
: Entradas/Salidas de flujos externos ya sea de Proveedores 
Externos o Clientes Externos
Ejemplo de Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 68
Independencia
Providencia
La Reina
Maipú
Lampa
Quilicura
Stgo. C.
1
2
3
4
5
6
7
 	
<	
Ejemplo de Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 69
Independencia
Lampa
Quilicura
Stgo. C.
1
5
6
7
 �,�
 �,� �,�
 �,� �,n n,�
,�Clientes Entradas de Flujo Interno Nodo Quilicura �,� + �,� + n,�
Salidas de Flujo Interno Nodo Quilicura
 �,� + �,� + �,n
Entradas/Salidas Externas a Quilicura
,� = #90
Equilibrio de flujos Neto Nodo Quilicura 
(Salidas-Entradas)
 �,� + �,� + �,n − �,� − �,� − n,� = ,� �,� + �,� + n,� −( �,� + �,� + �,n) + ,� = 0
Ejemplo de Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 70
Maipú
Lampa
Quilicura
Stgo. C.
4
5
6
7
Proveedores
,n
 n,�
 �,n �,n
 n,� n,c c,n
Entradas de Flujo Interno Nodo Lampa
 �,n + �,n + c,n
Salidas de Flujo Interno Nodo Lampa
 n,� + n,� + n,c
Entradas/Salidas Externas a Nodo Lampa
,n = +200
Equilibrio de flujos Neto Nodo Lampa 
(Salidas-Entradas)
 n,� + n,� + n,c − ( �,n + �,n + c,n) = ,n �,n + �,n + c,n + ,n − ( n,� + n,� + n,c) = 0
Ejemplo de Flujo de Red a Mínimo Costo
Optimización, Modelosde Redes, Mayo-2018 71
Nodo
Salidas de 
Flujo Interno
Entradas de
Flujo Interno
Entradas/Salidas 
Externas
Balance (SFI-EFI=E/SFE)
Independencia (1) �,� + �,� + �,� �,� + �,� + �,� ,� = +500 �,� + �,� + �,� − ( �,�+ �,� + �,�) = ,� = 500
Providencia (2) �,� + �,` + �,� �,� + `,� + �,� ,� = −150 �,� + �,` + �,� − �,� + `,� + �,� = ,� = −150
La Reina (3) `,� + `,c + `,� �,` + c,` + �,` ,` = −125 `,� + `,c + `,� − �,` + c,` + �,` = ,` = −125
Maipú (4) c,` + c,n + c,� `,c + n,c + �,c ,c = −195 c,` + c,n + c,� − `,c + n,c + �,c = ,c = −195
Lampa (5) n,c + n,� + n,� c,n + �,n + �,n ,n = +200 n,c + n,� + n,� − c,n + �,n + �,n = ,n = 200
Quilicura (6) �,� + �,n + �,� �,� + n,� + �,� ,� = −90 �,� + �,n + �,� − �,� + n,� + �,� = ,� = −90
Stgo. Centro (7)
 �,� + �,� + �,`+ �,c + �,n + �,� �,� + �,� + `,�+ c,� + n,� + �,� ,� = −140 �,� + �,� + �,` + �,c + �,n + �,�−( �,� + �,� + `,� + c,� + n,� + �,�) = ,� = −140
Equilibrios Nodales
Ejemplo: Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 72
Función Objetivo:
9�� :����� =
 �,�<�,� + �,�<�,� + �,�<�,� + �,�<�,� + �,�<�,� + �,�<�,� �,`<�,` + �,�<�,� + `,�<`,� + �,�<�,� `,c<`,c + `,�<`,� + c,`<c,` + �,`<�,` c,n<c,n + c,�<c,� + n,c<n,c + �,c<�,c n,�<n,� + n,�<n,� + �,n<�,n + �,n<�,n �,�<�,� + �,�<�,�
Restricciones: �,� + �,� + �,� − ( �,�+ �,� + �,�) = ,� = 500 
 �,� + �,` + �,� − �,� + `,� + �,� = ,� = −150 `,� + `,c + `,� − �,` + c,` + �,` = ,` = −125 
 c,` + c,n + c,� − `,c + n,c + �,c = ,c = −195 
 n,c + n,� + n,� − c,n + �,n + �,n = ,n = 200 
 �,� + �,n + �,� − �,� + n,� + �,� = ,� = −90 
 �,� + �,� + �,` + �,c + �,n + �,� − �,� + �,� + `,� + c,� + n,� + �,� = ,� = −140 
 	,
 ≥ 0 � = 1 → 7, j = 1 → 7
Ejemplo: Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 73
$/Encomienda Independencia Providencia La Reina Maipú Lampa Quilicura Stgo. Centro
Independencia 1.000.000 2.800 1.000.000 1.000.000 1.000.000 900 600
Providencia 2.750 1.000.000 1.970 1.000.000 1.000.000 1.000.000 750
La Reina 1.000.000 2.001 1.000.000 4.150 1.000.000 1.000.000 1.020
Maipú 1.000.000 1.000.000 4.001 1.000.000 3.970 1.000.000 4.120
Lampa 1.000.000 1.000.000 1.000.000 3.965 1.000.000 2.950 4.125
Quilicura 895 1.000.000 1.000.000 1.000.000 3.005 1.000.000 2.005
Stgo. Centro 605 745 999 4.220 4.435 2.105 1.000.000
Reformulando Matriz de Costos de rutas Directas 
El principio lógico detrás de asignar la unión virtual de dos nodos sin arcosa un valor de 1.000.000 tiene por
objetivo crear un modelo numérico generalizado en el cual debido al altísimo costo virtual de unir dos nodos, el
software considere que es tan poco viable de unir esos nodos que en la práctica no empleará como solución. Por
ejemplo para el software ir desde Independencia a Maipú de manera directa es tan excesivamente caro que de
todas formas más eficiente como alternativa mediante el tránsito por otros nodos y arcos como por ejemplo la ruta
descrita por Independencia-Stgo C-Maipú (600+4.220=4.820) o Independencia-Quilicura-Lampa-Maipú (7.870)
Ejemplo: Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 74
= ) 
,* �+�*+� � = 1 → Z = 7
Función Objetivo: 9�� :����� = ) ) <	,
�+�
+� 	,
�+�
	+�
Restricciones:
Salidas de Flujos desde el nodo j
No Negatividad N Enteros
 	,
 ≥ 0 � = 1 → � = 7, j = 1 → Z = 7 	,
 ∃ �
Entradas de Flujos hacia el nodo j = ) 	,
 �+�	+� � = 1 → Z = 7
Balanceo de Flujos Neto en nodo j = ) 
,* − ) 	,
 = ,
 �+�	+�
�+�
*+� � = 1 → Z = 7
Ejemplo: Flujo de Red a Mínimo Costo
Optimización, Modelos de Redes, Mayo-2018 75
Solución:
N Encomiendas Independencia Providencia La Reina Maipu Lampa Quilicura Stgo. Centro
Independencia �,� = 0 �,� = 0 �,` = 0 �,c = 0 �,n = 0 �,� = 85 �,� = 415
Providencia �,� = 0 �,� = 0 �,` = 0 �,c = 0 �,n = 0 �,� = 0 �,� = 0
La Reina `,� = 0 `,� = 0 `,` = 0 `,c = 0 `,n = 0 `,� = 0 `,� = 0
Maipú c,� = 0 c,� = 0 c,` = 0 c,c = 0 c,n = 0 c,� = 0 c,� = 0
Lampa n,� = 0 n,� = 0 n,` = 0 n,c = 195 n,n = 0 n,� = 5 n,� = 0
Quilicura �,� = 0 �,� = 0 �,` = 0 �,c = 0 �,n = 0 �,� = 0 �,� = 0
Stgo. Centro �,� = 0 �,� = 150 �,` = 125 �,c = 0 �,n = 0 �,� = 0 �,� = 0
:����� = $1.350.050
Ejemplo: Empresa exportadora
Optimización, Modelos de Redes, Mayo-2018 76
Una exportadora de fruta debe minimizar los costos asociados a la logística de transportar la fruta
producida en Chile en las localidades de Copiapó (CP) y Los Andes (LA) para llevarlas a destino final en
USA en las ciudades de Nueva York (NY), Long Beach (LB) y San Francisco (SF). La fruta producida en
Chile debe ser transportada en primer lugar vía terrestre desde el lugar de origen (CP y LA) con destino los
puertos de Caldera (CA) y Valparaíso (VP), luego es embarcada en buques refrigerados con destino los
puertos de Nueva York y Long Beach, a su vez también existe la posibilidad de transportar fruta vía
marítima entre ambos puertos Chilenos.
Finalmente, la fruta entregada en SF puede ser abastecida de manera terrestre tanto desde LB como
desde NY, destino en USA que también puede ser abastecido de manera terrestre desde SF. Los costos
asociados a transportar cada tonelada de fruta por sus respectivas rutas se detallan en la Tabla de Costos.
La demanda de fruta en USA según la ciudad de entrega queda determinada de la siguiente manera: NY
130 toneladas, LB 70 toneladas y SF 60 toneladas. Por otro lado, la cantidad de fruta producida en origen
queda determinada de la siguiente manera: Q� toneladas en CP y Q� toneladas en LA.
Las restricciones de capacidad indican que el puerto de CA puede recibir como máximo en su conjunto 100
tons de fruta transportada de manera terrestre, de manera análoga VP puede recibir como máximo en su
conjunto 200 tons de fruta transportada de manera terrestre, no existiendo restricciones de capacidad si la
fruta llega en barco entre ambos puertos chilenos.
Por otro lado, el puerto de NY puede recibir como máximo en su conjunto 180 tons. de fruta desde Chile,
mientras que LB puede recibir en su conjunto como máximo 115 tons de fruta Chilena.
Ejemplo: Empresa exportadora
Optimización, Modelos de Redes, Mayo-2018 77
Origen/Destino
(US$/Ton)
CP
(1)
LA
(2)
CA
(3)
VP
(4)
NY
(5)
LB
(6)
SF
(7)
Copiapó (1) -- -- 4 4,5 -- -- --
Los Andes (2) -- -- 5 3,5 -- -- --
Caldera (3) -- -- -- 1,8 7,1 6,9 --
Valparaíso (4) -- -- 1,7 -- 6,8 6,4 --
Nueva York (5) -- -- -- -- -- -- 3,7
Long Beach (6) -- -- -- -- -- -- 0,7
San Francisco (7) -- -- -- -- 3,6 -- --
b. Si en los puertos de Caldera y Valparaíso se producen pérdidas equivalentes a un 3 y 1% de la fruta 
recibida tanto por vía terrestre como marítima respectivamente, reformule los equilibrios nodales de 
ambos nodos (CA y VP) de manera de poder afrontar este problema (c.1)
Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 78
Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 79
i) Nodo Copiapó (1) 
��� = ��,` + ��,c				��� = 0				���� � �� → ��,` ! ��,c � ��
ii) Nodo Los Andes (2) 
��� � ��,` ! ��,c						��� � 0					���� � �� → ��,` ! ��,c � ��
iii) Nodo Caldera (3) 
��� � �̀ ,c ! �̀ ,n ! �̀ ,�					��� � ��,` ! ��,` ! �c,`					���� � 0
→ �̀ ,c ! �̀ ,n ! �̀ ,� #	��,` # ��,` # �c,` � 0	
iv) Nodo Valparaíso (4) 
��� � �c,` ! �c,n ! �c,�					��� � ��,c ! ��,c ! �̀ ,c					���� � 0
→ �c,` ! �c,n ! �c,� 	# 	��,c # ��,c # �̀ c` � 0	
Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 80
v) Nodo Nueva York (5) vi) Nodo Long Beach (6) 
vii) Nodo San Francisco (7) 
��� = �n,�				��� = �̀ ,n + �c,n + ��,n						���� = #120	
→ 	�n,� # �̀ ,n # �c,n # ��,n � #120
��� � ��,�			��� � �̀ ,� !�c,�				���� � #70	
→ 	��,� # �̀ ,� ! �c,� � #70	
��� � ��,n					��� � �n,� ! ��,�			���� � #60		
→ 		 ��,n # �n,� # ��,� � #60Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 81
- Restricciones de capacidad portuaria 
iii) Nodo Nueva York (5) 
i) Nodo Caldera (3) 
���(���������) = ��,` + ��,` ≤ 100
ii) Nodo Valparaíso (4) ���(���������) = ��,c + ��,c ≤ 200 
���(��
�� :������) = �̀ ,n + �c,n + ��,n ≤ 180
iv) Nodo Long Beach (6) ���(��
�� :������) = �̀ ,� +�c,� ≤ 115
- Costos de Transporte
i) Costo de transporte terrestre Chile 4��,` + 4,5��,c + 5��,` + 3,5��,c
ii) Costo de transporte terrestre USA 3,7�n,� + 0,7��,� + 3,6��,n
Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 82
- Costos de Transporte
iii) Costo de transporte marítimo interno Chile 1,8�̀ ,c + 1,7�c,`
iv) Costo de transporte marítimo Chile-USA 7,1�̀ ,n + 6,9�̀ ,� + 6,8�c,n + 6,4�c,�
- Tipo de Variable��,`, ��,c, ��,`, ��,c, �n,�, ��,�, ��,n, �̀ ,c, �c,`, �̀ ,n, �̀ ,�, �c,n, �c,� ≥ 0
Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 83
b. Si en los puertos de Caldera y Valparaíso se producen pérdidas equivalentes a un 3 y 1% de la fruta 
recibida tanto por vía terrestre como marítima respectivamente, reformule los equilibrios nodales de 
ambos nodos (CA y VP) de manera de poder afrontar este problema
i) Nodo Caldera con pérdidas (3) 
��� = �̀ ,c + �̀ ,n + �̀ ,� + �̀ ,@				��� = ��,` + ��,` + �c,`					���� = 0 → �̀ ,c ! �̀ ,n ! �̀ ,� ! �̀ @ #	��,` # ��,` # �c,` � 0				
�̀ @ � 0,03 ��,` ! ��,` ! 0,01�c,`
Empresa Exportadora: Solución
Optimización, Modelos de Redes, Mayo-2018 84
ii) Nodo Valparaíso con pérdidas (4) 
��� = �c,` + �c,n + �c,� + �c,@ ��� = ��,c + ��,c + �̀ ,c ���� = 0 → �c,` + �c,n + �c,� + �c,@ − ��,c − ��,c − �̀ c` = 0 
�c@ = 0,03 ��,c + ��,c + 0,01�̀ ,c