高等运筹第五讲刘巍大连海事大学

1、高等运筹学高等运筹学大连海事大学大连海事大学刘巍刘巍第二篇 运筹学中的数学规划 第四章第四章 线性规划线性规划 第五章第五章 非线性规划非线性规划 第六章第六章 锥规划、矩阵规划及变分不等式锥规划、矩阵规划及变分不等式 第七章第七章 整数规划整数规划 第八章第八章 动态规划动态规划 第九章第九章 向量优化（多目标优化）向量优化（多目标优化）第七章 整数规划 整数规划是带整数变量的最优化问题，即整数规划是带整数变量的最优化问题，即求解一个全部或部分变量为整数的多元函求解一个全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优数受约束于一组等式和不等式条件的最优化间题。化间题。 整数规

2、划的历史可以追溯到整数规划的历史可以追溯到20世纪世纪50年代，丹年代，丹齐格首先发现可以用齐格首先发现可以用0-1变量来刻画最优化模变量来刻画最优化模型中的固定费用、变量上界、非凸分片线性函型中的固定费用、变量上界、非凸分片线性函数等。他和富尔克森、约翰逊对旅行商间题的数等。他和富尔克森、约翰逊对旅行商间题的研究成为后来分支定界法和现代混合整数规划研究成为后来分支定界法和现代混合整数规划算法的开端。算法的开端。1958年戈莫里发现了第一个一般年戈莫里发现了第一个一般线性整数规划的收敛算法线性整数规划的收敛算法割平面方法。随着割平面方法。随着整数规划理论和算法的发展，整数规划已成为整数规划理论

3、和算法的发展，整数规划已成为应用最广泛的最优化方法之一，特别是近年来应用最广泛的最优化方法之一，特别是近年来整数规划算法技术和软件系统的发展和推广，整数规划算法技术和软件系统的发展和推广，整数规划得到了广泛的应用和发展。整数规划得到了广泛的应用和发展。 整数规划整数规划什么是整数规划？什么是整数规划？ 整数规划与线性规划有什么关系？整数规划与线性规划有什么关系？ 从集装箱托运谈起从集装箱托运谈起集装箱托运问题集装箱托运问题例例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。量、可

4、获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大件，问两种货物各托运多少件，可使获得利润最大?货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140 解：设解：设x1 、 x2分别为甲、乙两种货物托运的件数分别为甲、乙两种货物托运的件数，建立模型，建立模型 目标函数：目标函数： max z = 2x1 +3 x2 约束条件：约束条件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 为整数。为整数。如果去掉最后一个约束

5、，就是一个线性规划问题如果去掉最后一个约束，就是一个线性规划问题 求整数解的线性规划问题，不是用四舍五入法求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。解决的，而要用整数规划的方法加以解决。 在整数规划中，如果所有的变量都为非负整数在整数规划中，如果所有的变量都为非负整数，则称为，则称为纯整数规划问题纯整数规划问题；如果有一部分变量；如果有一部分变量为负整数，则称之为为负整数，则称之为混合整数规划问题混合整数规划问题。在整。在整数规划中，如果变量的取值只限于数规划中，如果变量的取值只

6、限于0和和1，这样，这样的变量我们称之为的变量我们称之为0-1变量变量。在纯整数规划和。在纯整数规划和混合整数规划问题中，如果所有的变量都为混合整数规划问题中，如果所有的变量都为0-1变量，则称之为变量，则称之为0-1规划规划。得到线性规划的最优解为得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为目标函数值为14.66。由图表可看出，整数规划的最优解为由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为目标函数值为14。12341232x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =61 1 整数规划的图解法整数规划的图解法1 1

7、整数规划的图解法整数规划的图解法性质性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。例例2 2： max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 为整数例3： max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x3 1

8、x1,x2,x3 0 x1，x3 为整数, x3 为0-1变量用管理运筹学软件求解得： x1 = 5 x2 = 2 x3 = 2 用管理运筹学软件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.252 2整数规划的计算机求解整数规划的计算机求解3 3整数规划的应用整数规划的应用 一、投资场所的选择一、投资场所的选择 例例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有市部，拟议中有10个位置个位置 aj (j1，2，3，10)可供选择，考虑到各地可供选择，考虑到各地区居民的消费水平及居民居住

9、密集度，规定：区居民的消费水平及居民居住密集度，规定： 在东区由在东区由a1 ， a2 ，a3 三个点至多选择两个；三个点至多选择两个； 在西区由在西区由a4 ， a5 两个点中至少选一个；两个点中至少选一个； 在南区由在南区由a6 ， a7 两个点中至少选一个；两个点中至少选一个； 在北区由在北区由a8 ， a9 ， a10 三个点中至少选两个。三个点中至少选两个。 aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示情况见表所示 (单位：万元单位：万元)。但投资总额不能超过。但投资总额不能超过720万元，问应

10、选择哪万元，问应选择哪几个销售点，可使年利润为最大几个销售点，可使年利润为最大?3 3整数规划的应用整数规划的应用解：解：设：设：0-1变量变量 xi = 1 (ai 点被选用）或点被选用）或 0 (ai 点没被选用）点没被选用）。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：max z =36max z =36x x1 1+40+40 x x2 2+50+50 x x3 3+22+22x x4 4+20+20 x x5 5+30+30 x x6 6+25+25x x7 7+48+48x x8 8+58+58x x9 9+61+61x x1010s.t. s.t. 100100

11、 x x1 1+120+120 x x2 2+150+150 x x3 3+80+80 x x4 4+70+70 x x5 5+90+90 x x6 6+80+80 x x7 7+140+140 x x8 8+160+160 x x9 9+180+180 x x1010 720 720 x x1 1 + + x x2 2 + + x x3 3 2 2 x x4 4 + + x x5 5 1 1 x x6 6 + + x x7 7 1 1 x x8 8 + + x x9 9 + + x x1010 2 2 x xj j 0 0 且且x xj j 为为0-10-1变量变量，i i = 1,2,3,

12、= 1,2,3,10,10二、固定成本问题 例例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 资源小号容器中号容器大号容器金属板（吨）248劳动力（人月）234机器设备（台月）123解：这是一个整数规划的问题。解：这

13、是一个整数规划的问题。 设设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设种性质，设 yi = 1(当生产第当生产第 i种容器种容器, 即即 xi 0 时时) 或或0（当不生产第（当不生产第 i种容种容器即器即 xi = 0 时）。时）。引入约束引入约束 xi m yi ，i =1，2，3，m充分大，以保证当充分大，以保证当 yi = 0 时，时，xi = 0 。 这样我们可建立如下的数学

14、模型：max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi m yi ，i =1，2，3，m充分大 xj 0 yj 为0-1变量，i = 1,2,3三、指派问题三、指派问题 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样

15、把现假设必须指派每个人去完成一项任务，怎样把 n n 项任务项任务指派给指派给 n n 个人，使得完成个人，使得完成 n n 项任务的总的效率最高，这就项任务的总的效率最高，这就是指派问题。是指派问题。例例6 6有四个工人，要分别指派他们完成四项不同的工作，每人做各有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。的消耗时间为最少。 工作工人abcd甲15182124乙19232218丙26171619丁19212317解：解：引入引入0 01 1变量变量 x

16、xijij，并令并令 x xij ij = 1(= 1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时) )或或0 0（当不指派第（当不指派第 i i人去完成第人去完成第j j项工作时项工作时) )这可以表示为一个这可以表示为一个0-1整数规划问题：整数规划问题：min min z=15z=15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x x2323+18+18x x2424+26+26x x3131+17+17x x3232+1+16 6x x3333+19+

17、19x x3434+19+19x x41 41 +21+21x x4242+23+23x x4343+17+17x x4444s.t. s.t. x x1111+ + x x1212+ + x x1313+ + x x1414= 1 (= 1 (甲只能干一项工作甲只能干一项工作) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一项工作乙只能干一项工作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一项工作丙只能干一项工作) ) x x4141+ + x x424

18、2+ + x x4343+ + x x4444= 1 (= 1 (丁只能干一项工作丁只能干一项工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( a= 1 ( a工作只能一人干工作只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( b= 1 ( b工作只能一人干工作只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( c= 1 ( c工作只能一人干工作只能一人干) ) x x1414+ + x x2424+ + x x3434+

19、+ x x4444= 1 ( d= 1 ( d工作只能一人干工作只能一人干) ) x xijij 为为0-10-1变量变量，i,j i,j = 1,2,3,4= 1,2,3,4四、分布系统设计四、分布系统设计例例7某企业在某企业在 a1 地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为 30 千箱，千箱，为了扩大生产，打算在为了扩大生产，打算在 a2，a3，a4，a5地中再选择几个地方建地中再选择几个地方建厂。已知在厂。已知在 a2 ， a3，a4，a5地建厂的固定成本分别为地建厂的固定成本分别为175千元、千元、300千元、千元、375千元、千元、500千元，另外，千元，

20、另外， a1产量及产量及a2，a3，a4，a5建成厂的产量，那时销地的销量以及产地到销地的单位运价建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千每千箱运费箱运费)如下表所示。如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小定成本和总的运输费用之和最小? b) 如果由于政策要求必须在如果由于政策要求必须在a2，a3地建一个厂，应在哪几个地方建地建一个厂，应在哪几个地方建厂厂? 销 地产 地b1b2b3产 量 (千 吨 )a184330a252310a343420a49753

21、0a5104240销 量 (千 吨 )302020解：解： a) 设 xij为从ai 运往bj 的运输量(单位千箱)， yk = 1(当ak 被选中时)或0（当ak 没被选中时),k =2,3,4,5这可以表示为一个整数规划问题：min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10 x51 +4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t. x11+ x12+ x13 30 ( a1 厂的产量限制) x21+ x22+ x23 10y2

22、 ( a2 厂的产量限制) x31+ x32+ x33 20y3 ( a3 厂的产量限制) x41+ x42+ x43 30y4 ( a4 厂的产量限制) x51+ x52+ x53 40y5 ( a5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( b1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( b2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( b3 销地的限制) xij 0，i = 1,2,3,4,5； j = 1,2,3， yk 为0-1变量，k =2,3,4,5五、投资问题五、投资问题

23、 例例8 8某公司在今后五年内考虑给以下的项目投资。已知：某公司在今后五年内考虑给以下的项目投资。已知：项目项目a a：从第一年到第四年每年年初需要投资，并于次年末回收本利从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为但要求第一年投资最低金额为4万元，第二、三、四年不限万元，第二、三、四年不限；项目项目b b：第三年初需要投资，到第五年末能回收本利第三年初需要投资，到第五年末能回收本利128，但规定最低投资，但规定最低投资金额为金额为3万元，最高金额为万元，最高金额为5万元万元； 项目项目 c：第二年初需要投资，到第五年末能回收本利：第二年初需要投资

24、，到第五年末能回收本利140%，但规定其投资，但规定其投资额或为额或为2万元或为万元或为4万元或为万元或为6万元或为万元或为8万元。万元。 项目项目 d：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投，此项投资金额不限。资金额不限。 该部门现有资金该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大使到第五年末拥有的资金本利总额为最大?解：解：1) 设设x xiaia、x xibib、x xicic、x xid id ( i 1，2，3，4，5)

25、分别表示第分别表示第 i 年年初给项目年年初给项目a，b，c，d的投资额；的投资额； 设设yia， yib，是，是01变量，并规定取变量，并规定取 1 时分别表示第时分别表示第 i 年给年给a、b投资，投资，否则取否则取 0（ i = 1, 2, 3, 4, 5）。）。 设设yic 是非负整数变量，并规定：第是非负整数变量，并规定：第2年投资年投资c项目项目8万元时，取值为万元时，取值为4；第第 2年投资年投资c项目项目6万元时，取值万元时，取值3；第；第2年投资年投资c项目项目4万元时，取值万元时，取值2；第第2年投资年投资c项目项目2万元时，取值万元时，取值1；第；第2年不投资年不投资c项

26、目时，取值项目时，取值0； 这样我们建立如下的决策变量：这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年 a x1a x2a x3a x4a b x3b c x2c=20000y2c d x1d x2d x3d x4d x5d 2 2）约束条件：）约束条件：第一年：年初有100000元，d项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1a+ x1d = 100000；第二年：a的投资第二年末才可收回，故第二年年初的资金为1.06x1d，于是x2a+x2c+x2d = 1.06x1d；第三年：年初的资金为 1.15x1a+1.06x2d，于是 x3a+x3b+

27、x3d = 1.15x1a+ 1.06x2d；第四年：年初的资金为 1.15x2a+1.06x3d，于是 x4a + x4d = 1.15x2a+ 1.06x3d；第五年：年初的资金为 1.15x3a+1.06x4d，于是 x5d = 1.15x3a+ 1.06x4d。 关于项目a的投资额规定: x1a 40000y1a ，x1a 200000y1a ，200000是足够大的数；保证当 y1a = 0时， x1a = 0 ；当y1a = 1时，x1a 40000 。 关于项目b的投资额规定: x3b 30000y3b ，x3b 50000y3b ； 保证当 y3b = 0时， x3b = 0

28、；当y3b = 1时，50000 x3b 30000 。 关于项目c的投资额规定: x2c = 20000y2c ，y2c = 0，1，2，3，4。3 3）目标函数及模型：）目标函数及模型： max z = 1.15x4a+ 1.40 x2c+ 1.28x3b + 1.06x5d s.t. x1a+ x1d = 100000； x2a+x2c+x2d = 1.06x1d； x3a+x3b+x3d = 1.15x1a+ 1.06x2d； x4a+x4d = 1.15x2a+ 1.06x3d； x5d = 1.15x3a+ 1.06x4d； x1a 40000y1a ， x1a 200000y1a

29、 ， x3b 30000y3b ， x3b 50000y3b ； x2c = 20000y2c ， yia， yib = 0 或 1，i = 1,2,3,4,5 y2c = 0，1，2，3，4 xia ，xib ，xic ，xid 0 ( i = 1、2、3、4、5） 4 4整数规划的分枝定界法整数规划的分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把

30、相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。 下面以例9予以说明。例9 用分枝定界法求解整数规划max 2x1+3x2s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1,x2 0且x1,x2为整数解: (一)先求出以下线性规划的解： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1,x2 0 得z1=14.66,x1=2.44,x2=3.26 (二)确定整数规划的最优目标函数值z*初始上界 和下界z。 分析后，

31、知道 =14.66，由观察法得下界z=13（当x1=2,x2=3时）。zz(三)将一个线性规划问题分为两枝，并求解。 可由x12或x13中取值。将线性规划1分解为两支，如下： 线性规划2： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1 2 x1,x2 0 解得z2=13.90,x1=2,x2=3.30 线性规划3： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1 3 x1,x2 0 解得z3=14.58,x1=3,x2=2.86(四)修改整数规划的最优目标函数的上下界。

32、 经分析，将上界 =14.66修改为 =14.58，z=13。(五)在线性规划2和线性规划3中选择一个上界最大的线性规划，即线性规划3，进行分枝。 线性规划3分解为线性规划4和线性规划5，如下： 线性规划4： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 4 x1 3 x2 2 x1,x2 0 解得z4=14,x1=4,x2=2 线性规划5： max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40 x2140 x1 3 x2 3 x1,x2 0 无可行解zz(六)进一步修改整数规划最优目标函数值z*的上下界。 从线

33、性规划2，4，5中修改上下界。分析后，可得 =14， z=14。都取线性规划2，4，5中的整数可行解的目标函数值的最大值。性质2： 当整数规划的最优目标函数值z*的上界 等于其下界z时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。zz用图8-2表示例9的求解过程与求解结果z线性规划线性规划1z1=14.66x1=2.44x2=3.26z z=13, =13, =14.66 线性规划线性规划2z2=13.90x1=2x2=3.30线性规划线性规划3z3=14.58x1=3x2=2.86线性规划线性规划4z4=14.00x1=4x2=2线性规划

34、线性规划5无可行解无可行解x12x13x22x23z z=13, =13, =14.58 z z=14, =14, =14图图8-28-2zz z 从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为a，将与其相对应的线性规划问题称为b： 第一步：求解问题b，可得以下情况之一： 1.b没有可行解，则a也没有可行解，求解过程停止。 2.b有最优解，且符合问题a的整数条件，则b的最优解即为a的最优解，求解过程停止。 3.b有最优解，但不符合a的整数条件，记其目标函数值为z1。 第二步：确定a的最优目标函数值z*的上下界，其上界即为z1, =z1,再用观察法

35、找到a的一个整数可行解，求其目标函数值作为z*的下界，记为z 。 第三步：判断 是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z的a的那个整数可行解；否则进行第四步。zz 第四步：在b的最优解中选一个最远离整数要求的变量，不妨设此变量为xj，以bj表示小于bj的最大整数，构造以下两个约束条件，并加入问题b，得到b的两个分枝b1和b2。xj bj和xj bj+1 第五步：求解b1和b2 。修改a问题的最优目标函数值z*的上下界， 和z 。 第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打表示），即以后不再考虑了。若大于 ，则不符合整数条件，则重复第三步至第六

36、步，直至 =z，求出最优解为止。 对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。zz整数规划问题的困难和挑战来源于三个方面整数规划问题的困难和挑战来源于三个方面: 一是大部分整数规划问题都是一是大部分整数规划问题都是np一难的，故本质一难的，故本质上不太可能存在和线性规划和凸规划一样有效的算上不太可能存在和线性规划和凸规划一样有效的算法法; 二是对整数点集合二是对整数点集合(如多面体格点理论和全单模理如多面体格点理论和全单模理论论)和整数变量的函数在数学上缺乏有力的理论和和整数变量的函数在数学上缺乏有力的理论和工具工具; 三是实际间题的规模往往超过现有算法的求解能力三是实际间题的

37、规模往往超过现有算法的求解能力，尽管现有的一些整数规划软件可以求解任意线性，尽管现有的一些整数规划软件可以求解任意线性、二次和非线性整数规划问题，但往往不能处理来、二次和非线性整数规划问题，但往往不能处理来源于实际间题的整数规划模型，例如运输和交通中源于实际间题的整数规划模型，例如运输和交通中的大规模的大规模0-1混合线性整数规划间题，金融优化中混合线性整数规划间题，金融优化中的离散约束问题等。的离散约束问题等。 整数规划未来发展方向和关键问题包括整数规划未来发展方向和关键问题包括: (1)整数多面体凸包的刻画整数多面体凸包的刻画; (2)随机整数规划随机整数规划; (3)多层整数规划多层整数

38、规划; (4)混合混合0-1二次整数规划二次整数规划; (5)协正规划协正规划; (6)半定整数规划。半定整数规划。第八章 动态规划 当系统模型具备马尔科夫性，同时目标函数当系统模型具备马尔科夫性，同时目标函数可分且嵌套单调时，基于贝尔曼提出的最优可分且嵌套单调时，基于贝尔曼提出的最优性原理，运用动态规划可将求解多阶段全局性原理，运用动态规划可将求解多阶段全局最优决策问题分解为一系列在各个时间段上最优决策问题分解为一系列在各个时间段上的局部优化问题。相比其它解法，特别是在的局部优化问题。相比其它解法，特别是在有扰动或在随机情况下，动态规划总是能有有扰动或在随机情况下，动态规划总是能有效地提供一

39、个在当前信息集下的最优反馈控效地提供一个在当前信息集下的最优反馈控制策略。制策略。马尔科夫性 在某些随机系统中，有一类具有“无后效性性质”，即当随机过程在某一时刻to所处的状态已知的条件下，过程在时刻tto时所处的状态只和to时刻有关，而与to以前的状态无关。这种在已知“现在”的条件下，“未来”与“过去”彼此独立的特性就被称为马尔科夫性，具有这种性质的随机过程就叫做马尔科夫过程，其最原始的模型就是马尔科夫链。贝尔曼“最优性原理” 这个原理归结为用一组基本的递推关系式使过程连续的最优转移，它可以求这样的最优解，这些最优解是以计算每个决策的后果并对今后的决策制定最优决策为基础的，但在求最优解时要按

40、倒过来的顺序进行，即从最终状态开始到初始状态为止。39动态规划动态规划1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理3动态规划的应用动态规划的应用(1)4动态规划的应用动态规划的应用(2)401 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点a到终点e之间各点的距离。求a到e的最短路径。bacbdbcdec41231231232216472483867561106437 51411 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例用穷举法的计算量用穷举

41、法的计算量: 如果从a到e的站点有k个，除a、e之外每站有3个位置则总共有3k-12条路径； 计算各路径长度总共要进行 (k+1) 3k-12次加法以及3k-12-1次比较。随着 k 的值增加时，需要进行的加法和比较的次数将迅速增加； 例如当 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014 次。若用1亿次/秒的计算机计算需要约508天。42bacbdbcdec41231231232216472483867561106437 51431 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例讨论： 1、以上求从a到e的最短路径

42、问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从di 、ci、bi、a到e的最短路径问题。 第四阶段：两个始点d1和d2，终点只有一个； 表10-1分析得知：从d1和d2到e的最短路径唯一。 阶段4本阶段始点（状态）本阶段各终点（决策）到e的最短距离本阶段最优终点（最优决策) e d1 d2 10* 6 10 6 e e44bacbdbcdec41231231232216472483867561106437 5145 第三阶段：有三个始点c1，c2，c3，终点有d1，d2，对始点和终点进行分析和讨论分别求c1，c2，c3到d1，d2 的最短路径问题： 表10-2分析得知：如果经过

43、c1，则最短路为c1-d2-e； 如果经过c2，则最短路为c2-d2-e； 如果经过c3，则最短路为c3-d1-e。 1 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 阶段3本阶段始点（状态）本阶段各终点（决策）到e的最短距离本阶段最优终点（最优决策) d1 d2 c1 c2 c3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 d2 d2 d146bacbdbcdec41231231232216472483867561106437 5147第二阶段：有4个始点b1,b2,b3,b4，终点有c1,c2,c3。对始点和终点

44、进行分析和讨论分别求b1,b2,b3,b4到c1,c2,c3 的最短路径问题： 表10-3 分析得知：如果经过b1，则走b1-c2-d2-e； 如果经过b2，则走b2-c3-d1-e； 如果经过b3，则走b3-c3-d1-e； 如果经过b4，则走b4-c3-d1-e。 1 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 阶段2本阶段始点（状态） 本阶段各终点（决策）到e的最短距离本阶段最优终点（最优决策) c1 c2 c3 b1 b2 b3 b4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11

45、=17 2+11=13 3+11=14 1+11=12 12 13 14 12 c2 c3 c3 c348bacbdbcdec41231231232216472483867561106437 5149 第一阶段：只有1个始点a，终点有b1,b2,b3,b4 。对始点终点进行分析和讨论分别求a到b1,b2,b3,b4的最短路径问题： 表10-4 最后，可以得到：从a到e的最短路径为a b4 c3 d1 e1 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 阶段1本阶段始点(状态) 本阶段各终点（决策）到e的最短距离本阶段最优终点(最优决策) b1 b2 b3 b4 a 4+12=16

46、 3+13=163+14=172+12=14 12 c250 以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从a到d的最短路径，同时，也得到了从图中任一点到e的最短路径。 以上过程，仅用了22次加法，计算效率远高于穷举法。bacbdbcdec412312312332164724 838675161060106121111121314144b127 5121 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例51一、基本概念： 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。 2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量

47、状态可以是连续的，也可以是离散的。 3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。 决策允许集合dk(sk)：在状态sk下，允许采取决策的全体。 4、策略pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。p1,n(s1)即为全过程策略。 5、状态转移方程 sk+1=tk(sk, xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理52 6、阶段指标函数vk(sk, xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。 过程指标函数vk,n(sk,

48、xk, xk+1, xn)：从状态sk出发，选择决策xk, xk+1, , xn所产生的过程指标。动态规划要求过程指标具有可分离性，即 vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+vk+1(sk+1, xk+1, , xn)称指标具有可加性，或 vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)vk+1(sk+1, xk+1, , xn)称指标具有可乘性。二、基本方程： 最优指标函数fk(sk)：从状态sk出发，对所有的策略pk,n，过程指标vk,n的最优值，即 ),()(,)(nkknksdxkkpsvsfoptkkk2 2基本概念、基

49、本方程与最优化原理基本概念、基本方程与最优化原理53 对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。nksfxsvsfkkkkksdxkkoptkkk, 2 , 1)(),()(11)(nksfxsvsfkkkkksdxkkoptkkk, 2 , 1)(),()(11)(2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化

50、原理54 三、最优化原理三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是最优的。2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理55一、资源分配问题一、资源分配问题 例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？ 表10-5 盈利 工厂设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2

51、7 10 6 3 9 11 11 4 12 11 12 5 13 11 123 3 动态规划的应用动态规划的应用(1)(1)56 解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、3）。 xk=分配给第k个设备台数。 已知s1=5, 并有 从与的定义，可知 以下我们从第三阶段开始计算。222223),(xsxstskskx33xs 3 3 动态规划的应用动态规划的应用(1)(1)111112),(xsxsts57 第三阶段: 显然将台设备都分配给第3工厂时， 也就是时，第3阶段的指标值（即第3厂的盈利） 为最大，即

52、 由于第3阶段是最后的阶段，故有 其中可取值为0,1,2,3,4,5。其数值计算见表106。 )5 , 4 , 3 , 2 , 1 , 0(33ss).,(),(max)(333333333ssrxsrsfx3x),(),(max3333333ssrxsrx3 3 动态规划的应用动态规划的应用(1)(1)33xs 58 表表10106 6 012345000014 4126623111134121243x3s),(333xsr)(33sf3*x3 3 动态规划的应用动态规划的应用(1)(1)59 其中表示取3子过程上最优指标值时的 决策，例如在表10-6中可知当=4时，有有 此时，即当时，此时

53、取 （把4台设备分配给第3厂）是最优决策，此时阶段指标值 （盈利）为12，最优3子过程最优指标值也为12。 第二阶段： 当把台设备分配给第2工厂和第3工 厂时，则对每个值，有一种最优分配方案，使最大盈利 即最优2子过程最优指标函数值为 3*x)(33sf3x3s;12)4 , 4(3r,12)4(3f43*x43s43x)5 , 4 , 3 , 2 , 1 , 0(22ss2s)(),(max)(33222222sfxsrsfx3 3 动态规划的应用动态规划的应用(1)(1)60 因为上式也可写成 其数值计算如表107所示。 表107 , 223xss0123450 00104 51206 5

54、4 1023011 56 110 1424012 114110 161,25012 512 116114 1102122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(223222222xsfxsrsfx3 3 动态规划的应用动态规划的应用(1)(1)61 其中在的这一行里，当时， 这里从表105中可知，把1台设备交给乙厂所得盈 利数即可，知，这里从表106查 即可知=11。同样可知当时，可知 ; 当时，；当时， ；当时， ；由于，不可能分2厂5 台设备，故时，栏空着不填。从 这些数值中取得最大即得，即有=16。在此行中 我

55、们在取最大值的 上面加一横以示 区别，也可知这时的最优决策为1或2。42s12x16115) 3() 1 , 4() 14() 1 , 4()(),(3232223222frfrxsfxsr) 1 , 4(2r5) 1 , 4(2r)3()14(33ff)3(3f) 3(3f22x16610)2()2 , 4()24()2 , 4()(),(3232223222frfrxsfxsr02x12120)04()0 , 4(32 fr32x411)34()3 , 4(32 fr42x11011)44()4 , 4(32 fr42s52x)54()5 , 4(32 fr)4(2f)4(2f)(),(2

56、23222xsfxsr2x3 3 动态规划的应用动态规划的应用(1)(1)62 第一阶段： 把台设备分配给第1，第2，第3厂时，最大 盈利为其中可取值0,1,2,3,4,5. 数值计算见表108 表10-8 然后按计算表格的顺序推算，可知最优分配方案有两个： 1.由于，根据，查表107可 知，再由 ，求得。即分配 给甲厂0台，乙厂2台，丙厂3台。 2.由于，根据 ，查表107可 )5(11ss),5(), 5(max)5(111111xfxrfx1x0123455 316 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr210147)(1xf1*x01*x50

57、51*12xss02*x3252*23xss333* sx21*x3251*12xss3 3 动态规划的应用动态规划的应用(1)(1)63 知，再由 ,求得， 即分配给甲厂2台，乙厂2台，丙厂1台。 这两种分配方案都能得到最高的总盈利21万元。 22*x1232*23xss133* sx3 3 动态规划的应用动态规划的应用(1)(1)64 二、背包问题二、背包问题 设有n种物品，每一种物品数量无限。第i种物品每件 重量为wi公斤，每件价值ci元。现有一只可装载重量为w 公斤的背包，求各种物品应各取多少件放入背包，使背 包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第i种 物品

58、装入背包的件数（i =1, 2, , n），背包中物品的总 价值为z，则 max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnw x1, x2, , xn0 且为整数。3 3 动态规划的应用动态规划的应用(1)(1)65 下面用动态规划逆序解法求解它。设 阶段变量k：第k次装载第k种物品（k=1, 2, , n） 状态变量sk：第k次装载时背包还可以装载的重量； 决策变量uk = xk：第k次装载第k种物品的件数； 决策允许集合：dk(sk) = xk | 0 xksk/wk，xk为整数； 状态转移方程： sk+1 = sk wkxk； 阶段指标： vk =

59、 ckxk； 最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使 用价值； 递推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xdk(sk) 终端条件： fn+1(sn+1) = 0。3 3 动态规划的应用动态规划的应用(1)(1)66 例3.某咨询公司有10个工作日可以去处理四种类型的咨 询项目，每种类型的咨询项目中待处理的客户数量、处理每个 客户所需工作日数以及所获得的利润如表109所示。显然该公 司在10天内不能处理完所有的客户，它可以自己挑选一些客 户，其余的请其他咨询公司去做，应如何选择客户使得在这1

60、0 个工作日中获利最大？ 表109 咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234432213472811203 3 动态规划的应用动态规划的应用(1)(1)67 解：用动态规划来求解此题。 我们把此问题分成四个阶段，第一阶段我们决策将 处理多少个第一种咨询项目类型中的客户，第二阶段决 策将处理多少个第二种咨询项目类型中的客户，第三阶 段、第四阶段我们也将作出类似的决策。我们设 分配给第k种咨询项目到第四种咨询项目的所 有客户的总工作日（第k阶段的状态变量）。 =在第k种咨询项目中处理客户的数量（第k阶段 的决策变量）。 已知10 并有 kx1s,),(11111