《运筹学》课程授课教案（讲稿）第7讲 对偶问题的提出与对偶理论

第_7_讲次课程名称：《运筹学》对偶问题的提出与对偶理论授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，了解线性规划的对偶以及相关理论。[重点及难点】原问题和对偶问题的相互转化、对偶理论。内容[本讲课程的引入]我们已经学习了线性规划问题及求解，今天我们开始学习对偶问题，[本讲课程的内容]对偶问题的提出一、在第一章例1中讨论了工厂生产计划模型及其解法，现从另一角度来讨论这个问题。假设该工厂的决策者决定不生产产品I、IⅡI，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在作定价决策时，作如下比计较：若用一个单位设备台时和4个单位原材料A可以生产一件产品I，可获利2元，那生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润，这就有：yl+4y2≥2同理将生产每件产品IⅡ的设备台时和原材料出租和出让的所有收入应不低于生产一件产品Ⅱ的利润，这就有：2yl + 4y3 ≥ 3把工厂所有设备台时和原材料都出租和出让，其收入为：W=8y1 + 16y2 + 12y3从工厂的决策者来看当然W越大越好，但从接受者来看他支付的越少越好，所以工厂的决策者只能在满足不小于所有产品利润的条件下，使其总收入尽可能地小，他才能实现其愿望，为此需解如下的线性规划问题：

课程名称：《运筹学》 第 7 讲次 授课题目 对偶问题的提出与对偶理论 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，了解线性规划的对偶以及相关理论。 [重点及难点] 原问题和对偶问题的相互转化、对偶理论。 内 容 [本讲课程的引入] 我们已经学习了线性规划问题及求解，今天我们开始学习对偶问题。 [本讲课程的内容] 一、 对偶问题的提出 在第一章例 1 中讨论了工厂生产计划模型及其解法，现从另一角度来讨论这个问题。假设该 工厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。这时工厂的决策者就要考虑 给每种资源如何定价的问题。设用 y1，y2，y3 分别表示出租单位设备台时的租金和出让单位原 材料 A，B 的附加额。他在作定价决策时，作如下比计较：若用一个单位设备台时和 4 个单位原 材料 A 可以生产一件产品Ⅰ，可获利 2 元，那生产每件产品Ⅰ的设备台时和原材料出租和出让 的所有收入应不低于生产一件产品Ⅰ的利润，这就有： y1 ＋ 4y2 ≥ 2 同理将生产每件产品Ⅱ的设备台时和原材料出租和出让的所有收入应不低于生产一件产品Ⅱ的 利润，这就有： 2y1 ＋ 4y3 ≥ 3 把工厂所有设备台时和原材料都出租和出让，其收入为： w = 8y1 ＋ 16y2 ＋ 12y3 从工厂的决策者来看当然 w 越大越好，但从接受者来看他支付的越少越好，所以工厂的决策者 只能在满足不小于所有产品利润的条件下，使其总收入尽可能地小，他才能实现其愿望，为此需解如 下的线性规划问题：

内容min w=8y1 + 16y2 + 12y3≥2y1 + 4y22yl +4y3 ≥3yi≥0，i=1,2,3称这个线性规划问题为例1线性规划问题（这里称原问题）的对偶问题。对偶问题的矩阵描述：已知当检验数(2.10)CN-CBBI-1≤0(2.11)-CBB -1:0这表示线性规划问题已得到最优解。1、（2.10），（2.11）中都有乘子CBB，称它-1单纯形乘子，用Y表示。由（2.10）可得：Y≥02、包括基变量在内的所有检验数可用C一CBBA≤0表示。H1此得,C一CBBA=C-YA≤O,即：YA≥C3、由Y=CBB，-1边右乘b，得到：因Y的上界为无限大，所以只存在最小值。由此可以得到另一个线性规划问题：min w= YbYA ≥ CY≥0称它为原线性规划问题（maxz=CX|AX≤b，X≥0)的对偶规划问题。二、线性规划的对偶理论（一）原问题与对偶问题的关系综合各种情况，线性规划的原问题与对偶问题的关系及其变换形式归纳为表2-2：

内 容 min w = 8y1 ＋ 16y2 ＋ 12y3 y1 ＋ 4y2 ≥ 2 2y1 ＋ 4y3 ≥ 3 yi ≥ 0 ，i = 1，2，3 称这个线性规划问题为例 1 线性规划问题（这里称原问题）的对偶问题。 对偶问题的矩阵描述： 已知当检验数 CN － CBB N ≤ 0 （2.10） －CBB ≤ 0 （2.11） 这表示线性规划问题已得到最优解。 1、（2.10），（2.11）中都有乘子 CBB ，称它为单纯形乘子，用 Y 表示。由（2.10） 可得： Y ≥ 0 2、包括基变量在内的所有检验数可用C － CBB A ≤ 0表示。由此得，C － CBB-1 A = C － YA ≤ 0 ，即： YA ≥ C 3、由 Y = CBB ，两边右乘 b ，得到： 因 Y 的上界为无限大，所以只存在最小值。 由此可以得到另一个线性规划问题： min w = Yb YA ≥ C Y ≥ 0 称它为原线性规划问题｛max z = CX | AX ≤ b ，X ≥ 0｝的对偶规划问题。 二、线性规划的对偶理论 （一） 原问题与对偶问题的关系 综合各种情况，线性规划的原问题与对偶问题的关系及其变换形式归纳为表 2-2： -1 -1 -1 -1 -1

内容原问题（或对偶问题）对偶问题（或原问题）目标函数minw目标函数maxz约n个n个变≥束≥0≤条量≤0=件无约束约m个m个≤束≥0变条≥量≤0件=无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项（二）对偶问题的基本性质1、对称性对偶问题的对偶是原问题。2、弱对偶性若X是原问题的可行解，Y是对偶问题的可行解。则存在CX≤Yb。3、无界性若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4、可行解是最优解时的性质设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时，X*，Y*是最优解。5、对偶定理若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。6、互补松驰性若X*，Y*分别是原问题和对偶问题的可行解，那么Y*XS=0和YSX*=0，当且仅当X*，Y*为最优解。7、设原问题是maxz=CX；AX十XS=b；X，XS≥0。它的对偶问题是minW=Yb；YA一YS=C：Y，YS≥0。则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如表2-3：

内 容 原问题（或对偶问题） 对偶问题（或原问题） 目标函数 max z 目标函数 min w n 个 n 个 约 变 ≥ 0 ≥ 束 量 ≤ 0 ≤ 条 无约束 ＝ 件 约 m 个 m 个 束 ≤ ≥ 0 变 条 ≥ ≤ 0 量 件 ＝ 无约束 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 （二） 对偶问题的基本性质 1、对称性 对偶问题的对偶是原问题 。 2、弱对偶性 若 X 是原问题的可行解，Y 是对偶问题的可行解。则存在 CX≤Yb。 3、无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 4、可行解是最优解时的性质 设 X*是原问题的可行解，Y*是对偶问题的可行解，当 C X*= Y*b 时，X*，Y*是最优解。 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。 6、互补松弛性 若 X*，Y*分别是原问题和对偶问题的可行解，那么 Y*XS = 0 和 YSX* = 0，当且仅当 X*，Y*为最优解。 7、设原问题是 max z = CX ；AX ＋ XS ＝ b ；X ，XS ≥ 0。它的对偶问题是 min w = Yb；YA － YS = C；Y，YS ≥ 0。则原问题单纯形表的检验数行对应其对偶问题的 一个基解，其对应关系如表 2-3：

内容XNXBXS0CN - CBB -1J-CBB -1YS1-YS2-y这里YS1是对应原问题中基变量XB的约束的剩余变量，YS2是对应原问题中非基变量XN的约束的剩余变量。【本讲小结】通过今天的学习我们了解了原问题和对偶问题的相互转化以及对偶理论，希望大家进一步掌握。[本讲课程的作业]74页2.1

内 容 XB XN XS 0 CN － CBB N －CBB YS1 －YS2 －Y 这里 YS1 是对应原问题中基变量 XB 的约束的剩余变量，YS2 是对应原问题中非基变 量 XN 的约束的剩余变量。 [本讲小结] 通过今天的学习我们了解了原问题和对偶问题的相互转化以及对偶理论，希望大家进 一步掌握。 [本讲课程的作业] 74 页 2.1 -1 -1