Investigación de Operaciones
Semana 06
Transporte : Sistema ENO, Vogel y Russell
El modelo de transporte es
una clase especial de
programación lineal que
tiene que ver con transportar
un artículo desde sus fuentes
(es decir, fábricas) hasta sus
destinos (es decir, bodegas).
El objetivo es determinar el
programa de transporte que
minimice el costo total del
transporte y que al mismo
tiempo satisfaga los límites
de la oferta y la demanda
EL ALGORITMO DE TRANSPORTE
El algoritmo de transporte sigue exactamente los mismos pasos que el método símplex. Sin embargo, en lugar de usar
la tabla símplex normal, se aprovecha la ventaja de la estructura especial del modelo de transporte para organizar los
cálculos en una forma más cómoda.
Ejemplo:
La compañía SunRay Transport transporta
grano desde tres silos hasta tres
molinos. La oferta (en camionadas) y la
demanda (también en camionadas) se
resume en el modelo de transporte de la
tabla siguiente, junto con los costos
unitarios de transporte por camionada
en las distintas rutas. Los costos
unitarios de transporte, cij (que se ven
en la esquina superior derecha o
“esquina noreste” de cada tabla), están
en cientos de $.
Determinación de la solución de inicio
Método de la esquina noroeste
Método del costo mínimo
Método de aproximación de Vogel.
Determinación de la solución óptima
Solución de inicio con el método de la esquina noroeste
La determinación de la variable de entrada, entre las
variables no básicas actuales (las que no forman parte
de la solución básica de inicio) se hace calculando los
coeficientes no básicos en el renglón z con el método
de los multiplicadores. En este método se asocian los
multiplicadores ui y vi al renglón i y la columna j de la
tabla de transporte
Para resolver esas ecuaciones con el método de los multiplicadores se necesita igualar, en forma arbitraria, ui 0 y
a continuación despejar y resolver las variables restantes como se ve a continuación.
Como en el modelo de transporte se busca minimizar el costo, la variable de entrada es la que tiene el coeficiente más
positivo en el renglón de z. De esta forma, x31 es la variable de entrada.
Habiendo determinado a x31 como la variable de entrada, se necesita determinar la variable de salida. Recuérdese que
si x31 entra a la solución para volverse básica, una de las variables básicas actuales debe salir como no básica (a nivel
cero). La selección de x31 como variable de entrada indica que se quiere transportar por esta ruta, porque reduce el
costo total de transporte. ¿Cuál es lo máximo que se puede transportar por la nueva ruta? Obsérvese en la tabla
anterior que si la ruta (3, 1) transporta (es decir, x31 ), el valor máximo de se determina con base en dos condiciones.
1. Los límites 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 máximo 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 sólo 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 básica. La tabla siguiente muestra el ciclo para x31.
Existe exactamente un ciclo para determinada variable de entrada.
A continuación se asigna la cantidad a la celda de la variable de entrada (3, 1). Para
que se sigan satisfaciendo los límites de oferta y demanda, se debe alternar entre restar
y sumar la cantidad en las esquinas sucesivas del ciclo, como se ve en la tabla adjunta
(no importa si el circuito se recorre en dirección de las manecillas del reloj, o la
contraria). Los nuevos valores de las variables siguen siendo no negativos si
El valor máximo de es 5, que se presenta cuando tanto x11 como x22 llegan al nivel cero. Como sólo una variable básica
actual debe salir de la solución básica, se puede escoger entre x11 o x22 como variable de salida. En forma arbitraria
escogeremos a x11 para que salga de la solución. La selección de x31 (= 5) como variable de entrada y x11 como variable de
salida requiere el ajuste de los valores de las variables básicas en las esquinas del ciclo cerrado, como se ve en la tabla
siguiente. Como cada unidad que se transporta por la ruta (3, 1) reduce el costo de transporte en $9 (= u3 + v1 - c31), el
costo total asociado con el nuevo programa es $9 X 5 = $45 menos que en el programa anterior. En consecuencia, el
costo nuevo es $520 - $45 = $475
EL MODELO DE ASIGNACIÓN
“La mejor persona para el puesto”
El modelo general de asignación con n trabajadores y n puestos se representa en la tabla siguiente:
El método húngaro
Trabajo grupal
