单位文秘网 2021-07-20 08:09:38 点击: 次
思想的简洁性、深刻性、数据结构形式优美性、逻辑推理的严密性,以至于学生通过接受这种严格的数学教育培养出来的数学审美意识影响到他们的日后工作,将这种数学原理的严谨性代入到社会中,提供精益求精的质量上乘的产品。
1 线性规划以及一般形式、规范形式和标准形式的线性规划
在普遍流行的线性规划[1,2]课本中对于线性规划模型不同形式的定义有一定的差别,在本文中为了避免这种差别带来的叙述上的困难,特定义如下:
线性规划问题的一般形式为
minz=c1x1+c2x2+…+cnxn
s.t.ai1x1+ai2x2+…ainxn=bi;i=1,2,…,pai1x1+ai2x2+…ainxn?叟bi;i=p+1,…,mxj?叟0;j=1,2,…,qxj无限制;j=q+1,…,n(1)
其中xj、j=1,2,…,n为待定的决策变量;c=(c1,c2,…,cn)T为价值向量,cj、j=1,2,…,n为价值系数;b=(b1,b2,…,bm)T为右端向量。
线性规划问题的规范形式为:
minz=c1x1+c2x2+…+cnxn
s.t.ai1x1+ai2x2+…ainxn?叟bi;i=1,2,…,mxj?叟0;j=1,2,…,n(2)
标准形式:
minz=c1x1+c2x2+…+cnxn
s.t.ai1x1+ai2x2+…ainxn?叟bi;i=1,2,…,mxj?叟0;j=1,2,…,n(3)
可以证明,这三者之间可以互相的转换,而且不会破坏解的性质。也就是可以得到所有的线性规划的模型都可以等价转换为(3)式的形式。
2 线性规划的一些重要理论
由上述的理论可知,只要求出标准形式的线性规划问题的解,即可得到所有形式的线性规划问题的解。所以本文以下的讨论都是针对于标准形式的线性规划问题的讨论。
考虑矩阵形式的线性问题的标准形式:
mincTx
s.t.Ax=bx?叟0
其中
c=(c1,c2,…,cn)T为价值向量,b=(b1,b2,…,bm)T为右端向量。
A=a11 … a1n■ ■ ■am1 … amn为系数矩阵。
定义3.1 可行解:满足所有约束条件的向量x=(x1,x2,…xn)T。
定义3.2 可行域:所有的可行解的全体D={x ■ Ax=b,x?叟0}。
定义3.3 最优解:在可行域中目标函数值最小的可行解,记做x*。
定义3.4 最优值:最优解的目标函数值v=cTx*。
定义3.5:设B是秩为m的约束矩阵A的一个m阶满秩子方阵,则称B为一个基(或基阵);B中m个线性无关的列向量称为基向量,变量x中与之对应的m个分量称为基变量,其余的变量为非基变量,令所有的非基变量取值为0,得到的解x=B-1b0称为相应于B的基本解。当B-1b?叟0则称基本解为基本可行解,这时对应的基阵B为可行基。
由高等代数的知识可知所有的线性规划解的情况为:无解或不可行、无界,有最优解。
定理3.1线性规划问题的可行域D={x ■ Ax=b,x?叟0}是凸集。
定理3.2线性规划问题的基本可行解对应于可行域的顶点。
定理3.3一个标准的线性规划问题如果有有限的最优值,则一定存在一个基本可行解是最优解。
基于以上理论,1947年G.B.Dantzig提出了著名的单纯形方法,直到现在仍是解决线性规划问题的重要理论,后来发展的一系列解法也都是在此方法的基础上拓展的,在此本文只叙述一下单纯形方法的原理以及算法步骤,具体的证明可在任何的一本线性规划课本中找到。单纯形方法的思想为先找到一个基本可行解,判别它是不是最优解,如果不是再找到另外的更好的基本可行解继续判断,直到找到最优或者判断无解。
单纯型方法的算法步骤:
①找一个初始可行基B;
②求出典式和检验数ξ;
③求ξk=max{ξj ■ j=1,2,…,n};
④如果ξk?燮0,停止,
已找到最优解x=xBxN=b0及最优值z=c■■b;
⑤如果Ak?燮0,停止,原问题无界;
⑥求θ=min{bi/aik ■ aik>0,i=1,2,…,m}=br/ark;
⑦以Ak替代A■得到一个新的基,转②。
3 算法的实现
部分学者认为,对于一个有效的算法,算法的理论是重点,而具体的实现只是一个重复的过程,不再是一个重点,但笔者认为,算法的理论基础以及算法的实现是同等重要的问题,诚然算法的理论是算法实现的源泉和基础,但是算法的实现更能使算法的理论清晰、明了。同时达到学以致用的目的,尤其对于应用型大学的建设更是必要的一步。
具体到本文,单纯形方法有两类计算的方式,一类是按照算法的步骤进行矩阵形式的迭代,另外一类也是比较简单但操作起来比较繁琐的单纯形表法。可以进行证明,[2]对单纯形表进行初等行变换也是一种有效的单纯形迭代法,但是由于数据较多,学生在计算的时候稍有不慎就会算错,而且进行检查的时候时间上的代价也是巨大的。因此在平时的课堂练习时,只是进行低维度的练习,没有进行高维数大数据的处理,但是借助于先进的计算机技术,可以轻松的达到这一目的。况且计算机技术的应用在当今的高校教育中已经不能算作一门先进的领先的技术,由于计算机技术的普及它更应该成为高校教育中的一个必备环节。文献[3]中提到,虽然单纯形方法的算法实现复杂,解得情况千差万别,但幸好解线性规划问题的商用软件包已经非常普及,大家可在计算机上直接的调用。笔者认为可惜的不是商用软件包非常普及,而是在商用软件包非常普及的前提下,高校中很多学生对于这些商用软件包都不熟悉,就拿去年和今年笔者所教授的两个班级的学生来说,总共135人,只有1个学生课下的时候来向笔者请教这方面的问题,实在是令人惋惜。下面笔者就1个简单的线性规划问题在matlab[3]软件上的实现来说明怎么运用计算机软件辅助线性规划的教学。
考虑问题
maxz=3x1+4x2+2x3
s.t.x1+x2+x3+x4?燮303x1+6x2+x3-2x4?燮0x2?叟4xj?叟0,j=1,2,…,4
首先,把这个问题转换为标准型
minz=-3x1-4x2-2x3
s.t.x1+x2+x3+x4+x5=303x1+6x2+x3-2x4+x6=0x2-x7=4xj?叟0,j=1,2,…,7
然后按照单纯性表格的方法列出初始单纯形表,然后再运用初等行变换进行变换直到找到最优解或者判断无解,可知这是涉及到一个四行八列的矩阵表格,计算起来是比较复杂的,本文用matlab进行简单的可视即可见的方法一步步进行计算,计算符号如下:
a=[3 4 2 0 0 0 0 0 0;0 0 0 0 0 0 0 -1 0;1 1 1 1 1 0 0 0 30;3 6 1 -2 0 1 0 0 0;0 1 0 0 0 0 -1 1 4]
a(2,:)=a(2,:)+a(5,:)
a(4,:)=a(4,:)/6
a(2,:)=a(2,:)+a(4,:)*(-1)
a(1,:)=a(1,:)+a(4,:)*(-4)
a(3,:)=a(3,:)+a(4,:)*(-1)
a(5,:)=a(5,:)+a(4,:)*(-1)
a(5,:)=a(5,:)*3
a(1,:)=a(1,:)+a(5,:)*(-4/3)
a(2,:)=a(2,:)+a(5,:)*(-1/3)
a(3,:)=a(3,:)+a(5,:)*(-4/3)
a(4,:)=a(4,:)+a(5,:)*(1/3)
a(2,:)=[]
a(:,8)=[]
a(2,:)=a(2,:)*2/5
a(1,:)=a(1,:)+a(2,:)*(-3)
a(4,:)=a(4,:)+a(2,:)*(3/2)
a(2,:)=a(2,:)*5/3
a(1,:)=a(1,:)+a(2,:)*(-1/5)
a(4,:)=a(4,:)+a(2,:)*(-2/5)
可以轻松得到最后的结果,而且只要明白里面的逻辑关系,检查的时候也是非常方便的,可以得到最优解为
x=[0,4,■,■]
最优值为■。
但是同时也可以进行matlab自带的线性规划工具箱进行求解,自带函数为
[x,feval,exitflag,output,lambda]=linprog(c,a,b,aa,bb,l,u)
c=[-3 -4 -2 0]
a=[1 1 1 1;3 6 1 -2]
b=[30 0]
aa=[]
bb=[]
l=[0 4 0 0]
u=[]
也可以得到相同的结果,只需要提供给软件相应的参数即可,这些参数都是线性规划问题的本身属性,熟知他们才能解决好这类问题。
4 总结
①线性规划是数学模型中的一类重要模型,现实当中的很多问题都可以转换成线性规划问题,进行相应的求解可以对生产活动提出有益的指导。②线性规划课程的教学中,可以在理论课的基础上加大对实践课的重视,加大对于这些计算软件的学习,包括matlab,c语言等。③现今的高校教学中,如何调动学生的积极性,很好地完成师生互动是一个大难题,可以多增加实践课,让学生自己去进行实践。增加他们的学习兴趣。摆脱传统的满堂灌。④高校的课堂教学中,应不能仅满足与讲解知识的层面,而是在讲解知识的基础上,为学生提供学习的方法和思路,即学习如何去学习,正所谓兴趣是最好的老师,适当的增加实践课程能在一定程度上促进学生的学习兴趣,达到抛砖引玉的作用。
参考文献:
[1]胡运权.运筹学基础及应用[M].五版.北京:高等教育出版社,2010.
[2]韩中庚.数学建模方法及其应用[M].北京:高等教育出版社,2009.
[3]李工农,阮晓青.经济预测与决策及其Matlab实现[M].北京:清华大学出版社,2007.
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-204-67508-1.html
上一篇:战争背后的科技智囊团
下一篇:数学规划在测绘工作中的应用
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用