线性规划算法的改进与在企业管理中的应用.doc

1、 晋中学院数学学院 2008 届本科生毕业论文线性规划算法的改进与在企业管理中的应用 学生姓名：李艳红（本六班）指导老师：潘玉峰摘 要：本文首先介绍了线性规划问题中单纯形法和两阶段法的算法改进，并对这两种方法进行了分析并进行举例说明。然后对线性规划增减约束条件的灵敏度进行分析。最后说明线性规划在企业管理中的应用。关键词：单纯形法；两阶段法；灵敏度分析晋中学院数学学院 2008 届本科生毕业论文Linear Programming Algorithm Improvement and in Business Management ApplicationStudent:Li YanhongInstr

2、uctor:Pan YufengAbstract: This paper first introduced algorithm improvement of the simplex method and two-stage method in the linear programming question and carried on to these two methods has analyzed and carries on explains with examplesThen it analysisd the sensitivity of adding or deleting cond

3、ition of linear programmingFinally it explains the application of linear programming in the business managementKey words: simplex method; two-stage method; sensitivity analysis晋中学院数学学院 2008 届本科生毕业论文目 录引言 .51.一种线性规划问题单纯形法的改进算法 .51.1 算法 .51.2 算法分析 .71.2.1 准备工作 .71.2.2 分析过程 .71.3 举例 .91.4 结论 .122.线性规划问

4、题两阶段法的改进算法 .122.1 引言 .132.2 算法 .132.3 算例 .143.线性规划增减约束条件的灵敏度分析 .153.1 增加约束条件 .163.2 减少约束条件 .163.3 算例 .173.4 灵敏度分析 .193.4.1 产品的市场价格发生变化 .193.4.2 资源量的变化分析. .19晋中学院数学学院 2008 届本科生毕业论文3.4.3 技术条件的变化分析 .20.线性规划在企业管理中的应用 .204.1 线性规划的概念和构成要素 .204.2 线性规划在企业管理中的应用范围 .214.3 线性规划问题求解方法介绍 .214.4 运用线性规划方法进行企业管理中应注

5、意的问题 .214.4.1 设定最优解中非零变量个数与约束条件个数 .214.4.2 目标函数中的价值系数 .214.4.3 线性规划模型的静态性 .22参考文献 .错误！未定义书签。晋中学院数学学院 2008 届本科生毕业论文引言 用单纯形法求解线性规划问题时，首先要找一个初始可行基，再用单纯形迭代公式求最优解当问题无明显的可行基时，通常是引入人工变量构造初始可行基，然后利用两阶段法求解一个辅助问题来得到一个原问题的一个初始可行基多年来的实践证明，两阶段法方便实用，但由于人工变量的引入不仅加大了计算机的贮存量还增加了计算量本文基于高斯消元法的思想，提出了一种不用引入人工变量，直接按一定的规则

6、迭代就可求出初始基本可行解或者得出原问题无可行解的改进算法其次用单纯形法求线性规划问题时可能产生循环，1955 年 Beale 给出了一个特例，证明用单纯形法求解线性规划问题时产生了循环，50 多年来不少人提出了避免循环的办法，最初是 Acharnes1952 提出的摄动法，其理论复杂，实际操作十分不便，1974 年 Dantzig 提出了字典序法，Bland 提出的勃兰特规则，同样是不利于实际操作本文提出的改进算法可以有效的避免循环，且操作简单随着改革开放的不断深入，如何提高企业的经济效益是一个大问题做为一个企业家，当然首先根据国际国内市场的信息确定生产的产品，然后再进行产品的设计和工艺装备

7、的设计与研究，提高产品的质量，降低成本并取得广大用户的信誉； 同时在管理中尽量采用现代化的管理方法和电子计算机管理，为提高企业的经济效益寻找出有效的途径1.一种线性规划问题单纯形法的改进算法1.1 算法考虑线性规划问题： 0.maxbAtscvT其中 是 阶的矩阵( )， ， ， 且 AnmnxnRcnnRb0在许多情况下，线性规划问题并无明显的可行基，通常是引入人工变量后采用大M 法或两阶段法，但都将使计算量增加，同时增加计算机的储存量，而且当线性规划晋中学院数学学院 2008 届本科生毕业论文问题出现退化时，采用单纯形法可能产生循环下面所提出的算法可以有效的避免循环，提高运算速度步骤 1：

8、写出约束方程组的增广矩阵，任取一个大于 0 的 ，并以第 t 行(该行tb称为无基行) 的- 倍加入到第 行( i = 1，2， ， - 1， +1， ， m) ，使第 行tibt i的常数项变为 0，( 为检验数) ；转步骤 2j步骤 2：令 = 1，若 = 0，j = 1，2， ，n，则此行对应的方程为多余方程，kkB去掉此行，否则取一个下标 最小的且满足 0 的项令其为主元实行一次高斯消元，kjB同时将 和 写在该行左边 下对应的位置；令 = +1，当 = 时令 = +1，jcjxBxcktkt重复上述过程直到 取完从 1 到 所有不等于 的整数为止；转步骤 3kmt步骤 3：若第 行元

9、素 0， = 1，2， ， ，结束，问题无可行解；否则考ttjjn查每一个 0，若存在某个 H 对应的列满足 0( 取从 1 到 中的不等于 的整tjBiHBmt数) ，则以 为主元进行一次高斯消元，同时将 和 写在该行左边 下对应的iH cxBxc位置，并按公式 =- 0( = 1，2， m 且不等于 t) 修正常数项，按公式 =ibtiBi j( 是修正后的列向量) 修正检验数，然后转步骤 5；否则转步骤 4jjBcpj步骤 4：任取一个 0( 取从 1 到 中的不等于 的整数) ，实行一次高斯iHi t消元，同时用 和 替换该行左边 下对应位置的元素，然后转步骤 3；cxBxc步骤 5：

10、若所有的检验数 大于或等于 0，则得到最优解否则转步骤 6；j步骤 6：找出所有 0，其所对应的列中有 0，则以 为主元进行高斯tHiHBiH消元，同时用 和 替换该行左边 下对应的位置上的元素；再看(2) 是否成立，HcxBxc不成立继续进行(3) 下述定理可以保证在有限步迭代后若问题有可行解，则步骤 3 中的第二种情况成立；定理 1 步骤 4 经有限步迭代后产生两种情况：(1) 该问题没有可行解； (2) 找到一个初始可行解证明 对于经步骤 2 消元后的初始表的无基行最右边引入人工变量 ，以及在表y中检验数上一行内引入辅助目标函数 = ，同时修正 ，并把其对于各变量的检验zyic数依次写入

11、相应位置，且在 最下方填入 Bx若不看人工变量 这一列，则原来的无基行第 行与第一阶段的目标函数行对应的yt项均相等，第 行的系数 ， = 1，2， ，n 就是相应的检验数，且在主元选在第ttja行之前上述对应关系不变因此无基行中的正系数所在列按最小比值选主元时，自然t等价于第一阶段目标函数 行的正检验数所在列按最小比值选主元，所以当 0， z tjaj= 1，2， ，n 时，这种问题无可行解的情况相当于对第一阶段的检验数全为非正，从而得第一阶段的最优解 = ztb晋中学院数学学院 2008 届本科生毕业论文若原问题要有可行解的话，第一阶段的最优解应为 0，所以原问题没有可行解，两者的结论一样

12、而迭代中一旦主元选在第 行，则经一次消元后，原有问题的一个t初始基本可行解，除人工变量 列外全变为 0，说明已得第一阶段的最优解，由于人工变y量 y 已离基，目标函数 z = 0，故删去人工变量 这一列和目标函数行即得原问题的y一个初始可行解，而迭代次数完全由第一阶段目标函数最优解的求解迭代次数决定，所以此定理可以保证如果原问题有可行解的话，经有限步就可得到步骤 3 的第 2 种情况 当得到步骤 3 的第 2 种情况时转步骤 5，验证检验数，如果所有检验数均大于等于 0，则得原问题的最优解，否则转 6，利用试算法的思想进行试算，确定最优主元，因为任意一个小于 0 的检验数对应的非基变量作为进基

13、都会使目标函数增加，所以对所有检验数小于 0 的列，找出其中所有大于 0 的项为主元进行试算，找出使目标函数值增量最大的项为最终主元，同时这个元素对应的非基变量为进基变量，而这个元素所在的行右边对应的的基变量为出基变量本算法和单纯形法选主元的思路是不同的，单纯性法是按 法则选的主元，它选的主元可以使目标函数值增加的最快但不是最大而本算法，选的是使目标函数增加的最大的元素为主元同时利用这种试算法选主元进行迭代可以避免出现循环以下定理可以保证：定理 2 以这种试算法确定主元进行的单纯性迭代不会出现循环证明 若每一次迭代都有目标函数值的最大增量为 0，则对于所有的小于的检验数其所对应的非基变量作为进

14、基变量时，目标函数均不增加，这时按步骤 6 的选主元规则，我们选的是负检验数中下标最小的那个负检验数， 这遵循了 Bland 法则 ，由Bland 法则我们知道，经有限步迭代后，要么得到最优解，要么产生一个主元使目标函数的增量大于 0，即不会出现循环1.3 举例v=-4 -3max133 -6 +4 =0.ts24晋中学院数学学院 2008 届本科生毕业论文1.5 -0.5 =31x3+ + - =2224x0 i =1，2，3，4ix解 按照前述程序步骤 1 先建立初始迭代表，选择第 3 行为无基行，迭代过程见下表 1.1，1.2，1.3，1.4经过 4 次迭代得到最优解 x=(2，1，0)，目标函数的最大值是-8；表 1.1BcBx1x23x4b1 -2 0 4/3 03/4 -3/2 -5/4 1 01/2 1 1/2 -2/3 2v 1234bBc1表 1.2BcBx1x23x4b-4 11 -2 0 4/3 00 0 -5/4 0 00 2 1/2 -4/3 2v 134bBc1表 1.3BcBx1x23x4b-4 11 -2 0 4/3 0-3 30 0 1 0 00 2 0 -4/3 2v 134bBc1表 1.4