第二章线性规划的对偶理论

第二章 线性规划的对偶理论北京物资学院 李珍萍2013年 3月北京物资学院运筹学教学课件本章主要内容第一节、 原问题与对偶问题第二节、 对偶问题的基本性质第三节、 影子价格第四节、 对偶单纯形方法第五节、 灵敏度分析第六节、 线性规划的求解软件第一节、原问题和对偶问题一、引例二、对称形式的对偶规划三、非对称形式的对偶规划四、一般形式的对偶规划一、引例A B C D原料 拥 有量（单 位）含量（ 单 位 /公斤）糖 5 2 4 2 60蛋白 质 3 2 1 4 40脂肪 3 1 2 5 35单 价（元 /公斤）15 7 9 12建立其数学模型。例 1 甲食品厂用糖、蛋白质和脂肪三种原料生产四种复合食品 A、 B、 C、 D， 复合食品中含有各种原料的数量、复合食品的单价、三种原料的拥有量分别如下表所示，问甲厂如何安排生产才能使总产值达到最大？x1 x2 x3 x4解：设甲厂安排 A、 B、 C、 D的产量分别为 x1、 x2、 x3、 x4 公斤，总产值为 z 元。于是，例 1的数学模型为：例 2. 假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少应付出多少代价，才能使甲厂放弃生产活动，出让原料？建立该问题的数学模型 。A B C D原料 拥 有量（ 单 位）含量（ 单 位 /公斤）糖 5 2 4 2 60蛋白 质 3 2 1 4 40脂肪 3 1 2 5 35单 价（元 /公斤）15 7 9 12y1y2y3解：设 y1,y2和 y3（ 元 /单位）分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为 w元，于是例 2的数学模型为：例 1和例 2的数学模型比较令以上两个线性规划分别称为线性规划的原问题和对偶问题。若两个线性规划分别是和则称它们是一对对称形式的对偶规划。二、对称形式的对偶规划对称形式的对偶规划还可以写成表格形式，称为对偶表Max zMin w原问题（求极大）c1 x1c2x2cnxn右端项对偶问题求极小b1 y1 a11 a12 a1n b1b2 y2 a21 a22 a2n b2 bm ym am1 am2 amn bm右端项 c1 c2 cn对偶规划中的两个问题分别称为原问题和对偶问题（互为对偶）。一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求 “极大 ”，约束为 “小于等于 ”型不等式，则它的对偶模型为目标求 “极小 ”，约束是 “大于等于 ”型不等式。即 “max， ”和 “min， ”相对应。(2) 一个模型是 m个约束， n个变量，则它的对偶模型为 n个约束， m个变量。 从约束系数矩阵看：一个模型中为 ，则另一个模型中为 AT。(3)原问题目标函数系数是对偶问题的约束条件右端项；原问题的约束条件右端项是对偶问题的目标函数系数。(4)两个规划模型中的变量皆非负。例 3：写出下列线性规划的对偶规划解：原规划的对偶规划为y1y2不等式约束对应非负变量三、非对称形式的对偶规划叫做非对称形式的对偶规划。非对称形式的对偶规划可以由对称形式的对偶规划推出。例 4：写出下列线性规划问题的对偶规划。解：将上述线性规划化成对称对偶规划的形式写出它的对偶规划y1y1y2y2等式约束对应自由变量(D)四、一般形式的对偶规划(P)一般形式的对偶规划的特点（ 1）原问题是 “ max， =,” 形式，对偶问题是 “ min，=,” 形式 （ 2）原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个不等式约束，对应对偶问题的一个非负变量；反之亦然，即原问题中的每个非负变量对应的是对偶问题中的一个不等式约束，而原始问题中的每个自由变量对应对偶问题中的一个等式约束。（ 3）原问题目标函数中的系数 c就是对偶问题约束条件的右端常数项，而原问题约束的右端常数项就是对偶问题目标函数中的系数。（ 4）如果用矩阵和向量形式写出问题 (P)和 (D)的约束，可以看出这两个问题的约束系数矩阵互为转置。例 5. 写出下面线性规划的对偶规划解 先将约束条件变形为 “” 形式y1y2y3y4y5再根据非对称形式的对应关系，直接写出对偶规划例写出下列线性规划问题的对偶规划解：令 x1= x1 ，将约束化成相对规范形式y1y2y3直接写出对偶规划比较原规划和对偶规划令 y1=y1, 并把第一个约束两端乘以 -1得不符合要求的约束对应非正变量线性规划原问题与对偶问题的对应关系原问题（对偶问题） 对偶问题（原问题）目标函数 max 目标函数 min n个变量 0 0无限制n个 约束条件=目标函数中变量的系数 约束条件右端常数m个约束条件 =m个 0 变量 0无限制约束条件右端常数 目标函数中变量的系数作业： P881 、 (1) (2)(3)第二节、对偶问题的基本性质（对偶定理）原问题与对偶问题的解之间的关系定理 1(对称性 ) 对偶问题的对偶是原问题 。定理 3 （强对偶定理） 若原问题有最优解，则其对偶问题也一定有最优解，并且此时目标函数的最优值相等。定理 2(弱对偶定理 ) 设 X0和 Y0分别是原问题和对偶问题的可行解，则 CX0Y0b； 特别当 CX0=Y0b 时， X0和 Y0 分别是原问题和对偶问题的最优解。证明：将原问题加上松弛变量化成标准形式：用单纯形方法求解得最优解 X， 设其最优基为 B， 则 XB=B-1b,检验数为令 则 Y是对偶问题的可行解又因为由定理 2知 Y是对偶问题的最优解。即即原问题和对偶问题的解的情况如下对偶原始有最优解 问题无界 无可行解有最优解 问题无界 无可行解 定理 4 给定一个线性规划的原问题和它的对偶问题 ，则上表中的三种情况恰有一种出现。证明：由 定理 2容易 证明，如果原问题或它的对偶中有一个是无界的，那么另一个不可能有可行解。（用反正法）下面举例说明剩下的情况（ 2）和（ 3）是可能出现的。考虑下列对偶规划显然两个问题均无可行解，情况（ 2）出现。原问题无可行解，对偶问题无界，情况（ 3）出现。考虑下列对