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

晋中学院数学学院2008届本科生毕业论文线性规划算法的改进与在企业管理中的应用 学生姓名：李艳红（本六班）指导老师：潘玉峰摘要：本文首先介绍了线性规划问题中单纯形法和两阶段法的算法改进，并对这两种方法进行了分析并进行举例说明。然后对线性规划增减约束条件的灵敏度进行分析。最后说明线性规划在企业管理中的应用。关键词：单纯形法；两阶段法；灵敏度分析Linear Programming Algorithm Improvement and in Business Management ApplicationStudent:Li YanhongInstructor: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 condition of linear programmingFinally it explains the application of linear programming in the business managementKey words: simplex method; two-stage method; sensitivity analysis目录引言51.一种线性规划问题单纯形法的改进算法51.1 算法51.2 算法分析71.2.1 准备工作71.2.2 分析过程71.3 举例91.4 结论122.线性规划问题两阶段法的改进算法122.1 引言132.2 算法132.3 算例143.线性规划增减约束条件的灵敏度分析153.1 增加约束条件163.2 减少约束条件163.3 算例173.4 灵敏度分析193.4.1 产品的市场价格发生变化193.4.2 资源量的变化分析.193.4.3 技术条件的变化分析20.线性规划在企业管理中的应用204.1 线性规划的概念和构成要素204.2 线性规划在企业管理中的应用范围214.3 线性规划问题求解方法介绍214.4 运用线性规划方法进行企业管理中应注意的问题214.4.1 设定最优解中非零变量个数与约束条件个数214.4.2 目标函数中的价值系数214.4.3 线性规划模型的静态性22参考文献错误！未定义书签。引言用单纯形法求解线性规划问题时，首先要找一个初始可行基，再用单纯形迭代公式求最优解当问题无明显的可行基时，通常是引入人工变量构造初始可行基，然后利用两阶段法求解一个辅助问题来得到一个原问题的一个初始可行基多年来的实践证明，两阶段法方便实用，但由于人工变量的引入不仅加大了计算机的贮存量还增加了计算量本文基于高斯消元法的思想，提出了一种不用引入人工变量，直接按一定的规则迭代就可求出初始基本可行解或者得出原问题无可行解的改进算法其次用单纯形法求线性规划问题时可能产生循环，1955 年 Beale 给出了一个特例，证明用单纯形法求解线性规划问题时产生了循环，50 多年来不少人提出了避免循环的办法，最初是 Acharnes1952 提出的摄动法，其理论复杂，实际操作十分不便，1974 年Dantzig 提出了字典序法，Bland 提出的勃兰特规则，同样是不利于实际操作本文提出的改进算法可以有效的避免循环，且操作简单随着改革开放的不断深入，如何提高企业的经济效益是一个大问题做为一个企业家，当然首先根据国际国内市场的信息确定生产的产品，然后再进行产品的设计和工艺装备的设计与研究，提高产品的质量，降低成本并取得广大用户的信誉； 同时在管理中尽量采用现代化的管理方法和电子计算机管理，为提高企业的经济效益寻找出有效的途径1.一种线性规划问题单纯形法的改进算法1.1 算法考虑线性规划问题：其中是阶的矩阵()，且在许多情况下，线性规划问题并无明显的可行基，通常是引入人工变量后采用大M 法或两阶段法，但都将使计算量增加，同时增加计算机的储存量，而且当线性规划问题出现退化时，采用单纯形法可能产生循环下面所提出的算法可以有效的避免循环，提高运算速度步骤 1：写出约束方程组的增广矩阵，任取一个大于0 的，并以第 t 行(该行称为无基行) 的-倍加入到第行(i = 1，2， ，- 1，+1， ， m) ，使第行的常数项变为0，(为检验数) ；转步骤2步骤2：令 = 1，若= 0，j = 1，2， ，n，则此行对应的方程为多余方程，去掉此行，否则取一个下标最小的且满足0的项令其为主元实行一次高斯消元，同时将和写在该行左边下对应的位置；令 = +1，当=时令 = +1，重复上述过程直到取完从1到所有不等于的整数为止；转步骤 3步骤3：若第行元素0， = 1，2， ，结束，问题无可行解；否则考查每一个 0，若存在某个H对应的列满足0(取从1到中的不等于 的整数) ，则以为主元进行一次高斯消元，同时将和写在该行左边下对应的位置，并按公式=-0(= 1，2， m且不等于t) 修正常数项，按公式= (是修正后的列向量) 修正检验数，然后转步骤 5；否则转步骤 4步骤 4：任取一个 0( 取从1到 中的不等于 的整数) ，实行一次高斯消元，同时用和替换该行左边下对应位置的元素，然后转步骤 3；步骤 5：若所有的检验数大于或等于 0，则得到最优解否则转步骤 6；步骤6：找出所有 0，其所对应的列中有 0，则以为主元进行高斯消元，同时用和替换该行左边下对应的位置上的元素；再看(2) 是否成立，不成立继续进行(3) 下述定理可以保证在有限步迭代后若问题有可行解，则步骤 3 中的第二种情况成立；定理 1步骤4 经有限步迭代后产生两种情况：(1) 该问题没有可行解； (2) 找到一个初始可行解证明对于经步骤 2 消元后的初始表的无基行最右边引入人工变量，以及在表中检验数上一行内引入辅助目标函数 = ，同时修正 ，并把其对于各变量的检验数依次写入相应位置，且在最下方填入 若不看人工变量这一列，则原来的无基行第行与第一阶段的目标函数行对应的项均相等，第行的系数， = 1，2， ，n就是相应的检验数，且在主元选在第行之前上述对应关系不变因此无基行中的正系数所在列按最小比值选主元时，自然等价于第一阶段目标函数 行的正检验数所在列按最小比值选主元，所以当0， = 1，2， ，n时，这种问题无可行解的情况相当于对第一阶段的检验数全为非正，从而得第一阶段的最优解 = 若原问题要有可行解的话，第一阶段的最优解应为 0，所以原问题没有可行解，两者的结论一样而迭代中一旦主元选在第 行，则经一次消元后，原有问题的一个初始基本可行解，除人工变量列外全变为 0，说明已得第一阶段的最优解，由于人工变量 y 已离基，目标函数 z = 0，故删去人工变量这一列和目标函数行即得原问题的一个初始可行解，而迭代次数完全由第一阶段目标函数最优解的求解迭代次数决定，所以此定理可以保证如果原问题有可行解的话，经有限步就可得到步骤 3 的第 2 种情况当得到步骤 3 的第 2 种情况时转步骤 5，验证检验数，如果所有检验数均大于等于 0，则得原问题的最优解，否则转 6，利用试算法的思想进行试算，确定最优主元，因为任意一个小于 0 的检验数对应的非基变量作为进基都会使目标函数增加，所以对所有检验数小于 0 的列，找出其中所有大于 0 的项为主元进行试算，找出使目标函数值增量最大的项为最终主元，同时这个元素对应的非基变量为进基变量，而这个元素所在的行右边对应的的基变量为出基变量本算法和单纯形法选主元的思路是不同的，单纯性法是按法则选的主元，它选的主元可以使目标函数值增加的最快但不是最大而本算法，选的是使目标函数增加的最大的元素为主元同时利用这种试算法选主元进行迭代可以避免出现循环以下定理可以保证：定理 2 以这种试算法确定主元进行的单纯性迭代不会出现循环证明 若每一次迭代都有目标函数值的最大增量为 0，则对于所有的小于的检验数其所对应的非基变量作为进基变量时，目标函数均不增加，这时按步骤 6 的选主元规则，我们选的是负检验数中下标最小的那个负检验数， 这遵循了Bland法则 ，由Bland 法则我们知道，经有限步迭代后，要么得到最优解，要么产生一个主元使目标函数的增量大于 0，即不会出现循环1.3 举例v=-4-3 3-6+4=01.5-0.5=3 +-=2 0 i =1，2，3，4解按照前述程序步骤1先建立初始迭代表，选择第3行为无基行，迭代过程见下表1.1，1.2，1.3，1.4经过4次迭代得到最优解x=(2，1，0)，目标函数的最大值是-8；表1.1b1-204/303/4-3/2-5/4101/211/2-2/32v表1.2b-41-204/3000-5/400021/2-4/32v表1.3b-41-204/30-300100020-4/32v表1.4b-410002-3001000010-2/31v0000-8如果是用单纯形法求最优解时，首先用大M 法求初始可行基，迭代4次求的初始可行基，然后再求原问题的最优解，利用单纯形迭代公式再迭代1次，总共迭代5次才得到最优解 x = (2，1，0) ；且由于引进了人工变量，所以计算量和储存量都比本算法大下面看Beale 给的例子Max v = -20+-6st +-8-+9=0 +-12-+3=0+=1 0 j=1，2，7.利用单纯形法去做经过 6 次迭代得到的单纯形表和初始单纯形表一样，做下去将无限循环，下面用本算法去做可以有效的避免循环，先按步骤1建立初始迭代表 2表2b1001/4-8-1900101/2-12-1/23000100101因为Beale 给的这个例子已经有一个明显的初始可行基，所以可直接把基变量和相应的系数填在相应的位置，见下表 3表3b01001/4-8-19000101/2-12-1/230000100101v000-3/420-1/260同时计算相应的检验数得和两个检数均为负数，所以对这两个检验数对应的列中所有正数项进行试算，最后以对应的主元 1 为最终主元进行迭代得下表 4表4b01011/4-80900011/21/2-12031/21/200100101v001/2-3/420061/2小于0，这个检验数对应的列按规则确定主元，最后以为主元进行迭代得下表5表5b01-1/23/40-2015/23/43/40211-240611/200100101v03/25/402021/25/4检验数全是正数，所以这时得到可行解为最优解，最优解为(，) = (，1，1) ，最优值为由此例可以看出，本算法可以有效避免循环1.4 结论结合上面的例子可以看出改进后的单纯形法主要有两大优点：(1)不用引入人工变量 ，这样减少了计算机的存储量 ，同时实验证明还降低了运算量减少了迭代次数；(2)可以避免循环；所以改进后的单纯形法大幅度的提高了单纯形的效率2.线性规划问题两阶段法的改进算法2.1 引言对于线性规划问题.用两阶段法求初始基可行解时，首先要在问题(1) 中引入人工变量，使约束方程组的系数矩阵中含有单位矩阵，用以作为人造基一般来说，有个相互独立的约束方程就需引入个人工变量，但若系数矩阵中含有单位列向量，引入的人工变量则可减少，例如：.由于变量的系数构成的列向量为单位向量(0，0，1) ，所以只要引入两个人工变量，可以直接作为人造基中的一个基变量一般说来，若约束矩阵中含有个单位列向量，则可少引入个人工变量能否尽量减少人工变量的个数，节省存储空间和计算量？基于这一思路，通过对线性规划问题增广矩阵的初等行变换，使约束方程组的系数矩阵中尽可能多的出现单位列向量，最后只须引进一个人工变量 (虚设) 即可求得初始基可行解2.2 算法第1 步：建立初始单纯形表第 2 步：用初等行变换将初始单纯形表简化由于0且不全为0，不妨设0，以 所在行为基准行，分别乘以该行的 - (= 2， ，m) 倍加到第行，使行的常数项变为0第3 步：用初等行变换产生单位列向量和对应的基变量令= 2，若= 0， = 1， ，n，则令 = +1；否则，任取0(一般可取下标最小的一个) ，以其为主元，用初等行变换将其所在列化为单位列向量，并把基变量填在第 k行左边位置，并令=+ 1，重复这一步骤直到=此时，系数矩阵中只有第一行没有产生基变量，不妨设产生的- 1 个基变量是， ，第4 步：对应的线性规划问题，在第 1个约束方程中引入一个人工变量，构造人造基(， ， ，) ， 用两阶段法求解2.3 算例例求解线性规划问题.问题的最优解为，最优解为求解过程见表6.1，6.2，6.3，6.4，6.5，6.6.表6.11-21-104111193-631-3010表6.21-21-1009-351018-6101-3010表6.3101/31/92/901-1/35/91/90000-1008/31/3表6.4101/31/9001-1/35/900000100-18/30表6.53011/301102/300000130030表6.65/2-1/21003/23/201000001-3/2-9/20003.线性规划增减约束条件的灵敏度分析设线性规划问题 . (1)由于现实世界是不断发展变化的，体现在约束条件上，增加或减少约束条件则是随时可能发生的这将导致最优方案的变化，如不与时俱进，及时做相应调整，必将造成经济损失本文在灵敏度分析的基础上，面对增减约束条件的情形，给出新最优方案的获得方法3.1 增加约束条件设增加的一个约束条件为 (2)则应在原问题的最优表(2)提供的数据，增加一行，然后用消去法，把这行中基变量的系数消为0，这显然对检验数没有影响，从而可化为仅缺少一个基变量且= 1， ， n 的问题，故可沿用对偶单纯形法或联合算法的规则，于新增之行确定主元，实行 Gauss 消元，便得一正则解，继之用对偶单纯形法迭代求优如果增加的约束不止一个，可一并处理3.2 减少约束条件对于减少约束条件的问题，大多的教材和其它文献都没有涉及事实上它和增加约束一样重要减少约束条件还有特殊的经济意义对于资源利用问题，它意味着解除对某些资源的限制，而在工厂里又相当于去掉一道工序，这些都为创新增值提供途径或指示方向，故值得详细讨论当需要减少一个约束时，并不是将最优表中，与该约束相应的行去掉就可以的，因为此约束的影响已通过 Gauss 消元施加在其它各行里了那么，如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢?设初始单纯形表中含有一个单位矩阵，不妨假定它是由辅助变量(松弛变量，剩余变量或人工变量等)形成， 现在要去掉原约束条件中的一个约束，不妨设为第个约束，则对上表应采取如下步骤：考虑原第个约束所加辅助变量 这一列，即()列，若 为基变量，则去掉最优表中第个约束行和()列即可(此时最优解与最优值均不变) 否则，若该列某系数0，取 (3)若则取 (4)然后以为主元实行Gauss消元，并去掉主元所在之行与列考察新检验数是否仍非正，是，则已得去掉原第个约束后的最优解；否，用单纯形法迭代求优3.3 算例某工厂去年根据市场需求和自身生产能力可以生产 A ，B 两种产品，当时的条件如下表所示表7 资源利用消耗表产品单位消耗资源A(千克)B(千克)资源可供应量电（度）设备（台时）劳动力（小时）流动资金（百元）517083115032105063024单位利润（百元）43据之可确定问题的初始单纯形表和最优表如下：表8例题的初始单纯形表和最优表53100021011010050715001063008030001244300000表910002180100-232000116240010-4240000-2-168今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制试问应如何调整生产，才能获得最大利润?由初始表 4 知关于流动资金的约束方程是第 4 个，相应松驰变量是，故考虑最优表中一列，由(3)得应以 为主元，实行 Gauss 消元，然后去掉 4 行，6 列得表10 去掉约束后的单纯形表10030010200041120000这已经是最优表，按它进行调整，可增加利润 180 - 168 =12(百元) 注意：由(3)知，主元所在之行未必一定是原约束中要去掉的那一行，如在例 1 中，若因进口设备而欲将第二个约束去掉，计算结果，主元是，因而消元之后，去掉的却是第三行此外，之所以先考虑 (3)式是因为去掉约束，一般将使目标函数值减少，但绝不会增大方法的原理是很简单的，通过比较，不难看出，初始表中将要去掉的约束行所加辅助变量那一列仅有一个 1 而其余都是0，而在最优表中该列一般将发生变化，说明将要去掉的约束行的影响已经通过迭代施加到别的行中注意，若从一开始就去掉那个约束，则所加辅助变量那一列全为 0，并且在迭代中保持不变；因此，只有经过上面的处理，使所加辅助变量那一列又全变回为 0，要去掉之约束在单纯形迭代中对其它约束施加的影响(即指此行的若干倍加于其它诸行)才被消除此外，按照(3)或(4)选主元是为了保证所得解的可行性如果初始表中没有单位矩阵，注意到前面的分析只涉及辅助变量一列，它由单位列向量最后变成的第列，检验数由0 变为因此，这时只需在最优表中增加一辅助列，对该列重复和的过程即可稍有不同的是，若0，则用(3)式选主元；不然，则用(4)式选主元此外，还应注意需先将基变量所在列调整成单位矩阵后按新的变量位置确定，再进行计算3.4 灵敏度分析在市场经济的现实情况中，产品的市场价格条件，拥有的资源量，以及企业的技术都有可能发生一定的变化，这就需要管理者在这些条件发生变化时也随着将原有生产计划作相应调整3.4.1 产品的市场价格发生变化产品的市场发生变化，必将导致单件利润 C也随着变化，现分两种情况来研究根据检验数计算公式可知，它将会影响非基变量的检验数，若要想原最优!解不变，根据单纯形法的计算原理可知，必须一旦，原最优生产计划将会发生改变，可以通过改进最优单纯形表来求出新的最优计划3.4.2 资源量的变化分析.资源量对应的线性规划模型中的右端常数，亦即求的灵敏度分析，由运筹学的灵敏度分析可知，劳动工时资源的拥有量在9/4，9范围内变化时原最优生产计划中安排生产的产品种类不变：而原材料的拥有量在3，12范围内变化原最优生产计划中安排生产的产品种类不变；一旦资源的拥有量超出上述各自的约束范围，则可以根据线性规划的知识在原生产计划的基础上重新调整生产计划3.4.3 技术条件的变化分析技术条件对应的是线性规划模型中的，生产某种产品的技术条件发生变化，将会影响到产品的检验数或者现有生产产品法重新调整4.线性规划在企业管理中的应用一个企业要在市场竞争中立于不败之地，就必须改善经营管理，提高经济效益，具体包括怎样合理安排生产任务，配置资源，怎样制定最优的生产计划，并对瞬息万变的市场信息及时作出反应随着计算机技术的普及，线性规划的数学方法在企业管理中应用的范围越来越广泛，线性规划产生于三十年代未和四十年代初，并随着现代科技和管理实践的发展而不断发展是运筹学中起源较早，理论上较成熟的一个分支线性规划的“线性”特点，简化了数学模型的构造和解题方法，容易被一般未具有高等数学知识的各级企业管理人员所掌握应用特别是计算机的广泛应用，线性规划的在企业管理中的应用范围更加广泛和深入，渐渐成为管理人员必须掌握的一门现代化管理方法和优化技术4.1 线性规划的概念和构成要素线性规划探讨的问题是在由所提出问题的性质决定的一系列约束条件下，如何把有限的资源进行合理的分配，制定出最优实施方案在企业的各项管理活动中，例如计划、生产、运输、技术等问题，线性规划是指从各种限制条件的组合中选择出最为合理的计算方法，从而求得最佳结果决策变量、约束条件、目标函数是线性规划的三要素决策变量是指决策问题需要控制的因素，一般称为决策变量例如，要考虑怎样确定不同产品的产量才能获得最大利润的问题，不同产品的产量可设为变量的多少，取决于决策问题的要求，一般地说，决策变量越多，越能反映实际问题，但求解也就越复约束条件是指实现目标的限制条件，艰制条件是多种多样的例如确定不同产品的产量时，会受到劳动力、设备能力、原材料等的限制因此要充分考虑约束条件在满足约束条件下实现决策目标约束条件有“”“”“ ”几种类型约束条件越多，考虑问题越周到目标函数是指把决策的目标用变量之间的函数关系式表示出来目标函数有最大值和最小值两种形式如果设目标函数为S，则求Max(s)和Min(s)最大值和最小值统称为最优值4.2 线性规划在企业管理中的应用范围企业的效益依赖于资源配置的优化，即依赖于线性规划模型的优化优化的范围越大，效果也就越好首先，线性规划可用于生产计划确定后的优化，包括确定最佳库存量，产品的最大利益，最佳效率和最小费用等等其次，利用线性规划支持企业未来的决策，管理者必须分析未来的经济走势，分析未来的消费趋势并预测同行的产销动向，然后确定自己的产品价格，广告与促销策略，最后再将这些数据进行线性规划，这是求解一个随机线性规划问题4.3 线性规划问题求解方法介绍所谓线性规划问题，简单地说就是求一组决策变量在满足一组线性等式或不等式的约束条件下的值，使线性目标函数的值达到最优的数学方法线性规划常用的解法有两种对于比较简单的只含有两个变量的线性规划问题，以用图解法求出最优值对于三个以上的变量的线性规划问题，可以用单纯形法求解图解法虽然较容易，但它可以为单纯形法提供理论基础单纯形法比较繁杂，变量越多，计算起来步骤越多，然而可以用电子计算机来进行数据处理4.4 运用线性规划方法进行企业管理中应注意的问题4.4.1 设定最优解中非零变量个数与约束条件个数应用线性规划对实际问题进行优化，都是在一定的约束条件之下进行的不容忽视的是线性规划模型所得的最优解中非零变量的数目n不会超过模型的约束条件数目m 如果我们采用线性规划方法建模，根据所给的条件又只能得到m个约束方程，那么，这样建立的模型的最优解如果存在，就最多只能有m个非零分量如果在应用中忽视了这个结论，而将由模型求得的最优解不加分析地付诸实施，常常会带来不良的后果 挪威在开始用线性规划方法编制经济发展计划时，由于忽视了这一点，最优解中许多商品的指标是零，使得规划失效给管理造成了巨大混乱和损失4.4.2 目标函数中的价值系数在许多实际企业管理中的线性规划问题中，目标函数=或=中和 分别为利润系数向量和成本系数向量，们都是与一定的价格相联系的，线性规划的目标实质上是一种货币形式表现的价值目标在一个较合理的价格体系中，价格一般是能够代表商品的价值的但在