Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

Un avión de carga tiene tres compartimentos para almacenar su carga, frontal, central y trasero, con los siguientes límites máximos de capacidad, en peso y en volumen:

Compartimento  Peso (Tm)  Volumen (m3)
Frontal              10          6800
Central              16          8700
Trasero               8          5300

Además, para mantener el balance adecuado del avión, el peso de la carga en los tres compartimentos debe mantener la misma proporción que sus límites de capacidad de carga en peso.

Para el siguiente vuelo, se dispone de las siguientes mercancías a embarcar:

Mercancía   Peso (Tm)   Volumen (m3/Tm)  Valor (€/Tm)
M1                18              480            310
M2                15              650            380
M3                23              580            350
M4                12              390            285

El objetivo es determinar qué cantidad de cada mercancía debe embarcarse y cómo distribuirla en los compartimentos de forma que el valor total de la mercancía embarcada sea máximo.

Puede suponerse que cada mercancía puede fraccionarse, si se precisa, en cualquier proporción y que puede repartirse entre dos o más compartimentos, si se desea.

Nuestro avión

 

Solución

  • Hay que decidir qué cantidad de cada mercancía debe ponerse en cada compartimento. Sea:

xij el número de toneladas de mercancía Mi (i=1,2,3,4) que va a ponerse en el compartimento j (j=1 para Frontal, j=2 para Central y j=3 para Trasero), con xij ≥ 0 para i=1,2,3,4; j=1,2,3.

  • No puede cargarse más cantidad de cada mercancía que la disponible:

x11 + x12 + x13 <= 18
x21 + x22 + x23 <= 15
x31 + x32 + x33 <= 23
x41 + x42 + x43 <= 12

  • Hay que respetar la capacidad en peso de cada compartimento:

x11 + x21 + x31 + x41 <= 10
x12 + x22 + x32 + x42 <= 16
x13 + x23 + x33 + x43 <= 8

  • Hay que respetar la capacidad en volumen de cada compartimento:

480 x11 + 650 x21 + 580 x31 + 390 x41 <= 6800
480 x12 + 650 x22 + 580 x32 + 390 x42 <= 8700
480 x13 + 650 x23 + 580 x33 + 390 x43 <= 5300

  • El peso de la carga en los tres compartimentos debe mantener la misma proporción que sus límites de capacidad de carga en peso:

(x11 + x21 + x31 + x41)/10 =

= (x12 + x22 + x32 + x42)/16 =

= (x13 + x23 + x33 + x43)/8

  • El objetivo es maximizar el valor total de la carga:

maximizar 310 (x11+ x12x13) +

+ 380 (x21+ x22+ x23) +

+ 350 (x31+ x32+ x33) +

+ 285 (x41+ x42+ x43)

En esta asignatura veremos cómo resolver este tipo de problemas para, en el caso que nos ocupa, llegar a obtener la siguiente solución óptima (calculada con esta herramienta en línea) (nueva versión):

x11 = 0, x12 = 0, x13 = 0, x21 = 7, x22 = 0, x23 = 8, x31 = 3, x32 = 12.9474, x33 = 0, x41 = 0, x42 = 3.05263, x43 = 0

Valor total óptimo de la carga: 12151.6 €

 

2 respuestas

Muchas gracias por la explicación, sin embargo tengo una duda. Por qué no se tiene en cuenta como restricción el volumen de cada pedido?

Simplemente porque el problema tratado aquí es más sencillo. No se consideran pedidos, sólo se considera el problema de maximizar el valor de la carga contenida en el avión. Se supone que el objetivo es transportar la carga a un almacén intermedio, situado en una ciudad determinada, desde la que posteriormente se satisfarán pedidos más pequeños por otros medios (carretera, por ejemplo).

Comentarios