性质2证明对偶单纯形算法基本思想算法过程算例单纯形算法对偶单纯形算法框图
算例00-5-24-15cj10-1-2-5-1y5001-1[
-6]0-2y40y5y4y3y2y1bxBcB00-5-24-15C
j-zj1-1/3[-2/3]0-5-1/3y500-1/61/6101/3y2-240-4
-10-15Cj-zj-3/21/21015/21/2y3-51/4-1/4
01-5/41/4y2-24-3/2-7/200-15/2Cj-zj例：用对偶
单纯形法求解解：将问题化为下式，以得到对偶问题的初始可行基00-4-3-2cj10-31
[-2]-4x5001-1-2-1-3x40x5x4x3x2x1bxBcB00-4
-3-2Cj-zj-1/203/2-1/212x1-2-1/211/2[-5
/2]0-1x40-10-1-40Cj-zj-2/5-1/57/5011
1/5x1-21/5-2/5-1/5102/5x2-3-1/5-8/5-3/500
Cj-zj否初始正则解检查可行是则停止得最优解选出基变量检查是否无可行解是则停止否无最优解选入
基变量计算检验数灵敏度分析灵敏度分析研究的问题单纯行表中基的位置：为清楚起见，把新单纯行表中的基对应的初始单纯行表中的那
些向量抽出来单独列一块，记为B，初始单纯行表为：0…0BNb基变量非基变量初始解单纯行法的迭代过
程实际上是对约束方程的系数矩阵实施行的初等变换，由线代知道，对矩阵0…0非基变量基变量基可行解实施行的初等变换时，当B变
为I时，I将变为则，上述矩阵将变为新单纯行表写为：灵敏度分析的步骤：1。将参数的改变计算反应到最终单纯形表上：具体方法是
，按下列公式计算由参数的变化而引起的最终单纯形表上有关数字的变化：2。检查原问题是否仍为可行解；3。检查对偶问题是否仍为可行
解；4。按下表所列情况得出结论和决定继续计算的步骤：仍为问题最优解单纯形法继续求最优解对偶单纯形法继续求最优解引入人工变
量，用新表计算可行解非可行解可行解非可行解可行解可行解非可行解非可行解结论（继续计算的步骤）对偶问题原问题
将cj的改变反应到最终单纯形表上,只能出现上页表中所示的前两种情形。例：已知LP问题用单纯形法求解得最终单纯形表如下：00
012cj-1/21/40017/2x12-15/25/410015/2
x30x5x4x3x2x1bxBcB3/2-1/40103/2x21-1/2-1/400
0Cj-zj（表1）试确定：a）当目标函数变为最优解会如何变化；b）当目标函数变为求?的变化
范围，使最优解不变。a)将cj的改变反应到最终单纯形表（1）上,得表（2）0001.55cj
-1/21/40017/2x15-15/25/410015/2x30x5x4x3x2x1
bxBcB[3/2]-1/40103/2x21.51/4-7/8000Cj
-zj（表2）表（2）中变量x5的检验数为正，继续迭代得表（3）0001.55cj01/
601/314x150015015x30x5x4x3x2x1bxBcB1-1/6
02/301x500-5/60-1/60Cj-zj（表3）即新解为b)将c
j的改变反应到最终单纯形表（1）上,得表（4）00012＋?cj-1/21/40017
/2x12＋?-15/25/410015/2x30x5x4x3x2x1bxBcB3/2-1
/40103/2x21-1/2+?1/2-1/4-?1/4000Cj-zj（表
4）二、分析bi变化的影响bi的变化在实际问题中表明可用资源的数量发生变化，将bi的改变反应到最终单纯形表上,只引起基变量列数
字变化。所以灵敏度分析的步骤为：1）按公式算出将其加到基变量列的数字上；2）因为其对偶问题仍为可行解，故只需检查原问题是否
为可行解。例：上例中：a）当第二个约束条件的右端项增大到32最优解会如何变化；b）当第二个约束条件变为求?的变化范围，使表中
基为最优基第页第页运筹帷幄之中决胜千里之外对偶理论运筹学
课件对偶理论对偶问题对偶理论对偶单纯形算法对偶问题的提出例：设某企业有m种资源，用于生产n种不同
的产品，各种资源的拥有量为bi（i=1,2,…m）,又知生产单位第j种产品（j=1,2,…n）消费第i种资源aij单位，产值为cj
元。若用xj表示第j种产品的生产量，求产值最大，LP模型为：任意线性规划问题都存在一个与之伴随的对偶问题现从另一角度提出问题：
假设此企业拥有资源但未生产，而另一企业预将上述企业拥有的资源买过来，至少应付出多少代价，才能使前一企业愿意放弃生产活动，出让资源。
若设yi表示收买该企业一单位i种资源时付出的代价。则另一线性规划问题为：收买的企业付出的代价是该商品的价格吗？若不是，它和原本
的价格是什么关系？收购资源的企业能赚钱吗?怎么赚？原问题与对偶问题对应关系资源向量价值向量价值向量资源向量第j个约
束条件为＝关系第j个变量无非负约束，自由变量第j个约束条件为≤关系第j个变量≤0第j个约束条件为≥关系第j个变量≥0第
j个变量无非负约束，自由变量第j个约束条件为等式关系第j个变量≤0第j个约束条件为≥关系第j个变量≥0第j个约束条件为≤
关系有m个变量有m个约束条件min问题max问题对偶问题（D）一一对应原问题（L）对偶问题的基本性质以下各
性质基于如下假设原问题对偶问题若是原问题的可行解，是其对偶问题的可行解，则恒有证明性质1（弱对偶性）若是原问题的
可行解，是其对偶问题的可行解，且有则是原问题的最优解，是其对偶问题的最优解。性质2（最优性）又因为则性质3（无界性
）：若原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。性质4（强对偶性，对偶定理）：若原问题有最优解，则其对偶问题也
一定有最优解，且maxz=minw。在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；
反之若约束条件取严格不等式，则其对应的对偶变量一定为零。即（另外说法）：分别是原问题和对偶问题的可行解，则为最优解的充分必
要条件是性质5（互补松弛性）性质5证明化原问题和对偶问题为标准形式原问题对偶问题若则则为最优解.
为最优解.则所以设原问题和对偶问题为原问题对偶问题性质6（变量对应关系）则，原问题单纯形表的检验数行对应其对偶问题的
一个基解。（对应关系见表）性质6证明设B是原问题的一个可行基，所以相应的对偶问题为若求得原问题的以解检验数
为和令将它代入（）,(),得对偶问题性质的应用Maxz=4y1＋3y2对偶问题（D）y1
＋2y2≤2y1－y2≤32y1＋3y2≤5y1＋
y2≤23y1＋y2≤3y1,y2≥0Min?=2x1＋3x2＋5x3＋2x4＋3
x5原问题（L）x1＋x2＋2x3＋x4＋3x5≥42x1－x2＋3x3＋x4＋x5≥3xj≥0,j=
1,2,…,5第2个约束2x1－x2＋3x3＋x4＋x5=3第2个变量y2＞0第1个约束
x1＋x2＋2x3＋x4＋3x5=4第1个变量y1＞0第5个变量x5≥0第5个约束
3y1＋y2=3第4个变量x4=0第4个约束y1＋y2＜2第3个
变量x3=0第3个约束2y1＋3y2＜5第2个变量x2=0第2个约束y1
－y2＜3第1个变量x1≥0第1个约束y1＋2y2=2原问题（L）对偶
问题（D）-Y松弛变量YS2松弛变量YS1对偶问题的基解-CBB－1CN-CBB－1N0原问题单纯形表中的检验向
量松弛变量XS非基变量XN基变量XB原问题变量在基B下的划分最优单纯形表对偶问题D的最优解：y1=3/2y2
=1/8y3=0Min??=8y1＋16y2＋12y3y1＋4y2≥22y1＋4y3≥4
y1,y2,y3≥0原问题L标准形MaxZ=2x1＋3x2x1＋2x2＋x3=84x1
＋x4=164x2＋x5=12x1,x2,x3,x4,x5≥0x3,x4,x5是松弛变量原问题L一般形式MaxZ=2x1＋3x2x1＋2x2≤84x1≤164x2≤12x1,x2≥0对偶问题D原问题L影子价格随具体情况而异：在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应该买进该资源用于扩大生产；当某种资源的市场价格高于影子价格时，企业应该把该资源卖掉。所以，影子价格具有市场调节作用。原问题对偶问题 |
|
