货舱容量分配问题

4、（选做）一架货机有三个货舱：前舱、中舱和后舱。三个货舱所能装载的

货物的最大重量和体积有限制（如表 3 所示）。现有四类货物用该货机进行装运，

货物的规格以及装运后获得的利润如表 4 所示。并且为了飞机的平衡，三个货

舱装载的货物重量必须与其最大的容许量成比例。问应如何装运，使货机飞行利

润最大？

假设：

每种货物可以无限细分；

每种货物可以分布在一个或者多个货舱内；

不同的货物可以放在同一个货舱内，并且可以保证不留空隙。

 

 

要求：

（1）查阅资料，解释什么是组合优化问题？现实生活中哪些问题属于组合

优化问题？通常采用什么方法求解组合优化问题？

（

2）分析问题，建立合理的数学模型。要求给出数学建模的主要步骤，给

出所有变量的定义、目标函数和约束条件。

（

3）线性规划问题通常采用什么方法求解？给出主要思路。

提示：

① 本题涉及组合优化问题、线性规划模型、线性规划方法等知识。

② 本题中，各变量可取值的范围为连续值，不同于前面三题中变量取值均

为离散整数量或者 0、1 量的情况，本题属于线性规划问题，模型为线性规划模

型。

线性规划问题参考书籍：实用线性规划方法及其支持系统. 清华大学出版社，

江道琪、何建坤、陈松华编著）

③ 本题需要解决的问题是在安排飞机装载的货物时，找到三个货舱装载的

各种货物的重量，使飞机获得的利润最大。在装载货物时需要考虑每个货舱的重

量限制，同时还要考虑货舱的体积限制，以及保证飞机平衡的限制。即在若干线

性约束条件下，求得目标函数的最大值。

答：（1）组合优化问题：通过百度百科，组合（最）优化问题是最优化问题的一类。最优化问题似乎自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。具有离散变量的问题，我们称它为组合的。在连续变量的问题里，一般地是求一组实数，或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。一般地，这两类问题有相当不同的特色，并且求解它们的方法也是很不同的。

在调度、资源分配、物流、城市规划、电路设计、制药等领域应用广泛。

现实中的组合优化问题：

旅行商问题，生产调度问题，0-1背包问题，装箱问题，图着色问题，聚类问题，最大团问题 ，我通过查找相关资料可知，图论中的最短路径问题就可以用组合优化来解决。

求解组合优化问题通常采用分支限界法（精确方法，但大规模实例上往往不可行）、贪心算法（近似算法，求解可被严格证明为与最优解差A倍）、启发式算法（需要特殊领域知识）、元启发算法（如蚁群算法、遗传算法、智能算法、进化算法等）、神经网络、RL方法等。

1. 问题分析：

分配不同货物在前中后，三个仓怎么发配，而且要求满足题意条件，我通过一些简单的运算，发现存在的货物重量远远大于飞机所能出承受的重量，又因为我们前中后三个舱都得成比例，又追求利润的最大化。我们观察飞机舱中的体积和重量限制，发现前，后两舱的体积限制非常大，所以我们不妨将前，后三个舱全部装满。（以具体问题来优化）

下面我们开始模型的建立：

Xij表示货物i在前中后三个货舱运输的重量。

	货物1	货物2	货物3	货物4
前舱	X11	X21	X31	X41
中舱	X12	X22	X32	X42
后舱	X13	X23	X33	X43

目标函数，设M为总利润

M = (X11 + X12 + X13)*3100+ (X21 + X22 + X23)*3800+ (X31 + X32 + X33)*3500+ (X41 + X42 + X43)*2850

约束函数：

480*X11 + 650*X21 + 580*X31 + 390*X41 <= 6800

480*X12 + 650*X22 + 580*X32 + 390*X42 <= 8700

480*X13 + 650*X23 + 580*X33 + 390*X43 <= 5300

X11 + X12 + X13 <= 18

X21 + X22 + X23 <= 15

X31 + X32 + X33 <= 23

X41 + X42 + X43 <= 12

X11 + X21 + X31 + X41 =10

X12 + X22 + X32 + X42=16

X13 + X23 + X33 + X43=8

Xij >= 0，1 <= i, j <= 4

1. 问题求解：

将题目中的约束条件转化为矩阵，然后利用Python或者matlab中求线性最优化的函数来求解。