el problema del transporte

Contenido

1. INTRODUCCIÓN ..................................................................................................................... 2

2. FORMULACION DEL PROBLEMA ............................................................................................ 2

3. El planteamiento del problema es el siguiente: .................................................................... 3

4. Ejemplo de aplicación ........................................................................................................... 5

5. Métodos para determinar una solución factible básica inicial ............................................. 7

5.1. EL METODO DE LA ESQUINA NOROESTE ........................................................................... 7

5.2. EL METODO DE LA MATRIZ MINIMA ................................................................................. 8

5.3. EL MÉTODO DE VOGEL .................................................................................................... 10

6. SOLUCIÓN ÓPTIMA ............................................................................................................. 12

6.1. Ejemplo de aplicación ..................................................................................................... 12

7. Solución del problema utilizando el software WINQSB ...................................................... 17

8. Consideraciones .................................................................................................................. 19

2 Lic. Araujo Cajamarca, Raul

1. INTRODUCCIÓN

El Problema de Transporte corresponde a un tipo particular de un problema de programación

Lineal. Si bien este tipo de problema puede ser resuelto por el método Simplex, existe un

algoritmo simplificado especial para resolverlo.

Dentro de la Programación Lineal existe una cierta clase de problemas en los cuales se debe

determinar un esquema óptimo del transporte que se origina en los lugares de oferta donde la

existencia de cierta mercadería es conocida, y llega a los lugares de donde se conoce la

cantidad requerida. El coste de cada envío es proporcional a la cantidad transportada y, el

costo total es la suma de los costos individuales.

Este tipo de problemas comenzó a estudiarse en 1939 por L. V. Kantarovich, despertándose

poco interés en ese tiempo pero conforme se fue necesitando su solución resaltó el hecho de

que poseía propiedades matemáticas, que permitían amplificaciones notables en su proceso

de cálculo. La solución de estos problemas son útiles en la agricultura la que necesita

esquemas de transportación para poder colocar en forma óptima su cosecha en el mercado de

consumo, y en la industria, la cual necesita el abastecimiento de materias primas para su

trasformación y posteriormente colocar sus productos manufacturados en el mercado.

Si el método Simplex fuera usado para encontrar la solución de este problema, el

procedimiento de cálculo sería muy ineficiente por tal motivo es deseable un algoritmo

especial para este tipo de problemas.

2. FORMULACION DEL PROBLEMA

El problema de transporte clásico consiste en distribuir cualquier producto desde un grupo de

centros de producción llamados orígenes a un grupo de centros de recepción llamados

destinos de manera que conocidos la cantidad de que se dispone en cada origen, la cantidad

demandad en cada destino y el costo de transportar una unidad de producto de cada origen a

cada destino; se satisfaga la demanda con el costo total mínimo.

Consideremos el caso general de m orígenes y n destinos.

Esquemáticamente se tiene:


1

2

m

1

2

n

.

.

.

.

.

.

Orígenes

(m)

Destinos

(n)

En forma tabular

Destinos

Oferta 1 2 n

Orí

gen

es 1 11C

12C 1nC 1a

2 21C 22C 2nC

2a

m 1mC 2mC mnC ma

Demanda 1b 2b nb

3. El planteamiento del problema es el siguiente:

Existen m orígenes y se supone que en cada origen hay ia unidades disponibles o

almacenadas de determinado producto; siendo 1;2;...;i m . Existen también n destinos y

cada una requiere de jb unidades de este tipo de producto siendo 1;2;...;j n . Los ia se

llaman exigencias por fila, las jb exigencias por columna, todas las exigencias por fila y

columna son positivas puesto que los valores nulos o negativos no tendrían significado físico.

Además se tiene el costo de transporte de una unidad del producto desde el origen i hasta el

destino j que está representado por ijc . Supondremos inicialmente que la cantidad disponible

en los centros de producción iguala a la cantidad requerida en los centros de consumo, esto es:

1 1

m n

i j

i j

a b


(Posteriormente veremos cómo solucionar el problema cuando esta condición no se satisface).

Una solución o programa de transporte queda definido por un conjunto de mxn número ijx

donde:

ijx =Número de unidades a enviar del origen i al destino j .

Escribiendo como una matriz solución.

11 12 1

21 22 2

1 2

n

n

m m mn

x x x

x x xX

x x x

Dado que no hay envíos negativos, supondremos siempre que:

0ijx Para ,i j

La cantidad total enviada por cada origen puede escribirse como:

1

n

ij i

j

x a

, 1;2;...;i m

La cantidad total recibidas por cada destino puede, a su vez describirse como:

1

m

ij j

i

x b

, 1;2;...;j n

De esta manera, la formula analítica del problema del transporte es la siguiente:

Min. 1 1

m n

ij ij

i j

z C x

Sujeto a las condiciones siguientes:

1

n

ij i

j

x a

, 1;2;...;i m y 1;2;...;j n

1

m

ij j

i

x b

, 1;2;...;j n

0ijx Para ,i j


Observe que los coeficientes de las variables de las restricciones todos son unidades y ceros

esto da lugar a una matriz especial y comparando justo con un problema de Programación

Lineal es muy diferente.

Justamente esta característica especial será aprovechada para obtener la solución de una

manera rápida.

No es necesario incluir dentro de estas condiciones, el requisito que ijx sea entera ya que si

ia , jb son enteros, necesariamente ijx resultará entero.

4. Ejemplo de aplicación

MG Autos Company tiene plantas en los Ángeles, Detroit y Nueva Orleans. Sus centros de

distribución principales son Denver y Miami. Las capacidades de las plantas durante el

trimestre próximo son 1000; 1500 y 1200 automóviles. La demanda trimestral en los dos

centros de distribución es de 2300 y 1400 vehículos. En la tabla siguiente se proporciona el

millaje entre las plantas y los centros de distribución.

Distancia entre orígenes y destinos

Plantas Centros de distribución

Denver Miami

Los Ángeles 1000 2690

Detroit 1250 1350

Nueva Orleans 1275 850

La compañía de camiones encargada del transporte de los automóviles cobra 8 centavos por

milla por automóvil. El costo de transporte por automóvil en las diferentes rutas, redondeado

al dólar más cercano, se calcula como se indica en la tabla siguiente:

Costo por milla entre orígenes y destinos

Denver (1) Miami(2)

Los Ángeles(1) 80 215

Detroit (2) 100 108

Nueva Orleans (3) 102 68


El modelo de Programación Lineal en forma tabular es el siguiente:

Costo de envío de cada origen a cada destino

ORIGEN DESTINO

1 2 Oferta

1 80 215 1000

2 100 108 1500

3 102 68 1200

Demanda 2300 1400 3700

Oferte=Demanda=3700

El modelo matemático:

Definición de variables:

ijx : Número de vehículos enviados desde el origen i hasta el destino j

Función objetivo

Min 11 12 21 22 31 3280 215 100 108 102 68z x x x x x x

S.A.

Restricciones de Oferta

11 12 1000x x

21 22 1500x x

31 32 1200x x

Restricciones de Demanda

11 21 31 2300x x x

12 22 32 1400x x x

Restricciones de no negatividad

0ijx 1;2;3i y 1;2j

Balanceado


5. Métodos para determinar una solución factible básica inicial

En los métodos que se describen a continuación varía en el tiempo para determinar la solución

de menos a más. Sin embargo, el tiempo utilizado al obtener una buena solución inicial está

bien empleado ya que permite reducir considerablemente el número total de iteraciones

requeridas para alcanzar una solución óptima.

Los métodos son los siguientes:

1. Método de la esquina noroeste(N-O)

2. Método de la Matriz Mínima

3. Método de Vogel

4. Método de Russell

5.1. EL METODO DE LA ESQUINA NOROESTE

1 2 Oferta

1 1000 80 215 1000 0

2 1300 100 200 108 1500 200 0

3 102 1200 68 1200 0

Demanda 2300 1400 3700

1300

1200

0

0

Por lo tanto la solución básica inicial obtenida se resume en la figura siguiente:

2300

1400

1000

1500

1200

Los Ángeles

Detroit

Nueva Orléans

1000

1300

200

1200

Denver

Miami

El cual se puede dar lectura de la siguiente manera:


Requiere el envío de 1000 automóviles de los Ángeles a Denver

Requiere el envío de 1300 automóviles de Detroit a Denver

Requiere el envío de 200 automóviles de Detroit a Miami y

Requiere el envío de 1200 automóviles de Nueva Orleans

El costo mínimo asociado de transporte es de:

1000(80)+1300(100)+200(108)+1200(68)=313200 dolares.

5.2. EL METODO DE LA MATRIZ MINIMA

1 2 Oferta

1 80 215 1000

2 100

108 1500

3 102 1200 68 1200 0

Demanda 2300 1400 3700

200

1 2 Oferta

1 1000 80 215 1000 0

2

100

108 1500

3 102 1200 68 1200 0

Demanda 2300 1400 3700

1300

200

1 2 Oferta

1 1000 80 215 1000 0

2 1300 100 200 108 1500 200 0

3 102 1200 68 1200 0

Demanda 2300 1400 3700

1300

200

0

0


El menor

El menor

El menor


2300

1400

1000

1500

1200

Los Ángeles

Detroit

Nueva Orléans

1000

1300

200

1200

Denver

Miami







1000(80)+1300(100)+200(108)+1200(68)=313200 dolares.


5.3. EL MÉTODO DE VOGEL

1 2 P* Oferta

1 1000 80 215 135 1000 0

2 100 108 8 1500

3 102 68 34 1200

P* 20 40

Demanda 2300 1400 3700

1300

1 2 P* Oferta

1 1000 80 215 135 1000 0

2 100 108 8 1500

3 102 1200 68 34 1200 0

P* 2 40

Demanda 2300 1400 3700

1300

200

1 2 P* Oferta

1 1000 80 215 135 1000 0

2 1300 100 200 108 8 1500 200 0

3 102 1200 68 34 1200 0

P* NO NO

Demanda 2300 1400 3700

1300

200

0

1. resta de los

dos menores

1. Resta de los

dos menores

2. El mayor P*

3. El menor costo


1 2 P* Oferta

1 1000 80 215 135 1000 0

2 1300 100 200 108 8 1500 200 0

3 102 1200 68 34 1200 0

P* NO NO

Demanda 2300 1400 3700

1300

200

0


2300

1400

1000

1500

1200

Los Ángeles

Detroit

Nueva Orléans

1000

1300

200

1200

Denver

Miami







1000(80)+1300(100)+200(108)+1200(68)=313200 dolares.


6. SOLUCIÓN ÓPTIMA

6.1. Ejemplo de aplicación

Una fábrica de piensos compuestos dispone de tres plantas diferentes de fabricación y cinco

almacenes para la distribución mensual. Las cantidades fabricadas en cada planta son de 100,

200 y 150 t. al mes.

Las cantidades mensuales solicitadas por los almacenes son 160, 70, 120, y 80 t.,

respectivamente. La matriz de costes por unidad de transporte es:

D1 D2 D3 D4 Oferta

O1 8 9 9 5 100

O2 4 5 8 7 200

O3 3 6 5 9 150

Demanda 160 70 120 80

¿Cuál es el costo total mínimo de transportar la demanda solicitada al mes?

Solución:

D1 D2 D3 D4 Oferta

O1 8

9

9

5

100

O2 4

5

8

7

200

O3 3

6

5

9

150

Demanda 160 70 120 80

Costo de envío

Costo de envío


CALCULAMOS: la Solución Básica inicial, utilizando algún método como: N-O, Matriz Mínima,

Vogel o Russell, en este caso utilizaremos el método N-O.

D1 D2 D3 D4 D5 Oferta

O1 100 8

9

9

5

0

100

0

O2 60 4 70 5 70 8

7

0

200

140 70 0

O3 3

6 50 5 80 9 20 0

150

100 20 0

Demanda 160 70 120 80 20 350

60

0

50

0

0

0

0

Se obtiene una solución básica inicial con un costo de: 2,920.00z

Aplicamos el método para obtener la solución óptima, en este caso el método U-V.

D1 D2 D3 D4 D5 Oferta

O1 100 8

9

9

5

0

100

O2 60 4 70 5 70 8

7

0

200

O3 3

6 50 5 80 9 20 0

150

Demanda 160 70 120 80 20 350

Obtenemos las ecuaciones para cada uno de las asignaciones (o donde haya envíos) hechas:

O1+D1=8

02+D1=4 02+D2=5 O2+D3=8

03+D3=5 O3+D4=9 O3+D5=0

CALCULAMOS: Calcular variables "u" y "v"

Artificial


Tenemos 7 ecuaciones y 8 variables, por lo tanto no es posible resolver este sistema, entonces

haremos convenientemente cero a una de las variables y obtendremos los valores de los otros.

HACEMOS 02=0 y obtenemos la siguiente tabla:

D1 4 D2 5 D3 8 D4 12 D5 3 Oferta

O1 100 8 9 9 5 0 100

4

O2 60 4 70 5 70 8 7 0 200

0

O3 3 6 50 5 80 9 20 0 150

-3

Demanda 160 70 120 80 20 350

CALCULAMOS: los coeficientes de costes reducidos ( )ij i jc U V de todos aquellos que “no

tengan envíos”, obteniéndose la siguiente tabla:

D1 4 D2 5 D3 8 D4 12 D5 3 Oferta

O1 100 8

9

9

5

0 100

4

0

-3

-11

-7

O2 60 4 70 5 70 8

7

0 200

0

-5

-3

O3

3

6 50 5 80 9 20 0 150

-3

2

4

Demanda 160 70 120 80 20 350

CALCULAMOS: ciclo de desplazamiento, buscamos el más negativo de los coeficientes de

costes reducidos, en este caso es 11 , lo marcamos con más (+) y balanceamos o bien las filas

o columnas según sea conveniente pero sólo donde haya asignaciones (obtenemos un

polígono cerrado), obteniéndose la siguiente tabla:

O2+D1=4

C. de costes reducidos

5-(4+12)=-11


NOTA: si no hubiese negativos, entonces se habrá llegado a la solución final.

D1 4 D2 5 D3 8 D4 12 D5 3 Oferta

O1 100 8

9

9

5

0 100

4 -

0

-3 + -11

-7

O2 60 4 70 5 70 8

7

0 200

0 +

-

-5

-3

O3

3

6 50 5 80 9 20 0 150

-3

2

4 +

-

Demanda 160 70 120 80 20 350

Todas las filas y columnas deben quedar balaceadas, primero en signos.

BUSCAMOS: Las asignaciones que tienen signo negativo (-) y elegimos el menor en valor

absoluto, entonces elegimos 70, luego aumentamos en 70 las celdas con más (+) y

disminuimos en 70 las celdas con menos (-).

D1 4 D2 5 D3 8 D4 12 D5 3 Oferta

O1 100 8 9 9 5 0 100

4 - 0 -3 + -11 -7

O2 60 4 70 5 70 8 7 0 200

0 + - -5 -3

O3 3 6 50 5 80 9 20 0 150

-3 2 4 + -

Demanda 160 70 120 80 20 350

El más negativo

El menor en

valor absoluto


Obteniéndose la siguiente tabla:

D1 4 D2 5 D3 8 D4 12 D5 3 Oferta

O1 30 8 9 9 70 5 0 100

4 - 0 -3 + -11 -7

O2 130 4 70 5 0 8 7 0 200

0 + - -5 -3

O3 3 6 120 5 10 9 20 0 150

-3 2 4 + -

Demanda 160 70 120 80 20 350

Hasta el momento el valor óptimo de 2,150Z

Teniéndose la nueva tabla listo para aplicar nuevamente la siguiente iteración…….

D1

D2

D3

D4

D5

Oferta

O1 30 8

9

9 70 5

0 100

O2 130 4 70 5

8

7

0

200

O3

3

6 120 5 10 9 20 0

150

Demanda 160 70 120 80 20 350

Que después de 4 iteraciones la solución óptima será: 1,960z


7. Solución del problema utilizando el software WINQSB

Ingresamos al metodo del problema

Ingresamos los datos: costos, demandas y ofertas

Datos ingresados: costos, demandas y ofertas


Configuramos el método para la solución básica inicial

Método de VOGEL, pero utilizamos N-O

Obtenemos la solución básica inicial método N-O


Solución óptima

8. Consideraciones

Degeneración:

Existe degeneración cuando: NUMERO DE SOLUCIONES <NUMERO DE FILAS +COLUMNAS-1

Soluciones=5 Filas+Columnas-1=3+4-1=6

Soluciones: asignaciones determinadas por algún método de solución básica inicia y/o óptima.

No vamos a poder relacionar las ecuaciones, entonces hacemos arbitrariamente una asignación, según nos convenga, pero el valor de dicha asignación debe ser cero. Esto nos indica que puede haber varias formas de asignación pero un mismo valor óptimo. En la tabla siguiente podemos observar justamente este caso:

AGREGAMOS: O3+V1=0, Luego continuamos con los pasos de la solución óptima método U-V

03=0


Hay degeneración: puesto que el número de soluciones (asignaciones) es menor que la suma de filas más columnas menos uno.

Entonces hacemos arbitrariamente una asignación, según nos convenga, pero el valor de dicha asignación debe ser cero. Esto nos indica que puede haber varias formas de asignación pero un mismo valor óptimo.

Y luego continuamos con el proceso que ya conocemos.


Como no hay costos reducidos negativos, hemos encontrado la asignación óptima

13 30x

24 50x

31 30x

32 20x

33 10x

34 40x

290z Unidades monetarias

Education

el problema del transporte