- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
•极大化问题的每个约束对应于极小化问题 的一个变量，其每个变量对应于对偶问题 的一个约束。
max Z c1 x1 c2 x2 cn xn
对 偶 问 题 的 定 义
a11 x1 a12 x 2 a1n x n (, )b1 a 21 x1 a 22 x 2 a 2 n x n (, )b2 a x a x a x (, )b m2 2 mn n m m1 1 x j 0( 0, 或符号不限) j 1 ~ n
c3 x3 c3 x3 max z c1 x1 c2 x2
对偶变量 y1 y2′
y2″
y3′
非 对 偶 形 式 的 原对 偶 问 题
例2-4
b2 y2 b3 y3 min w b1 y1 b2 y2
令各约束对应的对偶变量分别为y1、y2′、y2″、 -y3′
（2.4a） （2.4b） （2.4c）
（2.4d）
先转换成对称形式，如下：
a11 x1 a12 x2 a13 x3 a13 x3 b1 a x a x a x a x b 2 21 1 22 2 23 3 23 3 s.t. a21 x1 a22 x2 a23 x3 a23 x3 b 2 a x a x a x a x b3 31 1 32 2 33 3 33 3 x1 0，x2 0，x3 0，x3 0
a11 y1 a21 y2 a21 y2 a31 y3 c1 a y a y a y a y c 2 12 1 22 2 22 2 32 3 s.t. a13 y1 a23 y2 a23 y2 a33 y3 c 3 a y a y a y a y c 3 23 2 33 3 13 1 23 2 y1 0，y2 0，y2 0，y3 0
该公司希望用最小代价把美佳公司的全部资源收买过来，即：
min z 15 y1 24 y2 y3
例2-1
综上所述，
问 题 的 导 出
（LP2）
min w 15 y1 24 y2 y3
6 y2 y3 2 s.t. 5 y1 2 y2 y3 1 y1 , y2 , y3 0
maxW 7 y1 11y2 14y3
4 y1 8 y 2 12 y 3 4 5 y 9 y 13y 2 1 2 3 3 6 y1 10 y 2 y1符号不限, y 2 0, y 3 0
非 对 偶 形 式 的 原对 偶 问 题
第二章 线性规划的对偶理论及 灵敏度分析
Operational Research ( OR )
线性 规划 的对 偶问 题与 灵敏 度分 析
线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 参数线性规划
对 偶 原 理
对偶问题概念： 任何一个线性规划问题都有一个伴 生的线性规划问题，称为其“对偶” 问题。 对偶问题是对原问题从另一角度进 行的描述，其最优解与原问题的最 优解有着密切的联系，在求得一个 线性规划最优解的同时也就得到对 偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对 偶问题的理论，是线性规划理论的 重要内容之一。
minW b1 y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym (, )c1 a12 y1 a22 y2 am 2 ym (, )c2 a y a y a y (, )c mn m n 1n 1 2 n 2 y j 0(符号不限, 或 0)i 1 ~ m
项目
基变量 XB XN
基变量 Xs
0
Xs
cj-zj
b
B
CB
N
CN
I
0
对 偶 问 题 的 基 本 性 质
进一步迭代,新的单纯形表如下：
项目 CB XB cj-zj B-1b
基变量
非基变量
XB
I 0
XNB-1N CN-CB来自-1NXsB-1 –CBB-1
• 对应初始单纯形表中的单位矩阵I，迭代后的单纯形 表中为B-1 •初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b •初始单纯形表中约束系数矩阵为 [A,I]=[B,N,I]， 迭代后的表中约束系数矩阵为 [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
单纯形法计算的矩阵描述
max z CX 0 Xs AX IXs b s.t. X 0, Xs 0
对称形式线性规划矩阵表达式加上松弛变量Xs后为：
其中松弛变量Xs=（xn+1,xn+2,...,xn+m）,I为m×m单位矩阵
选取I为初始基，对应基变量为 Xs。设迭代若干步后，基变量 为XB，XB在初始单纯形表中的 系数矩阵为B。A中去掉B的若 干列后剩下的列组成矩阵N。
一 般 线 性 规 划 问 题 的 对 偶 问 题
对偶问题对应表
对 偶 问 题 的 定 义
原问题（对偶问题） 对偶问题（原问题）
目标函数maxZ
约束条件： m个
第i个约束类型为“≤” 第i个约束类型为“≥” 第i个约束类型为“＝”
目标函数minZ
变量数： m个
第i个变量≥0 第i个变量≤0 第i个变量是自由变量
LP1和LP2两个线性规划问题，通常称LP1为原问题， LP2为前者的对偶问题。
max Z c1 x1 c2 x2 cn xn
对 偶 问 题 的 定 义
a11 a12 a 21 a 22 s.t. a am2 m1 x1 , x 2 ,, x n
yj ( j 1,..., m) yj 0 变量 yj 0 yj无约束
线性 规划 的对 偶问 题与 灵敏 度分 析
线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 参数线性规划
对 偶 问 题 的 基 本 性 质
minW 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 a y a y a y c mn m n 1n 1 2 n 2 y1 , y2 , , ym 符号不限
项目
原问题（对偶问题）
对偶问题（原问题）
A
b C 目标函数
约束系数矩阵
约束条件的右端项向量 目标函数中的价格系数向量 max z=∑CjXj
其约束系数矩阵的转置
目标函数中的价格系数向量 约束条件的右端项向量 min w= ∑ biyi
有n个（j=1，...,n） m aijyi cj i=1 m 约束条件 a ij y i c j i=1 m a ij y i c j i=1
例2-1
条件：出让代价应不低于用同等数量资源由自己组织生 产活动时获取的赢利。
问 题 的 导 出
y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工 序的出让代价。 y1,y2,y3的取值应满足：
6 y2 y3 2 5 y1 2 y2 y3 1
美佳公司用6h设备B和1h调试可 生产一件家电I,赢利2元 用5h设备A,2h设备B及1h调试可 生产一件家电Ⅱ，赢利1元
例2-5
对 偶 问 题 的 基 本 性 质
参看例2-1中的原问题和对偶问题，并分别加上松 弛变量和剩余变量，如下：
a1n x1 b1 a 2 n x 2 b2 x b a mn n m 0
minW b1 y1 b2 y2 bm ym
a11 a 21 a m1 y1 c1 a12 a 22 a m 2 y 2 c 2 s.t. y c a a a 2n mn m n 1n y1 , y 2 ,, y m 0
对 应 关 系 总 结
x j ( j 1,..., n) xj 0 变量 xj 0 x 无约束 j
有m个（j=1，...,m） n aijxi bj i=1 约束条件 n aijxi bj i=1 n aijxi bj i=1
令y2= y2′-y2″， y3=-y3′，原问题的对偶问题为
min w b1 y1 b2 y2 b3 y3
a11 y1 a21 y 2 a31 y 3 c1 a y1 a y 2 a y 3 c 2 12 22 32 s.t. a13 y1 a23 y 2 a33 y 3 c 3 y1 0，y 2无约束，y3 0
例2-4 写出下列问题的对偶问题
max z c1 x1 c2 x2 c3 x3 a11 x a12 x a13 x3 b1 a x a x a x b 2 21 1 22 2 23 3 s.t. a31 x1 a32 x2 a33 x3 b3 x1 0，x2 0，x3无约束
对 称 形 式 下 的 对 偶 问 题
例2－3
min Z 4 x1 2 x2 3x3
