线性规划问题的对偶与灵敏度分析.ppt

第三章 线性规划问题的对偶与灵敏度分析1本章内容重点v线性规划的对偶问题概念、理论及经济意义v线性规划的对偶单纯形法v线性规划的灵敏度分析2线性规划原问题线性规划原问题 例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）15001500250025003 对偶问题若上问题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？设 y1,y2,y3 分别为每工时设备 A、B、C 的收取费用。4原问题原问题 Max z=1500 x1+2500 x2 s.t.3x1+2x2 65 2x1+x2 40 3x2 75 x1,x2 0对偶问题对偶问题Min f=65y1+40y2+75y3 s.t.3y1+2y2 1500 （不少于甲产品的利润）2y1+y2+3y3 2500 （不少于乙产品的利润）y1,y2,y3 05 2、对偶定义 对称形式：互为对偶 (LP)Max z=cTx (DP)Min f=bTy s.t.Ax b s.t.AT yc x 0 y 0 “Max-”“Min-”6 一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。7 (2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。8非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；9（3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式 下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+a1nxn=b1 那么，这个等式与下面两个不等式等价10这样，原规划模型可以写成11此时已转化为对称形式，直接写出对偶规划这里，把 y1看作是 y1=y1-y1，于是 y1 没有非负限制，关系（2）的说明完毕。12 例 写出下面线性规划的对偶规划模型解 先将约束条件变形为“”形式13 再根据非对称形式的对应关系，直接写出对偶规划1415对偶性定理设有一对互为对偶的线性规划A为mn阶矩阵，A的秩为m16引入松弛变量xs，得到原规划(P)的标准型为(P1)其中01和I分别为m维的零向量和m维的单位矩阵 17则上面的标准型可以表示为(P2)其中02为m+n维零向量18设B为一可行基得到模型P2的另一表达形式19记为非基变量检验数的向量表达式由于基变量的检验数为零，所以全部检验数的向量形式可记为20可行基B对应的基本可行解为x0的目标函数值为21定理3-1(弱对偶定理)设 分别为原规划(P)和对偶规划(D)的可行解，则 证：证：因为因为 是原规划可行解，且是原规划可行解，且 所以有所以有又因为又因为 是对偶规划的可行解，且是对偶规划的可行解，且 所以有所以有所以所以这这一一性性质质说说明明了了两两个个线线性性规规划划互互为为对对偶偶时时，求求最最大大值值的的线线性性规规划划的的任任意意目目标标值值都都不不会会大大于于求求最最小小值值的的线线性性规规划划的的任任一一目目标标值值，不不能能理理解解为为原原问问题题的的目目标标值值不不超超过过对对偶偶问问题题的的目标值目标值22推论1设 分别为原规划(P)和对偶规划(D)的可解，当 时，分别是两个问题的最优解证明，由定理可知，对于线性规划(D)的任一可行解y。都有 ，因此 是线性规划(D)的最优解，类似的，可以证明 是线性规划(P)的最优解2324v例例3.4 试用对偶理论判断下面线性规划是否有最优解试用对偶理论判断下面线性规划是否有最优解25v解此线性规划存在可行解 ,其对偶规划为 此线性规划没有可行解，因此原规划没有最优解2627v解此线性规划存在可行解 ,其对偶规划为此线性规划存在可行解因此原规划存在最优解28v定理 若原规划(P)有最优解，则对偶规划(D)也有最优解，反之亦然，并且两者的目标函数值相等v证明:考虑原规划(P)的标准型(P2)设 B为模型P2 的最优解，现在证明对偶规划D也有最优解。由单纯形法可知，此时29v令，则有因此，为对偶规划(D)的可行解。另一方面其中为原规划的最优解。由推论1可知为对偶规划(D)的最优解30v类似的，若对偶规划(D)有最优解，则原规划(P)也有最优解v从定理可以看到，对偶规划(D)的最优解 可以在原规划(P)的检验数 中得到 由于 的后m列为单位矩阵，的后m个分量为031v对偶规划(D)的最优解是原规划(P)的最优解的检验数中松弛变量对应检验数的相反数。3233基变量v解 引入松弛变量x4,x5将模型化为标准型，经求解后得到其最优单纯形表34v由此表可知，原问题的最优解为x*=(0,25,25)T 最优值为250.表中两个松弛变量的检验数分别为-1/2,-2,由上面的分析可知，对偶问题的最优解为 (1/2,2)T35影子价格363738 影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进39（2）影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划P和对偶规划D的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是4041 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义(2)，是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。424344v现在公司有另外一笔资金585元，进行投资，利用影子价格分析，应如何进行投资使公司获得更多利润？由上表可知，仓库的影子价格y2=1/9，即为增加1m3的仓库空间，可获利润1/9元。现在已知增加1m3的仓库需要元，即每投资元，可多获利1/9元。也就是每投资一元，可多获利润10/72元。45v仓库的影子价格y1=11/45，即为增加1元的购买产品，可获利润11/45元。v通过比较分析，应该将投资用于购买产品A1，A2 将585元进行投资，最大利润为 588*11/45=143元46v这一增量值，我们可以对改变条件的新模型的求解结果得到，新模型为v最优解为v总利润为533，利润增量为533-390=143元47 对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基基本本解解出发，此基本解不一定可行，但它对应着一个对对偶偶可可行行解解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。对偶单纯形法对偶单纯形法48 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性(即检验数非正)，使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。49 对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。50v1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若基本解所有分量皆非负,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,若有akj0 则选 =minj/akjakj0=r/akr那么 xr为进基变量,转4；4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程：51单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法52v例 用对偶单纯形法求解下面线性规划v解:(1)引入松弛变量x3,x4,x5化为标准型，并在约束等式两侧同乘以-1得到：53vx3,x4,x5化为基变量，此式为典式形式，并且检验数均为非正，因此可构造初始对偶单纯形表为54初始表中基本解的三个分量小于零，不是可行解，需要迭代求解新的基本解(2)定x4 为出基变量，按对偶 规则计算取x2为进基变量55v(3)以a22=-3为中心元素，进行迭代，迭代后的检验数仍保持非正v(4)经检验，上表仍需迭代，取x3 为出基变量56vx1 为出基变量，以a11=-5/3为中心进行迭代，这样就可以得到原规划的最优解 (3/5,6/5,0,0,11/5)T57v例 用对偶单纯形法求解下面线性规划58v解：59对偶单纯形法的适用范围 适合于解如下形式的线性规划问题在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。60 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。61灵敏度分析v以前讨论线性规划问题时，假定系数都是常数。但实际上这些系数往往是估计值和预测值。v因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。62v显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。v当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。v在灵敏度分析采用的办法，是从已得到的最优解出发，通过对数据进行一些简单的计算，便可迅速得到所需要的结果以及变化后的最优解。因此，灵敏度分析也称优化后分析63v考虑下面的线性规划模型v其向量形式为64v我们先给出一些矩阵的表达式：1.检验数的向量表示B为可行基 为系数矩阵A的第j列向量 cB,cB分别为基变量和非基变量的目标函数系数向量65v 的展开形式为检验数的向量表示令662.基本解的矩阵表示B对应的典式基本解的矩阵表示对应的目标函数的值为67v研究最优解受数据变化的影响情况主要考虑两个方面：1.是解的最优性，即检验数是否仍然非正2.是解的可行性，即基本解的各个分量是否非负68目标函数系数的变化v设只有一个系数cj变化，其它系数均保持不变，仅仅影响到检验数的变化v1.ck是非基变量的系数v2.ck是基变量的系数691.ck是非基变量的系数v根据检验数的向量表示非基变量的系数ck的变化只影响与ck有关的检验数，所以只考虑 设ck的变化为ck，此时 的改变量为 70v为了保持最优解不变，必须满足即为为ck的变化上限当ck的变化超过此上限时，最优解发生变化，应求出新的检验数的值，继续迭代求新的最优解712.若 cl 是基变量的系数：设cl变化为cl+cl那么，引入m维向量 72v其中 为构成 的第l个分量 为了使最优解保持不变，要保证n-m个 ，则需要为了保持最优解不变的 的变化范围73当 超过此范围，应该求出n-m个新检验数 ，继续迭代求新的最优解747576v解(1)c3 是非基变量的目标系数当 时，最优解保持不变也就是说，当第三种产品的单位利润小于等于时，不宜安排生产，只有在利润大于元时候，生产第三种产品才有利润 时，此时 77v以x3为进基变量进行迭代，求最优解最优解为(0,1000/9,200/9)T,最优值为78v这说明，当c3变为20后，应生产第二和第三种产品，并且最大利润增加了17元(2)c1是基变量系数为了保持最优解不变，应使下列不等式成立79v解出v由于c1=20，为了保持最优解不变，应该有 当 超过此范围，就会使检验数 中的某一个大于零，此时要取相应的变量进行迭代，求最优解 例如当80v，不满足最优性准则，所以，应将所求的检验数去替换原检验数，并以x5为进基变量迭代，求新的最优解81v新的最优解为(75,0,0)T,最优值为1875.这说明当c1变为25后，只生产第一种产品，最大利润为1875元8283848586v解:最优解xB和B-1的值为设 ，为了保持最优解不变，应使下式成立87v整理后得 在此范围内，最优基保持不变当 ，最优基不变新的最优解为88v当，最优基将发生变化，所以进行新的迭代求最优解，基变量的值变为其中出现了负分量，破坏了解的可行性需要用新的解替换原来的解，用对偶单纯形法迭代89得到的新最优解为(400,0,0)T90约束条件中的系数变化v假设只有一个aij变化，其它数据不变，并且只讨论 aij为非基变量xj系数的情况，此时，aij的变化只影响一个检验数v设此时 ，为改变量v检验数的另一种表示方式9192v其中y为对偶最优解，为y的第i个分量 为了使最优解不变，要使93增加新变量的分析v例3.13 在例中，企业考虑将一种新产品投入生产，这种新产品每件分别需要在第一种，第二种设备上加工的时间为10h和，试分析新产品的利润为多少，生产该产品对企业有利？v解 (1)设新产品的产量为 ，单位利润为 94v(2)计算检验数当 ，不影响原最优解，不宜生产当 ，可以考虑将 作为进基变量，迭代求新解95v(3)设 ，此时 ，考虑迭代。计算将这个结果及检验数作为新的一列填在新表中，继续迭代96新的最优解为生产新产品10件及第二种产品125件97增加一个约束条件v例3.14 在例中，企业关心当电力供应限制为多少时，不会影响已得到的最优解？已知生产3种产品每件需要消耗电力分别为20kw，10kw，19kw。解 设电力限制为b3，可得到新的约束条件为 增加松弛变量x6化为等式约束98v在原来的表上，将新的约束条件考虑进去，增加一个新行和一个新列，并指定x6为新增加的基变量由于x1和x2为基变量，应将a31和a32的元素利用初等变换，变为零99从上表可以看出，影响最优解变化的只有令，可得到保持最优解不变的电力限制当电力供应大于等于1500kw时，企业不用改变原有最优生产方案，当电力供应小于1500kw时，企业需改变原有生产方案100