整数规划应用案例分析

一、投资项目的选择一、投资项目的选择 利用线性规划可以来完成资金预算决策，决定对利用线性规划可以来完成资金预算决策，决定对 不同项目投资额各是多少。但实际中，一些资金预算决不同项目投资额各是多少。但实际中，一些资金预算决策不是决定投资多少，而是是否进行一些固定金额的投策不是决定投资多少，而是是否进行一些固定金额的投资。资。管理层必须经常面对的是：在预投入资金额度一定管理层必须经常面对的是：在预投入资金额度一定的情况下，是否进行一项或几项固定投资。的情况下，是否进行一项或几项固定投资。对每个是或否的决策：对每个是或否的决策：1 1，是，是 引入决策变量引入决策变量x=x=0 0，否，否第四章第四章 整数规划的应用整数规划的应用例例1 1 投资问题投资问题 设某公司在设某公司在m m个时段里有个时段里有n n项投资计划，由于资金限制不能项投资计划，由于资金限制不能全部进行。已知全部进行。已知 1)1)第第i i个时段里该公司可动用的资金个时段里该公司可动用的资金是是b b i i，2)2)第第j j项投资计划所需要的资金是项投资计划所需要的资金是a a ijij ,3)3)能够得到的利润能够得到的利润是是c c ijij。问该公司如何选择投资计划，使问该公司如何选择投资计划，使m m个时段内的总利润最大个时段内的总利润最大。解：解：设设x x ijij表示在第表示在第i i个时段内对个时段内对第第j j个投资计划的决策变量。个投资计划的决策变量。建立该投资问题的数学模型为建立该投资问题的数学模型为：表示第表示第i i个时段内选中第个时段内选中第j j个投资计划，个投资计划，表示第表示第i i时段内未选中第时段内未选中第j j个投资计划。个投资计划。项目项目项目项目投资额投资额投资额投资额(万元万元万元万元)投资收益投资收益投资收益投资收益(万元万元万元万元)1 12102101501502 23003002102103 310010060604 413013080805 5260260180180该公司只有该公司只有该公司只有该公司只有600600600600万元资金可用于投资，由于技术原因，万元资金可用于投资，由于技术原因，万元资金可用于投资，由于技术原因，万元资金可用于投资，由于技术原因，投资受到以下约束：投资受到以下约束：投资受到以下约束：投资受到以下约束：1 1 1 1）在项目）在项目）在项目）在项目1 1 1 1、2 2 2 2和和和和3 3 3 3中必须有一项被选中；中必须有一项被选中；中必须有一项被选中；中必须有一项被选中；2 2 2 2）项目）项目）项目）项目3 3 3 3和和和和4 4 4 4只能选中一项；只能选中一项；只能选中一项；只能选中一项；3 3 3 3）项目）项目）项目）项目5 5 5 5被选中的前提是项目被选中的前提是项目被选中的前提是项目被选中的前提是项目1 1 1 1必须被选中。必须被选中。必须被选中。必须被选中。如何在上述条件下，选择一个最好的投资方案，使收如何在上述条件下，选择一个最好的投资方案，使收如何在上述条件下，选择一个最好的投资方案，使收如何在上述条件下，选择一个最好的投资方案，使收益最大。益最大。益最大。益最大。投资项目的选择投资项目的选择例例2.2.华美公司有华美公司有华美公司有华美公司有5 5 5 5个项目被列入投资计划，各项目个项目被列入投资计划，各项目个项目被列入投资计划，各项目个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：的投资额和期望的投资收益见下表：的投资额和期望的投资收益见下表：的投资额和期望的投资收益见下表：1 1 1 1 选中项目选中项目选中项目选中项目i i i i 0 0 0 0 未选中项目未选中项目未选中项目未选中项目I I I I (i=1,5)(i=1,5)(i=1,5)(i=1,5)解：令解：令解：令解：令 xi=Max Z=150 xMax Z=150 x1 1+210 x210 x2 2+60 x60 x3 3+80 x+80 x4 4+180 x180 x5 5 s.t.s.t.210 x210 x1 1+300 x300 x2 2+100 x+100 x3 3+130 x+130 x4 4+260 x260 x5 5 600 600 x x1 1+x x2 2+x x3 3 =1=1 x x3 3+x+x4 4 1 1 x x5 5 x x1 1 x xi i=1=1或或或或0(i=1,5)0(i=1,5)1,2,31,2,3必须有一项选中必须有一项选中3,43,4只能选中一项只能选中一项5 5被选中前提是被选中前提是1 1选中选中解解解解得（得（得（得（1 1 1 1，0 0 0 0，0 0 0 0，1 1 1 1，1 1 1 1）Max Z=410Max Z=410Max Z=410Max Z=410即即即即投资项目投资项目投资项目投资项目1 1 1 1、4 4 4 4、5 5 5 5，可以获得，可以获得，可以获得，可以获得410410410410万元。万元。万元。万元。二、分布系统设计二、分布系统设计-选址问题选址问题 在如今的全球经济中，许多公司正在全世界各个地在如今的全球经济中，许多公司正在全世界各个地方建立新工厂，为的是获得低劳动力成本等好处。方建立新工厂，为的是获得低劳动力成本等好处。在为新工厂选址之前，需要分析和比较地点。每个在为新工厂选址之前，需要分析和比较地点。每个可供选择的地点都涉及一个是或否的决策。可供选择的地点都涉及一个是或否的决策。对每个是或否的决策：对每个是或否的决策：1 1，是，是 引入决策变量引入决策变量 x=x=0 0，否，否 在许多案例中，目标是地点的选择以使新建设施的总在许多案例中，目标是地点的选择以使新建设施的总的成本最小化，且这新设施能满足生产的需要。的成本最小化，且这新设施能满足生产的需要。分布系统设计分布系统设计-选址问题选址问题例例3 3某企业在某企业在 A A1 1 地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为 30 30 千箱，千箱，为了扩大生产，打算在为了扩大生产，打算在 A A2 2，A A3 3，A A4 4，A A5 5地中再选择几个地方建厂。地中再选择几个地方建厂。已知在已知在 A A2 2，A A3 3，A A4 4，A A5 5地建厂的固定成本分别为地建厂的固定成本分别为175175千元、千元、300300千元、千元、375375千元、千元、500500千元，另外，千元，另外，A A1 1产量及产量及A A2 2，A A3 3，A A4 4，A A5 5建成建成厂的产量，各销地的销量以及产地到销地的单位运价厂的产量，各销地的销量以及产地到销地的单位运价(每千箱运每千箱运费费)如下表所示。如下表所示。a)a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小固定成本和总的运输费用之和最小?解解：a)a)设设 x xijij为从为从A Ai i 运往运往B Bj j 的运输量的运输量(单位千箱单位千箱)，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 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 4项为固定投资额，后面的项为运输费用。）项为固定投资额，后面的项为运输费用。）s.ts.t.x x1111+x x1212+x x1313 30 (A 30 (A1 1 厂的产量限制厂的产量限制)x x2121+x x2222+x x2323 10 (A 10 (A2 2 厂的产量限制厂的产量限制)x x3131+x x3232+x x33 33 20 (A 20 (A3 3 厂的产量限制厂的产量限制)x x4141+x x4242+x x43 43 30 30 (A (A4 4 厂的产量限制厂的产量限制)x x5151+x x5252+x x53 53 40 40 (A (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 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。模型检查！是否有问题？模型检查！是否有问题？解：解：a)a)设设 x xijij为从为从A Ai i 运往运往B Bj j 的运输量的运输量(单位千箱单位千箱)，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 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 4项为固定投资额，后面的项为运输费用。）项为固定投资额，后面的项为运输费用。）s.t.s.t.x x1111+x x1212+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 (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 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。b)如果由于政策要求必须在如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂地建一个厂，应在哪几个地方建厂?练习练习 例例4.4.某钻井队要人以下某钻井队要人以下1010个可供选择的井位中确定个可供选择的井位中确定5 5个个钻井探油钻井探油,使总的钻探费用为最小使总的钻探费用为最小,若若1010个井位的代号个井位的代号为为 ,相应的钻探险费用为相应的钻探险费用为 ,并且并且井位选择上要满足下列限制条件井位选择上要满足下列限制条件:w或选择或选择 和和 ,或选择或选择w选择了选择了 或或 就不能选就不能选 ,或反过来也一或反过来也一w样样w在在 中最多只能选两个中最多只能选两个.w试建成立这个问题的整数规划模型试建成立这个问题的整数规划模型解:设决策变量目标函数为约束条件:1)从10个可供选择的井位中确定5个探油,则2)或选择 和 ,或选择 可表示为3)选择了 或 就不能选 ,反过来也一样,可表示为4)在 中最多只能选两个可表示为 综上所述,该问题的整数规划模型如下:例例5.5.某部队为了完成某项特殊任务某部队为了完成某项特殊任务,需要昼夜需要昼夜2424小时小时不间断值班不间断值班,但每天不同的阶段所需要的人数不同但每天不同的阶段所需要的人数不同,具具体情况如下体情况如下.假设值班人员分别在各时间段开始时上假设值班人员分别在各时间段开始时上班班,并连续工作并连续工作8 8小时小时.该部队要完成这项任务至少需该部队要完成这项任务至少需要配备多少名值班人员要配备多少名值班人员?班次班次 时间段时间段 需要人数需要人数 1 6:00-10:00 601 6:00-10:00 60 2 10:00-14:00 70 2 10:00-14:00 70 3 14:00-18:00 60 3 14:00-18:00 60 4 18:00-22:00 50 4 18:00-22:00 50 5 22:00-2:00 20 5 22:00-2:00 20 6 2:00-6:00 30 6 2:00-6:00 30三、值班安排三、值班安排解:设分别表示第i个班次开始上班的人数,每个人连续值班8小时.根据题意所求问题归结为如下整数规划的数学模型:wMODEL:wSets:wNum/1.6/:b,x;wEndsetswData:wb=60,70,60,50,20,30;wEnddatawOBJmin=sum(num(i):x(i);wx(1)+x(6)=60;wx(1)+x(2)=70;wx(2)+x(3)=60;wx(3)+x(4)=50;wx(4)+x(5)=20;wx(5)+x(6)=30;for(num(i):GIN(x(i);x(i)=0;);END练习(兼职值班)例例6.6.东方大学计算机实验室聘用东方大学计算机实验室聘用4 4名大学生名大学生(代号代号1,2,3,4)1,2,3,4)和和2 2名研究生名研究生(代号代号5,6)5,6)值班答疑值班答疑.已知每人已知每人从周一至周五每天最多可安排的值班时间及每人每小从周一至周五每天最多可安排的值班时间及每人每小时的值班报酬如下时的值班报酬如下:班次班次 报酬报酬 每天最多可安排的值班时间每天最多可安排的值班时间 (元元/时时)周一周一 周二周二 周三周三 周四周四 周五周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3 w该实验室开放时间为上午该实验室开放时间为上午8:008:00至晚上至晚上10:00,10:00,开放时间开放时间内须有且仅须一名学生值班内须有且仅须一名学生值班.规定大学生每周值班不规定大学生每周值班不少于少于8 8小时小时,研究生每周不少于研究生每周不少于7 7小时小时,每名学生每周值每名学生每周值班不超过班不超过3 3次次,每次值班不少于每次值班不少于2 2小时小时,每天安排的值班每天安排的值班学生不超过学生不超过3 3人人,且其中必须有一名研究生且其中必须有一名研究生.试为该实试为该实验室安排一张人员值班表验室安排一张人员值班表,使总支付的报酬最少使总支付的报酬最少,班次班次 报酬报酬 每天最多可安排的值班时间每天最多可安排的值班时间 (元元/时时)周一周一 周二周二 周三周三 周四周四 周五周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3 解解:设设 为学生为学生 i在周在周j的值班时间的值班时间,分析约束条件分析约束条件:四、固定成本问题四、固定成本问题 例例7 7高压容器公司制造小、中、大三种尺寸的金属高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为定费用，每种容器售出一只所得的利润分别为4 4万元、万元、5 5万元、万元、6 6万元，可使用的金属板有万元，可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/月，机器有月，机器有100100台台/月，此外不管每种容器制造月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是的数量是多少，都要支付一笔固定的费用：小号是l00l00万元，中号为万元，中号为 150 150 万元，大号为万元，大号为200200万元。现在万元。现在要制定一个生产计划，使获得的利润为最大。要制定一个生产计划，使获得的利润为最大。解：这是一个整数规划的问题。解：这是一个整数规划的问题。设设x x1 1，x x2 2，x x3 3 分别为小号容器、中号容器和大号容器的生分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设为了说明固定费用的这种性质，设 y yi i=1(=1(当生产第当生产第 i i种容器种容器,即即 x xi i 0 0 时时)或或0 0（当不生产第当不生产第 i i种容器即种容器即 x xi i=0 =0 时）。时）。引入约束引入约束 x xi i M M y yi i ，i=1i=1，2 2，3 3，M M充分大，以保证充分大，以保证当当 y yi i =0=0 时，时，x xi i=0 =0。可建立如下的数学模型：可建立如下的数学模型：Max z=4Max z=4x x1 1+5+5x x2 2+6+6x x3 3-100y-100y1 1-150y-150y2 2-200y-200y3 3 s.ts.t.2.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 x xi i M M y yi i ，i=1i=1，2 2，3 3，M M充分大充分大 x xj j 0 0 y yj j 为为0-10-1变量变量，i i=1,2,3=1,2,3五、五、分配问题分配问题分配问题分配问题 (Assignment problem)(Assignment problem)(Assignment problem)(Assignment problem)有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把指派每个人去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使个人，使得完成得完成 n n 项任务的总的效率最高，这就是项任务的总的效率最高，这就是指派问题。指派问题。例例8.48.4个人完成个人完成4 4项工作任务，由于个人的技术专长不同，他们完成项工作任务，由于个人的技术专长不同，他们完成4 4项工作任务所获得的收益如下表所示，且规定每人只能做一项工项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使收益最大的分派方案？作，一项工作任务只需一人操作，试求使收益最大的分派方案？解：引入解：引入0101变量变量 x xijij，并令并令 x xijij =1(=1(当指派第当指派第 i i名队员游第名队员游第j j种姿势种姿势)或或0 0（当不指派第（当不指派第 i i名队员游第名队员游第j j种姿势种姿势)这可以表示为一个这可以表示为一个0-10-1整数规划问题：整数规划问题：Min Min z=56z=56x x1111+74+74x x1212+61+61x x1313+63+63x x1414+63+63x x2121+69+69x x2222+65+65x x2323+71+71x x2424+57+57x x3131+77+77x x3232+63+63x x3333+67+67x x3434+55+55x x41 41+76+76x x4242+62+62x x4343+62+62x x4444s.t.s.t.x x1111+x x1212+x x1313+x x1414=1 (A=1 (A只能游一种姿势只能游一种姿势)x x2121+x x2222+x x2323+x x2424=1 (B=1 (B只能游一种姿势只能游一种姿势)x x3131+x x3232+x x3333+x x3434=1 (C=1 (C只能游一种姿势只能游一种姿势)x x4141+x x4242+x x4343+x x4444=1 (D=1 (D只能游一种姿势只能游一种姿势)x x1111+x x2121+x x3131+x x4141=1 (=1 (自由泳只能一人游自由泳只能一人游)x x1212+x x2222+x x3232+x x4242=1 (=1 (蛙泳只能一人游蛙泳只能一人游)x x1313+x x2323+x x3333+x x4343=1 (=1 (蝶泳只能一人游蝶泳只能一人游)x x1414+x x2424+x x3434+x x4444=1 (=1 (仰泳只能一人泳仰泳只能一人泳)x xijij 为为0-10-1变量变量，i,j i,j=1,2,3,4=1,2,3,4 Model:sets:num_i/1.4/;num_j/1.4/;link(num_i,num_j):a,x;endsetsdata:a=56,74,61,63,63,69,65,71,57,77,63,67,55,76,62,62;enddataOBJmin=sum(link(i,j):a(i,j)*x(i,j);for(num_i(i):sum(num_j(j):x(i.j)=1;);for(num_j(j):sum(num_i(i):x(i,j)=1;);for(link(i,j):BIN(x(i,j);x(i,j)=0;);END备用备用 例例9.9.某公司在今后五年内考虑给以下的项目投资。已知：某公司在今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第四年每年年初可以投资，并于次年末回收本从第一年到第四年每年年初可以投资，并于次年末回收本利利115%115%，但第一年如果投资则最低金额为但第一年如果投资则最低金额为4 4万元，第二、三、万元，第二、三、四年不限；四年不限；项目项目B B：第三年初可以投资，到第五年末能回收本利第三年初可以投资，到第五年末能回收本利128128，但规定，但规定最低投资金额为最低投资金额为3 3万元，最高金额为万元，最高金额为5 5万元；万元；项目项目 C C：第二年初可以投资，到第五年末能回收本利第二年初可以投资，到第五年末能回收本利140%140%，但规，但规定其投资额或为定其投资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。项目项目 D D：五年内每年初可购买公债，于当年末归还，并加利息五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项投资金额不限。，此项投资金额不限。该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目的每万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大年投资额，使到第五年末拥有的资金本利总额为最大?解：解：1)设xiA、xiB、xiC、xiD(i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；设yiA，yiB，是01变量，并规定取 1 时分别表示第 i 年给A、B投资，否则取 0（i=1,2,3,4,5）。设y2C 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值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+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；当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，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）例例例例10101010（电力规划问题（电力规划问题（电力规划问题（电力规划问题）某地区在制定十年电力某地区在制定十年电力某地区在制定十年电力某地区在制定十年电力规划时，遇到这样一个问题，根据电力需求规划时，遇到这样一个问题，根据电力需求规划时，遇到这样一个问题，根据电力需求规划时，遇到这样一个问题，根据电力需求预测，该地区十年以后发电装机容量需要增预测，该地区十年以后发电装机容量需要增预测，该地区十年以后发电装机容量需要增预测，该地区十年以后发电装机容量需要增加加加加180180180180万千瓦，到时年发电量需增加万千瓦，到时年发电量需增加万千瓦，到时年发电量需增加万千瓦，到时年发电量需增加100100100100亿度，亿度，亿度，亿度，根据调查和讨论，电力规划的备选技术方案根据调查和讨论，电力规划的备选技术方案根据调查和讨论，电力规划的备选技术方案根据调查和讨论，电力规划的备选技术方案有三个有三个有三个有三个：扩建原有火电站扩建原有火电站扩建原有火电站扩建原有火电站，但最多只能安装但最多只能安装但最多只能安装但最多只能安装5 5台台台台1010万千瓦机万千瓦机万千瓦机万千瓦机组；组；组；组；新建水电站，但最多只能安装新建水电站，但最多只能安装新建水电站，但最多只能安装新建水电站，但最多只能安装4 4台台台台2525万千瓦机组；万千瓦机组；万千瓦机组；万千瓦机组；新建火电站，但最多只能安装新建火电站，但最多只能安装新建火电站，但最多只能安装新建火电站，但最多只能安装4 4台台台台3030万千瓦机组万千瓦机组万千瓦机组万千瓦机组。通过调研和计算，获得有关参数如下：通过调研和计算，获得有关参数如下：通过调研和计算，获得有关参数如下：通过调研和计算，获得有关参数如下：备选备选备选备选方案方案方案方案工程特点工程特点工程特点工程特点前期工前期工前期工前期工程投资程投资程投资程投资(百万元百万元百万元百万元)单机设单机设单机设单机设备投资备投资备投资备投资(百万百万百万百万元元元元)单机容单机容单机容单机容量量量量(万万万万千瓦千瓦千瓦千瓦)允许允许允许允许装机装机装机装机台数台数台数台数1 1扩建火电站扩建火电站扩建火电站扩建火电站212110105 52 2新建水电站新建水电站新建水电站新建水电站504504707025254 43 3新建火电站新建火电站新建火电站新建火电站240240656530304 4备选备选备选备选方案方案方案方案工程特点工程特点工程特点工程特点资本回资本回资本回资本回收因子收因子收因子收因子年运行成本年运行成本年运行成本年运行成本(百万元百万元百万元百万元/亿度亿度亿度亿度)负荷因子负荷因子负荷因子负荷因子1 1扩建火电站扩建火电站扩建火电站扩建火电站0.1030.1034.114.110.660.662 2新建水电站新建水电站新建水电站新建水电站0.05780.05782.282.280.40.43 3新建火电站新建火电站新建火电站新建火电站0.1030.1033.653.650.70.7注：负荷因子注：负荷因子=全年满功率运行天数全年满功率运行天数/全全年总天数。方案年总天数。方案1：241天；方案天；方案2：146天；方案天；方案3：255天；天；建立模型：建立模型：设置决策变量设置决策变量 设备选方案设备选方案1，2，3的装机台的装机台数分别为数分别为x1、x2、x3，它们的年发电它们的年发电量分别为量分别为x6、x7、x8亿度，备选方亿度，备选方案案1无前期土建工程要求，备选方无前期土建工程要求，备选方案案2和和3都需要前期土建工程，这都需要前期土建工程，这两个前期土建工程是否施工用变两个前期土建工程是否施工用变量量x4、x5代表代表。则则x1取值取值0-5之间的整数，之间的整数，x2、x3取取值值0-4之间的整数，之间的整数，x4、x5只能取只能取0或或1，x6、x7、x8大于零。大于零。约束方程约束方程o满足装机容量需求约束：满足装机容量需求约束：10 x1+25x2+30 x3 180o满足规划年发电量需求约束：满足规划年发电量需求约束：x6+x7+x8 100o各电站容量与发电量平衡方程：各电站容量与发电量平衡方程：机组年发电量等于单机容量乘全机组年发电量等于单机容量乘全年小时数，再乘以负荷因子，换年小时数，再乘以负荷因子，换算亿度量纲，即：算亿度量纲，即：方案方案1：x6=(0.66*8760*10/10000)*x1方案方案2：x7=(0.4*8760*25/10000)*x2方案方案3：x8=(0.7*8760*30/10000)*x3得三个约束方程：得三个约束方程：5.782 x1 -x6 =0 8.76 x2 -x7 =018.39 x3 -x8 =0o每个方案最多的装机台数约束：每个方案最多的装机台数约束：方案方案1：不需前期土建工程；：不需前期土建工程；x1 5方案方案2：前期土建工程是装机的先决：前期土建工程是装机的先决条件，且小于最大允许数；条件，且小于最大允许数；x2 4 x4方案方案3：前期土建工程是装机的先决：前期土建工程是装机的先决条件，且小于最大允许数；条件，且小于最大允许数；x3 4 x5o变量取值限制变量取值限制x1、x2、x3 0 且整数且整数x6、x7、x8 0 x4或或x5=1 前期土建工程要求前期土建工程要求 x4或或x5=0 无前期土建工程要求无前期土建工程要求设计目标函数设计目标函数目标函数：年成本费用最低。目标函数：年成本费用最低。成本包括两大部分：成本包括两大部分：可变成本可变成本与发电量有关的成与发电量有关的成本，如：原材料，燃料，动力和本，如：原材料，燃料，动力和活劳动消耗等。即参数表中年运活劳动消耗等。即参数表中年运行成本。行成本。不变成本不变成本指与装机容量及前指与装机容量及前期土建投资有关的成本。期土建投资有关的成本。方案方案1：单机投资：单机投资*回收因子回收因子=21*0.103=2.163(百万元）百万元）方案方案2：单机投资：单机投资*回收因子回收因子=70*0.0578=4.046(百万元）百万元）方案方案3：单机投资：单机投资*回收因子回收因子=65*0.103=6.695(百万元）百万元）方案方案2和和3的前期土建投资的年资本的前期土建投资的年资本回收成本分别为回收成本分别为504*0.0578=29.131(百万元）百万元）240*0.103=24.72(百万元）百万元）对方案对方案1，2，3每发一亿度电的运每发一亿度电的运行成本分别为行成本分别为4.11,2.28,3.65百万元。百万元。则数学模型如下：则数学模型如下：Min Z=2.163x1+4.046x2+6.695x3 +29.131x4+24.72x5+4.11x6 +2.28x7+3.65x8s.t.10 x1+25x2+30 x3 180 x6+x7+x8 1005.782 x1 -x6 =0 8.76 x2 -x7 =018.39 x3 -x8 =0 x1 5 x2 4 x4 x3 4 x5x1、x2、x3 0 且整数且整数x6、x7、x8 0 x4、x5=1或或0求解得到：求解得到：x1 =2 x2 =4 x3=3 x4=1 x5=1 x6=11.56 x7=35.04 x8 =55.17 Z=423.24百万元。百万元。扩建原有火电站，安装扩建原有火电站，安装2台台10万千万千 瓦发电机组；瓦发电机组；新建水电站，安装新建水电站，安装4台台25万千瓦发万千瓦发电机组；电机组；新建火电站，新建火电站，安装安装3台台30万千瓦发万千瓦发电机组电机组。总装机容量达：总装机容量达：2*10+4*25+3*30=210万千瓦万千瓦