整数线性规划及规划.pptx

《整数线性规划及规划.pptx》由会员分享，可在线阅读，更多相关《整数线性规划及规划.pptx（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、令xj表示第j种物品的装入件数模型建立 整数线性规划模型(IP)第1页/共22页典型的整数线性规划问典型的整数线性规划问题题 二、投资问题今有一笔资金，设金额为b个单位，可以投资的发展项目有n个，要求对每个发展项目的的投资单位数必须是非负整数，且只考虑两种决策：要么投资，要么不投资，若对第j个发展项目投资，所花资金为aj。已知对第j个发展项目每投资一单位可获利cj个单位，问如何投资才能使总利润最大？第2页/共22页令xj表示对第j个发展项目的投资数量模型建立 整数线性规划01模型(IP)第3页/共22页 如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例例1 汽车厂生产

2、计汽车厂生产计划划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234制订月生产计划，使工厂的利润最大。整数线性规划及01规划第4页/共22页设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划 模型建立 小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)第5页/共22页模型求解 3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)6

3、32.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)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，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？第6页/共22页IP可用

4、LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解 IP结果输出第

5、7页/共22页其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划 若生产某类汽车，则至少生产80辆，求生产计划。x1,x2,x3=0或80 x1=80，x2=150，x3=0，最优值z=610第8页/共22页LINDO中对0-1变量的限定：inty1inty2inty3方法2：引入0-1变量，化为整数规划M为大的正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X3

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

7、3=0或80第10页/共22页丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例例2 混合泳接力队的选拔混合泳接力队的选拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。第11页/共22页目标函数若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0 0-1规划模规划模型型 cij(秒

8、)队员i 第j 种泳姿的百米成绩约束条件每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人 第12页/共22页模型求解 最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=413”2MIN66.8x11+75.6x12+87x13+58.6x14+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14=1x41+x42+x43+x

9、44=1x11+x21+x31+x41+x51=1x14+x24+x34+x44+x54=1ENDINT20输入LINDO求解 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.第13页/共22页丁蛙泳c43=69.675.2，戊自由泳c54=62.457.5,方案是否调整？敏感性分析？乙蝶泳、丙仰泳、丁蛙泳、戊自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最

10、优解：x21=x32=x43=x51=1,成绩为417”7c43,c54 的新数据重新输入模型，用LINDO求解 指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.原方案第14页/共22页为了选修课程门数最少，应学习哪些课程？例例3 选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课 课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹

11、学计算机编程7计算机编程2计算机8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？第15页/共22页0-1规划模型 决策变量 目标函数 xi=1选修课号i 的课程（xi=0不选）选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机第16页/共22页先修课程要求最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，

12、总学分210-1规划模型 约束条件x3=1必有x1=x2=1模型求解（LINDO）课号课名先修课要求1微积分2线性代数3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程8预测理论应用统计9数学实验微积分；线性代数第17页/共22页学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少以学分最多为目标，不管课程多少。以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。第18页/共22页多目标规划 在课程最少的前提下以学分最多为

13、目标。最优解：x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束 ，以学分最多为目标求解。第19页/共22页多目标规划 对学分数和课程数加权形成一个目标，如三七开。最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3第20页/共22页讨论与思考最优解与1=0，2=1的结果相同学分最多多目标规划 最优解与1=1，2=0的结果相同课程最少第21页/共22页感谢您的观看！第22页/共22页