您好,欢迎访问三七文档
运筹学习题答案第一章(39页)1.1用图解法求解下列线性规划问题,并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。(1)max12zxx51x+102x501x+2x12x41x,2x0(2)minz=1x+1.52x1x+32x31x+2x21x,2x0(3)maxz=21x+22x1x-2x-1-0.51x+2x21x,2x0(4)maxz=1x+2x1x-2x031x-2x-31x,2x0解:(1)(图略)有唯一可行解,maxz=14(2)(图略)有唯一可行解,minz=9/4(3)(图略)无界解(4)(图略)无可行解1.2将下列线性规划问题变换成标准型,并列出初始单纯形表。(1)minz=-31x+42x-23x+54x41x-2x+23x-4x=-21x+2x+33x-4x14-21x+32x-3x+24x21x,2x,3x0,4x无约束(2)maxkkzsp11nmkikikikzax11(1,...,)mikkxinikx0(i=1…n;k=1,…,m)(1)解:设z=-z,4x=5x-6x,5x,6x0标准型:Maxz=31x-42x+23x-5(5x-6x)+07x+08x-M9x-M10xs.t.-41x+2x-23x+5x-6x+10x=21x+2x+33x-5x+6x+7x=14-21x+32x-3x+25x-26x-8x+9x=21x,2x,3x,5x,6x,7x,8x,9x,10x0初始单纯形表:jc3-42-5500-M-MiBCBXb1x2x3x5x6x7x8x9x10x-M10x2-41-21-10001207x14113-11100014-M9x2-2[3]-12-20-1102/3-z4M3-6M4M-42-3M3M-55-3M0-M00(2)解:加入人工变量1x,2x,3x,…nx,得:Maxs=(1/kp)1ni1mkikikx-M1x-M2x-…..-Mnxs.t.11miikkxx(i=1,2,3…,n)ikx0,ix0,(i=1,2,3…n;k=1,2….,m)M是任意正整数初始单纯形表:jc-M-M…-M11kap12kap…1mkap…1nkap2nkap…mnkapiBCBXb1x2x…nx11x12x…1mx…1nx2nx…nmx-M1x110…011……00…0-M2x101…00……00…0…………………………………………-Mnx100…100…0…11…1-snM00…011kaMp12kaMp…1mkaMp…1nkaMp2nkaMp…mnkaMp1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解,并代入目标函数,确定最优解。(1)maxz=21x+32x+43x+74x21x+32x-3x-44x=81x-22x+63x-74x=-31x,2x,3x,4x0(2)maxz=51x-22x+33x-64x1x+22x+33x+44x=721x+2x+3x+24x=31x2x3x4x0(1)解:系数矩阵A是:23141267令A=(1P,2P,3P,4P)1P与2P线形无关,以(1P,2P)为基,1x,2x为基变量。有21x+32x=8+3x+44x1x-22x=-3-63x+74x令非基变量3x,4x=0解得:1x=1;2x=2基解(1)X=(1,2,0,0)T为可行解1z=8同理,以(1P,3P)为基,基解(2)X=(45/13,0,-14/13,0)T是非可行解;以(1P,4P)为基,基解(3)X=(34/5,0,0,7/5)T是可行解,3z=117/5;以(2P,3P)为基,基解(4)X=(0,45/16,7/16,0)T是可行解,4z=163/16;以(2P,4P)为基,基解(5)X=(0,68/29,0,-7/29)T是非可行解;以(4P,3P)为基,基解(6)X=(0,0,-68/31,-45/31)T是非可行解;最大值为3z=117/5;最优解(3)X=(34/5,0,0,7/5)T。(2)解:系数矩阵A是:12342112令A=(1P,2P,3P,4P)1P,2P线性无关,以(1P,2P)为基,有:1x+22x=7-33x-44x21x+2x=3-3x-24x令3x,4x=0得1x=-1/3,2x=11/3基解(1)X=(-1/3,11/3,0,0)T为非可行解;同理,以(1P,3P)为基,基解(2)X=(2/5,0,11/5,0)T是可行解2z=43/5;以(1P,4P)为基,基解(3)X=(-1/3,0,0,11/6)T是非可行解;以(2P,3P)为基,基解(4)X=(0,2,1,0)T是可行解,4z=-1;以(4P,3P)为基,基解(6)X=(0,0,1,1)T是6z=-3;最大值为2z=43/5;最优解为(2)X=(2/5,0,11/5,0)T。1.4分别用图解法和单纯形法求解下列线性规划问题,并指出单纯形迭代每一步相当于图形的哪一点。(1)maxz=21x+2x31x+52x1561x+22x241x,2x0(2)maxz=21x+52x1x422x1231x+22x181x,2x0解:(图略)(1)maxz=33/4最优解是(15/4,3/4)单纯形法:标准型是maxz=21x+2x+03x+04xs.t.31x+52x+3x=1561x+22x+4x=241x,2x,3x,4x0单纯形表计算:jc2100iBCBXb1x2x3x4x03x153510504x24[6]2014-z0210003x30[4]1-1/23/421x411/301/612-z-801/30-1/312x3/4011/4-1/821x15/410-1/125/24-z-33/400-1/12-7/24解为:(15/4,3/4,0,0)TMaxz=33/4迭代第一步表示原点;第二步代表C点(4,0,3,0)T;第三步代表B点(15/4,3/4,0,0)T。(2)解:(图略)Maxz=34此时坐标点为(2,6)单纯形法,标准型是:Maxz=21x+52x+03x+04x+05xs.t.1x+3x=422x+4x=1231x+22x+5x=181x,2x,3x,4x,5x0(表略)最优解X=(2,6,2,0,0)TMaxz=34迭代第一步得(1)X=(0,0,4,12,18)T表示原点,迭代第二步得(2)X=(0,6,4,0,6)T,第三步迭代得到最优解的点。1.5以1.4题(1)为例,具体说明当目标函数中变量的系数怎样变动时,满足约束条件的可行域的每一个顶点,都可能使得目标函数值达到最优。解:目标函数:maxz=1c1x+2c2x(1)当2c0时2x=-(1c/2c)1x+z/2c其中,k=-1c/2cABk=-3/5,BCk=-3kBCk时,1c,2c同号。当2c0时,目标函数在C点有最大值当2c0时,目标函数在原点最大值。BCkkABk时,1c,2c同号。当2c0,目标函数在B点有最大值;当2c0,目标函数在原点最大值。ABkk0时,1c,2c同号。当2c0时,目标函数在A点有最大值当2c0时,目标函数在原点最大值。k0时,1c,2c异号。当2c0,1c0时,目标函数在A点有最大值;当2c0,1c0时,目标函数在C点最大值。k=ABk时,1c,2c同号当2c0时,目标函数在AB线断上任一点有最大值当2c0,目标函数在原点最大值。k=BCk时,1c,2c同号。当2c0时,目标函数在BC线断上任一点有最大值当2c0时,目标函数在原点最大值。k=0时,1c=0当2c0时,目标函数在A点有最大值当2c0,目标函数在OC线断上任一点有最大值(2)当2c=0时,maxz=1c1x1c0时,目标函数在C点有最大值1c0时,目标函数在OA线断上任一点有最大值1c=0时,在可行域任何一点取最大值。1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题,并指出属于哪类解。(1)maxz=21x+32x-53x1x+2x+3x1521x-52x+3x241x,2x0(2)minz=21x+32x+3x1x+42x+23x831x+22x61x,2x,3x0(3)maxz=101x+152x+123x51x+32x+3x9-51x+62x+153x1521x+2x+3x51x,2x,3x0(4)maxz=21x-2x+23x1x+2x+3x6-21x+3x222x-3x01x,2x,3x0解:(1)解法一:大M法化为标准型:Maxz=21x+32x-53x-M4x+05x-M6xs.t.1x+2x+3x+4x=721x-52x+3x-5x+6x=101x,2x,3x,5x,4x,6x0M是任意大整数。单纯形表:jc23-5-M0-MiBCBXb1x2x3x4x5x6x-M4x71111007-M6x10[2]-510-115-z17M3M+23-4M2M-50-M0-M4x20[7/2]1/211/2-1/24/721x51-5/21/20-1/21/2--z2M-100(7/2)M+80.5M-600.5M+1-1.5M-132x4/7011/72/71/7-1/721x45/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最优解是:X=(45/7,4/7,0,0,0)T目标函数最优值maxz=102/7有唯一最优解。解法二:第一阶段数学模型为minw=4x+6xS.t.1x+2x+3x+4x=721x-52x+3x-5x+6x=101x,2x,3x,4x,5x,6x0(单纯形表略)最优解X=(45/7,4/7,0,0,0)T目标函数最优值minw=0第二阶段单纯形表为:jc23-50iBCBXb1x2x3x5x32x4/7011/71/721x45/7106/7-1/7-z-102/700-50/7-1/7最优解是X=(45/7,4/7,0,0,0)TMaxz=102/7(2)解法一:大M法z=-z有maxz=-min(-z)=-minz化成标准形:Maxz=-21x-32x-3x+04x+05x-M6x-M7xS.T.1x+42x+23x-4x+6x=431x+22x-5x+7x=61x,2x,3x,4x,5x,6x,7x0(单纯性表计算略)线性规划最优解X=(4/5,9/5,0,0,0,0)T目标函数最优值minz=7非基变量3x的检验数3=0,所以有无穷多最优解。两阶段法:第一阶段最优解X=(4/5,9/5,0,0,0,0)T是基本可行解,minw=0第二阶段最优解(4/5,9/5,0,0,0,0)Tminz=7非基变量3x的检验数3=0,所以有无穷多最优解。(3)解:大M法加入人工变量,化成标准型:Maxz=101x+152x+123x+04x+05x+06x-M7xs.t.51x+32x+3x+4x=9-51x+62x+153x+5x=1521x+2x+3x-6x+7x=51x,2x,3x,4x,5x,6x,7x0单纯形表计算略当所有非基变量为负数,人工变量7x=0.5,所以原问题无可行解。两阶段法(略)(4)解法一:大M法单纯形法,(表略)非基变量4x的检验数大于零,此线性规划问题有无界解。两阶段法略1.7求下述线性规划问题目标函数z的上界和下界;Maxz=11cx+22cx1111221axaxb2112222axaxb其中:113c,246c,1812b,21014b,1113a,1225a,2124a,2246a解:求Z的上界Maxz=31x+62xs.t.-1x+22x1221x+42x142x,1x0加入松弛变量,化成标准型,用单纯形法解的,最优解X=(0,7/2,5,
本文标题:运筹学习题及答案
链接地址:https://www.777doc.com/doc-4697910 .html