Agua Dulce

: Desarrollar la solución optima.

El desarrollo de una solución optima para el problema de transporte implica evaluar

cada celda no utilizada para determinar sin un cambio en ella resulta ventajoso desde el

punto de vista del costo total. So lo es, se hace el cambio, y se repite el proceso. Cuando

todas las celdas han sido evaluadas y se han hecho los cambios pertinentes, el problema

esta resuelto. Este procedimiento se conoce con el nombre de Método “Stepping Stone”.

Ahora se aplicaran estos conceptos a la solución encontrada con el método de la esquina

noroccidental.

Paso 1: Seleccionar cualquier celda vacía e identificar el camino cerrado que conduce a

ella. Un camino cerrado consiste en líneas horizontales y verticales que conducen de una

celda vacía de regreso a si misma. Se debe avanzar hasta una casilla llena (con asignación)

y girar ahí en ángulo recto hasta llegar a otra casilla llena. Así, sucesivamente hasta cerrar

el camino en la casilla vacía de partida. Se pueden saltar las casillas llenas o vacías

necesarias. Por ejemplo: para evaluar la celda B-E, el camino cerrado seria B-E, A-E, E-F,

F-B, que es el indicado con línea punteada en la figura 12.

Desde/Hasta E F G H Oferta

A

10

25

5

35 36 60 15

B 55

6

30 45 38 6

C 40

1

50

13

26 65 14

D 60 40

2

66

9

27 11

Requerimientos de

destino (Demandas)

10 12 15 9

Figura 12. Método “Stepping Stone”. Identificación de caminos cerrados

• Cual será el camino cerrado para evaluar la celda A-H?

35Cátedra: Producción I

Capítulo 7. Programación lineal. Problemas de transporte y asignación

Paso 2: Mover una unidad a una celda vacía desde una llena en una esquina del camino

cerrado, modificando las celdas llenas restantes en las otras esquinas del camino cerrado

para reflejar este movimiento. La modificación implica sumar a y restar de celdas llenas de

tal manera que no se violen las restricciones de oferta y demanda. Esto exige que una

unidad sea restada en una fila o columna dada por cada unidad sumada a dicha fila o

columna. Para la celda B-E implica: Sumar una unidad a B-E (celda vacía), restar una

unidad de B-F, sumar una unidad a A-F, restar una unidad de A-E.

Paso 3: Determinar la conveniencia del cambio. Esto se logra fácilmente al (1) sumar los

valores de costo para cada celda a la cual se ha agregado una unidad, (2) sumar los valores

de costo de las celdas de las cuales se ha restado una unidad, y (3) tomar la diferencia entre

las dos sumas para determinar si existe reducción de costos. Si el costo se reduce al hacer el

cambio, deben cambiarse cuantas unidades sea posible de las celdas llenas a las vacías. Si

el costo se incrementa, no debe hacerse ningún cambio y la celda vacía se debe tachar o

marcar de alguna manera para indicar que ha sido evaluada (por lo general se utiliza un

signo + para indicar que ha sido evaluada y se le ha hallado indeseable en problemas de

minimizacion de costos). En problemas de maximizacion de utilidades se utiliza un signo

menos para este propósito. Para la celda B-E entonces,

Celdas que se ha agregado una unidad: (+)

(B-E) = $ 55

(A-F) = $ 35

Celdas que se ha restado una unidad: (-)

(B-F) = $ 30

(A-E) = $ 25

Total = $35

Así, se puede ver que no se debe hacer el cambio, dado que no hay reducción de costo.

Paso 4: Repetir los pasos 1 a 3 hasta que hayan sido evaluadas

...