定义有限数量的多种物品和多个背包,且不同物品和不同背包都有长、宽、高、体积、重量,以背包的体积利用率最大作为目标函数求解。装载时采用“密度递增”的定序规则和“占角策略”的定位规则,将密度最小的货物第一个放入原点所在的角落。在货物摆放过程中,需设定重量约束,背包重量平衡约束,体积约束、三维尺寸约束(即长、宽、高约束)。请用lingo.11对上述问题建模求解,并输出最优装载方案,详细至哪个背包放了哪种物品多少个
时间: 2023-05-29 08:07:08 浏览: 43
完全背包_背包问题_容量为c的背包_背包_完全背包_4321_
5星 · 资源好评率100%
首先,定义决策变量:
$x_{ijk}$表示第$i$个物品放入第$j$个背包中的第$k$个位置,取值为0或1。
然后,建立约束条件:
1. 每个物品只能放入一个背包中的一个位置。
$$\sum_{j=1}^{m}\sum_{k=1}^{p}x_{ijk}=1,\quad i=1,2,\ldots,n$$
2. 每个背包的重量不超过其最大承载重量。
$$\sum_{i=1}^{n}\sum_{k=1}^{p}w_{i}x_{ijk}\leq W_{j},\quad j=1,2,\ldots,m$$
3. 所有物品的总重量不超过所有背包的最大承载重量之和。
$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}w_{i}x_{ijk}\leq \sum_{j=1}^{m}W_{j}$$
4. 每个背包的体积不超过其最大容量。
$$\sum_{i=1}^{n}\sum_{k=1}^{p}v_{i}x_{ijk}\leq V_{j},\quad j=1,2,\ldots,m$$
5. 所有物品的总体积不超过所有背包的最大容量之和。
$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}v_{i}x_{ijk}\leq \sum_{j=1}^{m}V_{j}$$
6. 每个物品的长、宽、高均不超过其所在背包的长、宽、高。
\begin{align}
&l_{i}\leq L_{j}-\sum_{k=1}^{p}(x_{ijk}\cdot l_{i}),\quad i=1,2,\ldots,n, j=1,2,\ldots,m \\
&w_{i}\leq W_{j}-\sum_{k=1}^{p}(x_{ijk}\cdot w_{i}),\quad i=1,2,\ldots,n, j=1,2,\ldots,m \\
&h_{i}\leq H_{j}-\sum_{k=1}^{p}(x_{ijk}\cdot h_{i}),\quad i=1,2,\ldots,n, j=1,2,\ldots,m
\end{align}
7. 线性化密度递增的定序规则。
$$\sum_{i=1}^{n}d_{i}\cdot\sum_{k=1}^{p}x_{ijk}\geq \sum_{i=1}^{n}d_{i}\cdot\sum_{k=1}^{p}x_{i(j+1)k},\quad j=1,2,\ldots,m-1$$
其中,$d_{i}=\frac{v_{i}}{w_{i}}$表示物品$i$的密度。
8. 线性化占角策略的定位规则。
$$\sum_{i=1}^{n}\sum_{k=1}^{p}(x_{ijk}\cdot l_{i})\leq \sum_{i=1}^{n}\sum_{k=1}^{p}(x_{i(j+1)k}\cdot l_{i}),\quad j=1,2,\ldots,m-1$$
$$\sum_{i=1}^{n}\sum_{k=1}^{p}(x_{ijk}\cdot w_{i})\leq \sum_{i=1}^{n}\sum_{k=1}^{p}(x_{i(j+1)k}\cdot w_{i}),\quad j=1,2,\ldots,m-1$$
$$\sum_{i=1}^{n}\sum_{k=1}^{p}(x_{ijk}\cdot h_{i})\leq \sum_{i=1}^{n}\sum_{k=1}^{p}(x_{i(j+1)k}\cdot h_{i}),\quad j=1,2,\ldots,m-1$$
最后,目标函数为最大化背包的体积利用率。
$$\max\frac{\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}(x_{ijk}\cdot v_{i})}{\sum_{j=1}^{m}V_{j}}$$
将上述模型输入lingo.11求解,即可得到最优的装载方案。其中,$x_{ijk}$的取值为1表示第$i$个物品放入第$j$个背包中的第$k$个位置。
阅读全文