Asigacion Y Transporte

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.

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.

A. MODELO DEL COSTO MINIMO

Asígnese el más grande valor posible a la variable con el menor costo unitario de toda la tabla. Táchese el renglón o columna satisfecha. Después de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repítase el proceso asignando el valor más grande posible a la variable con el costo unitario no tachado más pequeño. El procedimiento esta completo cuando queda exactamente un renglón o bien una columna sin tachar.

1 2 3 4

1 10 0 20 11 15

0 15 0

2 12 7 9 20 25

15 10

3 0 14 16 18 5

5

5 15 15 10

Determinación general del modelo de transporte requiere que:

m n

å ai = å bj

i=1 j = 1

Este requisito da origen a una ecuación dependiente, lo que significa que el modelo de transporte tiene sólo m + n –1 ecuaciones independientes. Por lo tanto, como en el método simplex, una solución factible básica inicial debe incluir m + n – 1 variables básicas.

Normalmente, si el modelo de transporte se formula como una tabla simplex, sería necesario utilizar variables artificiales para asegurar una solución básica inicial. Sin embargo, cuando se utiliza la tabla de transporte, una solución factible básica inicial se puede obtener fácil y directamente. Presentamos un procedimiento llamado regla de la esquina noroeste para este fin.

Destino

1 2 3 4 Oferta

Fuente 1 10 0 20 11 15

X11 X12 X13 X14

2 12 7 9 20 25

X21 X22 X23 X24

3 0 14 16 18 5

X31 X32 X33 X34

Demanda 5 15 15 10

B. MODELO DE LA ESQUINA NOROESTE

El método de la esquina noroeste comienza con la asignación de la máxima cantidad admisible a través de la oferta y la demanda de la variable x11 (la de la esquina noroeste de la tabla). Después se tacha la columna (renglón) satisfecha, lo que indica que las variables restantes de la columna (renglón) tachada son iguales a cero. Si se satisfacen una columna y un renglón al mismo tiempo, sólo una (una u otro) puede ser tachada. (Esta condición garantiza la ubicación automática de variables básicas cero, si las hay). Después de ajustar las cantidades de oferta y demanda de todos los renglones y columnas no tachados, la cantidad factible máxima se asigna al primer elemento no tachado de la nueva columna (renglón). El proceso se completa cuando se deja sin tachar exactamente un renglón o una columna.

El procedimiento que se acaba de describir se aplica ahora en el ejemplo:

1. x11 = 5, se tacha la columna 1. Por lo tanto, no se puede hacer otra asignación en la columna 1. La cantidad que falta en el

...