当前位置：文档之家 › 第二章 对偶理论和灵敏度分析PPT课件

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

  • 格式：ppt
  • 大小：1.17 MB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

对偶理论和灵敏度分析

对偶理论和灵敏度分析
从新的基，基变量开始。
可编辑ppt 23
福州大学公共管理学院
计算非基变量的检验数，确定换入变 量。
N1 CN1 CB1B11N1 ( 注意：N1 P1,P5 )
2,
0
(
0,0,3
1 )0
0 1
1/ 21 0 0 4 0
0 0 1/ 4 0 1
2, 3 / 4 对应 x1,x5
换入变量
a( 2) 23
a( 2) m3
a( 2) 2m
a( 2)
mm
可编辑ppt 13
福州大学公共管理学院
重复以上的步骤，直到获得
1
EmE2E1A
1
A1
1
可编辑ppt 14
福州大学公共管理学院
• 求单形法求解线性规划问题：
maxz 2x1 3x2 0x3 0x4 0x5
可编辑ppt
24
福州大学公共管理学院
(3) 确定换出变量
计算：
表示选择>0的元素
min
B11b B11P1
i i
B11P1 0
m
in
2 1
,16,3 4 0
2
对应x 1
可编辑ppt 25
福州大学公共管理学院
B 2 P1 , P4 , P2
主元素
1
1
1 0 0
P1 4
B3 P1 ,P5 ,P2 ;
换入变量x5 的系数向量是
1 0 1 / 2 0 1 / 2
B21P5
4
1
2 0 2 主元素
0 0 1 / 4 1 1 / 4
可编辑ppt 32
福州大学公共管理学院
计算B逆矩阵

运筹学对偶理论与灵敏分析PPT课件

运筹学对偶理论与灵敏分析PPT课件

2x1 x2 3x3 2x4 20
x1
4
0
试验证弱对偶性原理。
第25页/共86页
解：
m i nW 20y1 20y2
（D）
y1 2 y2 1
22
y1 y1
y2 3 y2
2 3
3 y1 2 y2 4
y1 0, y2 0
由观察可知：
__
X =（1.1.1.1），
Y__=（1.1），分别是
（1）若原问题是
MaxZ CX
(P)
s.t.
AX b X 0
(2) 其对偶问题为
MinW bY
(D)
YA C
s.t.
Y
0
这两个式子的变换关系称为“对称形式的对偶关系”。
第11页/共86页
怎样写出非对称形式的对偶问题？ 根据对应规律（参见对偶关系表）直接 写出；
第12页/共86页
原问题（或对偶问题） 对偶问题（或原问题）
第7页/共86页
如果模型(2.1)称为原问题（P）， 则模型(2.2)称为对偶问题（D）。 任何线性规划问题都有对偶问题。
原问题与对偶问题之间没有严格的 界限，它们互为对偶。
第8页/共86页
(P) 例1.1
MaxZ 2x1 3x2
x1 2x2 8
s.t.44
x1 x2
16 12
x1, x2 0
第37页/共86页
对偶性质定理总结：
定理2弱对偶定理： 判断原问题（对偶问题）目标函数值的上界 （下界）。
定理3、4、5： 判断原问题（对偶问题）解的两种对应关系。
判断原问题（对偶问题）有无最优解。
定理6互补松弛性定理： 根据原问题（或对偶问题）最优解，直接求出 对偶问题（或原问题）的最优解。

第02章 线性规划的对偶理论及灵敏度分析 《运筹学》PPT课件

第02章 线性规划的对偶理论及灵敏度分析 《运筹学》PPT课件

x1, x2 ,, xn 0
对 称 形 式 的
的 定 义
minW b1y1 b2 y2 bm ym
对
s.t.
a11 a12
a1n
a21 a22
a2n
am1 y1 c1
am2
y2
c2
amn ym cn
偶 问 题
y1, y2 ,, ym 0
max Z CX
用5h设备A,2h设备B及1h调试可 生产一件家电Ⅱ，赢利1元
该公司希望用最小代价把美佳公司的全部资源收买过来，即：
min z 15y1 24y2 y3
问 题 的 导 出
例2-1
综上所述，
（LP2） min w 15y1 24y2 y3
6 y2 y3 2
s.t.5 y1 2 y2 y3 1
的
x1, x2,, xn 0
对
minW b1y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym c1
偶 问 题
a12y1
a22 y2
am2 ym
c2
a1n y1 a2n y2 amn ym cn y1, y2 ,, ym符号不限
对
例2－3
称
minZ 4x1 2x2 3x3
[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1] •若初始矩阵中变量xj的系数向量为Pj，迭代后为 Pj′，则有Pj′=B-1Pj •当B为最优基时，表中应有
CN-CBB-1N≤0,-CBB-1≤0
例2-5
对
偶
参看例2-1中的原问题和对偶问题，并分别加上松 弛变量和剩余变量，如下：
23 3

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

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

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

运筹学——对偶问题与灵敏度分析幻灯片PPT

运筹学——对偶问题与灵敏度分析幻灯片PPT
产品A 产品B 资源限制
劳动力
9
4
360
设备
4
5
200
原材料
3
10
300
单位利润 70
120
OR1
18
Cj
CB XB
0 X3 0 X4 0 X5
σj
0 X3 0 X4 120 X2
σj
70 X3 1200 X1
X2 σj
OR1
b
360 200 300 0
240 50 30 3600
84 20 24 4280
〔1〕根据LP问题，列出初始单纯形表。检查b列的数字， 假设都为非负，检验数都为非正，那么已得到最优解， 停顿计算。假设检查b列的数字时，至少还有一个负分 量，检验数保持非正，那么进展以下计算。
〔2〕确定换出变量：将B-1b中最小的负分量所对应的 变量确定为换出变量。
〔3〕确定换入变量：检查换出变量所在行〔第L行〕的
〔3〕在灵敏度分析中，有时需要用对偶单纯形 法，这样可使问题的处理简化。
OR1
29
2.2灵敏度分析〔考研时常考的知识点〕
灵敏度分析通常有两类问题：①是当C,A,b 中某一局部数据发生给定的变化时，讨论 最优解与最优值怎么变化；②是研究 C,A,b中数据在多大范围内波动时，使原 有最优基仍为最优基，同时讨论此时最优 解如何变动？
OR1
22
对偶单纯形法
设有问题maxZ=CX ，
AX ＝b ，
X ≥0
又设B是其一个基，当非基变量都为0时， 可以得到XB=B-1b。假设在B-1b中至少有 一个负分量，设第i个为负分量，并且在单 纯形表的检验数行中的检验数都为非正，
这种情况就可以用对偶单纯形法来进展求 解。

运筹学线性规划对偶理论与灵敏度分析ppt课件

运筹学线性规划对偶理论与灵敏度分析ppt课件
2020/2/21
2020/2/21
一、单纯形法计算的矩阵描述
本节以对称形式的原始-对偶问题为讨论的基础， 除非特别需要，一般不再专门说明。
P. max z = CX AX≤b
D. min w = Yb YA≥C
X≥0
Y≥0
原问题通过加入松弛变量 Xs 可以化为标准形式：
max z = CX +0Xs st. AX + IXs = b
max z = x1－2 x4 + x5 － x6
x1 － x4 － x5 + x6 ≤ 2 x1－ x4 － x5 + x6 ≤ - 1 x1 + x4 + x5 － x6 ≤ 1 2x1+ x4 － x5 + x6 ≤- 2 x1 , x4 , x5 , x6 ≥0
（2）写出上述 对称形式线性规 划问题的对偶。
a12y1+ a22y2 + … + am2ym ≥ c2 ……
a1ny1+ a2ny2 + … + amnym ≥ cn y1 , y2 , …, ym ≥0
2020/2/21
原问题：
max z = C X AX ≤ b X ≥0
Y=(y1,y2,…,ym) 对偶问题： min w = Y b YA≥C Y≥0
max z =c1x1+ c2x2 +… + cnxn
a11x1+ a12x2 + … + a1nxn ≤ b1
st.
a21x1+ a22x2 + … + a2nxn ≤ b2 ……
am1x1+ am2x2 + … + amnxn ≤ bm

运筹学对偶理论与灵敏度分析PPT资料(正式版)

运筹学对偶理论与灵敏度分析PPT资料(正式版)

得一个基可行解
X
(1)
B 0
1b
对应的目标值 z= CB B-1 b
单纯形表的几个特征: 1、检验数:
非基底的检验数(等于对应的目标系数) cj –zj=( CN–CBB-1N)
基变量的检验系数为零，即 cj –zj= CB–CBB-1 B=0
进一步，非基底变量可分解XN →（XN1，Xs），其中 XN1 表示除去松弛变量以后的非基变量；Xs是松弛变量，其目标 系数为零。
主要是计算 的差别
maxZ CX0Xs
s.t.
AX b X 0
s.t.
AXIXs b X 0, Xs 0
0 XS b Cj-zj
非基变量 XB XN BN CB CN
基变量 XS I 0
初始表
CB XB B-1b Cj-zj
基变量 XB I 0
非基变量
XN
XS
B-1N
B-1
CN -CB B-1N -CB B-1
Xs非基底的检验数cj –zj=( 0–CBB-1)= –CBB-1 所有的检验数可用C–CBB-1A与–CBB-1表示
2、θ规则的表达形式
m iin ((B B 1 1P bk )i)i (B1P k)i 0 ((B B 1 1b P k )l)l
3、单纯形表的矩阵表达形式 将目标和约束条件改写为： –z+CBXB +C NXN+0 Xs =0， N, s对应非基变量 B XB +NXN+ IXs=b XB为基变量时，经基底转换后有XB , z的表达式: XB + B-1 N1XN+ B-1Xs= B-1b –z+( C N -CB B-1 N ) XN1 - CB B-1 Xs = - CB B-1 b 用矩阵表示为
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2n
am1 am2 amn
Chapter 1
Slide 10
标准(max,)型的对偶变换
1、求目标函数最大值的线性规划问题中有n个变量m个 约束条件，它的约束条件都是小于等于不等式。而其对偶则 是求目标函数为最小值的线性规划问题，有m个变量n个约束 条件，其约束条件都为大于等于不等式。
4、对偶问题的约束条件的系数矩阵A是原问题约束条件 的系数矩阵的转置AT。
P59 例1.18
非标准型的对偶变换 例 2 . 原线性规划问题
max z 4 x 1 5 x 2
s .t.
3 x 1 2 x 2 20 4 x 1 3 x 2 10
x1 x2 5
x 2 不限 , x 1 0
c
CB
x
b
XB
CN θ
XN
XB
B-1b
-Z -CBB-1b
B-1B 0
B-1N CN－CBB-1 N
二、对偶问题的经济含义
每一个线性规划问题，都存在一个与它密切相关的线性 规划的问题，我们称其中的任一个为原问题，另一个为对 偶问题。任何线性规划问题都有其对偶问题。
对偶思想： 周长一定的矩形,以正方形面积最大 面积一定的矩形,以正方形周长最小
2、原问题的目标函数中的变量系数为对偶问题中的约束 条件的右边常数项，并且原问题的目标函数中的第i个变量的 系数就等于对偶问题中的第i个约束条件的右边常数项。
3、原问题的约束条件的右边常数项为对偶问题的目标函 数中的变量的系数。并且原问题的第i个约束条件的右边常数 项就等于对偶问题的目标函数中的第i个变量的系数。
目标函数知道了其中一个最优值也就找到了其对偶问题 的最优值，因为这两个最优值相等。
所以以后我们求解一个线性规划问题时，我们可以把其 对偶问题一起来加以考虑，找一个比较容易求解的来求解， 求出了一个最优值同时也就求出了另一个问题的最优值。
Chapter 1
Slide 7
原问题:
LP OPTIMUM FOUND AT STEP 2
Y1
1.000000 0.000000
Y2
2.000000 0.000000
Y3
0.000000 20.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 4.000000
0.000000
3) 0.000000
-100.000000
4) 0.000000
-230.000000
出租所得的利润应不小于原来用于生产甲、乙、丙三种 产品的利润。
而对于租用生产能力的厂家，考虑的是在尽量满足上述 条件的基础上，总的租用花费最少。
设Y1、Y2、Y3为第一、第二、第三道工序每分钟的租金 。
Chapter 1
Slide 5
对偶问题的最优解，即生产能
力的租金，恰是原问题的对偶价 MINz＝430Y1+460Y2
格，即原问题中各道工序每分钟
+420Y3
加工能力变化一个单位，对目标 函数总利润的影响。
S.T.
原问题的最优解，即生产产品 Y1+3Y2+Y3 >=3
的产量，恰是对偶问题的对偶价 2Y1 +4Y3>=2
格，即生产产品甲、乙、丙的利 Y1+2Y2 >=5
润增加一个单位，总租金要增加 Y1、Y2、Y3>=0
多少。这表明生产计划中安排生
产的产品甲、乙、丙的产量是多
少。
Chapter 1
Slide 6
对偶价格——对偶变量yi(i=1,2,…,m)表示原问题的第i个 约束条件的影子价格（P72-73），它表示在其它条件不变的 情况下，单位资源变化所引起的目标函数的最优值的变化。
对于两个有对偶关系的线性规划的问题我们只要求得了 其中一个最优解，就可以从这个问题的对偶价格而求得其对 偶问题的最优解。
2) 0.000000
1.000000
3) 0.000000
2.000000
4) 20.000000
0.000000
Chapter 1
Slide 8
对偶问题:
LP OPTIMUM FOUND AT STEP 4
OBJECTIVE FUNCTION VALUE
1) 1350.000
VARIABLE VALUE REDUCED COST
三、原问题和对偶问题的关系
原问题: maxz CX
对偶问题 : minYb
s.t.
AX b
X0
YAC
s.t.
Y0
上两式中
X (x1, x2 , , xn )T Y ( y1, y2 , , ym ) C (c1,c2 , ,cn ) b (b1 , b2 , , bm )T
a11
A
P71 例1.1：MAXZ=3X1+2X2+5X3
S.T.
X1+2X2+X3<=430
3X1+2X3<=460
X1+4X2<=420
X1,X2,X3>=0
Chapter 1
Slide 4
设X1、X2、X3分别为生产甲、乙、丙三种产品的产量。
假如有另外一个工厂要求租用该厂的全部生产能力另做 他用。
那么该厂的厂长应该如何来确定合理的租金（各道工序 的每分钟加工能力的定价）呢?
XB=B-1b－B-1NXN
(1)
将(1)式代入目标函数的表达式，可以得到用非基变量表
示目标函数的表达式。
Chapter 1
Slide 2
Z=CX=(CB,CN)(XB,XN)’=CBXB+CNXN =CB(B-1b－B-1NXN)+CNXN =CBB-1b+(CN－CBB-1N)XN =CBB-1b+σXN 注意XB检验数为零，实质上是CB－CBB-1B=0 Y=CBB-1为单纯形乘子
OBJECTIVE FUNCTION VALUE
1) 1350.000
VARIABLE VALUE REDUCED COST
X1
0.000000
4.000000
X2
100.000000 0.000000
X3
230.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
第二章 对偶理论和灵敏度分析
第一节 对偶问题和对偶单纯形法
一、单纯形的矩阵描述
用矩阵语言描述单纯形法的关键是写出两个基本的表达 式，设线性规划的标准型为
maxz=CX
AX=b
X≥0
C=(CB,CN),X=(XB,XN)’,A=(B,N) 由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b,可以得到用非 基变量表示基变量的表达式: