《and线性规划的进步研究》由会员分享，可在线阅读，更多相关《and线性规划的进步研究（56页珍藏版）》请在金锄头文库上搜索。
1、 2.12.1单纯形法的矩阵描述单纯形法的矩阵描述一、为什么要研究单纯形法的矩阵描述？一、为什么要研究单纯形法的矩阵描述？A-AT; max-min; 约束条件符号 - 变量符号（容易出错）原问题问题 （或对对偶问问 题题） 对对偶问题问题 （或原问问 题题） 目标标函数 Max Z目标标函数 Min W约约束条件数：m个 第i个约约束条件类类型为为“” 第i个约约束条件类类型为为“” 第i个约约束条件类类型为为 “=” 对对偶变变量数：m个 第i个变变量0 第i个变变量0 第i个变变量是自由变变量 决策变变量数：n个 第j个变变量0 第j个变变量0 第j个变变量是自由变变量 约约束条件数：n
2、 第i个约约束条件类类型为为“” 第i个约约束条件类类型为为“” 第i个约约束条件类类型为为 “=” 课堂练习2-1写出下面线性规划的对偶规划：下面的答案哪下面的答案哪 一个是正确的一个是正确的 ？为什么？为什么？（原问题是极小化问题，因此应从原始对偶 表的右边往左边查！） 三、对偶问题的基本性质三、对偶问题的基本性质对偶定理对偶定理是揭示原始问题的解与对是揭示原始问题的解与对 偶问题的解之间重要关系的一系列定理偶问题的解之间重要关系的一系列定理 ，包括，包括对称性定理、弱对偶定理、有界对称性定理、弱对偶定理、有界 性定理、最优性准则定理、主对偶定理性定理、最优性准则定理、主对偶定理 、互补松
3、弛性、互补松弛性等。等。则其对偶问题为定理定理2-12-1 对称性定理对称性定理对偶问题的对偶是原问题对偶问题的对偶是原问题。证明：设原始问题为将上式两端同时取负，并转变为将上式两端同时取负，并转变为maxmax形式形式对偶 变换变换 符号定理定理2-22-2 弱对偶定理弱对偶定理若一对对称形若一对对称形 式的对偶线性规划式的对偶线性规划（L） 和 （D） 均有可行解，分别为 和 ，则C b。证明思路由（L） 左乘 ，得 由（D） 右乘 ，得 通俗地讲：原问题的极大 化目标函数值 不会超过其对 偶问题的极小 化目标函数值由该定理可以得到什么附带结果？ 问：推论推论1 1 极大化问题的极大化问题
4、的任意一个可行解任意一个可行解所对应的目标函数值是所对应的目标函数值是 其对偶问题其对偶问题( (极小化问题极小化问题) )最优目标函数值的一个下界。最优目标函数值的一个下界。 “极小化问题有下界”推论推论2 2 极小化问题的任意一个可行解所对应的目标函数值是极小化问题的任意一个可行解所对应的目标函数值是 其对偶问题其对偶问题( (极大化问题极大化问题) )最优目标函数值的一个上界。最优目标函数值的一个上界。 “ 极大化问题有上界”无界性无界性 若原始问题（对偶问题）无界，则其若原始问题（对偶问题）无界，则其 对偶问题（原问题）无可行解。对偶问题（原问题）无可行解。定理定理2-4 2-4 最优
5、性准则定理最优性准则定理若若 、 分别分别 为原问题和对偶问题的可行解，且两者为原问题和对偶问题的可行解，且两者 目标函数的相应值相等，即目标函数的相应值相等，即C = bC = b，则，则 ， 分别为原始问题和分别为原始问题和 对偶问题的最优解。对偶问题的最优解。 C = b CXYb弱对偶 定 理已 知结论最优解定义最优解定义X=CX bY=特别取bYbCXCC Yb证明思路证明思路 定理定理2-52-5 主对偶定理主对偶定理 若原始问题有最若原始问题有最 优解，那么对偶问题也有最优解，且优解，那么对偶问题也有最优解，且 二者目标函数值相同。二者目标函数值相同。证明：设原始问题有对应于最优
6、基B的最优基本可 行解X=（XB，0）T, 则有XB=B-1b。对应于最优基 B的检验数满足 （最优单纯形乘子） 定义上式说明最优单纯形乘子是对偶问题的可行解；又上式进一步说明 是对偶问题的最优解，并验 证了两个问题的目标函数值相等。那么，根据最优性准则定理，这时的 正是对偶问 题的最优解。定理定理2-62-6 互补松弛性互补松弛性 若若 、 分别为原问分别为原问 题和对偶问题的可行解。那么题和对偶问题的可行解。那么 和和，当且仅当，当且仅当 、 为最优解。为最优解。思路：证明证明 和和 与与 、 为为最优解互为充要条件。最优解互为充要条件。将原问题目标函数中的系数向量C用CYA-YS代替 ，
7、得到同理，将对偶问题目标函数中的系数向量用bAX+XS 代替，得到若 ， ；则有 ，由最优性 准则定理可知， 为最优解。（必要性 ）若 ， 分别为原问题和对偶问题的最优解，根据主对 偶定理有 ，则必有 ， （充分性 ）定理定理2-7 2-7 如下所示的原问题和对偶问题，原问题如下所示的原问题和对偶问题，原问题 单纯形表的检验数行对应其对偶问题的一个基解，单纯形表的检验数行对应其对偶问题的一个基解， 对应关系如表所示。对应关系如表所示。XBXNXs0CN-CBb-1N-CBB-1Ys1-Ys2-Y其中，Ys1是对应于原问题中基变量XB的剩余变量 ，Ys2是对应于原问题中非基变量XN的剩余变量。证
8、明：设B是原始问题的一个可行基，于是 A=(B,N)；原问题及其对偶问题可改写为这里有Ys(Ys1, Ys2) 。 当求得原问题的一个解XBB-1b，XN和Xs的检验 数分别为：CN-CBB-1N, -CBB-1。分析XN和Xs的检验数CN-CBB-1N和-CBB-1 与对偶问题的解之间的关系。令Y CBB-1，将其带入对偶问题的资源约束 ，可得命题得证 。四、对偶问题的经济含义（影子价格四、对偶问题的经济含义（影子价格 ）1 1、 对偶最优解的经济解释对偶最优解的经济解释在单纯形法的迭代过程中，目标函数取值Z CBB-1b，和非基变量检验数CN-CBB-1N中都有乘子 Y=CBB-1。设B是
9、maxZ=CX;AX=0的最优 基，则 Z*=CBB-1b=Y*b，由此有，所以，yi*的经济意义是在其他条件不变的情况下， 单位资源变化所引起的目 标函数最优值的变化。回忆例1-1的求解结果。0 1 2 3 4 5 6 7 8 9 x15 4 3 2 1x2（8，0）C=6（0，4）C=0Q2（4，2）Q2（4, 2.5）Z=2*4+3*2=14Z=2*4+3*2.5=15.5Q2”（4.25, 1.875）Z=2*4.25+3*1.875=14.125通过上面的例子可以看出：yi* 的值表示对第i种资源的估价，它是针对具体问题而存在的一种资源 的特殊价格，称为“影子价格影子价格”，它是一个
10、线性规一个线性规划对偶问题的最优解，在经济上可以解释划对偶问题的最优解，在经济上可以解释为约束约束 条件所付出的代价条件所付出的代价。cj23000CBXBbx1x2x3x4x52x141001/40-0x5400-21/21-3x22011/2-1/80-cj-zj00-3/2 -1/80课后小组讨论课后小组讨论 3 3适当查阅参考书，讨论总结对偶定理的应用适当查阅参考书，讨论总结对偶定理的应用. .参考练习：参考练习：1 1、考察原始线性规划：、考察原始线性规划： 写出其对偶问题，然后讨论：如果知道是原问题的可行解（用什么办法可以较方便地寻找一个可行解？），能否对 对偶问题的目标函数值做出估计？以此为启发，能否对原问题目标函数值作出估计？2、下面的问题是某线性规划的对偶问题，请写出其原始问题。可以观察到 是原始问题的可行解。不要使用单纯形法求解，能否说明原 始问题最优解无界？
