运筹学课件 第二章-对偶问题.ppt

2 3对偶问题与灵敏度分析 2 3 1线性规划的对偶问题2 3 2灵敏度分析 回顾煤电油例 某厂生产两种产品 产品甲 产品乙 需要三种资源 煤 电 油 甲乙资源限量煤 t 94360电 kw h 45200油 t 310300单位价格 万元 712 2 3 1线性规划的对偶问题 一 LP的对偶问题及其模型 1 对偶问题 问如何决定生产方案 使总收入最大 生产模型 P 现有另一厂商 提出购买全部资源煤 电 油 设煤 电 油的购买单价分别为y1 y2 y3 总花费为w 购买模型 D 称 D 为 P 的对偶问题 P 为 D 的原问题 2 对偶模型的一般式 原问题 P maxz CXs t AX bX 0 对偶问题 D minw Ybs t YA CY 0 max b A C C AT b min m n m n 对偶问题模型的特点 例1 写出下列LP问题的对偶问题 写出上述对偶问题的对偶问题 结论 对偶问题的对偶问题为原问题 若原问题第i个约束为 则对偶问题yi为自由变量 同理 若原问题xj为自由变量 则对偶问题第j个约束为 式 令x2 x2 则上式化为 若原问题xj 0 则对偶问题第j个约束反号 与规定形式比 同理 若原问题第i个约束反号 与规定形式比 则对偶问题yi 0 小结 写一个线性规划问题的对偶问题 约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的 例2写出下面线性规划的对偶规划 二 对偶问题的基本性质 对偶的对偶就是原始问题 互为对偶 1 对称性 注 此性质只适用于 P max型与 D min型 2 弱对偶性 3 无界性 若原问题 对偶问题 为无界解 则其对偶问题 原问题 无可行解 证 用反证法 若 D 有可行解 则由弱对偶性 有Z x w y 即 P 的目标函数值有上界 这与 P 有无界解相矛盾 所以命题成立 注 性质3的逆命题不成立 事实上 原问题 对偶问题 无可行解 则对偶问题 原问题 有无界解或无可行解 4 最优性 图示为 5 强对偶性 设如果 P 问题有最优解 则 D 问题也有最优解 且最优值相等 证 对 P 增加松弛变量XS 化为标准型 设其最优基解为B 则单纯形终表为 若 P 有最优解 则检验数 x C CBB 1A 0 s 0 CBB 1I CBB 1 0 小结 P 无界解 无可行解 最优解 无界解 无可行解 最优解 D 三 对偶变量的经济含义 影子价格 1 影子价格的定义 式中 bi 第i种资源的拥有量 yi 对第i种资源的估价 定义 D 问题的最优解y CBB 1为 P 问题资源的影子价格 于是CBB 1 1 作为 D 问题的最优解y 买主最低的价格 2 作为 P 问题的影子价格 卖主内部掌握的价格 例5 煤 电 油例的最终表 X 20 24 84 0 0 T z 428 w Y 0 1 36 0 52 CBB 1 资源煤的影子价格为0 资源电的影子价格为1 36 资源油的影子价格为0 52 影子价格越高 说明这种资源对生产越重要 2 3 2灵敏度分析 一 定义 灵敏度分析讨论建模时的系数及有关变量变化时对解的影响 反映在两个方面 二 目的 1 参数在何范围内变化最优解 基 不变 2 参数变化 最优解有何变化 1 资源向量b的变化分析 问题 br在何范围时可使原问题最优基不变 2 价格系数C变化的分析 方法 问题 cj在什么范围内变化 最优解不变 结果 1 若Cj的变化使检验数仍全部 0 则原问题最优解不变 2 若Cj的变化使检验数中含有 0的量 则应用单纯形法迭代至最优 3 追加新变量的分析 问题 新加入的变量是否应进基 如新产品是否应投产 方法 只需计算新变量Xn 1的检验数 n 1 Cn 1 CBB 1Pn 1 0则投产 0则不投产 若 n 1 0 则用单纯形法迭代至最优 例 回顾煤电油例的终表 1 请指出电的影子价格是多少 并给出使最优基仍适用的电的变化范围 2 若有人愿以每度1元的价格向该厂供应25度电 是否值得接受 3 甲产品的价格在何范围内变化时 原最优解不变 4 若现又考虑一新产品丙 资源单耗为10 2 5 售价为6 5 是否应投产 解 1 电的影子价格为1 36 即电的增量在 50 26 92 内变动时 可使原最优基B不变 2 因为25 26 92 所以原有影子价格仍适用 而1 36 1 故值得接受 3 4 第 章线性规划 LinearProgramming 第 章线性规划 2 1线性规划的模型与图解法2 2单纯形法2 3对偶问题与灵敏度分析2 4运输问题 2 1线性规划的模型与图解法 2 1 1问题的引入 生产安排问题如何合理使用有限的人力 物力和资金 使得收到最好的经济效益 例1 某工厂可生产甲 乙两种产品 需消耗煤 电 油三种资源 现将有关数据列表如下 试拟订使总收入最大的生产方案 配料问题如何合理地搭配 混合 材料 以最经济的方式 达到配比要求 例2 营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量 55克蛋白质和800毫克的钙 如果市场上只有四种食品可供选择 它们每千克所含的热量和营养成分和市场价格见下表 问如何选择才能在满足营养的前提下使购买食品的费用最小 解 设xj j 1 2 3 4 为第j种食品每天的购入量 z为每天购买食品的总费用 则配餐问题的线性规划模型为 minz 14x1 6x2 3x3 2x41000 x1 800 x2 900 x3 200 x4 300050 x1 60 x2 20 x3 10 x4 55400 x1 200 x2 300 x3 500 x4 800 x1 x2 x3 x4 0 3 下料问题如何截取原材料 在达到截取要求的情况下 使废料最少 例3 料长7 4米 截成2 9 2 1 1 5米各200根 方案如下表 如何截取余料最少 解 设xj j 1 2 3 4 5 为采用第j种方案截取的原料根数 z为截取后的余料总米数 则下料问题的线性规划模型为 minz 0 x1 0 1x2 0 2x3 0 3x4 0 8x5x1 2x2 x4 2002x3 2x4 x5 2003x1 x2 2x3 3x5 200 xj 0 j 1 2 3 4 5 2 1 2线性规划的模型 一 LP模型的三要素规划问题的数学模型包含三个组成要素 1 决策变量 指决策者为实现规划目标采取的方案措施 是问题中要确定的未知量 2 目标函数 指问题要达到的目的要求 表示为决策变量的函数 3 约束条件 指决策变量取值时受到的各种可用资源的限制 表示为含决策变量的等式或不等式 二 LP模型的一般式一般地 线性规划模型 1 决策变量 x1 xn2 目标函数 3 约束条件 简记为 例如 练习1 某畜牧厂每日要为牲畜购买饲料以使其获取A B C D四种养分 市场上可选择的饲料有M N两种 有关数据如下 试决定买M与N二种饲料各多少公斤而使支出的总费用为最少 饲料 2 1 3线性规划模型的图解法 适用于2个变量的一般型 一 线性规划问题的解的概念设线性规划问题的一般型为 1 可行解 满足全部约束条件的决策变量X为可行解 全部可行解的集合R称为可行解域 2 最优解 使目标函数为最大 或最小 的可行解X 二 线性规划的图解法图解法步骤 1 根据约束条件画出可行解域 1 先作非负约束 2 再作资源限制约束 3 各约束的公共部分即该LP的约束的图形 可行域 2 画出目标函数的等值线 1 任给z两个不同的值 作相应两条直线 2 将目标直线向增大的方向移 直至可行域的边界 交点X 即最优解 3 求出最优解 由交点二直线联立求解出最优解X 的值 x1 x2 0 90 40 40 50 30 100 D l1 l2 l3 例1用图解法求解下列线性规划问题 可行域 目标函数等值线 X 有唯一最优解 顶点D 解直线l2 l3组成的线性方程组得 X 20 24 T 最优生产方案Z 7 20 12 24 428 最大收入 2 在模型 1 中 目标函数改为maxz 3x1 10 x2 其它不变 0 90 40 40 50 30 100 D l1 l2 l3 A X1 易知 目标函数等值线与直线l3平行 X2 故线段AD上的点均为最优解 有无穷多最优解 x1 x2 0 4 可行域无界 在可行域上没有使目标函数值为有限的最优解 无有限最优解 无界解 1 x2 0 1 2 x1 1 不存在所有约束条件的公共范围无可行解 小结 1 线性规划问题 2 两个重要结论 1 线性规划的可行域是凸多面体 2 线性规划的最优解在可行域的角点 顶点 上 思考题 约束条件不等式的几何意义是什么 怎样做图 2 4 1运输问题的一般模型 一 一般提法 1 产销平衡问题 A1 a1 A2 a2 产地 Am am B1 b1 B2 b2 销地 Bn bn 2 4运输问题 2 4 1运输问题的一般模型2 4 2表上作业法2 4 3产销不平衡问题 已知从Ai到Bj的单位运价为cij 且 问题 如何制定最合理的物资调运方案 使总运费最低 2 产销不平衡问题 化为产销平衡问题来解决 供不应求 供大于求 例 某食品公司下设3个加工厂和4个门市部 各加工厂每天的产量和各门市部每天的销量及运价如表 A2 A3 B2 A1 B3 B4 B1 运输问题网络图 a2 4 a3 9 b1 3 b2 6 b3 5 b4 6 a1 7 供应量 供应地 运价 需求量 需求地 3 11 3 10 1 9 2 8 7 4 10 5 二 模型 设从Ai到Bj的运量是xij i 1 2 3 j 1 2 3 4 z为总费用 minz 3x11 11x12 3x13 10 x14 x21 9x22 2x23 8x24 7x31 4x32 10 x33 5x34 x11 x12 x13 x14 7x21 x22 x23 x24 4x31 x32 x33 x34 9 x11 x21 x31 3x12 x22 x32 6x13 x23 x33 5x14 x24 x34 6xij 0 i 1 2 3 j 1 2 3 4 运输问题的一般模型 有m个产地生产某种物资 有n个地区需要该类物资 令a1 a2 am表示各产地产量 b1 b2 bn表示各销地的销量 ai bj称为产销平衡 设xij表示产地i运往销地j的物资量 cij表示对应的单位运费 则我们有运输问题的数学模型如下 运输问题有m n个决策变量 m n个约束条件 由于有产销平衡条件 只有m n 1个约束相互独立 因此 运输问题的基变量只有m n 1个 模型特点 1 有有限最优解 2 系数矩阵中每列只有两个1 其余全为0 3 基变量的个数 m n 1 运输问题的表格表示 2 4 2表上作业法 运输问题的求解步骤 确定初始可行方案 最小元素法 最优性检验 闭回路法 调整新方案 方法 最先满足最小的运费安排调运 总是从运价表中找最小元 优先满足供应 填上相应运量后划去一线 最后划两线 一 确定初始可行方案 最小元素法 3 1 4 3 3 6 初始解 x13 4 x14 3 x21 3 x23 1 x32 6 x34 3 其余xij 0 相应的运费为 Z0 3 4 10 3 1 3 2 1 4 6 5 3 86 方法评价 优点 较简便易行 有目标观念 缺点 只从单一格出发 无全局观念 注 1 有数字格表示基变量 其个数为m n 1 空格表示非基变量 2 每填上一个数后 则只能划去一行 或一列 3 若中间过程填上一个数后 同时划去一行和一列 有数字格的个数将少1个 这时 要在所划去的该行 或该列 上任意一格填一个0 此格当有数格对待 二 最优性检验 计算空格检验数 要求 除此空格外 其余顶点均为有数格 2 计算每个空格的检验数 等于其闭回路上由此空格起奇数顶点运价与偶数顶点运价的负值之和 11 3 3 2 1 1 12 11 10 5 4 2 22 9 2 3 10 5 4 1 24 8 10 3 2 1 31 7 5 10 3 2 1 10 33 10 3 10 5 12 3 若所有 ij 0 则当前方案是最优方案 否则转第三步调整新方案 注 运输问题检验数的经济意义 当该空格增运1单位时引起的总运费的增量 本例中由于 24 1 0 所以该方案非最优方案 三 调整 从 ij为最小负值的空格出发 对其闭回路上的奇数顶点运量加 偶数顶点运量减 调量 该闭回路的偶数顶点运量中的最小值调整后得到新方案 转第二步检验 123 1 114 113 1 104 在本例中 1 11 3 10 8 1 0 12 11 10 5 4 2 22 9 8 5 4 2 23 2 3 10 8 1 31 7 1 8 5 9 33 10 3 10 5 12 所有 ij 0 得到最优解 最优方案为 x13 5 x14 2 x21 3 x24 1 x32 6 x34 3 其余xij 0最少运费为 Z