线性规划及其应用4-线性规划的对偶理论.ppt

3 4线性规划对偶理论 1 重庆大学经济与工商管理学院肖智 第四节线性规划的对偶理论一 线性规划的对偶问题1 对偶问题例3 4 1生产计划问题某家具厂生产桌子和椅子两种家具 桌子售价50元 个 椅子售价30元 个 生产桌子和椅子需木工和油漆工两种工种 生产一个桌子需要木工4小时 油漆工2小时 生产一个椅子需要木工3小时 油漆工1小时 该厂每月可用木工工时为120小时 油漆工工时为50小时 问该厂如何组织生产才能使每月的销售收入最大 该问题是一典型的线性规划问题 其数学模型如下 3 4线性规划对偶理论 2 重庆大学经济与工商管理学院肖智 3 4 1 上述问题是企业利用已有的资源 通过自己加工 生产出产品进行销售而获得收入 企业是利润最大化为目标 因此 对于该问题也可考虑另一种经营问题 即出租 或出让 资源 来获得收入 该问题的关键是确定资源的价格 特别是要确定资源的价格在什么条件下 使出租 或出让 资源所获的最少收入与自己生产所获最大收入相同 为此 不妨假设木工与油漆工的单位工时租金分别为 y1和y2 可得数学模型如下 3 4线性规划对偶理论 3 重庆大学经济与工商管理学院肖智 3 4 2 上述问题显然也是线性规划问题 通常称模型 3 4 1 与模型 3 4 2 互为对偶问题 若称模型 3 4 1 为原问题 则称模型 3 4 2 为模型 3 4 1 的对偶问题 2 原问题与对偶问题一般矩阵形式 原问题对偶问题 P D 3 4 3 3 4线性规划对偶理论 4 重庆大学经济与工商管理学院肖智 二 如何将原问题转化为对偶问题1 转化原则 表3 4 1对偶关系对应表 3 4线性规划对偶理论 5 重庆大学经济与工商管理学院肖智 2 例3 4 2原问题 3 4 5 对偶问题 3 4 6 3 4线性规划对偶理论 6 重庆大学经济与工商管理学院肖智 三 线性规划的对偶理论如果不特别说明 原问题 P 和对偶问题 D 由式 3 4 3 定义 定理3 4 1 对称性定理 对偶问题的对偶是原问题 定理3 4 2 弱对偶定理 设X Y分别是 P 和 D 的可行解 则CX Yb 定理3 4 3 对偶定理 P 和 D 存在以下对应关系 1 P 有最优解的充要条件是 D 有最优解 2 若 P 无界 则 D 不可行 3 若 D 无界 则 P 不可行 3 4线性规划对偶理论 7 重庆大学经济与工商管理学院肖智 4 若X Y 分别是 P 和 D 的可行解 则它们分别为 P 和 D 的最优解的充要条件是 CX Y b定理3 4 4 互补松弛定理 如果X Y分别是 P 和 D 的可行解 它们分别为 P 和 D 的最优解的充要条件是 C YA X 0和Y b AX 0四 对偶解的经济含义1 对偶解与影子价格对偶解 Y CBB 1 的经济含义是资源的单位改变量引起的目标函数值的改变量 人们通常用价值量来衡量目标函数值的大小 因此对偶解也具有价值的内涵 通常又被称为影子价格 3 4线性规划对偶理论 8 重庆大学经济与工商管理学院肖智 影子价格是对偶解的一个十分形象的名称 它既表明对偶解是对系统内部资源的一种客观估价 又表明它是一种虚拟的价格 或价值的映象 而不是真实的价格 2 影子价格的特点 1 影子价格是对系统资源的一种最优估价 只有系统达到最优状态时才可能赋予该资源这种价值 因此 也有人称之为最优价格 2 影子价格的取值与系统的价值取向有关 并受系统状态变化的影响 系统内部资源数量和价格的任何变化都会引起影子价格的变化 从这种意义上讲 它是一种动态的价格体系 3 对偶解 影子价格的大小客观地反映资源在系统内 3 4线性规划对偶理论 9 重庆大学经济与工商管理学院肖智 的稀缺程度 如果某资源在系统内供大于求 尽管它有实实在在的市场价格 但它的影子价格为零 这一事实表明 增加该资源的供应不会引起系统目标的任何变化 如果某资源是稀缺资源 其影子价格必然大于零 影子价格越高 资源在系统中越稀缺 4 影子价格是一种边际价值 它与经济学中边际成本的概念相同 因而在经济管理中有十分重要应用价值 企业管理者可以根据资源在本企业内影子价格的大小决定企业的经营策略 然而 对偶解准确的经济意义有时要根据模型构造的方法来确定 模型构造方法的不同有时会导致对对偶解的不同解释 3 影子价格在企业经营策略中的应用 3 4线性规划对偶理论 10 重庆大学经济与工商管理学院肖智 1 如果某资源的影子价格高于市场价格 表明该资源在系统内有获利能力 应买入该资源 2 如果某资源的影子价格低于市场价格 表明该资源在系统内一无获利能力 应卖出该资源 3 如果某资源的影子价格等于市场价格 表明该资源在系统内处于平衡状态 既不用买入 也不必卖出 4 检验数与边际贡献因为 所以 检验数也可解释为产品对目标函数的边际贡献 即 增加该产品的单位生产量给目标函数带来的贡献 检验数与每一个变量相对应 当线性规划问题达到最优时 检验数总是小于或等于零 对极大化问题 这意味 3 4线性规划对偶理论 11 重庆大学经济与工商管理学院肖智 着在最优状态下 每个变量对目标函数的边际贡献都小于或等于零 检验数所代表的边际贡献有和影子价格一样的特点 它是在系统达到最优时对变量的一种估价 它的取值也受系统状态的影响 并会随系统的变化而变化 5 影子价格与资源的关系如果某资源在系统内的影子价格大于零 yj o 该资源必是紧缺资源 对应的约束为紧约束 bi aix o 否则 若该资源在系统内仍有剩余 系统一定还未达到最优状态 因为继续利用该资源可使目标进一步得到改善 另一方面 如果某资源在系统内有剩余 资源约束为松约束 bi aix 0 时 其对偶解必为零 yj 0 否则 若对偶解大于零 3 4线性规划对偶理论 12 重庆大学经济与工商管理学院肖智 增加该资源的使用还可使目标得到改善 同样道理 在最优状态下 当变量的检验数小于零时 cj ypj 0 说明生产该产品的边际贡献是负的 在最优计划中不该生产它 因此 该变量必为零 xj 0 另一方面 当变量大于零时 xj 0 该变量检验数 边际贡献 必为零 cj一ypj 0 否则 无论边际贡献取正值或负值 相应地增加或降低该产品的产量都可使目标得到改善 五 对偶问题的求解方法1 对偶解的求法1 直接求对偶问题的解 2 求原问题的最优解时 求得对偶解Y CBB 13 对偶单纯形7 例 对例3 4 1用上述方法2 得原问题的最优单纯形表 3 4线性规划对偶理论 13 重庆大学经济与工商管理学院肖智 2 例 对例3 4 1用上述方法2 得原问题的最优