Programacion entera

Problema de la mochila
Este problema surge de distintas maneras, analizaremos la manera más sencilla.
Nos dan n objetos y una mochila. Para i=1,2,.., n, el objeto i tiene un peso positivo wi y un valor positivo vi. La mochila pude llevar un peso que no sobrepase W. nuestro objetivo es llenar la mochila de tal manera que se maximice el valor de los objetos transportados, respetando lalimitaron de capacidad impuesta. En esta primera versión del problema, suponemos que se pueden romper los objetos en trozos mas pequeños, de manera que podamos decidir solamente una fracción xi del objeto de i, con 0 x i 1(si no se nos permite romper los objetos, el problema es mucha más difícil) en este caso, el objeto i contribuye en xiwi al peso total de la mochila, y en xivi al valor de la carga. Ensímbolos, el problema se puede enunciar en la forma siguiente:
Maximizar i=1nxivi con la restricción i=1nxiwi≤W

Donde vi> o, wi >0 y 0 xi 1 para 1 i n. aquí las condiciones que afectan a vi y a wi son restricciones sobre el problema; las de xi son restricciones sobre la solución. Utilizaremos un algoritmo voraz para resolver el problema. En términos de nuestro problema en general,los candidatos son los diferentes objetos y la solución es un vector (xi,…, xn) que nos dice qué fracción de cada objeto hay que incluir. Una solución será factible cuando se respeten las restricciones indicadas anteriormente, y la función objetivo es el valor total de los objetos que están en la mochila. Queda por ver qué debemos tomar como función de selección.
Si i=0nwi≤W esta claro que looptimo es meter todos los objetos dentro de la mochila. Por tanto, podemos asumir que en los casos interesantes del problema, es i=0nwi>W. También esta claro que en una solución optima debe llenar exactamente la mochila, porque en caso contrario se podrá añadir una fracción de algunos de los objetos restantes o incrementar el valor de la carga. Por tanto, en una solución optima i=0nxiwi W.Puestoque esperamos que esperamos encontrar un algoritmo voraz que funcione, nuestra estrategia general consistirá en seleccionar cada objeto por turno en algún orden adecuado, poner la mayor fracción posible del objeto seleccionado de la mochila y detenernos cuando la mochila este llena. Se tiene el siguiente algoritmo
Función mochila(w[1…n],v[1…n],w): matriz[1…n]
{Inicialización}
Para i=0 hasta nhacer
X[i]0
peso0
{bucle voraz}
Mientras peso<N hacer
iel mejor objeto restante {ver mas abajo}
si peso+w[i]W entonces x[i] 1
pesopeso+w[i]
sino x[i] (W-peso)/w[i]
pesoW
devolver x
Para este problema hay por lo menos tres funciones de selección posibles: en cada fase, podemos seleccionar el objeto mas valioso, argumentando que esto incrementa el valor de la carga del modo másrápido posible, podemos seleccionar el objeto más pequeño restante, basándonos en que de este modo la capacidad se agota de la forma más lenta posible; o bien podemos evitar estos extremos seleccionando aquel objeto cuyo valor por unidad de peso sea el mayor posible. Las figuras a y b muestran la forma en que funcionan estas tácticas en un caso particular. Aquí tenemos 5 objetos y w=100.Siseleccionamos primero el objeto 3, luego el 5 y finalmente llenaremos la mochila con la mitad de objeto 4.el valor de la solución obtenida de esta manera es de 66+60+40/2=146. Si seleccionamos los objetos por orden de peso creciente, entonces seleccionaremos los objetos 1, 2,3 y 4 por este orden y la mochila estará llena. El valor de la solución es de 20+30+66+40=156. Finalmente, si seleccionamoslos objetos por orden creciente de vi/wi, entonces seleccionaremos primero el objeto 3, luego el objeto1, después el objeto 2, y finalmente llenaremos la mochila cuatro quintos del objeto 5. Empleando esta táctica, el valor de la solución es 20+30+66+0.8x60=164

n=5, W=100 |
w | 10 | 20 | 30 | 40 | 50 |
v | 20 | 30 | 66 | 40 | 60 |
v/w | 2.0 | 1.5 | 2.2 | 1.0 | 1.2 |

Figura a...