对偶单纯形法灵敏分析2.ppt

该【对偶单纯形法灵敏分析2 】是由【太丑很想放照片】上传分享，文档一共【64】页，该文档可以免费在线阅读，需要了解更多关于【对偶单纯形法灵敏分析2 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。对偶单纯形法灵敏度分析演示文稿
当前1页,总共64页。
优选对偶单纯形法灵敏度分析
当前2页,总共64页。
项目
非基变量
基变量
XBXN
XS
0XSb
BN
I
Cj-Zj
CBCN
0
项目
基变量
非基变量
XB
XNXS
CBXBB-1b
I
B-1NB-1
Cj-Zj
0
CN-CBB-1N-CBB-1
初始单纯形表
CB
CN
0
单纯形法是在保持所有约束条件常数项总是保持大于等于零的情况(保证可行),通过迭代,使所有检验数小于等于零(求最大值),求得最优解。
当前3页,总共64页。
1、当原问题达到最优时,松弛变量经过上述转换后构成的检验数的相反数为其对偶问题的一个可行解,反之亦成立
原问题表中的检验数满足最优性条件
CN-CBB-1N≤0
-CBB-1≤0;
ATY≥CT;
Y≥0
YT=CBB-1
从上面可以看出:
也就是说,当原问题达到最优时,对偶问题的解可行。并且根据对偶的性质,我们可以确定此时对偶问题也达到最优
CB:1×mB-1:m×m
CBB-1:1×mY:m×1
当前4页,总共64页。
项目
非基变量
基变量
XBXN
XS
0XSb
BN
I
Cj-Zj
CBCN
0
项目
基变量
非基变量
XB
XNXS
CBXBB-1b
I
B-1NB-1
Cj-Zj
0
CN-CBB-1N-CBB-1
初始单纯形表
也就是:单纯形法计算时只要原问题可行(B-1b≥0),对偶问题可行(即检验数小于0),解就是最优解。单纯形法的基本过程就是保证原问题解可行的情况下,不停迭代,直至对偶问题也达到可行,此时原问题达到最优,对偶问题也达到最优
当前5页,总共64页。
根据刚才所说,单纯形法只要单纯形法计算时只要原问题可行(B-1b≥0),对偶问题可行(即检验数小于0),解就是最优解。所以,我们利用单纯形法对原问题求解时,如果首先保持对偶问题的可行性(即原问题检验数≤0),然后再看原问题是否可行,如果此时原问题的解不可行,则换基迭代,换基过程中保证对偶可行(检验数≤0),直至原问题由不可行解变为可行解,此时就得到它的最优解,——这就是对偶单纯形法的基本思想。
第四节对偶单纯形法
也就是说:对偶单纯形法是在保持原问题所有检验数都小于等于零的基础上,通过迭代,使原问题的解(即右边常数项)都大于等于零,从而求得最优解。
当前6页,总共64页。
第四节对偶单纯形法
(2)初始解不可行,即右端常数项有负分量(如果原问题可行,则直接用单纯形法)
使用对偶单纯形法必须满足两个条件:
(1)单纯形表中的所有检验数必须符合对偶可行,即小于等于0
当前7页,总共64页。
①先找一个基,建立初始对偶单纯形表,使检验数全部非正,即C全部为非正;
②若b列元素非负,则已经是最优基。反之,则换基迭代,直至原问题可行。
第四节对偶单纯形法
怎么做呢?
当前8页,总共64页。
例用对偶单纯形法求解
该问题用单纯形法求解时,需要先化标准型,此时约束方程两边左边需要减去剩余变量,同时为了构造单位阵,需要添加人工变量,采用大M法求解。
第四节对偶单纯形法
思考:上面约束方程化为标准型后,两边乘以-1,就可得到单位阵。此时能否用单纯形法?原因?
答:不能。因为此时右边常数项为负数,解不可行。为了保证初始解可行
当前9页,总共64页。
例用对偶单纯形法求解
第四节对偶单纯形法
能否用对偶单纯形法呢?
对偶单纯形法初始对偶单纯形表只要保证对偶可行,即检验数全部非正即可。并不要求初始解可行,所以右边常数项可以非负,此题目价值系数均为负,意味着初始单纯形表格的检验数为负,而右端常数项又有负数,正好满足对偶单纯形法的要求。
当前10页,总共64页。