Algoritmo más o menos para problemas de transporte de carga fija

...

Ashram [6] demostró que la existencia de una situación MFL en un TP depende de la presencia de una celda con un índice Modi negativo para su solución óptima. La solución MFL se obtiene de la distribución óptima al aumentar y disminuir las cantidades de envío, al tiempo que se mantienen los requisitos mínimos para la oferta y la demanda. El proceso anterior conduce a una consolidación de envíos a medida que se mueven más unidades a algunas celdas, mientras que otras se agotan simultáneamente (a veces por completo) de la carga inicial, a menudo creando soluciones degeneradas. Debe notarse que una combinación de cargas crecientes y decrecientes es la única posibilidad para lograr MFL; una disminución exclusiva de las cargas daría lugar a una disminución del total de los bienes enviados y violaría las restricciones de los límites inferiores, mientras que un aumento exclusivo dará como resultado el crecimiento de la función de costos.

En el siguiente teorema, discutimos una propiedad inherente en el desarrollo de los algoritmos presentados en este documento.

Theorem 1.

Considere una celda no básica (sin envío) (k, p) en cualquier solución factible. Supongamos que existe una fila q y una columna r tal que las celdas (k, r), (q, r) y (q, p) son básicas. Por supuesto k, q ∈ {1,. . . , m} y p, r ∈ {1,. . . , n}. Deje que Xkr, Xqr y Xqp representen las cantidades en estas celdas, respectivamente. Entonces se puede obtener una solución MFL si el índice MODI, uk + vp, para cell (k, p) no es positivo. Específicamente, la cantidad que se enviará se puede aumentar en la cantidad Xqr mientras se reduce el costo por | uk + vp | * Xqr.

Prueba. Como la celda (k, p) no está cargada, debe haber al menos otra celda cargada tanto en la fila k como en la columna p para satisfacer los requisitos de demanda y suministro. Como se da, las celdas (k, r), (q, r) y (q, p) son básicas con las cantidades Xkr, Xqr y Xqp, respectivamente. Esta información se presenta en una tabla como se muestra en la Fig. 1a.

[pic 2]

Supongamos que movemos una unidad de la celda (q, r) y aumentamos las cargas en las celdas (k, r) y (q, p) en una unidad cada una. El resultado sería que la oferta ak y la demanda bp aumentarían en una unidad cada uno para una ganancia agregada de una unidad, mientras que la oferta aq y la demanda br se mantendrían sin cambios. Para ganar de este movimiento, debemos tener

[pic 3]

Como las celdas (k, r), (q, r) y (q, p) son básicas y ui + vj = cij para cada celda básica, Eq. (4) también se puede escribir como

[pic 4]

Esta es la misma condición que Arsham [6] obtuvo. Porque el costo se reduce por |uk + vp| para cada unidad movida desde la celda (q, r), obtenemos la reducción máxima moviendo la carga completa de la celda (q, r) a las celdas (k, r) y (q, p) como se muestra en la figura 1b.

El resultado neto es que Xqr aumenta el número de unidades que se pueden enviar, mientras que el costo de envío se reduce en una cantidad de | uk + vp | Xqr. ?

Este es un resultado poderoso a pesar de que el análisis está limitado solo a ciertas celdas donde se identifican las condiciones del Teorema 1. Tenga en cuenta que los resultados del Teorema 1 son aplicables a cualquier distribución básica factible y no solo a la solución óptima. Un profesional puede ver cualquier solución viable existente de un problema de transporte de cualquier tamaño; identificar tres celdas básicas que forman un ángulo recto en un rectángulo diagonalmente desde una celda no básica (como se muestra en la Fig. 1a); verificar la condición simple de Eq. (4); y lograr MFL moviendo la carga como se sugiere en el Teorema 1. Este fenómeno de MFL es el resultado de una "consolidación" de envíos, alcanzada al reducir el número de celdas básicas distintas de cero.

Tenga en cuenta que estamos en la búsqueda de células no básicas como la celda (k, p) como se ilustra en la Fig. 1a. Nos referimos a la celda (q, r) como la coincidencia de la celda "diagonal". El objetivo de identificar tales células es mover unidades de esta celda diagonal a otras dos esquinas del rectángulo. Proponemos el siguiente algoritmo heurístico para encontrar una solución MFL de TP.

- Algoritmo MFL para un TP

Paso 1: resuelve el TP usando cualquier método.

Paso 2: crea una matriz de índice Modi usando una solución óptima / actual.

Paso 3: Identifique las celdas no básicas con índices Modi negativos o nulos.

Paso 4: desde las celdas identificadas, seleccione aquellas que forman rectángulos con tres celdas básicas.

Paso 5: Cree una matriz colocando los índices de Modi calculados en las celdas "diagonales".

Paso 6: Cree una matriz de costo de carga multiplicando la matriz anterior por las cargas correspondientes.

Paso 7: Cree una solución MFL alejando la carga de cada celda con coeficientes negativos o cero, comenzando con los coeficientes más negativos y procediendo a las celdas con coeficientes cero, mientras mantiene esa carga

Xij ∀ i y j. FIN

Observación 1. El paso 5 proporciona una matriz que identifica la reducción por unidad de costo si una unidad se aleja de esta posición diagonal a las otras dos esquinas del rectángulo formado en el proceso.

Observación 2. Es posible que una celda diagonal haga coincidir dos o más celdas no básicas con diferentes índices Modi negativos. Tener en cuenta el valor más pequeño de estos proporcionaría la mayor disminución en la iteración.

Observación 3. La condición Xij

El Apéndice A proporciona un ejemplo numérico para ilustrar los pasos del algoritmo MFL para un TP.

- Más por menos análisis (MFL) para FCTP

El MFL para FCTP puede establecerse como un problema de distribución en el cual cada uno de los m proveedores puede enviar a cualquiera de los n clientes a un costo de envío por unidad cij más un costo fijo fij, asumido para abrir esta ruta.

[pic 5]

Como se discutió anteriormente, el fenómeno de MFL en un FCTP