métodos de transporte


MÉTODO DE TRANSPORTE
PROFESOR: Manuel Letzkus P.
El algoritmo de transporte:
Es un algoritmo simplex especializado, donde la demanda requerida y la oferta disponible se presenta en una matriz rectangular , formando casillas donde son colocados en la esquina superior derecha costos de transporte entre los puntos de oferta y demanda, como lo muestra el tableau de la figura:

Fig N°1:Algoritmo de Transporte



DESTINOS



1
2

n
OFERTA
ui


ORIGENES
1

c11

c12



c1n
S1
u1














2


c21

c22



c2n
S2
u2














m


cm1

cm1



cmn
Sm
um












DEMANDA
d1
d2

dn

vJ
v1
v2

vn


Donde ui y vJ son variables duales.

Adicionalmente se agrega en cadacelda:

i) Si XiJ es una variable básica


ciJ

xiJ




ii) Si XiJ es una variable no básica


ciJ

(cIj-ui-vJ)




Para desarrollar el algoritmo se debe recurrir a los siguientes pasos (Bronson ,68)

1) Encontrar una solución básica inicial
2) Probar la solución para determinar si es óptimo
3) Mejorar la solución cuando no es óptima y
4) Repetir los pasos ( 2) y (3)hasta que se obtenga la solución óptima.


Solución básica inicial


El objetivo de este paso es obtener una solución inicial básica factible para lo cual se han desarrollado varios métodos para obtener estas soluciones iniciales dentro de los cuales se tiene:



DESTINOS



1
2

n
OFERTA
ui


ORIGENES
1

c11

c12



c1n
S1
u1














2c21

c22



c2n
S2
u2














m


cm1

cm1



cmn
Sm
um












DEMANDA
d1
d2

dn

vJ
v1
v2

vn


Esquina Noroeste (NO).
Aproximación de Vogel (MAV).
Costo Mínimo.





1. Método Esquina Noroeste (NO)

La asignación inicial con este método se obtiene siguiendo los siguientes pasos:

a) Se asignan tantas yunidades (x11) como sea posible en la casilla de la esquina NO (1,1) de la matriz del algoritmo de transporte. Este será el menor valor de S1 y de d1.
b) Se continúa moviendo una celdilla hacia la derecha si queda algún suministro, asignando unidades sin ir en contra de las restricciones; sino, una celdilla hacia abajo.
c) Se continúa hacia debajo de la esquina NO, hasta que la oferta total haya sidoasignada a la demanda.
d) Las asignaciones son revisadas para verificar que todas las condiciones de oferta y demanda estén satisfechas. Asimismo, el número de asignaciones debe satisfacer el requerimiento m+n-1 (renglones más columnas menos uno); además, ninguna asignación puede ser negativa, como también una asignación puede ser cero.


Ejemplo: Dada la siguiente tabla de costos yrequerimiento de un problema de transporte, la solución básica inicial utilizando el método NO es la que se muestra en la figura N°2.



DESTINOS

ORIGEN
1
2
3
OFERTA
1
90
100
130
20
2
100
140
100
15
3
100
80
90
10
DEMANDA
5
20
20









Fig N°2: Solución básica inicial mediante el método NO


DESTINOS


1
2
3
OFERTA


ORIGENES
1

90100

130
20



5

15





2


100

140

100
15





5

10



3


100

80

90
10







10

DEMANDA
5
20
20
45


1. Método de Vogel

La solución inicial básica, usando este método se obtiene siguiendo los siguientes pasos (Monks, 68).

a) Calcular la diferencia entre los dos costos más pequeños en cada renglón y cada columna(escribir los resultados a la derecha/debajo de cada renglón o columna).
b) Seleccionar el renglón o columna que tenga diferencias de costo más grande (en caso de empate, usar el renglón o columna que tenga la casilla de costo más bajo) y asignar tantas unidades como sea posible en la casilla de costo más bajo.
c) Eliminar para consideraciones posteriores a las casillas (o cruzarlas con una x)...