TAREAAS

INSTITUTO TECNOLÓGICO SUPERIOR DE CALKINI EN EL
ESTADO DE CAMPECHE

INVESTIGACIÓN DE OPERACIONES II

INGENIERÍA INDUSTRIAL

7A

NOMBRE

MATRICULA

NÚMERO ASIGNADO

Ayil Canul Eysi Delba

1711

2

Cauich Chan Rosa María

1719

5

Moo Couoh Ana Bertha

1712

Urcid Vázquez Alma Rosa

1740

16

Calkini, camp., a 20 de septiembre del 2010.
1

INDICEObjetivos……………………………………………………………………………………3

5.1 Terminología…………………………………………………………………………..4

5.2 Problema de la ruta más corta……………………………………………………..10

5.3 Problema de árbol de mínima expansión…………………………………………19

5.4 Problema de flujo máximo………………………………………………………….29

5.5 Problema de flujo de costo mínimo……………………………………………….34

5.6 Uso de software……………………………………………………………………..45Bibliografía…………………………………………………………………………….....47

2

OBJETIVOS

•

Conocer conceptos como nodos, arcos, redes, rutas, flujos, etc., que serán utilizados
a lo largo de la unidad en la solución de problemas de redes.

•

Ser capaces de desarrollar ejercicios de redes, que incluyen los de árbol de
expansión mínima, problemas de la ruta más corta, algoritmo de flujo máximo, y
algoritmo de costo mínimo.•

Tener la capacidad de entender y explicar a los compañeros cada uno de los temas
asignados.

3

4

INTRODUCCIÓN

En el siguiente se trataran acerca de lo que son los nodos, los arcos y de cómo estos se
relacionan para formar una red y de la relación de que tienen para algún tipo de flujo,
hablaremos acerca de la notación para describir las redes que son (N, A), en donde N esel
conjunto de nodos y A es el conjunto de arcos.

5

5.1 TERMINOLOGÍA

Muchos problemas de optimización importantes se analizan mejor por medio de una
representación grafica o de red. En este capítulo, se consideran cuatro modelos específicos
de red: problemas de trayectoria más corta, problemas de flujo máximo, modelos de
programación de proyecto CPM-PERT y problemas de árbol deexpansión mínima, para
los que existen procedimientos de soluciones eficientes. También se estudian problemas de
redes en flujo mínimo o costo mínimo (FMOCM), de los cuales los problemas de transporte,
asignación, transbordo, trayectoria más corta, flujo máximo, y los modelos de programación
de proyecto CPM, son casos especiales. Por último, se analiza una generalización del
simplex detransporte, el simplex de red, que se puede utilizar para resolver problemas de
flujo de red de costo mínimo. El capitulo comienza con algunos términos básicos utilizados
para describir graficas y redes.

DEFINICIONES BASICAS
Una grafica, o red, se define mediante dos conjuntos de símbolos: nodos y arcos. Primero
se define, se define un conjunto (llámelo v) de puntos extremos o vértices. Losvértices de
una grafica o red también se llaman nodos.
También se define un conjunto de arcos A.

Un ARCO consiste en un par ordenado de puntos extremos y representa una posible
dirección de movimiento que podría ocurrir entre puntos extremos(o vértices).

Para los fines que aquí se persiguen, si una red contiene un arco (j, k), entonces el
movimiento es posible del nodo j al nodo k. suponga quelos nodos 1, 2, 3 y 4 de la figura 1
representa ciudades y cada arco representa una carretera (de un solo sentido) que enlaza
dos ciudades. Para esta red, V= [1, 2, 3, 4] Y A= [(1,2), (2,3),(3,4),(4,3),(4,1)]. Para el arco (j,
k), el nodo j es el nodo inicial y el nodo k es el nodo terminal. Se dice que el arco (j, k) va
del nodo jal nodo k.
Por consiguiente, el arco (2,3) tiene el nodoinicial 2 y el nodo terminal 3, y va del nodo 2 al
nodo 3. El arco (2,3) se podría viajar de la ciudad 2 a la ciudad 3. En la figura 1, los arcos
muestran que se permite viajar de la ciudad 3 a la ciudad 4 y de la ciudad 4 a la ciudad 3,
pero que viaje entre las otras ciudades podría ser en un solo sentido.
Después, se estudia con frecuencia un grupo o conjunto de arcos. Las definiciones...