经济管理中一类LP问题的改进单纯形法

经济管理中一类LP问题的改进单纯形法 经济管理中一类 LP 问题的改进单纯形法 马舰，张劲松 ,九 江 学 院 理 学 院 江 西 九 江 ,332005 摘 要,经济管理中的 LP 问题常含有大量的自由变量。对于 LP 问题中的自由变量，常将其化为非负变 量再实施单纯形法。通过研究单纯形法迭代过程中自由变量变换的规律，提出一种能有效节省存贮空 间和提高运算速度的改进单纯形法。 关键词,LP 问题;自由变量;单纯形法 中图分类号:O221.1 文献标识码:A 文章编号:1001-711(92012)07-0023-02 Improved Simplex Method about Linear Programming with Free Variable MA Jian，ZHANG Jinsong (Collegeof Science, Jiujiang University, Jiujiang 332005, China)Abstact,Linear Programming in economy and managemceonntta ion ftae lnot of freeva riables. For freev ariables in Linear r Programming often turn theinmto nonnegative variables and theinm plemetn Simplex method Through research r uthlee o f free ,-. variables in the process it eroatfi on on Simplex method after they wturerneed , offered ainm proved Simplex Method thit acat n effectively save storage spacei nacnredas e operation speed. Key words,linear programming; freev ariable; simplex method 本来规模就很大的问题再度增大规模。因此，研 引言0 究 x,x'-x''(x'?0，x''?0)在单纯形法迭代过 kk k kk 程中的规律，从而省略这一工作而直接由 x参与 k 考 虑LP 含 自 由变量的问题 : ?T迭代运算，具有重要的现实意义。 ? minz,cx ? ? ?T ? s,t,i,1，…,m (1) ax,b i i ?? ? ? 1 x?0 算法思想j,1，…,q(1?q?n) ?j TT T 其中 x,(x，…，x)，c,(c，…，c)，a为 1n1ni m×n实 矩阵 A 的第 i 个行向量，不妨设秩 A=m， 引理 1.1 若原始 LP 问题(1)中的自由变量个 T ?? 数大于或等于方程个数，则其对偶问题的自由变 D= xax,b，i,1，…,m，x0，j,1，…,q 覫，同时 ??i ij A 中已含有一个单位矩阵 I ，b0 (i,1，…,m)。 量个数小于或等于方程个数。 ?i 对问题(1)，由[2]对自由变量 x(k,q，1，…，n) 证明:若在问题(1)中有 n,q?m，则 m?n,q ，k 作变换 x,x'-x''(x'0，x''0)，即可将其化为 ??由对偶理论，即对偶问题的自由变量个数m 小于kk k kk 非负变量，从而启动单纯形法。但这样做显然增或等于方程个数 n,q。 证毕。加了问题的规模。特别是许多生产实践和实际生 由引理 1.1，只需考虑问题(1)所含自由变量 个数小于或等于 m 的情形。不失一般性，假定问活中的问题，自由变量的个数很多，这样将使得 收 稿 日 期 ,2011-11-12 作 者 简 介 ,马舰(1965-女)，副教授，硕士，研究方向:运筹学，E-mail: majian111@sina.com 24 科 技通 报第 28 卷 题(1)仅含一个自由变量 x,(q,1?k?n)，则有: 定理 1.3 与单纯形法相比，用本文所述改进 k 定理 1.2 若含自由变量 x的 LP 问题(1)有最 单纯形法(见第 2 节)求解含有(n)q)个自由变量 k 优解，则必定有 x(或)x)入基，或 x对应的检验数 的问题(1)至少减少 O(mnl)次运算，其中l 为 单纯 kkk 为零。 形法迭代步数。 证明:对问题(1)列出初始单纯形表。若自由 证明:由定理 1.2 不难看出，对于问题(1)的每 变量 x是非基变量，检验数为ζ ，对应的 A 中列 个自由变量，相比单纯形法来说，改进单纯形法 k k 向量为 A。作变换 x,x'-x''(x'c，x''?0)，则 每一步迭代减少了一列元素之间的运算，即 1 次 k kk k kk x、x的检验数分别为 ζ、ζ，对应的 A 中列向 乘法和 m 次加法，若需要 (l 1)步迭代才得到最 '''-?kk kk 优解，则减少 量分别为 A、-A。 m(l,1)次运算，当然算法中的以)x kk k 按最小比值规则确定 x(sk)为入基变量，替代 x又增加了 m,1次 乘以()1)的工作，所以 ?k s 至少共减少(m)1)(l,1)次运算。因此，含有(n)q) x为出基变量，作旋转运算得x '、x''的检验数分r kk 个自由变量的问题aa(1)至少减少(n)q)(m)1)(l,1) rk rk 别为 ζ) ζ、 ζ+ ζ。-ksks a a rsrs (即 O(mnl))次运算。 证毕。 若它们均为零，得证;否则，它们均不为零且 [3]互为相反数，必有一个大于零，由最优性准则， 算例4 此时的解不是最优解。依此迭代下去，要消除正 的检验数，只有 x'、x''入基。 ?kk ? minz,x) 4x 1 2? ?而由单纯形表显然有x 和)x( 或)x和 ''''k k k ? ? s,,t-3x +x +x =9 ?1 2 3 ?例 1 求解 LP 问题: x'')对应的列(包括检验数)完全一致，因此在表中 ?k? x+2x+x=10 124 ?? 可共用一列。而这两列合并后对应的变量为 x) ' ?k ?x ?0 ? 2 x(或)x,x)，即为 x(或)x)。所以，若 x入基，''''''kkk kkk 8 * 解:用改进单纯形法求解，得最优解x =() ， 则 x入基;若 x''入基，则)x入基。 证毕。k k k 7 39)，迭代过程见表 1，以x替代 x见表 2 -1 1 7 2 算法表 1 单纯形法求解迭代过程 1 Table1 Simple methodto solve the iterative processof 1 由定理 1.2 知，不必对 x,(k,q,1，…，n)作变 k xxxxb 1 2 3 4换 x,x')x''(x'?0，x''?0)，直接列出初始单纯 kkk kkz -1 4 0 0 0 形表，进入下述算法(改进单纯形法): -3 1 1 0 9 第 1 步 找一个初始的可行基;10 1 2* 0 0 求出对应的典式及检验数向量; 第 2 步 0 0 -20 -3-2 ??7 1 ; 第 3 步 求 ζ=max ζ j,1，…,n 0 1 4 t j- - 2 2 11 1 0 5 若 ζ?0，转第 5 步;否则，转第 6 步; 第 4 步 t2 2 第 5 步 若 x(或)x)入基，或 x对应的检验kkk 表 2 单纯形法求解迭代过程 2 数 ζ为零，停止，已得最优解;否则，考察作为非 k Table1 Simple methodto solve the iterative processof 2 基变量的自由变量 x，以)x替代 x，相应地在单 kk k -xxxxb 1 2 3 4纯形表中以-ζ替代 ζ，以- A替代 A，转第 3 k kk kz 3 0 0 -2 -20 步; 7 1 1 4 0 *- 2 2 11 第 6 步 若 A0，停止，已得最优解;否则，?1 0 5 - k2 2 11 164 6 - 0 - 0 - x入基，转第 7 步;t 7 7 7 8 1 2 - 0 1 7 7 7 第 7 步 由最小比值规则确定出基变量x ， r 3 39 1 0 1 7 7 7 旋转，得新的可行基，转第2 步; ,下转第 27 页, 3 算法复杂性分析 27 第 7 期 李小飞等.某些单叶函数子类的若干性质 P L Duren.Univalent Functions [M].New York/Berlin/ functions with negativ ecoefficients [J].Tr J of [2] Heidelberg/Tokyo:Springer-Verlag,1983. Mathematics,1998,22:15-32. Kim H S,Lee S K.Some classes of univ alent functions [J]. Sarangi S M, Uralegaddi B A.The radiusof convexity and [3] [8] Math Japan.1987,32:78-7916. starlikeness for certain classesof analytic functionswith [4] O Altintas,S Owa.On subclassesof uni valent functionswith negative coefficients [J].Rend Acad Naz Lincei , negative Coefficients [J].Pusan Kyongnam Math 88,4: J,191978,65:38-42. 41-46. [A] Amiri,H.S.On a subclassof clos e-to-convex functions [9] M D Hur,G H Oh.On certain classof anal ytic functions with negativecoefficient s[J].Mathematica(Cluj),1989,3(11): [5] with negative Coefficients [J].Pusan Kyongnam Math J. 1-7. 1989,5:69-80. N Uyanik,S Owa,Ekrem Kadioglu.Some properties of [10] H Silverman.Univalent functionswith negati ve coefficients functions associatedwith close-to-convex and starlike [6] [J].Proc Amer MathSoc, 9175,51:109-116. of order [J].Applied Mathematics and Computation, M K Aouf,NakEun Cho.On a certain subclassof anal ytic [7] 2010,216:38187. -3 ,上接第 24 页, 一个化归。 5 结束语 参考文献, 本文所给算法的实质是:在单纯形法迭代过 Dantzig,G.B.Linear programming extensions[M]. Princeton: [1] 程中，省略了自由变量 x经变换后的 x'(或 x'') k k k Princeton University Press,1963 . 及其相应的列。对于规模很大且自由变量个数很 教材编写组.运筹学(修订版)[M].北京,清华大学出版社.[2] 多的问题，这样做将节省大量的存贮空间，并显 1990.1 刁在筠,郑汉鼎,刘家壮等.运筹学[M].北京,高等著地提高运算速度。虽然算法是针对自由变量个 教育出 版社.2001.9 数不超过 的情形，但正如本文第1 节一开始的引 [3] 理 1.1 所说，相反的情形完全可以由对偶理论作