复件 31LP对偶理论.ppt

1 3 1LP的对偶问题 一 引入对偶问题 求 利润最大的生产方案 2 设X1 X2为产品1 2的产量 3 设y1 y2 y3 y4分别为A B C D设备的单价 minW 12y1 8y2 16y3 12y4 4 minW 12y1 8y2 16y3 12y4 y1 y4 影子价格 5 对称型 二 对偶问题的定义 6 三 对偶问题的性质 1 对偶问题的对偶问题是原问题 7 例1 写出下面问题的对偶规划 8 解 9 对偶问题 令y1 y1 y1 10 3 原问题第k个约束为等式 对偶问题第k个变量是自由变量 原问题第k个变量是自由变量 则对偶问题第k个约束为等式约束 11 对偶关系对应表 12 例2 写对偶规划 minZ 4X1 2X2 3X3 X1 2X2 62X1 3X3 9X1 5X2 2X3 4X2 X3 0 13 maxW 6y1 9y2 4y3 y1 2y2 y3 42y1 5y3 23y2 2y3 3y1 0 y2 0 y3自由 14 minZ 4X1 2X2 3X3 X1 2X2 62X1 3X3 9X1 5X2 2X3 4X2 X3 0 或将原问题变形为 15 maxW 6y1 9y2 4y3 y1 2y2 y3 4 2y1 5y3 23y2 2y3 3y1 y2 0 y3自由 对偶规划 16 产品A B产量X1 X2 Z为利润 例1 17 X 8 24 TZ 184 18 19 y 2 9 13 9 Z 184 20 观察结论 一对对偶问题都有最优解 且目标函数值相等 最优表中有两个问题的最优解 21 3 2LP的对偶理论 22 定理1 弱对偶定理 所以 CX X 23 推论2 P 有可行解 但无有限最优解 则 D 无可行解 推论1 P D 都有可行解 则必都有最优解 24 有C CBB 1A 0 CBB 1 0 即 所以是 D 的可行解 25 所以是 D 的最优解 26 27 定理4 松紧定理 互补松弛性 原问题 28 对偶问题 29 30 31 32 33 例 min 5y1 y2 34 P 最优解 0 9 0 4 64 9 35 36 37 解 D 为 38 将y1 y2 代入 知 为严格不等式 x2 x3 x4 0 x 1 0 0 0 1 TZ 5 39 3 3对偶解的经济解释 1 Z CBB 1b CN CBB 1N XN Z Z b b为资源 对偶解y b的单位改变量所引起的目标函数改变量 一 对偶解的经济解释 40 2 经济解释 bi 第i种资源的数量yi 对偶解bi增加 bi 其它资源数量不变时 目标函数的增量 yi 反映bi的边际效益 边际成本 例1中y1 2 9 当机器台时数增加1个单位时 工厂可增加利润2 9个单位 41 二 应用 松紧关系Y AX b 0也可以表示为 和 则 例中 y1 2 9 y2 13 9 42 3 4对偶单纯形法 一 思路 max型 单纯形法 找基B 满足B 1b 0 但C CBB 1A不全 0 即检验数 43 对偶单纯形法 找基B 满足C CBB 1A 0 但B 1b不全 0 44 例1 45 46 47 二 对偶单纯形法基本步骤max型 min型 1 作初始表 要求全部 j 0 0 48 3 确定换入变量 若Xil行的alj全 0 停 原问题无可行解 4 以alk为主元 换基迭代 49 关于 的解释