Aplicaciones
RUTA MÁS CORTA ENTRE DOS NODOS ESPECIFICOS
Suponga que cuesta $10 000 comprar un automóvil nuevo. El costo de operación anual y el valor de reventa de un automóvil usado se muestran en la siguiente tabla:
Suponiendo que en la actualidad se tiene un automóvil nuevo, determine una política de reemplazo que minimice los costos netos de poseer y operar un automóvil durante los siguientes seis años.
Ruta Más Corta Entre Todo Par De Nodos
Problema. Una empresa de comunicaciones desea saber cual es la distancia más corta entre cada uno de los estados (Guanajuato, Hidalgo, Michoacán, Querétaro) para formar una red de comunicación, dada la siguiente red calcular la distancia más corta entre todo par de estados.
Modelo de Programación Lineal, Solución Mediante el Método Floyd
 |  |  |
|---|---|---|
 |  |
El algoritmo consta en tener dos matrices C (controla los costos más cortos en las rutas) y Z (controla los nodos antecesores en las rutas, permite encontrar la ruta), las matrices se componen de {0 si j=i, ∞ si no existe arco y d(i,j) si existe arco}. Se va a seleccionar la fila y columna k de la matriz C entonces, para i y j, con i≠k, j≠k e i≠j se hace: Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj. De lo contrario, dejamos las matrices como están. Si k ≤ n, se aumenta k en una unidad y se repite el paso anterior, de lo contrario termina el algoritmo.
Para la interpretación se tienen las ultimas matrices de la iteción 4, en la cuál C nos dirá el costo de ir de un arco i a j, mientras que Z nos dira por que nodos se tienen que pasar para llegar al nodo buscado, ejemplo: si quiero ir del nodo 1 al 4 el costo sería de 8 y se tendría que pasar (de atrás hacía adelante) de 1 a 4 pasar por el 3, de 1 a 3 pasar por el 2 y finalmente de 1 a 2 es directo, siendo el camino 1-2-3-4.
Flujo Máximo
Ejemplo. Pemex quiere enviar la cantidad máxima posible de petróleo entre algunas de sus refinerías con ciertas capacidades y ciertos requerimientos, en la siguiente gráfica se muestra la red de tuberías
Modelo de Programación Lineal, Solución Mediante el Método Ford y Fulkerson
 |  |  |
|---|
El algoritmo consta en dos etapas, la primera se va a tratar de saturar todos los arcos con los requerimientos solicitados usando las capacidades de los arcos, en la segunda etapa consiste en que si los arcos les sobro capacidad a estos se les aumentará el flujo en n cantidad de flujo dependiendo del que le haga falta, si el flujo es de izquierda a derecha este aumentará y si va de derecha a izquierda el flujo se reducirá en la n cantidad de flujo posible, que será el mínimo de las capacidades posibles de los arcos seleccionados, el algoritmo concluye cuando los arcos lleguen a su capacidad máxima y no se puede aumentar más ya que el flujo llego a su máximo.
En la interpretación de la solución podemos decir que el la cantidad de flujo máximo que puede enviar el nodo 1 son {6,5,3} a los 3, 4 y 5 correspondientemente, mientras que el nodo 2 puede enviar {2,3,5} a los nodos 3, 4 y 5 correspondientemente.
Arborecencia de ruta más corta
En el transporte intermodal, los camiones de remolque cargados se transportan entre terminales ferroviarias sobre plataformas especiales. En la siguiente figura se muestran las ubicaciones de las principales terminales ferroviarias en los Estados Unidos y las vías de ferrocarril existentes. El objetivo es decidir qué vías deben ser revitalizadas para manejar el tráfico intermodal. Todas las terminales restantes pueden vincularse directa o indirectamente, de modo que la longitud total en millas de las vías seleccionadas se minimice.
Determinar los segmentos de las vías ferroviarias que deben incluirse en el programa de revitalización.
Red del problema
Interpretación
Se deben reparar las vías de SE a LA, SE a DE, SE a CH, CH a NY, NY a DC y de DE a DA para tener el punto de origen (SE) conectado a todos los demás estados con el menor número de millas posible que son en total 12,280 millas a reparar.
Flujo Mínimo
Suponga que se tiene la siguiente red de ductos de agua que se trae de Veracruz. Se requiere saber cuál es la cantidad mínima que circula en la red. Los valores corresponden a requerimientos (lij).
Solución
Interpretación
Para calcular el flujo mínimo de la red debemos calcular la diferencia entre V1 y V2 entonces obtendríamos que 45 es la cantidad mínima de agua que circula por los ductos
Flujo a costo Mínimo
GrainCo abastece de maíz a tres granjas avícolas desde tres silos. Las cantidades de oferta en los tres silos son 100, 200 y 50 mil bushels(1 bushel = 35.23 litros). GrainCo usa principalmente ferrocarril para transportar su maíz a las granjas, a excepción de tres rutas, en las que se usan camiones. La siguiente figura muestra las rutas disponibles entre los silos y las granjas. Los silos se representan con los nodos 1, 2 y 3, cuyas cantidades de suministro son [100], [200] y [50], respectivamente. Las granjas se representan con los nodos 4, 5 y 6, cuyas demandas son [-150], [-80] y [-120], respectivamente. Las rutas permiten transbordos entre los silos. Los arcos (1,4), (3,4) y (4,6) son de camiones, con capacidades mínimas y máximas Por ejemplo, la capacidad de la ruta (1,4) es de 50 a 80 mil bushels y costo de $1. Los costos de transporte, por bushel, se indican en sus arcos respectivos. (Capacidad mínima, Capacidad máxima, Costo).
Para resolver el modelos utilizamos el software WIN QSB
Interpretación de Resultados:
Por el arco (1,3) pasaran 50 mil bushels con un costo de $4
Por el arco (1,4) pasaran 50 mil bushels con un costo de $1
Por el arco (2,4) pasaran 150 mil bushels con un costo de $1
Por el arco (2,5) pasaran 50 mil bushels con un costo de $6
Por el arco (3,4) pasaran 70 mil bushels con un costo de $1
Por el arco (3,5) pasaran 30 mil bushels con un costo de $2
Por el arco (4,6) pasaran 120 mil bushels con un costo de $2
Con un costo total mínimo de $1,070.00
Redes de actividad
Una firma de contadores públicos requiere las siguientes actividades para una auditoría
Determinar el tiempo de terminación del proyecto
