Maria Jose

Un montañista esta planeando una excursión muy especial. Evaluando la capacidad de su morral, la dificultad de la excursión, algunos implementos indispensables y sus fuerzas, cree que tiene en sumorral una capacidad de C E Z kilos (u otra unidad de peso, o de manera mas precisa, de masa) disponibles para alimentos. De acuerdo con su experiencia, sus necesidades y sus gustos ha escogido ni tiposde alimentos A1, A2,….An, todos más o menos equilibrados. Estos alimentos vienen en paquetes indivisibles (por ejemplo en lata) y pi E Z indica el peso de cada paquete del alimento Ai. Teniendo encuenta la composición de cada alimento, las calorías, las vitaminas, los minerales, el sabor, el contenido de agua, etc., el montañista asigno a cada paquete del alimento Ai un beneficio global bi.
Eneste problema se supone que no es obligación llevar paquetes de cada uno de los alimentos. También su supone que no hay cotas inferiores ni superiores para el numero de paquetes de cada alimento.
Talvez ningún montañista ha tratado de resolver este problema para organizar su morral, seguramente ni siquiera ha tratado de plantearlo. Lo que si es cierto es que hay muchos problemas, de gran tamaño yde mucha importancia, que tienen una estructura análoga. Hay libros y muchos artículos sobre este problema.
2 Planteamiento del Problema
Si xj indica el número de paquetes del alimento Aj que elmontañista debe llevar en
su morral, entonces se debe maximizar el beneficio, bajo ciertas restricciones:
j
n
j
j b x
1
max
, 1,.... .
1
x Z j n
p x C
j
j
n
j
j
Este problema se puederesolver por la fuerza bruta construyendo todas las
combinaciones, haciendo variar xj entre 0 y [C/pj], verificando si cada combinación
es factible.
p x C
n
j 1 j j
La función objetivo (lafunción que hay que maximizar) es lineal, la restricción
también el lineal, las variables deben ser enteras y se puede suponer que los
coeficientes bj y pj también son enteros. Entonces este problema...