1、1毕业论文开题报告数学与应用数学线性规划算法的改进及在企业管理中的应用一、选题的背景与意义线性规划是运筹学最基本、运用最广泛的分支，是其他运筹学问题研究的基础。在20世纪50年代到60年代期间，运筹学领域出现许多新的分支非线性规划、商业应用、大尺度方法、随机规划、整数规划、互补转轴理论、多项式时间算法等。20世纪70年代末,上述分支领域都得到了极大发展，但是却都不完善。而且数学规划领域中存在许多NPHARD问题,如TSP问题，整数规划问题等。这些问题的基本模型都可以写成线性规划形式，因此通过对线性规划算法的进一步研究，可以进一步启发及推动数学规划领域内其他分支的发展。用单纯形法求解线性规划问题
2、时，首先要找一个初始可行基，再用单纯形迭代公式求最优解。当问题无可行基时，通常是引入人工变量构造初始可行基，然后利用两阶段法求解一个辅助问题来得到一个原问题的一个初始可行基。多年来的实践证明，两阶段法方便实用，但由于人工变量的引入不仅加大了计算机的储存量还增加了计算量。本篇基于高斯消元法的思想，提出了一种不可引入人工变量，直接按一定的规则迭代就可求出初始基本可行解或者得出原问题无可行解的改进算法。其次用单纯形法求线性规划问题时可能产生循环，1955年BEALE给出了一个特例，证明用单纯形法求解线性规划问题时产生了循环，50多年来不少人提出了避免循环的办法，最初是ACHARNES1952提出的摄
3、动法，其理论复杂，实际操作十分方便，1974年DANTZIG提出了字典序法，BLAND提出的勃兰特规则，同样是不利于实际操作。随着改革开放的不断深入，如何提高企业的经济效益是一个大问题。做为一个企业家，当然首先根据国际国内市场的信息确定生产的产品，然后再进行产品的设计和工艺装备的设计与研究，提高产品的质量，降低成本并取得广大用户的信誉；同时在管理中尽量采用现代化的管理方法和电子计算机管理，为提高企业的经济效益寻找出有效的途径。二、研究的基本内容与拟解决的主要问题2研究的基本内容1线性规划问题的中单纯形法和两阶段法的算法改进11单纯形法111单纯形法的算法介绍及分析112举例113结论12两阶段
4、法121两阶段法的算法介绍及分析122举例122结论2线性规划增减约束条件的灵敏度分析21增减约束条件对线性规划的影响22算例分析23灵敏度分析231产品市场价格变化分析232资源量的变化分析233技术条件的变化分析3线性规划在企业管理中的应用31线性规划的概念及构成要素32线性规划在企业管理中的应用范围介绍33线性规划求解方法介绍拟解决的主要问题通过上述三个部分的阐述，主要列举了线性规划方法的介绍及算法的异同点，通过比较分析说明线性规划算法改进后的优点并应用举例。同时分析说明增减约束条件对线性规划的影响及实际应用的分析。论述了线性规划对企业管理的重大意义，通过合理的方法应用，以期我国企业管理
5、能够得到更好的发展。三、研究的方法与技术路线本文通过文献综述法收集了大量国内外线性规划的理论分析及企业管理的发展现状。通过比较分析对线性规划算法改进前后进行比较，进而选择更优良的方法。3通过举例分析增减约束条件对线性规划的影响及其实际的应用，从而使企业管理得到合理性和科学性的发展。四、研究的总体安排与进度进度安排序号时间内容12010年12月17日前学生填写任务书、文献综述、文献翻译、开题报告，上传到毕业论文系统22010年12月20日24日初期检查（内容选题、指导教师、任务书、文献综述、开题报告、开题论证结果等32011年4月4日前完成初稿42011年4月4日8日中期检查（内容工作进度、工作
6、态度、纪律情况、翻译文章的原文来源、中期教学检查表、工作过程记录卡、初稿）52011年4月29日前提交定稿62011年4月6至2011年4月15日指导老师完成相关评语和整理资料72011年5月4日答辩五、主要参考文献1吕游运筹学的应用与发展J大庆师范学院,20072陈宝林最优化理论与算法M北京清华大学出版社,20053曾梅清、田大钢线性规划问题的算法综述J科学技术与工程2001,14周凯山、罗毅平两类特殊线性规划算法的改进J系统工程,1998,55展丙军单纯形法的改进及其应用J大庆师范学院学报2007,46金涛,刘三阳,孙小军一种线性规划问题单纯形法的改进算法J2007,127白岩线性规划中两
7、阶段法的简便计算法J长春师范学院学报,20058孙可钦线性规划两阶段法的改进算法J运筹与管理,2000,39夏少刚,刘心线性规划增减约束条件的灵敏度分析J运筹与管理2007,410王昌贵线性规划在企业管理中的应用J大众科技,2004,1211雷红浅谈线性规划在企业管理中的应用J科技情报开发与经济,2000,6412KONSTANTINOSDOSIOS,KONSTANTINOSPAPARRIZOSRESOLUTIONOFTHEPROBLEMOFDEGENERACYINAPRIMALANDDUALSIMPLEXALGORITHMJOPERATIONSRESEARCHLETTERS199713JIA
8、NFENGHUANOTEON“ANIMPROVEDINITIALBASISFORTHESIMPLEXALGORITHM”JCOMPUTERSTWOSTAGEMETHODSENSITIVITYANALYSISENTERPRISEMANAGEMENTAPPLICATIONS11目录摘要9ABSTRACT10目录111引言1211线性规划简介122线性规划问题单纯形法的改进算法1221问题的提出1222单纯形法的改进算法113221算法介绍13222算法分析14223举例1523单纯形法的改进算法219231用矩阵的方法求解线性规划问题19232举例203线性规划问题两阶段法的改进算法2031问题的
9、提出2032两阶段法改进算法121321算法介绍21322举例2333单纯形法的改进算法224331两阶段法的简便算法25332举例254线性规划增减约束条件的灵敏度分析2841引言2842增加约束条件2843减少约束条件2844举例2945灵敏度分析315线性规划在企业管理中的应用3151引言3152线性规划模型的描述和建立32521线性规划模型的描述32522建立生产计划决策分析的线性规划模型3353案例分析34531案例134532案例234533案例33554结论36参考文献37致谢错误未定义书签。附录错误未定义书签。121引言31线性规划简介线性规划是运筹学中研究较早、发展较快、应用
10、广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写为LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制订最佳决策的有力工具。线性规划的算法中，包括单纯形方法、两阶段法、对偶原理与对偶算法、灵敏度分析、分解算法、内点算法，以及整数线性规划等。本文就线性规划中的几种算法进行研究并改进，其中包括单纯形法算法的改进、两阶段
11、法算法的改进，及增减约束条件的灵敏度进行分析，最后讨论线性规划在企业管理中的应用。随着改革开放的不断深入，如何提高企业的经济效益是一个大问题，作为一个企业家，首先当然要根据国际国内市场的信息来确定生产的产品，然后再进行产品的设计和工艺装备的设计研究，提高产品的质量，降低成本并取得广大用户的信誉。同时，在管理中尽量采用现代化的管理方法和电子计算机管理，为提高企业的经济效益寻找出有效的途径。2线性规划问题单纯形法的改进算法21问题的提出单纯形法求解线性规划的问题时，首先要找到一个初始可行基，再用单纯形迭代公式来求最优解。当问题无明显的可行基时，通常是先引入人工变量构造初始可行基，然后再利用两阶段法
12、求解一个辅助问题，来得到一个原问题的一个初始可行基。多年的实践证明，两阶段法虽方便实用，但人工变量的引入不光加大了计算机的贮存量，还增加了计算量。文献中曾采用，基于了高斯消元法的思想，提出了一种不用引入人工变量，直接按一定的规则迭代来求出初始基本可行解或者求出原问题无可行解的改进算法。用单纯形法求线性规划问题时可能产生循环，它提出的单纯形法的改进算法可以有效的避免循环，13且操作简单。22单纯形法的改进算法1221算法介绍线性规划问题XCVTMAXTSBAX0X其中，A是NM阶的矩阵NM，NRX，NRC，MRB且0B。在很多情况下，线性规划问题并没有明显的可行基，通常是采用引入人工变量后用大M
13、法或两阶段法，但都会使计算量增加，同时还增加了计算机的储存量。此外当线性规划问题出现退化时，采用单纯形法可能会产生循环。下面所提出的算法有效的避免了循环，提高了运算速度。步骤1先写出约束方程组的增广矩阵，任取一个大于0的TB，并以第T行的TIBB倍加入到第I行MTTI,1,1,2,1，使第I行的常数项变为0，得到了下表1（J为检验数）；转步骤2。表1IC1C2CNCBBBXC1X2XNX11B12BNB101TA2TATMATB1MB2MBMMB0V12NBBCB1步骤2令1K，对应上表，若NJBKJ,2,1,0，则此行对应的方程则为多余方14程，去掉此行，否则取一个下标J最小且满足0KJB的
14、项，令其为主元实行一次高斯消元，然后将JC和JX写在该行左边BBXC下对应的位置；再令1KK，当TK时，令1TK，重复上述过程一直到K取完从1到M所有的不等于T的整数为止；然后转步骤3。步骤3若第T行元素NJBTJ,2,1,0，结束问题无可行解；否则就考查每一个0THB，倘若存在某个H对应的列满足0IHB（I取从1到M中的不等于T的整数），则以THB为主元进行一次高斯消元，并将HC和HX写在该行左边BBXC下对应的位置，然后按公式）且不等于TMIBBBBTTHIHI,2,10修正常数项，按公式JJBJCPC（JP是修正后的列向量）修正检验数。然后转步骤5；否则就转步骤4。步骤4任取一个0IHB
15、（I取从1到M中的不等于T的整数），实行一次高斯消元，并用HC和HX替换该行左边BBXC下对应的位置的元素，然后转步骤3；步骤5若所有的检验数J0或0，则得到的最优解，否则转步骤6；步骤6找出所有0J对应的列，并按规划确定每列的主元素IJB，并以这些元素为主元进行相应的试算，试算公式是IJIJBB，选择MAXIJIJBB对应的主元IJB为最终的主元迭代，若有几个IJIJBB同时达到最大，就选择JI最小的IJIJBB对应的主元IJB为最终主元进行迭代，然后转步骤5。222算法分析一、准备工作一个基本可行解就是方程组的一个自由变量取零时的非负特解，能否不引入人工变量像解方程组一样来找出这个问题的特
16、解一般说比较困难，就算找到了一个特解也无法保证其可行性，但我们仔细研究一下辅助问题的求解过程，可以注意以下3点。（1）将人工变量逐个从基变量中换出来的过程，就是解辅助问题的过程，每换出一个作一次迭代运算。（2）每作一次迭代运算，就决定了一个非人工变量作基变量，并将其系数列变化为单位向量。15（3）每作一次迭代前总要通过计算“最小比值”来确定主元，以保证基本解的可行性。基于上述几点，可以用高斯消元法的思想，融入一些技巧，则可以把两阶段法的上述步骤省略，以使求解初始可行解与解方程组的高斯消元法几乎无异，可以说做到了最大限度的简化。二、分析过程无基行是，任意找一个常数项大于0的方程在初始表中对应的行
17、。其它方程对应的行则叫做有基行，步骤1实质上是找一个无基行，并进行一次高斯消元，把有基行的常数项都变为零，然后在步骤2中进行以下变动，即在每一个有基行中找出第一个非零元素KJB，接下来以此为主元进行高斯消元，步骤1的作用在这里就体现出来了，因为不管这个非零元素KJB是正是负，由于步骤1已把有基行的常数项均变为零，这样我们以KJB为主元进行消元时就可以保证KJB对应的基变量JX是可行的，因为JX对应的常数项是零，保证了其可行性。同时我们是在每一个有基行中找第一个非零元KJB为主元进行消去，这样可以保证选择的主元不在同一列。对于无基行，我们在步骤3中点明了以下三种情况（1）当无基行在迭代表中对应的
18、TJB，NJ,2,1均小于等于零时，没有可行解。因为无基行对应的常数项TB大于零，且TJNJTJBXB1左边小于等于0而右边大于零，这样就矛盾了；（2）在无基行中选择一个大于零的项THB，如果这项对应的列中所有项IHBI取从1到M中的所有不等于T的整数均小于等于零，就以THB为主元进行高斯消元，同时将HC和HX写在该行左边BBXC下对应的位置，这样各行均为有基行，并且可以保证各行对应的常数项均大于等于零，不仅保证了解的可行性，还找到了一个非负特解即初始可行解；（3）若对于每一个0THB，其所对应的列中有0IHB，则以IHB为主元来进行高斯消元，同时分别用HC和HX替换该行左边BBXC下对应的位
19、置上的元素；再看（2）是否成立，不成立继续进行（3）。223举例3134MAXXXV16TS0463421XXX04651421XXX23221214321XXXX4,3,2,1,0IXI解按照前述程序步骤1先建立初始迭代表，选择第3行为无基行，迭代过程见下表3。表3BCBX1X2X3X4XB1203404323451021121322V1234BBCB141X1203400045000221342V1234BBCB141X12034033X00100020342V1234BBCB141X1000233X0010002X01032117V00008经过4次迭代得到最优解0,1,2X，目标函数的
20、最大值是8；若是用单纯形法求最优解，首先用最大M法求初始可行基，迭代4次后求得初始可行基，然后求原问题的最优解，然后利用单纯形迭代公式再迭代1次，总共迭代5次后才得到最优解0,1,2X；且因为引进了人工变量，所以计算量和储存量都比本算法要大。下面看BEALE给的例子76546212043MAXXXXXVTS0984176541XXXXX0321122176542XXXXX163XX7,2,1,0JXJ利用单纯形法去做经过6次迭代后得到的单纯形表和初始单纯形表一样，做下去将无限循环，这样复杂的多。用本算法去做可以有效的避免循环，那么先按步骤1建立初始迭代表4。表4BCBX1X2X3X4X5X6X
21、7XB1004181900102112213000100101V1234567BBCB1因为BEALE给的这个例子已经有了一个明显的初始可行基，所以可以直接把基变量和相应的系数填在相应的位置，见下表5。表5BCBX1X2X3X4X5X6X7XB1801X10041819002X0102112213003X00100101V00043202160计算相应的检验数得4和6两个检验数均为负数，对这两个检验数对应的列中所有正数项进行试算，最后以6对应的主元1为最终元进行迭代得到下表6。表6BCBX1X2X3X4X5X6X7XB01X10141809102X012121120321216X0010010
22、1V0021432006214小零0，这个检验数对应的列按规则确定主元，最后以21为主元来进行迭代，得下表7。表7BCBX1X2X3X4X5X6X7XB01X1214302021543434X021124061216X00100101V0234502022145发现检验数全是正数，所以这时得到可行解就为最优解，最优解是1,1,43,621）（XXX，最优值是45。由此例可以看出，本算法有效避免了循环。以上例子可以看出改进后的单纯形法有两大优点（1）不用引入人工变量，这样可以减19少计算机的存储量，同时实验证明还降低了运算量，减少了迭代次数；（2）可以避免循环。改进后的单纯形法大幅度的提高了单纯
23、形的效率。23单纯形法的改进算法2上面的单纯形法的改进算法已趋于完善，但在其求最优解的过程中还是有很多值得研究和改进的。上面的方法中，单纯形表很烦琐，计算中，制表会浪费很多的时间。另外，根据不同的类型有大M法、两阶段法，而这两种方法求解过程更麻烦，迭代次数也都较大，还要有很多语言叙述，即便一个很简单的题，要得到最优解，也需要做大量的工作。针对上述问题，本人利用单纯形法的思想，将现有的单纯形法又进行了改进，给出了单纯形表的矩阵形式，用矩阵的行的初等变换来实现求解过程，使方法更容易理解和掌握，求解过程更简捷，并通过例子来展示这种方法的优越性。231用矩阵的方法求解线性规划问题单纯形法的矩阵表示线性
24、规划CXZMAXTSBAX0X其中，NMIJAA）（，TMCCCC）（,21，TMBBBB,21，TNXXXX,21。此线性规划对应的矩阵可以表示为BAC0。要想得到最优解，就要求使检验数为非负的基本可行解，这是最终目标，要想完成此目标，可以有很多方法来实现。BBABBBCCABCBACBB11110通过行的初等变换这个初等变换实际上就是方程组的恒等变形，了解这一点是灵活使用初等变换来求解线性规划的关键。下面用矩阵及矩阵的初等变换法求解线性规划，从而实现单纯形法的改进，方法如下（1）化标准型（指求最大值问题）（2）写出对应的矩阵（3）用行的初等变换得到初始可行矩阵（要确保01BB）20（4）用
25、行的初等变换求出最优阵（此时01CACB）（5）写出最优解和最优值其中（2）、（3）、（4）步是连续的，可合为一步。232举例求解32132MINXXXZTS1221XX131XX0,0,0321XXX解化为标准型32132MAXXXXZTS1221XX131XX0,0,0321XXX写出对应的矩阵并对其进行初等变换2/112/102/102/1120102/112/102/102/121220110110120321312233122/2/RRRRRRR可得最优解2MAX,21,0,21321ZXXX，所以原问题的最优解为2MAX,21,0,21321ZXXX3线性规划问题两阶段法的改进算法
26、31问题的提出求解线性规划问题的第一步，就是寻找一个初始可行基或对偶可行基。一般的处理办法是对约束条件加入松驰变量标准化后再引入人工变量，用大M法或两阶段法求初始可行基或者增加大M约束条件求对偶可行基。引入过多的人工变量必然会增加计算机的存储量和计算量；增加大M约束条件的方法，首先因为M是一个非常大的正数，容易产生计算错误，其次21计算机求解线性规划问题的时间随约束条件数的立方倍数增加，增加约束条件势必延长计算时间。实际问题的模型越大，这个问题就越突出。在文献的启发下，笔者探索出一种先求出问题的一个基，再在最多使用一个人工变量条件下，寻求线性规划问题初始可行基的新算法，这种方法能有效地节约计算
27、机的存储量和计算量。32两阶段法改进算法1321算法介绍因为BX等价于BX，可设实际问题的线性规划模型为LPJNJJXCF10MAXTSNJXMRRIBXARIBXAJNJIJIJNJIJIJ,2,10,2,1,2,1100100引入松弛变量RISI,2,10，将不等式约束条件化为等式RIBSXAIINIJIJ,2,1010步骤1求出约束方程组的一个初始基，这时约束方程组的增广矩阵000201020,202,201,2010,102,101,100020102020220210101012011000000000100010001MMNMMRNRRRRNRRRRRNRRNNBAAABAAABA
28、AABAAABAAABAAAAA分块为2211BOABIAA下部子块22BA正好是后RM个等式构成的方程组的增广矩阵，首先将所有松弛变量定为基变量，以求解后RM个等式构成的方程组为目标，对增广矩阵A进行迭代运算，22得，MMNMRNRRRNRRRRNRNNBAABAABAABAABAABAAA00000000000110000100001022,22,21,12,1222221112其中01,10,1,1/RJRJRAAA；01011/RRRAAB。当1RI时，01,10IJRIJIJAAAA；0110IRIIABBB再以第2R行的第一个非零系数为旋转元对A继续作迭代运算，重复上述运算。设方程
29、组系数矩阵2A的秩为RM，一般重复RM次，可在原决策变量NXXXX,21中得到RM个基变量，它们的系数列与松弛变量的系数列合在一起正好构成一个M阶单位阵MI，取MI为初始基B，相应的基变量记作MIXBI,2,1（；其中前R个是松弛变量）。步骤2考查常数列MIBI,2,10是否成立是此时的基B是原LP的一个初始可行基。将目标函数系数引入，用单纯形法求出最优解。否常数列IB中有负数，该基不可行，则转步骤3。步骤3第一步得到的初始基B为基础，引入一个人工变量Y构造辅助问题1L，其目标函数为Y最小值，约束条件是原问题约束条件经第一步迭代后得到的所有方程等号左端减去Y得到的，即1LYWMINTSMIMR
30、NJYXXXMIBYXXABINJMRNJBIIBINJIJ,2,1,2,10,2,11为非基变量若取负值的常数IB中绝对值最大的一个为KB，即0MAXIIKBBB，则让KBX为出基变量23若值为KB的基变量不止一个，则让其中下标最小的出基，Y为进基变量进行换基迭代，迭代后的约束常数0KKBB；当KI时0KIIBBB得到的基是1L的可行基。用单纯形方法求解辅助问题1L，因为1L有可行解且目标函数有下界，所以1L一定有最优解。该方法是对两阶段法的改进，原理不变，所以两阶段法的一切结论在这里都成立。（1）若1L的最优值0MINW，原问题一定有可行解若1L最优解中Y是非基变量，则1L的最优基就是问题
31、的一个初始可行基；若1L的最优解中Y是基变量，则Y的值一定是零，说明1L有退化解，这时，若Y所在方程中非基变量的系数都为零，则该方程是原问题的多余方程，去掉该方程，得到原问题的一个1M阶的可行基；若Y所在方程中存在系数不为零的非基变量，任取其中一个进基，让Y出基，迭代后能得到原问题的一个初始可行基；（2）1L的最优值0MINW，这时最优解中0Y，说明原问题存在互不相容的约束条件，即系统中的资源不够充分，无法满足要求，原问题无可行解。322举例求解线性规划问题4321222MINXXXXFTS0,61222432143213231XXXXXXXXXXXX解引入松弛变量21,SS将原问题约束条件等
32、式化TS0,6122243214321232131XXXXXXXXSXXSXXBIX1X2X3X4X1S2SYB24W000000101S201010122S021001114X11210016W112100061S311110042S11110105Y11210016W000000101S2521021102112S2123021002123X212112100213F2122000F1201006421XSS、的系数列正好构成一个初始基,该基不可行，加入人工变量Y，构造辅助问题1L，上表迭代三次后得到问题的一个可行基及其对应的单纯形表。该例若采用大M法或两阶段法求解，需引入三个人工变量，至
33、少要迭代四次才能得到原问题的可行基。约束条件越多，迭代次数及迭代时间的差异就越大。运用上述方法求解一般线性规划问题时，若原问题的约束条件全部都是等式，需要迭代的次数可能比两阶段法多一次，但人工变量个数的减少将使迭代时间相应缩短；当原问题中BXAJIJ形式的约束条件个数较多时，使用上述方法的迭代次数将少于其他方法。33单纯形法的改进算法2在文献的启发下，本人认为，根据所给问题尽可能少的引入人工变量，可以使线性规划25问题的计算变得更加简单。331两阶段法的简便算法有些线性规划问题中，引进松驰变量化为标准形后，约束条件方程组的系数矩阵并不含有M阶单位矩阵，这样就会给单纯形解法的换基迭代带来困难。线
34、性规划利用两阶段法解这类问题，尤其是一些具体的实际问题时，对于加入的人工变量,2,1MIYI应该根据问题尽可能的少，使人工变量的个数小于或等于M。本人就线性规划问题的原问题在加入人工变量Y中，如何根据所给问题尽可能的少引人人工变量，来说明线性规划问题两阶段法的简便计算法。需要注意的是尽可能少引人人工变量Y的同时，要保证使问题的约束条件方程组的系数矩阵中有一个可行基，就要根据实际问题，灵活运用两阶段法。332举例线性规划问题3212MAXXXXSTS0,0,06429323213132321XXXXXXXXXX引入松弛变量，将问题转化为标准形式3212MINXXXSTS5,2,106429323
35、15324321JXXXXXXXXXXJ转化后的形式没有一个现成的可行基，因此要用两阶段法解，然后引入下面的辅助问题。21MINYYZTS2,105,2,106429320231253214321321IYJXXXYXXXYXXXXXXXSIJ其中）（87654321,00101100101200100113200000112001PPPPPPPPA，6490B，2600000110C显然，辅助问题有一现成的可行基1B，32711PPPPB，基变量为214,YYXS。对应于基1B的单纯形表为ABBBCBCBBCBTBB1111111）（1BTS1Y2Y1X2X3X4X5XZ1000012201
36、S0100211004X9000231101Y4010021012Y600110100检验数CABCB111有正数，进行换基迭代，得对应于新基32412PPPPB的单纯形表为，2BTS1Y2Y1X2X3X4X5XZ21100002125211S9100022101X29000123212101Y4010021012Y2300102323210检验数仍有正数，继续换基迭代，得到对应于新基35413PPPPB的单纯形表3BTS1Y2Y1X2X3X4X5X27Z29041000492143S5110003111X230430104521232X2021001210212Y29043100492143
37、检验数仍然有正数，继续换基迭代，得对应于新基65414PPPPB的单纯形表4BTS1Y2Y1X2X3X4X5XZ001100000S1110430003101X4031951009212132X10319201091313X2031940019231单纯形表4BT的检验数已全非正，所以基4B为辅助问题的最优基，0MINZ，同时基65414PPPPB的基变量无Y变量，所以）（321,PPPB为原问题的可行基，对应的单纯形表为）（BT1X2X3X4X5XS110003101X41009212132X101091313X20019231检验数已全非正，故,321PPPB为原问题的最优基，对应的最优解
38、为280,0,2,1,454321XXXXX，目标函数的最小值为11S，所以原线性规划问题的最优解为2,1,4321XXX，目标函数的最大值为11SS。从上面的解题过程可以看出，对于线性规划约束方程组的系数矩阵中不含有M阶单位矩阵，求初始可行基的方法。问题转化后，注意约束条件的结构，尽可能少的引入人工变量Y，可以使方法更灵活些，也使得线性规划问题中的两阶段法的解题过程更加简单明了。4线性规划增减约束条件的灵敏度分析41引言设线性规划问题CXFMINBAX（1）0X现实世界是不断发展变化的，主要体现在约束条件上，增加或减少约束条件则是随时可能发生的。这将导致最优方案的变化，如不与时俱进，及时做相
39、应调整，必将造成经济损失。本文在灵敏度分析的基础上，面对增加和减少约束条件的情形，给出新的最优方案。42增加约束条件设增加的一个约束条件为11212111MNNMMMBXAXAXA（2）在原问题的最优表给出的数据中，增加一行，然后用消去法，把这行中基变量的系数消为零，这显然对检验数没有影响，可化为仅缺少一个基变量且NJJ,1,0的问题，故可用对偶单纯形法规则，对新增之行确定主元，实行GAUSS消元，便得一正解，然后用对偶单纯形法迭代求最优解。如果增加的约束不止一个，可一一处理。43减少约束条件减少约束条件的问题，和增加约束条件一样重要。减少约束条件还有特殊的经济意义。29对于资源利用问题来看，
40、它意味着解除对某些资源的限制；而对于工厂里又相当于去掉一道工序，这些都为创新增值提供了途径或指示了方向，故值得详细讨论。当需要减少一个约束条件时，并不是将最优表中与该约束相应的行去掉就可以了，因为此约束的影响已通过GAUSS消元施加在其它各行里了。如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢设初始单纯形表中含有一个单位矩阵，不妨假设它是由辅助变量形成的，现在要去掉原约束条件BAX中的一个约束，不妨设为第T个约束，采用以下步骤（1）考虑原第T个约束所加辅助变量TY这一列，即（NT）列，若TY为基变量，则去掉最优表中第T个约束行和（NT）列即可。否则，若该列某系列0TM，取TNLLTN
41、ITNIII,0MAX（3）若MITNI,1,0,，则取TNLLTNITNIII,0MAX（4）然后以TLN为主元实行GAUSS消元，并去掉主元所在L行与TN列。（2）检查新检验数是否仍非正是，则已得去掉原第T个约束后的最优解；否，用单纯形法迭代求优。44举例某工厂去年根据市场需求和自身生产能力可以生产A、B两种产品，当时的条件如下表所示表1资源利用消耗表A（千克）B（千克）资源可供应量电（度）53210设备（台时）1150劳动力（小时）715630流动资金（百元）080324单位利润（百元）4330据之可确定问题的初始单纯形表和最优表如下表2例题的初始单纯形表和最优解1X2X1Y2Y3Y4Y
42、1Y5310002102Y110100503Y71500106304Y0803000124F43000001X2X1Y2Y3Y4Y1X1003/502182X0108/502323Y00099/5116244Y0019/50424F00012/502168今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制。问应如何调整生产，才能获得最大利润由初始表4知关于流动资金的约束方程是第4个，相应松驰变量是4Y，故考虑最优表中4Y一列，由（3）得424424,232MAX故应以446为主元，实行GAUSS消元，然后去掉4行，6列得1X2X1Y2Y3Y1X101/23/203031
43、2X011/25/20203Y004271120F001/23/20180这已经是最优表，按它进行调整，可增加利润18016812（百元）。45灵敏度分析在如今市场经济的现实情况下，产品的市场价格条件、拥有的资源量以及企业的技术都有可能发生变化，这就需要管理者在这些条件发生变化时也随着将原有生产计划作相应调整。（1）产品的市场价格变化分析产品市场发生变化，必将导致单件利润C也随着变化，现分两种情况研究。根据检验数计算公式JBJJPBCC1可知，它将会影响非基变量的检验数。若想使原最优解不变，根据单纯形法的计算原理可知，须0J，一旦0J，原最优生产计划将会发生改变，可以通过改进最优单纯形表来求出
44、新的最优计划。（2）资源量的变化分析资源量对应的线性规划模型中的IB，即求IB的灵敏度分析，由以前学的运筹学的灵敏度分析知道，劳动工时资源的拥有量在9,4/9范围内变化时，原最优生产计划中安排生产的产品种类不变；而原材料的拥有量在12,3范围内变化时，原最优生产计划中安排生产的产品种类不变；一旦资源的拥有量超出上述各自的约束范围，则可根据线性规划的知识在原计划的基础上来重新调整生产计划。（3）技术条件的变化分析技术条件对应的是线性规划模型中的IJA，生产某种产品的技术条件发生变化，将会影响到产品的检验数或者现有生产产品法重新调整。5线性规划在企业管理中的应用51引言一个企业要在市场竞争中立于不
45、败之地，就必须改善经营管理，提高经济效益，其中包32括怎样合理的安排生产任务、合理配置资源，怎样制定最优的生产计划，并对瞬息万变的市场信息及时作出反应。随着计算机技术的普及，线性规划的数学方法在企业管理中的应用范围也越来越广泛。在企业生产和经济管理的领域中，人们常会遇到这样的问题，如何从一切可能的方案中选择最好、最优的方案，在数学上把这类问题称为最优化问题。在当今的商品经济环境下，解决这类问题是一个关系到国计民生的重要问题。线性规划探讨的问题是在由所提出问题的性质决定的一系列约束条下，如何把有限的人力、物力、设备、资金等资源进行合理的分配，制定出最忧实施方案。在企业的各项活动中，例如计划、生产
46、、运输、技术等问题。为达到目的所采用的各种手段，从各种限制条件的组合中，选择出最为合理的计算方法，从而求得最佳结果。决策变量、约束条件、目标函数是线性规划的三要素。52线性规划模型的描述和建立在运筹学的发展过程中，线性规划给了工业运筹学一个重要的援助，它已经被广泛应用于生产企业、化工、交通、邮电、建筑、医药等经济管理的领域中。企业、政府部门的许多工作都使用了线性规划方法，并且取得了丰硕的成果。线性规划被广泛应用的原因主要有三个（1）在各个领域中有大量的问题可以或近似可以用线性规划模型表示；（2）存在可用的求解线性规划问题的有效方法；（3）通过线性规划模型，利用灵敏度分析容易处理数据的变化问题。521线性规划模型的描述线性规划问题是一个优化问题，其数学依据为（1）用一组未知数NXXX，21表示某一方案，这组未知数的一组定值代表一个具体方案，通常要求这些未知数取值是非负的。（2）存在一定的限制条件，这些限制条件可以用一组线性等式或不等式来表达。（3）都有一个目标要求，并且这个目标可以表示一组未知数的线性函数，根据问题的不同，要求函数实现最大化或者最小化。从而建立了线性规划的数学模型NNNXCXCXCXXXF221121，33满足约束条件0,2122112222212111212111NMNMNMMNNNNXXXBXAXAXABXAXAXABXAXAXA
