线性规划模型自来水输送混合泳接力队的选拔.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划模型,指导老师,:,梁海峰,其他费用,:,450,元,/,千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,元,/,千吨,甲,乙,丙,丁,A,160,130,220,170,B,140,130,190,150,C,190,200,230,/,引水管理费,运输问题：自来水输送,收入：,900,元,/,千吨,支出,A：50,B：60,C：50,甲：,30,；,50,乙：,70,；,70,丙：,10,；,20,丁：,10,；,40,水库供水量,(,千吨,),小区基本用水量,(,千吨,),小区额外用水量,(,千吨,),（以天计）,总,供水量：,160,确定送水方案,使利润最大,问题分析,A：50,B：60,C：50,甲：,30,；,50,乙：,70,；,70,丙：,10,；,20,丁：,10,；,40,总需求量：,120+,180,=300,总收入,900,160,=144,000(,元,),收入：,900,元,/,千吨,其他费用,:,450,元,/,千吨,支出,引水管理费,其他,支出,450,160,=72,000(,元,),使引水管理费最小,供应限制,约束条件,需求限制,线性规划模型,(LP),目标函数,水库,i,向,j,区的日供水量为,x,ij,（,x,34,=0,）,决策变量,模型建立,确定,3,个水库向,4,个小区的供水量,引水管理费,(,元,/,千吨,),甲,乙,丙,丁,A,160,130,220,170,B,140,130,190,150,C,190,200,230,/,模型求解,OBJECTIVE FUNCTION VALUE,1)24400.00,VARIABLE VALUE REDUCED COST,X11 0.000000 30.000000,X12 50.000000 0.000000,X13 0.000000 50.000000,X14 0.000000 20.000000,X21 0.000000 10.000000,X22,50.000000,0.000000,X23 0.000000 20.000000,X24,10.000000,0.000000,X31,40.000000,0.000000,X32 0.000000 10.000000,X33,10.000000,0.000000,利润,=,总收入,-,其它费用,-,引水管理费,=144000-72000-24400=47600,（元）,A(50),B(,60,),C(,50,),甲(30;,50),乙(70;,70),丙(10;,20),丁(10;,40),50,50,40,10,10,引水管理费,24400(,元,),丁的蛙泳成绩退步到,115”2,；,戊的自由泳成绩进步到,57”5,组成接力队的方案是否应该调整,？,如何选拔队员组成,4,100,米混合泳接力队,?,甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,5,名候选人的,百米成绩,穷举法,：,组成接力队的方案共有,5!=120,种,。,0-1,规划分配问题：混合泳接力队的选拔,目标函数,若选择队员,i,参加泳姿,j,的比赛，记,x,ij,=1,否则记,x,ij,=0,c,ij,(,秒,),队员,i,第,j,种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,c,ij,i,=1,i,=2,i,=3,i,=4,i,=5,j,=1,66.8,57.2,78,70,67.4,j,=2,75.6,66,67.8,74.2,71,j,=3,87,66.4,84.6,69.6,83.8,j,=4,58.6,53,59.4,57.2,62.4,每种泳姿有且只有,1,人,0-1,规划模型,模型求解,最优解：,x,14,=,x,21,=,x,32,=,x,43,=1,其它变量为,0;,成绩为,253.2,(,秒,),=413”2,MIN 66.8x11+75.6x12+87x13+58.6x14,+,+67.4x51+71 x52+83.8x53+62.4x54,SUBJECT TO,x11+x12+x13+x14=1,x41+x42+x43+x44=1,x11+x21+x31+x41+x51=1,x14+x24+x34+x44+x54=1,END,INT 20,输入,LINDO,求解,甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,甲,自由泳、乙,蝶泳、丙,仰泳、丁,蛙泳,.,丁蛙泳,c,43,=,69.6,75.2,，,戊自由泳,c,54,=,62.4,57.5,方案是否调整？,敏感性分析？,乙,蝶泳、丙,仰泳、丁,蛙泳、戊,自由泳,IP,规划一般没有与,LP,规划相类似的理论，,LINDO,输出的敏感性分析结果通常是没有意义的。,最优解：,x,21,=,x,32,=,x,43,=,x,51,=1,成绩为,417”7,c,43,c,54,的新数据重新输入模型，用,LINDO,求解,指派,(,Assignment,),问题,：,每项任务有且只有一人承担，每人只能承担一项,，效益不同，怎样分派使总效益最大,.,讨论,甲,自由泳、乙,蝶泳、丙,仰泳、丁,蛙泳,.,原,方案,为了选修课程门数最少，应学习哪些课程？,多目标规划：选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,课号,课名,学分,所属类别,先修课要求,1,微积分,5,数学,2,线性代数,4,数学,3,最优化方法,4,数学；运筹学,微积分；线性代数,4,数据结构,3,数学；计算机,计算机编程,5,应用统计,4,数学；运筹学,微积分；线性代数,6,计算机模拟,3,计算机；运筹学,计算机编程,7,计算机编程,2,计算机,8,预测理论,2,运筹学,应用统计,9,数学实验,3,运筹学；计算机,微积分；线性代数,选修课程最少，且学分尽量多，应学习哪些课程？,0-1,规划模型,决策变量,目标函数,x,i,=1,选修课号,i,的课程（,x,i,=0,不选）,选修课程总数最少,约束条件,最少,2,门数学课，,3,门运筹学课，,2,门计算机课。,课号,课名,所属类别,1,微积分,数学,2,线性代数,数学,3,最优化方法,数学；运筹学,4,数据结构,数学；计算机,5,应用统计,数学；运筹学,6,计算机模拟,计算机；运筹学,7,计算机编程,计算机,8,预测理论,运筹学,9,数学实验,运筹学；计算机,先修课程要求,最优解：,x,1,=,x,2,=,x,3,=,x,6,=,x,7,=,x,9,=1,其它为,0,；,6,门课程，总学分,21,0-1,规划模型,约束条件,x,3,=1必有,x,1,=,x,2,=1,模型求解（,LINDO,）,课号,课名,先修课要求,1,微积分,2,线性代数,3,最优化方法,微积分；线性代数,4,数据结构,计算机编程,5,应用统计,微积分；线性代数,6,计算机模拟,计算机编程,7,计算机编程,8,预测理论,应用统计,9,数学实验,微积分；线性代数,学分最多,多目标优化的处理方法,：,化成单目标优化。,两目标,(,多目标,),规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以,学分最多为目标，不管课程多少。,以,课程最少,为目标，不管学分多少。,最优解如上，,6,门课程，总学分,21,。,最优解显然是选修所有,9,门课程,。,多目标规划,在,课程最少的前提下,以,学分最多为目标。,最优解：,x,1,=,x,2,=,x,3,=,x,5,=,x,7,=,x,9,=1,其它为,0,；,总学分由,21,增至,22,。,注意：最优解不唯一！,课号,课名,学分,1,微积分,5,2,线性代数,4,3,最优化方法,4,4,数据结构,3,5,应用统计,4,6,计算机模拟,3,7,计算机编程,2,8,预测理论,2,9,数学实验,3,LINDO,无法告诉优化问题的解是否唯一。,可将,x,9,=1,易为,x,6,=1,增加约束 ，,以学分最多为目标求解。,多目标规划,对学分数和课程数加权形成一个目标，如三七开。,最优解：,x,1,=,x,2,=,x,3,=,x,4,=,x,5,=,x,6,=,x,7,=,x,9,=1,，,其它为,0,；,总学分,28,。,课号,课名,学分,1,微积分,5,2,线性代数,4,3,最优化方法,4,4,数据结构,3,5,应用统计,4,6,计算机模拟,3,7,计算机编程,2,8,预测理论,2,9,数学实验,3,讨论与思考,最优解,与,1,=0,，,2,=1,的结果相同,学分最多,多目标规划,最优解,与,1,=1,，,2,=0,的结果相同,课程最少,实验,见,数学建模,实验指导,_02_Lindo,求解线性规划问题,.doc,。,