资源描述
第四章习题,4.2,已知线性规划问题maxz=3x1+2x2s.t-x1+2x243x1+2x214x1-x23x1,x20,minf=4w1+14w2+3w2s.t-w1+3w2+3w232w1+2w2-w22w1，w2，w20,（2）,如果愿问题与对偶问题都有可行解，则二者都有最优解。由原题可见，下列解是原问题与对偶问题的可行解。X（0）=（0，0）TW（0）=（0，1，0）T,4.3,minz=2x1-x2+2x3s.t-x1+x2+x3=4-x1+x2-Kx36X10，X20,X3无约束最优解:X（0）=（-5，0，-1）T,先变成变量大于0,写出符合4.18,4.11,4.06条件的标准型,minz=2x1-x2+2x3s.t-x1+x2+x3=4-x1+x2-Kx36X10，X20,X3无约束最优解:X（0）=(-5，0，-1)T,maxz=-2x1+x2-2x3s.t-x1+x2+x3=4-x1+x2-Kx36X10，X20,X3无约束最优解:X（0）=(-5，0，-1)T,写出对偶问题,minf=4w1+6w2s.tw1+w22w1+w21w1-kw2=-2w1无约束，w20,令X1=-X1maxz=2x1+x2-2x3s.tx1+x2+x3=4x1+x2-Kx36X10，X20,X3无约束最优解:X（0）=（5，0，-1）T,写出目标等式和互补松紧条件,根据定理4.2.5，X（0）=（-5，0，-1）TZ*=2x1+x2-2x3=2（5）-0-2（-1）=12f*=Z*=4w1+6w2=124.2.7,w1=0w2=2,4.2.7w1+w2=2,求解,代入w1-kw2=-1A求得K=1,4.4对偶问题,minf=20w1+20w2s.tw1+2w212w1+w222w1+3w233w1+2w24w10，w20,maxz=x1+2x2+3x3+4x3s.tx1+2x2+2x3+3x4202x1+x2+3x3+2x420X1，X2,X30无约束,续,W*1=1.20W*2=0.20由互补松弛条件可得:x1+2x2+2x3+3x4=20(4.4.1)2x1+x2+3x3+2x4=20,续,将W*1=1.2，W*2=0.2代入对偶问题的约束条件。w1+2w2=1.2+20.2=1.612w1+w2=21.2+0.2=2.622w1+3w2=21.2+30.2=33w1+2w2=31.2+20.2=4,由互补松弛条件定理可知,X*1=0，X*2=0代入(4.4.1)得x1+2x2+2x3+3x4=20(4.4.1)2x1+x2+3x3+2x4=20解得:x*3=4x*4=4原问题最优解:X*=（0，0，4，4）T,4.5,minz=8x1+6x2+3x3+6x4s.tx1+2x2+x433x1+x2+x3+x46x3+x423x1+x32Xj0,j=1,2,3,4最优解:X（0）=(1，1，2，0)T,化标准型,maxz=-8x1-6x2-3x3-6x4s.t-x1-2x2-x43-3x1-x2-x3-x46(4.5.1)-x3-x42-3x1-x32Xj0,j=1,2,3,4最优解:X（0）=（1，1，2，0）T,写对偶问题,minf=3w1+6w2+2w3+2w4s.t-w1-3w2w4-8-2w1-w2-6-w1-w3w4-3(4.5.2)-w1-w2-w3-4wi0I=1,2,3,4,maxz=-8x1-6x2-3x3-6x4s.t-x1-2x2-x43-3x1-x2-x3-x464.5.1)-x3-x42-3x1-x32Xj0,j=1,2,3,4最优解:X（0）=（1，1，2，0）T,互补松弛条件,最优解:X（0）=（1，1，2，0）T即Xj0,j=1,2,3s.t-w1-3w2w4=-8-2w1-w2=-6(4.5.3)-w1-w3w4=-3,代原问题约束条件左端,X（0）=（1，1，2，0）T,x1+2x2+x4=1+2+0=33x1+x2+x3+x4=3+1+2+0=6x3+x4=2+0=23x1+x3=1+22互补松弛定理w4=0,w4=0代入对偶问题约束条件,s.t-w1-3w2w4=-8-2w1-w2=-6(4.5.3)-w1-w3w4=-3w4=0解得:w1=2w2=2w3=1对偶问题最优解:w*=（2，2，1，0）T,4.7,已知线性规划问题maxz=10 x1+5x2s.t3x1+4x295x1+2x28x1,x20,化成标准型maxz=10 x1+5x2s.t3x1+4x2+x3=95x1+2x2+x4=8x1,x20,A,表4.7,B-1,(1)CC+C,(1)目标函数中的价值系数c1，c2分别在什么范围内变动时,上述最优解不变。,当C由CC+C时新检验数=（C+C）-（CB+CB）B-1A4.5.2目标涵数Z=（CB+CB）B-1b4.5.3若0时，最优解仍为最优解，目标值发生了变化。否则，重新迭代。,解:c1C1）,变量=C-（CB+CB）B-1A变=C-CBB-1A,=（C1，5，0，0）-（5，C1）B-1(P1，P2，P3，P4),（B：E）（E：B-1）,B-1=,5/14-3/14-1/72/7,B,C=（5，C1）,B*/B（5，C1）,4325,B=,B=45-32=14,B11B21B12B22,B*=,4325,B21=（-1）（1+2）=-3,5-3-24,5/14-3/14-1/72/7,B-1=,（5，C1）,P,（P1，P2，P3，P4）=,34105201,A,HV,代入,=（C1，5，0，0）-（5，C1）B-1(P1，P2，P3，P4)=（C1，5，0，0）-（5，C1）,5/14-3/14-1/72/7,34105201,=（C1，5，0，0）-C1，5，(25-2C1)/14，(4C1-25)/14,每个分量小于0,=0，0，-(25-2C1)/14，-(4C1-15)/14,-(25-2C1)/140C125/2,-(4C1-15)/140C115/4,15/4C125/2,B*/B（C1，C2）,3452,B=,B=45-32=14,B11B21B12B22,B*=,3452,B21=（-1）（1+2）=-4,2-4-53,-1/72/75/14-3/14,B-1=,代入,=（C1，5，0，0）-（C1，5）B-1（P1，P2，P3，P4）=（C1，5，0，0）-（C1，5）,-1/72/75/14-3/14,34105201,=（C1，5，0，0）-C1，5，(25-2C1)/14，(4C1-25)/14,矩阵乘法的性质,(AB)C=A(BC)(A+B)C=AC+BCC(A+B)=CA+CBK(AB)=(KA)B=A(KB),(2)约束右端项b1,约束右端项b1，b2当一个不变时，另一个在什么范围变化时，原问题的最优解保持不变。,解：,当右端列向量bb+b改变第三列XB=B-1bXB=B-1（b+b）-Z=-CBB-1b-Z=-CBB-1（b+b）,A、若XB=B-1（b+b）0因为没有变则最优基不变，最优解为XB和Z,不大于0,B、若XB=B-1(b+b)0因为0没有变，XB=B-1（b+b）XN=0,XBXN,=,B-1(b+b)0,正则解,b2不变,XB=B-1(b+b)=,5/14-3/14-1/72/7,b18,=0,（5b1-24）/14（16-b1）/7,求解不等式,(5b1-24)/140(16-b1)/70,24/5b116,解法2(1),解:（1）当其它值不变，C1发生变化后最优单纯表变为如下,要保持最优解不变，所有检验数应0故：-（25-2C1）/140，C125/2；-(4C1-15)/140，C115/4所以15/4C125/2,(2),b10,3/21,5/14-1/7,00,（2）由于目标函数中其它参数不变，b1变化不影响检验数，如果变化后XB0那么最优基也不变。,B-1b+B-1=+b1b1-21/5，b17。b1+b124/5，b1+b116。b1的范围是-21/5，7，即b1的范围是24/5，16。,（3）目标函数,目标函数变为maxz=12x1+4x2时，最优解如何变化？,根本是c1，c2同时变化,解,.基变量=C-（CB+CB）B-1A变=C-CBB-1A,=（C1，C2，0，0）-（C2，C1）B-1（P1，P2，P3，P4）,（B：E）（E：B-1）,B-1=,5/14-3/14-1/72/7,P,（P1，P2，P3，P4）,34105201,代入,=（C1，C2，0，0）-（C2，C1）B-1（P1，P2，P3，P4）=（C1，C2，0，0）-（C2，C1）,5/14-3/14-1/72/7,34105201,=（C1，C2，0，0）-C1，C2，(5C2-2C1)/14，(4C1-3C2)/14,每个分量,=0，0，-(5C2-2C1)/14，-(4C1-3C2)/14=（0，0，2/7，-18/7）,表4.7.1,表4.7.2,表4.7.2,最优解:X=（8/5，0，21/5，0）T,(4)右端项,约束右端项由变为最优解为多少?,98,1119,XB,XB=B-1（b+b）=,5/14-3/14-1/72/7,1119,-1/727/7,=,B-1,5/14-3/14-1/72/7,B-1=,表4.7.41,表4.7.42,表4.7.43,表4.7.43,最优解:X=（11/3，0，0，2/3）T,4.6题,其中X2变为X2500。即某一个约束的右端项变化为350-500b=B-1（b+b）=,10-2-315001,800900500,-2001000500,=,Z=CBB-1b=（3，0，8）,-2001000500,=3400,4.6(1),用b，Z最终单纯形表可得：,4.6(11）,主行乘-1/2得,4.6(12）,主行分别乘-5加到第二行，乘-1加到第三行，把x1换成x5，系数3变成0。,4.6(2),用对偶单纯形法可得：,最优解：XB=（0，400，0，500，100）T，Z=3200,
展开阅读全文