Knapsack problem
Páginas: 7 (1719 palabras)
Publicado: 17 de diciembre de 2011
30-nov-2011
Aplicación en:
Industria. Economía.
Embalaje.
Almacenamiento. Corte de piezas. Criptografía.
El problema de la mochila consta de las siguientes variables involucradas:
pj; beneficio de elemento j. wj: peso de elemento j. xj: variable binaria que indica si se ingresa
elemento j a la mochila. c: capacidad total de la mochila.
Figura1. Problema de la mochila, objetos peso beneficio.
Restricción con múltiples mochilas. A este problema se le llama multidimensional knapsack problem.
wj es entero positivo. Lo mismo ocurre con pj y c i.
Los elementos se pueden ordenar de la siguiente manera:
Se permite que wij = 0 para algún i,j, siempre que:
M
válido para todos los elementos j= 1,…, n Al menos se debe dar esta opción para la matriz de pesos. j
W=
1 0 0 0 0 suma = 1
1 1 1 1 1 …
… … 1 … … …
… … … 1 … …
… … … … 1 …
El cálculo de los límites inferior y superior nos permite obtener valores aproximados a la solución óptima.
Dos técnicas se emplean generalmente para obtener los límites superiores para el problema MKP. La relajación sustituta y larelajación Langrangiana.
Tenemos un vector de multiplicadores positivo (∏1,…, ∏m), como la relajación sustituta estándar, S(MKP, ∏) de MKP es:
Teniendo un vector de multiplicadores no negativo (λ1,…,λn). La relajación Langrangiana L(MKP, λ) es:
Para calcular polinómicamente los límites superiores para MKP. Tenemos lo siguiente:
Entonces la proporción define elsiguiente teorema:
Elemento critico relativo de la mochila i (i pertenece M) definido como :
La única variable fraccionaria en la solución es , con . El valor de la solución:
Para resolver el problema de la mochila por fuerza bruta se necesita al menos:
O(2nm), siendo n el número de elementos
disponible para colocar en la mochila, m el valor del calculo del métodosimplex. Analizando el algoritmo de backtracking en el peor de los casos se debe recorrer el árbol completo. Una especificación de este algoritmo es el de branch and bound el cual tiene una complejidad similar.
Definición: Sea ∏1 y ∏2 dos problemas conocidos. Se puede decir que ∏1 se puede reducir a ∏2 (notación ∏1 ∝ ∏2) cada vez que una instancia I1 de ∏1 puede ser transformada entiempo polinómico en una instancia I2 de ∏2 de tal manera que I1 es una instancia-’si’ de ∏1 si y solo si I2 es una instancia-’si’ de ∏2.
A grandes rasgos, esta definición dice que ∏1 es un caso especial de ∏2. Por lo tanto, si ∏1 ∝ ∏2, entonces existe un algoritmo polinómico que transforma una instancia de ∏1 en una instancia de ∏2, que no cambia el resultado.
El Problema de lapartición (Karp 1972) es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede éste ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma.
Problema Partición:
El problema puede ser visto de la siguiente forma: Tenemos n elementos enterospositivos x1,x2,…,xn. De manera que existe un conjunto S ⊂ {1,…,n} tal que
El problema de la mochila lo podemos definir como: Tenemos t+1 enteros positivos x1,…,xt y c. Existe un conjunto S ⊂ {1,…,t} sujeto a:
Se puede decir que el problema de Partición ∝ Problema de la mochila. Supongamos I=(x1,…,xn) es una instancia de la partición. Haciendo la siguiente instancia para lamochila: Tomemos t =n, aj = 2xj para j = 1,2,…,t y c:= . Entonces tenemos que esta mochila es ‘si’ y solo si I es una instancia-’si’ de la partición. Y esta transformación se puede realizar en tiempo polinómico.
Con esta restricción el problema de la mochila y el de la partición es el mismo. El problema de la mochila corresponde a un problema np-completo ya que se puede transformar en un...
Aplicación en:
Industria. Economía.
Embalaje.
Almacenamiento. Corte de piezas. Criptografía.
El problema de la mochila consta de las siguientes variables involucradas:
pj; beneficio de elemento j. wj: peso de elemento j. xj: variable binaria que indica si se ingresa
elemento j a la mochila. c: capacidad total de la mochila.
Figura1. Problema de la mochila, objetos peso beneficio.
Restricción con múltiples mochilas. A este problema se le llama multidimensional knapsack problem.
wj es entero positivo. Lo mismo ocurre con pj y c i.
Los elementos se pueden ordenar de la siguiente manera:
Se permite que wij = 0 para algún i,j, siempre que:
M
válido para todos los elementos j= 1,…, n Al menos se debe dar esta opción para la matriz de pesos. j
W=
1 0 0 0 0 suma = 1
1 1 1 1 1 …
… … 1 … … …
… … … 1 … …
… … … … 1 …
El cálculo de los límites inferior y superior nos permite obtener valores aproximados a la solución óptima.
Dos técnicas se emplean generalmente para obtener los límites superiores para el problema MKP. La relajación sustituta y larelajación Langrangiana.
Tenemos un vector de multiplicadores positivo (∏1,…, ∏m), como la relajación sustituta estándar, S(MKP, ∏) de MKP es:
Teniendo un vector de multiplicadores no negativo (λ1,…,λn). La relajación Langrangiana L(MKP, λ) es:
Para calcular polinómicamente los límites superiores para MKP. Tenemos lo siguiente:
Entonces la proporción define elsiguiente teorema:
Elemento critico relativo de la mochila i (i pertenece M) definido como :
La única variable fraccionaria en la solución es , con . El valor de la solución:
Para resolver el problema de la mochila por fuerza bruta se necesita al menos:
O(2nm), siendo n el número de elementos
disponible para colocar en la mochila, m el valor del calculo del métodosimplex. Analizando el algoritmo de backtracking en el peor de los casos se debe recorrer el árbol completo. Una especificación de este algoritmo es el de branch and bound el cual tiene una complejidad similar.
Definición: Sea ∏1 y ∏2 dos problemas conocidos. Se puede decir que ∏1 se puede reducir a ∏2 (notación ∏1 ∝ ∏2) cada vez que una instancia I1 de ∏1 puede ser transformada entiempo polinómico en una instancia I2 de ∏2 de tal manera que I1 es una instancia-’si’ de ∏1 si y solo si I2 es una instancia-’si’ de ∏2.
A grandes rasgos, esta definición dice que ∏1 es un caso especial de ∏2. Por lo tanto, si ∏1 ∝ ∏2, entonces existe un algoritmo polinómico que transforma una instancia de ∏1 en una instancia de ∏2, que no cambia el resultado.
El Problema de lapartición (Karp 1972) es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede éste ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma.
Problema Partición:
El problema puede ser visto de la siguiente forma: Tenemos n elementos enterospositivos x1,x2,…,xn. De manera que existe un conjunto S ⊂ {1,…,n} tal que
El problema de la mochila lo podemos definir como: Tenemos t+1 enteros positivos x1,…,xt y c. Existe un conjunto S ⊂ {1,…,t} sujeto a:
Se puede decir que el problema de Partición ∝ Problema de la mochila. Supongamos I=(x1,…,xn) es una instancia de la partición. Haciendo la siguiente instancia para lamochila: Tomemos t =n, aj = 2xj para j = 1,2,…,t y c:= . Entonces tenemos que esta mochila es ‘si’ y solo si I es una instancia-’si’ de la partición. Y esta transformación se puede realizar en tiempo polinómico.
Con esta restricción el problema de la mochila y el de la partición es el mismo. El problema de la mochila corresponde a un problema np-completo ya que se puede transformar en un...
Leer documento completo
Regístrate para leer el documento completo.