第二章线性对偶理论和灵敏度分析

第2章线性规划的对偶理论与灵敏度分析2.1线性规划的对偶问题因此有:MaxMin原问题（LP1）对偶问题（LP2）任何线性规划问题都有对偶问题，且都有相应的经济意义。二、对称形式下对偶问题的一般形式满足下列条件的线性规划问题称为具有对称形式：（1）变量均具有非负约束（2）约束条件当目标函数求极大值时均取“≤”号（3）约束条件当目标函数当求极小值时均取“≥”号对称形式下线性规划原问题的一般形式为：

用yi

(i=1,…,m)代表第i种资源的估价，则其对偶问题的一般形式为：用矩阵形式表示MaxMin原问题：对偶问题：对偶问题的对偶即是原问题！例：对偶问题

Min令可改写为Max将它作为原问题，写出其对偶对偶问题：Min再令可改写为Max三、非对称形式的原-对偶问题关系例：求下面非对称形式规划问题的对偶问题Max(A)(B)(C)(D)（1）约束(B)先转换成两个约束条件解：先转换成对称形式，再写出对偶问题再转换为（2）约束(C)两端乘以（-1）得到（3）约束(D)中，令此时原问题转换成了如下对称形式：Max对偶变量设定对偶变量后，按表1写出对偶问题如下Min(E)(F)(G)(H)令且(F)式两端乘(-1)得Min总结：原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数最大化（MaxZ)目标函数最小化（Minw)n个变量n个约束m个约束m个变量约束条件限定向量（右边项）目标函数价值向量（系数）目标函数价值向量约束条件限定向量（右边项）(参考运筹学教程表2-2)写出下列问题的对偶问题：MinMaxïïîïïí죳-³-+-=-+-£+-无约束321321321321,0,0832353410..xxxxxxxxxxxxts2.2对偶问题的基本性质

本节基本性质讨论先假定原问题和对偶问题为对称形式线性规划问题，即：原问题：对偶问题：一、单纯形法的矩阵描述对称形式线性规划问题加上松弛变量Xs后得到：

单纯形法计算时，总选取I为初始基，对应基变量为Xs,设迭代若干步后基变量为XB，XB在初始单纯形表中的系数矩阵为B。N为A去掉B后剩余列构成的矩阵。CB和CN是与B和N对应的检验数。则初始单纯形表可表示为：非基变量基变量基XBXNXs0XsbBNIcj-zjCBCN0迭代后得到最终单纯形表如下表所示。（1）初始表中基变量对应的系数矩阵I，在最终表中变为B-1（2）初始表中基变量为Xs=b，最终表中基变量为XB=B-1b（3）初始表中的系数矩阵B和N，在最终表中变为I和B-1N（4）最终表中基变量XB的检验数全为0，XN、Xs的检验数分别变为CN-CBB-1N和-CBB-1非基变量基变量基XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1min对偶变量y1y2y3对偶变量x1x2原问题P：对偶变量y1y2y3对偶问题D：例：原-对偶问题的变量与解的对应关系（分别加上松弛变量与剩余变量）max解：用单纯形法求解下面问题（原问题）cj→21000CB基bx1x2x3x4x50x315051000x424[6]20100x5511001cj-zj21000线性规划对偶理论的主要基本定理：1.弱对偶性：设X和Y分别是原问题P和对偶问题D的可行解，则CX≤bTY。推论1：P有最优解的充要条件是D有最优解；推论2：若P无界则D无可行解，若D无界则P无可行解；2.最优性：若X*和Y*分别是P和D的可行解，则它们分别为P和D的最优解的充要条件是CX*=Y*b3.强对偶性：若P和D均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。4.互补松弛性：获得最优解时，若对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式，反之若该约束条件为严格不等式，则对应对偶变量为零。二、对偶问题的基本性质2.3影子价格（对偶解的经济学解释）bi：原问题约束条件右端项，代表第i种资源拥有量；对偶变量yi*：资源最优利用下对每个单位的第i种资源的估价（非市场价格，是对最优方案的贡献值），特称为影子价格（shadowprice）；

当线性规划问题取得最优解xj*时，其对偶问题也取得最优解yi*，代入各自目标函数后相等：（1）资源的市场价格围绕实际价格波动，比较稳定。影子价格则取决于资源的利用情况，它会随不同企业或同一企业不同生产任务、不同产品结构而不同。（2）影子价格是一种边际价格。影子价格yi*的理论值等于资源得到最优利用的生产条件下，第i种资源拥有量bi每增加一个单位时目标函数z的增量。0x1x2(3,3)(7/2,3/2)’’(15/4,5/4)例：最优解(7/2,3/2),目标函数z*=17/2若第二约束条件b2增加1，即25，最优解变为(15/4,5/4),目标函数z*=35/4,目标函数增量为1/4,故第二种资源的边际价格（影子价格）为1/4。同理，b3增加1，最优解(3,3),目标函数增量(边际价格)为1/2（3）资源的影子价格实际上也是一种机会成本，当某资源的市场价格低于资源成本加上其影子价格时，可以买入，当资源的市场价格高于资源成本加上其影子价格时，可以卖出。（4）当某种资源bi未得到充分利用时，它的影子价格为零，当影子价格不为零时，该资源在生产时已耗费完毕。（5）一个企业可借助影子价格确定有限资源的内部结算价格，以控制有限资源的使用。社会上对一些紧缺资源可借助影子价格确定使用一个单位资源必须上交的利润，以控制一些效益低的企业自觉节约使用紧缺资源，使紧缺资源发挥更大的经济效益。一、对偶单纯形法的基本思路（1）单纯形法思路：对原问题的一个基可行解（此时所有右端项bi≥0），判别是否所有的检验数σj≤0。若是且基变量中无人工变量，即找到了问题的最优解；若否，再找出相邻的目标函数值更大的基可行解，继续判断检验数，直到找到最优解（如果存在）。（2）根据对偶原理性质可知，在同一个单纯形表中，如果原问题为可行解（此时所有右端项bi≥0），且所有检验数σj≤0，则原问题和对偶问题都达到最优解。2.4对偶单纯形法（3）对偶单纯法的基本思想是：先找出对偶问题的基可行解（单纯形表中所有的检验数σj≤0），若此时原问题为非可行解（即不满足所有右端项≥0），则一直保持对偶问题为可行解的条件下，利用对偶单纯法进行迭代，一直到原问题也为可行解（即满足所有右端项≥0），这时也就同时得到了原问题和对偶问题的最优解。注意：对偶单纯形法是利用对偶原理求解原问题的一种方法，而不是求解对偶问题解的单纯形法。（1）对于线性规划问题，列出初始单纯形表，要求所有的检验数σj≤0，但b列不要求全为非负（即≥0）；若b列的数字全为非负，则已得到最优解；若不全为非负则转下一步；（2）确定换出基变量xr；（3）确定换入基变量xs；

(xs必须是arj<0对应的非基变量,ars为主元素

)（4）用换入变量替代换出变量，得到一个新的基，根据单纯形法更新表中数据，检查所有b列数字是否都为非负，是得到最优解，否则返回第2步继续迭代，直至求出最优解。二、对偶单纯形法的计算步骤例：MinMaxMax化标准型式：化为对偶单纯法求解形式CBCj-3-500xBbx1x2x3x40x3-4.8[-3]01-1/30-5x21.61/210-1/60cj-zj-1/200-1/12θj1/65/2CBCj-3-500xBbx1x2x3x4-3x11.610-1/31/90-5x20.8011/6-1/45cj-zj00-1/6-7/90最优解为:(1.6,0.8,0,0),zmin=8.8又例：用对偶单纯形法求解下面线性规划问题解：先将问题改写为对偶单纯形法求解形式：列出单纯形表，并用对偶单纯形法求解如下最优解为：(0,1/4,1/2,0,0),wmin=17/2

用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引进人工变量，计算简化。但在初始单纯形表中要求其对偶问题应是基可行解这点，对于多数线性规划问题很难实现。因此，对偶单纯形法一般不单独使用，主要用于灵敏度分析及整数规划等方法中。2.5灵敏度分析一、灵敏度分析的含义是指系统或事物因周围条件变化显示出来的敏感性程度的分析。对于线性规划问题的灵敏度分析是指参数A，b，C变化引起的对原问题最优解的变化的分析。

A为约束系数矩阵，b为资源向量，C为价值系数向量参数变化后的问题要重新用单纯形法求解？不用。可以把相应的变化反映到最终单纯形表中，观察表中数字变化后，最优解条件是否还满足，不满足再从这个表开始进行迭代计算，求得新的最优解。灵敏度分析的步骤（1）将参数变化通过计算反映到最终单纯形表上；（2）检查原问题是否仍为可行解；（3）检查对偶问题是否仍为可行解；（4）按下表所列情况，得出结论或决定继续计算。-1/21/40017/2x11.5xB-9/41/8000---3/2-1/40103/2x22-15/4[5/4]10015/2x30x5x4x3x2x1bθi00021.5CjCB614cj-zj例2-2：在上例中，(1)若家电I的利润降至1.5元/件,而家电II的利润增至2元/件时,美佳公司最优的生产计划有何变化？(2)若家电I的利润不变,则家电II的利润在什么范围内变化时,则该公司的最优生产计划将不发生变化？解:(1)将家电I、II的利润变化直接反映到最终单纯形表中得：CBCj1.52000xBbx1x2x3x4x50x46004/51-61.5x1210-1/5012X23011/500cj-zj00-1/100-3/2继续迭代后得到下表可知其为最终表,可得出最优解为:X*=(2,3,0,6,0)T,最优目标值Zmax=9CBCj21+a000xBbx1x2x3x4x50x315/20015/4-15/42x17/21001/4-1/21+ax23/2010-1/43/2cj-zj000-1/4+a/4-1/2-3a/2根据最优判别条件,要最优解不变,则:故有:(2)设家电II的利润为(1+a)元，变化到最终单纯形表：解:(1)因有:故:而:（二）bi的变化例2-3：在例2-1中，(1)若设备A和调试工序的每天能力不变,而设备B每天的能力增加到32h,分析公司最优计划的变化？(2)若设备A和B每天可用能力不变,则调试工序能力在什么范围内变化时,问题的最优基不变？CBCj21000xBbx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2cj-zj000-1/4-1/2最终单纯形表的值变化如下：CBCj21000xBbx1x2x3x4x50x315051002x15110010x420-401-6cj-zj0-100-2

因上表中原问题为非可行解，故用对偶单纯形法继续计算，得到如下表:故美佳公司的最优计划变为只生产5件家电I。当时，问题的最优基不变，解得：-1≤a≤1故调试工序的能力应在4－6h之间。(2)设调试工序每天可用能力为(5+a)h,因有:

增加一个变量，在实际问题中反映为增加一种新的产品。其分析步骤如下：（1）计算检验数（2）计算新增变量对应列向量（3）若检验数≤0，原最优解不变，只需将计算得到的检验数和新增变量对应列向量直接写入最终单纯形表中，若有检验数>0，则按单纯形法继续迭代计算找出最优解。（三）增加一个变量xj的分析解：假设生产该新产品的数量为x6（新增变量），c6＝3，P6=(3,4,2)T，根据步骤，先计算检验数和P’6将其反映到最终单纯形表中得例：上例中，设美佳公司又计划推出新型号的家电III，生产一件所需设备A、设备B以及调试工序的时间分别为3h、4h、2h，该产品预期利润为3元/件，试分析该产品是否值得投产，若投产该公司的最优生产计划有什么变化？CBCj210003xBbx1x2x3x4x5x60x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/2[2]cj-zj000-1/4-1/21有大于零的检验数，继续用单纯形法迭代，最终得到CBCj210003xBbx1x2x3x4x5x60x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40故最优生产计划为每天生产7/2件家电I和3/4件家电III。解：先将生产工时变化后的新家电II看作是一种新产品，生产量为x’2,参考上例的步骤，计算检验数σ’2和新增变量对应列向量P’2，并反映到最终单纯形表中。其中：（四）分析参数aij的变化例2-4：在例2-1中，若家电II每件需须设备A，B和调试工时变为8h、4h和1h，该产品的利润变为3元/件，试重新确定美佳公司最优生产计划。CBCj213000xBbx1x2x’2x3x4x50x315/20011/215/4-15/22x17/2101/201/4-1/21x23/201[1/2]0-1/43/2cj-zj003/20-1/4-1/2CBCj23000xBbx1x’2x3x4x50x3-90014-242x121001/2-23x’23010-1/23cj-zj0001/2-5

因x2已变换为x’2，故上表用x’2替换基变量x2(非θ最小规则)并在下一个表中不再保留x2

，得：

上一步的表中原问题与对偶问题均为非可行解，故先设法使原问题为可行解。表中第一行约束为：替换上表的第一行，重新计算检验数得:两端乘(-1)再加上人工变量x6得:92446543xxxx=++--9244543xxx-=-+CBCj23000-MxBbx1x’2x3x4x5x6-Mx6900-1-4[24]12x121001/2-203x’23010-1/230cj-zj00-M1/2-4M-5+24M0CBCj23000-MxBbx1x’2x3x4x5x60x53/800-1/24-1/611/242x111/410-1/121/601/123x’215/8011/800-1/8cj-zj00-5/24-1/30-M+5/24用单纯形法继续求解，得

由最终单纯形表得知，美佳公司的最优生产计划为每天生产11/4件家电I和15/8件新家电II。（五）增加一个约束条件的分析增加一个约束条件相当于增加一道工序。分析方法：将原问题最优解变量代入新增约束条件中，若满足则条件原问题最优解不变，若不满足则将新增条件直接反映到最终单纯形表中再进一步分析求解。例2-5：在例2-1中，设家电I、II经调试后，还需经过环境试验工序。环境试验约束条件为3x1+2x2≤12。家电I每件需