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

1、第四讲第四讲 整数规划与整数规划与0-10-1规划规划基础教研部：夏冰基础教研部：夏冰数学规划模型数学规划模型 mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x决策变量决策变量f(x)目标函数目标函数gi(x) 0约束条件约束条件分类：线性规划分类：线性规划 整数规划与整数规划与01规划规划 非线性规划非线性规划 重点：模型的建立和结果的分析重点：模型的建立和结果的分析 安排生产计划安排生产计划, 满足每周的需求满足每周的需求, 使使4周总费用最小。周总费用最小。存贮费存贮费: :每周每千箱饮料每周每千箱饮料 0.2千元。千元。 例例3 3 饮料厂

2、的生产与检修计划饮料厂的生产与检修计划 在在4周内安排一次设备检修，占用当周周内安排一次设备检修，占用当周15千箱生产能千箱生产能力，能使检修后每周增产力，能使检修后每周增产5千箱，检修应排在哪一周千箱，检修应排在哪一周? ? 周次周次需求量需求量(千箱千箱)生产能力生产能力(千箱千箱)成本成本(千元千元/千箱千箱)115305.0225405.1335455.4425205.5合计合计100135 某种饮料某种饮料4周的需求量、生产能力和成本周的需求量、生产能力和成本问题分析问题分析 除第除第4周外每周的生产能力超过每周的需求；周外每周的生产能力超过每周的需求； 生产成本逐周上升；生产成本逐

3、周上升； 前几周应多生产一些。前几周应多生产一些。 周次周次需求需求能力能力11530225403354542520合计合计100135成本成本5.0 饮料厂在第饮料厂在第1周开始时没有库存；周开始时没有库存； 从费用最小考虑从费用最小考虑, , 第第4周末不能有库存；周末不能有库存； 周末有库存时需支出一周的存贮费，周末有库存时需支出一周的存贮费， 存贮费存贮费:0.2 (千元千元/周周千箱千箱) ； 每周末的库存量等于下周初的库存量。每周末的库存量等于下周初的库存量。 模型假设模型假设 x1 x4：第：第14周周的生产量的生产量y1 y3：第：第13周末周末库存量库存量符

4、号说明符号说明 目标函数目标函数约束条件约束条件产量、库存与需求平衡产量、库存与需求平衡 )( 2 . 05 . 54 . 51 . 50 . 53214321yyyxxxxzMin1511 yx25212yyx35323yyx2534 yx20,4540,304321xxxx能力限制能力限制非负限制非负限制 0,3214321yyyxxxx建立模型建立模型思考：思考：在在4 4周内安排一次设备检修，占用当周周内安排一次设备检修，占用当周1515千箱千箱生产能力，能使检修后每周增产生产能力，能使检修后每周增产5 5千箱，检修应排在哪千箱，检修应排在哪一周一周? ? )( 2 . 05 . 54

5、 . 51 . 50 . 53214321yyyxxxxzMin约束条件约束条件目标函数目标函数产量、库存与需求平衡条件不变产量、库存与需求平衡条件不变 检修安排在任一周均可，由此引入检修安排在任一周均可，由此引入0-1变量变量wt ：wt=1表示检修安排在第表示检修安排在第t周周(t=1,2,3,4）。）。生产能力限制生产能力限制 204540304321xxxx301511wx12254015wwx1233554515wwwx321445552015wwwwx检修安排在任一周均可，由此引入检修安排在任一周均可，由此引入0-1变量变量wt ：wt=1表示检修安排在第表示检修安排在第t周周(t

6、=1,2,3,4）。）。检修次数限制检修次数限制14321wwww应用应用LingoLingo软件计算得软件计算得: :w1= =1, w2 , w3, w4=0; x1 x4：15, ,45, ,15, ,25； y1 y3：0, ,20, ,0 ; max Z=527 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆， 那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例4 4 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。对钢材

7、、劳动时间的需求，利润及工厂每月的现有量。 小型小型 中型中型 大型大型 现有量现有量钢材（吨）钢材（吨） 1.5 3 5 600劳动时间（小时）劳动时间（小时） 280 250 400 60000利润（万元）利润（万元） 2 3 4 制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。设每月生产小、中、大型汽车的数量分别为设每月生产小、中、大型汽车的数量分别为x1, x2, x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx建立模型建立模型 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3

8、 5 600时间时间 280 250 400 60000利润利润 2 3 4 线性线性规划规划模型模型(LP)模型求解模型求解 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE 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.0032261）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标

9、函数值，算出目标函数值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 321432xxxzMax600535 . 1.321xxxts60000400250280321xxx为非负整数321,xxx模型的改进模型

10、的改进 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。321432xxxzMax600535 . 1.321xxxts60000400250280321xxx建立模型建立模型x1,x2, x3=0 或或 80其中其中3个个子模型应子模型应去掉，然后逐一求解，比较目标函去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：数值，再加上整数约束，得最优解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0

11、,321xxx方法方法1：分解为分解为8个个LP子模型子模型 x1=80，x2= 150，x3=0，最优值，最优值z=610 x1,x2, x3=0 或或 80方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划 注：注：M为大的正数，可取为大的正数，可取1000 若若生产某类汽车，生产某类汽车， 则至少生产某类汽车生产则至少生产某类汽车生产8080辆，辆，求生产计划。求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx练习练习3 3 载货问题载货

12、问题 一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面下表所示。前舱中舱后舱最大允许载重量(t)200030001500容积(m3)400054001500现有三种货物待运，已知有关数据列于下表。商品数量（件）每件体积（m3/件）每件重量（t/件）运价（元/件）A6001081000B100056700C80075600为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。问该货轮应装载 A、B、C各多少件，运费收入为最大？ 因为因为A、B、C三种商品在货轮的前

13、、中、后舱均三种商品在货轮的前、中、后舱均可装载，令可装载，令 i = 1, 2, 3 分别代表商品分别代表商品 A、B、C，用，用 j = 1, 2, 3 分别代表前、中、后舱。设决策变量分别代表前、中、后舱。设决策变量 xij 为装为装于于 j 舱位的第舱位的第 i 种商品的数量（件）。种商品的数量（件）。 问题分析问题分析 (1) 确定目标函数确定目标函数 商品商品 A 的件数为：的件数为：x11 + x12 + x13，即装于货轮，即装于货轮前、中、后舱商品前、中、后舱商品 A 的件数之和；的件数之和； 商品商品 B 的件数为：的件数为：x21 + x22 + x23，即装于货轮，即装

14、于货轮前、中、后舱商品前、中、后舱商品 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 前、中、

15、后舱位体积限制为： 10 x11 + 5x21 + 7x31 4000 10 x12 + 5x22 + 7x32 5400 10 x13 + 6x23 + 7x33 1500A、B、C 三种商品数量限制为： x11 + x12 + x13 600 x21 + x22 + x23 1000 x31 + x32 + x33 800 根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%，可得舱体平衡条件为： )15. 01 (32568568)15. 01 (32322212312111xxxxxx)10. 01 (34568568)10. 01 (34)15. 01 (21568568)15. 01 (21332313312111322212332313xxxxxxxxxx