第二章第二章 对偶理论对偶理论n2.1 对偶规划对偶规划n2.2 对偶定理对偶定理n2.3 对偶单纯形法对偶单纯形法n2.4 线性规划灵敏度分析线性规划灵敏度分析n2.5 运输问题运输问题 n弱对偶定理弱对偶定理n强对偶定理强对偶定理n松紧定理松紧定理 原规划和对偶规划最优解原规划和对偶规划最优解之间的关系之间的关系复习复习第二章第二章 对偶理论对偶理论第二节第二节 对偶定理对偶定理 对偶理论2-2一一. .弱对偶定理：弱对偶定理：定理定理2-12-1：：推论推论1 1：：minS = maxZ设设X 和和 分别是分别是(P)和和(D)的可行解，则有的可行解，则有若若 和和 分别是分别是(P)和和(D)的可行解，且的可行解，且则则 和和 分别是分别是(P)和和(D)的最优解的最优解 二二. .强对偶定理：强对偶定理：定理定理2-22-2：：推论推论3 3：：推论推论1 1：：(P)有有限的最优解有有限的最优解 (D)有有限的最优解有有限的最优解且相应的目标函数值相等，即且相应的目标函数值相等，即若若 是是(P)的最优基本可行解，的最优基本可行解，B是相应的最优基，是相应的最优基， 则单纯形乘子则单纯形乘子 是是(D)的最优解。
的最优解若若(P)和和(D)中有一个有可行解，但没有有限的最优中有一个有可行解，但没有有限的最优解，则另一个问题无可行解解，则另一个问题无可行解对偶理论2-2 第二章第二章 对偶理论对偶理论n2.1 对偶规划对偶规划n2.2 对偶定理对偶定理n2.3 对偶单纯形法对偶单纯形法n2.4 线性规划灵敏度分析线性规划灵敏度分析n2.5 运输问题运输问题 第三节第三节 对偶单纯形法对偶单纯形法n基本思想基本思想n迭代原理迭代原理n举例求解举例求解n影子价格影子价格 第二章第二章 对偶理论对偶理论 单纯形法是保持单纯形法是保持 使迭代向实现使迭代向实现 进行一一. .基本思想：基本思想：11110 00000最优表最优表是基变量下标集是基变量下标集对偶单纯形法是保持对偶单纯形法是保持 使迭代向实现使迭代向实现 进行对偶理论2-3 若若 ，则这个解，则这个解X是是(P)的最优基本可行解的最优基本可行解若若(P)的一个基的一个基B，使得单纯形乘子，使得单纯形乘子 是是(D)的可行解的可行解 ，则，则(P)相应的基本解相应的基本解对偶可行解，正则基：对偶可行解，正则基：称为对偶可行解，称为对偶可行解，B称为正则基。
称为正则基对偶理论2-3 对偶理论2-3对偶可行解，正则基：对偶可行解，正则基：理解：理解：若若(P)的一个基的一个基B，使得单纯形乘子，使得单纯形乘子 是是(D)的可行解的可行解 ，则，则(P)相应的基本解相应的基本解 称为称为对偶可行解，对偶可行解，B称为正则基称为正则基若若 ，则，则X是是(P)的最优解的最优解1) 一个基一个基B对应一个单纯形乘子对应一个单纯形乘子2) 是是(D)的可行解的可行解正则基正则基 B对应的基本解称为对偶可行解对应的基本解称为对偶可行解B相应的单纯形表的检验数行相应的单纯形表的检验数行对应正则基的单纯形乘子是对应正则基的单纯形乘子是(D)的可行解；的可行解；对应最优基的单纯形乘子是对应最优基的单纯形乘子是(D)的最优解的最优解B是正则基是正则基 对偶可行解，正则基：对偶可行解，正则基：若若(P)的一个基的一个基B，使得单纯形乘子，使得单纯形乘子 是是(D)的可行解的可行解 ，则，则(P)相应的基本解相应的基本解 称为称为对偶可行解，对偶可行解，B称为正则基。
称为正则基若若 ，则，则X是是(P)的最优解的最优解基基可行基可行基正则基正则基最优基最优基基本解基本解 基本可行解基本可行解 对偶可行解对偶可行解 最优基本可行解最优基本可行解可逆可逆对偶理论2-3 n基本思想基本思想n迭代原理迭代原理n举例求解举例求解n影子价格影子价格 第三节第三节 对偶单纯形法对偶单纯形法第二章第二章 对偶理论对偶理论 二二. .迭代原理：迭代原理：11110 000对偶理论2-3 对偶理论2-3准备工作：准备工作：0,1,0,1, 11110 000准备工作：准备工作：0,1,对偶理论2-3 11110 000准备工作：准备工作：0,1,对偶理论2-3 设设 是是(P)的一个正则基，的一个正则基，11110 000二二. .迭代原理：迭代原理：0是是(D)的可行解的可行解则则对偶理论2-3 11110 00000 0 0 0二二. .迭代原理：迭代原理：设设 是是(P)的一个正则基，的一个正则基，则则 是是(P)的最优解的最优解,是是(D)的最优解。
的最优解则当前基本解则当前基本解不是最优解，因此进行换基运算，得到新表不是最优解，因此进行换基运算，得到新表对偶理论2-3 11110 00001.1.确定离基变量：确定离基变量：0 00 0二二. .迭代原理：迭代原理：则第则第r个方程的基变量个方程的基变量 离基对偶理论2-3 11110 00002.2.确定进基变量：确定进基变量：0 00 0二二. .迭代原理：迭代原理：不是不是(D)的最优解的最优解,不是不是(D)的最优值的最优值.所以所以(D)有可行解有可行解 使目标值使目标值 ，即，即的第的第r个行向量，个行向量，对偶理论2-3 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0,1,对偶理论2-3 11110 00000 0对偶理论2-3 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 0( 使使(D)目标值目标值 )0,1,对偶理论2-3 (D)的可行解的可行解(D)的可行解的可行解2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，2) 取取 使使 是是(D)的可行解的可行解, ,(D)的可行解的可行解(P)的最优解的最优解(P)无可行解无可行解对偶单纯形法的求解过程：对偶单纯形法的求解过程：( 使使(D)目标值目标值 )对偶理论2-30 0 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 02) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列( 使使(D)目标值目标值 )对偶理论2-3 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 0( 使使(D)目标值目标值 )2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列对偶理论2-30,1, 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 0( 使使(D)目标值目标值 )2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列对偶理论2-30,1, 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 0( 使使(D)目标值目标值 )2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列对偶理论2-3 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 0( 使使(D)目标值目标值 )2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列非基列非基列[3][3]对偶理论2-3 2.2.确定进基变量：确定进基变量：1) 对对的第的第r个行向量，个行向量，0 0( 使使(D)目标值目标值 )2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列非基列非基列[3][3]0,1,对偶理论2-3 非基列非基列2.2.确定进基变量：确定进基变量：的第的第r个行向量，个行向量，2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列[3][3]1 1若对若对都有都有对偶理论2-3 11110 00000 000二二. .迭代原理：迭代原理：对偶理论2-3 即对即对 是是(D)的可行解。
的可行解非基列非基列2.2.确定进基变量：确定进基变量：的第的第r个行向量，个行向量，2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列[3][3]1 1若对若对都有都有则则00但但0,1,对偶理论2-3 即对即对 是是(D)的可行解的可行解非基列非基列2.2.确定进基变量：确定进基变量：的第的第r个行向量，个行向量，2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列[3][3]1 1若对若对都有都有则则但但即即(D)没有有限的最优解，没有有限的最优解，0 02 2所以所以(P) 无可行解无可行解若若使使对偶理论2-3 11110 00000 00 0二二. .迭代原理：迭代原理：对偶理论2-3 为进基变量，为进基变量， 为主元为主元非基列非基列2.2.确定进基变量：确定进基变量：的第的第r个行向量，个行向量，2) 取取 使使 是是(D)的可行解的可行解, ,[1][1]不离基的基列不离基的基列[2][2] 离基的基列离基的基列[3][3]1 1若对若对都有都有(D)没有有限的最优解，没有有限的最优解，2 2所以所以(P) 无可行解。
无可行解若若使使要使要使3.3.进行换基运算：进行换基运算：得到新的单纯形表得到新的单纯形表对偶理论2-3 以以 为主元进行换基运算，得到新的单纯形表为主元进行换基运算，得到新的单纯形表11110 00000 00 00 0二二. .迭代原理：迭代原理：为进基变量为进基变量,所以新表对应的所以新表对应的基本解基本解目标值目标值对偶理论2-3 以以 为主元进行换基运算，得到新的单纯形表为主元进行换基运算，得到新的单纯形表11110 00000 00 00 0二二. .迭代原理：迭代原理：为进基变量为进基变量对偶理论2-31.1.确定离基变量：确定离基变量：2.2.确定进基变量：确定进基变量：为离基变量为离基变量3.3.换基运算：换基运算： 第二章第二章 对偶理论对偶理论n2.1 对偶规划对偶规划n2.2 对偶定理对偶定理n2.3 对偶单纯形法对偶单纯形法n2.4 线性规划灵敏度分析线性规划灵敏度分析n2.5 运输问题运输问题 n基本思想基本思想n迭代原理迭代原理n举例求解举例求解n影子价格影子价格 第三节第三节 对偶单纯形法对偶单纯形法第二章第二章 对偶理论对偶理论 11110 0000二二. .迭代原理：迭代原理：设设 是是(P)的一个正则基，的一个正则基，则则 是是(P)的最优解的最优解,是是(D)的最优解。
的最优解则当前基本解则当前基本解不是最优解，因此进行换基运算，得到新表不是最优解，因此进行换基运算，得到新表对偶理论2-3复习复习 以以 为主元进行换基运算，得到新的单纯形表为主元进行换基运算，得到新的单纯形表11110 00000 00 00 0二二. .迭代原理：迭代原理：为进基变量为进基变量对偶理论2-31.1.确定离基变量：确定离基变量：2.2.确定进基变量：确定进基变量：为离基变量为离基变量3.3.换基运算：换基运算：复习复习 三三. .举例：举例：对偶单纯形法开始于一个正则基对偶单纯形法开始于一个正则基B,即即注意：注意：例例2-22-2：：标准形标准形正则基正则基所以适用于所以适用于 且不等式约束都是且不等式约束都是 的问题对偶理论2-3 -1-2-310-5-2-2-101-634500034500000正则基正则基为进基变量为进基变量例例2-22-2：：对偶理论2-3 -1-2-31-5-2-2-101-634500001/3×(-1/3)2/3 1-1/35/3例例2-22-2：：对偶理论2-3 1/3-2-2-101-634500002/3 1-1/35/30-5/3-4/3-1/3-13/3例例2-22-2：：对偶理论2-3 1/3-5/3-13/3134500002/3 1-1/35/30-4/3-1/3×(-5)04/32/35/3-25/3例例2-22-2：：对偶理论2-3 11/3-5/3-13/3102/3-1/35/30-4/3-1/3004/32/35/3-25/30正则基正则基为进基变量为进基变量例例2-22-2：：对偶理论2-3 -4/3 11/3-5/3-13/3102/3-1/35/30-1/3004/32/35/3-25/3×(-3/4) 15/41/4 -3/413/4例例2-22-2：：对偶理论2-3 0 15/41/4 -3/413/4 11/302/3-1/35/3004/32/35/3-25/3×(-2/3) 0-1/2-1/2 1/2-1/2例例2-22-2：：对偶理论2-3 -1/2-1/20 15/41/4 -3/413/4004/32/35/3-25/3 1 0-1/2 1/2×(-2/3) 01/23/2 1/2-21/2例例2-22-2：：对偶理论2-3 -1/2-1/20 15/41/4 -3/413/4 1 0-1/2 1/20 03/2 1/21/2-21/20正则基正则基为进基变量为进基变量例例2-22-2：：对偶理论2-3 -1/2-1/20 15/41/4 -3/413/4 1 0-1/2 1/20 03/2 1/21/2-21/2×(-2) 1 -2 1-1 1例例2-22-2：：对偶理论2-3 0 1 -2 1-1 10 15/41/4 -3/413/40 03/2 1/21/2-21/2×(-5/4) 0-1 2 5/2 1/2例例2-22-2：：对偶理论2-3 1 0-1 2 5/2 1/2 0 1 -2 1-1 10 03/2 1/21/2-21/2×(-1/2) 011 1 -11例例2-22-2：：对偶理论2-3 1 0-1 2 5/2 1/2 0 1 -2 1-1 1 0 011 1最优表最优表0最优基最优基正则基正则基最优解最优解原问题最优解原问题最优解 -11例例2-22-2：：对偶理论2-3 例例2-22-2：：对偶理论2-3 1 0-1 2 5/2 1/2 0 1 -2 1-1 1 0 011 1 -1100E(1,1)最优基最优基有最优解有最优解例例2-22-2：：对偶理论2-33450034 对偶对偶对偶对偶标准形标准形例例2-22-2：：对偶理论2-3 n基本思想基本思想n迭代原理迭代原理n举例求解举例求解n影子价格影子价格 第三节第三节 对偶单纯形法对偶单纯形法第二章第二章 对偶理论对偶理论 四四. .影子价格：影子价格：通常在实际问题中表示通常在实际问题中表示资源拥有量资源拥有量.表示单位资源的价格，称为表示单位资源的价格，称为影子价格影子价格。
设设B是是(P)的最优基的最优基则则 是是(P)的最优解，的最优解，是是(D)的最优解的最优解且且是最优值是最优值对偶理论2-3 例：例： 某工厂在计划期内要安排生产甲乙两种产品，它某工厂在计划期内要安排生产甲乙两种产品，它们需要在四种不同的设备上加工加工工时数、可们需要在四种不同的设备上加工加工工时数、可得利润、总工时数均列于下表得利润、总工时数均列于下表 利润利润 甲甲 2 1 4 0 20 乙乙 2 2 0 4 30总工时数总工时数12 8 16 12 问：问： 应如何安排生产才能获利最大？应如何安排生产才能获利最大？对偶理论2-3 例：例： 利润利润 甲甲 2 1 4 0 20 乙乙 2 2 0 4 3012 8 16 12 (影子价格影子价格)A, B, C, D的资源拥有量的资源拥有量A, B, C, D的单位资源的价格的单位资源的价格对偶理论2-3 例：例： 利润利润 甲甲 2 1 4 0 20 乙乙 2 2 0 4 3012 8 16 12 甲乙最优产量甲乙最优产量4种设备单位工时的最优定价种设备单位工时的最优定价自己生产的利润收入自己生产的利润收入对外出租的租金收入对外出租的租金收入(影子价格影子价格)A, B, C, D的资源拥有量的资源拥有量A, B, C, D的单位资源的价格的单位资源的价格最优解：最优解：总收入：总收入：对偶理论2-3 第第i 种资源种资源 的影子价格的影子价格越多越多越大越大影子价格的经济解释：影子价格的经济解释：资源拥有量资源拥有量单位资源的价格单位资源的价格(影子价格影子价格)越越设设 是是(P)的最优解，的最优解， 是是(D)的最优解的最优解.且且当当 增加一个单位时，收入增加一个单位时，收入S的增加量。
的增加量增加增加 一个单位时，一个单位时，S 不增加，则不增加，则不应增加该种资源不应增加该种资源增加增加 一个单位时，一个单位时，S 增加，则增加，则 应增加该种资源应增加该种资源可用来决定是否应增加第可用来决定是否应增加第i 种资源种资源对偶理论2-3 n基本思想基本思想n迭代原理迭代原理n举例求解举例求解n影子价格影子价格 第三节第三节 对偶单纯形法对偶单纯形法第二章第二章 对偶理论对偶理论作业：作业：P96 10 (1) (2) P96 10 (1) (2) 作业：作业：P84 2 (1) (2) P84 2 (1) (2) 。