Tema_6_Optimización de Redes O1

Vista previa del material en texto

1
Tema 6
Optimización de Redes
Investigación de Operaciones - 1
2
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
3Investigación de Operaciones 1
1. Introducción
Una red o grafo es una representación gráfica basada en una serie de puntos
conectados con líneas. Los puntos suelen representarse con círculos o cuadrados,
y reciben el nombre de NODOS o vértices. Las líneas que los unen se suelen
denominar ARCOS o aristas.
Una red permite representar las relaciones que hay entre componentes de un
sistema.
Tiene muchas aplicaciones. Por ejemplo, los modelos de transporte son casos
particulares de redes.
nodos
arcos
4Investigación de Operaciones 1
Hito i Hito j
Actividad desarrollada entre 
ambos hitos:
nodo
nodo
1. Introducción
5Investigación de Operaciones 1
Arco dirigido: Arco con flujo en una sola dirección
1
2
4
5
3
Arco no dirigido: Arco con flujo en ambas direcciones
1
2
4
5
3
1. Introducción
6
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
7Investigación de Operaciones 1
2. PROBLEMA DE LA RUTA MÁS CORTA
Dada una red, los arcos tienen información de la distancia entre los nodos
(longitudes, tiempos, costes,…).
Se desea encontrar la ruta más corta entre un nodo de origen y otro de destino.
Los arcos pueden ser dirigidos o no.
Veámoslo con un ejemplo. Se desea encontrar la ruta más corta entre el origen
1 y el nodo 7. Los valores de los arcos es la distancia entre nodos.
1
2
3
4 5
6
7
>
>
8Investigación de Operaciones 1
Hito i
Localización i
Hito j:
Localización j
Actividad desarrollada entre 
ambos hitos:
desplazamiento de i a j
2. PROBLEMA DE LA RUTA MÁS CORTA
9Investigación de Operaciones 1
Hay muchos algoritmos. Los más populares: Dijkstra y Floyd.
También se puede modelizar como un PPL y resolverlo con el simplex, que es lo
que veremos aquí.
Definimos las variables binarias
𝑥𝑖𝑗 = ቊ
1, 𝑠𝑖 𝑒𝑙 𝑎𝑟𝑐𝑜 𝑖, 𝑗 𝑒𝑠𝑡á 𝑒𝑛 𝑙𝑎 𝑟𝑢𝑡𝑎
0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
Es como un problema de transporte entre sólo un origen y sólo un destino, con el
resto de nodos como posibles puntos de transbordo. El coste de transporte entre
nodos 𝑐𝑖𝑗 es la distancia, y la cantidad transportada, 𝑥𝑖𝑗 , es sólo 1 ó 0.
𝑐12 = 2
𝑐15 = 5
𝑐13 = 4
𝑐34 = 𝑐43 = 1
⋮
𝑐57 = 7
𝑐67 = 7
Costes de transporte
10Investigación de Operaciones 1
La forma más apropiada para analizar
una red es analizando el balance de
flujo en cada nodo.
En términos de flujo, la regla es: FLUJO DE ENTRADA=FLUJO DE SALIDA
Cada nodo debe cumplir unas reglas de balance de flujo, que dependen del tipo
de problema que se quiera resolver, y que son intuitivas. Se obtiene así una
restricción de balance por cada nodo.
Básicamente, los nodos de una red en las que se desea encontrar una ruta 
óptima deben cumplir que si se llega a un nodo también se ha de salir, salvo 
para los nodos de origen y destino. De esta forma, los nodos que participen en 
la solución estarán conectados formando un ‘camino dirigido’.
El flujo en un problema de ruta óptima es 𝑥𝑖𝑗 = 1 𝑜 0
• El nodo origen tiene un flujo de entrada de 1
• El nudo de salida tiene un flujo de salida de 1
11Investigación de Operaciones 1
Nodo 1:
• Flujo de entrada= 1
• Flujo de salida= 𝑥12 + 𝑥13 + 𝑥14
1
Flujo de entrada=Flujo de salida
1 = 𝑥12 + 𝑥13 + 𝑥14
También se suele usar la convención de que el flujo es:
• Negativo si es de entrada
• Positivo si es de salida
Y en este tipo de problema el flujo neto es cero, es decir
Flujo total=Suma de flujos=0
Flujos negativos (entradas) +Flujos positivos (salida)=0
En el nodo 1 se tiene entonces:
−1 + 𝑥12 + 𝑥13 ++𝑥14 = 0 ⇒ 𝑥12 + 𝑥13 + 𝑥14 = 1
Ambos tipos de cálculo son equivalentes
1
1
12Investigación de Operaciones 1
nodo 1: 𝑥12 + 𝑥13 + 𝑥14 − 1 = 0 ⇒ 𝑥12 + 𝑥13 + 𝑥14 = 1
nodo 2: 𝑥24 + 𝑥27 − 𝑥12 = 0
nodo 3: 𝑥34 − 𝑥43 + 𝑥36 − 𝑥13 = 0
nodo 4: 𝑥45 − 𝑥54 + 𝑥46 − 𝑥64 + 𝑥43 − 𝑥34 − 𝑥14 − 𝑥24 = 0
nodo 5: 𝑥57 + 𝑥56 − 𝑥65 + 𝑥54 − 𝑥45 − 𝑥25 = 0
nodo 6: 𝑥65 − 𝑥56 + 𝑥67 − 𝑥36 + 𝑥64 − 𝑥46 = 0
nodo 7: −𝑥67 − 𝑥57 + 1 = 0 ⇒ 𝑥67 + 𝑥57 = 1
(Nos imaginamos que un nodo es como un reloj. Nos ponemos a las 12 y lo recorremos en sentido horario)
La F.O. es la misma que en el planteamiento de tabla de transporte: minimizar la
distancia del trayecto.
min𝑍 = 2𝑥12 + 4𝑥13 + 5𝑥14 + 2𝑥24 + 7𝑥25 + 𝑥34 + 4𝑥36
+𝑥43 + 4𝑥45 + 3𝑥46 + 4𝑥54 + 𝑥56 + 5𝑥57 + 3𝑥64 + 𝑥65 + 7𝑥67
13Investigación de Operaciones 1
Distancia mínima: 13
No hay una 
solución única
Sale coste
13, pero otra
solución
óptima (es
múltiple)
14Investigación de Operaciones 1
PROBLEMA
Los nodos de la red siguiente muestra un conjunto de ciudades. Los arcos tienen el
tiempo que se tarda en ir de una ciudad a otra. Encuentra la ruta más corta para ir del
nodo 1: ‘B’ham’, al nodo 11: ‘Va Bch’ . Los arcos tienen también la valoración, en
puntos (pts), como ciudades de interés turístico. Encuentra la ruta entre ambas
ciudades que maximice el interés turístico.
15Investigación de Operaciones 1
2. PROBLEMA DE LA RUTA MÁS CORTA
Existen otras aplicaciones del problema de la ruta más corta que no están
relacionadas con distancias. Pueden ser, por ejemplo costos. Por ejemplo,
problemas de reemplazo de equipo
Se desea establecer una política óptima de reemplazo para una flota de automóviles
en un horizonte de planeación de 4 años. Al inicio de cada año, un automóvil se
reemplaza o se conserva en operación durante un año más. Un automóvil debe
estar en servicio de 1 a 3 años. La siguiente tabla proporciona el costo de reemplazo
como una función del año en que se adquiere un automóvil y los años en operación.
16Investigación de Operaciones 1
El problema puede formularse como una red en la que los nodos 1 a 5 representan el
inicio de los años 1 a 5 (eventos o hitos). Los arcos representan la actividad de
comprar en un nodo y vender en el otro.
Hito i: 
año i
Hito j: 
año j
Actividad desarrollada entre 
ambos hitos:
Compro en i y vendo en j
17Investigación de Operaciones 1
El problema puede formularse como una red en la que los nodos 1 a 5 representan el
inicio de los años 1 a 5. Los arcos a partir del nodo 1 (año 1) pueden llegar a los
nodos 2, 3 y 4 porque un automóvil puede estar en operación de 1 a 3 años. Los
arcos a partir de los demás nodos pueden interpretarse del mismo modo. La longitud
de cada arco es igual al costo de reemplazo. La solución del problema es equivalente
a determinar la ruta más corta entre los nodos 1 y 5.
𝑥𝑖𝑗 = ቊ
1, 𝑠𝑖 𝑒𝑙 𝑎𝑟𝑐𝑜 𝑖, 𝑗 𝑒𝑠𝑡á 𝑒𝑛 𝑙𝑎 𝑟𝑢𝑡𝑎
0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
𝑥𝑖𝑗 = ቊ
1, 𝑐𝑜𝑚𝑝𝑟𝑎𝑚𝑜𝑠 𝑢𝑛 𝑎𝑢𝑡𝑜 𝑒𝑙 𝑎ñ𝑜 𝑖 𝑦 𝑙𝑜 𝑟𝑒𝑛𝑜𝑣𝑎𝑚𝑜𝑠 𝑒𝑙 𝑎ñ𝑜 𝑗
0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
18Investigación de Operaciones 1
F.O.: Minimizar el coste de emplear los vehículos durante los 5 años
min𝑍 = 4000𝑥12 + 5400𝑥13 + 9800𝑥14 + 4300𝑥23 + 6200𝑥24 + 8700𝑥25
+4800𝑥34 + 7100𝑥35 + 4900𝑥45
19Investigación de Operaciones 1
Restricciones: flujo total en cada nodo nulo
nodo 1: 𝑥14 + 𝑥13 + 𝑥12 − 1 = 0
nodo 2: 𝑥23 + 𝑥24 + 𝑥25 − 𝑥12= 0
nodo 3: 𝑥35 + 𝑥34 − 𝑥23 − 𝑥13 = 0
nodo 4: 𝑥45 − 𝑥24 − 𝑥23 − 𝑥14 = 0
nodo 5: 1 − 𝑥25 − 𝑥45 − 𝑥35 = 0
𝑥𝑖𝑗 ∈ {0,1}
20Investigación de Operaciones 1
21Investigación de Operaciones 1
PROBLEMA
Rehaga el problema anterior con los siguientes cambios:
• Los autos deben mantenerse en servicio al menos dos años.
• La vida de servicio máxima d los autos es de 5 años.
• El horizonte de planificación abarca desde el principio del año 1 al final del año 5
(inicio del año 6).
• Los costes son:
22
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
23Investigación de Operaciones 1
La primera fase de un proyecto es la de planificación, la cual consiste en:
• Identificar cuáles serán las tareas que deberán ejecutarse para llevarlo a
cabo.
• Establecer su interrelación.
• Estimar su tiempo,
• Estimar sus recursos.
• Calcular el tiempo de ejecución del proyecto y
• Establecer un plan.
Las tareas son temporales (tienen principio y fin) y consumen recursos. Para la
gestión temporal de un proyecto se utiliza las llamadas metodologías CPM y
PERT. Una de las diferencias entre los sistemas CPM y PERT se da en la forma
de efectuar la estimación de los tiempos para las actividades. El CPM hace una
estimación única, es decir lo hace con un criterio determinístico, mientras que el
PERT efectúa una estimación ponderada, con un criterio probabilístico.
Haremos uso en primer lugar de la estimación determinística (CPM).
3. Red de un proyecto
Proyecto: conjunto de actividades interrelacionadas orientadas a alcanzar la
metas deseada .
24Investigación de Operaciones 1
3. Red de un proyecto. Análisis CPM
25Investigación de Operaciones 1
Ejemplo
Supongamos un proyecto muy simple de mantenimiento de un equipo que
consiste en la ejecución de las siguientes tareas, cuyo tiempo de
realización, y actividades precedentes se indican a continuación:
Act. Descripción
TIEMPO
(hs)
PREDECESORAS
A Desinstalar un motor de su base 2 -
B Limpiar la base 4 A
C Pintar la base 8 B
D Extraer las piezas X e Y del motor 3 A
E Rectificar la pieza X 4 D
F Rebobinar la pieza Y 6 D
G Alinear la pieza Y 3 E
H Ensamblar X e Y 5 F, G
I Instalar el motor en la base 3 C, H
26Investigación de Operaciones 1
GRAFICACIÓN DE LA RED DE UN PROYECTO
Existen dos métodos de graficar los proyectos. El primero de ellos es el denominado
"FLECHA-ACTIVIDAD", que fue el utilizado inicialmente por el sistema PERT, y que
consiste en evidenciar a las actividades en flechas. El otro método, desarrollado por el
sistema CPM, es el denominado "NODO-ACTIVIDAD" que consiste en representar a las
actividades en nodos. Aquí usaremos el método flecha-actividad
Método Flecha-Actividad
Las flechas representan a las actividades del proyecto y los nodos representan
eventos o hitos. Los eventos, también llamados hitos, sucesos o acontecimientos,
establecen estados en la ejecución del proyecto, los que se verifican básicamente como
consecuencia de comienzos y finalizaciones de actividades. Cada actividad queda
representada mediante un nodo inicio (dispuesto en la cola de la flecha) y un nodo fin
(dispuesto en la punta de la flecha). La siguiente es la representación de una actividad A
que dura 5 unidades de tiempo
A(5)1 2
A(5)
1 2
3. Red de un proyecto. Análisis CPM
27Investigación de Operaciones 1
Cada nodo se numera con un código único. No es necesario que la numeración
sea correlativa. Es deseable que, para una actividad cualquiera, el código origen sea un
número menor que el código fin. El siguiente gráfico indica que la actividad A queda definida
por los nodos 1 y 2, por lo que se la puede llamar actividad (1,2). Del mismo modo la
tarea B es la 2-3. No puede haber dos actividades con la misma definición (𝑖, 𝑗)
A(5)
1 2
B(3)
3
En este ejemplo el nodo 1 indica que puede comenzar a ejecutarse la actividad A,
mientras que el nodo 2 indica que la actividad A ha terminado de llevarse a cabo y que
puede comenzar a desarrollarse la tarea B. Finalmente, el nodo 3 muestra que la
tarea B ha finalizado. La actividad B no puede comenzar hasta que haya terminado la A.
La A es predecesora de la B
Los nodos a la izquierda de cada actividad no representan necesariamente los tiempos de
inicio de las actividades, sino los tiempos a partir de los cuales las actividades pueden
empezar. Análogamente, los nodos de la derecha no representan necesariamente el
instante en el que acaban, sino que para ese instante ya habrán acabado.
3. Red de un proyecto. Análisis CPM
28Investigación de Operaciones 1
A un nodo pueden concurrir varias actividades:
A(5)1
2
B(3)
3
4
C(1)
D(8)
Los nodos 1,2 y 3 representan los hitos en los que las actividades A,B y C pueden comenzar,
pero no implica necesariamente que tengan que comenzar justo en ese instante, ni que lo
hagan simultáneamente. Igualmente, el nodo 4 representa el hito en el que las actividades
A,B y C se encuentran terminadas, pero no implica necesariamente que tengan que terminar
en ese preciso instante ni que lo tengan que hacer simultáneamente, lo que es comprensible
al no tener la misma duración.
3. Red de un proyecto. Análisis CPM
A, B y C son 
actividades 
‘concurrentes’
29Investigación de Operaciones 1
A un nodo pueden concurrir varias actividades, y un nodo puede generar 
también varias actividades:
A(5)1
2
B(3)
3
4
C(1)
El suceso (evento, instante,…) 4 queda definido
cuando han finalizado todas las actividades que
concurren a él
D(8)
Para que comience la actividad D, deben
haber terminado A,B y C. Estas tres
actividades son predecesoras de D.
E(5)A, B y C son 
actividades 
‘concurrentes’
D y E son 
actividades 
‘concurrentes’
3. Red de un proyecto. Análisis CPM
30Investigación de Operaciones 1
Existe software específico para este tipo de tareas. El más popular es el Visio (Microsoft).
Opciones gratuitas: Dia, Diagramly, LucidChart, Openoffice…
1 2 3
4 5 6
7
A(5) B(4)
D(3) E(4) G(4)
F(6)
I(3)C(8)
8
H(5)
31Investigación de Operaciones 1
Diagramly. Se puede usar on-line. Su web es draw.io
3. Red de un proyecto. Análisis CPM
32Investigación de Operaciones 1
A veces es necesario definir actividades "ficticias“ para poder representar la interrelación
entre evento.
Ocurre, por ejemplo, cuando actividades concurrentes tienen diferentes actividades
predecesoras.
Supongamos que la actividad A precede inmediatamente a D y E, y que la actividad B
precede inmediatamente a D, E y F ¿Es correcta esta representación?
1
3
2
4
5
6
A
B
D
E
F
Esta representación asume que A y B
son predecesoras de los tres
33Investigación de Operaciones 1
1
3
2
4
5
6
A
B
D
E
F
Para salvar este
inconveniente se utiliza el
recurso de incluir una
actividad ficticia (que se
grafica en forma punteada),
como se indica a
continuación. Así se facilita
la representación de la
relación de precedencias.
1 3
2
5
6
7
A
B
D
E
F
4
actividad ficticia
No es correcta
porque asume que A
precede también a
F, lo que no es
cierto.
Supongamos que la actividad A precede inmediatamente a D y E, y que la actividad B
precede inmediatamente a D, E y F ¿Es correcta esta representación?
34Investigación de Operaciones 1
También es necesario usar actividades ficticias cuando varias actividades comparten los
mismos nodos de origen y destino. Supongamos que la actividad A precede
inmediatamente a D y E, y que la actividad B precede inmediatamente a D, E y F ¿Es
correcta esta representación?
1 2
A
B
Esta representación no es válida, pues cada actividad debe quedarperfectamente definida
por los códigos de los nodos inicio y fin. Ambas serían la actividad (1,2). En este caso, la
variable 𝑥12 podría corresponder a la actividad A o a la B.
1 3
A
B
2
Esta sería la
presentación
correcta
C
C
35Investigación de Operaciones 1
Ejemplo
Código Tarea Precedente
A Desarmar motor -
B Cambiar carbones A
C Rebobinar motor A
D Rebobinar estator A
E Armar el motor B,C,D
36Investigación de Operaciones 1
Ejemplo
Código Tarea Precedente
A Desarmar motor -
B Cambiar carbones A
C Rebobinar motor A
D Rebobinar estator A
E Armar el motor B,C,D
1 2
4
5
3
6
A
B
C
D
E
37Investigación de Operaciones 1
Ejemplo Un editor firmó un contrato con un autor para publicar un libro
de texto. El autor somete a consideración una copia impresa de un archivo de
computadora del manuscrito. Las actividades (simplificadas) asociadas con la
producción del libro de texto se resumen en la siguiente tabla.
38Investigación de Operaciones 1
Ejemplo Un editor firmó un contrato con un autor para publicar un libro
de texto. El autor somete a consideración una copia impresa de un archivo de
computadora del manuscrito. Las actividades (simplificadas) asociadas con la
producción del libro de texto se resumen en la siguiente tabla.
39Investigación de Operaciones 1
Ejemplo
Los cimientos de un edificio pueden completarse en cuatro secciones
consecutivas. Las actividades de cada sección incluyen (1) cavar; (2)
colocar el acero, y (3) verter el concreto.
El cavado de una sección no puede iniciarse hasta que se haya
completado el de la sección precedente. La misma restricción se aplica al
vertido del concreto. Desarrolle la red del proyecto.
El cavado de cada sección dura 4 días, colocar el acero, 5 días, y verter el
concreto 2 días.
40Investigación de Operaciones 1
Ejemplo
Los cimientos de un edificio pueden completarse en cuatro secciones
consecutivas. Las actividades de cada sección incluyen (1) cavar; (2)
colocar el acero, y (3) verter el concreto.
El cavado de una sección no puede iniciarse hasta que se haya
completado el de la sección precedente. La misma restricción se aplica al
vertido del concreto. Desarrolle la red del proyecto.
El cavado de cada sección dura 4 días, colocar el acero, 5 días, y verter el
concreto 2 días.
41Investigación de Operaciones 1
Ejemplo
42Investigación de Operaciones 1
Ejemplo
43Investigación de Operaciones 1
Ejemplo
44Investigación de Operaciones 1
45Investigación de Operaciones 1
Ejemplo
46Investigación de Operaciones 1
Ejemplo
47Investigación de Operaciones 1
3. Red de un proyecto. Análisis CPM
48Investigación de Operaciones 1
RUTA CRÍTICA
Secuencia de actividades
críticas. Es la secuencia más
larga de la red, que determina
su duración total. Por esa razón,
cualquier demora en las
actividades de esta ruta crítica
afectan a la duración del
proyecto
Actividad no crítica: se tiene un espacio de
tiempo mayor que su duración para programar
su ejecución. Se tiene, por tanto, holgura en su
programación. Cierto retraso en su ejecución no
compromete la duración total del proyecto
Actividad crítica: aquella que su tiempo de
inicio y terminación están predeterminados, en
el sentido de que cualquier modificación de
estos tiempos retrasa todo el proyecto
Una vez que tenemos el proyecto en forma de red, pasamos a 
analizar su duración.
49Investigación de Operaciones 1
Ejemplo
En un caso sencillo, la ruta
crítica se puede obtener por
simple inspección.
Duración del proyecto: 8 + 15 + 2 + 5 + 6 + 3 = 39
Las actividades B y F no son críticas. Hay holgura para su programación.
50Investigación de Operaciones 1
Hay varios algoritmos para calcular la ruta más larga. La ruta crítica puede
resolverse planteando un PPL igual que en el calculo de la ruta más corta, pero
maximizando la duración del trayecto.
𝑥𝑖𝑗 = ቊ
1, 𝑠𝑖 𝑒𝑙 𝑎𝑟𝑐𝑜 𝑖, 𝑗 𝑒𝑠𝑡á 𝑒𝑛 𝑙𝑎 𝑟𝑢𝑡𝑎
0, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
max𝑍 = 8𝑥12 + 15𝑥23 + 11𝑥24 + 2𝑥35 + 5𝑥56 + 6𝑥67 + 8𝑥68 + +3𝑥79
Los arcos ficticios (4,3) y (8,9) tienen duración nula
51Investigación de Operaciones 1
max𝑍 = 8𝑥12 + 15𝑥23 + 11𝑥24 + 2𝑥35 + 5𝑥56 + 6𝑥67 + 8𝑥68 + 3𝑥79
s.a:
• nodo 1: 𝑥12 = 1
• nodo 2: 𝑥23 + 𝑥24 − 𝑥12 = 0
• nodo 3: 𝑥35 − 𝑥43 − 𝑥23 = 0
• nodo 4: 𝑥43 − 𝑥24 = 0
• nodo 5: 𝑥56 − 𝑥35 = 0
• nodo 6: 𝑥67 + 𝑥68 − 𝑥56 = 0
• nodo 7: 𝑥79 − 𝑥67 = 0
• nodo 8: 𝑥89 − 𝑥68 = 0
• nodo 9: −𝑥89 − 𝑥79 = −1
52Investigación de Operaciones 1
53Investigación de Operaciones 1
3. Red de un proyecto. Análisis CPM
54Investigación de Operaciones 1
Localizamos el margen que tienen las actividades no críticas
Tareas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 Críticas
A
B
C
D
E
F
G
H
Esta actividad tiene holgura
Esta actividad tiene holgura
Podemos hacer un cronograma. En primer lugar fijamos las duraciones
de las actividades críticas.
Las actividades críticas aparecen escalonadas una a continuación de la otra
Podemos colocar las tareas no críticas asumiendo, por ejemplo, que
empiezan lo antes posible, y así visualizar fácilmente las holguras.
55Investigación de Operaciones 1
Tareas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 Críticas
A
B
C
D
E
F
G
H
Esta actividad tiene holgura
Esta actividad tiene holgura
holgura
holgura 
Existen técnicas (sencillas) para gestionar las holguras, especialmente en el
caso de que varias tareas no críticas sean consecutivas. En esos casos, las
holguras de una tarea dependen de si la anterior tarea consume o no sus
holguras, y a su vez condicionan las holguras de las tareas subsiguientes.
56
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
57Investigación de Operaciones 1
Método de la trayectoria crítica (CPM): Se basa en que se conoce la duración de cada
actividad. Con esas duraciones se calcula la ruta crítica.
Método PERT: Si la duración de las actividades no se conocen con certeza y se utiliza
para estimar la probabilidad de que el proyecto se complete en una fecha específica.
4. Análisis PERT de un proyecto
Para cada actividad, PERT requiere que el administrador de proyecto estime tres
cantidades siguientes:
𝒂𝒊𝒋= estimación de la duración de la actividad (i,j) en las condiciones más favorables.
𝒃𝒊𝒋=estimación de la duración de la actividad (i,j) en las condiciones menos favorables.
𝒎𝒊𝒋=valor más ‘probable’ (moda) para la duración de la actividad (i,j).
Se basa en suponer que la duración de la
tarea (i,j), 𝐷𝑖𝑗 , es una variable aleatoria
que sigue una distribución Beta en el
intervalo (a,b), de moda m.
función Beta(2,5,3,8)
a b
m 𝜇
58Investigación de Operaciones 1
4. Análisis PERT de un proyecto
función Beta(2,5,3,8)
𝑎𝑖𝑗 𝑏𝑖𝑗𝑚𝑖𝑗 𝜇𝑖𝑗
Entonces, según la teoría estadística, se cumple de forma aproximada que:
Duración media de la actividad (𝑖, 𝑗)
𝜇𝑖𝑗 = 𝐸(𝐷𝑖𝑗) =
𝑎 + 4𝑚 + 𝑏
6
Varianza de la duración de la
actividad (𝑖, 𝑗)
𝜎𝑖𝑗
2 = 𝑉𝑎𝑟 𝐷𝑖𝑗 =
𝑏 − 𝑎 2
36
59Investigación de Operaciones 1
Si tengo una ruta formada por una secuencia de tareas, cuyas duraciones asumo
independientes unas de otras, la duración de la ruta será la suma de las duraciones, y
media y la varianza de dicha ruta serán
𝜇𝑅 =෍
(𝑖,𝑗)
𝜇𝑖𝑗 𝜎𝑅
2 =෍
(𝑖,𝑗)
𝜎𝑖𝑗
2𝐷𝑅 =෍
(𝑖,𝑗)
𝐷𝑖𝑗
Se suele también asumir que, al ser 𝐷𝑅 una suma de variables aleatorias, por el
teorema del límite central 𝐷𝑅 ∼Normal.Entonces:
𝐷𝑅 ∼ 𝑁 𝜇𝑅; 𝜎𝑅
2
Si la ruta R es el camino crítico, con este
resultado se puede calcular la probabilidad
de que el proyecto se termine antes de un
tiempo T
𝑃(𝐷𝑅 < 𝑇)
𝜇𝑅 𝑇
60Investigación de Operaciones 1
Ejemplo ¿Cuál es la probabilidad de terminar este proyecto antes de 35 días?
Actividad 𝑎𝒊𝒋 𝑏𝒊𝒋 𝑚𝒊𝒋
(1,2) 5 13 9
(1,3) 2 10 6
(3,5) 3 13 8
(3,4) 1 13 7
(4,5) 8 12 10
(5,6) 9 15 12
1
3
2 4 5 6
La ruta crítica es: 1 → 2 → 3 → 4 → 5 → 6
Actividad 𝑎𝒊𝒋 𝑏𝒊𝒋 𝑚𝒊𝒋 𝝁𝒊𝒋 𝝈𝒊𝒋
(1,2) 5 13 9 9 1.78
(1,3) 2 10 6 6 1.78
(3,5) 3 13 8 8 2.78
(3,4) 1 13 7 7 4.00
(4,5) 8 12 10 10 0.44
(5,6) 9 15 12 12 1.00
𝜇𝑅= 9+0 +7+10 +12 =38
𝜎𝑅
2=1.78 + 0 +4 +0.44+1 = 7.22
𝑃(𝐷𝑅 < 35 días) = 0.13
61
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
62Investigación de Operaciones 1
5. Problemas de transporte y transbordo
▪ Un problema de transporte puede representarse mediante una red (ver Tema de
transporte), donde:
o Nodos: puntos hacia los que se envían los bienes o desde donde se
envían.
o Arcos: caminos, rutas o conexione entre los nodos.
O1
O2
O3
D1
D3
D2
T1
T2
63Investigación de Operaciones 1
Un problema de transporte ‘sin
trasbordo’ considera transportes ‘directos’
desde los nodos de origen a los nodos de
destino con el fin de cubrir la demanda a
partir de la oferta de los nodos de origen.
O1
O2
O3
D1
D3
D2
En los problemas de transbordo se
permite que haya flujo hacia nodos
intermedios que no sean el destinatario final
de las cantidades que se transportan. En
ese caso, se habla de transbordo entre
nodos. Los puntos por los que pasa ese flujo
de transbordo se denominan puntos de
transbordo.
O1
O2
O3
D1
D3
D2
T1
T2
orígenes
destinos
destinos
orígenes
puntos de 
transbordo
5. Problemas de transporte y transbordo
64Investigación de Operaciones 1
5. Problemas de transporte y transbordo
Hay tres tipos de nodos
▪ Nodos o puntos de suministro
▪ Nodos o puntos de demanda
▪ Nodos o puntos de transbordo
O1
O2
O3
D1
D3
D2
T1
T2
destinos
orígenes
puntos de 
transbordo
Puntos de suministro:
Se envían bienes a otros puntos,
pero no reciben bienes
Puntos de demanda:
Se reciben bienes de otros
puntos, pero no envían bienes
Puntos de transbordo:
Pueden recibir y enviar bienes. El balance puede ser
nulo (envían todo lo que reciben), positivo (se
quedan con una parte de lo que reciben - demandan
bienes- el resto lo transfieren), o negativo (una parte
de lo que envían lo suministran ellos, el resto es
transbordo ‘puro’ procedente de otros puntos)
65Investigación de Operaciones 1
En un caso muy general, también los puntos de origen y de destino podrían ser utilizados como puntos de
transbordo. Puede haber, por ejemplo, flujo de destino a origen, origen a origen, o destino a destino.
Virtualmente, todos los puntos podrían admitir transbordo. Todos los puntos serían de transbordo.
O1
O2
O3
D1
D3
D2
T1
T2
5. Problemas de transporte y transbordo
66Investigación de Operaciones 1
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-300
+80
+100
+60
+170
+70
5. Problemas de transporte y transbordo
Usamos números negativos, junto a los nodos, para representar suministro (entradas a
la red) y positivos para representar demanda (salidas de la red):
• Negativo si es de entrada
• Positivo si es de salida
En general, los números
en el interior de los
nodos sólo representan
su numeración, que se
utilizará para etiquetar
los arcos. El arco que
une el nodo i con el j es
el arco (i,j)
Sobre los arcos, ponemos el valor asociado a dicho arco, y puede ser coste, tiempo,
distancia, etc. Lo denotaremos por 𝑐𝑖𝑗
67Investigación de Operaciones 1
5. Problemas de transporte y transbordo
Hito i
Localización i
Hito j:
Localización j
Actividad desarrollada entre ambos hitos:
transporte de bienes en cantidad 𝑥𝑖𝑗
con coste 𝑐𝑖𝑗
Definimos la variable de decisión:
𝑥𝑖𝑗: cantidad a ser transportadas desde el nodo i al nodo j
𝑐𝑖𝑗
En general, 𝑥𝑖𝑗 ≥ 0
Pero podríamos tener 𝐿𝑖𝑗 ≤ 𝑥𝑖𝑗 ≤ 𝑈𝑖𝑗
capacidad del arco
flujo mínimo
68Investigación de Operaciones 1
• Cada nodo debe cumplir con unas reglas de balance de flujo.
• Si el problema de transporte esta balanceado o equilibrado, se imponen restricciones
que obliguen a suministrar toda la oferta y cubrir toda la demanda. En ese caso:
FLUJO DE ENTRADA=FLUJO DE SALIDA
y con el criterio de signos (-entrada; +salida):
Flujo total=Suma de flujos=0
Flujos negativos (entrada) +Flujos positivos (salida)=0
• ¿Y si no está balanceado?
Dos opciones:
Opción 1: Se siguen usando restricciones que fuercen a suministrar toda la demanda
y cubrir toda la oferta, pero se equilibra el problema poniendo orígenes o
destinos ficticios.
Opción 2: Se modifican las reglas de balance de flujo. Sólo se satisface oferta y
demanda hasta que se pueda. Hay que relajar algunas restricciones.
69Investigación de Operaciones 1
Una conocida compañía automovilística fabrica autos de lujo en Alemania, y los
transporta por barco hasta los puertos de Newark y Jacksonville (J’ville) , en Estados
Unidos.
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-300
+80
+100
+60
+170
+70
Ejemplo
De estos puertos, los autos
son transportados a las
diferentes ciudades de
acuerdo a la siguiente
figura.
Se desea determinar la
manera más económica de
transportar los autos desde
los puertos de Newark y
J’ville hasta las ciudades que
los necesiten.
(Usando la primera opción: balanceando)
70
4. Problemas de transporte y transbordo• La oferta de autos es de 200+300=500. La demanda es de 100+60+170+80+70=480. 
El problema de transporte no está balanceado, pues sobran 20 autos. 
• Para balancearlo creamos un punto de demanda ficticio con demanda 20 autos (*). Lo
unimos directamente a los puntos de suministro, con coste de transporte nulo
(físicamente no se transporta nada, por lo que no ganamos nada uniéndolo a los
transbordos, cuyos arcos sí tienen coste).
$0
$0
(*) Otra opción, menos popular, sería asignarle al destino ficticio una demanda arbitrariamente grande, con un coste de transporte también
muy grande, de manera que la solución use sólo la cantidad mínima de ese nodo ficticio para que el problema sea factible. En esta opción,
las restricciones que involucren a ese nodo no pueden ser de igualdad.
punto de demanda 
ficticio 
71Investigación de Operaciones 1
Nodo 1: −200 + 𝑥18 + 𝑥14 + 𝑥12 = 0Veamos el detalle
de algunos nodos
72Investigación de Operaciones 1
Nodo 2: −𝑥12 + 𝑥23 + 100 = 0
73Investigación de Operaciones 1
• Nodo 1: −200 + 𝑥18 + 𝑥14 + 𝑥12 = 0
• Nodo 2: −𝑥12 + 𝑥23 + 100 = 0
• Nodo 3: −𝑥23 − 𝑥53 + 𝑥35 + 60 = 0
• Nodo 4: −𝑥14 − 𝑥74 − 𝑥54 + 80 = 0
• Nodo 5: 𝑥54 − 𝑥75 + 𝑥56 − 𝑥65 − 𝑥35 + 𝑥53 + 170 = 0
• Nodo 6: 𝑥65 − 𝑥56 − 𝑥76 + 70 = 0
• Nodo 7: −300 + 𝑥76 + 𝑥75 + 𝑥74 + 𝑥78 = 0
• Nodo 8: 20 − 𝑥78 − 𝑥18 = 0
min𝑍 = 30𝑥12 + 40𝑥14 + 50𝑥23 + 35𝑥35 + 40𝑥53 + 30𝑥54 + 35𝑥56
+25𝑥65 + 50𝑥74 + 45𝑥75 + 50𝑥76 (+0𝑥18 + 0𝑥78)
La función objetivo busca minimizar los costes de transporte.
74Investigación de Operaciones 1
70
75Investigación de Operaciones 1
Partimos del mismo problema
anterior, pero con algunos
cambios:
• J’ville sólo suministra 200.
• Boston demanda 200.
• Richmond es ahora punto
de transbordo, con arco
dirigidohacia el nodo 5.
• El arco 57 sólo admite un
transporte máximo de 100
unidades
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-200
+200
+60
+170
+70
Ejemplo (Usando la primera opción: balanceando)
76Investigación de Operaciones 1
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-200
+200
+60
+170
+70
• La oferta es 400, y la demanda de 200+60+170+70=500. Faltan 100 autos.
• Colocamos un punto de oferta ficticio, que suministra 100 autos, justo la cantidad
para que se equilibre (*).
Ficticio
8
-100
(*) otra opción es asignarle una oferta arbitrariamente grande, con un coste de transporte también muy grande, de manera que la
solución use sólo la cantidad mínima de ese nodo ficticio para que el problema sea factible. En esta opción, las restricciones que
involucren a ese nodo no pueden ser de igualdad.
77Investigación de Operaciones 1
Nodo 1: −200 + 𝑥14 + 𝑥12 = 0
Nodo 2: 200 − 𝑥12 + 𝑥23 − 𝑥82 = 0
Nodo 3: −𝑥23 − 𝑥53 + 𝑥35 + 60 − 𝑥83 = 0
Nodo 4: −𝑥14 − 𝑥74 + 𝑥45 = 0
Nodo 5: −𝑥45 − 𝑥75 + 𝑥56 − 𝑥65 + 170 − 𝑥85 − 𝑥35 + 𝑥_53 = 0
Nodo 6: 𝑥65 − 𝑥56 − 𝑥76 + 70 − 𝑥86 = 0
Nodo 7: −200 + 𝑥76 + 𝑥75 + 𝑥74 = 0
Nodo 8: 𝑥82 + 𝑥83 + 𝑥85 + 𝑥86 − 100 = 0
Capacidad (7,5): 𝑥75 ≤ 100
𝑥𝑖𝑗 ≥ 0
F.O: min𝑍 = 40𝑥14 + 30𝑥12 + 50𝑥23 + 35𝑥35 + 30𝑥45 + 35𝑥56
+40𝑥53 + 25𝑥65 + 50𝑥76 + 45𝑥75 + 50𝑥74
78Investigación de Operaciones 1
El reparto de menor costo de la oferta disponible pasa por suministrar 60 autos
menos al nodo 3 (toda su demanda) y 40 autos menos al nodo 6
79Investigación de Operaciones 1
Otra forma de modelizar una red de un problema de transporte no balanceado
• Si el problema no está balanceado se puede interpretar como que
hay un exceso de oferta o de demanda.
• En ese caso, se toman dichos valores (los de demanda o los de oferta;
los que estén en exceso) como cotas superiores y no cantidades
exactas.
• En ese caso, al hacer el balance de flujo en los nodos implicados
(puntos con exceso de oferta o demanda) el balance de flujo no se
hace con ‘=‘ sino con ‘≤’ o ‘≥’.
• De esta forma, aunque sea imposible suministrar toda la oferta, o
satisfacer toda la demanda, se busca transportar el mayor número de
bienes posible al menor costo.
(la segunda opción)
80Investigación de Operaciones 1
Si hay exceso de oferta
𝑥14 + 𝑥12 ≤ 200 ⇒ 𝑥14 + 𝑥12 − 200 ≤ 0
En todos los nodos que tengan suministro, el balance es negativo pues tomamos menos de lo 
que nos ofrecen. El flujo negativo (entrada) es mayor que el positivo (salida). Por eso el balance 
(suma de flujos con su signo) es negativo.
El exceso de suministro hace que éste no
pueda ser transportado en su totalidad.
Lo que sale del nodo será menor que todo
lo que puede entrar.
Flujo total≤ 𝟎
En el resto de los nodos, el balance de flujo sigue siendo cero. El ‘problema’ se ha 
resuelto ya en los nodos de origen, y no se transmite al resto de la red.
entra al nodo
sale del nodo
81Investigación de Operaciones 1
Si hay exceso de demanda
En todos los nodos en los que haya demanda, el balance de
flujo es positivo. El flujo saliente (positivo) es mayor que el
entrante (negativo). La suma de flujos es positiva.
No se puede cubrir toda la demanda. Por
tanto, lo que entra al nodo será menor que
todo lo que pueda salir.
𝑥12 ≤ 𝑥23 + 200 ⇒ −𝑥12 + 𝑥23 + 200 ≥ 0
entra al nodo
sale del nodo
Flujo total≥ 𝟎
En el resto de los nodos, el flujo total es cero. 
82Investigación de Operaciones 1
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-300
+80
+100
+60
+170
+70
Ejemplo
La oferta de autos es de 
200+300=500. 
La demanda es de 
100+60+170+80+70=480. 
Sobran 20 autos. 
Vamos resolver el mismo
problema que antes
hicimos balanceando con
nodos ficticios.
En los puntos donde haya suministro, el balance será negativo
83Investigación de Operaciones 1
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-300
+80
+100
+60
+170
+70
Nodo 1: 𝑥14 + 𝑥12 ≤ 200
⇒ 𝑥12 + 𝑥14 − 200 ≤ 0
Nodo 7: 𝑥74 + 𝑥75 + 𝑥76 ≤ 300
⇒ 𝑥74 + 𝑥75 + 𝑥76 − 300 ≤ 0
No podemos aceptar en la red
todos los autos, pues sobran.
Por tanto, los que salgan del
nodo 1 (𝑥12 + 𝑥14), serán menos
que los que ofrezcan (200)
No podemos aceptar en la red
todos los autos, pues sobran.
Por tanto, los que salgan del
nodo 7 (𝑥74 + 𝑥75 + 𝑥76), serán
menos que los que ofrezcan
(300)
84Investigación de Operaciones 1
• Nodo 1: −200 + 𝑥14 + 𝑥12 ≤ 0
• Nodo 2: −𝑥12 + 𝑥23 + 100 = 0
• Nodo 3: −𝑥23 − 𝑥53 + 𝑥35 + 60 = 0
• Nodo 4: −𝑥14 − 𝑥74 − 𝑥54 + 80 = 0
• Nodo 5: 𝑥54 − 𝑥75 + 𝑥56 − 𝑥65 − 𝑥35 + 𝑥53 + 170 = 0
• Nodo 6: 𝑥65 − 𝑥56 − 𝑥76 + 70 = 0
• Nodo 7: −300 + 𝑥76 + 𝑥75 + 𝑥74 ≤ 0
min𝑍 = 30𝑥12 + 40𝑥14 + 50𝑥23 + 35𝑥35 + 40𝑥53 + 30𝑥54 + 35𝑥56
+25𝑥65 + 50𝑥74 + 45𝑥75 + 50𝑥76
La función objetivo es la misma y busca minimizar los costes de transporte.
En los nodos en los que no hay oferta,
el balance de flujo es cero
85Investigación de Operaciones 1
Sale lo mismo que cuando lo resolvimos balanceando.
86Investigación de Operaciones 1
Resolvemos ahora el problema que se expuso antes, con exceso de demanda.
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-200
+200
+60
+170
+70
Ejemplo
La oferta es 400, y la
demanda es de
200+60+170+70=500.
Hay un exceso de
demanda de 100 autos.
En los nodos donde hay
demanda, el balance
será positivo
87Investigación de Operaciones 1
Newark
1
Boston
2
Columbus
3
Atlanta
5
Richmond
4
J'ville
7
Mobile
6
$30
$40
$50
$35
$40
$30
$35
$25
$50
$45 $50
-200
-200
+200
+60
+170
+70
Nodo 2: 𝑥12 ≤ 200 + 𝑥23
⇒ 200 − 𝑥12 + 𝑥23 ≥ 0
Nodo 3: 𝑥23 + 𝑥53 ≤ 60 + 𝑥35
⇒ −𝑥23 − 𝑥53 + 𝑥35 + 60 ≥ 0
Nodo 5: 𝑥45 + 𝑥75 + 𝑥65 + 𝑥35 ≤
𝑥56 + 𝑥53 + 170
⇒ −𝑥45 − 𝑥75 + 𝑥56 − 𝑥65 + 170
− 𝑥85 − 𝑥35 + 𝑥53 ≥ 0
Nodo 6: 𝑥76 + 𝑥56 ≤ 𝑥65 + 70 ⇒ 𝑥65 − 𝑥56 − 𝑥76 + 70 ≥ 0
No seremos capaces de suministrar toda la demanda,
pues faltan autos. Por tanto, los que entren al nodo 2
(𝑥12), serán menos que los que se demandan (200)
88Investigación de Operaciones 1
Nodo 1: −200 + 𝑥14 + 𝑥12 = 0
Nodo 2: 200 − 𝑥12 + 𝑥23 ≥ 0
Nodo 3: −𝑥23 − 𝑥53 + 𝑥35 + 60 ≥ 0
Nodo 4: −𝑥14 − 𝑥74 + 𝑥45 = 0
Nodo 5: −𝑥45 − 𝑥75 + 𝑥56 − 𝑥65 + 170 − 𝑥35 + 𝑥53 ≥ 0
Nodo 6: 𝑥65 − 𝑥56 − 𝑥76 + 70 ≥ 0
Nodo 7: −200 + 𝑥76 + 𝑥75 + 𝑥74 = 0
Capacidad (7,5): 𝑥75 ≤ 100
𝑥𝑖𝑗 ≥ 0
F.O: min𝑍 = 40𝑥14 + 30𝑥12 + 50𝑥23 + 35𝑥35 + 30𝑥45 + 35𝑥56
+40𝑥53 + 25𝑥65 + 50𝑥76 + 45𝑥75 + 50𝑥74
Los nodos que no tienen demanda, tienen balance de flujo nulo.
89Investigación de Operaciones 1
Sale igual que en el caso en el que se
balanceaba con un origen ficticio
90
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
91Investigación de Operaciones 1
6. Problemas de flujo máximo
En este tipo de problemas, el objetivo es determinar la máxima cantidad de flujo que
puede circular por una red, desde un vértice origen (fuente) a un vértice destino
(sumidero). Además, se determinará el flujo que debe circular por cada arco para
conseguir el óptimo.
Hito i
Localización i
Hito j:
Localizaciónj
Actividad :
Flujo en cantidad 𝑥𝑖𝑗
por el arco de capacidad 𝑐𝑖𝑗
𝑐𝑖𝑗
𝐿𝑖𝑗 ≤ 𝑥𝑖𝑗 ≤ 𝑐𝑖𝑗
capacidad del arco
flujo mínimo
92Investigación de Operaciones 1
Ejemplo La compañía PetroPerú opera un campo petrolífero y una refinería en el
norte. El crudo es llevado de los pozos a la refinería a través de la red
que se muestra en la figura. Cada arco muestra la cantidad de crudo que
puede circular como máximo (miles de barriles por hora).
Campo 
petrolífero
Estación
de bombeo 1 
Refinería1
2
3
4
5
6
6
4
3
6
4
5
2
2
Estación
de bombeo 2 
Estación
de bombeo 3 
Estación
de bombeo 4 
La compañía quiere
determinar la cantidad
máxima de crudo que
puede hacer circular
cada hora, y cómo
debe hacerlo.
93Investigación de Operaciones 1
Se puede resolver como un problema de transbordo con restricciones de capacidades
máximas en los arcos. Para ello, añadimos un arco de retorno desde el sumidero a la
fuente, sin restricción de capacidad. Asignamos una demanda de 0 a cada nodo, e
intentamos maximizar el flujo en el arco de retorno (max 𝑧 = 𝑥61).
Campo 
de 
petróleo
Refinería1
2
3
4
5
6
6
4
3
6
4
5
2
2
+0 +0
+0
+0
+0
+0
𝒙𝟔𝟏
𝒙𝟏𝟐
𝒙𝟐𝟒
𝒙𝟒𝟔
𝒙𝟓𝟔
𝒙𝟑𝟓
𝒙𝟏𝟑
𝒙𝟐𝟓
𝒙𝟑𝟒
94Investigación de Operaciones 1
Dos tipo de restricciones:
• balance de flujo de cada nodo: Suma de flujo=0.
• capacidades de cada arco (y, si hubiese, límites inferiores)
Campo 
de 
petróleo
Refinería1
2
3
4
5
6
6
4
3
6
4
5
2
2
+0 +0
+0
+0
+0
+0
𝒙𝟔𝟏
𝒙𝟏𝟐
𝒙𝟐𝟒
𝒙𝟒𝟔
𝒙𝟓𝟔
𝒙𝟑𝟓
𝒙𝟏𝟑
𝒙𝟐𝟓
𝒙𝟑𝟒
95Investigación de Operaciones 1
Campo 
de 
petróleo
Refinería1
2
3
4
5
6
6
4
3
6
4
5
2
2
+0 +0
+0
+0
+0
+0
𝒙𝟔𝟏
𝒙𝟏𝟐
𝒙𝟐𝟒
𝒙𝟒𝟔
𝒙𝟓𝟔
𝒙𝟑𝟓
𝒙𝟏𝟑
𝒙𝟐𝟓
𝒙𝟑𝟒
max𝑍 = 𝑥61
Nodo 1: 𝑥12+ 𝑥13− 𝑥61 = 0
Nodo 2: 𝑥24+ 𝑥25− 𝑥12 = 0
Nodo 3: 𝑥34+ 𝑥35− 𝑥13 = 0
Nodo 4: 𝑥46− 𝑥34− 𝑥24 = 0
Nodo 5: 𝑥56− 𝑥35− 𝑥25 = 0
Nodo 6: 𝑥61− 𝑥56− 𝑥46 = 0
0 ≤ 𝑥12 ≤ 6
0 ≤ 𝑥13 ≤ 4
0 ≤ 𝑥24 ≤ 3
0 ≤ 𝑥25 ≤ 2
0 ≤ 𝑥34 ≤ 2
0 ≤ 𝑥35 ≤ 5
0 ≤ 𝑥46 ≤ 6
0 ≤ 𝑥56 ≤ 4
0 ≤ 𝑥61 ≤ ∞
96Investigación de Operaciones 1
Campo 
de 
petróleo
Refinería1
2
3
4
5
6
6
4
3
6
4
5
2
2
+0 +0
+0
+0
+0
+0
𝒙𝟔𝟏
𝒙𝟏𝟐
𝒙𝟐𝟒
𝒙𝟒𝟔
𝒙𝟓𝟔
𝒙𝟑𝟓
𝒙𝟏𝟑
𝒙𝟐𝟓
𝒙𝟑𝟒
Si se pudiese aumentar la capacidad de los arcos, ¿cuáles serían las prioridades? (mira los precios duales)
97
Tema 6 
Optimización de Redes
Investigación de Operaciones - 1
El contenido de este tema está
extraído parcialmente del Cap.
6 del libro ‘Investigación de
Operaciones’ de Taha, y del
Cap. 4 del libro Investigación
de Operaciones, de César
Angulo.
1. Introducción
2. Problema de la ruta más corta
3. Red de un proyecto. Análisis CPM
4. Análisis PERT de un proyecto
5. Problemas de transporte y transbordo
6. Problemas de flujo máximo
7. Problemas de árboles de expansión mínima
98Investigación de Operaciones 1
7. Problemas de árbol de expansión mínima
Un árbol es una red, no dirigida, con todos los puntos conectados (conexo) y sin
ciclos.
Un árbol de expansión es un árbol que cubre todos los vértices. Una red puede
tener muchos árboles de expansión
El problema del árbol de expansión mínima consiste en determinar un conjunto
de arcos que conecte todos los nodos de una red de forma que la longitud total
de los arcos sea mínima.
Al ser un árbol, no existirán ciclos.
Algunas aplicaciones:
• Redes de transporte
• Red de carreteras
• Redes de comunicación
• Cableados
99
Un grafo puede tener 
muchos árboles de 
expansión
El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos,
los mas conocidos son el de Prim y el de Kruskal. Ambos usan técnicas ‘voraces’ (greedy).
Un algoritmo voraz es aquel que, para resolver un determinado problema, elige la opción óptima en cada paso
local con la esperanza de llegar a una solución general óptima. En general, el uso de una técnica voraz no
garantiza que la solución encontrada sea el óptimo global pero, en el caso de los algoritmos de Kruskal y Prim se
puede probar que efectivamente es así.
También se puede usar PL, pero es muy poco eficiente por el problema de evitar los ciclos: necesita de un número
muy elevado de restricciones.
100Investigación de Operaciones 1
7. Problemas de árbol de expansión mínima
Algoritmo de Prim
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un
nodo inicial arbitrario al que se le van agregando sucesivamente nodos cuya
distancia a los anteriores es mínima.
En cada paso, se busca el arco más corto que conecte a un nuevo nodo con el árbol.
el nodo que se incorpora al árbol es aquel que se encuentra menor distancia del
árbol.
101Investigación de Operaciones 1
102Investigación de Operaciones 1
7. Problemas de árbol de expansión mínima
Algoritmo de Kruskal
Inicialmente se ordenan las aristas por su peso.
A continuación se van eligiendo las aristas de menor peso (los epates se
resuelven de forma arbitraria) de modo tal que no formen ciclo con las aristas
anteriormente seleccionadas.
103Investigación de Operaciones 1
6. Problemas de árbol de expansión mínima