problema de transporte | Juego 6 (Método MODI – Método UV)

Hay dos fases para resolver el problema del transporte. En la primera fase, se tiene que encontrar la solución factible básica inicial y la segunda fase implica la optimización de la solución factible básica inicial que se obtuvo en la primera fase. Hay tres métodos para encontrar una solución factible básica inicial,

1. Método de la esquina noroeste
2. Método de celda de menor costo
3. Método de aproximación de Vogel

Este artículo discutirá cómo optimizar la solución factible básica inicial a través de un ejemplo explicado. Considere el siguiente problema de transporte.

Solución:

Paso 1: Compruebe si el problema está equilibrado o no.
Si la suma total de toda la oferta de las fuentes O1 , O2 y O3 es igual a la suma total de todas las demandas de los destinos D1 , D2 , D3 y D4 , entonces el problema de transporte es un problema de transporte equilibrado.

Nota: si el problema no está desequilibrado, se puede seguir el concepto de una fila ficticia o una columna ficticia para transformar el problema desequilibrado en equilibrado, como se explica en este artículo.

Paso 2: Encontrar la solución factible básica inicial.
Cualquiera de los tres métodos antes mencionados se puede utilizar para encontrar la solución factible básica inicial. Aquí, se utilizará el método de la esquina noroeste . Y de acuerdo con el método de la esquina noroeste, esta es la solución factible básica inicial final:

Ahora, el costo total del transporte será (200 * 3) + (50 * 1) + (250 * 6) + (100 * 5) + (250 * 3) + (150 * 2) = 3700 .

Paso 3: método UV para optimizar la solución factible básica inicial.
La siguiente es la solución factible básica inicial:

– Para el método UV , se deben encontrar los valores u _i y v _{j para las filas y las columnas respectivamente.} Como hay tres filas, se deben encontrar tres valores de u _i , es decir, u ₁ para la primera fila, u ₂ para la segunda fila y u ₃ para la tercera fila. De manera similar, para cuatro columnas se deben encontrar
cuatro valores de v _j , es decir, v ₁ , v ₂ , v ₃ y v ₄ . Revisa la imagen a continuación:

Hay una fórmula separada para encontrar u _i y v _j ,
u _i + v _j = C _ij donde C _ij es el valor de costo solo para la celda asignada. Lea más sobre esto aquí .

Antes de aplicar la fórmula anterior, debemos verificar si m + n – 1 es igual al número total de celdas asignadas o no, donde m es el número total de filas y n es el número total de columnas.
En este caso, m = 3, n = 4 y el número total de celdas asignadas es 6, por lo que m + n – 1 = 6. El caso en que m + n – 1 no es igual al número total de celdas asignadas se discutirá en el publicaciones posteriores.

Ahora, para encontrar el valor de u y v, asignamos cualquiera de las tres u o cualquiera de las cuatro v como 0. En este caso, asignamos u ₁ = 0 . Luego, utilizando la fórmula anterior, obtendremos v ₁ = 3 como u ₁ + v ₁ = 3 (es decir, C ₁₁ ) y v ₂ = 1 como u ₁ + v ₂ = 1 (es decir, C ₁₂ ). De manera similar, tenemos el valor de v ₂ = 1 , por lo que obtenemos el valor de u ₂ = 5 , lo que implica que v₃ = 0 . Del valor de v ₃ = 0 obtenemos u ₃ = 3 lo que implica v ₄ = -1 . Vea la imagen a continuación:

Ahora, calcule las penalizaciones usando la fórmula P _ij = u _i + v _j – C _ij solo para las celdas no asignadas. Tenemos dos celdas sin asignar en la primera fila, dos en la segunda fila y dos en la tercera fila. Vamos a calcular esto uno por uno.

1. Para C ₁₃ , P ₁₃ = 0 + 0 – 7 = -7 (aquí C ₁₃ = 7 , u ₁ = 0 y v ₃ = 0 )
2. Para C ₁₄ , P ₁₄ = 0 + (-1) -4 = -5
3. Para C ₂₁ , P ₂₁ = 5 + 3 – 2 = 6
4. Para C ₂₄ , P ₂₄ = 5 + (-1) – 9 = -5
5. Para C ₃₁ , P ₃₁ = 3 + 3 – 8 = -2
6. Para C ₃₂ , P ₃₂ = 3 + 1 – 3 = 1

La regla: si obtenemos el valor de todas las penalizaciones como cero o valores negativos, significa que se alcanza la optimización y esta respuesta es la respuesta final. Pero si obtenemos algún valor positivo, significa que debemos continuar con la suma en el siguiente paso.

Ahora encuentre la pena positiva máxima. Aquí el valor máximo es 6 que corresponde a la celda C ₂₁ . Ahora esta celda es una nueva celda básica. Esta celda también se incluirá en la solución.

La regla para dibujar un camino cerrado o bucle. Comenzando desde la nueva celda básica, dibuje un camino cerrado de tal manera que el giro en ángulo recto se realice solo en la celda asignada o en la nueva celda básica. Vea las siguientes imágenes:

Asigne un signo más-menos alternativo a todas las celdas con giro en ángulo recto (o la esquina) en el bucle con el signo más asignado en la nueva celda básica.

Considere las celdas con un signo negativo. Compare el valor asignado (es decir, 200 y 250 en este caso) y seleccione el mínimo (es decir, seleccione 200 en este caso). Ahora reste 200 de las celdas con un signo menos y agregue 200 a las celdas con un signo más. Y dibuja una nueva iteración. El trabajo del ciclo ha terminado y la nueva solución se ve como se muestra a continuación.

Verifique que el número total de celdas asignadas sea igual a (m + n – 1). Nuevamente encuentre los valores de u y los valores de v usando la fórmula u _i + v _j = C _ij donde C _ij es el valor de costo solo para la celda asignada. Asigne u ₁ = 0 y luego obtenemos v ₂ = 1 . Del mismo modo, obtendremos los siguientes valores para u _i y v _j .

Encuentre las penalizaciones para todas las celdas no asignadas usando la fórmula P _ij = u _i + v _j – C _ij .

1. Para C ₁₁ , P ₁₁ = 0 + (-3) – 3 = -6
2. Para C ₁₃ , P ₁₃ = 0 + 0 – 7 = -7
3. Para C ₁₄ , P ₁₄ = 0 + (-1) – 4 = -5
4. Para C ₂₄ , P ₂₄ = 5 + (-1) – 9 = -5
5. Para C ₃₁ , P ₃₁ = 0 + (-3) – 8 = -11
6. Para C ₃₂ , P ₃₂ = 3 + 1 – 3 = 1

Hay un valor positivo, es decir, 1 para C ₃₂ . Ahora esta celda se convierte en nueva celda básica.

Ahora dibuje un bucle a partir de la nueva celda básica. Asigne un signo más y menos alternativo con una nueva celda básica asignada como un signo más.

Seleccione el valor mínimo de los valores asignados a la celda con un signo menos. Resta este valor de la celda con un signo menos y súmalo a la celda con un signo más. Ahora la solución se ve como se muestra en la siguiente imagen:

Compruebe si el número total de celdas asignadas es igual a (m + n – 1). Encuentre los valores de u y v como se indicó anteriormente.

Ahora encuentre nuevamente las penalizaciones para las celdas no asignadas como se indicó anteriormente.

1. Para P ₁₁ = 0 + (-2) – 3 = -5
2. Para P ₁₃ = 0 + 1 – 7 = -6
3. Para P14 = 0 ₊ 0 – 4 = -4
4. Para P ₂₂ = 4 + 1 – 6 = -1
5. Para P ₂₄ = 4 + 0 – 9 = -5
6. Para P ₃₁ = 2 + (-2) – 8 = -8

Todos los valores de penalización son valores negativos. Por lo que se alcanza la optimalidad.

Ahora, encuentre el costo total, es decir (250 * 1) + (200 * 2) + (150 * 5) + (50 * 3) + (200 * 3) + (150 * 2) = 2450