第4讲整数规划与0-1规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击鼠标编辑标题文的格式,单击鼠标编辑大纲正文格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,*,第四讲 整数规划与,0-1,规划,哈尔滨金融学院,数学建模,基础教研部：夏冰,数学规划模型,x,决策变量,f,(,x,),目标函数,g,i,(,x,),0,约束条件,分类：线性规划,整数规划与,0,1,规划,非线性规划,重点：模型的建立和结果的分析,哈尔滨金融学院,数学建模,安排生产计划,满足每周的需求,使,4,周总费用最小。,存贮费,:,每周每千箱饮料,0.2,千元。,例,3,饮料厂的生产与检修计划,在,4,周内安排一次设备检修，占用当周,15,千箱生产能力，能使检修后每周增产,5,千箱，检修应排在哪一周,?,周次,需求量,(,千箱,),生产能力,(,千箱,),成本,(,千元,/,千箱,),1,15,30,5.0,2,25,40,5.1,3,35,45,5.4,4,25,20,5.5,合计,100,135,某种,饮料,4,周的需求量、生产能力和成本,哈尔滨金融学院,数学建模,问题分析,除第,4,周外每周的生产能力超过每周的需求；,生产成本逐周上升；,前几周应多生产一些。,周次,需求,能力,1,15,30,2,25,40,3,35,45,4,25,20,合计,100,135,成本,5.0,5.1,5.4,5.5,哈尔滨金融学院,数学建模,饮料厂在第,1,周开始时没有库存；,从费用最小考虑,第,4,周末不能有库存；,周末有库存时需支出一周的存贮费，,存贮费,:0.2(,千元,/,周,千箱,),；,每周末的库存量等于下周初的库存量。,模型假设,哈尔滨金融学院,数学建模,x,1,x,4,：第,14,周,的生产量,y,1,y,3,：第,13,周末,库存量,符号说明,目标函数,约束条件,产量、库存与需求平衡,能力限制,非负限制,建立模型,哈尔滨金融学院,数学建模,思考：,在,4,周内安排一次设备检修，占用当周,15,千箱生产能力，能使检修后每周增产,5,千箱，检修应排在哪一周,?,哈尔滨金融学院,数学建模,约束条件,目标函数,产量、库存与需求平衡条件不变,检修安排在任一周均可，由此引入,0-1,变量,w,t,：,w,t,=1,表示检修安排在第,t,周,(,t,=1,2,3,4,）。,生产能力限制,检修安排在任一周均可，由此引入,0-1,变量,w,t,：,w,t,=1,表示检修安排在第,t,周,(,t,=1,2,3,4,）。,检修次数限制,数学建模,哈尔滨金融学院,应用,Lingo,软件计算得,:,w,1,=,1,w,2,w,3,w,4,=0;,x,1,x,4,：,15,45,15,25,；,y,1,y,3,：,0,20,0;,max Z=527,如果生产某一类型汽车，则至少要生产,80,辆，那么最优的生产计划应作何改变？,例,4,汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,小型 中型 大型,现有量,钢材（吨）,1.5 3 5 600,劳动时间（小时）,280 250 400 60000,利润（万元）,2 3 4,制订月生产计划，使工厂的利润最大。,哈尔滨金融学院,数学建模,设每月生产小、中、大型汽车的数量分别为,x,1,x,2,x,3,建立模型,小型 中型 大型 现有量,钢材,1.5 3 5 600,时间,280 250 400 60000,利润,2 3 4,线性规划模型,(LP),哈尔滨金融学院,数学建模,模型求解,OBJECTIVE FUNCTION VALUE,1)632.2581,VARIABLE VALUE REDUCED COST,X1 64.516129,0.000000,X2 167.741928,0.000000,X3 0.000000 0.946237,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 0.731183,3)0.000000 0.003226,1,）舍去小数：取,x,1,=64,，,x,2,=167,，,算出目标函数值,z,=629,，与,LP,最优值,632.2581,相差不大。,2,）试探：如取,x,1,=65,，,x,2,=167,；,x,1,=64,，,x,2,=168,等，计算函数值,z,，,通过比较可能得到更优的解。,哈尔滨金融学院,数学建模,应用,Lingo,软件求解得,整数规划,(,Integer Programming,简记,IP,),IP,的最优解,x,1,=64,，,x,2,=168,，,x,3,=0,，,最优值,z,=632,模型的改进,哈尔滨金融学院,数学建模,若生产某类汽车，则至少生产,80,辆，求生产计划。,哈尔滨金融学院,数学建模,建立模型,x,1,x,2,x,3,=,0,或,80,其中,3,个,子模型应,去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法,1,：,分解为,8,个,LP,子模型,x,1,=80,，,x,2,=150,，,x,3,=0,，,最优值,z,=610,哈尔滨金融学院,数学建模,x,1,x,2,x,3,=,0,或,80,方法,2,：,引入,0-1,变量，化为整数规划,注：,M,为大的正数，可取,1000,若,生产某类汽车，,则至少生产某类汽车生产,80,辆，求生产计划。,x,1,=0,或,80,x,2,=0,或,80,x,3,=0,或,80,哈尔滨金融学院,数学建模,练习,3,载货问题,一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面下表所示。,前舱,中舱,后舱,最大允许载重量,(,t,),2000,3000,1500,容积,(,m,3,),4000,5400,1500,现有三种货物待运，已知有关数据列于下表。,商品,数量（件）,每件体积（,m,3,/,件）,每件重量（,t/,件）,运价,（元,/,件）,A,600,10,8,1000,B,1000,5,6,700,C,800,7,5,600,数学建模,哈尔滨金融学院,为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过,15%,，前、后舱之间不超过,10%,。问该货轮应装载,A,、,B,、,C,各多少件，运费收入为最大？,数学建模,哈尔滨金融学院,因为,A,、,B,、,C,三种商品在货轮的前、中、后舱均可装载，令,i,=1,2,3,分别代表商品,A,、,B,、,C,，用,j,=1,2,3,分别代表前、中、后舱。设决策变量,x,ij,为装于,j,舱位的第,i,种商品的数量（件）。,数学建模,哈尔滨金融学院,问题分析,(1),确定目标函数,商品,A,的件数为：,x,11+,x,12+,x,13,，即装于货轮前、中、后舱商品,A,的件数之和；,商品,B,的件数为：,x,21+,x,22+,x,23,，即装于货轮前、中、后舱商品,B,的件数之和；,商品,C,的件数为：,x,31+,x,32+,x,33,，即装于货轮前、中、后舱商品,C,的件数之和。,为使运费总收入最大，目标函数为,max,Z,=1000(,x,11,+,x,12,+,x,13,)+700(,x,21,+,x,22,+,x,23,)+600(,x,31,+,x,32,+,x,33,),数学建模,哈尔滨金融学院,(2),确定约束条件,前、中、后舱位载重量限制为：,8,x,11,+6,x,21,+,5,x,31,2000,8,x,12,+6,x,22,+,5,x,32,3000,8,x,13,+6,x,23,+,5,x,33,1500,前、中、后舱位体积限制为：,10,x,11,+5,x,21,+,7,x,31,4000,10,x,12,+5,x,22,+,7,x,32,5400,10,x,13,+6,x,23,+,7,x,33,1500,A,、,B,、,C,三种商品数量限制为：,x,11+,x,12+,x,13,600,x,21+,x,22+,x,23,1000,x,31+,x,32+,x,33,800,根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过,15%,，前、后舱之间不超过,10%,，可得舱体平衡条件为：,且各决策变量要求非负，即,x,ij,0,，,i,=1,2,3,，,j,=1,2,3,。综上所述，该问题的线性规划模型如下：,数学建模,哈尔滨金融学院,数学建模,哈尔滨金融学院,最后解得,：,x,11,=206.7722,，,x,12,=318.2278,，,x,13,=75,，,x,21,=0,，,x,22,=0,，,x,23,=150,，,x,31,=69.1646,，,x,32,=90.8354,，,x,33,=0,；,总费用为：,8.01,10,5,。,数学建模,哈尔滨金融学院,数学对经济竞争力至为重要，数学是一种关键的普遍使用的、并授予人能力的技术。,格里姆,(,美国科学院院士,),数学建模,哈尔滨金融学院,