[数学]第三章 对偶理论 第一讲 线性规划的对偶模型_对偶性质.ppt

先将此规划问题转化为对称形式？ 经上述变换后可重新表达为 例2.1 写出线性规划问题的对偶问题 例2.2 写出下列线性规划问题的对偶问题. 求线性规划问题的对偶问题及两者的解 结 论 原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。 对偶问题 原问题 证明 设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和 Y＊满足： 设对偶问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理可知，X＊和 Y＊满足： 原问题与对偶问题解的对应关系小结 对偶问题的经济解释－影子价格 1. 影子价格的数学分析： 对偶问题的经济解释－影子价格 2. 影子价格的经济意义 1）影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即： 对偶问题的经济解释－影子价格 2）影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。 对偶问题的经济解释－影子价格 3）影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理: Y*Xs=0 , YsX*=0 表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。 对偶问题的经济解释－影子价格 4）影子价格对单纯形表计算的解释 设xj*(j=1,2…n)是原问题的最优解，yi*(i=1,2, …,m)是其对偶问题的最优解。 因为 又知 所以 3.2 对偶性质 Dual property 【性质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。 另一结论：若(LP)与(DP)都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。 【性质5】互补松弛定理: 设X*、Y*分别为 (LP) 与 (DP) 的可行解，XS和YS分别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当 YSX*=0 和 Y*XS=0 性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。 Y * XS = 0 和 YS X * = 0 两式称为互补松弛条件。将互补松弛条件写成下式 由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系： 3.2 对偶性质 Dual property (1)当yi*0时， , 反之当 , 时yi*=0； 利用上述关系，建立对偶问题(或原问题)的约束线性方程组，方程组的解即为最优解。 【例3.5】 已知线性规划 的最优解是 , 求对偶问题的最优解。 3.2 对偶性质 Dual property 标准化 【解】对偶问题是 即： 因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即 解此线性方程组得y1=1, y2=1, 从而对偶问题的最优解为Y=(1，1)，最优值w =26。 【例3.6】 已知线性规划 的对偶问题的最优解为Y=(0，－2)，求原问题的最优解。 【解】对偶问题是 3.2 对偶性质 Dual property 将Y＊带入由方程可知，y3＝y5＝0，y4＝1。 ∵y2=-2≠0 ∴x5＝0 又∵y4=1≠0 ∴x2＝0 将x2，x5分别带入原问题约束方程中，得： 解方程组得：x1=-5,x3=-1, 所以原问题的最优解为 X＊=(-5,0,-1)，最优值z=-12 无可行解 无界解 最优解 无法判断 (Y,Y) —— 无可行解 (Y,Y) —— —— 无界解 —— —— (Y,Y) (N,N) 最优解 对偶问题 原问题 对应关系 【例3.7】 证明该线性规划无最优解： 【证】容易看出X=(4，0，0) 是一可行解。对偶问题 将三个约束的两端分别相加得 , 而第二个约束有 y2≥1,矛盾，故对偶问题无可行解，因而原问题具有 无界解，即无最优解。 3.2 对偶性质 Dual property 【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解。 其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：不乘负号)对应于(LP)的一组基本解。 3.2 对偶性质 Dual property 注：应用性质