Quiero saber sobre el problema de las mochilas de viaje en la investigación de operaciones. ¡Gracias!

El problema de la mochila es un problema muy famoso. Se puede describir de la siguiente manera. Supongamos que hay n elementos, indicados como d1, d2, d3,... dn. Para cada elemento di (1=lt; i=lt; n), su peso es wi y su valor es vi. Ahora se requiere llenar la mochila con un subconjunto de estos n artículos para que su peso total no exceda el límite de peso TOT dado y el valor de la mochila sea lo más alto posible.

1. Mochila de números reales

Algunos artículos se pueden colocar en la mochila, así que sea codicioso y coloque los artículos en orden ascendente de rentabilidad (v[i]/ w[i]) Esa es la solución óptima.

Complejidad O(n nlogn)

2. Mochila entera

Los artículos solo se pueden colocar en la mochila en su conjunto y no se permite desmontarlos. Para solucionarlo se utiliza programación dinámica.

dp[i, j] representa la solución óptima que se puede obtener colocando los primeros i artículos en una mochila con capacidad j.

Ecuación de transición de estado: dp[i,j]=max{dp[i-1,j], dp[i-1,j-w[i]] v[i]}

Complejidad O(nm)

3. Múltiples mochilas

A diferencia de 1 y 2, aquí hay k mochilas, cada mochila tiene una capacidad diferente y las demás son iguales. .

No hay mejor manera que buscar.

Para cada elemento i, enumera si se puede colocar en la mochila j o no.

Complejidad O(kn)

Se pueden adoptar diferentes podas para diferentes preguntas.

El modelo matemático del problema de la mochila es (debido a problemas de entrada, es difícil ingresar la especificación del subíndice, como 1 en c1 es un subíndice, tenga en cuenta)

maxZ =c1x1 c2x2 ... cnxn

w1x1 w2x2 ... wnxnlt;=W

xigt;=0, y es un número entero, i=1, 2,... , n

En la fórmula:

ck es el valor unitario del k-ésimo artículo, wk es el peso o volumen unitario del k-ésimo artículo y W es el límite de peso o volumen de la mochila.

Los elementos relevantes de la programación dinámica son los siguientes:

Fase k: carga k-ésima del elemento k-ésimo (k=1, 2,...,n)

Variable de estado sk: el peso (o volumen) que la mochila aún puede cargar cuando se carga por késima vez

Variable de decisión xk: el número de artículos del késimo artículo cargado por kth vez

Conjunto de decisión permitido: Dk(sk)={dk|0? wkxk

Indicador de fase: vk= ckxk

En general, los métodos utilizados para resolver el problema de la mochila incluyen el método recursivo y el método codicioso. Sin embargo, se utilizan estos dos métodos para resolver el. El problema de la mochila tiene sus inevitables deficiencias. Aunque el método recursivo puede atravesar el espacio de búsqueda para encontrar la solución óptima, dado que el espacio de solución de este problema crece en N niveles de 2, solo es adecuado para resolver problemas de mochila a pequeña escala. Es difícil para el método codicioso encontrar realmente la solución óptima. La solución óptima encontrada por este método a menudo está lejos de la solución óptima real. Como método de búsqueda y optimización aleatoria, el algoritmo genético tiene un buen paralelismo y solo necesita utilizar la información de valor del objetivo sin requerir información de alto valor como grados, por lo que es adecuado para cualquier escala. El algoritmo genético tiene una gran versatilidad en la optimización de funciones multimodales discontinuas altamente no lineales y la optimización de funciones objetivo sin expresiones analíticas.

(Si necesitas programación informática, la respuesta será más detallada. Ahora no sé qué estás haciendo con el problema de la mochila)