论文发表、论文指导
周一至周五
9：00&22：00
用矩阵法求解线性规划问题
&&&&&&本期共收录文章20篇
　　摘要：线性规划作为运筹学的一个重要分支，自1947年丹捷格提出了一般线性规划问题的求解方法即单纯形法之后，线性规划在理论上日益成熟，在使用中日益广泛与深入，至今单纯形法仍是求解线性规划问题最常用、最有效的方法之一。单纯形法的基本步骤是换基迭代,求解过程实质是对线性规划问题所确定的某个特定矩阵施行初等变换以达到某种形式的过程。因此本文利用线性方程组的同解理论，通过引进人工变量等手段，化一般线性规划为标准线性规划，建立线性方程组，写出其系数矩阵，对系数矩阵进行一系列的最优化过程，得到最优矩阵从而求出最优解。 中国论文网 /1/view-238237.htm　　关键词：线性规划 单纯形法 矩阵 求解 　　 现代科学技术迅猛发展的今天对数学问题的研究提出了更新更高的要求，而线性规划问题在数学领域及科学技术中应用广泛，所以对线性规划问题的求解法要求也越来越高。教材中介绍的主要是用单纯形法求解，由于线性约束条件是由线性方程组构成的，而方程组的问题可以转化为矩阵的形式。所以本文结合自己的学习，通过认真分析查阅资料，整理出了用矩阵法求解线性规划问题的步骤，以期对线性规划问题的研究有一定的参考价值。 　　 1、线性规划问题基本知识简介 　　 1.1线形规划问题的标准形式 　　我们考虑下列线性规划问题： 　　 　　约束条件为 　　 　　其中，称为决策变量，变量表示决策方案，满足上述约束条件的决策变量的值称为线性规划问题的可行解，我们把使目标函数达到最大的可行解叫最优解，这个最大的值我们称为最优值；叫价值系数. 在解问题时若要求线性规划问题的极小值，即 　　 　　这时只需令 　　 　　即可将原问题转化为 　　 　　即可. 　　当约束条件为不等式时，有两种处理方式：当约束条件为“ ”的不等式时，可在不等式的左端加入非负松弛变量，将不等式变为等式；当约束条件为“”的不等式，可在不等式左端减去一个非负剩余变量（也可称松弛变量），把不等式变为等式约束. 　　1.2线性规划问题标准形式的矩阵形式 　　线性规划问题用矩阵描述时为： 　　其中： 　　―约束条件的维系数矩阵，一般 　　―资源向量； ―价值向量； ―决策变量向量 　　为便于使用矩阵法求解上述线性规划问题，我们构造如下初始矩阵 　　 　　这里是一个由约束方程的增广矩阵和价值系数组成的 　　矩阵，其中是约束条件的个数，是决策变量的个数.而问题中涉及的 表示的是矩阵秩，即 .问题的基变量可由矩阵中列向量的最大线性无关组的选取方式来确定。 　　1.3线性规划问题的最优解 　　(1)可行解 　　 线性规划问题： 　　 　　中，满足约束条件的 　　 　　称为线性规划问题的可行解，而使目标函数值达到最大的可行解称为该问题的最优解. 　　(2)基 　　设是约束方程组的维系数矩阵，其秩为,是矩阵中阶非奇子矩阵（）,则称是线性规划问题的一个基.这就是说，矩阵是由个线性独立的列向量组成,不失一般性，可设 　　 　　称为基向量，与基向量相应的变量 为基变量，否则称为非基变量. 为了进一步讨论线性规划问题的解，下面研究约束方程组(1-1) 的求解问题.假设该方程组系数矩阵的秩为，因 ，故它有无穷多个解，假设前个变量的系数列向量是线性独立的，这时(1-1)式可写成 　　 　　或 　　方程组(1-3)的一个基是 　　设 是对应于这个基的基变量 　　 　　现若令(1-3)式的非基变量 ，这时变量的个数等于线性方程的个数.用高斯消去法求出一个解 　　 　　该解的非零分量的数目不大于方程的个数 ，称为基解.由此可见，有一个基，就可以求出一个基解. 　　(3)基可行解 　　满足非负条件，的基解，称为基可行解. 　　(4)可行基 　　对应于基可行解的基称为可行基. 　　单纯形法的基本思想是用迭代法从初始基可行解出发，判断当前基可行解是否为最优解，如果是则求解结束，否则要进行换基，即将一个非基变量变为一个基变量（叫做入基），同时将一个基变量变为非基变量（叫做出基），换基的原则是换入使目标函数变化最大的,不断重复上述过程找到问题的最优解为止. 　　1.4用矩阵法求解线性规划问题的步骤 　　(1)确定初始基变量，求得初始基可行解. 　　 　　将矩阵第一列中 ，得到新的矩阵.重复(2)-(5)直到终止. 　　2、应用举例 　　例1.某工厂在计划期内要安排生产两种产品,已知生产单位产品需要设备1台时，原材料 4千克，生产单位产品需要设备2台时，原材料 4千克，且该工厂共有设备8台时，原材料 16千克，原材料12千克.该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多？ 　　解 设分别表示在计划期内产品的产量，则该问题可用数学模型表示为 　　第二步，比较价值系数，确定进基变量. 　　因为价值系数的大小对目标函数值的改变有影响，价值系数大的可以加快目标函数值的改变，故从所有价值系数中选择绝对值最大的正数如，确定该数在矩阵中的位置，然后把该列代表的决策变量 作为一个新的基变量取代前一个基变量中的一个变量.在本题中由于2＜3，所以此题中价值系数最大的正数为，它在中占第二列，于是就把 作为一个新的基变量. 　　第三步，依据最小比值原理,找到出基变量，进而求得基可行解. 　　将 所对的那一列的前三个正数分别去除最后列的对应元素，选出所得商中最小的正值并确定出其在中所占的行数，于是把该行所代表的基变量作为出基变量.通过计算可知 　　那么其对应的行所代表的基变量就作为出基变量被换出而成为非基变量.于是得到矩阵 如下： 　　将矩阵作一系列初等变换，将矩阵中第三行第二列处的值变为1，第二列的其他位置的值变为0，这样得到矩阵 　　 　　令代入约束条件就求得该可行基对应的可行解 　　 　　第四步，比较确定矩阵中的最后一行是否还有正数，有则重复二三步，直到最后一行所有元全为非正数为止.题中的最后一行中有正数=2，故重复上述二三步，因，且占中的第一行，故将作为新的基变量，作为非基变量，对作同的初等变换得到 　　从上面的例子我们可以看出，如果所给定的线性规划问题有现成的基，那么我们可以直接写出初始单纯形矩阵.如果所给定的线性规划问题没有现成的基，则可通过引入人工变量的方法得到一个人造基，从而构造一个辅助问题.然后利用例一中使用的单纯形法来求得辅助问题的最优解或判断辅助问题无最优解.此时原问题和辅助问题的解的情况相同.如果原问题有无最优解无法判定，且辅助问题的最优解中已不含人工变量可以去掉辅助问题的单纯形表中对于原问题来说是多余的行及多余的列.如果辅助问题的最优基中含有人工变量，这时若人工变量所对应的行中非人工变量的系数全为0，则可将此行去掉而使辅助问题的最优基中少一个人工变量.若人工变量所对应的行中某一非人工变量的系数不为0，则以此出发对单纯形表进行适当的变换进行换基.目的是迫使人工变量离基，经有限个步骤以后总可以使辅助问题的最优基中不再含有人工变量，从而得到原问题的初始单纯形表.以上所有的工作都可以用相应的单纯形矩阵代替单纯形表而对单纯形矩阵施行初等行变换达到预期的目的. 　　3、灵敏度分析 　　灵敏度分析也叫优化后分析，是研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程.灵敏度分析的主要内容包括研究目标函数的系数发生变化时对最优解的影响，约束方程右端系数发生变化时对最优解的影响以及约束方程组系数阵发生变化时对最优解的影响.针对上述情况，我们会作如下思考：如果上述问题中涉及的系数有一个或几个发生变化时，那么我们所求得的最优解又回随这些问题的变化而发生变化吗？或者说它们会发生怎么样的变化以及这些系数在哪个范围内变化时不会影响原问题的最优解或者说不会使问题的最优基发生变化呢？下面我将从资源数量变化和技术系数两方面的变化来讨论它们的变化对线性规划问题最优解和最优基的影响. 　　3.1资源数量变化的分析 　　3.2技术系数的变化 　　讨论技术系数的变化，下面我们以具体例子来说明 　　例4.分析在原计划中是否应该安排一种新产品.以例1为例，设该厂除了生产产品 外，现有一种新产品 ，已知生产产品每件需消耗原材料A,B各为6千克，3千克，使用设备2台时，每件可获利5元.问改厂是否生产该产品和生产多少？ 　　4、结束语 　　线性规划的求解问题在运筹学中中是最重要的知识点，且是贯穿运筹学各个章节的重要理论，在研究其他规划方面有非常重要的作用.本文通过对线性规划的矩阵求解法的描述加深了对单纯形法实质的理解，矩阵形式是表达最为简洁又便于理论推证的形式，单纯形法的矩阵描述也为研究修正单纯形法奠定了基础.灵敏度分析作为优化后分析对于线性规划的应用是非常重要的，但在考虑系数变化时一般每次只考虑一个，当多个系数同时变化时，就需要用参数线性规划进行处理，因此，可以把参数线性规划看作是灵敏度分析的扩展. 　　 　　参考文献： 　　[1]杨民助．运筹学[M]．西安：西安交通大学出版社，2000 　　[2]陶谦坎主编.运筹学应用案例[M]．北京：机械工业出版社，1993 　　[3]胡运权．运筹学习题集[M]．北京：清华大学出版社，1985 　　[4]林添华．线性规划的矩阵求解法[J]．龙岩师专学报，2003，6 　　
转载请注明来源。原文地址：
【xzbu】郑重声明：本网站资源、信息来源于网络，完全免费共享，仅供学习和研究使用，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除已转载的信息。
xzbu发布此信息目的在于传播更多信息，与本网站立场无关。xzbu不保证该信息（包括但不限于文字、数据及图表）准确性、真实性、完整性等。扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
浅析矩阵方程求解问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口小木虫 --- 500万硕博科研人员喜爱的学术科研平台
&&查看话题
求助一个矩阵求解问题
问题见附图，小弟不知如何把图显示在此处，请见谅。
在此问题重新描述下：
已知M对角矩阵diag(m_i)，L循环矩阵L(i,i)=2,L(i,i+1)=L(i,i-1)=-1，且存在向量X，使得（xM-L）X=0,则如何求其中的x？
敬请各位大侠指点下，多谢各位
未命名.jpg
恩，是的，但我想知道的是这种特殊的情形，能否求出来其值的表达式？
因为M为非奇异对角阵，其实就类似于求L的特征值。M^-1L是循环矩阵，关于循环矩阵特征值的求法很多，百度一下就出来不少文献了。
未命名1.jpg
未命名2.jpg
M^-1L并不是循环矩阵；另外m_i各不相同
m_i为不相同的正实数时，M^-1L是首先有一个0特征值，这一点把所有列加到第一列所得结果可以看出来。
利用降阶定理，剩下部分为“实对称三对角矩阵”，其特征 值计算论文很多，网上找了看一下。
过程懒得敲公式了。
几个矩阵的和求特征值如何求？本人愚钝，不清楚你说的这个方法怎么能求出来特征值，不知能否说的明白些。你验证过能做吗
不是矩阵求和，是把一个矩阵的第2到n列加到第一列，第一列为0，所以必然有0特征值
我最想知道的是非零的特征值，当然我知道其特征值都是非负的。所有特征值是什么样的，特别是非零的最大和最小的情形
研究生必备与500万研究生在线互动！
扫描下载送金币您的位置： &
线性规划的矩阵求解法线性规划问题的矩阵求解方法--《数学通报》1992年04期
线性规划问题的矩阵求解方法
【摘要】：正 单纯形法是求解线性规划问题的基本方法。它的解题思路是,先求一个可行解,经过检验如果不是最优解,则从这个可行解转换到另一个可行解。若后者仍不是最优解,再重复上述
【作者单位】：
【关键词】：
【正文快照】：
单纯形法是求解线性规划问题的基本方法.它的解题思路是,先求一个可行解,经过检验如果不是最优解,则从这个可行解转换到另一个可行解.若后者仍不是最优解,再重复上述步骤,直到求出最优解.单纯形算法的求解过程实质是对线性规划间题所确定的一个矩阵,按照某种规定实施行的初等
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
向荣华;张守诚;马家騄;;[J];西北大学学报(哲学社会科学版);1982年01期
徐冀太;;[J];江苏教育;1983年11期
何博传;;[J];开放时代;1984年05期
赵树嫄;[J];中国统计;1985年09期
陈松华;[J];中国统计;1985年11期
茅于轼;;[J];科学经济社会;1985年01期
林诒勋;;[J];中国管理科学;1985年01期
王全忠;马克;林诒勋;;[J];中国管理科学;1985年04期
赵宏量;;[J];中国管理科学;1985年04期
;[J];中国远程教育;1986年05期
中国重要会议论文全文数据库
刘思峰;;[A];全国青年管理科学与系统科学论文集（第2卷）[C];1993年
李培平;;[A];中国现场统计研究会第九届学术年会论文集[C];1999年
聂锐;陈权宝;;[A];系统工程与可持续发展战略——中国系统工程学会第十届年会论文集[C];1998年
黎建强;李录书;;[A];系统工程与可持续发展战略——中国系统工程学会第十届年会论文集[C];1998年
王延章;王众托;;[A];发展战略与系统工程——第五届系统工程学会年会论文集[C];1986年
郭延明;周宁;王凯悦;;[A];发展战略与系统工程——第五届系统工程学会年会论文集[C];1986年
朱美琳;倪慧君;陈涛;;[A];发展的信息技术对管理的挑战——99’管理科学学术会议专辑（上）[C];1999年
蔡晨;汪玲;;[A];发展的信息技术对管理的挑战——99’管理科学学术会议专辑（上）[C];1999年
顾昌耀;王建;;[A];发展战略与系统工程——第五届系统工程学会年会论文集[C];1986年
关嘉峪;吴翼平;王慧;;[A];科学决策与系统工程——中国系统工程学会第六次年会论文集[C];1990年
中国重要报纸全文数据库
洪先龙;[N];计算机世界;2001年
斯壮;[N];人民日报;2001年
程爱娟;[N];新疆科技报(汉);2001年
龚强（作者单位：哈尔滨工业大学管理学院）;[N];中国测绘报;2002年
王勇／文;[N];财经时报;2003年
杜超;[N];中国教育报;2003年
PALADIN;[N];电脑报;2003年
PALADIN;[N];电脑报;2003年
PALADIN;[N];电脑报;2003年
PALADIN;[N];电脑报;2003年
中国博士学位论文全文数据库
霍红卫;[D];西安电子科技大学;2000年
刘红英;[D];西安电子科技大学;2000年
李艳君;[D];浙江大学;2001年
罗兵;[D];重庆大学;2001年
吴镇;[D];武汉理工大学;2002年
骆正虎;[D];合肥工业大学;2002年
隋洪涛;[D];南京航空航天大学;2002年
郎艳怀;[D];大连理工大学;2002年
时贞军;[D];大连理工大学;2002年
韩其恒;[D];天津大学;2003年
中国硕士学位论文全文数据库
刘林涛;[D];北京工业大学;2001年
谢春利;[D];四川大学;2001年
王丽敏;[D];河北大学;2001年
杨亚红;[D];西安电子科技大学;2001年
金玉芳;[D];北京工业大学;2001年
高志慧;[D];华侨大学;2001年
杨晨影;[D];燕山大学;2002年
杜国宁;[D];河北工业大学;2002年
颜昌亚;[D];燕山大学;2002年
张晓峰;[D];大连理工大学;2002年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备74号