当前位置：文档之家 › 第二章--线性规划的对偶理论与灵敏度分析--运筹学

第二章--线性规划的对偶理论与灵敏度分析--运筹学

  • 格式：ppt
  • 大小：1020.00 KB
  • 文档页数：45

下载文档原格式

  / 45

合集下载

《运筹学》胡运权 第4版 第二章 线性规划的对偶理论及灵敏度分析

《运筹学》胡运权 第4版 第二章 线性规划的对偶理论及灵敏度分析

b2 bm
x1, x2 , , xn 0
对 称 形 式 的
的 定 义
m W ib 1 n y 1 b 2 y 2 b m y m 对
s.t.
a11 a12 a1n
a21 a22 a2n
am1 y1 c1
am2 y2 amn ym
c2 cn
偶 问 题
y1, y2 , , ym 0
a23 x3 a33 x3
b2 b3
x1 0， x2 0， x3无 约 束
（2.4a） （2.4b） （2.4c） （2.4d）
先转换成对称形式，如下：
的 的一个变量，其每个变量对应于对偶问题 的一个约束。
定
义
m Z a c 1 x 1 x c 2 x 2 c n x n 一
对 偶
a11x1 a12x2 a1n xn (,)b1
a2
1x1
a22x2
a2n xn
(, )b2
般 线 性
问 题 的 定 义
am1x1 am2 x2 amnxn (,)bm xj 0( 0,或符号不限) j 1 ~ n
问题。
对
对偶问题是对原问题从另一角度进
偶
行的描述，其最优解与原问题的最 优解有着密切的联系，在求得一个
原
线性规划最优解的同时也就得到对 偶线性规划的最优解，反之亦然。
理
对偶理论就是研究线性规划及其对 偶问题的理论，是线性规划理论的
重要内容之一。
问 题 的 导 出
例2-1
我们引用第一章中美佳公司的例子，如表1
的
x1, x2, , xn 0
对
m W ib 1 n y 1 b 2 y 2 b m y m

运筹学课件 第2章：线性规划的对偶理论

运筹学课件 第2章：线性规划的对偶理论

min w 16y1 36y2 65y3
90 y1 3 y 2 y1 2 y 2 5 y 3 70 y , y , y 0 1 2 3
原问题 A b C 约束系数矩阵
对偶问题 约束系数矩阵的转臵
约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量 约束条件的右端项向量 Max z=CX Min w=Y’b 目标函数 AX≤b A’Y≥C’ 约束条件 X≥0 Y≥0 决策变量
若原问题为求极小形式的对称形式线性规划问题， 对偶问题应该具有什么形式？
Min w Y 'b A'Y C Y 0
max w Y 'b A'Y C Y 0
min z CX
Max z CX
AX b X 0
AX b X 0
min w 5 y1 4 y2 6 y3 4 y1 3 y2 2 y3 2 y1 2 y2 3 y3 3 3 y1 4 y3 5 2 y 7 y y 1 2 3 1 y1 0, y2 0, y3无约束
对偶问题 约束系数矩阵的转臵
目标函数中的价格系数向量
目标函数 约束条件
变量
Max z=CX m个 ≤ ≥ = n个 ≥0 ≤0 无约束
约束条件的右端项向量 目标函数 Min w=Y’b m个 ≥0 变量 ≤0 无约束 n个 ≥ 约束条件 ≤ =
【例2-3】写出下列线性规划问题的对偶问题
min 2x1 3x2 5x3 x4
1.初始表中单位阵在迭代后单纯形表中对应的位臵就是B-1 2.对于原问题的最优解，各松弛变量检验数的相反数恰好 是其对偶问题的一个可行解，且两者具有相同的目标函数 值。根据下面介绍的对偶问题的基本性质还将看到，若原 问题取得最优解，则对偶问题的解也为最优解。

运筹学第2章对偶理论和灵敏度分析-第4节

运筹学第2章对偶理论和灵敏度分析-第4节

1 y1 2 y2 3 y3
x1 0, x2,x3 0, x4无约束
则由表2-4中原问题和对偶问题的对应关系， 可以直接写出上述问题的对偶问题，
max z ' 5 y 1 4 y 2 6 y 3
y1 2 y2
2



y1 3 y1
2 y2
综合上述，线性规划的原问题与对偶问题 的关系，
其变换形式归纳为表2-4中所示的对应关系。
原问题
目标函数 max z
n个
变 0
量

0
无约束
约 m 个
束


0
条


0
件
约束条件右端项
目标函数变量的系数
对偶问题
目标函数 min
n个 约
束

证：由性质（2）可知，
YbCX ,是不可能成立。
例：
LP:
DP:
maxzx1 x2
mi n4y1 2y2
2xx11xx22
4 2

2yy11yy22
1 1
x1,x2 0
y1,y2 0
从两图对比可明显看到原问题无界， 其对偶问题无可行解
j1

x
j

0,
j

1 ,2 ,
,n
第一步：先将等式约束条件分解 为两个不等式约束条件。
n
maxz cj xj j1


n
aijxj bi j 1,2,,m 213
j1


n
ai j x j
bi ,
i

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

运筹学对偶理论与灵敏度分析
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

运筹学(第二版)课后答案

运筹学(第二版)课后答案
由单纯形表计算：
４０５
附录四习题参考答案
CB -M 0 -M σj -M 5 -M σj 1 0 -M σj
XB X6 X5 X7 X6 X2 X7 X3 X2 X7
4 X1 3 2 1 4+4M -1 2 -1 4-2M -1 2 -2 5-2M
5 X2 2 1 1 5+3M 0 1 0 0 0 1 0 0
（1） 、 （2）答案如下表所示，其中打三角符号的是基本可行解，打星 号的为最优解：
４０２
附录四习题参考答案
x1 x2 x3 x4 x5 z x1 x2 x3 △ 0 0 4 12 18 0 0 0 0 △ 4 0 0 12 6 12 3 0 0 6 0 -2 12 0 18 0 0 1 △ 4 3 0 6 0 27 -9/2 0 5/2 △ 0 6 4 0 6 30 0 5/2 0 *△ 2 6 2 0 0 36 0 3/2 1 4 6 0 0 -6 42 3 5/2 0 0 9 4 -6 0 45 0 0 5/2 1.3 (1)解：单纯形法 首先，将问题化为标准型。加松弛变量 x3，x4，得
1 0 1 0 0 （P 1，P 2，P 3，P 4，P 5）即 0 2 0 1 0 3 2 0 0 1 x1 x3 4 1 0 1 0 2 0 线性独立，故有 2 x 2 12 x 4 因（P 1，P 2，P 3） 3x 2 x 18 x 2 5 3 2 0 1 x1 x3 4 令非基变量 x4 , x5 0 得 2 x 2 12 → 3x 2 x 18 2 1
12400120300175max547543216543215443217654321?jxxxxxxxxxxxxxxxxxxxxxstxxxxxxxzj第二章对偶理论和灵敏度分析21对偶问题为1????????????????02211042010min2121212121yyyyyyyystyys2????????????????????????无约束32131321213213210013312245minyyyyyyyyyyyyystyyys3???????????????????????????无约束32132132132131321001373323232253minyyyyyyyyyyyyyystyyys4?????????????????????????无约束3213213213213210071036655552015maxyyyyyyyyyyyystyyys附录四习题参考答案410221因为对偶变量ycbb1第k个约束条件乘上0即b1的k列将为变化前的1由此对偶问题变化后的解y1y2

运筹学线性规划对偶理论和灵敏度分析

运筹学线性规划对偶理论和灵敏度分析
建立非对称形式线性规划问题旳对偶模型可采用下 列环节： （1）经过变换，把线性规划问题化为具有对称形式 旳原问题。 （2）根据原问题，写出对偶问题。（此时旳对偶并 非是原线性规划问题旳对偶） （3）经过变量代换等，把参数还原为最初旳形式 （必须做）。
例2.1.2写出下面非对称线性规划问题旳对偶。 max z = x1+2 x2 + x3 x1 + x2 － x3 ≤ 2
xj x1 x2 …
xn 原始约束 对偶：极小化 w
y1
a11 a12
…a22
… a2n ≤
b2
：
：
：
：
：
ym
am1 am2
…
amn ≤
bm
对偶约束 ≥ ≥ …
≥
原始极大化 z c1 c2 …
cn
阐明：表 2旳变量行与参数行相乘构成原始问题旳约 束条件和目旳函数；表2 旳变量列与参数列相乘构成 对偶问题旳约束条件和目旳函数。
max
z 33
=22002233 x1+4000 x1+ 44x2 + 2 2x3
x2 ≤
+3000 606000
x3 y1
22x1 + 1x2 + 2 2x3 ≤ 404000 y2 1 x1+ 33x2 + 33x3 ≤ 30300 y3 1x1+ 2 2x2 + 4 4x3 ≤ 20200 y4 x1 ≥0, x2 ≥ 0,x3 ≥0
max z = CX +0Xs st. AX + IXs = b
X , Xs≥0
其中，I 是相应于松弛变量旳单位方阵。
单纯形法计算时，总是选择 I 为初始可行基，松 弛变量作为初 始基变量旳。因为松弛变量作为基变

运筹(第二章对偶与灵敏度分析)(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、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。

应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。

例：某家具厂木器车间生产木门与木窗；两种产品。

加工木门收入为56元/扇，加工木窗收入为30元/扇。

生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。

问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。

他想利用该木器车间的木工与油漆工来加工完成他的订单。

他就要考虑付给该车间每个工时的价格。

他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。

解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。

运筹学--第二章 线性规划的对偶问题

运筹学--第二章 线性规划的对偶问题

习题二2.1 写出下列线性规划问题的对偶问题(1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤54x1＋x2＋x3≤20 2x1－x2＋3x3＝－4x j≥0 （j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤202x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2 已知线性规划问题max z＝CX，AX=b，X≥0。

分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）；'x代换。

（4）模型中全部x1用312.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4st. x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3 ＋x4＝2x1 ＋x3 ≥2x j≥0（j＝1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。

2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量st. 2x1 ＋x3＋x4≤8 y12x1＋2x2＋x3＋2x4≤12 y2x j≥0（j＝1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。

2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3st. 3x1＋4 x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80x j≥0 （j＝1,2,3）４７４８（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。

运筹学习题解答(chap2)(1)(1)

运筹学习题解答(chap2)(1)(1)

第二章 对偶问题与灵敏度分析一、写出下列线性规划的对偶问题1、P89,(a)321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++.,0,;534;332;243321321321321无约束x x x x x x x x x x x x解：原模型可化为321422m in x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≥≥++.,0,;534;3-3--2-;243321321321321321无约束x x x y y y x x x x x x x x x 于是对偶模型为321532m ax y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;22321321321321无约束y y y y y y y y y y y y2、P89,(b)321365m ax x x x Z ++=⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++.0,0,;8374;35;522321321321321x x x x x x x x x x x x 无约束解：令033≥-='x x 原模型可化为321365m ax x x x Z '-+=⎪⎪⎩⎪⎪⎨⎧≥'≥≤'+≤'='+.0,0,;83-74;3--5-;52-2321321321321321x x x y y y x x x x x x x x x 无约束于是对偶模型为321835m in y y y W +-=⎪⎪⎩⎪⎪⎨⎧≥-≥---≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束 或⎪⎪⎩⎪⎪⎨⎧≥≤++≥+-=++.0,,;332;6752;54321321321321y y y y y y y y y y y y 无约束二、灵敏度分析1、P92, 线性规划问题213m ax x x Z += ⎪⎩⎪⎨⎧≥≤+≤+0,1025;74212121x x x x x x最优单纯形表如下试用灵敏度分析的方法，分析：（1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变（2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变解：（1） 1c 的分析：要使得最优解不变，则需⎪⎪⎩⎪⎪⎨⎧≤⨯-⨯+=≤⨯+⨯-=034131003513201413c c σσ 即 ⎪⎩⎪⎨⎧≤≥42511c c 所以：4251≤≤c 时可保持最优解不变。

运筹学第11讲灵敏度分析

运筹学第11讲灵敏度分析

第二章 线性规划的对偶理论
Duality Theory 对偶问题的经济解释——影子价格 线性规划的对偶问题 对偶单纯形法 灵敏度分析 对偶问题的基本性质
1、什么是灵敏度分析？ 是指研究线性规划模型的某些参数(bi, cj, aij）或限制量（xj, 约束条件）的变化对最优解的影响及其程度的分析过程<也称为优化后分析>。
设备A(h)
设备B(h)
调试工序(h)
利润(百元)
Ⅰ
Ⅱ
每天可用能力
资源
产品
0
5
6
2
1
1
2
1
15
24
5
例2-1
如何安排生产计划才能使总利润最多？
解：
(1) 设x1, x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型
max z = 2x1+x2 s.t. 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0
用单纯形法求解得最终单纯形表
得最优解为：
X*=(7/2, 3/2, 15/2, 0, 0)T
zmax=8.5(百元)。
即每天生产3.5单位产品Ⅰ，1.5单位产品Ⅱ时总利润最多，且
max z = 2x1+x2 s.t. 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0
5. 分析系数 aij 的变化
系数矩阵A
s.t.
对偶问题决策变量的最优解<影子价格>：
初始单纯形表
最优单纯形表
X*=B-1b
CN－CBB-1N ≤0
－CBB-1 ≤0
原问题基变量的最优解：

《运筹学》胡运权第4版线性规划的对偶理论及灵敏度分析省名师优质课赛课获奖课件市赛课一等奖课件

《运筹学》胡运权第4版线性规划的对偶理论及灵敏度分析省名师优质课赛课获奖课件市赛课一等奖课件

13
2
y3
2 3
题
y1符号不限, y 2 0, y3 0
非 对 偶 形 式 旳 原对 偶 问 题
例2-4 写出下列问题旳对偶问题
max z c1x1 c2 x2 c3x3
a11x a12 x a13x3 b1
s.t.
a21x1 a31x1
a22 x2 a32 x2
a23 x3 a33 x3
出让自己旳资源？
问 题 旳 导 出
例2-1
条件：出让代价应不低于用同等数量资源由自己组织生 产活动时获取旳获利。
y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工 序旳出让代价。 y1,y2,y3旳取值应满足：
6y 2
y 3
2
5y 1
2y 2
y 3
1
美佳企业用6h设备B和1h调试可 生产一件家电I,获利2元
y1, y2 , y3 0
LP1和LP2两个线性规划问题，一般称LP1为原问题， LP2为前者旳对偶问题。
max Z c1x1 c2 x2 cn xn
对 偶 问 题
s.t.
a11 a21
am1
a12 a22
am2
a1n x1 b1
a2n
x2
b2
amn xn bm
规 划 问
minW b1 y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym (, )c1
a12y1
a22 y2
am2
ym
(,
)c2
题 旳 对 偶 问
a1n y1 a2n y2 amn ym (, )cn
题
y j 0(符号不限,或 0)i 1 ~ m

运筹学第二章线性规划的对偶理论

运筹学第二章线性规划的对偶理论

(5.5) (5.6)
4.3 对偶问题的基本性质
证： 设B是一可行基，于是A=(B,N)
max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0
其中Yξ=(Yξ1, Yξ2)
min ω =Yb YB－Yξ1=CB YN－Yξ2=CN Y, Yξ1 Yξ2 ≥0
(5.5) (5.6)
x1﹐x2 ≥0
关系？
对原模型设： 1 2
A= 4 0 b=(8,16,12)T C=(2，3) 04
X=（x1，x2）T Y=（y1，y2 ，y3 ） 则可得:
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
120
A=
1 -3
0 2
1 1
1 -1 1
b=(2,3,-5,1)T C=(5,4, 6)
确定约束条件
YA
C
x1 ≥0 ﹐x2≤0, x3 无约束
解：因原问题有3个变 于是 量，4个约束条件， 所以对偶问题4个 变量，3个约束条

运筹学第2章-线性规划的对偶理论

运筹学第2章-线性规划的对偶理论
❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

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

运筹学-02对偶理论与灵敏度分析
page 9 Sep.2009
Yao Yuan School of Business Administration
Operations Research
原问题和对偶问题的对应关系
原问题（对偶问题） 对偶问题（原问题） 约束系数矩阵的转置 目标函数中的价值系数向量 约束系数矩阵 约束条件的右端向量
A b C
min W Y T b A Y C s.t. Y 0
T T
X n1，Ym1 C1n，Amn，bm1
对偶问题 约束系数矩阵的转置 目标函数中的价值系数向量 约束条件的右端向量 Min W=YTb ATY≥CT
Yao Yuan School of Business Administration
目标函数
目标函数中的价值系数向量
max Z c j x j
j 1 n
约束条件的右端向量
min W bi y i
有n个 ( j 1,..., n) m a y c 约 ij i j i 1 束 m aij y i c j 条 i 1 件 m a ij y i c j i 1
0 6 1 2
5 2 1 1
15 24 5
max Z 2 x1 x2 5 x2 15 6 x 2 x 24 1 2 s.t. x1 x2 5 x1 , x2 0
min W 15 y1 24 y 2 5 y 3 6 y 2 y3 2 s.t.5 y1 2 y 2 y 3 1 y ,y ,y 0 1 2 3
page 3 Sep.2009
min W 24 y1 26 y 2 2 y1 3 y 2 4 s.t.3 y1 2 y 2 3 y ,y 0 1 2

运筹学第二章灵敏度分析

运筹学第二章灵敏度分析

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 无限制
型 约束 型 型

运筹学第2章 对偶理论

运筹学第2章 对偶理论
写出对偶问题
2 y1 3 y2 y3 2 3 y1 y2 4 y3 3 5 y1 7 y2 6 y3 4 y , y , y 0 1 2 3
原—对偶问题的相互变换形式
原问题（或对偶问题） 目标函数 max 约 束 条 件 变 量 m个 ≤ ≥ = n个 ≥0 ≤0 无约束 约束条件右端项 目标函数变量的系数 对偶问题（或原问题） 目标函数 min m个 ≥0 ≤0 无约束 n个 ≥ ≤ = 目标函数变量的系数 约束条件右端项 变 量 约 束 条 件
设y1 , y2 , y3分别为三种资源的收费单价，所以 有下式： 5 y1 2 y2 y3 10 2 y1 3 y2 5 y3 18 y1 , y2 , y3 0 就目标而言，用下式可以表达： 170 y1 100 y2 150 y3 W
一般而言，W 越小越好，但因需双方满意，故
变为对称形式
m axZ 2 x1 3 x 2 4 x 3 2 x 3 x 2 5 x 3 2 3 x1 x 2 7 x 3 3 x1 4 x 2 6 x 3 5 x1 , x 2 , x 3 0
min W 2 y1 3 y2 5 y3
B
1 0
M-1
-2
最 终 表
cj cB 3 -1 -1 xB x1 x2 x3 检验数 b 4 1 9
3 x1 1 0 0 0
-1 x2
-1 x3 0 0 1 0
0 x4 1/3 0 2/3 -1/3
I
0 1 0 0
-1/3 1/3-M 2/3- M
所以， X*=（4 , 1 , 9），Z = 2
初 始 表

《运筹学》第二章 对偶问题

《运筹学》第二章 对偶问题


3 x1 2 x2
7x4 4
2 x1 3 x2 4 x3 x4 6
x1 0, x2 , x3 0, x4无 约 束
解：原问题的对偶问题为
mi nW 5 y1 4 y2 6 y3
4 y1 3 y2 2 y3 2

20
一组互为对偶的线性规划问题的解之间只有 下列三种情况:
(1)两个规划问题都有可行解(此时,两个规划问题都有最优 解,且最优值相等);
(2)两个规划问题都不可行; (3) 一个规划问题不可行,另一个规划问题有可行解,且具有
无界解。
21
（4）互补松弛性： 在线性规划问题的最优解中，
则 aij xj * = bi ；
bi , 则 y i* = 0 (4)’ 互补松弛性：
在线性规划问题的最优解中， 则 aij yi * = cj ；
>cj , 则 xj* = 0
n
若 y i * >0,
j=1 n
若 a ij xj * <
j=1
m
若 x j * >0,
i=1 m
若 a ij yi*
i=1 22
m
= 证b：i y∵i*
y1 3 y1

2 y2
3 y3 4 y3
3 5

2 y1 7 y2 y3 1
y1

0,
y2

0,
y
无
3
约
束
对偶问题的对 偶还是原问题
14
• 练习 写出下列线性规划问题的对偶问题.
max Z 4x1 3x2 2x3
4x1

《运筹学》第二章 对偶问题和灵敏度分析jssk1

《运筹学》第二章 对偶问题和灵敏度分析jssk1

2.1 线性规划的对偶理论
解：写出该问题的对偶问题
min W 20 y1 20 y2 y1 2 y2 1 2y y 2 2 1 2 y1 3 y2 3 3 y 2 y 4 2 1 y1 , y2 0
根据互补松弛性，可得： X3*=4>0 则 2y1+3y2=3
s.t. AX ≤b X≥0 s.t. YA ≥ C Y≥0
2.1 线性规划的对偶理论
二、原问题和对偶问题的关系
1、原问题目标函数求最大值，对偶问题求最小值； 2、原问题目标函数的系数是对偶问题约束条件的右端项，原问 题中的右端项是对偶问题目标函数的系数； 3、原问题约束条件为“≤”，则在其对偶问题中决策变量为 “≥”；原问题中决策变量为“≥”，则在其对偶问题中的约束条 件为“≥”； 4、原问题中的约束条件个数等于它的对偶问题中的变量个数， 原问题中的变量个数等于它的对偶问题中的约束条件个数；
YA ≥ C
Y≥0
在单纯形法的每一步迭代中，目标函数取值 Z=CBB-1b+(CN-CBB-1N)XN ，当非基变量XN=0时有 Z=CBB-1b和检验数CN-CBB-1N中都有乘子Y=CBB-1， 那么Y的经济意义是什么？
2.1 线性规划的对偶理论
Y=CBB-1=(y1,y2,…,ym)，则得
Z CB B b Yb bi yi
2.1 线性规划的对偶理论
三、对偶问题的基本定理
1、对称性：对偶问题的对偶是原问题。
2、弱对偶定理：若X(0)是原问题的可行解，Y(0)是对偶 问题的可行解，则一定有CX(0) ≤ Y(0)b
max Z=CX 证明：设原问题是 AX ≤b X≥0
则对偶问题是
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

？
•两个问题的最优解的值一致 •最大值问题可行解的目标值必定不大于最
结 论
小值问题可行解的目标值 •一个问题的剩余变量（松弛变量） 不为0 （即有资源剩余），则对应问题的解为0 •一个决策变量不为0，则对应的问题的约束 条件的剩余变量(松弛变量) 为0(即资源彻 底用完)
5*3/2 = 15/2 ＜ 15 6*7/2+2*3/2 = 24 = 24 7/2+3/2 = 5 = 5
分
总价值
6y2 + y3 ≥
析
2
st .
5y1 + 2y2 + y3 y1 , y 2 , y3
≥ 1 ≥ 0
问题求解
min z= 15 y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 max z'= -15 y1 - 24y2 - 5y3 6y2 + y3 – y4 = 2
st .
5y1 + 2y2 + y3 y1 , y 2 , y3
运筹学基础
教 材
《运筹学教程》（第二版） 胡运权 主编 清华大学出版社
例一
美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设 备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少 件．使获取的利润为最大。
C
CB 0 0 0 2 0 1 XB bb
2
x1 0 0 6 1 1 0 2 0
1
x2 5 0 2 0 1 1 1 0
0
x3 1 1 0 0 0 0 0 0
0
x4 0 5/4 1 1/4 0 -1/4 0 -1/4
0
x5 0 -15/2 0 -1/2 13/2 0 -1/2 θ
15 xx3 15/2 3 24 xx4 7/2 1 5 xx5 3/2 2 σ σ
0 x3 1 0 0
0 x4 5/4 1/4 -1/4
0 x5 -15/2 -1/2 3/2 θ
B=
x1 0 1 0
B =
-1
1 0 0
5/4 1/4 -1/4
-15/2 -1/2 3/2
影子价格
从上节对偶问题的基本性质可以看出 ， 当线性规划原问题求得最优解 xj*(j=1,…n)时，其对偶问题也得到最优解yi*(i=1,….,m)，且代入各自的目标 函数后有： n m
一、线性规划的对偶问题
非对称形式？
max z = c1x1 + c2x2 +c3x3 a11x1+a12x2+a13x3 ≤ b1 st. a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 ≥ b3 st.
min w = b1y1 +
a11y1 + a12y1 + a13y1 + y1≥0,
CB XB B B
-1 -1
min w = Y b st.
T
AY ≥ C
Y≥ 0
T
T
CN XN B N
-1 -1
0 Xs B I -CBB
-1 -1
原问题为最优解σ≤0，即：
CB-CBB B CN-CBB N -CBB
T
-1 -1 -1 -1
CB-CBB B CN-CBB N
≤0 ≤0 ≤0
C - CBB A≤0 CBB
max z=CX AX (≤ ＝ ≥) b X (≤ ＝ ≥) 0 或无约束 有n个决策变量 xj (j＝0、2……n) xj ≥ 0
对偶问题（原问题）
min w=Yb -T YA (≤ ＝ ≥) C Y (≤ ＝ ≥) 0 或无约束 有n个约束条件 对应的约束为 ≥
变量
xj ≤ 0 xj 无约束
约束
0 Xs B I 0-CBB I
-1 -1
CB
XB
σ
B b
B B
0
-1
B N
CN-CBB N
-1
-1
B I
-CBB
-1
XB B b σ
CB-CBB B CN-CBB N
对偶问题性质证明的几个重要内容
对 称 形 式
C CB CB XB XB σ b B b
-1
max z = CX st. AX ≤ b X≥ 0
0 x4 5/4 1/4 -1/4 -1/4 1/4
0 x5 -15/2 -1/2 3/2 -1/2 1/2
x3 15/2 0 7/2 3/2
-24 y2 1/4
-5
y3 1/2
σ -σ
X =(7/2,3/2,
15/2,0,0)
Y=(0, ¼, ½ , 0, 0 )
一、线性规划的对偶问题
1、对偶问题定义
X =(7/2,3/2,15/2,0,0) Z = 17/2
* *
6y 估价——影子价格 2 + y3 ≥ 2 （即增加单位资源所 + y st . 5y1 + 2y2 ≥ 1 3 得到的贡献） y1 , y 2 , y3 ≥ 0 问题 Y=(0, ¼, ½ , 0, 0 ) 的解
Z = 17/2
*


需要说明的是：这些性质同样适用于非对称形问题
B与B
C CB XB
-1
2 b 15 24 x1 0 6 1 x2 5 2 0 x3 1 0 0 x4 0 1 0 x5 0 0 θ
5
σ C CB XB b 15/2 7/2 3/2 σ 2
1
1
0
0
1
1 0 0 0 6 1 5 2 1
1 x2 0 0 1
C CB -M YB y6 b 2 -15 y1 0
≥ 1 ≥
-24 y2 6
st .
5y1 + 2y2 + y3
– y5 =
1
0
-5 y3 1 0 y4 -1 0 y5 0 -M y6 1
y1, y 2, y3, y 4, y5
≥ 0
-M y7 0 θ
-M
y7
σ
1
5
2
1
0
-M
-1
-M
0
0
1
0
M-15 8M-24 2M-5
三、最优解检验（唯一解、无限多解、无界解和无解）
X =(7/2,3/2,15/2,0,0)
*
Z = 17/2
*
四、分析 把解X=(7/2,3/2)代入原问题(因为x3、 x4、 x5为附加变量) 5×3÷2＝15/2 5x2 6x + 24 2x
1 2
约束 条件
x1 + 5 2 x x1，x2 ≥ 0
-24 y2 1
st .
5y1 + 2y2 + y3
– y5 =
1
0
-5 y3 0 0 y4 -1/4
y1, y 2, y3, y 4, y5
≥ 0
0 y5 1/4 θ
-24 y2
-5
y3
σ
1/2
15/2
-15/2
0
0
1
0
1/2
-7/2
-3/2
-3/2
Y=(0, ¼, ½ , 0, 0)
z'=-17/2
问题求解
min z= 15 y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 max z'= -15 y1 - 24y2 - 5y3 6y2 + y3 – y4 = 2
st .
5y1 + 2y2 + y3 y1 , y 2 , y3
C CB YB b 1/4 -15 y1 -5/4
≥ 1 ≥
max z = CX + 0Xs st.
AX + IXs = b
X, Xs≥ 0
C
CB 0 XB Xs σ b b
C
X I
0
Xs
CB
XB B
CN
XN N
0
Xs I
C CB XB b
-1
CB XB
CN XN
0 Xs CB CB
-1
C XB b
-1
CB XB B B
-1 -1
CN XN B N
-1 -1
对偶规则

——
变量、约束与系数
原问题有m个约束条件，对偶问题有m个变量
原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵
对偶规则—— 变量与约束对应关系
原问题（对偶问题）
对 称 形 式
max z = CX
st. AX ≤ b X≥ 0 其中： C=（c1，c2, b=（b1，b2, X=（x1，x2, Y=（y1，y2,
min w = YTb T AY ≥ C st. Y≥ 0
a11 a12 … … … a1n a1n
┇
… … … …
,cn) ,bm)T ,xn)T ,ym)T
min w = b1y1 +
b2y2'- b2y2" - b3y3'
a11y1 + a21y2'– a21y2" - a31y3'≥ c1 -a12y1 - a22y2'+ a22y2" - a32y3'≥-c2 st. a13y1 + a23y2'– a23y2"- a33y3'≥ c3 -a13y1 - a23y2'+ a23y2"+ a33y3'≥-c3 y1 , y2', y2" ，y3'≥0