《现代企业运筹学管理方案》由会员分享，可在线阅读，更多相关《现代企业运筹学管理方案（55页珍藏版）》请在金锄头文库上搜索。
1、运筹学 OperationalResearch OR 线性规划进一步研究 对偶原理对偶单纯形方法灵敏度分析 对偶原理 对偶问题概念 任何一个线性规划问题都有一个伴生的线性规划问题 称为其 对偶 问题 对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系 在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解 反之亦然 对偶理论就是研究线性规划及其对偶问题的理论 是线性规划理论的重要内容之一 问题的导出 问题的导出 例1 2 假设有客户提出要求 购买工厂所拥有的工时和材料 为客户加工别的产品 由客户支付工时费和材料费 那么工厂给工时和材料制订的最低价格应是多少 才值
2、得出卖工时和材料 问题的导出 例1 2 出卖资源获利应不少于生产产品的获利 约束价格应该尽量低 这样 才能有竞争力 目标价格应该是非负的 问题的导出 用y1和y2分别表示工时和材料的出售价格 总利润最小minW 3y1 9y2保证A产品利润y1 y2 2保证B产品利润y1 4y2 3保证C产品利润y1 7y2 3售价非负y1 0y2 0 问题的导出 问题的导出 对偶问题的定义 对称形式的对偶问题 对偶问题的定义 对称形式的对偶问题 对偶问题的定义 对偶问题的特点若原问题目标是求极大化 则对偶问题的目标是极小化 反之亦然原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵极大化问题的每个约束
3、对应于极小化问题的一个变量 其每个变量对应于对偶问题的一个约束 对偶问题的定义 一般线性规划问题的对偶问题 对偶问题的定义 对偶问题对应表 对偶问题的写出 例2 2标准型对偶问题 对偶问题的写出 例2 3 弱对偶定理 定理2 1弱对偶定理若互为对偶的线性规划分别有可行解则其相应的目标函数值满足 弱对偶定理 推论 推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界 推论2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界 推论3若原始问题可行 则其目标函数无界的充要条件是对偶问题没有可行解 最优性准则定理 定理2 2最优性准则定理
4、若X和Y分别是互为对偶的线性规划的可行解 且使CX Yb 则X和Y分别是相应线性规划问题的最优解 主对偶定理 定理2 3 主对偶定理 若原始问题和对偶问题两者均可行 则两者均有最优解 且此时目标函数值相同 证明 由两者均有可行解 则根据定理2 1可知两者均有界 因此均有最优解 设B是其最优基 X是其对应的基本可行解令A BN 则 对应于基B的检验数满足 主对偶定理 定理2 3 主对偶定理 设B是其最优基 X是其对应的基本可行解令A BN 则 对应于基B的检验数满足 对偶问题的一个可行解 其目标值 影子价格 对偶最优解的经济含义 影子价格 代表着当第i个右端常数增加一个单位时 最优目标函数值的相
5、应增量 其含议是在目前已给定的情况下 最优目标值随资源数量变化的变化率 其经济含义是为约束条件所付出的代价 当B是原问题的最优基时 Y CBB 1就是影子价格向量 影子价格举例 y1 5 3 y2 1 3即工时的影子价格为5 3 材料的影子价格为1 3 如果目前市场上材料的价格低于1 3 则企业可以购进材料来扩大生产 反之可以卖掉部分材料 如果有客户以高于5 3的价格购买工时 则可以出售一些工时 反之则反 从原始问题最优表求影子价格 当B是原问题的最优基时 CBB 1就是影子价格向量 由检验数的计算方法可知 C A若A中有单位子矩阵 则在最优表中有 对偶单纯形法 对偶单纯形法并不是求解对偶问题
6、解的方法 而是利用对偶理论求解原问题的解的方法 对于标准线性规划问题 可行基B若B对应的基本解是可行解最优基B若B对应的基本解是最优解对偶可行基B若CBB 1是对偶问题可行解即C CBB 1A 0或检验数 0 对偶单纯形法 对于标准线性规划问题 对偶单纯形法 对于标准线性规划问题 找一个基 建立初始对偶单纯形表 检验数全部非正 若b列元素非负 则已经是最优基 反之 则取相应行的基变量为出基变量 为保证能对基的可行性有所改进 则将来的主元应该为负数 为保证下一个基还能是对偶可行基 应使检验数仍为非正的 主元变换 对偶单纯形法举例 例2 6用对偶单纯形法求解 对偶单纯形法举例 对偶单纯形法举例 对
7、偶单纯形法举例 灵敏度分析 在生产计划问题的一般形式中 A代表企业的技术状况 b代表企业的资源状况 而C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定 在实际生产过程中 上述三类因素均是在不断变化的 如果按照初始的状况制订了最佳的生产计划 而在计划实施前或实施中上述状况发生了改变 则决策者所关心的是目前所执行的计划还是不是最优 如果不是应该如何修订原来的最优计划 更进一步 为了防止在各类状况发生时 来不及随时对其变化作出反应 即所谓 计划不如变化快 企业应当预先了解 当各项因素变化时 应当作出什么样的反应 灵敏度分析 当系数A b C发
8、生改变时 目前最优基是否还最优 为保持目前最优基还是最优 系数A b C的允许变化范围是什么 假设每次只有一种系数变化 目标系数C变化基变量系数发生变化 非基变量系数发生变化 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化 灵敏度分析 若B是最优基 则最优表形式如下 灵敏度分析总是在最优表上进行 灵敏度分析 例2 7线性规划 灵敏度分析 例2 7线性规划 灵敏度分析 例2 7线性规划 3 2 1 3 2 1 灵敏度分析 例2 7线性规划 价值系数CN发生改变 C3 C3 4 如果C3 4 则目前解不再是最优解 应该用单纯形方法继续求解 否则解不变 即对于C3而言 使最优解不变的
9、条件是C3 4 灵敏度分析 例2 7线性规划 价值系数CN发生改变 灵敏度分析 例2 7线性规划 价值系数CB发生改变 C1 3 1 4 3C1 1 3C1 1 C1 3 0 1 4 3C1 0 1 3C1 1 0 C1 3若C1 3 4则x4进基 x1出基若3 C1则x3或x5进基 x2出基 灵敏度分析 例2 7线性规划 价值系数CB发生改变 灵敏度分析 例2 7线性规划 价值系数CB发生改变 灵敏度分析 例2 7线性规划 右端常数b发生改变 b1 4b1 3 3 3 b1 3 9 4 b1 9 3 5b1 3 灵敏度分析 例2 7线性规划 右端常数b发生改变 灵敏度分析 例2 7线性规划
10、右端常数b发生改变 灵敏度分析 例2 7线性规划 右端常数b发生改变 b2 4 b2 3 b2 3 1 3 b2 12 b2 3 5 灵敏度分析 增加一个变量若企业在计划期内 有新的产品可以生产 则在知道新产品的单位利润 单件资源消耗量时 可以在最优表中补充一列 其中的前m行可以由基矩阵的逆矩阵得到 而检验数行也可以由与其它列相同的方法计算得到 若检验数非正 则原最优解仍为最优 原生产计划不变 不生产这种新产品 否则 当检验数为正时 则应以该变量进基 作单纯形迭代 从而找出新的最优解 灵敏度分析 例2 11 灵敏度分析 增加一个约束在企业的生产过程中 经常有一些突发事件产生 造成原本不紧缺的某
11、种资源变成为紧缺资源 对生产计划造成影响 若把目前的最优解代入新增加的约束 能满足约束条件 则说明该增加的约束对最优解不构成影响 即不影响最优生产计划的实施 若当前最优解不满足新增加的约束 则应把新的约束添到原问题的最优表内新的一行中去 用对偶单纯形方法来进行迭代 求出新的最优解 灵敏度分析 例2 12增加约束 灵敏度分析 例2 12增加约束 灵敏度分析 A中元素改变如果N中数据改变 可以用增加一个变量来处理如果B中元素改变 则情况较复杂 一般需要修改问题后重新求解 讨论题 1 7在极大化问题的下列表中 六个常数 1 2 3 1 2 之值未知 假定无人工变量 分别写出对六个未知数的约束条件 使以下各小题关于该表的说法为真 现行解最优 但不唯一 现行解不可行 指出哪个变量造成 一个约束条件有矛盾 现行解是退化的基本可行解 现行解可行 但问题无有限最优解 现行解是唯一最优解 现行解可行 但将x1取代x6后 目标函数能改进 讨论题 现行解最优 但不唯一 现行解不可行 指出哪个变量造成 一个约束条件有矛盾 现行解是退化的基本可行解 现行解可行 但问题无有限最优解 现行解是唯一最优解 现行解可行 但将x1取代x6后 目标函数能改进
