韩伯棠管理运筹学(第三版)-第六章-单纯形法的灵敏度分析与对偶

第六章单纯形法的灵敏度分析与对偶•§6.1、单纯形表的灵敏度分析•§6.2、线性规划的对偶问题•§6.3、对偶单纯形法•§1．单纯形表的灵敏度分析•一、目标函数中变量系数ck灵敏度分析•1．在最终的单纯形表里，xk是非基变量。•在这种情况下，由于约束方程系数增广矩阵（方程AX=b系数矩阵为A，它的增广矩阵为(Ab)）在迭代中只是其本身的行的初等变换与ck没有任何关系，所以当ck变成ck+△ck时，在最终单纯形表中其系数的增广矩阵不变，又因为xk是非基变量，所以基变量的目标函数的系数不变，即cB不变，可知zK也不变，只是ck变成了ck+△ck。这时σK=ck–zk就变成了ck+△ck–zk=σk+Δck。要使得原来的最优解仍为最优解，只要σK+Δck≤0即可，也就是Ck的增量Δck≤-σK即可。迭代次数基变量cBx1x2s1s2s3b比值bi/ai2501000000s1s2s3000111002101001001300400250zjσj=cj-zj00000z=050100000xk是非基变量ck是系数2．在最终的单纯形表中，xk是基变量。•当ck变成ck+△ck时，同上一样，可知在最终的单纯形表中的约束方程的增广矩阵不变，但是基变量在目标函数中的系数cB变了，则zj(j=1,2,…,n)一般也变了，不妨设cB=(cB1,cB2,…,cK,…,cBm),当cB变成(cB1,cB2,…,（cK+Δck),…,cBm),则：kjkkjkjkjkjjjjkjkkjkmjBmkjKjBjBmjBmkjkKjBjBTmjkjjjBmkKBBjTmjkjjjBmKBBjacaccacczcacacacacacacacaccacacaaaaccccczaaaaccccz--)z(-z.z.........)(...),...,,...,,)(),...,(,...,,(:),...,,...,,)(,...,,...,,(jjjj2211221121212121这样检验数变成了•这也就是说，要使最优解不变，对于除了akk′外的所有的大于零的akj′,ck的增量△ck都要小于等于–σj/akj′,对于所有小于零的akj′，Δck都要大于等于–σj/akj′。我们用数学式表示使得最优解不变，Δc的变化范围为：.0,1,0,,,kj;0a,a,0a;0a,a,0a,,0:,0,,kkjkjkjkjkjkjkkkkkKKkkkkkkkjjkjjkjkjkkjkjjaxaczcczccccacackj故知知是基变量因为时而当这里当这里当也就是时只要当要使最优解不变0min0maxkjkjjkkjkjjaacaa以第2章例1为例在最终的单纯形表上对ck进行灵敏度分析。•目标函数：maxz=50x1+100x2，•约束条件：x1+x2≤300，2x1+x2≤400，x2≤250,•x1≥0,x2≥0.•此题在第五章里，已得到最终单纯形表为：迭代次数基变量cBx1x2s1s2s3b501000002x1s2x25001001010-100-211010015050250zjσj=cj-zj501005005000-500-50z=27500先对非基变量s1的目标函数的系数c3进行灵敏度分析。这里σ3=-50，所以当c3的增量Δc3≤-(-50)即Δc3≤50时，最优解不变，也就是说s1的目标函数的系数c′3=c3+△c3≤0+50=50时，最优解不变。再对基变量x1的目标函数的系数c1进行灵敏度分析。•也可以按以下方法来计算出使最优解不变的c′1的变化范围。.1000,50505050:,5050,50)150max(max0max:,5050min0min,50150,,0,0,,,,,111111115511111331513111514131211的最优解不变即有的目标函数也就是时这样可知当同样有有可知外有知道除了中在cccccxcaaaaaaaaaaaaaajjjjjj在最终的单纯形表中，用c′1代替原来的c1=50计算得表如下：•从σ3≤0，得到-c′1≤0，即c′1≥0，并且从σ5≤0，•得到c′1-100≤0，c′1≤100。•从上两式可知：当0≤c′1≤100时最优解不变，如果采取了不属于这范围的c′1，必存在某个检验数σj0，我们可以继续用单纯形表进行迭代，以求出新的最优解。迭代次数基变量cBx1x2s1s2s3bc′11000002x1s2x2c′101001010-100-211010015050250zjσj=cj-zjc′1100c′10-c′1+10000-c′10c′1-100用最终单纯形表对cj进行灵敏度分析，求得使最优解保持不变的c1,c3变化范围与我们在第三章里用计算机求解所得的结果是一样，其实管理运筹学软件就是按这种方法进行编程，对cj进行灵敏度分析的。•二、约束方程右边常数灵敏度分析•我们在第三章对线性规划问题的计算机求解中，也曾经对约束方程右边常数bj进行了灵敏度分析，根据计算机输出的表格，可知道，约束方程右边常数在什么范围内变化时，其对偶价格不变，那么在用单纯形表对bj进行灵敏度分析时，首先应从单纯形表中找到有关对偶价格的信息。•在第三章里我们给了对偶价格这样的定义：在约束条件右边量增加一个单位而使最优目标值得到改进的数量。根据这个定义，我们可以发现约束条件的对偶价格与松弛变量(或剩余变量或人工变量)的zj有关。下面我们仍以第二章例1为例在其最终单纯形表上找出其约束条件的对偶价格。此题的最终单纯形表如下，这是一个求目标函数最大值的问题。•从上表可以发现设备台时数的约束方程中的松弛变量s1的zj值50正好等于计算机解中设备台数的对偶价格，原料A约束方程中的松弛变量s2的zj值0正好等于计算机解中的原料A的对偶价格。同样原料B的约束方程中的松弛变量s3的zj值50正好等于计算机解中的原料B的对偶价格。迭代次数基变量cBx1x2s1s2s3b501000002x1s2x25001001010-100-211010015050250zjσj=cj-zj501005005000-500-5027500松弛变量的zj值是否等于对应的约束条件的对偶价格呢?回答是肯定的。首先知道在最优解中s2=50是基变量，也就是说，原料A有50千克没用完，再增加原料A是不会带来任何利润的，故原料A的对偶价格为零。在最终单纯形表上当松弛变量为基变量时，都有其检验数σj为零，又知道对任何的松弛变量，它在目标函数中的系数cj都为零，那么为基变量的松弛变量的zj也必然为零，因为zj=cj-σj=0-0=0，这正确地反映了对于任何为基变量的松弛变量所对应的约束条件的对偶价格为零。•下面我们来看一看对于非基变量的松弛变量的zj值是否也正确地给出了与其对应的约束条件的对偶价格?迭代次数基变量cBx1x2s1s2s3b501000002x1s2x25001001010-100-211010015050250zjσj=cj-zj501005005000-500-5027500因为对所有松弛变量都有cj=0所以zj=cj-σj=-σj，在对非基变量的目标函数的灵敏度分析中，知道当Δcj≤-σj时最优解不变。也就是说当Δcj≤-σj时，非基变量仍然为非基变量，仍然为零。这时与其对应的约束条件譬如说设备台时数全部使用完了。只有当Δcj≥-σj，也就是△cj≥zj时，对应为非基变量的松弛变量要变成入基变量了。对于设备台时数来说，当其松弛变量在目标函数中系数从零变到z3=50时，也就是说只有当余下一个台时数的设备不能获利变成能获利50元时，譬如说别人愿意出价50元买一个设备时，就不必为生产Ⅰ、Ⅱ产品而使用完所有的设备台时了，这正说明了设备台数的对偶价格就是z3=50元。同样我们也可以知道原料B的对偶价格为z5=50元。•对于含有大于等于号的约束条件，为了化成标准型就添上了剩余变量。这时这个约束条件的对偶价格就和这个剩余变量的Zj有关了。只不过当约束条件右边的常量增加一个单位时，约束条件更严格了。这将给满足约束条件带来些困难。就使最优目标函数值特别“恶化”而不是改进，故这时，约束条件的对偶价格应取Zj值的相反数-Zj。•对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的Zj值。•下面我们给出一个由最终单纯形表对于不同约束类型的对偶价格的取值表：约束类型对偶价格的取值≤等于这个约束条件对应的松弛变量的Zj值≥等于与这个约束条件对应的剩余变量的Zj值的相反数-Zj=等于与这个约束条件对应的人工变量的Zj值从对偶价格的定义，可以知道当对偶价格为正时，它将改进目标函数值。对于求目标函数最大值的线性规划来说改进就是增加其目标函数值，而对求目标函数最小值的线性规划来说改进却是减少其目标函数值。当对偶价格为负时，它将“恶化”目标函数值，对求目标函数最大值的线性规划来说恶化就是减少其目标函数值，而对求目标函数最小值的线性规划来说“恶化”却是增加其目标函数值。在第三章我们已提及过影子价格，对于求目标函数最大值的线性规划中对偶价格等于影子价格，而对求目标函数最小值的线性规划中影子价格为对偶价格的相反数。•下面我们就来求出bj的变化范围，在这个范围内变化其对偶价格不变。当bj变成b′j=bj+△bj时，由于表的迭代实际是约束方程的增广矩阵行的初等变换，bj的变化并不影响系数矩阵的迭代，故其最终表中的系数矩阵没有变化，要使其对偶价格不变，只要原来最终表中的所有Zj值都不变，而Zj值是由基变量的系数与系数矩阵中j列对应元素相乘所得即Zj=CBpTj。这样基变量的系数CB不变，也就是所有的基变量仍然是基变量，即基不变时，原线性规划问题的对偶价格就不变。而要使所有的基变量仍然是基变量只要当bj变化成b′j=bj+△bj时，原来的基不变所得到的基本解仍然是可行解，也就是所求得的基变量的值仍然大于等于零。•一般地，由于bj的变化，资源投入起了变化，最优解是变化的。从这时也可以看出：所谓使其对偶价格不变的bj的变化范围，也就是使其最优解的所有基变量(最优基)不变，且所得的最优解仍然是可行的bj的变化范围。下面我们来看一下当某个bk变成b′k=bk+△bk时在原来的最终单纯形表中的基不变的条件下，最终单纯形表会有什么变化。•单纯形表的迭代实际上是约束方程的增广矩阵的行的初等变换，bk的变化不会影响系数矩阵的迭代，所以在最终单纯形表的系数矩阵不变，又已知最终单纯形表中的基不变，可知CB不变，这样Zj=CBpTj也不变，检验数σj=Cj-Zj也不变，唯一带来变化的只是最终单纯形表中的b列，那么bk变化前后的b列到底有什么关系呢?•原来的约束方程组不妨用矩阵表示为Ax=b，通过一些单纯形表的迭代变成以B为基的最终单纯形表，实际上也就是在原来的约束方程组左乘B-1。即B-1AX=B-1b，在初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里正好就变成了B-1，这里可知：•••其实迭代过程也是用矩阵初等变换求B的逆阵B-1的过程。1001121011B这样在最终单纯形表里系数矩阵就是B-1·A，基变量(记为xB)的解就为B-1b记在单纯形表的b列中。当bk变成bk+Δbk时，也就是原来初始单纯形表中的b向量变成了b′向量，这里•这样在最终单纯形表中基变量XB的解就变成了•x′B=B-1(b+△b)=B-1b+B-1△b。