换基迭代
指求解线性规划问题过程中的迭代技巧
换基迭代(basis iteration)一般是指求解线性规划问题过程中的迭代技巧,是从一个基可行解到另一个基可行解的迭代,表作业法的换基迭代是一种求解运输问题过程中的迭代技巧。
单纯形表上
单纯形表上的换基迭代过程是:
1.确定入基变量。若在 的检验数 中有检验数 ,且λs所在列的其他元素中有 ,则取 ,即T(B)中最左边的一个正检验数λs(或取 ),让其对应的变量xs为入基变量。
2.求主元,确定出基变量。按最小比值原则
其中brs为主元,记为 ,主元brs所在行的基变量xr就是要确定的出基变量。
3.以brs为主元,进行初等行变换。将入基变量xs所在的列变为单位向量,即 ,与此同时,原T(B)中的各元素按以下各式计算,变为相应的新元素:
于是得到新基 所对应的单纯形表 :
表作业法
表作业法的换基迭代是一种求解运输问题过程中的迭代技巧,指在调运表上对负检验数相应的空格所在的闭回路上进行的迭代,先把第一个出现负检验数的空格所对应的非基变量作为入基变量,并使这些非基变量的值由零增到调整量,为了保持平衡,在这空格的闭回路上取调整量θ=min{第奇数次拐角点的调运量},然后对闭回路中的每个第奇数次拐角点的调运量各减去调整量θ,对每个第偶数次拐角点的调运量加上调整量θ,闭回路外的调运量均不变.这样,便得到一个新的调运方案。
参考资料
最新修订时间:2022-08-25 16:03
目录
概述
单纯形表上
参考资料