课程名称：运筹学 专业：信息管理与信息系统 班级： 第2章线性规划的对偶理论 章节名称 第2章线性规划的对偶理论 理解对偶问题的基本概念： 课堂教学 2.掌握对偶单纯形法： 目的 3. 掌握线性规划的灵敏度分析： 4. 掌握线性规划在管理中的应用。 1.线性规划的对偶问题 教学内容及 2.对偶单纯形法 3.线性规划的灵敏度分析 学时分配 4.线性规划在管理中的应用 (共6学时) 重点、难点 重点：对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规 划在管理中的应用 以及对策 难点：对偶问题的基本概念和线性规划的灵敏度分析 教学方法和 教学方式：讲授+实验 手段 教学辅助手段：教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪 作业、思考题 P79课后习题2.1(a,c)、2.3、2.4、2.6(a)、2.8、2.9 课后记 对偶问题与原问题的相互关系，及模型中变量的含义的理解很重要
课程名称：运筹学 专业：信息管理与信息系统 班级： 19 第 2 章 线性规划的对偶理论 章节名称 第 2 章 线性规划的对偶理论 课堂教学 目的 1．理解对偶问题的基本概念； 2．掌握对偶单纯形法； 3．掌握线性规划的灵敏度分析； 4．掌握线性规划在管理中的应用。 教学内容及 学时分配 1．线性规划的对偶问题 2．对偶单纯形法 3．线性规划的灵敏度分析 4．线性规划在管理中的应用 （共 6 学时） 重点、难点 以及对策 重点：对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规 划在管理中的应用 难点：对偶问题的基本概念和线性规划的灵敏度分析 教学方法和 手段 教学方式：讲授+实验 教学辅助手段：教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪 作业、思考题 P79 课后习题 2.1(a,c)、2.3、2.4、2.6(a)、2.8、2.9 课后记 对偶问题与原问题的相互关系，及模型中变量的含义的理解很重要
课程名称：运筹学 专业：信息管理与信息系统 班级： 问题分析不是数字和字符的堆砌，他们包含许多意义。 第2章线性规划的对偶理论 §1对偶问题的提 可顾第 章例2， 反过来问：现假定有另一四海机器厂，为扩大生产想租借常山机 器厂拥有的3种设备资源，问常山厂分别以每小时什么样的价格才愿意出程自已的 设备？ 解：设A、B、C3种设备每小时出租的价格分别为y1、y2、y3,则新的线性规划 数学模型为： min=12y+16y,+15y [2+4+022 s1.{2%+0%+5y23 (,片≥0 与第一章例2的线性规划模型对比： 设X、2分别为1、两种产品的产量，则数学模型为： max =2x+3x [2x+2x2s12 r/4s16 5x,≤15 x.x.20 分析对偶问题 原问颗 max :=CX IAX≤b X≥0 它的对偶问题 min w=Yb IYA≥C 1Y20 注意：=(，2，.，m)是行向量。 原问题 对偶问恩题 (1)决策变量 X≥0(n个 Y≥0(m个) (2)目标函数 max ==CY min w=Yb (3)约束条件 AX≤b(m个) A≥C(n个) (4)系数矩哟 4 (5)右端向量 6 (6)价值向 d
课程名称：运筹学 专业：信息管理与信息系统 班级： 20 第 2 章 线性规划的对偶理论 §1 对偶问题的提出 回顾第一章例 2，反过来问：现假定有另一四海机器厂，为扩大生产想租借常山机 器厂拥有的 3 种设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的 设备？ 解：设 A、B、C 3 种设备每小时出租的价格分别为 y1、y2、y3，则新的线性规划 数学模型为： 1 2 3 1 2 3 1 2 3 1 2 3 min 12 16 15 2 4 0 2 . . 2 0 5 3 , , 0 y y y y y y s t y y y y y y = + + + + + + 与第一章例 2 的线性规划模型对比： 设 x1、x2 分别为 I、Ⅱ两种产品的产量，则数学模型为： 1 2 1 2 1 2 1 2 max 2 3 2 2 12 4 16 . . 5 15 , 0 x x x x x s t x x x = + + 分析对偶问题： 原问题 = 0 b max X AX z CX 它的对偶问题 = 0 min b Y YA C w Y 注意：Y=（y1，y2，.，ym）是行向量。 原问题 对偶问题 （1）决策变量 （2）目标函数 （3）约束条件 （4）系数矩阵 （5）右端向量 （6）价值向量 X≥0（n 个） max z=CX AX≤b（m 个） A b C Y≥0（m 个） min w=Yb YA≥C（n 个） A T C b 问题分析不是数字和字符的堆砌，他们包含许多意义
课程名称：运筹学 专业：信息管理与信息系统 班级： §2原问题与对偶问题 原问题（对偶问题）max 对偶间题（原间题）min 约束条件系数矩阵 约束条件系数矩阵的转置 标函数价值向品 约束条件右端常数向量 约束条件右端常数向量 目标函数价值向 ≥0 n个变量 ≤0 a,c m个技术约束 无约束 2,56 片≥0 J片≤0 m个变量 片无约束 课堂练习：写出下列线性规划问题的对偶问题 mAx Z=2x+3x2-5x,+ 4x1+x2-3x3+2x,25 3x1-2x +7x,≤4 -2x+3x2+4x3+x,=6 x≤0,2，x20,x无约束 小结： 学习要点： 1掌握原问题与其对偶问题的对应关系： 2.能熟练准确地写出一般形式的线性规划的对偶问题。 课后作业：(P79)2.1(a,b) §3对偶问题的基本性质 定理1对偶问题的对偶是与原问题。 定理2（弱对偶定理）设X=(x,x2,.,x)'与7=(0，y)分别是(2.9)与 (2.10)的可行解，则CX≤b
课程名称：运筹学 专业：信息管理与信息系统 班级： 21 §2 原问题与对偶问题 原问题（对偶问题）max 对偶问题（原问题）min A C b 约束条件系数矩阵 目标函数价值向量 约束条件右端常数向量 约束条件系数矩阵的转置 约束条件右端常数向量 目标函数价值向量 n 个变量 = = = = j m i ij i j m i ij i j m i ij i a y c a y c a y c 1 1 1 n 个技术约束 m 个技术约束 = = = = i n j ij j i n j ij j i n j ij j a x b a x b a x b 1 1 1 m 个变量 课堂练习：写出下列线性规划问题的对偶问题 − + + + = − + + − + = + − + 1 2 3 4无约束 1 2 3 4 1 2 4 1 2 3 4 1 2 3 4 0, , 0, 2 3 4 6 3 2 7 4 4 3 2 5 max 2 3 5 x x x x x x x x x x x x x x x Z x x x x 小结： 学习要点： 1.掌握原问题与其对偶问题的对应关系； 2.能熟练准确地写出一般形式的线性规划的对偶问题。 课后作业： （P79） 2.1（a , b） §3 对偶问题的基本性质 定理 1 对偶问题的对偶是与原问题。 定理 2（弱对偶定理） 设 T n X (x , x , , x ) = 1 2 与 ( , , , ) 1 2 m Y = y y y 分别是（2.9）与 （2.10）的可行解，则 CX Yb。 xj≥0 xj≤0 xj 无约束 yi≥0 yi≤0 yi 无约束
课程名称：运筹学 专业：信息管理与信息系统 班级： 定理3（最优性判定定理）设x,7分别为问题(2.3)与(2.4)的可行解，且CX= 则两者均为最优解。 定理4（强对偶定理）如果原问题有最优解，那么对偶问题也有最优解：设前者的 最优基为B,则对偶最优解为广=CB厂，且两者最优值相等。 定理5（互补松弛定理）设灭与7分别是问题(2.9)与(2.10)的可行解，那么 它们都是最优解的充要条件是 6-2a成=0，2.m (2.18) 且y-c,压=0，l,2,n (219) 条件(2.18)与(2.19)也可以写为： xy=0=l,2,.,m (220) ygx,=0户1,2，.，n (221) (性质5的应用) 例2.4已知线性规划 max =3x+4x2+ x+2x2+x3≤10 2x1+2x2+x≤16 x,20,j=1,2,3 的最优解是X*=6,2,0)T求其对偶问题的最优解Y*。 解：写出原问题的对偶问题，即 min w=10y +16y2 [1+2y2≥3 2y1+2y2≥4 乃+少2≥1 4,y2≥0 2
课程名称：运筹学 专业：信息管理与信息系统 班级： 22 定理 3（最优性判定定理）设 X ，Y 分别为问题（2.3）与（2.4）的可行解，且 CX = Yb， 则两者均为最优解。 定理 4（强对偶定理） 如果原问题有最优解，那么对偶问题也有最优解；设前者的 最优基为 B，则对偶最优解为 Y * =CBB －1，且两者最优值相等。 定理 5（互补松弛定理） 设 X 与 Y 分别是问题（2.9）与（2.10）的可行解，那么 它们都是最优解的充要条件是 ( ) 0 1 − = = i n j i ij j b a x y ， i=1，2，.，m （2.18） 且 ( ) 0 1 − = = j j m i ij i a y c x ， j=1，2，.，n （2.19） 条件（2.18）与（2.19）也可以写为： xsi yi = 0 i=1，2，.，m （2.20） ysj x j = 0 j=1，2，.，n （2.21） （性质 5 的应用） 例 2.4 已知线性规划 = + + + + = + + 0, 1,2,3 2 2 16 2 10 max 3 4 1 2 3 1 2 3 1 2 3 x j x x x x x x z x x x j 的最优解是 X＊=(6,2,0)T,求其对偶问题的最优解 Y＊。 解：写出原问题的对偶问题，即 + + + = + , 0 1 2 2 4 2 3 min 10 16 1 2 1 2 1 2 1 2 1 2 y y y y y y y y w y y
课程名称：运筹学 专业：信息管理与信息系统 班级： 解：因为X1≠0，X2≠0，所以对偶问题的第一、二个约束为严格等式，即： +2=3 2y+2=4 解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y*=(1,1),最优值w=26, 小结 学习要点： 深入理解、熟练掌握对偶问题的基本性质，并且会应用这些性质。 课后作业：(P79)2.3,2.4 §4影子价格 (1)影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。 即对偶变量yi就是第1种资源的影子价格。 在r,列 (2.26) 对b求偏导数，得到： de' (2.27) 即第i种资源影子价格是对资源数量b的变化率，是第i种资源增加一个单 位时，最大产值的改变量。 (2)影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市 场价格。因此，从另一个角度说，它是一种机会成本。 若第i种资源的单位市场价格为mi,则有当yi*>m时，企业愿意购进这种资源， 单位纯利为yi*一mi,则有利可图：如果yi*<mi,则企业有偿转让这种资源，可获 单位纯利mi一yi*,否则，企业无利可图，甚至亏损。 学习要点： ,明确影子价格的定义及意义： 2.能准确地在最优单纯形表的检验数中我出各种资琼的影子价格。 §5对偶单纯形法 对偶单纯形法的基本思路 由具体例是 引出 2、对偶单纯形法的计算步骤 对于标准形式的线性规划：
课程名称：运筹学 专业：信息管理与信息系统 班级： 23 解：因为 X1≠0，X2≠0，所以对偶问题的第一、二个约束为严格等式，即： + = + = 2 2 4 2 3 1 2 1 2 y y y y 解此线性方程组得 y1=1,y2=1,从而对偶问题的最优解为： Y＊=(1,1)，最优值 w=26。 小结 学习要点： 深入理解、熟练掌握对偶问题的基本性质，并且会应用这些性质。 课后作业： （P79） 2.3，2.4 §4 影子价格 （1）影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。 即对偶变量 yi 就是第 i 种资源的影子价格。 z * =w * = Y * b= = m i i i b y 1 * （2.26） 对 bi求偏导数，得到： * * i i y b z = （2.27） 即第 i 种资源影子价格 yi *是 z *对资源数量 bi的变化率，是第 i 种资源增加一个单 位时，最大产值的改变量。 （2）影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市 场价格。因此，从另一个角度说，它是一种机会成本。 若第 i 种资源的单位市场价格为 mi ，则有当 yi* > mi 时，企业愿意购进这种资源， 单位纯利为 yi*－mi ，则有利可图；如果 yi* < mi ，则企业有偿转让这种资源，可获 单位纯利 mi－yi * ，否则，企业无利可图，甚至亏损。 学习要点： 1.明确影子价格的定义及意义； 2.能准确地在最优单纯形表的检验数中找出各种资源的影子价格。 §5 对偶单纯形法 1、对偶单纯形法的基本思路 由具体例题引出。 2、对偶单纯形法的计算步骤 对于标准形式的线性规划：