SIMPLEX PARA REDES

Método simplex para redes

1.   INTRODUCCIÓN

En esencia la programación lineal provee de métodos y formas de análisis de eficiencia y eficacia en cierto proceso o situación, esto es lograr el objetivo según lo planeado haciendo un uso adecuado y racional de los recursos y variables que intervienen. En algunos problemas de optimización puede ser útil representar el problema a través de una gráfica: ruteo de vehículos, distribución de producto, programa de actividades en un proyecto, redes de comunicación, etc.

Los problemas de transporte, transbordo, camino más corto, flujo máximo, red deproyectos (cpm) son casos especiales del modelo de flujo de costo mínimo en una red y pueden resolverse con una forma especial del simplex.

En nuestro caso nos enfrentamos a un problema real el cual podemos modelar por medio de redes, los nodos indican puntos estratégicos, k_IJ indica el número de pasajeros promedio que acuden a dicho punto y c_IJ el costo en tiempo que requiere desplazarse de determinado nodo al otro. Por tanto este trabajo muestra la manera de determinar por el método simplex la mejor forma de recoger los pasajeros en el menor tiempo posible.

2.   OBJETIVOS

• Construir un modelo matemático que permita representar con la mejor exactitud una situación real para encontrar soluciones óptimas.

• Determinar dicha solución haciendo uso de la metodologías aprendidas como lo es el método simplex.

3.   DESARROLLO DE ACTIVIDADES

3.1.      FORMULACION DE EL PROBLEMA

Existe la propuesta de crear una nueva ruta de transporte público a nivel del casco urbano, se tiene una lista de puntos clave (paraderos) en los cuales se concentra determinado número de pasajeros, se busca conocer la mejor forma de pasar por todos ellos en el menor tiempo posible de manera que se minimicen costos en cuanto a combustible y tiempo.

3.2.      MODELO DEL SISTEMA REAL

3.3.      MODELO MATEMÁTICO

El objetivo es representar la situación por medio de un modelado de redes y así poder implementar el método simplex.

Los nodos de la red representan los paraderos del sistema de transporte público, puntos claves de transbordo con determinado número promedio de pasajeros en la ciudad. Los arcos representan las rutas posibles y las distancias representan el tiempo de recorrido que depende de las paradas. El origen está en el nodo 1 y en el nodo 6 se encuentra el final del recorrido. Se quiere encontrar la ruta más corta del origen a cada nodo de transbordo y en particular la ruta más corta al destino final.

3.3.1.            DIAGRAMA DE RED

3.3.2.   PLANTEAMIENTO DE LAS ECUACIONES

Para la definición del algoritmo Simplex para un problema de redes es imprescindible partir de una solución básica factible con la que iniciar el proceso de iteración. La obtención de esta solución básica factible puede realizarse haciendo uso de variables de holgura y resolviendo la Fase I del sistema de ecuaciones así obtenido. Por tanto, definimos todas las posibles rutas como y le asignamos variables las cuales tendrán determinado valor en tiempo y en número de pasajeros. El problema se redactaría de la siguiente manera:

Existen 5 posibles rutas x1, x2, x3, x4, x5; cuyos beneficios en número de pasajeros y demanda en tiempo se relacionan en la tabla, se busca conocer la ruta más eficiente, esto es la que obtenga el mayor número de pasajeros en el menor tiempo posible.

3.3.2.1.     FUNCION OBJETIVO

El programa nos muestra con un valor de 1 cercano a la ruta más probable y con cero la que definitivamente es ineficiente por tanto la función objetivo será:

z = x1 + x2 + x3 + x4 +x5

3.3.2.2.     RESTRICCIONES

Tenemos dos restricciones una en el número de pasajeros y otra en el tiempo empleado por tanto el número de pasajeros debe ser mínimo el menor número de pasajeros de las rutas y el máximo tiempo empleado por las rutas:

16x1 + 19x2 + 17x3 + 21x4 + 16x5 >= 16

16x1 + 21x2 + 14x3 + 11x4 + 10x5 <= 21

3.3.2.3.     SOLUCION POR EL METODO SIMPLEX

Tabla simplex

Tabla 2

El método simplex nos indica que la ruta X4 es la más óptima recogiendo 21 pasajeros en 11minutos.

4.   CONCLUSIONES

Los métodos que provee la programación lineal son una herramienta bastante útil en la toma de decisiones en distintos campos de acción, permite conoce la mejor manera de hacer las cosas teniendo en cuenta los recursos y así obtener el mejor beneficio.

Los modelos gráficos nos ayudan a comprender mejor el problema, a visualizar alternativas y representar de la mejor manera la situación real, a partir de él es mucho más fácil generar un modelo matemático para su solución. El método simplex admite un gran número de variables así como de restricciones, su metodología es netamente aritmética y fácil de manejar, y asigna un valor a la variable más óptima.

      5. BIBLIOGRAFÍA

 [1].Modulo de Probabilidad y estadística pág. 78-112

 [2].G ASS, Saul I. Linear Programming. Methods and Applications. Editorial    McGraw Hill. 1969.

video del metodo simplex para red