1、本科毕业设计（20届）线性规划算法的改进及在企业管理中的应用所在学院专业班级数学与应用数学学生姓名学号指导教师职称完成日期年月I摘要【摘要】线性规划是运筹学最基本、运用最广泛的分支，是其他运筹学问题研究的基础。线性规划的算法有若干种，本文仅对其中的几种算法进行改进并研究。首先介绍了线性规划问题中的单纯形法和两阶段法的算法改进，并对这两种方法进行了分析和举例说明，然后对线性规划增减约束条件的灵敏度进行分析，最后说明线性规划在企业管理中的应用。线性规划的“线性”特点，简化了数学模型的构造和解题方法，容易被一般未具有高等数学知识的各级企业管理人员所掌握应用，特别是计算机的广泛应用，线性规划的在企业管
2、理中的应用范围更加广泛和深入，渐渐成为管理人员必须掌握的一门现代化管理方法和优化技术。【关键词】单纯形法；两阶段法；灵敏度分析；企业管理应用。ABSTRACT【ABSTRACT】LINEARPROGRAMMINGISTHEMOSTBASICOPERATIONSRESEARCH,THEMOSTWIDELYUSEDBRANCHOPERATIONSRESEARCHPROBLEMSINOTHERRESEARCHLINEARPROGRAMMINGALGORITHMHASSEVERAL,THISISONLYAFEWOFTHEALGORITHMISIMPROVEDANDSTUDYTHISPAPERFIRST
3、INTRODUCEDALGORITHMIMPROVEMENTOFTHESIMPLEXMETHODANDTWOSTAGEMETHODINTHELINEARPROGRAMMINGQUESTIONANDCARRIEDONTOTHESETWOMETHODSHASANALYZEDANDCARRIESONEXPLAINSWITHEXAMPLESTHENITANALYSISDTHESENSITIVITYOFADDINGORDELETINGCONDITIONOFLINEARPROGRAMMINGFINALLYITEXPLAINSTHEAPPLICATIONOFLINEARPROGRAMMINGINTHEBUS
4、INESSMANAGEMENTLINEARPROGRAMMING“LINEAR“FEATURESTOSIMPLIFYTHEMATHEMATICALMODELOFTHESTRUCTUREANDPROBLEMSOLVINGMETHOD,ACCESSIBLETOTHEGENERALKNOWLEDGEOFHIGHERMATHEMATICSISNOTABUSINESSMANAGEMENTSTAFFATALLLEVELSMASTERTHEAPPLICATION,INPARTICULAR,EXTENSIVEUSEOFCOMPUTERS,LINEARPROGRAMMINGINBUSINESSMANAGEMEN
5、TWIDERANDDEEPERRANGEOFAPPLICATIONS,MANAGERSMUSTGRADUALLYBECOMEAMASTEROFMODERNMANAGEMENTMETHODSANDOPTIMIZATIONTECHNIQUES【KEYWORDS】SIMPLEXMETHODTWOSTAGEMETHODSENSITIVITYANALYSISENTERPRISEMANAGEMENTAPPLICATIONSII目录摘要IABSTRACTI目录II1引言111线性规划简介12线性规划问题单纯形法的改进算法121问题的提出122单纯形法的改进算法12221算法介绍2222算法分析3223举例4
6、23单纯形法的改进算法27231用矩阵的方法求解线性规划问题7232举例83线性规划问题两阶段法的改进算法931问题的提出932两阶段法改进算法19321算法介绍9322举例1133单纯形法的改进算法213331两阶段法的简便算法13332举例134线性规划增减约束条件的灵敏度分析1641引言1642增加约束条件1643减少约束条件1744举例1745灵敏度分析195线性规划在企业管理中的应用1951引言1952线性规划模型的描述和建立20521线性规划模型的描述20522建立生产计划决策分析的线性规划模型2053案例分析21531案例121532案例222533案例32254结论23参考文献
7、24致谢错误未定义书签。III附录错误未定义书签。11引言11线性规划简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写为LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制订最佳决策的有力工具。线性规划的算法中，包括单纯形方法、两阶段法、对偶原理与对偶算法、灵敏度分析、
8、分解算法、内点算法，以及整数线性规划等。本文就线性规划中的几种算法进行研究并改进，其中包括单纯形法算法的改进、两阶段法算法的改进，及增减约束条件的灵敏度进行分析，最后讨论线性规划在企业管理中的应用。随着改革开放的不断深入，如何提高企业的经济效益是一个大问题，作为一个企业家，首先当然要根据国际国内市场的信息来确定生产的产品，然后再进行产品的设计和工艺装备的设计研究，提高产品的质量，降低成本并取得广大用户的信誉。同时，在管理中尽量采用现代化的管理方法和电子计算机管理，为提高企业的经济效益寻找出有效的途径。2线性规划问题单纯形法的改进算法21问题的提出单纯形法求解线性规划的问题时，首先要找到一个初始
9、可行基，再用单纯形迭代公式来求最优解。当问题无明显的可行基时，通常是先引入人工变量构造初始可行基，然后再利用两阶段法求解一个辅助问题，来得到一个原问题的一个初始可行基。多年的实践证明，两阶段法虽方便实用，但人工变量的引入不光加大了计算机的贮存量，还增加了计算量。文献中曾采用，基于了高斯消元法的思想，提出了一种不用引入人工变量，直接按一定的规则迭代来求出初始基本可行解或者求出原问题无可行解的改进算法。用单纯形法求线性规划问题时可能产生循环，它提出的单纯形法的改进算法可以有效的避免循环，且操作简单。222单纯形法的改进算法1221算法介绍线性规划问题XCVTMAXTSBAX0X其中，A是NM阶的矩
10、阵NM，NRX，NRC，MRB且0B。在很多情况下，线性规划问题并没有明显的可行基，通常是采用引入人工变量后用大M法或两阶段法，但都会使计算量增加，同时还增加了计算机的储存量。此外当线性规划问题出现退化时，采用单纯形法可能会产生循环。下面所提出的算法有效的避免了循环，提高了运算速度。步骤1先写出约束方程组的增广矩阵，任取一个大于0的TB，并以第T行的TIBB倍加入到第I行MTTI,1,1,2,1，使第I行的常数项变为0，得到了下表1（J为检验数）；转步骤2。表1IC1C2CNCBBBXC1X2XNX11B12BNB101TA2TATMATB1MB2MBMMB0V12NBBCB1步骤2令1K，对
11、应上表，若NJBKJ,2,1,0，则此行对应的方程则为多余方程，去掉此行，否则取一个下标J最小且满足0KJB的项，令其为主元实行一次高斯消元，然后将JC和JX写在该行左边BBXC下对应的位置；再令1KK，当TK时，令1TK，重复上述过程一直到K取完从1到M所有的不等于T的整数为止；然后转步骤3。步骤3若第T行元素NJBTJ,2,1,0，结束问题无可行解；否则就考查每一个0THB，3倘若存在某个H对应的列满足0IHB（I取从1到M中的不等于T的整数），则以THB为主元进行一次高斯消元，并将HC和HX写在该行左边BBXC下对应的位置，然后按公式）且不等于TMIBBBBTTHIHI,2,10修正常数
12、项，按公式JJBJCPC（JP是修正后的列向量）修正检验数。然后转步骤5；否则就转步骤4。步骤4任取一个0IHB（I取从1到M中的不等于T的整数），实行一次高斯消元，并用HC和HX替换该行左边BBXC下对应的位置的元素，然后转步骤3；步骤5若所有的检验数J0或0，则得到的最优解，否则转步骤6；步骤6找出所有0J对应的列，并按规划确定每列的主元素IJB，并以这些元素为主元进行相应的试算，试算公式是IJIJBB，选择MAXIJIJBB对应的主元IJB为最终的主元迭代，若有几个IJIJBB同时达到最大，就选择JI最小的IJIJBB对应的主元IJB为最终主元进行迭代，然后转步骤5。222算法分析一、准
13、备工作一个基本可行解就是方程组的一个自由变量取零时的非负特解，能否不引入人工变量像解方程组一样来找出这个问题的特解一般说比较困难，就算找到了一个特解也无法保证其可行性，但我们仔细研究一下辅助问题的求解过程，可以注意以下3点。（1）将人工变量逐个从基变量中换出来的过程，就是解辅助问题的过程，每换出一个作一次迭代运算。（2）每作一次迭代运算，就决定了一个非人工变量作基变量，并将其系数列变化为单位向量。（3）每作一次迭代前总要通过计算“最小比值”来确定主元，以保证基本解的可行性。基于上述几点，可以用高斯消元法的思想，融入一些技巧，则可以把两阶段法的上述步骤省略，以使求解初始可行解与解方程组的高斯消元
14、法几乎无异，可以说做到了最大限度的简化。二、分析过程无基行是，任意找一个常数项大于0的方程在初始表中对应的行。其它方程对应的行则叫做有基行，步骤1实质上是找一个无基行，并进行一次高斯消元，把有基行的常数项都变为零，然后在步骤2中进行以下变动，即在每一个有基行中找出第一个非零元素KJB，接下来以此为主元进行高4斯消元，步骤1的作用在这里就体现出来了，因为不管这个非零元素KJB是正是负，由于步骤1已把有基行的常数项均变为零，这样我们以KJB为主元进行消元时就可以保证KJB对应的基变量JX是可行的，因为JX对应的常数项是零，保证了其可行性。同时我们是在每一个有基行中找第一个非零元KJB为主元进行消去
15、，这样可以保证选择的主元不在同一列。对于无基行，我们在步骤3中点明了以下三种情况（1）当无基行在迭代表中对应的TJB，NJ,2,1均小于等于零时，没有可行解。因为无基行对应的常数项TB大于零，且TJNJTJBXB1左边小于等于0而右边大于零，这样就矛盾了；（2）在无基行中选择一个大于零的项THB，如果这项对应的列中所有项IHBI取从1到M中的所有不等于T的整数均小于等于零，就以THB为主元进行高斯消元，同时将HC和HX写在该行左边BBXC下对应的位置，这样各行均为有基行，并且可以保证各行对应的常数项均大于等于零，不仅保证了解的可行性，还找到了一个非负特解即初始可行解；（3）若对于每一个0THB
16、，其所对应的列中有0IHB，则以IHB为主元来进行高斯消元，同时分别用HC和HX替换该行左边BBXC下对应的位置上的元素；再看（2）是否成立，不成立继续进行（3）。223举例3134MAXXXVTS0463421XXX04651421XXX23221214321XXXX4,3,2,1,0IXI解按照前述程序步骤1先建立初始迭代表，选择第3行为无基行，迭代过程见下表3。表3BCBX1X2X3X4XB51203404323451021121322V1234BBCB141X1203400045000221342V1234BBCB141X12034033X00100020342V1234BBCB141
17、X1000233X0010002X010321V00008经过4次迭代得到最优解0,1,2X，目标函数的最大值是8；若是用单纯形法求最优解，首先用最大M法求初始可行基，迭代4次后求得初始可行基，然后求原问题的最优解，然后利用单纯形迭代公式再迭代1次，总共迭代5次后才得到最优解0,1,2X；且因为引进了人工变量，所以计算量和储存量都比本算法要大。下面看BEALE给的例子76546212043MAXXXXXVTS0984176541XXXXX60321122176542XXXXX163XX7,2,1,0JXJ利用单纯形法去做经过6次迭代后得到的单纯形表和初始单纯形表一样，做下去将无限循环，这样复杂
18、的多。用本算法去做可以有效的避免循环，那么先按步骤1建立初始迭代表4。表4BCBX1X2X3X4X5X6X7XB1004181900102112213000100101V1234567BBCB1因为BEALE给的这个例子已经有了一个明显的初始可行基，所以可以直接把基变量和相应的系数填在相应的位置，见下表5。表5BCBX1X2X3X4X5X6X7XB01X10041819002X0102112213003X00100101V00043202160计算相应的检验数得4和6两个检验数均为负数，对这两个检验数对应的列中所有正数项进行试算，最后以6对应的主元1为最终元进行迭代得到下表6。表6BCBX1X
19、2X3X4X5X6X7XB01X101418091702X012121120321216X00100101V0021432006214小零0，这个检验数对应的列按规则确定主元，最后以21为主元来进行迭代，得下表7。表7BCBX1X2X3X4X5X6X7XB01X1214302021543434X021124061216X00100101V0234502022145发现检验数全是正数，所以这时得到可行解就为最优解，最优解是1,1,43,621）（XXX，最优值是45。由此例可以看出，本算法有效避免了循环。以上例子可以看出改进后的单纯形法有两大优点（1）不用引入人工变量，这样可以减少计算机的存储量
20、，同时实验证明还降低了运算量，减少了迭代次数；（2）可以避免循环。改进后的单纯形法大幅度的提高了单纯形的效率。23单纯形法的改进算法2上面的单纯形法的改进算法已趋于完善，但在其求最优解的过程中还是有很多值得研究和改进的。上面的方法中，单纯形表很烦琐，计算中，制表会浪费很多的时间。另外，根据不同的类型有大M法、两阶段法，而这两种方法求解过程更麻烦，迭代次数也都较大，还要有很多语言叙述，即便一个很简单的题，要得到最优解，也需要做大量的工作。针对上述问题，本人利用单纯形法的思想，将现有的单纯形法又进行了改进，给出了单纯形表的矩阵形式，用矩阵的行的初等变换来实现求解过程，使方法更容易理解和掌握，求解过
21、程更简捷，并通过例子来展示这种方法的优越性。231用矩阵的方法求解线性规划问题单纯形法的矩阵表示线性规划CXZMAX8TSBAX0X其中，NMIJAA）（，TMCCCC）（,21，TMBBBB,21，TNXXXX,21。此线性规划对应的矩阵可以表示为BAC0。要想得到最优解，就要求使检验数为非负的基本可行解，这是最终目标，要想完成此目标，可以有很多方法来实现。BBABBBCCABCBACBB11110通过行的初等变换这个初等变换实际上就是方程组的恒等变形，了解这一点是灵活使用初等变换来求解线性规划的关键。下面用矩阵及矩阵的初等变换法求解线性规划，从而实现单纯形法的改进，方法如下（1）化标准型（
22、指求最大值问题）（2）写出对应的矩阵（3）用行的初等变换得到初始可行矩阵（要确保01BB）（4）用行的初等变换求出最优阵（此时01CACB）（5）写出最优解和最优值其中（2）、（3）、（4）步是连续的，可合为一步。232举例求解32132MINXXXZTS1221XX131XX0,0,0321XXX解化为标准型32132MAXXXXZTS1221XX131XX0,0,0321XXX9写出对应的矩阵并对其进行初等变换2/112/102/102/1120102/112/102/102/121220110110120321312233122/2/RRRRRRR可得最优解2MAX,21,0,21321
23、ZXXX，所以原问题的最优解为2MAX,21,0,21321ZXXX3线性规划问题两阶段法的改进算法31问题的提出求解线性规划问题的第一步，就是寻找一个初始可行基或对偶可行基。一般的处理办法是对约束条件加入松驰变量标准化后再引入人工变量，用大M法或两阶段法求初始可行基或者增加大M约束条件求对偶可行基。引入过多的人工变量必然会增加计算机的存储量和计算量；增加大M约束条件的方法，首先因为M是一个非常大的正数，容易产生计算错误，其次计算机求解线性规划问题的时间随约束条件数的立方倍数增加，增加约束条件势必延长计算时间。实际问题的模型越大，这个问题就越突出。在文献的启发下，笔者探索出一种先求出问题的一个
24、基，再在最多使用一个人工变量条件下，寻求线性规划问题初始可行基的新算法，这种方法能有效地节约计算机的存储量和计算量。32两阶段法改进算法1321算法介绍因为BX等价于BX，可设实际问题的线性规划模型为LPJNJJXCF10MAXTSNJXMRRIBXARIBXAJNJIJIJNJIJIJ,2,10,2,1,2,1100100引入松弛变量RISI,2,10，将不等式约束条件化为等式RIBSXAIINIJIJ,2,101010步骤1求出约束方程组的一个初始基，这时约束方程组的增广矩阵000201020,202,201,2010,102,101,100020102020220210101012011
25、000000000100010001MMNMMRNRRRRNRRRRRNRRNNBAAABAAABAAABAAABAAABAAAAA分块为2211BOABIAA下部子块22BA正好是后RM个等式构成的方程组的增广矩阵，首先将所有松弛变量定为基变量，以求解后RM个等式构成的方程组为目标，对增广矩阵A进行迭代运算，得，MMNMRNRRRNRRRRNRNNBAABAABAABAABAABAAA00000000000110000100001022,22,21,12,1222221112其中01,10,1,1/RJRJRAAA；01011/RRRAAB。当1RI时，01,10IJRIJIJAAAA；01
26、10IRIIABBB再以第2R行的第一个非零系数为旋转元对A继续作迭代运算，重复上述运算。设方程组系数矩阵2A的秩为RM，一般重复RM次，可在原决策变量NXXXX,21中得到RM个基变量，它们的系数列与松弛变量的系数列合在一起正好构成一个M阶单位阵MI，取MI为初始基B，相应的基变量记作MIXBI,2,1（；其中前R个是松弛变量）。步骤2考查常数列MIBI,2,10是否成立是此时的基B是原LP的一个初始可行基。将目标函数系数引入，用单纯形法求出最优解。11否常数列IB中有负数，该基不可行，则转步骤3。步骤3第一步得到的初始基B为基础，引入一个人工变量Y构造辅助问题1L，其目标函数为Y最小值，约
27、束条件是原问题约束条件经第一步迭代后得到的所有方程等号左端减去Y得到的，即1LYWMINTSMIMRNJYXXXMIBYXXABINJMRNJBIIBINJIJ,2,1,2,10,2,11为非基变量若取负值的常数IB中绝对值最大的一个为KB，即0MAXIIKBBB，则让KBX为出基变量若值为KB的基变量不止一个，则让其中下标最小的出基，Y为进基变量进行换基迭代，迭代后的约束常数0KKBB；当KI时0KIIBBB得到的基是1L的可行基。用单纯形方法求解辅助问题1L，因为1L有可行解且目标函数有下界，所以1L一定有最优解。该方法是对两阶段法的改进，原理不变，所以两阶段法的一切结论在这里都成立。（1
28、）若1L的最优值0MINW，原问题一定有可行解若1L最优解中Y是非基变量，则1L的最优基就是问题的一个初始可行基；若1L的最优解中Y是基变量，则Y的值一定是零，说明1L有退化解，这时，若Y所在方程中非基变量的系数都为零，则该方程是原问题的多余方程，去掉该方程，得到原问题的一个1M阶的可行基；若Y所在方程中存在系数不为零的非基变量，任取其中一个进基，让Y出基，迭代后能得到原问题的一个初始可行基；（2）1L的最优值0MINW，这时最优解中0Y，说明原问题存在互不相容的约束条件，即系统中的资源不够充分，无法满足要求，原问题无可行解。322举例求解线性规划问题4321222MINXXXXF12TS0,
29、61222432143213231XXXXXXXXXXXX解引入松弛变量21,SS将原问题约束条件等式化TS0,6122243214321232131XXXXXXXXSXXSXXBIX1X2X3X4X1S2SYBW000000101S201010122S021001114X11210016W112100061S311110042S11110105Y11210016W000000101S2521021102112S2123021002123X212112100213F2122000F1201006421XSS、的系数列正好构成一个初始基,该基不可行，加入人工变量Y，构造辅助问题1L，13上表迭代
30、三次后得到问题的一个可行基及其对应的单纯形表。该例若采用大M法或两阶段法求解，需引入三个人工变量，至少要迭代四次才能得到原问题的可行基。约束条件越多，迭代次数及迭代时间的差异就越大。运用上述方法求解一般线性规划问题时，若原问题的约束条件全部都是等式，需要迭代的次数可能比两阶段法多一次，但人工变量个数的减少将使迭代时间相应缩短；当原问题中BXAJIJ形式的约束条件个数较多时，使用上述方法的迭代次数将少于其他方法。33单纯形法的改进算法2在文献的启发下，本人认为，根据所给问题尽可能少的引入人工变量，可以使线性规划问题的计算变得更加简单。331两阶段法的简便算法有些线性规划问题中，引进松驰变量化为标
31、准形后，约束条件方程组的系数矩阵并不含有M阶单位矩阵，这样就会给单纯形解法的换基迭代带来困难。线性规划利用两阶段法解这类问题，尤其是一些具体的实际问题时，对于加入的人工变量,2,1MIYI应该根据问题尽可能的少，使人工变量的个数小于或等于M。本人就线性规划问题的原问题在加入人工变量Y中，如何根据所给问题尽可能的少引人人工变量，来说明线性规划问题两阶段法的简便计算法。需要注意的是尽可能少引人人工变量Y的同时，要保证使问题的约束条件方程组的系数矩阵中有一个可行基，就要根据实际问题，灵活运用两阶段法。332举例线性规划问题3212MAXXXXSTS0,0,06429323213132321XXXXX
32、XXXXX引入松弛变量，将问题转化为标准形式3212MINXXXSTS5,2,10642932315324321JXXXXXXXXXXJ转化后的形式没有一个现成的可行基，因此要用两阶段法解，然后引入下面的辅助问题。21MINYYZ14TS2,105,2,106429320231253214321321IYJXXXYXXXYXXXXXXXSIJ其中）（87654321,00101100101200100113200000112001PPPPPPPPA，6490B，00000110C显然，辅助问题有一现成的可行基1B，32711PPPPB，基变量为214,YYXS。对应于基1B的单纯形表为ABBB
33、CBCBBCBTBB1111111）（1BTS1Y2Y1X2X3X4X5XZ1000012201S0100211004X9000231101Y4010021012Y600110100检验数CABCB111有正数，进行换基迭代，得对应于新基32412PPPPB的单纯形表为，2BTS1Y2Y1X2X3X4X5XZ21100002125211S9100022101X29000123212101Y401002101152Y2300102323210检验数仍有正数，继续换基迭代，得到对应于新基35413PPPPB的单纯形表3BTS1Y2Y1X2X3X4X5XZ29041000492143S5110003
34、111X230430104521232X2021001210212Y29043100492143检验数仍然有正数，继续换基迭代，得对应于新基65414PPPPB的单纯形表4BTS1Y2Y1X2X3X4X5XZ001100000S1110430003101X4031951009212132X10319201091313X2031940019231单纯形表4BT的检验数已全非正，所以基4B为辅助问题的最优基，0MINZ，同时基65414PPPPB的基变量无Y变量，所以）（321,PPPB为原问题的可行基，对应的单纯形表为）（BT1X2X3X4X5XS110003101X4100921213162X
35、101091313X20019231检验数已全非正，故,321PPPB为原问题的最优基，对应的最优解为0,0,2,1,454321XXXXX，目标函数的最小值为11S，所以原线性规划问题的最优解为2,1,4321XXX，目标函数的最大值为11SS。从上面的解题过程可以看出，对于线性规划约束方程组的系数矩阵中不含有M阶单位矩阵，求初始可行基的方法。问题转化后，注意约束条件的结构，尽可能少的引入人工变量Y，可以使方法更灵活些，也使得线性规划问题中的两阶段法的解题过程更加简单明了。4线性规划增减约束条件的灵敏度分析41引言设线性规划问题CXFMINBAX（1）0X现实世界是不断发展变化的，主要体现在
36、约束条件上，增加或减少约束条件则是随时可能发生的。这将导致最优方案的变化，如不与时俱进，及时做相应调整，必将造成经济损失。本文在灵敏度分析的基础上，面对增加和减少约束条件的情形，给出新的最优方案。42增加约束条件设增加的一个约束条件为11212111MNNMMMBXAXAXA（2）在原问题的最优表给出的数据中，增加一行，然后用消去法，把这行中基变量的系数消为零，这显然对检验数没有影响，可化为仅缺少一个基变量且NJJ,1,0的问题，故可用对偶单纯形法规则，对新增之行确定主元，实行GAUSS消元，便得一正解，然后用对偶单纯形法迭代求最优解。如果增加的约束不止一个，可一一处理。1743减少约束条件减
37、少约束条件的问题，和增加约束条件一样重要。减少约束条件还有特殊的经济意义。对于资源利用问题来看，它意味着解除对某些资源的限制；而对于工厂里又相当于去掉一道工序，这些都为创新增值提供了途径或指示了方向，故值得详细讨论。当需要减少一个约束条件时，并不是将最优表中与该约束相应的行去掉就可以了，因为此约束的影响已通过GAUSS消元施加在其它各行里了。如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢设初始单纯形表中含有一个单位矩阵，不妨假设它是由辅助变量形成的，现在要去掉原约束条件BAX中的一个约束，不妨设为第T个约束，采用以下步骤（1）考虑原第T个约束所加辅助变量TY这一列，即（NT）列，若T
38、Y为基变量，则去掉最优表中第T个约束行和（NT）列即可。否则，若该列某系列0TM，取TNLLTNITNIII,0MAX（3）若MITNI,1,0,，则取TNLLTNITNIII,0MAX（4）然后以TLN为主元实行GAUSS消元，并去掉主元所在L行与TN列。（2）检查新检验数是否仍非正是，则已得去掉原第T个约束后的最优解；否，用单纯形法迭代求优。44举例某工厂去年根据市场需求和自身生产能力可以生产A、B两种产品，当时的条件如下表所示表1资源利用消耗表A（千克）B（千克）资源可供应量电（度）53210设备（台时）1150劳动力（小时）715630流动资金（百元）080324单位利润（百元）43据
39、之可确定问题的初始单纯形表和最优表如下表2例题的初始单纯形表和最优解181X2X1Y2Y3Y4Y1Y5310002102Y110100503Y71500106304Y0803000124F43000001X2X1Y2Y3Y4Y1X1003/502182X0108/502323Y00099/5116244Y0019/50424F00012/502168今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制。问应如何调整生产，才能获得最大利润由初始表4知关于流动资金的约束方程是第4个，相应松驰变量是4Y，故考虑最优表中4Y一列，由（3）得424424,232MAX故应以446为
40、主元，实行GAUSS消元，然后去掉4行，6列得1X2X1Y2Y3Y1X101/23/20302X011/25/20203Y004271120F001/23/2018019这已经是最优表，按它进行调整，可增加利润18016812（百元）。45灵敏度分析在如今市场经济的现实情况下，产品的市场价格条件、拥有的资源量以及企业的技术都有可能发生变化，这就需要管理者在这些条件发生变化时也随着将原有生产计划作相应调整。（1）产品的市场价格变化分析产品市场发生变化，必将导致单件利润C也随着变化，现分两种情况研究。根据检验数计算公式JBJJPBCC1可知，它将会影响非基变量的检验数。若想使原最优解不变，根据单纯
41、形法的计算原理可知，须0J，一旦0J，原最优生产计划将会发生改变，可以通过改进最优单纯形表来求出新的最优计划。（2）资源量的变化分析资源量对应的线性规划模型中的IB，即求IB的灵敏度分析，由以前学的运筹学的灵敏度分析知道，劳动工时资源的拥有量在9,4/9范围内变化时，原最优生产计划中安排生产的产品种类不变；而原材料的拥有量在12,3范围内变化时，原最优生产计划中安排生产的产品种类不变；一旦资源的拥有量超出上述各自的约束范围，则可根据线性规划的知识在原计划的基础上来重新调整生产计划。（3）技术条件的变化分析技术条件对应的是线性规划模型中的IJA，生产某种产品的技术条件发生变化，将会影响到产品的检
42、验数或者现有生产产品法重新调整。5线性规划在企业管理中的应用51引言一个企业要在市场竞争中立于不败之地，就必须改善经营管理，提高经济效益，其中包括怎样合理的安排生产任务、合理配置资源，怎样制定最优的生产计划，并对瞬息万变的市场信息及时作出反应。随着计算机技术的普及，线性规划的数学方法在企业管理中的应用范围也越来越广泛。在企业生产和经济管理的领域中，人们常会遇到这样的问题，如何从一切可能的方案中选择最好、最优的方案，在数学上把这类问题称为最优化问题。在当今的商品经济环境下，解决这类问题是一个关系到国计民生的重要问题。线性规划探讨的问题是在由所提出问题的性质决定的一系列约束条下，如何把有限的人力、
43、物力、设备、资金等资源进行合理的分配，制定出最忧实施方案。在20企业的各项活动中，例如计划、生产、运输、技术等问题。为达到目的所采用的各种手段，从各种限制条件的组合中，选择出最为合理的计算方法，从而求得最佳结果。决策变量、约束条件、目标函数是线性规划的三要素。52线性规划模型的描述和建立在运筹学的发展过程中，线性规划给了工业运筹学一个重要的援助，它已经被广泛应用于生产企业、化工、交通、邮电、建筑、医药等经济管理的领域中。企业、政府部门的许多工作都使用了线性规划方法，并且取得了丰硕的成果。线性规划被广泛应用的原因主要有三个（1）在各个领域中有大量的问题可以或近似可以用线性规划模型表示；（2）存在
44、可用的求解线性规划问题的有效方法；（3）通过线性规划模型，利用灵敏度分析容易处理数据的变化问题。521线性规划模型的描述线性规划问题是一个优化问题，其数学依据为（1）用一组未知数NXXX，21表示某一方案，这组未知数的一组定值代表一个具体方案，通常要求这些未知数取值是非负的。（2）存在一定的限制条件，这些限制条件可以用一组线性等式或不等式来表达。（3）都有一个目标要求，并且这个目标可以表示一组未知数的线性函数，根据问题的不同，要求函数实现最大化或者最小化。从而建立了线性规划的数学模型NNNXCXCXCXXXF221121，满足约束条件0,2122112222212111212111NMNMNM
45、MNNNNXXXBXAXAXABXAXAXABXAXAXA522建立生产计划决策分析的线性规划模型生产计划决策分析的基本方法是以利润最大化作为优化目标，明确未知变量，确定约束条件，建立线性规划模型，最终实现企业效益最大化的生产计划。其一般模式为目标函数为利润P销售收入R（成本费用）C在各个约束条件下，使目标函数达最大值。分析企业生产过程中的日产量情况，设模型的未知变量为企业生产产品种类日产量,2,1NJXJ，建立生产计划决策分析线性规划模型过程如下（1）目标函数。企业进行生产计划决策的目标值是企业利润最大化。假设生产各种产品所获得的销售收入JR与所耗费的产品成本和费用JC均已知，则可以得出生产
46、计划问题的目标函数为21JNJJJNNNXCRXCRXCRXCRP1222111MAX（2）原材料约束。无论是生产何种产品都需要消耗一定的原材料，在实际中企业若需耗用多种原材料则可根据原材料的种类，增添相应约束条件即可，建立约束不等式11212111BXAXAXANN其中NAAA11211,分别为生产第1,2,N种产品的单件原材料消耗量，1B为企业每可用的原材料总量。（3）生产能力约束。此约束具体表现为企业的可用工时或可用设备工时，而企业在一定时期内可用工时是有限的，所以可建立如下约束不等式22222121BXAXAXANN其中NAAA22221,分别为生产第1,2,N种产品的单件消耗工时，2B为企业的日可用的工时、料总量。（4）市场需求约束。为使问题方便，假设企业生产的产品市场都有需求，即021NXXX，无上限约束。若第J种产品市场需求有限，最大需求为JD，则可增加约束JJDX。（5）非负约束。生产实际中最多即为不生产产品，所以所有变量0,2,1NJXJ。53案例分析为了研究生产计划决策分析线性规划模型在企业实际中的应用，给出几个算例并简要介绍线性规划模型的建立及求解过程。531案例1应用举例某企业用甲乙两种原料生产A、B、C、D等4种产品，每种产品
