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

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

  • 格式：ppt
  • 大小：1.46 MB
  • 文档页数：81

下载文档原格式

  / 81

合集下载

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

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

A
Ⅰ
2
Ⅱ
2
设备可用机时
12
数（工时）
B
C
产品利润／
（元／件）
4
0
2
0
5
3
16
15
2020/5/24
第2页/共83页
第 2页
第2章 线性规划的对偶理论与灵敏度分析
解：设Ⅰ、Ⅱ产品的生产数量分别为x1和x2，建立问题数学模型如下：
max z =2x1+3x2 2x1+2x2≤12 4x1 ≤16 5x2 ≤15 xj≥0，j=1，2
第2章 线性规划的对偶理论与灵敏度分析
运筹学基础及应用
第2章 线性规划的对偶理论与灵敏度分析
2020/5/24
第1页/共83页
第 1页
第2章 线性规划的对偶理论与灵敏度分析
§1 对偶问题的提出
运筹学基础及应用
例2.1常山机械厂生产Ⅰ和Ⅱ两种产品。生产中需使用A、B、C三种设备进行加工，加工 每件Ⅰ产品或Ⅱ产品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问： 充分利用设备机台时，工厂应生产Ⅰ和Ⅱ产品各多少件才能获得最大利润？试列出相应的 线性规划数学模型。
原始问题 max z=CX s.t. AX≥b
X ≥0
max
C
m
A
n
对偶问题 min w=bTY s.t. ATY≤CT
Y ≥0
min
bT
运筹学基础及应用
≥b
n
AT
≤ CT
m
2020/5/24
第7页/共83页
第 7页
第2章 线性规划的对偶理论与灵敏度分析
2 原问题与对偶问题
运筹学基础及应用

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

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

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

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

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 为初始可行基，松 弛变量作为初 始基变量旳。因为松弛变量作为基变

运筹(第二章对偶与灵敏度分析)(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

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

运筹学课件-第二章对偶理论与灵敏度分析
对偶问题与原问题
对偶问题的目标函数是原问题约束条 件中某个或某几个变量的函数，而对 偶问题的约束条件是原问题目标函数 中某个或某几个变量的函数。
对偶问题的性质
对偶弱对偶性质
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

运筹学02_对偶理论与敏感性分析


0 x3 1 0 0 0 1 0 0 0 1 -2 0 50
0 x4 0 1 0 0 0 1 0 0 0 1 0 0
0 x5 0 0 1 0 -1 -1 1 -100 -1 1 1 50
I
θi 300 400 250 50 75
０
B-1
cBB-1
最优解：x1 = 50, x2 = 250, x4 = 50 B=(P1, P4, P2) 对偶最优解：y1 = 50, y2 = 0, y3 = 50 B-1对应的检验数 σT = cBB-1。
系数变成约束 条件右侧值
变成目标函 数的系数
最小化问题的对偶问题： 最小化问题的对偶问题：
max w = − 25 y 1 + 2 y 2 + 3 y 3
反过来， 反过来，由下 往上也是一样 的。
− y1 − y 2 + y 3 ≤ 1 − y1 + 2 y 2 − y 3 ≤ − 1 − 2 y1 − y 2 + y 3 = − 1 y1 , y 2 ≥ 0
12
CB 0 0 0 z 0 0 100 z 50 0 100 z
XB x3 x4 x5 x3 x4 x2 x1 x4 x2
300 400 250 0 50 150 250
-25000
50 50 250
-27500
50 x1 1 2 0 50 (1) 2 0 50* 1 0 0 0
100 x2 1 1 (1) 100* 0 0 1 0 0 0 1 0
25
例： 已知线性规划 max z = x1 + x2 s.t. -x1 + x2 + x3 ≤ 2 -2x1 + x2 - x3 ≤ 1 x1, x2 x3 ≥ 0 试用对偶理论证明该线性规划无最优 解。

第2章：线性规划的对偶理论和灵敏度分析l

第二章 线性规划的对偶理论和 灵敏度分析
2.1 单纯性法的矩阵描述和改进的单纯性法*** 2.2 对偶问题的提出与线性规划的对偶理论** 2.3 影子价格与对偶单纯性法*** 2.4 灵敏度分析
2.1 单纯形法的矩阵描述
为了便于利用计算机求解大规模 的线性规划问题，所以需要讨论单纯 形法的矩阵描述。
y1 2 y 2
s .t
y1 3 y1
2
y2
2 y3 3 y3 5
对 偶 问
y1 y 2 y3 1
题
y 1 0 , y 2 0 , y 3 无 约 束
2.2.2 线性规划的对偶理论与基本性质*
对称性 弱对偶性 无界性 最优性 对偶定理（强对偶性） 互补松弛性 对偶关系在单纯形表中的关系
KK根1S据标K准 形 规 范 形 ,
输计基基入算 X利 BXBsBKBBs用:利XKs初1(B(用,(P0(hx始(Pj11xj(1,j)1,jP1,基h初(x,jP21xjx2,j2等 )j,1B2,初,0行,x,P,x等jj2变,mPjm,x)(jm,)行j换Pm非T)),j,1,T非变(X基,xB,PNX基j向K换msj2;N|)C,量向KTI(B;),sB矩C量,X,C0B阵PK矩NN|(,sj0ImNC;阵;b)|)CsNsB,;KN非BK;01KbB,);(基KC,sIo11|Nrb向0B，(B;h0K量b2110)1bB矩,，oK1br阵，=( hN|2B0)1K;B|0B1 K*=,
8
4x1
4 x2
x4 16 x5 12
x1, x2, x3, x4, x5 0
加入了松弛 变量x3,,x4, x5表示没有 被利用的资 源，所以没 有利润，故 相应的价值 系数均为零。

对偶问题与灵敏分析


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. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2x1+2x2 + 4x4 3 y2 x1，x2 ， x3 ， x4 0
解：该问题的对偶问题：
max z = 2y1 + 3y2
s.t. 2y1 + 2y2 12
y1 + 2y2 8
4 y1
16
4y2 12
y1，y2 0
2020/8/1
运筹学基础及应用
第 10页
第2章 线性规划的对偶理论与灵敏度分析
a21x1 + a22x2 + … + a2nxn ≤ b2
(1)
……
am1x1 + am2x2 + … + amnxn ≤ bm xj ≥ 0 （j = 1,2,…,n）
min w = b1 y1 + b2 y2 + … +bm ym
s.t. a11y1 + a21 y2 + … + am1ym ≥ c1
a12y1 + a22y2 + … + am2 ym ≥ c2
(2)
……
a1ny1 + a2ny2 + … + amnym ≥ cn yi≥ 0 （i = 1,2,…,m）
为其对偶问题，其中 yi ≥ 0 （i = 1,2,…,m）称为对偶变量， 并称（1）、（2）为一对对称型对偶问题
2020/8/1
bT
运筹学基础及应用
≥b
n
AT
≤ CT
m
2020/8/1
第 8页
第2章 线性规划的对偶理论与灵敏度分析
2 原问题与对偶问题
运筹学基础及应用
设原 LP 问题为
则称下列 LP 问题
max z = c1x1 + c2x2 + … + cnxn
s.t. a11x1 + a12x2 + … + a1nxn ≤ b1
例2.3 写出下列线性规划问题的对偶问题 max z = 10x1 + x2 + 2x3 s.t. X1 + x2 + 2x3 10 y1
4x1 +2x2 - x3 20 y2 x1，x2 ， x3 0
解：该问题的对偶问题： min w = 10 y1 + 20 y2
s.t. y1 + 4y2 10 y1 + 2y2 1
Ⅰ（x1）
Ⅱ （x2）
设备可用机时 数（工时）
A（y1） 2 2 12
B（y2） 4 0 16
C（y3） 0 5 15
产品利润／ （元／件）
2
3
2020/8/1
第 5页
第2章 线性规划的对偶理论与灵敏度分析
运筹学基础及应用
2
3
x1
x2
原问题
12
y1
2
2
≤
12
16
y2
4
0
≤
16
15
y3
0
5
≤
15
对偶问题
原关系
a1n
a2 n
... ...
amn
Min w
b1 b2 ... bm
Max Z = Min w
cn
2020/8/1
第 7页
第2章 线性规划的对偶理论与灵敏度分析
原始问题 max z=CX s.t. AX≥b
X ≥0
max
C
m
A
n
对偶问题 min w=bTY s.t. ATY≤CT
Y ≥0
min
2020/8/1
运筹学基础及应用
第 12页
第2章 线性规划的对偶理论与灵敏度分析
例2.5写出下列线性规划问题的对偶问题
min z = 7x1 ﹢4x2 ﹣ 3x3 s.t. ﹣4x1﹢2x2 ﹣ 6x3 ≦24
﹣3x1﹣6x2 ﹣4x3 ≧15 5x1 ﹢3x3 = 30
x1≦0，x2无约束 ， x3 0
运筹学方法及其应用
讲授：毕德春 辽东学院信息技术学院信息管理系
第2章 线性规划的对偶 线性规划的对偶理论与灵敏度分析
2020/8/1
第 2页
第2章 线性规划的对偶理论与灵敏度分析
§1 对偶问题的提出
运筹学基础及应用
例2.1常山机械厂生产Ⅰ和Ⅱ两种产品。生产中需使用A、B、C三种设备进行加工，加工 每件Ⅰ产品或Ⅱ产品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问： 充分利用设备机台时，工厂应生产Ⅰ和Ⅱ产品各多少件才能获得最大利润？试列出相应的 线性规划数学模型。
解：用（-1）乘以第二个约束方程两边 min w=x1+2x2 +3x3
s.t. 2x1+3x2 + 5x3 2 y1 -3x1- x2 - 7x3 -3 y2 x1，x2 ， x3 0
该问题的对偶问题： max z = 2 y1 - 3y2
s.t. 2y1- 3y2 1 3y1- y2 2 5y1- 7y2 3 y1，y2 0
A
Ⅰ
2
Ⅱ
2
设备可用机时
12
数（工时）
B
C
产品利润／
（元／件）
4
0
2
0
5
3
16
15
2020/8/1
第 3页
第2章 线性规划的对偶理论与灵敏度分析
解：设Ⅰ、Ⅱ产品的生产数量分别为x1和x2，建立问题数学模型如下：
max z =2x1+3x2 2x1+2x2≤12 4x1 ≤16 5x2 ≤15 xj≥0，j=1，2
运筹学基础及应用
现假设有另一家四海机器厂，为了扩大生产想租借常山机器厂拥有的设备资源，问常山 厂分别以每小时什么样的价格才愿意出租自己的设备呢？
2020/8/1
第 4页
第2章 线性规划的对偶理论与灵敏度分析
运筹学基础及应用
设A、B、C设备的机时单价分别为y1、y2、y3，新的线性规划数学模型为
min w=12y1+16y2+15y3 2y1+4y2 ≥2 2y1 +5y3≥3 yj≥0，j=1，2，3
2 y1 - y2 2 y1，y2 0
2020/8/1
运筹学基础及应用
第 11页
第2章 线性规划的对偶理论与灵敏度分析
例2.4 写出下列线性规划问题的对偶问题 min w = x1 + 2x2 + 3x3
s.t. 2x1+3x2 + 5x3 2 3x1+ x2 + 7x3 3 x1，x2 ， x3 0
第 9页
第2章 线性规划的对偶理论与灵敏度分析
例2.2写出下列线性规划问题的对偶问题
min w=12x1+8x2 +16x3+12x4
s.t. 2x1+ x2 +4x3
2
2x1+2x2 + 4x4 3
x1，x2 ， x3 ， x4 0
min w=12x1+8x2 +16x3+12x4 s.t. 2x1+ x2 +4x3 2 y1
2
3
2020/8/1
第 6页
第2章 线性规划的对偶理论与灵敏度分析
原问题与对偶问题的形式关系
运筹学基础及应用
xj yi
u1 u2 ... um
对偶关系
Max Z
X1 , X2 , … , Xn
a11 a12 ... a21 a22 ... ... ... ... am1 am2 ...
…
c1 c2 ...