数学模型 第六讲 整数规划模型与求解软件2011

1、E-MAIL: 数学模型课程教学课件Copyright 2011 Dalian Jiaotong University. All rights reserved.2010-2011学年第二学期1第六讲 整数规划模型与0-1规划 时间：2011年3月24日主讲人：周大勇E-MAIL:整数规划模型及其处理方法0-1规划模型及其处理方法数学软件求解上述模型分析2请各小组思考下列问题 数学规划模型的一般形式是什么？E-mail: 常用的解决规划模型的软件有哪些？3规划模型构成及软件处理实际问题中的优化模型x决策变量f(x)目标函数gi(x)0约束条件数学规划线性规划非线性规划整数规划重点在模型的建立和

2、结果的分析E-mail:处理软件LindoLingo MatlabMathematica 4设每月生产小、中、大型汽车的数量分别为x1, x2, x3汽车厂生产计划 模型建立 小型 中型 大型 现有量钢材 1.5 3 5 600时间 280 250 400 60000利润 2 3 4 线性规划模型(LP)E-mail:5模型求解 3） 模型中增加条件：x1, x2, x3 均为整数，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0

3、.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，通过比较可能得到更优的解。 但必须检验它们是否满足约束条件。为什么？请写出在Lindo软件的源程序E-mail:6IP可用LINDO直接求解整数规划(Integer Programmin

4、g,简记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.000000 -4.000000 IP 结果输出E-mail:7其

5、中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型 汽车厂生产计划-讨论 若生产某类汽车，则至少生产80辆，求生产计划。x1,x2, x3=0 或 80 x1=80，x2= 150，x3=0，最优值z=6108LINDO中对0-1变量的限定：int y1int y2int y3 方法2：引入0-1变量，化为整数规划 M为大的正数，可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000

6、 -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 x2=0 或 80 x3=0 或 80最优解同前 E-mail:9NLP虽然可用现成的数学软件求解(如LINGO, MATLAB)，但是其结果常依赖于初值的选择。 方法3：化为非线性规划 非线性规划（Non- Linear Programming，简记NLP） 实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。 若生

7、产某类汽车，则至少生产80辆，求生产计划。 x1=0 或 80 x2=0 或 80 x3=0 或 80E-mail:10分派问题 接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。E-mail:11丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?混合泳接力队的选拔

8、甲乙丙丁戊蝶泳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目标函数若选择队员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

9、.8j=458.65359.457.262.4每种泳姿有且只有1人 E-mail:13模型求解 最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0;成绩为253.2(秒)=413”2 MIN 66.8x11+75.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求解 甲乙丙丁戊蝶泳106”857

10、”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.E-mail:14丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否调整？ 敏感性分析？乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21 = x32 = x43 = x54 = 1, 成绩为417”7 c43, c54 的新数据重新输入模型，用LINDO求

11、解 指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大. 讨论甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.原方案E-mail:15为了选修课程门数最少，应学习哪些课程 ？ 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课 课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数选修课程最少

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

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

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

15、8预测理论29数学实验3 E-mail:21讨论与思考最优解与1=0，2=1的结果相同学分最多多目标规划 最优解与1=1，2=0的结果相同课程最少E-mail:22“课程论文二”发布时间，请安静！ 论文上交时间：2011年 9月 27 日E-mail:注意 （1）封面必须是打印版，格式已下发 （2）从摘要开始全部为手写稿。23课程论文评分标准 方法新颖巧妙，格式非常好 20分模型建立，求解合理，格式很好 18-19分 模型建立，求解合理，格式规范 16-17分模型建立，求解基本合理，格式一般 14-15分模型建立，求解有问题，格式一般 12-13分模型建立不正确，格式糟糕，态度有问题 0-6分E-mail:24E-mail:A题：营养配餐问题每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表A-1中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20 kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜，为了使费用最小又满足营养素等其它方面的要求，试建立数学模型，说明在下一周内应当供应每种蔬菜各多少kg？25表A-1E-mail:26B题:广告竞