下载文档原格式
第二章 线性规划问题的对偶理论与灵敏度分析总结一．对偶问题统一归纳表注意：对偶问题允许i b 小于0，也正是对于原问题i b 小于0，才引入了后面的对偶单纯形法解决问题。
二．对偶问题的基本性质⎩⎨⎧≥≤=0X ..max 设原问题为b AX t s CXz⎩⎨⎧≥≥=是列向量,0A .. min 对偶问题为TY Y C Y t s Yb TTω1.对称定理：对偶问题的对偶是原问题2.弱对偶性定理：若Y X 和分别是原问题和对偶问题的可行解，则有b TY X C ≤推论（1）max 问题的任一可行解的目标是对偶问题最优目标值的一个下界。
min 问题的任一可行解的目标函数 值是原问题最优目标值的一个上界。
（2）若原问题可行且其目标函数值无界，则对偶问题无可行解。
反之对偶问题可行且其目标函数值无界，则原问题无可行解。
（3）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而原问题无可行解，则对偶问题目标函数值无界。
3. 最优性定理：若Y X 和分别是原问题和对偶问题的可行解，并且b TY X C =，则X 是原问题最优解，Y 是其对偶问题的最优解4. 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
5.互不松弛性：若Y X 和分别是原问题和对偶问题的可行解，则它们分别是最优解的充要条件是：0ˆ,ˆˆ0ˆ1j 1=<=>∑∑==i i nj ij i nj j ij i y b xa b x a y则如果，则如果练习：判断下列说法是否正确：(1) 任何线性规划问题存在并具有惟一的对偶问题；(✓)(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(✗)(3) 设j ˆx ，i ˆy 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m**j j j j i i i i j 1j 1i 1i 1ˆˆc x c x b y b y ====≤=≤∑∑∑∑；(✓) (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓) (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗)简析：对(5)、(6)，由互补松弛性质判断，具体详见课本P59三．对偶单纯形法(1). 对偶单纯形法应用前提： 1.检验数行全部非正2.变量取值有负数(2). 对偶单纯形法计算步骤：1.确定换出基变量 取{}i rb min b =，其对应变量r x 为换出基的变量。
第二章线性规划的对偶理论1．对偶问题的提出2．原问题与对偶问题3．对偶问题的基本性质4．影子价格5对偶单纯形法5．对偶单纯形法6．灵敏度分析7．参数线性规划1§1．对偶问题的提出原问题设某企业有m种资源用于生产n种不同产品，各种（i=1m）又生产单位第j种资源的拥有量分别为b i （i=1，…，m），又生产单位第j种产品（j=1，…，n）消费第i种资源a ij 单位，产值为c j 元。
用x 代表第j种产品的生产数量，为使该企业产值最大，可将上述问题建立线性规划模型j 将上述问题建立线性规划模型：max z =c 1x 1+c 2x 2+…+c n x n a 11x 1+a 12x 2+…+a 1n x n ≤b 1a 21x 1+a 22x 2+…+a 2n x n ≤b 2………………2a m 1x 1+a m 2x 2+…+a m n x n ≤b m x 1，x 2，…，x n ≥0§1．对偶问题的提出现在从另一角度提出问题：假定有另一企业欲将上述企业拥有的资源收买过来，至少应付出多少代价，才能使前一拥有的资源收买过来，至少应付出多少代价，才能使前企业愿意放弃生产活动，出让资源。
设用y i 代表收买该企业一单位i种资源时付给的代价，则总收买价为：ωb ω = b1y 1＋…＋b m y m 前一企业生产一单位第j种产品时，消耗各种资源的数量分别为a 1j ，a 2j ，…，a mj ，如果出让这些资源，价值应不低于单位j种产品的价值c j 元，因此：a 1 j y 1+ a 2 j y 2 + …+ a m j y m ≥ c j 3j j j j （j =1，…，n）§1．对偶问题的提出对后一企业来说，希望用最小代价把前一企业所有资源收过来此有有资源收买过来，因此有：min ω=b1y 1＋b 2y 2＋…＋b m y m a11y 1+a 21y 2+…+a m 1y m ≥c 1a 12y 1+a 22y 2+…+a m 2y m ≥c 2………………a 1n y 1+a 2n y 2+…+a mn y m ≥c ny 1，y 2，…，y m ≥04§1对偶问题的提出§1．对偶问题的提出max z = c 1x 1+ c 2x 2+ … + c n x na x +a x ++a xb a 1 1x 1+ a 1 2x 2 + … + a 1 n x n ≤b 1a 2 1x 1+ a 2 2x 2 + … + a 2 n x n ≤b 2………………a m 1x 1+ a m 2x 2 + … + a m n x n ≤b mmin ω = b 1y 1＋b 2y 2＋…＋b m y mx 1 ，x 2 ，… ，x n ≥0a 1 1y 1+ a 21 y 2 + … + a m 1y m ≥c 1a 1 2y 1+ a 22y 2 + … + a m 2y m ≥c 2………………a 1n y + a 2n y 2+ … + a y ≥c 51 n 12 n 2 mn m ny 1，y 2，… ，y m ≥0§2．原问题与对偶问题后一个线性规划问题是前一个问题从不同角度作的阐述如前者称为线性规划问的话的阐述。
第二章 线性规划问题的对偶理论与灵敏度分析总结
一．对偶问题统一归纳表
注意：对偶问题允许i b 小于0，也正是对于原问题i b 小于0，才引入了后面的对偶单纯形法解决问题。
二．对偶问题的基本性质
⎩⎨
⎧≥≤=0
X ..max 设原问题为b AX t s CX
z
⎩⎨
⎧≥≥=是列向量
,0A .. min 对偶问题为
T
Y Y C Y t s Yb T
T
ω
1.对称定理：对偶问题的对偶是原问题
2.弱对偶性定理：若Y X 和分别是原问题和对偶问题的可行解，则有b T
Y X C ≤
推论（1）max 问题的任一可行解的目标是对偶问题最优目标值的一个下界。
min 问题的任一可行
解的目标函数 值是原问题最优目标值的一个上界。
（2）若原问题可行且其目标函数值无界，则对偶问题无可行解。
反之对偶问题可行且其目标函数值无界，则原问题无可行解。
（3）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而原问题无可行解，则对偶问题目标函数值无界。
3. 最优性定理：若Y X 和分别是原问题和对偶问题的可行解，并且b T
Y X C =，则X 是原问题最优解，Y 是其对偶问题的最优解
4. 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
5.互不松弛性：若Y X 和分别是原问题和对偶问题的可行解，则它们分别是最优解的充要条件是：
0ˆ,ˆˆ0ˆ1
j 1
=<=>∑∑==i i n
j ij i n
j j ij i y b x
a b x a y
则如果，则如果
练习：判断下列说法是否正确：
(1) 任何线性规划问题存在并具有惟一的对偶问题；(✓)
(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(✗)
(3) 设j ˆ
x ，i ˆy 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m
**j j j j i i i i j 1
j 1
i 1
i 1
ˆ
ˆc x c x b y b y ====≤=≤∑∑∑∑；(✓) (5) 已知*
i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓) (6) 已知*
i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗)
简析：对(5)、(6)，由互补松弛性质判断，具体详见课本P59
三．对偶单纯形法
(1). 对偶单纯形法应用前提： 1.检验数行全部非正
2.变量取值有负数
(2). 对偶单纯形法计算步骤：
1.确定换出基变量 取{}
i r
b min b =，其对应变量r x 为换出基的变量。
2.确定换入基的变量
rs a 为主元素，s x 为进基变量，若所有0≥rj a ，则原问题无可行解
3.用换入变量替换换出变量，得到一个新的基。
对新的基再检查是否所有0b ≥i ，如是，找到
两者的最优解，如为否，回到第1步继续迭代。
练习：用对偶单纯形法解下列线性规划问题
解：
进基2y ∴
rs s s rj rj j j j a z c a a z c -=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧<-=0m in θ0
,,,y 1
25-26..5215321432⎪⎩⎪⎨⎧≥-=+---=+--y y y y y y y y y t s 32152415m ax y
y y w ---=32152415m in y y y w ++= 0,,y 12526..3
2132132⎪⎩⎪
⎨⎧≥≥++≥+y y y y y y y t s 4/14
/10
14/54/12404
1015
13/13/2053/103/1252----------y y 46-24-m in 0m in =⎭⎫⎩⎨⎧=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧<-=rj rj j j j a a z c θ011602045
4
321---y y
y y y y b Y C B B
四．灵敏度分析
2.分析j c 的变化
当N c （非基变量的目标函数系数）中某个j c 发生变化时，只影响到非基变量j x 的检验数 带入变化后的j
c 到单纯形表中，求解检验数，j σ
⎩⎨
⎧≥≤形法继续迭代，不是最优解，用单纯
值可能发生变化，仍为最优解，但最优
，
00j σ
3.分析i b 的变化
带入变化量b ∆求出)(b
1b b B ∆+=-，
⎩
⎨⎧≤≥单纯形法继续迭代是对偶可行解，用对偶、最优值可能改变仍为最优解，但最优解
，
0 0b
4.增加一个变量j x 的分析
（1）计算j B
j P B c c 1
-j -=，σ （2）计算j 1,
j
P P B -=
（3）若⎩
⎨⎧≥≤代找出最优，则按单纯形法继续迭，原最优解不变
，00j
σ
5.分析参数ij a 变化
（1）若ij a 的变化发生在非基变量，按4中办法求解
（2）若ij a 的变化发生在基变量，将使B 和-1
B 发生改变，需引入人工变量求解，将原问题转为
可行解再用单纯形表发求解
6.增加一个约束条件的分析
（1）将当前的最优解带入新增的约束，若满足约束条件，可暂不考虑新增约束的影响，否则转下
一步；
（2）把新增约束添加到原问题的最终表中，并做初等行变换，构成对偶可行的单纯形表，并用对偶单纯形表迭代，求出新的最优解。
