Embed Size (px)
Citation preview
FELIPE DE JESUS MORENO OVANDO
Investigación de operaciones II
PORTAFOLIO DE EVIDENCIAS
CRISTINA BASAÑEZ FUENTES -CAROLINA BASAÑEZ FUENTES
INGENIERIA INDUSTRIAL 5 “A”
INTRODUCCIÓN
Las técnicas de flujo de redes están orientadas
a optimizar situaciones vinculadas a las redes
de transporte, redes de comunicación, sistema
de vuelos de los aeropuertos, rutas de
navegación de los cruceros, estaciones de
bombeo que transportan fluidos a través de
tuberías, rutas entre ciudades, redes de
conductos y todas aquellas situaciones que
puedan representarse mediante una red donde
los nodos representan las estaciones o las
ciudades, los arcos los caminos, las líneas
aéreas, los cables, las tuberías y el flujo lo
representan los camiones, mensajes y fluidos
que pasan por la red. Con el objetivo de
encontrar la ruta más corta si es una red de
caminos o enviar el máximo fluido si es una red
de tuberías.
INGENIERIA INDUSTRIAL 5 “A”
Cuando se trata de encontrar el camino más
corto entre un origen y un destino, la técnica,
algoritmo o el modelo adecuado es el de la ruta
más corta; aunque existen otros modelos de
redes como el árbol de expansión mínima, flujo
máximo y flujo de costo mínimo cada uno
abarca un problema en particular. En este
trabajo se mencionan los modelos de redes
existentes y los problemas que abarca cada uno
de ellos, además se describen los algoritmos
que aplican estos modelos para encontrar la
solución óptima al problema. Utilizando la
terminología utilizada para representarlos como
una red.
NOTACIÓN Y TERMINOLOGÍA
CONCEPTOS BÁSICOS EN TEORÍA DE REDES
Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas líneas llamadas ramales o arcos.
INGENIERIA INDUSTRIAL 5 “A”
Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y que se compone por los elementos [1-4, 4-7]. Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso [1,
4, 7].
Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].
INGENIERIA INDUSTRIAL 5 “A”
Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.
Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.
Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran orientados hacia afuera. Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran orientados hacia él.
Red: Una red consiste en un conjunto de puntos
y un conjunto de líneas que unen ciertos pares
Nodo
Arco
Figura 1. Representación de una Red
A
O
C
B
E
D
T
INGENIERIA INDUSTRIAL 5 “A”
de puntos. Los puntos se llaman nodos (o
vértices). Las líneas se llaman arcos (o
ligaduras, aristas o ramas).
Los arcos se etiquetan para dar nombres a los
nodos en sus puntos terminales, por ejemplo,
AB es el arco entre lo nodos A Y B.
En un problema de programación lineal, las
redes pueden representar un conjunto de
estaciones, campos petrolíferos, almacenes,
A B
Figura 2. Representación de un Arco Dirigido
INGENIERIA INDUSTRIAL 5 “A”
fabricas, sucursales, ciudades, interconectadas
entre si a través de caminos, conductos,
tuberías que permiten fluir productos para la
comercialización o la distribución.
Arcos Dirigidos: Se dice que un arco es
dirigido cuando el arco tiene flujo en una
dirección (como en una calle de un sentido). La
dirección se indica agregando una cabeza de
flecha al final de la línea que representa el arco.
Al etiquetar un arco dirigido con el nombre de
los nodos que une, siempre se coloca primero al
nodo de donde viene y después el nodo a donde
va, esto es, un arco dirigido del nodo A al nodo
B debe etiquetarse como AB y no como BA.
Otra Manera es A→B.
A B
Figura 3. Representación de un Arco No Dirigido
INGENIERIA INDUSTRIAL 5 “A”
Arcos No Dirigidos: Si el flujo a través de un
arco se permite en ambas direcciones (como
una tubería que se puede usar para bombear
fluido en ambas direcciones), se dice que es un
arco no dirigido.
También se les llama ligadura. Aunque se
permita que el flujo a través de un arco no
dirigido ocurra en cualquier dirección, se supone
que ese flujo será en una dirección, en la
seleccionada, y no se tendrá flujos simultáneos
en direcciones opuestas.
Trayectoria: Una trayectoria entre dos nodos
es una sucesión de arcos distintos que conectan
estos nodos. Por ejemplo, una de las
trayectorias que conectan los nodos O y T en la
figura 4 es la sucesión de arcos OB-BD-DT (O→B
→D→T), y viceversa.
Figura 4. Representación de una Trayectoria
A
O
C
B
E
D
T
INGENIERIA INDUSTRIAL 5 “A”
Cuando algunos o todos los arcos de una red
son arcos dirigidos, se hace la distinción entre
trayectorias dirigidas y trayectorias no dirigidas.
Trayectoria Dirigida: Una trayectoria dirigida
del nodo i al nodo j, es una sucesión de arcos
cuya dirección (si la tienen) es hacia el nodo j,
de manera que el flujo del nodo i al nodo j, a
través de esta trayectoria es factible.
Trayectoria No Dirigida: Una trayectoria no
dirigida del nodo i al nodo j es una sucesión de
arcos cuya dirección (si la tienen) pueden ser
Figura 5. Representación de un Ciclo
A
O
C
B
E
D
T
INGENIERIA INDUSTRIAL 5 “A”
hacia o desde el nodo j. Con frecuencia alguna
trayectoria no dirigida tendrá algunos arcos
dirigidos hacia el nodo j y otros desde él (es
decir, hacia el nodo i).
Ciclo: Un ciclo es una trayectoria que comienza
y termina en el mismo nodo. En la red no
dirigida que se muestra en la figura 5 existen
muchos ciclos, OA-AB-BC-CO.
Figura 6. Red Conexa
B
A
E
D
C
INGENIERIA INDUSTRIAL 5 “A”
Red Conexa: Una red conexa es una red en la
que cada par de nodos está conectado. Se dice
que dos nodos están conectados si la red
contiene al menos una trayectoria no dirigida
entre ellos. Se debe resaltar que no es
necesario que la trayectoria sea dirigida aun
cuando la red sea dirigida. La figura 6
representa una red conexa.
Capacidad de Arco: Es la cantidad máxima de
flujo (quizás infinito) que puede circular en un
arco dirigido.
INGENIERIA INDUSTRIAL 5 “A”
Nodo Fuente: (o nodo de origen) tiene la
propiedad de que el flujo que sale del nodo
excede al flujo que entra a él.
Nodo Demanda: (o nodo destino) es el caso
contrario al nodo fuente, donde el flujo que
llega excede al que sale de él.
Nodo de Trasbordo: (o nodo intermedio)
satisface la conservación del flujo, es decir, el
flujo que entra es igual al que sale.
REDES DIRIGIDAS Y NO DIRIGIDAS
Red Dirigida: Es una red que tiene solo arcos
dirigidos.
B
A
E
D
C
Figura 9. Representación de una Red Dirigida
INGENIERIA INDUSTRIAL 5 “A”
En una red dirigida, un ciclo puede ser dirigido o
no dirigido, según si la trayectoria en cuestión
es dirigida o no dirigida. (Como una trayectoria
dirigida también es no dirigida, un ciclo dirigido
es un ciclo no dirigido, pero en general el
inverso no es cierto.) Por ejemplo en la figura 9
DE-ED es un ciclo dirigido. Por contrario, AB-BC-
CA no es un ciclo dirigido puesto que la
dirección del arco AC es opuesta a la de los
arcos AB y BC. Por otro lado, AB-BC-AC no es
un ciclo dirigido porque ABCA es una trayectoria
no dirigida.
B
A
E
D
C
Figura 10. Representación de una Red No Dirigida
INGENIERIA INDUSTRIAL 5 “A”
Red No Dirigida: Es una red donde todos sus
arcos son no dirigidos. La figura 10 representa
una red no dirigida.
5.2 PROBLEMA DE LA RUTA MÁS CORTA. REDES CÍCLICAS Y ACÍCLICAS.
Aunque al final de la sección se mencionan
otras versiones del problema de la ruta más
corta—Incluso algunas para redes dirigidas—, la
atención se centrará en la siguiente versión
sencilla. Considere una red conexa y no dirigida
con dos nodos especiales llamados origen y
destino. A cada Ligadura (arco no dirigido) se
asocia una distancia no negativa. El objetivo es
INGENIERIA INDUSTRIAL 5 “A”
encontrar la ruta más Corta —la trayectoria con
la mínima distancia total— del origen al destino.
Se dispone de un algoritmo relativamente
sencillo para manejar este problema. La esencia
del procedimiento es que analiza toda la red a
partir del origen; identifica de manera sucesiva
la ruta más corta a cada uno de los nodos en
orden ascendente de sus distancias (más
cortas), desde el origen; el problema queda
resuelto en el momento de llegar al nodo
destino. Primero se describirá el método y
después se ejemplificará con la solución del
problema de la ruta más corta que enfrenta la
administración de Seervada Park en la sección
9.1.
Algoritmo de la ruta más corta
Objetivo de la n -ésima iteración : encontrar
el n-ésimo nodo más cercano al origen. (Este
INGENIERIA INDUSTRIAL 5 “A”
paso se repetirá para n = 1, 2, . . . hasta que el
n-ésimo nodo más cercano sea el nodo destino.)
Datos de la n -ésima iteración: n – 1 nodos
más cercanos al origen —que se encontró en
las iteraciones previas—, incluida su ruta más
corta y la distancia desde el origen. (Estos
nodos y el origen se llaman nodos resueltos; el
resto son nodos no resueltos.)
Candidatos para n -ésimo nodo más
cercano: cada nodo resuelto que tiene
conexión directa por una ligadura con uno o
más nodos no resueltos proporciona un
candidato, esto es, el nodo no resuelto que
tiene la ligadura más corta. (Los empates
proporcionan
candidatos adicionales.)
Cálculo del n -ésimo nodo más cercano:
para cada nodo resuelto y sus candidatos, se
suma la distancia entre ellos y la distancia de la
ruta más corta desde el origen a este nodo
INGENIERIA INDUSTRIAL 5 “A”
resuelto. El candidato con la distancia total más
pequeña es el n-ésimo nodo más
cercano —los empates proporcionan nodos
resueltos adicionales—, y su ruta más corta es
la que genera esta distancia.
Aplicación de este algoritmo al problema
de la ruta más corta de Seervada Park
La administración de Seervada Park necesita
encontrar la ruta más corta desde la entrada del
parque(nodo O) hasta el mirador (nodo T ) a
través del sistema de caminos que se presenta
en la fi gura9.1. En la tabla 9.2 se encuentran
los resultados que se obtuvieron al aplicar el
algoritmo anterior, donde el empate del
segundo nodo más cercano permite pasar
directo a buscar el cuarto nodo más cercano. La
primera columna (n) indica el número de la
iteración. La segunda proporciona una lista de
INGENIERIA INDUSTRIAL 5 “A”
los nodos resueltos para comenzar la iteración
actual, después de quitar los que no sirven (los
que no tienen conexión directa con nodos no
resueltos). La tercera columna da los candidatos
para el n-ésimo nodo más cercano (nodos no
resueltos con la ligadura más corta al nodo
resuelto). La cuarta columna calcula la distancia
de la ruta más corta desde el origen a cada
candidato, esto es, la distancia al nodo resuelto
más la distancia de la ligadura que va al
candidato.
El candidato con la suma de distancias más
pequeña es el n-ésimo nodo más cercano al
origen, según se indica en la quinta columna.
Las dos últimas columnas resumen la
información de este último nodo resuelto
necesaria para pasar a las iteraciones
siguientes, es decir, la distancia de la ruta más
corta del origen a este nodo y la última rama en
esta ruta. Ahora se deben relacionar las
INGENIERIA INDUSTRIAL 5 “A”
columnas con la descripción del algoritmo. Los
datos para la n-ésima iteración se encuentran
en las columnas 5 y 6 de las iteraciones
anteriores, donde los nodos resueltos de la
quinta columna se enumeran después en la
segunda para la iteración actual después de
eliminar los que no tienen conexión directa con
nodos no resueltos. Los candidatos para el n-
ésimo nodo más cercano se enumeran en la
tercera columna de la iteración actual. El
cálculo del n-ésimo nodo más cercano se realiza
en la columna 4 y los resultados se registran en
las últimas tres columnas de la iteración actual.
La ruta más corta desde el nodo destino hasta
el origen se puede rastrear hacia atrás en la
última columna de la tabla 9.2, con lo que se
obtiene T → D → E → B → A → O o bien T → D
→B → A → O. Por tanto, se identifi caron las dos
opciones de ruta más corta desde el origen
INGENIERIA INDUSTRIAL 5 “A”
hasta el destino como O → A → B → E → D → T
y O → A → B → D → T, con una distancia total
de 13 millas en cualquiera de las dos.
5.3 PROBLEMA DEL ÁRBOL DE MÍNIMA EXPANSIÓN
El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o más poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansión mínima. Los pasos del procedimiento son los siguientes. Sea N {1, 2, ...,n} el conjunto de no-dos de la red.
El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de
INGENIERIA INDUSTRIAL 5 “A”
forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una cantidad variable según el contexto operacional de minimización, y que puede bien representar una distancia o unidad de medida).
Sean
N = {1,2,3,...,n} el conjunto de nodos de la red.
Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración k
Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.
PASO CERO (0): CONCEPTUALIZACIÓN DEL ALGORITMO
Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se han enlazado de forma permanente nodo alguno, y por ende el conjunto que representa a los nodos que hacen falta por enlazarse de forma permanente es igual a la cantidad de nodos que existen en la red.
INGENIERIA INDUSTRIAL 5 “A”
PASO 1:Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto C1 = {i}, que significa que al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0 pierde el elemento i por ende ahora será igual a Č1 = N - {i}, además se debe actualizar el subíndice de los conjuntos k, el cual ahora será igual a 2.
PASO 2: PASO GENERAL "K"Se debe de seleccionar un nodo j del conjunto ČK-1 ("k-1" es el subíndice que indica que se está haciendo referencia al conjunto de la iteración inmediatamente anterior) el cual tenga el arco o ramal con menor longitud con uno de los nodos que se encuentran en el conjunto de nodos de enlace permanente CK-1. Una vez seleccionado se debe de enlazar de forma permanente lo cual representa que pasa a formar parte del conjunto de enlaces permanentes y deja de formar parte del conjunto que todavía se debe conectar para lograr la expansión. Al actualizar el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.
INGENIERIA INDUSTRIAL 5 “A”
CK = CK-1 + {j} mientras que ČK = ČK-1 - {j}El paso general que define k que al mismo tiempo representa a las iteraciones debe de ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este conjunto sea igual a vacío se tendrá el árbol de expansión mínima.
El entendimiento del algoritmo desde el punto de vista algebraico no es quizá el más simple, sin embargo mediante el ejemplo gráfico se verá que es un algoritmo muy sencillo de elaborar.
RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE EXPANSIÓN MÍNIMAEL PROBLEMA La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contará con la urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura necesaria para satisfacer las necesidades de servicios públicos en materia de
INGENIERIA INDUSTRIAL 5 “A”
suministro de agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto madre, el cual cuenta con las conexiones de las unidades de vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del acueducto municipal para contar con su suministro). El acueducto municipal al ver la situación del plan parcial debe de realizar las obras correspondientes a la instalación de ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias existentes (dadas en kilómetros) correspondientes a las rutas factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las necesidades de presión que necesita la red madre.
INGENIERIA INDUSTRIAL 5 “A”
El acueducto municipal le contacta a usted para que mediante sus conocimientos en teoría de redes construya una red de expansión que minimice la longitud total de ductos y que enlace todos los nodos del plan parcial de vivienda.
PASO 0:
Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto de nodos enlazados de forma permanente en la iteración indicada en el subíndice y Č0 = {N = 1,2,3,4,5,6,7,8} que corresponde al conjunto de nodos pendientes por enlazar de manera permanente en la iteración indicada en el subíndice.
INGENIERIA INDUSTRIAL 5 “A”
PASO 1:
Se debe definir de manera arbitraria el primer nodo permanente del conjunto Č0, en este caso escogeremos el nodo 1 (puede ser cualquier otro), que algebraicamente se representa con la letra i, se procede a actualizar los conjuntos iniciales, por ende C1 = {i} = {1} y Č0 = {N -
i} = {2, 3, 4,5, 6, 7,8}, actualizamos k por ende ahora será igual a 2.
PASO 2:
Ahora se debe seleccionar el nodo j del conjunto ČK-1 (es decir del conjunto del paso 1) el cual presente el arco con la menor longitud y
que se encuentre enlazado con uno de los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir que se debe de encontrar un nodo que
INGENIERIA INDUSTRIAL 5 “A”
tenga el arco de menor longitud enlazado al nodo 1).
Los arcos o ramales de color naranja representan los arcos que enlazan el conjunto ČK-1(es decir del conjunto del paso 1, recordemos que K en este paso es igual a 2, por ende ČK-1= Č1) con los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1, por ende ahora solo falta escoger el de menor longitud, que en este caso es el arco cuya longitud es 2, que enlaza de forma permanente ahora el nodo 2. Al actualizar los conjuntos quedan así:
C2 = {1,2} y Č2 = {3, 4,5,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ahora se seleccionará un nuevo nodo j del conjunto Č2que presente el enlace (ramal o arco) de menor longitud con los nodos que se encuentran en el conjunto C2.
INGENIERIA INDUSTRIAL 5 “A”
Los arcos de color naranja representan los enlaces posibles y dado que existe empate entre las menores longitudes se elige de manera arbitraria, en este caso se representa nuestra elección con un arco de color verde, enlazando de forma permanente ahora el nodo 4.
Al actualizar los conjuntos quedan así:
C3 = {1,2,4} y Č3 = {3,5,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
INGENIERIA INDUSTRIAL 5 “A”
Lo que representan los arcos naranja y verde es ya conocido, ahora la línea azul interrumpida irá trazando nuestro árbol de expansión final. Dado a que el arco menor es el de longitud 3, ahora se enlazará de manera permanente el nodo 5.
Al actualizar los conjuntos quedan así:
C4 = {1,2,4,5} y Č4 = {3,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
INGENIERIA INDUSTRIAL 5 “A”
Ahora se enlazará de manera permanente el nodo 7.
Al actualizar los conjuntos quedan así:
C5 = {1,2,4,5,7} y Č5 = {3,6,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
INGENIERIA INDUSTRIAL 5 “A”
Ahora se enlazará de manera permanente el nodo 6.
Al actualizar los conjuntos quedan así:
C6 = {1,2,4,5,7,6} y Č6 = {3,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
INGENIERIA INDUSTRIAL 5 “A”
Se rompen los empates de forma arbitraria, ahora se enlazará de manera permanente el nodo 3.
Al actualizar los conjuntos quedan así:
C7 = {1,2,4,5,7,6,3} y Č7 = {8}
Ahora se procede a actualizar k ya que se procede a efectuar la última iteración.
INGENIERIA INDUSTRIAL 5 “A”
Ahora se enlazará de manera permanente el nodo 8.
Al actualizar los conjuntos quedan así:
C8 = {1,2,4,5,7,6,3,8} = {N} y Č8 = {ø}
Por ende se ha llegado al árbol de expansión mínima
Árbol que presenta una longitud total minimizada de 21 kilómetros de ductos.
INGENIERIA INDUSTRIAL 5 “A”
5.4 PROBLEMA DE FLUJO MÁXIMO
Introducción
La importancia del análisis y cálculo de redes se explica en la creciente demanda por soluciones matemáticas que faciliten la planeación, programación y control de actividades y proyectos en campos tan disímiles como la planeación de flujos de tráfico para evitar congestión vehicular en las ciudades; recolección y entrega de mercancías y paquetes; diseños de redes de abastecimiento y distribución eficiente de agua para asentamientos humanos; obras civiles, programación de la producción y gestión documental entre muchas otras aplicaciones.
El objetivo de la representación mediante redes de una situación problema en contextos como los anteriores, es identificar la ruta crítica que maximiza flujo.
INGENIERIA INDUSTRIAL 5 “A”
EJEMPLOS DE CONTEXTUALIZACION
Una compañía aérea desea saber el número máximo de vuelos directos y no directos que diariamente pueden conectar el aeropuerto A con el F.
Para representar el problema es necesario representar en un Grafo la situación, de ahí que:
Cada Nodo (circulo) debe representar un punto de flujo y/o ramificación. En este caso son los aeropuertos alternos.
La flecha o arcos de la red señalan el sentido de los vuelos directos entre aeropuertos.
La capacidad "𝑞" de cada arco indica el número de vuelos directos entre los aeropuertos y se ubica sobre cada arco.
F
E
D
C
B
A
22 1
43
51
2
4
3
2
INGENIERIA INDUSTRIAL 5 “A”
Flujo y leyes de conservación
Teniendo en cuenta que el sentido en todo arco se denota con los subíndices (i,j) y la capacidad con qij.
Las capacidades deben representar la máxima cantidad de flujo que puede pasar por los diferentes arcos de la red.
Si no existe limite de capacidad entre un nodo "i " y un nodo " j ", entonces, se debe asignar una capacidad qij muy grande M.
Si los nodo " i " y " j " se encuentran conectados por un arco no orientado de capacidad qij, entonces se entenderá que representa dos arcos orientados con igual capacidad qij=qji.
Algoritmo de solución de una red
1.Definir la lista de actividades con (relaciones de precedencia inmediata, restricciones, y/o simultaneidad) de manera que permita identificar aquellas actividades criticas que afectan el proyecto.
INGENIERIA INDUSTRIAL 5 “A”
2.Definir las capacidades máximas, y los tiempos de realización tempranos y tardíos. (Se entiende por tiempo temprano al menor tiempo posible para la realización de una actividad, y por tiempo tardío, al mayor tiempo posible a invertir en la realización de la misma actividad-)
3.Trazar el grafo para visualizar el problema.4.Fase de paso hacia adelante
Fase de paso hacia atrás y trazado de la ruta crítica de máximo flujo.
EJEMPLO DE APLICACIÓN
Debido al cierre temporal de la variante de occidente, la empresa Coordinadora es avocada a desviar su flota de camiones por las calles de la ciudad siguiendo las instrucciones de la secretaria de transito que indica las posibles vías de flujo vehicular. Como información adicional se presenta el grafo de la situación. Hallar la ruta que permita el máximo flujo de camiones.
INGENIERIA INDUSTRIAL 5 “A”
SOLUCION GRAFICA
Lista de la actividad del flujo vehicularCódigo de identificación de la actividad o calle a usar
precedente inmediata
A -B AC AD BE BF C,BG C,BH F,E
INGENIERIA INDUSTRIAL 5 “A”
Fase de paso hacia Adelante: Se avanza acumulando la máxima capacidad de ocurrencia inicial en cada
Fase de paso hacia Adelante: Se avanza acumulando la máxima capacidad de ocurrencia inicial en cada nodo
D23E
6
652
3
4
1
2 5
H
G7F
C3
A
B
3
D
23
E6
652
3
4
0
1
2
5
H
G7
F
C
3
A
B
3
INGENIERIA INDUSTRIAL 5 “A”
Observe que la capacidad máxima asignada en el nodo UNO es «0».
Por qué: En el nodo objeto de análisis, aún no hay capacidad acumulada; es apenas el inicio.
INGENIERIA INDUSTRIAL 5 “A”
INGENIERIA INDUSTRIAL 5 “A”
INGENIERIA INDUSTRIAL 5 “A”
INGENIERIA INDUSTRIAL 5 “A”
INGENIERIA INDUSTRIAL 5 “A”
INGENIERIA INDUSTRIAL 5 “A”
INGENIERIA INDUSTRIAL 5 “A”
5.5 PROBLEMA DE FLUJO DE COSTO MÍNIMO
El problema de flujo de costo mínimo tiene una posición medular entre los problemas de optimización de redes; primero, abarca una clase amplia de aplicaciones y segundo, su solución es muy eficiente.
Todos los problemas de red anteriores son casos especiales del problema de flujo de costos mínimo. Al igual que el problema de flujo máximo, este considera flujos en las redes con capacidades. Al igual que el problema del camino mas corto, este considera un costo por flujo hacia un arco. Al igual que el problema de transporte, este permite múltiples orígenes y destinos. Por lo tanto, todos estos problemas pueden ser vistos como casos especiales del problema de flujo de costos mínimo.
El problema es minimizar el costo total sujeto a la disponibilidad y la demanda de algunos nodos, y de la conexión superior de flujo a través de cada arco.
También se puede decir que El método del costo mínimo o de los mínimos costos es un algoritmo desarrollado con el objetivo de
INGENIERIA INDUSTRIAL 5 “A”
resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos. El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores dado que se trata simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el método.
ALGORITMO DE RESOLUCIÓN DEL COSTO MÍNIMO
PASO 1:De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.
INGENIERIA INDUSTRIAL 5 “A”
PASO 2:En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.
PASO 3:Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".
EJEMPLO DEL MÉTODO DEL COSTO MÍNIMO
Por medio de este método resolveremos el problema de transporte propuesto y resuelto en módulos anteriores mediante programación lineal.
EL PROBLEMAUna empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la
INGENIERIA INDUSTRIAL 5 “A”
demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.
Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.
Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.
SOLUCIÓN PASO A PASO
INGENIERIA INDUSTRIAL 5 “A”
Luego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la "Planta 3", en un proceso muy lógico. Dado que Bogotá se queda sin demanda esta columna desaparece, y se repite el primer proceso.
Nuevo proceso de asignación:
INGENIERIA INDUSTRIAL 5 “A”
Nuevo proceso de asignación:
Nuevo proceso de asignación:
INGENIERIA INDUSTRIAL 5 “A”
Una vez finalizado el cuadro anterior nos daremos cuenta que solo quedará una fila, por ende asignamos las unidades y se ha terminado el método:
INGENIERIA INDUSTRIAL 5 “A”
Los costos asociados a la distribución son:
En este caso el método del costo mínimo presenta un costo total superior al obtenido mediante Programación Lineal y el Método de Aproximación Vogel, sin embargo comúnmente no es así, además es simple de desarrollar y tiene un mejor rendimiento en cuanto a resultados respecto al Método de la Esquina Noroeste.
5.6PROGRAMACIÓN LINEAL EN TEORÍA DE REDES
La modelación de redes permite la resolución de múltiples problemas de programación
INGENIERIA INDUSTRIAL 5 “A”
matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos como Algoritmos de optimización de redes. Dentro de los problemas más comúnmente resueltos mediante la modelación de redes se encuentran los ya vistos modelos de transporte, transbordo además de los muy conocidos modelos de determinación de cronograma de actividades para proyectos como lo son el PERT y el CPM.
La Programación Lineal corresponde a un algoritmo a través del cual se resuelven situaciones reales en las que se pretende identificar y resolver dificultades para aumentar la productividad respecto a los recursos (principalmente los limitados y costosos), aumentando así los beneficios.
El objetivo primordial de la Programación Lineal es optimizar, es decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando una función objetivo también lineal.
INGENIERIA INDUSTRIAL 5 “A”
Los resultados y el proceso de optimización se convierten en un respaldo cuantitativo de las decisiones frente a las situaciones planteadas. Decisiones en las que sería importante tener en cuenta diversos criterios administrativos como:
Los hechos La experiencia La intuición La autoridad
¿COMO RESOLVER UN PROBLEMA MEDIANTE PROGRAMACIÓN LINEAL?
El primer paso para la resolución de un problema de programación lineal consiste en la identificación de los elementos básicos de un modelo matemático, estos son:
Función Objetivo Variables Restricciones
INGENIERIA INDUSTRIAL 5 “A”
El siguiente paso consiste en la determinación de los mismos, para lo cual proponemos seguir
la siguiente metodología:
LA FUNCIÓN OBJETIVOLa función objetivo tiene una estrecha relación con la pregunta general que se desea responder. Sí en un modelo resultasen distintas preguntas, la función objetivo se relacionaría con la pregunta del nivel superior, es decir, la pregunta fundamental. Así por ejemplo, si en una situación se desean minimizar los costos, es muy probable que la pregunta de mayor nivel sea la que se relacione con aumentar la utilidad en lugar de un interrogante que busque hallar la manera de disminuir los costos.
INGENIERIA INDUSTRIAL 5 “A”
LAS VARIABLES DE DECISIÓN
Similar a la relación que existe entre objetivos específicos y objetivo general se comportan las variables de decisión respecto a la función objetivo, puesto que estas se identifican partiendo de una serie de preguntas derivadas de la pregunta fundamental. Las variables de decisión son en teoría factores controlables del sistema que se está modelando, y como tal, estas pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor
INGENIERIA INDUSTRIAL 5 “A”
óptimo, que contribuya con la consecución del objetivo de la función general del problema.
LAS RESTRICCIONES
Cuando hablamos de las restricciones en un problema de programación lineal, nos referimos a todo aquello que limita la libertad de los valores que pueden tomar las variables de decisión. La mejor manera de hallarlas consiste en pensar en un caso hipotético en el que decidiéramos darle un valor infinito a nuestras variables de decisión, por ejemplo, ¿qué pasaría sí en un problema que precisa maximizar sus utilidades en un sistema de producción de calzado decidiéramos producir una cantidad infinita de zapatos? Seguramente ahora nos
INGENIERIA INDUSTRIAL 5 “A”
surgirían múltiples interrogantes, como por ejemplo:
o Con cuánta materia prima cuento para producirlos?
o Con cuánta mano de obra cuento para fabricarlos?
o Pueden las instalaciones de mi empresa albergar tal cantidad de producto?
o Podría mi fuerza de mercadeo vender todos los zapatos?
o Puedo financiar tal empresa?
Pues bueno, entonces habríamos descubierto que nuestro sistema presenta una serie de limitantes, tanto físicas, como de contexto, de tal manera que los valores que en un momento dado podrían tomar nuestras variables de decisión se encuentran condicionados por una serie de restricciones.
EJEMPLO DE RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL
EL PROBLEMA
INGENIERIA INDUSTRIAL 5 “A”
La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos tejidos de calidad diferente T y T’; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c. Para obtener un metro de T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un metro de T’ por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c.
El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si se debe obtener el máximo beneficio, ¿cuántos metros de T y T’ se deben fabricar?
El problema se recomienda leer en más de una ocasión para facilitar el reconocimiento de las variables, además es muy recomendable la elaboración de tablas o matrices que faciliten una mayor comprensión del mismo.
PASO 1: "FORMULAR EL PROBLEMA"
Para realizar este paso partimos de la pregunta central del problema.
¿Cuántos metros de T y T’ se deben fabricar?
Y la formulación es:
INGENIERIA INDUSTRIAL 5 “A”
“Determinar la cantidad de metros diarios de tejido tipo T y T’ a fabricar teniendo en cuenta el óptimo beneficio respecto a la utilidad”.
PASO 2: DETERMINAR LAS VARIABLES DE DECISIÓN
Basándonos en la formulación del problema nuestras variables de decisión son:
XT: Cantidad de metros diarios de tejido tipo T a fabricar
XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar
PASO 3: DETERMINAR LAS RESTRICCIONES DEL PROBLEMA
En este paso determinamos las funciones que limitan el problema, estas están dadas por capacidad, disponibilidad, proporción, no negatividad entre otras.
INGENIERIA INDUSTRIAL 5 “A”
De disponibilidad de materia prima:
0,12XT + 0,2XT’ <= 500 Hilo “a”
0,15XT + 0,1XT’ <= 300 Hilo “b”
0,072XT + 0,027XT’ <= 108 Hilo “c”
De no negatividad
XT,XT’ >= 0
PASO 4: DETERMINAR LA FUNCIÓN OBJETIVO
En este paso es de vital importancia establecer el contexto operativo del problema para de esta forma determinar si es de Maximización o Minimización. En este caso abordamos el contexto de beneficio por ende lo ideal es Maximizar.
Función Objetivo
ZMAX = 4000XT + 5000XT’
INGENIERIA INDUSTRIAL 5 “A”
PASO 5: RESOLVER EL MODELO UTILIZANDO SOFTWARE O MÉTODOS MANUALES
A menudo los problemas de programación lineal están constituidos por innumerables variables, lo cual dificulta su resolución manual, es por esto que se recurre a software especializado, como es el caso de WinQSB, TORA, Lingo o para modelos menos complejos se hace útil la herramienta Solver de Excel.
El anterior ejercicio fue resuelto mediante Solver - Excel, y su resultado fue:
CONCLUSIÓN
INGENIERIA INDUSTRIAL 5 “A”
Los modelos de optimización de redes constituyen una herramienta muy sencilla para la encontrar la solución óptima a los problemas de flujo de redes, porque proporcionan algoritmos fáciles de comprender y aplicar que comparados con el método simplex disminuyen el número de iteraciones que resuelven el problema. Si se aplicara el método simplex en un problema de distribución o de redes, tendríamos muchas variables y restricciones en el modelo y se tendría que utilizar herramientas computacionales para encontrar la solución optima de una forma rápida, ahora con los modelos de redes solo habría que aplicar las iteraciones al grafo que origina la representación de la red del problema y luego aplicar el algoritmo que corresponde, que puede ser el algoritmo de la ruta más corta, algoritmo para encontrar el árbol de expansión mínima, algoritmo de la trayectoria de aumento o el algoritmo de flujo máximo.
Aunque los problemas de flujo de costo mínimo y el de la ruta más corta pueden formularse como modelos de programación lineal para luego aplicar el método simplex, no es
INGENIERIA INDUSTRIAL 5 “A”
conveniente su utilización. Por otro lado solucionar el problema utilizando redes mejora la eficiencia de los cálculos.
