《线性规划模型》PPT课件.ppt

0-1线性规划模型,在实际优化问题中存在一类所谓的分派问题,其含义如下:有若干项任务,每项任务必须有一人且只能有一人承担,每人也只能承担其中一项,不同人员承担不同任务的收益(或成本)不同.优化目标是:怎样分派各项任务使总收益最大(或总成本最小). 本节通过若干个实际的分派问题,说明如何建立这类优化问题的数学模型,并用Matlab求出最优解及对应的目标函数最优值,同时对结果作一些分析.,A 混合接力队的最优组合问题, 问题:某学院准备从5名游泳队员中选择4 人组成学院的接力队,参加校运动会的4 100混合泳接力赛.5名队员b1,b5的4种 泳姿(蝶,仰,蛙,自由)a1,a4的百米平 均成绩cij,i=1,5;j=1,4如下表所示. 应如何选择4人组成最优的接力队?,问题分析,要求从5名队员选择4人,每人一种泳姿且4人泳姿各不相同,使接力队成绩最好. 容易想到的办法是穷举法,组成接力队的方案共5!=120种,逐一计算并作比较即可找出最优方案.显然,这不是解决这类问题的有效办法,随着问题规模变大,穷举法的计算量将是无法接受的. 一个好的办法是:用0-1变量表示一个队员是否入选接力队,从而建立这个问题的0-1规划模型,再借助数学软件求解.,建立0-1线性规划模型,引入0-1变量xij,若队员bj参加泳姿ai的比赛,记xij=1,否则记xij=0.根据组成接力队的要求,应满足两个约束条件: 每人至多入选4种泳姿之一,应有 j=14xij1,i=1,5 每种泳姿必须有一人入选 i=15xij=1,j=1,4 当队员bj入选泳姿ai时,其成绩为cijxij,于是接力队的成绩可表为z= j=14i=15cijxij,这就是问题的目标函数.,所以,混合接力队的最优组合问题的数学 模型是下列0-1线性规划问题: Min z=j=14i=15cijxij s.t. j=14xij1,i=1,5 i=15xij=1,j=1,4 xij0,1,i=1,5,j=1,4 这类线性规划问题的特点是决策变量只取值1或0,故称为0-1线性规划问题. Matlab的函数bintprog专门用来求解0-1线性规划,下面介绍此函数的使用范围及使用方法,其理论基础从略.,函数bintprog(f,A,b,Aeq,beq)使用范围,函数linprog(f,A,b,Aeq,beq)用来求解一般的标准型0-1线性规划: Min z=cTx s.t. Axb, Aeqx=beq x=0或1 其中,约束条件除若干不等式Axb外,还有若干等式Aeqx=beq,A,b;Aeq,beq分别代表二者的系数矩阵及右端向量.若置A=,b=,则不等式全缺省;若置 Aeq=,beq=,则等式全缺省.,函数linprog(f,A,b,Aeq,beq)使用方法,首先,(必要的话)改变z中所有系数的符号把”Max z”化为”Min z”;把”化为”. 其次,输入具体的f(=c),A,b,Aeq,beq. 最后执行行命令: x z=bintprog(f,A,b,Aeq,beq) 则输出的x即为最优解;z(或-z)即为目标函数最小(大)值.,混合接力队优化组合问题求解,解:执行下列Matlab行命令: f=66.8 75.6 87 58.6 57.2 66 66.4 53 78 67.8 84.6 59.4 70 74.2 69.6 57.2 67.4 71 83.8 62.4; A=1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 b=1 1 1 1 1;beq=1 1 1 1; Aeq=1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0; 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;,0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0; 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1; x z=bintprog(f,A,b,Aeq,beq) 由屏幕最后显示结果得: 最优解 x14=x21=x32=x43=1,其它xij=0 目标函数最小值 z=253.2“=413“2 即应该选派b1,b2,b3,b4四人组成接力队参加混合泳接力比赛,并分别游自由泳,蝶泳,仰泳,和蛙泳.他们的预期成绩(是一切可能组合中最好成绩)为:4分13秒2.,思考题1: 在校运会报名时,发现队员b4的蛙泳成绩有较大退步,只有115“2;而队员b5训练努力自由泳有明显进步,达到57“5. 问组成接力队的方案应作如何调整?,B 选课策略问题,问题:某大学规定,运筹学专业学生毕业时必须至少修过2门数学课,3门运筹学课和2门计算机课.这些课的编号及信息如下表所示. 给出毕业时选课门数最少的一个方案. 给出毕业时选课门数少而学分多的一个方案.,选课策略问题的数学模型,用xi=1(0)表示选修(不选)按上表中编号顺序的9门课程的第i门课. 问题决策目标为选修课程门数最少,即 Min z=j=19xi. 其约束条件包括 首先,每人最少要选2门数学课,3门运筹学课和2门计算机课,按表中课程类别划分可将此约束表示为 x1+x2+x3+x4+x52 x3+x5+x6+x8+x93 x4+x6+x7+x92 ,其次,某些课有先修课的要求,例如,数据结构的先修课是计算机编程,这意味着x4=1蕴涵x7=1,这个条件可表示为x4x7或 x4-x70. 同理,最优化方法的先修课是微积分和线性代数的条件可表示为x3x1,x3x2,此二式可合并为一个不等式 2x3-x1-x20. 另外有 2x5-x1-x20 x6-x70 x8-x5 0 2x9-x1-x20 ,所以,选课策略问题的数学模型就是:只取值0或1的9个决策变量x1,x9,满足约束条件-,并使目标函数取最小值的0-1线性规划模型.,选课策略问题数学模型求解,首先,把约束条件-标准化为 -x1-x2-x3-x4-x5-2 -x3 -x5-x6 -x8-x9-3 -x4 -x6-x7 -x9-2 其次,输入数据 A=-1 -1 -1 -1 -1 0 0 0 0;0 0 -1 0 -1 -1 0 -1 -1;0 0 0 -1 0 -1 -1 0 -1;-1 -1 2 0 0 0 0 0 0; 0 0 0 1 0 0 -1 0 0;-1 -1 0 0 2 0 0 0 0; 0 0 0 0 0 1 -1 0 0;0 0 0 0 -1 0 0 1 0; -1 -1 0 0 0 0 0 0 2; b=-2 -3 -2 0 0 0 0 0 0,Aeq=;beq=; f=1 1 1 1 1 1 1 1 1;,核对输入数据正确之后,键入下列行命令: x z=bintprog(f,A,b,Aeq,beq) 由屏幕最后显示结果得: 最优解 x1=x2=x5=x6=x7=x8=1, x3=x4=x9=0 目标函数最小值 z=6 即应该选修微积分,线性代数,应用统计,计算机模拟,计算机编程,预测理论等6门课,最小选课门数是6.,思考题2: 在选课策略问题中,如果一个学生因对最优化方法特有兴趣而把此课定为必选,仍然希望毕业时所学课程门数尽可能少,试给出他(她)的一个选课方案.,关于解的唯一性,一般来说,线性规划问题,包括0-1线性规划问题的解都不是唯一的,例如对选课策略问题,我们先求出一个最优解x=1,1,0,0,1,1,1,1,0; 后又在思考题5-5中求得另外一个最优解 x=1,1,1,0,0 1,1,0,1,它们对应的最优目标函数值相等(=6).说明对应选课策略问题的0-1线性规划至少有两个的解,说明它的解不唯一.,我们可以证明 此问题恰有两个解. 证:如果我们再把x4=1作为约束条件(表示为 -x4-1),求得最优解x=1,1,1,1,1 1,1,0,0,但对应最优目标值已不是6,而是7.说明,此解与上面二解不同,不是选课策略问题的最优解.再注意观察:上面两个最优解恰有一个分量,第4分量,同时为0,由此可见(没有第4分量为1的最优解),选课策略问题只有上述两个解.,思考题3: 在选课策略问题中如果一个学生在满足学校有关选课规定条件下,希望毕业时所学课程获得的学分数尽可能多,试给出他(她)的一个选课方案.,选课策略问题的数学模型,选课策略问题的数学模型与选课策略问题的数学模型的约束条件完全一样;只是目标函数不同.要求”选课门数少而学分多”意味着同时要求两个决策目标: Min z=j=19xi Max w=5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9 具有多个决策目标的规划称为多目标规划,前面讲的只有一个目标的规划称为单目标规划.所以,选课策略问题的数学模型是满足约束条件-并有双目标 Min z和 Max w 的0-1线性规划.,双目标规划的一种处理方法,把双目标归结为一个单目标,即令y=z+(1-)w,为闭区间0,1中任一数,并取决策目标为(Max w=Min(-w) Min y=z-(1-)w 值的大小体现决策者对每个目标的重视程度,例如,某同学觉得学分数和课程数是三七开,故把取为0.7,决策目标为 Min y=0.7z-0.3w =-0.1(8x1+5x2+5x3+2x4+5x5+2x6-x7-x8+2x9),用Matlab函数bintprog求解这个问题时,与前面求解选课策略问题时的 A,b,Aeq,beq数据完全一样,只需把f改为 f=-