运筹学整数规划建模.pptx

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