整数线性规划及0-1规划.ppt

《整数线性规划及0-1规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、典型的整数线性规划问题一、背包问题有一徒步旅行者要带一背包，设对背包的总重量限制为b千克，今有n种物品可供选择，已知第j种物品每件重量为aj千克，使用价值为cj，问旅行者应如何选取这些物品，使得总价值最大？整数线性规划及0－1规划令xj表示第j种物品的装入件数模型建立整数线性规划模型(IP)典型的整数线性规划问题二、投资问题今有一笔资金，设金额为b个单位，可以投资的发展项目有n个，要求对每个发展项目的的投资单位数必须是非负整数，且只考虑两种决策：要么投资，要么不投资，若对第j个发展项目投资，所花资金为a

2、j。已知对第j个发展项目每投资一单位可获利cj个单位，问如何投资才能使总利润最大？令xj表示对第j个发展项目的投资数量模型建立整数线性规划0－1模型(IP)如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234制订月生产计划，使工厂的利润最大。整数线性规划及0－1规划设每月生

3、产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRIC

4、ES2)0.0000000.7311833)0.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx

5、3IP的最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解IP结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约

6、束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划若生产某类汽车，则至少生产80辆，求生产计划。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINDO中对0-1变量的限定：inty1inty2inty3方法2：引入0-1变量，化为整数规划M为大的正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000

7、X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80x2=0或80x3=0或80最优解同前NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。

8、若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80x2=0或80x3=0或80丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例2混合泳接力队的选拔甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳