清华大学《运筹学教程》胡运权主编课后习题答案(第一章)

1第一章习题解答1.1用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。0,423664.32min)1(21212121xxxxxxstxxZ0,124322.23max)2(21212121xxxxxxstxxZ85105120106.max)3(212121xxxxstxxZ0,23222.65max)4(21212121xxxxxxstxxZ2是其中一个最优解优解）蓝色线段上的点都是最无穷多最优解,51,56(0,423664.32min)1(2121212121xxxxxxxxstxxZ该问题无可行解0,124322.23max)2(21212121xxxxxxstxxZ3166,1085105120106.max)3(21212121ZxxxxxxstxxZ唯一最优解，该问题有无界解0,23222.65max)4(21212121xxxxxxstxxZ41.2将下述线性规划问题化成标准形式。.,0,,2321422245243min)1(43214321432143214321无约束xxxxxxxxxxxxxxxxstxxxxZ无约束321321321321,0,0624322min)2(xxxxxxxxxstxxxZ5.,0,,2321422245243min)1(43214321432143214321无约束xxxxxxxxxxxxxxxxstxxxxZ0,,,,,232142222455243max,0,6424132164241321542413214241321424132165424142414xxxxxxxxxxxxxxxxxxxxxxxstxxxxxwxxxxxxxZw，则标准形式为：，剩余变量同时引入松弛变量，，其中解：令6无约束321321321321,0,0624322min)2(xxxxxxxxxstxxxZ0,,,,6243322max432312114323121132312113231211xxxxxxxxxxxxxxstxxxxW，则标准形式为：同时引入松弛变量解：令433231111,,xxxxxxZW71.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。）（6,,1,0031024893631223max)1(6153214321321jxxxxxxxxxxxstxxxZj)4,1(,0322274322325min)2(432143214321jxxxxxxxxxstxxxxZj8）（6,,1,0031024893631223max)1(6153214321321jxxxxxxxxxxxstxxxZjx1x2x3x4x5x6是否基可行解Z(x1,x2,x3)061/3-7/6000否(x1,x2,x4)0100-700否(x1,x2,x5)03007/20是3(x1,x2,x6)7/4-400021/4否(x1,x3,x4)00-5/2800否(x1,x3,x5)001.5080是3(x1,x3,x6)10-0.5003否(x1,x4,x5)000350是0(x1,x4,x6)5/400-2015/4否(x1,x5,x6)3/400029/4是9/4(x2,x3,x6)016/3-7/6000否(x2,x4,x6)0100-700否(x2,x5,x6)03007/20是3(x3,x4,x6)00-5/2800否(x3,x5,x6)003/2080是3(x4,x5,x6)000350是0所有基可行解中最优解为X=(0,3,0,0,3.5,0)T和X=(0,0,1.5,0,8,0)T10)4,1(,0322274322325min)2(432143214321jxxxxxxxxxstxxxxZjx1x2x3x4是否基可行解Z(x1,x2)-411/200否(x1,x3)2/5011/50是43/5(x1,x4)-1/30011/6否(x2,x3)01/220是5(x2,x4)0-1/202否(x3,x4)0011是5所有基可行解中最优解为X=(0,1/2,2,0)T和X=(0,0,1,1)T111.4分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。0,825943.510max)1(21212121xxxxxxstxxZ1050009341008[5]20110500jjzcjcBCBxb4x2x3x4x3x1x021/50[14/5]1-3/5108/512/501/5010-2jjzc1x3x53/2015/14-3/1410110-1/72/700-5/14-25/141x2xjjzc0点A1点A2点所以最优解为X*=(1,3/2,0,0)T130,24261553.2max)2(21212121xxxxxxstxxZl.5上题(1)中，若目标函数变为maxZ=cx1+dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。最优值1)c0d0d=0d0O点OA3线段A3点2)c=0d0d0OA1线段A3点3)c0d0d=0d0A1点A1点A3点A2A3线段A2点A1A2线段A1点430dc43dc2543dc25dc25dc17式中，1≤c1≤3,4≤c2≤6,-1≤a11≤3,2≤a12≤5,8≤b1≤12,2≤a21≤5,4≤a22≤6,10≤b2≤14,试确定目标函数最优值的下界和上界。0,.max21222212112121112211xxbxaxabxaxastxcxcZl.6考虑下述线性规划问题：18目标函数最优值的上界为：210,14421221.63max21212121xxxxxxstxxZ解：上界对应的模型如下（c,b取大，a取小）19目标函数最优值（下界）为：6.40,1065853.4max21212121xxxxxxstxxZ解：下界对应的模型如下（c,b取小，a取大）20l.7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪—类解。。）（3,,1,00222623max)1(3231321321jxxxxxxxxstxxxZj260,623824.32min)2(2121321321xxxxxxxstxxxZ见下表。31）（4,,1,042634334max)3(4213212121jxxxxxxxxxstxxZj方法一：大M法引入人工变量x6和x7,线性规划问题变为：）（4,,1,042634334max42163215216521jxxxxxxxxxxxstMxMxxxZj00-M4M-17M-4010214000-1346-M1001[3]3-M-M00-1-4jjzcjcBCBxb6x2x3x4x5x5x1x4x01013/246x0-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-1[5/3]02-M1/3001/311-4jjzc6x1x4x106/59/5003-Mi-M+8/501/50011[1]0010-4/50-3/5106/5-13/501/5013/5-4-M00-1-4jjzcjcBCBxb2x2x3x4x5x1x1x4x-1/5-3/5-1316x-M-1/5-M+7/5-1/50001110010-1/53/50105/9-12/5-1/50012/5-4jjzc2x1x3x0-1-M0-Mi由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：TX0,0,0,1,5/9,52*方法二：两阶段法第一阶段：）（4,,1,04263433421632152165jxxxxxxxxxxxstxxmimWj00-147010214000-1346-11001[3]3-1-10000jjzcjcBCBxb6x2x3x4x5x5x1x4x01013/246x0-7/30-15/30-1/3105/3030-4/30-1[5/3]02-11/3001/3110jjzc6x1x4x106/59/5003-1i-1000011[1]0010-4/50-3/5106/503/501/5013/50-M0000jjzcjcBCBxb2x2x3x4x5x1x1x4x-1/5-3/5-16x-1-Mi该模型最优解为X=（3/5，6/5，0，1，0，0）T，其基变量不含人工变量，说明原问题的一个基可行解为X=（3/5，6/5，0，1）T，转入第二阶段。01/5001[1]00100-3/5106/5-101/5013/5-400-1-4jjzcjcBCBxb2x2x3x4x1x1x4x3-1/50001100103/50105/9-1-1/50012/5-4jjzc2x1x3xi由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：TX0,1,5/9,52*139）（3,,1,052151565935121510max)4(321321321321jxxxxxxxxxxstxxxZj431.8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数a∼l值。项目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01Cj－Zja-1200X1(f)(g)2-11/20X54(h)(i)11/21Cj－Zj0-7(j)(k)(l)b=2,c=4,d=-2,g=1,h=0,f=3,i=5,e=2,l=0,-7=-1-(c/b)*a-7=-1-2aa=3j=2-(d/b)*aj=2+3=5k=-(1/b)*ak=-3/2451.9若X(1)、X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。连线上的点和表示)2()1()2()1()10()1(XXaXaaXX的最优解是问题：和证明：设0max)2()1(XbAXCXZXX是问题的可行解因此XbbababAXaAXaAXXaAAaXAX)2()2()1()2()1()1(是问题的最优解因此又因为XCXCXaCXCaXXaCCaXCX)2()2()2()1()2()1()1(471.10线性规划问题maxZ＝CX,AX＝b，X≥0，设X0为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X*，求证(C*-C)(X*-X0)≥010max为问题称问题XbAXCXZ20max*为问题称问题XbAXXCZ证明：的可行解一定是问题的最优解，则是问题12**X*