矩阵在线性规划中的应用
来源:用户上传
作者: 尚馥娟 李风梅
[摘要] 在经济管理、交通运输、工农业生产等经济活动中，合理安排人力物力资源尤为重要。可以建立线性规划问题的标准形式，利用矩阵的理论和方法，作一系列的行初等变换，根据检验数的值求出线性规划最优解。
[关键词] 数学模型 初等变换 检验数 最优解
运筹学发展历史不长，但内容丰富，涉及面广，应用范围大，形成了相当庞大的学科。线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中，提高经济效益是人们不可缺少的要求，建立数学模型运用矩阵求规划问题的最优解尤为重要。
一、线性规划问题
1.线性规划问题的数学模型的一般形式：
设有n个变量，满足
s称为目标函数,式(1)称为约束条件.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，使S取最大值或最小值的可行解叫线性规划问题的最优解。
2.线性规划问题的标准形式
只要引入新的非负变量（称为松弛变量），不妨设不等式组中每一个不等式加一个松弛变量后变为等式，这样就可以使不等式组(1)变为线性方程组，作为线性规划问题的标准形式。即
满足（2）的解成为线性规划的最优解，相应的s值称为该问题的最优值。
二、运用矩阵解线性规划最优解
矩阵在经济分析中有着广泛的应用，可以利用矩阵的理论和方法，对标准形式中线性方程组的增广矩阵作一系列的行初等变换，根据检验数的值可判定基变量为多少时，规划问题有最优解及最优值，最优解及最优值是多少，从而解决线性规划最优解问题。
在方程（2）中若S把视为一个变量，写为
方程（3）是一个n+m+1个未知量，m+1个方程的线性方程组，解法如下
[第一步]
记方程（3）的增广矩阵为
矩阵L中的最后一行的数称为检验数，从S=0做起。
[第二步]
当所有检验数为非负数时，转入第三步。当检验数有负数时，转入第五步。
[第三步]
最小比值原则：用矩阵L中的第一列前m行大于0的元素除同行对应的最后一列的元素，即。取比值最小者，记为。此时称为主元，所在的行称为主元行，所在的列称为主元列。(若第一列的前m个元素没有正数，就试第二列，依次类推)
对矩阵作初等行变换，将主元变为1，所在列的其他元素变为0；重复类似的变换运算，依次继续作若干次得到矩阵,在中必有m行m列的元素构成一个m阶单位矩阵，不妨设的前m行m列是m阶单位矩阵，于是，矩阵为
[第四步]
①的单位矩阵所在的列的检验数都为0，而其余检验数非负时，则所求的最优值为
(中最后一行最后一列的元素数值)
矩阵中单位矩阵所在各行的最后一列元素，为所求相应变量（称为基变量）的值，其他变量取值均为0（称为非基变量）这样得到的解为所求的最优解。
②的检验数有负数时，转入第五步。
[第五步]
所有检验数为负数时，取其绝对值最大者所在的列为主元列，返回第三步作行初等变换，从而求出最优解及最优值。
三、解决经济中的实际问题
例如 为制造两种类型的产品，仓库最多提供80的钢材，已知每制造一件Ⅰ型产品需要耗钢2kg，最少需生产10件，而每件售价50元；每制造一件Ⅱ型产品需要耗钢1kg，最少需生产40件，而每件售价30元。试选择最优生产方案，以获最大收入?
设生产Ⅰ型产品件，生产型产品件，获得的收入为R
则此规划问题的一般形式为
引入非负的松弛变量，标准形式为
对应的方程组
方程组的增广矩阵为
末行检验数中有两个负数，绝对值最大者为-50，取-50所在的列为主元列，用最小比值原则，第二行为主元行，为主元。进行行初等变换得：
检验数中仍有负数，同样，-50所在第四列为主元列，按最小比值原则，取为主元。进行行初等变换得：
仍有负检验数-5，同样的方法取为主元。进行行初等变换得：
以上矩阵前三行的第1，2，4列构成一个3阶单位矩阵，其所在的列的检验数为0，其余检验数均非负，所以，为基变量，为非基变量，得到
最优解为:件，件，件，件，件
最优值为：（元）
故当件，件时，获得最大收入为件，件。
在线性规划的实际问题中，主要研究解决两种类型的问题：一是给定一定数量的人力、物力和财力资源，怎样运用这些资源使完成的任务量最大，收到的效益最大；二是给定一项任务问怎样统筹安排，完成这项任务耗费的人力、物力资源最小．随着计算机的逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行动和科学研究的各个方面，为社会节省的财富、创造的价值无法估量。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
转载注明来源:https://www.xzbu.com/3/view-1493347.htm
