1、第 4章 整数规划与分配问题管理运筹学课件*教学目标与要求n 【 教学目标 】n 通过本章学习，了解求解整数规划 “分枝定界法 ”的其中思路，掌握 0-1变量在数学建模中的应用；熟练掌握 “匈牙利法 ”，至少掌握一种软件求得整数规划及分配问题的最优解。n 【 知识结构 】管理运筹学课件*本章主要内容 n 4.1 整数规划n 4.1.1 整数规划的概念n 4.1.2 分枝定界法的基本思路 *n 4.2 0-1规划n 4.2.1 0-1规划的概念n 4.2.2 0-1规划的隐枚举法简介 *n 4.2.4 0-1变量在数学建模中的用途n 案例 4-1 球队队员筛选n 案例 4-2 选址问题n 案例
2、4-3 集合覆盖问题n 4.3 分配问题n 4.3.1 分配问题数学模型n 4.3.2 分配问题的解题方法 匈牙利法n 案例 4-4 任务分派n 本章小结管理运筹学课件*导入案例 集装箱托运计划某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利润以及托运所受到的限制如表 4-1所示。问怎样安排托运计划，可使利润最大？货物 每箱体积 /米 3 每箱质量 /50千克 每箱利润 /百元甲乙384356托运限制 40 24 设 x1,x2表示两种货物装载数量 (整数 )，依题意有如下数学模型：在实际中，许多要求变量取整的数学模型，称为整数规划。本章将讨论整数规划求解的基本思路、 0-1变量
3、的用法、分配问题及匈牙利法，以及利用 Excel, Lingo, WinQSB求解的演示。管理运筹学课件*4.1.1 整数规划的基本概念n 整数规划（ integer programming， IP）是指一类要求问题中的全部或一部分变量为整数的数学规划。n 在整数规划中，依决策变量的取值不同，又可进一步划分：如果所有变量都限制为整数，则称为纯整数规划（ Pure Integer Programming， PIP）；如果仅一部分变量限制为整数，则称为混合整数规划（ Mixed Integer Programming， MIP）；变量取二进制的整数规划则称为 0-1规划（ Binary Integ
4、er Programming， BIP）。管理运筹学课件*4.1.2 分枝定界法的基本思路 *【 例 4.1】 用图解法求解整数规划分枝定界法 (Branch and Bound Method)用于求解整数规划问题，是在 20世纪 60年代初，由 Land Doig和 Dakin等人提出的。解 (1) 绘制直角坐标系，图示约束条件，图示目标函数一根基线(z=30)，使其平行移动，求得非整数最优解。该解的坐标为(72/23,88/23)，不在网格线的交叉点上，非整数解（非可行解）。(2) 对 “解 1”分枝定界：选取 x1 进行分枝定界：在原模型的基础上，分别添加 x13,x14 。优化结果 “
5、解 2” ， X=(3,31/8)， z=38.25； “解 3”， X=(4,8/3)， z=36，均为非整数（非可行解）。(3) 先对 “解 2”分枝定界： “解 2”的坐标为 (3,31/8)，分别添加 x23，x24，优化结果 “解 4”， X=(3,3)， z=33，为可行解； “解 5”，X=(8/3,4)， z=37.33，为非可行解。(4) 再对 解 3”分枝定界： 解 3”的坐标 ， 为非整数，添加 x22 （ x2 3为非可行域），优化结果为 X=(9/2,2)， z=34.5；再添加 x1 =4,x1 5 。解得整数解 X=(4,2)， z=32和非整数解 X=(21/4
6、,1)，目标值 z=31.25；整数解目标值大于非整数解，取 (4,2)，得 “解 6”。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x10 1 2 3 4 5 6 7 8 x2(2,9/2),z=34.5解 3 (4,8/3)解 1 (72/23,88/23)解 2 (3,31/8)5x1+6x2=30解 4 (3,3),z=33解 5 (8/3,4),z=37.33解 6 (4,2),z=32(5) 对 “解 5”分枝定界： “解 5”的坐标 (8/3,4)， 为非整数，添加 x12 （ x13为非可行域），优化结果为 X=(2,17/4)，再添加 x2=4 和
7、x2=5 。求得整数解 (2,4)，目标值 34；整数解 (0,5)，目标值 30，取 (2,4)。如图 “解 7”。解 7 (2,4),z=34(6) 剪枝：上述有三个区域的整数解分别为 “解 4”X=(3,3)， z=33； “解6”X=(4,2)， z=32； “解 7”X=(2,4)， z=34。相比较，目标值最大的为34，对应的最优方案 。演示：利用 WinQSB,ExcelORM+ 规划求解 ,ExcelORM+Lingo求例 4.1管理运筹学课件*4.2.1 0-1规划的概念n 0-1规划是一种特殊类型的整数规划，即决策变量只取 0或1。 0-1规划在整数规划中占有重要地位，许多
8、实际问题，例如指派问题、选址问题、送货问题都可归结为此类规划。求解 0-1规划的常用方法是隐枚举法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。n 0-1规划的数学模型为：管理运筹学课件*4.2.2 隐枚举法简介1.化成标准形式(1)目标函数 :min ,cj0(2)目标若 max,目标系数改变符号 ,变为 min;(2)若 cj0,令 yj=1-xj使其变正 ;(3)目标函数中 ,变量按目标系数从小到大排列 ,约束条件中也跟着相应改变 .2.令标准化后的 0-1问题所有变量为 0,若满足约束,即为最优 ,否则转下步 .3.按目标函数中排列顺序依次令各变量分别取 1或0,进行枚举 .管理运筹学课件*4.2.4 0-1变量在数学建模中的应用管理运筹学课件*案例 4-1 球队队员筛选预备队员 身高 /厘米 位置ABCDEF193191187186180185中锋中锋前锋前锋后卫后卫某校篮球队准备从以下 6名预备队员中选拔 3名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示。队员的挑选要满足下列条件：(1) 6位预备队员选 3名。(2) 至少补充 1名后卫人员。(3) B或 E中间最多入选 1名。(4) 最多补充 1名中锋。(5) 无论 B或 D入选， F都不能入选。
