中图分类号：O221C93文献标识码：A
An aplication of minimum ratio rwiddle iteration algorithm
in production planning
CAO Xi-yu
(Business shool,Shan Tou University,Shan Tou Guang Dong 515063)
Abstract:With an example of applying minimum ratio rwiddle iteration algorithm in making production planning,a simple and easy to apply method of working and the optimun solution to the linear programming is put forword.
Key word:minimum ratio twiddle iteration algorithm,production plannling.
一、方法简述
对于一个线性规划问题的标准形式
(1)
我们通常利用单纯形法求解，但单纯形法需要在一个基本可行解的情况下进行，且当基本可行解出现退化时，还可能产生循环现象。在《数理统计与管理》97年第11期赵学慧等提出用枚举法求解，但此方法对于约束条件个数和变量个数很大时，其计算量是相当大的，且此文中的应用实例的最优解x1=162,x2=135是错的，很容易验证此解不满足第3个约束条件20x1+8x24000。最小值旋转迭代法是利用单纯形法的原理求最优解，但此方法能有效克服上述两种方法的不足，且简单易行，计算量比一般方法更小。
1.1用最小值旋转迭代法求最优解的方法与步骤
线性规划问题的标准形式如(1)所示。
第1步。建立如下初始旋转迭代表格
表1
Cj c1 c2 … cn b
CB XB x1 x2 … xn
a11 a12 … a1n b1
a21 a22 … a2n b2
… … … … …
am1 am2 … amn bm
第2步。若在表1中，存在一行，比如说第t行，对于所有Ijn,有atj0且bt≠0，此时原问题无可行解，停止计算。
第3步。考察所有正数项aij,利用最小比值规则，计算出以此确定主元素atk，作旋
转迭代运算得到如下表2，并在表2中的XB和CB的下方分别填上xk和ck。
表2
Cj c1 c2 … ck … cn b
CB XB x1 x2 … xk … xn
11 12 … 0 … 1n 1
21 22 … 0 … 2n 2
… … … … … … …
ck xk t1 t2 … I … tn t
… … … … … … …
m1 m2 … 0 … mn m
第4步。如果还没有得到一个明显的可行基In,则考察除XB下方所出现的基变量所在行以外的所有正数ij,转入第2步。如果已得到一个明显的可行基In，则按照单纯形法计算检验数的方法计算检验数ζj=CBj-cj(j=1,…，n)(此处j是此时表中xj所对应的系数列向量)，若所有的ζ0，则停止，已找到最优解
1.2最小比值旋转迭代法的几点说明
1.如b中的元素有两个或者两个以上为0时，在利用最小比值法确定atk时，应取b中所有零元素所在行中最大的那个正数。
2.如果有相同的最小比值θ≠0，在确定atk时，应取所对应的ck中较大的那个。
3.如果表中xi所对应的列向量中有单位列向量εi=(0，…，0，1，0，…，0)T时，则确定的atk不能是单位列向量εi中的元素1。
4.如果通过最小比值旋转迭代法进行后得到明显的可行基In，则再利用量小比值法确定的那个tk，其所对应XB中的出基变量xt应是最先进入的。
二、应用实列
对文［1］中提出的线性规化问题应用实例用最小比值旋转迭代法求解。
Max L=800x1+=650x2
将此规化问题化成标准形式
Max L=800x1+650x2
建立表格计算
Cj 800 650 0 0 0 0 b
CB XB x1 x2 x3 x4 x5 x6
0 x3 6 5 1 0 0 0 1500
0 x4 20 45 0 1 0 0 10000
0 x5 20 8 0 0 1 0 4000
1 1 0 0 0 -1 0
0 x3 0 -1 1 0 0 6 1500
0 x4 0 25 0 1 0 20 10000
0 x5 0 -12 0 0 1 20 4000
800 x1 1 1 0 0 0 -1 0
ζ 0 150 0 0 0 -800
Cj 800 650 0 0 0 0 b
CB XB x1 x2 x3 x4 x5 x6
0 x3 0 1 0 0 300
0 x4 0 37 0 1 -1 0 6000
0 x6 0 0 0 1 200
800 x1 1 0 0 0 200
ζ 0 -330 0 0 40 0
650 x2 0 1 0 0
0 x4 0 0 1 0
0 x6 0 0 0 1
800 x1 1 0 0 0
ζ 0 0 0 0
由于检验ζ≥0(j=1，…，6)，故原问题有最优解效益指标L达到最大为，这与
用单纯形法求的结果完全一致。
三、结束语
实例的计算步骤与结果向人们充分显示了最小比值旋转迭代法的简便性与可信度，从制定生产计划的过程来看，用最小比值旋转迭代法比用单纯形法和枚举法要简单的多，且作者通过大量求解线性规划问题及线性规划教材中的Beale例子，都说明此方法是简单易行的，可见最小比值旋转迭代法在生产管理系统有广泛的使用价值。
作者单位：汕头大学商学院，广东 汕头 515063
参考文献
［1］赵学慧，赵瑛，枚举法在制定生产计划中的应用，数理统计与管理，1997年第11期.
［2］许建中，许绍吉，线性规划，科学出版社，1990年.
|