26 Ene
Fundamentos de Investigación de Operaciones: El Problema de Transporte
Septiembre 2002
El Problema de Transporte corresponde a un tipo particular de 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.
2 Resolución del Problema de Transporte
2.1 Solución inicial
Consideremos un problema de transporte balanceado con m puntos de oferta y n puntos de demanda. De acuerdo a la formulación vista anteriormente, el problema tendría m + n restricciones de igualdad.
Para proceder a describir algunos métodos para encontrar una primera solución inicial, es importante observar que si un conjunto de valores para las variables xij satisface todas las restricciones salvo una, automáticamente satisface la otra restricción. Por ejemplo, consideremos que en el ejemplo anterior se sabe que los valores de las variables satisfacen todas las restricciones, salvo la primera restricción de oferta. Por lo tanto, los valores de las xij satisfacen d1 + d2 + d3 + d4 = 125 millones de [kWh] y proveen s2 + s3 = 125 – s1 = 90 millones de [kWh] de las plantas 2 y 3. Por lo tanto, la planta 1 debe proveer 125 – (125 – s1) = 35 millones de [kWh]; luego los valores de xij también satisfacen la primera restricción de oferta.
En lo sucesivo, para resolver el problema de transporte consideraremos que se satisfacen m + n – 1 restricciones, omitiendo alguna. En forma arbitraria, omitiremos la primera restricción de oferta. Evidentemente, cualquier colección de m + n – 1 variables no necesariamente es una solución factible para el problema.
Consideremos el siguiente problema de transporte (omitiremos los costos unitarios):
4 5 3 2 4
En forma matricial, las restricciones del problema de transporte balanceado anterior pueden ser escritas de la siguiente forma:
[ 1 1 1 0 0 0 ] [ 0 0 0 1 1 1 ] [ 1 0 0 1 0 0 ] [ 0 1 0 0 1 0 ] [ 0 0 1 0 0 1 ] [ x11 ] [ x12 ] [ x13 ] [ x21 ] [ x22 ] [ x23 ] = [ 4 ] [ 5 ] [ 3 ] [ 2 ] [ 4 ]
Eliminando la primera restricción de oferta el sistema se reduce a:
[ 0 0 0 1 1 1 ] [ 1 0 0 1 0 0 ] [ 0 1 0 0 1 0 ] [ 0 0 1 0 0 1 ] [ x11 ] [ x12 ] [ x13 ] [ x21 ] [ x22 ] [ x23 ] = [ 5 ] [ 3 ] [ 2 ] [ 4 ]
Como el sistema anterior tiene 4 restricciones y 6 variables posee infinitas soluciones; sin embargo, siempre tendrá como solución al menos 4 variables no nulas.
Para obtener una solución básica factible en forma simple introduciremos el concepto de loop.
Definición 1
Un orden secuencial de al menos cuatro celdas distintas se denomina loop si:
- Dos celdas consecutivas están en la misma columna o en la misma fila.
- No tiene tres celdas consecutivas en una misma columna o en una misma fila.
- La última celda de la secuencia tiene una fila o columna común con la primera celda de la secuencia.
Las figuras siguientes muestran algunos tipos de loop en dos tableaux de transporte.
Las siguientes figuras muestran algunos ejemplos de secuencias de celdas que no conforman un loop, pues no satisfacen todas las condiciones.
Teorema 1
En un problema de transporte balanceado con m puntos de oferta y n puntos de demanda, las celdas correspondientes a un conjunto de m + n – 1 variables no contienen un loop si y sólo si las m + n – 1 variables constituyen una solución inicial.
El teorema anterior se desprende del hecho de que en un conjunto de m + n – 1 celdas no contienen un loop si y sólo si las m + n – 1 columnas correspondientes a las celdas son linealmente independientes.
Los métodos más empleados para obtener soluciones iniciales son:
- El método de la Esquina Noroeste.
- El método del Costo Mínimo.
- El método de Vogel.
A continuación revisaremos sólo el método de la Esquina Noroeste y el de Vogel.
Método de la Esquina Noroeste
Para encontrar una solución inicial se comienza por la esquina superior izquierda (noroeste) del tableau de transporte intentando asignar la máxima cantidad posible a x11. Evidentemente, el valor máximo de x11 debe ser el menor entre s1 y d1. Si x11 = s1, se puede descartar la primera fila pues ya no podría asignarse más desde el primer punto de oferta; se avanza a la siguiente fila. Al mismo tiempo, se debe cambiar d1 por d1 – s1, de forma de indicar la cantidad de demanda no satisfecha en el primer punto de demanda. En caso que x11 = d1, se debe descartar la primera columna y cambiar s1 por s1 – d1, avanzando una columna. Si x11 = d1 = s1, se debe avanzar en una columna o en una fila (pero no en ambas). Se asigna un cero en la dirección escogida y se descarta la otra alternativa.
El método continúa aplicando el mismo criterio desde la esquina noroeste del tableau restante. Una vez que están asignadas toda la demanda y oferta disponible, se terminan las asignaciones y está completa la asignación inicial.
Apliquemos el método al siguiente tableau (notar que no se incorporan los costos pues el método no los emplea):
5 1 3 2 4 2 1
Comenzamos asignando la máxima cantidad posible por fila o por columna en la esquina noroeste. En este caso, controla la primera columna, luego:
2 3 <= 1 <= 3 0 4 2 1
A continuación, avanzamos una columna y en esta celda controla la fila, por lo tanto queda:
6 2 3 . . 0 . 1 . 3 0 1 2 1
En este caso, la esquina más noroeste disponible es la celda 2-2. Aquí, la demanda y la oferta se igualan. Arbitrariamente se escogería la celda inferior de la misma columna para asignar un cero:
2 3 . . 0 . 1 . . 0 . 0 3 0 0 2 1
Luego, la celda más noroeste disponible es la 3-3. En esta celda, controla la demanda de 2 sobre la oferta de 3, luego:
2 3 . . 0 . 1 . . 0 . 0 2 1 0 0 0 1
Finalmente, se completa el tableau haciendo la última asignación factible:
2 3 . . 0 . 1 . . 0 . 0 2 1 0 0 0 0 0
En el tableau final se puede verificar las m + n – 1 asignaciones. Además se observa que la secuencia de celdas no conforman ningún loop; por lo tanto, de acuerdo al teorema corresponde a una asignación inicial factible.
Método de Vogel
El método comienza calculando por cada columna y por cada fila el castigo o penalty. El castigo se calcula como la diferencia entre los dos costos menores en la columna o en la fila según corresponda. A continuación, se determina la fila o columna con un mayor valor de castigo. Luego, se selecciona como variable basal la celda con menor costo de la fila o columna, según corresponda, y se le asigna la máxima cantidad posible. Una vez realizada la asignación, se descarta la fila o columna cuya oferta o demanda haya sido completa. Se recalcula la demanda u oferta disponible en la fila o columna. La primera asignación se ha completado.
Se vuelven a calcular los castigos por fila y por columna y se repite el procedimiento descrito hasta completar las asignaciones posibles en el tableau.
La ventaja del método de Vogel por sobre el de la Esquina Noroeste es que avanza algunas iteraciones y, por lo tanto, se obtiene una solución inicial mejor. Eventualmente puede ocurrir que aplicando el método se llegue directamente a la solución óptima. La desventaja del método de Vogel radica en que sin duda es más complejo que el de la esquina noroeste; por lo tanto es más difícil de implementar y más proclive a errores en la aplicación.
Para ilustrar la aplicación del método veamos un ejemplo. Consideremos el siguiente tableau de transporte:
Oferta 6 7 8 10 15 80 78 15 Demanda 15 5 5
De acuerdo al método, en primer lugar se calculan los castigos por fila y por columna:
Oferta Castigo 6 7 8 10 7 - 6 = 1 15 80 78 15 78 - 15 = 63 Demanda 15 5 5 Castigo 9 73 70
El mayor castigo entre filas y columnas se encuentra en la segunda columna. De ambas celdas, la de mínimo costo es la de costo unitario 7; buscando la máxima asignación por fila y por columna controla la columna con una asignación máxima de 5 unidades.
(Se continúa recalculando castigos y aplicando el mismo criterio. En el ejemplo, finalmente se obtienen las asignaciones tales que el número de asignaciones es exactamente igual a m + n – 1 = 2 + 3 – 1 = 5. Eventualmente, el método puede generar un número inferior de asignaciones. En dicho caso se completan las m + n – 1 asignaciones con ceros. En el caso de que falte sólo una asignación, se puede ubicar un cero en cualquier casilla no asignada. En el caso que se requiera de dos o más ceros, la asignación no es tan arbitraria. Más adelante se definirá qué criterio emplear en dichos casos.)
Existen problemas de maximización que pueden ser considerados como problemas de Transporte. En este caso, los coeficientes cij están asociados a los beneficios unitarios de la variable asociada a la combinación i – j y el objetivo es maximizar la suma total de los aportes individuales de las variables. Se mantienen las restricciones de oferta y demanda.
En los casos de maximización, es preciso alterar los métodos para obtener una solución inicial factible. En el caso del método de la Esquina Noroeste, se debe intentar asignar la mayor cantidad posible a las casillas con mayor cij. En el caso del método de Vogel, los castigos se calculan entre los dos mayores beneficios por fila y por columna. Al igual que el método de la Esquina Noroeste, se busca asignar la mayor cantidad posible a las casillas con mayor beneficio.
2.2 El Método Simplex del Problema de Transporte
A continuación se exponen los pasos para aplicar el método Simplex para el problema de Transporte. La deducción y justificación detallada de cada uno de los pasos se puede encontrar en los textos de la bibliografía de la asignatura.
- Paso 1. Si el problema no está balanceado, balancearlo. Construir el tableau de transporte.
- Paso 2. Encontrar una solución inicial factible por el método de la Esquina Noroeste o el de Vogel. Verificar las m + n – 1 asignaciones y completarlas si es necesario.
- Paso 3. Plantear y resolver el sistema que se obtiene a través de:
- Definir para cada fila del tableau la variable ui con (i = 1 … m).
- Definir para cada columna del tableau la variable vj con (j = 1 … n).
- Plantear para cada casilla asignada la ecuación ui + vj = cij, donde cij es el costo unitario asociado a la casilla i – j.
- Asignar un valor arbitrario a una de las variables, por ejemplo u1 = 0.
- Paso 4. Calcular en todas las casillas no asignadas (no básicas) eij = cij – ui – vj. Si todos los eij ≥ 0 se ha encontrado el óptimo. Si existe algún eij < 0, incorporar la variable con menor eij siempre y cuando pueda formar un loop; en dicho caso, asignar el mayor valor posible de modo de mantener las variables básicas mayores o iguales a cero.
- Paso 5. Si la solución no es la óptima, emplear la solución del paso anterior para volver a plantear y resolver el sistema (Paso 3). Seguir al Paso 4.
La variable eij representa el aporte neto unitario de la incorporación de la variable i – j a la base. Por lo tanto, si el problema es de maximización, la solución sería óptima si todos los eij < 0. En caso contrario, se ingresa a la base la variable con mayor eij que pueda formar un loop.
En el caso de que al emplear uno de los métodos para obtener una solución inicial falten dos o más asignaciones para completar las m + n – 1 asignaciones requeridas, los ceros deben ser ubicados de tal forma que sea suficiente dar sólo un valor arbitrario a las variables del sistema asociado a la asignación para poder resolverlo completamente.
Ilustremos el procedimiento resolviendo el tableau planteado para el problema del primer ejemplo. En ese caso, mediante la Esquina Noroeste se obtuvo la siguiente solución inicial:
Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Oferta 8 6 10 9 Planta 1 35 35 9 12 13 7 Planta 2 10 20 20 50 14 9 16 5 Planta 3 10 30 40 Demanda 45 20 30 30
A continuación podemos plantear las variables del sistema asociado:
v1 v2 v3 v4 8 6 10 9 u1 35 35 9 12 13 7 u2 10 20 20 50 14 9 16 5 u3 10 30 40 45 20 30 30
Luego, las ecuaciones se plantean en las casillas asignadas:
u1 + v1 = 8 (1) u2 + v1 = 9 (2) u2 + v2 = 12 (3) u2 + v3 = 13 (4) u3 + v3 = 16 (5) u3 + v4 = 5 (6)
Agregando la condición u1 = 0 se obtiene de (1) v1 = 8. Luego, de (2) u2 = 1. De (3) y de (4) v2 = 11 y v3 = 12. Reemplazando en (5) se calcula u3 = 4. Finalmente, de (6) se obtiene v4 = 1. A continuación se calculan los eij en las casillas no básicas:
e12 = 6 - 0 - 11 = -5 e13 = 10 - 0 - 12 = -2 e14 = 9 - 0 - 1 = 8 e24 = 7 - 1 - 1 = 5 e31 = 14 - 4 - 8 = 2 e32 = 9 - 4 - 11 = -6
Por lo tanto, el menor eij corresponde a e32 con valor -6. Lo que significa que por cada unidad asignada a la variable x32 el efecto global neto es de -6, independientemente de que el costo asociado a dicha casilla sea de 9. Veamos si existe un loop factible y el máximo valor α que podría tomar la variable.
8 6 10 9 35 35 9 12 13 7 10 20 - α 20 + α 50 14 9 16 5 α 10 - α 30 40 45 20 30 30
Como las variables deben ser positivas, el valor de α debe ser tal que no introduzca una variable negativa al tableau. En este caso, la condición que controla es 10 – α ≥ 0, por lo tanto α = 10.
Introducimos el valor de α y volvemos a plantear el sistema asociado:
v1 v2 v3 v4 8 6 10 9 u1 35 35 9 12 13 7 u2 10 10 30 50 14 9 16 5 u3 10 30 40 45 20 30 30
Las únicas variables no básicas que tienen un eij < 0 son: e12 = -5, e24 = -1 y e13 = -2. Buscando un loop para x12 y su máximo valor factible se obtiene:
8 6 10 9 35 - α α 35 9 12 13 7 10 + α 10 - α 30 50 14 9 16 5 10 30 40 45 20 30 30
De acuerdo al loop encontrado, el máximo valor para α es 10. Luego, volvemos a plantear el sistema para las variables basales:
v1 v2 v3 v4 8 6 10 9 u1 25 10 35 9 12 13 7 u2 20 30 50 14 9 16 5 u3 10 30 40 45 20 30 30
Resolviendo y evaluando los eij para cada variable no basal, el único eij < 0 es e13 = -2. Verificando que exista un loop y determinando el máximo valor posible se tiene:
8 6 10 9 25 - α 10 α 35 9 12 13 7 20 + α 30 - α 50 14 9 16 5 10 30 40 45 20 30 30
En este caso, para mantener las variables positivas α debe ser ≤ 25. Haciendo la actualización y volviendo a resolver el sistema asociado se tiene:
v1 v2 v3 v4 8 6 10 9 u1 10 25 35 9 12 13 7 u2 45 5 50 14 9 16 5 u3 10 30 40 45 20 30 30
Resolviendo el sistema, se determina que todos los eij son positivos; por lo tanto la incorporación de cualquier variable a la base aumentaría el valor total de la función objetivo. Como el problema es de minimización, se ha alcanzado el óptimo. Por lo tanto, el tableau final queda:
8 6 10 9 10 25 35 9 12 13 7 45 5 50 14 9 16 5 10 30 40 45 20 30 30
La solución corresponde exactamente a la entregada con anterioridad. La solución óptima es:
x12 = 10 x13 = 25 x21 = 45 x23 = 5 x32 = 10 x34 = 30 x11 = x14 = x22 = x24 = x31 = x33 = 0 z = 6(10) + 10(25) + 9(45) + 13(5) + 9(10) + 5(30) = 1020
3 Análisis de Sensibilidad en Problemas de Transporte
A continuación se discutirán tres tipos de análisis de sensibilidad de un problema de transporte:
- Variación 1. Cambios en los coeficientes de la función objetivo de variables no básicas.
- Variación 2. Cambios en los coeficientes de la función objetivo de variables básicas.
- Variación 3. Incrementos en una oferta y en una demanda.
Para ilustrar el análisis de sensibilidad sobre la solución óptima de un problema de transporte emplearemos la solución obtenida en la sección anterior:
v1 = 6 v2 = 6 v3 = 10 v4 = 2 8 6 10 9 u1 = 0 10 25 35 9 12 13 7 u2 = 3 45 5 50 14 9 16 5 u3 = 3 10 30 40 45 20 30 30
3.1 Variación de coeficientes en la función objetivo de variables no basales
En este caso, simplemente se impone una variación Δ en el coeficiente de la variable xij a modificar, estudiando el rango de variación admisible de modo que el eij respectivo mantenga su signo.
A modo de ejemplo, supongamos que se desea determinar cuánto debe disminuir el costo de envío desde la Planta 1 a la Ciudad 1 de modo de incorporar esta combinación a la solución óptima. En este caso, un cambio del coeficiente c11 = 8 a c11 = 8 – Δ no afecta los valores de los ui y vj calculados previamente, por lo tanto:
e11 = (8 - Δ) - 0 - 6 = 2 - Δ
Como corresponde a un problema de minimización, para que x11 entre a la base debe cumplirse que e11 < 0, es decir Δ ≥ 2. Por lo tanto, el costo debe disminuir en al menos 2 (hasta menos de 6) para que se incorpore a la solución óptima. De todas formas, se debe verificar que la variable pueda generar un loop:
v1 = 6 v2 = 6 v3 = 10 v4 = 2 8 6 10 9 u1 = 0 α 10 25 - α 35 9 12 13 7 u2 = 3 45 - α 5 + α 50 14 9 16 5 u3 = 3 10 30 40 45 20 30 30
Por lo tanto la variable puede entrar a la base con valor de 25, el nuevo valor de la función objetivo sería:
z_{k+1} = z_k + e_{ij} · α = 1020 + (2 - Δ) · 25, Δ ≥ 2
3.2 Variación de coeficientes en la función objetivo de variables basales
En este caso la situación es más compleja pues una variación del coeficiente de una variable basal afectará el valor de los ui y los vj calculados previamente. Es necesario volver a resolver el sistema en términos de la variación Δ del coeficiente de la variable basal, volver a calcular los eij y determinar el rango de variación admisible.
Supongamos por ejemplo que se desea determinar en cuánto podría aumentar el costo de envío desde la Planta 1 a la Ciudad 3 de modo de mantener la base óptima. En este caso, cambiamos c13 = 10 por c13 = 10 + Δ y volvemos a resolver el sistema:
u1 + v2 = 6 u1 + v3 = 10 + Δ u2 + v1 = 9 u2 + v3 = 13 u3 + v2 = 9 u3 + v4 = 5 u1 = 0
De esta forma, se obtiene:
u1 = 0 v2 = 6 v3 = 10 + Δ v1 = 6 + Δ u2 = 3 - Δ u3 = 3 v4 = 2
Luego, calculamos los eij para todas las variables no basales y sus restricciones:
e11 = 8 - u1 - v1 = 2 - Δ ≥ 0 ⇒ Δ ≤ 2 e14 = 9 - u1 - v4 = 7 ≥ 0 e22 = 12 - u2 - v2 = 3 + Δ ≥ 0 ⇒ Δ ≥ -3 e24 = 7 - u2 - v4 = 2 + Δ ≥ 0 ⇒ Δ ≥ -2 e31 = 14 - u3 - v1 = 5 - Δ ≥ 0 ⇒ Δ ≤ 5 e33 = 16 - u3 - v3 = 3 - Δ ≥ 0 ⇒ Δ ≤ 3
Por lo tanto, la base óptima se mantiene para un rango de variación: -2 ≤ Δ ≤ 2, o bien,
8 ≤ c13 ≤ 12
3.3 Incrementos en una oferta y en una demanda
Si tanto en alguna oferta si como en alguna demanda dj se produce un aumento de Δ, se mantiene el balanceo del problema. En este caso, se demuestra que:
z_{nuevo} = z_{original} + Δ·u_i + Δ·v_j
La expresión anterior se obtiene a partir de que tanto los ui y los vj equivalen a menos el precio sombra de la restricción asociada a cada origen i o destino j según corresponda.
Por ejemplo, si la oferta de la Planta 1 y la demanda de la Ciudad 2 crece en una unidad, se tiene:
z_{nuevo} = 1020 + 1·0 + 1·6 = 1026
Una vez definido el nuevo valor de la función objetivo, es importante determinar cómo cambian los valores de las variables. Para ello se siguen las siguientes reglas:
- Si xij es una variable básica, xij se incrementa en Δ.
- Si xij es una variable no básica, se debe encontrar el loop que contenga a xij y algunas de las variables basales. Encontrar la primera celda de la fila i (distinta de xij) y aumentar su valor en Δ. Continuar el loop, incrementando y disminuyendo en Δ en forma alternada.
Para ilustrar la primera situación, supongamos que s1 y d2 aumentan en 2. Como x12 es una variable basal, el nuevo tableau óptimo queda:
v1 = 6 v2 = 6 v3 = 10 v4 = 2 8 6 10 9 u1 = 0 12 25 37 9 12 13 7 u2 = 3 45 5 50 14 9 16 5 u3 = 3 10 30 40 45 22 30 30
El nuevo valor de la función objetivo es: 1020 + 2·u1 + 2·v2 = 1032.
Para ilustrar la segunda situación, supongamos que s1 y d1 aumentan en 1. Como x11 es una variable no basal, debemos determinar el loop que incorpora a la celda (1,1). En este caso, el loop es (1,1) – (1,3) – (2,3) – (2,1). La primera celda del loop que está en la fila 1 distinta de (1,1) es (1,3). Entonces, se debe agregar Δ a x13. Continuando con el loop, se debe disminuir en Δ x23 y volver a aumentar en Δ a x21. El nuevo tableau óptimo se muestra a continuación:
v1 = 6 v2 = 6 v3 = 10 v4 = 2 8 6 10 9 u1 = 0 10 26 36 9 12 13 7 u2 = 3 46 4 50 14 9 16 5 u3 = 3 10 30 40 46 20 30 30
El nuevo valor de la función objetivo es: 1020 + u1 + v1 = 1026.
4 El Problema de Transbordo
Un problema de transporte permite sólo envíos directamente desde los puntos de origen a los puntos de demanda. En muchas situaciones, sin embargo, existe la posibilidad de hacer envíos a través de puntos intermedios (puntos de transbordo). En este caso se habla de un problema de transbordo. A continuación veremos cómo la solución de un problema de transbordo puede ser encontrada a través de un problema de transporte.
Definiremos los puntos de oferta como aquellos puntos desde donde sólo se puede despachar unidades. Similarmente, un punto de demanda es un punto donde sólo se pueden recibir unidades. Un punto de transbordo es un punto que puede recibir y enviar unidades a otros puntos. Veamos un ejemplo:
Ejemplo 2
Una fábrica posee dos plantas de manufactura, una en Memphis y otra en Denver. La planta de Memphis puede producir hasta 150 unidades al día; la de Denver hasta 200 unidades al día. Los productos son enviados por avión a Los Angeles y Boston. En ambas ciudades, se requieren 130 unidades diarias. Existe la posibilidad de reducir costos enviando algunos productos en primer lugar a New York o a Chicago y luego a sus destinos finales. Los costos unitarios de cada tramo factible se ilustran en la siguiente tabla:
Hacia Desde Memphis Denver N.Y. Chicago L.A. Boston Memphis 0 - 8 13 25 28 Denver - 0 15 12 26 25 N.Y. - - 0 6 16 17 Chicago - - 6 0 14 16 L.A. - - - - 0 - Boston - - - - - 0
La fábrica desea satisfacer la demanda minimizando el costo total de envío. En este problema, Memphis y Denver son puntos de oferta de 150 y 200 unidades respectivamente. New York y Chicago son puntos de transbordo. Los Angeles y Boston son puntos de demanda de 130 unidades cada uno. Esquemáticamente, la situación es la siguiente:
Memphis → New York / Chicago → Los Angeles / Boston, con Denver como origen adicional y New York/Chicago como nodos de transbordo.
A continuación construiremos un problema de transporte balanceado a partir del problema de transbordo. Para ello podemos seguir los siguientes pasos (suponiendo que la oferta excede a la demanda):
- Paso 1. Si es necesario, agregar un punto de demanda dummy (con oferta 0 y demanda igual al excedente) para balancear el problema. Los costos de envío al punto dummy deben ser cero. Sea s la oferta total disponible.
- Paso 2. Construir un tableau de transporte siguiendo las siguientes reglas:
- Incluir una fila por cada punto de oferta y de transbordo.
- Incluir una columna por cada punto de demanda y de transbordo.
- Cada punto i de oferta debe poseer una oferta igual a su oferta original si. Cada punto de demanda j debe poseer una demanda igual a su demanda original dj.
- Cada punto de transbordo debe tener una oferta igual a su oferta original + s y una demanda igual a su demanda original + s. Como de antemano no se conoce la cantidad que transitaría por cada punto de transbordo, la idea es asegurar que no se exceda su capacidad. Se agrega s a la oferta y a la demanda del punto de transbordo para no desbalancear el tableau.
En el ejemplo, s = 150 + 200 = 350. La demanda total es 130 + 130 = 260. Luego, el punto dummy debe tener una demanda de 350 – 260 = 90. Como en el ejemplo los puntos de transbordo no tienen ni demanda ni oferta por sí mismos, la oferta y demanda en el tableau debe ser igual a s. Una vez planteado el tableau, se pueden emplear los métodos vistos anteriormente para obtener una solución inicial factible y obtener la solución óptima. En este caso el tableau queda (incluida la solución óptima):
N.Y. Chicago L.A. Boston Dummy Oferta
Memphis 8 13 25 28 0 130 20 (150 total pero 20 al dummy)
Denver 15 12 26 25 0 130 70 (200 total pero 70 al dummy)
N.Y. 0 6 16 17 0 220 130 (transbordo: 220 no pasan por N.Y.)
Chicago 6 0 14 16 0 350 350 (transbordo: no se empleó)
Demanda 350 350 130 130 90
Para interpretar la solución anterior, es preciso revisar cuidadosamente las combinaciones asignadas. De la primera fila, vemos que de Memphis sólo se despacharon 130 unidades a New York del total de 150 disponibles; el excedente de 20 unidades está asignado al punto artificial. De la segunda fila se desprende que de Denver se enviaron 130 unidades a Boston del total de 200 disponibles, quedando 70 asignadas al punto dummy. En la tercera fila vemos que se enviaron desde el punto de transbordo en New York 130 unidades a Los Angeles. La asignación de 220 de N.Y. a N.Y. significa que del total de unidades en tránsito, 220 no pasaron por dicho nodo de transbordo, o bien, que no se emplearon 220 unidades de la capacidad del punto. Finalmente, en la cuarta fila, la asignación de 350 del punto de transbordo de Chicago a Chicago representa simplemente que no se empleó el punto de transbordo. Gráficamente, la solución óptima resulta en envíos directos y algunos envíos vía transbordo según lo indicado arriba.
5 Ejercicios
Una fábrica de zapatos predice las siguientes demandas por sus pares de zapatos para los próximos 6 meses: mes 1: 20 000; mes 2: 26 000; mes 3: 24 000; mes 4: 34 000; mes 5: 19 000; mes 6: 15 000. (Nota: los números originales parecen expresados en centenas o miles; ajuste a la unidad apropiada en su formulación.) El costo de fabricar un par de zapatos es de US$ 7 con horas normales de trabajo y de US$ 11 con horas de sobretiempo. Durante cada mes, la producción en horario normal está limitada a 20 000 pares de zapatos y la producción con sobretiempo está limitada a 10 000 pares. Guardar un par de zapatos en inventario cuesta US$ 1 por mes.
- Formule un modelo que permita obtener una solución óptima.
- Determine una solución factible y verifique si es la solución óptima.
Debido a las fuertes lluvias de los últimos días en el sur, la empresa Stop-Lluvia, dedicada al rubro de los paraguas, ha visto un aumento en la demanda de sus productos. Los paraguas se arman en dos plantas, según la siguiente tabla:
Planta Capacidad de producción [paraguas] Costo de producción [US$/paragua] A 2600 2300 B 1800 2500Cuatro cadenas de multitiendas están interesadas en adquirir los paraguas, con las siguientes características:
Cadena Máxima demanda [paraguas] Precio dispuesto a pagar [US$/paragua] 1 1800 3900 2 2100 3700 3 550 4000 4 1750 3600El costo de traslado a cada tienda (fijo) se muestra en la siguiente tabla:
Costo Fijo [US$] 1 2 3 4 A 600 800 1100 900 B 1200 400 800 500- Determinar la mejor decisión de entrega, para la empresa productora de paraguas.
- Si todas las tiendas acuerdan pagar lo mismo por cada paraguas, plantee el problema desde el punto de vista de la minimización de lo que deja de ganar por no elegir lo que más conviene.
- ¿Cuál sería la mejor asignación si el costo de traslado desde ambas plantas es el mismo para todas las tiendas?
Se desataron tres incendios en Santiago. Los incendios 1 y 2 requieren de la participación de dos carros bomba y el incendio 3 requiere tres carros bomba. Existen cuatro compañías de bomberos que pueden responder a estos incendios. La compañía 1 tiene tres carros bombas disponibles, las compañías 2 y 3 tienen dos carros bombas cada una y la compañía 4 tiene doce carros bombas disponibles. El tiempo en minutos que toma un carro bomba en viajar desde cada compañía al lugar de cada incendio se muestra en la siguiente tabla:
Incendio 1 Incendio 2 Incendio 3 Compañía 1 6 7 9 Compañía 2 5 8 11 Compañía 3 6 9 10 Compañía 4 7 10 12El costo de respuesta a cada incendio puede ser estimado según el tiempo que tardan en llegar al lugar de incendio cada uno de los carros bombas requeridos. Sea Tij el tiempo (en minutos) cuando el j-ésimo carro bomba llega al incendio i. Luego, el costo de respuesta a cada incendio se puede estimar de la siguiente manera:
- Incendio 1: 4·T11 + 6·T12
- Incendio 2: 7·T21 + 3·T22
- Incendio 3: 9·T31 + 8·T32 + 5·T33
- Formule y resuelva el problema que minimice los costos de respuesta asociados a la asignación de los carros bombas a los incendios.
- ¿Podría ser válido lo obtenido anteriormente si el costo del incendio 1 fuese 6·T11 + 4·T12?
Usted ha sido encargado de diseñar un plan de producción ventajoso para una empresa durante las 4 estaciones del año. Esta empresa tiene una capacidad de producción para manufacturar 30 000 unidades de un producto no perecible en Primavera y Otoño de este año. Debido a enfermedades, vacaciones y permisos, la producción será sólo de 25 000 unidades en Verano e Invierno. La demanda por este producto también es estacional. El Departamento de Marketing ha estimado las ventas de Primavera en 25 000 unidades, en Verano 40 000 unidades, 30 000 unidades en Otoño y sólo 15 000 unidades en Invierno. Los costos unitarios de producción se estiman en US$ 80, US$ 85, US$ 82 y US$ 86 en Primavera, Verano, Otoño e Invierno, respectivamente. Cualquier exceso de producción se puede almacenar a un costo de US$ 10 por unidad almacenada durante una estación. Una unidad se vende en US$ 120, US$ 140, US$ 125 y US$ 105 en Primavera, Verano, Otoño e Invierno, respectivamente. En bodega había al comienzo 10 000 unidades y al final deben haber 10 000 unidades. ¿Cuál es la mayor ganancia para su plan?
Fin del documento.
Deja un comentario