运筹学(第二版)课后答案

附录四习题参考答案４００附录四：习题参考答案第一章线性规划及单纯形法1.1（1）解：第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图1-1所示，交集为（1/2,0）。第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4），过原点O作一条矢量指向点（6，4），矢量的长度不限，矢量的斜率保持4比6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函数图形的位置任意，如果通过原点则目标函数值Z=0，如图1-2所示。第三，求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向，在求最小值时将目标函数图形沿梯度方向的反方向平行移动，（在求最大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移动，其交点对应的坐标就是最优解，如图1-3所示。最优解x=（1/2,0）,目标函数的最小值Z=3。X22x1+x2≥13x1+4x2≤1.5O1/2X1图1.1-1X22x1+x2≥13x1+4x2≤1.5(6,4)O1/2X1图1.1-2附录四习题参考答案４０１（2）无可行解；[求解方法与（1）类似]（3）无界解；（4）无可行解；（5）无穷多最优解z*=66（6）唯一最优解z*=92/3,x1=20/3,x2=3/81.2（1）解：由题目可知，其系数矩阵为）即，，，，（54321PPPPP100230102000101因），，（321PPP023020101线性独立，故有521423118231224xxxxxxx令非基变量0,54xx得1823122421231xxxxx→264321xxx得到一个基可行解Tx），，，，（00262)1(，361Z。X22x1+x2≥13x1+4x2≤1.5(6,4)O1/2X1图1.1-3附录四习题参考答案４０２），，（431PPP003100011线性独立，故有521243121832124xxxxxxx令非基变量0,52xx得1831241431xxxx→2126341xxx得到一个基本解，但非可行解Tx）（0,12,2,0,6)2(，182Z。同理可以求出），，（543PPP100010001，得基本可行解Tx）（18,12,4,0,0)3(。），，（541PPP103010001，得基本可行解Tx）（6,12,0,0,4)4(。），，（421PPP023120001，得基本可行解Tx）（0,6,0,3,4)5(。），，（532PPP102002010，得基本可行解Tx）（6,0,4,6,0)6(。），，（521PPP123020001，得基本非可行解Tx）（6,0,0,6,4)7(。），，（432PPP002102010，得基本非可行解Tx）（0,6,4,9,0)8(。（1）、（2）答案如下表所示，其中打三角符号的是基本可行解，打星号的为最优解：附录四习题参考答案４０３x1x2x3x4x5zx1x2x3x4x5△00412180000-3-5△400126123000-560-2120180010-3△4306027-9/205/200△064063005/20-30*△262003603/2100△*4600-64235/2000△094-6045005/29/20△1.3(1)解：单纯形法首先，将问题化为标准型。加松弛变量x3，x4，得0825943510max42132121jxxxxxxxstxxz其次，列出初始单纯形表，计算最优值。CBXB10500bX1X2X3X40X3341090X452018σj105000X3014/51-3/521/510X112/501/58/5σj010-25X2115/14-3/143/210X100-1/72/71σj00-5/14-25/14（表一）由单纯形表一得最优解为.2/35,)2/3,1(*zxT图解法：附录四习题参考答案４０４X245X1+2X2≤8第一步：相当于原点（0,0）3X1+4X2≤99/4(1,3/2)O8/53x1图1.3-1X245X1+2X2≤8第二步：相当于点（8/5,0）3X1+4X2≤99/4(1,3/2)O8/53x1图1.3-2附录四习题参考答案４０５（2）略1.4(1)解：大M法首先将数学模型化为标准形式)5,,1(,0542182354max3215214321321jxxxxxxxxxxxstxxxzj式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束分别加入人工变量x6x7，目标函数中加入-Mx6-Mx7一项，得到大M单纯形法数学模型)7,,1(,0542182354max732152164321321jxxxxxxxxxxxxxstxxxzj由单纯形表计算：X245X1+2X2≤8第三步：相当于点（1,3/2）3X1+4X2≤99/4(1,3/2)O8/53x1图1.3-3附录四习题参考答案４０６CBXB45100-M-MbX1X2X3X4X5X6X7-MX6321-1010180X521001004-MX711-100015σj4+4M5+3M1-M000-MX6-101-1-210105X221001004-MX7-10-100011σj4-2M01-M-2M001X3-101-1-20100X22100104-MX7-200-1-2111σj5-2M001-M2-2M0表1.4-1.1在迭代过程中，人工变量一旦出基后不会在进基，所以当人工变量X6出基后，对应第六列的系数可以不再计算，以减少计算量。当用大M单纯形法计算得到最优解并且存在人工变量大于零时，则表明原线性规划无可行解。两阶段单纯形法首先，化标准形同大M法，第一、三约束分别加入人工变量x6x7后，构造第一阶段问题)7,,1(,05421823min73215216432176jxxxxxxxxxxxxxstxxwj用单纯形法求解，得到第一阶段问题的计算表1.4-1.2，CBXB0000011bX1X2X3X4X5X6X71X6321-1010180X5210010041X711-100015σj-4-301000附录四习题参考答案４０７1X601/21-1-3/210120X111/2001/20021X701/2-10-1/2013σj0-1012001X6-101-1-210100X2210020041X7-10-10-1011σj2001300表1.4-1.2在第一阶段的最优解中人工变量不为零，则原问题无可行解。注：在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数。(2)无穷多最优解，如X1＝（4，0，0）；X2＝（0，0，8）(3)无界解(4)唯一最优解X*＝（5/2，5/2，5/2，0）(5)唯一最优解X*＝（24，33）(6)唯一最优解X*＝（14，0，－4）1.5（1）X*仍为最优解，maxz＝λCX；（2）除C为常数向量外，一般X*不再是该问题的最优解；（3）最优解变为λX*，目标函数值不变。1.6（1）d≥0,c1＜0,c2＜0（2）d≥0,c1≤0,c2≤0,但c1，c2中至少一个为零（3）d＝0或d＞0，而c1＞0且d/4=3/a2（4）c1＞0,d/4＞3/a2（5）c2＞0,a1≤0（6）x5为人工变量，且c1≤0,c2≤01.7解：设xj表示第j年生产出来分配用于作战的战斗机数；yj为第j年已培训出来的驾驶员；（aj－xj）为第j年用于培训驾驶员的战斗机数；zj为第j年用于培训驾驶员的战斗机总数。则模型为maxz=nx1+(n-1)x2+…+2xn-1+xns.t.zj=zj-1+(aj-xj)yj=yj-1+k(aj-xj)x1+x2+…+xj≤yjxj,yj,zj≥0(j=1,2,…,n)1.8附录四习题参考答案４０８提示：设出每个管道上的实际流量，则发点发出的流量等于收点收到的流量，中间点则流入等于流出，再考虑容量限制条件即可。目标函数为发出流量最大。设xij＝从点i到点j的流量maxz＝x12＋x13st.x12＝x23＋x24＋x25x13＋x23＝x34＋x35x24＋x34＋x54＝x46x25＋x35＝x54＋x56以上为流量平衡条件x12＋x13＝x46＋x56始点＝收点x12≤10，x13≤6，x23≤4，x24≤5，x25≤3，x34≤5，x35≤8，x46≤11，x54≤3，x56≤7xij≥0，对所有i，j1.9提示：设每个区段上班的人数分别为x1，x2，…，x6即可1.10解：设男生中挖坑、栽树、浇水的人数分别为x11、x12、x13，女生中挖坑、栽树、浇水的人数分别为x21、x22、x23,S为植树棵树。由题意，模型为：maxS＝20x11+10x21s.t.x11+x12+x13=30x21+x22+x23=2020x11+10x21=30x12+20x22=25x13+15x23Xij≥0i=1,2；j=1,2,31.11解：设各生产x1,x2,x3maxz=1.2x1+1.175x2+0.7x3s.t.0.6x1+0.15x2≤20000.2x1+0.25x2+0.5x3≤25000.2x1+0.6x2+0.5x3≤1200x1,x2,x3≥01.12解：设7－12月各月初进货数量为xi件，而各月售货数量为yi件，i＝1，2，…，6，S为总收入，则问题的模型为：maxS＝29y1＋24y2＋26y3＋28y4＋22y5＋25y6－（28x1＋24x2＋25x3＋27x4＋23x5＋23x6）st.y1≤200＋x1≤500y2≤200＋x1－y1＋x2≤500y3≤200＋x1－y1＋x2－y2＋x3≤500y4≤200＋x1－y1＋x2－y2＋x3－y3＋x4≤500y5≤200＋x1－y1＋x2－y2＋x3－y3＋x4－y4＋x5≤500y2≤200＋x1－y1＋x2－y2＋x3－y3＋x4－y4＋x5－y5＋x6≤500附录四习题参考答案４０９xi≥0，yi≥0i＝1，2，…，6整数1.13解：用x1，x2，x3分别代表大豆、玉米、麦子的种植面积（hm2，公顷）；x4，x5分别代表奶牛和鸡的饲养数；x6，x7分别代表秋冬和春夏季多余的劳动力（人日），则有），，鸡舍限制）（牛栏限制）（劳动力限制）资金限制）土地限制）71(0(30003240003.050401755035006.0100103520(150003400(1005.1.1.28.12400120300175max547543216543215443217654321jxxxxxxxxxxxxxxxxxxxxxstxxxxxxxzj第二章对偶理论和灵敏度分析2.1对偶问题为(1)0,2211042010min2121212121yyyyyyyystyys(2)无约束3213132121321321,0,013312245minyyyyyyyyyyyyystyyys(3)无约束32132132132131321,0,01373323232253minyyyyyyyyyyyyyystyyys(4)