定义有限数量的多种物品和多个背包,且不同物品和不同背包都有长、宽、高、体积、重量,以背包的体积利用率最大作为目标函数求解。装载时采用“密度递增”的定序规则和“占角策略”的定位规则,将密度最小的货物第一个放入原点所在的角落。在货物摆放过程中,需设定重量约束,背包重量平衡约束,体积约束、三维尺寸约束(即长、宽、高约束)。请用lingo.11对上述问题建模求解,并输出最优装载方案,详细至哪个背包放了哪种物品多少个
时间: 2023-05-28 15:03:48 浏览: 55
该问题可以建立如下的混合整数线性规划模型:
目标函数:
$\max Z=\frac{\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_i x_{ij}}{\sum\limits_{j=1}^m v_j}$
其中,$n$为物品数量,$m$为背包数量,$d_i$为第$i$个物品的密度,$v_j$为第$j$个背包的体积。
决策变量:
$x_{ij}=\begin{cases}1, & \text{第$i$个物品放入第$j$个背包} \\0, & \text{其他情况}\end{cases}$,$i=1,2,\cdots,n$,$j=1,2,\cdots,m$
$y_j=\begin{cases}1, & \text{第$j$个背包被使用} \\0, & \text{其他情况}\end{cases}$,$j=1,2,\cdots,m$
其中,$x_{ij}$为0-1变量,$y_j$为整数变量。
约束条件:
(1)每个物品只能放入一个背包:
$\sum\limits_{j=1}^m x_{ij}=1$,$i=1,2,\cdots,n$
(2)每个背包的重量不超过其容量:
$\sum\limits_{i=1}^n w_i x_{ij}\leq c_j y_j$,$j=1,2,\cdots,m$
其中,$w_i$为第$i$个物品的重量,$c_j$为第$j$个背包的容量。
(3)每个背包的体积不超过其容量:
$\sum\limits_{i=1}^n v_i x_{ij}\leq v_j y_j$,$j=1,2,\cdots,m$
其中,$v_i$为第$i$个物品的体积,$v_j$为第$j$个背包的体积。
(4)每个物品在三个维度上的尺寸不超过背包的三个维度:
$x_{ij}(l_i\leq L_j)\land x_{ij}(w_i\leq W_j)\land x_{ij}(h_i\leq H_j)$,$i=1,2,\cdots,n$,$j=1,2,\cdots,m$
其中,$l_i$、$w_i$、$h_i$分别为第$i$个物品的长、宽、高,$L_j$、$W_j$、$H_j$分别为第$j$个背包的长、宽、高。
(5)每个背包的重量平衡:
$\sum\limits_{j=1}^m w_i x_{ij}=\frac{\sum\limits_{j=1}^m w_j y_j}{m}$,$i=1,2,\cdots,n$
(6)每个物品按密度递增的顺序装载:
$x_{i,j}\geq x_{i-1,j}$,$i=2,3,\cdots,n$,$j=1,2,\cdots,m$
其中,$x_{0,j}=0$,表示第一个物品可以放在任意一个位置。
(7)每个物品按照占角策略定位:
$x_{i,j}\geq x_{i,j-1}+x_{i-1,j-1}-x_{i-1,j}$,$i=1,2,\cdots,n$,$j=2,3,\cdots,m$
其中,$x_{i,0}=0$,表示第一个背包可以放在任意一个位置。
上述模型可以用LINGO.11求解,输出最优装载方案,包括哪个背包放了哪种物品多少个。