运筹学习题及答案

运筹学习题答案第一章（39页）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max12zxx51x+102x501x+2x12x41x，2x0（2）minz=1x+1.52x1x+32x31x+2x21x，2x0（3）maxz=21x+22x1x-2x-1-0.51x+2x21x，2x0（4）maxz=1x+2x1x-2x031x-2x-31x，2x0解：（1）（图略）有唯一可行解，maxz=14（2）（图略）有唯一可行解，minz=9/4（3）（图略）无界解（4）（图略）无可行解1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。（1）minz=-31x+42x-23x+54x41x-2x+23x-4x=-21x+2x+33x-4x14-21x+32x-3x+24x21x，2x，3x0，4x无约束（2）maxkkzsp11nmkikikikzax11(1,...,)mikkxinikx0(i=1…n;k=1,…,m)（1）解：设z=-z,4x=5x-6x,5x,6x0标准型：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,10x0初始单纯形表:jc3-42-5500-M-MiBCBXb1x2x3x5x6x7x8x9x10x-M10x2-41-21-10001207x14113-11100014-M9x2-2[3]-12-20-1102/3-z4M3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工变量1x，2x，3x，…nx，得：Maxs=(1/kp)1ni1mkikikx-M1x-M2x-…..-Mnxs.t.11miikkxx(i=1,2,3…,n)ikx0,ix0,(i=1,2,3…n;k=1,2….,m)M是任意正整数初始单纯形表：jc-M-M…-M11kap12kap…1mkap…1nkap2nkap…mnkapiBCBXb1x2x…nx11x12x…1mx…1nx2nx…nmx-M1x110…011……00…0-M2x101…00……00…0…………………………………………-Mnx100…100…0…11…1-snM00…011kaMp12kaMp…1mkaMp…1nkaMp2nkaMp…mnkaMp1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）maxz=21x+32x+43x+74x21x+32x-3x-44x=81x-22x+63x-74x=-31x,2x,3x,4x0(2)maxz=51x-22x+33x-64x1x+22x+33x+44x=721x+2x+3x+24x=31x2x3x4x0（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+52x1561x+22x241x，2x0（2）maxz=21x+52x1x422x1231x+22x181x，2x0解：（图略）（1）maxz=33/4最优解是(15/4,3/4)单纯形法：标准型是maxz=21x+2x+03x+04xs.t.31x+52x+3x=1561x+22x+4x=241x,2x,3x,4x0单纯形表计算：jc2100iBCBXb1x2x3x4x03x153510504x24[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,5x0(表略)最优解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)当2c0时2x=-（1c/2c）1x+z/2c其中，k=-1c/2cABk=-3/5，BCk=-3kBCk时，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=1c1x1c0时，目标函数在C点有最大值1c0时，目标函数在OA线断上任一点有最大值1c=0时，在可行域任何一点取最大值。1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。（1）maxz=21x+32x-53x1x+2x+3x1521x-52x+3x241x，2x0（2）minz=21x+32x+3x1x+42x+23x831x+22x61x，2x，3x0（3）maxz=101x+152x+123x51x+32x+3x9-51x+62x+153x1521x+2x+3x51x，2x，3x0（4）maxz=21x-2x+23x1x+2x+3x6-21x+3x222x-3x01x，2x，3x0解：（1）解法一：大M法化为标准型：Maxz=21x+32x-53x-M4x+05x-M6xs.t.1x+2x+3x+4x=721x-52x+3x-5x+6x=101x,2x,3x,5x,4x,6x0M是任意大整数。单纯形表：jc23-5-M0-MiBCBXb1x2x3x4x5x6x-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,6x0（单纯形表略）最优解X=（45/7，4/7，0，0，0)T目标函数最优值minw=0第二阶段单纯形表为：jc23-50iBCBXb1x2x3x5x32x4/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，7x0（单纯性表计算略）线性规划最优解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，7x0单纯形表计算略当所有非基变量为负数，人工变量7x=0.5，所以原问题无可行解。两阶段法（略）（4）解法一：大M法单纯形法，（表略）非基变量4x的检验数大于零，此线性规划问题有无界解。两阶段法略1.7求下述线性规划问题目标函数z的上界和下界；Maxz=11cx+22cx1111221axaxb2112222axaxb其中：113c，246c，1812b，21014b，1113a，1225a，2124a，2246a解：求Z的上界Maxz=31x+62xs.t.-1x+22x1221x+42x142x，1x0加入松弛变量，化成标准型，用单纯形法解的，最优解X=（0，7/2，5，