当前位置：文档之家 › 对偶与灵敏度分析

对偶与灵敏度分析

  • 格式：doc
  • 大小：578.54 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

第6章单纯形法的灵敏度分析与对偶

第6章单纯形法的灵敏度分析与对偶

这个约束条件的对偶价格就和这个剩余变量的
z
有关了。这将使得最优目
j
标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 z j 值的相反
数- z j。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方
程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变
量的 z j值。
管理运筹学
XB
bb12
5
5
,
X
B
5
5
b3 15
15
对于b1：比值的分母取B－1的第一列，这里只有β11=1，而β21=β31=0，则
1
max
b1
11
5 1
5
Δb1无上界，即Δb1≥－5，因而b1在[35,+∞) 内变化时对偶价格不变。
管理运筹学
18
§1 单纯形表的灵敏度分析
对于b2：比值的分母取B－1的第二列，β12＜0，β22＞0，则
§1 单纯形表的灵敏度分析
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变
xBi di1
|
d 'i1
0
50
而Min
xBi di1
|
d 'i1
0
25,故有当 50
b1
25,即250
b
b
325第一个
约束条件的对偶价格不变。

运筹学对偶理论与灵敏度分析

运筹学对偶理论与灵敏度分析
17
（6）（互补松驰性）
若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是： Y*XS=0,YSX*=0 (其中XS，YS分别是原问题和对偶问题的松驰变量向量)。
证明：设原问题和对偶问题的标准型是 原问题
对偶问题
max Z CX
s.t.
AX X, Xs
Xs 0
b
CX (0) Y (0)b CX
所以 X是(0最) 优解。
15
（5）（强对偶定理） 若互为对偶问 题之一有最优解，则另一问题必有最优解，且它们的 目标函数X值* 是相原等问题。的最优解，对应基阵B必存在
C CB B1A 0
即得到 Y *A， C其中
Y * CB B 1
若 Y * 是对偶问题的可行解，它使
3x5 2 x4 2x5
3
解：对偶问题为
maxW 2 y1 3y2
x2 3x5 2
x1
x2
2x5
3
化简为
x1 1 x5
x2
2
3x5
y2 3
(1)
y1 y2 4
( 2)
5
y1 y1
y2 2 y2 5
( 3) ( 4)
3y1 2 y2 9
( 5)
y1, y2 0
n
max z c j x j j 1
s.t.
n
aij x j bi ,
j1
i 1, 2,
,m
x
j
0,
j 1, 2, , n
特点：对偶变量符号不限
对偶问题:
m
minW bi yi i 1
s.t.
m
aij yi c j ,
i1

第六章单纯形法灵敏度分析与对偶

第六章单纯形法灵敏度分析与对偶
X4 19 2 4/3 0 X3 50 -1/2 -1/3 1 σj= cj - zj -4 -2/3 0
X4 X5 X6 19 0 0 1 2/3 -10/3 0 -1/6 4/3 0 -13/3 -10/3
bθ
2 1 Z = 88
∴ 最优生产计划是：生产1个单位产品C，生产2个单位产 品D，不生产A、B产品。可得最大总利润 88 个单位。
可能改变 C – CBB-1A ≤ 0 变
求出使该表达式仍然成立的 C 的变化范围
若 C 的变化超出该范围，则原最优解将改变
例1：某工厂用甲、乙两种原料生产A、B、C、 D
四种产品，要求确定总利润最大的最优生产 计划。该问题的线性规划模型如下：
Max Z = 9 x1 +8x2 + 50x3 + 19x4
则：在原最终单纯形表上，新变量对应的系数列为Pj '= B-1Pj，
检验数为 σj= Cj – CBB-1 Pj
若 σj= Cj – CBB-1 Pj ≤ 0，则原最优解不变；
若 σj= Cj – CBB-1 Pj ≥ 0，则继续迭代以求出新的最优解。
例3： 沿用例1 ►
如果该工厂考虑引进新产品E ，已知生产 E 产品1 个单位要消耗甲材料3个单位和乙材料1个单位。
要求：⑶产品E 的利润达到多少时才值得投产？
解： 设生产 E 产品X7个单位，单位产品的利润为C7，
则模型变为：
Max Z = 9 x1 +8x2 + 50x3 + 19x4 + 0x5 + 0x6+ C7x7 3x1+ 2 x2 + 10 x3 + 4 x4 + x5 + 3 x7 = 18（甲材料） 2x3+ 1/2x4 + x6 + x7 = 3 （乙材料）

3对偶理论与灵敏度分析解析

3对偶理论与灵敏度分析解析
X ≥0
对偶的定义 min W= Y b s.t. ATY ≥ C
Y≥0
min Z’= - CX
max W’ = -Yb
s.t. - AX ≥ - b
s.t. -ATY ≤ -C
X ≥0 对偶的定义
Y≥0
__
__
（2）弱对偶性：设 X和 分Y 别是问题（P）和（D）的
可行解，则必有
__ __
n
m
C X Y b, 即 c j x j yibi
i 1
m
aij yi
c j ( j 1,2,, n)
i1
yi无符号限制（无约束）(i 1,2,, m)
例： 原问题为
max Z 2 x1 3 x2 4 x3
2 x1 3 x2 5 x3 2
3
x1
x2
7 x3 3
x1 4 x2 6 x3 5
x1 , x2 , x3 0
对偶问题的无界性。
无界
关于无界性有如下结论：
minW 4 y1 2 y2
原问题 问题无界
对偶问题 无可 行解
（D）
y1 y1
y2 y2
2 1
y1
0,
y2
0
无可 行解
问题无界
无可 行解
推论3：在一对对偶问题（P）和（D）中，若一个可行 （如P），而另一个不可行，（如D），则该可行的问 题无界。
一、问题的提出
• 对偶是什么：对同一事物（或问题），从不同 的角度（或立场）提出对立的两种不同的表述。 • 在平面内，矩形的面积与其周长之间的关系， 有两种不同的表述方法。 （1）周长一定，面积最大的矩形是正方形。 （2）面积一定，周长最短的矩形是正方形。 • 这种表述有利于加深对事物的认识和理解。 • 线性规划问题也有对偶关系。

运筹(第二章对偶与灵敏度分析)(1)

运筹(第二章对偶与灵敏度分析)(1)

5x2 3x3 30
x1 0, x2无约束，x3 0
2023/2/22
17
解：将原问题模型变形, 令x1 x1
min z 7x1 4x2 3x3
4x1 2x2 6x3 24
3x1 6x2 4x3 15 5x2 3x3 30
y1 y2 y3
x1 0, x2无约束，x3 0
则对偶问题是
max w 24 y1 15y2 30 y3
4 y1 3y2
7
x1
2 y1 6 y2 5 y3 4
x2
6 y1 4 y2 3x3 3
x3
y1, y2 0, x3无约束
2023/2/22
18
小结：对偶问题与原问题的关系：
目标函数：MAX
原 约束条件：m个约束
对
问
y1 y2
ym
2023/2/22
12
类似于前面的资源定价问题，每一个约束条件对 应一个“ 对偶变量”，它就相当于给各资源的单 位定价。于是我们有如下的对偶规划：
min W b1 y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym c1 a12y1 a22y2 am2ymc2 a1n y1 a2n y2 amn ym cn y1, y2 ,, ym 0
分别是原问题和对偶问题的可行解，则恒有
n
m
c j x j bi yi
j 1
i 1
m
n
考虑利用 c j aij yi 及
aij x j bi
i 1
j 1
代入。
2、无界性 如果原问题（对偶问题）有无界解，则
其对偶问题(原问题）无可行解。
2023/2/22

运筹学：第1章 线性规划 第3节 对偶问题与灵敏度分析

运筹学：第1章 线性规划 第3节 对偶问题与灵敏度分析

s.t.
4x1 3x1
5x2 200 10x2 300
x1, x2 0
9x1 4x2 360
s.t.
34xx11
5x2 10 x
200 2 300
3x1 10x2 300
x1, x2 0
则D为
min z 360y1 200y2 300y3 300y4
9 y1 4 y2 3y3 3y4 7 s.t.4 y1 5y2 10 y3 10 y4 12
amn xn bm ym xn 0
机会成本 a1 j y1 a2 j y2 aij yi amj ym
表示减少一件产品所节省的可以增加的利润
（3）对偶松弛变量的经济解释——产品的差额成本
机会成本
利润
min w b1 y1 b2 y2 bm ym
a11 y1
st
a12
y1
a1n y1
max z CX
（P）
AX b
s
.t
.
X
0
（D）
min w Yb
s.t.
YA C Y 0
• （2）然后按照（D）、（P）式写出其对偶
例：写出下面线性规划的对偶规划模型：
max z 2x1 3x2
min w 3 y1 5y2 1y3
x1 2x2 3 y1 0
s.t.
2xx11
例如，在前面的练习中已知
max z 2.5x1 x2 的终表为
3x1 5x2 15 s.t.5x1 2x2 10
x1, x2 0
0 x3 9 2.5 x1 2
0 19 1 - 3
5
5
1
2
0
1
5

第三章-对偶理论及灵敏度分析3课件

第三章-对偶理论及灵敏度分析3课件

二、原问题与对偶问题的数学模型
继续
三、原问题与对偶问题的对应关系
返回
第三章-对偶理论及灵敏度分析3
一、对偶问题的提出
对
偶 问
实例：某家电厂家利用现有资源生产两种
题
产品， 有关数据如下表：
上页 下页 返回
设备A 设备B 调试工序
产品Ⅰ 产品Ⅱ
0
5
6
2
1
1
利润（元） 2
1
D
15时 24时 5时
第三章-对偶理论及灵敏度分析3
第三章 对偶理论及灵敏度分析
3.1.1 线性规划对偶问题 3.1.2 对偶问题的基本性质 3.1.3 影子价格 3.1.4 对偶单纯形法 3.2.1 灵敏度问题及其图解法 3.2.2 灵敏度分析 3.2.3 参数线性规划
第三章-对偶理论及灵敏度分析3
3.1.1 线性规划的对偶问题
一、对偶问题的提出
下页
(Y1,Y2
)
A A
C
返回
Y1 0 ,Y2 0
第三章-对偶理论及灵敏度分析3
对 偶 问
(mY1inwY2 )(YA1YC2 )b
题
Y1 0, Y2 0
令 YY1 ，Y 得2对偶问题为：
上页
下页
maYxA
w C
Yb
返回
Y无约束
证毕。
第三章-对偶理论及灵敏度分析3
三、原问题与对偶问题的对应关系
设备B –––– 元／y时2
问 题
调试工序 –––– 元y／3时
付出的代价最小，
且对方能接受。
上页
下页
出让代价应不低于
返回
用同等数量的资源
收

运筹学第二章第6讲

运筹学第二章第6讲
12
例题4：写出以下模型的对偶问题
max z = 3 x1 − 2 x2 − 5 x3 + 7 x4 + 8 x5 x2 − x3 + 3 x4 − 4 x5 = −6 2 x1 + 3 x2 − 3 x3 − x4 ≥ 2 − x1 + 2 x3 − 2 x4 ≤ −5 s.t. − 2 ≤ x1 ≤ 10 5 ≤ ≤ 25 x2 , ≥ 0, 为自由变量 x5 x3 x4
OR1
对偶问题（或原问题） 对偶问题（或原问题） 目标函数 MinW
约束条件数： 约束条件数：n 第i个约束条件类型为“≥” 个约束条件类型为“ ” 个约束条件类型为 个约束条件类型为“ ” 第i个约束条件类型为“≤” 个约束条件类型为 个约束条件类型为“ 第i个约束条件类型为“=” 个约束条件类型为 对偶变量数： 个 对偶变量数：m个 第i个变量 个变量≥0 个变量 个变量≤0 第i个变量 个变量 第i个变量是自由变量 个变量是自由变量
OR1
15
2 弱对偶性：极大化原问题的任一可行解的目标 弱对偶性： 函数值不大于其对偶问题任意可行解的目标函数 值。即： C X≤ Yb
证明：设原问题为maxZ=CX, AX ≤b ，X ≥0. ≥0. 证明： 原问题为maxZ=CX,
为原问题的可行解， ≤b， X 为原问题的可行解，有AX ≤b，
二.对偶线性规划的定义 对偶线性规划的定义
max Z = CX ( LP ) AX ≤ b S .T . X ≥ 0
称线性规划(DLP)为线性规划 为线性规划(LP)的对偶线性规划 称线性规划 为线性规划 的对偶线性规划
minω = yb ( DLP ) yA ≥ C S .T . y ≥ 0

数学建模---对偶问题和灵敏度分析

数学建模---对偶问题和灵敏度分析

对偶问题例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。

要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。

已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。

试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。

显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1nij j j a x =∑为这批混合饲料中第i 种营养成分的总含量；它不应低于bi 。

于是，我们得下列线性规划模型(1—1)：1min nj jj f c x ==∑11,,..01,,nij j i j j a x b i m s t x j n=⎧≥=⎪⎨⎪≥=⎩∑现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。

设第i 种营养丸的价格为ui(i ＝1，…，m)。

则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1mij ii a u =∑养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件：11,,mij ij i a uc j n =≤=∑另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i饲料加工厂面临的问题是：应把这m 种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。

为该问题建立数学模型，即得如下线性规划(1—2)：1max mi i i z b u ==∑11,,..01,,mij i j i ia u c j n s t u i m =⎧≤=⎪⎨⎪≥=⎩∑我们称问题(1—2)为原有问题 (1—1)的对偶问题(记为(D))。

对偶问题与灵敏分析

对偶问题与灵敏分析

y1，y2，… ，ym ≥0
y1，y2，… ，ym ≥0
原问题为：
Max Z= c1x1+c2x2+…+cnxn Min (-Z）= -c1x1-c2x2-…-cnxn
a11x1 + a12x2+…+a1n xn ≤ b1 a21x1 + a22x2+…+a2n xn ≤ b2
MaxZ（X）= 2x2-5x3
y1 -x1
-x3 ≤- 2
y2 2x1 + x2+6x3 ≤ 6
y3/
x1 - x2+3x3 ≤ 0
y3// -x1 + x2-3x3 ≤ 0
x1，x2，x3≥0
其对偶问题为：
Min W(y）= -2y1+6y2
x1
-y1 +2y2 +y3/ -y3//
≥x02
y2 -y3/ +y3// ≥2
4
4 x4
6
x1 0, x2 , x3 0, x4无限制
s.t约无2变y束符1y量4方号y1≤1y≥程约01003≤束7,≥=2yyy13y22y22约40y束y3无,332变y方y符3y3量程号无31≥≥≤≤约=00限53束2制
2．1．4对偶问题的基本性质
以对称型为例
设原问题（P）为 其对偶问题（D）为
无符号约束
约束方程≥ ≤
=
原问题（ P）为
对偶规划问题（D）为：
max z c1x1 c2 x2 c3 x3 c4 x4
s.t aa2111xx11
a12 x2 a22 x2
a13 x3 a23 x3
a14 x4 a24 x4

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案一、填空题1. 在线性规划问题中，若原问题存在最优解，则其对偶问题也一定存在最优解，这是线性规划的基本性质之一，称为______。

答案：对偶性2. 在线性规划问题中，若原问题与对偶问题均存在可行解，则它们均有______。

答案：最优解3. 对于线性规划问题，若原问题约束条件系数矩阵为A，目标函数系数向量为c，则其对偶问题的目标函数系数向量是______。

答案：c的转置（c^T）二、选择题1. 线性规划的原问题与对偶问题之间的关系是：A. 原问题的最优解和对偶问题的最优解相同B. 原问题的最优解是对偶问题的最优解的负数C. 原问题的最优解与对偶问题的最优解互为对偶D. 原问题的最优解和对偶问题的最优解没有关系答案：C2. 在线性规划中，若原问题不可行，则其对应的对偶问题：A. 可行B. 不可行C. 无界D. 无法确定答案：B三、判断题1. 线性规划的原问题和对偶问题具有相同的可行解。

（）答案：错误2. 若线性规划的原问题存在唯一最优解，则其对偶问题也一定存在唯一最优解。

（）答案：正确四、计算题1. 已知线性规划问题：max z = 3x1 + 2x2s.t.x1 + 2x2 ≤ 42x1 + x2 ≤ 5x1, x2 ≥ 0求该问题的对偶问题，并求解原问题和对偶问题的最优解。

答案：对偶问题为：min w = 4y1 + 5y2s.t.y1 + 2y2 ≥ 32y1 + y2 ≥ 2y1, y2 ≥ 0原问题和对偶问题的最优解如下：原问题最优解：x1 = 2, x2 = 1，最大利润z = 8对偶问题最优解：y1 = 2, y2 = 1，最小成本w = 82. 某工厂生产甲、乙两种产品，生产一件甲产品需要2小时的机器时间和3小时的工人劳动时间，生产一件乙产品需要1小时的机器时间和1小时的工人劳动时间。

工厂每周最多能使用12小时的机器时间和9小时的工人劳动时间。

运筹学第二章灵敏度分析

运筹学第二章灵敏度分析

CB
-3 -5 -Z’
xB x1 X2
2.4 对偶解的经济解释
一、对偶线性规划 的解： P55
Cj xB x3 x1 x2 z b 7/2 7/2 3/2 x1 1 0 0 y4 Cj yB b y1 15/2 0 原问题变量 x2 0 0 1 0 y5 对偶问题变量 y2 y3 x3 1 0 0 0 y1 原问题变量 x4 5/4 1/4 -1/4 1/4 y2 x5 -15/2 -1/2 3/2 1/2 y3
T.G.Koopman（库普曼）和 L.V.Kamtorovich（康脱罗维奇）
二人因此而共同分享了1975年的第7届诺贝尔经 济学奖。
2.5 灵敏度分析
一、灵敏度分析的含义 是指系统或事物因周围条件变化显示出来的敏感性程度的分析。 对于线性规划问题的灵敏度分析是指参数A，b，C变化引起的 对原问题解的变化的分析。 其中：A为技术参数矩阵，b为资源向量，C为价值向量 可以用参数变化后的问题重新用单纯形法求解？ 没必要，意义不大，有些问题看不出来。 把相应的变化反映到最终单纯形表中，再根据情况用相应的方 法求解。
Z 50 x1 30 x2
2.1 线性规划的对偶问题与对偶理论
假设现有乙公司准备租借用(购买)该木器厂的木工和 油漆工两种劳力的劳务，需要考虑这两种劳务以什么 样的价格租入最合算？而同时甲公司要以什么条件才 会租让？甲公司肯定会以自己利用两种劳力的劳务组 织生产所获得的利润最大为条件，设每个木工的租用 价格为y1，每个油漆工的租用价格为y2，则乙公司愿 意租用的出资为：
0 变量 0 无限制
型 约束 型 型
0 变量 0 无限制
型 约束 型 型

线性规划中的对偶问题与灵敏度分析

线性规划中的对偶问题与灵敏度分析

线性规划中的对偶问题与灵敏度分析线性规划是一种优化方法，广泛应用于各个领域的决策问题。

在线性规划中，对偶问题与灵敏度分析是两个重要的概念和工具，可以帮助我们更好地理解和解决实际问题。

1. 对偶问题在线性规划中，对偶问题是指与原始问题相对应的一个问题。

它通过转换原始问题并构造一个新的问题，以便从不同的角度来解释和解决原始问题。

对偶问题能够提供原始问题的一些有用信息，并且在某些情况下，对偶问题的解与原始问题的解是相等的。

对偶问题的构造可以通过拉格朗日对偶性理论来完成。

该理论通过构造一个拉格朗日函数，将原始问题中的约束条件转化为拉格朗日乘子，从而得到对偶问题。

对偶问题的目标函数是原始问题的约束条件的线性组合。

解决对偶问题可以通过求解拉格朗日函数的最优化问题来实现。

对于线性规划问题，对偶问题的解可以通过求解一组线性方程或线性不等式来获得。

对偶问题的解不仅可以提供原始问题的一些信息，还可以用于检验原始问题的解的可行性和最优性。

2. 灵敏度分析灵敏度分析是在线性规划中评估解决方案对问题参数变化的响应程度的方法。

它可以帮助我们了解如果问题的参数发生变化，对解决方案的影响有多大，并做出相应的调整和决策。

灵敏度分析可以通过改变单个参数或多个参数来进行。

其中，常见的灵敏度分析包括目标函数系数的变化、约束条件右侧常量的变化和新增或取消约束条件。

这些变化可以用来模拟实际情况中可能发生的条件变化，以及评估解决方案的稳定性和可行性。

在进行灵敏度分析时，我们可以通过计算变动参数对解决方案的影响程度来得到一些关键指标。

例如，参数的变化导致目标函数值的变化量称为“影子价格”，而约束条件右侧常量的变化导致解决方案中相应决策变量的变化量，则称为“机会成本”。

灵敏度分析的结果可以帮助我们确定参数的重要性，判断解决方案的可行性和稳定性，以及找到最佳的决策方案。

在实际应用中，灵敏度分析可以帮助我们应对不确定性和风险，做出更加准确和可靠的决策。

管理运筹学--单纯形法的灵敏度分析与对偶对偶问题讲课讲稿

管理运筹学--单纯形法的灵敏度分析与对偶对偶问题讲课讲稿
2. 初始单纯表中的基变量Xs=b，迭代后的单 纯形表中为XB= B-1b
3. 初始单纯表中的约束系数矩阵为：
[A,I]=[B,N,I] 迭代后的单纯形表中约束系数矩阵为：
[B-1A, B-1I]=[B-1B, B-1N, B-1I]=[I , B-1N, B-1] 4. 若初始矩阵中变量xj的系数向量为Pj，迭代
x4
x5 值
0 x3
8
1
0
1
0
0
0 x4 12 0 2 0 1 0
0 x5 36 3 4 0 0 1
检验数j
3 50 0 0
• 最优基和最优基的逆
Cj
3 5 0 0 0比
CB XB
b
x1
x2 x3
x4
x5 值
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
3 x1 4 1 0 0 -2/3 1/3
0
0
1
表
j
0
0 -50
0
-50
初始单纯形表为:
Cj
CB
CN
0
XB
XN
XS
0
X S
b
B
N
I
检验数j
CB
CN
0
当迭代若干步，基变量为X B时，新的单纯形表:
Cj
CB
CN
0
XB
XN
XS
CB
b X B
B-1
I
检验数j
0
B-1N CN- CB B-1N
B-1 - CB B-1
小结
1. 对应初始单纯表中的单位矩阵I，迭代后的 单纯形表中为B-1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

§2 对偶与灵敏度分析§2.1 LP 的对偶问题无论从理论和实践角度，对偶理论是LP 中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP 问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。

一、问题的提出例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD 进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表：1.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？ 解：1.设甲乙产品各生产1x 2x 件LP1：⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤++=0,16482122232211212121x x x x x x x x x MaxZ 2.设每台设备的机时最低价分别为：1y ，2y ，3y ，4yLP2：⎪⎩⎪⎨⎧=≥≥++≥+++++=4,3,2,1,0342224212168124213214321i y y y y y y y y y y y MinZ i二、原问题和对偶问题之间的关系： 1.对称形式下的原问题与对偶问题对称形式下原问题的一般式： 矩阵形式：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+++≤+++≤++++++=n j x bx a x a x a b x a x a x a b x a x a x a x c x c x c MaxZ j mn mn m m n n n n nn .......21,0 (221)122222121112121112211⎩⎨⎧≥≤=0X b AX CX Max 若用i y 代表第i 种资源的估价，则其对偶问题的一般式为：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥+++≥+++≥++++++=m j y cy a y a y a c y a y a y a c y a y a y a y b y b y b MinZ j nm mn n n m mn m m mm .......21,0 (221)122222112112211112211⎩⎨⎧≥≥=0Y C Y A Yb Min T T ω 2.非对称形式下原问题与对偶问题：方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。

例2.2写出下列LP 问题的对偶问题：⎪⎪⎩⎪⎪⎨⎧≤≥≤+--≥-++=--+-+++=无约束43214321432143214321,0,0,)3.........(..........2099912)2..(....................85376)1.....(....................53432x x x x x x x x x x x x x x x x x x x x MaxZ 为写出基对偶问题，先将其转化为对称形式，再进行变化：因目标函数为Max ，故约束条件全部转化为“0≤”，所有变量均应为“0≥”。

将（1）式变为：535343214321≤--+-≥--+-x x x x x x x x 和。

再将535343214321-≤-+-≥--+-x x x x x x x x 转化为将（2）式两端同乘以“-1”，并令：0,,;0,''4'4''4'44'33'3≥-=≥∴-=x x x x x x x x 其中得：855376''4'4'321-≤-++--x x x x x所以，例2.2可以变为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-++--≤-++---≤-+--≤+-++--+-+=0,,,,20999912855376533533)(432''4'4'321''4'4'321''4'4'321''4'4'321''4'4'321''4'4'321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x MaxZ 令对应上述四个约束条件的对偶变量为3'2''1'1,,,y y y y ，则其对偶问题为： ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥-≥---≥+++--≥++-≥---≥+-+-+--=0,,,4953349533393297112'6208553'2''1'13'2''1'13'2''1'13'2''1'13'2''1'132''1'13'2''1'1y y y y y y y y y y y y y y y y y y y y y y y y y y y y Min ω令'22''1'11,y y y y y -=-=，将第4与第5个不等式合并，将第三个不等式两端同乘以“-1”得：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤=+--≤-+-≥-+≥++-++=0,0,495339329711262085321321321321321321y y y y y y y y y y y y y y y y y y Min 无约束ω 由以上的推导可以发现有以下规律：方法二：根据原问题与对偶问题之间的关系，可将其归纳如下表：§2.2 对偶问题的基本性质一、单纯形法计算的矩阵描述设线性规划问题的矩阵表达式为：⎩⎨⎧≥≤=0X bAX CXMaxZ ，加上松弛变量s X 后为：⎩⎨⎧≥≥=++=0,00s s s X X b IX AX X CX MaxZ 式中：单位矩阵为m m I x x x X m n n n s ⨯=+++,),......,(21。

单纯形法计算时，总选取为初始基I ，对应基变量为s X 。

设迭代若干步后，基变量为B X ，B X 在初始单纯形表中的系数矩阵为B 。

将B 在初始单纯形表中单独列出，而A 中去掉B 的若干列后组成矩阵N ，同时将C 也分为两块),(N B C C ，B C 是目标函数中基变量B X 的系数行向量；N C 是目标函数中非基变量N X 的系数行向量。

这样LP 的初始单纯形表可列成如下形式：于是原LP 问题可以改写为：⎩⎨⎧≥=++++=0,,0s N B s N B sN N B B X X X bIX NX BX X X C X C MaxZ 将约束条件移项并左乘1-B 后得到B X 的表达式：s N B IX B NX B b B X 111-----=代入目标函数得：s B N B N B X B C X N B C C b B C Z 111)(-----+= 所以，经过迭代之后，得出新的单纯形表为：当为最优基时，在上述单纯形表中有：01≤--N B C C B N ，01≤--B C B 而B X 的检验数可以写为：0=-I C C B B 因此有：01≤--A B C C B ，01≤--B C B称1-B C B 为单纯形乘子，若令1-=B C Y B T则有：⎩⎨⎧≥≥0Y C Y A TT可以发现这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。

将这个解代入对偶问题的目标函数值，有：Z b B C b Y B T ===-1ω即：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值。

（其实，这时对偶问题的解也为最优解。

）二、本节讨论先假定原问题和对偶问题为对称形式的LP ，即原问题为：⎩⎨⎧≥≤=0X b AX CX MaxZ 其对偶问题为：⎩⎨⎧≥≥=0Y C Y A YbMin T T ω然后说明对偶问题的基本性质在非对称形式也适用。

1.对称性：对偶问题的对偶是原问题。

证明：原问题与其对偶问题分别为：⎩⎨⎧≥≤=0X b AX CX Max 与⎩⎨⎧≥≥=0Y C Y A Yb Min T T ω2.弱对偶性：若X 是原问题可行解，Y 是对偶问题的可行解，则存在b Y X C ≤。

证明：设原问题为：0≥≤=X bAX CX Max原问题的对偶问题为：0≥≥=Y C Y A Yb Min TT ω3.无界性：若原问题为无界解，则其对偶问题为无可行解。

证明：由弱对偶性可得，本性质成立。

4.可行解是最优解时的性质：若X 是原问题可行解，Y 是对偶问题的可行解，当b Y X C =时，X 与Y 是原问题与对偶问题的最优解。

证明：5.对偶定理：若原问题有最优解，那么其对偶问题也有最优解，且目标函数值相等。

6.互补松弛性：若X 是原问题可行解，Y 是对偶问题的可行解，那么00==X Y X Y s s 和，当且仅当为X ，Y 最优解。

（在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量值一定为零。

）0,01==∑=si i nj j ij i x b x a y 则有　若 ；00,1=∑=i si i nj j ij y x b x a 则有　若 。

将互补松弛性质应用于其对偶问题时可以这样叙述：j mi i ij j c y a x =∑=1,0则有　若 ；0,1=∑=j j mi i ij x c y a 则有　若 。

由互补松弛定理可知：若原问题最优解中的第j个变量为正，则其对偶问题中与之对应的第j个约束条件在最优情况下必呈严格等式（即其松弛变量为0）；而如果对偶问题中第j个约束条件在最优情况下呈严格不等式，则原问题最优解中第j个变量必为0。

类似地，若对偶问题最优解中第i个对偶变量为正，则其原问题中与之对应的第i个约束条件在最优情况下必呈严格等式（即其剩余变量为0）；而如果原问题中第i个约束条件在最优情况下呈严格不等式，则对偶问题最优解中第i个对偶变量必为0。

互补松弛定量阐明了原问题及其对偶问题最优解各分量之间的关系，当已知一对对偶问题之一的最优解时，可利用该定量求出另一个问题的最优解。

7.设原问题是：0,≥=+=s s X X bX AX CX Max对偶问题为：0,≥=-=s s Y Y CY YA YbMin ω则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下表所示：这里1S Y 是对应原问题中B X 基变量的剩余变量，2S Y 是对应原问题中非基变量N X 的剩余变量。