对偶定理
- 格式：ppt
- 大小：1.50 MB
- 文档页数：14
下载文档原格式
合集下载
fenchel对偶定理
Fenchel对偶定理引言Fenchel对偶定理是数学中一个重要的理论，它在凸分析和凸优化等领域具有广泛的应用。
该定理由德国数学家Werner Fenchel在20世纪40年代提出，为我们提供了一种将凸函数的对偶问题转化为原始问题的方法。
本文将介绍Fenchel对偶定理的基本概念、证明过程以及应用。
Fenchel对偶定理的基本概念凸函数在介绍Fenchel对偶定理之前，我们首先需要了解什么是凸函数。
凸函数是指定义在实数集上的一个函数，其图像位于其任意两个点之间区域上方。
具体地说，一个函数f(x)被称为凸函数，如果对于任意两个实数x1和x2以及0 <= t <= 1，以下不等式成立：f(t*x1 + (1-t)*x2) <= t*f(x1) + (1-t)*f(x2)其中t表示权重。
对偶问题对于一个给定的原始问题（也称为原始优化问题），我们可以通过构造一个与之相关的对偶问题来求解原始问题。
这个与原始问题有着特定关系的问题被称为对偶问题。
通常情况下，对偶问题的求解比原始问题更加容易。
Fenchel对偶定理的表述Fenchel对偶定理描述了凸函数的对偶问题与原始问题之间的关系。
具体地说，设f(x)是一个凸函数，其定义域为实数集，那么其对偶函数f*(y)定义为：f*(y) = sup(x∈dom(f)) { y*x - f(x) }其中sup表示上确界，dom(f)表示函数f的定义域。
Fenchel对偶定理可以表述为：若f(x)是一个凸函数，则其对偶函数f*(y)也是一个凸函数，并且有以下关系成立：f**(x) = f(x)其中f**表示f*的对偶函数。
Fenchel对偶定理的证明过程Fenchel对偶定理的证明过程相当复杂，在此我们只给出一个简要概述。
首先，我们需要证明f*(y)是一个凸函数。
为此，我们需要证明它满足凸函数的定义。
具体来说，我们需要证明对于任意两个实数y1和y2以及0 <= t <= 1，以下不等式成立：f*(t*y1 + (1-t)*y2) <= t*f*(y1) + (1-t)*f*(y2)然后，我们使用分离超平面定理来证明上述不等式。
sylvester对偶定理_理论说明
sylvester对偶定理理论说明1. 引言1.1 概述本文旨在对Sylvester对偶定理进行理论说明，并探讨其在实际应用领域中的价值和影响。
Sylvester对偶定理是数学领域中一个重要的定理，它建立了向量空间中两个重要概念之间的联系：维数与秩。
通过该定理，我们可以更好地理解向量空间中维数和秩的含义，并应用于不同领域的问题求解。
1.2 文章结构本文分为五个主要部分，每个部分都有其特定目的：- 引言部分将介绍文章的概述、结构和目的。
- Sylvester对偶定理部分将给出该定理的定义、背景以及两个重要的理论说明。
- 应用领域分析部分将探讨Sylvester对偶定理在实际应用中的各个领域内具体作用和应用案例。
- 实例分析与证明部分将通过具体实例来解释和证明Sylvester对偶定理。
- 结论与展望部分将总结文章内容并展望未来研究方向。
1.3 目的本文旨在提供关于Sylvester对偶定理背后原理和应用领域相关信息的全面理解。
通过对该定理的深入研究，我们将揭示其在数学和实际问题中的重要性，并希望能够激发读者进一步探索和应用Sylvester对偶定理的兴趣。
2. Sylvester对偶定理:2.1 定义和背景:Sylvester对偶定理是数学中的一项重要定理，由詹姆斯·约瑟夫·西尔维斯特（James Joseph Sylvester）提出。
该定理主要涉及到二次型和矩阵的关系。
在线性代数和代数几何等领域，这个定理被广泛应用于求解问题、证明命题以及推导其他重要结论。
2.2 理论说明1:根据Sylvester对偶定理，给定一个实对称矩阵A，则存在一个实矩阵B，使得A可以表示为B的转置乘以A与B相乘的形式。
这种表示通常被称为二次型的标准形式或规范形式。
具体表达式如下：A = B^T * A * B其中，^T表示转置操作。
2.3 理论说明2:Sylvester对偶定理还指出了与矩阵的秩相关的一些性质。
对偶定理_精品文档
（2）极小化问题（对偶问题）的任一可行解
上页
所对应的目标函数值是原问题最优目标函数值
的上界。
下页
返回
原问题
对偶问题
CX Y b
对偶问题的基本性质
定理三 最优性准则定理 若X~ 、Y~ 分 别为对称形式对C偶X 线 Y性b,规划X的 ,可Y 行解， 且两者目标函数的相应值相等， C X~ =bY~ ，则 X~ ，Y~ 分别为原始问题 和对偶问题的最优解。
x1, x2 0
下页
min 8 y1 4 y2 6 y3
返回
2 y1 4 y3 5
2 y1
3y2
y3
4
y1
,
y2 ,
y3
0
对 偶
课堂练习：已知线型规划问题
问
题
min Z 2x1 3x2 5x3 2x4 3x5
上页
2x1x1 x2x223x3x3xx4 43xx55
偶 问
二、弱对偶性定理：
题
——若 和X 分别Y 是原问题（1）及
对偶问题（2）的可行解，则有
上页
CX Yb
下页
证明： AX b YAX Yb YA C YAX CX
返回
CX YAX Yb
从弱对偶性可得到以下重要结论：
对
偶 （1）极大化问题（原问题）的任一可行解所
问 题
对应的目标函数值是对偶问题最优目标函数值 的下界。
4 3
下页
x
j
0,
j
1,2...,5
返回 又已知其对偶问题的最优解为y1=4/5，y2=3/5，
Z＝5。试用对偶理论解原问题。
互补松弛定理应用：
对 偶
（1）从已知的最优对偶解，求原问题最
帕斯卡定理的对偶定理(3篇)
第1篇一、帕斯卡定理及其背景帕斯卡定理是组合数学中的一个基本定理，它描述了二项式系数的性质。
具体来说，对于任意的非负整数n和k，有：C(n, k) = C(n-1, k-1) + C(n-1, k)其中，C(n, k)表示从n个不同元素中取出k个元素的组合数，也称为二项式系数。
帕斯卡定理的证明有多种方法，其中一种常用的是数学归纳法。
假设当n=1时，帕斯卡定理成立，即C(1, k) = C(0, k-1)，显然成立。
接下来，假设当n=m时，帕斯卡定理成立，即C(m, k) = C(m-1, k-1) + C(m-1, k)。
现在考虑n=m+1的情况，我们有：C(m+1, k) = C(m, k-1) + C(m, k)根据归纳假设，上式可转化为：C(m+1, k) = [C(m-1, k-2) + C(m-1, k-1)] + [C(m-1, k-1) + C(m-1, k)]合并同类项，得：C(m+1, k) = C(m-1, k-2) + 2C(m-1, k-1) + C(m-1, k)这正是C(m+1, k) = C(m, k-1) + C(m, k)的形式，说明帕斯卡定理在n=m+1时也成立。
由数学归纳法，帕斯卡定理对所有的非负整数n和k都成立。
二、帕斯卡定理的对偶定理帕斯卡定理的对偶定理是关于组合数之间的一种对偶关系。
具体来说，对于任意的非负整数n和k，有：C(n, k) = C(n, n-k)这个对偶定理揭示了组合数之间的对称性。
证明如下：由组合数的定义，C(n, k)表示从n个不同元素中取出k个元素的组合数。
而C(n, n-k)表示从n个不同元素中取出n-k个元素的组合数。
由于从n个元素中取出的元素个数总和为n，因此取出k个元素的同时，必然取出了n-k个元素。
因此，C(n, k)和C(n, n-k)表示的是相同的情况，即从n个元素中取出k个元素，剩下的n-k个元素也被取出。
因此，C(n, k) = C(n, n-k)。
对偶定理和反演定理
对偶定理和反演定理
对偶定理和反演定理是组合数学中常用的两个定理。
对偶定理是指：对于一个命题，把其中的所有“∧”和“∨”互换位置，把所有的“真”和“假”互换位置，所得到的命题与原命题等价。
例如，若命题为“若一个人不是男性且不是成年人，则他是未成年女性”，则对偶命题为“若一个人不是未成年女性或不是女性，则他是成年人或男性”。
对偶定理在组合数学中有着广泛的应用，例如在计算某些图形的性质时，可以通过对偶来简化问题。
反演定理是指：在一个集合中，如果存在某种关系，我们可以通过反演来求出该集合中满足某一条件的元素个数。
具体地，如果存在一个函数$f:Srightarrow T$，其中$S$表示原集合，$T$表示目标集合，且$f$是可逆的，那么我们可以通过反演来求出集合$S$中满足某一条件的元素个数，例如：
设$S$为由$n$个元素组成的集合，$T$为由所有的01串构成的集合，$f:Srightarrow T$是一个将$S$中的元素映射为01串的函数。
如果我们需要求出$S$中满足某一条件的元素个数，可以先通过$f$将$S$中的元素映射为01串，然后对$T$中的所有元素进行计数，最后再通过$f$的逆映射得到集合$S$中满足条件的元素个数。
反演定理在组合数学中有着广泛的应用，例如在计算某些图形的性质时，可以通过反演来求解。
- 1 -。
第三章线性规划的对偶定理
特点：
1． max min 2．限定向量b 价值向量C
其它形式 的对偶
?
（资源向量）
3．一个约束 一个变量。
4． max z的LP约束“ ” min z 的
LP是“ ”的约束。
5．变量都是非负限制。
二、原问题与对偶问题的数学模型
❖ 1．对称形式的对偶
当原问题对偶问题只含有不等式约束
时，称为对称形式的对偶。
根据对称形式的对偶模型,可直接 写出上述问题的对偶问题:
b max w (Y 1,Y 2 ) -b
(Y
1,Y
2
)
A A
C
Y1 0 ,Y2 0
max w (Y 1 Y 2 ) b
(Y
1
Y
2
)
A
C
Y 1 0, Y 2 0
令 Y Y，1 Y得2对偶问题为：
max w Yb
❖ （3）若原问题可行，但其目标函数值无 界，则对偶问题无可行解。
❖ （4）若对偶问题可行，但其目标函数值 无界，则原问题无可行解。
❖ （5）若原问题有可行解而其对偶问题无 可行解，则原问题目标函数值无界。
❖ （6）对偶问题有可行解而其原问题无可 行解，则对偶问题的目标函数值无界。
CX Yb
原问题
设备A 设备B 调试工序
产品Ⅰ 产品Ⅱ
0
5
6
2
1
1
利润（元） 2
1
D
15时 24时 5时
x 设 Ⅰ产量––––– 1
x Ⅱ产量––––– 2
如何安排生产， 使获利最多？
max z 2 x1 x2
s.t.
5x2 15
6 x1 2 x2 24
第一章-命题逻辑04对偶定理
相反赋值
4.2定义 如果真值赋值 v1 和 v2 满足:
对每个命题变元 p , pv1=/ pv2 , 则称 v1 和 v2 是相反的.
□ □
对偶定理
4.1定理(真值相关) 设 A 是由 {0,1,\ ,[,Z} 生成的公式,
A* 与 A 互为对偶式 v 和 vd 是相反的真值赋值
则v(A*)=\ vd(A) .
设 A 的长度为 n+1 ,对于长度不超过 n 的每个公式 B , v(B*)=\ vd(B).
若 A 为 \ B , 则 B 的小于 n , 由归纳假设知, v(B*)=\ vd(B).
A* 为 \ B* . 因此, v(A*) =v(\ B*) =\ v(B*) =\ \ vd(B) =\ vd(\ B).
v(A*)=\ vd(A)==\ vd(B)v(B*) 所以,A* EB* .
□ □
定理应用
4.2例子 证明以下等值式：
(p[q)Z(\ pZ(\ pZq))E\ pZq
(pZq)[(\ p[(\ p[q))E\ p[q □
解答
(p[q)Z(\ pZ(\ pZq)) E(p[q)ZqZ\ p EqZ\ p E\ pZq
若 A 为 B[C ,则 B 和 C 的长度都小于 n , 由归纳假设知, v(B*)=\ vd(B) 且 v(C*)=\ vd(C),
A* 为 B*ZC* . 因此, v(A*) =v(B*ZC*) =v(B*)Zv(C*) =\ vd(B)Z\ vd(C) =vd(\ BZ\ C) =\ vd(B[C).
所以
(pZq)[(\ p[(\ p[q))E\ p[q. □ □
4.2定理(对偶定理) 设 A,B 是由 {0,1,\ ,[,Z} 生成的公式:
4.2定义 如果真值赋值 v1 和 v2 满足:
对每个命题变元 p , pv1=/ pv2 , 则称 v1 和 v2 是相反的.
□ □
对偶定理
4.1定理(真值相关) 设 A 是由 {0,1,\ ,[,Z} 生成的公式,
A* 与 A 互为对偶式 v 和 vd 是相反的真值赋值
则v(A*)=\ vd(A) .
设 A 的长度为 n+1 ,对于长度不超过 n 的每个公式 B , v(B*)=\ vd(B).
若 A 为 \ B , 则 B 的小于 n , 由归纳假设知, v(B*)=\ vd(B).
A* 为 \ B* . 因此, v(A*) =v(\ B*) =\ v(B*) =\ \ vd(B) =\ vd(\ B).
v(A*)=\ vd(A)==\ vd(B)v(B*) 所以,A* EB* .
□ □
定理应用
4.2例子 证明以下等值式：
(p[q)Z(\ pZ(\ pZq))E\ pZq
(pZq)[(\ p[(\ p[q))E\ p[q □
解答
(p[q)Z(\ pZ(\ pZq)) E(p[q)ZqZ\ p EqZ\ p E\ pZq
若 A 为 B[C ,则 B 和 C 的长度都小于 n , 由归纳假设知, v(B*)=\ vd(B) 且 v(C*)=\ vd(C),
A* 为 B*ZC* . 因此, v(A*) =v(B*ZC*) =v(B*)Zv(C*) =\ vd(B)Z\ vd(C) =vd(\ BZ\ C) =\ vd(B[C).
所以
(pZq)[(\ p[(\ p[q))E\ p[q. □ □
4.2定理(对偶定理) 设 A,B 是由 {0,1,\ ,[,Z} 生成的公式:
对偶定理实验报告
一、实验目的1. 理解对偶定理的基本概念和原理。
2. 掌握对偶定理的证明方法。
3. 通过实验验证对偶定理的正确性。
4. 培养学生的逻辑思维能力和实际操作能力。
二、实验原理对偶定理是图论中的一个重要定理，它揭示了两个图之间的对偶关系。
对偶定理的表述如下：设G=(V,E)是一个简单无向图，V为顶点集，E为边集。
若G的对偶图G'=(V',E')满足以下条件：（1）G'的顶点集V'与G的边集E一一对应；（2）G'的边集E'与G的顶点集V一一对应；（3）若G中存在一条从顶点u到顶点v的路径，则G'中存在一条从边u到边v的路径，反之亦然。
则称G和G'为对偶图。
三、实验内容1. 选择一个简单无向图G，并画出其图形。
2. 根据对偶定理的原理，构造G的对偶图G'。
3. 证明G和G'为对偶图。
4. 分析对偶图G'的性质。
四、实验步骤1. 选择一个简单无向图G，例如K3,3（三个顶点的完全图）。
2. 画出G的图形，并标注顶点和边。
3. 根据对偶定理的原理，构造G的对偶图G'。
对于G中的每条边，在G'中找到对应的顶点，并将G'中的顶点两两相连，形成G'的边。
4. 证明G和G'为对偶图。
具体步骤如下：（1）证明G'的顶点集V'与G的边集E一一对应。
由于G中有6条边，G'中有6个顶点，且G'的顶点与G的边一一对应，因此满足条件。
（2）证明G'的边集E'与G的顶点集V一一对应。
由于G中有3个顶点，G'中有3条边，且G'的边与G的顶点一一对应，因此满足条件。
（3）证明若G中存在一条从顶点u到顶点v的路径，则G'中存在一条从边u到边v的路径，反之亦然。
对于G中的一条从顶点u到顶点v的路径，将其对应的边u 和边v在G'中相连，即可得到一条从边u到边v的路径。
对偶原理
证明：对于问题（P）的任意一个可行解X ，必有
CX≤Y*b 但 CX*=Y*b ， 故对原问题（P）的所有可行解X，有
CX≤CX* 所以，X*为原问题（P）的最优解。 同理可证Y*是对偶问题（D）的最优解。
例Leabharlann min W 20 y1 20 y2
max Z x1 2x2 3x3 4x4
x1 2x2 2x3 3x4 20
C)X
*
0
根据这一定理，在一对对偶问题中，我们可以把其 中任何一个称为原问题，则另一个就是其对偶问题.
定理1（对称性定理）对偶问题的对偶是原问题.
证明：对于问题（D）
minW Yb
(D)
s.t.
YA C Y 0
将问题(D)改写对称形 式(D)’ ：
maxW (bT )Y T
s.t.
( AT
xj 0( j 1, 2,3)
解：此问题的对偶问题为 max Z x1 2x2
min W 2 y1 y2
y1 2 y2 1
s.t.
s.t.
y1 y2 2 y1 3y2 0
y1, y2 0
x1 x2 x3 2 2x1 x2 3x3 1 xj 0( j 1, 2,3)
Y
T
)Y 0
T
CT
记对偶变量为XT，
则(D)’的对偶规划为
min z' ( X TCT )
即
s.t.
X X
T T
(
AT 0
)
bT
max Z CX
AX b
s.t.
X
0
这就是原问题(P),证毕.
定理2（弱对偶定理） 设 X 和 Y 分别是问题(P)和(D)的可行解，则必有
CX≤Y*b 但 CX*=Y*b ， 故对原问题（P）的所有可行解X，有
CX≤CX* 所以，X*为原问题（P）的最优解。 同理可证Y*是对偶问题（D）的最优解。
例Leabharlann min W 20 y1 20 y2
max Z x1 2x2 3x3 4x4
x1 2x2 2x3 3x4 20
C)X
*
0
根据这一定理，在一对对偶问题中，我们可以把其 中任何一个称为原问题，则另一个就是其对偶问题.
定理1（对称性定理）对偶问题的对偶是原问题.
证明：对于问题（D）
minW Yb
(D)
s.t.
YA C Y 0
将问题(D)改写对称形 式(D)’ ：
maxW (bT )Y T
s.t.
( AT
xj 0( j 1, 2,3)
解：此问题的对偶问题为 max Z x1 2x2
min W 2 y1 y2
y1 2 y2 1
s.t.
s.t.
y1 y2 2 y1 3y2 0
y1, y2 0
x1 x2 x3 2 2x1 x2 3x3 1 xj 0( j 1, 2,3)
Y
T
)Y 0
T
CT
记对偶变量为XT，
则(D)’的对偶规划为
min z' ( X TCT )
即
s.t.
X X
T T
(
AT 0
)
bT
max Z CX
AX b
s.t.
X
0
这就是原问题(P),证毕.
定理2（弱对偶定理） 设 X 和 Y 分别是问题(P)和(D)的可行解，则必有
对偶定理运筹学
对偶定理是运筹学中最基本的概念之一，它在线性规划中起着非常重要的作用。
在线性规划问题中，存在原始问题和对偶问题两种形式，它们之间通过对偶定理建立了密切的联系。
对偶定理的核心思想是将原始线性规划问题转化为对偶问题，并且通过对偶问题来分析原始问题，从而得到有关原始问题的有效信息。
具体来说，对偶定理可以帮助我们在求解原始问题时，通过求解对偶问题来获得额外的信息和优化结果。
在运筹学中，对偶定理的应用主要体现在以下几个方面：
1. 最优性分析：对偶定理可以帮助我们分析原始问题的最优解以及对应的对偶问题，从而验证原始问题的最优性和对偶问题的最优性，并且可以相互印证，增强了问题解的可靠性。
2. 敏感度分析：对偶定理也可以用于进行敏感度分析，通过对对偶问题的解进行改变，可以评估原始问题解对参数变化的敏感程度，从而指导决策者进行风险评估和决策制定。
3. 经济学解释：对偶问题的解可以提供经济学上的解释和意义，比如对偶问题中的对偶变量可以表示资源的单位价值，对偶问题的约束条件可以反映出资源的受限性，这些信息可以为管理决策提供重要参
考。
总之，对偶定理在运筹学中具有重要的作用，通过对原始问题和对偶问题的分析，可以为决策者提供更全面的信息，帮助其做出更加合理的决策。
因此，对偶定理是线性规划理论中不可或缺的重要内容。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
max -f=-Yb -YA -C Y 0 根据变换关系，得到上式的对偶问题是：
min(-f’)=-CX -AX -b X 0 又因： min(-f’)=maxf 得到 maxf =maxz= CX AX b
X 0
2 弱对偶性 若 是原问题的可行解， 是对偶 问题的可行解，则存在: C b
证明：设原问题是
这里YS=(YS1,YS2)当求得原问题的一个解： XB=B-1b 其相应的检验数为CN-CBB-1N与- CBB-1 令Y=CBB-1,代入上式，得到
YS1=0 -YS2=CN-CBB-1N
例4
布置作业
P74 2.2 2.4 2.6
同理 可证明 C = bC
所以 是最优解
5.对偶定理 若原问题有最优解，那么对偶问题也有最优解；且 目标函数值相等。
证明：设 是原问题的最优解，他对应的基矩阵B 必存在C-CBB-1A 0.即得到 A C，其中 = CBB-1。 若此时 是对偶问题的可行解，它使
因原问题的最优解是 ，使目标函数取值 由此，得到
maxz=CX AX b X 0 因为 是原问题的可行解，所以A b
若 是给定的一组值，设它是对偶问题的可行解，将 左乘上式，得到 A b
原问题的对偶问题是： min f=Yb YA C Y 0 因为 是对偶问题的可行解，所以 A C 若 右乘上式，得到： A C 得到C A b
3.无界性 若原问题（对偶问题）为无界解， 则其对偶问题（原问题）无可行解。
第三章 对偶线性规划
运筹帷幄，决胜千里
史记《张良传》
第七讲
(2 学时)
2005-09-22
P57
§4.2 对偶问题的基本性质
1. 对称性 对偶问题的对偶是原问题
证明：设原问题是 maxz=CX AX b X 0
根据对偶问题的对称变换关系，得到对偶问题是
min f=Yb YA C Y 0 若将上式两边取负，得到：
反之 不成立
当原问题无可行解时，其对偶问题或具有 无界解或者无可行解。
例：
4 .可行解是最优解时的性质 设 是原问 题的可行解， 是对偶问题的可行解，当
C = b 时，两个解是最优解。
证明：若C = b ，根据性质2，可知，对偶问 题的所有可行解 都存在 b C ，因为 C = b ,所以 b b .可见 是使目标 函数取值最小的可行解，因而是最优解。
可见 是对偶问题的最优解。
6 互补松弛性
证明：
7. 设原问题是 它的对偶问题是 则原问题单纯表的检验数行对应其对偶问
题的一个基解，对应关系如下：
Ys1是对应原问题中基变量XB的剩余变量， Ys2是对基，于是 A=(B,N)原问题可以改写成：
min(-f’)=-CX -AX -b X 0 又因： min(-f’)=maxf 得到 maxf =maxz= CX AX b
X 0
2 弱对偶性 若 是原问题的可行解， 是对偶 问题的可行解，则存在: C b
证明：设原问题是
这里YS=(YS1,YS2)当求得原问题的一个解： XB=B-1b 其相应的检验数为CN-CBB-1N与- CBB-1 令Y=CBB-1,代入上式，得到
YS1=0 -YS2=CN-CBB-1N
例4
布置作业
P74 2.2 2.4 2.6
同理 可证明 C = bC
所以 是最优解
5.对偶定理 若原问题有最优解，那么对偶问题也有最优解；且 目标函数值相等。
证明：设 是原问题的最优解，他对应的基矩阵B 必存在C-CBB-1A 0.即得到 A C，其中 = CBB-1。 若此时 是对偶问题的可行解，它使
因原问题的最优解是 ，使目标函数取值 由此，得到
maxz=CX AX b X 0 因为 是原问题的可行解，所以A b
若 是给定的一组值，设它是对偶问题的可行解，将 左乘上式，得到 A b
原问题的对偶问题是： min f=Yb YA C Y 0 因为 是对偶问题的可行解，所以 A C 若 右乘上式，得到： A C 得到C A b
3.无界性 若原问题（对偶问题）为无界解， 则其对偶问题（原问题）无可行解。
第三章 对偶线性规划
运筹帷幄，决胜千里
史记《张良传》
第七讲
(2 学时)
2005-09-22
P57
§4.2 对偶问题的基本性质
1. 对称性 对偶问题的对偶是原问题
证明：设原问题是 maxz=CX AX b X 0
根据对偶问题的对称变换关系，得到对偶问题是
min f=Yb YA C Y 0 若将上式两边取负，得到：
反之 不成立
当原问题无可行解时，其对偶问题或具有 无界解或者无可行解。
例：
4 .可行解是最优解时的性质 设 是原问 题的可行解， 是对偶问题的可行解，当
C = b 时，两个解是最优解。
证明：若C = b ，根据性质2，可知，对偶问 题的所有可行解 都存在 b C ，因为 C = b ,所以 b b .可见 是使目标 函数取值最小的可行解，因而是最优解。
可见 是对偶问题的最优解。
6 互补松弛性
证明：
7. 设原问题是 它的对偶问题是 则原问题单纯表的检验数行对应其对偶问
题的一个基解，对应关系如下：
Ys1是对应原问题中基变量XB的剩余变量， Ys2是对基，于是 A=(B,N)原问题可以改写成：