ANOTACIÓN 2012 Serie 1 No 8: 27 de febrero,
2012
VIPERS:
Especificaciones para la primera generación de prototipos, cont.
Nota: Continuamos con nuestro afán
de definir modelos de sistemas cuya estructura es descrita y optimizaba con el modelo
matemático general conocido como la “programación lineal”. Se trata de un plan de
investigación y desarrollo de la primera generación de VIPERS proveyendo una colección
diversa de sistemas reales para definir la metodología diagramática de VIPERS en
términos de las necesidades del usuario real.
El “Problema
del Transporte” – Dos Variedades
Fuente: “An
Illustrated Guide to Linear Programming” de Saul I. Gass
El Problema del Transporte de Refrigeradores
El problema:
Un fabricante de refrigeradores tiene dos fábricas con las que
abastece a sus tres tiendas minoristas. Al principio de cada mes, el fabricante
recibe de cada gerente de las tiendas una lista de las ventas incumplidas que
deben ser completadas al mes siguiente con nueva producción. Este conjunto de
requisitos representa el número total de nuevos refrigeradores que deben ser
producidos por las dos fábricas. Para simplificar la discusión, suponemos que
el fabricante tiene bastantes recursos – mano de obra, materiales, etcétera – para
abastecer los requisitos, y en esta instancia, no tiene ninguna sobreproducción,
produciendo solamente para la venta; o sea, no tiene instalaciones para
almacenaje. (Nota: la producción misma
podría tratarse día un modelo matemático, pero nuestros intereses presentes
están en otra área.)
La tienda número uno del
fabricante, designada por T1, requieres 10 refrigeradores, T2
requiere 8, el T3 requiere 7,
para un total de 25 refrigeradores. El Presidente ha decidido producir 11 en la
fábrica número uno, F1, y las restantes 14 en F2. El
problema que deseamos considerar es cuantos refrigeradores deberían ser
enviados de cada fábrica a cada una de las tiendas para minimizar el costo
total del transporte de refrigeradores de las fábricas a las tiendas. La forma
básica de este problema, denominada el “problema del transporte”, es una de las
primeras y más empleadas formulaciones de la programación lineal.
Necesitamos información adicional
con respecto a las restricciones de transporte y costos. Se supone que es
posible enviar cualquier número específico de refrigeradores de cada fábrica a
cualquier tienda; o sea, algún medio de transporte – ferrocarril, avión, u otro – conecta a toda
fábrica a cualquiera de las tiendas. También suponemos un conocimiento de los
costos de envío de un refrigerador de una fábrica a una tienda. Aquí debemos
hacer una suposición de linealidad o proporcionalidad con respecto a estos
costos de transporte que es muy crítica – y en algunos casos bastante
debatible. Esta suposición de linealidad o proporcionalidad requiere que si el
costo de envío de un refrigerador de F1 a T1 sea de $10
entonces el costo de enviar dos refrigeradores sea de $20, y el costo de tres
sea $30, y así sucesivamente. Podemos debatir esta suposición basado en la
experiencia real, según la cual, por ejemplo, el costo inicial fijo de $100 de arrendar un camión para transportar un
refrigerador (descontando costos de manejo) seria tal que el costo individual de
transportar dos refrigeradores sería de $50 por cada uno, y el de transportar tres
refrigeradores sería de $33 1/3 por cada uno, o sea, una relación no lineal. No
obstante para lo presente problema vamos a suponer una linealidad o
proporcionalidad en los costos de transporte de cada uno de los refrigeradores.
Para este problema entonces
suponemos que el costo del transporte para un refrigerador desde una fábrica a
una tienda son cantidades conocidas y lineales. Estos costos se muestran en la
siguiente tabla:
|
Costos de Transporte por cada Refrigerador de cada una de las
dos fábricas a cada una de las tres tiendas
|
Tienda T1
|
Tienda T2
|
Tienda T3
|
|
Fábrica F1
|
$8
|
$6
|
$10
|
|
Fábrica F2
|
$9
|
$5
|
$7
|
Buscamos una solución que cumpla
con las restricciones del problema: o sea, 1) enviar 11 unidades de la fábrica F1
y enviar 14 unidades de la fábrica F2; 2) que la tienda T1 ese
uno recibe 10 unidades, la tienda T2 recibe 8 unidades, la tienda T3
recibe 7 unidades; y, 3) al mismo tiempo minimizar el costo total de transporte
de las fábricas a las tiendas. La siguiente tabla combina la información de la
tabla anterior con las restricciones descritas en el presente párrafo.
|
|
Tienda T1
|
Tienda T2
|
Tienda T3
|
|
|||
|
Fábrica F1
|
Costo de envío: $8
|
Número: ¿?
|
Costo de envío: $6
|
Número: ¿?
|
Costo de envío: $10
|
Número: ¿?
|
Unidades producidas: 11
|
|
Fábrica F2
|
Costo de envío: $9
|
Número: ¿?
|
Costo de envío: $5
|
Número: ¿?
|
Costo de envío: $7
|
Número: ¿?
|
Unidades producidas: 14
|
|
|
Total requeridas: 10
|
Total requeridas: 8
|
Total requeridas: 7
|
|
|||
En las celdas grises de la tabla
anterior queda por determinar el número de refrigeradores enviados de cada
fábrica a cada tienda. Para demostrar que un empleado cualquiera no tendría
dificultades en idear una solución aquí podemos asignar una serie de números
para calcular unos ejemplos de costos de transportes:
Ejemplo 1:
|
|
Tienda T1
|
Tienda T2
|
Tienda T3
|
|
|||
|
Fábrica F1
|
Costo de envío: $8
|
Número: 10
|
Costo de envío: $6
|
Número: 1
|
Costo de envío: $10
|
Número: 0
|
Unidades producidas: 11
|
|
Fábrica F2
|
Costo de envío: $9
|
Número: 0
|
Costo de envío: $5
|
Número: 7
|
Costo de envío: $7
|
Número: 7
|
Unidades producidas: 14
|
|
|
Total requeridas: 10
|
Total requeridas: 8
|
Total requeridas: 7
|
|
|||
Ejemplo 2:
|
|
Tienda T1
|
Tienda T2
|
Tienda T3
|
|
|||
|
Fábrica F1
|
Costo de envío: $8
|
Número: 0
|
Costo de envío: $6
|
Número: 7
|
Costo de envío: $10
|
Número: 4
|
Unidades producidas: 11
|
|
Fábrica F2
|
Costo de envío: $9
|
Número: 10
|
Costo de envío: $5
|
Número: 1
|
Costo de envío: $7
|
Número: 3
|
Unidades producidas: 14
|
|
|
Total requeridas: 10
|
Total requeridas: 8
|
Total requeridas: 7
|
|
|||
El lector no tendrá dificultades ideando
otros ejemplos. Los números escritos en cada celda apropiada de las tablas anteriores
de los dos ejemplos propuestos constituyen soluciones de acuerdo a las
especificaciones del problema, con un número total de refrigeradores enviados
desde las fábricas F1 y F2 a cada una las tiendas. En el
ejemplo número uno la fábrica F1 envía 10+ 1 + 0 = 11 refrigeradores a las tiendas T1,
T2 y T3 respectivamente, mientras que la fábrica F2
envía 0 + 7 + 7 = 14 refrigeradores a
las tiendas T1, T2 y T3 respectivamente. En el
segundo ejemplo, la fábrica F1 envía: 0 + 7 + 4 = 11 refrigeradores
a las tiendas T1, T2 y T3 respectivamente,
mientras que la fábrica F2 envía: 10 + 1 + 3 = 14 refrigeradores a
las tiendas T1, T2 y T3 respectivamente. A su
vez en cada ejemplo el número total de refrigeradores recibidos por las tiendas
T1, T2 y T3 está de acuerdo a las
especificaciones del problema: 10, 8, y 7 respectivamente. Suponiendo una
linealidad (o proporcionalidad) en el costo del transporte en cada caso, el
costo total para las primeras soluciones se calcula mediante las siguientes
expresiones.
Ejemplo 1: $8 x 10 + $6 × 1 + $5 × 7 + $7 × 7 = $170.
Ejemplo 2: $6 x 7 + $10 x 4 + $9 x 10 + 5 + $5 x 1 + $7 × 7 = 198.
Para las soluciones presentadas la
primera tiene un costo menor. Queda por descubrir
si existe otra solución factible de aún menor costo. Un expedidor no empleando
las técnicas de programación lineal para ayudarle en resolver el problema debe confiar
fuertemente en su experiencia e intuición y no comprara exhaustivamente todas
las soluciones posibles – tampoco emplea la metodología de la programación
lineal. Un expedidor escoge una solución en particular pero no puede garantizar
absolutamente que tenga la solución más económica. El enfoque de la programación
lineal ofrece una garantía incondicional de que el costo mínimo será determinado.
Para el problema del transporte de los
refrigeradores la primera solución es la más óptima.
Para continuar con el desarrollo
de un modelo matemático del transporte y para simplificar la discusión unas
abreviaciones matemáticas son necesarias. Dejemos que x11 sea el número
desconocido de refrigeradores para ser enviados de la fábrica F1 a
la tienda T1; x12 el número desconocido de refrigeradores
para ser enviados de la fábrica F1 a la tienda T2, etc.
En general xij representa el número desconocido de refrigeradores
para ser enviados desde la fábrica Fi a la tienda Tj.
Aplicando estas anotaciones a la estructura de la tabla empleada anteriormente,
nos quedamos con:
|
|
Tienda T1
|
Tienda T2
|
Tienda T3
|
|
|||
|
Fábrica F1
|
$8
|
x11
|
$6
|
x12
|
$10
|
x13
|
Unidades: 11
|
|
Fábrica F2
|
$9
|
x21
|
$5
|
x22
|
$7
|
x23
|
Unidades: 14
|
|
|
Total requeridas: 10
|
Total requeridas: 8
|
Total requeridas: 7
|
|
|||
En total enviado de la fábrica F1
es 11 y los las cantidades en día desde F1 a las tres tiendas son X11,
X12, y X13, respectivamente. Similarmente el total
enviado desde F2 es 14 y los envíos desde F2 son X21,
X22, y X23. Puesto que el fabricante requiere un total de
25 unidades (10 + 8 + 7) y puesto que están fabricando exactamente 25 unidades
(11 + 14), el total fabricado en cada fábrica debe ser enviado a las tiendas.
El total enviado por F1 se describe por la siguiente ecuación:
F1 = x11 + x12 + x13 = 11.
Y el total enviado decir desde F2 es:
F2 =
x21 + x22 + x23 = 14.
Estas cifras son obtenidas al sumar cada fila de la tabla anterior.
Puesto que cada tienda deberá recibir exactamente el número de refrigeradores pedidos,
las cantidades enviadas a cada tienda – se encuentran al sumar las columnas – son
descritas por las siguientes ecuaciones:
x11 + x21 = 10 para la tienda T1;
y
x12 + x22 = 8 para la tienda T2;
y
x13 + x23 = 7 para la tienda T3.
Para cualquiera de los números xij, la i representa cada
una de las fábricas y la j cada una de las tiendas; el costo total – la suma de
los costos de cada uno de los envíos individuales – de igual a:
$8x11
+ $6x12 + $10x13 + $9x21 + $5x22 + $7x23.
Estas ecuaciones representan las
restricciones básicas del modelo matemático. El único elemento que falta es que
debemos limitar los valores posibles de xij a valores positivos o a cero.
Una xij negativa representaría un envío de refrigeradores de la
tienda a la fábrica; o sea, representaría que sería introducida una fuente de
refrigeradores además de aquellas producidas en la fábrica. Eliminamos esta
posibilidad al restringir x11 >= 0, x12 >=
0… x23 a >= 0, o en
general la anotación, xij >= 0. Estas son las restricciones de no
negatividad de la programación lineal. Puesto que queremos determinar el
conjunto de números xij que satisface las ecuaciones, las
restricciones de no negatividad y que minimicen el costo total, debemos tener el
siguiente modelo matemático – el modelo de programación lineal de este problema
del transporte:
Encuentra el conjunto de números xij > = 0 que minimicen:
$8x11
+ $ 6x12 + $10 x13 + $9x21 + $5x22
+ $7x23.
Sujeto a las siguientes restricciones:
TABLA DE RESTRICCIONES PARA RESOLVER EL PROBLEMA DEL TRANSPORTE
DE REFRIGERADORES
|
|||||||
|
x11
|
x12
|
x13
|
x21
|
x22
|
x23
|
|
|
|
x11
|
+ x12
|
+ x13
|
|
|
|
=
|
11
|
|
|
|
|
x21
|
+ x22
|
+ x23
|
=
|
14
|
|
x11
|
|
|
+ x21
|
|
|
=
|
10
|
|
|
x12
|
|
|
+ x22
|
|
=
|
8
|
|
|
|
x13
|
|
|
+ x23
|
=
|
7
|
La primera solución ofrecida
satisface estas ecuaciones, donde x11= 10, x12 = 1, x13 = 0, x21=
0, x2= 7, y x23 = 7,,
y como se indicó en anteriormente, la solución minimiza la función objetiva con
un valor de $170.
Cada fábrica o tienda
contribuyeron una ecuación en términos de las variables relacionadas a la
fábrica o tienda correspondiente. Las funciones objetivas son ecuaciones
lineales puesto que son simplemente sumas de las variables. El número total de
variables es el producto del número de fábricas y el número de tiendas; en este
caso 2 × 3 = 6. También, el número de ecuaciones es la suma del número de
fábricas y del número de tiendas; aquí es cinco. Los problemas de transporte
puede ser muy grandes, pero los procedimientos computacionales – algoritmos – para
resolver problemas más bien grandes están disponibles para la mayoría de los
computadores electrónicos.
Desde un punto de vista matemático
hay un número de puntos que deberían ser indicados sobre el sistema de
ecuaciones anterior. Para comenzar, hay una ecuación de más en el sentido de
que una de ellas está implícita por las restantes. Por ejemplo, podemos dejar aparte
la primera ecuación, ya que puede lograrse sumando las últimas tres después
restando la segunda. Otro punto importante, sin embargo, es que si resolvemos
el programa usando los procedimientos computacionales normales de la de
programación lineal, determinaremos una solución óptima cuyos valores de las
variables, las xijs consisten de números enteros. Se supone
tácitamente que las xijs deberían ser números enteros – no podemos
enviar 3 y ¾ partes de un refrigerador…
Aunque hemos descrito este modelo
de programación lineal en términos de fábricas, tiendas, y refrigeradores, es
muy importante reconocer que lo podíamos haber representado de una forma más
general tratando de orígenes (fábricas), destinos (tiendas), unidades
homogéneas para ser enviadas (refrigeradores), y alguna medida para hacer
minimizado (el costo total de transporte). Esto nos lleva a la siguiente que
ilustra este punto y ofrece otro modelo de programación lineal, es decir, otro
ejemplo de la programación lineal aplicado también al denominado modelo del
transporte.
El Problema del Transporte entre Bases Aéreas.
Este tipo de problema transporte
requiere el envío de un ítem desde un grupo de depósitos de las fuerzas aéreas
americanas a un grupo de estaciones de recepción. Cada depósito tiene una
cantidad limitada de ese ítem. Hay muchas rutas que abastecerían cada estación
de recepción con exactamente el número requerido de este ítem. El problema es
determinar la ruta que no solamente cumpla con los requerimientos, sino también
que minimice alguna medida del costo. Por ejemplo, el objetivo podría ser
minimizar uno de los siguientes: el costo total en dólares, el número total de
millas en el horario de envío, o el tiempo total que los ítems están en
tránsito. Y aparte supongamos que la base de la fuerza aérea de Lockbourne en
Columbus, Ohio, ha estado probando un ítem
grande de equipo, pesando una tonelada, para el B-52. Ahora se precisa que este
equipo sea probado en otras bases. Cinco son requeridos en la base de aérea de
March en Riverside, California; en Davis-Mountain en Tucson, Arizona; y McConnell
en Wichita, Kansas. La base aérea de Pinecastle en Orlando, Florida, y la base aérea
de MacDill en Tampa Florida cada una precisa de tres. Para abastecer estos 21
ítems, Lockbourne en Columbus, Ohio puede enviar ocho; el depósito de Oklahoma City
tiene 8; y Warner-Robins en Macon, Georgia tiene 5. Los ítems del equipo deben
ser transportados por aire a su destino. Toda la anterior información, junto
con las distancias aéreas aproximadas, están representadas en la tabla siguiente:
|
Ciudad
|
Ítems Disponibles
|
Ítems requeridos
|
||||
|
MacDill
3
|
March
5
|
Davis-Monthan
5
|
MacConnell
5
|
Pinecastle
|
||
|
Oklahoma City
|
8
|
938
|
1030
|
824
|
136
|
995
|
|
Macon
|
5
|
346
|
1818
|
1416
|
806
|
296
|
|
Columbus
|
8
|
905
|
1795
|
1590
|
716
|
854
|
ß Distancias en
millas à
Aquí el objetivo es de minimizar el total de millas por tonelada. La
solución óptima en términos de este objetivo es la calculada y se ofrece más
adelante. Será instructivo para el lector intentar encontrar la ruta más
eficiente por su cuenta.
Un primer intento hacia la
solución podría ser algo así: intentar cumplir cada encargo desde el depósito
más próximo. Dejemos que MacConnell reciba sus 5 ítems y Davis-Monthan 3 de sus
5 ítems de Oklahoma City. Los requisitos de las bases de Florida deberían
cumplirse, en cuanto sea posible, desde Macon. Dejemos que Pinecastle reciba sus
3 y MacDill reciba 2 de sus 3 ítems desde Macon. El resto de los requisitos deberán cumplirse desde
Columbus. Este ejemplo de horario de envío tiene un costo total de 17,792
millas-toneladas, de acuerdo a la siguiente tabla:
La primera solución descrita arriba
se resume a continuación en la siguiente tabla:
|
Ciudad
|
Ítems Disponibles
|
Ítems requeridos
|
||||
|
MacDill
3
|
March
5
|
Davis-Monthan
5
|
MacConnell
5
|
Pinecastle
3
|
||
|
Oklahoma City
|
8
|
0
|
0
|
3
|
5
|
0
|
|
Macon
|
5
|
2
|
0
|
0
|
0
|
3
|
|
Columbus
|
8
|
1
|
5
|
2
|
0
|
0
|
Hay muchos otras posibles rutas. La solución mínima obtenida por
los métodos de programación lineal, con un valor de 16,864 millas-toneladas.
La programación lineal garantiza que el mínimo se ha logrado:
|
Ciudad
|
Ítems Disponibles
|
Ítems requeridos
|
||||
|
MacDill
3
|
March
5
|
Davis-Monthan
5
|
MacConnell
5
|
Pinecastle
3
|
||
|
Oklahoma City
|
8
|
0
|
3
|
5
|
0
|
0
|
|
Macon
|
5
|
3
|
0
|
0
|
0
|
2
|
|
Columbus
|
8
|
0
|
2
|
0
|
5
|
1
|
No hay comentarios:
Publicar un comentario