对偶单纯形法

大家好，欢迎来到IT知识分享网。

对偶单纯形法是利用对偶原理求解原线性规划问题的一种方法，而不是直接求对偶问题的方法。前面介绍的单纯形法相对而言称为原始单纯形法。

目录

算法原理：

算法步骤：

例题解析：

算法原理：

用单纯形法求解线性规则问题（LP），是由一个基本可行解迭代到下一个基本可行解，在迭代过程中始终保持解的可行性不变，检验数逐步变为全部为非正的过程，一旦所有检验数非正，则对应的基本可行解就是最优解。当所有检验数为非正时，由对偶理论可知  正是对偶问题（DP）的可行解，因此将原问题（LP）对应于检验数全部非正的基本解称为对偶可行解。

算法步骤：

步骤1：确定初始单纯形表，给出一个初始对偶可行解  ;

步骤2：如果  则  是最优解，停止；否则下一步；

步骤3：若  ，选取  为离基变量；

步骤4：若  ，则无可行解，停止；否则，按 确定进基变量; 

步骤5：以  为旋转主元做旋转变换，迭代到新的对偶可行解，转步骤2。

例题解析：

例题：利用对偶单纯形法求解线性规则问题：

解：先标准化：

这里为了将  作为初始基，对约束条件两边同乘 -1 ：

对应的初始单纯形表如下：

f	0	-4	-12	-18	0	0
	-3	-1	0	-3	1	0
	-5	0	-2	-2	0	1

当前解  为非可行解，但是它是对偶可行解

，， 为离基变量

，

 进基变量 ， 为主元

经旋转变换后，有：

f	30	-4	0	-6	0	-6
	-3	-1	0	-3	1	0
	5/2	0	1	1	0	-1/2

此时  不成立，仍为不可行解。

， 为离基变量，

，

 进基变量 ， 为主元

经旋转变换后，有：

f	36	-2	0	0	-2	-6
	1	1/3	0	1	-1/3	0
	3/2	-1/3	1	0	1/3	-1/2

此时  成立，是可行解，算法终止。

最优解：，最优值 

（行文中若有纰漏，希望大家指正）