第4章-整数规划与分配问题-管理运筹学

1、第4章 整数规划与分配问题目录4整数规划1230-1规划分配问题本章小结与作业管理运筹学 第4章 整数规划与分配问题4.1 整数规划管理运筹学 第4章 整数规划与分配问题导入案例整数规划的基本概念图解法分枝定界法的基本思路4.1.1导入案例集装箱托运计划管理运筹学 第4章 整数规划与分配问题货物每箱体积(m3)每箱质量(50kg)每箱利润(百元)甲乙384356托运限制4024某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利润以及托运所受到的限制如表所示。问怎样安排托运计划，可使利润最大？设 x1,x2表示两种货物装载数量(整数)，依题意有如下数学模型：在实际中，许多要求变量取整

2、的数学模型，称为整数规划。4.1.2 整数规划的基本概念整数规划（integer programming，IP）是指一类要求问题中的全部或一部分变量为整数的数学规划。在整数规划中，依决策变量的取值不同，又可进一步划分：如果所有变量都限制为整数，则称为纯整数规划（Pure Integer Programming，PIP）；如果仅一部分变量限制为整数，则称为混合整数规划（Mixed Integer Programming，MIP）；变量取二进制的整数规划则称为0-1规划（Binary Integer Programming，BIP）。管理运筹学 第4章 整数规划与分配问题4.1.3 图解法管理运筹

3、学 第4章 整数规划与分配问题【例4.1】 用图解法求解整数规划（1）建立直角坐标系，图示约束条件，确定可行域。（2）图示目标函数一根基线，按目标要求平行移动，直到与可行域相交。（3）求出交点坐标与目标值。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x10 1 2 3 4 5 6 7 8 x2X=(2,4),z=344.1.4 分枝定界法的基本思路*管理运筹学 第4章 整数规划与分配问题【例4.1】 分枝定界法求解分枝定界法(Branch and Bound Method)用于求解整数规划问题，是在20世纪60年代初，由Land Doig和Dakin等人提出的。解 (

4、1) 承例4.1，由图解法知，一般线性规划解的坐标为(72/23,88/23)，不在网格线的交叉点上，非整数解（非可行解）。(2) 对“解1”分枝定界：选取x1 进行分枝定界：在原模型的基础上，分别添加x13,x14 。优化结果 “解2” ，X=(3,31/8) ；“解3”，X=(4,8/3) ，均为非整数（非可行解）。(3) 先对“解2”分枝定界：“解2”的坐标为(3,31/8)，分别添加 x23，x24，优化结果 “解4”，X=(3,3)，z=33，为可行解；“解5”，X=(8/3,4)，z=37.33，为非可行解，由于其目标值大于解4的目标值，先保留，待进一步分枝定界。(4) 再对“解3

5、”分枝定界：“解3”的x2坐标 为非整数，添加x22 （x2 3为非可行域），优化结果为“解6”X=(9/2,2)，z=34.5；再添加x1 =4,x1 5 。解得整数解X=(4,2)，z=32和非整数解X=(5,4/3)，目标值z=33，这两个整数解和非整数解的目标值均不大于整数解解4，不再保留。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解6(9/2,2),z=34.5解3 (4,8/3)解1 (72/23,88/23)解2 (3,31/8)解4 (3,3),z=33解5 (8/3,4),z=37.33 (5) 对“解5

6、”分枝定界：“解5”的坐标(8/3,4)， 为非整数，添加x12 （ x13为非可行域），优化结果为X=(2,17/4)，再添加x2=4 和x2=5 。求得整数解(2,4)，目标值34；整数解(0,5)，目标值30，取(2,4)。如图“解7”。解7 (2,4),z=34(6) 剪枝：将“解4”X=(3,3)，z=33与 “解7”X=(2,4)，z=34。相比较，“解7”目标值为34，对应的最优方案 。4.2 0-1规划管理运筹学 第4章 整数规划与分配问题0-1规划的概念与隐枚举法简介0-1变量在数学建模中的应用案例1：球队队员筛选案例2：选址问题案例3：集合覆盖问题4.2.1 0-1规划的概

7、念0-1规划是一种特殊类型的整数规划，即决策变量只取0或1。0-1规划在整数规划中占有重要地位，许多实际问题，例如指派问题、选址问题、送货问题都可归结为此类规划。求解0-1规划的常用方法是隐枚举法，对各种特殊问题还有一些特殊方法，例如求解指派问题的匈牙利方法。0-1规划的数学模型为：管理运筹学 第4章 整数规划与分配问题4.2.2 隐枚举法简介管理运筹学 第4章 整数规划与分配问题1.化成标准形式(1)目标函数:min ,cj0。目标若max,目标系数改变符号,变为min;(2)若cj1) 项工作任务，需要 m(n1)个人去完成，并且每个人只干一件工作，每项工作都必须有人干，通过权衡，合理分派

8、任务，使总的消耗(或收益)达到最小(或最大)的0-1规划问题，称为分配问题(Assignment Problem，AP)当n=m时为人员与任务平衡，nm为人多任务少，nm为人少任务多，其数学模型如下。人少任务多(nm)人员与任务平衡(n=m)4.3.1 分配问题数学模型管理运筹学 第4章 整数规划与分配问题匈牙利法是1955年库恩(W.W.Kuhu) 引用匈牙利数学家考尼格(D.Konig) 关于“一个矩阵中独立0元素最多个数等于能够覆盖所有0元素的最少直线数”的定理而提出的分配问题的解题方法。虽然在此以后方法不断改进，但仍沿用这个名称。匈牙利法解题首先要将模型标准化（人员任务平衡、目标极小）

9、。(1) 若人员数(n)任务数(m)，则添加(n-m=k)个虚拟任务，效率矩阵中对应的元素为0；(2) 若人员数(n)任务数(m)，则添加(m-n=s)个虚拟人员，效率矩阵中对应的元素为0；(3) 若目标函数为极大，则令 ，构造新的效率矩阵 将目标函数转化为最小。4.3.2 匈牙利法管理运筹学 第4章 整数规划与分配问题4.3.2 匈牙利法管理运筹学 第4章 整数规划与分配问题证：匈牙利法迭代步骤每行减去该行最小数每列减去该列最小数先看行，只有1个0，标记为，划去所在列，转下行，直到最后行再看列，只有1个0，标记为，划去所在行，转下列，直到最后列重复上述过程三种结局处取1，其余取0，得最优解从

10、未被划去的数找最小数k，末被划去的数字减k，覆盖直线交叉处加k个数=n个数n从闭回路任一0出发，在转弯处按顺序编号，取单号(或双号)标记存在0的闭回路管理运筹学 第4章 整数规划与分配问题【例4.7】 用匈牙利法求解引例中最小化分配问题。匈牙利法迭代例题管理运筹学 第4章 整数规划与分配问题【例4.8】 用匈牙利法求解最小化分配问题。k=2最优方案：x11=x23=x35=x44=x51=1,其余=0。最优值=34匈牙利法迭代例题管理运筹学 第4章 整数规划与分配问题分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如表所示。由于任务数多于人数，故考虑：（1）任

11、务E必须完成，其他4项中可任选3项完成；（2）其中有一个人完成两项，其他每人完成一项；（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项。试分别确定最优分配方案，使完成任务的总时间为最小。 任务人员ABCDE甲乙丙丁2539342429382742312628364220402337333245案例4-4任务分派管理运筹学 第4章 整数规划与分配问题（1）任务E必须完成，其他4项中可任选3项完成管理运筹学 第4章 整数规划与分配问题该问题为人少任务多，应添加假想人员，但任务E必须完成，故c55应为M。匈牙利法求解管理运筹学 第4章 整数规划与分配问题k=4k=1（2）其中一人完成两项,其他每人完成一项管理运筹学 第4章 整数规划与分配问题（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项。管理运筹学 第4章 整数规划与分配问题1.基本概念变量取整数的规划问题称为整数规划。当变量全部取整数，称为纯整数规划；变量部分取整数，称为混合整数规划；变量取二进制称