大家好，欢迎来到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 |
此时 成立，是可行解，算法终止。
最优解：，最优值
（行文中若有纰漏，希望大家指正）
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/144785.html
