《第4讲整数规划与0-1规划》由会员分享，可在线阅读，更多相关《第4讲整数规划与0-1规划（23页珍藏版）》请在金锄头文库上搜索。
1、第四讲 整数规划与0-1规划,哈尔滨金融学院,数学建模,基础教研部：夏冰,数学规划模型,x决策变量,f(x)目标函数,gi(x)0约束条件,分类：线性规划 整数规划与01规划 非线性规划,重点：模型的建立和结果的分析,哈尔滨金融学院,数学建模,安排生产计划, 满足每周的需求, 使4周总费用最小。,存贮费:每周每千箱饮料 0.2千元。,例3 饮料厂的生产与检修计划,在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?,某种饮料4周的需求量、生产能力和成本,哈尔滨金融学院,数学建模,问题分析,除第4周外每周的生产能力超过每周的需求； 生产成本逐周上升；
2、前几周应多生产一些。,哈尔滨金融学院,数学建模,饮料厂在第1周开始时没有库存； 从费用最小考虑, 第4周末不能有库存； 周末有库存时需支出一周的存贮费， 存贮费:0.2 (千元/周千箱) ； 每周末的库存量等于下周初的库存量。,模型假设,哈尔滨金融学院,数学建模,x1 x4：第14周的生产量,y1 y3：第13周末库存量,符号说明,目标函数,约束条件,产量、库存与需求平衡,能力限制,非负限制,建立模型,哈尔滨金融学院,数学建模,思考：在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?,哈尔滨金融学院,数学建模,约束条件,目标函数,产量、库存与需求平
3、衡条件不变,检修安排在任一周均可，由此引入0-1变量wt ：wt=1表示检修安排在第t周(t=1,2,3,4）。,生产能力限制,检修安排在任一周均可，由此引入0-1变量wt ：wt=1表示检修安排在第t周(t=1,2,3,4）。,检修次数限制,数学建模,哈尔滨金融学院,应用Lingo软件计算得:w1=1, w2 , w3, w4=0; x1 x4：15,45,15,25； y1 y3：0,20,0 ; max Z=527,如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？,例4 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂
4、每月的现有量。,制订月生产计划，使工厂的利润最大。,哈尔滨金融学院,数学建模,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,建立模型,线性规划模型(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
5、0.003226,1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,哈尔滨金融学院,数学建模,应用Lingo软件求解得,整数规划(Integer Programming,简记IP),IP 的最优解x1=64，x2=168，x3=0，最优值z=632,模型的改进,哈尔滨金融学院,数学建模,若生产某类汽车，则至少生产80辆，求生产计划。,哈尔滨金融学院,数学建模,建立模型,x1,x2, x3=0 或 80,其中3个子模型应去掉，然后
6、逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1： 分解为8个LP子模型,x1=80，x2= 150，x3=0，最优值z=610,哈尔滨金融学院,数学建模,x1,x2, x3=0 或 80,方法2： 引入0-1变量，化为整数规划,注：M为大的正数，可取1000,若生产某类汽车， 则至少生产某类汽车生产80辆，求生产计划。,x1=0 或 80,哈尔滨金融学院,数学建模,练习3 载货问题,一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面下表所示。,现有三种货物待运，已知有关数据列于下表。,数学建模,哈尔滨金融学院,为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱
7、最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。问该货轮应装载 A、B、C各多少件，运费收入为最大？,数学建模,哈尔滨金融学院,因为A、B、C三种商品在货轮的前、中、后舱均可装载，令 i = 1, 2, 3 分别代表商品 A、B、C，用 j = 1, 2, 3 分别代表前、中、后舱。设决策变量 xij 为装于 j 舱位的第 i 种商品的数量（件）。,数学建模,哈尔滨金融学院,问题分析,(1) 确定目标函数 商品 A 的件数为：x11 + x12 + x13，即装于货轮前、中、后舱商品 A 的件数之和； 商品 B 的件数为：x2
8、1 + x22 + x23，即装于货轮前、中、后舱商品 B 的件数之和； 商品 C 的件数为：x31 + x32 + x33，即装于货轮前、中、后舱商品 C 的件数之和。,为使运费总收入最大，目标函数为 maxZ=1000(x11+x12+x13)+700(x21+x22+x23)+600(x31+x32+x33),数学建模,哈尔滨金融学院,(2) 确定约束条件 前、中、后舱位载重量限制为： 8x11 + 6x21 + 5x31 2000 8x12 + 6x22 + 5x32 3000 8x13 + 6x23 + 5x33 1500 前、中、后舱位体积限制为： 10x11 + 5x21 + 7
9、x31 4000 10x12 + 5x22 + 7x32 5400 10x13 + 6x23 + 7x33 1500,A、B、C 三种商品数量限制为： x11 + x12 + x13 600 x21 + x22 + x23 1000 x31 + x32 + x33 800,根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%，可得舱体平衡条件为：,且各决策变量要求非负，即 xij 0，i = 1, 2, 3， j = 1, 2, 3。综上所述，该问题的线性规划模型如下：,数学建模,哈尔滨金融学院,数学建模,哈尔滨金融学院,最后解得： x11 = 206.7722，x12 = 318.2278， x13 = 75， x21 = 0， x22 = 0， x23 = 150， x31 = 69.1646， x32 = 90.8354， x33 = 0； 总费用为：8.01105。,数学建模,哈尔滨金融学院,数学对经济竞争力至为重要，数学是一种关键的普遍使用的、并授予人能力的技术。 格里姆(美国科学院院士),数学建模,哈尔滨金融学院,
