《运筹学》线性规划的对偶问题

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

下载文档原格式

运筹学线性规划的对偶问题

一个也有最优解，且相应的目标函数值相等。
证明：设X（0）是原问题的最优解，对应的基矩阵为B, 非基变量的检验数为CN- CBB-1N≤0
全体检验数 C- CBB-1A≤0，即C≤CBB-1A 令Y（0）= CBB-1，则有Y（0）A≥C
即Y（0）是对偶问题的可行解。由于z=C X（0）= CBXB（0）= CBB-1b= Y（0）b（目标值相等）由最优性定理可知Y（0）为对偶问题的最优解。
对偶问题:Y在b和A的左边（左右对换）
对偶问题的基本性质和基本定理 1. 对称性定理：对偶问题的对偶是原问题证明：
设原问题为
max Z = CX
AX b
s.t.
X
0
max() = Y (b)
Y (A) C s.t.Y 0 max Z = CX
AX b s.t.X 0

A
A

C
y '' 0
min = ( y ' y '' )b
s.t
.
(y' y',
y ''
y ''
)A 0

C
min = Yb YA C
s.t.Y 自由
原问题（或对偶问题）目标函数 max z
n个
变量
0 0
无约束
Y（0）AX（0）≤Y（0）b, 及Y（0）A≥C
故
C X（0）≤Y（0）A X（0）≤Y（0）b
亦即 C X（0）≤Y（0）b
证毕
3. 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
由弱对偶定理可证得

运筹学04-线性规划的对偶问题

生产计划问题
总结词
生产计划问题是线性规划对偶问题的另一个重要应用，主要研究如何安排生产计划，以满足市场需求并实现利润最大化。
详细描述
在生产过程中，企业需要合理安排生产计划，以最小化生产成本并最大化利润。通过线性规划对偶问题，可以确定最优的生产计划，使得生产过程中的资源得到充分利用，同时满足市场需求。
对偶理论的发展趋势与未来研究方向
1 2 3
混合整数对偶
随着混合整数规划问题的日益增多，对偶理论在处理这类问题中的研究将更加深入。
大数据优化
随着大数据技术的不断发展，如何利用对偶理论进行大规模优化问题的求解将成为一个重要研究方向。
人工智能与优化
人工智能和机器学习方法为优化问题提供了新的思路，与对偶理论的结合将有助于开发更高效的算法。
THANKS
感谢观看
线性规划问题的数学模型
目标函数
通常是一个线性函数，表示要优化的目标。
约束条件
通常是一组线性等式或不等式，表示决策变量所受到的限制。
可行解集合
满足所有约束条件的解的集合，称为可行解集合。
02
对偶问题概念
对偶问题的定义
线性规划的对偶问题是通过将原问题的约束条件和目标函数进行转换，形成与原问题等价的新问题。
对偶理论与实际问题的结合
01
02
03
供应链管理
在供应链优化问题中，对偶理论可以用于协调供应商和零售商之间的利益，实现整体最优。
金融风险管理
在金融领域，对偶理论可以用于评估和管理投资组合的风险，提高投资效益。
交通调度
在交通调度问题中，对偶理论可以用于优化车辆路径和调度计划，提高运输效率。

运筹学对偶问题的直观描述

运筹学对偶问题的直观描述
运筹学中的对偶问题是指原始线性规划问题和对应的对偶线性规划问题之间的关系。

直观描述对偶问题可以从几个方面来理解。

首先，可以从成本和效益的角度来理解。

原始线性规划问题通常涉及最小化成本或者最大化利润，而对偶线性规划问题则涉及最大化成本或者最小化利润。

这种对偶关系可以被解释为在资源有限的情况下，通过最小化成本来实现最大化效益，或者通过最大化效益来实现最小化成本。

其次，可以从约束条件的角度来理解。

原始线性规划问题的约束条件对应着对偶线性规划问题的变量，而对偶线性规划问题的约束条件对应着原始线性规划问题的变量。

这种对偶关系可以被理解为在资源分配和利用的过程中，对约束条件和变量之间的转换和对应关系。

另外，可以从几何图形的角度来理解。

原始线性规划问题的最优解和对偶线性规划问题的最优解之间存在着一种对偶关系，即原始问题的最优解和对偶问题的最优解分别对应着凸集的两个相对的极值点，它们之间的距离可以被理解为对偶问题的最优值和原始问
题的最优值之间的关系。

总的来说，对偶问题在运筹学中具有重要的意义，它不仅可以帮助我们理解原始问题和对偶问题之间的关系，还可以为我们寻找最优解提供了一种新的视角和方法。

通过对偶问题的研究和理解，我们可以更好地解决实际生产和管理中的复杂问题。

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

目
标函数求极小时取“≥”号
注：对称形式与线性规划标准型是两种不同的形式，对称形式中约束条件的符号由目标函数决定
从以下方面比较(LP1)与(LP2)：
原问题
对偶问题约束系数矩阵的转臵目标函数中的价格系数向量约束条件的右端项向量 Min w=Y’b A’Y≥C’ Y≥0
A
b C 目标函数约束条件决策变量
非基变量基变量
XB
0 b Xs C j - zj B
XN
N
Xs
I
0
初始单纯形表
非基变量
CB
CN
基变量
最终
单纯形表
CB
XB
XB B-1b Cj - zj
I 0
Xs B-1 N B-1 CN-CBB-1N -CBB-1
XN
若B-1b为最优解，则
CB CB ( B 1B) 0 C N CB B N 0 CB B 1 0
令 y 2 y 2 , y3 y3 y3 ，则
min 2 y1 y2 4 y3
2 y1 3 y2 y3 1 3 y y y 4 1 2 3 s.t. 5 y1 6 y2 y3 3 y1 0, y2 0, y3无约束
n j 1 m j j
C X Y b, 即 c j x j y i bi
j 1 i 1
__
__
n
m
c x ( a
j 1 m i 1 n i i i 1 i 1 j 1
n
m
ij
yi ) x j aij x j yi ( a ji yi c j )
例1

运筹学第3章对偶问题

y1 + 2 y2 + 4 y3 = 3 2 y1 + y2 + 3 y3 = 2
x1 > 0, x2 > 0
联立求解得： y1 = 0, y2 = 0.5, y3 = 0.5
三、影子价格
设 x* ( j = 1,L, n) 和 yi* (i = 1,L, n) 分别是原问题和 j 对偶问题的最优解，则由对偶性质，有
=b
BX B + NX N + IX S = b X ≥ 0, X ≥ 0 N B
S S
max z = C B X B + C N X N + 0 X s
将XB的系数矩阵化为单位矩阵
原来 BX B + NX N + IX IX B + B − 1 NX N + B − 1 X
= b = B
注上表中我们将松弛变量与剩余变量统称为松弛变量
二、对偶问题的基本性质
1、对偶问题的对偶问题是原问题
max z=CX s.t. AX≤b X ≥0 对偶的定义 min w=b’Y s.t. A’Y≥C Y ≥0
min z’ = - CX s.t. -AX ≥-b X ≥0
对偶的定义
max w = -b’Y s.t. -A’Y≤-C Y ≥0
−1
b
项目
原问题变量
原问题松弛变量
原问题最终单纯形表
x1
x3 15/2 x1 7/2 x2 3/2 -σj 0 1 0 0
x2
0 0 1 0
x3
1 0 0 0
x4
5/4 1/4 -1/4 1/4
x5
15/2 -1/2 3/2 1/2

运筹学：第1章线性规划第3节对偶问题与灵敏度分析

s.t.
4x1 3x1
5x2 200 10x2 300
x1, x2 0
9x1 4x2 360
s.t.
34xx11
5x2 10 x
200 2 300
3x1 10x2 300
x1, x2 0
则D为
min z 360y1 200y2 300y3 300y4
9 y1 4 y2 3y3 3y4 7 s.t.4 y1 5y2 10 y3 10 y4 12
amn xn bm ym xn 0
机会成本 a1 j y1 a2 j y2 aij yi amj ym
表示减少一件产品所节省的可以增加的利润
（3）对偶松弛变量的经济解释——产品的差额成本
机会成本
利润
min w b1 y1 b2 y2 bm ym
a11 y1
st
a12
y1
a1n y1
max z CX
（P）
AX b
s
.t
.
X
0
（D）
min w Yb
s.t.
YA C Y 0
• （2）然后按照（D）、（P）式写出其对偶
例：写出下面线性规划的对偶规划模型：
max z 2x1 3x2
min w 3 y1 5y2 1y3
x1 2x2 3 y1 0
s.t.
2xx11
例如，在前面的练习中已知
max z 2.5x1 x2 的终表为
3x1 5x2 15 s.t.5x1 2x2 10
x1, x2 0
0 x3 9 2.5 x1 2
0 19 1 - 3
5
5
1
2
0
1
5

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

(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个约束条

运筹学对偶问题

在运筹学中，对偶问题是一个与原问题相对应的问题。

以线性规划问题为例，每一个线性规划问题必然有与之相伴而生的另一个线性规划问题，即任何一个求maxz的LP1都有一个求minw的LP2。

将LP1称为“原问题”，记为P；将LP2称为“对偶问题”，记为D。

对偶问题的经济学解释——影子价格又称影子利率，用线性规则方法计算出来的反映资源最优使用效果的价格。

用微积分描述资源的影子价格，即当资源增加一个数量而得到目标函数新的最大值时，目标函数最大值的增量与资源的增量的比值，就是目标函数对约束条件（即资源）的一阶偏导数。

用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为对资源的经济评价，表现为影子价格。

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

运筹学对偶理论

min w 5 y1 9 y2 4 y3
y1 3y2 2 y3 2
s.t.2
y1 3 y1
y
2 2y
2y 2
3 1 4 y3
3
y1
y1
y2 0,
y2
y3
0,
5
y
无约束
3
LP1: max z=3x1+2x2
xx11++22xx2 2≤+5x3
=5
st.
2x1+ x2 ≤4 +x4 = 4
0
0
1
3
x1
1
0
0
2
x2
0
1
0
0
0
0
0
0
x4
x5
b
0
05
1
04
0
19
0
00
-1/2
0
3
1/2
02
-2
11
-3/2
0
6
5/2 -3/2 3/2
3/2 -1/2 3/2
-2
11
-1/2 -1/2 13/2
单纯形算法的矩阵表示
LP: max z = CX st. AX ≤ b
X≥0
max z = CX + 0XS st. AX +I XS = b ( I式 )
3.2.4 强对偶性定理（对偶定理）
如果原问题存在最优解X*，则其对偶问题一定具有最优解Y*，且 CX * b'Y *
• 如果原问题存在最优解，假设其对应的基是B，即
X
* B
B 1b,
X
* N
0

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

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案一、填空题1. 在线性规划问题中，若原问题存在最优解，则其对偶问题也一定存在最优解，这是线性规划的基本性质之一，称为______。

答案：对偶性2. 在线性规划问题中，若原问题与对偶问题均存在可行解，则它们均有______。

答案：最优解3. 对于线性规划问题，若原问题约束条件系数矩阵为A，目标函数系数向量为c，则其对偶问题的目标函数系数向量是______。

答案：c的转置（c^T）二、选择题1. 线性规划的原问题与对偶问题之间的关系是：A. 原问题的最优解和对偶问题的最优解相同B. 原问题的最优解是对偶问题的最优解的负数C. 原问题的最优解与对偶问题的最优解互为对偶D. 原问题的最优解和对偶问题的最优解没有关系答案：C2. 在线性规划中，若原问题不可行，则其对应的对偶问题：A. 可行B. 不可行C. 无界D. 无法确定答案：B三、判断题1. 线性规划的原问题和对偶问题具有相同的可行解。

（）答案：错误2. 若线性规划的原问题存在唯一最优解，则其对偶问题也一定存在唯一最优解。

（）答案：正确四、计算题1. 已知线性规划问题：max z = 3x1 + 2x2s.t.x1 + 2x2 ≤ 42x1 + x2 ≤ 5x1, x2 ≥ 0求该问题的对偶问题，并求解原问题和对偶问题的最优解。

答案：对偶问题为：min w = 4y1 + 5y2s.t.y1 + 2y2 ≥ 32y1 + y2 ≥ 2y1, y2 ≥ 0原问题和对偶问题的最优解如下：原问题最优解：x1 = 2, x2 = 1，最大利润z = 8对偶问题最优解：y1 = 2, y2 = 1，最小成本w = 82. 某工厂生产甲、乙两种产品，生产一件甲产品需要2小时的机器时间和3小时的工人劳动时间，生产一件乙产品需要1小时的机器时间和1小时的工人劳动时间。

工厂每周最多能使用12小时的机器时间和9小时的工人劳动时间。

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

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

《运筹学》对偶理论

s.t
6
x1 2x2 x1 x2
x4 x5
2 5
4
xj 0
s.t
5
6 y2 y3 y1 2 y2
y
y4 3
2 y5
1
yi 0
分别用单纯形法求解上述2个规划问题，得到最终单纯形表如
下表:
对偶性质
原问题最优表
XB
b
x3
15/2
x1
7/2
x2
3/2
j
原问题的变量
x1
x2
0
max z c1x1 c2 x2
s.t.
11x1 12x2 21x1 22x2
b1 b2
x1
0,
x
无约束
2
min w b1 y1 b2 y2
s.t.1121yy11
21y2 22 y2
c1 c2
y1, y2 0
min w b1 y1 b2 y2
s.t.1121yy11
4
y1 , y2 , y3 0
线性规划的对偶模型
(2) 非对称型对偶问题若给出的线性规划不是对称形式, 可以先化成对称形式
再写对偶问题。也可直接写出非对称形式的对偶问题。
线性规划的对偶模型
原问题（或对偶问题）
约束条件右端项
目标函数变量的系数
目标函数 max
约
m个
束
≤
条
件
≥
=
n个
变
≥0
量
≤0
s.t.2111xx11
12 22
x2 x2
b1 b2
x1 0, x2 0
min w b1 y1 b2 y2

运筹学-对偶问题

对偶问题的应用场景
资源分配问题
在资源有限的情况下，如何合理分配资源以达到最优目标。
运输问题
如何制定运输计划，使得运输成本最低且满足运输需求。
生产计划问题
如何制定生产计划，使得生产成本最低且满足市场需求。
投资组合优化问题
如何选择投资组合，使得投资收益最大且风险最小。
02
对偶问题在运筹学中的重要性
对偶问题的理论完善与深化
对偶理论的数学基础
进一步深入研究对偶理论的数学基础，包括对偶映射、对偶函数、对偶不等式等，为解决对偶问题提供更坚实的理论基础。
对偶问题的转化与求解
研究如何将复杂的对偶问题转化为更容易求解的形式，或者设计有效的求解方法，以提高对偶问题的求解效率。
对偶理论与实际应用的结合
在对偶理论不断完善的基础上，进一步探索如何将其应用于实际问题中，以解决实际问题的优化问题，提高决策的科学性和效率。
在整数规划中，对偶问题通常是指将原问题的约束条件或目标函数进行一些变换，使得原问题与对偶问题在结构上存在一定的对称性。
对偶问题的性质
02
01
03
对偶问题的最优解与原问题的最优解具有密切关系。
在线性规划中，如果原问题是最大化问题，则对偶问题是最小化问题，反之亦然。
在整数规划中，对偶问题的约束条件和目标函数通常与原问题存在一定的对称性。
02 求解步骤
03 1. 定义原问题和对偶问题。
04
2. 利用状态转移方程和最优子结构性质，求解对偶问题。
05 3. 利用对偶问题的解，求解原问题。
博弈论中的对偶策略
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）计算结果。

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

第2章线性规划的对偶理论与灵敏度分析
§2.1 线性规划的对偶问题
随着线性规划应用的逐步加深，人们发现每一个线性规划问题都存在一个与之对应的、具有密切关联的线性规划问题，其中一个称为原问题，另一个称为对偶问题（Dual linear programming，DLP）。对偶问题不仅具有优良的数理性质，而且还有着重要的实际意义，尤其在生产运营管理中有明显的经济含义。对偶理论充分显示出线性规划理论逻辑上的严谨性和结构上的对称性，使线性规划理论更加丰富，应用领域更为广泛。
yi 0 (i 1,2,3)
则得如下的线性规划模型：
min w 48 y1 20 y2 8 y3 8 y1 4 y2 2 y3 600 6 y 2 y2 1.5 y3 300 s.t. 1 y1 1.5 y2 0.5 y3 200 y , y , y 0 1 2 3
max z 2 y1 5 y2 9 y3 y1 3 y2 2 y3 3 2 y y 2 y 1 1 2 3 5 y1 y2 3 y3 1 y1无约束,y2 0, y3 0,
max z 600 x1 300 x2 200 x3 8 x1 6 x2 x3 48 4 x1 2 x2 1.5 x3 20 s.t 2 x1 1.5 x2 0.5 x3 8 x , x , x 0 1 2 3
x1 2, x2 0, x3 8
（2.1.6）
设 yi (i 1,2,, m) 表示第i种资源的定价，则其对偶问题的形式为：
min w b1 y1 b2 y2 ... bm ym a11 y1 a21 y2 ... am1 ym c1 a y a y ... a y c 12 1 22 2 m2 m 2 s.t. a y a y ... a y c mn m n 1n 1 2 n 2 y1 , y2 , , ym 0

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3、资源影子价格的性质
z y b1w1 b2w2 bi wi bmwm z z b1w1 b2w2 (bi bi )wi bmwm z bi wi
w
o i
z o bi
最大利润的增量第i种资源的增量
第i种资源的边际利润
■影子价格越大，说明这种资源越是相对紧缺 ■影子价格越小，说明这种资源相对不紧缺 ■如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0
总利润（元）
单位产品的利润（元/件）
产品产量（件）
max z c1x1 c2 x 2 c2 x 2
s.t.
a11x1 a12x 2 a1n x n x n1
a 21x1 a 22x 2 a 2n x n
x n2
b1
b2
a m1x1 a m2 x 2 a mn x n
差额成本=机会成本 ——利润
5、互补松弛关系的经济解释
wix ni
0xwni
0 x ni i 0 wi
0 0
x jwmj
0xwjm j
0 0
w m x
j j
0 0
在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产
4、产品的机会成本
增加单位资源可以增加的利润
max z c1x1 c2x2 c jx j cn xn
s.t.
a11x1 a12x 2 a1jx j a1nx n b1 w1
a 21x1 a 22x 2 a 2jx j a 2nx n b2 w2
a m1 x1 a m2 x 2 a mj x j a mn x n bm wm
X
x1 x2
b1
b
b2 b3
特点：
1． max min 2．限定向量b 价值向量C
其它形式的对偶
?
（资源向量）
3．一个约束一个变量。
4． max z的LP约束“ ” min z 的
LP是“ ”的约束。
5．变量都是非负限制。
其他形式问题的对偶
min z=CTX s.t. AX≥b
线性规划的对偶问题
一、对偶问题的提出
二、原问题与对偶问题的数学模型
继续
三、对偶的经济解释
返回
一、对偶问题的提出
某工厂要生产两种新产品：门和窗。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？
车间
单位产品的生产时间（小时）
门
窗
1
1
0
2
0
2
3
3
2
单位利润（元） 300
500
每周可获得的生产时间（小
min w 4 y1 12y2 18y3 1y1 0 y2 3y3 300 0 y1 2 y2 2 y3 500
原问题是求极小值，非规范形式的对应关系是： ①约束条件是“≤”符号对偶变量y≤0 ②约束条件是“＝”符号对偶变量y无约束 ③变量x≤0 对偶约束是“≥”符号 ④变量x无约束对偶约束是“＝”符号
x1 x2 x3 x3 x4 10
s.t.
6x1 3x2 7x3 7x3 15 10 x1 12 x2 x3 x3 x5 19
10 x1 12 x2 x3 x3 x6 19
x1, x2 , x3 , x3, x4, x5, x6 0
max g( y) 10 y1 15 y2 19 y3 19 y4
x1
x2
xj
xn 0
减少一件产品可以节省的资源
机会成本 a1jw1 a 2 jw 2 a ijwi a mj w m
表示减少一件产品所节省的资源可以增加的利润
5、产品的差额成本（Reduced Cost）
机会成本
差额成本
利润
min y b1w1 b2 w 2 bm w m
线性规划的对偶问题
返回
第 3、4 题
原问题：
标准型：
min f ( x) 5x1 3x2 2x3
x1 x2 x3 10
s.t.
6x1 3x2 7x3 15 |10 x1 12 x2 x3 | 19
x1 0, x2 0, x3 不限
对偶问题：
max[ f ( x)] 5x1 3x2 2x'3 2x3
a11w1 a 21w 2 a m1w m w m1
资源价格（元/吨）
a12w1 a 22w2 a m2 w m
wm2
c1
c2
a1n w1 a 2n w 2 a mn w m
w1
w2
wm
w m1
wmn cn wm2 wmn 0
对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、 wm称为m种资源的影子价格（Shadow Price）
s.t.
a11w1 a 21w 2 a m1w m w m1
a12w1 a 22w2 a m2 w m
wm2
c1
c2
a1n w1 a 2n w 2 a mn w m
w1
w2
wm
w m1
wmn cn wm2 wmn 0
wm j (w1a1j w2a 2 j wma mj ) c j WTa j c j
1y1 0 y2 3y3 300厂
0 y1 2 y2 2 y3 500家
原问题
对偶问题
max
s.t.
z CX AX b
ms.itn.
w Yb YA C
X 0
Y0
一般规律
3个约束 2个变
量C (c1, c2 )
2个约束 3个变量
Y (y1,y2,y3 )
A (aij )
时）
4 12 18
x 设门产量––––– 1
x 窗产量––––– 2
如何安排生产，使获利最多？
max z 300x1 500x2
s.t. 2x1
4
2x2 12
3x1 2x2 18
x1, x2 0
厂家
y 设：车间1 —— 元／1 时 y 车间2 –––– 元／时2 y 车间3 –––– 元／时3
非规范型模型的“非”无非有4个方面: ①约束条件是“≥”符号对偶变量y≤0 ②约束条件是“＝”符号对偶变量y无约束 ③变量x≤0 对偶约束是“≤”符号 ④变量x无约束对偶约束是“＝”符号
max z 300x1 500x2 s.t. 2x1 0x2 4 0x1 2x2 12 3x1 2x2 18 x1, x2 0
二、原问题与对偶问题的对应关系
原问题
目标函数 Max
约
m个
束
条
件
=
决
n个
策
0
变
0
量
无约束
资源系数 b 价值系数 C 约束条件系数矩阵 A
对偶问题
目标函数 Min
m个
决
0
策
0
变
无约束
量
n个
约
束
条
=
件
价值系数 bT
资源系数 CT 约束条件系数矩阵 AT
Байду номын сангаас
例:
max z 5x1 3x2 2x3 4x4 5x1 x2 x3 8x4 8
消耗的资源（吨） x1
x2
xn
x n1
xnm bm xn2 xnm 0
单位产品消耗的资源（吨/件）
剩余的资源（吨）资源限量（吨）
2、对偶问题
原始和对偶问题都取得最优解时，最大利润 max z=min y
总利润（元）
资源限量（吨）
min y b1w1 b2 w 2 bm w m
s.t.
s.t 2x1 4x2 3x3 2x4 10
x1,x2 0 x3,x4无约束
对偶问题为
min w 8y1 10y2
5 y1 2 y2 0
s.t.
y1 4 y2 3 y1 3y2 2
8 y1 2 y2 4
y1 0, y2无约束
三、对偶的经济解释
1、原始问题是利润最大化的生产计划问题
付出的代价最小，且对方能接受。
出让代价应不低于
用同等数量的资源
收
自己生产的利润。
购
厂家能接受的条件：
1y1
出用0同让y等代2数价量应3的不y3资低源于300
单位产品门出租收入不低于300元
0
y1
自己2生y2产的2利y润3 。
500
单位产品窗出租收入不低于500
收购方的意愿：
元
min w 4 y1 12 y2 18 y3
X ≥0
min z=CTX s.t. AX=b
X ≥0
min z=CTX
s.t. AX≤b
X ≥0
max y=bTW s.t. ATW≤C
W ≥0
max y=bTW s.t. ATW≤C
W ：unr
max y=bTW s.t. ATW≤C
W ≤0
关键口诀：对偶问题约束符号由原问题变量符号确定，对偶问题变量符号由原问题约束符号确定。
s.t.
y1 3y2 12 y3 12 y4 3 y1 7 y2 y3 y4 2
y1 0, y2 不限, y3 0, y4 0
s.t.
y1 6 y2 10 y3 10 y4 5 y1 3y2 12 y3 12 y4 3 y1 7 y2 y3 y4 2
y1 0, y2 不限, y3 0, y4 0
max g( y) 10 y1 15 y2 19 y3 19 y4
y1 6 y2 10 y3 10 y4 5

《运筹学》线性规划的对偶问题

合集下载