线性规划对偶理论含影子价格21136
- 格式：pptx
- 大小：430.14 KB
- 文档页数：48
下载文档原格式
合集下载
第一讲 对偶理论和影子价格
四川农业大学数学系王莉莉
14
线性规划问题的参数变化灵敏度分析
灵敏度分析中研究C、b等参数在保持最优解或最优 基不变时的允许变化范围或改变到某一值时对问题 最优解的影响，若C按( C+λC* )或b按( b+ λ b* )连 续变化，而目标函数Z(λ )是参数λ的线性函数时， 将下面的问题称为参数线性规划。
四川农业大学数学系王莉莉
9
对偶问题解的经济含义：
对偶问题解中变量 yi* 的经济含义是在其他条件 不变的情况下，单位第 i 种“资源”变化所引起 的目标函数最优值的变化。所以， yi* 描述了原 始线性规划问题达到最优时（各种“资源”都处 于最优的配置时），第 i 种“资源”的某种“价 值”，故称其为第 i 种“资源”的影子价格。
25
四川农业大学数学系王莉莉 16
并进一步讨论以下3个附加问题： 1） 若用35元可以买到1桶牛奶，应否作这项 投资？若投资，每天最多购买多少桶牛奶？ 2） 若可以聘用临时工人以增加劳动时间，付 给临时工人的工资最多是每小时几元？ 3） 由于市场需求变化，每公斤A1的获利增加 到30元，应否改变生产计划？
对偶理论与灵敏度分析
线性规划的对偶理论
对偶理论是线性规划中最重要的理论之一，是 深入了解线性规划问题结构的重要理论基础。同 时，由于问题提出本身所具有的经济意义，使得它 成为对线性规划问题系统进行经济分析和敏感性分 析的重要工具。那么，对偶问题是怎样提出的，为 什么会产生这样一种问题呢？
四川农业大学数学系王莉莉
四川农业大学数学系王莉莉
22
最优基不变条件 下目标函数系数 的允许变化范 围：x1的系数为 Ranges in which the basis is unchanged: （72-8， 72+24）= Objective Coefficient Ranges （64，96） Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Row 2 3 4 Righthand Side Ranges Current Allowable Allowable RHS Increase Decrease 50.00000 10.00000 6.666667 480.0000 53.33333 80.00000 100.0000 INFINITY 40.00000
第四章线性规划的对偶理论
定义4.4.1 正则解
设X(0)是原问题的一个基本解，对应的基是B.若它 对应的检验数σ=C-CBB-1A≤0成立。则原问题的一 个正则解。对应的基矩阵B称为正则基。
注意：正则解是基本解，不要求是可行解
对偶单纯形法的算法步骤
给定初始正则解 计算b=B-1b。b≥0
确定离基变量
Yes 得到最优解
解
x1 每日生产木门数 x2 每日生产木窗数 max Z 56x1 30x2 s.t. 4x1 3x2 120
2x1 x2 50 x1, x2 0
另一个解题思路
1 木工每个工时的工资 2 油漆工每个工时的工资 min f 1201 502 s.t. 41 22 56
1
x
(0) j
0, W (0) p j
cj
2
W
(0)
pj
cj
x
(0) j
0
例子
max z x1 2x2
s.t. 3x1 x2 2
x1 2x2 3
x1 3x2 1
x1, x2 0
x*
1
,
11T
7 7
4.3 对偶解(影子价格)的经济解释
4.4 对偶单纯型法
问题的提出 原始单纯形法的解题思路 对偶单纯形法的解题思路
31 2 30 1,2 0
4.1.2 三种形式的对偶问题
1、对称形式的对偶问题
LP max Z CX s.t. AX b
X 0n1
DP min f Wb s.t. WA C
W 01m
例子
LP max Z 2x1 2x2 s.t. 2x1 4x2 1
x1 2x2 1 2x1 x2 1 x1, x2 0
运筹学课件 第2章：线性规划的对偶理论
min w 16y1 36y2 65y3
90 y1 3 y 2 y1 2 y 2 5 y 3 70 y , y , y 0 1 2 3
原问题 A b C 约束系数矩阵
对偶问题 约束系数矩阵的转臵
约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量 约束条件的右端项向量 Max z=CX Min w=Y’b 目标函数 AX≤b A’Y≥C’ 约束条件 X≥0 Y≥0 决策变量
若原问题为求极小形式的对称形式线性规划问题， 对偶问题应该具有什么形式？
Min w Y 'b A'Y C Y 0
max w Y 'b A'Y C Y 0
min z CX
Max z CX
AX b X 0
AX b X 0
min w 5 y1 4 y2 6 y3 4 y1 3 y2 2 y3 2 y1 2 y2 3 y3 3 3 y1 4 y3 5 2 y 7 y y 1 2 3 1 y1 0, y2 0, y3无约束
对偶问题 约束系数矩阵的转臵
目标函数中的价格系数向量
目标函数 约束条件
变量
Max z=CX m个 ≤ ≥ = n个 ≥0 ≤0 无约束
约束条件的右端项向量 目标函数 Min w=Y’b m个 ≥0 变量 ≤0 无约束 n个 ≥ 约束条件 ≤ =
【例2-3】写出下列线性规划问题的对偶问题
min 2x1 3x2 5x3 x4
1.初始表中单位阵在迭代后单纯形表中对应的位臵就是B-1 2.对于原问题的最优解，各松弛变量检验数的相反数恰好 是其对偶问题的一个可行解，且两者具有相同的目标函数 值。根据下面介绍的对偶问题的基本性质还将看到，若原 问题取得最优解，则对偶问题的解也为最优解。
线性规划问题的影子价格研究解析
目录1 引言....................................................................................................... 错误!未定义书签。
2 文献综述............................................................................................... 错误!未定义书签。
2.1 国内外研究现实状况.......................................................................... 错误!未定义书签。
2.2 国内外研究现实状况评价.................................................................. 错误!未定义书签。
2.3 提出问题.............................................................................................. 错误!未定义书签。
3 技术系数与约束右端项不发生变化................................................... 错误!未定义书签。
3.1线性规划原问题与对偶问题及其性质............................................... 错误!未定义书签。
3.2详细应用............................................................................................... 错误!未定义书签。
3.3 影子价格确实定.................................................................................. 错误!未定义书签。
2.2 对偶理论 2.3对偶问题的经济意义——影子价格
影子价格是经济学中的重要概念，将一个企业拥 有的资源的影子价格与市场价格比较，可以决定是购 入还是出让该种资源。当某资源的市场价格低于影子 价格时，企业应该买进该资源用于扩大生产；而当市 场价格高于影子价格时，则企业的决策者应该将已有 资源买掉。这样获利会更多。在考虑一个地区或一个 国家某种资源的进出口决策中，资源的影子价格是影 响决策的一个重要因素。 利用单纯形表求解线性规划，在求得最优解的同 时，很容易得到问题的各种资源的影子价格。某资源 的影子价格，就是该资源对应的约束条件所加松弛变 量在最优表中的检验数的相反数。
例1 写出下面线性规划的对偶规划 minZ=2x1+ x2-4x3 原问题即 2x1+3x2 +x3 ≥1 minZ=2x1+ x2-4x3 3x1- x2 +x3 ≤4 2x1+3x2 +x3 ≥1 x1 +x3=3 -3x1+ x2-x3 ≥-4 x1,x2≥0 x1 +x3=3 其对偶为：maxW=y1 -4y2+3y3 x1,x2≥0 2y1- 3y2 +y3 ≤2 3y1+ y2 ≤1 y1- y2 +y3 =-4 y1,y2≥0
线性规划的原问题与对偶问题的变换规则表：
原问题（或对偶问题） 目标函数 maxZ 价值系数 资源系数 行约束的个数为m 行约束的个数为m 第i个行约束取“≤” 个行约束取“≤ 第ι个行约束取“＝” 原变量的个数为n 原变量的个数为n 第j个变量xj ≥0 个变量x 第k个变量xk无限制 个变量x 对偶问题（或原问题） 目标函数 minW 资源系数 价值系数 对偶变量的个数为m 对偶变量的个数为m 第i个变量yi ≥0 个变量y 第ι个变量yι无限制 个变量y 行约束的个数为n 行约束的个数为n 第j个行约束取“≥” 个行约束取“≥ 第k个行约束取“＝”
运筹学课件第三节影子价格
运筹学教程
第三节 影子价格
对偶问题解的经济解释——影子价格
我们已经明白原始线性规划与对偶线性规 划之间形式上的对偶以及他们解之间的关系， 那么对偶问题的解除了前面引例中提到的租金 这种经济含义外其深刻的经济含义是什么呢？
运筹学教程
线性规划的对偶理论
对偶问题解的经济含义分析：
从单纯形法的矩阵描述中，目标函数取值 Z = CBB-1 b ， 和检验数CN -CBB-1N 中都有乘子 Y = CBB-1。
注意：在初始单纯形表其对偶问题应该是基 可行解，对多数线性规划问题难实现。
主要应用：灵敏度分析。
运筹学教程
练习:使用对偶单纯形法求解
min Z 4 x1 x2 3x3 x1 x2 x3 5 st. x1 x2 4 x3 3 x ,x ,x 0 1 2 3
当产品产值大于隐含成本时，表明生产该产品有利。 当产品产值小于隐含成本时，表明用资源生产别的产品有利。
运筹学教程
第四节 对偶单纯形法
一、对偶单纯形法的基本思路 对偶单纯形法是应用对偶原理求解线性 规划的一种方法 ——在原问题的单纯形表 上进行对偶处理。
注意：不是解对偶问题的单纯形法！
运筹学教程
1、 单纯形法求解 初始可行基（对应一个初始基可行解） →迭代→另一个可行基（对应另一个基可行 解），直至所有检验数≤0为止。
j 1
n
若 aij x j bi, 有yi 0
j 1
n
运筹学教程
特点5、从影子价格考察单纯形表的计算。
j c j CB B 1Pj c j aij yi
i 1
m
Cj代表第j种产品的产值，
第三节 影子价格
对偶问题解的经济解释——影子价格
我们已经明白原始线性规划与对偶线性规 划之间形式上的对偶以及他们解之间的关系， 那么对偶问题的解除了前面引例中提到的租金 这种经济含义外其深刻的经济含义是什么呢？
运筹学教程
线性规划的对偶理论
对偶问题解的经济含义分析：
从单纯形法的矩阵描述中，目标函数取值 Z = CBB-1 b ， 和检验数CN -CBB-1N 中都有乘子 Y = CBB-1。
注意：在初始单纯形表其对偶问题应该是基 可行解，对多数线性规划问题难实现。
主要应用：灵敏度分析。
运筹学教程
练习:使用对偶单纯形法求解
min Z 4 x1 x2 3x3 x1 x2 x3 5 st. x1 x2 4 x3 3 x ,x ,x 0 1 2 3
当产品产值大于隐含成本时，表明生产该产品有利。 当产品产值小于隐含成本时，表明用资源生产别的产品有利。
运筹学教程
第四节 对偶单纯形法
一、对偶单纯形法的基本思路 对偶单纯形法是应用对偶原理求解线性 规划的一种方法 ——在原问题的单纯形表 上进行对偶处理。
注意：不是解对偶问题的单纯形法！
运筹学教程
1、 单纯形法求解 初始可行基（对应一个初始基可行解） →迭代→另一个可行基（对应另一个基可行 解），直至所有检验数≤0为止。
j 1
n
若 aij x j bi, 有yi 0
j 1
n
运筹学教程
特点5、从影子价格考察单纯形表的计算。
j c j CB B 1Pj c j aij yi
i 1
m
Cj代表第j种产品的产值，
对偶理论与影子价格
9
管
理
运
筹
学
一对对称形式的对偶规划之间具有下面的对应关系： 1.若一个模型为目标求“极大”，约束为“小于等于”的 不等式，则它的对偶模型为目标求“极小”，约束是“大于等 于”的不等式。即“max，≤”和“min，≥”相对应。 2.从约束系数矩阵看：一个模型中为Ａ，则另一个模型中 为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个 约束，m个变量 3.从数据b、C的位置看：在两个规划模型中，b和C的位置 对换 4.两个规划模型中的变量皆非负
21
管
理
运
筹
学
弱对偶定理的推论： 1.（P）任一可行解的目标函数值是其对偶问题目 标函数值的下界；（D）任一可行解的目标函数值是 其原问题目标函数值的上界。 2. 若（P）可行，那么（P）无有限最优解的充分 必要条件是（D）无可行解。 3. 若（D）可行，那么（D）无有限最优解的充分 必要条件是（P）无可行解。 4. 若（P）、（D）可行，那么（P）、（D）都有 最优解。
第六节 对偶理论与影子价格
对偶问题的提出 对偶问题的形式 对偶问题的基本性质 影子价格
1
管
理
运
筹
学
对偶问题的提出
2
管
理
运
筹
学
例1：某工厂拥有A、B、C三种类型 的设备，生产甲、乙两种产品。每 件产品在生产中需要占用的设备机 时数，每件产品可以获得的利润以 及三种设备可利用的时数如下表所 示：问题：工厂应如何安排生产可 获得最大的总利润？
设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收费。 设x1，x2分别为生产甲乙两种产品的件数 目标函数 min f 65 y1 40 y2 75 y3 max z 1500 x1 2500 x2 目标函数 3 y1 2 y2 1500 3 x1 2 x2 65 （不少于甲产品的利润） 2 x x 40 约束条件 1 2 约束条件 2 y1 y2 3 y3 2500 3 x2 75 （不少于乙产品的利润） x 0, x 0 1 2 y1 0, y2 0, y3 0
线性规划中影子价格的定义及计算
线性规划中影子价格的定义及计算
影子价格是指在线性规划中，用来确定最优解的一种数学模型。
简单来说，影子价格就是一组参数，用来表示特定限制被侵蚀的代价。
在线性规划中，影子价格用来度量对于受限制约束而导致可行解发生
变化的成本。
影子价格的计算方法是通过求解线性规划问题的两个不同最优解
的分歧来实现的。
在线性规划中，第一个最优解的定义是在考虑所有
约束条件的情况下，可以使目标函数达到最优解的解决方案。
而第二
个最优解则是在不考虑某些约束条件时，能够使目标函数达到最优解
的解决方案。
影子价格的计算公式是，Sj=c1-c2，其中Sj表示约束条件j的影
子价格，c1是考虑所有约束条件时可以使目标函数达到最优解的值，
c2是不考虑某些约束条件时可以使目标函数达到最优解的值。
通过计算影子价格，可以更好地确定系统的最优解。
因此，影子
价格的定义和计算在线性规划中起着重要的作用，可以帮助我们更快
更有效地找到满足目标的最优解。
线性规划对偶理论(含影子价格)_21136
对 偶
a11 a12
s.t.
a21
a22
a1n x1 b1
a2n
x2
b2
对 称
问
am1 am2
amn
xn
bm
形
题
x1, x2 , , xn 0
的
min Z c1x1 c2 x2 cn xn
定 义
a11 a21
s.t.
a12
a22
a1n a2n
x2 0,
x2
2
0
无界
关于无界性有如下结论： minW 4 y1 2 y2
原问题
问题无界
无可 行解
对偶问题 无可行解 无可行解
问题无界
y1 y2 2
（对）
y1
y1
y2 0, y2
1 0
无可 行解
原 : max Z x1 2x2
x1 x2 x3 2
2x1 x2 x3 1
m
m
A
≥b
n
对偶问题的特点
〔1〕目标函数在一个问题中是求最大值在 另一问题中则为求最小值
〔2〕一个问题中目标函数的系数是另一个 问题中约束条件的右端项
〔3〕一个问题中的约束条件个数等于另一 个问题中的变量数
〔4〕原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵
一般
线性规 划问题 的对偶 问题
〔4〕强对偶性〔最优解的目标函数之间的关系〕 如果原问题有最优解，则其对偶问题也一定有 最优解，且两者的目标函数值相等
3、互补松弛性
在线性规划问题的最优解中， 如果对应某一约束条件的对偶变量值为非零，
则该约束条件取严格等式；
反之如果约束条件取严格不等式，
线性规划对偶理论21136
l （2）一个问题中目标函数的系数是另一个 问题中约束条件的右端项
l （3）一个问题中的约束条件个数等于另一 个问题中的变量数
l （4）原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵
线性规划对偶理论21136
一般 线性规 划问题 的对偶 问题
线性规划对偶理论21136
对偶问题对应表
原问题（对偶问题）
-Z′ 42 -6 -9 0 0 0 -3
线性规划对偶理论21136
cj
-9 -12 -15 0 0
0
cB xB b
x1 x2 x3 x4 x5
x6
0 x4 -9/7 - 0 9/14
-12 x2 23/7 9/14 1
-15 x3 15/7 1/14 0
0 1 -9/14 -1/14
0 0 -5/14 1/14
试用对偶理论证明原问题无界。 解： =（0.0.0）是 原问题的一个可行解，而 对偶
问题 的第一个约束条件不能成立（因为y1 , y2 ≥0)。因 此，对偶问题不可行，可知，原问题无界。
线性规划对偶理论21136
（4）强对偶性（最优解的目标函数之间的关系） 如果原问题有最优解，则其对偶问题也一定有 最优解，且两者的目标函数值相等
线性规划对偶理论21136
对偶单纯形法的优点和缺点
优点： l 初始解可以是非可行解，当检验数都为负数时，就
可以进行基的变换，不需要加入人工变量。 l 当变量多于约束条件，用对偶单纯形法计算可以减
少计算工作量，因此对于变量较少，而约束条件很多 的线性规划问题，可以首先将它变换成为对偶问题， 然后用对偶单纯形法来求解。 l 在灵敏度分析中，有时需要使用对偶单纯形法，这 样可以使问题处理简化。
l （3）一个问题中的约束条件个数等于另一 个问题中的变量数
l （4）原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵
线性规划对偶理论21136
一般 线性规 划问题 的对偶 问题
线性规划对偶理论21136
对偶问题对应表
原问题（对偶问题）
-Z′ 42 -6 -9 0 0 0 -3
线性规划对偶理论21136
cj
-9 -12 -15 0 0
0
cB xB b
x1 x2 x3 x4 x5
x6
0 x4 -9/7 - 0 9/14
-12 x2 23/7 9/14 1
-15 x3 15/7 1/14 0
0 1 -9/14 -1/14
0 0 -5/14 1/14
试用对偶理论证明原问题无界。 解： =（0.0.0）是 原问题的一个可行解，而 对偶
问题 的第一个约束条件不能成立（因为y1 , y2 ≥0)。因 此，对偶问题不可行，可知，原问题无界。
线性规划对偶理论21136
（4）强对偶性（最优解的目标函数之间的关系） 如果原问题有最优解，则其对偶问题也一定有 最优解，且两者的目标函数值相等
线性规划对偶理论21136
对偶单纯形法的优点和缺点
优点： l 初始解可以是非可行解，当检验数都为负数时，就
可以进行基的变换，不需要加入人工变量。 l 当变量多于约束条件，用对偶单纯形法计算可以减
少计算工作量，因此对于变量较少，而约束条件很多 的线性规划问题，可以首先将它变换成为对偶问题， 然后用对偶单纯形法来求解。 l 在灵敏度分析中，有时需要使用对偶单纯形法，这 样可以使问题处理简化。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
a1n y1 a2n y2 amn ym (, )cn y j 0(符号不限,或 0)i 1 ~ m
对偶问题对应表
原问题（对偶问题）
目标函数min
约束条件： m个
第i个约束类型为“≥” 第i个约束类型为“≤” 第i个约束类型为“＝”
变量数：n个
第j个变量≤ 0 第j个变量x z(y)=bTy s.t. ATy≤C
y ≥0
max bT
原始问题 min f(x)=CTX s.t. AX≥b
X ≥0
min
CT
n AT ≤ C
m
m
A
≥b
n
对偶问题的特点
（1）目标函数在一个问题中是求最大值在 另一问题中则为求最小值
（2）一个问题中目标函数的系数是另一个 问题中约束条件的右端项
max Z 2x1 3x2 3x3
x1 x2 x3 3
s.t.x1 4x2 7x3 9
x1
0,
x2
0,
x3
0
A B C 拥有量
工时
111
3
材料
147
9
单件利润 2 3 3
假设有客户提出要求，购买工厂所拥有的 工时和材料，为客户加工别的产品，由客 户支付工时费和材料费。那么工厂给工时 和材料制订的最低价格应是多少，才值得 出卖工时和材料 ?
问
am1 am2
amn
xn
bm
形
题
x1, x2 , , xn 0
的
min Z c1x1 c2 x2 cn xn
定 义
a11 a21
s.t.
a12
a22
a1n a2n
am1 y1 c1
am2
y2
c2
amn
ym
cn
式 的 对 偶 问 题
y1, y2 , , ym 0
对偶问题
max z 6 y1 5 y2 9 y3
3y1 4 y2 y3 1
2 y1 2 y2 3y3 2
y1
3 y2
5 y3
3
y1符号不限, y2 0, y3 0
对偶问题的性质
1、对偶的对偶就是原始问题
min z=CTX s.t. AX≥b
X ≥0
对偶的定义
max y=bTW s.t. ATW≤C
XB XN
XS
b
XB
I B－1N
B－1
B－1b
N
0 CN－CBB－1N －CBB－1 －CBB－1b
j c j CB B1Pj
Y=CBB-1 称为单纯形乘子（对偶变量）
对偶原理
对偶问题概念：
任何一个线性规划问题都有一个与之相对应 的线性规划问题，如果前者称为原始问题，后者 就称为“对偶”问题。
(, )b2
am1x1 am2 x2 amn xn (, )bm
x j 0( 0,或符号不限) j 1 ~ n
max z b1 y1 b2 y2 bm ym
a11 y1 a21 y2 a12 y1 a22 y2
am1 ym (, )c1 am2 ym (, )c2
对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系，在 求得一个线性规划最优解的同时也就得到对偶线 性规划的最优解，反之亦然。
对偶理论就是研究线性规划及其对偶问题的 理论，是线性规划理论的重要内容之一。
问题的导出
A B C 拥有量
工时
111
3
材料
147
9
单件利润 2 3 3
保证A产品利润
y1+y2≥2
保证B产品利润
y1+4y2≥3
保证C产品利润
y1+7y2≥3
售价非负
y1≥0 y2≥0
A B C 拥有量
工时
111
3
材料
147
9
单件利润 2 3 3
minW 3y1 9 y2
y1 y2 2
s.t.
y1 y1
4y2 7 y2
3 3
y1 0, y2 0
W ≥0
max z’=-CTX s.t. -AX≤-b
X ≥0
对偶的定义
min y=-bTW s.t. -ATW≥-C
W ≥0
2、对偶问题的性质
（1）弱对偶性（可行解的目标函数值之间的关系） 设X、Y分别是原始问题和对偶问题的可行解
∑cjxj≤∑biyi
min f CT X
AX b
s.t.
A B C 拥有量
工时
111
3
材料
147
9
单件利润 2 3 3
•出卖资源获利应不少于生产产品的获利; 约束
•价格应该尽量低，这样，才能有竞争力; 目标
•价格应该是非负的
A B C 拥有量
工时
111
3
材料
147
9
单件利润 2 3 3
用y1和y2分别表示工时和材料的出售价格
总利润最小
min W=3y1+9y2
对偶问题（原问题）
目标函数max
变量数： m个
第i个变量≥0 第i个变量≤0 第i个变量是自由变量
约束条件：n个
第j个约束类型为“≥” 第j个约束类型为“≤” 第j个约束类型为“＝”
例 写出如下LP问题的对偶问题
min f x1 2x2 3x3
3x1 2x2 x3 6 4x1x1 3x22x2 x33x39 5 x1 0, x2 0,, x3符号不限
max Z 2x1 3x2 3x3
x1 x2 x3 3 s.t.x1 4x2 7x3 9
x1 0, x2 0, x3 0
maxW b1 y1 b2 y2 bm ym
对 偶
a11 a12
s.t.
a21
a22
a1n x1 b1
a2n
x2
b2
对 称
线性规划的对偶理论
对偶的定义 对偶问题的性质 对偶的经济解释
SUES
了解----单纯形的矩阵描述
max Z CB X B CN X N 0 X S
BX B NX XB, XN, X
N S
IX S 0
b
XS为松弛变量
XB XN XS
b
XB B
N
I
b
C CB CN 0
0
单纯性法计算时，总选取单位矩阵 I 为初始基， 对应基变量为XS, 设迭代若干步后，基变量变为 XB, XB 在初始单纯性表中的系数矩阵为 B。则该 步的单纯性表中由 XB 系数组成的矩阵为单位矩 阵 I ，对应XS 的系数矩阵在新表中应为B-1
（3）一个问题中的约束条件个数等于另一 个问题中的变量数
（4）原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵
一般
线性规 划问题 的对偶 问题
min f c1x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn (, )b1
a21x1
a22 x2
a2n xn