运筹学概论 第2章 线性规划的对偶理论.pptVIP

●任何线性规划问题都有其对偶问题 ●对偶问题有其明显的经济含义 * 第二章 线性规划的对偶理论 线性规划的对偶问题 对偶问题的基本性质 影子价格 第一节 线性规划的对偶问题 窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象 例1 美佳公司计划制造甲、乙两种家电产品，已知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时； A设备每天可用15小时， B设备可用24小时，调试工序每天可用5小时。已知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？ 例2 假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。 对偶问题 原问题 一、对偶问题的提出 二、对称形式下对偶问题的一般形式 用矩阵形式表示： 例 3 假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？ ●设A、B资源的出售价格分别为 y1 和 y2 ●显然商人希望总的收购价越小越好(目标) ●工厂希望出售资源后所得不应比生产产品所得少（约束） Y ?0 X ?0 决策变量 A’Y?C’ AX?b 约束条件 Min w=Y’b Max z=CX 目标函数 约束条件的右端项向量 目标函数中的价值系数向量 C 目标函数中的价值系数向量 约束条件的右端项 b 其约束系数矩阵的转置 约束系数矩阵 A 对偶问题 原问题 对偶问题的对偶即原问题。同样，可以将对偶问题当作原问题，写出其对偶问题。 课堂练习： 三、非对称形式的原-对偶问题关系 转换为对偶问题的思路是：先将其转化成对称形式，再按对应关系来写。因例中目标函数为max，故约束条件应换为“?”号，所有的变量均应“?0”， -3x1+x2-6x3?-1 x1+x2+x3?4 -x1-x2-x3?-4 x2’=-x2；x3=x3’-x3’’ y2=-y2’；y3=y3’-y3’’；（3）式 两端乘“-1”，（4）、（5）合并。 解：设对偶变量为y1,y2,y3,对偶问题模型为： Max w=5y1+4y2+6y3 y1 +2y2 y1 + y3 -3y1 +2y2 +y3 y1 - y2 +y3 ≥2 ≤3 ≤-5 =1 y1≥0, y2≤0, y3无约束 ≤ 2 ≥ 课堂练习： 第二章 线性规划的对偶理论 线性规划的对偶问题 对偶问题的基本性质 影子价格 第二节 对偶问题的基本性质 为了便于讨论，下面不妨总是假设： 原线性规划问题的矩阵表达式加上松弛变量后为： 一、单纯形法的矩阵描述 上式中Xs为松弛变量， ，I为m×m单位矩阵。 0 ? 0 0 cn ? c2 c1 cj-zj 1 ? 0 0 amn ? am2 am1 bm xn+m 0 ? ? ? ? ? ? ? ? ? ? ? 0 ? 1 0 a2n ? a22 a21 b2 xn+2 0 0 ? 0 1 a1n ? a12 a11 b1 xn+1 0 xn+m ? xn+2 xn+1 xn ? x2 x1 b XB CB 0 ? 0 0 cn ? c2 c1 Cj? 0 CB CN Cj-zj I B N 0 XS b XS XB XN 基变量 非基变量 单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出，而A中去掉若干列后剩下的列组成矩阵N，这样初始单纯形表可列成如下形式。 0 CB CN Cj-zj I B N 0 XS b XS XB XN 基变量 非基变量 当迭代若干步后，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换，对应XS的系数矩阵在新表中应为B-1。故当基变量为XB时，新的单纯形表具有如下形式。 CN -CB B-1 N -CB B-1 0 Cj-zj B-1 N B-1 I CB XB B-1 b XN XS XB 非基变量 基变量 当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有： （1）对应初始单纯形