《运筹学 整数规划建模.pptx》由会员分享，可在线阅读，更多相关《运筹学 整数规划建模.pptx（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章内容要点本章内容要点整数规划相关概念整数规划相关概念整数规划问题的一般特点整数规划问题的一般特点整数规划建模举例整数规划建模举例第1页/共41页引例引例经济管理当中经常存在人员分派问题，企业中有经济管理当中经常存在人员分派问题，企业中有4个个人可以胜任人可以胜任4项不同工作的任意一项，但是完成工作项不同工作的任意一项，但是完成工作的效率有所不同。如表所示：的效率有所不同。如表所示：为了使得企业获得最好的经济效益，应该如何分派这为了使得企业获得最好的经济效益，应该如何分派这四个人完成四项不同工作？四个人完成四项不同工作？第2页/共41页 6.1 整数规划问题的提出整数规划问题的提出6.1.1
2、 问题特征问题特征 变量取值范围是离散的，经典变量取值范围是离散的，经典连续数学中的理论和方法一般无连续数学中的理论和方法一般无法直接用来求解整数规划问题。法直接用来求解整数规划问题。第3页/共41页不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为整数规划问题的松弛问题。若松弛问题是一个线性规划问题，则称该整数规划问题为整数线性规划问题。整数线性规划问题的分类：纯整数线性规划问题：要求全部变量均取整数混合整数线性规划问题：要求部分变量取值为整数0-1整数线性规划问题：决策变量取值为0或1第4页/共41页6.1.2 整数规划建模中常用的处理方整数规划建模中常用的处理方法法（1）资本预
3、算问题）资本预算问题 设有设有n个投资方案，个投资方案，cj为第为第j个投资方案的收益。个投资方案的收益。投资过程共分为投资过程共分为m个阶段，个阶段，bi为第为第i个阶段的个阶段的投资总量，投资总量，aij为第为第i阶段第阶段第j项投资方案所需要项投资方案所需要的资金。目标是在各阶段资金限制下使整个的资金。目标是在各阶段资金限制下使整个投资的总收益最大。投资的总收益最大。第5页/共41页设决策变量设决策变量xj为对第为对第j个方案的取（个方案的取（xj=1）或舍（或舍（xj=0），可得到下列整数规划问题，），可得到下列整数规划问题，是是01规划。规划。yjyjyjxxij 为整数第6页/共4
4、1页8例某公司考虑今后五年内给以下项目投资。例某公司考虑今后五年内给以下项目投资。项目项目A：每年年初可以投资，于次年末回收本利：每年年初可以投资，于次年末回收本利115%，投资金额必须为，投资金额必须为1万元的整数倍；万元的整数倍；项目项目 B：每年初可购买公债，于当年末归还，并加利：每年初可购买公债，于当年末归还，并加利息息6%，投资金额必须为，投资金额必须为1万元的整数倍；万元的整数倍；项目项目 C：第：第2年初可以投资，到第年初可以投资，到第5年未能回收本利年未能回收本利140%，投资金额必须为，投资金额必须为1万元的整数倍；万元的整数倍；项目项目D：第：第3年初可以投资，到第年初可以
5、投资，到第5年未能回收本利年未能回收本利128%，如果投资金额必须大于，如果投资金额必须大于2万元；万元；该部门现有资金该部门现有资金10万元，问它应如何确定给这万元，问它应如何确定给这些项目的每年投资额，使到第些项目的每年投资额，使到第 5 年末拥有的资年末拥有的资金本利总额为最大金本利总额为最大?第8页/共41页9解：1)设xiA、xiB、xiC、xiD(i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；变量：第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x1B x2B x3B x4B x5B C x2C D x3D第9页/共41
6、页6.1.2 建模中常用的处理方法（续）建模中常用的处理方法（续）（2）指示变量：）指示变量：指示不同情况的出现指示不同情况的出现P139 例例.有有m个仓库，要决定动用哪些仓库，满足个仓库，要决定动用哪些仓库，满足n个顾客对货物的需要，并决定从各仓库个顾客对货物的需要，并决定从各仓库分别向不同顾客运送多少货物？分别向不同顾客运送多少货物？第10页/共41页第11页/共41页6.1.2 建模中常用的处理方法（续）建模中常用的处理方法（续）费用费用:fi:动用动用i仓库的固定运营费（租金等）仓库的固定运营费（租金等）cij:从仓库从仓库i到到j顾客运送单位货物的运顾客运送单位货物的运费费约束条件
7、：约束条件：i)每个顾客的需要量每个顾客的需要量dj必须得到满足；必须得到满足；ii)只能从动用的仓库运出货物。只能从动用的仓库运出货物。第12页/共41页6.1.2 建模中常用的处理方法（续）建模中常用的处理方法（续）取足够大的数，迫使当yi=0时，xij必须为0第13页/共41页6.1.2 建模中常用的处理方法建模中常用的处理方法（续）（续）（3）线性规划模型的附加条件）线性规划模型的附加条件在许多实际问题中，线性规划模型中在许多实际问题中，线性规划模型中的约束条件允许一定范围的放宽或对的约束条件允许一定范围的放宽或对个别因素有进一步限制时，常可通过个别因素有进一步限制时，常可通过引入引入
8、01变量来处理。下面介绍几种变量来处理。下面介绍几种情况，作为一种建模思路的启示。情况，作为一种建模思路的启示。第14页/共41页不同时成立的约束条件。设某个模不同时成立的约束条件。设某个模型问题中的约束条件不必同时成立，型问题中的约束条件不必同时成立，有有m个线性不等式约束个线性不等式约束对每个约束引入一个指示变量对每个约束引入一个指示变量yi，并得，并得到每个约束左端的一个上界到每个约束左端的一个上界Mi(i=1,2,n)，建立下列不等式：，建立下列不等式：第15页/共41页显然，当显然，当yi=1时，两式等价；当时，两式等价；当yi=0时，第二个式子是恒成立，相时，第二个式子是恒成立，相
9、当于除去了这个限制。当于除去了这个限制。在实际问题中，如果至少有在实际问题中，如果至少有k个约个约束成立时，只需附加下列约束：束成立时，只需附加下列约束：第16页/共41页最优解中非零分量个数的限制。在许最优解中非零分量个数的限制。在许多实际问题中，对最优解中的非零分多实际问题中，对最优解中的非零分量个数有所限制。类似上述分析可对量个数有所限制。类似上述分析可对每个决策变量每个决策变量xi找到其上界找到其上界Mi，并引，并引入指示变量入指示变量yi。附加下式。附加下式 （6-4）（6-5）式（式（6-5）说明，非零分量至多有）说明，非零分量至多有k个。个。第17页/共41页6.2 6.2 整数
10、规划问题建模整数规划问题建模整数规划问题的特征：整数规划问题的特征：变量取值范围是离散的，变量取值范围是离散的，在经典连续数学中的理论和方法在经典连续数学中的理论和方法一般无法直接用来求解整数规划一般无法直接用来求解整数规划问题，求解时需要技巧。问题，求解时需要技巧。第22页/共41页23整数规划建模整数规划建模P305P305例P305 S2.1 京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj(j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区 A1，A2，A3,3 个点至多选择 2 个；在西区 A4，A5 ，2 个点
11、中至少选 1 个；在南区 A6，A7 ，2 个点中至少选 1 个；在北区 A8，A9，A10，3 个点中至少选 2 个。第23页/共41页24整数规划建模整数规划建模P305P305例P305 S2.1 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见下表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?第24页/共41页25解：设：0-1变量 xi=1(Ai 点被选用）或 0(Ai 点没被选用）。这样我们可建立如下的数学模型：Max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6 +25x7+48x8+58
12、x9+61x10s.t.100 x1+120 x2+150 x3+80 x4+70 x5+90 x6 +80 x7+140 x8+160 x9+180 x10 720 x1+x2+x3 2 x4+x5 1 x6+x7 1 x8+x9+x10 2 xj 为0-1变量，j=1,2,3,10第25页/共41页软件求解演示第26页/共41页27例例P305 S2.2高压容器公司制造小、中、大高压容器公司制造小、中、大3种尺寸的金属容器，所用资源为金属板、劳动力和种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。每种容器售出所得机器设备，制造一个容器所需的
13、各种资源的数量如下表所示。每种容器售出所得的利润分别为的利润分别为 4万元、万元、5万元、万元、6万元。可使用的金属板有万元。可使用的金属板有500吨，劳动力有吨，劳动力有300人月，机器有人月，机器有100台月。此外，每种容器制造都要支付一笔固定的费用：小台月。此外，每种容器制造都要支付一笔固定的费用：小号是号是l00万元，中号为万元，中号为 150 万元，大号为万元，大号为200万元。现在要制定一个生产计划，万元。现在要制定一个生产计划，使获得的利使获得的利 润为最大。润为最大。整数规划建模整数规划建模第27页/共41页28解：设解：设x1，x2，x3 分别为小号容器、中号容器和大号分别为
14、小号容器、中号容器和大号容器的生产数量。容器的生产数量。各种容器的固定费用只有在生产该种容器时才投各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设入，为了说明固定费用的这种性质，设 yi=1(当生产第当生产第 i种容器种容器,即即 xi 0 时时)或或0（当不生（当不生产第产第 i种容器即种容器即 xi=0 时）时）引入约束引入约束 xi M yi ，i=1，2，3，M充分大，以充分大，以保证当保证当 yi =0 时，时，xi=0。数学模型：。数学模型：Max z=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3 500 2x
15、1+3x2+4x3 300 x1+2x2+3x3 100 xi M yi ，i=1，2，3，M充分大充分大 xj 0 且为整数且为整数 yj 为为0-1变量，变量，j=1,2,3第28页/共41页软件求解演示第29页/共41页30整数规划建模整数规划建模指派问题指派问题 有有 n 项不同的任务，恰好项不同的任务，恰好 n 个人可个人可分别承担这些任务，但由于每人特长不同，完成各分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把人去完成一项任务，怎样把 n 项任务指派给项任务指派给 n 个个
16、人，使得完成人，使得完成 n 项任务的总的效率最高，这就是项任务的总的效率最高，这就是指派问题。指派问题。例有例有4个工人，要分别指派他们完成个工人，要分别指派他们完成4项不同的项不同的工作，每人做各项工作所消耗的时间如下表所示，工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。问应如何指派工作，才能使总的消耗时间为最少。第30页/共41页31解：解：令令 xij=1(第第 i人完成第人完成第j项工作项工作)或或0（第（第 i人不进人不进行第行第j项工作项工作)于是得到一个于是得到一个0-1整数规划问题：整数规划问题：Min z=15x11+18x12+2
17、1x13+24x14+19x21+23x22 +22x23+18x24+26x31+17x32+16x33+19x34 +19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1 (甲只能干一项工作甲只能干一项工作)x21+x22+x23+x24=1 (乙只能干一项工作乙只能干一项工作)x31+x32+x33+x34=1 (丙只能干一项工作丙只能干一项工作)x41+x42+x43+x44=1 (丁只能干一项工作丁只能干一项工作)x11+x21+x31+x41=1 (A工作只能一人干工作只能一人干)x12+x22+x32+x42=1 (B工作只能一人干工作只能一人
18、干)x13+x23+x33+x43=1 (C工作只能一人干工作只能一人干)x14+x24+x34+x44=1 (D工作只能一人干工作只能一人干)xij 为为0-1变量变量，i,j=1,2,3,4第31页/共41页32例某企业在例某企业在 A1 地已有工厂，其产品的生产能地已有工厂，其产品的生产能力为力为30 万箱。为扩大生产，拟在万箱。为扩大生产，拟在 A2，A3，A4，A5地中再选择若干地建厂。已知在地中再选择若干地建厂。已知在 A2，A3，A4，A5地建厂的固定成本分别为地建厂的固定成本分别为17.5、30、37.5、50万元，另外，万元，另外，A1产量及产量及A2，A3，A4，A5建成厂
19、的产量，那时销地的销量以及产地建成厂的产量，那时销地的销量以及产地到销地的单位运价到销地的单位运价(每万箱运费每万箱运费)如右下表所示。如右下表所示。问应该在哪些地方建厂，在满足销量的前提下，问应该在哪些地方建厂，在满足销量的前提下，使得其总的固定成使得其总的固定成 本和总的运输费用本和总的运输费用 之和最小之和最小?整数规划建模整数规划建模第32页/共41页33解：解：设设 xij为从为从Ai 运往运往Bj 的运输量的运输量(单位千箱单位千箱)，yi=1(当当Ai 被选中时被选中时)或或0（当（当Ai 没被选中时没被选中时)Min z=8x11+4x12+3x13+5x21+2x22+3x2
20、3+4x31+3x32 +4x33+9x41+7x42 +5x43+10 x51+4x52+2x53 +17.5y2+30y3+37.5y4+50y5s.t.x11+x12+x13 30 (A1 厂的产量限制厂的产量限制)x21+x22+x23 10y2 (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
21、+x52=20 (B2 销地的限制销地的限制)x13+x23+x33+x43+x53=20 (B3 销地的限制销地的限制)xij 0 yi为为0-1变量变量，i=1,2,3,4,5；j=1,2,3第33页/共41页34例某公司考虑今后五年内给以下项目投资。例某公司考虑今后五年内给以下项目投资。项目项目A：每年年初需要投资，于次年末回收本利：每年年初需要投资，于次年末回收本利115%，但要求第，但要求第1年投资最低金额为年投资最低金额为4万元，第万元，第2、3、4年年不限；不限；项目项目B：第：第3年初投资，到第年初投资，到第5年未能回收本利年未能回收本利128，但规定最低投资金额为但规定最低投
22、资金额为3万元，最高金额为万元，最高金额为5万元；万元；项目项目 C：第：第2年初投资，到第年初投资，到第5年未能回收本利年未能回收本利140%，但规定其投资额只能为，但规定其投资额只能为2、4、6或或8万元。万元。项目项目 D：每年初可购买公债，于当年末归还，并加利：每年初可购买公债，于当年末归还，并加利息息6%，此项投资金额不限。，此项投资金额不限。该部门现有资金该部门现有资金10万元，问它应如何确定万元，问它应如何确定给这些项目的每年投资额，使到第给这些项目的每年投资额，使到第 5 年末拥有年末拥有的资金本利总额为最大的资金本利总额为最大?第34页/共41页35解：1)设xiA、xiB、
23、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）。设yiC 是非负整数变量，并规定：2年投资C项目为8万元、6万元、4万元、2万元、不投资C项目时，分别取值为4、3、2、1、0；变量：第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C(=20000y2C)D x1D x2D x3D x4D x5D 第35页/共41页362）约束条件：）约束条件：第一年：年初有第一年：年初有10元，元，D项目
24、在年末可收回投项目在年末可收回投资，故第一年年初应把全部资金投出去，于是资，故第一年年初应把全部资金投出去，于是 x1A+x1D=10；第二年：第二年：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；第五年：年初的资金为第五年：
25、年初的资金为 1.15x3A+1.06x4D，于是，于是 x5D=1.15x3A+1.06x4D；第36页/共41页37关于项目关于项目A的投资额规定的投资额规定:x1A 4y1A，x1A 20y1A，20是足够大的数；是足够大的数；保证当保证当 y1A=0时，时，x1A=0；当当 y1A=1时，时，x1A 4。关于项目关于项目B的投资额规定的投资额规定:x3B 3y3B，x3B 5y3B；保证当保证当 y3B=0时，时，x3B=0；当当y3B=1时，时，5 x3B 。关于项目关于项目C的投资额规定的投资额规定:x2C=2y2C，y2C=0，1，2，3，4。第37页/共41页383）模型：）模
26、型：Max z=1.15x4A+1.40 x2C+1.28x3B+1.06x5D s.t.x1A+x1D=10；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A 4y1A，x1A 20y1A，x3B 3y3B，x3B 5y3B；x2C=2y2C，yiA，yiB=0 或或 1，i=1,2,3,4,5 y2C=0，1，2，3，4 xiA,xiB,xiC,xiD0(i=1,2,3,4,5)第38页/共41页作业：1.计算机求解PPT-29,PPT-39问题的解第39页/共41页作业：1.P161-6.4，建模不求解2.计算机求解P305-306 S2.1，S2.2第40页/共41页感谢您的观看！第41页/共41页