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