周六刚第二章-线性规划的对偶理论与灵敏度分析-PPT课件.ppt

线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）第二章第二章线线性性规规划的划的对对偶理偶理论论与与灵敏度分析灵敏度分析1线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划对对偶理偶理论论2线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶理理论是是线性性规划中最重要的理划中最重要的理论之一，是深入了解之一，是深入了解线性性规划划问题结构的重要理构的重要理论基基础。同。同时，由于，由于问题提出本身所具有的提出本身所具有的经济意意义，使得，使得它成它成为对线性性规划划问题系系统进行行经济分析和敏感性分析的重要工具。那么，分析和敏感性分析的重要工具。那么，对偶偶问题是怎是怎样提出的，提出的，为什么会什么会产生生这样一种一种问题呢？呢？且看下面且看下面详详解解3线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论引例引例俩俩家具制造商家具制造商间间的的对话对话：唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋用。咋样样？价格嘛？价格嘛好好说说，肯定不会肯定不会让让您兄弟吃您兄弟吃亏亏讪讪。王老板做家具王老板做家具赚赚了了 大大钱钱，可惜我老李有，可惜我老李有 高科技高科技产产品，却苦于没有品，却苦于没有足足够够的木工和油漆工的木工和油漆工 咋咋办办？只有租咯。？只有租咯。Hi：王老板，听：王老板，听说说近来家具生意好惨了，近来家具生意好惨了，也帮帮兄弟我哦也帮帮兄弟我哦!家具生意家具生意还还真真赚钱赚钱，但，但 是是现现在的手机生意在的手机生意这这么好，么好，不如干脆把我的木工和油漆不如干脆把我的木工和油漆工租工租给给他，又能他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量，好商量。只是好商量。只是.王王 老老 板板李李 老老 板板4线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论王老板的王老板的家具生家具生产产模型模型：x1、x2是桌、椅生是桌、椅生产产量。量。Z是家具是家具销销售售总总收入（收入（总总利利润润）。）。max Z=50 x1+30 x2s.t.4x1+3x2 120（木工）木工）2x1+x2 50（油漆工）（油漆工）x1，x2 0原始原始线线性性规规划划问题问题，记为记为（P）王老板的王老板的资资源出租模型源出租模型：y1、y2单单位木、漆工出租价格。位木、漆工出租价格。W是是资资源出租租金源出租租金总总收入。收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1，y2 0对对偶偶线线性性规规划划问题问题，记为记为（D）5线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 王老板按（王老板按（D）的解）的解 y1、y2出租其出租其拥拥有的木、漆工有的木、漆工资资源，既保源，既保证证了自了自己不吃己不吃亏亏（出租（出租资资源的租金收入并不低于自己生源的租金收入并不低于自己生产时产时的的销销售收入），又使售收入），又使得出租价格得出租价格对对李老板有极大的吸引力（李老板所付出的李老板有极大的吸引力（李老板所付出的总总租金租金W最少）。最少）。按按按按时时时时下最流行的一个下最流行的一个下最流行的一个下最流行的一个词词词词，叫什么来着，叫什么来着，叫什么来着，叫什么来着6线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论中美佳公司利用中美佳公司利用该该公司公司资资源生源生产产两种家两种家电产电产品品时时，其，其线线性性规规划划问题为问题为将其称将其称为为原始原始问题问题，记为记为P 对应对应第一个第一个约约束条件束条件 对应对应第一个第一个约约束条件束条件（P）max Z=2X1+X2 5X2 15 对应对应第一个第一个对对偶偶变变量量 y1 6X1+2X2 24 对应对应第二个第二个对对偶偶变变量量 y2 X1+X2 5 对应对应第三个第三个对对偶偶变变量量 y3 X1，X2 07线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 下面我下面我们们从另一角度提出一个新的从另一角度提出一个新的问题问题。这这个个问题问题我我们们将其称将其称为为原始原始问题问题的的对对偶偶问题问题，记为记为D（D）min w=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1，y2，y3 08线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对称形式下称形式下对对偶偶问题问题的一般形式的一般形式 项项目目原原问题问题对对偶偶问题问题AbC目目标标函数函数约约束条件束条件决策决策变变量量约约束系数矩束系数矩阵阵约约束条件的右端束条件的右端项项向量向量目目标标函数中的价格系数向量函数中的价格系数向量max Z=CXAX bX 0其其约约束系数矩束系数矩阵阵的的转转置置目目标标函数中的价格系数向量函数中的价格系数向量约约束条件的右端束条件的右端项项向量向量min W=YbAY CY 09线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 非非对对称形式下称形式下对对偶偶问题问题的一般形式的一般形式 原始（原始（对对偶偶）对对偶（偶（原始原始）关系表）关系表项项目目原原问题问题（对对偶偶问题问题）对对偶偶问题问题（原（原问题问题）目目标标函数函数类类型型maxmin目目标标函数系数与右函数系数与右边项边项的的对应对应关系关系目目标标函数各函数各变变量系数量系数对应约对应约束条束条件右件右边项边项的系数的系数右右边项边项的系数的系数对应对应目目标标函数系函数系数数变变量个数与量个数与约约束条件个数的束条件个数的对对应应关系关系变变量个数量个数 n约约束条件个数束条件个数 m约约束条件个数束条件个数 n变变量个数量个数 m原原问题变问题变量量类类型与型与对对偶偶问题约问题约束条件束条件类类型的型的对应对应关系关系 0变变量量类类型型 0 自由自由 约约束条件束条件类类型型 =原原问题约问题约束条件束条件类类型与型与对对偶偶问问题变题变量量类类型的型的对应对应关系关系 约约束条件束条件类类型型 =0 变变量量类类型型 0 自由自由10线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论对对偶偶问题问题的基本性的基本性质质1.对对称性称性原始原始问题问题与与对对偶偶问题问题是两个互是两个互为对为对偶的偶的问题问题。2.弱弱对对偶性偶性两个两个问题问题的可行解的可行解对应对应的目的目标标函数函数值值互互为为上下界。上下界。3.最最优优性性两个两个问题问题最最优优解的目解的目标标函数函数值值必相等。必相等。4.强强对对偶性偶性两个两个问题问题都有可行解都有可行解时则时则两个两个问题问题必都有最必都有最优优解。解。5.互互补补松弛性松弛性两个两个问题问题最最优优解中，一个解中，一个问题问题中某个中某个变变量取量取值值非零，非零，则该变则该变量在量在对对偶偶问题问题中中对应对应的某个的某个约约束条件必束条件必为紧约为紧约束；反之，如果束；反之，如果约约束条件束条件为为松松约约束，束，则则其其对应对应的的对对偶偶变变量一定取量一定取值为值为零。因此，零。因此，该该定定理又称理又称为为松松紧紧定理。定理。11线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论原原问题问题与与对对偶偶问题问题解的解的对应对应关系表关系表问题问题与解的状与解的状态态对对偶偶问题问题有最有最优优解解无界解无界解无可行解无可行解原原问问题题有最有最优优解解一定一定不可能不可能不可能不可能无界解无界解不可能不可能不可能不可能可能可能无可行解无可行解不可能不可能可能可能可能可能12线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶问题问题解的解的经济经济解解释释影子价格影子价格 我我们们已已经经明白原始明白原始线线性性规规划与划与对对偶偶线线性性规规划之划之间间形式上的形式上的对对偶以及他偶以及他们们的解之的解之间间的关系，那么的关系，那么对对偶偶问题问题的解除了前面引例中提到的租金的解除了前面引例中提到的租金这这种种经经济济含含义义外其深刻的外其深刻的经济经济含含义义是什么呢？是什么呢？13线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶问题问题解的解的经济经济含含义义分析：分析：从从单纯单纯形法的矩形法的矩阵阵描述中，目描述中，目标标函数取函数取值值 Z=CBB-1 b，和和检验数数CN -CBB-1N 中都有乘子中都有乘子 Y=CBB-1。设B是是 max Z=CX|AX b，X 0 的最的最优基矩基矩阵，由，由强对对偶偶定理知定理知 Z*=CX*=CBB-1b=Y*b=W*由此由此 Z*b Z*bi （Y*b）bi=CBB-1=Y*或或=yi*14线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶问题问题解的解的经济经济含含义义：由上面分析由上面分析对对偶偶问题问题解中解中变变量量 yi*的的经济经济含含义义是在其他条件不是在其他条件不变变的情况下，的情况下，单单位第位第 i 种种“资资源源”变变化所引起的目化所引起的目标标函数最函数最优值优值的的变变化。所以，化。所以，yi*描述了原始描述了原始线线性性规规划划问题问题达到达到最最优时优时（各种（各种“资资源源”都都处处于于最最优优的配置的配置时时），第，第 i 种种“资资源源”的某种的某种“价价值值”，故称其，故称其为为第第 i 种种“资资源源”的的影子价格。影子价格。下面下面图图解解阐阐述影子价格的直述影子价格的直观观含含义义：15线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 影子价格影子价格 我我们们首先采用首先采用单纯形法求解得形法求解得王老板的家具生王老板的家具生产产模型模型（P）的最的最优解、解、最最优基矩基矩阵如下如下（P）的最的最优解解为X*=（15，20，0，0）TB=（p2，p1）=34412（D）的最的最优解解为Y*=CBB-1=（5，15）CB=（C2，C1）=（30，50）B-1=1 -2-1/2 3/2 16线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 影子价格影子价格王老板的家具生王老板的家具生产产模型的模型的图图解：解：x1x2D可行域可行域1350=50 x1+30 x2（15，20）（P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 02x1+x2=504x1+3x2=120L0：50 x1+30 x217线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 影子价格的直影子价格的直观观含含义义：x1x24x1+3x2=1202x1+x2=50 L0：50 x1+30 x2 D可行域可行域（P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 02x1+x2=51 4x1+3x2=1211365=50 x1+30 x21355=50 x1+30 x218线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 影子价格的特点：影子价格的特点：影子价格是影子价格是对对偶解的一个十分形象的名称，它既表明偶解的一个十分形象的名称，它既表明对对偶解是偶解是对对系系统统内部内部资资源在当前的源在当前的最最优优利用配置下利用配置下的一种客的一种客观观估价，又表明它是一种虚估价，又表明它是一种虚拟拟的价格（或价的价格（或价值值的影象）而不是真的影象）而不是真实实的价格。的价格。特点特点1、影子价格是影子价格是对对系系统资统资源的一种源的一种内部最内部最优优估价估价，只有当系，只有当系统统 达达到最到最优优状状态时态时才可能才可能赋赋予予资资源源这这种价种价值值。特点特点2、系系统资统资源的一种源的一种动态动态价格体系价格体系，影子价格的大小与系影子价格的大小与系统统的价的价值值取向有关，并受系取向有关，并受系统统状状态变态变化的影响。系化的影响。系统环统环境的任何境的任何变变化都可能会引起化都可能会引起影子价格的影子价格的变变化。化。19线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 影子价格的特点：影子价格的特点：特点特点3、影子价格的大小客影子价格的大小客观观地反映地反映资资源在系源在系统统内的内的稀缺程度稀缺程度。如果。如果某种某种资资源在系源在系统统内供大于求，尽管它有内供大于求，尽管它有实实实实在在的市在在的市场场价格，但它在系价格，但它在系统统内的内的影子价格却影子价格却为为零，而影子价格越高，零，而影子价格越高，资资源在系源在系统统内内越越稀缺。稀缺。特点特点4、影子价格是一种影子价格是一种边际边际价价值值，其与，其与经济经济学中的学中的边际边际成本的概念相成本的概念相同。因而，在同。因而，在经济经济管理中十分重要的管理中十分重要的应应用价用价值值。企。企业业管理者可以根据管理者可以根据资资源源在企在企业业内部的影子价格的大小决定企内部的影子价格的大小决定企业业的的经营经营策略。策略。特点特点5、对对偶解准确的偶解准确的经济经济意意义义与与线线性性规规划模型的构造方法有关，模划模型的构造方法有关，模型构造方法的不同有型构造方法的不同有时时会会导导致致对对偶解的不同偶解的不同经济经济解解释释。20线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶单纯单纯形法思路形法思路max Z=2x1+x2s.t.x1+x2+x3=5 2x2+x3 5 4x2+6x3 9 x1，x2，x3 0max Z=2x1+x2s.t.x1+x2+x3 =5 2x2+x3+x4 =5 4x2+6x3 -x5=9 x1，x2，x3，x4，x5 0准典式：准典式：max Z=-1x2-2x3s.t.x1+x2+x3 =5 2x2+x3+x4 =5 -4x2-6x3 +x5 =-9 x1，x2，x3，x4，x5 0标标准化准化化化典典式式21线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶单纯单纯形法思路形法思路 对对偶偶单纯单纯形法基本思路：形法基本思路：如果如果线线性性规规划原划原问题标问题标准化之后不能准化之后不能简单简单得出一个初始基可行解（典得出一个初始基可行解（典式），但却能容易得到式），但却能容易得到该问题该问题的的对对偶偶问题问题的一个初始基可行解（准典式），的一个初始基可行解（准典式），此此时时我我们们就可以通就可以通过过保持保持对对偶基可行解的可行性的方法偶基可行解的可行性的方法进进行迭代，逐步消行迭代，逐步消除原除原问题问题基本解的不可行性，最基本解的不可行性，最终终，当，当对对偶基可行解迭代到偶基可行解迭代到对对偶最偶最优优解的解的同同时时原原问题问题也得到了最也得到了最优优的基可行解。的基可行解。22线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划的划的对对偶理偶理论论 对对偶偶单纯单纯形法的形法的计计算方法算方法基基解解 X1 X2 X3 X4 X5X1X4X555-9 1 1 1 0 0 0 2 1 1 0 0 -4 -6 0 1检验检验数数 0 -1 -2 0 0比比值值 -1/4 1/3 -基基解解 X1 X2 X3 X4 X5X1X4X211/4 1/2 9/4 1 0 -1/2 0 1/4 0 0 -2 1 1/2 0 1 2/3 0 -1/4检验检验数数 0 0 -1/2 0 -1/4比比值值 迭迭代代准典式：准典式：max Z=-1x2-2x3s.t.x1+x2+x3 =5 2x2+x3+x4 =5 -4x2-6x3 +x5 =-9 x1，x2，x3，x4，x5 023线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）灵敏度分析灵敏度分析24线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析 敏感性分析的重要性在于向决策者提供敏感性分析的重要性在于向决策者提供线线性性规规划划问题问题的最的最优优解所能适解所能适应应的的环环境条件境条件变变化的范化的范围围，环环境条件境条件变变化化时时可能可能对经营对经营状况状况带带来何种影响，来何种影响，产产生影响后的解决途径。生影响后的解决途径。敏感性分析的敏感性分析的类类型：型：1、模型中各个模型中各个参数在什么范参数在什么范围变围变化化时时，最，最优优基不基不发发生改生改变变。2、模型中模型中参数参数变变化已化已经经超出上述范超出上述范围时围时，如何快速确定新的最，如何快速确定新的最优优 基和基和最最优优解解新的最新的最优优决策方案。决策方案。敏感性分析的方法：敏感性分析的方法：敏感性分析方法的关敏感性分析方法的关键键是从是从单纯单纯形法形法对应对应的的 I 表表中参数的中参数的变化来分析化来分析B 表表中中对应参数的参数的变化情况来回答决策者所关心化情况来回答决策者所关心问题。25线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析 线线性性规规划原划原问题单纯问题单纯形法形法对应对应的的 I 表表中参数的中参数的变化将引起化将引起B 表表中中对应参数的参数的变化情况表：化情况表：原原问题问题对对偶偶问题问题结论结论或或继续计继续计算的步算的步骤骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题问题的最的最优优解或最解或最优优基不基不变变可以用可以用单纯单纯形法形法继续继续迭代求最迭代求最优优解解可以用可以用对对偶偶单纯单纯形法形法继续继续迭代求最迭代求最优优解解引引进进人工人工变变量，量，编编制新的制新的单纯单纯形表重新形表重新计计算算26线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析一、分析一、分析 C 的的变变化化 当当 Ci 是基是基变变量量 Xi 的目的目标标系数系数时时，若要保持最，若要保持最优优解不解不变变，则则必必须满须满足：足：CN CB B-1 0-CB B-1 0基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1 -CB B-1对应对应I 式式的的单纯形表形表 I 表表对应对应B 式式的的单纯形表形表 B 表表27线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析一、分析一、分析 C 的的变变化化 当当 Cj 是非基是非基变变量量 Xj 的目的目标标系数系数时时，若要保持最，若要保持最优优解不解不变变，则则必必须满须满足：足：CN CB B-1 0基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1 -CB B-1对应对应I 式式的的单纯形表形表 I 表表对应对应B 式式的的单纯形表形表 B 表表28线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析二、分析二、分析 b 的的变变化化当当I 表中表中b变变化化为为b时时，在，在B 表中将只有解列表中将只有解列B-1b发发生生变变化，化，为为保保证证最最优优基基不不变则变则必必须满须满足：足：B-1b 0基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1 -CB B-1对应对应I 式式的的单纯形表形表 I 表表对应对应B 式式的的单纯形表形表 B 表表29线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析三、分析增加一个新三、分析增加一个新变变量量 Xj 的的变变化化 30线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析四、分析参数四、分析参数 aij 的的变变化化31.线线性性规规划划问题问题的参数的参数变变化灵敏度分析化灵敏度分析 灵敏度（敏感性）分析灵敏度（敏感性）分析五、分析新增加五、分析新增加约约束条件的束条件的变变化化 线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）32线线线线性性性性规规规规划划划划 Linear Programming Linear Programming（LPLP）第一章第一章结结束束谢谢谢谢！33