El problema general del transporte se refiere a la distribución de mercancía desde cualquier conjunto de centro de suministro, denominados orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados destinos, de tal forma que se minimicen los costos totales de distribución. Cada origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene cierta demanda de unidades que deben recibir de los orígenes.
 |
| Representación de una red de transporte |
Como se puede observar cualquier modelo de transporte se compone de unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de distribución por unidad. Adicionalmente, se tienen varios supuestos:
- Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.
- Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas.
- Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos.
- Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución optima), asumen también valores enteros.
Debido a la particularidad del modelo de transporte la forma tabular Símplex adquiere una estructura que facilita el proceso de asignación a las variables básicas, tal se muestra a continuación:
En los renglones se ubican los orígenes indicando en la columna de la derecha los recursos (oferta disponible). En las columnas se ubican los distintos destinos indicando en el último renglón los totales demandados. En el pequeño recuadro ubicado en la margen superior derecha se indica el costo de distribuir una unidad desde el origen hasta ese destino y en la parte inferior de cada recuadro se registran las asignaciones Xi para cada variable. En los casos donde la sumatoria de los recursos y las demanda no sean las mismas, se agrega un origen o destino ficticio con la cantidad que permita cumplir la propiedad de soluciones factibles.
Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:
En cada iteración se determina una variable básica entrante, una variable básica saliente y luego la nueva solución básica factible. Paso 1: la variable de entrada se determina a partir de la relación Cij - Uij -Vij, donde la variable Xij con el resultado más negativo es la que contribuye en una mejor medida a disminuir el costo total, se debe tener en cuenta que esta disminución va en proporción a la asignación resultante. Paso 2: la variable básica saliente es aquella variable básica que disminuya su valor a cero, es decir, es aquella variable de menor asignación y que participa en la reacción en cadena que se establece para compensar los cambios de asignar valor a la variable entrante que permitan satisfacer las restricciones de recursos y demandas. En este punto, se definen dos tipos variables para receptoras y donadoras, de acuerdo a la variación de signo que se produzca en el polígono que permite la transferencia desde la variable de salida a la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras.
ALGORITMO DE VOGEL
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.
 |
| Forma Tabular Símplex Transporte |
Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:
- Regla de la esquina noroeste.
- Método de la ruta preferente.
- Método de aproximación de Vogel
Antes de explicar el procedimiento para cada uno de estos criterios de asignación para encontrar la solución inicial BF, se debe conocer el número de variables básicas, el cual se determina con la expresión: m + n - 1. En el modelo anterior 3 + 2 - 1 = 4 variables básicas.
- Regla de la esquina noroeste: la primera elección X11, es decir, se inicia la asignación por la esquina noroeste de tabla. Luego se desplaza a la columna de la derecha si todavía quedan recursos en ese origen. De lo contrario se mueve al reglo debajo hasta realizar todas las asignaciones.
- Método de la ruta preferente: se fundamenta en la asignación a partir del costo mínimo de distribuir una unidad. Primero se identifica este costo se realiza la asignación de recursos máxima posible y luego se identifica el siguiente costo menor realizando el mismo procedimiento hasta realizar todas las asignaciones.
- Método de asignación de Vogel: para cada reglón y columna, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño y el costo menor que le sigue en ese renglón o columna. En el renglón o columna con la mayor diferencia, se le asigna al menor costo unitario. Los empates se pueden romper de manera arbitraria.
De estos 3 modelos para encontrar la solución inicial BF, el método de Vogel ha sido el más utilizado. Considerando que este criterio toma en cuenta los costos de distribución de forma más eficaz, ya que la diferencia representa el mínimo costo adicional que se incurre por no hacer una asignación en la celda que tiene el menor costo ya sea columna o renglón.
Posterior a esta asignación inicial se requiere un procedimiento que permita las siguientes iteraciones y se obtenga la solución óptima.
Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij >= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij = Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes de las diferente ecuaciones resultantes se asume el valor de U1 como cero.
Posterior a esta asignación inicial se requiere un procedimiento que permita las siguientes iteraciones y se obtenga la solución óptima.
Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij >= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij = Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes de las diferente ecuaciones resultantes se asume el valor de U1 como cero.
En cada iteración se determina una variable básica entrante, una variable básica saliente y luego la nueva solución básica factible. Paso 1: la variable de entrada se determina a partir de la relación Cij - Uij -Vij, donde la variable Xij con el resultado más negativo es la que contribuye en una mejor medida a disminuir el costo total, se debe tener en cuenta que esta disminución va en proporción a la asignación resultante. Paso 2: la variable básica saliente es aquella variable básica que disminuya su valor a cero, es decir, es aquella variable de menor asignación y que participa en la reacción en cadena que se establece para compensar los cambios de asignar valor a la variable entrante que permitan satisfacer las restricciones de recursos y demandas. En este punto, se definen dos tipos variables para receptoras y donadoras, de acuerdo a la variación de signo que se produzca en el polígono que permite la transferencia desde la variable de salida a la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras.
ALGORITMO DE VOGEL
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
PASO 1
Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.
PASO 2
Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).
PASO 3
De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).
PASO 4: DE CICLO Y EXCEPCIONES
- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.
- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.
- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.
EJEMPLO DEL MÉTODO DE APROXIMACIÓN DE VOGEL
Por medio de este método resolveremos el ejercicio de transporte resuelto en módulos anteriores mediante programación lineal.
EL PROBLEMA
Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.
Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.
El paso siguiente es escoger la mayor penalización, de esta manera:
El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es "2" y que a esa celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la planta 3".
Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.
Se ha llegado al final del ciclo, por ende se repite el proceso
Iniciamos una nueva interacción
Continuamos con las interacciones,
Iniciamos otra interacción
Al finalizar esta iteración podemos observar como el tabulado queda una fila sin tachar y con valores positivos, por ende asignamos las variables básicas y hemos concluido el método.
Los costos asociados a la distribución son:
De esta manera hemos llegado a la solución a la cual también llegamos mediante programación lineal, definitivamente desarrollar la capacidad para modelar mediante programación lineal y apoyarse de una buena herramienta como WinQSB, STORM, LINGO, TORA etc. termina siendo mucho más eficiente que la utilización de los métodos heurísticos para problemas determinísticos;
Sin embargo, cabe recordar que uno de los errores más frecuentes en los que caen los ingenieros industriales es en tratar de adaptar sus organizaciones a los modelos establecidos, cabe recordar que son los modelos los que deben adaptarse a las organizaciones, lo cual requiere de determinada habilidad para realizar de forma inmediata cambios innovadores para sus fines
Un vídeo para mayor entendimiento
No hay comentarios.:
Publicar un comentario