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:
- 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).
- 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.
- 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.
- 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 (-).
- 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.
muy bueno amigo gracias :D
ResponderEliminarexcelente!!
ResponderEliminarRecomendación: Agregar ejemplos.
gracias por tu aporte me sirvió de mucho, ahora buscar los ejemplos gracias de nuevo
ResponderEliminarMuy buen aporte, explícito.
ResponderEliminarMuy buen aporte, explícito.
ResponderEliminar