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

1、第第4章章 整数规划与整数规划与分配问题分配问题目录4整数规划整数规划1230-1规划规划分配问题分配问题本章小结与作业本章小结与作业管理运筹学 第4章 整数规划与分配问题4.1 整数规划管理运筹学 第4章 整数规划与分配问题导入案例导入案例整数规划的基本概念整数规划的基本概念图解法图解法分枝定界法的基本思路分枝定界法的基本思路4.1.1导入案例集装箱托运计划管理运筹学 第4章 整数规划与分配问题货物货物每箱体积每箱体积(m3)每箱质量每箱质量(50kg)每箱利润每箱利润(百元百元)甲甲乙乙384356托运托运限制限制4024某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利某厂拟

2、用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利润以及托运所受到的限制如表所示。问怎样安排托运计划，可使利润最润以及托运所受到的限制如表所示。问怎样安排托运计划，可使利润最大大？1212121212max z563843,0,xxxxxxxxxx 40 24取整数设设 x1,x2表示两种货物装载数量表示两种货物装载数量(整整数数)，依题意有如下数学模型：，依题意有如下数学模型：在实际中，许多要求变量取整在实际中，许多要求变量取整的数学模型，称为整数规划的数学模型，称为整数规划。4.1.2 整数规划的基本概念n整数规划（整数规划（integer programming，IP）是指一类要求

3、问）是指一类要求问题中的全部或一部分变量为整数的数学规划。在整数规划中，题中的全部或一部分变量为整数的数学规划。在整数规划中，依决策变量的取值不同，又可进一步划分：依决策变量的取值不同，又可进一步划分：n如果所有变量都限制为整数，则称为纯整数规划（如果所有变量都限制为整数，则称为纯整数规划（Pure Integer Programming，PIP）；）；n如果仅一部分变量限制为整数，则称为混合整数规划如果仅一部分变量限制为整数，则称为混合整数规划（Mixed Integer Programming，MIP）；）；n变量取二进制的整数规划则称为变量取二进制的整数规划则称为0-1规划（规划（Bin

4、ary Integer Programming，BIP）。）。管理运筹学 第4章 整数规划与分配问题4.1.3 图解法管理运筹学 第4章 整数规划与分配问题【例例4.1】用图解法求解整数规划用图解法求解整数规划1212121212max 563840(1)4324(2),0,zxxxxxxxxxx取整数（1）建立直角坐标系，）建立直角坐标系，图示约束条件，确定图示约束条件，确定可行域。可行域。（2）图示目标函数一）图示目标函数一根基线，按目标要求根基线，按目标要求平行移动，直到与可平行移动，直到与可行域相交。行域相交。（3）求出交点坐标与）求出交点坐标与目标值。目标值。0 1 2 3 4 5

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】分枝定界法求解分枝定界法求解1212121212max 563840(1)4324(2),0,zxxxxxxxxxx取整数分枝定界法分枝定界法(Branch and Bound Method)用于求解整数规划问题，用于求解整数规划问题，是在是在20世纪世纪60年代初，由年代初，由Land Doig和和Dakin等人提出的等人提出的。解解 (1)承例承例4.1，由图解法知，一般线性规划解，由图解法知

6、，一般线性规划解的坐标为的坐标为(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)，

7、z=33，为可行解；，为可行解；“解解5”，X=(8/3,4)，z=37.33，为非为非可行解，由于其目标值大于解可行解，由于其目标值大于解4的目标值，先保留，待进一步分枝定界。的目标值，先保留，待进一步分枝定界。(4)再对再对“解解3”分枝定界：分枝定界：“解解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，这两个整数解和非，这两个整数解和非

8、整数解的目标值均不大于整数解整数解的目标值均不大于整数解解解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”分枝定界：分枝定界：“解解5”的坐标的坐标(8/3,4)，为非整数，添加为非整数，添加x12（x13为非可行域），优化结果为为非可行域），优化结果为X=(2,17/4)，再添加，再添加x2=4 和和x2=5。求得整数解。求

9、得整数解(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-

10、1规划的概念l0-10-1规划是一种特殊类型的整数规划，即决策变量只取规划是一种特殊类型的整数规划，即决策变量只取0 0或或1 1。0-10-1规划在整数规划中占有重要地位，许多实际问规划在整数规划中占有重要地位，许多实际问题，例如指派问题、选址问题、送货问题都可归结为此题，例如指派问题、选址问题、送货问题都可归结为此类规划。求解类规划。求解0-10-1规划的常用方法是隐枚举法，对各种规划的常用方法是隐枚举法，对各种特殊问题还有一些特殊方法，例如求解特殊问题还有一些特殊方法，例如求解指派问题的匈牙指派问题的匈牙利方法。利方法。l0-10-1规划的数学模型为规划的数学模型为：管理运筹学 第4章

11、整数规划与分配问题01m ax(m in)(,).zC XAXbs tX取或4.2.2 隐枚举法简介管理运筹学 第4章 整数规划与分配问题12312312312123max 322(1)44(2)s.t.+3(3),01zxxxxxxxxxxxx xx例:求最优解或12312312312123minmin 32244s.t.+3,01jcwxxxxxxxxxxxx xx 改变符号,变为或112233111xxxxxx 令12312312312123min 352042s.t.1,01wxxxxxxxxxxxx xx 或23123123121123min 352042s.t.+1,01wxxxx

12、xxxxxxxx xx 目标系数升序排序或1.化成标准形式化成标准形式(1)目标函数目标函数:min,cj0。目标。目标若若max,目标系数改变符号目标系数改变符号,变为变为min;(2)若若cj 4,3xxxx则则否否则则【例例4.64.6】用用0-10-1表示：若表示：若解解 该问题可表示成该问题可表示成11223344()()()()()()(1)()()(1)01f XgMyfXgMyfXgMyfXgMyy ()()()()或4.2.4 0-1变量在数学建模中的应用管理运筹学 第4章 整数规划与分配问题(8)分段函数的分段函数的0-1表述表述 0,0()0()01xf xkcxxf x

13、ykcxyMxxMyy当当对可表示为或生产过程的种类生产过程的种类固定固定投资投资(元元)生产生产成本成本(元元/千克千克)最大最大日产量日产量(千克千克)甲甲乙乙丙丙1 0002 0003 0005432 0003 0004 000例例(P76(P76第第6 6题题)某企业接受某项产品订货，某企业接受某项产品订货，需求量为每日需求量为每日3 5003 500千克，千克，现现有有3 3种生产种生产过程供选择，各生产过程所需固定投资过程供选择，各生产过程所需固定投资(成本成本)，生产成本，最大日产量如表，生产成本，最大日产量如表所示。问所示。问:企业需要决定采用哪种企业需要决定采用哪种(一种一种

14、或多种或多种)生产过程和日产量多少千克，生产过程和日产量多少千克，才能既保证按合同交货又使总成本最小？才能既保证按合同交货又使总成本最小？试列出该问题的整数规划数学模型。试列出该问题的整数规划数学模型。4.2.4 0-1变量在数学建模中的应用管理运筹学 第4章 整数规划与分配问题10(1,2,3)iiiiyxii采采用用第第 种种生生产产过过程程不不采采用用第第 种种生生产产过过程程采采用用第第 种种生生产产过过程程生生产产的的数数量量1231231231122331122331313min100020003000543,3000,4000.,01;zyyyxxxxxxxy xyxystyx

15、M yx M yx Myx35002000或0解解 设：设：采用生产过程丙生产采用生产过程丙生产3500kg，总成本，总成本13500元。元。生产生产过程过程固定固定投资投资(元元)生产生产成本成本(元元/千克千克)最大最大日产量日产量(千克千克)甲甲乙乙丙丙1 0002 0003 0005432 0003 0004 0004.2.4 0-1变量在数学建模中的应用管理运筹学 第4章 整数规划与分配问题某校篮球队准备从以下某校篮球队准备从以下6名预备队员中选名预备队员中选拔拔3名为正式队员，并使平均的身高尽可名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示。能高。这六名预备队员情

16、况如表所示。队员的挑选要满足下列条件：队员的挑选要满足下列条件：(1)6位预备队员选位预备队员选3名。名。(2)至少补充至少补充1名后卫人员。名后卫人员。(3)B或或E中间最多入选中间最多入选1名。名。(4)最多补充最多补充1名中锋。名中锋。(5)无论无论B或或D入选，入选，F都不能入选都不能入选。案例4-1 球队队员筛选管理运筹学 第4章 整数规划与分配问题预备队员预备队员身高身高(cm)(cm)位置位置A AB BC CD DE EF F193193191191187187186186180180185185中锋中锋中锋中锋前锋前锋前锋前锋后卫后卫后卫后卫s.t.123456max1931

17、91187186180185zxxxxxx0,:1,iixi第第名名未未进进入入正正式式队队设设第第名名进进入入正正式式队队561(2)xx1234563(1)xxxxxx251(3)xx121(4)xx26461(5)1xxxx160 1x或案例4-2 选址问题管理运筹学 第4章 整数规划与分配问题地点地点A A1 1A A2 2A A3 3A A4 4A A5 5A A6 6A A7 7建点成本建点成本2020202025252424222224242323估计利润估计利润3030303035353434383840404545某公司在城市东、西、南某公司在城市东、西、南三区拟建立门市部。

18、计划三区拟建立门市部。计划有有7个位置个位置(点点)Aj(j=1,7)可供选择。规定：可供选择。规定：在东区，由在东区，由A1,A2,A3 三个三个点至多选两个；在西区，点至多选两个；在西区，由由 A4,A5 两个点至少选一两个点至少选一个；在南区，由个；在南区，由A6,A7 两两个点至少选一个。设各位个点至少选一个。设各位置建点的成本与预计利润置建点的成本与预计利润见表，若建点总成本控制见表，若建点总成本控制在在100万元以内，试问应万元以内，试问应该选取哪几个点可使年利该选取哪几个点可使年利润为最大？。润为最大？。1 :1 270 iiiAxi=A当当被被选选中中，设设，当当未未被被选选中

19、中，123456712345671234567max 30303534384045202025242224231002()s.t.+1()+1()01izxxxxxxxxxxxxxxxxxxxxxx东区西区南区或数学模型为：数学模型为：某区有某区有6个街道。这个区必须确定在什个街道。这个区必须确定在什么地方修建消防站。在保证至少有一么地方修建消防站。在保证至少有一个消防站在每个街道的个消防站在每个街道的15min行驶时行驶时间内的情况下，这个区希望修建的消间内的情况下，这个区希望修建的消防站最少。各街道间行驶时间如表防站最少。各街道间行驶时间如表案例4-3 集合覆盖问题管理运筹学 第4章 整数

20、规划与分配问题街道街道1 1 街道街道2 2 街道街道3 3 街道街道4 4 街道街道5 5 街道街道6 6街道街道1 10 010102020303030302020街道街道2 210100 02525353520201010街道街道3 3202025250 0151530302020街道街道4 43030353515150 015152525街道街道5 530302020303015150 01414街道街道6 6202010102020252514140 0121263434545625616+1+1+1.+1+1+1=01xxxxxxxstxxxxxxxxxx或或1,0,1,6:iii

21、ix第第 街街道道设设消消防防站站第第 街街道道不不设设消消防防站站设设123456:min zxxxxxx目目标标 消消防防站站数数目目最最少少4.3 分配问题管理运筹学 第4章 整数规划与分配问题l分配问题数学模型分配问题数学模型l匈牙利法匈牙利法l案例案例:任务分派任务分派4.3.1 分配问题数学模型管理运筹学 第4章 整数规划与分配问题项目项目张张王王李李赵赵仰泳仰泳蛙泳蛙泳蝶泳蝶泳自由泳自由泳3737434333333030333333332929262638384242393929293737343430302929l 导入案例导入案例任务分配任务分配l 某游泳队有四名运动员，其平

22、某游泳队有四名运动员，其平时训练成绩时训练成绩(s/50m)如表所示。如表所示。问如何安排可使总成绩最好？问如何安排可使总成绩最好？人员人员任务任务效率矩阵效率矩阵cij1,0,:ijijijx第第 分分配配给给第第 人人第第 不不分分给给第第 人人设设11121314212223243132333441424344min37333837433342343329393030262929zxxxxxxxxxxxxxxxx111213142122232431323334414243441111xxxxxxxxxxxxxxxx 每每项项任任务务交交给给一一人人01(1,.,4;1,.,4)ijxij

23、或112131411222324213233334142434441111xxxxxxxxxxxxxxxx 每每人人分分给给一一项项任任务务.s t在管理活动中，人们会经常遇到这样的问题，某单位有在管理活动中，人们会经常遇到这样的问题，某单位有n(n1)n(n1)项工作任项工作任务，需要务，需要 m(n1)m(n1)个人去完成，并且每个人只干一件工作，每项工作都必个人去完成，并且每个人只干一件工作，每项工作都必须有人干，通过权衡，合理分派任务，使总的消耗须有人干，通过权衡，合理分派任务，使总的消耗(或收益或收益)达到最小达到最小(或最或最大大)的的0-10-1规划问题，称为分配问题规划问题，称

24、为分配问题(Assignment Problem(Assignment Problem，AP)AP)当当n=mn=m时为人员与任务平衡，时为人员与任务平衡，nmnm为人多任务少，为人多任务少，nmnm为人少任务多，其为人少任务多，其数学模型如下数学模型如下。人少任务多人少任务多(nm)人员与任务平衡人员与任务平衡(n=m)1111min(max)11s.t.011,2,.,1,2,.,mnijijijnijjmijiijzzc xxxximjn 或4.3.1 分配问题数学模型管理运筹学 第4章 整数规划与分配问题1111min(max)11s.t.011,2,.,1,2,.,mnijijijn

25、ijjmijiijzzc xxxximjn 或1111min(max)11s.t.011,2,.,1,2,.,mnijijijnijjmijiijzzc xxxximjn 或匈牙利法是匈牙利法是1955年库恩年库恩(W.W.Kuhu)引用匈牙利数学家考尼格引用匈牙利数学家考尼格(D.Konig)关于关于“一个矩阵中独立一个矩阵中独立0元素最多个数等于能够覆盖所有元素最多个数等于能够覆盖所有0元元素的最少直线数素的最少直线数”的定理而提出的分配问题的解题方法。虽然在此以的定理而提出的分配问题的解题方法。虽然在此以后方法不断改进，但仍沿用这个名称。后方法不断改进，但仍沿用这个名称。匈牙利法匈牙利法

26、解题首先要将模型标准化（人员任务平衡、目标极小）。解题首先要将模型标准化（人员任务平衡、目标极小）。(1)若人员数若人员数(n)任务数任务数(m)，则添加，则添加(n-m=k)个虚拟任务，效率矩阵个虚拟任务，效率矩阵中对应的元素为中对应的元素为0；(2)若人员数若人员数(n)任务数任务数(m)，则添加，则添加(m-n=s)个虚拟人员，效率矩阵个虚拟人员，效率矩阵中对应的元素为中对应的元素为0；(3)若目标函数为极大，则令若目标函数为极大，则令 ，构造新的效率矩阵，构造新的效率矩阵 将目标函数转化为最小。将目标函数转化为最小。4.3.2 匈牙利法管理运筹学 第4章 整数规划与分配问题ijMijb

27、ccmax()Mijn ncc4.3.2 匈牙利法管理运筹学 第4章 整数规划与分配问题ijMijbccmax()Mijn ncc11nnijijijzc x 1111maxminnnnnijijijijijijc xb x等价于11nnMijijijncb x 11()nnMijijijcbx 1111nnnnMijijijijijcxb x 证：证：匈牙利法迭代步骤每行减去该行最小数每行减去该行最小数每列减去该列最小数每列减去该列最小数先看行，只有先看行，只有1个个0，标记为，标记为，划去所在列，转下行，直到最后行，划去所在列，转下行，直到最后行再看列，只有再看列，只有1个个0，标记为，标

28、记为，划去所在行，转下列，直到最后列，划去所在行，转下列，直到最后列重复上述过程重复上述过程三种结局三种结局处取处取1，其余取，其余取0，得最优解得最优解从未被划去的数找从未被划去的数找最小数最小数k，末被划，末被划去的数字减去的数字减k，覆，覆盖直线交叉处加盖直线交叉处加k个数个数=n个数个数n从闭回路任一从闭回路任一0出发，出发，在转弯处按顺序编在转弯处按顺序编号，取单号号，取单号(或双号或双号)标记标记存在存在0的闭回路的闭回路管理运筹学 第4章 整数规划与分配问题【例例4.7】用匈牙利用匈牙利法求解引例中最小化法求解引例中最小化分配问题分配问题。匈牙利法迭代例题管理运筹学管理运筹学 第

29、第4章章 整数规划与分配问题整数规划与分配问题0 10 00 0 0 11 0 0 00 0 1 0X37333837433342343329393030262929Cmin3333292640541009140 1014033min 4031002460600070000210000 100000 100 10X:129z 最优值37 33 38 3743 33 42 3433 29 39 3030 26 29 29C【例例4.8】用匈牙用匈牙利法求解最小化分利法求解最小化分配问题配问题。12799989777 7 11 12 12915 14 147 104 10 1079C min127

30、9997897777 711 12 129715 14 147107410 10794C解 50020340200435087501064335022212000045528770306635k=2最优方案最优方案：x11=x23=x35=x44=x51=1,其余其余=0。最优值最优值=34匈牙利法迭代例题管理运筹学 第4章 整数规划与分配问题n分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人五项任务，每个人完成各项任务的时间如表所示。完成各项任务的时间如表所示。n由于任务数多于人数，故考虑：由于任务数多于人数，故考虑：n（1）任务任务E必须完成，

31、其他必须完成，其他4项中可任选项中可任选3项完成；项完成；n（2）其中有一个人完成两项，其他每人完成一项；其中有一个人完成两项，其他每人完成一项；n（3）任务任务A由甲或丙完成，任务由甲或丙完成，任务C由丙或丁完成，任务由丙或丁完成，任务E由甲、乙或丁由甲、乙或丁完成，且规定完成，且规定4人中丙或丁完成两项任务，其他每人完成一项。人中丙或丁完成两项任务，其他每人完成一项。n试分别确定最优分配方案，使完成任务的总时间为最小。试分别确定最优分配方案，使完成任务的总时间为最小。任务任务人员人员ABCDE甲甲乙乙丙丙丁丁2539342429382742312628364220402337333245案

32、例4-4任务分派管理运筹学 第4章 整数规划与分配问题45115141451min 1(1,2,3,4)s.t.1(1,2,3,4)1,01ijijijijjijiiijizc xxixjxx数学模型或（1 1）任务）任务E E必须完成，其他必须完成，其他4 4项中可任选项中可任选3 3项完成项完成管理运筹学 第4章 整数规划与分配问题2529314237393826203334272840322442362345ijABCDEc甲乙丙丁该该问题为人少任务多，应添加问题为人少任务多，应添加假想人员，但任务假想人员，但任务E E必须完成，必须完成，故故c c5555应为应为MM。25293142

33、373938262033342728403224423623450000ijcM25293142373938262033342728403224423623450000ijcM匈牙利法求解匈牙利法求解管理运筹学 第4章 整数规划与分配问题046171219186013701135119130220000Mm in25202723004617719186087011301191301700005Mm in 00005k=400217319142041101170115901340045Mk=100218318131031101180014801240055M*010000001000001100

34、0000100X*29203224105z 123,:25293142372529314237000393826203339382620330003427284032342728403200024423623452442362345000ijABCDEMMMMMMcMMMMMM匈牙利法计算 需调整效率矩阵虚虚虚甲甲乙乙丙丙丁丁（2 2）其中一人完成两项）其中一人完成两项,其他每人完成一项其他每人完成一项管理运筹学管理运筹学 第第4章章 整数规划与分配问题整数规划与分配问题2529314237393826203334272840322442362345ijc计算机求解模型:45115141min

35、 12(1,2,3,4)s.t.1(1,2,.,5)01ijijijijjijiijzc xxixjx或123,:252942372529423700038203338203300034272840342728400004236234542362345000ijABCDEMMMMMMMMMMMMcMMMMMMMMMM匈匈牙牙利利法法计计算算 需需调调整整效效率率矩矩阵阵虚虚虚虚虚虚甲甲甲甲乙乙乙乙丙丙丙丙丁丁丁丁4511515141min 1(1,2)12(3,4)s.t.1(1,2,.,5)01ijijijijjijjijiijzc xxixixjx或或（3）任务A由甲或丙完成，任务C由丙或

36、丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项。管理运筹学管理运筹学 第第4章章 整数规划与分配问题整数规划与分配问题252942373820333427284042362345MMMCMM算算机机求求解解效效率率矩矩:n1.基本概念基本概念n变量取整数的规划问题称为整数规划。当变量全部取整数，称为纯变量取整数的规划问题称为整数规划。当变量全部取整数，称为纯整数规划；变量部分取整数，称为混合整数规划；变量取二进制称整数规划；变量部分取整数，称为混合整数规划；变量取二进制称为为0-1规划。规划。n2.基本要求基本要求n要求了解整数规划的分枝定界法、要求了解整数规划的分枝定界法、0-1规划的隐枚举法。规划的隐枚举法。n熟练掌握分配问题的匈牙利法。熟练掌握分配问题的匈牙利法。n至少掌握一种软件求解整数与至少掌握一种软件求解整数与0-1规划及分配问题。规划及分配问题。n3.0-1变量变量n0-1变量在数学建模中的应用，掌握变量在数学建模中的应用，掌握4.2.4给出的给出的8种情况。种情况。n4.典型应用典型应用n选址问题，集合覆盖问题，任务分派问题选址问题，集合覆盖问题，任务分派问题n作业作业:P33-36：2,4,5,6,7,9本章小结管理运筹学 第4章 整数规划与分配问题