运筹学_对偶问题.ppt

第二章LP的对偶理论与灵敏度分析 线性规划的对偶问题 例1 设y1,y2和y3分别表示出让资源A，B和调试工序的单价，则美佳公司同意出让的条件将是 同意出让生产产品I的资源 同意出让生产产品II的资源 购买者希望用最少的代价获得这些资源，因此 LP问题的对称形式 变量：所有变量均具有非负约束 约束条件： 最大化问题 所有约束条件都是“≤”型的 最小化问题 所有约束条件都是“≥”型的 对称形式下的对偶关系 非对称形式下的对偶关系 单纯形法的矩阵表示 在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆 在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量 XB=B-1b 系数矩阵的变化: [A, I]?B-1[A, I] 在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj′,并且Pj′=B-1 Pj 若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解 对偶问题的基本性质 弱对偶性 原问题可行解的目标函数不超过对偶问题可行解的目标函数 互补松弛性的另一种表述 第三节 影子价格 式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi的意义代表在资源最优利用的条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格。 资源的影子价格随企业的生产任务、产品结构的改变而改变 影子价格是资源的边际价格 资源的影子价格也可视为一种机会成本 在生产过程中若某种资源未得到充分利用则其影子价格为零；只有在资源得到充分利用时，其影子价格才可能非零 利用影子价格可以说明：单纯形法中的检验数可以看成生产某种产品的产值与隐含成本的差 可以利用影子价格确定企业内部的核算价格，以便控制有限资源的使用和考核下属企业经营的好坏。 第四节 对偶单纯形法 按对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。 保持对偶问题有基可行解,而原问题只是基本解,通过迭代,使后者的负分量个数减少，一旦成为基可行解,则原问题与对偶问题同时实现最优解. 对偶单纯形法计算步骤 适应于求解这样的LP问题：标准化后不含初始基变量，但将某些约束条件两端乘以“-1”后，即可找出初始基变量。 要求：初始单纯形表中的检验数满足最优性条件 灵敏度分析 将讨论LP问题中的参数 中有一个或几个发生改变时问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变 研究的思路 将个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要从头计算，而直接检查在参数改变后最终表有什么改变，若仍满足最终表的条件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。 灵敏度分析的步骤 将参数的改变计算反映到最终表上来。具体计算公式可以使用 检查原问题是否仍为可行解 检查对偶问题是否仍为可行解 对检查情况按下表进行处理 价值系数变化的灵敏度分析 例：在第一章美佳公司的例1中 （1）若产品I的利润降至1.5元/件，而产品 II的利润增至2元/件，美佳公司的最优生产计划有何改变； （2）若产品I的利润不变，则产品II的利润在什么范围变化时，该公司的最优生产计划不发生变化 资源常数变化的灵敏度分析 例：在第一章美佳公司的例1中 （1）若设备A与调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化； （2）若设备A和B每天可用能力不变，则调试工序能力在什么范围变化时，问题的最优基不变 2．4对偶问题为 2.5对偶线性规划为 将各约束条件两端同乘“-1”得 用对偶单纯形法求解得 缄宅想仁割向眩孕蕾眼杉坠熔省狐趴巢绝珊浸侄席借能谦汁蕴叮相谋蹿犯运筹学_对偶问题运筹学_对偶问题 最优解：x1=0, x2=1/4, x3=1/2, x4=0, x5=0 最优目标函数值：w*=-8.5（z*=8.5） 注：通常很少直接使用对偶单纯形法求解线性规划问题。 凰限庶耶猴是娘震搐喇捌口崩蝶伟伊庇殷烛舟诡舀戌您瓦博弗辊舶壤痒咯运筹学_对偶问题运筹学_对偶问题 志君爪臃搽员木谢胁供撮叠畸鸯观峡陵聪恳纵巷叭掸挎纠霓思撞睹刷恭兹运筹学_对偶问题运筹学_对偶问题 自顽缚蛹冈己五叶迁脉串僧霄健邀龄阎勒架牛恋镰奏辽耐廉权今召旨尊路运筹学_对偶问题运筹学_对偶问题 促敛技扎湃卖讼锭卖寐沤抽怪蠕史痹蔚迸桓档莆浅仁妒留歇揩添倪宙吮唤运筹学_对偶问题运筹学_对偶问题 原问题 可行解 可行解 非可行解 非可行解 对偶问题 可行解 非可行解 可行解 非可行解 结论或继续计算步骤 问题的最优解或最优