运筹学考试资料

1、大工15秋运筹学开卷考试期末复习资料一、单项选择题大工15秋运筹学开卷考试期末复习资料 第1页 共16页1、下列叙述正确的是（ ）。A线性规划问题，若有最优解，则必是一个基变量组的可行基解B线性规划问题一定有可行基解C线性规划问题的最优解只能在最低点上达到D单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A2、数学规划的研究对象为（ ）。A数值最优化问题 B最短路问题 C整数规划问题 D最大流问题答案：A3、下列方法中可以用来求解部分树的方法的为（ ）。大工运筹学课程考试试卷（A） 第3页 共16页A闭回路法 B破圈法 C踏石法 D匈牙利算法答案：B4、把各种备选方案、可

2、能出现的状态和概率以及产生的后果绘制在一张图上，称为（ ）。A决策树 B最大流 C最小支撑树 D连通图答案：A5、以下说法中，不属于无概率决策问题（不确定型决策问题）的特点的为（ ）。A决策人面临多种决策方案B对每个决策方案对应的几个不同决策状态无法估计其出现概率的大小C仅凭个人的主观倾向和偏好进行方案选择D未来情况和条件出现的概率已知答案：D6、线性规划问题中决策变量应为（ ）。A连续变量 B离散变量 C整数变量 D随机变量答案：A7、线性规划问题的数学模型由目标函数、约束条件和（ ）三个部分组成。A非负条件 B顶点集合 C最优解 D决策变量答案：D8、典型的无概率决策准则，不包括（ ）。A

3、乐观准则 B折中准则 C等可能准则 D最大后悔值准则答案：D9、以下说法中不正确的为（ ）。A完成各个作业需要的时间最长的路线为关键路线 B关键路线上的作业称为关键作业C所有关键作业的总时差为0 D以上说法均不正确答案：D10、（ ）也称小中取大准则。这是一种在不确定型决策问题中，充分考虑可能出现的最小收益后，在最小收益中再选取最大者的保守决策方法。A悲观准则 B折中准则 C等可能准则 D后悔值准则答案：A11、当某个非基变量检验数为零，则该问题有（ ）。大工15秋运筹学开卷考试期末复习资料 第2页 共16页A无解B无穷多最优解C退化解D惟一最优解答案：B12、假设对于一个动态规划问题，应用顺

4、推法以及逆推解法得出的最优解分别为P和D，则有（ ）。AP>DBP<DCP=DD不确定答案：C13、下列有关线性规划问题的标准形式的叙述中错误的是（ ）。大工运筹学课程考试试卷（C） 第3页 共16页A目标函数求极大B约束条件全为等式C约束条件右端常数项全为正D变量取值全为非负答案：C14、运输问题的基变量有（ ）个。大工运筹学课程考试试卷（A） 第3页 共16页Am×nBm+n-1Cm+nD不确定答案：B15、目标规划的目标权系数是定量的概念，数值（ ），表示该目标越重要。大工运筹学课程考试试卷（C） 第3页 共16页A越小B越大C为0D为正答案：B16、下列叙述正确的

5、是（ ）。A线性规划问题，若有最优解，则必是一个基变量组的可行基解B线性规划问题一定有可行基解C线性规划问题的最优解一定唯一D单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案： A17、设M是线性规划问题，N是其对偶问题，则（ ）不正确。AM有最优解，N不一定有最优解B若M和N都有最优解，则二者最优值肯定相等C若M无可行解，则N无有界最优解DN的对偶问题为M答案： A18、PERT 网络图中，（ ）表示为完成某个工序所需的时间或资源等数据。大工15秋运筹学开卷考试期末复习资料 第3页 共16页A节点B弧C权D圆圈答案： C19、网络的最大流量应（ ）它的最小割集的容量。A大

6、于B等于C小于D不大于答案： B20、利用单纯形法求解线性规划问题时，判断当前解是否为最优解的标准为所有非基变量的检验数应为（ ）。大工运筹学课程考试试卷（B） 第4页 共16页A正B负C非正D非负答案：C21、若原问题为无界解，则对偶问题的解是（ ）。A无解B无穷多解C无界解D不能确定答案：A22、PERT 网络图中，（ ）表示一个事件，用圆圈和里面的数字表示。大工15秋运筹学开卷考试期末复习资料 第4页 共16页A节点B弧C权D关键路线答案：A23、具有 7个节点的树 T 的边恰好为（ ）条。A5B6C7 D8答案：B24、下列数学模型中，（ ）是线性规划模型。MaxZ=10x1+x2-3

7、x3x21+5x215x1-8x2+3x322xj0, j=1,2,3A. MinZ=3x1+x22x3 B. 2x1+3x2-4x312 4x1+x2+2x38 3x1-x2+3x3=6 x10,x2无约束,x30Z=5x1+6x2+8x3-9x4x1+4x3-x4=19x2-5x3+4x430x1+x2-6x49xj0,j=1,2,3,4MaxZ=x1+4x2-8x3+x24 x1+4x3-x4=29x2-5x3+4x440x1+x2-6x419xj0,j=1,2,3,4 C. D. 答案：A25、若线性规划问题的最优解不唯一，则在最优单纯形表上（ ）。大工运筹学课程考试试卷（A） 第5页

8、 共16页A非基变量的检验数都为零B非基变量检验数不必有为零者C非基变量检验数必有为零D非基变量的检验数都小于零答案：C26、对于总运输费用最小的运输问题，若已得最优运输方案，则其中所有空格的检验数均（ ）。大工运筹学课程考试试卷（A） 第5页 共16页A非正B非负C大于0D小于0答案：B27、下列步骤中，不属于目标规划模型图解法的为（ ）。大工运筹学课程考试试卷（A） 第5页 共16页A作平面直角坐标系B作出目标约束所在直线，标出偏差方向C作出目标函数的一族平行线D按优先级次序，确定满意解答案：C28、下列关于图的说法中，错误的为（ ）。第5页 共16页A点表示所研究的事物对象B边表示事物之

9、间的联系C无向图是由点及边所构成的图D无环的图称为简单图答案：D二、判断题1、增加约束条件时，线性规划模型的可行域不扩大。（ ）答案：对2、决策变量、目标函数和约束条件是数学规划模型的三个要素，若目标函数和约束条件均为线性的数学规划问题称为非线性规划。（ ）答案：错3、产地数与销地数相等的运输问题是产销平衡运输问题。（ ）答案：错4、能够通过网络的最大可行流称最大流。（ ）答案：对5、确定主观概率常用的方法是专家咨询法。（ ）答案：对6、在二人有限对策中，若甲乙双方的赢得总和不全为零，则称为二人有限非零和对策。（ ）答案：对7、增加约束条件时，线性规划模型的可行域不扩大。（ ）答案：对8、线性

10、规划问题存在至少一个对偶问题。（ ）答案：错9、产地数与销地数相等的运输问题是产销平衡运输问题。（ ）大工15秋运筹学开卷考试期末复习资料 第6页 共16页答案：错10、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或是极小，原问题可行解的目标函数值都一定超过其对偶问题可行解的目标函数值。（ ）答案：错11、图的最小生成树一定唯一。（ ）答案：错12、动态规划的逆推与顺推解法得到不同的最优解。（ ）答案：错13、对于线性规划标准型，利用单纯形求解时，每做一次换基迭代，都能保证它相应的目标函数值必为不减少。（ ）答案：对14、当目标规划问题模型中存在的约束条件，则该约束为系统约束。（ ）

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

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

13、偶问题的目标函数值是相等的。（ ）大工15秋运筹学开卷考试期末复习资料 第7页 共16页答案：错32、在解决运输问题时，采用闭回路法，可以得到运输问题的基本可行解。（ ）大工运筹学课程考试试卷（A） 第7页 共16页答案：错33、在整数规划问题中，若变量取值为0或者1，则为01规划问题。（ ）大工运筹学课程考试试卷（A） 第7页 共16页答案：对34、PERT网络图是由结点、弧及权所构成的有向图。（ ）大工运筹学课程考试试卷（A） 第8页 共16页答案：对35、完成各个作业需要的时间最长的路线称为关键路线。（ ）大工运筹学课程考试试卷（A） 第8页 共16页答案：对三、名词解释题1、凸集1如果

14、n维空间的一个子集S中任意两点X1、X2连线上的点都在S中，则称为凸集。2、策略答案：存储策略是指决定多长时间补充一次货物以及每次补充多少数量的策略。3、无概率决策问题答案：无概率决策问题是指决策人面临多种决策方案，对每个决策方案对应的几个不同决策状态无法估计其出现概率的大小，仅凭个人的主观倾向和偏好进行方案选择。4、对策论答案：对策论又被称为博弈论，它是运筹学的一个重要分支，主要研究具有竞争或者对抗性质的现象和规律，在经济学、政治科学、军事科学、进化生物学以及当代的计算机科学等领域中有广泛的应用。5、可行解答案：求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性约束条件的解叫做

15、可行解。6、关键活动答案：为了完成整个项目的进度计划，需要找出其中最长的路径，即关键路径。关键路径上的活动称为项目的关键活动。7、增广链答案：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即fij<cij，后向弧上满足流量大于0，即fij>0，则称这样的链为增广链。8、局势答案：局势是指在一局对策中，每个局中人从其策略集中各取出一个策略参与对策，这些策略合起来称为一个局势。9、线性规划的建模答：线性规划的建模是指将用语言文字描述的应用问题转化为用线性规划模型描述的数学问题。10、灵敏度分析答：灵敏度分析是分析研究一个线性规划模型中的参数A,b,C取值的变化对最优解或最优

16、基的影响。11、基础图答：若把一个有向图D中所有弧的方向去掉，即每一条弧都有相应的无向边替代，所得到一个无向图称为该有向图D的基础图。12、纳什均衡答：在一局二人有限非零和对策中，无论对方的策略如何选择，本方都会选择某个确定的策略，则该策略被称为支配性策略。而由双方各自的支配性策略所构成的这个局势，就被定义为纳什均衡。13、正偏差变量答案：正偏差变量指实际值超出目标值的差距。14、作业的最早开始时间答案：作业的最早开始时间是它的各项紧前作业最早结束时间中的最大一个值。15、连通图答案：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。16、0-1规划问题答案：在整数规划问题中，若变量

17、取值为0或者1，则为0-1规划问题。17、负偏差变量答案：负偏差变量指实际值未达到目标值的差距。18、作业的最迟结束时间答案：作业的最迟结束时间是它的各项紧后作业最迟开始时间中的最小一个。19、最小割答案：网络中所有割集中容量之和为最小的一个割集。20、偏差变量答案：偏差变量指实际值与目标值的差距。d+表示实际值超出目标值的差距；d-表示实际值未达到目标值的差距。21、图答案：图是指点V和边E的集合，用以表示对某种现实事物的抽象。其中点表示所研究的事物对象；边表示事物之间的联系。22、容量网络答案：容量网络指对网络上的每条弧(vi，vj)都给出一个最大的通过能力，称为该弧的容量，记为c(vi，

18、vj)，简称容量。以cij表示。23、状态答案：状态指某阶段初始状况。既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。是动态规划中各阶段信息的传递点和结合点。四、简答题1、简述线性规划四条基本假设的内容。答：(1)比例性：要求每个决策变量在目标函数和约束函数中，其贡献与决策变量的值存在直接比例性。 (2)连续性：指所有的决策变量取值为连续的数。 (3)确定性：指线性规划中所有目标函数和约束函数中的系数都是确定的常数，不含随机因素。 (4)可加性：指所有决策变量对目标函数和约束函数的贡献是相互独立的（包括正向贡献和负向贡献），目标函数值等于每个决策变量各自对目标函数贡献的总和。 2

19、、简述网络计划优化的思路与注意事项。答：（1）优先关注单位时间紧缩成本最小的关键活动进行紧缩。（2）注重关键路径可能的变化。（3）充分利用非关键活动的松弛变量，合理调配资源。3、简述线性规划的建模包括哪些内容。答：（1）决策变量的识别与描述；（2）目标函数的识别与描述；（3）约束条件的识别与描述。4、简述决策树方法的具体步骤。答：具体步骤:（1）画一个方框作为出发点，称为决策点。从决策点画出若干条直线或折线，每条线代表一个行动方案，这样的直（折）线，称为方案枝。（2）在各方案枝的末端画一个圆圈，称为状态点，从状态点引出若干条直线或折线，每条线表示一种状态，在线旁边标出每一状态的概率，称为概率枝

20、。（3）把各方案在各种状态下的损益值标记在概率枝的末端。（4）把计算得到的每个方案的损益期望值标在状态点上，然后，通过比较，选出收益期望值最大（或损失期望值最小）的方案作为最优方案。5、简述单纯形法的基本思路。答：基本思路：确定可行域中的一个极点作为初始点（初始基本可行解），判断此极点是否为最优解，如不是则再找另一个使得其目标函数值更优的极点（称之为迭代），再判断此极点是否为最优解，直到找到一个极点为其最优解，或能判断出LP问题无最优解为止。 6、简述何谓最小支撑树问题，最小支撑树问题的常用方法有哪些。答：如何找出网络的最小树就是最小支撑树问题。 最小支撑树问题可以采用避圈法和破圈法等方法进行

21、求解，也可借助相关的运筹学软件包进行求解。7、简述产销平衡运输问题的数学模型？答：具有个产地（）和个销地（）的运输问题的数学模型为对于产销平衡问题有运输问题有个决策变量，个约束条件。由于产销平衡条件，只有个相互独立，因此，运输问题的基变量只有个。8、简述树的性质？答：（1）任何树必存在次数为 1 的点；（2）具有个节点的树 T 的边恰好为 -1 条；（3）任何有个节点，-1 条边的连通图必是一棵树。9、简述整数规划的求解方法有哪些？答：整数规划的求解方法包括：（1）图解法；（2）分枝定（限）界法；（3）割平面法；（4）匈牙利法；（5）隐枚举法。10、简述网络图的绘制原则和注意事项？答：（1）节

22、点标号原则：箭头节点的标号要大于箭尾节点的标号。（2）两个节点之间只能表示一道工序，只能划一条箭线。作业和箭线是一对一的关系。（3）全图只有一个起点、一个终点。（4）不能出现缺口与回路。（5）各项作业之间的关系：1）作业a结束后可以开始b和c2）作业c在a和b均结束后才能开始3）ab两项作业结束后才可以开始c和d4）作业c在a结束后即可进行，但作业d必须同时在a和b结束后才能开始（6）从左到有，从上到下，尽量避免交叉。五、计算题1、某一最大化线性规划问题在利用单纯形法计算时得到表1。其中为未知数，原问题中要求各变量均非负。问应满足什么条件下，有下面各解成立？表171002-1-501-106-

23、300-4100-30（1）是非可行解；（2）是唯一最优解；（3）有无穷多最优解；（4）是退化基可行解；（5）是可行解但非最优解，只有可以为换入变量且换出变量必为。解：（1）当所有基变量取值均非负时的基解才是可行基解，故当时，表中是非可行解。（2）当现行解为可行解，且对应的非基变量的检验数均小于0时，线性规划问题才有唯一最优解，即。（3）当所有非基变量检验数都小于等于0且其中存在一个非基变量检验数等于0，而在的系数列向量中有大于0的分量时有无穷多最优解。所以或。（4）现行解为退化基可行解的条件是基变量中含有零分量且所有的检验数均非正。所以。（5）因是可行解，所以有；非最优解且只有可以为换入变量

24、，所以有；只有可以为换出变量，所以有，故参数应满足：，。2、已知：（1）运输问题的供需关系与单位运价表（见表1）； （2）用最小元素法求得表1的初始调运方案（见表2）；试用闭回路法求其检验数，并判断此初始调运方案是否最优。表1 供需关系与单位运价表 销地产地甲乙丙丁产量132765027523603254525销量60402015表2 初始调运方案 销地产地甲乙丙丁产量110405022520156032525销量60402015 解：先找出各非基变量的闭回路，即从表2的某一空格（非基变量）为起点，用水平或垂直线，只有碰到数字格（基变量）后才旋转，继续向前划，直到回到起始空格为止。检验数的计算

25、，就是从空格对应的单位运价开始，对闭回路所对应的单位运价交替地赋予“+”和“-”号，并计算它们的代数和，如表3所示。 表3空格闭回路检验数（1丙）（1丙）（2丙）（2甲）（1甲）（1丙）7-2+7-3=9（1丁）（1丁）（2丁）（2甲）（1甲）（1丁）6-3+7-3=7（2乙）（2乙）（2甲）（1甲）（1乙）（2乙）5-7+3-2=-1（3乙）（3乙）（3甲）（1甲）（1乙）（3乙）5-2+3-2=4（3丙）（3丙）（3甲）（2甲）（2丙）（3丙）4-2+7-2=7（3丁）（3丁）（3甲）（2甲）（2丁）（3丁）5-2+7-3=7 选出检验数最小的为（-1），小于0，所以该初始调运方案不是最优调运方案。 3、试用单纯形法解下列线性规划问题。解：化标准形，找一个单位矩阵作为基，列出初始单纯形表 建立初始单纯形表表11200082210040201如表1所示，其中为目标函数中决策变量的系数（），由系数矩阵选