PHPSimplex

Optimizando recursos con Programación Lineal



Camino mínimo

Los problemas conocidos como problemas del camino mínimo o camino más corto tratan, como su nombre indica, de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.

Ejemplo

Una persona tiene que desplazarse a diario de un pueblo A a otro G. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:

Problema del camino mínimo

 

Determinar las variables de decisión y expresarlas algebraicamente. En este caso:

Determinar las restricciones y expresarlas como ecuaciones o inecuaciones dependientes de las variables de decisión. Dichas restricciones se deducen del balance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que regresen al punto de partida y aquellos que provengan del punto de destino):

Expresar todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores, ... En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:

Determinar la función objetivo:

Realizar un cambio de variables con la siguiente correspondencia:

XAB XAC XBE XBD XDB XEB XCD XCF XFC XDC XDE XED XEG XFG
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14

Resolver con PHPSimplex.

Copyright ©2006-2016 PHPSimplex. Todos los derechos reservados. Términos y condiciones.
Síguenos en Twitter
X

PHPSimplex
Versión 0.81

Copyright ©2006-2016. Todos los derechos reservados.

Desarrollado por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Traducción a inglés por:
Luciano Miguel Tobaria

Traducción a francés por:
Ester Rute Ruiz