最小比值旋转迭代法在生产计划中的应用

时间：2022-10-09 02:50:35 经济管理毕业论文我要投稿

相关推荐

最小比值旋转迭代法在生产计划中的应用

　　摘　要　本文通过用最小比值旋转迭代法制定生产计划的实例，向管理人员介绍计算性规划最优解的一种简单而易行的方法。

最小比值旋转迭代法在生产计划中的应用

　　关键词：最小比值旋转迭代法，生产计划。

　　一、方法简述

　　对于一个线性规划问题的标准形式

　　(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