optimizacion_sistemas_iii_-_utp-2015-i_-8-__15434__ (2)
Post on 21-Dec-2015
219 Views
Preview:
DESCRIPTION
TRANSCRIPT
JOSE EDUARDO TORRES VEGACoronel EP ( R )
Diplomado en Ciencia y TecnologíaIngeniero Electrónico CIP Maestro en Administración
Experto en LogísticaDiplomado en Seguridad y Salud Ocupacional
Docente Universitario a nivel pre grado y post gradoConsultor en Servicios de Telecomunicaciones
Estudios Teóricos de Radiaciones No Ionizantes
PRESENTADO POR:
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
SEMANA 1 El problema de transporte. Solución básica inicial: Método de la Esquina Nor-oeste, Método de costo mínimo, Método de Vogel. Desarrollo del modelo. SEMANA 2 Solución óptima del problema de transporte. Prueba de Optimalidad: Método de distribución Modificada (MODI). Desarrollo de problemas. SEMANA 3Casos especiales. Problema de maximización y degeneración. Desarrollo de problemas. SEMANA 4 El problema de transbordo. Desarrollo de la solución. PRÁCTICA CALIFICADA 1 SEMANA 5 El problema de asignación. El Método Húngaro. Desarrollo de problemas. SEMANA 6Teoría de redes: Definiciones. Problema de flujo máximo: Algoritmo de Ford y Fulkerson. Teorema de Mínimo corte-Máximo flujo. Desarrollo de problemas. SEMANA 7 Problema del camino más corto. Algoritmo Dijkstra. Problema de conexión mínima. Algoritmo de Krustral. Desarrollo de problemas. PRÁCTICA CALIFICADA 2 SEMANA 8 Problema de Flujo máximo a costo mínimo. Algoritmo de Busacker y Gowen. Desarrollo de problemas.
ESCUELA DE INGENIERÍA INDUSTRIAL
SEMANA 9 Programación de proyectos. Desarrollo de PERT/CPM: conceptos, actividad y evento. Presentación gráfica. Construcción de la red. problemas. PRÁCTICA CALIFICADA 3 SEMANA 10Ruta crítica - Caso determinístico: Cálculo del tiempo más próximo y más lejano. Tiempos de holgura, Ruta crítica. Control: Presentación del proceso PERT/CPM. Ruta crítica - Caso probabilístico. Cálculos de sensibilidad. Diagrama de tiempo, Diagrama de nivelación de recursos. Desarrollo de problemas. SEMANA 11Optimización de programas. Desarrollo de problemas. SEMANA 12Software MS Project. PRÁCTICA CALIFICADA 4 SEMANA 13Programación dinámica: Conceptos, Elementos, Principio de Optimalidad. SEMANA 14Formulación de modelos con programación dinámica. Problemas de Programación Dinámica: Ruta más corta, problema de reemplazo, asignación de recursos, producción, inventarios. Desarrollo de problemas. SEMANA 15 EXAMEN FINAL
ESCUELA DE INGENIERÍA INDUSTRIAL
SUMARIO
BIBLIOGRAFÍA
1. PROBLEMA DE FLUJO MAXIMO:ALGORITMO DE FORD Y FULKENSON2. TEOREMA DE MINIMO CORTE-MAXIMO FLUJO3. PROBLEMA DEL CAMINO MAS CORTO: ALGORITMO DIJKSTRA4. PROBLEMA DE LA CONEXIÓN MINIMA:ALGORITMO DE KRUSTRAL5. PROBLEMA DEL FLUJO MAXIMO AL COSTO MÌNIMO:ALGORITMO DE BUSACKER Y GOWEN. 6. PROGRAMACIÓN DE PROYECTOS.7. PERT/CPM: CONCEPTOS, ACTIVIDAD Y EVENTO. 8. PRESENTACION GRAFICA, CONSTRUCCION DE LA RED.9. RUTA CRÍTICA - CASO DETERMINÍSTICO: CÁLCULO DEL TIEMPO MÁS PRÓXIMO Y MÁS LEJANO.
TIEMPOS DE HOLGURA, RUTA CRÍTICA. CONTROL: PRESENTACIÓN DEL PROCESO PERT/CPM. 10. RUTA CRÍTICA - CASO PROBABILÍSTICO. CÁLCULOS DE SENSIBILIDAD. DIAGRAMA DE TIEMPO,
DIAGRAMA DE NIVELACIÓN DE RECURSOS.
TEORIA DE REDES
WINSTON, WAYNE Investigación de operaciones. Editorial: THOMSON. HANDY TAHA. Investigación de operaciones. Ediciones Alfa Omega, (1991). HILLER – LIEBERMAN. Introducción a la investigación de Operaciones. Mc Graw
Hill, (1990).
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
1. Propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino
Una fuente produce material en forma estacionaria y un resumidero lo consume.
Cada arco puede ser considerado como un conducto de cierta capacidad.
Como con la ley de corrientes de Kirchhoff, la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos saliendo del vértice.
2. Problema de flujo máximo: ¿Cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al resumidero sin violar ninguna restricción de capacidad?
EL ALGORITMO DE FORD-FULKERSON
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Redes de flujo
Una red de flujo es un grafo dirigido G=(V,E) en donde cada arco (u,v)E tiene una capacidad no negativa c(u,v)0.
Se distinguen dos vértices: la fuente “s “ y el resumidero “t”.
Se asume que cada vértice se encuentra en alguna ruta de “s” a “t”.
Un flujo en G es una función f: VxV----> R tal que:o Restricción de capacidad: u,v en V, f(u,v) c(u,v)o Simetría: f(u,v) = - f(v,u)o Conservación: u en V-{s,t} v en Vf(u,v) = 0
El valor del flujo es |f| = v en Vf(s,v) El problema del flujo máximo trata de maximizar este flujo.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Ejemplo
s
v1
v3
t
v2 v4
16
1220
7
4
14
13
4109
s
v1
v3
t
v2 v4
11/16
12/1215/20
7/7
4/4
11/14
8/13
1/4104/9
f(u,v)/c(u,v)si f(u,v) 0 no se anota
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Método de Ford-FulkersonEste método depende de tres ideas importantes: Camino de
aumento , cortesy red residual. Este método es iterativo.Se comienza con f(u,v) =0 para cada par de nodos. En cada iteración se
incrementa el valor del flujo buscando un camino de aumento, el cual es un camino desde la fuente al resumidero que puede conducir más flujo.
Ford-Kulkerson_method(G,s,t)inicializar flujo f a 0; while (existe un camino de aumento p) do aumentar el flujo f a lo largo de p; return f;
o Se repite el proceso previo hasta no encontrar un camino de aumento.o Capacidad residual: es la capacidad adicional de flujo que un arco
puede llevar: cf(u,v)= c(u,v) - f(u,v)o Dado una red de flujo G=(V,E) y un flujo f, la red residual: inducida por
f es Gf=(V,Ef), con Ef={(u,v) VxV: cf(u,v)>0}
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
K=min(∞,30,20), K=20C13,31 =(30-20, 0+20). C13,31 =(10, 20)C35,53 =(20-20, 0+20), C35,53 =(0, 20)
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
K=min(∞,20,40,10,20), K=10
C12,21 =(20-10, 0+10), C12,21 =(10, 10)
C23,32 =(40-10, 0+10), C23,32 =(30, 10)
C34,43 =(10-10, 5+10), C34,43 =(0, 15)
C45,54 =(20-10, 0+10), C45,54 =(10, 10)
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
K=min(∞,10,20), K=10
C12,21 =(10-10, 10+10), C12,21 =(0, 20)
C25,52 =(20-10, 0+10), C25,52 =(10, 10)
K=min(∞,10,10,10), K=10
C13,31 =(10-10, 20+10), C13,31 =(0, 30)
C32,23 =(10-10, 30+10), C32,23 =(0, 40)
C25,52 =(10-10, 10+10), C25,52 =(0, 20)
Y por ultimo escogemos el camino 1,4.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
K=min(∞,10,10), K=10
C14,41 =(10-10, 0+10), C14,41 =(0, 10)
C45,54 =(10-10, 10+10), C45,54 =(0, 40)
Flujo Máximo = Σ KFlujo Máximo = 20+10+10+10+10Flujo Máximo = 60El flujo máximo que puede pasar del nodo origen 1 hasta el nodo destino es de 60.
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
ALGORITMO DE DIJKSTRA1. Dado un V0, se busca un conjunto D con las menores distancias de V0 al
resto de vértices2. Al inicio, solo se conocen las distancias de los adyacentes; D es inicializada
con un Factor de peso para los adyacentes e Infinito para los no adyacentes3. D va ser mejorado sucesivamente, escogiendo el vértice Vk (no elegido
antes) que tenga la distancia mas corta V0, Vk.4. Se prueba si pasando por Vk, se puede obtener distancias mas cortas de las
que tenemos para cada vértice restante del grafo.5. Entonces, resumiendo:6. Se crea una lista de VDiks con todos los vértices del grafo, y cada VDiks creado también se encola7. Se saca de la cola el menor VDiks por distancia (v menor)8. Por cada VDiks v de la lista, se revisa si su vértice es adyacente al vértice de v menor y si
pasando por v menor se puede conseguir una mejor distancia Si es así, se modifica v con los nuevos datos
9. Se repite todo desde el paso 2 hasta que no haya nada mas en la cola
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
V2 V5
V1
V3 V4
V6
38
5
34
7
3
2
Escogidos
Vertice Evaluado
D[0] D[1] D[2] D[3] D[4]D[5]
V1 V2 V3 V4 V5 V6
De V1 AL RESTO
V1 0 3 4 ∞ 8 ∞V1
1. D[] se incializa con F.P. de adyacentes al origen
2. Escoger vértice Vk que no haya sido escogido, con la menor distancia del V evaluado a Vk
V2
3. Revisar si alguna distancia puede ser mejorada pasando por Vk
Pasando por V2, Distancia de V1 a V5 seria 8, no hay
mejora
0 3 4 ∞ 8 ∞V1,V2
Repetir K hasta que se hayan visitado todos los vertices
V3 0 3 4 ∞ 7 ∞V1,V2,V3
V5 0 3 4 14 8 10V1,V2,V3,V5
V6 0 3 4 12 8 10V1,V2,V3,V5,V6
Pasando por V3, Distancia de V1 a
V5 seria 7, CAMBIAR
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
para grafos dirigidos (la extensión a no dirigidos es inmediata) genera uno a uno los caminos de un nodo v al resto por orden
creciente de longitud usa un conjunto de vértices donde, a cada paso, se guardan los
nodos para los que ya se sabe el camino mínimo devuelve un vector indexado por vértices: en cada posición w
se guarda el coste del camino mínimo que conecta v con w cada vez que se incorpora un nodo a la solución se comprueba
si los caminos todavía no definitivos se pueden acortar pasando por él
se supone que el camino mínimo de un nodo a sí mismo tiene coste nulo
un valor ∞ en la posición w del vector indica que no hay ningún camino desde v a w
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Entonces, el ALGORITMO DE DIJKSTRA:
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
ALGORITMO DE KRUSKAL
Soluciona el problema de elegir uno de varios árboles de expansión que cumplan con el requisito de que la suma total del peso de sus vértices sea la mínima posible. Se busca reducir el costo total de unir una serie de puntos en un grafo, por ejemplo, unir con caminos un conjunto de ciudades de tal forma que la longitud total de los caminos a construir sea el mínimo y que además permita que todas estén conectadas
El algoritmo de Kruskal basa su funcionamiento en la elección de las aristas de menor peso que no forman ciclos, para poder elegir dichas aristas es necesario usar un método de almacenamiento que las ordene de menor a mayor peso, pero además, de otros artificios matemáticos
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
a ----(4)---> bd ----
(7)---> ce ----
(9)---> df ----
(4)---> cg ----
(2)---> f h ----
(2)---> ci ----
(8)---> ai ----
(1)---> g
Se marca la arista con menor valor. Si hay más de una, se elige cualquiera de ellas.
De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera de ellas.
Repetir la operación siempre que la arista elegida no forme un ciclo con las ya marcadas.
El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2
A B
C D
E F
5
5
G
7
65
4
3
3
2
23
1
2 FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
c ----(8)---> b
d ----(7)---> c
f ----(14)---> d
f ----(10)---> e
h ----(6)---> g
i ----(8)---> a
i ----(11)---> b
i ----(7)---> h
ARBOL DE COSTO MÁXIMO
El algoritmo se inicializa con un flujo nulo o cualquier flujo factible en todos los arcos, esto es, satisfaciendo las restricciones de capacidad y conservación de los flujos en todos los nodos.Para mejorar este flujo, se etiqueta inicialmente el nodo s y se aplica el proceso de etiquetado para etiquetar los otros nodos hasta alcanzar el destino. Cuando esto ocurra tendremos un camino incremental desde s a n a través del cual se puede enviar un flujo positivo.A continuación, se vuelve hacia atrás en el camino incremental con la ayuda de las etiquetas de los nodos y se calcula el flujo máximo que puede ser enviado por el camino. Entonces se incrementa el flujo en unidades en todos los arcos hacia delante en el camino incremental y decrementamos el flujo en unidades en todos los arcos hacia atrás.Se repite el proceso de etiquetado para encontrar otro camino incremental desde s a n. El algoritmo termina cuando no se pueda encontrar ningún otro camino incremental, lo que nos conduce al máximo flujo posible de s a n.
Algoritmo del Flujo Máximo
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Paso 0:Se inicializa f = 0 (o cualquier flujo factible) y f (i, j) = 0 (i,j) A.∀ ∈Se construye la red incremental, que coincide con la original. Esto es, r (i, j) = k (i, j) para todo arco en la red original y se añade su opuesto con r (j, i) = 0.Sea δ= . Sea hace i = s el nodo fuente, se marca con Pred (i) = 0.∝Paso 1:Se elige un j Γ (i) no marcado tal que r (i, j) > 0 para el arco (i,j) y se marca ∈con Pred (j) = i.Se asigna δ= min{δ, r (Pred (j), j)}. En caso de que no exista y si i = s parar ya que se ha alcanzado el máximo flujo posible que se puede enviar desde s a n.Si i ≠s se hace i = Pred (i)y se busca otro j Γ (i), no marcado con r (i, j) > 0.∈Paso 2:Si j = n, hacer f = f + δ, e ir al paso 3.En caso contrario, hacer i = j y repetir el paso 1.Paso 3:Cambiamos r (Pred (j), j)= r(Pred (j), j)= – δy r(j, Pred (j)) = r(j, Pred (j))+ δ.Hacer j = Pred (j), si j = s ir al paso 4. En otro caso, repetimos el paso 3.Paso 4:Se borran todas las marcas menos la de s, sea s = i. Se vuelve a asignar δ=
y se va al paso 1. ∝
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Sea G = (V,A) un grafo con dos vértices fijos, s el nodo fuente y t el nodo destino. Cada arco (i,j) A tiene asociada una capacidad k (i, j) y un ∈coste por unidad de flujo que circula por cada arco c (i, j). Sea Φ la cantidad de flujo demandada desde el nodo t, para ser servida desde el nodo s. Entonces podemos plantear el problema de flujo a coste mínimo en los siguientes términos: enviar Φ unidades de flujo desde el nodo s al nodo t de G = (V,A) con el patrón de flujo cuyo coste asociado sea el mínimo, satisfaciendo las restricciones de capacidad y conservación en los nodos V – {s,t}. En este caso el patrón de flujo f de ser tal que:
Problema de flujo a coste mínimo
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
Red residual:La red residual R(f) correspondiente a un flujo f se define como sigue: Reemplazamos cada arco (i,j) A por dos arcos (i,j) y (j,i). El arco (i, j) ∈tiene un coste c (i, j) y una capacidad residual de r (i, j)= k (i, j) – f (i, j), y el arco (j,i) tiene un coste de c (j, i) = – c (i, j) y una capacidad residual de r(j,i) = f(i,j). En la red residual se consideran sólo los arcos con capacidad positiva.
Intenta enviar las Φ unidades de flujo de s a t eligiendo en cada iteración el camino de mínimo coste de s a t, que envía un flujo igual al cuello de botella del camino. El algoritmo termina cuando se han enviado las Φ unidades de flujo, o no hay camino de s a t. En este último caso el problema no tiene solución. Denotamos:CT = coste total del camino que envía las Φ unidadesCC = coste del camino mínimo que se calcula en cada iteración.Sea G = (V,A) un grafo dado, y s y t dos vértices fijados a priori.
El algoritmo de Busacker y Gowen
FACULTAD DE INGENIERÍA INDUSTRIAL Y MECÁNICA
top related