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

第4章整数规划与分配问题管理运筹学课件22020/3/5教学目标与要求【教学目标】通过本章学习，了解求解整数规划“分枝定界法”的其中思路，掌握0-1变量在数学建模中的应用；熟练掌握“匈牙利法”，至少掌握一种软件求得整数规划及分配问题的最优解。【知识结构】整数规划与分配问题分配问题数学模型0-1变量用法：添加特殊约束的LP变量取整的LP整数规划变量取0-1的LP数学模型计算机求解匈牙利法应用管理运筹学课件32020/3/5本章主要内容4.1整数规划4.1.1整数规划的概念4.1.2分枝定界法的基本思路*4.20-1规划4.2.10-1规划的概念4.2.20-1规划的隐枚举法简介*4.2.40-1变量在数学建模中的用途案例4-1球队队员筛选案例4-2选址问题案例4-3集合覆盖问题4.3分配问题4.3.1分配问题数学模型4.3.2分配问题的解题方法——匈牙利法案例4-4任务分派本章小结管理运筹学课件42020/3/5导入案例——集装箱托运计划某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利润以及托运所受到的限制如表4-1所示。问怎样安排托运计划，可使利润最大？货物每箱体积/米3每箱质量/50千克每箱利润/百元甲乙384356托运限制40241212121212maxz563843,0,xxxxxxxxxx≤40≤24≥取整数(1)(2)(3)(4)(5)设x1,x2表示两种货物装载数量(整数)，依题意有如下数学模型：在实际中，许多要求变量取整的数学模型，称为整数规划。本章将讨论整数规划求解的基本思路、0-1变量的用法、分配问题及匈牙利法，以及利用Excel,Lingo,WinQSB求解的演示。管理运筹学课件52020/3/54.1.1整数规划的基本概念整数规划（integerprogramming，IP）是指一类要求问题中的全部或一部分变量为整数的数学规划。在整数规划中，依决策变量的取值不同，又可进一步划分：如果所有变量都限制为整数，则称为纯整数规划（PureIntegerProgramming，PIP）；如果仅一部分变量限制为整数，则称为混合整数规划（MixedIntegerProgramming，MIP）；变量取二进制的整数规划则称为0-1规划（BinaryIntegerProgramming，BIP）。管理运筹学课件62020/3/54.1.2分枝定界法的基本思路*【例4.1】用图解法求解整数规划1212121212max563840(1)4324(2),0,zxxxxxxxxxx≤≤≥取整数分枝定界法(BranchandBoundMethod)用于求解整数规划问题，是在20世纪60年代初，由LandDoig和Dakin等人提出的。解(1)绘制直角坐标系，图示约束条件，图示目标函数一根基线(z=30)，使其平行移动，求得非整数最优解。该解的坐标为(72/23,88/23)，不在网格线的交叉点上，非整数解（非可行解）。①(2)对“解1”分枝定界：选取x1进行分枝定界：在原模型的基础上，分别添加x1≤3,x1≥4。优化结果“解2”，X=(3,31/8)，z=38.25；“解3”，X=(4,8/3)，z=36，均为非整数（非可行解）。(3)先对“解2”分枝定界：“解2”的坐标为(3,31/8)，分别添加x2≤3，x2≥4，优化结果“解4”，X=(3,3)，z=33，为可行解；“解5”，X=(8/3,4)，z=37.33，为非可行解。(4)再对“解3”分枝定界：“解3”的坐标，为非整数，添加x2≤2（x2≥3为非可行域），优化结果为X=(9/2,2)，z=34.5；再添加x1=4,x1≥5。解得整数解X=(4,2)，z=32和非整数解X=(21/4,1)，目标值z=31.25；整数解目标值大于非整数解，取(4,2)，得“解6”。01234567891011121314x1012345678x2②(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)，为非整数，添加x1≤2（x1≥3为非可行域），优化结果为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；“解6”X=(4,2)，z=32；“解7”X=(2,4)，z=34。相比较，目标值最大的为34，对应的最优方案。演示：利用WinQSB,ExcelORM+规划求解,ExcelORM+Lingo求例4.1管理运筹学课件72020/3/54.2.10-1规划的概念0-1规划是一种特殊类型的整数规划，即决策变量只取0或1。0-1规划在整数规划中占有重要地位，许多实际问题，例如指派问题、选址问题、送货问题都可归结为此类规划。求解0-1规划的常用方法是隐枚举法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。0-1规划的数学模型为：01max(min)(,)..zCXAXbstX取或≥≤管理运筹学课件82020/3/54.2.2隐枚举法简介12312312312123max322(1)44(2)s.t.+3(3),,01zxxxxxxxxxxxxxx例或12312312312123minmin32244s.t.+3,,01jcwxxxxxxxxxxxxxx改变符号,变为或112233111xxxxxx令12312312312123min352042s.t.1,,01wxxxxxxxxxxxxxx或23123123121123min352042s.t.+1,,01wxxxxxxxxxxxxxx目标系数升序排序或1.化成标准形式(1)目标函数:min,cj0(2)目标若max,目标系数改变符号,变为min;(2)若cj0,令yj=1-xj使其变正;(3)目标函数中,变量按目标系数从小到大排列,约束条件中也跟着相应改变.2.令标准化后的0-1问题所有变量为0,若满足约束,即为最优,否则转下步.3.按目标函数中排列顺序依次令各变量分别取1或0,进行枚举.123010xxx解得123101xxxmax4z管理运筹学课件92020/3/54.2.40-1变量在数学建模中的应用管理运筹学课件102020/3/5案例4-1球队队员筛选预备队员身高/厘米位置ABCDEF193191187186180185中锋中锋前锋前锋后卫后卫某校篮球队准备从以下6名预备队员中选拔3名为正式队员，并使平均的身高尽可能高。这六名预备队员情况如表所示。队员的挑选要满足下列条件：(1)6位预备队员选3名。(2)至少补充1名后卫人员。(3)B或E中间最多入选1名。(4)最多补充1名中锋。(5)无论B或D入选，F都不能入选。123456max193191187186180185zxxxxxx0,:1,iixi第名未进入正式队设第名进入正式队s.t.561(2)xx≥1234563(1)xxxxxx251(3)xx≤121(4)xx≤26461(5)1xxxx≤≤1~601x或管理运筹学课件112020/3/5案例4-2选址问题某公司在城市东、西、南三区拟建立门市部。计划有7个位置(点)Aj(j=1,…,7)可供选择。规定：在东区，由A1,A2,A3三个点至多选两个；在西区，由A4,A5两个点至少选一个；在南区，由A6,A7两个点至少选一个。设各位置建点的成本与预计利润见表，若建点总成本控制在100万元以内，试问应该选取哪几个点可使年利润为最大？。地点A1A2A3A4A5A6A7建点成本20202524222423估计利润303035343840451:1270iiiAxi=A当被选中，设，，，当未被选中，123456712345671234567max30303534384045202025242224231002()s.t.+1()+1()01izxxxxxxxxxxxxxxxxxxxxxx东区西区南区或≤≤≥≥数学模型为：管理运筹学课件122020/3/5案例4-3集合覆盖问题街道1街道2街道3街道4街道5街道6街道101020303020街道210025352010街道320250153020街道430351501525街道530203015014街道620102025140某区有6个街道。这个区必须确定在什么地方修建消防站。在保证至少有一个消防站在每个街道的15min行驶时间内的情况下，这个区希望修建的消防站最少。各街道间行驶时间如表1,1,,60,:iiiix第街道设消防站第街道不设消防站设123456:maxzxxxxxx目标消防站数目最少12126343454562561~6:+1+1+1..+1+1+1=01xxxxxxxstxxxxxxxxxx约束少于10min到达各消防站至少存在1个≥≥≥≥≥≥或管理运筹学课件132020/3/54.3.1分配问题数学模型项目张王李赵仰泳蛙泳蝶泳自由泳37433330333329263842392937343029在管理活动中，人们会经常遇到这样的问题，某单位有n(n1)项工作任务，需要m(n1)个人去完成，并且每个人只干一件工作，每项工作都必须有人干，通过权衡，合理分派任务，使总的消耗(或收益)达到最小(或最大)的0-1规划问题，称为分配问题(AssignmentProblem，AP)导入案例运动项目分配问题某游泳队有四名运动员，其平时训练成绩(s/50m)如表所示。问如何安排可使总成绩最好？人员任务效率矩阵cij1,0,:ijijijx第分配给第人第不分给第人设11121314212223243132333441424344min37333837433342343329393030262929zxxxxxxxxxxxxxxxx111213142122232431323334414243441111xxxxxxxxxxxxxxxx每项任务交给一人01(1,...,4;1,...,4)ijxij或112131411222324213233334142434441111xxxxxxxxxxxxxxxx每人分给一项任务..st管理运筹学课件142020/3/54.3.1分配问题数学模型管理运筹学课件152020/3/54.3.2匈牙利法管理运筹学课件162020/3/54.3.2匈牙利法【例4.7】用匈牙利法求引例中的最小化分配问题。37333837433342343329393030262929Cmin33332926405410091401014033min40310024606000700002①⑥②③④⑤0100000110000010X0100000110000010X:129z最优值管理运筹