第三章-整数规划模型08-5课件.ppt

1、第三章 整数规划3.1 整数规划简介n要求所有 xj 的解为整数，称为纯整数规划n要求部分 xj 的解为整数，称为混合整数规划n对应没有整数解要求的线性规划称之为松弛问题n整数规划的解是可数个的，最优解不一定发生在极点n整数规划的最优解不会优于其松弛问题的最优解njxmibxatsxcxfjnjijijnjjj,2,1,0,2,1,),(.)(max(min)11且为整数3.2 整数规划问题及其数学模型1 1、生产计划问题、生产计划问题例例3.2.1 3.2.1 某工厂生产某工厂生产A1A1、A2A2两种产品，产品分别由两种产品，产品分别由B1B1、B2B2两种部件组装两种部件组装而成。每件产

2、品所用部件数量和部件的产量限额以及产品利润如下表而成。每件产品所用部件数量和部件的产量限额以及产品利润如下表所示，应如何安排所示，应如何安排A1A1、A2A2的产量，该厂才能获得最大利润？的产量，该厂才能获得最大利润？部件部件产品产品B1B1B2B2利润（百元）利润（百元）A1A16 61 11515A2A24 43 32020最大产量最大产量25251010解：设x1、x2分别表示产品A1、A2的产量，则该问题的数学模型为且皆为整数,0,010325462015max21212121xxxxxxxxZ3.2 整数规划问题及其数学模型2 2、投资项目选择问题、投资项目选择问题例例3.2.2 3

3、.2.2 某单位有某单位有5 5个拟选择的投资项目，其所需投资额与期望收益如下表所个拟选择的投资项目，其所需投资额与期望收益如下表所示。由于各项目之间有一定联系，示。由于各项目之间有一定联系，A A、C C、E E之间必须选择一项，且仅需选择之间必须选择一项，且仅需选择一项；一项；B B和和D D之间需选择且仅需选择一项；之间需选择且仅需选择一项；C C的实施必须以的实施必须以D D的实施为前提条的实施为前提条件。该单位共筹集资金件。该单位共筹集资金1515万元，应选择哪些项目投资，使期望收益最大？万元，应选择哪些项目投资，使期望收益最大？项目项目所需投资额（万元）所需投资额（万元）期望收益（

4、万元）期望收益（万元）A A6.06.010.010.0B B4.04.08.08.0C C2.02.07.07.0D D4.04.06.06.0E E5.05.09.09.03.2 整数规划问题及其数学模型解：解：考虑到有的项目有可能被选中，也有可能不被选中，设决策变量考虑到有的项目有可能被选中，也有可能不被选中，设决策变量x xi i(i=1,2,3,4,5)(i=1,2,3,4,5)分别表示项目分别表示项目A A、B B、C C、D D、E E，且定义，且定义)5,4,3,2,1(10iiixi被选中项目不被选中项目由于A、C、E之间必须且仅需选择一项，故有x1+x3+x5=1与此类似，

5、B、D之间有关系式x2+x4=1由C的实施必须以D的实施为前提，因此，若x4=0(即D不实施)，则x3=0(即C一定不实施）；若x4=1(即D实施），则x3=0或1(即C可实施，也可不实施），因此有x3x4,即x3-x40对所有项目投资总额的限制条件为6x1+4x2+2x3+4x4+5x5153.2 整数规划问题及其数学模型目标函数为期望收益最大，可表示为目标函数为期望收益最大，可表示为max Z=10 xmax Z=10 x1 1+8x+8x2 2+7x+7x3 3+6x+6x4 4+9x+9x5 5因此，此问题的数学模型为因此，此问题的数学模型为)5,4,3,2,1(,1015542460

6、11967810max54321434253154321ixxxxxxxxxxxxxxxxxxZi或皆为此问题的所有决策变量只限取0或1，因此，称为0-10-1规划规划对实际问题建立数学模型，常可借助0-1变量，使含“非此即彼”的、相互排斥的决策变量和约束条件寓于同一模型之中。3.2 整数规划问题及其数学模型3 3、指派问题、指派问题例例3.2.3 3.2.3 现有现有A1A1、A2A2、A3A3、A4A4四人，每人都能完成工作四人，每人都能完成工作B1B1、B2B2、B3B3、B4B4四项中四项中的一项。下表列出了他们完成各项工作所需的时间。如果每项工作需安排的一项。下表列出了他们完成各项工

7、作所需的时间。如果每项工作需安排且仅需安排一人完成。问如何安排四人可使完成四项任务所花费的总时间且仅需安排一人完成。问如何安排四人可使完成四项任务所花费的总时间最少？最少？工作工作人人B1B1B2B2B3B3B4B4A1A13 3141410105 5A2A210104 412121010A3A39 9141415151313A4A47 78 811119 93.2 整数规划问题及其数学模型解：由于每项工作需安排一人且仅需一人去完成，所以，设解：由于每项工作需安排一人且仅需一人去完成，所以，设x xijij表示表示AiAi去去做做BjBj工作（工作（i,j=1,2,3,4i,j=1,2,3,4

8、），且），且工作不被安排做当工作被安排做当BjAiBjAixij01则该问题的数学模型是)4,3,2,1,(,10111111119118713151491012410510143min443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211jixBjxxxxxxxxxxxxxxxxAixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZji或工作只有一人去做表示只做一项工作表示3.3 分枝定界法3.3.1 思路与解题步骤n只解松弛问题,通过分枝

9、，逐步缩小目标函数的上下界之差1、在全部可行性域上解松弛问题n若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程n若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分n构造两个新的约束条件 xk bk 和 xk bk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题 定界过程n设两个分枝的松弛问题分别为问题 1 和问题 2，它们的最优解有如下情况表3.3.1 分枝问题解可能出现的情况序序号号 问问题题 1 1 问问题题 2 2 说说 明明 1 无无可可行行解解 无无可可行行解解 整整数数规规划划无无可可行行解解 2 无无可可行行解解 整整数

10、数解解 此此整整数数解解即即最最优优解解 3 无无可可行行解解 非非整整数数解解 对对问问题题 2 继继续续分分枝枝 4 整整数数解解 整整数数解解 较较优优的的一一个个为为最最优优解解 5 整整数数解解，目目标标函函数数优优于于问问题题 2 非非整整数数解解 问问题题 1 的的解解即即最最优优解解 6 整整数数解解 非非整整数数解解，目目标标函函数数优优于于问问题题 1 问问题题 1 1 停停止止分分枝枝(剪剪枝枝)，其其整整数数解解为为界界，对对问问题题 2 继继续续分分枝枝 7 非非整整数数解解 非非整整数数解解 对对目目标标函函数数较较优优的的一一个个继继续续分分枝枝 情况情况 2,4

11、,5:对该分枝，找到最优解对该分枝，找到最优解情况情况 3,7:在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6:问题问题 1 的整数解作为界被保留，用于以后与的整数解作为界被保留，用于以后与问题问题 2 的后续分枝所得到的解进行比较，结论如情的后续分枝所得到的解进行比较，结论如情况况 4 或或 53.3.2 分枝定界法举例例3.3.1 且为整数 0,01 3 25462015max21212121xxxxxxxxZ解解 1.松弛问题的最优解为 x1=2.5,x2=2.5,Z=87.5 为上 界，令下界为Z=02.由 于x1=2.5不为整数，分别增加新的约束条件x1 2和 x1

12、 3 得到两个分枝，它们的松弛问题如下：0,2 01 3 2546)1(2015max211212121xxxxxxxxxZ问题 0,3 01 3 2546)2(2015max211212121xxxxxxxxxZ问题123.解问题（1）的松弛问题，问题（2）暂时记录下来.问题（1）的松弛问题最优解为 x1=2,x2=2.67,Z=83.3 由于x2不为整数，对问题（1）分别增加新的约束条件x2 2.x2 3，分枝为两个子问题，它们的松弛问题如下：0,32 01 3 2546)4(2015max2121212121xxxxxxxxxxZ问题 0,2 201 3 2546)3(2015max21

13、21212121xxxxxxxxxxZ问题134.解问题（3）的松弛问题，问题（4）暂时记录下来.问题（3）的松弛问题最优解为 x1=2,x2=2,Z=70 由于解为整数，问题（3）不再分枝，目标函数新的下界为Z=max0,70=70.5.对记录下来的问题，依“后进先出”的原则进行求解.对问题（4）进行求解，最优解为 x1=1,x2=3,Z=75 由于解为整数，问题（4）不再分枝，目标函数新的下界为Z=max70,75=75.X3=3X3=3X1 Z=75.对问题（2）进行分枝,增加新的约束条件 x2 1.x2 2，分枝为两个子问题，它们的松弛问题如下：0,1 301 3 2546)5(201

14、5max2121212121xxxxxxxxxxZ问题 0,23 01 3 2546)6(2015max2121212121xxxxxxxxxxZ问题157.7.对问题（5）进行求解，最优解为 x1=3.5,x2=1,Z=72.5 由于Z=72.5=4X3=6X10，则令yi=1-xi替换xi，于是yi在目标函数中的系数变为负，且yi也为0-1变量;(3)如果约束条件为“”，则可两边乘以-1，改为“”型(4)如果有k个等式约束，则可用以下(k+1)个“”约束代替。kjjkjniiijniiiijnijiijbxakjbxakjbxa11111),2,1(),2,1(3.4.2 隐枚举法基本思路

15、：（1）首先令全部变量取0，如果此解可行，则为最优解，最优值为0，计算终止；否则，（2）有选择地指定某个变量为0或1，并把它们固定下来（称为固定变量），其他变量为自由变量，将原问题分枝成两个子问题.对每个子问题，取自由变量均为0，继续分别检验；（3）对某个子问题，如果其有解，则停止分枝，返回；如果其目标函数值优于下界（初始设为-Inf)，则以其目标函数值为原问题的一个下界；否则不对界作修改。（4）如果无解，且取自由变量均为0时的目标函数值大于界，则继续步骤（2）进行分枝；否则，停止分枝，返回（5）以上分枝、定界的过程至所有子问题停止分枝，或没有自由变量为止（6）问题的最优解为最大下界值对应的可

16、行解。（7）在第（2）步中，选择变量为固定变量的原则是：能使所有的约束到可行情况的总距离最小，所谓到可行情况的距离，是指将约束变为可行情况，应在约束的左端所必须减少的数值例3.4.2用隐枚举法求解如下0-1规划问题)3,2,1(1073257324625624.161017max32132132132321jxxxxxxxxxxxxtsxxxZj或解：（1）令x1=1-y1,x2=1-y2,x3=1-y3,代入原问题，将其化为规范型)4()3()2()1()3,2,1(1033252324225024.)161017(max43max32132132132321jyyyyyyyyyyyytsy

17、yySZj或例3.4.2(2)(2)目标函数值的下界设为目标函数值的下界设为-Inf-Inf;视视y y1 1,y,y2 2,y,y3 3均为自由变量均为自由变量，令，令(y(y1 1,y,y2 2,y,y3 3)=(0,0,0)=(0,0,0)，检验知，此解不可行；，检验知，此解不可行；(3)(3)选择固定变量：各变量到可行情况的距离如下表所示：选择固定变量：各变量到可行情况的距离如下表所示：(1)(1)(2)(2)(3)(3)(4)(4)总距离总距离目标系数目标系数 固定变量固定变量Y Y1 1=1=10 00 00 00 00 0-17-17Y Y2 2=1=10 01 10 01 12

18、 2-10-10Y Y3 3=1=10 00 00 00 00 0-16-16 因此：以y3为固定变量，令y3=1,y3=0，将原问题分解为两个子问题)2,1(100255240524.101716max)1()1(2121212213jyyyyyyyytsyySyj或问题)2,1(103252242504.1017max)0()2(2121212213jyyyyyyyytsyySyj或问题例3.4.2(4)(4)检验问题检验问题(1)(1)：令自由变量：令自由变量(y1,y2)=(0,0)(y1,y2)=(0,0)，知其可行，连同固定变量，知其可行，连同固定变量y3=1y3=1，有变量，有变

19、量(y1,y2,y3)=(0,0,1)(y1,y2,y3)=(0,0,1)，目标函数值为，目标函数值为-16-16，优于当前下界，优于当前下界-Inf-Inf，因此，设下界为，因此，设下界为-16-16；返回。；返回。(5)(5)检验问题检验问题(2)(2)：令自由变量：令自由变量(y1,y2)=(0,0)(y1,y2)=(0,0)，知其不可行，目标函数值，知其不可行，目标函数值为为0 0，优于当前下界，优于当前下界-16-16，因此应继续分枝；，因此应继续分枝；(6)(6)选择固定变量，其与可行情况的距离如下表：选择固定变量，其与可行情况的距离如下表：(1)(1)(2)(2)(3)(3)(4

20、)(4)总距离总距离目标系数目标系数 固定变量固定变量Y Y1 1=1=10 00 00 00 00 0-17-17Y Y2 2=1=10 01 10 01 12 2-10-10虽然，选择y1为固定变能使所有的约束到可行情况的总距离最小，但y1=1，y2=0 时，目标函数值为为17，小于当前下界，小于当前下界16。因此，选择y2为固定变量，令y2=0,1，将问题(2)分解为两个子问题。例3.4.2)1(10150415.1710max)1()3(11112jyyyytsySyj或问题)1(10352425.17max)0()4(11112jyyyytsySyj或问题（7）检验问题(4)知，自由

21、变量y1=0不可行，y1=1所得的目标函数值-17小于目标函数值的下界-16，故返回（8）检验问题(3)知，自由变量y1=0不可行，y1=1所得的目标函数值-27小于目标函数值的下界-16，故返回（9）总之，此问题的解为(0,0,1)，目标函数值为-163.5 指派问题的解法例3.5.1 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表3.6.1，问如何分配任务使完成四项任务的总工时耗费最少？1,0,2,1 1,2,1 1)0(,)(min1111ijniijnjijijninjijijxnjxnixcxcxf任任务务

22、工工时时ABCD人人员员人人员员甲甲109781乙乙58771丙丙54651丁丁23451任任务务11113.5.1 指派问题的数学模型模型中：xij 为第 i 个工人是否分配去做第 j 项任务；cij 为第 i 个工人为完成第 j 项任务时的工时消耗；cijnn 称为效率矩阵njijijixij,2,1,01项任务个工人未分配去做第当第项任务个工人分配去做第当第 指派指派问题是运输问题是运输问题问题的特例的特例 指派问题指派问题不但是整数规划，而且是不但是整数规划，而且是0 1规划规划 指派问题有指派问题有2n个约束条件，但有且只有个约束条件，但有且只有n个非零解，是高个非零解，是高度退化的

23、度退化的3.5.2 匈牙利算法定理 1 如果从效率矩阵cijnn中任何一行各元素分别减去一个常数 ui，从任何一列各元素分别减去一个常数 vj，所得新的效率矩阵bijnn的指派问题的最优解等价于原问题的最优解。证明：略定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略匈牙利算法的基本思路：n根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 n 个不同行不同列的零，就找到了最优解n若覆盖变换后的效率矩阵零元素的直线少于n 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零匈牙利算法的步骤：例3.5

24、.1第一步：变换效率矩阵，使每行每列至少有一个零n行变换：找出每行最小元素，从该行各元素中减去之n列变换：找出每列最小元素，从该列各元素中减去之2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910换变列换变行第二步：检查覆盖所有零元素的直线是否为第二步：检查覆盖所有零元素的直线是否为n n条条划线规则划线规则1 1、逐行检查，若该行只有一个未标记的零，对其加逐行检查，若该行只有一个未标记的零，对其加()()标记，标记，将将 ()()标记元素同行同列上其它的零打上标记元素同行同列上其它的零打上*标记。若该行有二标记。若该行有二个以

25、上未标记的零，暂不标记，转下一行检查，直到所有行检个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；查完；匈牙利算法的步骤：例3.5.12、逐列检查，若该列只有一个未标记的零，对其加、逐列检查，若该列只有一个未标记的零，对其加()标记，将标记，将()标标记元素同行同列上其它的零打上记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；零，暂不标记，转下一列检查，直到所有列检查完；221*0*02)0(1123)0(*0)0(23221*00201123)0(0023查检列逐查检行逐3、重复、重复1、2后

26、，可能出现三种情况：后，可能出现三种情况：a.每行都有一个每行都有一个(0)，显然已找到最优解，令对应，显然已找到最优解，令对应(0)位置的位置的 xij=1；b.仍有零元素未标记，此时，一定存在某些行和列同时有多个零，仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用称为僵局状态，因为无法采用 1、2 中的方法继续标记。中的方法继续标记。打破僵局：令未标记零对应的同行同列上其它未标记零的个数为该零打破僵局：令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记的指数，选指数最小的先标记()；采用这种方法直至所有零都被标；采用这种方法直至所

27、有零都被标记，或出现记，或出现 情况情况 a，或，或 情况情况 c。匈牙利算法的步骤：例3.5.1c.c.所有零都已标记所有零都已标记，但标有，但标有()()的零的个数少于的零的个数少于n ；开始开始划线过程划线过程：I.I.对没有标记对没有标记 ()()的行打的行打 II.II.对打对打 行上所有其它零元素对应的列打行上所有其它零元素对应的列打 III.III.再对打再对打 列上有列上有 ()()标记的零元素对应的行打标记的零元素对应的行打 IV.IV.重复重复IIII、III III，直至无法继续，直至无法继续V.V.对没有打对没有打 的行划横线，对所有的行划横线，对所有打打 的列划垂线的

28、列划垂线 221*0*02)0(1123)0(*0)0(23 划线后会出现两种情况：划线后会出现两种情况：(1)(1)标记标记()()的零少于的零少于n n个，但划有个，但划有 n n条直线，说明矩阵中已存在条直线，说明矩阵中已存在 n n 个个不同行不同列的零，但打破僵局时不同行不同列的零，但打破僵局时选择不合理，没能找到。回到选择不合理，没能找到。回到 b b 重新标记；重新标记；(2)(2)少于少于n n条直线，到第三步条直线，到第三步；匈牙利算法的步骤：例3.5.1第三步：进一步变换，第三步：进一步变换，增加新的零增加新的零；I.在未划线的元素中找出值最小者，设其值为在未划线的元素中找

29、出值最小者，设其值为 II.对未被直线覆盖的各元素减去对未被直线覆盖的各元素减去 III.对两条直线交叉点覆盖的元素加上对两条直线交叉点覆盖的元素加上 IV.只有一条直线覆盖的元素保持不变只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用以上步骤实际上仍是利用定理 1 221*0*02)0(1123)0(*0)0(2311000202012000241 第四步：抹除所有标记，回到第二步，重新标记第四步：抹除所有标记，回到第二步，重新标记；解优最列逐行逐记标11)0(*0)0(2*02*012)0(*0)0(24匈牙利算法的步骤：例3.5.111000202012000241 答：最优分配方案

30、为答：最优分配方案为 x13=x21=x34=x42=1，其余为，其余为0，即甲即甲C，乙，乙A，丙，丙D，丁，丁B，OBJ=20110002020120*0)0(24记记标标列列110*00202*012)0(*0)0(24局局僵僵破破打打221*0*02)0(1123)0(*0)0(236 0 2 0 5 0 4 0 0 3 0 1 0 2 0 0 局局僵僵破破打打3.5.3 匈牙利匈牙利算法的适用条件n要求所有要求所有cij 0n若某些若某些 cij 0，则利用定理，则利用定理 1 进行变换，使所有进行变换，使所有 cij 0n目标函数为目标函数为min型型n对于对于max型目标函数，将

31、效率矩阵中所有型目标函数，将效率矩阵中所有 cij反号，则等效于反号，则等效于求求min型问题；再利用定理型问题；再利用定理 1 进行变换，使所有进行变换，使所有 cij 0，则可，则可采用采用匈牙利匈牙利算法算法 打破僵局时选择不当的结果：打破僵局时选择不当的结果：结果仅出现结果仅出现 3 个标记个标记()，但却划出，但却划出 4 条线，条线，说明什么？！说明什么？！6 0 2 *0 5 0 4 *0 0 3 0 1 *0 2 *0 )0(局局僵僵破破打打6 *0 2 *0 5 )0(4 *0 0 3 0 1 *0 2 *0 )0(局局僵僵破破打打6 *0 2 *0 5 )0(4 *0 *0

32、 3 )0(1 *0 2 *0 )0(局局僵僵破破打打3.6 3.6 利用利用0-10-1变量处理变量处理“选择问题选择问题”n设设x xi i(i=1,2,n)(i=1,2,n)为为0-10-1变量变量,则则nx x1 1+x+x2 2+x+x3 3=1=1表示表示在在x x1 1,x,x2 2,x,x3 3中必须且只能选择一项中必须且只能选择一项nx x1 1+x+x2 2+x+xn n=k=k表示在表示在x x1 1,x,x2 2,x,xn n中必须且只能选择中必须且只能选择k k项项nx x1 1+x+x2 2+x+xn n=k=k=k表示表示在在x x1 1,x,x2 2,x,xn

33、n中至少选择中至少选择k k项项nX X1 1=x=x2 2表示表示x x1 1的成立以的成立以x x2 2的成立为先决条件的成立为先决条件3.6 3.6 利用利用0-10-1变量处理变量处理“选择问题选择问题”n例例3.6.1 3.6.1 试用试用0-10-1变量对下列各题分别表变量对下列各题分别表示成一般线性约束条件：示成一般线性约束条件：1.1.x x1 1+x+x2 2=2=8=82.2.变量变量x x3 3只能取值只能取值0,5,9,120,5,9,123.3.若若x x2 2=4,=0=0，否则，否则x x5 5=3=34.4.以以下下4 4个约束条件至少满足个约束条件至少满足2

34、2个个a.xa.x6 6+x+x7 7=2 b.x=2 b.x6 6=1 c.x=1 c.x7 7=5 d.x=3=33.6 3.6 利用利用0-10-1变量处理变量处理“选择问题选择问题”n解：解：为任意大正数或 MyyMxxMyxx,10832)1(2.121213,2,1,1011295.23213213iyyyyyyyxi或225544(1)3.3(1)01,xyMxy Mxy MxyMyM 或为任意大正数671627367412342154.3201,1,2,3,4ixxy Mxy Mxy Mxxy Myyyyyi 或线性规划有关的英文词汇nOperational/operation

35、s research 运筹学nLinear programming 线性规划 Feasible domain 可行域nConvex set 凸集 Basic feasible solutions 基础可行解nSimplex algorithm 单纯型法 Pivot 主元 Pivoting 主元变换nRevised,dual simplex algorithm 修正、对偶单纯型法nRelative cost 相对成本(机会成本)Shadow price 影子价格nSlack,Surplus,Artificial variable 松弛，剩余，人工变量nUnbounded,Infeasible,Degenerate solution 无界解,无可行解,退化解nDuality 对偶性 Primal,dual problem 原问题，对偶问题nComplementary slackness 互补松弛 Sensitivity analysis 灵敏度分析nTtransportation problem 运输问题nAssignment problem 任务分配(指派)问题nHungarian method 匈牙利算法