运筹学线性规划的对偶理论及其应用.pptx

管理与人文学院管理与人文学院 忻展红忻展红 1999，4第二章第二章线性规划的对偶理论及其应用线性规划的对偶理论及其应用窗含西岭千秋雪，门泊东吴万里船窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象对偶是一种普遍现象22.1 线性规划的对偶理论线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式线性规划原问题与对偶问题的表达形式任何线性规划问题都有其对偶问题任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义对偶问题有其明显的经济含义 假设有商人要向厂方购买资源假设有商人要向厂方购买资源A和和B，问他们谈判原料，问他们谈判原料价格的模型是怎样的？价格的模型是怎样的？3 例例2.1.1设设A、B资源的出售价格分别为资源的出售价格分别为 y1 和和 y2显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资源后所得不应比生产产品所得少目标函数目标函数 min g(y)=25y1+15y24 2.1.1 线性规划原问题与对偶问题的表达形式线性规划原问题与对偶问题的表达形式5 2.1.1 线性规划原问题与对偶问题的表达形式线性规划原问题与对偶问题的表达形式6 2.1.2 标准标准(max,(max,)型的对偶变换型的对偶变换目标函数由目标函数由 max 型变为型变为 min 型型对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量 yi，i=1,2,m对偶问题约束为对偶问题约束为 型，有型，有 n 行行原问题的价值系数原问题的价值系数 C 变换为对偶问题的右端项变换为对偶问题的右端项原问题的原问题的右端项右端项 b 变换为对偶问题的变换为对偶问题的价值系数价值系数原问题的技术系数矩阵原问题的技术系数矩阵 A 转置后成为对偶问题的技术转置后成为对偶问题的技术系数矩阵系数矩阵原问题与对偶问题互为对偶原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义 2.1.3 非非标准标准型的对偶变换型的对偶变换8 表表2.1.1 对偶变换的规则对偶变换的规则约束条件的类型与非负条件对偶约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的对偶变换是一一对应的92.2 线性规划的对偶定理线性规划的对偶定理 2.2.1 弱弱对偶定理对偶定理定理定理 对偶问题对偶问题(min)的任何可行解的任何可行解Y0，其目标函数值总是其目标函数值总是不小于原问题不小于原问题(max)任何可行解任何可行解X0的目标函数值的目标函数值 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设10 弱弱对偶定理推论对偶定理推论max问题的任何可行解目标函数值是其对偶问题的任何可行解目标函数值是其对偶min问题问题目标函数值的下限；目标函数值的下限；min问题的任何可行解目标函数问题的任何可行解目标函数值是其对偶值是其对偶max问题目标函数值的上限问题目标函数值的上限如果原如果原max(min)问题为无界解，则其对偶问题为无界解，则其对偶 min(max)问题无可行解问题无可行解如果原如果原max(min)问题有可行解，其对偶问题有可行解，其对偶 min(max)问问题无可行解，则原问题为无界解题无可行解，则原问题为无界解注注：有可能存在原问题和对偶问题同时无可行解的情：有可能存在原问题和对偶问题同时无可行解的情况况11 2.2.2 最优解判别最优解判别定理定理定理定理 若原问题的某个可行解若原问题的某个可行解X0的目标函数值与对偶问题的目标函数值与对偶问题某个可行解某个可行解Y0的目标函数值相等，则的目标函数值相等，则X0,Y0分别是相分别是相应问题的最优解应问题的最优解证证：由弱对偶定理推论：由弱对偶定理推论1，结论是显然的。，结论是显然的。即即CX0=Y0b CX,Y0b=CX0 Yb。证毕证毕。2.2.3 主对偶主对偶定理定理定理定理 如果原问题和对偶问题都有可行解，则它们都有最如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。优解，且它们的最优解的目标函数值相等。证证：由弱对偶定理推论：由弱对偶定理推论1可知，原问题和对偶问题的目标可知，原问题和对偶问题的目标函数有界，故一定存在最优解。函数有界，故一定存在最优解。现证明定理的后一句话。现证明定理的后一句话。12 主对偶主对偶定理的证明定理的证明 证证：现证明定理的后一句话。：现证明定理的后一句话。设设 X0 为原问题的最优解，它所对应的基矩阵是为原问题的最优解，它所对应的基矩阵是 B，X0=B 1 b，则其检验数满足，则其检验数满足 C CBB 1A 0 令令 Y0=CBB 1，则有，则有 Y0 A C；而对原问题松弛变量；而对原问题松弛变量的检验数有的检验数有 0 CBB 1I 0，即，即 Y0 0。显然显然Y0为对偶问题的可行解。因此有对偶问题目标函为对偶问题的可行解。因此有对偶问题目标函数值，数值，g(Y0)=Y0b=CBB 1 b 而原问题最优解的目标函数值为而原问题最优解的目标函数值为 f(X0)=CX0=CBB 1 b故由最优解判别定理可知故由最优解判别定理可知Y0 为对偶问题的最优解。为对偶问题的最优解。证毕证毕。该定理的证明告诉我们一个非常重要的概念：该定理的证明告诉我们一个非常重要的概念：对偶变对偶变量的最优解等于原问题松弛变量的机会成本量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的即对偶变量的最优解是原问题资源的影子价格影子价格13 2.2.4 互补松弛互补松弛定理定理定理定理 设设X0,Y0分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解，U0为为原问题的松弛变量的值、原问题的松弛变量的值、V0为对偶问题剩余变量的为对偶问题剩余变量的值。值。X0,Y0分别是原问题和对偶问题最优解的充分分别是原问题和对偶问题最优解的充分必要条件是必要条件是 Y0 U0+V0 X0=0证证：由定理所设，可知有：由定理所设，可知有 A X0+U0=b X0,U0 0 (1)Y0 A V0 =C Y0,V0 0 (2)分别以分别以Y0左乘左乘(1)式，以式，以X0右乘右乘(2)式后，两式相减，得式后，两式相减，得 Y0 U0+V0 X0=Y0 b C X0若若 Y0 U0+V0 X0=0，根据最优解判别定理，根据最优解判别定理，X0,Y0分别分别是原问题和对偶问题最优解。反之亦然。是原问题和对偶问题最优解。反之亦然。证毕证毕。14 2.2.4 互补松弛互补松弛定理定理 Y0 U0+V0 X0=0 有什么应用有什么应用若若(Y0)i 00，则，则 (U0)i=0=0，意味着原问题第，意味着原问题第 i 约束行约束行必须为必须为 =约束；对约束；对(X0)i 0 0 亦如此亦如此可用来简化问题的求解可用来简化问题的求解线性规划的高级算法：利用互补松弛定理，原问题与线性规划的高级算法：利用互补松弛定理，原问题与对偶问题同时解对偶问题同时解原问题为基础可行解，对偶问题为非可行解，但满足原问题为基础可行解，对偶问题为非可行解，但满足互补松弛条件；则当对偶问题为可行解时，取得最优互补松弛条件；则当对偶问题为可行解时，取得最优解解15 2.2.5 原问题检验数与对偶问题的解原问题检验数与对偶问题的解在主对偶定理的证明中我们有：对偶在主对偶定理的证明中我们有：对偶(min型型)变量的最变量的最优解等于原问题松弛变量的机会成本，或者说原问题松优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在更一般地讲，不管原问题是否标准，在最优解的单纯型最优解的单纯型表中，都有原问题表中，都有原问题虚变量虚变量(松弛或剩余松弛或剩余)的机会成本对应的机会成本对应其对偶问题其对偶问题实变量实变量(对偶变量对偶变量)的最优解的最优解，原问题原问题实变量实变量(决策变量决策变量)的检验数对应其对偶问题的检验数对应其对偶问题虚变量虚变量(松弛或剩松弛或剩余变量余变量)的最优解。因此，原问题或对偶问题只需求解的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。其中之一就可以了。16 例例2.2.3 原问题检验数与对偶问题的解原问题检验数与对偶问题的解1718192.3 对偶单纯型算法对偶单纯型算法 2.3.1 基本思路基本思路原单纯型迭代要求每步都是基础可行解原单纯型迭代要求每步都是基础可行解达到最优解时，检验数达到最优解时，检验数 cjzj 0(max)或或 cjzj 0(min)但对于但对于(min,)型所加的剩余变量无法构成初始基础型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决可行解，因此通过加人工变量来解决大大M法和二阶段法较繁法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，能否从剩余变量构成的初始基础非可行解出发迭代，但保证但保证检验数满足最优条件，检验数满足最优条件，cjzj 0(max)或或 cjzj 0(min)每步迭代保持每步迭代保持检验数满足最优条件，但减少非可行度检验数满足最优条件，但减少非可行度如何判断达到最优解如何判断达到最优解如何保证初始基础解满足最优条件如何保证初始基础解满足最优条件为什么叫对偶单纯型法为什么叫对偶单纯型法b=B1b020 2.3.2 迭代步骤迭代步骤1确定出变量确定出变量找非可行解中最小者，即找非可行解中最小者，即 min bi|bi0，设第，设第 i*行的最行的最负，则负，则i*行称为行称为主行主行，该行对应的基变量为，该行对应的基变量为出变量出变量，xi*2确定入变量确定入变量最大比例原则最大比例原则 设设 j*列满足列满足(2.3.1)式，式，j*列称为列称为主列主列，xj*为为出变量出变量3 以主元以主元 ai*j*为中心迭代为中心迭代4 检查当前基础解是否为可行解检查当前基础解是否为可行解 若是，则当前解即为最优解若是，则当前解即为最优解 否则，返回否则，返回 步骤步骤 121最大比例原则最大比例原则令令 V=C-CBB-1A 为检验数向量为检验数向量对对 min 问题，问题，V 0 称为正则，即满足最优判定条件称为正则，即满足最优判定条件可以证明，可以证明，V 的迭代也满足四角运算法则的迭代也满足四角运算法则令令 xr 为出变量，在第为出变量，在第i*行；若选非基变量行；若选非基变量 xj*为入变量为入变量必须满足什么条件才能保证迭代后的解仍为正则的？必须满足什么条件才能保证迭代后的解仍为正则的？因此只需考虑因此只需考虑 非基变量非基变量 xj 观察出变量观察出变量 xr 对应的检验数变化，因为有对应的检验数变化，因为有 ai*r=1，故，故 由于由于 vj*0，故必有故必有 ai*j*0 时，显然有时，显然有 结合上述的几个条件，则得到最大比例原则结合上述的几个条件，则得到最大比例原则 若若 ai*j 0 时，则要求时，则要求 vj-vj*ai*j/ai*j*0,可解出可解出注注：这里的：这里的 aij 都表示当前单纯性表中的技术系数都表示当前单纯性表中的技术系数23 例例2.3.1 对偶单纯型解法对偶单纯型解法解解：化原问题为适合对偶解法的标准型：化原问题为适合对偶解法的标准型24 表表2.3.1 对偶单纯型法的单纯型表对偶单纯型法的单纯型表(min)答答：最优解为：最优解为x1=14,x3=8,x2=x4=0,OBJ=14管理与人文学院管理与人文学院 忻展红忻展红 1999，4习习 题题 课课学而时习之，不亦乐乎学而时习之，不亦乐乎 论语论语26第第 1 题题解：设车间：设车间 1 生产生产x1A单位单位A、生产、生产x1B单位单位B；设车间设车间 2 生产生产x2A单位单位A、生产、生产x2B单位单位B；设车间设车间 3 生产生产x3A单位单位A、生产、生产x3B单位单位B；则有生产安排最优化的模型如下则有生产安排最优化的模型如下：27第第 2 题题解：解：设设 x1A 为饮料甲中为饮料甲中A的总含量的总含量 (升升)设设 x2A 为饮料乙中为饮料乙中A的总含量的总含量 (升升)设设 x3A 为饮料丙中为饮料丙中A的总含量的总含量 (升升)设设 x1B 为饮料甲中为饮料甲中B的总含量的总含量 (升升)设设 x2B 为饮料乙中为饮料乙中B的总含量的总含量 (升升)设设 x3B 为饮料丙中为饮料丙中B的总含量的总含量 (升升)设设 x1C 为饮料甲中为饮料甲中C的总含量的总含量 (升升)设设 x2C 为饮料乙中为饮料乙中C的总含量的总含量 (升升)设设 x3C 为饮料丙中为饮料丙中C的总含量的总含量 (升升)则有模型如下：则有模型如下：2829第第 3、4 题题原问题原问题：标准型标准型：对偶问题：对偶问题：