UNIDAD 3: MODELO DE TRANSPORTE Y ASIGNACION

 

Definición y aplicación del modelo de transporte. Problemas de transporte o de distribución. Casos prácticos. Búsqueda de la primera solución. Regla de la esquina  noroeste. Costo mínimo. Índices de Vogel. Optimización de la solución básica. Problemas de asignación. Método Húngaro. Manejo de software específico

 

Bibliografía

 

1.      Investigación de operaciones - Taha, Hamdy - Ed. Alfaomega - 1991 - 2ª edición

 

Introducción

 

          Esta unidad trata con una clase importante de programas lineales llamada el modelo de transporte. En el sentido obvio, el modelo busca la minimización del costo de transportar una mercadería desde un número de fuentes a varios destinos. Se conocen el abastecimiento en cada origen y la demanda en cada destino. Por ejemplo, un producto puede transportarse de las fábricas (orígenes) a las tiendas.

          Aunque el problema de transporte puede resolverse por método simplex regular, sus propiedades especiales ofrecen un procedimiento de solución más conveniente.

 

El modelo de transporte 

 

Definición del modelo

 

          Supongamos que existen m orígenes y n destinos. Sea ai el número de unidades disponibles para ofrecerse en cada origen i (i=1,2,...,­m) y sea bj el número de unidades requeridas en el destino j (j=1,2,.,­n)

Sea cij el costo de del transporte por unidad en la ruta (i,j) que une el origen i con el destino j. El objetivo es determinar el número de unidades transportadas del origen i la destino j de manera que minimicen los costos totales de transporte.

          Sea xij el número de unidades transportadas del origen i al destino j; entonces el modelo de programación lineal equivalente está dado como:

                                                  

1

 

sujeto a:

                                                  

2

 

                                                  

3

 

                                                                     

4

          A fin de apreciarla estructura especial del modelo de transporte consideremos un ejemplo con dos orígenes ( m=2 ) y tres destinos (n=3). La tabla del programa lineal asociado al problema se muestra en la Tabla 1. Todos los elementos que faltan son iguales a cero.

 

                        Variables del        Variables del

                          origen 1             origen 2

                                                               

                 Z │  x11    x12    x13      x21    x22    x23   

───────────────────┼───────────────────────────────────────────

Ecuación                                                  

objetivo             c11    c12    c13      c21    c22    c23    

───────────────────┼───────────────────────────────────────────

Restricciones    0 │   1     1     1                         a1

de origen        0 │                       1     1     1     a2

...................│........................................ ..­.

Restricciones    0 │   1                   1                 b1

de destino       0 │         1                   1           b2

                 0 │                1                   1    b3

───────────────────┴───────────────────────────────────────────

Tabla 1

          Todos los coeficientes diferentes de 0 son iguales a +1.

          La forma rectangular de la Tabla 1 no ofrece una solución obvia de inicio. Esta dificultad se evita presentando el problema de una forma más conveniente. Esta clase de disposición ( Tabla 2 ) es la que se utiliza para desarrollar la técnica de transporte.

 

 

 

 

Destino j

 

 

 

 

1

2

3

Oferta

 

Origen i

1

 

c11

 

c12

 

c13

a1

 

x11

 

x12

 

x13

 

 

2

 

c21

 

c22

 

c23

a2

 

x21

 

x22

 

x23

 

 

 

Demanda

b1

b2

b3

 

 

Tabla 2

 

Balanceo del modelo del transporte

 

          La definición general del modelo de transporte implica que:

 

                                    

5

 

          Esto significa que la oferta en todos los orígenes debe igualar a la demanda de todos los destinos. En problemas reales esta restricción no necesita satisfacerse siempre. En otras palabras la oferta disponible puede ser menor que la demanda o excederla. En este caso se dice que el modelo no está balanceado.

           La restricción  mSi=1 ai = nSj=1 bj se impone únicamente porque es fundamental al desarrollar la técnica de transporte. Sin embargo cualquier problema real puede balancearse artificialmente convirtiéndolo a un problema con igual oferta y demanda.

          Si la demanda excede a la oferta, se aumenta un origen ficticio que suministrará la cantidad de Sj bj - Si ai. Si existe exceso de oferta se utiliza un destino ficticio para absorber la cantidad de

Si ai - Sj bj. Los costos de "transporte" por unidad desde el origen ficticio a todos los destinos son cero 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 todos los destinos ficticios son 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.

  También se pueden asignar costos de penalización ( en lugar de ceros ) para dar idea del grado de

La técnica del transporte

 

Los pasos básicos de la técnica del transporte son:

 

Paso 1: Determinar la solución factible básica de inicio.

Paso 2: Determinar una variable que entra de las variables no básicas. Si todas de tales variables satisface la condición de optimidad (del método simplex) parar; de otra manera , ir al paso 3.

Paso 3: Determinar una variable que sale ( usando la condición de factibilidad ) de entre las variables de la solución básica real; entonces encontrar la nueva solución básica. Regresar al paso 2.

 

          Para considerar todos los pasos se utilizará la Tabla 3. El costo de transporte unitario cij está en unidades monetarias. La oferta y la demanda están dadas en número de unidades.

 

Solución básica inicial

 

          La definición general del modelo del transporte requiere que mSi=1 ai = nSj=1 bj. Este requisito resulta en una ecuación depen­diente, lo cual significa que el modelo de transporte tiene únicamente m + n - 1 ecuaciones independientes. Por consiguiente, como en el método simplex una solución factible básica de inicio debe incluir m + n - 1 variables básicas.

          Normalmente, si el modelo de transporte se formula como la tabla simplex mostrada en la Tabla 1, sería necesario utilizar variables artificiales para asignar una solución básica de inicio. Sin embargo, cuando se usa la tabla de transporte ( Tabla 2 ), puede obtenerse fácil y directamente una solución básica inicial (factible).

          A continuación se presentan tres métodos para obtener la solución básica inicial. Se supone que el modelo de transporte está balanceado.

 

          a - Método de la "esquina noroeste" 

 

          Este método comienza asignando la cantidad máxima permisible por la oferta y la demanda a la variable x11 ( la que está en la esquina noroeste de la tabla ). La columna satisfecha ( fila ) se tacha indicando que las variables restantes de la columna tachada (fila) son igual a cero. Si una columna y una fila se satisfacen simultánea­men­te, únicamente uno ( cualquiera de los dos ) debe tacharse. Después de ajustar las cantidades de oferta y demanda para todas las filas y columnas no tachados, la cantidad máxima factible se asigna al primer elemento no tachado de la nueva columna ( fila ). El procedimiento termina cuando exactamente una fila o una columna se dejan sin tachar.

          El procedimiento se aplica a la Tabla 3.

 

 

 

 

Destino j

 

 

 

 

1

2

3

4

Oferta

 

Origen i

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

 

 

Tabla 3

          x11 = 5, lo cual tacha la columna 1. Por consiguiente ninguna asignación puede hacerse en dicha columna. La cantidad que queda en la fila 1 es de 10 unidades.

          x12 = 10, lo cual tacha la fila 1 y deja 5 unidades en la columna 2.

          x22 = 5, lo cual tacha la columna 2 y deja 20 unidades en la fila 2.

          x23 = 15, lo cual tacha la columna 3 y deja 5 unidades en la fila 2.

          x24 = 5, lo cual tacha la fila 2 y deja 5 unidades en la columna 4.

          x34 = 5, lo cual tacha la fila 3 o la columna 4. Ya que únicamente una fila o una columna permanecen sin tachar, termina así el procedimiento.

 

          La solución básica inicial resultante se da en la Tabla 4. Las variables básicas son x11 = 5, x12 = 10, x22 = 5, x23 = 15, x24 = 5 y x34 = 5. Las variables restantes son no básicas a nivel 0.

          El costo del transporte asociado es:

 

   SS xij cij = 5 * 10 + 10 * 0 + 5 * 7 + 15 * 9 + 5 * 20 + 5 * 18 =  $ 410

 

                  1   2   3   4

                  ┌───┬───┬───┬───┐                   

                1 │  5│ 10│      15                

                  ├───┼───┼───┼───┤                    

                2 │     5│ 15│  5│ 25                

                  ├───┼───┼───┼───┤                   

                3 │           5│  5                

                  └───┴───┴───┴───┘                   

                     5  15  15  10                    

Tabla 4

 

          Cuando tanto una columna como una fila se satisfacen simultánea­mente, la variable siguiente que debe agregarse a la solución básica

 

                  1   2   3   4

                  ┌───┬───┬───┬───┐                    

                1 │  5│  5│      10 5               

                  ├───┼───┼───┼───┤                   

                2 │     5│  0│     5                

                  ├───┼───┼───┼───┤                   

                3 │        8│  7│ 15                

                  └───┴───┴───┴───┘                   

                     5  10   8   7                    

                         5                            

Tabla 5

 

necesariamente estará en un nivel 0. La Tabla 5 muestra este caso. La columna 2 y la fila 2 se satisfacen simultáneamente. Si la columna 2 se tacha, x23 se hará básica a nivel 0 en el siguiente paso, ya que la oferta restante para la fila 2 es 0 ahora ( ver Tabla 5 ). Si en lugar de la columna se tachara la fila 2, x23 sería la variable básica 0.

          Las soluciones de inicio de las Tablas 4 y 5 incluyen el número adecuado de variables básicas, a saber, n + m - 1 = 6. La regla de la esquina noroeste siempre proporciona el número apropiado de variables básicas.

 

          b - Método de costo mínimo

 

          El método de la esquina noroeste no intenta localizar una buena solución de inicio usando rutas "baratas" en el modelo de transporte. Por ese motivo de crea el método de costo mínimo.

          El procedimiento es como sigue. Asignar tanto como sea posible a la variable con el costo unitario más pequeño en la tabla completa ( los empates se rompen arbitrariamente ). Se tacha la fila o columna satisfecha. Después de ajustar la oferta y la demanda para todos los elementos no tachados, se repite el proceso asignando tanto como sea posible a la variable no tachada con el costo unitario más pequeño. El procedimiento está completo cuando sólo una fila o una columna está sin tachar.

          Utilizando el ejemplo de la Tabla 3, se obtiene por este método la solución de inicio resultante. (Tabla 6 )

 

                                 Destino

 

                        1         2         3         4    Oferta

                   ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐

                        10│     │ 0 │     20│     │ 11│

                 1 │     └───┤     └───┤     └───┤     └───┤  15

                       0       15                 0   

                   ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                        12│     │ 7 │     9 │     20│

   Origen        2 │     └───┤     └───┤     └───┤     └───┤  25

                                        15       10   

                   ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                        0 │     14│     │ 16│     │ 18│

                 3 │     └───┤     └───┤     └───┤     └───┤   5

                       5                              

                   └─────────┴─────────┴─────────┴─────────┘

       Demanda         5         15        15        10

 

Tabla 6

 

          Los pasos de la solución son los siguientes: x12 y x31 son las variables asociadas a los costos unitarios más pequeños(c12=c31= 0)

Rompiendo arbitrariamente el empate, por ejemplo seleccionamos x12. Las unidades asociadas de oferta y demanda dan x12 = 15, lo cual satisface tanto la fila 2 como la columna 2. Tachando la columna 2 la oferta que se deja en la fila 1 es cero. Ahora x31 tiene el costo unitario más pequeño sin tachar. Por consiguiente x31 = 5 satisface tanto la fila 3 como la columna 1. Tachando la fila 3 la demanda en la columna 1 es 0. El elemento más pequeño sin tachar es c23 = 9. Las unidades de oferta y demanda dan x23 = 15, lo cual tacha la columna 3 y deja 10 unidades de oferta en la fila 2. El elemento más pequeño sin tachar es c11 = 10. Ya que la oferta restante en la fila 1 y la demanda que queda en la columna 1 son ambas cero, x11=0. Tachando la columna 1, la oferta que se deja en la fila 1 es cero. Las variables básicas restantes se obtienen, respectivamente, como

x14 = 0 y x24 = 10.

 

          El costo asociado con esta solución es:

 

   SS xij cij = 0 * 10 + 15 * 0 + 0 * 11 + 15 * 9 + 10 * 20 + 5 * 0= $ 335

 

que es mejor ( más pequeño ) que el obtenido por el método de la esquina noroeste.

          La solución básica de la Tabla 6 incluye cuatro variables positivas y dos variables cero. Esto significa que la solución básica inicial es degenerada, esto es, al menos una variable básica es igual a cero. La degeneración no presenta problemas especiales ya que las variables básicas cero pueden tratarse como cualquiera de las variables básicas positivas.

 

 

 

 

 

          c - Método de Aproximación de Vogel (MAV)

 

          Este método es heurístico y usualmente proporciona una mejor solución de inicio que los dos métodos anteriores. Generalmente el MAV produce una solución de inicio óptima o cercana a la óptima.

          Los pasos del procedimiento son los siguientes:

 

Paso 1: Evaluar una penalización para cada fila ( columna ) restando el elemento de costo más pequeño en la fila (columna) del siguiente elemento de costo más pequeño en la misma fila (columna).

Paso 2: Identificar la fila o columna con la penalización mayor, rompiendo arbitrariamente los empates. Asignar tanto como sea posible a la variable con el costo mínimo en la fila o columna seleccionados. Ajuste la oferta y la demanda y tache la fila o la columna satisfechas. Si una fila y una columna se satisfacen simultáneamente, únicamente uno de ellos se tacha y a la fila ( columna ) restante se le asigna una oferta (demanda) cero. Cualquier fila o columna con oferta o demanda cero no deberán ser utilizados al calcular futuras penalizaciones ( en el paso 3 ).

Paso 3: a)       Si exactamente una fila o una columna permanece sin tachar; parar.

          b)         Si únicamente una fila ( columna ) con oferta (demanda) positiva permanece sin estar tachada, determinar las variables básicas en la fila (columna) por el método de costo mínimo.

          c)         Si todos las filas y columnas no tachados tienen oferta y demanda cero, determinar las variables básicas por el método de costo mínimo. Parar

          d)         En cualquier caso calcular las penalizaciones para las filas y columnas no tachadas y después ir al paso 2.

 

          Aplicando el MAV al problema dado en la Tabla 3 se obtiene la Tabla 7 en la que se muestra el primer conjunto de penalizaciones de fila y columna.

 

 

                              Destino

                  1         2         3         4    Oferta Pena-        ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐

lidad             10│     │ 0 │     20│     │ 11│

fila       1 │     └───┤     └───┤     └───┤     └───┤  15    10

                                                

             ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                  12│     │ 7 │     9 │     20│

Origen     2 │     └───┤     └───┤     └───┤     └───┤  25     2

                                                

             ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                  0 │     14│     │ 16│     │ 18│

           3 │     └───┤     └───┤     └───┤     └───┤   5    14

                 5                              

             └─────────┴─────────┴─────────┴─────────┘

  Demanda         5         15        15        10

 

Penalidad de

columna          10           7        7          7

Tabla 7

 

          Ya que la fila 3 tiene la penalización mayor ( 14 ) y ya que c31 = 0 es el costo unitario mínimo en la misma fila, la cantidad 5 se le asigna a x31. La fila 3 y la columna 1 se satisfacen simultá­nea­mente. Supongamos que la columna 1 se tacha. La oferta restante para la fila 3 es 0.

          La Tabla 8 muestra el nuevo conjunto de penalizaciones después de tachar la columna 1 en la Tabla 7. La fila 1 y la columna 3 tienen las mismas penalizaciones. Seleccionando arbitrariamente la columna 3, la cantidad 15 se asigna a x23, se tacha la columna 3 y se ajusta a 10 la oferta en la fila 2.

          Aplicaciones sucesivas del MAV producen x22 = 10 ( se tacha la fila 2 ); x12 = 5 ( se tacha la columna 2 ); x14 = 10 ( se tacha la fila 1 ) y x34 = 0.

          El costo del programa es de $ 315, que es el óptimo.

 

¡Error! Marcador no definido.

                            Destino

 

                 1         2         3         4    Oferta  Pena-      ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐       

lidad         / │ 10│     │ 0 │     20│     │ 11│       

fila     1 │   / └───┤     └───┤     └───┤     └───┤  15      11

              /                               

           ├───/─┬───┼─────┬───┼─────┬───┼─────┬───┤

              / │ 12│     │ 7 │     9 │     20│

Origen   2 │   / └───┤     └───┤     └───┤     └───┤  25  10   2

              /                 15            

           ├───/─┬───┼─────┬───┼─────┬───┼─────┬───┤

              / │ 0 │     14│     │ 16│     │ 18│

         3 │   / └───┤     └───┤     └───┤     └───┤   5   0  --

              /5                              

           └─────────┴─────────┴─────────┴─────────┘

Demanda         5         15        15        10

 

Penalidad de

columna        --          7        11         9

Tabla 8

          Existen otros métodos y criterios para conseguir la solución inicial básica, como por ejemplo: Columna mínima, Fila mínima y Algoritmo de Russell.

 

Obtención de la solución óptima: Método de banquillo (stepping stone)

 

          La solución inicial puede ser ahora considerada como la asociada con la iteración actual. La forma de verificar si la solución actual puede mejorarse es examinar las variables no básicas actuales en busca de mejoras potenciales en el valor de la función objetivo. Si existe una de tales variables, será la variable que entra, en cuyo caso una de las variables básicas actuales debe dejar la solución

( como en el método simplex ).

          A fin de determinar la variable que entra y la que sale, se identifica un circuito cerrado para cada variable no básica. El circuito comienza y termina en la variable no básica designada. Consiste en segmentos horizontales y verticales sucesivos (conectados) cuyos puntos extremos deben ser variables básicas, excepto para los dos segmentos de inicio y de terminación en la variable no básica. La Tabla 9 ilustra un circuito para la variable no básica x31

que da la solución básica de la Tabla 4. Este circuito puede definirse en función de las variables básicas como:

 

                      x31 ® x11 ® x12 ® x22 ® x24 ® x34 ® x31.

 

Es indiferente si el circuito se recorre en el sentido horario o en el sentido contrario. Se observa que para una solución básica dada sólo un circuito único puede construirse para cada variable no básica.

          El circuito se utiliza para comprobar si el valor de la función objetivo puede mejorarse cuando la variable no básica asociada se aumenta sobre su valor actual de cero. Por ejemplo, en la Tabla 9, si x31 se aumenta en una unidad, entonces, a fin de mantener la

 

                            Destino

 

                   1         2         3         4    Oferta

             ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐      

                  10│     │ 0 │     20│     │ 11│      

           1 │     └───┤     └───┤     └───┤     └───┤  15  

                ║5  - ╞═══10  +                 

             ├───╫─┬───┼───╥─┬───┼─────┬───┼─────┬───┤

                ║ │ 12│   ║ │ 7 │     9 │     20│

Origen     2 │   ║ └───┤   ║ └───┤     └───┤     └───┤  25  

                         5  - ╞═══15════╪═══ 5  +

             ├───╫─┬───┼─────┬───┼─────┬───┼───╥─┬───┤

                ║ │ 0 │     14│     │ 16│   ║ │ 18│

           3 │     └───┤     └───┤     └───┤   ║ └───┤   5

                x31 + ═╪═════════╪═════════╪══  5  -

             └─────────┴─────────┴─────────┴─────────┘

  Demanda         5         15        15        10

 

Tabla 9

factibilidad de la solución, los elementos en las esquinas del circuito x31 deben ajustarse de la manera siguiente. Disminuir x11 en una unidad, aumentar x12 en una unidad, disminuir x22 en una unidad, aumentar x24 en una unidad y finalmente disminuir x34 en una unidad. Este procedimiento se resume con los signos + y en las esquinas apropiadas de la Tabla 9. El cambio mantendrá satisfechas las restricciones de oferta y demanda.

 

Variable no básica                 Circuito asociado

        x13                      x13 ® x12 ® x22 ® x23 ® x13

       x14                      x14 ® x12 ® x22 ® x24 ® x14

       x21                      x21 ® x11 ® x12 ® x22 ® x21

       x32                      x32 ® x22 ® x24 ® x34 ® x32

       x33                      x33 ® x23 ® x24 ® x34 ® x33

1

          Considerando Dc31 el aumento o disminución neto en costo como resultado de aumentar x31 en una unidad. Entonces,

 

Dc31 = c31 ‑ c11 + c12 ‑ c22 + c24 ‑ c34 = 0 ‑ 10 + 0 ‑ 7 + 20 ‑ 18       = ‑ $15

 

          Es importante aumentar x31 sobre el nivel cero, ya que cada aumento de una unidad reduce el costo de transporte en $ 15. Haciendo lo mismo para los otros circuitos se obtienen los siguientes valores: Dc13 = +$18, Dc14 = ‑ $2, Dc21 = ‑ $5, Dc32 = + $9 y Dc33 = + $9. Ya que x31 proporciona la mayor dis­minución por unidad de costo, se elige como variable que entra ( como en la condición de optimidad del método simplex ).

          La variable que sale se elige de las variables en las esquinas del circuito, las cuales disminuirán cuando la variable de entrada x31 aumente sobre el nivel cero. Estas se indican en la Tabla 9 por las variables designadas con el signo . De la Tabla 9 x11, x22 y x34 son las variables básicas que disminuirán cuando x31 aumente. La variable que sale se elige como aquella que tiene el valor más pequeño, ya que será la primera que llegue al valor cero y cualquier disminución adicional causará su negatividad. En este ejemplo, las tres variables de signo tienen el mismo valor, en cuyo caso cualquiera de ellas puede elegirse como la variable que sale. Supongamos que x34 se toma como variable que sale; entonces el valor de x31 se aumenta en 5 y se ajustan los valores en las esquinas ( básicas ). La nueva solución está dada en la Tabla 10. Su nuevo costo es:

   SS xij cij = 0 * 10 + 15 * 0 + 0 * 7 + 15 * 9 + 10 * 20 + 5 * 0 = $ 335

                       Destino

 

                   1         2         3         4    Oferta

             ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐      

                  10│     │ 0 │     20│     │ 11│      

           1 │     └───┤     └───┤     └───┤     └───┤  15  

                 0       15                     

             ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                  12│     │ 7 │     9 │     20│

Origen     2 │     └───┤     └───┤     └───┤     └───┤  25  

                          0       15       10   

             ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                  0 │     14│     │ 16│     │ 18│

           3 │     └───┤     └───┤     └───┤     └───┤   5  

                 5                              

             └─────────┴─────────┴─────────┴─────────┘

  Demanda         5         15        15        10

Tabla 10

 

 

 

Este difiere del asociado a la solución de la Tabla 4 en 410 ‑ 335 = $75, el cual es igual al número de unidades asignadas a x31 multipli­cado por la disminución en costo por unidad.

          La solución básica en la Tabla 10 es degenerada, ya que las variables básicas x11 y x22 son cero. Sin embargo, la degenera­ción no necesita provisiones especiales y las variables básicas iguales a cero se tratan como cualquier otra variable básica positiva.

          Se verifican las nuevas variables no básicas para ver la posibilidad de mejorar la solución actual. El procedimiento dado en la Tabla 9, se repite para la Tabla 10, determinando los circuitos y verificando luego la optimidad para cada variable no básica. Los números en la esquina inferior de cada cuadrado no básico en la Tabla 11, resumen si un aumento unitario en la variable puede aumentar el costo total del transporte.

 

 

                              Destino

 

                   1         2         3         4    Oferta

             ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐      

                  10│     │ 0 │     20│     │ 11│      

           1 │     └───┤     └───┼───┐ └───┼───┐ └───┤  15  

                 0  - ╞═══15  + │+18│     │-2 │    

             ├────╫┬───┼───╥─┬───┼───┴─┬───┼───┴─┬───┤

                 ║│ 12│   ║ │ 7 │     9 │     20│

Origen     2 ├──┐ ║└───┤   ║ └───┤     └───┤     └───┤  25  

             │-5│x21  +═╪═══ 0  -   15       10   

             ├──┴──┬───┼─────┬───┼─────┬───┼─────┬───┤

                  0 │     14│     │ 16│     │ 18│

           3 │     └───┼───┐ └───┼───┐ └───┼───┐ └───┤   5  

                 5    │+24│     │+24│     │+15│    

             └─────────┴───┴─────┴───┴─────┴───┴─────┘

  Demanda         5         15        15        10

 

Tabla 11

 

          En la Tabla 11 entra la variable x21 y sale x11 o x22 ( se elige arbitrariamente x11 ). La Tabla 12 da la nueva solución básica junto con la evaluación de las variables no básicas asociadas, la cual muestra que x14 es la variable de entrada y x24 es variable de salida.

 

                              Destino

 

                   1         2         3         4    Oferta

             ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐      

                  10│     │ 0 │     20│     │ 11│      

           1 ├───┐ └───┤     └───┼───┐ └───┼──┐  └───┤  15  

             │+5 │        15  - │+18│═════│-2│x14  +

             ├───┴─┬───┼────╫┬───┼───┴─┬───┼──┴╥─┬───┤

                  12│    ║│ 7 │     9 │   ║ │ 20│

Origen     2 │     └───┤    ║└───┤     └───┤   ║ └───┤  25  

                 0        0  +═╪═══15════╪══ 10  -

             ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                  0 │     14│     │ 16│     │ 18│

           3 │     └───┼───┐ └───┼───┐ └───┼───┐ └───┤   5  

                 5    │+19│     │+19│     │+10│    

             └─────────┴───┴─────┴───┴─────┴───┴─────┘

  Demanda         5         15        15        10

Tabla 12

          Cuando x14 entra a la solución y x24 la deja, resulta la nueva solución de la Tabla 13. La evaluación de todas las variables no básicas muestra que la solución es óptima, ya que un aumento en el valor de cualquier variable no básica sobre su valor actual de cero aumentará los costos totales.

          La solución óptima se resume como sigue: transportar 5 unidades 1 (origen) a 2 ( destino ), 10 unidades de 1 a 4, 10 unidades de 2 a 2, 15 unidades de 2 a 3 y 5 unidades de 3 a 1.

          El costo total de transporte del programa es $ 315.

 

          Existen otros métodos y criterios para conseguir la solución inicial básica, como por ejemplo: Método de los multiplicadores, Solución numérica de Houthakker, Primal Dual para el transporte.

 

 

 

 

                              Destino

 

                   1         2         3         4    Oferta

             ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐      

                  10│     │ 0 │     20│     │ 11│      

           1 ├───┐ └───┤     └───┼───┐ └───┤     └───┤  15  

             │+5 │         5    │+18│        10   

             ├───┴─┬───┼─────┬───┼───┴─┬───┼─────┬───┤

                  12│     │ 7 │     9 │     20│

Origen     2 │     └───┤     └───┤     └───┤     └───┤  25  

                 0       10       15            

             ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤

                  0 │     14│     │ 16│     │ 18│

           3 │     └───┼───┐ └───┼───┐ └───┼───┐ └───┤   5  

                 5    │+19│     │+19│     │+12│    

             └─────────┴───┴─────┴───┴─────┴───┴─────┘

  Demanda         5         15        15        10

Tabla 13

 

El modelo de asignación

 

          Considerando la situación de asignar m trabajos (o trabajadores) a n máquinas. Un trabajo i (= 1,2,..,m) cuando se asigna a la máquina j (=1,2,..,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 como el problema de asignación.

          La formulación de este problema puede considerarse como un caso especial del modelo de transporte. Aquí los trabajos representan "orígenes" y las máquinas representan "destinos". La oferta disponi­ble en cada fuente es 1; esto es ai = 1 para toda i. De igual manera la demanda requerida en cada destino es 1; esto es bj = 1 para toda j. 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 la cij correspondiente se toma igual a M, un costo muy alto. La Tabla 14 da una representación general del modelo de asignación.

 

 

 

Máquina

 

 

 

 

1

2

....

n

 

 

Trabajo

1

c11

c12

....

c1n

1

 

2

c21

c22

....

c2n

1

 

.

.

.

....

.

.

 

m

cm1

cm2

....

cmn

1

 

 

 

1

1

....

1

 

 

Tabla 14

 

          Antes de que el modelo pueda resolverse por la técnica de transporte, es necesario balancear primero el problema añadiendo trabajos ficticios o máquinas ficticias dependiendo de si m < n  o  m > n. Por consiguiente, se supone que m=n.

          El modelo de asignación puede expresarse matemáticamente como sigue. Sea

 

                                    

6

 

          El modelo, por consiguiente, está dado como:

 

                                                   

7

 

 

sujeto a

 

                                                   

8

 

                                                   

9

 

                                                                    

10

 

          Para ilustrar el modelo de asignación se utiliza el ejemplo de la Tabla 14 con tres trabajos y tres máquinas. La solución inicial (usando la regla de la esquina noroeste) obviamente es degenerada. Este será siempre el caso en el modelo de asignación independiente del método utilizado para obtener la base de inicio. La solución continuará como degenerada en cada iteración.

 

 

 

 

Máquina

 

 

 

 

1

2

3

 

 

Trabajo

1

 

5

 

7

 

9

1

 

1

 

x12

 

x13

 

 

2

 

14

 

10

 

12

1

 

x21

 

1

 

x23

 

 

3

 

15

 

13

 

16

1

 

x31

 

x32

 

1

 

 

 

 

 

1

1

1

 

 

Tabla 15

          La estructura especial del modelo de asignación permite el desarrollo de un método eficiente de solución.

          La solución óptima del modelo de asignación permanece igual si una constante se suma o se resta a cualquier fila o columna de la matriz de costo. Si pi y qj se restan de la fila i y de la columna j, los nuevos elementos del costo serán:

         

                     c'ij = cij - pi - qj   

 

Esto proporciona la nueva función objetivo

                                

11

 

Ya que

                                                              

12

 

se obtiene

                                                          

13

 

Esto demuestra que la minimización de la función objetivo original Z proporciona la misma solución que la minimización de Z'.

          La idea anterior indica que si uno puede crear una nueva matriz c'ij con cantidades cero y si estos elementos, o un subconjunto, constitu­ye una solución factible, entonces esta solución factible es óptima, ya que el costo no puede ser negativo.

          En la Tabla 15, los elementos cero se crean restando el elemento más pequeño de cada fila ( columna ) de la fila correspondiente  (columna). Si cada uno considera las filas primero, la nueva matriz c'ij se muestra en la Tabla 16

 

 

 

 

1

2

3

 

 

c'ij ║ =

1

0

2

4

p1 = 5

 

2

4

0

2

p2 = 10

 

3

2

0

3

p3 = 13

 

 

 

 

 

 

 

 

Tabla 16

 

          La última matriz puede hacerse para que incluya más ceros restando q3 = 2 de la  tercera columna. Esto proporciona la Tabla 17.

                     

 

 

 

1

2

3

 

 

c'ij ║ =

1

 

 

 

2

2

 

 

0

 

 

 

 

 

2

4

0

 

 

 

 

 

0

 

 

 

 

 

3

2

 

 

 

1

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

Tabla 17

          Los rectángulos de la Tabla dan la asignación factible ( y por tanto óptima ) (1,1), (2,3) y (3,2) que cuesta 5 + 12 + 13 = 30. Este costo es igual a p1 + p2 + p3 + q3.

          No siempre es posible obtener una asignación factible; por consi­guiente se requieren reglas adicionales para encontrar la solución óptima. Esta reglas se ilustran con el ejemplo de la Tabla 18

 

 

1

2

3

4

 

 

1

1

4

6

3

 

 

2

9

7

10

9

 

 

3

4

5

11

7

 

 

4

8

7

8

5

 

 

Tabla 18

          Efectuando los mismos pasos iniciales que en el ejemplo anterior se obtiene la Tabla 19

 

 

 

1

2

3

4

 

 

1

0

3

2

2

 

 

2

2

0

0

2

 

 

3

0

1

4

3

 

 

4

3

2

0

0

 

 

Tabla 19

          Una asignación factible a los elementos cero no es posible en este caso. El procedimiento es entonces dibujar un número mínimo de líneas a través de algunas filas y columnas, de tal manera que todos los ceros se tachen. Esto se muestra en la Tabla 20.

                     

 

1

2

3

4

 

 

1

0

3

2

2

 

2

2

0

0

2

 

 

3

0

1

4

3

 

4

3

2

0

0

 

 

Tabla 20

          El paso siguiente es seleccionar el elemento más pequeño que no esté cruzado ( 1 ). Este elemento no tachado y se agrega a todo elemento en la intersección de dos líneas. Esto proporciona la asignación óptima ( Tabla 21 ) (1,1), (2,3), (3,2) y (4,4). El costo total correspondiente es 1 + 10 + 5 +  5 = 21

 

 

 

1

2

3

4

 

1

 

 

 

2

1

1

 

0

 

 

 

 

 

2

3

0

 

 

 

2

 

0

 

 

 

 

 

3

0

 

 

 

3

2

 

0

 

 

 

 

 

4

4

2

0

 

 

 

 

0

 

 

 

 

 

Tabla 21

          Si la solución óptima no se obtuviera en el caso anterior, el procedimiento se debe repetir hasta que se logre una asignación factible.

          A este método se lo conoce con el nombre de Método Húngaro.

          También es posible investigar la asignación que de el máximo de la función económica ( funcional ). En este caso se debe operar de la siguiente manera:

            1 - Determinar el costo unitario más elevado de la tabla completa, o sea: c = máx cij.

            2 - Restar este costo unitario de todos los elementos de la tabla. O sea, se forma una una nueva tabla formada con números negativos o nulos:

 

                                                c*ij = cij - c

 

            3 -        Cambiar los signos de todos los elementos c*ij, o sea

 

                                              c**ij = - c*ij = c - cij

 

          Como el máximo del problema de asignación formado con las cij corresponde al mínimo de aquel formado con las c**ij; se busca entonces, la solución óptima de la tabla formada con las c**ij.

 

1