当前位置：文档之家 › 对偶理论与灵敏度分析(1)

对偶理论与灵敏度分析(1)

  • 格式：ppt
  • 大小：1.31 MB
  • 文档页数：62

下载文档原格式

  / 62

合集下载

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

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

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）面积一定，周长最短的矩形是正方形。 • 这种表述有利于加深对事物的认识和理解。 • 线性规划问题也有对偶关系。

第二章 对偶理论和灵敏度分析

第二章 对偶理论和灵敏度分析
经整理得 : min 20 y1 10 y2 5 y3 3 y1 4 y2 y3 4 s.t. 2 y1 3 y2 y3 5 y 0, y 0, y 不限 2 3 1
Slide 12
4 5 5 0
第二章 对偶理论和灵敏度分析
c
CB
CN
x
b XB -Z B-1b -CBB-1b
θ
XB
B-1B 0
XN
B-1N CN－CBB-1 N
二、对偶问题的经济含义
每一个线性规划问题，都存在一个与它密切相关的线性 规划的问题，我们称其中的任一个为原问题，另一个为对 偶问题。任何线性规划问题都有其对偶问题。 对偶思想： 周长一定的矩形,以正方形面积最大 面积一定的矩形,以正方形周长最小 P6 例1.1：MAXZ=3X1+2X2+5X3 S.T. X1+2X2+X3<=430 3X1+2X3<=460 X1+4X2<=420 X1,X2,X3>=0
《运筹学》 第二章 对偶理论和灵敏度分析 Slide 4
设X1、X2、X3分别为生产甲、乙、丙三种产品的产量。 解见P71表1.63。 假如有另外一个工厂要求租用该厂的全部生产能力另做 他用。 那么该厂的厂长应该如何来确定合理的租金（各道工序 的每分钟加工能力的定价）呢? 出租所得的利润应不小于原来用于生产甲、乙、丙三种 产品的利润。 而对于租用生产能力的厂家，考虑的是在尽量满足上述 条件的基础上，总的租用花费最少。 设Y1、Y2、Y3为第一、第二、第三道工序每分钟的租金 。
《运筹学》 第二章 对偶理论和灵敏度分析 Slide 17
五、对偶单纯形法
对偶单纯形法是应用对偶原理求解原问题线性规划的一 种方法，采用的技术是在原问题的单纯形表格上进行对偶处 理。 注意：对偶单纯形法不是求解对偶问题的单纯形法。 对偶单纯形法的基本思想：当一个原始问题从可行但不 最优开始，并继续保持可行直到取得最优解的时候，也就是 它的对偶问题从不可行但比最优还好开始并继续保持最优直 到取得可行最优解。 当原问题在寻找最优性的时候，对偶问题相应地寻找可 行性。P56图1.12

运筹学(二)

运筹学(二)
C
CB
b
CN
0
CB CB
xB XB
XB
B B
CB CB B1B
1
XN
B 1 N
CN CB B1 N
XS
B 1
CB B 1
B 1b
cz
若XB为最优基变量，则对应的目标函数值为： z CB XB CN XN 0 X S CB B1b
且对于上表中各检验数，有：
min W Y b
可见，当原问题得到最优解时，其松弛变量检验数的相反数 CB B 是该问题的对偶问题的一个可行解。
1
例：
原问题
对偶问题
max z 2 x1 x2
同样，少生产一件I产品，则可以 节省设备A、设备B和调试工序0、 6、1个小时，把这些资源出租， 就可以获得租金0y1+6y2+y3
但少生产一件I产品，则 丧失了2元的利润
所以，只有当 6 y2 y3 2
5 y1 2 y2 y3 1
总的出让费 最低出让费即为：
15 y1 24 y2 5 y3
max z c1 x1 c2 x2 c3 x3 c3 x3
a11 x1 a12 x2 a13 x3 a13 x3 b1 a21 x1 a22 x2 a23 x3 a23 x3 b2 st . a21 x1 a22 x2 a23 x3 a23 x3 b2 a31 x1 a32 x2 a33 x3 a33 x3 b3 x1 , x2 , x3 , x3 0
(1 ) (2) (3)
约束（2）可以用以下两个约束来表示：
a21 x1 a22 x2 a23 x3 a23 x3 b2 (2 -1) a21 x1 a22 x2 a23 x3 a23 x3 b2 (2 - 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

对偶理论与灵敏度分析课件

对偶理论与灵敏度分析课件

航空航天领域
飞机和航天器的设计过程中需要 对气动性能、结构性能等进行灵
敏度分析，以优化设计方案。
机械工程领域
在机械设计中，需要对机构性能 、动力学特性等进行灵敏度分析 ，以提高机械设备的性能和稳定
性。
环境工程领域
在环境治理和生态保护方面，需 要对污染物扩散、水体自净等进 行灵敏度分析，以制定有效的环
详细描述
在机器学习中，我们通常会使用各种模型来预测未知数据。对偶理论和灵敏度分析可以 帮助我们理解这些模型的预测能力和泛化性能。例如，通过对偶理论，我们可以将一个 复杂的模型转化为一个更简单的模型，从而更容易理解和使用。同时，灵敏度分析可以
用来研究模型参数变化对预测结果的影响，从而更好地调整模型参数。
详细描述
在优化问题中，对偶理论可以将原问题转化为一个等价的优 化问题，有时这个新问题可能更容易求解。同时，灵敏度分 析可以用来研究原问题的参数变化对最优解的影响，从而更 好地理解问题的性质和最优解的稳定性。
金融问题中的对偶与灵敏度分析
总结词
在金融领域，对偶理论和灵敏度分析可 以用于风险评估、投资组合优化等问题 。
对偶理论的应用场景
资源分配问题
对偶理论可以应用于资源分配问 题，通过求解对偶问题来获得最
优解。
运输问题
对偶理论可以应用于运输问题，通 过求解对偶问题来获得最优解。
投资组合优化
对偶理论可以应用于投资组合优化 问题，通过求解对偶问题来获得最 优解。
02
灵敏度分析简介
灵敏度分析的定义
01
灵敏度分析是指对系统参数变化 引起系统性能变化的程度进行分 析，旨在了解系统对参数变化的 敏感程度。2
灵敏度分析算法的改进

对偶理论与灵敏度分析

对偶理论与灵敏度分析
对偶理论与灵敏度分析
第三章 对偶理论与灵敏度分析
第一节 对偶问题的提出
例：常山机械厂生产Ⅰ和Ⅱ两种产品。生产中需使用A、B、C三种设备进行加工，加工每件Ⅰ产品或Ⅱ产 品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生 产Ⅰ和Ⅱ产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。
4x1 +2x2 - x3 20 y2 x1，x2 ， x3 0 解：该问题的对偶问题： min w = 10 y1 + 20 y2 s.t. y1 + 4y2 10
y1 + 2y2 1 2 y1 - y2 2
y1，y2 0
第一节 对偶问题的提出
例：写出下列线性规划问题的对偶问题 min w = x1 + 2x2 + 3x3
解：化为对称形式。 令 x2 x2，x3 x3 x3 (x3 0, x3 0) max z c1x1 c2x2 c3x3 c3x3
s.t. a11x1 a12x2 a13x3 a13x3 b1
aaa222a111xxx2111x1 aaa222a222xx2x2222x2 aaa222a333xxx23333x3 aaa222a333xxx23333x3 bbb222b2 a3a13x11x1 a3a23x22x2 a3a33x33x3 a3a33x33x3 b3b3 x1, x2 , x3, x3 0
a21x1 + a22x2 + … + a2nxn ≤ b2 ……
am1x1 + am2x2 + … + amnxn ≤ bm xj ≥ 0 （j = 1,2,…,n）
则称下列 LP 问题
min w = b1 y1 + b2 y2 + … +bm ym s.t. a11y1 + a21 y2 + … + am1ym ≥ c1

运筹学-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

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

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

第三章线性规划对偶理论与灵敏度分析习题 一、思考题1．对偶问题和对偶变量的经济意义是什么？2．简述对偶单纯形法的计算步骤。

它与单纯形法的异同之处是什么？3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+kn σ（标准形为求最小值），其经济意义是什么？8．将i j ji bc a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确1．任何线性规划问题都存在且有唯一的对偶问题。

2．对偶问题的对偶问题一定是原问题。

3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。

4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。

5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。

6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。

7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。

8．对于i j ji bc a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。

9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。

10．应用对偶单纯形法计算时，若单纯形表中某一基变量0<i x ，且i x 所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。

第二章对偶理论及灵敏度分析

第二章对偶理论及灵敏度分析
三、非对称形式的原-对偶问题
四、对偶问题的写法
第3页，共68页。
返回本章目录
引言
在实际问题中，一个问题的优化往往可以从不同的 两个角度提出问题。
譬如，要求在有限资源条件下生产利润最大；或在一 定生产能力条件下使资源消耗最少。
所以，在线性规划中，对任一给定的求最大值问题，相 应也存在一个求最小值的问题。且两者包括有相同的数据。
6x3 4
1
x1 x1
x2 x3 x3 , x2 , x3 , x3 0
4
x1x, 1x2,
x2 x3
x3 x3 , x3 0
4
第14页，共68页。
max z x1 4 x2 3 x3 3 x3
2 x1 3 x2 5 x3 5 x3 2
3 x1 x1 x2
m aaay111iin21 nyyyw1110 a aab(1222iyn12 y1yy222 1,b2 2 ,y2 ,aam a mmm)12 nyyymmm bmycccm 12n
(2.4)
第7页，共68页。
矩阵形式表示的原问题与对偶问题
原问题： maxz CX XAX0b (2.5)
4 3 3
5
y
1
6 y 2
y 3
y 3
3
y1 , y 2 , y 3 , y 3 0
min w 2 y1 y 2 4 y 3
2 y1 3 y2 y3 1
3 5
y1 y1
y2 6y
y3 4 2 y3 3
5
y
1
6
y2
y3
3
y1 0 , y 2 0 , y 3无约束
第15页，共68页。
min w 2 y1 y 2 4 y 3

运筹学：对偶理论与灵敏度分析习题与答案

运筹学：对偶理论与灵敏度分析习题与答案

一、填空题1、对偶问题的对偶问题是（）。

正确答案：原问题2、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y﹡b。

正确答案：=3、若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX（）Yb。

正确答案：<=4、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y*b。

正确答案：=5、设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为（）。

正确答案：min=Yb YA>=c Y>=06、影子价格实际上是与原问题各约束条件相联系的（）的数量表现。

正确答案：对偶变量7、线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为（）。

正确答案：AT8、在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，…n)，则原问题（）。

正确答案：无解二、选择题1、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。

A. “≥”B. “≤”C. “>”D. “=”正确答案：A2、如果z*是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡满足（）。

A.W﹡=Z﹡B.W﹡≠Z﹡C.W﹡≤Z﹡D.W﹡≥Z﹡正确答案：A3、如果某种资源的影子价格大于其市场价格，则说明（）。

A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开辟新的生产途径正确答案：B4、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。

A.≥B.≤C. >D. =正确答案：A5、对偶单纯形法的迭代是从（）开始的。

A.正则解B.最优解C.可行解D.可行解正确答案：A6、如果某种资源的影子价格大于其市场价格，则说明（）。

A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开辟新的生产途径正确答案：B7、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。

[学习]对偶理论和灵敏度分析

[学习]对偶理论和灵敏度分析

maxw=5y1+4y2+6y3
s.t. y1+2y2 ≥2
y1
+y3 ≤3
-3y1+2y2+y3 ≤ -5
y1 -y2 +y3 = 1
y1≥0 ,y2≤0,y3无约束
minz=2x1+3x2-5x3+x4
比较原问题 s.t. x1+x2-3x3+x4≥5
和对偶问题
2x1 +2x3-x4≤ 4
x2+x3+x4 = 6
19
当B为最优基时，XB为最优解时，则有：
CN-CBB-1N≤0 -CBB-1≤0
∵CB-CBI=0
代入得：
整理得：
CN－CBB-1N+CB-CBI≤0 C－CBB-1(B+N)≤0
C－CBB-1 A≤0 -CBB-1≤0
令CBB-1为单纯形乘子，Y‘＝CBB-1 则：
C－Y’ A≤0
Y’ A≥C’
CB
YB
b
y1
24
y1
-x1+2x2-3x3 = 12 2x1+x2+2x3 ≤ 8 x1+3x2-x3 ≥ 15 x1≥0 x2≤0 x3: Free
max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4≤ 2
-w1+2w2+ w3+3w4 ≥ 4 2w1- 3w2+2w3- w4 = -1 w1 ≥ 0,w2Free,w3 ≤ 0,w4 ≥ 0
2 C(0,1)
1 B(1.9,0.4)
O(0,0) 0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
设生产三种产品各为x1, x2, x3公斤，总利 为Z元。于是得 max Z 3x1 5x2 4x3
2x1 3x2 1500
s.t. 2x2 4x3 800
3x1 2x2 5x3 2000 x1, x2 , x3 0
8
对偶问题
设出售材料的定价为每单位 yi 元，
* 获利为 W 元
12
原问题（或对偶问题） 对偶问题（或原问题）
目标函数 MaxZ
目标函数 MinW
约束条件数：m个 第i个约束条件类型为“≤” 第i个约束条件类型为“≥” 第i个约束条件类型为“=”
对偶变量数：m个 第i个变量≥0 第i个变量≤0 第i个变量是自由变量
决策变量数：n个 第j个变量≥0 第j个变量≤0 第j个变量是自由变量
（3）对偶问题的解正是原问题的最优表中松驰变 量 在检验数行中的数。反之，原问题的解正是对 偶问题的最优表中松驰变量 在检验数行中的数。
（4）对偶问题的解yi称为资源的影子价格。
26
原问题
对偶问题
每次迭代，检验数行的数
基解（最优表中是最优解
------影子价格）
松馳变量
决策变量
决策变量
松馳变量
基变量
对偶问题 (min)
技术系数矩阵 AT
右端项 b
价值系数 C
对偶变量 yi 0
对偶变量 yi 0
对偶变量 yi 不限
第 j 行约束条件为 型
第 j 行约束条件为 型
第 j 行约束条件为 = 型
• 约束条件的类型与非负条件对偶 • 非标准的约束条件类型对应非正常的非负条件 • 对偶变换是一一对应的
非基变量
非基变量
基变量
目标函数值 =
目标函数值
练习P.30例14
27
2.4.5 对偶变量的经济意义和影子价格
1、影子价格（Shadow Pyice)：对资源在生产中做出的贡献而 做出的评价。它不是市场价格。资源的市场价格是已知的， 而影子价格有赖于资源的利用情况，是未知的。
对偶变量的经济意义就是影子价格.
s.t5 y1 2 y2 y3 y5 1
y1,
y2，y3 ,
y4 ,
y5
0
23
约束条件两端乘以“-1”得
max w 15y1 24y2 5y3 0y4 0y5
6 y2 y3 y4 2
s.t 5y1 2 y2 y3 y5 1
y1,
y2，y3
,
y4
,
y5
0
24
cj
约束条件数：n
第i个约束条件类型为“≥”
第i个约束条件类型为“≤”
第i个约束条件类型为“=”
13
课堂练习：写出下面线性规划的对偶规划：
MinZ 4x1 2x2 3x3
4x1 5x2 6x3 7
s.t.182x1x191x32 x2
10x3 14ຫໍສະໝຸດ 11x1 0, x2符号不限, x3 0
4、对偶定理：若两个互为对偶问题之一有最优解，则 另一个必有最优解，且目标函数值相等。
5、互补松弛性定理： X* 、Y*分别是原问题和对偶问题的
可行解，则 和Y*XL=0
X*
、Y*是最优解的充分必要条件是X*YS
=0
6、解的对应定理：原问题的单纯形表的检验数行对应
其对偶问题的一个基解.
由解的对应定理可知，当在检验数行得到对偶问题的 解可行时，原问题已达到最优解。
21
出基原则：小于0的 bi中最小者（绝对值最大者）所对应的行变
量。即在所有bi <0中，
原b问r 题m的iin进b对基i 应原的则变：量j yr出CB基B，-1Pyj r-所C在j 中行0最为小主对元应行的。列变量。
（4）确定“进基”变量
若主元行中没有负元素，可以证明问题没有可行解，计算结束。
2
对偶问题?
• 任何线性规划问题都有其对偶问题 • 对偶问题有其明显的经济含义
假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？
3
原问题—简单的生产计划问题
某工厂生产甲、乙两种产品，单位产品 利润、耗工耗料及工料限额为下表
产品 甲
项目
材料
2
工时
3
利润(元)/件 4
乙 限额
3
24
第4章 主要内容：
• 对偶规划 • 对偶理论 • 对偶单纯形算法
1
4.1对偶问题的提出
现从另一个角度来讨论，假定工厂考虑不 安排生产，而是出售原材料，出租工时或转产 新产品等。问如何定价，可使工厂获利不低于 安排生产所获得的收益，且又能使这些定价具 有竞争力？
设出售原料的定价为毎公斤y1元，出租工时 的定价为毎工时y2元.从工厂考虑，这些定价下 的获利不应低于安排生产所获得的收益。否则 工厂宁可生产，而不出售或出租或转产等,由此 考虑出售或出租或转产的数学模型.
16
2.4.3 对偶问题的基本性质定理
1、对称性定理：对偶问题的对偶是原问题。
2、弱对偶定理：若X(0)是原问题的可行解, Y(0)是对偶问 题的可行解,则有CX(0) ≤ Y(0)b.
3、最优性定理：若X(0)是原问题的可行解, Y(0)是对偶问 题的可行解,且有CX(0) = Y(0)b则 X(0) 、Y(0)分别是原问题和 对偶问题的最优解。
0 J
1/6 -1/6 0
[-2/3] -1/3 1
1 40
0 -1/4 1/4
1 1/2 -3/2
w
-17/2 15/2 0
0 2/7 3/2 25
原问题的最优解为(0,1/4,1/2),最优值为17/2
由上例得结论：
（1）当约束条件为“≥”时，不必引进人工变量， 使计算简化。
（2）由对偶问题的性质知道：用单纯形法求解L.P 问题时，每一次迭代可得一个基解，这时检验数 行的数是对偶问题的一个基解。原问题的松驰变 量对应着对偶问题的决策变量，对偶问题的松驰 变量对应着原问题的决策变量。在一个问题中是 基变量，则在另一个问题中就是非基变量 ，反之 亦然。
y1符号不限, y2 0, y3 0 y1符号不限, y2 0, y3 0
√
×
（原问题是极小化问题，因此应从原始对偶
表的右边往左边查！）
15
（二）非对称形式的对偶问题 （1） 如果原问题约束中包含等式约束，如AX=b 等价于
AX b AX b
(2)如果x j 0,可用xj x j 0代替。 （3）如果x j取值无约束，可用x j xj xj代替 （xj，xj 0）
每迭代一次，就使目标函数值增大一次， 当问题取得最优解时，目标函数达到最大 值。
对偶单纯形法特点：将单纯形法应用于对偶 问题的计算，在保持对偶问题有可行解的 基础上，每迭代一次，就使目标函数值减 少一次，当问题得到最优解时，目标函数 取到最小值。
20
2、对偶单纯形法的计算步骤 （1）把对偶问题化为标准形，但允许主约束条件右
CB YB b
0 y4 -2
0 y5 -1
w
0
-24 y2 1/3 0 y5 -1/3
w -8
-24 y2 1/4 -5 y3 1/2
-15 y1 0 -5 15
0 -5 15 -5/4 15/2
-24 y2 [-6]
-2 24
1 0 0 1 0
-5 0 y3 y4
0
y5
-1 1 0
-1 0 1
5
0
,2xx22
26
0
目标函数 约束条件
“s.t.”:Subject to
线性规划
5
新问题—简单的生产计划问题
设出售原料的定价为毎公斤y1元，出租工时的 定价为毎工时 y元2 .
min w 24 y1 26 y2
s.t. 2 y1 3y2 4
3y1 2 y2 3 y1, y2 0.
6
2
26
3
如何安排一天的生产计划，使企业利润最大？
4
解：设甲、乙产品的产量分 别为x1, x2 ,则
利润 Z 4x1 3x2
决策变量
限制条件：
2x1 3x2 24
3x1 2x2 26
x1 0, x2 0
数学模型： max Z 4x1 3x2
2x1 3x2 24
s.t.3xx11
min W 1500 y1 800 y2 2000 y3 2 y1 3y3 3
s.t. 3y1 2 y2 2 y3 5
4 y2 5 y3 4 y1, y2 , y3 0
定义 2.4.1：称上述的两问题之一 为原问题，则另一问题称为对偶问题， 两者互为对偶。
9
原问题与对偶问题的关系
17
对偶定理
是揭示原始问题的解与对偶问 题的解之间重要关系的一系列定理。
18
2.4.4 对偶单纯形法
什麽是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法——在原始问题的单 纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！
19
2.4.4 对偶单纯形法
1、两种方法的特点 单纯形法特点：在保持基可行解的情况下，
• （一）对称形式的对偶问题 • 比较上述的两个互为对偶问题：
max Z 3x1 5x2 4x3
2x1 3x2 1500 s.t. 2x2 4x3 800
3x1 2x2 5x3 2000 x1, x2 , x3 0
min W 1500y1 800y2 2000y3 2 y1 3y3 3
显然：对称形式的对偶问题，若已知其中 一个问题，立即就可以写出相应的对偶问 题。
11
表2.13 对偶变换的规则
原问题 (max)
技术系数矩阵 A 价值系数 C 右端项 b