UNIDAD
3: MODELO DE
TRANSPORTE Y ASIGNACION
Definición y aplicación del modelo de transporte. Problemas de transporte o de distribución. Casos
prácticos. Búsqueda de la primera solución. Regla de la esquina noroeste. Costo mínimo. Índices de Vogel. Optimización de la solución básica. Problemas de
asignación. Método Húngaro. Manejo de software específico
Bibliografía
1.
Investigación de
operaciones - Taha, Hamdy - Ed.
Alfaomega - 1991 - 2ª edición
Introducción
Esta
unidad trata con una clase importante de programas lineales llamada el modelo de transporte. En el sentido
obvio, el modelo busca la minimización del costo de transportar una mercadería
desde un número de fuentes a varios destinos. Se conocen el abastecimiento en
cada origen y la demanda en cada destino. Por ejemplo, un producto puede
transportarse de las fábricas (orígenes) a las tiendas.
Aunque
el problema de transporte puede resolverse por método simplex
regular, sus propiedades especiales ofrecen un procedimiento de solución más
conveniente.
El
modelo de transporte
Definición
del modelo
Supongamos
que existen m orígenes y n destinos. Sea ai el número de
unidades disponibles para ofrecerse en cada origen i (i=1,2,...,m) y sea bj el
número de unidades requeridas en el destino j (j=1,2,.,n)
Sea cij el costo de del
transporte por unidad en la ruta (i,j)
que une el origen i con el destino j. El objetivo es determinar el número de
unidades transportadas del origen i la destino j de
manera que minimicen los costos totales de transporte.
Sea
xij
el número de unidades transportadas del origen i al destino j; entonces el
modelo de programación lineal equivalente está dado como:
|
|
sujeto a:
|
|
|
|
|
|
A
fin de apreciarla estructura especial del modelo de transporte consideremos un
ejemplo con dos orígenes ( m=2 ) y tres destinos (n=3). La
tabla del programa lineal asociado al problema se muestra en la Tabla 1. Todos
los elementos que faltan son iguales a cero.
|
Variables del Variables del origen
1 origen 2
Z │ x11 x12 x13 x21 x22 x23 ───────────────────┼─────────────────────────────────────────── Ecuación │ objetivo │ c11 c12 c13 c21 c22 c23 ───────────────────┼─────────────────────────────────────────── Restricciones 0 │ 1
1 1
a1 de
origen 0 │ 1 1 1 a2 ...................│........................................
... Restricciones 0 │ 1 1 b1 de
destino 0 │ 1 1 b2 0 │ 1 1 b3 ───────────────────┴─────────────────────────────────────────── Tabla 1 |
Todos
los coeficientes diferentes de 0 son iguales a +1.
La
forma rectangular de la Tabla 1 no ofrece una solución obvia de inicio. Esta
dificultad se evita presentando el problema de una forma más conveniente. Esta
clase de disposición ( Tabla 2 ) es la que se utiliza
para desarrollar la técnica de transporte.
|
|
|
|
Destino j |
|
|||||
|
|
|
|
1 |
2 |
3 |
Oferta |
|||
|
|
Origen i |
1 |
|
c11 |
|
c12 |
|
c13 |
a1 |
|
|
x11 |
|
x12 |
|
x13 |
|
|||
|
|
2 |
|
c21 |
|
c22 |
|
c23 |
a2 |
|
|
|
x21 |
|
x22 |
|
x23 |
|
|||
|
|
|
Demanda |
b1 |
b2 |
b3 |
|
|||
|
Tabla 2 |
Balanceo
del modelo del transporte
La
definición general del modelo de transporte implica que:
|
|
Esto
significa que la oferta en todos los orígenes debe igualar a la demanda de
todos los destinos. En problemas reales esta restricción no necesita
satisfacerse siempre. En otras palabras la oferta disponible puede ser menor
que la demanda o excederla. En este caso se dice que el modelo no está balanceado.
La restricción
mSi=1 ai = nSj=1 bj se impone únicamente porque es fundamental al
desarrollar la técnica de transporte. Sin embargo cualquier problema real puede
balancearse artificialmente convirtiéndolo
a un problema con igual oferta y demanda.
Si
la demanda excede a la oferta, se aumenta un origen ficticio que suministrará
la cantidad de Sj bj - Si ai. Si existe exceso de oferta se utiliza un
destino ficticio para absorber la cantidad de
Si ai - Sj bj. Los costos de
"transporte" por unidad desde el origen ficticio a todos los destinos
son cero ya que esto es equivalente a no
transportar desde el origen ficticio. En forma semejante, los costos de
"transporte" por unidad desde todas las fuentes a todos los destinos
ficticios son cero. Físicamente las cantidades enviadas desde un origen
ficticio pueden interpretarse como escasez de la demanda, mientras que los
asignados a un destino ficticio pueden interpretarse como capacidades no
utilizadas en el origen.
La
técnica del transporte
Los
pasos básicos de la técnica del transporte son:
Paso 1: Determinar la
solución factible básica de inicio.
Paso 2: Determinar una
variable que entra de las variables no básicas. Si todas de tales variables
satisface la condición de optimidad (del método simplex) parar; de otra manera ,
ir al paso 3.
Paso 3: Determinar una
variable que sale ( usando la condición de
factibilidad ) de entre las variables de la solución básica real; entonces
encontrar la nueva solución básica. Regresar al paso 2.
Para
considerar todos los pasos se utilizará la Tabla 3. El costo de transporte
unitario cij está en unidades monetarias.
La oferta y la demanda están dadas en número de unidades.
Solución
básica inicial
La
definición general del modelo del transporte requiere que mSi=1 ai = nSj=1 bj.
Este requisito resulta en una ecuación dependiente, lo cual significa que el
modelo de transporte tiene únicamente m +
n - 1 ecuaciones independientes. Por consiguiente, como en el método simplex una solución factible básica de inicio debe incluir
m + n - 1 variables básicas.
Normalmente,
si el modelo de transporte se formula como la tabla simplex
mostrada en la Tabla 1, sería necesario utilizar variables artificiales para
asignar una solución básica de inicio. Sin embargo, cuando se usa la tabla de
transporte ( Tabla 2 ), puede obtenerse fácil y
directamente una solución básica inicial (factible).
A
continuación se presentan tres métodos para obtener la solución básica inicial.
Se supone que el modelo de transporte está balanceado.
a - Método de la "esquina
noroeste"
Este
método comienza asignando la cantidad máxima permisible por la oferta y la
demanda a la variable x11 ( la que está en
la esquina noroeste de la tabla ). La columna satisfecha (
fila ) se tacha indicando que las variables restantes de la columna
tachada (fila) son igual a cero. Si una columna y una fila se satisfacen
simultáneamente, únicamente uno ( cualquiera de los dos ) debe tacharse. Después de ajustar
las cantidades de oferta y demanda para todas las filas y columnas no tachados,
la cantidad máxima factible se asigna al primer elemento no tachado de la nueva
columna ( fila ). El procedimiento termina cuando exactamente una fila o una columna se
dejan sin tachar.
El
procedimiento se aplica a la Tabla 3.
|
|
|
|
Destino j |
|
|||||||
|
|
|
|
1 |
2 |
3 |
4 |
Oferta |
||||
|
|
Origen i |
1 |
|
10 |
|
0 |
|
20 |
|
11 |
15 |
|
|
x11 |
|
x12 |
|
x13 |
|
x14 |
|
|||
|
|
2 |
|
12 |
|
7 |
|
9 |
|
20 |
25 |
|
|
|
x21 |
|
x22 |
|
x23 |
|
x24 |
|
|||
|
|
3 |
|
0 |
|
14 |
|
16 |
|
18 |
5 |
|
|
|
x31 |
|
x32 |
|
x33 |
|
x34 |
|
|||
|
|
|
Demanda |
5 |
15 |
15 |
10 |
|
||||
|
Tabla 3 |
x11
= 5, lo cual tacha la columna 1. Por consiguiente ninguna asignación puede
hacerse en dicha columna. La cantidad que queda en la fila 1 es de 10 unidades.
x12 = 10, lo cual tacha la fila 1 y deja 5
unidades en la columna 2.
x22 = 5, lo cual tacha la columna 2 y deja 20
unidades en la fila 2.
x23 = 15, lo cual tacha la columna 3 y deja 5
unidades en la fila 2.
x24 = 5, lo cual tacha la fila 2 y deja 5
unidades en la columna 4.
x34
= 5, lo cual tacha la fila 3 o la columna 4. Ya que únicamente una fila o una
columna permanecen sin tachar, termina así el procedimiento.
La
solución básica inicial resultante se da en la Tabla 4. Las variables básicas son x11 = 5, x12
= 10, x22 = 5, x23 = 15, x24 = 5 y x34
= 5. Las variables restantes son no
básicas a nivel 0.
El
costo del transporte asociado es:
SS xij
cij = 5 * 10 + 10 * 0 + 5 * 7 + 15 * 9 + 5
* 20 + 5 * 18 = $ 410
|
1 2
3 4
┌───┬───┬───┬───┐ 1 │ 5│ 10│ │
│ 15
├───┼───┼───┼───┤ 2 │ │ 5│ 15│ 5│ 25
├───┼───┼───┼───┤ 3 │ │ │ │ 5│
5
└───┴───┴───┴───┘ 5 15 15 10 Tabla 4 |
Cuando tanto una columna
como una fila se satisfacen simultáneamente, la variable siguiente que debe
agregarse a la solución básica
|
1 2
3 4
┌───┬───┬───┬───┐ 1 │ 5│
5│
│ │
├───┼───┼───┼───┤ 2 │ │ 5│
0│ │ 5
├───┼───┼───┼───┤ 3 │
│
│
8│ 7│ 15
└───┴───┴───┴───┘ Tabla 5 |
necesariamente estará en un nivel 0. La Tabla 5
muestra este caso. La columna 2 y la fila 2 se satisfacen simultáneamente. Si
la columna 2 se tacha, x23 se hará básica a nivel 0 en el siguiente
paso, ya que la oferta restante para la fila 2 es 0 ahora (
ver Tabla 5 ). Si en lugar de la columna se tachara la fila 2, x23
sería la variable básica 0.
Las
soluciones de inicio de las Tablas 4 y 5 incluyen el número adecuado de
variables básicas, a saber, n + m - 1 = 6. La regla de la esquina noroeste
siempre proporciona el número apropiado de variables básicas.
b - Método de costo mínimo
El
método de la esquina noroeste no intenta localizar una buena solución de inicio
usando rutas "baratas" en el modelo de transporte. Por ese motivo de
crea el método de costo mínimo.
El
procedimiento es como sigue. Asignar tanto como sea posible a la variable con
el costo unitario más pequeño en la
tabla completa ( los empates se rompen arbitrariamente
). Se tacha la fila o columna satisfecha. Después de ajustar la oferta y la
demanda para todos los elementos no
tachados, se repite el proceso asignando tanto como sea posible a la variable
no tachada con el costo unitario más pequeño. El procedimiento está completo
cuando sólo una fila o una columna está sin tachar.
Utilizando
el ejemplo de la Tabla 3, se obtiene por este método la solución de inicio
resultante. (Tabla 6 )
|
Destino 1 2 3 4
Oferta
┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ │ │
10│ │ 0 │ │
20│ │ 11│ 1 │ └───┤ └───┤ └───┤ └───┤ 15 │ 0
│ 15 │ │ 0
│ ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │
12│ │ 7 │ │ 9
│ │
20│ Origen 2 │ └───┤ └───┤ └───┤ └───┤ 25 │ │ │ 15
│ 10 │ ├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │ 0
│ │
14│ │ 16│ │ 18│ 3 │ └───┤ └───┤ └───┤ └───┤ 5 │ 5
│ │ │ │
└─────────┴─────────┴─────────┴─────────┘
Demanda 5 15 15 10 Tabla 6 |
Los
pasos de la solución son los siguientes: x12 y x31 son
las variables asociadas a los costos unitarios más pequeños(c12=c31= 0)
Rompiendo arbitrariamente el empate,
por ejemplo seleccionamos x12. Las unidades asociadas de oferta y
demanda dan x12 = 15, lo cual satisface tanto la fila 2 como la
columna 2. Tachando la columna 2 la oferta que se deja en la fila 1 es cero.
Ahora x31 tiene el costo unitario más pequeño sin tachar. Por consiguiente
x31 = 5 satisface tanto la fila 3 como la columna 1. Tachando la
fila 3 la demanda en la columna 1 es 0. El elemento más pequeño sin tachar es c23
= 9. Las unidades de oferta y demanda dan x23 = 15, lo cual tacha la
columna 3 y deja 10 unidades de oferta en la fila 2. El elemento más pequeño
sin tachar es c11 = 10. Ya que la oferta restante en la fila 1 y la
demanda que queda en la columna 1 son ambas cero, x11=0. Tachando la
columna 1, la oferta que se deja en la fila 1 es cero. Las variables básicas
restantes se obtienen, respectivamente, como
x14 = 0 y x24 = 10.
El
costo asociado con esta solución es:
SS xij
cij = 0 * 10 + 15 * 0 + 0 * 11 + 15 * 9 +
10 * 20 + 5 * 0= $ 335
que es mejor ( más pequeño ) que el
obtenido por el método de la esquina noroeste.
La
solución básica de la Tabla 6 incluye cuatro variables positivas y dos
variables cero. Esto significa que la solución básica inicial es degenerada, esto es, al menos una
variable básica es igual a cero. La degeneración no presenta problemas
especiales ya que las variables básicas cero pueden tratarse como cualquiera de
las variables básicas positivas.
c - Método de Aproximación de Vogel (MAV)
Este
método es heurístico y usualmente proporciona una mejor solución de inicio que
los dos métodos anteriores. Generalmente el MAV produce una solución de inicio
óptima o cercana a la óptima.
Los
pasos del procedimiento son los siguientes:
Paso
1: Evaluar una penalización para cada fila
( columna ) restando el elemento de costo
más pequeño en la fila (columna) del siguiente
elemento de costo más pequeño en la
misma fila (columna).
Paso
2: Identificar la fila o columna con la
penalización mayor, rompiendo arbitrariamente los empates. Asignar tanto como
sea posible a la variable con el costo mínimo en la fila o columna seleccionados. Ajuste la oferta y la demanda y tache la fila
o la columna satisfechas. Si una fila y una columna se satisfacen
simultáneamente, únicamente uno de ellos se tacha y a la fila ( columna ) restante se le asigna una oferta (demanda) cero.
Cualquier fila o columna con oferta o
demanda cero no deberán ser utilizados al calcular futuras penalizaciones ( en el paso 3 ).
Paso 3: a) Si exactamente una fila o una columna permanece sin tachar; parar.
b) Si únicamente una fila ( columna ) con oferta (demanda) positiva permanece sin estar tachada, determinar las variables
básicas en la fila (columna) por el método de costo mínimo.
c) Si todos las
filas y columnas no tachados tienen oferta y demanda cero, determinar las
variables básicas por el método de costo mínimo. Parar
d) En cualquier caso calcular las
penalizaciones para las filas y columnas no tachadas y después ir al paso 2.
Aplicando
el MAV al problema dado en la Tabla 3 se obtiene la Tabla 7 en la que se
muestra el primer conjunto de penalizaciones de fila y columna.
|
Destino 1 2 3 4
Oferta Pena- ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ lidad │
│ 10│ │ 0 │ │
20│ │ 11│ fila 1 │ └───┤ └───┤ └───┤ └───┤ 15
10 │ │ │ │ │
├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │
12│ │ 7 │ │ 9
│ │
20│ Origen 2 │ └───┤ └───┤ └───┤ └───┤ 25
2 │ │ │ │ │
├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │ 0
│ │
14│ │ 16│ │ 18│ 3 │ └───┤ └───┤ └───┤ └───┤ 5
14 │ 5
│ │ │ │
└─────────┴─────────┴─────────┴─────────┘
Demanda 5 15 15 10 Penalidad de columna 10 7 7 7 Tabla 7 |
Ya
que la fila 3 tiene la penalización mayor ( 14 ) y ya
que c31 = 0 es el costo unitario mínimo en la misma fila, la
cantidad 5 se le asigna a x31. La fila 3 y la columna 1 se
satisfacen simultáneamente. Supongamos que la columna 1 se tacha. La oferta
restante para la fila 3 es 0.
La
Tabla 8 muestra el nuevo conjunto de penalizaciones después de tachar la
columna 1 en la Tabla 7. La fila 1 y la columna 3 tienen las mismas
penalizaciones. Seleccionando arbitrariamente la columna 3, la cantidad 15 se
asigna a x23, se tacha la columna 3 y se ajusta a 10 la oferta en la
fila 2.
Aplicaciones
sucesivas del MAV producen x22 = 10 ( se
tacha la fila 2 ); x12 = 5 ( se tacha la columna 2 ); x14
= 10 ( se tacha la fila 1 ) y x34 = 0.
El
costo del programa es de $ 315, que es el óptimo.
|
¡Error! Marcador no definido. Destino 1 2 3 4
Oferta Pena- ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ lidad │ / │ 10│ │ 0 │ │
20│ │ 11│ fila 1 │ / └───┤ └───┤ └───┤ └───┤ 15
11 │ /
│ │ │ │ ├───/─┬───┼─────┬───┼─────┬───┼─────┬───┤ │ / │ 12│ │ 7 │ │ 9
│ │
20│ Origen 2 │
/ └───┤ └───┤ └───┤ └───┤ │ /
│ │ 15 │ │
├───/─┬───┼─────┬───┼─────┬───┼─────┬───┤ │ / │ 0 │ │
14│ │ 16│ │ 18│ 3 │ / └───┤ └───┤ └───┤ └───┤ │ /5
│ │ │ │
└─────────┴─────────┴─────────┴─────────┘
Demanda Penalidad de columna -- 7 11 9 Tabla 8 |
Existen
otros métodos y criterios para conseguir la solución inicial básica, como por
ejemplo: Columna mínima, Fila mínima y Algoritmo de Russell.
Obtención
de la solución óptima: Método de banquillo (stepping stone)
La
solución inicial puede ser ahora considerada como la asociada con la iteración
actual. La forma de verificar si la solución actual puede mejorarse es examinar
las variables no básicas actuales en busca de mejoras potenciales en el valor
de la función objetivo. Si existe una de tales variables, será la variable que
entra, en cuyo caso una de las variables básicas actuales debe dejar la
solución
( como en el
método simplex ).
A
fin de determinar la variable que entra y la que sale, se identifica un
circuito cerrado para cada variable no básica. El circuito comienza y termina
en la variable no básica designada. Consiste en segmentos horizontales y
verticales sucesivos (conectados)
cuyos puntos extremos deben ser variables básicas, excepto para los dos
segmentos de inicio y de terminación en la variable no básica. La Tabla 9
ilustra un circuito para la variable no básica x31
que da la solución básica de la Tabla 4.
Este circuito puede definirse en función de las variables básicas como:
x31 ® x11 ®
x12 ® x22 ®
x24 ® x34 ®
x31.
Es
indiferente si el circuito se recorre en el sentido horario o en el sentido
contrario. Se observa que
para una solución básica dada sólo un circuito
único puede construirse para cada variable no básica.
El
circuito se utiliza para comprobar si el valor de la función objetivo puede
mejorarse cuando la variable no básica asociada se aumenta sobre su valor
actual de cero. Por ejemplo, en la Tabla 9, si x31 se aumenta en una
unidad, entonces, a fin de mantener la
|
Destino 1 2 3 4
Oferta ┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ │ │
10│ │ 0 │ │
20│ │ 11│ 1 │ └───┤ └───┤ └───┤ └───┤ 15 │ ║5
-
╞═══10 + │ │ │
├───╫─┬───┼───╥─┬───┼─────┬───┼─────┬───┤ │ ║ │ 12│ ║ │ 7 │ │ 9
│ │
20│ Origen 2 │ ║
└───┤
║ └───┤ └───┤ └───┤ 25 │ ║
│ 5 -
╞═══15════╪═══
5 +
│
├───╫─┬───┼─────┬───┼─────┬───┼───╥─┬───┤ │ ║ │ 0 │ │
14│ │ 16│ ║ │ 18│ 3 │ └───┤ └───┤ └───┤ ║
└───┤ 5
│ x31
+ ═╪═════════╪═════════╪══ 5 - │
└─────────┴─────────┴─────────┴─────────┘
Demanda 5 15 15 10 Tabla 9 |
factibilidad de la solución, los elementos en las
esquinas del circuito x31 deben ajustarse de la manera siguiente.
Disminuir x11 en una unidad, aumentar x12 en una unidad,
disminuir x22 en una unidad, aumentar x24 en una unidad y
finalmente disminuir x34 en una unidad. Este procedimiento se resume
con los signos + y ‑ en las esquinas apropiadas de
la Tabla 9. El cambio mantendrá satisfechas las restricciones de oferta y
demanda.
|
Variable no básica Circuito asociado x13 x13
® x12 ® x22
® x23 ®
x13 x14 x14
® x12 ®
x22 ® x24 ®
x14 x21 x21
® x11 ® x12
® x22 ®
x21 x32 x32
® x22 ®
x24 ® x34 ®
x32 x33 x33
® x23 ®
x24 ® x34 ®
x33
|
Considerando
Dc31 el aumento o
disminución neto en costo como resultado de aumentar x31 en una
unidad. Entonces,
Dc31 = c31 ‑
c11 + c12 ‑ c22 + c24 ‑
c34 = 0 ‑ 10 + 0 ‑ 7 + 20 ‑ 18 = ‑ $15
Es
importante aumentar x31 sobre el nivel cero, ya que cada aumento de
una unidad reduce el costo de transporte en $ 15. Haciendo lo mismo para los
otros circuitos se obtienen los siguientes valores: Dc13 = +$18, Dc14 = ‑ $2, Dc21 = ‑ $5, Dc32 = + $9 y Dc33 = + $9. Ya que x31
proporciona la mayor disminución por unidad de costo, se elige como variable
que entra ( como en la condición de optimidad del método simplex ).
La
variable que sale se elige de las variables en las esquinas del circuito, las
cuales disminuirán cuando la variable de entrada x31 aumente sobre
el nivel cero. Estas se indican en la Tabla 9 por las variables designadas con
el signo ‑. De la Tabla 9 x11,
x22 y x34 son las variables básicas que disminuirán
cuando x31 aumente. La variable que sale se elige como aquella que
tiene el valor más pequeño, ya que será la primera que llegue al valor cero y
cualquier disminución adicional causará su negatividad. En este ejemplo, las
tres variables de signo ‑
tienen el mismo valor, en cuyo caso cualquiera de ellas puede elegirse como la
variable que sale. Supongamos que x34 se toma como variable que
sale; entonces el valor de x31 se aumenta en 5 y se ajustan los
valores en las esquinas ( básicas ). La nueva solución
está dada en la Tabla 10. Su nuevo costo es:
SS xij
cij = 0 * 10 + 15 * 0 + 0 * 7 + 15 * 9 +
10 * 20 + 5 * 0 = $ 335
|
Destino 1 2 3 4
Oferta
┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ │ │
10│ │ 0 │ │
20│ │ 11│ 1 │ └───┤ └───┤ └───┤ └───┤ 15 │ 0
│ 15 │ │ │
├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │
12│ │ 7 │ │ 9
│ │
20│ Origen 2 │ └───┤ └───┤ └───┤ └───┤ 25 │ │ 0
│ 15 │
10 │
├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │ 0
│ │
14│ │ 16│ │ 18│ 3 │ └───┤ └───┤ └───┤ └───┤ 5 │ 5
│ │ │ │
└─────────┴─────────┴─────────┴─────────┘ Demanda 5 15 15 10 Tabla 10 |
Este difiere del asociado a la solución
de la Tabla 4 en 410 ‑ 335 = $75, el cual es igual al número de unidades
asignadas a x31 multiplicado por la disminución en costo por
unidad.
La
solución básica en la Tabla 10 es degenerada, ya que las variables básicas x11
y x22 son cero. Sin embargo, la degeneración no necesita
provisiones especiales y las variables básicas iguales a cero se tratan como
cualquier otra variable básica positiva.
Se
verifican las nuevas variables no básicas para ver la posibilidad de mejorar la
solución actual. El procedimiento dado en la Tabla 9, se repite para la Tabla
10, determinando los circuitos y verificando luego la optimidad
para cada variable no básica. Los números en la esquina inferior de cada cuadrado
no básico en la Tabla 11, resumen si un aumento unitario en la variable puede
aumentar el costo total del transporte.
|
Destino 1 2 3 4
Oferta
┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ │ │
10│ │ 0 │ │
20│ │ 11│ 1 │ └───┤
└───┼───┐ └───┼───┐
└───┤
15 │ 0 - ╞═══15 +
│+18│ │-2
│ │ ├────╫┬───┼───╥─┬───┼───┴─┬───┼───┴─┬───┤ │ ║│ 12│ ║ │ 7 │ │ 9
│ │
20│ Origen 2 ├──┐
║└───┤
║ └───┤ └───┤ └───┤ 25 │-5│x21 +═╪═══
0 -
│ 15 │
10 │
├──┴──┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │ 0
│ │
14│ │ 16│ │ 18│ 3 │
└───┼───┐ └───┼───┐
└───┼───┐
└───┤
5 │ 5
│+24│ │+24│
│+15│ │
└─────────┴───┴─────┴───┴─────┴───┴─────┘
Demanda 5
15 15 10 Tabla 11 |
En
la Tabla 11 entra la variable x21 y sale x11 o x22
( se elige arbitrariamente x11 ). La Tabla
12 da la nueva solución básica junto con la evaluación de las variables no
básicas asociadas, la cual muestra que x14 es la variable de entrada
y x24 es variable de salida.
|
Destino 1 2 3 4
Oferta
┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ │ │
10│ │ 0 │ │
20│ │ 11│ 1
├───┐ └───┤
└───┼───┐
└───┼──┐ └───┤ 15 │+5 │ │ 15 -
│+18│═════│-2│x14 +
│
├───┴─┬───┼────╫┬───┼───┴─┬───┼──┴╥─┬───┤ │ │
12│ ║│ 7
│ │
9 │ ║ │ 20│ Origen 2 │ └───┤
║└───┤ └───┤ ║
└───┤
25 │ 0
│ 0 +═╪═══15════╪══
10 - │
├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │ 0
│ │
14│ │ 16│ │ 18│ 3 │
└───┼───┐ └───┼───┐
└───┼───┐
└───┤
5 │ 5
│+19│ │+19│
│+10│ │
└─────────┴───┴─────┴───┴─────┴───┴─────┘
Demanda 5 15 15 10 Tabla 12 |
Cuando
x14 entra a la solución y x24 la deja, resulta la nueva
solución de la Tabla 13. La evaluación de todas las variables no básicas
muestra que la solución es óptima, ya que un aumento en el valor de cualquier
variable no básica sobre su valor actual de cero aumentará los costos totales.
La
solución óptima se resume como sigue: transportar 5 unidades 1 (origen) a 2 ( destino ), 10 unidades de 1 a 4, 10 unidades de 2 a 2, 15
unidades de 2 a 3 y 5 unidades de 3 a 1.
El
costo total de transporte del programa es $ 315.
Existen
otros métodos y criterios para conseguir la solución inicial básica, como por
ejemplo: Método de los multiplicadores, Solución numérica de Houthakker, Primal Dual para el transporte.
|
Destino 1 2 3 4
Oferta
┌─────┬───┬─────┬───┬─────┬───┬─────┬───┐ │ │
10│ │ 0 │ │
20│ │ 11│ 1
├───┐ └───┤
└───┼───┐
└───┤
└───┤ 15 │+5 │ │ 5
│+18│
│ 10 │
├───┴─┬───┼─────┬───┼───┴─┬───┼─────┬───┤ │ │
12│ │ 7 │ │ 9
│ │
20│ Origen 2 │ └───┤ └───┤ └───┤ └───┤ 25 │ 0
│ 10 │
15 │ │
├─────┬───┼─────┬───┼─────┬───┼─────┬───┤ │ │ 0
│ │
14│ │ 16│ │ 18│ 3 │
└───┼───┐ └───┼───┐
└───┼───┐
└───┤
5 │ 5
│+19│ │+19│
│+12│ │ └─────────┴───┴─────┴───┴─────┴───┴─────┘
Demanda 5 15 15 10 Tabla 13 |
El
modelo de asignación
Considerando
la situación de asignar m trabajos
(o trabajadores) a n máquinas. Un
trabajo i (= 1,2,..,m) cuando se asigna a la máquina j (=1,2,..,n) incurre en un costo cij.
El objetivo es asignar los trabajos a las máquinas ( un
trabajo por máquina ) con el costo mínimo total. Este caso es conocido como el
problema de asignación.
La
formulación de este problema puede considerarse como un caso especial del
modelo de transporte. Aquí los trabajos representan "orígenes" y las
máquinas representan "destinos". La oferta disponible en cada fuente
es 1; esto es ai
= 1 para toda i. De igual manera la
demanda requerida en cada destino es 1; esto es bj = 1 para toda j. El costo de
"transportar" ( asignar ) el trabajo i a la máquina j es cij. Si un trabajo no
puede asignarse a una cierta máquina la cij
correspondiente se toma igual a M, un
costo muy alto. La Tabla 14 da una representación general del modelo de
asignación.
|
|
|
|
Máquina |
|
|||
|
|
|
|
1 |
2 |
.... |
n |
|
|
|
Trabajo |
1 |
c11 |
c12 |
.... |
c1n |
1 |
|
|
2 |
c21 |
c22 |
.... |
c2n |
1 |
|
|
|
. |
. |
. |
.... |
. |
. |
|
|
|
m |
cm1 |
cm2 |
.... |
cmn |
1 |
|
|
|
|
|
1 |
1 |
.... |
1 |
|
|
Tabla 14 |
Antes
de que el modelo pueda resolverse por la técnica de transporte, es necesario
balancear primero el problema añadiendo trabajos ficticios o máquinas ficticias
dependiendo de si m < n o m > n. Por consiguiente, se supone
que m=n.
El
modelo de asignación puede expresarse matemáticamente como sigue. Sea
|
|
El
modelo, por consiguiente, está dado como:
|
|
sujeto a
|
|
|
|
|
|
Para
ilustrar el modelo de asignación se utiliza el ejemplo de la Tabla 14 con tres
trabajos y tres máquinas. La solución inicial (usando la regla de la esquina
noroeste) obviamente es degenerada. Este será siempre el caso en el modelo de
asignación independiente del método utilizado para obtener la base de inicio.
La solución continuará como degenerada en cada iteración.
|
|
|
|
Máquina |
|
|||||
|
|
|
|
1 |
2 |
3 |
|
|||
|
|
Trabajo |
1 |
|
5 |
|
7 |
|
9 |
1 |
|
|
1 |
|
x12 |
|
x13 |
|
|||
|
|
2 |
|
14 |
|
10 |
|
12 |
1 |
|
|
|
x21 |
|
1 |
|
x23 |
|
|||
|
|
3 |
|
15 |
|
13 |
|
16 |
1 |
|
|
|
x31 |
|
x32 |
|
1 |
|
|
||
|
|
|
|
1 |
1 |
1 |
|
|||
|
Tabla 15 |
La
estructura especial del modelo de asignación permite el desarrollo de un método
eficiente de solución.
La
solución óptima del modelo de asignación permanece igual si una constante se
suma o se resta a cualquier fila o columna de la matriz de costo. Si pi
y qj
se restan de la fila i y de la columna j, los nuevos elementos del costo serán:
c'ij = cij
- pi - qj
Esto proporciona la nueva función
objetivo
|
|
Ya que
|
|
se obtiene
|
|
Esto demuestra que la minimización de
la función objetivo original Z proporciona la misma solución que la
minimización de Z'.
La
idea anterior indica que si uno puede crear una nueva matriz c'ij con cantidades cero y si estos elementos, o
un subconjunto, constituye una solución factible, entonces esta solución
factible es óptima, ya que el costo no puede ser negativo.
En
la Tabla 15, los elementos cero se crean restando el elemento más pequeño de
cada fila ( columna ) de la fila correspondiente (columna). Si cada uno considera las filas
primero, la nueva matriz c'ij se muestra
en la Tabla 16
Tabla 16 |
La
última matriz puede hacerse para que incluya más ceros restando q3 =
2 de la tercera columna. Esto
proporciona la Tabla 17.
|
Tabla 17 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Los
rectángulos de la Tabla dan la asignación factible ( y
por tanto óptima ) (1,1), (2,3) y (3,2) que cuesta 5 + 12 + 13 = 30. Este costo
es igual a p1 + p2 + p3 + q3.
No
siempre es posible obtener una asignación factible; por consiguiente se
requieren reglas adicionales para encontrar la solución óptima. Esta reglas se ilustran con el ejemplo de la Tabla 18
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
1 |
4 |
6 |
3 |
|
|
|
2 |
9 |
7 |
10 |
9 |
|
|
|
3 |
4 |
5 |
11 |
7 |
|
|
|
4 |
8 |
7 |
8 |
5 |
|
|
Tabla 18 |
Efectuando
los mismos pasos iniciales que en el ejemplo anterior se obtiene la Tabla 19
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
0 |
3 |
2 |
2 |
|
|
|
2 |
2 |
0 |
0 |
2 |
|
|
|
3 |
0 |
1 |
4 |
3 |
|
|
|
4 |
3 |
2 |
0 |
0 |
|
|
Tabla 19 |
Una
asignación factible a los elementos cero no es posible en este caso. El
procedimiento es entonces dibujar un número mínimo de líneas a través de
algunas filas y columnas, de tal manera que todos los ceros se tachen. Esto se
muestra en la Tabla 20.
|
Tabla 20 |
El
paso siguiente es seleccionar el elemento más pequeño que no esté cruzado ( 1 ). Este elemento no tachado y se agrega a todo elemento
en la intersección de dos líneas. Esto proporciona la asignación óptima ( Tabla 21 ) (1,1), (2,3), (3,2) y (4,4). El costo total
correspondiente es 1 + 10 + 5 + 5 = 21
Tabla 21 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Si
la solución óptima no se obtuviera en el caso anterior, el procedimiento se
debe repetir hasta que se logre una asignación factible.
A
este método se lo conoce con el nombre de Método
Húngaro.
También
es posible investigar la asignación que de el máximo de la función económica ( funcional
). En este caso se debe operar de la siguiente manera:
1
- Determinar el costo unitario más elevado de la tabla completa, o sea: c = máx cij.
2
- Restar este costo unitario de todos los elementos de la tabla. O sea, se
forma una una nueva tabla formada con números
negativos o nulos:
c*ij = cij - c
3
- Cambiar los signos de todos los
elementos c*ij, o sea
c**ij = - c*ij = c - cij
Como
el máximo del problema de asignación formado con las cij
corresponde al mínimo de aquel formado con las c**ij; se busca entonces, la solución óptima de la
tabla formada con las c**ij.