第二章-线性规划的对偶理论与灵敏度分析.ppt

对偶性质 原问题与对偶问题解的对应关系小结 对应关系 原问题 最优解 无界解 无可行解 对偶问题 最优解 (Y,Y) (N,N) —— —— 无界解 —— —— (Y,Y) 无可行解 —— (Y,Y) 无法判断 当线性规划原问题求得最优解 时，其对偶问题也得到最优解 ，且代入各自的目标函数后有： ——是线性规划原问题约束条件的 右端项，它代表第 种资源的拥有量； （3） 对偶问题的经济解释－影子价格 对偶问题的经济解释－影子价格 1. 影子价格的数学分析： 定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。 由对偶问题得基本性质可得： 资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 市场价格 影子价格 市场 企业 对偶问题的经济解释－影子价格 2. 影子价格的经济意义 1）影子价格是一种边际价格 在式 中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数 的增量。 几何解释：引例图解法分析。 （15/4，5/4）,z=8.75 （7/2，3/2），z=8.5 对偶问题的经济解释－影子价格 2）影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。 若第i 种资源的单位市场价格为mi ，则有当yi* mi 时，企业愿意购进这种资源，单位纯利为yi*－mi ，则有利可图；如果yi* mi ，则企业有偿转让这种资源，可获单位纯利mi－yi * ，否则，企业无利可图，甚至亏损。 结论：若yi* mi 则购进资源i，可获单位纯利yi*－mi 若yi* mi则转让资源i ，可获单位纯利mi－yi 对偶问题的经济解释－影子价格 3）影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理: Y*Xs=0 , YsX*=0 表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。 对偶问题的经济解释－影子价格 4）影子价格对单纯形表计算的解释 单纯形表中的检验数 其中cj表示第j种产品的价格; 表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。 当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。 一、什么是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！ 2.3 对偶单纯形法 单纯形法的求解过程就是： 在保持原始可行的前提下(b列保持≥0)， 通过逐步迭代实现对偶可行(检验数行≤0)。 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0） ，通过逐步迭代实现原始可行（b列≥0，从非可行解变成可行解）。 2.3 对偶单纯形法 对偶单纯形法的思想（图示） 原问题 初始基本可行解 保持为基本可行解 初始对偶可行解 保持对偶可行性 最优解 基本可行性 对偶可行性 始终满足解的可行性 始终满足对偶可行性 对偶单纯形法的计算步骤 线性规划问题 不妨设 为对偶问题的 初始可行基，则 。 若 ，即表中原问题和 对偶问题均为最优解，否则换基。 换基方法： 确定换出基变量 对应变量 为换出基的变量 确定换入基变量 为主元素， 为换入基变量 初始可行基 例、用对偶单纯形法求解线性规划问题： 对偶问题的 初始可行基 例、用对偶单纯形法求解线性规划问题： 使对偶问题基变量可行, 换出 换出 换出 例、用对偶单纯形法求解