Comprobando la Optimalidad
Se puede realizar la prueba de optimalidad si se cumplen dos condiciones, es decir
1. Hay m + n - 1 asignaciones, cuya m es el número de filas, n es el número de columnas. Aquí m + n - 1 = 6. Pero el número de asignación es de cinco.
2. Estas asignaciones de m + n - 1 deben estar en posiciones independientes. Es decir, no debería ser posible aumentar o disminuir ninguna asignación sin cambiar la posición de las asignaciones o violar las restricciones de fila o columna.
Una regla simple para que las asignaciones se encuentren en posiciones independientes es que es imposible viajar desde cualquier asignación, de vuelta a sí mismo mediante una serie de pasos horizontales y verticales desde una celda ocupada a otra, sin una inversión directa de la ruta. Se puede ver que en el presente ejemplo, la asignación está en posiciones independientes ya que no se puede formar un bucle cerrado en las celdas asignadas.
Por lo tanto, no se cumple la primera condición y, por lo tanto, para satisfacer la primera condición, tendremos que asignar una pequeña cantidad E a las celdas vacías que tengan el costo de transporte más bajo. Se puede ver que t puede asignarse a la celda (2, 2) con un costo de 7 unidades y aún así las asignaciones permanecerán en una posición independiente como se describe a continuación:
Ahora el número de asignación es m + n- = 6 y están en posiciones independientes.
Anote la matriz de costos en las celdas asignadas.
Matriz de costo inicial para celdas asignadas.
También escriba los valores de u i y v j como se explicó anteriormente.
Matriz de evaluación celular
En la tabla 5 se puede ver que la evaluación de la celda en la celda (1, 4) es negativa, es decir -4, por lo tanto, al asignar el costo de transporte a la celda (1, 4), se debe reducir aún más. Anotemos las asignaciones originales y la nueva asignación propuesta.
En la tabla 6 puede verse que si asignamos en la celda (1, 4) se forma un bucle como se muestra y asignamos 10 unidades para que la asignación en la celda (2, 4) desaparezca como se muestra a continuación en la tabla 7.
Nueva tabla de asignación se convertirá
Costo de transporte = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 unidades. Es decir, el costo de transporte ha bajado de 475 unidades a 435 unidades.
Compruebe la Optimidad:
¡A ver si esta solución es óptima! ¿o no? Para eso de nuevo hay que comprobar dos condiciones, es decir,
Nº de asignación = m + n - 1 = 6 (satisfecho)
Asignación en posición independiente (satisfecha ya que no se forma el bucle cerrado para las celdas asignadas)
Escriba el costo en los valores y valores asignados de u i y v j
Ejemplo 2:
(Desequilibrio de oferta y demanda). Resuelve el siguiente problema de transporte
Suministro total = 200 unidades, Demanda = 185 unidades.
Solución:
Dado que la oferta y la demanda no son iguales, el problema está desequilibrado. Para equilibrar el problema, se debe agregar una columna ficticia como se muestra a continuación. La demanda en esa columna ficticia (tienda) será de 15 unidades.
Solución factible básica:
Usaremos el método de aproximación de Vogel's para encontrar la solución factible inicial.
La solución factible inicial está dada por la siguiente matriz:
Prueba de optimalidad:
De la matriz anterior encontramos que:
(a) Número de asignaciones = m + n - 1 = 4 + 5-1 = 8
(b) Estas asignaciones de m + n - 1 están en posiciones independientes.
Por lo tanto se puede realizar la prueba de optimalidad. Consiste en los pasos secundarios explicados anteriormente como se muestra en las Tablas a continuación:
Dado que los valores celulares son + ve, la primera solución factible es óptima. Como la tabla 6 contiene cero entradas, existen soluciones óptimas alternativas. La importancia práctica de que la demanda sea 15 unidades menos que la oferta es que la empresa puede reducir la producción de 15 unidades en la fábrica donde no es económico.
El transporte óptimo (mínimo) más el costo de producción.
Z = Rs. (4 x 25 + 6 x 5 + 8 x 20 +10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)
= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1, 465.
Ejemplo 3:
Resuelve el siguiente problema de transporte para maximizar el beneficio. Debido a la diferencia en el costo de la materia prima y el costo de transporte, la ganancia por unidad en rupias es diferente a la que se muestra en la siguiente tabla:
Resuelve el problema para maximizar el beneficio.
Solución:
El problema está desequilibrado y, por lo tanto, se debe agregar una fila ficticia para equilibrarlo.
Encuentre la solución factible básica inicial:
Utilizaremos el método de aproximación de vogel's para determinar la solución factible inicial.
Tenga en cuenta que estamos tratando con el problema de maximización. Por lo tanto, introduciremos la diferencia entre los elementos más altos y segundos más altos en cada fila a la derecha de la fila y la diferencia entre los elementos más altos y segundos más altos en cada columna debajo de la columna correspondiente.
Cada una de estas diferencias representa el beneficio unitario perdido por no asignarse a la celda de mayor beneficio. Por lo tanto, mientras hacemos asignaciones, al principio seleccionamos la celda (2, 3) con la entrada más alta en la fila 2 que corresponde a la diferencia más alta de [45].
Prueba de optimalidad:
Número requerido de asignaciones = m + n - 1 = 3 + 4 - 1 = 6
Número real de asignación = 5.
Por lo tanto, asignamos un pequeño número positivo de € a la celda (1, 3) (celda que tiene el máximo beneficio de las celdas vacantes) para que la cantidad de asignaciones se convierta en 6. Estas 6 asignaciones están en posiciones independientes. Por lo tanto se puede realizar la prueba de optimalidad.
Dado que todos los valores de celda son negativos o cero (problema de maximización), la solución factible básica inicial es óptima. La demanda en el primer destino se deja insatisfecha por 5units. El beneficio es
Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]
= Rs. 31.600.
