《典型的整数线性规划问题.ppt》由会员分享，可在线阅读，更多相关《典型的整数线性规划问题.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、典型的整数线性规划问题典型的整数线性规划问题一、背包问题一、背包问题有一徒步旅行者要带一背包，设对背包的总重量有一徒步旅行者要带一背包，设对背包的总重量限制为限制为b千克，今有千克，今有n种物品可供选择，已知第种物品可供选择，已知第j种种物品每件重量为物品每件重量为aj千克，使用价值为千克，使用价值为cj，问旅行者，问旅行者应如何选取这些物品，使得总价值最大？应如何选取这些物品，使得总价值最大？整数线性规划及整数线性规划及01规划规划令令xj表示第表示第j种物品的装入件数种物品的装入件数模型建立模型建立 整数整数线性线性规划规划模型模型(IP)典型的整数线性规划问题典型的整数线性规划问题二、投
2、资问题二、投资问题今有一笔资金，设金额为今有一笔资金，设金额为b个单位，可以投资的发个单位，可以投资的发展项目有展项目有n个，要求对每个发展项目的的投资单位个，要求对每个发展项目的的投资单位数必须是非负整数，且数必须是非负整数，且只考虑两种决策：要么投只考虑两种决策：要么投资，要么不投资资，要么不投资，若对第，若对第j个发展项目投资，所花个发展项目投资，所花资金为资金为aj。已知对第。已知对第j个发展项目每投资一单位可个发展项目每投资一单位可获利获利cj个单位，问如何投资才能使总利润最大？个单位，问如何投资才能使总利润最大？令令xj表示对第表示对第j个发展项目的投资数量个发展项目的投资数量模型
3、建立模型建立 整数整数线性线性规划规划01模型模型(IP)如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1汽车厂生产计划汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材、劳动时间的需求，利润及工厂每月的现有量。小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂
4、的利润最大。制订月生产计划，使工厂的利润最大。整数线性规划及整数线性规划及01规划规划设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.
5、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、满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？IP可用可用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.0000VARIABLEVALUEREDUCEDCOSTX16
7、4.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解模型求解 IP结果输出结果输出其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610LINDO中中 对对 0-1变量
8、的限定：变量的限定：inty1inty2inty3方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数，为大的正数，可取可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或
9、 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解(如如LINGO,MATLAB)，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）实实践践表表明明，本本例例仅仅当当初初值值非非常常接接近近上上面面方方法法算算出出的最优解时，才能得到正确的结果。的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 8
10、0 x2=0 或 80 x3=0 或 80丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步到57”5,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队?例例2混合泳接力队的选拔混合泳接力队的选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的名候选人的百米成绩百米成绩穷举
11、法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型规划模型 cij(秒秒)队员队员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 1人人 模型求解模型求解 最最优优解解：
12、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+x44=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”
13、6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.丁蛙泳丁蛙泳c43=69.675.2，戊自由泳，戊自由泳c54=62.457.5,方案是否调整？方案是否调整？敏感性分析？敏感性分析？乙乙蝶泳、丙蝶泳、丙仰泳、仰泳、丁丁蛙泳、戊蛙泳、戊自由泳自由泳IP规划一般没有与规划一般没有与LP规划相类似的理论，规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。输出的敏感性分析结果通常是没有意义的。最优解：最优解：x21=x32=x43=x51=1,成绩为成绩为417”7c43,c54 的新数据重新输
14、入模型，用的新数据重新输入模型，用LINDO求解求解 指派指派(Assignment)问题问题：每项任务有且只有一人承担，每项任务有且只有一人承担，每人只能承担一项每人只能承担一项，效益不同，怎样分派使总效益最大，效益不同，怎样分派使总效益最大.讨论讨论甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.原原方方案案为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？例例3选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分
15、5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型规划模
16、型 决策变量决策变量 目标函数目标函数 xi=1选修课号选修课号i 的的课程（课程（xi=0不选）不选）选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课。门计算机课。课号课号课名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学实验数学实验运筹学；计算机运筹学；计
17、算机先修课程要求先修课程要求最优解：最优解：x1=x2=x3=x6=x7=x9=1,其它为其它为0；6门课程，总学分门课程，总学分210-1规划模型规划模型 约束条件约束条件x3=1必有必有x1=x2=1模型求解（模型求解（LINDO）课号课号课名课名先修课要求先修课要求1微积分微积分2线性代数线性代数3最优化方法最优化方法微积分；线性代数微积分；线性代数4数据结构数据结构计算机编程计算机编程5应用统计应用统计微积分；线性代数微积分；线性代数6计算机模拟计算机模拟计算机编程计算机编程7计算机编程计算机编程8预测理论预测理论应用统计应用统计9数学实验数学实验微积分；线性代数微积分；线性代数学分最
18、多学分最多多目标优化的处理方法：化成单目标优化。多目标优化的处理方法：化成单目标优化。两目标两目标(多目标多目标)规划规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少课程最少以以学分最多为目标，不学分最多为目标，不管课程多少。管课程多少。以以课程最少课程最少为目标，不为目标，不管学分多少。管学分多少。最优解如上，最优解如上，6门课门课程，总学分程，总学分21。最优解显然是选修所最优解显然是选修所有有9门课程门课程。多目标规划多目标规划 在在课程最少的前提下课程最少的前提下以以学分最多为目标。学分最多为目标。最优解：最优解：x1=x2
19、=x3=x5=x7=x9=1,其它为其它为0；总总学分由学分由21增至增至22。注意：最优解不唯一！注意：最优解不唯一！课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 LINDO无法告诉优化无法告诉优化问题的解是否唯一。问题的解是否唯一。可将可将x9=1易为易为x6=1增加约束增加约束 ，以学分最多为目标求解。以学分最多为目标求解。多目标规划多目标规划 对学分数和课程数加权形成一个目标，如三七开。对学分数和课程数加权形成一个目标，如三七开。最优解：最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为其它为0；总学分总学分28。课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 讨论与思考讨论与思考最优解最优解与与 1=0，2=1的结果相同的结果相同学分最多学分最多多目标规划多目标规划 最优解最优解与与 1=1，2=0的结果相同的结果相同课程最少课程最少