Unidad Cinco: Método de Transporte y Método de Asignación





TRANSPORTE Y ASIGNACIÓN

5.1  Definición del problema de transporte

Método de Transporte
El método de transporte analiza los costos de transporte tanto de la materia prima como de los productos terminados. El método consiste en reducir al mínimo posible los costos destinados a satisfacer los requerimientos totales de demanda y abastecimiento de materiales.

5.2 Método de Aproximación de Vogel (MAV)
Este método es un método de transporte en el cual todos los datos se llevan a una matriz oferta-demanda u origen-destino, se escogerá aquel sitio que cause los mínimos costos totales.

Oferta /Origen
Demanda/Destino

W
X
Y
Z

C11

C12

C13

C14
n1
X11
X12
X13
X14

C21

C22

C23

C24
n2
X21
X22
X23
X24

C31

C32

C33

C34
n3
X31
X32
X33
X34
m1
m2
m3
m4


m1+m2 + m3 + m4  = n1 + n2 + n3

La oferta en todos los orígenes debe igualar a la demanda de todos los destinos. Esta restricción se impone porque es fundamental para desarrollar la técnica de transporte. Sin embargo, cualquier sistema real puede balancearse artificialmente convirtiéndolo en un a un problema con igual oferta y demanda, mediante la añadidura de orígenes o destinos ficticios. Si la demanda excede a la oferta se aumenta un destino ficticio que suministrará la cantidad faltante. Si existe un exceso de oferta se utiliza un destino ficticio para absorber la cantidad excedente. Los costos de transporte por unidad desde el origen ficticio a todos los destinos son ceros ya que esto es equivalente a no transportar desde el origen ficticio. En forma semejante los costos de transporte por unidad desde todas las fuentes a los destinos ficticios es cero. Físicamente las cantidades enviadas desde un origen ficticio pueden interpretarse como escasez de la demanda, mientras que los asignados a un destino ficticio pueden interpretarse como capacidades no utilizadas en el origen.

El MAV es un método heurístico y la mayor parte del tiempo produce soluciones óptimas o muy cercanas a la óptima.

Pasos del MAV
1.    Evalúe una penalización para cada renglón (columna) restando el elemento de costo más pequeño en el renglón (columna) del siguiente elemento de costo más pequeño en el mismo renglón (columna).
2.    Identifique el renglón o columna con la penalización mayor, rompiendo arbitrariamente los empates. Asigne tanto como sea posible a la variable con el costo mínimo en el renglón o columna, si se satisfacen simultáneamente, únicamente uno de ellos se tacha y al renglón (columna) restante se le asigna una oferta (demanda) cero. Cualquier renglón o columna con oferta o demanda cero no deberá ser utilizado al calcular penalizaciones futuras.
3.    Si exactamente un renglón o columna esta sin tachar pare o deténgase. Si únicamente un renglón (columna) con oferta (demanda) positiva permanece sin estar tachada, determine las variables básicas por el método de costo mínimo (asignar tanto como sea posible a la variable con el costo unitario más pequeño). En cualquier otro caso calcule las penalizaciones para los renglones y columnas no tachadas y vaya al paso dos.
Nota: el número de variables básicas tiene que ser m + n – 1

5.4 Procedimiento de optimización

Método del Banquillo (Stepping Stones)
Este método sirve para probar si ya se alcanzó la optimización en el método de transporte. Una vez que se tiene una buena solución al método de transporte usando el MAV, es necesario probar si esta es óptima, cambiando unas unidades a otras rutas, para evaluar cada cuadro abierto (sin número asignado). Siga estos pasos:

  1. Determine una trayectoria cerrada. Empezando con el cuadro abierto a ser evaluado y saltando a otros cuadros cerrados (con asignaciones), hasta regresar al cuadro original abierto. Cada elemento de la esquina de la trayectoria debe ser un cuadro cerrado (con asignaciones).
  2. Empezando con el cuadro abierto a ser evaluado, asigne un signo más (+) alterne signos menos (-) y más (+). A las esquinas (cuadros) de la trayectoria. Es indiferente si el circuito se recorre en el sentido de las manecillas del reloj o en sentido contrario.
  3. Sume los costos por unidad en los cuadros con el signo más (+), reste los costos por unidad en los cuadros con el signo menos (-). Si el resultado es negativo, significa que se puede obtener una disminución de los costos con una nueva asignación.
  4. Si el resultado del punto 3 fue negativo, entonces la variable que sale es aquel cuadro cerrado que tiene el valor más pequeño ya que será la primera que llegue al valor cero y cualquier disminución adicional causará se negatividad. El cuadro deberá tener el signo menos (-).
  5. Cuando la suma de todos los cuadros abiertos sea positiva, entonces se ha llegado a la solución óptima.
Nota: recuerde que el número de variables básicas (cuadros cerrados) debe ser m+n-1.







5.4 Definición del problema de asignación

Considere  la situación de asignar m trabajos o trabajadores a n máquinas. Un trabajo i (i=1, 2, 3…, m) cuando se asigna a la máquina j (j=1, 2, 3,…, n) incurre en un costo Cij. El objetivo es asignar los trabajos a las máquinas (un trabajo por máquina) con el costo mínimo total. Este caso es conocido con el nombre de asignación.

La formulación de este problema puede considerarse como un caso especial del método de transporte. Aquí los trabajos representan “orígenes” y las máquinas representan “destinos”. La oferta disponible en cada fuente es 1. De igual manera la demanda requerida en cada destino es 1. El costo de “transportar” (asignar) el trabajo i a la máquina j es Cij. Si un trabajo no puede asignarse a una cierta máquina, el Cij correspondiente se toma igual a M, es decir, un costo muy alto.


Máquina

Trabajo

1
2
………………
n

1
C11
C12
………………
C1n
1
2
C21
C22
……………….
C2n
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
Cm1
Cm2
……………….
Cmn
1


1
1
……………….
1


Nota: las columnas o renglones ficticios tienen costos M.
Antes de que el modelo pueda resolverse, es necesario balancear primero el problema, añadiendo trabajos ficticios o máquinas ficticias, dependiendo si m<n o m>n. Por consiguiente, se supondrá que m=n. Para resolver el problema de asignación se siguen estos pasos:


Pasos en  el Método de Asignación
1.    Encuadre el elemento mínimo en cada renglón de la matriz. Construya una nueva matriz, restando de cada costo, el costo mínimo de su renglón. Para esta nueva matriz encuentre el costo mínimo en cada columna. Construya una nueva matriz, llamada la matriz de costo reducida, restando de cada costo el costo mínimo en su columna.
2.    Dibuje el mínimo número de líneas, horizontales y verticales que son necesarias para cubrir todos los ceros en la matriz de costo reducida. Si m líneas son requeridas para cubrir todos los ceros, entonces se tiene una solución óptima disponible dentro de los ceros cubiertos en la matriz. Si existen menos de m líneas que cubren todos los ceros entonces proceda al paso 3.
3.    Encuentre el elemento más pequeño diferente a cero (llamado valor k). En la matriz de costo reducida que no está cubierto por las líneas del paso 2. Reste k de cada elemento no cubierto de la matriz de costos reducida y sume k a cada elemento cubierto por 2 líneas de la matriz de costo reducida. Regrese al paso 2.

5 comentarios: