当前位置：文档之家 › 第2章+对偶理论和灵敏度分析-第3节

第2章+对偶理论和灵敏度分析-第3节

  • 格式：pdf
  • 大小：86.68 KB
  • 文档页数：13

下载文档原格式

  / 13

合集下载

《运筹学》胡运权 第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

对偶理论与灵敏度分析

对偶理论与灵敏度分析
Min W=Yb s.t. YA≥C Y≥0
Max W ’= -Yb s.t. -YA≤ -C Y≥0
Min Z ’= (-C)X s.t. (-A)X≥ (-b) X≥0
Max W ’= Y(-b) s.t. Y(-A)≤ (-C) Y≥0
单击此处添加标题
Min W =8y1+16y2+12y3 s.t. y1+4y2 ≥2 2y1 +4y3 ≥3 y1 ,y2,y3 ≥0
单击此处添加标题
（3）对偶问题的对偶是原问题
推导过程
变形
对偶
变 形
对偶
ห้องสมุดไป่ตู้对偶
变 形
Max Z=CX s.t. AX≤b X≥0
例4 考虑下面一对LP问题
其对偶问题为：
由于X(0) =(1,1,1,1)T, Y(0)=(1,1)T分别为(L),(D)的可行解，
Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20 s.t. 2x1+ x2+3x3+2x4 ≤20 x1,x2,x3,x4 ≥0
二、对偶问题
对称LP问题的对偶问题
变量为非负； 约束条件为不等式。 对于max ，约束为“” ； 对于min，约束为“”
对称LP问题的定义 第一类对称形式 第二类对称形式
例1 写出下列LP问题的对偶问题
单击此处添加标题
对偶
单击此处添加标题
Max Z =2x1+3x2 s.t. x1+ 2x2≤8 4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0
Min W = 20y1+20y2 y1+2y2 ≥ 1 2y1+ y2 ≥ 2 s.t. 2y1+3y2 ≥ 3 3y1+2y2 ≥ 4 y1,y2≥0

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

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

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

第二章 对偶理论和灵敏度分析
经整理得 : 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

对偶理论和灵敏度分析(新)

对偶理论和灵敏度分析(新)
minZ=2x1+2x2+4x3 s.t. x1+3x2+4x3≥2 2x1+ x2+3x3≤3 x1+4x2+3x3=5 x1 ≥0, x2≤0
minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y3≥1 4y1-2y2+3y3= -2 3y1+6y2+4y3≥3 y1≤0,y2≥0
-w1+2w2+ w3+3w4 ≥ 4 2w1- 3w2+2w3- w4= -1 w1 ≥ 0,w2Free,w3 ≤ 0,w4 ≥ 0
原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；
原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。
原始问题变量的性质影响对偶问题约束条件的性质。
原始问题约束条件的性质影响对偶问题变量的性质。
max z=c1x1+c2x2+……+cnxn s.t. a11x1+a12x2+……+a1nxn ≤b1
a21x1+a22x2+……+a2nxn ≤b2 ……
am1x1+am2x2+……+amnxn ≤bm x1, x2, ……, xn ≥0
min w=b1y1+b2y2+……+bmym s.t. a11y1+a21y2+……+am1ym ≥c1
X ≥0
max
C
m
A
≥b
n
对偶问题 min w=Y’b s.t. A’Y≥C’
Y ≥0 min b
n AT ≤ C

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

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

x1
x2
xj
xn 0
减少一件产品可以节省的资源
机会成本a1jy1+ a2jy2+ …… aijyi+ ……amjym
表示减少一件产品所节省的资源可以增加的利润
运筹学第二章对偶理论与灵敏度分析
4、产品的差额成本（Reduced Cost）
机会成本
差额成本
利润
min w b1y1 b2 y2 bm ym
运筹学第二章对偶理论与灵敏度分析
min w=YTb
ATY ≥ CT st.
Y ≥0
1,若原问题目标是求极大化，则对偶问题的目标是 极小化，反之亦然。
特对 点偶
问 题 的
2,原问题的约束系数矩阵与对偶问题的约束系数矩 阵互为转置矩阵。
3,极大化问题的每个约束对应于极小化问题的一个 变量，其每个变量对应于对偶问题的一个约束。
6 y2 + y3 ≥2
题对 偶
St. 5y1 + 2y2 + y3 ≥1
问
y1、y2 、y3 ≥0
最终表
210 0
CB 基 b x1 x2 x3 x4
0 x3 15/2 0 0 1 5/4 2 x1 7/2 1 0 0 1/4 1 x2 3/2 0 1 0 -1/4
cj－zj
0 0 0 -1/4
0 x5 -15/2 -1/2 3/2 -1/2
≤
≥
约束条件
≥
≤
变量
=
无约束
≥
≥
变量
≤
≤
无约束
=
运筹学第二章对偶理论与灵敏度分析
约束条件
§2.2 对偶问题的基本性质
性质1 弱对偶性

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

建立非对称形式线性规划问题旳对偶模型可采用下 列环节： （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 为初始可行基，松 弛变量作为初 始基变量旳。因为松弛变量作为基变

运筹学02对偶理论(2)对偶单纯形法,灵敏度与参数分析

从满足条件(2)的基出发去找原问题的最优解→ 对偶单纯形法思想： 从满足条件(2) 的基(一般称为正则基)B出发，经 过换基运算到另一个正则基，即一直保证条件 (2)成立， 直到找到一个满足条件(1)的正则基。
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
注：当模型的数据发生变化后，不必对线性规划问题
重新求解，而用灵敏度分析方法直接在原线性规划取
得的最优结果的基础上进行分析或求解 . 线性规划的参数分析(Parametric Analysis)是研究和分
析目标函数或约束中含有的参数μ在不同的波动范围内 最优解和最优值的变化情况．这种含有参数的线性规划
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
X XB σ
b
B-1A B-1b C-CBB－1A －CBB－1b 若上表为最优单纯形表，则下列两个式子同时成立：
(1) B1b 0 (可行性条件，又叫对偶最优性条件)
(2) C CB B 1 A 0 (最优性条件,又叫对偶可行性条件)
4.最优解、无可行解的判断。
作业：教材P81 1.12 (2)
下一节：灵敏度分析与参数分析
3.4 灵敏度与参数分析
Sensitivity and Parametric Analysis
3.4 灵敏度与参数分析 Sensitivity and Parametric Analysis
Chapter3 对偶理论 Dual Theory
3.3 对偶单纯形法 Dual Simplex Method
max z 7 x1 3x 2

运筹学课件-第二章对偶理论与灵敏度分析

对偶问题与原问题
对偶问题的目标函数是原问题约束条 件中某个或某几个变量的函数，而对 偶问题的约束条件是原问题目标函数 中某个或某几个变量的函数。
对偶问题的性质
对偶弱对偶性质
01
如果原问题是凸的，则对偶问题是弱对偶的。
对偶强对偶性质
02
如果原问题是凸的，且存在最优解，则对偶问题是强对偶的。
对偶互补性质
01
03
椭球法是一种基于椭球算法的线性规划方法，通过对 偶理论将原问题转化为对偶问题，然后利用椭球算法
求解对偶问题，最终得到原问题的最优解。
04
单纯形法是一种基于线性规划的直接算法，通过对偶 理论将原问题转化为对偶问题，然后利用单纯形表格 求解对偶问题，最终得到原问题的最优解。
动态规划的对偶算法
动态规划的对偶算法主要包括状 态转移方程和最优子结构等。这 些算法通过求解对偶问题来找到 最优解，其中状态转移方程用于 描述问题的状态转移过程，最优 子结构用于描述问题的最优解的 结构。
03
如果原问题有最优解，则对偶问题的最优解与原问题的最优解
互补。
对偶理论的应用场景
1 2
线性规划
在求解线性规划问题时，可以利用对偶理论将原 始问题转化为对偶问题，简化计算过程。
运输问题
在求解运输问题时，可以利用对偶理论将原始问 题转化为对偶问题，从而得到最优解。
3
分配问题
在求解分配问题时，可以利用对偶理论将原始问 题转化为对偶问题，从而得到最优解。
通过物流配送的模型灵敏度分析，可以确定哪些参数对物流配送过程的影响较大，哪些 参数对物流配送过程的影响较小，从而对物流配送模型进行优化和调整。
模型灵敏度分析可以帮助企业更好地理解物流配送过程的特性，提高物流配送的效率和 质量，降低物流成本和风险。

《运筹学》胡运权第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
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第2章 对偶理论和灵敏度分析
第3节 对偶问题的提出
第1章例1的不同表述
• 现从另一角度来讨论这个问题。 • 假设该工厂的决策者决定不生产产品Ⅰ、 Ⅱ，而将其所有资源出租或外售。这时工厂 的决策者就要考虑给每种资源如何定价的问 题 • 设用y1，y2，y3分别表示出租单位设备台时的 租金和出让单位原材料A，B的附加额 • 他在做定价决策时，做如下比较：
称这个线性规划问题为例1线性规划 问题(这里称原问题)的对偶问题。 min ω=8y1+16y2+12y3 y1+4y2 ≥2 +4y3≥3 2y1 yi≥0，i=1,2,3
(2-8)
这就是从另一角度提出的线性规划问题
进一步讨论它们之间的关系
•从第1节得到检验数的表达式是 CN-CBB-1N与-CBB-1 •当检验数 CN-CBB-1N≤0 -CBB-1≤0 (2-9) (2-10)
– 表示线性规划问题已得到最优解。 – 也作为得到最优解的判断条件。
现在讨论这两个条件。
(1) (2-9)式，(2-10)式中都有乘子 CBB-1 ，称它为单纯形乘子，用 符号Y= CBB-1表示。 •由(2-10)式，可得到Y≥0
(2) 对应基变量XB的检验数是0。 • 它是CB- CBB-1B=0。包括基变量在内的所 有检验数可用C- CBB-1A≤0表示。 • 从此可得C-CBB-1A=C-YA≤0 移项后，得到YA≥C
T
min ω = 8 y1 + 16 y2 + 12 y3
≥2 ⎧ y1 + 4 y2 ⎪ + 4 y3 ≥ 3 ⎨ 2 y1 ⎪ y,y ,y ≥o 1 2 3 ⎩
对偶规划问题
目标函数：
例1的各系数矩阵：
⎡ 1 2⎤ A = ⎢4 0⎥ ⎥ ⎢ ⎢0 4⎥ ⎣ ⎦ c = ( 2, 3) ⎡8⎤ ⎢16⎥ b= ⎢ ⎥ ⎢12⎥ ⎣ ⎦
min ω = Y (8,16,12) 约束条件： ⎧ ⎛ 1 2⎞ ⎟ ⎪ ⎜ Y ⎜ 4 0 ⎟ ≥ (2, 3) ⎪ ⎪ ⎜ 0 4⎟ ⎪ ⎝ ⎠ ⎨ ⎪ ⎪Y ≥ 0 ⎪ ⎪Y = ( 若用1个单位设备台时和4个单位原材料A 可以生产一件产品Ⅰ，可获利2元，那么 生产每件产品Ⅰ的设备台时和原材料出 租或出让的所有收入应不低于生产一件 产品Ⅰ的利润，这就有 y1+4y2≥2 • 同理将生产每件产品Ⅱ的设备台时和原 材料出租或出让的所有收入应不低于生 产一件产品Ⅱ的利润，这就有 2y1+4y3≥3
(3) Y由(2-10)式，得到 -Y= - CBB-1 (2-11) • 将(2-11)式两边右乘b，得到 -Yb=- CBB-1b (2-12) Yb= CBB-1b=z • 因Y的上界为无限大，所以只存在最小值
(4) 从这里可以得到另一个线性规划问题 min ω=Yb YA≥C Y≥0 • 称它为原线性规划问题｛max z=CX｜ AX≤b，X≥0｝的对偶规划问题
目标函数
• 把工厂所有设备台时和资源都出租或出 让，其收入为
ω=8y1+16y2+12y3
• 从工厂的决策者来看当然ω愈大愈 好；但受到接受方的制约，从接受 者来看他的支付愈少愈好，所以工 厂的决策者只能在满足大于等于所 有产品的利润条件下，提出一个尽 可能低的出租或出让价格，才能实 现其原意，为此需解如下的线性规 划问题