INGENIERÍA EN SISTEMAS COMPUTACIONALES

Materia:

INVESTIGACION DE OPERACIONES Semestre-Grupo:

3-°A

Producto Académico:

RESUMEN Tema:

Redes y programacion lineal

UNIDAD 2

Presenta:

ROSAS ESCOBEDO JOSE ANGELCAMARA JIMENEZ RAMON

BARRIENTOS HERNANDEZ ELIAZERVERDEJO HERNADEZ EDGAR MIGUEL

ZAMUDIO VALERIO JORGE JOSUE

Docente:

ING: GUSTAVO ALONSO ZAMUDIO

H. Y G. ALVARADO, VER. 10 DE NOVIEMBRE 2012

INSTITUTO TECNOLOGICO SUPERIORDE ALVARADO

Resumen

Red

Se entiende como un grupo de individuos que, en forma agrupada o individual, se relacionan con otros con un fin especifico, caracterizado por la existencia de flujos de información. Las redes pueden tener muchos o pocos actores y una o más clases de relaciones entre pares de actores. Una red se compone, por tanto, de tres elementos básicos los cuales son: nodos o actores, vínculos o relaciones y, flujos.

NODOS O ACTORES:

Son las personas o grupos de personas que se encuentran en torno a un objetivo en común. Usualmente los nodos o actores se representan por círculos. La suma de todos los nodos representa el tamaño de la red.

VÍNCULO O RELACIONES:

Son los lazos que existen entre dos o más nodos. En una red de amistad, por ejemplo, un actor muestra un vínculo directo con otro actor. Los vínculos o relaciones se representan con líneas.

GRAFOS NO DIRIGIDOS

Si los pares que forman las relaciones no son pares ordenados, entonces el lazo (na,nb) entre dos nodos es exactamente la misma que (nb,na), es decir, no hay un origen y un destino de la relación. Este tipo de relaciones son simétricas o no direccionales. Por ejemplo, la relación es hermano de es de este tipo.

2.4 Problema de la ruta más corta

El problema de la ruta más corta tiene que ver con la determinación de las ramas conectadas en una red de transporte que constituyen, en conjunto la distancia más corta entre una fuente y un destino.

Existen dos algoritmos para encontrar la ruta más corta en redes acíclicas y cíclicas. Se dice que una red es acíclica si no contiene lazos; de otra manera, es cíclica.

Los algoritmos Acíclicos son usados en redes que no tienen ciclos, es decir que no tienen rutas que partiendo de un nodo lo lleven a él mismo de nuevo. Los ciclos son también llamados "lazos".

Los algoritmos cíclicos son para las redes que tienen ciclos o lazos... o en español vueltas en redondo. Un ejemplo de un lazo: Si del nodo "A" puedo ir al nodo "B", y del nodo "B" puedo ir al "C" y del "C" al "D" y del "D" puedo retornar al "A" de nuevo, ahí hay un lazo o un ciclo. Las flechas indican en que sentido esta permitido el movimiento.

Algoritmo Acíclico:

Si la red no tiene ciclos, apliquemos el siguiente algoritmo:

Etiquetar cada nodo con el siguiente formato [distancia desde el nodo inicial, Nombre del Nodo Precedente]. Para el nodo inicial por definición la distancia es cero (la distancia a sí mismo), y el nodo precedente es vacío (ninguno): [0 , ] . Después para cada nodo, se analiza los nodos que lo preceden por las flechas, se escoge aquel cuya distancia al nodo inicial más la distancia al nodo presente sea mínima. Se etiqueta con la suma, y el nombre del nodo escogido... bueno, esto en carreta es muy enredador... mejor con un ejemplo, paso a paso.

El Algoritmo se describe así:

Rotular todos los nodos a los que se puede llegar desde el nodo inicial con etiquetas temporales, la etiqueta que se les pondrá será [distancia desde el nodo inicial, Nombre del Nodo Inicial]. Aquí no nos va a importar que estos nodos tengan caminos desde otros nodos diferentes al nodo inicial, a diferencia del algoritmo anterior. Sencillamente se rotulan como se describió.

Evaluar de todas los nodos con etiquetas temporales, cual posee la distancia más corta en la etiqueta. Marcarlo como Etiqueta Permanente (para esto puede usar un asterisco).

Etiquetar todos los nodos a los que se pueda llegar desde el último nodo con etiqueta permanente, si ya tienen una etiqueta temporal, esta se reevalúa con respecto a la distancia del nodo permanente con que se está trabajando. Si la distancia que da (o sea la distancia de la etiqueta permanente + la distancia al nodo evaluado ) es menor que la que tiene en la etiqueta ésta es cambiada por una nueva etiqueta con la distancia calculada a la de la etiqueta permanente.

Se chequean todas las etiquetas temporales existentes, la que tenga la distancia más pequeña se marca como etiqueta permanente y se repite el paso anterior hasta que todas las etiquetas sean permanentes.

Ejemplo:

Supongamos que existen 7 ciudades interconectadas (o sitios cualquiera: barrios en una ciudad, departamentos en una fabrica, etc.), cada línea representa la trayectoria permitida de una ciudad a otra. Las distancias (o costo de transporte) entre ciudades está representado por un valor sobre la línea. Se pregunta por la secuencia de ciudades que dan la distancia mínima entre la ciudad A y la ciudad G.

2.5 Programación de proyectos (PERT-CPM)

Un proyecto se refiere a una serie de actividades interrelacionadas con un tiempo asignado a cada una de ellas y un orden y precedencia establecido con el fin de lograr un objetivo común. Cada actividad requiere unos recursos, tiene unos costos y estimaciones de duración de la misma.

Ejemplos de Proyectos:

Construcción de Aviones

Construcción de Edificios

Construcción de Barcos, Submarinos

Innovación de Productos

Invasiones Militares

La Administración de Proyectos se compone de tres fases:

Planeación:

Definición de Objetivos

Definición de las variables más relevantes a controlar

Definición del Criterio de Desempeño: Tiempo, Costo

Programación:

Disposición de Recursos en Cantidad y tiempos : Humanos, Materiales, Financieros

Control:

Verificación de las Actividades

Ordenes de Ajuste

Existen varios métodos de Administración de Proyectos, y entre ellos podemos destacar:

CPM (Critical Path Method) - Método de la Ruta Crítica

PERT (Project Evaluation And Review Technique) - Técnica de Evaluación y Revisión de Proyectos

Critical Chain - Cadena Crítica

Todas estas técnicas tienen en común los items en la Planeación, Programación y Control, enumerados anteriormente. Con base en el objetivo propuesto, se definen las actividades que se deben realizar con las estimaciones de tiempo. Cada actividad puede requerir o no que se realice una actividad anteriormente, es lo que denominaremos precedencia.

Una herramienta útil en este sentido es un diagrama de redes, dónde se puede ver que actividad depende de cual otra.

El diagrama de flechas representa las interdependencias y relaciones de precedencia entre las actividades del proyecto. Se utiliza comúnmente una flecha para representar una actividad, y la punta indica el sentido de avance del proyecto. La relación de precedencia entre las actividades se especifica utilizando eventos. Un evento representa un punto en el tiempo y significa la terminación de algunas actividades y el comienzo de nuevas. Los puntos inicial y final de cada actividad, por consiguiente, están descritos por dos eventos generalmente conocidos como evento de inicio y evento terminal. Las actividades que originan un cierto evento no pueden comenzar hasta que las actividades que concluyen en el mismo evento hayan terminado. En la terminología de la teoría de redes cada actividad está representada por un arco dirigido y cada evento está simbolizado por un nodo. La longitud del arco no necesita ser proporcional a la duración de la actividad ni tiene que dibujarse como una línea recta.

Las reglas para construir el diagrama de flechas se resumirán ahora

Regla 1. Cada actividad está representada por una y sólo una flecha en la red.

Ninguna actividad puede representarse dos veces en la red

Regla 2. Dos actividades diferentes no pueden identificarse por los mismos eventos terminal y de inicio

Una situación como ésta puede surgir cuando dos o más actividades deben ejecutarse simultáneamente. El procedimiento es introducir una actividad ficticia, ya sea entra A y uno de los eventos finales, o entre B y uno de los eventos finales.

Las actividades ficticias también son útiles al establecer relaciones lógicas en el diagrama de flechas, las cuales de otra manera, no pueden representarse correctamente.

Regla 3.

A fin de asegurar la relación de precedencia correcta en el diagrama de flechas, las siguientes preguntas deben responderse cuando se agrega cada actividad a la red.

¿Qué actividades deben terminarse inmediatamente antes de que esta actividad pueda comenzar?

¿Qué actividades deben seguir a esta actividad?

¿Qué actividades deben efectuarse simultáneamente con esta actividad?

Cálculos de ruta crítica:

Programación Lineal

Un modelo de Programación Lineal (PL) considera que las variables de decisión

tienen un comportamiento lineal, tanto en la función objetivo como

restricciones del problema. En este sentido, la Programación Lineal es una de

las herramientas más utilizadas en la Investigación Operativa debido a que por

su naturaleza se facilitan los cálculos y en general permite una buena

aproximación de la realidad.

Los Modelos Matemáticos se dividen básicamente en Modelos Determistas

(MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los

parámetros asociados al modelo son conocidos con certeza absoluta, a

diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de

los parámetros tienen una distribución de probabilidad asociada. Los cursos

introductorios a la Investigación Operativa generalmente se enfocan sólo en

Modelos Determistas.

Las aplicaciones de los modelos de Programación Lineal abarcan diversas áreas

de la Ingeniería. A continuación un breve compendio de alguna de sus

aplicaciones y referencias de interés para el lector:1. Problema de Transporte: (Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947). El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (platas, ciudades, etc) a ciertos puntos de destino (centros de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos.

Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:

 

Se requiere formular un modelo de Programación Lineal que permita satisfacer los requerimientos de demanda al mínimo costo.Solución:Variables de Decisión: Xij: Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)Función Objetivo: Minimizar el costo de transporte dado por la función: 21X11 + 25X12 + 15X13 + 28X21 + 13X22 + 19X23Restricciones:Satisfacer los requerimientos de Demanda:X11+ X21 = 200X12 + X22 = 200X13 + X23 = 250Sujeto a la Oferta de las plantas::X11+ X12 + X13 = 250X21 + X22+ X23 = 400No Negatividad: Xij >= 0El siguiente diagrama permite una visualización de la situación anterior:

 

Resolución utilizando el complemento Solver de Microsoft Excel: 1. Abrir una Planilla de Cálculo de Excel. Asegurese de tener instalado el complemento Solver (Opción Herramientas – Complementos)

Luego construya una planilla como la de la imagen de referencia. Se han marcado con amarillo las celdas cambiantes (variables de decisión) y función objetivo. Para facilitar el seguimiento se ha escrito en rojo las fórmulas asociadas a cada celda.

 

4. Seleccione “Resolver”. Obtendrá la solución al problema y podrá requerir los Informes de Solver. Finalmente presione “Aceptar”.

 

5. Se actualizarán los valores en la Planilla de Cálculo en las celdas marcadas en amarillo desplegando la solución óptima y valor óptimo. Adicionalmente se verifica el cumplimiento de las restricciones del problema.

 

6. Finalmente, se obtienen los informes de sensibilidad los cuales entregan información relevante en cuanto a los precios sombra asociados a las restricciones, intervalos de variación de garantizan la validez del precio sombra, intervalo de variación para los coeficientes de la función objetivo, etc.