第三章对偶规划和灵敏度分析.docVIP

第三章对偶规划和灵敏度分析 教学目的和要求： 目的：使学生了解对偶规划的基本知识及具有进行简单的灵敏度分析的能力。 要求：理解对偶规划的概念，掌握对偶规则，了解对偶原理，掌握对偶单纯形法，理解影子价格概念，掌握灵敏度分析的方法以及参数规划的方法。 重点：对偶规划，对偶单纯形法，灵敏度分析法。 难点：对偶原理，灵敏度分析法。 教学方法：讲授法，习题法。 学时分配：8学时 作业安排：见教材P71. 第一节对偶规划和对偶原理 每一种形式的线性规划，都有称作为它的对偶规划的线性规划与之对应，这两个规划在形式结构上，求解，实际经济意义等方面有密切的关联，因此有必要对两个互为对偶的线性规划进行比较研究。 一、线性规划的对偶规划 1.对偶规划问题的提出：例1.对外加工定价问题 某工厂利用甲、乙、丙、丁四种设备生产A、B、C三种产品，具体数据如下表所示。 A、B、C单位产品的利润分别是4.5、5、7(百元)。如果工厂用甲、乙、丙、丁四种设备承担对外加工业务，工厂收取加工费，那么每种设备的每工时应如何定价才是合适的？这一问题与第二章第一节例1 (生产计划问题)是对应的。 产品 设备 A B C 设备可供工时(h) 甲 2 2 4 800 乙 1 2 3 650 丙 4 2 3 850 丁 2 4 2 700 单位利润 4.5 5 7 ---- 解：设yi(i=1,2,3,4)分别表示设备甲、乙、丙、丁单位工时对外加工定价(单位为百元),显然将原生产1件产品A的工时用于对外加工，所收取的加工费，不应低于生产1件产品A所获利润，即2y1+y2+4y3+2y4≥4.5,同理有2y1+2y2+2y3+4y4≥5, 4y1+3y2+3y3+2y4≥7;总的收费为W=800y1+650y2+850y3+700y4 ，考虑到市场竞争，加工费应尽量定得低，但不减少总收入(与生产计划问题相比)，故W取最小值。 以上对外加工定价问题可用数学模型表述如下： Min W=800y1+650y2+850y3+700y4 满足 2y1+y2+4y3+2y4≥4.5 2y1+2y2+2y3+4y4≥5 4y1+3y2+3y3+2y4≥7 yi≥0(i=1,2,3,4) 这个线性规划称为生产计划问题线性规划的对偶规划,它们互为对偶规划。 Max Z=4.5X1+5X2+7X3 满足 2X1+2X2+4X3≦800 X1+2X2+3X3≦650 4X1+2X2+3X3≦850 2X1+4X2+2X3≦700 Xj≧0 (j=1,2,3) 2.对偶规划的一般定义(一)对称形式的对偶规划 设原线性规划问题是Max Z=CX 满足AX≤b X≥0…(3-3)，则定义其对偶规划为Min W=Yb 满足YA≥C Y≥0…(3-4)或写成MinW=bTYT 满足ATYT≥CT YT≥0，Y=(Y1……Ym) X=(X1……Xn)T b=(b1……bm)T C=(C1……Cn)以上两个线性规划的对偶关系称为对称型的对偶关系，它们互为对偶规划，本章称求极大化为原规划。 例2.求线性规划Max Z=2X1+3X2 满足 X1+2X2≦9 2X1+X2≦10 4X1 ≦16 4X2≦12 Xj≧0 (j=1,2)的对偶规划 解:对偶规划为MinW=9y1+10y2+16y3+12y4 满足 y1+2y2+4y3 ≥2 2y1+y2 +4y4≥3 yi≥0(i=1,2,3,4) (二)非对称形式的对偶规划 若原规划是求目标函数极大化，但约束条件中出现“=”或“≧”约束条件，决策变量中出现无非负要求或非正要求(≦0)的决策变量，则其对偶规划称为非对称形式的对偶规划。在这种情况下，先把原规划化成对称的形式，再按对称形式的对偶关系写出其对偶规划，再整理便得非对称形式的对偶规划。 1)若原规划第k个约束条件是等式即ak1X1+ ak2X2+…+aknXn=bk 则可化为 ak1X1+ ak2X2+…+aknXn ≦ bk 即 ak1X1+ ak2X2+…+aknXn ≦ bk ak1X1+ ak2X2+…+aknXn ≧ bk -ak1X1- ak2X2-…-aknXn ≦- bk 故原规划变为极大化Z=C1X1+C2X2+…+CnXn 满足 ai1X1+ ai2X2+…+ainXn ≦ bi i=1,2, …,k-1 ak1X1+ ak2X2+…+akn