第五章运筹学整数线性规划ppt课件.ppt

《第五章运筹学整数线性规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《第五章运筹学整数线性规划ppt课件.ppt（94页珍藏版）》请在三一办公上搜索。

1、,第五章 整数线性规划,第五章 整数线性规划,第1节 整数线性规划的数学模型及解的特点第2节 分支定界解法第3节 0-1型整数线性规划第4节 指派问题,第1节 整数线性规划的数学模型及解的特点,一、整数线性规划的含义要求一部分或全部决策变量必须取整数值的线性规划问题。,第1节 整数线性规划的数学模型及解的特点,二、整数线性规划的数学模型,第1节 整数线性规划的数学模型及解的特点,整数线性规划的松弛问题不考虑整数条件，由余下的目标函数和约束条件构成的线性规划问题。,第1节 整数线性规划的数学模型及解的特点,三、整数线性规划的解的特点整数线性规划问题的可行域是它的松弛问题可行域的子集整数线性规划问

2、题的可行解是它的松弛问题的可行解整数线性规划问题最优解的目标函数值不优于它的松弛问题最优解的目标函数值,第1节 整数线性规划的数学模型及解的特点,四、整数线性规划的解法例1：某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大？,第1节 整数线性规划的数学模型及解的特点,例1：解：设x1，x2分别为甲、乙两种货物的托运箱数 max z =20 x1+10 x2 5x1+4x224 2x1+5x213 x1，x20 x1，x2整数,第1节 整数线性规划的数学模型及解的特点,A,松弛问题的最优解,第1节 整数线性规划的数

3、学模型及解的特点,A,整数线性规划问题的最优解,第1节 整数线性规划的数学模型及解的特点,例2：某宝石加工厂最近新到6粒大小、质量等级相似的钻石毛料，管理层有两种选择，一是切磨成一般的皇冠形，每粒可获利2.5千元；一是切磨成虽然较难切磨但当前市场较流行的心形，每粒可获利4千元。若切磨成皇冠形则每粒需要5个工作日，若切磨成心形则每粒需要9个工作日，由于工厂切工师傅较忙，最多只有45个工作日来做这批工作。另外，由于毛料自身形状的关系，其中只有4粒毛料可以切磨成皇冠形，而6粒毛料中任何一粒都可以切磨成心形。那么，管理层应如何决策才能使这批钻石获利最大？,第1节 整数线性规划的数学模型及解的特点,例2

4、：解：设x1，x2分别为切磨成皇冠形和切磨成心形的钻石粒数 max z =2.5x1+4x2 x1+x26 5x1+9x245 x14 x1，x20 x1，x2整数,第1节 整数线性规划的数学模型及解的特点,完全枚举法对于可行域有界的整数线性规划问题，整数线性规划的可行解是一个有限集，将这个集内的每一个点对应的目标函数值都一一计算出来，然后从中找出最优者，则为整数线性规划的最优解。,第1节 整数线性规划的数学模型及解的特点,小结（1）对整数线性规划问题的松弛问题的最优解中不符合整数要求的分量进行简单地取整，所得到的整数解可能不一定是整数线性规划问题的最优解，甚至也不一定是整数线性规划问题的可行

5、解（2）对于复杂的模型，完全枚举法费时，甚至不可能实现,第2节 分支定界解法,一、分支定界解法的思路分支定界解法是先求解整数线性规划的松弛问题，如果其最优解不符合整数条件，则用增加约束的办法求出整数线性规划问题的上下界，并把松弛问题的可行域分成互不重叠的子区域，再求解这些子区域的松弛问题，不断缩小整数线性规划问题上下界的差距，最后取得整数线性规划问题的最优解。,第2节 分支定界解法,二、分支定界解法的含义分支定界解法是一种部分枚举法，通过不断地分割松弛问题的可行域并进行比较，最终求得整数线性规划问题的最优解。,第2节 分支定界解法,三、分支定界解法的步骤第一步：求解松弛问题。（1）松弛问题无可

6、行解，则整数线性规划问题无可行解，计算停止；（2）松弛问题有最优解，并且符合整数线性规划问题的整数条件，则松弛问题的最优解就是整数线性规划问题的最优解，计算停止；（3）松弛问题有最优解，但是不符合整数线性规划问题的整数条件，则松弛问题的最优值是整数线性规划问题最优值的上界值（求极大时）或下界值（求极小时），下界值（求极大时）可暂定为-或上界值（求极小时）可暂定为+。,第2节 分支定界解法,第二步：分支。在松弛问题的最优解中任选一个不符合整数条件的变量xi，其值为bi，用bi表示小于bi的最大整数，构造以下两个约束条件：将这两个约束条件分别加入整数线性规划问题，形成两个子问题，再求解这两个子问题

7、的松弛问题。,第2节 分支定界解法,第三步：定界。以每个子问题的松弛问题为一分支标明求解的结果，与其他问题的解的结果相比较：（1）若解满足子问题的整数条件，则找到了一个整数线性规划问题的可行解，为新的下界值（求极大时）或上界值（求极小时） ；（若计算中同时出现两个及以上整数线性规划问题可行解，则选取其中最大（求极大时）或最小（求极小时）的一个保留）（2）若解不满足子问题的整数条件，则为新的上界值（求极大时）或下界值（求极小时）。（若所有子问题的最优解都不是整数线性规划问题可行解，则选取边界值最大（求极大时）或最小（求极小时）的子问题进一步再细分子问题，并求解）,第2节 分支定界解法,第四步：比

8、较与剪支。各分支的目标函数值中，若小于下界值（求极大时）或大于上界值（求极小时），则剪去该分支（用打表示）；若大于下界值（求极大时）或小于上界值（求极小时），且不符合整数条件，则回到第二步，对该分支继续分支。若除保留下来的可行解外，其余分支都被剪去，则该可行解是整数线性规划问题的最优解。,第2节 分支定界解法,要求：用分支定界解法求解下列整数线性规划问题。例3： max z=3x1+2x2 2x1+3x214 x1+0.5x24.5 x1，x20 x1，x2整数,第2节 分支定界解法,例4： max z =x1+4x2 -2x1+3x23 x1+2x28 x1，x20 x1，x2整数,第2节

9、分支定界解法,小结分支定界法：仅检查可行的整数组合的一部分，从而定出最优整数解。,作业5-1,作业5-1：用分支定界解法求解例2。 max z =2.5x1+4x2 x1+x26 5x1+9x245 x14 x1，x20 x1，x2整数,第3节 0-1型整数线性规划,一、整数线性规划问题的类型1、纯（全）整数线性规划：全部决策变量都必须取整数值的整数线性规划,第3节 0-1型整数线性规划,例5：某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定，服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。,第3节 0-1型整数线性规划,例5：解：

10、设在第j时段开始时上班的服务员人数为xj。,第3节 0-1型整数线性规划,2、0-1型整数线性规划：决策变量只能取值0或1的整数线性规划（1）0-1型变量的含义变量只能取值0或1。（2）0-1型变量的特点表示是或否表示系统是否处于某个特定状态表示决策时是否取某个特定方案当问题含有多项要素，每项要素都有两种选择表示二进制变量,第3节 0-1型整数线性规划,例：令,第3节 0-1型整数线性规划,例：设问题有有限项要素E1，E2，En，其中每项Ej有两种选择Aj和 ，（j=1，2，n）。令,第3节 0-1型整数线性规划,例：变量x可取0与9之间的任意整数。令,第3节 0-1型整数线性规划,例6：现有

11、资金总额为B。可供选择的投资项目有7个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,7)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,第3节 0-1型整数线性规划,例6：解：,第3节 0-1型整数线性规划,3、混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划,第3节 0-1型整数线性规划,例7：工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3

12、和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij（i，j=1，2，3，4）见下表。工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少。,第3节 0-1型整数线性规划,例7：解：,第3节 0-1型整数线性规划,二、0-1型整数线性规划的解法1、完全枚举法定义：含有n个变量，产生2n个可能的变量组合（每一个组合即变量取值为0或1），比较目标函数值确定最优解特点：适于变量个数n10的0-1型整数线性规划,

13、第3节 0-1型整数线性规划,2、隐枚举法定义：只检查2n个可能的变量组合的一部分，确定问题的最优解,第3节 0-1型整数线性规划,解题思路（1）某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行（2）确定一个可行解的目标函数值：对于目标函数值比它差的变量组合就不必再去检验它的可行性；对于目标函数值比它好的变量组合再去检验它的可行性,第3节 0-1型整数线性规划,解题步骤第一，按目标函数中各变量系数的大小顺序排列各变量，然后把约束条件做相应的调整。第二，在表中列出变量取值的全部组合（2n个），并分别计算各自的目标函数值。第三，以第一个可行解计算得出的目标函数值作为一个过滤

14、条件，比较表中其它目标函数值与该过滤条件：比它差的变量取值组合舍弃；比它好的变量取值组合保留，并检验约束条件，同时以其计算得出的目标函数值作为新的过滤条件替换上一个过滤条件。重复这个过程，直至所有变量取值组合的目标函数值都比较完成，从而得到最优解。,第3节 0-1型整数线性规划,要求：用隐枚举法求解下列0-1型整数线性规划。例8： max z =3x1-2x2+5x3 x1+2x2-x32 x1+4x2+x34 x1+x23 4x1+x36 x1，x2 ，x3=0或1,第3节 0-1型整数线性规划,例8：解： max z =-2x2+3x1+5x3 2x2+x1-x32 4x2+x1+x34

15、x2+x13 4x1+x36 x1，x2 ，x3=0或1,第3节 0-1型整数线性规划,例9： min z =2x1+5x2+3x3+4x4 -4x1+x2+x3+x40 -2x1+4x2+2x3+4x44 x1+x2-x3+x41 x1，x2，x3，x4=0或1,第3节 0-1型整数线性规划,例9：解： min z = 5x2+4x4+3x3+2x1 x2+x4 +x3 -4x10 4x2+4x4+2x3-2x14 x2+x4-x3+x11 x1，x2，x3，x4=0或1,第3节 0-1型整数线性规划,小结采用隐枚举法求解0-1型整数线性规划，可以减少计算次数，使最优解能较快地被发现,作业5

16、-2,作业5-2：用隐枚举法求解下列0-1型整数线性规划。1、 min z =4x1+3x2+2x3 2x1-5x2+3x34 4x1+x2+3x33 x2+x31 x1，x2，x3=0或12、 max z =3x1+2x2-5x3-2x4+3x5 x1+x2+x3+2x4+x54 7x1+3x3-4x4+3x58 11x1-6x2+3x4-3x53 x1，x2，x3，x4，x5=0或1,第4节 指派问题,一、指派问题的标准形式含义：将n项工作交给n个人去做，由于每个人做每一项工作所用的时间等成本不同，指派问题的目标是如何安排工作，使总的时间等成本最小。标准形式：有n个人和n件事，已知第i人做

17、第j事的费用为cij(i,j=1,2,n)，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。基本要求：在满足特定的指派要求条件下，使指派方案的总体效果最佳。,第4节 指派问题,二、指派问题的假设条件执行工作的人数和要完成的工作数量是相同的每个人只能做一件工作每件工作只能由一个人来完成系数矩阵：C=(cij)nn（1）矩阵C表示费用、成本、时间等（2）元素cij表示指派第i人去完成第j项任务时的费用（或时间、成本等）目标是如何分配工作，使总的成本最小,第4节 指派问题,例10：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们

18、将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，使所需总时间最少。,第4节 指派问题,例10：解：,第4节 指派问题,三、指派问题的数学模型,第4节 指派问题,数学模型的特点（1）特殊的0-1型整数线性规划问题（2）特殊的运输问题,第4节 指派问题,解矩阵：X=(xij)nn（1）矩阵每行各元素中都有且只有一个1，表示每个人必做且只做一件事（2）矩阵每列各元素中都有且只有一个1，表示每件事必有且只有一个人去做（3）有n!个可行解,第4节 指派问题,四、指派问题的解题方法匈牙利法（一）解题思路（1）若从指派问题的系数矩阵（cij）的某行（或某列）各元素分别减去一个

19、常数k，得到一个新的矩阵（cij），则以（cij）和（cij）为系数矩阵的两个指派问题有相同的最优解（2）独立0元素：位于不同行不同列的0元素（3）若在系数矩阵中找到n个独立0元素，则对应的指派方案总费用（或时间、成本等）为零，即为原指派问题的最优解,第4节 指派问题,（二）匈牙利法的解题步骤1、变换系数矩阵。具体做法：（1）从系数矩阵的每行元素减去该行的最小元素。（2）再从所得的系数矩阵的每列元素减去该列的最小元素。变换后，指派问题的系数矩阵中每行及每列都出现0元素，同时不出现负元素，得新的系数矩阵。,第4节 指派问题,2、在变换后的系数矩阵中确定独立0元素。具体做法：（1）从只有1个0元素

20、的行开始，给这个0元素加圈，记作，然后划去所在列的其它0元素，记作。（2）给只有1个0元素的列的0元素加圈，记作，然后划去所在行的其它0元素，记作。（3）重复12，直到所有0元素都被圈出或划掉为止，元素即为独立0元素。（4）若元素有n个，则已得最优解；若元素少于n，则转入3。最优解矩阵：独立0元素对应位置上的元素为1，其他元素为0。,第4节 指派问题,3、用最少的直线覆盖所有0元素，以确定该系数矩阵中能找出最多的独立0元素。具体作法：1）对没有元素的行打号。2）对已打号的行中所有元素所在的列打号。3）再对打号的列中所有元素所在的行打号。4）重复23，直到得不出新的打号的行和列为止。5）对没有打

21、号的行划一横线，对已打号的列划一竖线，得到覆盖所有0元素的最少直线数。6）若直线数少于n，则转入4；若直线数等于n，而元素少于n，则回到2，另行试指派。矩阵中独立0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,另行试指派例16,第4节 指派问题,4、继续变换系数矩阵。具体作法：1）在没有被直线覆盖的元素中找出最小元素。2）打号的行的各元素减去最小元素。3）打号的列的各元素加上最小元素。4）得新的系数矩阵，重复2，若找出n个独立0元素，则得最优解；否则返回3，重复34。,匈牙利法求解例10,第4节 指派问题,例10：解：最优解为 z*=28,第4节 指派问题,例1

22、1：求下表所示系数矩阵的指派问题的最小解。,第4节 指派问题,例11：解：多重最优解，为 z*=32,第4节 指派问题,小结（1）当指派问题的系数矩阵经过变换，遇到在所有的行和列中，0元素都不止一个时，可任选其中一个0元素加圈，并同时划去同行和同列中其他0元素。其最优解为多重最优解（2）匈牙利法充分利用指派问题的特殊性质，有效地减少计算量,第4节 指派问题,例12：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i=1,2, ,5)对新商店Bj(j=1,2, ,5)的建造费用的报价（万元）为cij(i,j=1,2, ,5) ，如下表所示。商

23、业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？,第4节 指派问题,例12：解：最优解为 z*=34,第4节 指派问题,五、非标准形式的指派问题处理方法：将非标准形式转化为标准形式，然后应用匈牙利法求解。,第4节 指派问题,最大化指派问题设最大化指派问题系数矩阵C=(cij)nn，令矩阵B=(bij)nn=(M-cij)nn，其中M是足够大的正数（通常选M=maxcij），则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同最优解。,第4节 指派问题,例13：某建筑公司所属五个工程队，现有五项工程需要该公司承包。考虑各方面原因，规定每个工程队只能包其中一项工

24、程，由于各队施工质量和技术水平的差异，其承包后各队的报酬不同，如下表所示。试问如何分配任务，使得该建筑公司获得最好的经济效益？,第4节 指派问题,例13：解：转化为求极小化问题，系数矩阵为,第4节 指派问题,最优解为 z*=60,第4节 指派问题,人数和事数不等的指派问题若人少事多，则添上一些虚拟的“人”，虚拟的“人”做各事的费用cij取“0”，表示这些费用实际上不会发生；若人多事少，则添上一些虚拟的“事”，虚拟的“事”被各人做的费用cij仍取“0”。,第4节 指派问题,例14：求下列系数矩阵的最小化指派问题。,第4节 指派问题,例14：解：转化为平衡指派问题，系数矩阵为,第4节 指派问题,最

25、优解为 z*=22,第4节 指派问题,某事一定不能由某人做的指派问题若某事一定不能由某个人做，则将相应的费用cij取“M”（M是足够大的正数）。,第4节 指派问题,例15：分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如下表所示，由于任务数多于人数，故考虑任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。,第4节 指派问题,例15：解：转化为平衡指派问题，系数矩阵为,第4节 指派问题,最优解为 z*=105,第4节 指派问题,例16：6个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示

26、，且规定每人只能做一项工作，一项工作只需1人操作，试求使总收益最大的分派方案？,第4节 指派问题,例16：解：转化为平衡指派问题，系数矩阵为,第4节 指派问题,转化为求极小化问题，系数矩阵为,直线数等于n，元素少于n,第4节 指派问题,多重最优解（之一）为 z*=43,第4节 指派问题,一个人可做几件事的指派问题若某个人可做几件事，则将该人化作相同的几个“人”来接受指派，这几个“人”做同一件事的费用cij相同。,第4节 指派问题,例17：对于例12的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，而让技术力量较强的建筑公司A1、A2和A3来承建。根据实际情况，可以允许每家建筑公

27、司承建一家或两家商店。求使总费用最少的指派方案。,第4节 指派问题,例17：方法一解：系数矩阵转化为,第4节 指派问题,转化为平衡指派问题，系数矩阵为,第4节 指派问题,多重最优解（之一）为z*=35,第4节 指派问题,方法二解：转化为平衡指派问题，系数矩阵为,第4节 指派问题,多重最优解（之一）为 z*=35,第4节 指派问题,例18：从A、B、C、D、E等5人中挑选4人去完成4项工作，已知每人完成各项工作的时间如下表所示，规定每项工作只能由其中一人单独完成，而每个人最多只能承担其中一项任务。又假设A必须保证分配一项任务，D因某种原因决定不同意承担第4项任务。在上述条件下，试问如何分配工作，使完成这4项任务所需的总时间为最少？,第4节 指派问题,例18：解：转化为平衡指派问题，并将系数矩阵转置,第4节 指派问题,最优解为 z*=21,作业5-3,作业5-3： 一、求下列系数矩阵的指派问题的最小解。1、 2、,作业5-3,二、有四个工人，要指派他们分别完成四项工作，每个人做各项工作所获得的收益如下表所示，问指派哪个人去完成哪项工作，可使总收益最大。,作业5-3,三、根据例15所示表，若考虑其中有一人完成两项，其他人每人完成一项。试确定最优分配方案，使完成任务的总时间最少。,