Data, Model and Decisions

1、2 2其它规划问题其它规划问题规划的组成规划的组成： 目标函数目标函数 opt（optimize） max z (f) 或或 min z(f) 约束条件约束条件 s.t. (subject to) 满足于满足于 决策变量决策变量 用符号来表示可控制的因素用符号来表示可控制的因素2022-3-2322.12.1整数规划整数规划2.22.2目标规划目标规划2.32.3动态规划动态规划42.1 2.1 整数规划整数规划 1 1整数规划的图解法整数规划的图解法 2 2整数规划的计算机求解整数规划的计算机求解 3 3整数规划的整数规划的应用应用5求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划

2、求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。解决。在整数规划中在整数规划中: : 如果所有的变量都为非负整数，则称为如果所有的变量都为非负整数，则称为纯整数规划问题纯整数规划问题； 如果只有一部分变量为非负整数，则称之为如果只有一部分变量为非负整数，则称之为混合整数规划问题混合整数规划问题。 如果所有的变量都为如果所有的变量都为0-10-1变量，则称之为变量，则称之为0-10-1规划规划。6 1 1整数规划的图解法整数规划的图解法例例8-1. 某公司拟用集装箱托运甲、

3、乙两种货物，这两种货物每某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4件，问两种货物各托运多少件，可使获得利件，问两种货物各托运多少件，可使获得利润最大润最大?货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制13651407解：设解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型分别为甲、乙两种货物托运的件数，建立模型 目标函数：目标函数

4、： Max z = 2x1 +3 x2 约束条件：约束条件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 为整数。为整数。如果去掉最后一个约束，就是一个线性规划问题。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，利用图解法，8得到线性规划的最优解为得到线性规划的最优解为x x1 1=2.44, x=2.44, x2 2=3.26,=3.26,目标函数值为目标函数值为14.6614.66。由图表可看出，整数规划的最优解为由图表可看出，整数规划的最优解为x x1 1=4, x=4, x2 2=2,=2,目标函数值目标函数

5、值为为1414。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=69性质性质1 1： 任何求任何求最大最大目标函数值的纯整数规划或混合整数目标函数值的纯整数规划或混合整数规划的最大目标函数值规划的最大目标函数值小于或等于小于或等于相应的线性规相应的线性规划的最大目标函数值；划的最大目标函数值； 任何求任何求最小最小目标函数值的纯整数规划或混合整数目标函数值的纯整数规划或混合整数规划的最小目标函数值规划的最小目标函数值大于或等于大于或等于相应的线性规相应的线性规划的最小目标函数值。划的最小目标函数值。10例例8-28-2： Max z = 3Max z = 3

6、x x1 1 + + x x2 2 + 3 + 3x x3 3 s.t. s.t. - -x x1 1 + 2 + 2x x2 2 + + x x3 3 4 4 4 4x x2 2 -3 -3x x3 3 2 2 x x1 1 -3-3x x2 2 + 2 + 2x x3 3 3 3 x x1 1, ,x x2 2, ,x x3 3 0 0 为整数为整数例例8-38-3： Max z = 3xMax z = 3x1 1 + x + x2 2 + 3x + 3x3 3 s.t. s.t. -x -x1 1 + 2x + 2x2 2 + x + x3 3 4 4 4x 4x2 2 -3x -3x3

7、 3 2 2 x x1 1 -3x -3x2 2 + 2x + 2x3 3 3 3 x x3 3 1 1 x x1 1,x,x2 2,x,x3 3 0 0 x x1 1，x x3 3 为整数为整数 x x3 3 为为0-10-1变量变量用用管理运筹学管理运筹学软件求解得：软件求解得： x x1 1 = 5 = 5 x x2 2 = 2 = 2 x x3 3 = 2 = 2 用用管理运筹学管理运筹学软件求解得：软件求解得： x x1 1 = 4 = 4 x x2 2 = 1.25 = 1.25 x x3 3 = 1 = 1 z = 16.25 z = 16.25 2 2整数规划的计算机求解整数规

8、划的计算机求解11 3 3整数规划的应用整数规划的应用 一、投资场所的选择一、投资场所的选择 例例8-4:京成畜产品公司计划在市区的东、西、南、北四区建立销售京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有门市部，拟议中有10个位置个位置 Aj (j1，2，3，10)可供选择，考虑到可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：各地区居民的消费水平及居民居住密集度，规定： 在东区由在东区由A1 ， A2 ，A3 三个点至多选择两个；三个点至多选择两个； 在西区由在西区由A4 ， A5 两个点中至少选一个；两个点中至少选一个； 在南区由在南区由A6 ， A7 两

9、个点中至少选一个；两个点中至少选一个； 在北区由在北区由A8 ， A9 ， A10 三个点中至少选两个。三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示情况见表所示 (单位：万元单位：万元)。但投资总额不能超过。但投资总额不能超过720万元，问应选择哪万元，问应选择哪几个销售点，可使年利润为最大几个销售点，可使年利润为最大?12解：设：解：设：0-1变量变量 xi = 1 (Ai 点被选用）或点被选用）或 0 (Ai 点没被选用）。点没被选用）。 这样我们可建立如下的数学模型：这样我们可

10、建立如下的数学模型：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. 100 100 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 x101072

11、0720 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,= 1,2,3,10,1013二、固定成本问题二、固定成本问题 例例8-5:高压容器公司制造小、中、大三种尺寸的金属容器，所用资源高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如为金属板、劳动力和机器设备，制造

12、一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、万元、5万元、万元、6万元，可使用的金属板有万元，可使用的金属板有500吨，劳动力有吨，劳动力有300人人/月，机器有月，机器有100台台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是费用：小号是l00万元，中号为万元，中号为 150 万元，大号为万元，大号为200万元。现在要制定万元。现在要制定一个生产计划，使获得的利润为最大。一个生产计划，使获得的利润为最大。1

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

14、= 0 。 yi=0 xi=0 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z = 4Max z = 4x x1 1 + 5+ 5x x2 2 + 6+ 6x x3 3 - 100y- 100y1 1 - 150y- 150y2 2 - 200y- 200y3 3s.t. 2s.t. 2x x1 1 + 4+ 4x x2 2 + 8+ 8x x3 3 500 500 2 2x x1 1 + 3+ 3x x2 2 + 4+ 4x x3 3 300 300 x x1 1 + 2+ 2x x2 2 + 3+ 3x x3 3 100 100 xi M yi ，i =1，2，3，

15、M充分大充分大 x xj j 0 0 y yj j 为为0-10-1变量变量，i i = 1,2,3= 1,2,315三、指派问题三、指派问题 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由于每个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把个人去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使得完成个人，使得完成 n n 项任务的总的效率最高，这就是项任务的总的效率最高，这就是指派问题。指派问题。例

16、例8-68-6有四个工人，要分别指派他们完成四项不同的工作，每人做各项有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。时间为最少。16解：解：引入引入0 01 1变量变量 x xijij，并令并令 x xij ij = 1(= 1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时) )或或0 0（当不指派第（当不指派第 i i人人去完成第去完成第j j项工作时项工作时) )这可以表示为一个这可以表示为一个0-1整数规划问题：整数规划问题：

17、Minz=15Minz=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+16+16x x3333+19+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

18、x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一项工作乙只能干一项工作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一项工作丙只能干一项工作) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (= 1 (丁只能干一项工作丁只能干一项工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( A= 1 ( A工作只能一人干工作只能一人干) ) x x1212+ + x x2222+

19、+ 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+ + x x4444= 1 ( D= 1 ( D工作只能一人干工作只能一人干) ) x xijij 为为0-10-1变量变量，i,j i,j = 1,2,3,4= 1,2,3,417四、分布系统设计四、分布系统设计例例8-7某企业在某企业在 A1 地已有一个工厂，其产品的生产能力为地已有一个

20、工厂，其产品的生产能力为 30 千箱，为了扩大千箱，为了扩大生产，打算在生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为地建厂的固定成本分别为175千元、千元、300千元、千元、375千元、千元、500千元，千元，另外，另外， A1产量及产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地建成厂的产量，那时销地的销量以及产地到销地的单位运价到销地的单位运价(每千箱运费每千箱运费:千元千元)如下表所示。如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总

21、问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小的运输费用之和最小? b) 如果由于政策要求必须在如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂地建一个厂，应在哪几个地方建厂? 18解：解： a) 设设 x xijij为从为从Ai 运往运往Bj 的运输量的运输量(单位千箱单位千箱)， y yk k = 1(= 1(当当A Ak k 被选中时被选中时) )或或0 0（当（当A Ak k 没被选中时没被选中时),),k k =2,3,4,5 =2,3,4,5这可以表示为一个整数规划问题：这可以表示为一个整数规划问题：Min z = 175Min

22、z = 175y y2 2+300+300y y3 3+375+375y y4 4+500+500y y5 5+8+8x x1111+4+4x x1212+3+3x x1313+5+5x x2121+2+2x x2222+3+3x x2323+4+4x x3131+ +3 3x x3232+4+4x x3333+9+9x x41 41 +7+7x x4242+5+5x x4343+10+10 x x51 51 +4+4x x5252+2+2x x5353其中前其中前4项为固定投资额，后面的项为运输费用。项为固定投资额，后面的项为运输费用。s.t. s.t. x x1111+ + x x1212

23、+ + x x1313 30 ( A 30 ( A1 1 厂的产量限制厂的产量限制) ) x x2121+ + x x2222+ + x x2323 10 10y y2 2 ( A ( A2 2 厂的产量限制厂的产量限制) ) x x3131+ + x x3232+ + x x33 33 20 20y y3 3 ( A ( A3 3 厂的产量限制厂的产量限制) ) x x4141+ + x x4242+ + x x43 43 30 30y y4 4 ( A ( A4 4 厂的产量限制厂的产量限制) ) x x5151+ + x x5252+ + x x53 53 40 40y y5 5 ( A

24、 ( A5 5 厂的产量限制厂的产量限制) ) x x1111+ + x x2121+ + x x3131+ + x x41 41 + + x x51 51 = 30 ( B= 30 ( B1 1 销地的限制销地的限制) ) x x1212+ + x x2222+ + x x3232+ + x x42 42 + + x x52 52 = 20 ( B= 20 ( B2 2 销地的限制销地的限制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 销地的限制销地的限制) ) x xijij 0

25、 0，i i = 1,2,3,4,5= 1,2,3,4,5； j j = 1,2,3= 1,2,3， y yk k 为为0-10-1变量，变量，k k =2,3,4,5=2,3,4,5。19五、投资问题五、投资问题( (第第4 4章）章） 例例8-88-8某公司在今后五年内考虑给以下的项目投资。已知：某公司在今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第四年每年年初需要投资，并于次年末回收本利从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为但要求第一年投资最低金额为4万元，第二、三、四年不限万元，第二、三、四年不限；项目项目B B：

26、第三年初需要投资，到第五年末能回收本利第三年初需要投资，到第五年末能回收本利128，但规定最低，但规定最低投资金额为投资金额为3万元，最高金额为万元，最高金额为5万元万元； 项目项目 C：第二年初需要投资，到第五年末能回收本利：第二年初需要投资，到第五年末能回收本利140%，但规定其，但规定其投资额或为投资额或为2万元或为万元或为4万元或为万元或为6万元或为万元或为8万元。万元。 项目项目 D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%，此，此项投资金额不限。项投资金额不限。 该部门现有资金该部门现有资金10万元，问它应如何确定给这些项目

27、的每年投资额，万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大使到第五年末拥有的资金本利总额为最大?20解：解：1) 设设x xiAiA、x xiBiB、x xiCiC、x xiD iD ( i 1，2，3，4，5)分别表示第分别表示第 i 年年初给项年年初给项目目A，B，C，D的投资额的投资额(元元)； 设设yiA， yiB，是，是01变量，并规定取变量，并规定取 1 时分别表示第时分别表示第 i 年给年给A、B投投资，否则取资，否则取 0（ i = 1, 3）。）。 设设yiC 是非负整数变量，并规定：第是非负整数变量，并规定：第2年投资年投资C项目项目8万

28、元时万元时，取值为取值为4；第第 2年投资年投资C项目项目6万元时，取值万元时，取值3；第；第2年投资年投资C项目项目4万元时，取值万元时，取值2；第第2年投资年投资C项目项目2万元时，取值万元时，取值1；第；第2年不投资年不投资C项目时，取值项目时，取值0； 这样我们建立如下的决策变量：这样我们建立如下的决策变量： 第第1 1年年 第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 A A x x1A 1A x x2A 2A x x3A3A x x4A4A B B x x3B3B C C x x2C2C=20000y=20000y2C2C D D x x1D 1D x x2D 2

29、D x x3D3D x x4D4D x x5D5D 212 2）约束条件：）约束条件：第一年：年初有第一年：年初有100000100000元，元，D D项目在年末可收回投资，故第一年年初应把全部资金投出去，项目在年末可收回投资，故第一年年初应把全部资金投出去，于是于是 x x1A1A+ + x x1D 1D = 100000= 100000；第二年：第二年：A A的投资第二年末才可收回，故第二年年初的资金为的投资第二年末才可收回，故第二年年初的资金为1.061.06x x1D1D，于是，于是x x2A2A+ +x x2C2C+ +x x2D2D = = 1.061.06x x1D1D；第三年：

30、年初的资金为第三年：年初的资金为 1.151.15x x1A1A+1.06+1.06x x2D2D，于是，于是 x x3A3A+ +x x3B3B+ +x x3D3D = 1.15 = 1.15x x1A1A+ 1.06+ 1.06x x2D2D；第四年：年初的资金为第四年：年初的资金为 1.151.15x x2A2A+1.06+1.06x x3D3D，于是，于是 x x4A 4A + + x x4D4D = 1.15 = 1.15x x2A2A+ 1.06+ 1.06x x3D3D；第五年：年初的资金为第五年：年初的资金为 1.151.15x x3A3A+1.06+1.06x x4D4D，于

31、是，于是 x x5D 5D = 1.15= 1.15x x3A3A+ 1.06+ 1.06x x4D4D。 关于项目关于项目A A的投资额规定的投资额规定: : x x1A1A 40000 40000y y1A1A ，x x1A1A 200000 200000y y1A1A ，200000200000是足够大的是足够大的数；保证当数；保证当 y y1A1A = 0 = 0时，时， x x1A1A = 0 = 0 ；当；当y y1A1A = 1 = 1时，时，x x1A1A 40000 40000 。 关于项目关于项目B B的投资额规定的投资额规定: : x x3B3B 30000 30000y

32、 y3B3B ，x x3B3B 50000 50000y y3B3B ； 保证当保证当 y y3B3B = 0 = 0时，时， x x3B3B = 0 = 0 ；当；当y y3B3B = 1 = 1时，时，50000 50000 x x3B3B 30000 30000 。 关于项目关于项目C C的投资额规定的投资额规定: : x x2C2C = 20000 = 20000y y2C2C ，y y2C2C = 0 = 0，1 1，2 2，3 3，4 4。223 3）目标函数及模型：）目标函数及模型： Max z = 1.15Max z = 1.15x x4A4A+ 1.40+ 1.40 x x2

33、C2C+ 1.28+ 1.28x x3B 3B + 1.06+ 1.06x x5D 5D s.t. s.t. x x1A1A+ + x x1D 1D =10=10； x x2A2A+ +x x2C2C+ +x x2D2D = 1.06 = 1.06x x1D1D； x x3A3A+ +x x3B3B+ +x x3D3D = 1.15 = 1.15x x1A1A+ 1.06+ 1.06x x2D2D； x x4A4A+ +x x4D4D = 1.15 = 1.15x x2A2A+ 1.06+ 1.06x x3D3D； x x5D 5D = 1.15= 1.15x x3A3A+ 1.06+ 1.0

34、6x x4D4D； x x1A1A 4 4y y1A1A ， x x1A1A 10 10y y1A1A ， x x3B3B 3 3y y3B3B ， x x3B3B 5 5y y3B3B ； x x2C2C = 2 = 2y y2C2C ， y y2C2C 4 4 x xiAiA ，x xiBiB ，x xiCiC ，x xiDiD 0 ( i = 1 0 ( i = 1、2 2、3 3、4 4、5 5）, ,y y1A1A， y y3B3B 为为0-10-1变量变量, ,y y2C 2C 整数整数 案例分析案例分析 教材教材P199案例分析案例分析9-122022-3-232324练练 习习

35、 教材教材P195习题习题2-1125 2.2 2.2 目标规划目标规划 1 1 目标规划问题举例目标规划问题举例 2 2 目标规划问题求解目标规划问题求解 3 3 复杂情况下的目标规划复杂情况下的目标规划 4 4 加权目标规划加权目标规划26 1 1目标规划问题举例目标规划问题举例多目标问题多目标问题例例1 1企业生产企业生产例例2 2商务活动商务活动例例3 3投资投资例例4 4裁员裁员例例5 5营销营销27 2 2目标规划问题求解目标规划问题求解 例例9-6一位投资商有一笔资金准备购买股票。资金总额为一位投资商有一笔资金准备购买股票。资金总额为90000元，目元，目前可选的股票有前可选的股

36、票有A和和B两种（可以同时投资于两种股票）。其价格以两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表及年收益率和风险系数如表1：股票股票价格（元）价格（元）年收益（元）年收益（元）年年风险系数风险系数A2030.5B5040.2从上表可知，从上表可知，A股票的收益率为（股票的收益率为（320）10015，股票，股票B的收益的收益率为率为4501008，A的收益率比的收益率比B大，但同时大，但同时A的风险也比的风险也比B大。大。这也符合高风险高收益的规律。这也符合高风险高收益的规律。 试求一种投资方案，使得一年的总投资风险不高于试求一种投资方案，使得一年的总投资风险不高于700，

37、且投资收益，且投资收益不低于不低于10000元。元。28 显然，此问题属于目标规划问题。它有显然，此问题属于目标规划问题。它有两个目标变量两个目标变量：一：一是限制风险，一是确保收益。在求解之前，是限制风险，一是确保收益。在求解之前，应首先考虑两个目应首先考虑两个目标的优先权标的优先权。 假设第一个目标（即限制风险）的优先权比第二个目标假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。标，然后在此基础上再尽量满足第二个目标。 建立模型：建立模型： 设

38、设x x1 1、x x2 2分别表示投资商所购买的分别表示投资商所购买的A A股票和股票和B B股票的数量。股票的数量。 首先考虑资金总额的约束：总投资额不能高于首先考虑资金总额的约束：总投资额不能高于9000090000元。元。即即 20 x20 x1 150 x50 x2 29000090000。29一、约束条件一、约束条件 再来考虑风险约束：总风险不能超过再来考虑风险约束：总风险不能超过700700。投资的总风。投资的总风险为险为0.5x0.5x1 10.2x0.2x2 2。引入两个变量引入两个变量d d1 1+ +和和d d1 1- -, ,建立等式如下：建立等式如下： 0.5x0.5

39、x1 1 +0.2x +0.2x2 2=700+d=700+d1 1+ +-d-d1 1- - 其中，其中，d d1 1+ +表示总风险高于表示总风险高于700700的部分，的部分，d d1 1- -表示总风险少表示总风险少于于700700的部分，的部分，d d1 1+ +,d,d1 1- - 00。 目标规划中把目标规划中把d d1 1+ +、d d1 1- -这样的变量称为这样的变量称为偏差变量偏差变量。 偏差变量的作用是偏差变量的作用是允许约束条件不被精确满足允许约束条件不被精确满足。30 把等式转换，可得到把等式转换，可得到 0.5x0.5x1 1 +0.2x +0.2x2 2-d-d

40、1 1+ +d+d1 1- -=700=700 再来考虑年收入再来考虑年收入: : 年收入年收入=3x=3x1 1+4x+4x2 2 引入变量引入变量d d2 2+ +和和d d2 2- -，分别表示年收入超过与低于，分别表示年收入超过与低于1000010000的数量。的数量。 于是，第于是，第2 2个目标可以表示为个目标可以表示为 3x3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=10000=1000031二、有优先权的目标函数二、有优先权的目标函数 本问题中第一个目标的优先权比第二个目标本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过大。即最重

41、要的目标是满足风险不超过700700。分配给第一个目标较高的优先权分配给第一个目标较高的优先权P P1 1分配给第二个目标较低的优先权分配给第二个目标较低的优先权P P2 232针对每一个优先权，应当建立一个单一目标的线性规针对每一个优先权，应当建立一个单一目标的线性规划模型：划模型：1.1. 首先建立具有最高优先权的目标的线性规划模型，首先建立具有最高优先权的目标的线性规划模型，求解；求解；2.2. 然后再按照优先权逐渐降低的顺序分别建立单一然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模

42、型求解所得的目标上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，最优值作为一个新的约束条件加入到当前模型中，并求解。并求解。33三、建模三、建模1 1针对优先权最高的目标建立线性规划针对优先权最高的目标建立线性规划建立线性规划模型如下：建立线性规划模型如下： Min dMin d1 1+ +s.t.s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=

43、10000=10000 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -00342 2针对优先权次高的目标建立线性规划针对优先权次高的目标建立线性规划优先权次高（优先权次高（P P2 2）的目标是总收益超过）的目标是总收益超过1000010000。建立线性规划如下：建立线性规划如下： Min dMin d2 2- - s.t. s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2

44、2- -=10000=10000 d d1 1+ +0 0 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -0035目标规划的这种求解方法可以表述如下：目标规划的这种求解方法可以表述如下： 1 1确定解的可行区域。确定解的可行区域。 2 2对优先权对优先权最高最高的目标求解，如果找不到能满足该目标的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。的解，则寻找最接近该目标的解。 3 3对优先权对优先权次之次之的目标进行求解。的目标进行求解。注意：必须保证优先注意：必须保证优先权高的目标不变。权高的目标不变。 4. 4. 重复

45、第重复第3 3步，直至所有优先权的目标求解完。步，直至所有优先权的目标求解完。 36四、目标规划模型的标准化四、目标规划模型的标准化 例例6 6中对两个不同优先权的目标单独建立线性规划进行中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：求解。为简便，把它们用一个模型来表达，如下： min Pmin P1 1（d d1 1+ +）+P+P2 2（d d2 2- -） s.t.s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=70

46、0 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=10000=10000 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -0037管理运筹学软件运用注意事项管理运筹学软件运用注意事项 决策变量个数：不包括偏差变量（决策变量个数：不包括偏差变量（2 2） 优先级数：目标优先等级（优先级数：目标优先等级（2 2） 目标约束个数：含偏差变量约束条件个数（目标约束个数：含偏差变量约束条件个数（2 2） 绝对约束个数：不含偏差变量约束条件个数（绝对约束个数：不含偏差变量约束条件个数（1 1）38 3 3复杂情况下的目标

47、规划复杂情况下的目标规划例例9-79-7一工艺品厂商手工生产某两种工艺品一工艺品厂商手工生产某两种工艺品A A、B B，已知生产一，已知生产一件产品件产品A A需要耗费人力需要耗费人力2 2工时，生产一件产品工时，生产一件产品B B需要耗费人力需要耗费人力3 3工时。工时。A A、B B产品的单位利润分别为产品的单位利润分别为250250元和元和125125元。为了最大元。为了最大效率地利用人力资源，确定生产的效率地利用人力资源，确定生产的首要任务首要任务是保证人员高负是保证人员高负荷生产，要求每周总耗费人力资源不能低于荷生产，要求每周总耗费人力资源不能低于600600工时，但也不工时，但也不

48、能超过能超过680680工时的极限；工时的极限；次要任务次要任务是要求每周的利润超过是要求每周的利润超过7000070000元；在前两个任务的前提下，为了保证库存需要，元；在前两个任务的前提下，为了保证库存需要，要求要求每周产品每周产品A A和和B B的产量分别不低于的产量分别不低于200200和和120120件，因为件，因为B B产品比产品比A A产品更重要，不妨假设产品更重要，不妨假设B B完成最低产量完成最低产量120120件的重要性是件的重要性是A A完成完成200200件的重要性的件的重要性的2 2倍。倍。 试求如何安排生产？试求如何安排生产？39解：解： 本问题中有本问题中有3个不

49、同优先权的目标，不妨用个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。表示从高至低的优先权。 对应对应P1有两个目标：每周总耗费人力资源不能低于有两个目标：每周总耗费人力资源不能低于600工时工时,也不能超过也不能超过680工时；工时； 对应对应P2有一个目标：每周的利润超过有一个目标：每周的利润超过70000元；元； 对应对应P3有两个目标：每周产品有两个目标：每周产品A和和B的产量分别不低的产量分别不低于于200和和120件。件。40采用简化模式，最终得到目标线性规划如下：采用简化模式，最终得到目标线性规划如下： Min PMin P1 1(d(d1 1+ +)+ P)+

50、P1 1(d(d2 2)+P)+P2 2(d(d3 3- -)+ P)+ P3 3(d(d4 4- -)+ P)+ P3 3( (2 2d d5 5- -) ) s.t. s.t. 2x1+3x2-d d1 1+ +d d1 1- -=680 对应第对应第1个目标个目标 2x1+3x2-d d2 2+ +d d2 2- -=600 对应第对应第2个目标个目标 250 x1+125x2-d3 + +d3-70000 对应第对应第3个目标个目标 x1-d d4 4+ +d d4 4- -=200 对应第对应第4个目标个目标 x2-d d5 5+ +d d5 5- -=120 对应第对应第5个目标个

51、目标 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -,d,d3 3+ +,d,d3 3- -,d,d4 4+ +,d,d4 4- -,d,d5 5+ +,d,d5 5- -00罚数权重罚数权重41 使用运筹学软件求解可得：使用运筹学软件求解可得：x x1 1=250=250；x x2 2=60=60；d d1 1+ +=0=0；d d1 1- -=0=0；d d2 2+ +=80=80；d d2 2- -=0=0；d d3 3+ +=0=0；d d3 3- -=0=0；d d4 4+ +=50=50；d d4 4- -=0=0；d d

52、5 5+ +=0=0；d d5 5- -=60=60，目标函数目标函数120120。 可见，目标可见，目标1 1、目标、目标2 2、目标、目标3 3和目标和目标4 4达达到了，但目标到了，但目标5 5有一些偏差。有一些偏差。 42 4 4加权目标规划加权目标规划加权目标规划加权目标规划是另一种解决多目标决策问题的方法，其是另一种解决多目标决策问题的方法，其基本方法基本方法是是: :1.1.通过量化的方法分配给通过量化的方法分配给每个目标的偏离的严重程度一个罚数每个目标的偏离的严重程度一个罚数权重权重，2.2.然后建立总的目标函数，该目标函数表示的目标是要使每个然后建立总的目标函数，该目标函数表

53、示的目标是要使每个目标函数与各自目标的目标函数与各自目标的加权偏差之和最小加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，那么，整个问题都可以描述为一个线性规划的问题。整个问题都可以描述为一个线性规划的问题。43在例在例7 7中我们对中我们对 每周总耗费的人力资源超过每周总耗费的人力资源超过680680工时或低于工时或低于600600工时工时的每工时罚数权重定为的每工时罚数权重定为7 7； 每周利润低于每周利润低于7000070000元时，每元的罚数权重为元时，每元的罚数权重为5 5； 每周产品每周产品A A产

54、量低于产量低于200200件时每件罚数权重为件时每件罚数权重为2 2， 每周产品每周产品B B产量低于产量低于120120件时每件罚数权重为件时每件罚数权重为4 4。44 则其目标函数化为：则其目标函数化为： min7d1+7d2-+5d3-+2d4-+4d5- 这就变成了一个普通的单一目标的线性规划问题这就变成了一个普通的单一目标的线性规划问题 min7d1+7d2-+5d3-+2d4-+4d5- s.t. 2x1+3x2-d1+d1-=680 2x1+3x2-d2+d2-=680 250 x1+125x2-d3+d3-=70000 x1-d4+d4-=200 x2-d5+d5-=120 x

55、1,x2,d1+,d1-,d2-,d2+, d3+,d3-,d4+,d4-,d5+,d5-0 。练练 习习 教材教材P212P212习题习题1-101-1045462.3 2.3 动态规划动态规划 1 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理 3 3动态规划的应用动态规划的应用47 1 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例10-1 最短路径问题最短路径问题 下图表示从起点下图表示从起点A到终点到终点E之间各点的距离。求之间各点的距离。求A到到E的最短路径。的最短路径。BACBDBCD

56、EC412312312322164724838675611064375148用穷举法的计算量用穷举法的计算量: : 如果从如果从A A到到E E的站点有的站点有k k个，除个，除A A、E E之外每站有之外每站有3 3个位置则个位置则总共有总共有3 3k-1k-12 2条路径；条路径； 计算各路径长度总共要进行计算各路径长度总共要进行 (k+1) 3(k+1) 3k-1k-12 2次加法以及次加法以及3 3k-k-1 12-12-1次比较。随着次比较。随着 k k 的值增加时，需要进行的加法和比较的的值增加时，需要进行的加法和比较的次数将迅速增加；次数将迅速增加； 例如当例如当 k=20k=2

57、0时，加法次数为时，加法次数为 4.25508339662274.255083396622710101515 次，次，比较比较 1.37260754729771.372607547297710101414 次。若用次。若用1 1亿次亿次/ /秒的计算机计算秒的计算机计算需要约需要约508508天。天。49讨论：讨论： 1 1、以上求从、以上求从A A到到E E的最短路径问题，可以转化为四个性质完的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从全相同，但规模较小的子问题，即分别从D Di i 、C Ci i、B Bi i、A A到到E E的最短路径问题。的最短路径问题。

58、第四阶段：两个始点第四阶段：两个始点D D1 1和和D D2 2，终点只有一个；，终点只有一个； 表表10-110-1分析得知：从分析得知：从D D1 1和和D D2 2到到E E的最短路径唯一。的最短路径唯一。 阶段阶段4本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策) E D1 D2 10* 6 10 6 E E50 第三阶段：有三个始点第三阶段：有三个始点C1，C2，C3，终点有，终点有D1，D2，对始点，对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求C1，C2，C3到到D

59、1，D2 的最短的最短路径问题：路径问题： 表表10-2分析得知：如果经过分析得知：如果经过C1，则最短路为则最短路为C1-D2-E； 如果经过如果经过C2，则最短路为则最短路为C2-D2-E； 如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。 阶段阶段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 D151第二阶段：有第二阶段

60、：有4个始点个始点B1,B2,B3,B4，终点有，终点有C1,C2,C3。对始点。对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求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。 阶段阶段2本阶段始点本阶段始点（状态）（状态） 本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优