《现代物流运筹学（第二版）》 课件 6.整数规划及其解法

整数规划《现代物流运筹学》主讲教师：王东辉整数规划的性质整数规划的解法0102目录CONTENT案例某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如表所示。问两种货物各装运多少箱，可使获得利润最大？

表1-1

货物每件体积(立方米)每件重量(百斤)

每件利润(百元)甲乙54252010托运限制2414数学模型特点

设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：maxz＝20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x1,x2为整数(1)(2)(3)(4)(5)

货物每件体积(立方米)每件重量(百斤)

每件利润(百元)

甲乙54252010托运限制24(立方米)14(百斤)它和线性规划问题的区别在于条件(5)整数规划的特点与分类

整数规划（IP）：要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。数学模型整数线性规划数学模型的一般形式：

整数规划的分类纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。010-1型整数线性规划ONE案例现有资金总额为B，可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2，反之不一定项目3和4中至少选择一个项目5,6,7中恰好选择2个应该怎样选择投资项目，才能使总预期收益最大。数学模型解：对每个投资项目都有被选择和不被选择两种可能，因此分别

用0和1表示，令xj表示第j个项目的决策选择，记为：

投资问题可以表示为：02整数规划的解法“凑整法”TWO整数规划的解法“凑整法”直觉认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整方法寻找最优解。是否合适？是否可行？案例求下述整数规划问题的最优解:

案例(3,3)(3,2)(4,3)(4,2)(4,1)，Z=14(3.25，2.5)2x1+3x2=14x1+0.5x2=4.53x1+2x2=0注意：(4，1)不是可行域的顶点，因此直接用图解法或单纯形法都无法找出整数规划问题的最优解来。这就要求研究解整数规划问题的特殊方法。010203整数规划的可行域包含在其对应的一般线性规划可行域之内整数规划的最优解可能不是其对应的一般线性规划的顶点整数规划需要专门的求解方法研究解整数规划问题的特殊方法收获整数规划与对应的线性规划解的关系任何求max的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；（对应线性规划最优解为其上界）任何求min的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数。（对应线性规划最优解为其下界）整数规划之相应线性规划的最优解经四舍五入不能得到其最优解整数规划的最优解不会优于其对应的线性规划的最优解。