运筹学(第五版)习题答案定义.docx

运筹学习题答案第一章〔39页〕1.1用图解法求解以下线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解〔1〕max 5+1050+14，0〔2〕min z=+1.5+33+2，0〔3〕max z=2+2--1-0.5+2，0〔4〕max z=+-03--3，0解：〔1〕〔图略〕有唯一可行解，max z=14〔2〕〔图略〕有唯一可行解，min z=9/4〔3〕〔图略〕无界解〔4〕〔图略〕无可行解1.2将以下线性规划问题变换成标准型，并列出初始单纯形表〔1〕min z=-3+4-2+54-+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-Ms. t . -4+-2+-+=2++3-++=14-2+3-+2-2-+=2,,,,,,,,0 初始单纯形表:3-42-5500-M-Mb-M2-41-21-100012014113-11100014-M2-2[3]-12-20-1102/3-4M3-6M4M-42-3M3M-55-3M0-M00(2)解：参加人工变量，，，…，得：Max s=(1/)-M-M-…..-Ms.t. (i=1,2,3…,n)0, 0, (i=1,2,3…n; k=1,2….,m)M是任意正整数初始单纯形表：-M-M…-M………b…………-M110…011……00…0-M101…00……00…0…………………………………………-M100…100…0…11…1-snM00…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=72+++2=30〔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-42+=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+542123+218，0解：〔图略〕〔1〕max z=33/4 最优解是(15/4,3/4)单纯形法：标准型是max z=2++0+0s.t. 3+5+=15 6+2+=24 ,,,0单纯形表计算：2100b01535105024[6]2014-z02100030[4]1-1/23/42411/301/612-z-801/30-1/313/4011/4-1/8215/410-1/125/24-z-33/400-1/12-7/24解为：〔15/4，3/4，0，0 Max z=33/4迭代第一步表示原点；第二步代表C点〔4，0，3，0；第三步代表B点〔15/4，3/4，0，0 〔2〕解：〔图略〕 Max z=34 此时坐标点为〔2，6〕单纯形法，标准型是：Max z=2+5+0+0+0s.t. +=4 2+=12 3+2+=18,,,,0(表略)最优解 X=〔2，6，2，0，0 Max z=34迭代第一步得=〔0，0，4，12，18表示原点，迭代第二步得=〔0，6，4，0，6，第三步迭代得到最优解的点。

1.5以1.4题〔1〕为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值到达最优解：目标函数：max z=+(1)当0时 =-〔/〕+z/ 其中，k=-/=-3/5，=-3l k 时， ，同号当0时，目标函数在C点有最大值当0时，目标函数在原点最大值l k时，，同号当0， 目标函数在B点有最大值；当0，目标函数在原点最大值l k 0时，， 同号当0时，目标函数在A点有最大值当0时，目标函数在原点最大值l k 0时， ，异号当0， 0时，目标函数在A点有最大值；当0， 0时，目标函数在C点最大值l k= 时，， 同号当0时，目标函数在AB线断上任一点有最大值当0，目标函数在原点最大值l k= 时，， 同号当0时，目标函数在BC线断上任一点有最大值当0时，目标函数在原点最大值l k=0时，=0当0时，目标函数在A点有最大值当0，目标函数在OC线断上任一点有最大值〔2〕当=0时，max z= l 0时，目标函数在C点有最大值l 0时，目标函数在OA线断上任一点有最大值l =0时，在可行域任何一点取最大值1.6分别用单纯形法中的大M法和两阶段法求解以下线性问题，并指出属于哪类解。

〔1〕max z=2+3-5++152-5+24，0〔2〕min z=2+3++4+283+26，，0〔3〕max z=10+15+125+3+9-5+6+15152++5，，0〔4〕max z=2-+2++6-2+22-0，，0解：〔1〕解法一：大M法化为标准型：Max z=2+3-5-M+0-Ms.t. +++=7 2-5+-+=10,,,,,0 M是任意大整数单纯形表：23-5-M0-Mb-M71111007-M10[2]-510-115-z17M3M+23-4M2M-50-M0-M20[7/2]1/211/2-1/24/7251-5/21/20-1/21/2--z2M-100(7/2)M+80.5M-600.5M+1-1.5M-134/7011/72/71/7-1/7245/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 目标函数最优值 max z=102/7有唯一最优解解法二：第一阶段数学模型为 min w= + S.t. ++ + =72 -5 + - + =10,,,，,0〔单纯形表略〕最优解X=〔45/7，4/7，0，0，0 目标函数最优值 min w=0第二阶段单纯形表为：23-50b34/7011/71/7245/7106/7-1/7-z-102/700-50/7-1/7最优解是X=〔45/7，4/7，0，0，0 Max z=102/7〔2〕解法一：大M法=-z 有max =-min 〔-〕=-min z化成标准形：Max =-2-3-+0+0-M-MS.T. +4+2-+=4 3+2-+=6 ,,,，,，0〔单纯性表计算略〕线性规划最优解X=〔4/5，9/5，0，0，0 ，0 目标函数最优值 min z=7非基变量的检验数=0，所以有无穷多最优解。

两阶段法：第一阶段最优解X=〔4/5，9/5，0，0，0，0 是根本可行解,min w=0第二阶段最优解〔4/5，9/5，0，0，0，0 min z=7非基变量的检验数=0，所以有无穷多最优解〔3〕解：大M法参加人工变量，化成标准型：Max z=10 +15 +12 +0 +0 +0 -M s.t. 5 +3 + + =9 -5 +6 +15 + =15 2 + + - + =5 ,,,，,，0单纯形表计算略当所有非基变量为负数，人工变量=0.5，所以原问题无可行解两阶段法〔略〕〔4〕解法一：大M法单纯形法，〔表略〕非基变量的检验数大于零，此线性规划问题有无界解两阶段法略1.7求下述线性规划问题目标函数z的上界和下界；Max z=+其中：，，，，，，，解：l 求Z的上界Max z=3+6s.t. -+212 2+414，0参加松弛变量，。