Algoritmo de transporte

Programación lineal Transporte Algoritmo del transporte Existen dentro de la programación lineal algoritmos que muchos autores llaman modelos de distribución y son, el algoritmo de transporte y el de asignación. Es importante mencionar que estos algoritmos de distribución forman parte de la programación lineal y que los procedimientos que se desarrollaran se pueden resolver por medio delalgoritmo que se vio en el capitulo anterior. El algoritmo del transporte tiene como base colocar varios destinos, y los recursos colocados en varios orígenes, de tal forma que la distribución sea óptima (maximizar, minimizar). Matemáticamente, el algoritmo consiste en la siguiente función objetivo y restricciones:
m n

Z
i 1 j 1

Cij xij

Sujeto a:
n

xij
j 1
m

ai Para i 1,2,3,...,m
b jPara j 1,2,3,...,n
n

xij
i 1

Condición necesaria y suficiente:
m

ai
i 1 j 1

bj

Condición de no negatividad: xij 0 Donde el x ij es la cantidad que se asigna desde el origen i hasta el destino j y el C ij es el costo o ganancia de asignar una unidad desde el origen i hasta el destino j. los valores de a i es la cantidad disponible en cada origen, y los valores de b j son lascantidades que se requieren en cada destino, a ambos conceptos de a. y.b se le llaman requerimiento de contorno. A la tabla siguiente le llamamos matriz de transporte: Destinos . j
C12
C1 j x1 j

Suministros .
x1n
C2 j

Origen 1
x11

1 C11
x12
C 21
x 21

2

n
C1n

a1

2

C 22

C 2n
x2n

a2

x 22

x2 j

. i
x i1

C i1 xi 2 C m1
x m1 xm 2

Ci 2
x ij

C ijC i, j

. ai . am

x in
C mj

. m Reqto.
b1

Cm2
x mj

C mn
x mn

b2

.

bj

.

bn

bj

ai

1

Programación lineal Transporte Método de la esquina noroeste (caso minimización) Cuatro zonas habitacionales (en construcción) A, B, C, D requieren de 50,000, 40,000, 60,000 y 40,000 metros cúbicos de concreto respectivamente. Es posible satisfacer esta demanda a partirde de tres concreteras 1, 2 y 3 que disponen de 80,000, 100,000 y 40,000 metros cúbicos de concreto los costos de despachar (transportar) 1000 metros cúbicos se muestran en la siguiente tabla. A B C 1 700 600 600 2 500 800 600 3 800 500 800 D 600 700 600

Determine la cantidad de concreto que debe enviarse de cada dosificadora a cada unidad habitacional de manera que se satisfagan losrequerimientos a un costo mínimo. Método de la esquina noroeste (caso maximización) El primer paso que se debe hacer para obtener la solución de un problema de transporte, es establecer la matriz y realizar la distribución inicial a partir de la esquina superior izquierda de la matriz que se muestra en seguida (recuerde que no se puede violar el contorno). Es importante recalcar que se tuvo la necesidad deaumentar una columna ficticia debido a que la cantidad de recursos disponibles es superior a los requerimientos de las unidades habitacionales. dosificadora 1 50 2 3 Requerimiento 500 10 800 50 500 40 A 700 30 800 60 800 10 60 40 600 30 60 40 40 0 50 700 0 100 Unidad habitacional B C D 600 600 600 suministro Fict. 0 80

Prueba de degeneración: Después de cada asignación en la matriz de transportese debe realizar las pruebas de degeneración. Cuando el número de casillas que tienen asignación es menor a m n 1, (donde m es el número de filas, n número de columnas), se dice que la matriz de transporte es degenerada. Esta matriz de transporte tiene 7 casillas asignadas (números de color rojo). Por lo tanto esta propuesta de solución no es degenerada. Prueba para determinar si la matriz esoptima Pasos para determinar si es optima o no: 1) Formar una matriz que contenga los costos asociados (con la matriz de transporte) con las casillas en las cuales se han hecho asignaciones

2

Programación lineal Transporte
ui
vj

700

600 800 600 700 600 0

2) Utilizando esta última matriz. Establecer un conjunto de número u i la suma sea iguala los costos obtenidos en el paso 1. u i...