出处：管理学卷 • 运 筹 学 • 数学规划
对偶单纯形法
对偶单纯形法 与单纯形法相类似的求解线性规划问题的迭代方法。求解是在对偶规划问题的可行解集合的极点上进行迭代的。从原问题的一个正则解出发,在保持对偶问题的解始终是可行解的前提下,经过换基迭代,逐步使正则解变成原问题的可行解,从而得到原问题的最优解。由勒姆克(C.E.Lemke)于1954年提出。对偶单纯形法的计算步骤如下:(1)引入松弛变量,把原问题化为标准型,列出初始单纯形表。(2)如果检验数全部非正,检查b列的各分量。若b列的各分量均非负,则得到原问题的最优解,计算终止;否则转入步骤(3)。(3)由min{i|b i <0}=r,确定对应的基变量x r 为出基变量。同时,检查x r 所在行的各系数a rj (j=1,2,…,n)。若所有的b rj ≥0,则原问题无可行解,计算终止;否则,由 确定a rs ,相应的非基变量x s ,为入基变量。(4)以a rs 为枢轴元,进行转轴,换基迭代得到新的单纯形表,并返回步骤(2)。