A.CanoM. Pgina 1

Transporte

Introduccin

El modelo de transporte es una clase especial de programacin lineal que tiene que ver con

transportar un artculo desde sus fuentes (fbricas) hasta sus destinos (bodegas).

El objetivo es determinar el programa de transporte que minimice el costo del transporte y que

al mismo tiempo satisfaga los lmites de la oferta y la demanda.

En general, se puede ampliar el modelo de transporte a otras reas de operacin, entre otras el

control de inventarios, programacin de empleos y asignacin de personal.

Definicin del modelo de transporte

El problema general se representa en la red de la figura 1.

Hay fuentes y destinos, cada fuente y cada destino representados por un nodo.

Los arcos representan las rutas que enlazan las fuentes y los destinos. El arco que une a

la fuente con el destino conduce dos clases de informacin:

- El costo de transporte por unidad, y

- La cantidad transportada

La cantidad de oferta en la fuente es y la cantidad de demanda en el destino es .

Objetivo del modelo: Determinar las incgnitas que minimice el costo total del

transporte, y que al mismo tiempo satisfagan las restricciones de oferta y demanda.

Figura 1: Representacin del modelo de transporte con nodos y arcos.

Ejemplo 1: MG Auto tiene tres plantas: en Los ngeles, Detrioit y New Orleans; y dos

centros principales de distribucin en Denver y en Miami. Las capacidades de las tres plantas

durante el prximo trimestre sern 1000, 1500 y 2000 autos. Las demandas trimestrales en los

dos centros de distribucin son 2300 y 1400 autos.

La empresa transportista cobra 8 centavos por milla y por auto. El costo de transporte por

auto, en las distintas rutas y redondeado hasta el ms prximo, se calcula como se ve en la

tabla abajo:

El modelo de programacin lineal para el problema sigue los siguientes pasos:

A.CanoM. Pgina 2

Paso 1: La empresa necesita determinar la cantidad a ser transportada de cada fuente u origen

para cada destino.

cantidad a ser transportada de la fuente al destino :

Paso 2: Funcin Objetivo

Objetivo: Minimizar el costo del transporte

Minimizar

Paso 3: Restricciones:

Restricciones de oferta (Fuentes): retiradas = disponibilidades

(Los ngeles)

(Detroit)

(New Orleans)

Restricciones de Demanda (Destinos): transportes = Necesidades

(Denver)

(Miami)

Restricciones adicionales : no negatividad

El Problema de Programacin Lineal es:

Minimizar

sujeto a

(Los ngeles)

(Detroit)

(New Orleans)

(Denver)

(Miami)

Todas las restricciones son ecuaciones, porque el abasto total desde las tres fuente

es igual a la demanda total en los tres destinos

El PPL se puede resolver con el mtodo Smplex. Sin embargo, la estructura especial de las

restricciones permite resolverlos con ms comodidad usando la tabla de transporte

siguiente.

A.CanoM. Pgina 3

La solucin ptima se indica en la figura abajo.

El algoritmo de Transporte se basa en la hiptesis que el modelo est balanceado, y eso

quiere decir que la demanda total es igual a la oferta total. Si el modelo est desbalanceado

siempre se podr aumentar con una fuente ficticia o un destino ficticio para restaurar el

equilibrio o balance.

Ejemplo 2: En el modelo MG, suponer que la capacidad de la planta de Detroit es 1300

automviles (en lugar de 1500). La oferta total es menor que la demanda total

, lo que quiere decir que no ser satisfecha parte de la demanda en Denver y Miami.

Como la demanda es mayor que la oferta se agrega una fuente (planta) ficticia con una

capacidad de 200 automviles para balancear el modelo de transporte. En

este caso, el costo de transporte por unidad, desde la planta ficticia a los dos destinos es cero,

porque no existe esta fbrica.

El costo de transporte por unidad desde la fuente ficticia a los destinos puede asumir tambin

valores positivos. Por ejemplo, para asegurar que Miami recibe toda su demanda, se asignar

un costo (penalizacin) alto de transporte por unidad al elemento cero, desde la fuente ficticia

hasta Miami.

La tabla abajo muestra el modelo balanceado junto con su solucin ptima. Se ve que la

planta ficticia manda 200 automviles a Miami, y eso quiere decir que a Miami le faltan 200

vehculos para satisfacer su demanda de 1400 unidades.

Tambin podemos demostrar el caso en el que la oferta es mayor que la demanda, suponiendo

que en Denver la demanda es de 1900 autos. En este caso se debe agregar un centro de

distribucin ficticio que reciba el exceso de oferta. Tambin, los costos unitarios de

transporte al centro de ficticio de distribucin son cero, a menos que se deseen imponer otras

condiciones.

A.CanoM. Pgina 4

En la tabla abajo se ve el nuevo modelo y su solucin ptima. Esta solucin indica que la

planta de Detroit tendr un sobrante de 400 autos.

El Algoritmo de Transporte

El algoritmo de transporte sigue exactamente los mismo pasos que el mtodo Smplex. Sin

embargo, en lugar de usar la tabla Smplex normal, se aprovecha la ventaja de la estructura

especial del modelo de transporte para organizar los clculos en una forma ms cmoda.

Se debe recordar que el algoritmo especial de transporte fue desarrollado por primera vez

cuando la norma eran los clculos a mano, y se necesitaba soluciones con mtodo

abreviado. Hoy contamos con poderosos programas de cmputo que pueden resolver un

modelo de transporte de cualquier tamao en forma de programacin lineal.

Para facilitar la presentacin de los detalles del algoritmo usaremos el ejemplo numrico que

sigue.

Ejemplo 3: La compaa SunRay Transport transporta grano desde tres silos hasta tres

molinos. La oferta (en camionadas) y la demanda (en camionadas) se resume en el modelo de

transporte de la Tabla 5, junto con los costos unitarios de transporte por camionada en las

distintas rutas. Los costos unitarios de transporte, (que se ven en la esquina superior

derecha o esquina noreste de cada tabla), estn en cientos de $.

En el modelo se busca el programa de transportes entre silos y molinos que tenga costo

mnimo. Eso equivale a determinar la cantidad transportada del silo al molino

.

A.CanoM. Pgina 5

Los pasos del algoritmo de transporte son exactamente iguales a los del algoritmo smplex:

Paso 1. Determinar una solucin bsica factible de inicio y seguir con el paso 2.

Paso 2. Usar la condicin de optimalidad del mtodo smplex para determinar la variable de

entrada entre todas las variables no bsicas. Si se satisface la condicin de optimalidad,

detenerse. En caso contrario seguir en el paso 3.

Paso 3. Usar la condicin de factibilidad del mtodo smplex para determinar la variable de

salida entre todas las variables bsicas en ese momento, y determinar la nueva solucin

bsica. Regresar al paso 2.

Determinacio n de la solucio n de inicio

Un modelo general de transporte con fuentes y destinos tiene ecuaciones de

restriccin, una para cada fuente y cada destino. Sim embargo, como el modelo de transporte

siempre est balanceado (oferta=demanda), una de esas ecuaciones es redundante. Entonces,

el modelo tiene Entonces, el modelo tiene ecuaciones independientes de

restriccin, lo que quiere decir que la solucin bsica de inicio consiste de

variables bsicas. En nuestro ejemplo la solucin de inicio tiene variables

bsicas.

La estructura especial del modelo de trasporte permite asegurar que haya una solucin bsica

no artificial de inicio, obtenida con uno de los tres mtodos siguientes:

1. Mtodo de la esquina noroeste (superior, izquierda)

2. Mtodo del costo mnimo

3. Mtodo de aproximacin de Vogel.

El mtodo de Vogel produce la mejor solucin bsica de inicio, y el de la esquina noroeste

produce la peor.

Me todo de la esquina noroeste

El mtodo comienza en la celda (ruta) de la esquina noroeste, o superior izquierda, de tabla

(variable ).

Paso 1. Asignar todo lo ms que se pueda a la celda seleccionada y ajustar las cantidades

asociadas de oferta y demanda restando la cantidad asignada.

Paso 2. Salir de la fila o la columna cunado se alcance oferta o demanda cero, y tacharlo, para

indicar que no se pueden hacer ms asignaciones a esa fila o columna. Si un fila y columna

dan cero al mismo tiempo, tachar solo uno (la fila o la columna) y dejar una oferta (demanda)

cero en la fila (columna) que no se tach.

Paso 3. Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario,

avanzar a la celda de la derecha si se acaba de tachar una columna, o la de abajo si se tach

una fila. Seguir al paso 1.

Ejemplo 4: Al aplicar al modelo del ejemplo 3 se obtiene la solucin bsica de inicio, en la

tabla 6. Las flechas indican el orden en el que se generan las cantidades asignadas.

A.CanoM. Pgina 6

La solucin bsica de inicio es la siguiente:

El costo del programa correspondiente es

Me todo del costo m nimo

Este mtodo determina una mejor solucin de inicio, porque se concentra en las rutas menos

costosas. Se inicia asignando todo lo posible a la cela que tenga el mnimo costo unitario (los

empates se rompen en forma arbitraria). A continuacin, la fila o la columna ya satisfechos se

tacha, y las cantidades de oferta y demanda se ajustan en consecuencia. Si se satisfacen en

forma simultanea fila y columna al mismo tiempo, slo se tacha uno de los dos, igual que el

mtodo de la esquina noroeste. A continuacin se busca la celda no tachada con el costo

unitario mnimo y se repite el proceso hasta que queda sin tachar exactamente una fila y una

columna.

Ejemplo 4: Se aplica el mtodo al ejemplo 3 de la siguiente manera:

1. La celda (1,2) tiene costo unitario mnimo de toda la tabla (=$2). Lo ms que se puede

transportar por (1,2) es camionadas, y en este caso se satisfacen al mismo

tiempo fila 1 y columna 2. Se tacha en forma arbitraria la columna 2 y se ajusta la

oferta de la fila 1 a cero.

2. La celda (3,1) tiene el mnimo costo unitario sin tachar (=$4). Se asigna , se

tacha la columna 1 porque qued satisfecha y se ajusta la demanda de la fila 3 a

camionadas.

3. Al continuar de este modo, se asignan en forma sucesiva 15 camionadas a la celda

(2,3), 0 camionadas a la celda (1,4), 5 a la celda (3,4) y 10 a la celda (2,4).

La solucin de inicio que resulta se muestra en la Tabla 7. Las flechas indican el orden en que

hacen las asignaciones.

A.CanoM. Pgina 7

La solucin de inicio, formada con 6 variables bsicas, es

El valor objetivo asociado es

La calidad de la solucin de inicio obtenida con costo mnimo es mejor que la del mtodo de

la esquina noroeste.

Me todo de aproximacio n de Vogel

Es una versin mejorada del mtodo del costo mnimo, que en general produce mejores

soluciones de inicio.

Paso 1. Determinar para cada fila (columna) una medida de penalizacin restando el

elemento de costo unitario mnimo en la fila (columna) del elemento con costo unitario

siguiente mnimo de la misma fila (columna).

Paso 2. Identificar la fila o columna con la mayor penalizacin. Romper los empates en forma

arbitraria. Asignar todo lo posible a la variable que tenga el mnimo costo unitario de la fila o

columna seleccionada. Ajustar la oferta y la demanda y tachar la fila o la columna ya

satisfechos. Si se satisfacen una fila y una columna en forma simultnea, slo se tacha uno de

los dos y al que queda se le asigna oferta o demanda cero.

Paso 3.

a) Si queda sin tachar exactamente una fila o columna con cero oferta o demanda,

detenerse.

b) Si queda sin tachar una fila (columna) con oferta (demanda) positiva , determinar las

variables bsicas en la fila (columna) con el mtodo del costo mnimo. Detenerse.

c) Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda

(restante), determinar las variables bsicas cero por el mtodo del costo mnimo.

Detenerse.

d) En cualquier otro caso, seguir en el paso 1.

Ejemplo 5. Apliquemos al ejemplo 3. En la Tabla 8 se calcula el primer conjunto de

penalizaciones.

A.CanoM. Pgina 8

Como la fila 3 tiene la mxima penalizacin (=10) y la celda (3,1) tiene el costo unitario

mnimo de esa fila, se asigna la cantidad 5 a . Queda satisfecha ahora la columna 1 y se

debe tachar. A continuacin se vueleven a calcular nuevas penalizaciones, como se ve en la

Tabla 9.

En la Tabla 9 se ve que la fila 1 tiene la penalizacin mxima (=9). En consecuencia, se

asigna la mxima cantidad posible a la celda (1,2), con lo que se obtiene , y al

mismo tiempo se satisfacen tanto la fila 1 como la columna 2. En forma arbitraria se tacha la

columna 2 y se ajusta a cero la oferta en la fila 1.

Al continuar en la misma forma, la fila 2 produce la penalizacin mxima (=11) y se asigna

, con lo que se tacha la columna 3 y quedan 10 unidades en la fila 2. Slo queda la

columna 4, y tiene 15 unidades de oferta positiva. Al aplicar el mtodo del costo mnimo a esa

columna, se asigna en forma sucesiva , y .

Hay otras soluciones posibles, que dependen de cmo se rompen los empates.

El valor objetivo asociado a esta solucin es

Problemas:

Compare las soluciones de inicio, obtenidas con los mtodos aprendidos, en cada uno de los

modelos siguientes:

A.CanoM. Pgina 9

Ca lculos Iterativos del algoritmo de transporte

Despus de determinar la solucin de inicio (con cualquiera de los mtodos) se usa el

siguiente algoritmo para determinar la solucin ptima:

Paso 1. Usar la condicin de optimalidad smplex para determinar la variable de entrada como

variable no bsica actual que puede mejorar la solucin. Si se satisface la condicin de

optimalidad, detenerse. En caso contrario seguir al paso 2.

Paso 2. Determinar la variable de salida con la condicin de factibilidad smplex. Cambiar la

base y regresar al paso 1.

Los clculos de cambio de base no implican las operaciones familiares de fila que se usan en

el mtodo Simplex. En lugar de ello, la estructura especial del mtodo de transporte nor

permite hacer clculos ms sencillos.

Ejemplo 6. Resolver el modelo de transporte del ejemplo1, comenzando con la solucin de la

esquina noroeste.

La Tabla 10 muestra la solucin de inicio con el mtodo de la esquina noroeste, que se obtuvo

anteriormente

La determinacin de la variable de entrada, entre las variables no bsicas actuales, se hace

calculando los coeficientes no bsicos en la fila z con el mtodo de multiplicadores.

En este mtodo se asocian los multiplicadores y a la fila y la columna de la tabla de

transporte:

En el ejemplo hay 7 variables y 6 ecuaciones que corresponden a las seis variables bsicas.

Para resolver esas ecuaciones con el mtodo de los multiplicadores se necesita:

Igualar, en forma arbitraria,

A continuacin despejar y resolver las variables restantes

Resumiendo, se tienen

A.CanoM. Pgina 10

A continuacin se usan y para evaluar las variables no bsicas, calculando

Los resultados de estas evaluaciones se ven el siguiente tabla:

Como el mtodo de transporte se busca minimizar el costo, la variable de entrada es la que

tiene el coeficiente ms positivo en la fila z. De esta forma, es la variable de entrada.

Los clculos anteriores se se suelen hacer en forma directa sobre la tabla de transporte como

se ve la Figura 11, las evaluaciones estn en la esquina inferior izquierda de cada celda.

Habiendo determinado a como la variable de entrada, se necesita determinar la variable de

salida. Recurdese que si entra en la solucin para volverse bsica, una de las variables

bsicas actuales debe salir como no bsica.

La seleccin de como variable de entrada indica que se quiere transportar por esta ruta,

porque reduce el costo total de transporte. Cul es lo mximo que se puede transportar por la

nueva ruta?. Observe en la tabla 11 que si la ruta (3,1) transporta (es decir ), el valor

mximo de se determina con base en dos condiciones.

1. Los lmites de oferta y los requerimientos de demanda permanecen satisfechos.

2. Los transportes en todas las rutas deben ser no negativos.

Esas dos condiciones determinan el valor mximo de y la variable de salida como sigue:

Primero se forma un ciclo cerrado que comienza y termina en la celda de la variable

de entrada (3,1).

El ciclo consiste slo en segmentos horizontales y verticales conectados (no se

permiten diagonales). Excepto para la celda de la variable de entrada, cada esquina del

ciclo cerrado debe coincidir con una variable bsica.

A.CanoM. Pgina 11

La Tabla 12 muestra el ciclo para .

El valor de es 5, que se presenta cuando tanto como llegan al nivel cero. Como slo

una variable bsica actual debe salir de la solucin bsica, se puede escoger entre o

como variable de salida. En forma arbitraria escogeremos a para que salga de la solucin.

La seleccin de (=5) como variable de entrada y como variable de salida requiere el

ajuste de los valores de las variables bsicas en las esquinas del ciclo cerrado, como se ve en

la tabla 13. En consecuencia el nuevo costo es .

Con la nueva solucin bsica se repite el clculo de los multiplicadores u y v, como se ve en

la Tabla arriba. La variable de entrada es . El ciclo cerrado indica que y que la

variable de salida es .

La nueva solucin se ve en la Tabla abajo, donde el nuevo costo es

Los nuevos son ahora negativos para todas las no bsicas. Por consiguiente,

la solucin de la tabla abajo es ptima.

A.CanoM. Pgina 12

Solucin ptima: