《线性规划的对偶问题》由会员分享，可在线阅读，更多相关《线性规划的对偶问题（30页珍藏版）》请在金锄头文库上搜索。
1、1第三章 线性规划的对偶问题p 对偶线性规划 p 对偶定理 p 对偶单纯形法第一节 对偶问题对偶问题概念：任何一个线性规划问题都有一个与之相对应 的线性规划问题，如果前者称为原始问题，后者 就称为“对偶”问题。对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系，在 求得一个线性规划最优解的同时也就得到对偶线 性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的 理论，是线性规划理论的重要内容之一。 3n对偶问题的提出 例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上 加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获
2、 得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试 问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利 润达到最大。p对偶线性规划设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 4假设计划期内甲乙两种产品各生产 吨，设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产 吨，乙产品生产8吨，可以使总利润达到最大，为 元。5现在从另一个角度来考虑该工厂的生
3、产问题:假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设 分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少（价格应该尽量低，这样，才能有竞争力）价格应该是非负的 6由此可得两个对称的线性规划：设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 7矩阵形式：8可以得到另一个线性规划： 称之为原线性规划问题的对偶问题，n对偶线性规划考虑如下具有不等式约
4、束的线性规划问题9101112若令 线性规划标准型的对偶规划为：n 线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：它的对偶规划为：对偶问题的特点 （1）目标函数在一个问题中是求最大值在 另一问题中则为求最小值 （2）一个问题中目标函数的系数是另一个 问题中约束条件的右端项 （3）一个问题中的约束条件个数等于另一 个问题中的变量数 （4）原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵min f=CTXs.t.AXb X 0max z=bTY s.t. ATYCY 0其他形式问题的对偶
5、min f=CTX s.t.AXb X 0max z=bTY s.t. ATYCY 0min f=CTX s.t.AX=b X 0max z=bTY s.t. ATYCY ：unr15n对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解 过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对 应关系的原始对偶表： 目标函数变量系数 约束条件右端项 约束条件右端项 目标函数变量系数 约束条件个数：n个 变量个数：n个 变量个数：m个 约束条件个数：m个 目标函数minW 目标函数maxZ 对偶问题（或原问题） 原问题（或对偶问题） 16解：对偶规划：例2 写
6、出下列线性规划的对偶问题17例3 写出下列线性规划的对偶问题解：上述问题的对偶规划：18本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。定理1：（对称性）对偶问题的对偶是原问题。证明：设原问题为 对偶问题为改写对偶问题为 对偶问题的对偶为第二节 对偶定理19定理2：弱对偶定理若 是原（极小化）问题的可行解， 是对偶（极大化）问题的可行解，那么 证明：因为 是对偶问题的可行解，所以满足约束条件 又因为 是原问题的可行解，可得 ， ,所以 。注：原（极小化）问题的最优目标函数值以对偶问题任一 可行解的目标函数值为下界。对偶（极大化）问题的最优目标函数值以原问题任
7、一 可行解的目标函数值为上界。推论1：如果原问题没有下界（即minZ），则对偶问 题不可行。如果对偶问题没有上界（即maxW），则原问题 不可行。若原问题与对偶问题之一无界，则另一个无可行解。20证明：由弱对偶定理，对于原始问题的所有可行解 ，都有 因此 是原问题的最优解。同理，对于对偶问题的所有可行解 ，都有所以 是对偶问题的最优解。 推论2：最优性定理若 是原问题的可行解， 是对偶问题的可行解，而且两者的目标函数值相等，即 ，则 和 分别是原问题和对偶问题的最优解。21证明：设 是原问题(min)的最优解，则对应的基必有。若定义 ，则 ，因此 为对偶问题的可行解，而且 ，由最优性定理， 是
8、对偶问题的最优解。 定理3: 强对偶定理如果原问题（min)与对偶问题(max)之一有最优解，那么另一个也有最优解，而且目标函数值相等。22证明：设 满足原问题(min)的最优性条件，则对应的 基必有。若定义 ，则 ，因此 为对偶问题的基本可行解。 定理4：设 满足原问题(min)的最优性条件的一个基本解 ，则其对应的线性规划问题(min)的检验数对应对偶问题的 一个基本可行解。23原问题与对偶问题可能出现的情况（1）两者都有最优解，且最优值相等；（2）一个有可行解，但无界，则另一个无可行解；（3）两者都无可行解。24定理5：互补松弛定理如果 分别是原问题(min)和对偶问题（max)的可行解
9、，那么 和 为最优解的充要条件是 通常称 为互补松弛条件。证明：充分性必要性25例5、已知线性规划问题: 其对偶问题的最优解。试用互补松弛定理找出原问题的最优解。解：原问题的对偶问题为：由对偶问题最优解 可知 ，由互补松弛定理， 解方程组 所以原问题最优解26假设计划期内甲乙两种产品各生产 吨，设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产 吨，乙产品生产8吨，可以使总利润达到最大，为 元。例：对偶最优解的经济解释影子价格 2728由强对偶定理可知，如果
10、原问题有最优解 ，那么对偶问题也有最优解 ，而且它们的目标函数值相等，即有：其中 是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润，产值等）而作出估价，为区别起见，称之为影子价格(shadow price)。29影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量 ，由互补松弛定理，在对偶最优解 中，第i种资源的影子价格 。反之如果第i种资源的影子价格 ，那么由互补松
11、弛定理，原问题的第i个约束为严格等式，即 ，这表明第i种资源已经用完，成为稀缺资源。 资源的影子价格同时也是一种机会成本，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。30设备每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 例：对偶最优解其中 为设备A的影子价格，在资源最优利用的条件下，设备A每增加一个单位台时，可以使总利润增加 元。若设备可供台时数，则
