运筹学期末复习题

1、、单项选择题1下列叙述正确的是（）。A.线性规划问题，若有最优解，则必是一个基变量组的可行基解B.线性规划问题一定有可行基解C.线性规划问题的最优解只能在最低点上达到D.单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A2、线性规划的变量个数与其对偶问题的（A.变量目标函数C.约束条件个数答案：C3、在利用表上作业法求各非基变量的检验数时，A.西北角法C.最低费用法答案：B4、下列各项（）不是目标规划的特点A.多目标C.具有优先次序答案：B5、下列关于图的说法中，错误的为 （A.点表示所研究的事物对象C.无向图是由点及边所构成的图答案：D6、利用单纯形法求解线性规划问题时

2、，首先需要A.找初始基础可行基C.确定改善方向）相等。B.变量约束条件D.不确定（）两种方法。B.位势法D.元素差额法B.单一目标D.不求最优B.边表示事物之间的联系答案：A7、对偶问题最优解的剩余变量解值（A.大于 B.小于C.等于D.不能确定答案：CD.无环的图称为简单图B.检验当前基础可行解是否为最优解D.确定入变量的最大值和出变量）原问题对应变量的检验数的绝对值。1010、假设对于一个动态规划问题，应用顺推法以及逆推解法得出的最优解分别为8、当某个非基变量检验数为零，则该问题有（A.无解C.退化解答案：B9、PERT网络图中，（）表示一个工序。A.节点C.权答案：B）0B.无穷多最优解

3、D.惟一最优解B.弧D.关键路线P和 则有（BB? PDC?P=DC11 下列有关线性规划问题的标准形式的叙述中错误的是（A.目标函数求极大C.约束条件右端常数项全为正答案：C12、线性规划问题的数学模型由目标函数、约束条件和（A.非负条件C.最优解答案：D13、如果原问题有最优解，则对偶问题一定具有（A.无穷多解C.最优解答案：C14、运输问题的基变量有（）个。A. rrx nC? m+n答案：B15、目标规划的目标权系数是定量的概念，数值（A.越小C.为0）三个部分组成B.顶点集合D.决策变量答案：B16、下列叙述正确的是（）oA.线性规划问题，若有最优解，则必是一个基变量组的可行基解B.

4、线性规划问题一定有可行基解C.线性规划问题的最优解一定唯一D.单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A17、设M是线性规划问题，N是其对偶问题，则（）不正确。A. M有最优解，N不一定有最优解B.若M和N都有最优解，则二者最优值肯定相等C.若M无可行解，则 N无有界最优解D. N的对偶问题为M18、PERT网络图中，（）表示为完成某个工序所需的时间或资源等数据A.节点B.弧C.权D.答案：c19、网络的最大流量应（）它的最小割集的容量。A.大于B.等于答案：AC.小于D.不大于答案：B20、利用单纯形法求解线性规划问题时，判断当前解是否为最优解的标准为所有非基变

5、量的检验数应为）0B?负B?负D.非负C.非正答案：C21、若原问题为无界解，则对偶问题的解是（A.无解B.无穷多解C.无界解D.不能确定答案：A22、PERT网络图中，（）表示一个事件，用圆圈和里面的数字表示26、对于总运输费用最小的运输问题，若已得最优运输方案A.节点C.权关键磴答案：A TOC o 1-5 h z 23、具有7个节点的利的边恰好为）条。5C? 7D答案：B24、下列数学模型中，（）是线性规划模型。A. MinZ=3xq+X2 2xsB.2 彳I+3X2-4X 3 83xx楼6娉嚷勺束,x 3 0,j=1,2,3,4答案：A25、若线性规划问题的最优解不唯一，则在最优筵痕上

6、A.非基变量的检验数都爱C.非基变量检验数必有霎答案：C)0则槃所有圈栩均)0B.弧6MaxZ=10 xi+x 2-3x 32J x l+5x20,j=1,2,3MaxZ=Xi+4% 2-8x 3+xx I+4X3-X 4=29、X2-5X 3+4x40X1+X2-6X 19Xj0j=1,2,3,4B.非基变量检验数不必有符D.非基变量的检验数都小于零A?非正C.大于0答案：B27、下列步骤中，不属于目标规划模型图解法的为A?作平面直角坐标乐 作出目标约束所在直线，标出愠向C.作出目标函数的一族平线答案：C28、下列关于图的说法中,)0B.非负D.小于0)oD .按优先级次序，确定斶B.B.边

7、表示事物之间的联系A.点表示所研究的事物对象C.无向图是由点及边所构成的图D.无环的图称为简单图答案：D二、判断题 TOC o 1-5 h z K若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。（）答案：对2、在运输问题的解的检验数的计算时，常采用匈牙利法。（）答案：错3、偏差变量是指实际值与目标值的差距，其中 cT 可以用来表示实际值未达到目标值的差距。（）答案：错4、作业的最早结束时间是它的最早开始时间加上该项作业的计划时间。（答案：对5、关键路线上的作业称为关键作业。（）答案：对6、破圈法可以用来求解部分树。（）答案：对7、增加约束条件时，线性规划模型的可行域不扩大。（）答案：

8、对 &线性规划问题存在至少一个对偶问题答案：错 TOC o 1-5 h z 9、产地数与销地数相等的运输问题是产销平衡运输问题。（）答案：错10、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或是极小，原问题可行解的目标函数值都一定超过其对偶问题可行解的目标函数值。（）答案：错11 图的最小生成树一定唯一。（）答案：错12、动态规划的逆推与顺推解法得到不同的最优解。（）答案：错13、对于线性规划标准型，利用单纯形求解时，每做一次换基迭代，都能保证它相应的目标函数值必为不14.当目标规划问题模型中存在14.当目标规划问题模型中存在Xi +x +d 一 = 5的约束条件，则该约束为系统约束

9、。 2答案：错. PERT网络图中，事件通常用箭线表示，作业用圆圈表示。答案：错.无多重边的图称为简单图。（）答案：错仃、运输问题、最短路问题和求网络最大流问题，都可看作是最小费用流的特例答案：对18、目标规划问题中，权系数是定量的概念，数值越大，表示该目标越重要。答案：对 TOC o 1-5 h z 19、若线性规划问题存在可行域，则问题的可行域是凸集。（答案：对20、目标规划模型中，应同时包含系统约束与目标约束。（答案：错21、PERT网络图中，任何消耗时间或资源的行动都可称作作业。答案：对22、任务分配问题共有rrx m个约束条件。（）答案：错23、树枝总长为最短的部分树称为图的最小部分

10、树。（）答案：对24、目标的优先级是一个定性的概念，不同优先级的目标无法从数量上来衡量。答案：对25、单纯形法计算中，应选取最小正检验数对应的变量作为换入变量。答案：错+ 答案当目标规划问题模型中存在的约束条件，则该约束为目标约束PERT网络图中，事件消耗一定的时间和资源。（）答案：错28、在动态规划模型中，问题的阶段数等于问题中的子问题的数目。答案：对29、运输问题和求网络最大流问题，都可看作是最小费用流的特例。答案：对30、当网络中不存在任何增广链口寸，则网络达到最大流状态。31、在可行解的状态下，原问题与对偶问题的目标函数值是相等的。答案：对答案：错32、在解决运输问题时，采用闭回路法，

11、可以得到运输问题的基本可行解。33、在整数规划问题中，若变量取值为0或者仁则为01规划问题。（答案：错答案：对34、PERT网络图是由结点、弧及权所构成的有向图。（）答案：对35、完成各个作业需要的口寸间最长的路线称为关键路线。（）答案：对三、名词解释题K规划问题答案：生产和经营中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益。这就是所谓的规戈问题。2、对偶问题答案：内容一致但从相反角度提出的一对问题称为对偶问题。3、无向图答案：无向图是指由点及边所构成的图。4、割集答案：割集是指容量网络中一组弧的集合，割断这些弧，能使流中断，简称割。5、路线答案：从PERT网络图中

12、从最初事件到最终事件的一条路。6、偏差变量答案：偏差变量指实际值与目标值的差距。7、PERT网络图答案：PERT网络图是由结点、弧及权所构成的有向图。&曾广链答案：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即fj0,则称这样的链为增广链。9、系统约束答案：系统约束指某种资源在使用上要受到严格的限制，决不允许超用或超负荷运行。10、简单图答案：既没有自环也没有平行边的图称为简单图。11状态转移律答案：状态参数变化的规律。从第k阶段的某一状态值 Sk出发，当决策变量Xk的取值确定之后，下一阶段的状态值Sk+i按某种规律T(Sk,x k)确定。12.闭回路答案：闭回路指调运方案中由一

13、个空格和若干个有数字格的水平和垂直连线包围成的封闭回路。13、正偏差变量答案：正偏差变量指实际值超出目标值的差距。14、作业的最早开始时间答案：作业的最早开始时间是它的各项紧前作业最早结束时间中的最大一个值。15.连通图答案：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。16 0-1规戈ij问题答案：在整数规划问题中，若变量取值为0或者1,则为0-1规划问题。.负偏差变量答案：负偏差变量指实际值未达到目标值的差距。.作业的最迟结束时间答案：作业的最迟结束时间是它的各项紧后作业最迟开始时间中的最小一个。19最小割答案：网络中所有割集中容量之和为最小的一个割集。20、偏差变量答案：偏

14、差变量指实际值与目标值的差距。表示实际值超出目标值的差距；d表示实际值未达到目标值的差距。示事物之间的c(v动态规划中各阶段信示事物之间的c(v动态规划中各阶段信21、图答案：图是指点 V和边E的集合，用以表示对某种现实事物的抽象。其中点表示所研究的事物对象；边表联系。22、容量网络答案：容量网络指对网络上的每条弧（Vi, Vj）都给出一个最大的通过能力，称为该弧的容量，询Vj ），简称容量。以Cij表示。23、状态答案：状态指某阶段初始状况。既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和据是息的传递和结合点。答案：答：将图中所有的点分为四、简答题内点的集合。（1）任取一点vi,令v

15、j eV; （3）重复（2），至所有的点均在V之内。简述避圈法的步骤？V和V两部分，其中V -一最小部分树内点的集合；V 非最小部分树加粗，令vi eV; （2）取V中与V相连的边中一条最值边（vi,vj）2、简述利用分枝定界法求解整数规划问题时，首先需要寻找替代问题，简述替代问题应翔修件答案：（1）容易求解；（2）松弛问题的解集应全部包含原问题的解集。3、简述图解法的适用条件和基本步骤答案：答：对于只含两个变量的线性规划问题，可通过在平面上作图的方法求解。图解法的步骤如下(1)建立平面直角坐标系；(2)图示约束条件，找出可行域；(3)图示代表目标函数的直线及目标函数值增加 (或减小)的方向；

16、函数达到最优值(4)将目标函数直线沿其法线方向在可行域内向可行域边界平移至目标函数达到最优值为止目标 的点就为最优点。函数达到最优值4、简述利用元素差额法确定运输问题初始方案的基本思想和步骤。答：基本思想：从总体考虑，得到初始可行方案。步骤：从运价表上分别找出每行与每列的最小的两个元 素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。5、简述求网络最大流的标号算法的基本步骤。答：第一步：标号过程，找一条增链(1)给源点s标号s+ , e(s) = x,表示从s点有无限流出潜力(2)找出与已标号节点i相邻的所有未标号节点j，若(i,j)是前向弧且饱和，则节点j不标号；(i,j)是

17、前向弧且未饱和，则节点 j标号为i+, B(j)，表示从节点i正向流出，可增广0 0_f =0,f =0,则节点j不标号；? ?J一 0f 0,则节点j标号为i ,(j)，表示从节点j流向i，可增广(j, i)是后向弧，若(j,i)是后向弧，若e o(j) =min (i), fj门；(3)重复步骤(2),可能出现两种情况：1)节点t尚未标号,但无法继续标记，说明网路中已不存在增广链，当前流V就是最大流；所有获标号的节点在V中，未获标号节点在 V中，V与V间的弧即为最小割集；算法结束；2)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链；到第二步。第二步：增广过程。r 0 0(1

18、)对增广链中的前向弧，令f = f +,(t)为节点t的标记值；? 0(2)对增广链中的后向弧，令f = f-(t);(3)非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步。6、简述目标规划问题图解分析法的基本思路?答案：除了刚性约束必须严格满足外，对所有的目标约束允许出现偏差，求解的过程是按照问题要求从高 层到低层逐层优化，在不加大高层偏差值的情况下，使该层次的加权偏差值达到最小，进而找出满意解。7、简述产销平衡运输问题的数学模型?答：具有m个产地a: ( i 1,2, ,m)和n个销地bj ( j 1,2, ,n )的运输问题的数学模型为min z对于产销平衡问题有(j

19、 =1,2,- ,n)m)运输问题有m n对于产销平衡问题有(j =1,2,- ,n)m)运输问题有m n个决策变量,=b jn卞约束条件。由于产销平衡条件，只有 m n 1个相互独立, TOC o 1-5 h z Z X =b , ? ?IJJi n ns.t. IZ x a ,? ?IJIj 1X ? ? ?J因此，运输问题的基变量只有 &简述树的性质？答：（1）任何树必存在次数为1的点；（2）具有n个节点的树T的边恰好为n 1条；（3）任何有答：（1）任何树必存在次数为节点，n 1条边的连通图必是一棵树。9、简述整数规划的求解方法有哪些 ？答：整数规划的求解方法包括：（1）图解法；（2）

20、分枝定邙艮）界法；（3）割平面法；（4）匈牙利法；（5）隐枚举法。10、简述网络图的绘制原则和注意事项 ？答：（1）节点标号原则：箭头节点的标号要大于箭尾节点的标号。（2）两个节点之间只能表示一道工序，只能划一条箭线。作业和箭线是一对一的关系。（3）全图只有一个起点、一个终点。（4）不能出现缺口与回路。（5）各项作业之间的关系：1）作业a结束后可以开始b和c2）作业c在a和b均结束后才能开始cr3) ab两项作业结束后才可以开始 c和dQ-*O*O4)作业c在a结束后即可进行，但作业 d必须同时在a和b结束后才能开始(6)从左到有，从上到下，尽量避免交叉。五、计算题1、某一最大化线性规划问题在

21、利用单纯形法计算时得到表1o其中a,b,c,d,e, f为未知数，原问题中要求各变量均非负。问a,b,c,d,e, f应满足什么条件下，有下面各解成立？表1C BXBbXiX2X3X4X5X6Xf7C10e03Y2Jn1nX66a-300-41CjZ ?bd00 30（1）是非可行解;是唯一最优解；有无穷多最优解；是退化基可行解；是可行解但非最优解，只有X可以为换入变量且换出变量必为 X是可行解但非最优解，只有X可以为换入变量且换出变量必为 X6= =列向量中有大于0的分量时有无穷多最优解。所以f 0,b 0,d 0或f 0,d 0,b 0,c 0。-（4$现彳产解为退化基可行解的条件是基变量

22、中含有零分量且所有的检验数均非正。所以（5）因是可行解，所以有、f 0;非最优解且只有*可多为换冬变量，却b 0,d0 ；只有X6b 0, d 0, f 0 o0,b0, d 0,Q可以为换出变量，所以有,故参数应满足:可以为换出变量，所以有,故参数应满足:7 a2、已知：（1）运输问题的供需关系与单位运价表（见表（2）用最小元素法求得表1的初始调运方案（见表 2）；试用闭回路法求其检验数，并判断此初始调运方案是否最优表1 供凰关系与单位运价7曼甲乙丙丁产量9750197V9V60DQ242只110405022520156032525销量60402015解：先找出各非基变量的闭回路，即从表 2

23、的某一空格（非基变量）为起点，用水平或垂直线，只有碰到 数字格（基变量）后才旋转90；继续向前划，直到回到起始空格为止。检验数的计算，就是从空格对应的单位运价开始，对闭回路所对应的单位运价交替地赋予“+”和”号，并计算它们的代数和，如表 3所示。闭回路T(1/1丙(1 T -7 -/( 丙/J3/(甲/(甲7 - X 丙 z(x 申 /(z(x 甲 /(3乙闭回路T(1/1丙(1 T -7 -/( 丙/J3/(甲/(甲7 - X 丙 z(x 申 /(z(x 甲 /(3乙3(x /丙/_3 TJZ乙/ - 乙丙-3 /z3 T ZJ/(777/(甲2甲,/一z(xz(xz(x1乙）-1乙）-2

24、7丙/(/(/(5 73 +21 T42-27 +7 =52137 +7 =选出检验数最小的为（-1 ），小于0,所以该初始调运方案不是最优调运方案3、试用单纯形法解下列线性规划问题maxz = Xi +2xs.t.解：化标准形，找一个单位矩阵作为基，列出初始单纯形表建立初始单纯形表+2x 2xOx 2ximaxz Xi 2x + +2s.t.2xiI Ox1X+2x x22x2XOx Oxb / 口i/ =y7 a ,XiX4XiX4如表1所示，其中C为目标函数中决策变量Xj的系数 22101,2,3,4 ),由系数矩阵A L选择单位矩阵选择单位矩阵B110作为初始可行基，则对应的基变量为1

25、TXb(X3, X4),基变量的系数 CB =(0,0）,常数向量（资源向量）（8,4），列出约束方程组的增光矩阵bA.（注：XB所对应的列的变量X ）为基变量，其余的变量都为非基变量）4计算初始单纯形表币的检验馥1 (1)Cj z =Cj CbB Pj = Cj C P ,如非基变量 Xi X2- r j ?01(1)CbP =1-01(1)CbP =1-1(00 )的检验数：2=1- ( 0*2+0*2 ) =101(1)2z2= C2 CbP =2(00)=2- ( 0*2+0*2 ) =2基变量X3 , X4的检验数为0 （所有基变量的检验数都必定为0,不用再另行计算），由于非基变量的检验数为基