FACULTAD DE INGENIERA CURSO: INVESTIGACIN DE OPERACIONES

1 INSTRUCTOR: DR. RAL HERNNDEZ MOLINAR

III. PROBLEMAS DE ASIGNACIN Y TRANSPORTE

Mtodo del Costo Mnimo para Encontrar una Solucin Factible Bsica

El mtodo de la esquina noroeste no utiliza costos de envo; esto significa que es posible producir una sfb

inicial que tiene un costo de envo muy alto. Por lo tanto, determinar una solucin ptima podra requerir

varias iteraciones. El mtodo de costo mnimo utiliza los costos de envo para producir una sfb que tenga

un menor costo total. Es posible que se requieran pocas iteraciones para hallar la solucin ptima del

problema.

Primero determine las variables con el costo de envo ms pequeo (llamado ). Asigne a su valor

ms grande posible, min{, }. Al igual que en el mtodo de la esquina noroeste, cancele el rengln i

o la columna j y reduzca el suministro o demanda de la columna o rengln no cancelado por el valor de

. Despus, con base en las celdas que no se encuentren en un rengln o columna cancelada, seleccione

la celda con el costo de envo mnimo y repita el procedimiento.

Contine el proceso hasta que haya slo una celda que pueda ser elegida. En este caso cancele tanto el

rengln como la columna de la celda. Recuerde que (con excepcin de la ltima variable) si una variable

satisface tanto una restriccin de suministro como de demanda, slo cancele un rengln o columna, pero

no ambos.

Para ilustrar el mtodo de costo mnimo, determine una sfb para el problema de transporte equilibrado

de la Tabla 1. La variable con el costo de envo mnimo es 22. Sea 22 = min{10, 8} = 8. Se cancela la

columna 2 y se reduce 2 a 10-8 = 2 (TABLA 2). Se podra elegir 11 o 21 (ambas con costos de envo igual

2).

FACULTAD DE INGENIERA CURSO: INVESTIGACIN DE OPERACIONES

2 INSTRUCTOR: DR. RAL HERNNDEZ MOLINAR

Se elige de manera arbitraria 21 y se hace 21 = {2, 12} = 2. Se cancela el rengln 2 y se cambia 1

a 12 2 = 10 (TABLA 3). Ahora se considera 11 y se selecciona 11 = {5, 10} = 5. Se cancela el

rengln 1 y se cambia 1= 10 - 5 = 5 (TABLA 4). El costo mnimo que no se encuentra en el rengln

eliminado, o columna, es 31. Sea 31 = {15, 5} = 5, se cancela la columna 1 y se reduce 3 a 15 5

= 10 (TABLA 5).

TABLA 1

2 3 5 6

2 1 3 5

3 8 4 6

5

10

15

12 8 4 6

TABLA 2

2 3 5 6

2 1 3 5

3 8 4 6

5

2

15

12 X 4 6

8

FACULTAD DE INGENIERA CURSO: INVESTIGACIN DE OPERACIONES

3 INSTRUCTOR: DR. RAL HERNNDEZ MOLINAR

TABLA 3

2 3 5 6

2 1 3 5

3 8 4 6

10 X 4 6

5

x2 8

15

TABLA 4

2 3 5 6

2 1 3 5

3 8 4 6

5 X 4 6

x5

x2 8

15

FACULTAD DE INGENIERA CURSO: INVESTIGACIN DE OPERACIONES

4 INSTRUCTOR: DR. RAL HERNNDEZ MOLINAR

Ahora, sea 33 = {10, 4} = 4, se cancela la columna 3 y se reduce 3 a 10 4 = 6 (TABLA 6). La nica

celda que se puede elegir es 34. Sea 34 = {6, 6} y cancele el rengln 3 y la columna 4.

Ahora ya se tiene la sfb:

11 = 5 21 = 2 22 = 8 31 = 5 33 = 4 34 = 6

A continuacin se muestran los resultados empleando Excel; la Tabla 7 muestra los resultados empleando

el mtodo de costo mnimo, y la Tabla 8 muestra los resultados utilizando la solucin ptima de SOLVER.

TABLA 5

2 3 5 6

2 1 3 5

3 8 4 6

X X 4 6

105

x2 8

x5

2 3 5 6

2 1 3 5

3 8 4 6

X X X 6

TABLA 6

65 4

x2 8

x5

FACULTAD DE INGENIERA CURSO: INVESTIGACIN DE OPERACIONES

5 INSTRUCTOR: DR. RAL HERNNDEZ MOLINAR

TABLA 7: SOLUCIN CASO MTODO COSTO MNIMO

COSTOS

89

A B C D

1 2 3 5 6

2 2 1 3 5

3 3 8 4 6

ENVOS

A B C D

1 5 0 0 0 5 < 5

2 2 8 0 0 10 < 10

3 5 0 4 6 15 < 15

RECIBIDO 12 8 4 6

> > > >

DEMANDAS 12 8 4 6

SUMINISTRO

COSTOSSOLUCIN SFB EMPLEANDO: MTODO COSTO MNIMO

CIUDAD

CIUDADENVIADO

TABLA 8: SOLUCIN PTIMA. CASO MTODO COSTO MNIMO

COSTOS

89

A B C D

1 2 3 5 6

2 2 1 3 5

3 3 8 4 6

ENVOS

A B C D

1 5 0 0 0 5 < 5

2 0 8 0 2 10 < 10

3 7 0 4 4 15 < 15

RECIBIDO 12 8 4 6

> > > >

DEMANDAS 12 8 4 6

SUMINISTROENVIADO

SOLUCIN PTIMA PARA: MTODO COSTO

MNIMOCOSTOS

CIUDAD

CIUDAD