运筹学电子教案-LP对偶理论.ppt

1,对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？ 且看下面详解,线性规划Linear Programming（LP） 对偶基本理论,对偶问题？,2,唉!我想租您的木工和油漆工一 用。咋样？价格嘛好说， 肯定不会让您兄弟吃亏讪。,引例俩家具制造商间的对话：,线性规划Linear Programming（LP） 对偶基本理论,王老板做家具赚了 大钱，可惜我老李有 高科技产品，却苦于没有 足够的木工和油漆工 咋办？只有租咯。,Hi：王老板，听说近来家具生意 好惨了，也帮帮兄弟我哦!,家具生意还真赚钱，但 是现在的手机生意这么好， 不如干脆把我的木工和油漆 工租给他，又能 收租金又可做生意。,价格嘛好商量， 好商量。只是.,王 老 板,李 老 板,3,王老板的家具生产模型： x1 、 x2是椅、桌生产量。 Z是家具销售总收入（总利润）。 max Z = 50x1+30x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1，x2 0 原始线性规划问题，记为（P）,线性规划Linear Programming（LP） 对偶基本理论,王老板的资源出租模型： y1、 y2单位木、漆工出租价格。 W是资源出租租金总收入。 min W =120y1+50y2 s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0 对偶线性规划问题，记为（D）,4,线性规划Linear Programming（LP） 对偶基本理论,王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。,按时下最流行的一个词，叫什么来着,双赢,5,原始（对偶）对偶（原始）关系表,线性规划Linear Programming（LP） 对偶基本理论,原问题（对偶问题）,对偶问题（原问题）,目标函数类型,max,变量个数与约束条件个数的对应关系,目标函数系数与右边项的对应关系,原问题变量类型与对偶问题约束条件类型的对应关系,原问题约束条件类型与对偶问题变量类型的对应关系,min,0 变量类型 0 无限制,约束条件个数 m,变量个数 n,右边项的系数对应目标函数系数,目标函数各变量系数对应约束条件右边项的系数,约束条件个数 m,变量个数 n, 约束条件类型 =, 约束条件类型 =, 0 变量类型 0 无限制,6,对偶理论基本定理： 1、对称性定理 2、弱对偶定理 3、强对偶定理 原问题与对偶问题解的对应关系表,线性规划Linear Programming（LP） 对偶基本理论,问题与解的状态,无界解,对偶问题,有最优解,无可行解,一定,有最优解,无界解,无可行解,原问题,可能,不可能,不可能,不可能,不可能,不可能,可能,可能,7,对偶问题解的经济解释影子价格 我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？ 对偶问题解的经济含义分析： 从单纯形法的矩阵描述中，目标函数取值 Z=CBB-1，和 检验数 CN -CBB-1N 中都有乘子 Y = CBB-1。 设B是 max Z=CX | AX b，X 0 的最优基矩阵，由强对偶定理知 Z* =CX*= CBB-1b=Y*b=W* 由此,线性规划Linear Programming（LP） 对偶基本理论, Z* b, Z* bi,（ Y*b） bi,= CBB-1= Y* 或,=,= yi*,8,对偶问题解的经济含义： 由上面分析对偶问题解中变量 yi* 的经济含义是在其他条件不变的情况下，单位第 i 种“资源”变化所引起的目标函数最优值的变化。所以， yi* 描述了原始线性规划问题达到最优时（各种“资源”都处于最优的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源”的影子价格。 下面图解阐述影子价格的直观含义： 采用单纯形法求解得（P）的最优解、最优基矩阵如下,线性规划Linear Programming（LP） 对偶基本理论,（P）的最优解为X* =（15，20，0，0）T,B =（p2 ，p1）=,3 4 1 2,（D）的最优解为Y* = CBB-1 =（5，15）,CB =（C2，C1） =（30，50）,B-1 =,1 -2 -1/2 3/2,9,王老板的家具生产模型的图解：,线性规划Linear Programming（LP） 对偶基本理论,x1,x2,4x1+3x2 = 120,2x1+ x2 = 50,L0： 50x1+30x2,D,可行域,1350=50x1+30x2,（15，20）,（P）max Z = 50x1+30x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1，x2 0,10,影子价格的直观含义：,线性规划Linear Programming（LP） 对偶基本理论,x1,x2,4x1+3x2 = 120,2x1+ x2 = 50,L0： 50x1+30x2,D,可行域,（P）max Z = 50x1+30x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1，x2 0,2x1+ x2 = 51,4x1+3x2 = 121,1365=50x1+30x2,1355=50x1+30x2,11,影子价格的特点： 影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。 特点1、影子价格是对系统资源的一种内部最优估价，只有当系统 达到最优状态时才可能赋予资源这种价值。 特点2、系统资源的一种动态价格体系，影子价格的大小与系统的 价值取向有关，并受系统状态变化的影响。系统环境的任 何变化都可能会引起影子价格的变化。 特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如 果某种资源在系统内供大于求，尽管它有实实在在的市场 价格，但它在系统内的影子价格却为零，而影子价格越高， 资源在系统内越稀缺。,线性规划Linear Programming（LP） 对偶基本理论,12,特点4、影子价格是一种边际价值，其与经济学中的边际成本的概 念相同。因而，在经济管理中十分重要的应用价值。企业 管理者可以根据资源在企业内部的影子价格的大小决定企 业的经营策略。 特点5、对偶解准确的经济意义与线性规划模型的构造方法有关， 模型构造方法的不同有时会导致对偶解的不同经济解释。,线性规划Linear Programming（LP） 对偶基本理论,13,对偶单纯形法： 引例,线性规划Linear Programming（LP） 对偶基本理论,max Z =2x1+x2 s.t. x1+ x2+ x3 = 5 2x2+ x3 5 4x2+6x3 9 x1 ，x2 ，x3 0,max Z =2x1+x2 s.t. x1+ x2+ x3 = 5 2x2+ x3+ x4 = 5 4x2+6x3 -x5= 9 x1 ，x2 ，x3 ， x4 ， x5 0,标准化,准典式：max Z = -1x2 -2x3 s.t. x1+ x2+ x3 = 5 2x2+ x3+ x4 = 5 -4x2 -6x3 +x5 = -9 x1 ，x2 ，x3 ， x4 ， x5 0,化典式,14,对偶单纯形表：,线性规划Linear Programming（LP） 对偶基本理论,基 解 X1 X2 X3 X4 X5,X1 5 1 1 1 0 0 X4 5 0 2 1 1 0 X5 -9 0 -4 -6 0 1,检验数 0 -1 -2 0 0,比值 - 1/4 1/3 - -,X1 11/4 1 0 -1/2 0 1/4 X4 1/2 0 0 -2 1 1/2 X2 9/4 0 1 2/3 0 -1/4,检验数 0 0 -1/2 0 -1/4,15,线性规划问题参数变化敏感性分析： 敏感性分析的重要性在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围，环境条件变化时可能对经营状况带来何种影响，产生影响后的解决途径。