实用运筹学习题选详解复习过程

1、实用运筹学习题选详解精品资料运筹学判断题一、第1章线性规划的基本理论及其应用1、线性规划问题的可行解集不一定是凸集。（X）2、若线性规划无最优解则其可行域无界。（X）3、线性规划具有惟一的最优解是指最优表中非基变量检验数全部非零。（V）4、线性规划问题的每一个基本可行解对应可行域的一个顶点。（V）5、若线性规划模型的可行域非空有界，则其顶点中必存在最优解。（V）6线性规划问题的大M法中，M是负无穷大。（X）7、单纯形法计算中，若不按最小比值原则选取换出变量，则在下一个解中至少 有一个基变量为负。（V）8、对于线性规划问题的基本可行解，若大于零的基变量数小于约束条件数，则 解是退化的。（V）。9

2、、一旦一个人工变量在迭代过程中变为非基变量后，则该变量及相应列的数字 可以从单纯性表中删除，且这样做不影响计算结果。（V）10、线性规划的目标函数中系数最大的变量在最优解中总是取正值。（X）11、对一个有n个变量，m个约束的标准型的线性规划问题，其可行域的顶点恰好为个Cm 0（X）12、线性规划解的退化问题就是表明有多个最优解。（X）13、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。（V）14、单纯型法解线性规划问题时值为 0的变量未必是非基变量。（V）15、任何线性规划问题度存在并具有唯一的对偶问题。（V）16、对偶问题的对偶问题一定是原问题。（V）17、根据对偶问题的性质

3、，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题为无界解。（X）18、若原问题有可行解，则其对偶问题也一定有可行解。（X）19、若原问题无可行解，其对偶问题也一定无可行解。（X）20、若原问题有最优解，其对偶问题也一定有最优解。（V）21、 已知yi*为线性规划的对偶问题的最优解，若 y* 0 ,说明在最优生产计划 中，第i种资源一定有剩余。（X）22、原问题具有无界解，则对偶问题不可行。（V）23、互为对偶问题，或者同时都有最优解，或者同时都无最优解。（V）24、某公司根据产品最优生产计划，若原材料的影子价格大于它的市场价格， 则可购进原材料扩大生产。（V）25

4、、对于线性规划问题，已知原问题基本解不可行，对偶问题基本解可行，可 采用对偶单纯形法求解。（V）26、 原问题（极小值）第i个约束是“ ”约束，则对偶变量yi 0 0（V）27、线性规划问题的原单纯形解法，可以看作是保持原问题基本解可行，通过 迭代计算，逐步将对偶问题的基本解从不可行转化为可行的过程。（V）*28、运输问题不能化为最小费用流问题来解决。（X）29、运输问题一定有最优解。（V）30、若运输问题的可行解退化，贝U存在等于零的数字格。（V）31、运输问题是特殊的线性规划问题，表上作业法也是特殊形式的单纯形法。32、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以 找出

5、，而且仅能找出唯一闭合回路。（V）33、如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，调运方案将不会发生变化。（X）34、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，调运方案将不会发生变化。（V）35、 如果运输问题单位运价表的全部元素分别乘上一个常数k k 0，调运方 案将不会发生变化。（V）36、运输问题独立约束条件数 m n 1个，变量数是mn个，于是基变量数为 mn m n 个。（X）37、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数 值。（X）38、一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最 优解&#

6、176;（x）39、分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解 °（V）40、整数规划的最优解是先求相应的线性规划的最优解然后取整得到。（X）41、用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标 函数值是该问题的下界。（V）42、用分支定界法求解一个极大化的整数规划问题，当得到多于一个可行解 时。通常可任取其中一个作为下界值，再进行比较剪枝。（X）（V）仅供学习与交流，如有侵权请联系网站删除 谢谢5精品资料43、求最大值的整数规划问题中，其松弛问题的最优解是整数规划问题最优解 的上界。（V）44、匈牙利算

7、法是对指派问题求最小值的一种求解方法。（V）45、指派问题效率矩阵的每个元素分别乘上一个常数 k，将不影响最优指派方 案。（X）46、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。（V）47、匈牙利算法是对指派问题求最小值的一种求解方法。（V）48、应用匈牙利算法求解工作指派问题时，对不打勾的行和打钩的列画横线。（V）49、求解效率最大的指派问题，可以用指派矩阵的最小元素减去该矩阵的各元素，得到新的指派矩阵，再用匈牙利算法求解。（X）1、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而 对图中点与点的相对位置、点与点的连线的长短曲直等都要严格注意。（X）

8、2、连通图G的部分树是取图G的点和G的所有边组成的树。（X）3、在有向图中，链和路是一回事。（X）4、连通图一定有支撑树。（V）5、避圈法（加边法）是：去掉图中所有边，从最短边开始添加，加边的过程中 不能形成圈，直到有n条边（n为图中的点数）°（X）&应用矩阵法计算网络最小支撑树问题，应当在所有记有 T的行里没有划去的 元素中寻找最小元素。（V）7、用避圈法得到的最小树是惟一的，但破圈法得到的则不是。（X）8、最小生成树的Kruskal算法，每次迭代是将剩下边集中的最小权边加入树 中。（X）9、Dijkstra算法和Ford算法均要求边的权重非负。（2?）°（X）1

9、0、Dijkstra算法可用于正权网络也可用于负权网络。（X）11、Dijkstra算法可用于求解有负权的网络最短路问题。（X）12、Dijkstra算法可用于求解最短路中的所有情形。（X）13、Dijkstra算法是求最大流的一种标号算法。（X）14、在最短路问题中，发点到收点的最短路长是惟一的。（V）15、求图的最小支撑树以及求图中一点到另一点的最短路问题，都可以归结为 求解整数规划问题。（V）16、只有一个奇点的连通图是欧拉图。（X）17、在任何网络流中，零流总是一个可行流。（V）18、在最大流问题中，最大流是惟一的。（X）19、最大流问题是找一条从发点到收点的路，使得通过这条路的流量最

10、大。（X）20、 容量Cij是弧i, j的实际通过量。（X）21、可行流是最大流的充要条件是不存在发点到收点的增广链。（V）22、一个具有多个发点和多个收点地求网络最大流的问题一定可以转化为具有 单个发点和单个收点地求网络最大流问题。（V）23、形成增广链的条件是对于正向弧必须满足 fj 0 o （X）24、可行流的流量等于每条弧上的流量之和。（X）25、最大流量等于最大流。（X）26、求网络最大流的问题可归结为求解一个线性规划模型。（V）27、若已求得网络最大流，已标号节点的集合和未标号节点的集合给出了网络 的最小割集。（V）28、网络最大流等于该网络最大割容量。（X）29、割集中弧的流量之

11、和称为割量。（X）30、最小割集等于最大流量。（X）31、任意可行流得流量不超过任意割量。（V）32、若已给网络的一个最小费用可行流，它的最小费用增广链对应于长度网络（赋权图）的最短路。（V）33、总时差为零的各项作业所组成的路线即为关键路线。（V）34、工程网络图中关键路线是最长路线。（V）35、网络规划中，工作的机动时间或富余时间叫做时差，分为总时差和单时 差。（V）36、以同一节点为开始事件的各项作业的最早开始时间相同。（V）37、以同一节点为结束事件的各项作业的最迟结束时间相同。（V）38、节点的最早开始时间与最迟完成时间两两相同所组成的路线是关键路线。（X）39、优化网络图计划，保证

12、资源的最优配置和工期的按时完成，通常根据工作 的时差，采用非关键路线上的工作开始时间来实现。（V）40、采取应急措施，往往不但缩短了工期环可以减少工程总费用。（X）41、工程网络图中，只能有一个开始节点，但可以有多个结束节点。（X）仅供学习与交流，如有侵权请联系网站删除谢谢7精品资料42、工程网络图中，事项只表示某项工作结束的状态。（X）43、工程网络图可以有几个初始事项，但不可以有几个最终事项。（X）44、虚活动的作业时间等于零。（V）45、在网络图得关键路线上，总时差等于零。（V）1、矩阵对策中，如果最优解要求一个局中人采取纯策略，则另一个局中人也必须采取纯策略。（X）2、任何矩阵对策一定

13、存在混合策路意义下的解，并可以通过求解两个互为对偶的线性规划问题得到。（V）3、对策模型的三要素：局中人、策略、赢得函数。（V）4、 在两人零和对策支付矩阵的某一行（或某一列）上加上一个常数k，将不影 响对策双方各自的最优策略。（X）5、 二人零和对策支付矩阵的所有元素乘上一个常数k，将不影响对策双方各自 的最优策略。（V）6应对灾害天气制定预案的策略，同制订对一场可能发生的军事冲突的策略，具有相同的性质和过程。（X）7、如果在任一“局势”中，全体局中人的“得失”相加总是等于零，这个对策就叫 做“零和对策” °（V）8、任何一个给定的矩阵对策 G 一定有解（在混合扩充中的解）

14、6;（V）9、一个矩阵对策问题的赢得矩阵 A aj，一定有不等式max min aij min maxaij 0（X）1 3210、 已知某对策问题的赢得函数矩阵为 5 2 3，所以它是纯策略对策问2 43题。（X）11、二人零和有限对策问题中，对局双方的赢得函数值互为相反数。（V）12、最优纯策略中，mpxminay min maxa,a为局中人赢得函数中的元素。（V）运筹学实用教程解答题、第1章线性规划的基本理论及其应用max z 3x1 2x22x-i4x2221（ 1.3.1）、用图解法解线性规划问题x14x210(答案:s.t2 x-i4x27X13x21x1, x20max z 2

15、1;x5,x2 3 )线性规划图解法20 I1.115 仅供学习与交流，如有侵权请联系网站删除 谢谢11-2011111024681012x=(0:0.1:12)：y1=(22-2*x)/4;y2=2*x-7;y3=(x+10)/4;y4=(x-1)/3;z1=(1-3*x)/2;z2=(4-3*x)/2;z3=(8-3*x)/2;z4=(12-3*x)/2;'b-plot(x,y1, 'g：',x,y2,'g:',x,y3,'g：',x,y4,'g:',x,z1,'b-',x,z2,',x,z3,

16、'b-',x,z4,'b-');title('?D?1? i ?a ');精品资料max z 2x1 x2x2102x1 5x2602 (1.3.2)、用图解法解线性规划问题1(答案:s.t x1 x2183x-i x244x1, x20仅供学习与交流，如有侵权请联系网站删除谢谢11x=(0:0.1:15)'y1=10;y2=(60-2*x)/5;y3=18-x;y4=44-3*x;z1=1-2*x;z2=4-2*x;z3=8-2*x;z4=12-2*x;'b-plot(x,y1, 'g:',x,y2,'g

17、:',x,y3,'g:',x,y4,'g:',x,z1,'b-',x,z2,',x,z3,'b-',x,z4,'b-');title('?D?1? i ?a ');精品资料仅供学习与交流，如有侵权请联系网站删除 谢谢23max z 3 2x23 （1.3.3）、用图解法解线性规划问题x13s.t x1x20（答案：可行域无界,x1, x20无最优解）0.552线性规划图解法x1=3-3x1+2x2=1 -3x1+2x2=4（图形是matlab结合几何画板绘制出来的）max z 3%

18、2x24（ 1.3.4）、用图解法解线性规划问题x1x21s.t2x1 2x2 4（答案：无可行域，无最x1, x?0优解）（图形是matlab结合几何画板绘制出来的）max z 4x1 3x23% 2x265 （1.3.5）、用图解法解线性规划问题1（答案：可行域无界,s.t x1 3x2 18x1, x20无最优解）线性规划图解法x=(0:0.1:3)'y1=(6+3*x)/2;y2=(18+x)/3;z1=(12-4*x)/3;z2=(20-4*x)/3;plot(x,y1, 'g：',x,y2,'g:',x,z1,'b-',x,z

19、2,'b-');title('?D?1? i ?a ');(图形是matlab结合几何画板绘制出来的)maxz 2x1 3x26 (1.3.6)、用图解法解线性规划问题4x116s.t x1 2x28(答案:max z 14“4, x22)x=(0:0.1:9)'y1=(8-x)/2;z1=(12-2*x)/3;z2=(20-2*x)/3;plot(x,y1, 'g:',x,z1,'b-',x,z2,'b-');title('?D?1? i ?a ');线性规划图解注(图形是matlab结合

20、几何画板绘制出来的)max z7 (1.4.1)、用单纯形法计算X22x,st X13x,2x1 x2105x260x218x244x1, x20(答案：maxz 31“ 13, x2 5 ,松弛变量x3详解：弓I进 松弛变量X3,X4,X5,X6，标准化模型为5,X49,X5X60 )max z2x1X2X2X3102x-i5x2X460s.tx1X2X5183x_jX2X644X1,X2,X3,X4,X5,X60建立初始单纯形表并作基的变换如下,XX1X2X3X4X5X6bthitac210000X3001100010X402601006060/2=30X501100101818/ 仁18

21、X603100014444/3 最小！zj00000 d00Zj-cj2-10000先找负的绝对值最大的定入X300110001010X40013/3010-2/392/392/13X5002/3001-1/310/35最小！定 岀X1211/3000 d1/344/344zj22/30002/388/3下一行+cjZj-cj01/30002/3先找负的绝对值最大的定入X300010-3/21/25X40000113/23/29X2101003/2-1/25X121000-1/21/213zj21001/21/231下一行+cjZj-cj00001/2 n1/2最优性判别，得知最优解5n从表中

22、得答案，maxz 31;x19, X5X60 013, X25 ,松弛变量Xgmaxz4x13x26X33为X23X330st 2为3x?3x340X1,X2,X3010, x320/3)8 (142)、用单纯形法计算maxz详解：引进松弛变量X4, X5，标准化模型为3x1 st 2x1X23x23x23x33x36X3X4Xi,X2,X3,X4,X5X5030040(答案：maxz 70; x10,x2建立初始单纯形表并作基的变换如下,XX1X2X3X4X5bthitac43600X40313103030/3=10,最小出 基X50223014040/3>10zj000000Zj-c

23、j-4-3-6 丁00先找负的绝对值最大的定入X3611/311/301030X50-110-111010,最小出基zj6262060下一行+cjZj-cj2-1020先找负的绝对值最大的定入X364/3012/3-1/320/3X23-110-1110zj5361170下一行+cjZj-cj10011最优性判别，得知最优解从表中得答案，maxz 70;论0X10, X320/3min z2x1X25x3X4X425X1X2X3X4206x3s.t 4x159 (143)、现有单纯形法问题2 2x2 3x3 2x430x1,x2, x30, x4无非负要求max( z)2为x2 5x3 x4

24、x4 Xt 0 x5X1X4X4X525X2X3X4x4 x620(答案:mx6 0 x7 mx8 0 x9 o x0 mx“(1)化为标准型；(2)列出初始单纯型表4* st2x26x3X7X 53x32x42X4Xg302x23x32x42x4 X10X11 2xi,x2,x3,x4,x4,x5,x6,x7,x5,xg,xio,xi1 0XX1X2X3X41X42X5X6X7X8X9X10X11bc-2-151-10-M0-M00-MX503001-1100000025X6M1111-1010000020X8M4060000-110005X900232-2000010030X11M0232

25、-200000-112zj5M3M10M-3M3M0-MM-M0M-M27MZj-cj5M+23M+1-1UIVI-5-3IVI-1-3IVI+1IM0M0)maxz 60x1 50x2% 2x24010 (1.6.1.1)求线性规划2为X26的对偶问题(答案:s.tx1 x225x1, x20min w 40y1 6y2 25y3y 2y2 y360)st 2y1 y2 y3 50Y1，Y2, Y30maxz2428x24为6x24811( 1.6.1.2)、求线性规划s.tx19的对偶问题（答案:X27x1,x20min w 48y19y2 7y34y1 y224)st 6y1 y328y

26、2, y30, y1无非负要求min z 2x1 x2 6x3 x43x1 x42512（ 161.3）、求线性规划s.tX1 X2 x3 X44x1 6x3520的对偶问题（答案:2 2x2 3x3 2x430x1, x2, x30, &无非负要求min z2x1X26X3X43x1X425X1x2 x3 x 20st4x16X352x23x32x42继而得max w25y1 20y2 5y3 2y4 30 y52x2 3x3 2x430x!，x2, x3 0,x4无非负要求3y1 y2 4y32Y2 2y4 2y51y2 6y3 3y4 3%6Y1 y2 2y4 2y51%”3，丫

27、450, y2无非负要求min f 6x1 4x2x 2x2413 (161.4)、求线性规划的对偶问题(答案:s.t 2x1 x22x1,x20maxw 4y1 2y2* 2y26)st 2*1 *24*1,*2 0min f 5x1 3x22x. 3x2614 (161.5)、求线性规划2 的对偶问题(答案:s.t 3x1 6x24X1,X20maxw 6y14y22% y25st 3y1 6y23)y1,y2 0minz20x110x215( 162)、用对偶单纯型法解5%6(答案:st2x12x?8xxmax z45; %1严10X2、5x. x? 6详解：转化为5%s.t 2x1 2

28、x28s.t2x1N ,x20为必max(z)20x110x2得到标准化模型为5x1XX36st2x12x2 X48min z 20x1max( z)X1,)<2,X3,X40020x110x2x26、，引入松弛变量X3M4 ,2x2800 x30 x4建立初始对偶单纯形表并作基的变换如下,XX1X2X3：X4bc-20-100X30-5-110-6先取负的最大的 b值所在，确定 换出X40-2-201-8精品资料zj0ro0ro0Zj-cj201000thita|20/-2|10/-2| I再找比值的绝对值最小的定入X30-401r-1/2-2先取负的最大的 b值所在，确定 换出X2-

29、10110-1/24zj-101-1001 5下行加cjZj-cj10005-40thita|-10/4|I-5/0.5|再找比值的绝对值最小的定入X1-2010-1/4r 1/81/2已经全为正了， 说明基解已可行X2-10011/4-5/83.5zj-20-105/2；3.75下行加cjZj-cj005/23.75-45依判据，得最优解11从表中看出 max z45; x1, x2 3 , minz 4522max z 2% x2 x33x1 2x2 2x31516 (163)、现有线性规划问题： X2 X33，用单纯形法求最优s.tx1 x2 x34石，必 0解和资源1、资源2、资源3的

30、影子价格。(答案：最优解x 21,24,0,0,7 T资源1、资源2、资源3的影子价格1,1,0)maxz2为 x2x3max z 2x1X2X33x12x2 2x3 153为 2x22x315详解：x2 x33转化为X1X2X3 3，引入松弛变量s.ts.tX2X34x1x2X34加2必0X1,X2,X30maxz2x1 x2 x332x2 2x3x415x4 , x5, x6 ，得到标准化模型为%X2X3X53。s.tJ JX2X3x4X1,X2,X3,X4,xs,x60建立初始单纯形表并作基的变换如下,XX1X2X3X4X5 X6bthitac2-11000X403-221001515/

31、3=5X50-1110103X601-1100144/仁4最小！定出基变量zj000000Zj-cj21-1000先找负的绝对值最大的定入基变量X4001-110-333/仁3最小！定出基变量X5000201 117X121-110014zj2-22002下行加cj定入基变量Zj-cj0-1100 128先找负的绝对值最大X2-101-110-33X5000201177/仁7最小！定出基变 量X1210010-27zj2-1110-1下行加cj定入基变量Zj-cj00010-111先找负的绝对值最大X2-101513024X600020117X1210412021zj2-13110下行加cjZ

32、j-cj00211018判定最优解从表中看出x21,24,0,0,7 T,maxz 18，由表的最后一行，可得资源1、资源2、资源3的影子价格分别为1,1,017（ 1.6.4）、现有线性规划问题:min z2x14x26x32x1x2%102x22x312，（ 1）用单纯形法求s.t2x2X340仅供学习与交流，如有侵权请联系网站删除谢谢31解该问题;（2）用对偶单纯形法求解该问题（答案：x 6,2,0 T,z 20min( z)2x14X26x3 MX52xjx2x3X5X410（1）花2x22X3X612st2x2X3xX74X1, x2,X3,Xs,X8, X4,Xs,X70Mx8 0

33、 X4 x6 x7用单纯性法迭代;18( 1.6.5)、求解线性规划丄3x2X23(答案：s.tX1X23X1,X20Tx 2,1,7,0,0 ,z 55)minz 20x1 15x2max(z)20x1 15x22x1 x252x1X25详解：3X1 2x2 3转化为3x12x23，s.ts.tx1 x2 3X1X23x1 ,x20X1,X20max( z)2015x2 0x32x1X2X35X3,X4, X5，得到标准化模型为3ct2x2 x43Ol LX2X530Xi，X2，X3，X4，X引入松弛变量0x4 0x5min( z)2x-| 4x26X30 X4X5x2x1 x2(2)X1

34、2x2st2x2 X3X32x3X410X6X5412用对偶单纯性法迭代)Xi, X2,X3, X4,X5, X6min z 20x12x1 x215x25建立初始对偶单纯形表并作基的变换如下,XX1X2X3X4X5bc-20-15000X30-2-1100-5先取负的最大的 b值所在，确定 换出X40-320103X50-1-1001-3zj°0000下行加cjZi-ci20150000thita再找比值的绝对值|20/ (-2) |=10，|15/ (-1)|=15最小的定入X：X1X2X3X4X5bc-20-15000X1011/2-1/2005/2先取负的最 大的b值所 在，

35、确定换 出X4097/2-3/2h021/2X500-1/2-1/201-1/2zj-20-1010：00下行加cjzj-ci0510：00-50thita再找比值的绝对值|5/（-1/2）|=10，|10/（-1）1=20最小的定入XX1X2X3X4X5bc-20-15000X1010-1o12全正，基解X400o-5177可行X200110-21zj-20-155010下行加cjZj-cj：o05o10-55 1判定最优从表中看出最优解为 x 2,1,7,0,0T,z 55mi nz 10捲 8x2 7x319（ 1.6.6）、用对偶单纯型法解2为x24（答案：Stx1x2X33X1,X2

36、,X30x 1,2,0 T ,z 26)min z 10为 8x27X3maxz10x1 8x27X3，“2x1 x? 42为x24详解：12转化为，引入松弛变量s.t % x2 x33s.tX-!X2X33为冬必 0N，X2，X30max( z)10为8x27x30x4 OX5沧,X5，得到标准化模型为2x1X2X44。s.t为X2X3X53X1,X2，X3,X4，X50建立初始对偶单纯形表并作基的变换如下,XX1X2X3X4X5bc-1O-8-7OOX3O-2-1O1O-4先取负的最大的X4O-1-1-1O1-3b值所在，确定 换出cj -ZjP-1O-8-7OOOthita再找比值的-1

37、0/( -2)=5，-8/（-1）=8最小的定入X1-1Op1/2O-1/2O2先取负的最大的X4OO-1/2-1-1/21-1b值所在，确定 换出cj -ZjO-3-75O20thita再找比值的-3/(-1/2)=6，-7/(-1)=7,-5/（ -1/2）=1O最小的定入X1-1Op1/2O-1/2O2全正，基解可行X2-8Lo12h-22cj -ZjOO-1-2-626判别数非正，确认最 优从而得最优解x 1,2,0 丁，z 26min w 3 3x22x 3x21820 (167)用对偶单纯型法解 X2 2(答案:st捲 3x210x20x 4,2,4 T , w 16)min w3

38、x1 3x2max( w)3x1 3x22x13x2 182x13x218详解：X1X22 转化为X1X22，引入松弛变量X3,X4,X5，s.ts.tX13x210X13x210X1,X20X1,X20max( z)3x13x20X30x4 0x52为3x2 x318得到标准化模型为X1X2X42。stX13x2 X510X1，X2,X3，X4,X50建立初始对偶单纯形表并作基的变换如下,XX1X2X3X4X5bc1-3-301 00X302310018先取负的最大的 b值所在，确定 换出X40I1010 J-2X50-1-3001-10cj -Zj-3-30000thita再找比值的-3/

39、（-1）=3，-3/（ -3）=1最小的定入X30101018先取负的最大的 b值所在，确定 换出X40-4/30011/3-16/3X2-31/3100-1/310/3ci -Zj2000：-110thita再找比值的-2/（ -4/3）=3/2最小的定入X300013/45/44全正，基解可行X1-3100-3/4-1/44X2-30101/4-1/42cj -Zj-2000-110判别数非正，确认最 优thita再找比值的-2/（ -4/3）=3/2最小的定入从表中看出，最优解为X 4,2,4 t,w 161 （4.2.1）、某市举行1990年世界杯6强（A、B、C、D、E、F）联赛。竞

40、赛采取循环制，每天安排三场比赛。同一个队一天之内只安排一场，要求竞赛在5天之内赛完，请用图的方法表示 6个队之间的联赛，和竞赛日程安排，并指 出每个图是什么类型的图，各日程安排图与联赛图是什么关系。（答案：GA：FG2G3FCA.«BG4FACEG5，G是完全图，GgGGG为非连通图，且都是G的子图）精品资料V101011V2101012 (4.2.2)、写 V301011出右图的关联矩阵和相关矩阵V410100V4e3V3V5 11100（答案：列都对应顶点,0 110 0 0e5 0 10 0 1e6 0 0 1 0 1V410100v511100100V101011110V21

41、0101010，相关矩阵为v301011 )e2 01e3 0 0关联矩阵为e4 10仅供学习与交流，如有侵权请联系网站删除 谢谢27e7 1 0 0 0 13 （423）、有甲乙丙丁戊己6名运动员报名参加ABCDEF6个项目的比赛。下表中打“V”的是各运动员报名参加的比赛项目（表4-1）。问：6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛?ABCDEF甲VV乙VVV丙VV丁VV戊VV己VV（答案:有人同时参加则连线，方案一 ACBFED，方案二AFBCDE，条任意两点不相关序列）4（ 424）、出席某处国际学术报告会的 6个成员ABCDEF被分在一组。他们 的情况是：A会讲汉语、

42、法语和日语；B会讲德语、俄语和日语；C会讲英 语、法语；D会讲汉语和西班牙语；E会讲英语和德语；F会讲俄语和西班牙 语。怎么把他们安排在一张圆桌旁坐下，使得每个人能和他两旁的人交谈？（答案:F俄汉德 西A日 cB找一条汉密顿回路ACEBFDA）5（4.2.5）、图 G=（V，E）是连通图，且e E。证明：e属于每一棵生成树的充要条件是e为G的割集。（答案：都用反证法。充分性： e属于每一棵生成树，若e不为G的割集（反设）。则G-e必连通，则G-e中必存在生成树T， 因为T也是G的生成树，但T不包含e,导致矛盾。必要性：设e不为G的割 集(反设)。若G有生成树T,则T+e包含回路。删去e后连通，即与e属于 每棵生成树矛盾，反设不成立。)6(426)、已知图得结点集V=a,b,c,d，以及图G和图D的边集合分别为E(G)=(a,a),(a,b),(b,c),(a,c); E(D)= <a,b>,<a,c>,<c,d>,<c,a>,<c,b>。试作图 G 和图D，写出个结点的度数，回答图G、图D是简单图还