《整数线性规划及0-1规划.ppt》由会员分享，可在线阅读，更多相关《整数线性规划及0-1规划.ppt（22页珍藏版）》请在三一办公上搜索。
1、典型的整数线性规划问题,一、背包问题 有一徒步旅行者要带一背包，设对背包的总重量限制为b千克，今有n种物品可供选择，已知第j种物品每件重量为aj千克，使用价值为cj，问旅行者应如何选取这些物品，使得总价值最大？,整数线性规划及01规划,令xj表示第j种物品的装入件数,模型建立,整数线性规划模型(IP),典型的整数线性规划问题,二、投资问题 今有一笔资金，设金额为b个单位，可以投资的发展项目有n个，要求对每个发展项目的的投资单位数必须是非负整数，且只考虑两种决策：要么投资，要么不投资，若对第j个发展项目投资，所花资金为aj。已知对第j个发展项目每投资一单位可获利cj个单位，问如何投资才能使总利润
2、最大？,令xj表示对第j个发展项目的投资数量,模型建立,整数线性规划01模型(IP),如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？,例1 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,制订月生产计划，使工厂的利润最大。,整数线性规划及01规划,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3）模型中增加条件：x1,x2,x3 均为整数，重新求解。,OBJECTIVE FUNCTION VALUE 1)632.2581VARIABLE VA
3、LUE 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）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,IP可
4、用LINDO直接求解,整数规划(Integer Programming,简记IP),“gin 3”表示“前3个变量为整数”，等价于：gin x1gin x2gin x3,IP 的最优解x1=64，x2=168，x3=0，最优值z=632,max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3,OBJECTIVE FUNCTION VALUE 1)632.0000VARIABLE VALUE REDUCED COST X1 64.000000-2.000000 X2 168.000000-3.000000 X3 0.0
5、00000-4.000000,模型求解,IP 结果输出,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划。,x1,x2,x3=0 或 80,x1=80，x2=150，x3=0，最优值z=610,LINDO中对0-1变量的限定：int y1int y2int y3,方法2：引入0-1变量，化为整数规划,M为大的正数，可取1000,OBJECTIVE FUNCTION VALUE 1)610.0000VARIABLE VALUE REDUCED COST X1 80.00000
6、0-2.000000 X2 150.000000-3.000000 X3 0.000000-4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划。,x1=0 或 80,最优解同前,NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。,方法3：化为非线性规划,非线性规划（Non-Linear Programming，简记NLP）,实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。,若生产某类汽车，
7、则至少生产80辆，求生产计划。,x1=0 或 80,丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,例2 混合泳接力队的选拔,5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=120种。,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(秒)队员i 第j 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,模型求解,最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=413”2,MIN 66.8x11+75
8、.6x12+87x13+58.6x14+67.4x51+71 x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14=1 x41+x42+x43+x44=1 x11+x21+x31+x41+x51=1 x14+x24+x34+x44+x54=1END INT 20,输入LINDO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,丁蛙泳c43=69.675.2，戊自由泳c54=62.4 57.5,方案是否调整？,敏感性分析？,乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。,最优
9、解：x21=x32=x43=x51=1,成绩为417”7,c43,c54 的新数据重新输入模型，用LINDO求解,指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.,讨论,为了选修课程门数最少，应学习哪些课程？,例3 选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,选修课程最少，且学分尽量多，应学习哪些课程？,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课，2门计算机课。,先修课程要求,最优解：x1=x2=x3=x6=x7=x9=
10、1,其它为0；6门课程，总学分21,0-1规划模型,约束条件,x3=1必有x1=x2=1,模型求解（LINDO）,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以学分最多为目标，不管课程多少。,以课程最少为目标，不管学分多少。,多目标规划,在课程最少的前提下以学分最多为目标。,最优解：x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。,注意：最优解不唯一！,LINDO无法告诉优化问题的解是否唯一。,可将x9=1 易为x6=1,多目标规划,对学分数和课程数加权形成一个目标，如三七开。,最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。,讨论与思考,最优解与1=0，2=1的结果相同学分最多,多目标规划,最优解与1=1，2=0的结果相同课程最少,
