• Author / Uploaded
• Alex Widoo

Citation preview

TECNOLOGICO DE ESTUDISO SUPERIORES DE SAN FELIPE DEL PROGRESO Modelos de optimización de recursos TEMA: CARPETA DE EVIDENCIAS

NOMBRE DEL ESTUDIANTE: ALEJANDRO JOAN ESPINOZA CHAPARRO NOMBRE DEL DOCENTE INGENIERA GABRIELA GRUPO: 401

CICLO ESCOLAR: 2018-A SAN FELIPE DEL PROGRESO, ESTADO DE MÉXICO, 10 DE JUNIO DE 2018

CARPETA DE EVIDENCIAS 1.1 Toma de decisiones y la investigación operativa Definición de investigación de Operaciones Teniendo en cuenta sus orígenes la investigación de Operaciones la podemos definir como un enfoque científico de la toma de decisión. En este orden de ideas, la toma de decisión es dada a través de la aplicación del método científico, de ahí la definición antes dada. La investigación de operaciones comienza describiendo algún sistema mediante un modelo que luego se manipula y a través de este determinar la mejor forma de operación de dicho sistema. Es esta, tal vez la mejor forma de tomar una decisión, no obstante, nos compromete a seguir un proceso de toma de decisiones racional. Proceso racional de toma de decisiones. ¿Cómo debemos actuar al tomar una decisión? ¿Qué debemos hacer para tomar la mejor decisión? Hacernos estas preguntas nos ha ocurrido en cualquier situación. A través de los tiempos muchos intelectuales las discurrieron ya que en si forman parte fundamental de la búsqueda de la verdad. En esa época muchos fueron los debates al respecto, el resultado de este extenso debate fue un enfoque general conocido como el método científico. Además, se han desarrollado varios modelos matemáticos para problemas específicos. La investigación de operaciones no hace distinción a los nombres proceso de toma de decisiones y solución de problemas por tanto cualquier término se utilizará indistintamente. El método científico El método científico surgió a través del tiempo, a partir de la experiencia práctica de muchos científicos, astrónomos, químicos, físicos y biólogos; a continuación, se enumeran los pasos del método científico para resolver problemas: •

Definir el problema. Este primer paso es crítico porque establece las fronteras para todo lo que sigue. Debe definirse en magnitud, tiempo y grado de importancia.

•

Recolección de datos. La razón para este paso es sencilla, pues se estará más capacitado para resolver problemas si se tiene suficiente información sobre el mismo. Deberá reunirse información pasada, hechos pertinentes, así como soluciones previas a problemas semejantes.

•

Evaluar las alternativas de solución. Una vez enumeradas todas las alternativas de solución, deberán evaluarse. Esto puede lograrse comparando una por una con un conjunto de criterios de solución u objetivos que se deben cumplir. Seleccionar la mejor alternativa. Aquí se toma la decisión de cuál de las alternativas cumple mejor con los criterios de solución.

•

1.2 Concepto y clasificación de sistemas Un sistema es un conjunto de partes o elementos organizados y relacionados que interactúan entre sí para lograr un objetivo. Los sistemas reciben (entrada) datos, energía o materia del ambiente y proveen (salida) información, energía o materia. Un sistema puede ser físico o concreto (una computadora, un televisor, un humano) o puede ser abstracto o conceptual (un software) Cada sistema existe dentro de otro más grande, por lo tanto, un sistema puede estar formado por subsistemas y partes, y a la vez puede ser parte de un súper sistema. Los sistemas tienen límites o fronteras, que los diferencian del ambiente. Ese límite puede ser físico (el gabinete de una computadora) o conceptual. Si hay algún intercambio entre el sistema y el ambiente a través de ese límite, el sistema es abierto, de lo contrario, el sistema es cerrado. Tipos de sistemas Pueden ser Físicos o abstractos. Sistemas físicos o concretos: compuestos por equipos, maquinaria, objetos y cosas reales. El hardware. Sistemas abstractos: compuestos por conceptos, planes, hipótesis e ideas. Muchas veces solo existen en el pensamiento de las personas. Es el software. En cuanto a su naturaleza Pueden cerrados o abiertos. Sistemas cerrados: no presentan intercambio con el medio ambiente que los rodea, son herméticos a cualquier influencia ambiental.

Se da el nombre de sistema cerrado a aquellos sistemas cuyo comportamiento es determinista y programado y que opera con muy pequeño intercambio de energía y materia con el ambiente. Se aplica el término a los sistemas completamente estructurados, donde los elementos y relaciones se combinan de una manera peculiar y rígida produciendo una salida invariable, como las máquinas. Sistemas abiertos: presentan intercambio con el ambiente, a través de entradas y salidas. Intercambian energía y materia con el ambiente. Son adaptativos para sobrevivir. Su estructura es óptima cuando el conjunto de elementos del sistema se organiza, aproximándose a una operación adaptativa. Sistemas aislados: son aquellos sistemas en los que no se produce intercambio de materia ni energía. Caracteristicas de los Sistemas Sistema es un todo organizado y complejo; es un conjunto de objetos unidos por alguna forma de interacción o interdependencia. Los límites o fronteras entre el sistema y su ambiente. Objeto: Todo sistema tiene uno o algunos propósitos. Los elementos (u objetos), como también las relaciones, definen una distribución que trata siempre de alcanzar un objetivo. Goblalismo o totalidad: Un cambio en una de las unidades del sistema, con probabilidad producirá cambios en las otras. El efecto total se presenta como un ajuste a todo el sistema. Hay una relación de causa / efecto.

1.3 Concepto y tipología de modelos Un modelo es una representación o abstracción de una situación u objeto real, que muestra las relaciones (directas o indirectas) y las interrelaciones de la acción y la reacción en términos de causa y efecto. Tipos de modelos   

Icónico Analógicos Simbólicos o matemáticos

MODELO ICÓNICO: Es una representación física de algunos objetos, ya sea en forma idealizada (bosquejos) o a escala distinta. Ejemplo:

•Planos y mapas (dos dimensiones). •Maquetas y prototipos (4 dimensiones). Ejemplo:

MODELO ANALÓGICO: Puede representar situaciones dinámicas o cíclicas, son más usuales y pueden representar las características y propiedades del acontecimiento que se estudia. Ejemplo: •Curvas de demanda. •Curvas de distribución de frecuencia en las estadísticas y diagramas de flujo. MODELO SIMBÓLICO O MATEMÁTICO: Son representaciones de la realidad en forma de cifras, símbolos matemáticos y funciones, para representar variables de decisión y relaciones que nos permiten describir y analizar el comportamiento del sistema. Tipos de modelos Matemáticos: 1. Cuantitativos y cualitativos 2. Estándares y hechos a la medida 3. Probabilísticas y determinísticos 4. Descriptivos y de optimización 5. Estáticos y dinámicos 6. De simulación y no simulación Modelos Cuantitativos y Cualitativos: La mayor parte de los problemas de un negocio u organización comienzan con un análisis y definición de un modelo cualitativo y se avanza gradualmente hasta

obtener un modelo cuantitativo. La investigación de operaciones se ocupa de la sistematización de los modelos cualitativos y de su desarrollo hasta el punto en que pueden cuantificarse. Cuando es posible construir unos modelos matemáticos insertando símbolos para representar relaciones entre constantes y variables estamos ante un modelo cuantitativo. Una ecuación es un modelo de este tipo. Las formulas, las matrices, los diagramas o series de valores que se obtienen mediante procesos matemáticos. Modelos Estándar: Se llaman modelos estándar a los que solo hay que insertar o sustituir diferentes valores con el fin de obtener un valor a una respuesta de un sistema y son aplicables al mismo tipo de problemas en negocios afines. Ejemplo: •El cálculo de costos o gastos. •El cálculo de las ganancias, etc. Modelos hechos a la medida: Se llaman modelos hechos a la medida cuando se crean modelos para resolver un caso de problema en específico que se ajusta únicamente a este problema. Modelos Probabilístico y determinístico: Los los modelos que se basan en las probabilidades y estadísticas y que se ocupan de incertidumbres futuras se llaman probabilísticas y los modelos que no tienen consideraciones probabilísticas se llaman determinísticos; el PERT, los inventarios, la programación lineal, enfocan su atención en aquellas circunstancias que son críticas y en los que las cantidades son determinadas y exactas. Modelo Descriptivo y de Optimización: Cuando un modelo constituye sencillamente una descripción matemática de una condición real del sistema se llama descriptivo. Algunos de estos modelos se emplean para mostrar geográficamente una situación y ayudan al observador a evaluar resultados por secciones una sobre otra. Modelo Estático y Dinámico: Los modelos estáticos se ocupan de determinar una respuesta para una serie especial de condiciones fijas que probablemente no cambiaran significativamente a corto plazo es decir, la solución está basada en una condición estática. Modelos Simulados y No Simulados:

Con el uso de la computadora es fácil preparar un modelo simulado paso por paso donde se puede reproducir el funcionamiento de sistemas o problemas de gran escala. En un modelo de simulación los datos de entrada pueden ser reales o generados en forma aleatoria.

Unidad 2 2. programación lineal La investigación de operaciones utiliza una metodología sencilla para acercarse a la solución de problemas que requieren de optimización. Tal metodología puede expresarse como sigue: • Identicación del problema que requiere de la investigación de operaciones y recopilación de información. • Planteamiento del modelo matemático. • Solución del problema matemático y ajustes al mismo. • Implementación de la mejor solución. Uno de los modelos más utilizado en la investigación de operaciones es el Modelo de Programación Lineal (PL), el cual tiene la característica de que todas las expresiones que lo componen son lineales. El modelo de programación lineal cuenta con una función objetivo, la cual se pretende optimizar, y una serie de expresiones matemáticas que representan las restricciones que deben satisfacerse para que la solución obtenida sea óptima y factible. El siguiente es un ejemplo de un modelo de programación lineal: 0 1 Max Z x x = 5 12 + s. a 0 1 x + 2 125 x ≤ 0 1 3 65 x + x ≤ CNN 0 1 x , x ≥ 0

2.1. Planteamiento del modelo Un modelo es la representación abstracta de un proceso en particular o de la realidad en general. Dependiendo de la complejidad y del fin de lo que se desea representar, se han desarrollado diferentes modelos como son los diagramas de flujo, que indican el orden y secuencia de una serie de actividades; los organigramas, que indican la jerarquía e interrelaciones de una organización; o los modelos matemáticos, que son representaciones de problemas o casos prácticos con números y signos matemáticos.

Ejemplo de estos últimos son las ecuaciones que representan la oferta y la demanda y la expresión matemática de las utilidades o de los costos de producción de una empresa.

2.1.1. Datos y variables de decisión La identificación de un problema, proceso o situación que puede optimizarse con la investigación de operaciones se basa en reconocer si el problema de estudio cuenta con variables controlables, que llamaremos variables de decisión. Una variable controlable o de decisión es aquella que se puede medir y modificar en su valor deliberadamente. Una empresa comercializa dos tipos de viaje en globo aerostático, uno llamado de lujo y el segundo llamado económico a un precio de $3,000.00 y $2,000.00 respectivamente. Saben que en un día sólo pueden vender a lo más 6 viajes de cualquier tipo, debido a que tienen prohibido volar de noche por razones de seguridad. Cada viaje de lujo requiere de tres cilindros de gas y cada viaje económico sólo dos cilindros, la empresa cuenta con 12 cilindros de gas en total. Con esta información se desea conocer la combinación óptima de viajes necesaria para maximizar los ingresos de la empresa. De manera similar al primer ejemplo de la sección, las variables de decisión pueden obtenerse respondiendo a la pregunta ¿qué se desea cuantificar?, y la respuesta está en el planteamiento mismo como “...la combinación óptima de viajes necesaria para maximizar los ingresos...”, entonces se definen como variables de decisión aquellas que indiquen la cantidad de viajes de cada tipo: x = Cantidad de viajes de lujo que se requiere vender. : y = Cantidad de viajes económicos que se requiere vender. A partir de este punto, las expresiones de “la función objetivo” y “las restricciones” del problema en un modelo de P. L. deben escribirse en función de las variables de decisión definidas. 2.1.2. Función objetivo y las restricciones Toda vez que se han definido las variables de decisión, es momento de indicar la forma en que estas variables y los datos se interrelacionan, obteniendo de esto la función objetivo y las restricciones del problema. Identificación de la función objetivo La función objetivo es una expresión matemática que representa una cantidad, la cual tratamos de optimizar (maximizar o minimizar) como pueden ser los ingresos, las utilidades o los costos en una empresa. Como la investigación de operaciones es una herramienta que permite tomar decisiones de tipo operativo, estas decisiones son tomadas con la premisa de

maximizar las utilidades o minimizar los costos de la organización, los cuales dependen de los siguientes factores: • Costos de producción. • Precio de venta. • Volumen de venta. Por lo tanto, toda función objetivo deberá estar conformada por este tipo de componentes. De no ser así, se sugiere validar la función objetivo con las variables y datos del problema. La función objetivo se obtiene, primero, identificando si se trata de maximizar ingresos o minimizar costos y, segundo, escribiendo la forma en la que los ingresos o costos se cuantifican. Para el ejemplo 2 de los viajes en globo (del cual tenemos identificadas las variables de decisión) se trata de maximizar los ingresos de la empresa, ya que se indica “combinación óptima de viajes necesaria para maximizar los ingresos”; la forma en la que se cuantifican los ingresos es multiplicando el ingreso que cada tipo de viaje genera por el número de viajes que se pueden comercializar. Esto es: x = Cantidad de viajes de lujo que se requiere vender.: y = Cantidad de viajes económicos que se requiere vender.: Max Z x y = 3000 2000 +

2.2. Solución gráfica La solución de un modelo de programación lineal es el siguiente paso después de obtener el modelo matemático de un problema. Para seleccionar el método de solución se requiere considerar la cantidad de variables de decisión del modelo matemático; cuando se tienen dos variables de decisión puede obtenerse la solución de manera gráfica; sin embargo, cuando se tienen más de dos variables a graficar se torna complejo y por esta razón se han desarrollado otros métodos que se estudiarán más adelante. Aunque son pocos los ejemplos reales de dos dimensiones, éstos sirven como antecedente para comprender mejor el método analítico de solución que se estudiará más adelante, el cual se utiliza para resolver problemas de PL de n variables. Por otra parte realizaremos un análisis de sensibilidad, el cual consiste en estudiar el comportamiento de la solución óptima de un modelo cuando los coeficientes de la función objetivo o las cantidades limitantes de las restricciones se modifican. Se debe tener presente que existen problemas cuya solución no existe o bien no es única, lo cual se presenta continuamente en la realidad.

2.2.1. Gráfica de rectas y desigualdades Para utilizar el método gráfico se requiere graficar rectas y desigualdades asociadas a la función objetivo y a cada restricción respectivamente, y debido a esta razón revisaremos los siguientes apartados.

Una línea recta es un objeto geométrico que ha sido definido por diversos autores con características bien definidas, las cuales utilizaremos para dibujarlas. Gráfica de rectas Para graficar líneas rectas consideraremos que sólo necesitamos obtener dos puntos de una misma recta; para obtener dichos puntos podemos utilizar dos caminos: Partiendo de la ecuación general Ax + By + C = 0 se da un valor arbitrario a una de las dos variables y se despeja o resuelve la ecuación para la otra variable. Como se indica, puede sustituirse cualquier valor; sin embargo, se recomienda sustituir el valor de cero para las dos variables (no al mismo tiempo), ya que esto facilita los cálculos y la construcción de una gráfica más precisa y con esto se determinan los puntos de intersección de la recta con los ejes coordenados. Obtener la gráfica de la ecuación 2x + 6y − 6 = 0. Comenzamos por sustituir arbitrariamente el valor de x = 0 en la ecuación general de la recta dada y resolver la expresión para y , con lo que se tiene: 2(O) + y -6 = O O+ y -6 = 0 y=6 Esto nos indica un primer punto por donde pasará nuestra recta, el punto es P1 = ( 0,6). Ahora sustituimos el valor de y = 0 en la ecuación general de la recta dada y se resuelve la expresión para x, con lo que se tiene: 2x + (0) − 6 = 0 2x − 6 = 0 2x = 6 x =6/2 x=3 Esto nos indica un segundo punto por donde pasará nuestra recta, el punto es 2 P = (3,0). Los dos puntos recién obtenidos se grafican sobre ejes coordenados y se unen mediante una línea recta, la cual representa la recta de la ecuación dada. La línea recta que une los dos puntos puede prolongarse tanto como se requiera en cualquier sentido.

Partiendo de la ecuación ordinaria y = mx + b , se da un valor arbitrario a una de las dos variables y se despeja o resuelve la ecuación para la otra variable. Como en la primera forma, en realidad se está realizando la misma operación; sin embargo, el lector puede hacer uso de la que más fácil represente su manejo. Gráfica de desigualdades Toda desigualdad de dos variables tiene asociada una línea recta, la cual se obtiene graficando la restricción o desigualdad como una igualdad. 2.2.2. Región factible La región factible o región de soluciones factibles es una región del plano cartesiano donde se satisfacen todas las restricciones de un modelo de programación lineal y, por tanto, en ella se encuentran las probables soluciones del modelo. Existen diferentes tipos de región factible e incluso problemas que no tienen región factible debido a las condiciones que las restricciones imponen. En un solo sistema coordenado se grafica el conjunto de restricciones (rectas llamadas fronteras y regiones) cuya intersección será la región factible; es importante señalar la región factible de cada modelo, por ejemplo, sombreando la región, con una letra “R” o con el símbolo Ω, como algunos autores lo aconsejan.

2.2.3. Punto óptimo Una vez que se ha obtenido la región factible –si ésta existe– de un problema, es momento de localizar el punto óptimo en la gráfica generada y para tal efecto es necesario graficar la recta asociada a la función objetivo del modelo PL. Para graficar la función objetivo simplemente se toma un par ordenado que pertenezca a la región factible y se sustituye en la función Z, después se obtienen los puntos restantes de la recta por sustitución. Cuando se tiene la gráfica de la función objetivo, la línea recta que se obtuvo se desplaza de manera paralela a la recta original hasta alcanzar el último punto de la región factible sin salirse de la misma, considerando lo siguiente: i) Para maximizar se desplaza hacia la derecha y arriba de la región factible. ii) ii) Para minimizar se desplaza hacia la izquierda y debajo de la región factible. Es importante recordar que los desplazamientos siempre se realizan de forma paralela a la gráfica de la recta de la función objetivo. Una forma de realizar los desplazamientos abarca los siguientes pasos: 1. Alinear una escuadra sobre la función objetivo. 2. Apoyar el otro lado recto de la escuadra sobre una regla o escuadra. 3. Desplazar la primera escuadra hacia la izquierda o derecha, según corresponda, de la región factible hasta el último punto de la misma. El punto localizado por este método se le conoce como punto óptimo del modelo y representa los valores de las variables de decisión del problema, lo cual quiere decir que con este punto podemos interpretar la solución de un modelo. Del ejemplo 8

recuperamos la región factible generada para graficar la función objetivo del modelo PL sobre la región factible. Una forma analítica de encontrar el punto óptimo de un modelo PL de dos variables proviene de aplicar un teorema (el cual no se demuestra en este texto) que asegura que la solución óptima de un problema (al maximizar o minimizar la función objetivo) se encuentra en uno de los vértices de la región factible. Con base en lo anterior, lo que debe hacerse es identificar los puntos de todos los vértices de la región factible y evaluarlos en la función objetivo. Si el propósito es maximizar, se selecciona el punto con resultado máximo en la función objetivo; en caso de minimizar se escoge el punto cuyo valor en la función objetivo sea mínimo. Este método es más preciso por ser analítico, sin embargo, es indispensable obtener la región factible y después estudiar el comportamiento de los vértices en la función objetivo en lugar de los desplazamientos.

2.2.4. Análisis gráfico de sensibilidad Debido a que los sistemas con los que se trabaja son dinámicos y no estáticos, es necesario realizar un análisis de sensibilidad para conocer cómo se afecta la solución a un modelo cuando se modifican los coeficientes de la función objetivo o las cantidades limitantes del modelo. Cambio en los coeficientes de la función objetivo Los coeficientes de la función objetivo representan la utilidad o costo unitario de cada uno de los bienes o servicios, y por esta razón un cambio en alguno de estos datos representará una modificación a la función objetivo, para lo cual se considera que la solución se mantendrá en el mismo vértice mientras la pendiente m de la recta asociada a la función objetivo sea tal que Ri Rj m ≤ m ≤ m ; siendo Ri m y Rj m las pendientes de las fronteras de la región factible cuya intersección forma el vértice solución. Como se muestra en la Figura 2.13. donde las curvas punteadas indican el cambio que la pendiente de la función objetivo puede tener sin modificar la solución del problema. Cambio en las cantidades limitantes Cuando cambia alguna de las cantidades limitantes, la región factible cambia su tamaño, por lo que el vértice solución puede cambiar. Al realizar el análisis debemos cuidar que el cambio que se haga no provoque una región no factible.

2.3. Desigualdades lineales: Casos de inversión y distribución Como una aplicación del modelo de programación lineal se encuentran los casos de inversión y distribución, los cuales generalmente están sujetos a múltiples restricciones que dependen de diversos contextos, desde reservas de capital hasta cantidad de orígenes y destinos de un problema de distribución. El problema de un caso de inversión puede ser la selección óptima de los instrumentos financieros que conforman un portafolio de inversiones

donde las restricciones quizás estén asociadas al riesgo de cada instrumento, a la tasa de rendimientos o al plazo de que cada uno maneje. Otro problema útil en los negocios puede ser la selección de diferentes fuentes de financiamiento, ya que generalmente los negocios requieren buscar recursos de varias fuentes y por esta razón la toma de decisiones debe apoyarse en información cuantitativa proveniente de la solución de modelos matemáticos. Las variables de decisión serían la cantidad de unidades que deben ser financiadas por cada opción de financiación y la finalidad es maximizar los ingresos o minimizar los pagos del financiamiento.

2.4. Aplicaciones de la optimización en la toma de decisiones en los negocios En esta sección se muestra cómo la optimización puede aportar información válida y confiable para sustentar una toma de decisión; es importante remarcar que, a fin de cuentas, el gerente o administrador es quien tomará la decisión; sin embargo, si se fundamenta esta decisión en resultados cuantitativos se estará en posición de generar mejores resultados en un negocio. Al manejar el término negocio podríamos pensar en diferentes definiciones, y para evitar confusiones se presenta la siguiente definición: Se entiende por negocio: cualquier ocupación, quehacer o trabajo que sea lucrativo o de interés. De acuerdo con lo anterior: cualquier planteamiento referido a alguna actividad de producción, transformación, distribución o en general que se apegue a la definición de negocio se considera como tal; dentro de estas actividades también se tienen negocios particularmente específicos, como los casos de inversión y distribución. Problemas de optimización de recursos empresariales Max ó Min Z = C X S.A: AX≤B XJ > 0 ; j = 1, 2, ..., n Objetivo Mediante una recopilación de problemas representativos de programación lineal se busca desarrollar la capacidad inventiva para formular problemas de optimización de recursos.

Programación Lineal - Problema General Definición: Dado un conjunto de m desigualdades lineales ó ecuaciones lineales, con n variables, se requiere hallar valores no negativos de éstas variables que satisfagan las restricciones y maximicen ó minimicen alguna función lineal de las variables llamada Función Objetivo. Matemáticamente: Hallar XJ , J = 1, 2, . . . . . n Maximizar ó Minimizar

para:

Z = C1X1 + C2X2 + . . . . . . + CnXn

Con las siguientes restricciones: a11X1 + . . . . . . + a1jXj + . . . . . . + a1nXn ≤ ó ≥ b1 . ai1X1 + . . . . . . + aijXj + . . . . . + ainXn ≤ ó ≥ bi . am1X1 + . . . . . . + amjXj+ . . . . . . + amnXn ≤ ó ≥ bm Xj =0 ; j = 1, 2, . . . . . . n

Unidad 3 Algoritmos especiales en la programación en 3.1. El problema de transporte: planteamiento del problema, determinación de la Solución Básica Factible Inicial, el criterio de optimalidad y el algoritmo de mejoramiento de la solución (Ruta de los signos) ¿Qué significa problema de transporte? Supongamos que un fabricante tiene tres plantas que producen el mismo producto. Estas plantas a su vez mandan el producto a dos depósitos. Cada planta puede mandar productos a todos los depósitos, pero el costo de transporte varía con las diferentes combinaciones. El problema es determinar la cantidad que cada planta debe mandar a cada depósito con el fin de minimizar el costo total de transporte. La manera más fácil de reconocer un problema de transporte es por su naturaleza o estructura “de-hacia”: de un origen hacia un destino, de una fuente hacia un

usuario, del presente hacia el futuro, de aquí hacia allá, una relación de uno a otroAl enfrentar este tipo de problemas, la intuición dice que debe haber una manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas y los costos de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o maximice la ganancia). La dificultad está en el gran número de combinaciones posibles, debido a eso el problema del transporte recurre a buscar soluciones con la computara y software especializado. El responsable de gestión del trasporte debe determinar una política óptima: cómo hacer llegar los productos de sus diversos depósitos, plantas de producción o bodegas a sus consumidores o clientes, con el objeto de satisfacer la demanda a un costo mínimo de transporte o de envío. Planteamiento del problema El problema del transporte en general se especifica mediante la siguiente información: 1. Un conjunto de m puntos de oferta desde los cuales se envían utilidades o bienes. 2. Una lista de capacidades de suministro máximo de cada sitio de oferta si para i = 1, 2, . . ., m. 3. Un conjunto de n puntos de demanda hacia los cuales se envía una utilidad o bien. 4. Una lista de demandas de utilidades o bienes dj de cada punto de demanda j las cuales deben satisfacerse mínimamente. 5. Una matriz de valores que indica el costo fijo en el que se incurre al enviar una unidad producida en el punto de oferta i y enviada al punto de demanda j, cij . Sea: X i j = Unidades enviadas del origen i (i =1,2,...m), al destino j ( j = 1,2,...,n) C i j = Costo unitario desde el nodo origen i hasta el nodo destino j. = Oferta del origen i, (i = 1, 2,...,m); b j = Demanda del destino j ( j = 1, 2,...,n)

El modelo de programación lineal aquí mostrado se presenta para un problema balanceado con las restricciones de oferta y demanda en igualdad. Para el caso de un problema no balanceado (oferta y demanda en desigualdad) es necesario el

Equilibrio:

= b j; además, debe cumplirse que toda X i j >= 0

Determinación de la Solución Básica Factible La utilización del método SIMPLEX no resulta eficiente para resolver el Problema de Transporte, por lo cual se utilizan otros métodos como: a) Método de la Esquina Nor-Oeste (N-O) b) Método de la Matriz de Costo Mínimo c) Método de Vógel Método de la esquina noroeste Características Sencillo y fácil de hacer No tiene en cuenta los costos para hacer las asignaciones Generalmente nos deja lejos del óptimo Algoritmo 1. Construya una tabla de ofertas (disponibilidades) y demandas (requerimientos). 2. Empiece por la esquina noroeste. 3. Asigne lo máximo posible (Lo menor entre la oferta y la demanda, respectivamente) 4. Actualice la oferta y la demanda y rellene con ceros el resto de casillas (Filas ó Columnas) en donde la oferta ó la demanda halla quedado satisfecha. 5. Muévase a la derecha o hacia abajo, según halla quedado disponibilidad para asignar. 6. Repita los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior derecha en la que se elimina fila y columna al mismo tiempo.

Nota: No elimine fila y columna al mismo tiempo, a no ser que sea la última casilla. El romper ésta regla ocasionará una solución en donde el número de variables básicas es menor a m+n-1, produciendo una solución básica factible degenerada. Problema de ejemplo Una compañía tiene 3 fábricas ubicadas en A, B y C, las cuales proveen a los almacenes que están ubicados en D, E, F y G. La capacidad de producción de las fábricas es de 70, 90 y 115 unidades mensuales respectivamente, mientras que las capacidades de los almacenes son de 50, 60, 70 y 95 unidades respectivamente. El costo de envió de una unidad desde cada una de las fábricas a cada una de los almacenes se presenta en el siguiente cuadro (en pesos):

Por consiguiente la solución es:

Método del costo mínimo Características: Es más elaborado que el método de la esquina noroeste

Tiene en cuenta los costos para hacer las asignaciones Generalmente nos deja alejados del óptimo Algoritmo: 1. Construya una tabla de disponibilidades, requerimientos y costos 2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja arbitrariamente (Cualquiera de los empatados). 3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos). 4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el requerimiento, restándoles lo asignado. Nota: Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde usar la ε (Épsilon). 5. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en cuenta la fila o columna satisfecha). 6. Regrese a los puntos 3, 4,5 sucesivamente, hasta que todas las casillas queden Asignadas. Método de Vogel Características Es más elaborado que los anteriores, más técnico y dispendioso. Tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones. Generalmente nos deja cerca al óptimo. Algoritmo 1. Construir una tabla de disponibilidades (ofertas), requerimientos (demanda) y costos. 2. Calcular la diferencia entre el costo más pequeño y el segundo costo más pequeño, para cada fila y para cada columna. 3. Escoger entre las filas y columnas, la que tenga la mayor diferencia (en caso de empate, decida arbitrariamente). 4. Asigne lo máximo posible en la casilla con menor costo en la fila o columna escogida en el punto 3. 5. asigne cero (0) a las otras casillas de la fila o columna donde la disponibilidad ó el requerimiento quede satisfecho. 6. Repita los pasos del 2 al 5, sin tener en cuenta la(s) fila(s) y/o columna(s) satisfechas, hasta que todas las casillas queden asignadas. Nota: Recuerde que no debe satisfacer filas y columnas al mismo tiempo; caso enque la disponibilidad sea igual al requerimiento; en tal caso use el ε (epsilon).

3.2. El problema de asignación: planteamiento del problema, Algoritmo para determinar la asignación óptima. Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no. Así Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no. Así es que podemos representar éstas posibilidades con los valores 0 (no) y 1 (si), y aprovechar las matemáticas para que nos den una mano ante decisiones difíciles; a esto es lo que solemos llamar -por obvias razones Programación Binaria. Una de las muchísimas aplicaciones de la Programación Binaria, es el problema de la Asignación. Este método analiza el problema de asignar un cierto número de recursos a un determinado número de tareas, con base en algún tipo de valoración para cada recurso. Cada recurso, podrá ser asignado a una sola tarea. El PA consiste en asignar recursos a tareas en función de un objetivo ligado a la eficiencia del sistema. Un ejemplo típico es el de asignación de personas a turnos horarios, o el de asignar personas a máquinas. El esquema tabular del PA es:

Planteamiento del problema

Minimizar el costo total de operación de modo que:  

Cada tarea se asigne a una y sólo una máquina Cada máquina realice una y sólo una tarea

Algoritmo para determinar la asignación optima La utilización del método SIMPLEX o los métodos del Problema de Transporte, no resultan eficientes para resolver el Problema de Asignación, por lo cual se utiliza otro método denominado METODO HÚNGARO. El Método Húngaro se desarrolló por Kuhn, basado en un trabajo de Egerváry y Konig. Fue Kuhn quien lo denominó: Método Húngaro. Característica del Método Húngaro El método a estudiar tiene la siguiente característica: a) Se garantiza la solución óptima. b) El procedimiento requiere que la matriz de costos sea no negativa. c) La solución óptima se obtiene en una matriz de costos equivalente cuyo valor óptimo es cero (0). d) El problema planteado debe estar balanceado:

e) La solución óptima no varía si a la matriz original se le incrementa un valor k a cada celda. Pero el valor Z se incrementa en nk.

f) La solución óptima no varía si a la matriz original se le incrementa un valor k a una fila o columna. Pero el valor Z se incrementa en k. Proceso del Método Húngaro 1) Reducción por filas Determinar el mínimo valor de cada fila y restarlo a todas las celdas de su correspondiente fila. Esto garantiza un cero en cada fila. 2) Reducción por columnas Determinar el mínimo valor de cada columna y restarlo a todas las celdas de su correspondiente columna. Esto garantiza un cero en cada columna. 3) Cubrimiento de ceros Con el mínimo número de rectas cubrir los ceros de la matriz reducida. Empezar por la fila o columna que tenga el mayor número de ceros. Si el número de rectas resulta igual a n (número de tareas o equipos) se ha llegado a la solución óptima Pasar al paso 5 de lo contrario pasar al óptima. 5, paso 4. 4) Reducción posterior Localizar la celda no cubierta de menor costo. Restar el valor determinado a las celdas no cubiertas. Sumar el valor determinado a las celdas que se encuentren en la intersección de las rectas. Regresar al paso 3. 5) Localización de la solución Determinar las filas que tengan un único valor cero y asignarlos, eliminar las columnas correspondientes. Determinar las columnas que tengan un único valor cero y asignarlos, eliminar las filas correspondientes. Repetir este procedimiento tantas veces sea necesario. En caso de celdas con empates seleccionar arbitrariamente. La asignación localizada de valor cero, implantarla en la matriz de costos original y determinar el valor de Z. Problema ejemplo Existen 5 operarios (A, B, C, D y C) que tienen que llenar 5 cargos (I, II, III, IV y V). La matriz de costos que caracteriza el problema de asignación es la siguiente:

Determinar la asignación óptima 1- Se calcula C’ij= Cij – elemento más pequeño de cada columna

2. Se calcula C*ij = C’ij – elemento mas pequeño de cada fila

3. Procederemos a encontrar el número mínimo de recta r que cubren todos los ceros de la matriz C*

Vemos que r = 4 que es diferente de m=5, por consiguiente no se ha llegado al óptimo 4. En este caso ⍬= 1 (elemento mínimo no cubierto por las rectas). Se resta ⍬ a todos los elementos no cubiertos por las rectas- Se suma ⍬ a todos los

elementos en las intersecciones entre 2 rectas y se vuelve al paso 3. La matriz C* se transforma en

Se observa que r = 5 = m =5, por consiguiente se ha llegado al óptimo 6. Determinamos la asignación óptima

Hay dos soluciones óptimas: A es asignado a IV B es asignado a II C es asignado a I D es asignado a V E es asignado a II O bien: A es asignado a V

B es asignado a II C es asignado a I D es asignado a IV E es asignado a III El costo total del programa en ambos casos es Z = $ 18

3.3 El uso de software El WinQsb maneja el problema del transporte en su módulo de Modelos de Redes, el cual en su inicio nos muestra la siguiente ventana, que se debe diligenciar así:

Fíjese que éste módulo también resuelve otros modelos de redes, que se especifican en la parte izquierda de la ventana. Los datos se pueden ingresar de dos formas: En una matriz ó tablero de doble entrada ó de forma gráfica. A continuación se ilustra el ingreso de datos en la tabla de doble entrada. El modo de edición del menú principal permite cambiar los rótulos de las fuentes y los destinos. No es necesario que la oferta sea igual a la demanda, el software se encarga de agregar fuentes ó destinos de holgura, según sea la necesidad. Para solucionar el problema, se da clic sobre el icono que aparece en la parte superior y que se señala en la figura siguiente:

El WinQsb le ofrecerá entonces una ventana con la respuesta óptima del problema, indicando cuántas unidades enviar desde cada una de las ciudades de origen a cada una de las ciudades de destino, con su costo por envío y el costo total de la operación.

Unidad 4: Modelos De Flujos En Redes Una red se compone de un conjunto de nodos unidos por arcos (o ramas). La notación para describir una red es (N, A), donde N es el conjunto de nodos, y A es el conjunto de arcos. N = {1, 2, 3, 4, 5} A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}

4.1 El Modelo Del Camino Más Corto Este problema determina la ruta más corta entre un origen y un destino en una red de transporte. El mismo modelo puede representar otras situaciones. Esta sección presenta dos algoritmos para resolver tanto redes cíclicas (es decir, que contienen bucles) como redes acíclicas: 1. El algoritmo de Dijkstra para determinar las rutas más cortas entre el nodo origen y los demás nodos en la red.

2. El algoritmo de Floyd para determinar la ruta más corta entre dos nodos cualesquiera en la red. En esencia, el algoritmo de Floyd incluye a Dijkstra. Algoritmo de Dijkstra. Sea Ui la distancia más corta del nodo origen 1 al nodo i, y defina Dij (≥ 0) como la longitud del arco (i,j). El algoritmo define la etiqueta para un nodo j que sigue inmediatamente como:

La etiqueta para el nodo de inicio es [0, 2], que indica que el nodo no tiene predecesor. Las etiquetas de nodo en el algoritmo de Dijkstra son de dos tipos: temporales y permanentes. Una etiqueta temporal en un nodo se modifica si puede hallarse una ruta más corta al nodo. De lo contrario, el estado temporal cambia a permanente.

Ejemplo 1:

La red de la figura muestra las rutas permisibles y sus longitudes en millas entre la ciudad 1 (nodo 1) y las otras cuatro ciudades (nodos 2 a 5). Determine las rutas más cortas entre la ciudad 1 y cada una de las cuatro ciudades restantes.

Interacción 1. Se puede llegar a los nodos 2 y 3 desde el nodo 1 (el último etiquetado permanentemente). Así, la lista de nodos etiquetados (temporales y permanentes) es:

Para las dos etiquetas temporales [100,1] y [30,1], el nodo 3 da la distancia mínima (u3 = 30). De este modo, el estado del nodo 3 cambia a permanente. Interacción 2. Se puede llegar a los nodos 4 y 5 desde el nodo 3, y la lista de los nodos etiquetados es:

La etiqueta temporal [40,3] en el nodo 4 ahora es permanente (u4 = 40).

Interacción 3. Desde el nodo 4 se puede llegar a los nodos 2 y 5 Así, la lista de los nodos etiquetados se actualiza como:

En el nodo 2, la nueva etiqueta [55,4] reemplaza a la etiqueta temporal [100,1] de la iteración 1 porque proporciona una ruta más corta. Además, en la iteración 3 el nodo 5 tiene dos etiquetas alternativas con la misma distancia (u5 5 90). La etiqueta temporal [55,4] en el nodo 2 ahora es permanente (u2 = 55). Iteración 4. Sólo el nodo 3 permanentemente etiquetado puede ser alcanzado desde el nodo 2. Por consiguiente, el nodo 3 no puede ser reetiquetado. La nueva lista de etiquetas permanece como estaba en la iteración 3 excepto que la etiqueta en el nodo 2 ahora es permanente. Esto deja al nodo 5 como la única etiqueta temporal. Como el nodo 5 no conduce a otros nodos, su etiqueta se hace permanente, y el proceso termina. Los cálculos del algoritmo pueden realizarse directamente en la red, como lo demuestra la figura:

La ruta más corta entre el nodo 1 y cualquier otro nodo en la red se determina partiendo del nodo destino deseado y retrocediendo hasta el nodo de inicio

utilizando la información en las etiquetas permanentes. Por ejemplo, la siguiente secuencia determina la ruta más corta del nodo 1 al nodo 2:

Por lo tanto, la ruta deseada es 1 ⇒ 3 ⇒ 4 ⇒ 2 con una distancia total de 55 millas. Ejemplo 2: I. Q. Smart va en auto diariamente al trabajo. Habiendo completado un curso de análisis de redes, Smart es capaz de determinar la ruta más corta al trabajo. Por desgracia, la ruta seleccionada está fuertemente patrullada por la policía, y con todas las multas pagadas por exceso de velocidad, la ruta más corta puede no ser la mejor opción. Smart ha decidido por lo tanto elegir una ruta que maximice la probabilidad de no ser detenido por la policía. La red en la figura muestra las posibles rutas de la casa al trabajo y la probabilidad asociada de no ser detenido en cada segmento. La probabilidad de no ser detenido en la ruta es el producto de las probabilidades de sus segmentos. Por ejemplo, la probabilidad de no ser multado en la ruta 1 ⇒ 3 ⇒ 5 ⇒ 7 es .9 3 .3 3 .25 5 .0675. El objetivo de Smart es seleccionar la ruta que maximice la probabilidad de no ser multado.

El problema puede formularse como un modelo de la ruta más corta por medio de una transformación logarítmica para convertir el producto de las probabilidades en la suma de los logaritmos de las probabilidades, esto es, p1k x p1 x p2 3 … x pk se transforma en log p1k = log p1 1 log p2 1 … 1 log pk. Las dos funciones p1k y log

p1k son monótonas y decrecen en k, así pues, maximizar p1k es equivalente a maximizar log p1k, lo que a su vez equivale a minimizar log p1k. Por lo tanto, al reemplazar pj con log pj para toda la j en la red, el problema se convierte en la red de la ruta más corta en la figura:

4.2 El Modelo De Flujo Máximo Considere una red de oleoductos que transporta petróleo crudo desde pozos hasta refinerías. Se instalan estaciones intermedias de reforzamiento y bombeo a distancias apropiadas para mover el crudo en la red. Cada segmento de tubería tiene una velocidad de descarga finita (o capacidad) de flujo de crudo. Un segmento de tubería puede ser unidireccional o bidireccional, según su diseño. La figura 6.26 muestra una red de oleoductos típica. El objetivo es determinar la capacidad de flujo máxima de la red. La solución del problema propuesto requiere agregar una sola fuente y un solo sumidero o vertedero, utilizando arcos de capacidad infinita unidireccionales, como se muestra mediante los arcos de rayas en la figura 6.26. Para el arco (i,j), la notación proporciona las capacidades de flujo en las dos direcciones i S j y j S i. Para eliminar la ambigüedad, colocamos a junto al nodo i y a junto al nodo Cji, como se muestra en la figura.

Enumeración de cortes: Un corte define un conjunto de arcos cuya eliminación de la red interrumpe el flujo entre los nodos fuente y sumidero. La capacidad de corte es igual a la suma de las capacidades de su conjunto de arcos. Entre todos los cortes posibles en la red, el corte con la capacidad mínima es el cuello de botella que determina el flujo máximo en la red. Algoritmo de flujo máximo: Este algoritmo se basa en el hallazgo de rutas de avance con flujo positivo entre los nodos fuente y sumidero. Cada ruta destina una parte de o todas las capacidades de sus arcos al flujo total en la red. Considere el arco (i, j) con las capacidades bidireccionales (de diseño) (cij, cji). Como algunas partes de estas capacidades se destinan al flujo en el arco, los residuos (capacidades no utilizadas, o flujo remanente) del arco se actualizan. Utilizamos la notación (cij, cji) para representar los residuos. Para un nodo j que recibe flujo del nodo i, anexamos la etiqueta [aj,i] donde aj es el flujo del nodo i al nodo j.

Ejemplos: Considere la red de la figura 6.28. Las capacidades bidireccionales se muestran en los arcos respectivos por medio de la convención utilizada en la figura 6.27. Por ejemplo, el límite de flujo para el arco (3,4) es de 10 unidades de 3 a 4, y de 5 unidades de 4 a 3. La figura 6.28 ilustra tres cortes con las siguientes capacidades:

La única información de los tres cortes es que el flujo máximo en la red no puede exceder de 60 unidades. Para determinar el flujo máximo es necesario enumerar todos los cortes, una tarea difícil para la red general. Por lo tanto, la necesidad de un algoritmo eficiente es imperativa.

Determine el flujo máximo en la red del ejemplo 6.4-1 (figura 6.28). La figura 6.30 proporciona un resumen gráfico de las iteraciones del algoritmo. Verá que es útil comparar la descripción de las iteraciones con el resumen gráfico.

4.3 El Modelo Del Árbol De Expansión Mínima Este árbol vincula los nodos de una red valiéndose de la longitud mínima total de las ramas de conexión. Una aplicación común se presenta en la pavimentación de

carreteras que unen poblaciones, o de forma directa, o que pasan por otras poblaciones. La solución del árbol de mínima expansión proporciona el diseño del sistema de carreteras. Sea N = {1, 2,…,n} el conjunto de nodos de la red y defina Ck = Conjunto de nodos que han estado conectados de manera permanente en la iteración Ck = Conjunto de nodos que se construirán permanentemente después de la iteración k Los siguientes pasos describen al algoritmo del árbol de mínima expansión: Paso 0. Establezca CO = Ø Y C 0 = N Paso 1. Inicie con cualquier nodo i en el conjunto no conectado C o y establezca C1 = [i] , lo que produce C1 = N – [i] . Establezca k = 2. Paso general k. Seleccione un nodo, j*, en el conjunto no conectado Ck-1, que produzca el arco más corto a un nodo en el conjunto Ck-1 conectado. Vincule j* permanentemente a Ck-1 y elimínelo de

CK- 1 para obtener CK Y CK

respectivamente. Deténgase si CK está vacío; de lo contrario, establezca k = k + 1 y repita el paso.  Ejemplo 1 Dada la siguiente red obtenga el árbol de expansión mínima

El árbol de expansión mínima es: 200 + 224 + 300 + 283 + 200 + 400 = 1607

 Ejemplo 2

Midwest TV Cable Company va a proporcionar servicio de cable a cinco desarrollos habitacionales. La figura 6.6 ilustra las posibles conexiones de TV a las cinco áreas, con las millas de cable anexadas a cada arco. El objetivo es determinar la red de cables más económica. El algoritmo se inicia en el nodo 1 (en realidad, cualquier otro nodo puede ser un punto de inicio), el cual da por resultado Las iteraciones del algoritmo se resumen en la figura 6.7. Los arcos delgados proporcionan todos los candidatos entre C y. Los arcos gruesos son los vínculos permanentes del conjunto conectado C, y el arco de rayas es el nuevo vínculo (permanente) agregado en cada iteración. Por ejemplo, en la iteración 1, la rama (1, 2) es el vínculo más corto (5 1 milla) entre todas las ramas candidatas del nodo 1 a los nodos 2, 3, 4, 5 y 6 en el conjunto no conectado. De ahí que el vínculo (1, 2) se hace permanente y j* 5 2, de lo cual resulta C2 = {1, 2}, C2 = {3, 4, 5, 6} C1 C El árbol de mínima expansión que se muestra en la iteración 6 de la figura 6.7 da la solución. Las millas de cable mínimas resultantes que se necesitan para proporcionar el servicio de cable deseado son 1 + 3 + 4 + 3 + 5 = 16 millas. Comentarios. En teoría, un árbol de mínima expansión puede formularse y resolverse como un programa lineal. Sin embargo, la PL no es una opción práctica porque deben agregarse numerosas restricciones para excluir todos los ciclos y el resultado es una PL enorme, aun para redes pequeñas.

Unidad 4: Modelos De Flujos En Redes Una red se compone de un conjunto de nodos unidos por arcos (o ramas). La notación para describir una red es (N, A), donde N es el conjunto de nodos, y A es el conjunto de arcos. N = {1, 2, 3, 4, 5} A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}

4.1 El Modelo Del Camino Más Corto

Este problema determina la ruta más corta entre un origen y un destino en una red de transporte. El mismo modelo puede representar otras situaciones. Esta sección presenta dos algoritmos para resolver tanto redes cíclicas (es decir, que contienen bucles) como redes acíclicas: 1. El algoritmo de Dijkstra para determinar las rutas más cortas entre el nodo origen y los demás nodos en la red. 2. El algoritmo de Floyd para determinar la ruta más corta entre dos nodos cualesquiera en la red. En esencia, el algoritmo de Floyd incluye a Dijkstra. Algoritmo de Dijkstra. Sea Ui la distancia más corta del nodo origen 1 al nodo i, y defina Dij (≥ 0) como la longitud del arco (i,j). El algoritmo define la etiqueta para un nodo j que sigue inmediatamente como:

La

etiqueta

para

el nodo

de

inicio es

[0, 2], que indica que el nodo no tiene predecesor. Las etiquetas de nodo en el algoritmo de Dijkstra son de dos tipos: temporales y permanentes. Una etiqueta temporal en un nodo se modifica si puede hallarse una ruta más corta al nodo. De lo contrario, el estado temporal cambia a permanente.

Ejemplo 1: La red de la figura muestra las rutas permisibles y sus longitudes en millas entre la ciudad 1 (nodo 1) y las otras cuatro ciudades (nodos 2 a 5). Determine las rutas más cortas entre la ciudad 1 y cada una de las cuatro ciudades restantes.

Iteración 0. Asigne una etiqueta permanente [0, 2] al nodo 1. Iteración 1. Se puede llegar a los nodos 2 y 3 desde el nodo 1 (el último etiquetado permanentemente). Así, la lista de nodos etiquetados (temporales y permanentes) es:

Para las dos etiquetas temporales [100,1] y [30,1], el nodo 3 da la distancia mínima (u3 = 30). De este modo, el estado del nodo 3 cambia a permanente. Iteración 2. Se puede llegar a los nodos 4 y 5 desde el nodo 3, y la lista de los nodos etiquetados es:

La etiqueta temporal [40,3] en el nodo 4 ahora es permanente (u4 = 40). Iteración 3. Desde el nodo 4 se puede llegar a los nodos 2 y 5 Así, la lista de los nodos etiquetados se actualiza como:

En el nodo 2, la nueva etiqueta [55,4] reemplaza a la etiqueta temporal [100,1] de la iteración 1 porque proporciona una ruta más corta. Además, en la iteración 3 el nodo 5 tiene dos etiquetas alternativas con la misma distancia (u5 5 90). La etiqueta temporal [55,4] en el nodo 2 ahora es permanente (u2 = 55). Iteración 4. Sólo el nodo 3 permanentemente etiquetado puede ser alcanzado desde el nodo 2. Por consiguiente el nodo 3 no puede ser reetiquetado. La nueva lista de etiquetas permanece como estaba en la iteración 3 excepto que la etiqueta en el nodo 2 ahora es permanente. Esto deja al nodo 5 como la única etiqueta temporal. Como el nodo 5 no conduce a otros nodos, su etiqueta se hace permanente, y el proceso termina. Los cálculos del algoritmo pueden realizarse directamente en la red, como lo demuestra la figura:

La ruta más corta entre el nodo 1 y cualquier otro nodo en la red se determina partiendo del nodo destino deseado y retrocediendo hasta el nodo de inicio utilizando la información en las etiquetas permanentes. Por ejemplo, la siguiente secuencia determina la ruta más corta del nodo 1 al nodo 2:

Por lo tanto, la ruta deseada es 1 ⇒ 3 ⇒ 4 ⇒ 2 con una distancia total de 55 millas. Ejemplo 2: I. Q. Smart va en auto diariamente al trabajo. Habiendo completado un curso de análisis de redes, Smart es capaz de determinar la ruta más corta al trabajo. Por desgracia, la ruta seleccionada está fuertemente patrullada por la policía, y con todas las multas pagadas por exceso de velocidad, la ruta más corta puede no ser la mejor opción. Smart ha decidido por lo tanto elegir una ruta que maximice la probabilidad de no ser detenido por la policía. La red en la figura muestra las posibles rutas de la casa al trabajo y la probabilidad asociada de no ser detenido en cada segmento. La probabilidad de no ser detenido en la ruta es el producto de las probabilidades de sus segmentos. Por ejemplo, la probabilidad de no ser multado en la ruta 1 ⇒ 3 ⇒ 5 ⇒ 7 es .9 3 .3 3 .25 5 .0675. El objetivo de Smart es seleccionar la ruta que maximice la probabilidad de no ser multado.

El problema puede formularse como un modelo de la ruta más corta por medio de una transformación logarítmica para convertir el producto de las probabilidades en la suma de los logaritmos de las probabilidades, esto es, p1k x p1 x p2 3 … x pk se transforma en log p1k = log p1 1 log p2 1 … 1 log pk. Las dos funciones p1k y log p1k son monótonas y decrecen en k, así pues, maximizar p1k es equivalente a maximizar log p1k, lo que a su vez equivale a minimizar log p1k. Por lo tanto, al reemplazar pj con log pj para toda la j en la red, el problema se convierte en la red de la ruta más corta en la figura:

4.2 El Modelo De Flujo Máximo Considere una red de oleoductos que transporta petróleo crudo desde pozos hasta refinerías. Se instalan estaciones intermedias de reforzamiento y bombeo a distancias apropiadas para mover el crudo en la red. Cada segmento de tubería tiene una velocidad de descarga finita (o capacidad) de flujo de crudo. Un segmento de tubería puede ser unidireccional o bidireccional, según su diseño. La figura 6.26 muestra una red de oleoductos típica. El objetivo es determinar la capacidad de flujo máxima de la red. La solución del problema propuesto requiere agregar una sola fuente y un solo sumidero o vertedero, utilizando arcos de capacidad infinita unidireccionales, como se muestra mediante los arcos de rayas en la figura 6.26. Para el arco (i,j), la notación proporciona las capacidades de flujo en las dos

direcciones i S j y j S i. Para eliminar la ambigüedad, colocamos a junto al nodo i y a junto al nodo Cji, como se muestra en la figura.

Enumeración de cortes: Un corte define un conjunto de arcos cuya eliminación de la red interrumpe el flujo entre los nodos fuente y sumidero. La capacidad de corte es igual a la suma de las capacidades de su conjunto de arcos. Entre todos los cortes posibles en la red, el corte con la capacidad mínima es el cuello de botella que determina el flujo máximo en la red. Algoritmo de flujo máximo: Este algoritmo se basa en el hallazgo de rutas de avance con flujo positivo entre los nodos fuente y sumidero. Cada ruta destina una parte de o todas las capacidades de sus arcos al flujo total en la red. Considere el arco (i, j) con las capacidades bidireccionales (de diseño) (cij, cji). Como algunas partes de estas capacidades se destinan al flujo en el arco, los residuos (capacidades no utilizadas, o flujo remanente) del arco se actualizan. Utilizamos la notación (cij, cji) para representar los residuos. Para un nodo j que recibe flujo del nodo i, anexamos la etiqueta [aj,i] donde aj es el flujo del nodo i al nodo j.

Ejemplos: Considere la red de la figura 6.28. Las capacidades bidireccionales se muestran en los arcos respectivos por medio de la convención utilizada en la figura 6.27. Por ejemplo, el límite de flujo para el arco (3,4) es de 10 unidades de 3 a 4, y de 5 unidades de 4 a 3. La figura 6.28 ilustra tres cortes con las siguientes capacidades:

La única información de los tres cortes es que el flujo máximo en la red no puede exceder de 60 unidades. Para determinar el flujo máximo es necesario enumerar todos los cortes, una tarea difícil para la red general. Por lo tanto, la necesidad de un algoritmo eficiente es imperativa.

Determine el flujo máximo en la red del ejemplo 6.4-1 (figura 6.28). La figura 6.30 proporciona un resumen gráfico de las iteraciones del algoritmo. Verá que es útil comparar la descripción de las iteraciones con el resumen gráfico.

4.3 El Modelo Del Árbol De Expansión Mínima Este árbol vincula los nodos de una red valiéndose de la longitud mínima total de las ramas de conexión. Una aplicación común se presenta en la pavimentación de

carreteras que unen poblaciones, o de forma directa, o que pasan por otras poblaciones. La solución del árbol de mínima expansión proporciona el diseño del sistema de carreteras. Sea N = {1, 2,…,n} el conjunto de nodos de la red y defina Ck = Conjunto de nodos que han estado conectados de manera permanente en la iteración Ck = Conjunto de nodos que se construirán permanentemente después de la iteración k Los siguientes pasos describen al algoritmo del árbol de mínima expansión: Paso 0. Establezca CO = Ø Y C 0 = N Paso 1. Inicie con cualquier nodo i en el conjunto no conectado C o y establezca C1 = [i] , lo que produce C1 = N – [i] . Establezca k = 2. Paso general k. Seleccione un nodo, j*, en el conjunto no conectado Ck-1, que produzca el arco más corto a un nodo en el conjunto Ck-1 conectado. Vincule j* permanentemente a Ck-1 y elimínelo de

CK- 1 para obtener CK Y CK

respectivamente. Deténgase si CK está vacío; de lo contrario, establezca k = k + 1 y repita el paso.  Ejemplo 1 Dada la siguiente red obtenga el árbol de expansión mínima

El árbol de expansión mínima es: 200 + 224 + 300 + 283 + 200 + 400 = 1607

 Ejemplo 2

Midwest TV Cable Company va a proporcionar servicio de cable a cinco desarrollos habitacionales. La figura 6.6 ilustra las posibles conexiones de TV a las cinco áreas, con las millas de cable anexadas a cada arco. El objetivo es determinar la red de cables más económica. El algoritmo se inicia en el nodo 1 (en realidad, cualquier otro nodo puede ser un punto de inicio), el cual da por resultado Las iteraciones del algoritmo se resumen en la figura 6.7. Los arcos delgados proporcionan todos los candidatos entre C y. Los arcos gruesos son los vínculos permanentes del conjunto conectado C, y el arco de rayas es el nuevo vínculo (permanente) agregado en cada iteración. Por ejemplo, en la iteración 1, la rama (1, 2) es el vínculo más corto (5 1 milla) entre todas las ramas candidatas del nodo 1 a los nodos 2, 3, 4, 5 y 6 en el conjunto no conectado. De ahí que el vínculo (1, 2) se hace permanente y j* 5 2, de lo cual resulta C2 = {1, 2}, C2 = {3, 4, 5, 6} C1 C El árbol de mínima expansión que se muestra en la iteración 6 de la figura 6.7 da la solución. Las millas de cable mínimas resultantes que se necesitan para proporcionar el servicio de cable deseado son 1 + 3 + 4 + 3 + 5 = 16 millas. Comentarios. En teoría, un árbol de mínima expansión puede formularse y resolverse como un programa lineal. Sin embargo, la PL no es una opción práctica porque deben agregarse numerosas restricciones para excluir todos los ciclos y el resultado es una PL enorme, aun para redes pequeñas.

5.1 Construcción de redes de actividades de un proyecto El Método del Camino Crítico es una parte de la fase administrativa de planeación que se encarga de la programación, ejecución y control de un proyecto que deba realizarse con aprovechamiento óptimo de tiempo y costos destinados al mismo. No solo se denomina Camino Crítico al sistema total, sino también se le llama así a la serie de actividades, a partir de la iniciación y hasta la terminación del proyecto que no tienen posibilidad de variación en su tiempo de ejecución, ya que si una de ellas retrasara el proyecto total sufrirá el mismo efecto. También se entiende por camino crítico a la secuencia de actividades que ocupan el mayor tiempo de ejecución del proyecto y con lo cual definen la duración total del mismo. El Método del Camina Crítico tiene una variada gama de aplicaciones dentro de la Administración moderna, además de aquellas correspondientes a la industria de la construcción de procesos industriales. Algunos de los proyectos de carácter administrativo financiero o mercadotécnico que pueden ser desarrollados mediante el Método del Camino Crítico son: Lanzamiento de un nuevo producto al mercado. Instalación y puesta en marcha de un sistema de Cómputo Electrónico. Preparación del presupuesto de una obra civil. Realización de Auditorías de Estados Financieros. Etc. Prevaleciendo como características de los proyectos el que: No sean cíclicos o repetitivos dentro del trabajo cotidiano. Se busque realizarlos con el óptimo aprovechamiento de los recursos financieros, humanos y materiales dentro del tiempo programado. PASOS PARA ELABORAR UNA RED DE ACTIVIDADES.

En todo proyecto será necesario dividir el Método del Camino Crítico en dos etapas: 1.- Planeación y Programación 2.- Ejecución y Control a) Definición y Objetivos del Proyecto. En él se evalúa la factibilidad de éxito del mismo, si se cuenta con los recursos necesarios, así como la época más viable para el inicio tomando en cuenta las necesidades de la empresa y sus directivos, la carga del trabajo en determinadas temporadas, etc. b) Lista de Actividades a realizar. Es el detalle de las funciones a ejecutar ya sean físicas o mentales, que integran procesos o fases que se interrelacionan en el desarrollo de un proyecto. c) Matrices o tablas de información •Matriz de antecedentes y secuencias. -esta tabla de información permite interrelacionar las actividades indicando cuáles deberán ser elaboradas antes o después según la secuencia del desarrollo del proyecto. Para ser llenada se prepara una hoja con 4 columnas cuyos encabezados son: Antecedentes, Actividad Núm., Secuencias y Anotaciones. •Matriz de tiempos. - Se procede a elaborar la correspondiente a los tiempos estimados para la realización de cada actividad programada y así obtener la duración total de un proyecto. Aplicando la fórmula PERT permitirá calcular el tiempo estándar (te) el cual será usado en el proyecto. Tiempo óptimo (o) representa el mínimo posible de consumir la actividad. Tiempo Normal (M) es el que en condiciones normales se necesita para la ejecución de las actividades programadas. Tiempo pésimo (p) es el máximo necesario para realizar la actividad si todo saliera mal. Tiempo estándar (te) te = 0 + 4M + p 6 •Matriz de costos y pendientes. - Se solicita a los responsables del proyecto que proporcionen el costo expresado en unidades monetarias; ya con los datos solicitados se calcula la pendiente (m) que es la relación que guardan el tiempo y el costo. d) Red o gráfica de actividades (símbolos). Se llama así a la representación gráfica de la matriz de antecedentes, secuencias y tiempos, mediante ella es posible mostrar en forma clara y comprensible la relación, interrelación, secuencias,

etc., de las actividades a realizar así como el camino crítico. Las actividades se representan mediante flechas las cuales indican el tiempo que se ocupará en su realización. Estas flechas pueden ser rectas, curvas, quebradas, etc., según las necesidades en el trazo de la red, ejemplos:

En algunos casos, al trazar la red, es necesario indicar la relación de una actividad con otro u horas, para lo cual es necesario dibujar flechas que indiquen dicha relación; este tipo de flechas, al no representar consumo de tiempo y/o recursos, se dibujan en forma punteada, ejemplos:

A estas actividades se les conoce con los nombres de actividades ficticias o "ligas". Todas las ligas se dibujarán de izquierda a derecha (a excepción de aquellas actividades reales que por ser muy breve su duración se represente con cero de tiempo y por lo tanto se dibujarán en forma

ascendente o descendente), y tanto al inicio como al término de cada una de ellas es necesario dibujar un pequeño círculo (o) el cual se denomina como "evento" o "nodo", los que señalarán el principio o fin de la actividad, ejemplos:

Al evento de iniciación se le conoce como evento "i" y al de la finalización como evento "j", el evento final de una actividad será el inicial de la actividad siguiente. De un evento pueden iniciar o terminar varias actividades, ejemplo:

Al dibujar la Red es conveniente evitar: 1) Que dos o más actividades que inicien de un mismo evento terminen, también, en un mismo evento, ejemplo:

Ya que puede provocar error al interpretarla, por lo que se recomienda el uso de luna "liga" o actividad ficticia para relacionarlos, ejemplo:

2) No puede iniciar una actividad a la mitad de la otra

Y para evitarlo es necesario dividir en dos la actividad en donde se origine el problema. 3) No se deben tener al iniciar la red, varios eventos que parten de actividades distintas sin relacionarlos entre sí, mediante ligas, ejemplo

4) El mismo cuidado se debe tener al finalizar la red, ejemplo

5) Cuando existe alguna actividad con duración de cero, se dibuja así:

Para trazar la red se utiliza, preferentemente, papel cuadriculado dibujando primero una escala de tiempos que represente la división utilizada al calcular la matriz (horas, días semanas, meses, etc.) Es siempre conveniente dibujar la red con lápiz ya que, normalmente, se cambiarán de lugar algunas actividades para facilitar su construcción. Para finalizar el dibujo de una red se trazan las ligas a partir de las actividades hasta el último nodo o evento ya trazado, quedando totalmente terminada la red del proyecto el cual tendrá una duración a tiempo estándar (te). Una vez que la Red de Actividades del proyecto ha sido concluida, se conoce la duración total del mismo el cual puede ser: Menor del tiempo previsto.- En este caso se puede decir que la Red de está terminada y se procede a calcular los costos del proyecto. Igual del tiempo previsto.- Se procede igual que en el inciso anterior. Mayor del tiempo previsto.- En este caso obliga a cumplir el tiempo de algunas actividades, con el objetivo de reducir el tiempo del proyecto obtenido por el programado por la dirección. e) Elasticidad y probabilidad de retraso. La segunda etapa se divide a su vez en: .

a) Graficas de control b) Ajustes y Evaluación de resultados

de

tiempos

y

costos

5.2 Aplicación métodos de planeación, programación y control de proyectos para determinar la ruta crítica bajo condiciones de certidumbre e incertidumbre.

Definición.El método del camino crítico es un proceso administrativo de planeación, programación, ejecución y control de todas y cada una de las actividades componentes de un proyecto que debe desarrollarse dentro de un tiempo crítico y al costo óptimo. Usos. El campo de acción de este método es muy amplio, dada su gran flexibilidad y adaptabilidad a cualquier proyecto grande o pequeño. Para obtener los mejores resultados debe aplicarse a los proyectos que posean las siguientes características:  Que el proyecto sea único, no repetitivo, en algunas partes o en su totalidad.  Que se deba ejecutar todo el proyecto o parte de el, en un tiempo mínimo, sin variaciones, es decir, en tiempo crítico.  Que se desee el costo de operación más bajo posible dentro de un tiempo disponible. Dentro del ámbito aplicación, el método se ha estado usando para la planeación y control de diversas actividades, tales como construcción de presas, apertura de caminos, pavimentación, construcción de casas y edificios, reparación de barcos, investigación de mercados, movimientos de colonización, estudios económicos regionales, auditorías, planeación de carreras universitarias, distribución de tiempos de salas de operaciones, ampliaciones de fábrica, planeación de itinerarios para cobranzas, planes de venta, censos de población, etc., etc. DIFERENCIAS ENTRE PERT Y CPM Como se indicó antes, la principal diferencia entre PERT y CPM es la manera en que se realizan los estimados de tiempo. E1 PERT supone que el tiempo para realizar cada una de las actividades es una variable aleatoria descrita por una distribución de probabilidad. E1 CPM por otra parte, infiere que los tiempos de las actividades se conocen en forma determinísticas y se pueden variar cambiando el nivel de recursos

utilizados.

La distribución de tiempo que supone el PERT para una actividad es una distribución beta. La distribución para cualquier actividad se define por tres estimados: (1) el estimado de tiempo más probable, m; (2) el estimado de tiempo más optimista, a; y (3) el estimado de tiempo más pesimista, b La forma de la distribución se muestra en la siguiente Figura tiempo más probable es el tiempo requerido para completar la actividad bajo condiciones normales. Los tiempos optimistas y pesimistas proporcionan una medida de la incertidumbre inherente en la actividad, incluyendo desperfectos en el equipo, disponibilidad de mano de obra, retardo en los materiales y otros factores. Con la distribución definida, la media (esperada) y la desviación estándar, respectivamente, del tiempo de la actividad para la actividad Z puede calcularse por medio de las fórmulas de aproximación El tiempo esperado de finalización de un proyecto es la suma de todos los tiempos esperados de las actividades sobre la ruta crítica. De modo similar, suponiendo que las distribuciones de los tiempos de las actividades son independientes (realísticamente, una suposición fuertemente cuestionable), la varianza del proyecto es la suma de las varianzas de las actividades en la ruta crítica. Estas propiedades se demostrarán posteriormente En CPM solamente se requiere un estimado de tiempo. Todos los cálculos se hacen con la suposición de que los tiempos de actividad se conocen. A medida que el proyecto avanza, estos estimados se utilizan para controlar y monitorear el progreso. Si ocurre algún retardo en el proyecto, se hacen esfuerzos por lograr que el proyecto quede de nuevo en programa cambiando la asignación de recursos.

cambiando la asignación de recursos. Metodología. El Método del Camino Critico consta de dos ciclos: 1. Planeación y Programación. Definición del proyecto Lista de Actividades Matriz de Secuencias Matriz de Tiempos

2. Ejecución y Control Aprobación del proyecto Ordenes de trabajo Gráficas de control Reportes y análisis de los avances

Red de Actividades Toma de decisiones y ajustes Costos y pendientes Compresión de la red Limitaciones de tiempo, de recursos y económicos Matriz de elasticidad Probabilidad de retraso

Definición del Proyecto En toda actividad a realizar se requieren conocimientos precisos y claros de lo que se va a ejecutar, de su finalidad, viabilidad, elementos disponibles, capacidad financiera, etc. Esta etapa aunque esencial para la ejecución del proyecto no forma parte del método. Es una etapa previa que se debe desarrollar separadamente y para la cual también puede utilizarse el Método del Camino Critico. Es una investigación de objetivos, métodos y elementos viables y disponibles.

Lista de Actividades Es la relación de actividades físicas o mentales que forman procesos interrelacionados en un proyecto total. En general esta información es obtenida de las personas que intervendrán en la ejecución del proyecto, de acuerdo con la asignación de responsabilidades y nombramientos realizados en la Definición del Proyecto. Las actividades pueden ser físicas o mentales, como construcciones, tramites, estudios, inspecciones, dibujos, etc. En términos generales, se considera Actividad a la serie de operaciones realizadas por una persona o grupo de personas en forma continua, sin interrupciones, con tiempos determinables de iniciación y terminación. Esta lista de actividades sirve de base a las personas responsables de cada proceso para que elaboren sus presupuestos de ejecución.

Ejemplo: Jefes de mantenimiento y producción. Elaboración del proyecto parcial de ampliación. Calculo del costo y preparación de presupuestos Aprobación del proyecto Desempaque de las maquinas nuevas Colocación de las maquinas viejas y nuevas. Instalación de las maquinas Pruebas generales Arranque general Revisión y limpieza de maquinas viejas Pintura de maquinas viejas Pintura y limpieza del edificio Ingeniero electricista. Elaboración del proyecto eléctrico Calculo de los costos y presupuestos. Aprobación del proyecto Instalación de un transformador nuevo Instalación de nuevo alumbrado Instalación de interruptores y arrancadores Ingeniero contratista Elaboración del proyecto de obra muerta Calculo de los costos y presupuestos. Aprobación del proyecto Cimentación de las máquinas Pisos nuevos. Colocación de ventanas nuevas

          

     

     

Esta es una lista de los responsables en un proyecto de ampliación de una fabrica

Matriz de Secuencias Existen dos procedimientos para conocer la secuencia de las actividades: (1) Por antecedentes (2) Por secuencias Por antecedentes, se les preguntará a los responsables de los procesos cuales actividades deben quedar terminadas para ejecutar cada una de las que aparecen en la lista. Debe tenerse especial cuidado que todas y cada una de las actividades tenga por lo menos una antecedente excepto en el caso de ser actividades iniciales, en cuyo caso su antecedente será cero(0) En el segundo procedimiento se preguntara a los responsables de la ejecución, cuales actividades deben hacerse al terminar cada una de las que aparecen en la lista. Para este efecto debemos presentar la matriz de secuencias iniciando con la actividad cero(0) que servira para indicar solamente el punto de partida de las demás. La información debe tomarse una por una de las actividades listadas, sin pasar por alto ninguna de ellas

En la columna de "anotaciones" el programador hara todas las indicaciones que le ayuden a aclarar situaciones de secuencias y presentación de la red. Estas anotaciones se hacen a discreción, ya que esta matriz es solamente un papel de trabajo. Si se hace una matriz de antecedentes es necesario hacer después una matriz de secuencias, pues es ésta última la que se utiliza para dibujar la red. Esta matriz no es definitiva, porque generalmente se hacen ajustes posteriores en relación con la existencia y disponibilidades de materiales, mano de obra y otras limitaciones de ejecución. Por Matriz de Secuencias Matriz de Tiempos En el estudio de tiempos se requieren tres cantidades estimadas por los responsables de los procesos: El tiempo medio (M), el tiempo óptimo (o) y el tiempo pésimo (p) El tiempo medio (M) es el tiempo normal que se necesita para la ejecución de las actividades, basado en la experiencia personal del informador. El tiempo óptimo (o) es el que representa el tiempo mínimo posible sin importar el costo o cuantía de elementos materiales y humanos que se requieran; es simplemente la posibilidad física de realizar la actividad en el menor tiempo. El tiempo pésimo (p) es un tiempo excepcionalmente grande que pudiera presentarse ocasionalmente como consecuencia de accidentes, falta de suministros, retardos involuntarios, causas no

previstas, etc. Debe contarse sólo el tiempo en que se ponga remedio al problema presentado y no debe contar el tiempo ocioso.