导航菜单

基于matlab的《线性规划》教学研究

李林汉 LI Lin-han;韩祝华 HAN Zhu-hua

(河北金融学院基础部,保定 071051)

摘要: 线性规划模型是数学建模过程的重要模型,应用广泛,因此在经济类的高校中都开设了相应的课程,各类高校对于线性规划或运筹学的课程也都比较重视。本文借助matlab计算语言工具的优越性,给出不同形式下的线性规划模型的求解过程,并给出关于计算机软件在线性规划教学过程中的有益建议。

教育期刊网 http://www.jyqkw.com
关键词 : matlab;线性规划;数学建模

中图分类号:G420 文献标识码:A 文章编号:1006-4311(2015)23-0195-03

课题项目:河北金融学院应用数学优秀基础学科资助项目。

作者简介:李林汉(1986-),男,河北邯郸人,硕士,助教,研究方向为数值计算与最优化;韩祝华(1980-),女,河北冀州人,硕士,助教,研究方向为数理统计。

0 引言

线性规划模型是运筹学以及数学建模过程中的重要模型,应用极其广泛,作用也越来越被人们重视。随着计算机软件的迅猛发展,使线性规划模型在经济、军事和科学研究各方面都得到了急速的应用。这就要求教学过程中要求学生不仅要了解单纯形方法的原理,还要掌握并实现这一方法。而普遍流行的运筹学教材上例题都是低阶维数,仅仅让学生理解了原理,而并没有给出高阶的例子,或者大数据的例子,使得学生认为计算机语言对于线性规划的学习没有帮助。再一个方面学生的自主学习能力较弱,本来引入计算机语言能够使得单纯形方法的运算过程简化,但是由于学生没有自主学习的能力,那么学生就会认为还需要学习一种更加复杂的理论知识,反而会误认为这是一种负担。

随着计算机软硬件水平的日益更新,正在对人们的日常行为方式进行着巨大的变革,那么作为大学生更加应该把这种便利引入到日常的学习中,因此在教学中可以借用计算机,网络等现代技术使得线性规划以及线性代数这种的课程原理的讲解更加的完整清晰化,经典化。对于计算过程的实现,完全交给计算机实现。使学生领略到单纯形思想的简洁性、深刻性、数据结构形式优美性、逻辑推理的严密性,以至于学生通过接受这种严格的数学教育培养出来的数学审美意识影响到他们的日后工作,将这种数学原理的严谨性代入到社会中,提供精益求精的质量上乘的产品。

1 线性规划以及一般形式、规范形式和标准形式的线性规划

在普遍流行的线性规划[1,2]课本中对于线性规划模型不同形式的定义有一定的差别,在本文中为了避免这种差别带来的叙述上的困难,特定义如下:

线性规划问题的一般形式为

可以证明,这三者之间可以互相的转换,而且不会破坏解的性质。也就是可以得到所有的线性规划的模型都可以等价转换为(3)式的形式。

2 线性规划的一些重要理论

由上述的理论可知,只要求出标准形式的线性规划问题的解,即可得到所有形式的线性规划问题的解。所以本文以下的讨论都是针对于标准形式的线性规划问题的讨论。

考虑矩阵形式的线性问题的标准形式:

由高等代数的知识可知所有的线性规划解的情况为:无解或不可行、无界,有最优解。

定理3.1线性规划问题的可行域是凸集。

定理3.2线性规划问题的基本可行解对应于可行域的顶点。

定理3.3一个标准的线性规划问题如果有有限的最优值,则一定存在一个基本可行解是最优解。

基于以上理论,1947年G.B.Dantzig提出了著名的单纯形方法,直到现在仍是解决线性规划问题的重要理论,后来发展的一系列解法也都是在此方法的基础上拓展的,在此本文只叙述一下单纯形方法的原理以及算法步骤,具体的证明可在任何的一本线性规划课本中找到。单纯形方法的思想为先找到一个基本可行解,判别它是不是最优解,如果不是再找到另外的更好的基本可行解继续判断,直到找到最优或者判断无解。

单纯型方法的算法步骤:

3 算法的实现

部分学者认为,对于一个有效的算法,算法的理论是重点,而具体的实现只是一个重复的过程,不再是一个重点,但笔者认为,算法的理论基础以及算法的实现是同等重要的问题,诚然算法的理论是算法实现的源泉和基础,但是算法的实现更能使算法的理论清晰、明了。同时达到学以致用的目的,尤其对于应用型大学的建设更是必要的一步。

具体到本文,单纯形方法有两类计算的方式,一类是按照算法的步骤进行矩阵形式的迭代,另外一类也是比较简单但操作起来比较繁琐的单纯形表法。可以进行证明,[2]对单纯形表进行初等行变换也是一种有效的单纯形迭代法,但是由于数据较多,学生在计算的时候稍有不慎就会算错,而且进行检查的时候时间上的代价也是巨大的。因此在平时的课堂练习时,只是进行低维度的练习,没有进行高维数大数据的处理,但是借助于先进的计算机技术,可以轻松的达到这一目的。况且计算机技术的应用在当今的高校教育中已经不能算作一门先进的领先的技术,由于计算机技术的普及它更应该成为高校教育中的一个必备环节。文献[3]中提到,虽然单纯形方法的算法实现复杂,解得情况千差万别,但幸好解线性规划问题的商用软件包已经非常普及,大家可在计算机上直接的调用。笔者认为可惜的不是商用软件包非常普及,而是在商用软件包非常普及的前提下,高校中很多学生对于这些商用软件包都不熟悉,就拿去年和今年笔者所教授的两个班级的学生来说,总共135人,只有1个学生课下的时候来向笔者请教这方面的问题,实在是令人惋惜。下面笔者就1个简单的线性规划问题在matlab[3]软件上的实现来说明怎么运用计算机软件辅助线性规划的教学。

考虑问题

然后按照单纯性表格的方法列出初始单纯形表,然后再运用初等行变换进行变换直到找到最优解或者判断无解,可知这是涉及到一个四行八列的矩阵表格,计算起来是比较复杂的,本文用matlab进行简单的可视即可见的方法一步步进行计算,计算符号如下:

可以轻松得到最后的结果,而且只要明白里面的逻辑关系,检查的时候也是非常方便的,可以得到最优解为

但是同时也可以进行matlab自带的线性规划工具箱进行求解,自带函数为

也可以得到相同的结果,只需要提供给软件相应的参数即可,这些参数都是线性规划问题的本身属性,熟知他们才能解决好这类问题。

4 总结

①线性规划是数学模型中的一类重要模型,现实当中的很多问题都可以转换成线性规划问题,进行相应的求解可以对生产活动提出有益的指导。②线性规划课程的教学中,可以在理论课的基础上加大对实践课的重视,加大对于这些计算软件的学习,包括matlab,c语言等。③现今的高校教学中,如何调动学生的积极性,很好地完成师生互动是一个大难题,可以多增加实践课,让学生自己去进行实践。增加他们的学习兴趣。摆脱传统的满堂灌。④高校的课堂教学中,应不能仅满足与讲解知识的层面,而是在讲解知识的基础上,为学生提供学习的方法和思路,即学习如何去学习,正所谓兴趣是最好的老师,适当的增加实践课程能在一定程度上促进学生的学习兴趣,达到抛砖引玉的作用。

教育期刊网 http://www.jyqkw.com
参考文献:

[1]胡运权.运筹学基础及应用[M].五版.北京:高等教育出版社,2010.

[2]韩中庚.数学建模方法及其应用[M].北京:高等教育出版社,2009.

[3]李工农,阮晓青.经济预测与决策及其Matlab实现[M].北京:清华大学出版社,2007.

下载文本