物流运筹学习题及答案3题目--对偶原理.docx

《物流运筹学习题及答案3题目--对偶原理.docx》由会员分享，可在线阅读，更多相关《物流运筹学习题及答案3题目--对偶原理.docx（5页珍藏版）》请在优知文库上搜索。

1、习题三3.1成建立下述LP问题的对偶关系表，并写出其对偶问题:s.t.(2)(3)s.t.maxz=4x+3x26xj3xi+x2+x3602xl+2x2+3x3402x1+2x2+x36xl0,x20,x30minw=60x+Ix2+2x33xi+x2+x32X1-X2X3-1x1+2x2-x3x10,20,30minw=5xj-3x22x1-X2+4x32x1+x2-2x313x,-x2-x33x10,20,x30(4)maxz=4x+3x2+6xjx1+2x2+4x3=102x1+5x2+3x3=15xlO,x2O,x3O3.2试写出下述LP问题的对偶问题:(1)(5)1.1(1)题(2

2、)1.5题minw=2x+2x24x32x1+3x2+5x323x1+x27x33x1+4x2+6xj=5X20,A0(3)2.4(5)题(4)2.4(7)题(6)ninw=2x+3x2+6x3+X4s.t.3xi+4x2+4x3+7X4=212xl+7x2+3x3+8x418x1-2x2+5x3-3x44x10,x20,x403.3 试证明LP问题(P2)是(D2)的对偶，(P2)是(D2)的对偶。3.4 试写出下述LP问题的对偶问题：(1)minw=CXs.t.AX=bX(0)mminz=EElqjXiji=j=Z%=ajti=1,2,.n7=1Is.t.,EXij=bj,j=l,2,.n

3、i马maxz=ZC/7=1E%Xjbj,i=1,2,r7=1s.t.-=bi,i=r+l,r+2,.,my=xj0,J=l,2,.,5(n)3.5已知LP问题：minz=5xi+6x2+3x35x1+5x2+3x350xl+x2-x3207x1+6x2-9x330x+x2+x37s.t.42x1+4x2-15x3106xl+5x245x2-10x320x10,x20,x30试通过求解其对偶问题来确定该LP问题的最优解。3.6已知LP问题：maxz=x+2x2xl-x22S.t.-Xi+工2Nlx10,x20(1)试证明它与其对偶问题均无可行解(2)试构造一个LP问题，使其本身及其对偶问题均无可

4、行解。3.7已知(I)(II)两个LP问题：(I)maxZi=ZCjXj7=Zaijxjbi,i=1,2,.,wS.t.J=Ix70,7=1,2,.,w(II)maxZ2=ZCjXjJ=Zaijxjbi+ki,i=L2,.,mJ=IXjOJ=1,2,.,H其中rbi,%均为已知常数。设z；,z；分别为(I),（三）的最优值，y；(i=l,2,m)为(I)的对偶问题的最优解，求证:z2zf+Xr=l3.8不用单纯形法，利用对偶性质和其它简便方法求解下述LP问题：(1) maxw=4x+3x26x33x1+x2+3x330s.t.2x1+2x2+3x340xl0,x20,x30(2) maxz=X

5、i-x2+3X1-X34x1-x2+2x33x10,x2O,x3O3.9已知LP问题：maxZ=6x1+8x25xl+Ix220s.t.sx1+2x210x1O,x2O(1)写出它的对偶问题。(2)用图解发求解原始、对偶问题。识别两个问题的所有极点解。(3)用单纯形法求解原始问题。在每个单纯形表中，识别此问题的基本可行解及对偶问题的互补基本解。指出它们相应于图解法中哪个极点。(4)按表3-8的格式，列出该问题的全部互补基本解。(5)用对偶单纯形法求解对偶问题，并将结果与(3)中结果进行对比。(6)该问题是否满足互补松弛性？为什么？3.10用对偶单纯形法求解下述LP问题:(1)minz=x+x2

6、x1+2x24s.t.xl53x1+x26x1O,x2O（2） minz=3x+2x2X3X1+X2+X36s.t.内-4x2-x33x10,20,x30（3） 2.4（4）题3.11 某厂拟生产甲、乙、丙三种产品，都需要在A,B两种设备上加工，有关数据如下表所示:A=品设广、单耗（台时/件）设备有效台时甲乙丙AI2I400B2I25产值（千元/件）321（1） 如何充分发挥设备能力，使产品总产值最大？（2） 若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？3.12 用对偶单纯形法求解下述LP问题：（1） maxz=3xi-2x2-X3X1-X2-X3=4x2+2X38x2-x

7、32x1,x2,x30(2) maxz=2x-X22x3X1+X2+X36-21+X362x2-x30XiyX29X30(3) maxz=5x-8x2-x34x4-11xs2x1-9x2-7xi+2x4-1Ix55xl-6x2-6x3+2x4-9x53F-7%2-8了3+3%4-12毛4xj,2,x3,x4,503.13 用交替单纯形法求解3.12题。第三章对偶原理3.14 X*=(0,20,0),Z*=120.3.15 (1)先用图解法求解对偶问题，得对偶解Y*=(IJ),a*=70;再根据对偶问题的约束条件可确定对偶基本解y*=(1,1,1,0,0)T；最后按互补松弛性，得X*=(0,10,20/3),z*=70;(2)易知对偶问题无可行解，故原问题也无解。3.16 (2)X*=(5/2,15/4),z*=70;Y*=(1/2,7/2),3*=45。3.17 (1)X*=(8/5+12P/5,6/5-6/5),01,z*=4；(2)无可行解。3.18 (1)生产甲产品200件，乙产品100件，总产值800千元；(2)不合算。3.19 (1)X*=(12-2P,8-4,2),01,z*=20;(2)无最优解(无界)；(3)X*=(5-,1-P,2+2,),0U1,z*=25