Download - Optimizacion de Redes, programación entrera
-
4.1 INTRODUCCIN
Los modelos de programacin matemtica pueden ser aplicados a una gran variedad de
situaciones; algunas de ellas tienen en comn la caracterstica que pueden ser representadas y
modeladas por una red.
Estos modelos de redes son formulados como un conjunto de puntos que son comnmente
llamados nodos, los que pueden representar entes tales como ciudades, bodegas, estanques,
mquinas, computadores, puertos, personas, comienzo o trmino de trabajos o actividades, entre
otros; adems hay interconexiones de unin entre los nodos conocidas como arcos, los que
pueden representar entes tales como caminos, puentes, tuberas, cables conductores de
electricidad, rutas areas o martimas, trabajos, perodos de tiempo, entre otros.
As estos modelos de redes nos pueden ayudar a representar, modelar y optimizar sistemas de
transporte, programacin de rutas de vehculos, cadenas logsticas, gestin de procesos de
manufactura, distribucin de productos, organizacin de las actividades de un proyecto, etc.; lo
anterior dado que todas ellos poseen en comn una estructura particular que permite una
representacin en base a redes (construidas con nodos y arcos), para luego aplicar las tcnicas de
anlisis y modelos optimizacin que explicaremos a continuacin, y que se pueden resolver
usando los conceptos de programacin lineal y entera presentados en los captulos anteriores.
-
4.2 APLICACIONES
Las redes (tambin llamadas grafos por los matemticos) estn formadas por un conjunto de
puntos (nodos), que pueden estar o no relacionados (conectados) entre si por una lnea (arco).
Estas redes sirven para representar y modelar situaciones muy diversas, tales como:
Transporte y distribucin de productos.
Distribucin de servicios pblicos (agua, alcantarillado, telfono, TV por cable,
electricidad, gas).
(Ver en la pgina siguiente una representacin del SIN, Sistema interconectado del Norte
Grande, que es una red donde hay nodos de generacin de electricidad, lneas de
transmisin, nodos de distribucin y nodos de consumo).
Computadores interconectados a nivel empresa (intranet) y a nivel global (internet).
Lneas de ferrocarriles, terminales y estaciones.
Recorridos de buses y metro.
Carreteras y ciudades.
Aeropuertos y rutas areas.
Mquinas y trabajos.
Lneas de produccin.
Actividades de un proyecto, lo que ser tema del prximo captulo.
Personas y tareas.
Trnsito de vehculos (autos, buses, taxis, camiones) en una ciudad.
Redes de transporte martimo formadas por puertos, puertos secos, bodegas.
Tecnologa BPL (Broadband Power Line) que permite transportar voz, datos y video
utilizando las lneas de media y baja tensin.
El modelamiento de una situacin a travs de una red busca analizar y optimizar la situacin a
nivel de diseo y/u operacin de ella; por ejemplo en el caso de transporte y distribucin de
productos es importante contar con un buen modelo de la red, objeto generar las rutas ptimas
para los vehculos de acuerdo a los lugares de origen y destino de las mercaderas demandadas.
-
En el caso de la optimizacin de la red vial de una ciudad, es necesario contar con un modelo de
esta, para sobre ella efectuar las modificaciones que permitirn efectuar mejoras que vayan en
beneficio de los usuarios. En este caso, y para decidir sobre las modificaciones, se podrn usar
herramientas como la programacin lineal y entera, las simulaciones, la teora de lneas de espera
y los pronsticos de trfico y demandas sobre la red vial.
En general, se pueden usar algoritmos de programacin matemtica lineal o entera, los que casi
siempre permitirn modelar la situacin y solucionar el problema. Existen tambin algoritmos
particulares, que en situaciones especficas pueden ser ms eficientes que la programacin lineal
o la entera, especialmente en modelos de gran tamao. A continuacin se presentan cinco
modelos bsicos que ayudan a resolver diversos problemas:
1. Problema de Transporte.
2. Problema de Asignacin.
3. Problema de Transporte con Transbordo.
4. Problema del Camino Ms Corto.
5. Problema del Flujo Mximo.
-
4.2.1 PROBLEMA DE TRANSPORTE
Este tipo de problema aparece en el caso de la planificacin de la distribucin de productos desde
diversos puntos de abastecimiento (orgenes, oferta) a distintos puntos de destino o demanda
(venta, almacenamiento). Usualmente la cantidad de unidades del producto disponibles en cada
punto de abastecimiento (orgen) es limitada, y el producto es requerido en cada uno de los
puntos de venta (destino), en cantidades determinadas.
El objetivo es minimizar el costo global de envo del producto, desde los orgenes hasta los
distintos destinos, satisfaciendo los requerimientos de los destinos y respetando las
disponibilidades de los orgenes.
Tambin el modelamiento de este tipo de situaciones nos puede ayudar a tomar decisiones de
ubicacin de bodegas, fbricas o centros de distribucin.
La siguiente figura 4.1 muestra en forma esquemtica la situacin a modelar.
Figura 4.1
Sean m los puntos de origen o abastecimiento y n los puntos de venta, demanda o destino; se
trata de satisfacer los requerimientos de estos puntos de destino, minimizando el costos total de
transporte.
OR1 1
2
m n
2
1
OR2
ORm
DE1
DE2
DEn
-
Funcin Objetivo: Minimizar ( Z = Cij*Xij ) con 1 i m 1 j n
Cij = costo de enviar una unidad del producto desde el origen i al destino j.
Xij = cantidad de unidades del producto a transportar desde el origen i al destino j.
Restricciones:
la cantidad que sale del nodo i = Xij = ORi = la cantidad disponible en el nodo i
la cantidad que llega al nodo j = Xij = DEj = la cantidad demandada en el nodo j
Estamos asumiendo que la suma de las disponibilidades en los orgenes es igual a la suma de las
demandas en los destinos.
Ejemplo. Una firma distribuye maquinaria industrial especializada y posee 3 bodegas localizadas
en 3 regiones distintas. Se han recibido ordenes de 4 clientes, por un total de 15 mquinas de un
tipo particular. En total, en las 3 bodegas hay 15 unidades disponibles de este tipo de mquinas y
se ha obtenido la siguiente informacin (ver tabla 4.1) sobre los costos de envo de un lugar a
otro, las cantidades disponibles en bodega y las cantidades necesarias para cada uno de los
clientes (se muestran junto a la letra de identificacin de los clientes y las bodegas).
Requerimientos de Clientes
A
(3)
B
(3)
C
(4)
D
(5)
TOTAL
15
Disponibilidad
De Bodega
X (2) $130 $110 $150 $200
Y (6) $170 $140 $120 $130
Z (7) $180 $180 $150 $120
TOTAL 15
Tabla 4.1
m
n
i=1
j=1
-
Determinar como deben ser distribuidas las mquinas para satisfacer a los clientes, a un mnimo
costo. Cual es ese costo mnimo?
Usando PL tenemos:
MIN Z = 130Xxa + 110Xxb + 150Xxc + 200Xxd + 170Xya + 140Xyb + 120Xyc
+ 130Xyd + 180Xza + 180Xzb + 150Xzc + 120Xzd
Xxa+ Xxb+Xxc+Xxd = 2
Xya+ Xyb+Xyc+Xyd = 6 LO QUE SALE DE LAS BODEGAS
Xza+ Xzb+Xzc+Xzd = 7
Xxa+ Xya+Xza = 3
Xxb+ Xyb+Xzb = 3 LO QUE LLEGA A LOS CLIENTES
Xxc+ Xyc+Xzc = 4
Xxd+ Xyd+Xzd = 5
En este caso demanda = oferta, por lo que tenemos una situacin balanceada.
Mathprog nos entrega usando Programacin Entera los siguientes valores: 1, 1, 0, 0, 0, 2, 4, 0, 2,
0, 0, 5 (variables en el mismo orden que en la FO) con Z* = 1960
A continuacin presentaremos el ejemplo anterior usando la estructura de un problema de
transporte; para ello ordenaremos los coeficientes de las restricciones en una matriz, la que se
presenta a continuacin en la tabla 4.2. En este caso las tres primeras filas estn asociadas a las
restricciones de oferta, mientras que las ltimas cuatro estn asociadas a las restricciones de
demanda. Se acostumbra no escribir los ceros.
-
Xxa Xxb Xxc Xxd Xya Xyb Xyc Xyd Xza Xzb Xzc Xzd
1 1 1 1 2
1 1 1 1 6
1 1 1 1 = 7
1 1 1 3
1 1 1 3
1 1 1 4
1 1 1 5
Tabla 4.2
Cualquier modelo que tenga la estructura de restricciones mostrada en la matriz anterior se
conoce como un problema de transporte, independientemente de si representa o no una
situacin de transporte.
En la gran mayora de los casos, las cantidades a transportar desde los orgenes a los destinos y
por otra parte las cantidades demandadas en los destinos son cantidades enteras (contenedores,
cajones, sacos, autos, etc.); la pregunta que cabe hacerse es si las variables de decisin o
cantidades distribuidas sern enteras o no, ya que no tiene sentido por ejemplo hablar de medio
contenedor o de un cuarto de auto.
Para fortuna nuestra los problemas de transporte tienen dos propiedades que nos permiten
aclarar este punto, las que presentamos a continuacin:
PROPIEDAD DE SOLUCIONES ENTERAS; esta indica que si todas las cantidades ofrecidas
y demandadas son enteras (ver ltima columna de la tabla 4.2), entonces todas las variables
bsicas en toda solucin bsica factible (incluyendo la ptima) tendrn valores enteros.
PROPIEDAD DE SOLUCIONES FACTIBLES; esta indica que una condicin necesaria y
suficiente para que existan soluciones factibles es que la suma de las cantidades ofertadas en los
orgenes sea igual a la suma de las cantidades demandadas en los destinos.
-
(En el caso del ejemplo anterior, donde se cumple que oferta = demanda, las variables de decisin
en el ptimo resultaron todas enteras).
Si se tiene una situacin no balanceada (demanda oferta), podemos crear orgenes o destinos
ficticios (imaginarios), objeto tener una situacin balanceada y poder modelar la situacin como
un problema de transporte. Esto lo analizaremos en los siguientes dos ejemplos.
Ejemplo con demanda < oferta, ver tabla 4.3 adjunta
Requerimientos de Clientes
A
(3)
B
(3)
C
(4)
D
(5)
TOTAL
15
Disponibilidad
De Bodega
X (3) $130 $110 $150 $200
Y (7) $170 $140 $120 $130
Z (8) $180 $180 $150 $120
TOTAL 18
Tabla 4.3
Con respecto al modelo anterior, solamente cambian las primeras tres restricciones, relacionadas
con lo que sale de las bodegas, las que ahora tienen una mayor flexibilidad, al cambiar el = por
.
Xxa + Xxb + Xxc + Xxd 3
Xya + Xyb + Xyc + Xyd 7
Xza + Xzb + Xzc + Xzd 8
Mathprog nos entrega usando Programacin Entera los siguientes valores: 3, 0, 0, 0, 0, 3, 4, 0, 0,
0, 0, 5 (variables en el mismo orden que en la FO) con Z* = 1890.
En este caso, para tener una situacin balanceada (o sea un problema de transporte) debemos
agregar un destino ficticio con una demanda ficticia de tres unidades, como se muestra en la
siguiente tabla 4.4.
-
El costo de transporte asociado a las tres unidades ficticias ser cero, ya que en forma ficticia
estamos transportando estas tres unidades sobrantes; esto es compatible con el hecho que el costo
del flete es el que determina a quien se entregan las unidades. En nuestra solucin ptima
debemos tener en cuenta que si una bodega enva unidades al cliente o destino ficticio, en la
realidad no las enva, sino que las mantiene almacenadas.
Requerimientos de Clientes
A
(3)
B
(3)
C
(4)
D
(5)
FIC
(3)
TOTAL
18
Disponibilidad
De Bodega
X (3) $130 $110 $150 $200 $0
Y (7) $170 $140 $120 $130 $0
Z (8) $180 $180 $150 $120 $0
TOTAL 18
Tabla 4.4
Ejemplo con demanda > oferta, ver tabla 4.5 adjunta
Requerimientos de Clientes
A
(4)
B
(4)
C
(5)
D
(6)
TOTAL
19
Disponibilidad
De Bodega
X (2) $130 $110 $150 $200
Y (6) $170 $140 $120 $130
Z (7) $180 $180 $150 $120
TOTAL 15
Tabla 4.5
Xxa + Xxb + Xxc + Xxd = 2
Xya + Xyb + Xyc + Xyd = 6
Xza + Xzb + Xzc + Xzd = 7
-
Xxa + Xya + Xza 4
Xxb + Xyb + Xzb 4
Xxc + Xyc + Xzc 5
Xxd + Xyd + Xzd 6
MIN Z = 130Xxa + 110Xxb + 150Xxc + 200Xxd + 170Xya + 140Xyb + 120Xyc
+ 130Xyd + 180Xza + 180Xzb + 150Xzc + 120Xzd
Mathprog nos entrega usando Programacin Entera los siguientes valores: 0, 2, 0, 0, 0, 2, 4, 0, 0,
0, 1, 6 (variables en el mismo orden que en la FO) con Z* = 1850.
Para analizar este resultado, la pregunta que debemos formularnos en esta situacin es con que
criterio daremos satisfaccin (o insatisfaccin, como en el caso del cliente A) a nuestros clientes.
En este caso, para tener una situacin balanceada (o sea un problema de transporte) debemos
agregar un origen ficticio con una oferta ficticia de cuatro unidades, como se muestra en la
siguiente tabla 4.6.
El costo asociado ser una cantidad M (valor muy grande), ya que en forma ficticia estamos
transportando estas tres unidades inexistentes; el valor del M lo podemos imaginar como una
multa por no satisfacer la demanda.
En nuestra solucin ptima debemos tener en cuenta que si un cliente recibe unidades de la
bodega ficticia, en realidad no las recibe, por lo que tendr una demanda no satisfecha.
-
Requerimientos de Clientes
A
(4)
B
(4)
C
(5)
D
(6)
TOTAL
19
Disponibilidad
De Bodega
X (2) $130 $110 $150 $200
Y (6) $170 $140 $120 $130
Z (7) $180 $180 $150 $120
FIC (4) $M $M $M $M
TOTAL 19
Tabla 4.6
Para resolver una situacin que pueda ser modelada como problema de transporte podemos
usar la PL PE; no obstante, si pensamos en las dos propiedades de los problemas de transporte
ya explicadas, usar la PE es equivalente a la PL, ya que la soltura del modelo de PE y la solucin
mediante PL nos entregarn la misma solucin ptima, donde todas las variables de decisin
sern enteras.
Por otra parte, y dada la estructura especial de los problemas de transporte, se ha desarrollado el
mtodo simplex de transporte, el cual puede ser muy eficiente en situaciones con gran cantidad
de variables de decisin. En forma muy sinttica diremos que el mtodo simplex de transporte
consiste en determinar una solucin bsica factible inicial en forma distinta al mtodo simplex
estndar (lo que hace mucho ms rpido el llegar al ptimo), para luego iterar a partir de ella de
la misma forma que en el caso del simplex estndar, hasta llegar al ptimo.
Tres son las formas ms usadas para determinar la solucin bsica factible inicial:
el mtodo o regla de la esquina noroeste
el mtodo de aproximacin de Russell (o de la celda de costo mnimo)
el mtodo de aproximacin de Vogel
-
Estos algoritmos son especficos para el problema de transporte, y debe quedar claro que no
solucionan el modelo; solamente nos permiten determinar una solucin bsica factible inicial
para comenzar a aplicar el mtodo simplex. Tambin se puede escoger una solucin bsica
factible inicial en forma arbitraria, la que debe respetar las cantidades ofrecidas y las
demandadas.
Por otra parte los mtodos de Russell y de Vogel son bastante ms eficientes en relacin al
mtodo de la esquina noroeste, y en general determinan una solucin bsica factible inicial
cercana a la ptima.
Finalmente se debe dejar claro que los software que usan estos mtodos son aquellos
especficamente construidos para resolver problemas de transporte mediante el mtodo simplex
de transporte. Mayor detalle de la aplicacin de estos mtodos se presenta en el captulo 8 (8.2)
de la bibliografa (1).
4.2.2 PROBLEMA DE ASIGNACIN
Este tipo de problema es un caso particular del problema de transporte presentado anteriormente
(con igual cantidad de orgenes que de destinos) y aparece en una serie de situaciones de toma de
decisiones relacionadas con asignaciones. Por ejemplo, asignar mquinas a trabajos, asignar
administradores a planes o proyectos, asignar vendedores a territorios de ventas, asignar
intervalos de tiempo a tareas, etc. En general en este tipo de situaciones un recurso es asignado a
una tarea, pudiendo existir asignaciones dobles (ver ejemplo de Elvira y Esteban en el captulo
anterior) o mayores.
Se busca el conjunto de asignaciones que optimizar un objetivo global determinado, tal como
minimizar costos, minimizar tiempo, o maximizar beneficios.
Consideremos la siguiente situacin general. Una planta manufacturera cuenta con m mquinas, a
la vez que se deben desarrollar m trabajos. El costo de asignar a la mquina i el trabajo j es Cij.
Se pide modelar el problema de asignacin asociado, asignando a cada mquina un trabajo.
Solucin
Para modelar este problema se utilizan variables binarias (estudiadas en Programacin Entera),
las cuales se presentan a continuacin:
-
Xi,j =
Con la definicin de estas variables de decisin, el problema se modela de la siguiente forma:
Funcin Objetivo: Minimizar ( Z = Cij*Xij )
Restricciones: Xij = 1 i =1,...........,m (toda mquina obtiene un y solo un trabajo)
La sumatoria anterior representa m restricciones de igualdad del tipo:
Xi1 + Xi2 + + Xim = 1 (la mquina i obtiene un y slo un trabajo).
Xij = 1 j =1,., m (todo trabajo debe ser realizado por una mquina)
La sumatoria anterior representa m restricciones de igualdad del tipo:
X1j + X2j + + Xmj = 1 (el trabajo j es ejecutado por una y slo una mquina)
En total se tienen m2 variables de decisin, de las cuales m tendrn valor uno y las restantes valor
cero.
Para resolver este problema se puede usar Programacin Entera (PE), o bien un algoritmo
especfico conocido como Mtodo Hngaro. Mayor detalle de la aplicacin de este algoritmo se
presenta en el captulo 9 (9.4.2) de la bibliografa (6).
Como ejemplo, el entrenador de un equipo de posta 4x100 metros desea determinar el orden en
que corrern sus cuatro titulares en el prximo Campeonato Mundial de Atletismo. El desea
considerar como elemento de decisin los tiempos obtenidos en los ltimos entrenamientos, los
que se muestran en la tabla 4.7 adjunta en unidades de segundos; veamos si podemos ayudarlo.
m
m
i=1
j=1
0, si la mquina i no realiza el trabajo j i =1,..........., m
1, si la mquina i realiza el trabajo j j =1,..., m
-
PARTIDA 2 LUGAR 3er
LUGAR REMATADOR
CORREDOR A 10,2 9,6 9,8 9,5
CORREDOR B 10 9,8 9,6 9,8
CORREDOR C 10,3 9,6 9,5 9,4
CORREDOR D 10,1 9,5 9,4 9,6
Tabla 4.7
Para modelar y resolver esta situacin usaremos Mathprog, The transportation problem, Enter or
Revise an Assignment Problem
Assignment Problem Model:
Number of Tasks and Assignees: 4
Cost Table
| Tasks
| 1 2 3 4
__________|_____________________________
1| 10.2 9.6 9.8 9.5
Assignee 2| 10 9.8 9.6 9.8
3| 10.3 9.6 9.5 9.4
4| 10.1 9.5 9.4 9.6
Optimal Solution:
The X's in the table indicate an optimal assignment of assignees to tasks.
Task
| 1 2 3 4
__________|_____________________________
1| X
Assignee 2| X
3| X
4| X
Cost is 38.4
Se pide modelar esta situacin usando programacin entera binaria.
-
4.2.3 PROBLEMA DE TRANSPORTE CON TRANSBORDO
Otro tipo de problemas de gran importancia es el de transporte usando transbordo, situacin que
se produce frecuentemente en los sistemas de transporte y distribucin al existir varios medios de
transporte que operan en forma secuencial y a la vez intercalados con fbricas, bodegas y centros
de distribucin. Es el caso, por ejemplo, del transporte usando contenedores en forma intermodal,
donde se emplean camiones, buques, trenes y eventualmente aviones.
Consideremos el caso de la distribucin de combustible con transbordo, el que se muestra en la
siguiente figura 4.2, ya presentada en la figura 1.2 del captulo 1, introductorio a la IO.
Figura 4.2
Se pide modelar y optimizar esta situacin.
-
Solucin
La situacin se puede modelar usando la red mostrada en la figura 4.3 adjunta; se debe considerar
que la capacidad de produccin supera a la capacidad de almacenamiento, la que a su vez es igual
a la demanda. Por otra parte no hay restricciones de flujo por los ductos.
Figura 4.3
Primero, se deben definir las variables que vamos a utilizar, stas sern
Xij: Cantidad de producto enviado del punto (o nodo) i al punto j.
Funcin Objetivo: Minimizar Z = (2*X13 + 3*X14 + 5*X15 + 4*X23 + 3*X24 + 2*X25 +
8*X36 + 4*X37 + 5*X38 + 7*X46 + 9*X47 + 9*X48 + 6*X49 + 9*X57 + 7*X58 + 8*X59)
1
2
3
4
5
6
7
8
9
PRODUCCIN ALMACENAMIENTO DEMANDA
-
Restricciones: Estas se analizarn para cada una de las reas.
1. Flujos entre Produccin y Almacenamiento, limitados por produccin
X13 + X14 + X15 200000
X23 + X24 + X25 200000
2. Flujos entre Produccin y Almacenamiento, limitados por almacenamiento
X13 + X23 = 175000
X14 + X24 =125000
X15 + X25 = 75000
3. Flujos entre Almacenamiento y Demanda, limitados por almacenamiento
X36 + X37 + X38 = 175000
X46 + X47 + X48 + X49 =125000
X57 + X58 + X59 =75000
4. Flujos entre Almacenamiento y Demanda limitados para satisfacer demanda
X36 + X46 = 100000
X37 + X47 + X57 = 75000
X38 + X48 + X58 = 75000
X49 + X59 = 125000
Mathprog nos entrega usando Programacin Lineal los siguientes valores en unidades de galones:
X13 = 175.000, X14 = 25.000, X15 = 0, X23 = 0, X24 = 100.000, X25 = 75.000, X36 = 25.000,
X37 = 75.000, X38 = 75.000, X46 = 75.000, X47 = 0, X48 = 0, X49 = 50.000, X57 = 0, X58 = 0
y X59 = 75.000 (comparar con la cifra indicada sobre cada una de las flechas de la figura 4.2) El
Z* = 3.175.000; considerando que la unidad monetaria usada en la FO son centavos de US$,
entonces tenemos un Z* = US$ 31.750.
La primera restriccin tiene una holgura de cero, mientras que la segunda de 25.000 galones.
-
4.2.4 PROBLEMA DEL CAMINO MS CORTO
Este problema tambin es llamado de la ruta ms rpida o ms barata, ya que depender de si se
trata de distancia, tiempo o dinero lo que se est minimizando.
La situacin consiste en un nodo fuente y un nodo de destino, enlazados a travs de una red con
flechas que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, impuestos,
peajes, etc.
La idea es buscar la ruta ptima, que minimice el atributo definido.
Ejemplo. Considere el siguiente diagrama (figura 4.4) asumiendo que los nmeros asignados a
cada una de las flechas representan las distancias de un nodo a otro. Se pide la ruta con la
distancia mnima para ir del nodo 1 al nodo 8.
Figura 4.4
Para obtener la ruta ms corta en forma trivial, se pueden determinar las distancias totales de
todas las rutas posibles y se elige la menor; as tenemos en este caso las siguientes alternativas
posibles:
RUTA 1-2-5-7-8 = 4 + 8 + 17 + 9 = 38
RUTA 1-3-4-7-8 = 3 + 12 + 20 + 9 = 44
RUTA 1-3-4-8 = 3 + 12 +15 = 30
RUTA 1-3-4-6-8 = 3 + 12 + 2 + 22 = 39
RUTA 1-3-6-8 = 3 + 4 +22 = 29
Luego, se elige la ruta 1-3-6-8 porque es la que tiene asociada la menor distancia (29).
Desde el punto de vista de la PEB se puede plantear de la siguiente forma:
8
20 9
22 2 4
12 3
4
1
3
2 5 7
8
6
4 15
17
-
MIN Z = 4X12 + 3X13 + 8X25 + 12X34 + 4X36 + 17X57 + 20X47 + 2X46 + 15X48 + 22X68
+ 9X78
X12 + X13 = 1
X12 X25 = 0
X13 X34 X36 = 0
X25 X57 = 0
X34 X47 X48 X46 = 0
X36 + X46 X68 = 0
X57 + X47 X78 = 0
X78 + X48 + X68 = 1, con Xij = { 0, 1}
Resultan X13 = X36 = X68 = 1, y el resto a nivel cero. Se obtiene Z* = 29, valor igual al ya
obtenido mediante el anlisis de las cinco rutas alternativas posibles.
Alternativamente podemos determinar la ruta ms corta avanzando hacia la derecha en la red por
una ruta cualquiera a partir del nodo origen y acumulando la distancia hasta llegar a un nodo en
que lleguen dos o ms flechas; en dicho nodo se debe considerar la menor distancia acumulada
para continuar; usando la figura 4.5 adjunta se pide al lector usar este sencillo algoritmo.
Figura 4.5
8
20 9
22 2 4
12 3
4
1
3
2 5 7
8
6
4 15
17
-
4.2.5 PROBLEMA DEL FLUJO MXIMO
Este tipo de problemas es similar al anteriormente tratado, pero ahora se busca determinar el flujo
mximo entre un nodo fuente y un nodo de destino, los que estn enlazados a travs de una red
con flechas de capacidad finita, tal como se presenta en la siguiente figura 4.6 adjunta.
Figura 4.6
Los nmeros asignados a cada una de las flechas representan los flujos mximos o capacidades
correspondientes.
Un mtodo para solucionar este problema es determinar el corte con el flujo mnimo (anlogo al
cuello de botella de una carretera o el eslabn ms dbil de una cadena)
Para realizar lo anteriormente sealado, se hacen cortes a travs de la red, que separen la
red en dos mitades, con el nodo fuente en una mitad y el de destino en la otra.
El corte que tenga el menor flujo asociado determina el flujo mximo, ya que nos permite
detectar el corte cuello de botella con las correspondientes flechas.
Esta metodologa se muestra aplicada a continuacin
10
18
40 9 25
9
15
4
20
5
7
1
5
2 3
7
8 6 4
-
Se realiza un corte a la red, tal como se ve en la figura 4.7 adjunta.
Figura 4.7
El corte mostrado tiene el menor flujo (32) entre todos los cortes posibles, por lo que determina el
flujo mximo entre el nodo fuente y el nodo de destino.
Desde el punto de vista de la PE podemos plantear la situacin de la siguiente forma:
Restricciones de flujo en las flechas:
X12 7; X14 25; X15 5; X46 9; X56 4;
X23 10; X43 20; X57 15; X38 18; X68 40; X78 9
Balance de flujo en los nodos:
X12 = X23
X14 = X43 + X46
X15 = X56 + X57
X23+X43 = X38
X46 + X56 = X68
X57 = X78
MAX Z = X12 + X14 + X15; alternativamente MAX Z = X38 + X68 + X78 (estas FO las
podemos asociar a cortes; cualquier corte nos sirve para determinar una FO alternativa).
Mathprog nos entrega usando Programacin Lineal los siguientes valores: X12 = 7, X15 = 5, X46
= 9, X23 = 7, X57 = 1, X68 = 13, X14 = 20, X56 = 4, X43 = 11, X38 = 18, X78 = 1 como
flujo para cada uno de los arcos con Z* = 32.
18
40 9 25
9
15
4
20
5
7
1
5
2 3
7
8 6 4
Corte
10
-
4.3 ANEXOS
4.3.1 EJERCICIOS PROPUESTOS
1.- Considerar el siguiente problema de envo de bienes desde 3 bodegas a 4 puntos de venta.
Los costos de envo, las cantidades disponibles en las bodegas (fuentes) y las demandas en
los puntos de venta (destinos) se presentan a continuacin. La bodega A tiene 125 unidades
para abastecer, mientras la B tiene 60 y la C 75. los puntos de venta 1, 2, 3 y 4 por su parte
requieren 40, 55, 85 y 60 unidades respectivamente. El costo de enviar una unidad desde
cada uno de los puntos de abastecimiento a cada uno de los puntos de venta se presenta en la
siguiente tabla resumen.
DESTINOS
1 2 3 4 Abastecimiento
FUENTES
A $20 $18 $12 $19 125
B $25 $16 $17 $21 60
C $18 $23 $19 $18 75
Demanda 40 55 85 60 240 \ 260
Cabe destacar que la cantidad total que se puede abastecer (260 unidades) es mayor a lo
demandado.
El problema de toma de decisin consiste en modelar el problema como problema de
transporte para determinar el nmero de unidades enviadas desde cada una de las fuentes a
cada uno de los destinos, de tal manera de minimizar el costo total (transporte y bodegaje);
las unidades sobrantes se deben enviar a una bodega de artculos rezagados, con un costo de
transporte unitario de $10, $20 y $15 (segn el artculo venga de A, B, C) y un costo
unitario de almacenamiento de $5 que se debe considerar. Una vez modelado este problema,
considerar su solucin con Mathprog, usando The Transportation Problem.
Alternativamente considerar su solucin con Mathprog, usando General Linear
Programming.
-
2.- La misma situacin ya planteada en el prrafo 4.2.1 con demanda > oferta, pero por cada
unidad deficitaria en el cliente A se paga una multa de $100. Resolver con Mathprog usando
General Linear Programming, y The Transportation Problem; comparar con el resultado
obtenido sin multa.
Para resolver con The Transportation Problem se debe modelar previamente como problema
de transporte.
Requerimientos de Clientes
A
(4)
B
(4)
C
(5)
D
(6)
TOTAL
19
Disponibilidad
De Bodega
X (2) $130 $110 $150 $200
Y (6) $170 $140 $120 $130
Z (7) $180 $180 $150 $120
TOTAL 15
3.- Estudie la factibilidad de modelar el problema planteado para transbordo como problema de
transporte; de ser factible, resulvalo usando Mathprog, The Transportation Problem.
4.- Usando el Mathprog, programacin entera binaria (solucin automtica o interactiva),
resuelva el modelo planteado para determinar el camino ms corto, pero determinando el
camino ms largo.
NOTA: MATHPROG puede tener limitaciones con la cantidad de variables o de
restricciones en alguno de los tres ltimos problemas.
-
4.3.2 BIBLIOGRAFA
(1) CAPTULOS 8 Y 9 DE INVESTIGACIN DE OPERACIONES POR F. HILLIER Y G.
LIEBERMAN, SPTIMA EDICIN.
(2) SUPLEMENTO PAGS. 323 A LA 329 ADMINISTRACIN DE OPERACIONES POR R.
SCHROEDER, TERCERA EDICIN.
(3) CAPTULO 6 DE INVESTIGACIN DE OPERACIONES EN LA CIENCIA
ADMINISTRATIVA POR G. EPPEN, F. GOULD, C. SCHMIDT, J. MOORE, L.
WEATHERFORD, QUINTA EDICIN.
(4) CAPTULO 13 DE QUANTITATIVE ANALYSIS FOR BUSINESS DECISIONS POR H.
BIERMAN, C. BONINI Y W. HAUSMAN, OCTAVA EDICIN.
(5) CAPTULO 8 DE OPTIMIZACIN Y MODELOS PARA LA GESTIN DE CARMEN
ORTIZ, SAMUEL VARAS Y JORGE VERA. ESTE TEXTO FUE ESCRITO POR
CHILENOS, EDITADO E IMPRESO EN CHILE.
(6) DIRECCIN DE OPERACIONES ASPECTOS TCTICOS Y OPERATIVOS EN LA
PRODUCCIN Y LOS SERVICIOS
DE J. A. DOMNGUEZ, M. J. ALVAREZ, S. GARCIA, M. A. DOMNGUEZ, A. RUIZ.
(7) MODELACION DE SISTEMAS DE DISTRIBUCIN DE CARGA DE RODRIGO
GARRIDO H. ESTE LIBRO ES DE EDICIONES UNIVERSIDAD CATLICA DE
CHILE.