《线性规划算法的改进与在企业管理中的应用.doc》由会员分享，可在线阅读，更多相关《线性规划算法的改进与在企业管理中的应用.doc（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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. . maxxbAxtsxcvT其中是阶的矩阵()，且Anmnm xnRcnRbnRb0在许多情况下，线性规划问题并无明显的可行基，通常是引入人工变量后采用大M 法或两阶段法，但都将使计算量增加，同时增加计算机的储存量，而且当线性规划晋中学院数学学院 2008 届本科生毕业论文问题出现退化时，采用单纯形法可能产生循环下面所提出的算法可以有效的避免循环，提高运算速度步骤
8、 1：写出约束方程组的增广矩阵，任取一个大于 0 的，并以第 t 行(该行tb称为无基行) 的-倍加入到第 行( i = 1，2， ， - 1， +1， ， m) ，使第 行ti bbiitti的常数项变为 0，(为检验数) ；转步骤 2j步骤 2：令 = 1，若= 0，j = 1，2， ，n，则此行对应的方程为多余方程，kkjB去掉此行，否则取一个下标最小的且满足0 的项令其为主元实行一次高斯消元，jkjB同时将和写在该行左边下对应的位置；令 = +1，当= 时令 = +1，jcjxBBxckkktkt重复上述过程直到取完从 1 到所有不等于 的整数为止；转步骤 3kmt步骤 3：若第 行元
9、素0， = 1，2， ，结束，问题无可行解；否则考ttjB jn查每一个 0，若存在某个 H 对应的列满足0( 取从 1 到中的不等于 的整tjBiHBimt数) ，则以为主元进行一次高斯消元，同时将和写在该行左边下对应的iHBHcHxBBxc位置，并按公式=-0( = 1，2， m 且不等于 t) 修正常数项，按公式=ibt tHiHbBBij(是修正后的列向量) 修正检验数，然后转步骤 5；否则转步骤 4jjBcpcjp步骤 4：任取一个 0( 取从 1 到 中的不等于 的整数) ，实行一次高斯iHBimt消元，同时用和替换该行左边下对应位置的元素，然后转步骤 3；HcHxBBxc步骤 5
10、：若所有的检验数大于或等于 0，则得到最优解否则转步骤 6；j步骤 6：找出所有 0，其所对应的列中有 0，则以为主元进行高斯tHBiHBiHB消元，同时用和替换该行左边下对应的位置上的元素；再看(2) 是否成立，HcHxBBxc不成立继续进行(3) 下述定理可以保证在有限步迭代后若问题有可行解，则步骤 3 中的第二种情况成立；定理定理 1 步骤 4 经有限步迭代后产生两种情况：(1) 该问题没有可行解； (2) 找到一个初始可行解证明 对于经步骤 2 消元后的初始表的无基行最右边引入人工变量，以及在表y中检验数上一行内引入辅助目标函数 = ，同时修正 ，并把其对于各变量的检验zyic数依次写
11、入相应位置，且在最下方填入Bxz若不看人工变量这一列，则原来的无基行第 行与第一阶段的目标函数行对应的yt项均相等，第 行的系数， = 1，2， ，n 就是相应的检验数，且在主元选在第ttjaj行之前上述对应关系不变因此无基行中的正系数所在列按最小比值选主元时，自然t等价于第一阶段目标函数 行的正检验数所在列按最小比值选主元，所以当0， ztjaj= 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-3max1x3x3-6+4=0. .ts1x2x4x晋中学院数学学院 2008 届本科生毕业论文1.5-0.5=31x3x+-=2211x2x213x324x0 i =1，2，3，4ix 解 按照前述程序步骤 1 先建立初始迭代表，选择第 3 行为无基行，迭代过程见下表 1.1，1.2，1.3，1.4经过 4 次迭代得到最优解 x=
15、(2，1，0)，目标函数的最大值是-8；表 1.1BcBx1x2x3x4xb1-204/303/4-3/2-5/4101/211/2-2/32v1234bBcB1表 1.2BcBx1x2x3x4xb-41x1-204/3000-5/400021/2-4/32v1234bBcB1表 1.3BcBx1x2x3x4xb-41x1-204/30-33x00100020-4/32v1234bBcB1表 1.4晋中学院数学学院 2008 届本科生毕业论文BcBx1x2x3x4xb-41x10002-33x0010002x010-2/31v0000-8如果是用单纯形法求最优解时，首先用大 M 法求初始可行基
16、，迭代 4 次求的初始可行基，然后再求原问题的最优解，利用单纯形迭代公式再迭代 1 次，总共迭代 5 次才得到最优解 x = (2，1，0) ；且由于引进了人工变量，所以计算量和储存量都比本算法大下面看 Beale 给的例子Max v = -20+-6434x5x216x7xst +-8-+9=01x41 4x5x6x7x+-12-+3=02x21 4x5x21 6x7x+=13x6x0 j=1，2，7.jx利用单纯形法去做经过 6 次迭代得到的单纯形表和初始单纯形表一样，做下去将无限循环，下面用本算法去做可以有效的避免循环，先按步骤 1 建立初始迭代表 2表 2BcBxBxBxBxBxBxB
17、xBxb1001/4-8-1900101/2-12-1/230001001011111111bBcB1因为 Beale 给的这个例子已经有一个明显的初始可行基，所以可直接把基变量和晋中学院数学学院 2008 届本科生毕业论文相应的系数填在相应的位置，见下表 3表 3BcBxBxBxBxBxBxBxBxb01x1001/4-8-19002x0101/2-12-1/23003x00100101v000-3/420-1/260同时计算相应的检验数得和两个检数均为负数，所以对这两个检验数对应的46列中所有正数项进行试算，最后以对应的主元 1 为最终主元进行迭代得下表 44表 4BcBxBxBxBxBx
18、BxBxBxb01x1011/4-809002x011/21/2-12031/21/23x00100101v001/2-3/420061/2小于 0，这个检验数对应的列按规则确定主元，最后以为主元进行迭代得下421表 5表 5BcBxBxBxBxBxBxBxBxb01x1-1/23/40-2015/23/43/44x0211-240611/26x00100101v03/25/402021/25/4检验数全是正数，所以这时得到可行解为最优解，最优解为(，) = 1x4x6x晋中学院数学学院 2008 届本科生毕业论文(，1，1) ，最优值为由此例可以看出，本算法可以有效避免循环431.4 结论结
19、合上面的例子可以看出改进后的单纯形法主要有两大优点：(1)不用引入人工变量 ，这样减少了计算机的存储量 ，同时实验证明还降低了运算量减少了迭代次数；(2)可以避免循环；所以改进后的单纯形法大幅度的提高了单纯形的效率2.线性规划问题两阶段法的改进算法2.1 引言对于线性规划问题.)0(0. .minbxbAxtscxf用两阶段法求初始基可行解时，首先要在问题(1) 中引入人工变量，使约束方程组的系数矩阵中含有单位矩阵，用以作为人造基一般来说，有个相互独立的约束方程就m需引入个人工变量，但若系数矩阵中含有单位列向量，引入的人工变量则可减少，m例如：.)4 , 3 , 2 , 1(010421852
20、152. .23min432131321321 ixxxxxxxxxxtsxxxfi由于变量的系数构成的列向量为单位向量(0，0，1) ，所以只要引入两个人工4xT变量，可以直接作为人造基中的一个基变量4x一般说来，若约束矩阵中含有个单位列向量，则可少引入个人工变量能否尽kk量减少人工变量的个数，节省存储空间和计算量？基于这一思路，通过对线性规划问题增广矩阵的初等行变换，使约束方程组的系数矩阵中尽可能多的出现单位列向量，最后只须引进一个人工变量 (虚设) 即可求得初始基可行解2.2 算法第 1 步：建立初始单纯形表晋中学院数学学院 2008 届本科生毕业论文第 2 步：用初等行变换将初始单纯形
21、表简化由于0 且不全为 0，不妨设ib 0，以 所在行为基准行，分别乘以该行的 - ( = 2， ，m) 倍加到第 行，ibib1bbiii使 行的i常数项变为 0第 3 步：用初等行变换产生单位列向量和对应的基变量令= 2，若= 0， kkja= 1， ，n，则令 = +1；否则，任取0(一般可取下标最小的一个) ，以其jkkkjaj为主元，用初等行变换将其所在列化为单位列向量，并把基变量填在第 k 行左边位jx置，并令=+ 1，重复这一步骤直到=此时，系数矩阵中只有第一行没有产生kkkm基变量，不妨设产生的- 1 个基变量是， ，m2x3xmx第 4 步：对应的线性规划问题，在第 1 个约
22、束方程中引入一个人工变量，构造y人造基(， ， ，) ， 用两阶段法求解y2x3xmx2.3 算例例 求解线性规划问题 .)4 , 3 , 2 , 1(093412. .3min432432132131ixxxxxxxxxxxtsxxf问题的最优解为，最优解为求解过程见表T Txxxx 0 ,23,25, 0),(4321236.1，6.2，6.3，6.4，6.5，6.6.表 6.1Bx1x2x3x4x1-21-1041111晋中学院数学学院 2008 届本科生毕业论文93-631-3010表 6.2Bx1x2x3x4x1-21-1009-351018-6101-3010表 6.3Bx1x2x
23、3x4x1x101/31/92/901-1/35/91/90000-1008/31/3表 6.4Bx1x2x3x4x1x101/31/904x01-1/35/900000100-18/30表 6.5Bx1x2x3x4x2x3011/301x1102/30晋中学院数学学院 2008 届本科生毕业论文4x0000130030表 6.6Bx1x2x3x4x2x5/2-1/21003x3/23/20104x00001-3/2-9/20003.线性规划增减约束条件的灵敏度分析设线性规划问题. (1)0minXbAXCXf由于现实世界是不断发展变化的，体现在约束条件上，增加或减少约束条件则是随时可能发生的
24、这将导致最优方案的变化，如不与时俱进，及时做相应调整，必将造成经济损失本文在灵敏度分析的基础上，面对增减约束条件的情形，给出新最优方案的获得方法3.1 增加约束条件设增加的一个约束条件为(2)11212111mnnmmmbxaxaxa则应在原问题的最优表(2)提供的数据，增加一行，然后用消去法，把这行中基变量的系数消为 0，这显然对检验数没有影响，从而可化为仅缺少一个基变量且= 1， 0jj， n 的问题，故可沿用对偶单纯形法或联合算法的规则，于新增之行确定主元，实行 Gauss 消元，便得一正则解，继之用对偶单纯形法迭代求优如果增加的约束不止一个，可一并处理3.2 减少约束条件晋中学院数学学
25、院 2008 届本科生毕业论文对于减少约束条件的问题，大多的教材和其它文献都没有涉及事实上它和增加约束一样重要减少约束条件还有特殊的经济意义对于资源利用问题，它意味着解除对某些资源的限制，而在工厂里又相当于去掉一道工序，这些都为创新增值提供途径或指示方向，故值得详细讨论当需要减少一个约束时，并不是将最优表中，与该约束相应的行去掉就可以的，因为此约束的影响已通过 Gauss 消元施加在其它各行里了那么，如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢?设初始单纯形表中含有一个单位矩阵，不妨假定它是由辅助变量(松弛变量，剩余变量或人工变量等)形成， 现在要去掉原约束条件中的一个约束，不妨设
26、为第bAX 个约束，则对上表应采取如下步骤：t考虑原第 个约束所加辅助变量 这一列，即()列，若 为基变量，01ttytn ty则去掉最优表中第 个约束行和()列即可(此时最优解与最优值均不变) 否则，若ttn 该列某系数0，取tni,(3)tnll tni tniii , ,0max若则取, 1, 0,mitni(4)tnll tni tniii , ,0min然后以为主元实行 Gauss 消元，并去掉主元所在之 行与列tnl,ltn 考察新检验数是否仍非正，是，则已得去掉原第 个约束后的最优解；否，用02t单纯形法迭代求优3.3 算例某工厂去年根据市场需求和自身生产能力可以生产 A ，B
27、两种产品，当时的条件如下表所示表 7 资源利用消耗表晋中学院数学学院 2008 届本科生毕业论文A (千克)B (千克)资源可供应量电（度） 设备（台时） 劳动力（小时） 流动资金（百元）5 1 7 083 1 15 03210 50 630 24 单位利润（百元）43据之可确定问题的初始单纯形表和最优表如下：表 8 例题的初始单纯形表和最优表表 91X2X1Y2Y3Y4Y1X1005302182X010580-2323Y000599116241Y001590-424f0005120-2-168今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制试问应如何调整生产，才能获
28、得最大利润?由初始表 4 知关于流动资金的约束方程是第 4 个，相应松驰变量是，故考虑4y最优表中一列，由(3)得4y424 424,232max 1X2X1Y2Y3Y4Y1Y5310002102Y110100503Y71500106304Y0803000124f4300000产品单 位 消 耗资源晋中学院数学学院 2008 届本科生毕业论文应以 为主元，实行 Gauss 消元，然后去掉 4 行，6 列得446表 10 去掉约束后的单纯形表1X2X1Y2Y3Y1X1021230302X0121250203Y004271120f0021230180这已经是最优表，按它进行调整，可增加利润 180
29、 - 168 =12(百元) 注意：由(3)知，主元所在之行未必一定是原约束中要去掉的那一行，如在例 1 中，若因进口设备而欲将第二个约束去掉，计算结果，主元是，因而消元之后，59934去掉的却是第三行此外，之所以先考虑 (3)式是因为去掉约束，一般将使目标函数值减少，但绝不会增大方法的原理是很简单的，通过比较，不难看出，初始表中将要去掉的约束行所加辅助变量那一列仅有一个 1 而其余都是 0，而在最优表中该列一般将发生变化，说明将要去掉的约束行的影响已经通过迭代施加到别的行中注意，若从一开始就去掉那个约束，则所加辅助变量那一列全为 0，并且在迭代中保持不变；因此，只有经过上面的处理，使所加辅助
30、变量那一列又全变回为 0，要去掉之约束在单纯形迭代中对其它约束施加的影响(即指此行的若干倍加于其它诸行)才被消除此外，按照(3)或(4)选主元是为了保证所得解的可行性如果初始表中没有单位矩阵，注意到前面的分析只涉及辅助变量一列，它由单ty位列向量最后变成的第 列，检验数由 0 变为因此，这时只需在最优1Bt1 tP1 tBPC表中增加一辅助列，对该列重复和的过程即可稍有不同的是，若 11tBt PCP01021 tBPC0，则用(3)式选主元；不然，则用(4)式选主元此外，还应注意需先将基变量所在列晋中学院数学学院 2008 届本科生毕业论文调整成单位矩阵后按新的变量位置确定，再进行计算BC3
31、.4 灵敏度分析在市场经济的现实情况中，产品的市场价格条件，拥有的资源量，以及企业的技术都有可能发生一定的变化，这就需要管理者在这些条件发生变化时也随着将原有生产计划作相应调整3.4.1 产品的市场价格发生变化产品的市场发生变化，必将导致单件利润 C 也随着变化，现分两种情况来研究根据检验数计算公式可知，它将会影响非基变量的检验数，若jBjjPBCC1要想原最优!解不变，根据单纯形法的计算原理可知，必须一旦，原最0j0j优生产计划将会发生改变，可以通过改进最优单纯形表来求出新的最优计划3.4.2 资源量的变化分析.资源量对应的线性规划模型中的右端常数，亦即求的灵敏度分析，由运筹学ibib的灵敏
32、度分析可知，劳动工时资源的拥有量在9/4，9范围内变化时原最优生产计划中安排生产的产品种类不变：而原材料的拥有量在3，12范围内变化原最优生产计划中安排生产的产品种类不变；一旦资源的拥有量超出上述各自的约束范围，则可以根据线性规划的知识在原生产计划的基础上重新调整生产计划3.4.3 技术条件的变化分析技术条件对应的是线性规划模型中的，生产某种产品的技术条件发生变化，将ija会影响到产品的检验数或者现有生产产品法重新调整4.线性规划在企业管理中的应用一个企业要在市场竞争中立于不败之地，就必须改善经营管理，提高经济效益，具体包括怎样合理安排生产任务，配置资源，怎样制定最优的生产计划，并对瞬息万变的
33、市场信息及时作出反应随着计算机技术的普及，线性规划的数学方法在企业管晋中学院数学学院 2008 届本科生毕业论文理中应用的范围越来越广泛，线性规划产生于三十年代未和四十年代初，并随着现代科技和管理实践的发展而不断发展是运筹学中起源较早，理论上较成熟的一个分支线性规划的“线性”特点，简化了数学模型的构造和解题方法，容易被一般未具有高等数学知识的各级企业管理人员所掌握应用特别是计算机的广泛应用，线性规划的在企业管理中的应用范围更加广泛和深入，渐渐成为管理人员必须掌握的一门现代化管理方法和优化技术4.1 线性规划的概念和构成要素线性规划探讨的问题是在由所提出问题的性质决定的一系列约束条件下，如何把有
34、限的资源进行合理的分配，制定出最优实施方案在企业的各项管理活动中，例如计划、生产、运输、技术等问题，线性规划是指从各种限制条件的组合中选择出最为合理的计算方法，从而求得最佳结果决策变量、约束条件、目标函数是线性规划的三要素决策变量是指决策问题需要控制的因素，一般称为决策变量例如，要考虑怎样确定不同产品的产量才能获得最大利润的问题，不同产品的产量可设为变量的多少，取决于决策问题的要求，一般地说，决策变量越多，越nXXX21,能反映实际问题，但求解也就越复约束条件是指实现目标的限制条件，艰制条件是多种多样的例如确定不同产品的产量时，会受到劳动力、设备能力、原材料等的限制因此要充分考虑约束条件在满足
35、约束条件下实现决策目标约束条件有“” “” “ ”几种类型约束条件越多，考虑问题越周到目标函数是指把决策的目标用变量之间的函数关系式表示出来目标函数有最大值和最小值两种形式如果设目标函数为 S，则求 Max(s)和 Min(s)最大值和最小值统称为最优值4.2 线性规划在企业管理中的应用范围企业的效益依赖于资源配置的优化，即依赖于线性规划模型的优化优化的范围晋中学院数学学院 2008 届本科生毕业论文越大，效果也就越好首先，线性规划可用于生产计划确定后的优化，包括确定最佳库存量，产品的最大利益，最佳效率和最小费用等等其次，利用线性规划支持企业未来的决策，管理者必须分析未来的经济走势，分析未来的
36、消费趋势并预测同行的产销动向，然后确定自己的产品价格，广告与促销策略，最后再将这些数据进行线性规划，这是求解一个随机线性规划问题4.3 线性规划问题求解方法介绍所谓线性规划问题，简单地说就是求一组决策变量在满足一组线性等式或不等式的约束条件下的值，使线性目标函数的值达到最优的数学方法线性规划常用的解法有两种对于比较简单的只含有两个变量的线性规划问题，以用图解法求出最优值对于三个以上的变量的线性规划问题，可以用单纯形法求解图解法虽然较容易，但它可以为单纯形法提供理论基础单纯形法比较繁杂，变量越多，计算起来步骤越多，然而可以用电子计算机来进行数据处理4.4 运用线性规划方法进行企业管理中应注意的问
37、题4.4.1 设定最优解中非零变量个数与约束条件个数应用线性规划对实际问题进行优化，都是在一定的约束条件之下进行的不容忽视的是线性规划模型所得的最优解中非零变量的数目 n 不会超过模型的约束条件数目m 如果我们采用线性规划方法建模，根据所给的条件又只能得到 m 个约束方程，那么，这样建立的模型的最优解如果存在，就最多只能有 m 个非零分量如果在应用中忽视了这个结论，而将由模型求得的最优解不加分析地付诸实施，常常会带来不良的后果 挪威在开始用线性规划方法编制经济发展计划时，由于忽视了这一点，最优解中许多商品的指标是零，使得规划失效给管理造成了巨大混乱和损失4.4.2 目标函数中的价值系数在许多实
38、际企业管理中的线性规划问题中，目标函数=或=中 和MaxZcxMinZxcc分别为利润系数向量和成本系数向量，们都是与一定的价格相联系的，线性规划的c目标实质上是一种货币形式表现的价值目标在一个较合理的价格体系中，价格一般是晋中学院数学学院 2008 届本科生毕业论文能够代表商品的价值的但在有些情况下，价格又不能正确地反映商品的价值，不同的人对商品的价值定义不同另外，有些服务工作是不经过买卖的，因而也不存在着市场价格问题我们需要注意的是，这些价格的不确定性，绝不是意味这些服务所用的产品在目标函数中的价值系数为零，而是我们在确定目标函数中的利润系数或成本系数所涉及到的价格时，在实际价格的基础上适
39、当地加以调整，或者调高或者降低，这样模型所得到的最优计划才有实际意义4.4.3 线性规划模型的静态性当我们用线性规划的理论和方法去研究某个部门或地区的发展规划时，其模型具有静态性，但这只是近似的严格说来，模型中所涉及到的价格并非常数这说明线性规划模型的静态性是近似的，既然是近似的，所以在实际的应用中，考虑问题误差的大小，划定问题的界限是必要的在企业资金、技术、设备等其它条件不变的情况下，合理安排人力物力和资金，合理组织生产经营，统筹规划，求得最佳效益，是线性规划技术得以在企业管理中发挥作用的重要原因目前，我国对于这方面的运用还不成熟，需要学术人员加强同企业的合作调研，进一步开发实际运用晋中学院
40、数学学院 2008 届本科生毕业论文参考文献1 胡运权运筹学基础及应用M北京：清华大学出版社，20042 潘平奇，李炜，王涌基于最钝角规则的亏基对偶单纯形 I 阶段算法J运筹学学报，2004，(2)3 陈宝林最优化理论与算法M北京：清华大学出版社，200550 - 744 夏少刚对单纯形算法的两点改进意见J运筹学，1990(2) ：27228 5 张干宗线性规划 M武汉：武汉大学出版社，19881464716 白岩线性规划中两阶段法的简便计算法J长春师范学院学报，2005，24(5)：137 俞玉森数学规划的原理和方法M武汉：华中工学院出版社，19858 范贻昌实用管理运筹学M天津：天津大学出
41、版社，19959 胡运权运筹学教程M北京：清华大学出版社，199810 摩特爱尔玛拉巴 S E运筹学手册(基础和基本原理)M上海：上海科学技术出版社，1987教师评语：教师评语：该论文对古典的线性规划问题中的单纯形算法和两阶段算法作出改进.对于单纯形算法的改进是不用引入人工变量，减少了计算机的存储量，减少了迭代次数，可以有效的避免循环，并提高了运算速度.对于两阶段算法作出改进是在原有的两阶段算法的基础上分析，首先通过对增广距阵进行初等行变换，使约束方程组的系数距阵中尽可能的多出现单位列向量，最后只需引入一个虚设的人工变量就可以得到初始基本可行解.论文还在灵敏度方面给予分析，即在增加与减少约束条件作出论述.对于改进的每一种方法都给出相应的例子做详细的阐述，并在经济模型中作了应用.晋中学院数学学院 2008 届本科生毕业论文