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

《《线性规划模型》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0-1线性规划模型在实际优化问题中存在一类所谓的分派问题,其含义如下:有若干项任务,每项任务必须有一人且只能有一人承担,每人也只能承担其中一项,不同人员承担不同任务的收益(或成本)不同.优化目标是:怎样分派各项任务使总收益最大(或总成本最小).本节通过若干个实际的分派问题,说明如何建立这类优化问题的数学模型,并用Matlab求出最优解及对应的目标函数最优值,同时对结果作一些分析.A混合接力队的最优组合问题•问题:某学院准备从5名游泳队员中选择4人组成学院的接力队,参加校运动会的4100混合泳接力赛.5名队员b1,…,b5的4种泳姿(蝶,仰,蛙,自由)a1,…,a4的百米平均成绩cij,

2、i=1,…,5;j=1,…,4如下表所示.应如何选择4人组成最优的接力队?cij(秒)a1a2a3a4a5b166.857.2787067.4b275.66667.874.271b38766.484.669.683.8b458.65359.457.262.4问题分析要求从5名队员选择4人,每人一种泳姿且4人泳姿各不相同,使接力队成绩最好.容易想到的办法是穷举法,组成接力队的方案共5!=120种,逐一计算并作比较即可找出最优方案.显然,这不是解决这类问题的有效办法,随着问题规模变大,穷举法的计算量将是无法接受的.一个好的办法是:用0-1变量表示一个队员是否入选接力队,从而建立这个问题的0-

3、1规划模型,再借助数学软件求解.建立0-1线性规划模型引入0-1变量xij,若队员bj参加泳姿ai的比赛,记xij=1,否则记xij=0.根据组成接力队的要求,应满足两个约束条件:①每人至多入选4种泳姿之一,应有j=14xij1,i=1,…,5②每种泳姿必须有一人入选i=15xij=1,j=1,…,4当队员bj入选泳姿ai时,其成绩为cijxij,于是接力队的成绩可表为z=j=14i=15cijxij,这就是问题的目标函数.所以,混合接力队的最优组合问题的数学模型是下列0-1线性规划问题:Minz=j=14i=15cijxijs.t.j=14xij1,i=1,…,5i

4、=15xij=1,j=1,…,4xij{0,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线性规划:Minz=cTxs.t.Axb,Aeqx=beqx=0或1其中,约束条件除若干不等式Axb外,还有若干等式Aeqx=beq,A,b;Aeq,beq分别代表二者的系数矩阵及右端向量.

5、若置A=[],b=[],则不等式全缺省;若置Aeq=[],beq=[],则等式全缺省.函数linprog(f,A,b,Aeq,beq)使用方法首先,(必要的话)改变z中所有系数的符号把”Maxz”化为”Minz”;把””化为””.其次,输入具体的f(=c),A,b,Aeq,beq.最后执行行命令:[xz]=bintprog(f,A,b,Aeq,beq)则输出的x即为最优解;z(或-z)即为目标函数最小(大)值.混合接力队优化组合问题求解解:执行下列Matlab行命令:f=[66.875.68758.657.26666.4537867.884.659.47074.269.657.267

6、.47183.862.4];A=[11110000000000000000;00001111000000000000;00000000111100000000;00000000000011110000;00000000000000001111]b=[11111];beq=[1111];Aeq=[10001000100010001000;01000100010001000100;00100010001000100010;00010001000100010001];[xz]=bintprog(f,A,b,Aeq,beq)由屏幕最后显示结果得:最优解x14=x21=x32=x43=1,其它x

7、ij=0目标函数最小值z=253.2"=413"2即应该选派b1,b2,b3,b4四人组成接力队参加混合泳接力比赛,并分别游自由泳,蝶泳,仰泳,和蛙泳.他们的预期成绩(是一切可能组合中最好成绩)为:4分13秒2.思考题1:在校运会报名时,发现队员b4的蛙泳成绩有较大退步,只有115"2;而队员b5训练努力自由泳有明显进步,达到57"5.问组成接力队的方案应作如何调整?B选课策略问题问题:某大学规定,运筹学专业学生毕业时必须至少修