unidad 2

CONTENIDO
INTRODUCCIÓN 3
UNIDAD 2: ANÁLISIS DE REDES 4
2.1 Conceptos Básicos. 4
2.2 Problema de transporte. 4
2.3 Problema de asignación. 5
2.4 Problema de la ruta más corta. 8
2.5 Administración de proyectos (PERT-CPM). 13
CONCLUSIÓN 15


INTRODUCCIÓN
Muchas situaciones de Investigación de Operaciones pueden modelarse y resolverse como redes (nodos conectados por ramas).
Lasolución de estas situaciones se logra por medio de varios algoritmos de optimización de redes.
Se presentan cuatro de estos algoritmos:
1) Algoritmo del problema de transporte.
2) Algoritmo del problema de asignación.
3) Algoritmo del problema de la ruta más corta.
4) Algoritmo para la administración de proyectos (PERT-CPM).

UNIDAD 2: ANÁLISIS DE REDES
2.1 Conceptos Básicos.
En una red detransporte, las ciudades representan nodos y los caminos representan ramas, mientras que el tráfico representa el flujo en las ramas.
En general, el flujo en una rama, está limitada por su capacidad que puede ser finita o infinita.
Se dice que una rama está dirigida u orientada si permite un flujo positivo en una dirección y cero flujo en la dirección opuesta.
La notación para describir una red Ges: G= (N, A), donde N es el conjunto de nodos y A es el conjunto de ramas.
Ejemplo:
N= {1,2,3,4,5}
A= {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}

2.2 Problema de transporte.
Es un problema de optimización de redes donde debe determinarse como hacer llegar los productos desde los puntos de existencia hasta los puntos de demanda minimizando los costos de envío.
Este método ha sidoaplicado a algunos problemas de negocios, tales como: el control y diseño de plantas de fabricación, determinación de territorios de ventas y localización de centros de distribución y almacenaje.
Ejemplo:
Tres plantas generadoras de energía eléctrica, con capacidades de 25, 40 y 30 000 kw/h, suministra electricidad a 3 ciudades cuyas demandas máximas son de 30, 35 y 30 000 kw/h. El costo en unidadesmonetarias de la venta de corriente eléctrica a las diferentes ciudades por miles de kw es como sigue:


Ciudad (j= Destino)
Oferta


1
2
3

Planta (i= Origen)
1

600

700

400
25







2

320

300

350
40







3

500

480

450
30






Demanda
30
35
30

Forma tabular del Método de Transporte
2.3 Problema de asignación.
Estosproblemas tratan de asignar trabajadores a distintas tareas, considerando los tiempos que tardan en desempeñarlas, teniendo como objetivo minimizar el tiempo total.
Hillier & Lieberman mencionan que el problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos que se destinan a la realización de tareas. Por ejemplo, los asignados pueden serempleados a quienes se tiene que dar trabajo. La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no tienen que ser personas. También pueden ser maquinas, vehículos o plantas, o incluso periodos a los que se asignan tareas.
Para que se ajuste a la definición de un problema de asignación, es necesario que este tipo de aplicaciones seformule de manera tal que se cumplan los siguientes supuestos.
1) El número de asignados es igual al número de tareas.
2) A cada asignado se le concede sólo una tarea.
3) Cada tarea debe ser realizada sólo por un asignado (aunque algunas veces no es posible cumplir con este criterio).
4) Existe un costos Cij asociado con al asignado i (i = 1, 2, 3,…., n) que realiza la tarea j (j = 1, 2,…., 3).
5)El objetivo es determinar cómo deben hacerse las “n” asignaciones para minimizar los costos totales.
Un algoritmo especial para los problemas de asignación.
Los problemas de asignación pueden ser resueltos por el método simplex, sin embargo existe un algoritmo más eficiente para resolver este tipo de problemas, el cual, es conocido como el “método húngaro” porque fue desarrollado por...