用矩阵法求解线性规划问题

来源:用户上传      作者: 李晓东

　　摘要：线性规划作为运筹学的一个重要分支，自1947年丹捷格提出了一般线性规划问题的求解方法即单纯形法之后，线性规划在理论上日益成熟，在使用中日益广泛与深入，至今单纯形法仍是求解线性规划问题最常用、最有效的方法之一。单纯形法的基本步骤是换基迭代,求解过程实质是对线性规划问题所确定的某个特定矩阵施行初等变换以达到某种形式的过程。因此本文利用线性方程组的同解理论，通过引进人工变量等手段，化一般线性规划为标准线性规划，建立线性方程组，写出其系数矩阵，对系数矩阵进行一系列的最优化过程，得到最优矩阵从而求出最优解。
　　关键词：线性规划 单纯形法 矩阵 求解
　　 现代科学技术迅猛发展的今天对数学问题的研究提出了更新更高的要求，而线性规划问题在数学领域及科学技术中应用广泛，所以对线性规划问题的求解法要求也越来越高。教材中介绍的主要是用单纯形法求解，由于线性约束条件是由线性方程组构成的，而方程组的问题可以转化为矩阵的形式。所以本文结合自己的学习，通过认真分析查阅资料，整理出了用矩阵法求解线性规划问题的步骤，以期对线性规划问题的研究有一定的参考价值。
　　 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
　　

转载注明来源:https://www.xzbu.com/1/view-238237.htm