数学模型第六讲整数规划模型与求解软件省公共课一等奖全国赛课获奖课件.pptx

LOGO主讲人：周大勇主讲人：周大勇E-MAIL:E-MAIL:理学院应用数学教研室理学院应用数学教研室 数学模型数学模型课程教学课件课程教学课件版权全部：大连交通大学理学院应用数学教研室版权全部：大连交通大学理学院应用数学教研室 Copyright Dalian Jiaotong University.All rights reserved.Copyright Dalian Jiaotong University.All rights reserved.-年第二学期年第二学期第1页LOGO第六讲第六讲 整数规划模型与整数规划模型与0-10-1规划规划 时间：3月24日主讲人：周大勇E-MAIL:整数规划模型及其处理方法整数规划模型及其处理方法0-1规划规划模型及其处理方法模型及其处理方法数学软件求解上述模型分析数学软件求解上述模型分析第2页LOGO请请各小组思索以下问题各小组思索以下问题 数学规划模型普通形式是什么？数学规划模型普通形式是什么？E-mail:惯用处理规划模型软件有哪些？惯用处理规划模型软件有哪些？第3页LOGO规划模型组成及软件处理规划模型组成及软件处理实际问题中实际问题中优化模型优化模型x决议变量决议变量f(x)目标函数目标函数gi(x)0约束条约束条件件数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型建立和结果分析重点在模型建立和结果分析E-mail:处处理理软软件件LindoLingoMatlabMathematica第4页LOGO设每个月生产小、中、大设每个月生产小、中、大型汽车数量分别为型汽车数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)E-mail:第5页LOGO模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.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，经过比较可能得到更优解。，经过比较可能得到更优解。但必须检验它们是否满足约束条件。为何？但必须检验它们是否满足约束条件。为何？请写出在请写出在Lindo软件源程序软件源程序E-mail:第6页LOGOIP可用可用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.000000IP结果输出结果输出E-mail:第7页LOGO其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划-讨论讨论 若生产某类汽车，则最少生产若生产某类汽车，则最少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610第8页LOGOLINDO中中 对对 0-1变量限定：变量限定：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 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前E-mail:第9页LOGONLP即即 使使 可可 用用 现现 成成 数数 学学 软软 件件 求求 解解(如如 LINGO,MATLAB)，不过其结果常依赖于初值选择。，不过其结果常依赖于初值选择。方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）实实践践表表明明，本本例例仅仅当当初初值值非非常常靠靠近近上上面面方方法法算算出出最优解时，才能得到正确结果。最优解时，才能得到正确结果。若生产某类汽车，则最少生产若生产某类汽车，则最少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80E-mail:第10页LOGO分配问题分配问题 接力队选拔和选课策略接力队选拔和选课策略若干项任务分给一些候选人来完成，每人专长不一样，若干项任务分给一些候选人来完成，每人专长不一样，完成每项任务取得效益或需要资源就不一样，怎样分配完成每项任务取得效益或需要资源就不一样，怎样分配任务使取得总效益最大，或付出总资源最少。任务使取得总效益最大，或付出总资源最少。若干种策略供选择，不一样策略得到收益或付出成本若干种策略供选择，不一样策略得到收益或付出成本不一样，各个策略之间有相互制约关系，怎样在满足不一样，各个策略之间有相互制约关系，怎样在满足一定条件下作出决择，使得收益最大或成本最小。一定条件下作出决择，使得收益最大或成本最小。E-mail:第11页LOGO丁蛙泳成绩退步到丁蛙泳成绩退步到115”2；戊自由泳成绩进步到；戊自由泳成绩进步到57”5,组成接力队方案是否应该调整组成接力队方案是否应该调整？怎样选拔队员组成怎样选拔队员组成4 4 100100米混合泳接力队米混合泳接力队?混合泳接力队选拔混合泳接力队选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳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种种。E-mail:第12页LOGO目标目标函数函数若选择队员若选择队员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人人 E-mail:第13页LOGO模型求解模型求解 最最优优解解：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”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.E-mail:第14页LOGO丁蛙泳丁蛙泳c43=69.675.2，戊自由泳，戊自由泳c54=62.457.5,方案是否调整？方案是否调整？敏感性分析？敏感性分析？乙乙蝶泳、丙蝶泳、丙仰泳、仰泳、丁丁蛙泳、戊蛙泳、戊自由泳自由泳IP规划普通没有与规划普通没有与LP规划相类似理论，规划相类似理论，LINDO输输出敏感性分析结果通常是没有意义。出敏感性分析结果通常是没有意义。最优解：最优解：x21=x32=x43=x54=1,成绩为成绩为417”7c43,c54 新数据重新输入模型，用新数据重新输入模型，用LINDO求解求解 指派指派(Assignment)问题问题：每项任务有且只有一人负担，每项任务有且只有一人负担，每人只能负担一项每人只能负担一项，效益不一样，怎样分配使总效益最，效益不一样，怎样分配使总效益最大大.讨论讨论甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.原原方方案案E-mail:第15页LOGO为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？选课策略选课策略要求最少选两门数学课、三门运筹学课和两门计算机课要求最少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学试验数学试验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽可能多，应学习哪些课程选修课程最少，且学分尽可能多，应学习哪些课程？E-mail:第16页LOGO0-1规划模型规划模型 决议变量决议变量 目标函数目标函数 xi=1选修课号选修课号i 课课程（程（xi=0不选）不选）选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课。门计算机课。课号课号课名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学试验数学试验运筹学；计算机运筹学；计算机E-mail:第17页LOGO先修课程要求先修课程要求最优解：最优解：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数学试验数学试验微积分；线性代数微积分；线性代数E-mail:第18页LOGO学分最多学分最多多目标优化处理方法：化成单目标优化。多目标优化处理方法：化成单目标优化。两目标两目标(多目标多目标)规划规划 讨论：选修课程最少，学分尽可能多，应学习哪些课程讨论：选修课程最少，学分尽可能多，应学习哪些课程？课程最少课程最少以以学分最多为目标，不学分最多为目标，不论课程多少。论课程多少。以课程最少以课程最少为目标，不为目标，不论学分多少。论学分多少。最优解如上，最优解如上，6门课门课程，总学分程，总学分21。最优解显然是选修全最优解显然是选修全部部9门课程门课程。E-mail:第19页LOGO多目标规划多目标规划 在在课程最少前提下课程最少前提下以以学分最多为目标。学分最多为目标。最优解：最优解：x1=x2=x3=x5=x7=x9=1,其它为其它为0；总总学分由学分由21增至增至22。注意：最优解不唯一！注意：最优解不唯一！课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学试验数学试验3 LINDO无法告诉优化无法告诉优化问题解是否唯一。问题解是否唯一。可将可将x9=1易为易为x6=1增加约束增加约束 ，以学分最多为目标求解。以学分最多为目标求解。E-mail:第20页LOGO多目标规划多目标规划 对学分数和课程数加权形成一个目标，如三七开。对学分数和课程数加权形成一个目标，如三七开。最优解：最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为其它为0；总学分总学分28。课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学试验数学试验3 E-mail:第21页LOGO讨论与思索讨论与思索最优解最优解与与 1=0，2=1结果相同结果相同学分最多学分最多多目标规划多目标规划 最优解最优解与与 1=1，2=0结果相同结果相同课程最少课程最少E-mail:第22页LOGO“课程论文二课程论文二”公布时间，请平静！公布时间，请平静！论文上交时间：9月27日E-mail:注意注意（1）封面必须是打印版，格式已下发封面必须是打印版，格式已下发（2）从摘要开始全部为手写稿。）从摘要开始全部为手写稿。第23页LOGO课程论文评分标准课程论文评分标准 方法新奇巧妙，格式非常好方法新奇巧妙，格式非常好20分分模型建立，求解合理，格式很好模型建立，求解合理，格式很好18-19分分模型建立，求解合理，格式规范模型建立，求解合理，格式规范16-17分分模型建立，求解基本合理，格式普通模型建立，求解基本合理，格式普通14-15分分模型建立，求解有问题，格式普通模型建立，求解有问题，格式普通12-13分分模型建立不正确，格式糟糕，态度有问题模型建立不正确，格式糟糕，态度有问题0-6分分E-mail:第24页LOGOE-mail:vA A题：营养配餐问题题：营养配餐问题v每种蔬菜含有营养素成份是不一样，从医学上知道，每人每七天对每种营养成份最低需求量。某医院营养室在制订下一周菜单时，需要确定表A-1中所列六种蔬菜供给量，方便使费用最小而又能满足营养素等其它方面要求。要求白菜供给一周内不多于20kg，其它蔬菜供给在一周内不多于40kg，每七天共需供给140kg蔬菜，为了使费用最小又满足营养素等其它方面要求，试建立数学模型，说明在下一周内应该供给每种蔬菜各多少kg？第25页LOGO表表A-1E-mail:第26页LOGOB题题:广告竞争计划广告竞争计划v某市场研究小组考虑下一步怎样选择广告竞争计某市场研究小组考虑下一步怎样选择广告竞争计划，在进行大量调查研究后，制订了各种可供选划，在进行大量调查研究后，制订了各种可供选择方案，方案特征数字以下：择方案，方案特征数字以下：E-mail:第27页LOGO广告计划目标是使受影响用户数为最大。上表广告计划目标是使受影响用户数为最大。上表所给出资源限制（资金、设计员和推销员）所给出资源限制（资金、设计员和推销员）外，还有以下约束条件：外，还有以下约束条件：（1 1）假如决定发起推销运动，那么必）假如决定发起推销运动，那么必须同时用电台或流行杂志配合；须同时用电台或流行杂志配合；（2 2）企业不能同时在商业杂志和流行）企业不能同时在商业杂志和流行杂志上作广告。杂志上作广告。假定各种广告伎俩所影响用户不一样，假定各种广告伎俩所影响用户不一样，不重复（即每一用户只受一个广告伎俩影响）不重复（即每一用户只受一个广告伎俩影响），请你们小组建立模型，说明怎样开展广告，请你们小组建立模型，说明怎样开展广告宣传？宣传？E-mail:第28页