运筹学（第2版）课件 第三章 整数规划.pptx

运筹学

南京航空航天大学经济与管理

学院

第三章整数规划

目前世界上大多航空公司的机队都具有多种机型，不同机型有着不同的设计特点，如座位数、着陆重量、机组、飞机维护和燃油消耗等等。针对不同的运营航线，每种机型的运营成本也都有所不同，如何安排不同机型承担运输任务是航空公司生产运营过程中一项非常重要的工作。

对于机型的分配是一般是通过对已经开航或拟开辟的各航线进行客流量预测，并通过对机队中各种机型在不同航线和航班上的运营成本进行对比分析，最终的目标是为各个航班匹配合理的机型。机型分配的结果直接影响到航空公司的运营成本和飞行安全问题，对航空公司的正常运作和整体效益有着决定性影响。

机型分配问题主要通过考虑飞机飞行时间、旅客数量、两地航班次数等约束条件，建立总成本最小的目标函数，从而得到最优的机型配置方案。在这类问题中，最优解是各种类型飞机班次，所以是一定是整数。因此航空公司大多采用基于整数规划算法的航班计划编制管理系统解决机型分配问题，该系统能为航空公司提高飞机利用率、节省航班计划编制时间，从而提高航空公司整体的经济效益。

第三章整数规划

从上述情况可以看出，航空公司机型分配与前面介绍的线性规划问题最大的不同在于最优解必须是整数。因此，人们将决策变量必须取整数的线性规划问题称为整数线性规划问题。在整数线性规划问题中，如果所有决策变量都是整数，则称为纯整数规划；如果一部分决策变量是整数，一部分是非整数，则称为混合整数规划；而变量取值只能是0或1的问题称为0-1整数规划。这些分类主要是根据决策变量的整数要求和限制来进行区分的。

3.1.1整数规划的求解

例3.1某厂拟用集装箱托运甲、乙两种货物，两种货物的体积、质量、单件利润以及集装箱托运限制情况如表3.1所示。问两种货物各托运多少箱，可使获得的利润为最大?

表3.1两种货物的体积、质量、单件利润以及集装箱托运限制情况

货物

体积/立方米

质量/百千克

单件利润/百元

甲

5

2

20

乙

4

5

10

集装箱托运限制

24

13

解：设x₁,x₂分别为甲、乙两种货物的托运箱数，则数学模型可以表示为：

maxz=20x₁+10x₂

整数

其中，目标函数代表追求最大利润，约束条件是对集装箱的体积和质量限制，决策变量要求集装箱数量必须是整数。

3.1.2分支定界算法

当涉及整数规划问题的求解时，可以使用单纯形算法来求得非整数约束下的最优解，然后通过四舍五入或取整法来获得最优整数解。然而，这种方法有时并不能保证得到整数规划的最优解。

为更好地理解，以例3.1的求解为例，先不考虑x1,x2为整数的条件，采用单纯形法求解该问题，得到：

x1=4.8,x2=0,z=96。若对x1,x2采用四舍五入法求解，则

有x1=5,x2=0,显然，此解不是可行解；如果采用取整法，

x1=4,x2=0。此时，目标函数z=80,这个解也不是最优解。由此表明，四舍五入或者取整法得到的解并不是整数规划的最优解。

对于整数规划问题，如果可行域是有界的，那么整数

解的数量应该是有限的。在这种情况下，可以使用枚举法计算所有可行整数解，并比较它们对应的目标函数值，从中选择最优解。当决策变量较少且取值范围不大时，枚举法是可行且有效的。然而，对于具有大量决策变量的整数规划问题，当决策变量很多且取值范围较大时，采用枚举法将导致指数级增长的计算量，并不可行。

目前，解决整数规划问题的两种常用方法是分支定界

算法和割平面法。分支定界算法是在20世纪60年代提出的一种灵活且适合计算机求解的方法。下面将通过例子说明分支定界算法的思想和步骤。

例3.2求解对如下整数规划：

maxz=40x₁+90x₂

解：先不考虑整数条件，解相应的线性规划，得最优解：x₁=4.81,x₂=1.82,z₀=356该解不符合整数条件。

对其中一个非整数变量解，如x=4.81,显然，若要满

足整数条件x₁必定有x₁≥5或x₁≤4

maxz=40x₁+90x₂

maxz=40x₁+90x₂

x₁+7x₂≤56

20x,≤70

s.t

x₁≤4

x,x₂≥0

(LP1)和

(LP2)

于是，对原问题增加两个新约束条件，将原问题分为两个子问题，即有

问题(LP1)和(LP2)的可行域中包含了原整数规划问题的所有整数可行解，而在4x5中不可能存在整数可行解的区域已被切除。分别求解这两个线性规划问题，得到的解是：x=4,x₂=2.1,z=349和x=5,x₂=1.57,z=341。

变量x₂仍然不满足