El método de la ruta más corta es un método de programación lineal, que permite buscar la solución a un problema de optimización que resulte de una combinatoria y de diferentes aplicaciones, el objetivo de este método esta en encontrar rutas cortas o de menor costo, según sea el caso, que va desde un nodo especifico hasta cada uno de los demás nodos de la red.
En este sentido un nodo es una representación gráfica en forma de circulo, este nodo es muy importante ya que denota los orígenes y destinos del problema que se realice, asimismo una red representa un conjunto de puntos y líneas que conectan pares de puntos, estos puntos son los que llamaremos nodos y las líneas serían las aristas.
Un ejemplo simple para aplicar a este tipo de problemas sería el viaje de una persona desde un estado a ciudad el cual pudiese tener varias alternativas, según el interés de la persona, bien sea para ir más rápido o llegar de manera económica según sus recursos, para el primer caso se minimizaría la distancia y para el segundo caso el costo.
En cualquier caso el objetivo consistiría en encontrar la ruta más eficiente a un menor costo, y por lo tanto tendríamos que los estados estarán representados como los nodos y las carreteras como los arcos.
IMPORTANCIA
Este método es muy importante ya que por medio de este modelo se pueden resolver de manera rápida, ya que pueden formularse como modelos de redes obteniendo soluciones enteras sin necesidad de restricciones, aunque en algunos casos pudieran tenerlas. Asimismo se puede decir que no importa que tan grande sea el problema se puede resolver por pequeños algoritmos.
El problema de la ruta más corta es fundamental en muchas áreas, como son: Investigación de operaciones, ciencia de la computación e ingeniería.
Algunas de las razones son:
- La amplia variedad de aplicaciones prácticas como es el envío de algún material entre dos puntos específicos de la forma más eficiente, económica o rápida.
- Existen métodos de solución eficientes, los cuales al ser aplicados a una red con características específicas, proveen una solución exacta a un tiempo y costo razonables.
- Se puede utilizar como inicio en el estudio de modelos complejos de redes, esto es, cuando no se conoce la estructura de la red se pueden aplicar algoritmos para conocer algunas características de la red (presencia de ciclos negativos).
- Se utiliza frecuentemente como sub-problemas (subrutinas) en la solución de problemas combinatorios y redes, así en el caso de problemas para los cuales no existe un algoritmo de solución exacto, la aplicación de algoritmos de ruta más corta, resultan auxiliares para encontrar una buena solución.
APLICACIONES
En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la vida práctica, dentro de las que podemos mencionar:
- Transporte,
- Horarios de operadores telefónicos,
- Planeación de tráfico urbano,
- Trasbordo,
- En las redes eléctricas,
- Diseño de rutas de vehículos,
- Telecomunicaciones,
- Planeación de inventarios,
- Planeación de producción, entre otros...
EL PROBLEMA
Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente gráfica dadas en cientos de metros. Formule un modelo de transbordo y resuelva mediante cualquier paquete de herramientas de investigación operativa que permita establecer la ruta más corta para poder así auxiliar al minero.
VARIABLES DE DECISIÓN
El nombre de las variables en este caso poco importa, dado que de ser escogida para la solución básica eso significa simplemente que será empleada como ruta para ir a rescatar al minero, sin embargo nada tiene de malo el que se le pueda asociar con el envío de unidades desde la entrada de la mina hacia el minero, por ende puede sugerirse este como nombre de las variables. "Cantidad de unidades enviadas desde el nodo i hacia el nodo j".
X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2 X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3 X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3 X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4 X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2 X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4 X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5 X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6 X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7 X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4 X56 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6 X57 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7 X58 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8 X67 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7 X69 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9 X76 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6 X78 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8 X79 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9 X87 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7 X89 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9
RESTRICCIONES
Restricciones de Oferta y Demanda
Hay que recordar que el objetivo de este modelo es la consecución de un plan de ruta que nos permita encontrar al minero lo más pronto posible al recorrer la distancia mínima posible, por ende la clave para plantear el modelo como si fuese de transbordo es establecer una demanda y oferta igual a la unidad (1).
X12 + X13 = 1
X69 + X79 + X89 = 1
Restricciones de Balance
X12 + X32 - X23 - X24 = 0
X13 + X23 - X32 - X34 - X35 = 0
X24 + X34 + X54 - X46 - X47 = 0
X35 - X54 - X56 – X57 – X58 = 0
X46 + X56 + X57 - X67 – X69 = 0
X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0
X78 + X58 – X89 = 0
En palabras sencillas: "Todo lo que entra a cada nodo es igual a lo que sale de él"
La ruta más corta para rescatar al minero tiene como distancia total 1600 metros (dado que las distancias estaban dadas en cientos de metros) y es tal como se muestra en la siguiente gráfica.
¿UN PLANETA HELADO EN EL CONFÍN DEL SISTEMA SOLAR?
"Astrónomos aseguran tener evidencias de un Nuevo planeta en el sistema solar"
El equipo de astrónomos del California Institute of Technology (Caltech) que investigaba un puñado de rocas espaciales que se habían alineado sin razón aparente más allá de Plutón. Por su lejanía respecto del sol sería un planeta helado. El planeta misterioso estaría orbitando alrededor del sol unas 20 veces mas lejos que neptuno Konstantin Batygin y Mike Brown, del
Caltech, dicen que lo que han denominado “Planeta Nueve” tiene una masa diez
veces superior a la Tierra y una órbita muy alongada mucho más afuera que la de
Plutón, que necesitaría entre 10.000 y 20.000 años para dar una vuelta completa
alrededor del sol.
Los investigadores han identificado su
existencia mediante Modelación
matemática y Simulación
computarizada, explican en el Astronomical Journal. Todavía no lo ha podido observar de manera directa, aunque se conoce su órbita.
Este nuevo mundo helado, no fue detectado
hasta ahora debido a su lejanía. Brown y Batygin venían investigando versiones
según las cuales 13 objetos helados en el cinturón Kuiper (región del espacio
donde está Plutón) tenían en común algunos raros rasgos orbitales que tal vez
podrían explicar por la presencia de un pequeño planeta. Suponían que iban a
demostrar que todo eso estaba equivocado, pero resulta que hicieron este descubrimiento.
Encontraron que 6 de los 13 objetos del cinturón Kuiper se movían en órbitas
orientadas en la misma dirección. Además, esas órbitas estaban inclinadas en el
mismo ángulo que los otros ocho planetas del sistema solar.
Los astrónomos han creído, durante mucho
tiempo, que el sistema solar comenzó con cuatro nodos planetarios. La gravedad
de esos nodos atrajo el polvo circundante formando los cuatro gigantes de gas:
Júpiter, Saturno, Urano y Neptuno.
Brown
dice: "Pero también pudo haber cinco
nodos en lugar de cuatro”. El Planeta Nueve representaría el quinto nodo,
que fue eyectado a su órbita distante y excéntrica por un encuentro
gravitacional con Júpiter o Saturno.
Los astronomos esperan que sea posible observar este nuevo planeta directamente con los telescopios más grandes del Mundo.
¿Quién sabe que descubrimientos nos aguardan aún en nuestro propio sistema solar?
Este es un problema propuesto en el texto "Investigación de Operaciones de TAHA" que hace referencia a una red de gasoductos en la que los distintos nodos representan estaciones de bombeo y recepción, los costos se encuentran en las rutas de la siguiente figura:
VARIABLES DE DECISIÓN
X12 = Cantidad de galones enviados desde la estación 1, hacia la estación 2 X17 = Cantidad de galones enviados desde la estación 1, hacia la estación 7 X37 = Cantidad de galones enviados desde la estación 3, hacia la estación 7 X34 = Cantidad de galones enviados desde la estación 3, hacia la estación 4 X72 = Cantidad de galones enviados desde la estación 7, hacia la estación 2 X75 = Cantidad de galones enviados desde la estación 7, hacia la estación 5 X57 = Cantidad de galones enviados desde la estación 5, hacia la estación 7 X62 = Cantidad de galones enviados desde la estación 6, hacia la estación 2 X65 = Cantidad de galones enviados desde la estación 6, hacia la estación 5 X56 = Cantidad de galones enviados desde la estación 5, hacia la estación 6 X54 = Cantidad de galones enviados desde la estación 5, hacia la estación 4
LINGO es una herramienta diseñada para construir y resolver modelos de optimización matemática. LINGO proporciona un paquete integrado que incluye un potente lenguaje para expresar modelos de optimización, un ambiente con todas las funciones para los problemas de construcción y edición, y un conjunto de solucionadores rápidos incorporados, capaces de resolver de manera eficiente la mayoría de las clases de modelos de optimización. Aprender acerca del acceso a las herramientas más poderosas de LINGO a través de su lenguaje es una tarea compleja, sin embargo los modelos que no precisan de un complejo uso de recursos pueden resolverse con una sintaxis sumamente sencilla.
SOLUCIÓN DE UN PROBLEMA DE
PROGRAMACIÓN LINEAL CON LINGO
Al igual que para cualquier otro método de resolución, el primer paso para resolver un problema de programación lineal (PL) consiste en el modelamiento matemático, y es en esta fase en la que el profesional de Ingeniería Industrial debe desarrollar su mayor habilidad y destreza. Los pasos para resolver un problema de PL se encuentran en el módulo de programación lineal.
EL PROBLEMA
Un herrero con 80 Kg. de acero y 120 Kg. de aluminio quiere hacer bicicletas de paseo y de montaña que quiere vender, respectivamente a 20.000 y 15.000 pesos cada una para sacar el máximo beneficio. Para la de paseo empleará 1 Kg. De acero y 3 Kg. de aluminio, y para la de montaña 2 Kg. de ambos metales. ¿Cuántas bicicletas de paseo y de montaña deberá fabricar para maximizar las utilidades?
EL MODELO MATEMÁTICO
Acero
Aluminio
Precio de Venta
Bicicleta de paseo (x)
1 kg
3 kg
$ 20.000
Bicicleta de montaña (y)
2 kg
2 kg
$ 15.000
Disponibilidad
80 kg
120 kg
Declaración de variables
x = Cantidad de bicicletas de paseo a producir
y = Cantidad de bicicletas de montaña a producir
Restricciones de capacidad
Aluminio:
x + 2y <= 80
Acero:
3x + 2y <= 120
Función Objetivo
Zmax = 20000x + 15000y
INGRESANDO LOS DATOS A LINGO
La interfaz de LINGO es quizá la más simple de todas las aplicaciones de resolución de modelos matemáticos, y en el caso de los modelos de programación lineal el ingreso de los datos es muy sencillo, en su ventana inicial es suficiente con utilizar un comando de apertura "MODEL:" y uno de cierre "END", en medio de estos comandos se escribe el modelo tal como mostramos a continuación:
Como podemos observar, el comando "MAX:" se utiliza para consignar la función objetivo y su criterio (en caso de minimizar se utilizará MIN:). Para separar cada línea de código es necesario utilizar el caracter ";". Una vez tenemos el código con nuestras restricciones establecidas, procedemos a resolver, dando clic en el botón Solve:
Al resolver obtendremos el reporte solución, con base en sus datos podremos efectuar un análisis de sensibilidad, hay que tener en cuenta que los datos expresados en el reporte se encuentran en función de la línea de código ingresada, por lo tanto hay que considerar en que línea se escribió cada restricción y función objetivo para hacer un adecuado análisis.
Objective Function: Nos muestra el resultado de nuestra función objetivo, en este caso la solución óptima tiene una función objetivo (utilidad) de $ 850.000.
Value: Es el valor que toman las variables de decisión en la función objetivo.
Slack or Surplus: Cuando la restricción en cuestión tiene el operador <=, corresponde a una holgura, es decir, se puede interpretar como el recurso no utilizado. Cuando la restricción en cuestión tiene el operador >=, corresponde a un exceso, es decir, se puede interpretar como el recurso utilizado por encima de la restricción de mínimo uso.
Dual Price: El precio sombra de una restricción, es el cambio marginal de la función objetivo cuando el valor del lado derecho de la restricción aumenta en una unidad. En nuestro ejemplo sería así: por cada kg de acero adicional que tengamos disponible, la función objetivo aumentará en $ 1250.
El término simulación se utiliza en las disciplinas
científicas para señalar la acción de representar una cosa mediante algún
modelo con cierto grado de abstracción. Con los avances de la tecnología en el
desarrollo de las computadoras personales, hoy en día se puede interpretar la simulación
como un proceso de diseñar y realizar experimentos con modelos matemático en
una computadora.
En ciertas áreas de trabajos se
identifican los procesos de modelar y simular como uno solo; sin embargo, es de
vital importancia conocer que no es así y aprender a diferenciarlos. Es totalmente cierto que en
conjunto representan un novedoso método científico, pero se debe tener en
cuenta que la modelación puede realizarse sin necesidad de desarrollar el
proceso de simulación, a diferencia de este último, el cual no puede ser efectuado
sin la existencia del proceso de modelación.
Por medio de los mismos se puede dirigir unaindustria o proceso
a un direccionamiento empresarial más claro y confiable, contribuyendo así con la
formación de profesionales mejor capacitados para satisfacer las necesidades y
cumplir con los objetivos planteados. Se logran detallar con interés particular las limitaciones de sistemas,
la capacidad de producción, el tiempo del proceso, el tiempo ocioso del talento
humano, el consumo innecesario de los insumos, entre otros. Como resultado se obtiene una representación
razonable de un proceso que facilita al analista su comprensión, evaluación y
mejoramiento del sistema productivo.
El modelo de simulación es una herramienta
muy utilizada, valiosa en el análisis, diseño y operación de sistemas y
procesos complejos. Se puede definir también como el proceso de diseñar y
desarrollar un modelo computarizado de un sistema y dirigir experimentos con
dicho modelo teniendo como fin el fácil entendimiento del comportamiento del
sistema y/o la evaluación de las distintas estrategias con las que se puede
poner en funcionamiento el sistema. Debido a su alcance, se considera que los
modelos de simulación son los que pueden interactuar con el resto aunque con
las complejidades de las investigaciones científicas actuales, pueden
encontrarse combinaciones de diferentes modelos.
La simulación discreta es una de las
herramientas que se utilizan para modelar sistemas reales y sobre el modelo
construido evaluar el impacto que tendrían ciertas decisiones, mejorando así la
toma de decisiones sobre el sistema real.
En el estudio de un proceso productivo, la
simulación ofrece beneficios económicos para la empresa debido a que las
decisiones se realizan en el sistema real, una vez los datos arrojados
evidencian que la decisión se ajusta significativamente respecto a la meta
planteada; evitando así inversiones injustificadas de dinero que ocurren
cuando no se tienen en cuenta los efectos a largo plazo. Como bien sabemos, en
la actualidad los sistemas de producción son muy complejos y el hecho de tomar
una mala decisión puede llegar a generar grandes pérdidas para la empresa por
lo que es necesario y de gran ayuda Simular el proceso y así poder analizar los
diferentes escenarios que permitan tomar mejores decisiones sobre el sistema
final. Básicamente, resume toda la teoría relacionada con un proceso en el cual
se sustituyen situaciones reales por otras creadas artificialmente.
“...La simulación
consiste simplemente en poner a un individuo en un ambiente que omite algún
aspecto de la realidad y en idear dentro de ese marco un problema que exija la
participación activa del analista para iniciar y llevar a cabo una serie de
indagaciones, decisiones y actos...”
Objetivos principales de la Simulación: - Descubrir el comportamiento de un
sistema. - Postular teorías o hipótesis que
expliquen el comportamiento observado. - Usar esas teorías para predecir el
comportamiento futuro del sistema, es decir, mirar los efectos que se
producirían en el sistema mediante los cambios dentro de él o en su método de
operación.
Su
importancia como método radica en que reproduce los objetos reales cuando por
problemas, bien sea de tiempo o de recursos, no es posible realizar la
actividad en su medio natural. Por lo que precisamente surge la utilización tan
amplia de este método, pues se aplica prácticamente en todas las disciplinas y
ramas de la ciencia. De igual forma, la modelación facilita el análisis de los
procesos del original en aquellos casos en que resulta difícil, imposible o
costoso investigar los objetos reales. Es
evidente que la explotación eficiente de la simulación, como método de
enseñanza, requiere, además del enriquecimiento de su teoría mediante las
experiencias de su aplicación, el esclarecimiento de sus fundamentos
filosóficos, lo cual se logra en alguna medida cuando se analiza dicho método
de aprendizaje en su relación con uno de los métodos científicos generales de
obtención del conocimiento: La Modelación.
