[Python知识库]华数杯B题

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

摘要

一、问题的提出

<少问题的提出>

二、模型假设

<少模型假设>

三、符号说明

<少符号表：最后完成>

四、模型的建立与求解

4.1 问题一：空隙最小的装运方案

4.1.1 问题分析

我们首先计算了在前50个周期的货物平均销售量，如下表所示：
$$\begin{array}{clcrccccccc}HW& \text{HW1}& \text{HW2}& \text{HW3}& \text{HW4}& \text{HW5}& \text{HW6}& \text{HW7}& \text{HW8}& \text{HW9}& \text{HW10}\\ & 119& 368& 361& 364& 247& 307& 611& 2993& 617& 1225\end{array}$$

通过对飞机和货物数据，我们发现飞机机舱的载重限制相比较于其体积限制要更加严格，所以载重对货物运输的数量影响较大。我们以空隙最小为目标函数，以载重约束和体积约束为主建立整数规划模型，并使用MATLAB求解出装运货物的大致数量。之后，再通过反向检验来判断我们的模型是否合理，如果合理，则确定其装运方案；如果不合理，则进一步采取逐步调整，调整个别货物的装配情况以达到在满足一定的条件下，该装运方案使得空隙最小。

4.1.2 模型的建立：

4.1.2.1 整数规划——确定基本的装运模型

为简化模型，我们在这一操作上只考虑载重约束和体积约束。我们事先规定大飞机的前、中、后舱分别为1号舱、2号舱、3号舱，中飞机的前、中、后舱分别为4号舱、5号舱、6号舱，小飞机的前、中、后舱分别为7号舱、8号舱、9号舱。

决策变量：
每种货物在各货舱的数量。用$x_{ij}$表示第i种货物安排在j号舱的数量。$i=1,2,\dots ,10$表示HW1，HW2,…,HW10,$j=1,2,\dots ,9$表示1，2,…,9号舱。由于数量为非负整数，所以$x_{ij}\in Z^{?}$。

目标函数：
总缝隙最小化，即所装货物的体积最大化，则以大飞机为例，目标函数为：
$$\max \sum _{j=1}^3\sum _{i=1}^{10}HWvolumn(i)?x_{ij}$$

约束条件：
分为载重约束和体积约束，以大飞机为例：
载重约束：
$$?\begin{array}{l}2.1x_{11}+0.2x_{21}+0.7x_{31}+1.8x_{41}+1.3x_{51}+0.3x_{61}+0.23x_{71}+1.2x_{81}+0.9x_{91}+0.3x_{101}\le 10\\ 2.1x_{12}+0.2x_{22}+0.7x_{32}+1.8x_{42}+1.3x_{52}+0.3x_{62}+0.23x_{72}+1.2x_{82}+0.9x_{92}+0.3x_{102}\le 16\\ 2.1x_{13}+0.2x_{23}+0.7x_{33}+1.8x_{43}+1.3x_{53}+0.3x_{63}+0.23x_{73}+1.2x_{83}+0.9x_{93}+0.3x_{103}\le 8\end{array}$$
载重比例约束：
$$\{\begin{array}{l}\frac{2.1x_{11}+0.2x_{21}+0.7x_{31}+1.8x_{41}+1.3x_{51}+0.3x_{61}+0.23x_{71}+1.2x_{81}+0.9x_{91}+0.3x_{101}}{10}?\frac{2.1x_{12}+0.2x_{22}+0.7x_{32}+1.8x_{42}+1.3x_{52}+0.3x_{62}+0.23x_{72}+1.2x_{82}+0.9x_{92}+0.3x_{102}}{16}=0\\ \frac{2.1x_{11}+0.2x_{21}+0.7x_{31}+1.8x_{41}+1.3x_{51}+0.3x_{61}+0.23x_{71}+1.2x_{81}+0.9x_{91}+0.3x_{101}}{10}?\frac{2.1x_{13}+0.2x_{23}+0.7x_{33}+1.8x_{43}+1.3x_{53}+0.3x_{63}+0.23x_{73}+1.2x_{83}+0.9x_{93}+0.3x_{103}}{8}=0\end{array}$$

体积约束：
令HWweight=[7.592992 1.157625 5.712340 5.067300 2.405970 0.709632 0.214032 2.470000 2.870400 1.500000]
$$?\begin{array}{l}7.592992x_{11}+1.157625x_{21}+5.712340x_{31}+5.067300x_{41}+2.405970x_{51}+0.709632x_{61}+0.214032x_{71}+2.470000x_{81}+2.870400x_{91}+1.500000x_{101}\le 2038.14\\ 7.592992x_{12}+1.157625x_{22}+5.712340x_{32}+5.067300x_{42}+2.405970x_{52}+0.709632x_{62}+0.214032x_{72}+2.470000x_{82}+2.870400x_{92}+1.500000x_{102}\le 2501.2\\ 7.592992x_{13}+1.157625x_{23}+5.712340x_{33}+5.067300x_{43}+2.405970x_{53}+0.709632x_{63}+0.214032x_{73}+2.470000x_{83}+2.870400x_{93}+1.500000x_{103}\le 1703.52\\ {\sum }_{i=1}^{10}货物i的最小边长?x_{ij}\le j号货舱的最小边长(j=1,2,...,9)\end{array}$$
且$x_{ij}\in Z^{?}$

求解得到的结果如下：

注：

1. 平衡=$\frac{前舱货物}{前舱限重}：\frac{中舱货物}{中舱限重}：\frac{后舱货物}{后舱限重}$
2. 剩余空隙=飞机体积-飞机内货物的总体积

4.1.2.2 反向检验——判断是否需要调整

我们现在需要检验通过整数规划的结果能不能将货物按照一定的摆放放入货舱中：
经检验我们发现：
体积限制是非常小的，可满足的摆放种类相当多，而且非常容易满足：
下面列举一个满足题意的摆放方案：
<少摆放方案>（经验证非常容易实现：考虑最小边长即可）