运筹学 对偶理论和灵敏度分析学习课件

对偶理论和灵敏度分析OperationsResearch,Autumn2017,C.-J.Chang对偶问题的提出什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。EX.在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。周长一定，面积最大的矩形是正方形。面积一定，周长最短的矩形是正方形。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。23对偶问题的提出以例2-1来看对偶角度的表述。分析获益状况来追求利润最大化

评估生产投入来获得成本最小化(资源消耗最少)看似不同，但却是同一件事原问题与对偶问题的关系对于同一数据集(a,c,b)，可以用“≤”不等式约束条件和目标函数最大化的原问题与“≥”不等式约束条件和目标函数最小化的对偶问题，建立标准的对应关系。4原问题与对偶问题的关系5Ex.对偶问题的转换试求下述线性规划问题的对偶问题。6x1x2b1284016041223

y1y2y3c1402204381612

不熟练时，可以透过系数矩阵的转置进行转换极大化的对偶是极小化随堂练习试求下述标准型式线性规划问题的对偶问题。7大于约束条件对偶问题的变换形式8等式约束条件对偶问题的变换形式9非对称形式的变换关系10大小变(+)约(+)约(+)变(-)Ex.非对称对偶问题的转换试求下述线性规划问题的对偶问题。11大小变(+)约(+)约(+)变(-)随堂练习写出下列线性规划问题的对偶问题。12对偶问题的基本性质对称性：对偶问题的对偶是原问题。弱对偶性：若

是原问题的可行解，

是对偶问题的可行解。则存在。无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。这个性质不存在逆。当原问题(对偶问题)无可行解时，其对偶问题(原问题)具有无界解或无可行解。

13原问题对偶问题无界解无可行解无可行解无界解无界性已知线性规划问题如下，试用对偶理论证明其无最优解(无界解)。14先写出对偶问题由对偶问题的第一个约束条件可知对偶问题无可行解，原问题应为无界解或无可行解。而原问题至少有一可行解X=(0,0,0)T，因此原问题应为无界解(无最优解)。对偶问题的基本性质可行解是最优解时的性质：设

是原问题的可行解，

是对偶问题的可行解，当

时，与是最优解。对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。15原问题与对偶问题解的可能情况两个问题都有最优解，若记为X*和Y*，必有CX*=Y*b一个问题无界，则另一个问题无可行解。两个问题都无可行解。16对偶问题的基本性质互补松弛性：若与分别是原问题和对偶问题的可行解。那么和，当且仅当与为最优解。XS与YS分别代表松弛变量向量与剩余变量向量即上面的每对互乘因子中，一个松(不等于)，另一个必紧(等于)，这就所谓的互补松紧。严格不等式的约束条件所对应的对偶变量必是零；非零的对偶变量所对应的约束条件必是等式。17互补松弛性已知线性规划问题如下，其对偶问题最优解为,

;z=5。试用对偶理论找出原问题的最优解。18先写出对偶问题[2−(4/5+2*(3/5))]=0?≠0≠0≠0=0000?≠0≠0代入所以原问题的最优解为X*=(1,0,0,0,1)T;ω=5找出对偶问题中那些约束条件是严格不等式，其对应的变量为0。代入原问题的约束条件，其应为等式。00随堂练习已知线性规划问题如下，其对偶问题的最优解为,

，试应用对偶问题的性质，求原问题的最优解。19提示：先写出对偶问题。透过互补松弛性求解原问题。X*=(0,0,4,4)T;z=44随堂练习试通过求对偶问题的最优解，来求解下列线性规划问题之原问题的解。20提示：先转换成对偶问题。使用图解法求解对偶问题。透过互补松弛性求解原问题。X*=(1,2,0,0,0)T;z=11Y*=(1,3);ω=11随堂练习试通过求对偶问题的最优解，来求解下列线性规划问题之原问题的解。21提示：先转换成对偶问题。使用图解法求解对偶问题。透过互补松弛性求解原问题。X*=(7/5,0,1/5,0)T;z=19/5Y*=(8/5,1/5);ω=19/5单纯形法的矩阵描述单纯形法的运作方式是由一个初始基可行解，逐步转移至其它基可行解以改善目标函数值，反复运作直到找出最佳解为止。

22每组基可行解都对应一组基，所以求解过程也就是基的转换。既然单纯形运算过程中，转换的是基，那我们是不是可以用基来描绘出单纯形表的一般式。单纯形法的矩阵描述设线性规划问题可以用如下矩阵形式表示：

目标函数maxz=CX

约束条件AX≤b

非负条件X≥0约束条件加入松弛变量后，可得到标准型：

maxz=CX+0Xs

AX+IXs=b

(其中I是m×m单位矩阵)

X,Xs≥0系数矩阵(A,I)可分成基矩阵与非基矩阵(B,N)，问题可改写成：

maxz=CBXB+CNXN

BXB+NXN=b

XB,XN≥023单纯形法的矩阵描述由BXB+NXN=b可得：

BXB+NXN=b→BXB=b−NXN

→XB=B−1(b−NXN)

→XB=B−1b−B−1NXN此时：

z=CBXB+CNXN=CB(B−1b−B−1NXN)+CNXN

=CBB−1b+(CN−CBB−1N)XN令非基变量XN=0，则基变量XB=B−1b，基可行解为(B−1b,0)T，目标函数z=CBB−1b。24这部份就是我们的检验数cj−zj单纯形法的矩阵描述基变量XB非基变量XN等式右边RHS系数矩阵IB−1NB−1b检验数0CN−CBB−1N−CBB−1b25一开始是松弛变量的部份B−1−CBB−1对偶问题的基本性质原问题检验数与对偶问题解的关系。设原问题是

maxz=CX;AX+XS=b;X,XS≥0

对偶问题是

minω=Yb;YA−YS=C;Y,YS≥0

则原问题单纯型表的检验数行对应其对偶问题的一个基解，其对应关系如下表。

这里YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。26原问题XBXNXS检验数0CN−CBB-1N−CBB-1对偶问题YS1−YS2−Y原问题与对偶问题在单形表的判读原问题与对偶问题的目标函数会有相同的最佳值松弛变量(约束条件为≤)：对偶问题的解是cj−zj的相反数。剩余变量(约束条件为≥)：对偶问题的解是cj−zj的值。人工变量(约束条件为=)：对偶问题的解是M−(cj−zj)。约束条件为≥也可由人工变量读出解，从剩余变量与人工变量读出的解会相同。27原问题与对偶问题的解已知某线性规划问题及其最后单形表如下，请分别写出原始问题与对偶问题的解。28cj5040000θiCBXBbx1x2x3x4x540x212018/250-3/250x4800-8/2513/2550x13010-1/501/5cj-zj00-14/50-26/5y4y5y1y2y3所以原问题的最优解为

X*=(30,12,0,8,0)T;z=1980对偶问题的最优解为

Y*=(14/5,0,26/5,0,0);ω=1980随堂练习一线性规划问题之原问题如左下；利用单纯形法解其对偶问题后所得之最后单形表如右下。请分别写出原始问题与对偶问题的解。29cj34000θiCBXBBy1y2y3y4y54y21/5012/5-1/503y18/5101/52/500y59/500-7/51/51cj-zj00-11/5-2/50x4x5x1x2x3所以原问题的最优解为

X*=(11/5,2/5,0,0,0)T;z=28/5对偶问题的最优解为

Y*=(8/5,1/5,0,0,9/5);ω=28/5随堂练习一线性规划问题之原问题如左下；利用单纯形法解其对偶问题后所得之最后单形表如右下。请分别写出原始问题与对偶问题的解。30cj10121200θiCBXBBy1y2y3y4y510y11/410-3/41/4-1/412y27/80119/8-1/85/8cj-zj00-9-1-5所以原问题的最优解为

X*=(1,5,0,0,9)T;z=13对偶问题的最优解为

Y*=(1/4,7/8,0,0,0);ω=13影子价格以例2-1来看

31z=(产品Ⅰ的利润)×(产品Ⅰ的数量x1)+(产品Ⅱ的利润)×(产品Ⅱ的数量x2)ω=(设备的台时)×(y1)+(原材料A数量)×(y2)+(原材料B数量)×(y3)原问题与对偶问题目标函数的最优值相等，量纲也应该一致。对偶变量可理解为每个单位资源的价值(价格)，这就是所谓的对偶价格或影子价格。cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80y1*=1.5,y2*=0.125,y3*=0影子价格的意义影子价格反映资源对目标函数的边际贡献，即资源转换成经济效益的效率。这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。32影子价格的意义影子价格反映了资源的稀缺程度。当某种资源的yi*˃0，表示这种资源短缺。决策者要增加收入，应先增加影子价格高的资源。当某种资源的yi*=0，表示这种资源有剩余，不短缺。影子价格反映出资源的边际使用价值。假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。影子价格就代表此时工厂决策者对每种资源给出的最低定价或附加额。33请先将下列线性规划问题转换成对偶问题，再使用单纯形法求解。(须写出原问题与对偶问题的解)原问题与对偶问题是一体两面的关系，一张单形表可以同时找到原问题与对偶问题的解。那可以不转换成对偶问题，直接用原问题的单形表搭配求解对偶问题的逻辑进行求解吗？随堂练习34对偶单纯形法的思维对偶单纯形法是将对偶问题的思维引入单纯形法用以解决原问题的一种方法。一般单纯形法是从一个基可行解(对偶解为基解)开始进行迭代，目标值逐步上升，进而达到线性规划问题的最优解(此时对偶解为基可行解)。对偶单纯形法则是从一个基解(对偶解为基可行解)开始进行迭代，目标值逐步下降，进而达到线性规划问题的最优解(此时原问题为基可行解)。35对偶单纯形法适合时机可以很容易地得到初始对偶基可行解时B−1b至少存在一个负分量

(≥限制式转换为=限制式时，以松弛变量处理)检验数都为非正(max问题的目标函数系数均为负值)36对偶单纯形法步骤(针对max问题)对线性规划问题进行变换，使列出的初始单纯形表中所有的检验数σj≤0(即对偶问题为基可行解)。检查b列的数字，若都为非负(≥0)，检验数都为非正(≤0)，则已得到最优解；否则应继续计算。确定换出变量。

选取最小负值的bi为换出变量。确定换入变量。

在单纯形表中检查xi所在行的各系数aij。若所有aij≥0，则无可行解，停止计算。若存在aij＜0,则选择正最小比值的(cj−zj)/aij为换入变量。进行迭代计算，得到新的单纯形表，并回到步骤2。37对偶单纯型法用对偶单纯型法求解下列限性规划问题。38先改写问题，以符合初始要求目标函数系数皆为负。等式右边的值至少有一个为负。cj-2-3-400CBXBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301cj-zj-2-3-400建立初始单形表挑选负最多的行1-4/3--挑选出最小比值，分母只考虑aij系数为负的部份(比值计算后为正)[]进行旋转运算39cj-2-3-400CBXBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301cj-zj-2-3-400[]因为b列数字皆≥0，检验数皆为非正，故问题已得到最优解，X*=(11/5,2/5,0,0,0)T，ω*=2×(11/5)+3×(2/5)=28/5Y*=(8/5,1/5,0,0,9/5),目标值为28/51-4/3--cj-2-3-400CBXBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2cj-zj0-4-10-1-8/5--2[]cj-2-3-400CBXBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5cj-zj00-9/5-8/5-1/5一般纯单形法和对偶单纯形法的差异差异项目一般单纯形法对偶单纯形法cj−zj不受正负限制。必须均为负值。bi必须均为非负值。不受正负限制。最优解判断所有(cj−zj)≥0，若有(cj−zj)<0要继续算。所有bi≥0，若有bi<0要继续算。换入变量确定选取最大正值的(cj−zj)为换入变量。选取最小负值的bi为换出变量。换出变量确定只考虑换入变量列中，系数为正的变量为换出变量。换出变量选择正最小比值的bi/aij。

只考虑换出变量行中，系数为负的变量为换入变量。换入变量选择正最小比值的(cj−zj)/aij。运算步骤先确定换入变量，再决定换出变量。先确定换出变量，再决定换出变量。40随堂练习使用对偶单纯型法求解下面的线性规划问题：41X*=(5/2,3/2,0,0)T;z=52X*=(2,2,2,0,0,0)T;z=72X*=(1,2,0,0,0)T;z=11灵敏度分析前面讨论线性规划问题时，假定aij,bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件发生变化，cj值就会变化；aij会因工艺条件的改变而改变；bi则根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化。或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。42灵敏度分析当线性规划问题中某一个或某几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯型表从头计算，以便得到新的最优解。但这样做很麻烦也没有必要。因为单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，再依不同情况处理。43原问题对偶问题结论或继续计算的步骤可行解可行解表中的解仍为最优解可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表，求最优解灵敏度分析资源变量bi的变化可行范围：为了保证基变量非负，bi必须确保b≥0若bi改变使b<0，则须继续运算求最优解。价值系数cj的变化最优范围：为了确保当前解为最优，cj必须确保检验数≤0若cj改变使检验数>0，则须继续运算求最优解。技术系数的变化新增一种产品：新增一列代表新产品，再继续运算求最优解原产品的技术系数发生变化：以新的系数计算最终单形表相应的列向量，以取代原来的变量，并继续运算求最优解。44cjCBCN0CBXBbXBXNXSCBXBB−1bIB−1NB−1cj-zj0CN−CBB−1N−CBB−1灵敏度分析已知线性规划问题的最终单形表如下，试问：当约束条件右端项b1与b3保持不变时，b2在什么范围内变化，最优基会保持不变。当目标函数系数c1保持不变时，c2在什么范围内变动，最优解会保持不变。45cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80资源变量bi的变化46cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80cj23000θiCBXBbx1x2x3x4x50x38121000x416400100x51204001cj-zj最终单纯形表初始单纯形表价值系数cj的变化47cj2c2000θiCBXBbx1x2x3x4x52x141001/400x5400-21/21c2x22011/2-1/80cj-zj00-3/2-1/80最终单纯形表灵敏度分析延续上题，若该厂从其它处抽调4台时用于生产产品Ⅰ与Ⅱ，求这时该厂生产产品Ⅰ、Ⅱ的最优方案。48cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80cj23000θiCBXBbx1x2x3x4x52x141001/400x5-400-21/213x24011/2-1/80cj-zj00-3/2-1/80cj23000θiCBXBbx1x2x3x4x52x141001/400x32001-1/4-1/23x2301001/4cj-zj000-1/2-3/4[]所以最优解为

x1=4,x2=3;z=4×2+3×3=17使用对偶单纯型法继续运算新增一种产品延续前题，若工厂除了产品Ⅰ与Ⅱ外，又开发了一种新产品Ⅲ。已知生产产品Ⅲ需使用设备2台时，原材料A与B各6kg与3kg；每件可获利5元。问该厂是否应生产该产品和生产多少？49cj230005θiCBXBbx1x2x3x4x5xnew2x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/803/221/45/48/328cj230005θiCBXBbx1x2x3x4x5xnew2x11101.5-1/8-3/405xnew200-11/41/213x23/2013/4-3/16-1/80cj-zj00-3/2-7/16-5/80所以最优解为

x1=1,x2=1.5,xnew=2;z=16.5[]技术系数发生变化延续前题，若工厂生产产品Ⅰ的工艺结构有了改进，这时它的技术系数向量变为P1′=(2,5,