运筹学第五版 习题答案.docVIP

运筹学习题答案 第一章（39页） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max 5+1050 +1 4 ，0 （2）min z=+1.5 +33 +2 ，0 （3）max z=2+2 --1 -0.5+2 ，0 （4）max z=+ -0 3--3 ，0 解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。 （1）min z=-3+4-2+5 4-+2-=-2 ++3-14 -2+3-+22 ，，0，无约束 （2）max 0 (i=1…n; k=1,…,m) （1）解：设z=-,=-, ,0 标准型： Max =3-4+2-5(-)+0+0-M-M s. t . -4+-2+-+=2 ++3-++=14 -2+3-+2-2-+=2 ,,,,,,,,0 初始单纯形表: 3 -4 2 -5 5 0 0 -M -M b -M 2 -4 1 -2 1 -1 0 0 0 1 2 0 14 1 1 3 -1 1 1 0 0 0 14 -M 2 -2 [3] -1 2 -2 0 -1 1 0 2/3 - 4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 0 (2)解：加入人工变量，，，…，得： Max s=(1/)-M-M-…..-M s.t. (i=1,2,3…,n) 0, 0, (i=1,2,3…n; k=1,2….,m) M是任意正整数 初始单纯形表： -M -M … -M … … … b … … … … -M 1 1 0 … 0 1 1 … … 0 0 … 0 -M 1 0 1 … 0 0 … … 0 0 … 0 … … … … … … … … … … … … … … … … -M 1 0 0 … 1 0 0 … 0 … 1 1 … 1 -s nM 0 0 … 0 … … … 1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。 （1）max z=2+3+4+7 2+3--4=8 -2+6-7=-3 ,,,0 (2)max z=5-2+3-6 +2+3+4=7 2+++2=3 0 （1）解： 系数矩阵A是： 令A=(，，，) 与线形无关，以（，）为基，，为基变量。 有 2+3=8++4 -2=-3-6+7 令非基变量，=0 解得：=1；=2 基解=（1，2，0，0为可行解 =8 同理，以（，）为基，基解=（45/13，0，-14/13，0是非可行解； 以（，）为基，基解=（34/5，0，0，7/5是可行解，=117/5； 以（，）为基，基解=（0，45/16，7/16，0是可行解，=163/16； 以（，）为基，基解=（0，68/29，0，-7/29是非可行解； 以（，）为基，基解=（0，0，-68/31，-45/31是非可行解； 最大值为=117/5；最优解=（34/5，0，0，7/5。 （2）解： 系数矩阵A是： 令A=(，，，) ，线性无关，以（，）为基，有： +2=7-3-4 2+=3--2 令 ，=0得 =-1/3，=11/3 基解=（-1/3，11/3，0，0为非可行解； 同理，以（，）为基，基解=（2/5，0，11/5，0是可行解=43/5； 以（，）为基，基解=（-1/3，0，0，11/6是非可行解； 以（，）为基，基解=（0，2，1，0是可行解，=-1； 以（，）为基，基解=（0，0，1，1是=-3； 最大值为=43/5；最优解为=（2/5，0，11/5，0。 1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。 （1）max z=2+ 3+515 6+224 ，0 （2）max z=2+5 4 212 3+218 ，0 解：（图略） （1）max z=33/4 最优解是(15/4,3/4) 单纯形法： 标准型是max z=2++0+0 s.t. 3+5+=15 6+2+=24 ,,,0 单纯形表计算： 2 1 0 0 b 0 15 3 5 1 0 5 0 24 [6] 2 0 1 4 -z 0 2 1 0 0 0 3 0 [4] 1 -1/2 3/4 2 4 1 1/3 0 1/6 12 -z -8 0 1/3 0 -1/3 1 3/4 0 1 1/4 -1/8 2 15/4 1 0 -1/12 5/24 -z -33/4 0 0 -1/12 -7/24 解为：（15/4，3/4，0，0