对偶单纯形法

对偶单纯形法第1页，课件共22页，创作于2023年2月

二、对偶单纯形法的基本思想

1、对“单纯形法”求解过程认识的提升——

从更高的层次理解单纯形法

初始可行基（对应一个初始基本可行解）

→迭代→另一个可行基（对应另一个基本可行解），直至所有检验数≤0为止。第2页，课件共22页，创作于2023年2月

所有检验数≤0意味着

，说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基。定理2-5

B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。第3页，课件共22页，创作于2023年2月LP原问题:若B是A中的一个基可行基B对应的解是基本可行解，则B是可行基对偶可行基若单纯形乘子是对偶问题的可行解，则B是对偶可行基

是对偶问题的可行解检验数等价

第4页，课件共22页，创作于2023年2月

证明：第5页，课件共22页，创作于2023年2月单纯形法的求解过程就是：

在保持原始可行的前提下(b列保持≥0)，

通过逐步迭代实现对偶可行(检验数行≤0)。

2、

对偶单纯形法思想：

换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0）

，通过逐步迭代实现原始可行（b列≥0，从非可行解变成可行解）。

第6页，课件共22页，创作于2023年2月对偶单纯形法的思想（图示）原问题初始基本可行解保持为基本可行解初始对偶可行解保持对偶可行性最优解基本可行性对偶可行性始终满足解的可行性始终满足对偶可行性第7页，课件共22页，创作于2023年2月

三、对偶单纯形法的实施1、使用条件：

①检验数全部≤0；

②解答列至少一个元素

<0；2、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。

第8页，课件共22页，创作于2023年2月3、计算步骤：

①建立初始单纯形表，计算检验数行。解答列≥0——已得最优解；至少一个元素<0,转下步;解答列≥0——原始单纯形法；至少一个元素<0,另外处理；

检验数全部≤0（非基变量检验数<0）至少一个检验数>0第9页，课件共22页，创作于2023年2月

基变换：

先确定换出变量——解答列中的负元素（一般选最小的负元素）对应的基变量出基；

即相应的行为主元行。第10页，课件共22页，创作于2023年2月然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果

(最小比值原则),则选

为换入变量

,相应的列为主元列

,主元行和主元列交叉处的元素

为主元素。若,要计算最小比值吗？为什么？第11页，课件共22页，创作于2023年2月

按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。

循环以上步骤，直至求出最优解。第12页，课件共22页，创作于2023年2月3、举例——用对偶单纯形法求解LP：

化为标准型

→

将两个等式约束两边分别乘以-1，得第13页，课件共22页，创作于2023年2月以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：第14页，课件共22页，创作于2023年2月-2/-2----4/-3------

比

值-2-3-4000-Z-1-2-110-21-301-3-4

x4

x5

00

-2-3-400x1x2x3x4x5cjxjbXBCB第15页，课件共22页，创作于2023年2月----4/-5/2----1/-1/2

比

值0-4-10-10

cj-zj0-5/21/21-1/21-1/23/20-1/2-12

x4

x1

0-2

-2-3-400x1x2x3x4x5cjxjbXBCB第16页，课件共22页，创作于2023年2月00-3/5-8/5-1/50

cj-zj01-1/5-2/51/5107/5-1/5-2/52/511/5

x2

x1

-3-2

-2-3-400x1x2x3x4x5cjxjbXBCB最优解:X*=（11/5，2/5,0,0,0）T，最优值:minW=-maxZ*=-[11/5×(-2)+2/5×(-3)]=28/5第17页，课件共22页，创作于2023年2月4、举例——用对偶单纯形法求解LP：

化为标准型

→

将三个等式约束两边分别乘以-1，然后列表求解如下：第18页，课件共22页，创作于2023年2月-3/-1-9/-1---------

比

值-3-90000-Z-1-1100-1-4010-1-7001-2-3-3y3

y4

y5000-3-9000y1y2y3y4y5cjyjbXBCB第19页，课件共22页，创作于2023年2月

----6/-3-3/-1------

比

值0-6-3006-Z11-1000-3-1100-6-1012-1-1

y1

y4

y5

-300-3-9000y1y2y3y4y5cjyjbXBCB第20页，课件共22页，创作于2023年2月00-1-208-Z10-4/31/30011/3-1/30001-215/31/31

y1

y2

y5

-3-90-3-9000y1y2y3y4y5cjyj