线性规划的对偶问题.ppt

1 线性规划的对偶问题的例子 某工厂生产A B两种产品 已知制造A产品每件需劳动力7人 原料5公斤 电力2度 制造B产品每件需劳动力5人 原料8公斤 电力5度 工厂可使用的劳动力最多为3500人 原料最多为4000公斤 电力最多为2000度 A产品每件利润6元 B产品每件利润7元 问如何安排生产 才使工厂的利润最大 2 线性规划的对偶问题的例子 设x1 x2分别是A B产品的生产量 则 劳动力约束 原料约束 电力约束 问题 某公司欲购买该工厂的三种资源 劳动力 原料 电力 确定这三种资源的价格 使工厂愿意出售同时又使公司化费最小 3 线性规划的对偶问题 设购买该厂的资源 劳动力 原料 电力 的单位价格分别为y1 y2 y3 则有 生产1个单位的A产品的资源出售给公司应大于其利润 生产1个单位的B产品的资源出售给公司应大于其利润 4 线性规划的对偶问题 两个问题的线性规划如下 两个线性规划之间的关系 5 线性规划的对偶问题 饲养场的混合饲料由两种配料组成 混合饲料必须含有维生素B和维生素C 并且维生素B和C的含量分别不低于5和6 现已知第一种配料中每单位维生素B含量为3 维生素C含量为3 单价为13 第二种配料中每单位维生素B含量为1 维生素C含量为4 单价为10 问在保证营养的条件下 应如何配方 使混合饲料的费用最小 6 线性规划的对偶问题 设第一种配料用x1单位 第二种配料用x2单位 第一个约束为维生素B的含量 第二个约束为维生素C的含量 7 线性规划的对偶问题 现有某个制药厂要推销维生素B和维生素C药剂 厂商希望饲养场能够用维生素B和维生素C药剂来配制混合饲料 为做到这一点 必须保证维生素B和维生素C的价格不超过上述两种配料 在这种条件下 应如何确定维生素B和C药剂的价格 使制药厂的收益最大 8 线性规划的对偶问题 设y1 y2分别是维生素B和C药剂的单价 在具有第一种配料的营养条件下 药剂的价格不超过第一种配料 在具有第二种配料的营养条件下 药剂的价格不超过第二种配料 9 两个线性规划的特点 约束条件的右端是另一个规划的目标函数的系数约束条件的系数矩阵的转置是另一个规划的约束条件的系数矩阵 这两个线性规划具有对称性 10 线性规划的对偶问题 称 LP 和 LD 是一对相互对偶的线性规划问题 目标函数求最小 约束条件写成大于等于 目标函数求最大 约束条件写成小于等于 11 标准形式的对偶 12 标准形式的对偶 13 两种形式的对偶 对称形式 标准形式 14 标准形式的对偶问题例子 则它的对偶问题为 15 对偶性与最优性 研究一对相互对偶的线性规划问题它们最优解之间的关系 先考虑对称形式的对偶问题 再考虑标准形式的对偶问题 16 弱对偶性 弱对偶性 17 最优性 若X Y 分别是 LP 和 LD 的可行解 且CTX bTY 则X Y 分别是 LP 和 LD 的最优解 证 对 LP 的任一可行解X bTY CTX bTY CTX 这说明CTX 是bTY的一个下界 当bTY CTX 时 目标函数CTX达到最大值 18 无界性 若 LP 的目标函数 求Max 在可行域内无上界 则对偶问题 LD 是不可行的 若对偶问题 LD 的目标函数 求Min 在可行域内无下界 则原问题 LP 是不可行的 反证法 若 LD 是可行的 即存在可行解Y 由弱对偶性 CTX bTY此即说明 LP 的目标函数有上界 19 无界性 该定理的逆定理不成立 有可能 LP 和 LD 都是不可行的 LP 无界 LD 不可行 20 LP 和 LD 都是不可行的 无界性的逆定理不成立 21 互补松弛性质 22 互补松弛性质 若 LP 有最优解X 则 LD 也有最优解Y 且有X TV 0 Y TU 0其中V ATY C U b AX 証 若y Y 分别是 LP 和 LD 的最优解 则CTX bTY 23 将它们化成标准形式 并求出最优解 24 25 LD 的剩余变量 LP 的松弛变量 它们的最优解满足互补松弛性质 26 对偶问题最优解的性质 对称形式 若 LP 有最优解X 则对偶问题 LD 也有最优解Y 且y 是 LP 最优单纯形表中松弛变量V下的检验数的负值 X 是 LD 最优单纯形表中剩余变量U下的检验数的负值 27 用对偶单纯形法求解 LD 列出初始单纯形表如下 28 最优解 剩余变量y3 y4下的检验数 24 8 最优单纯形表 可求得最优解如下 对偶问题的最优解 y1 24 y2 8 29 对偶问题 LP 的初始单纯形表如下 30 最优解 松弛变量的检验数 2 2 31 标准形式的对偶问题最优解的性质 若标准形式 LP 有基本最优解y 且 则 LD 的最优解为 标准形式的对偶问题 LP 中基本最优解y 的检验数 32 标准形式的对偶问题最优解的性质 基本解y 的检验数 CT CBTB 1A 0 ATy AT CBTB 1 T C y 是对偶问题的可行解 对偶问题 LD 的目标函数值 原问题 LP 的目标函数值 f z 两目标函数值相等 33 34 35 恰好是单纯形表中x4 x5 x6下的检验数的负值 36 单纯形法的求解 LP 问题 若x满足条件 1 xB B 1b 0 xN 0 2 CT CBTB 1A 0 则x是 LP 的最优解 单纯形法是在满足第1个条件下 通过运算逐步使第二个条件满足 37 对偶单纯形法的求解 对偶单纯形法是在满足第2个条件下CT CBTB 1A 0 通过运算逐步使第1个条件满足 即在单纯形表中要求检验数行小于零 而初始基本解不一定可行 38 原问题与对偶问题之间的形式 原问题 LP 的目标函数求May 则对偶问题 LD 的目标函数求Min 原问题 LP 的主约束条件有m个 则对偶问题 LD 的对偶变量有m个 原问题 LP 的变量有n个 则对偶问题 LD 的主约束条件有n个 原问题 LP 的第i个约束条件为 型 则对偶问题 LD 的第i个变量yi 0 39 原问题与对偶问题之间的关系 原问题 LP 的第i约束条件为 型 则对偶问题 LD 的第i个变量yi 0 原问题 LP 的第i约束条件为 型 则对偶问题 LD 的第i个变量yi无非负限制 原问题 LP 的第i个变量yi为 0 则对偶问题 LD 的第i个约束条件为 型 原问题 LP 的第i个变量yi为 0 则对偶问题 LD 的第i个约束条件为 型 原问题 LP 的第i个变量yi无非负限制 则对偶问题 LD 的第i个约束条件为 型 40 原问题与对偶问题之间的关系 原问题 LP 的目标函数求May 主约束条件为 型 则称此约束为规范约束 否则称为非规范约束 同样对偶问题 LD 的目标函数求Min 主约束条件为 型 则称此约束为规范约束 否则称为非规范约束 LP 的每一个约束对应于 LD 的每一个变量 LP 的每一个变量对应于 LD 的每一个约束 41 写出下列线性规划的对偶问题 对偶问题应有3个变量 4个约束 对偶问题的目标函数 第一个约束对应于第一个变量 y1 2y2 2 42 写出下列线性规划的对偶问题 第二个约束对应第二个变量 y1 y3 3它应是规范约束 第三个约束对应第三个变量 y1 y2 y3 5它是规范约束 第四个约束对应第四个变量 y1 y3 0它是等式约束 对偶问题的第一个变量 0 第二个变量 0 第三个变量无非负限制 43 44 45 用对偶单纯形法求解 46 第三行1200 150 3 6003 150 第二行0 110130 第一行0 6103 120 检验数010003 150 47 第一行01 1 60 1 220 011 11 60 11 2220 第二行00 11 61 5 2220 0 21 301 40 第三行101 30010 0 105 305 200 检验数005 308 350 48 最优解 x1 10 x2 20 MinS 350 对偶问题的最优解 49 对偶问题 按对称形式 50 对偶问题 按一般形式 51 对偶问题解的意义 某工厂生产A B两种产品 已知制造A产品每件需劳动力7人 原料5公斤 电力2度 制造B产品每件需劳动力5人 原料8公斤 电力5度 工厂可使用的劳动力最多为3500人 原料最多为4000公斤 电力最多为2000度 A产品每件利润6元 B产品每件利润7元 问如何安排生产 才使工厂的利润最大 可列出如下的线性规划模型 52 对偶问题解的意义 设y1 y2分别是A B产品的生产量 则 可求得最优解 53 对偶问题解的意义 最优单纯形表如下 最优基底B P1 P4 P2 B 1 工厂的劳动力增加一个单位 工厂可增加多少利润 54 对偶问题解的意义 设工厂的劳动力从3500增加到3500 b1 在基底B下 基本解为B 1 b b 此时 目标函数值为 55 对偶问题解的意义 劳动力每增加一个单位 工厂可增加利润 16 25 同理可算得电力每增加一个单位 工厂可增加利润 19 25 原料增加下一个单位 工厂可增加多少利润 利润增加为0 56 对偶问题解的意义 原料的增加 工厂的利润不能增加 为什么 原料约束 5y1 8y2 4000 在最优解 y1 300 y2 280时 5 300 8 280 3740 4000 对偶变量的解称为原问题中资源的影子价格 第二个松弛变量大于0 第二个对偶变量y2 0满足互补松弛性质 劳动力 原料 电力增加下一个单位时 利润可增加为16 25 0 19 25它恰是对偶问题的解 57 对偶问题解的意义 原问题中劳动力的影子价格是16 25 原问题中原料的影子价格是0 原问题中电力的影子价格是19 25 上述三个数据恰是对偶问题的解 影子价格的意义是资源每增加一个单位 利润可增加的数量 58 某房产公司有水泥120单位 木材160单位和玻璃400单位 用以建造A型和B型住宅 建一栋A型住宅需用水泥 木材 玻璃分别为1 2 2个单位 售价每栋100万元 建一栋B型住宅需用水泥 木材 玻璃分别为1 2 5个单位 售价每栋150万元 公司如何安排这两种住宅的建设 可使销售收入最大 设A B型住宅各建x1 x2栋 则销售收入为 100 x1 150 x2 水泥约束 x1 x2 120 木材约束 x1 x2 160 玻璃约束 x1 5x2 400 59 60 61 最优解 A型住宅建50栋 B型住宅建60栋 最大收入14000 木材增加一个单位 销售收入可增加多少 水泥增加一个单位 销售收入可增加多少 62 最优基底B P3 P2 P1 设木材增加为