大工15秋《运筹学》开卷考试期末复习资料
21、图
答案：图是指点V和边E的集合，用以表示对某种现实事物的抽象。其中点表示所研究的事物对象；边表示事物之间的联系。 22、容量网络
答案：容量网络指对网络上的每条弧(vi，vj)都给出一个最大的通过能力，称为该弧的容量，记为c(vi，vj)，简称容量。以cij表示。 23、状态
答案：状态指某阶段初始状况。既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。是
动态规划中各阶段信息的传递点和结合点。
四、简答题
1、简述线性规划四条基本假设的内容。
答：(1)比例性：要求每个决策变量在目标函数和约束函数中，其贡献与决策变量的值存在直接比例性。 (2)连续性：指所有的决策变量取值为连续的数。 (3)确定性：指线性规划中所有目标函数和约束函数中的系数都是确定的常数，不含随机因素。 (4)可加性：指所有决策变量对目标函数和约束函数的贡献是相互独立的（包括正向贡献和负向贡献），目标函数值等于每个决策变量各自对目标函数贡献的总和。 2、简述网络计划优化的思路与注意事项。
答：（1）优先关注单位时间紧缩成本最小的关键活动进行紧缩。（2）注重关键路径可能的变化。（3）充分利用非关键活动的松弛变量，合理调配资源。 3、简述线性规划的建模包括哪些内容。
答：（1）决策变量的识别与描述；（2）目标函数的识别与描述；（3）约束条件的识别与描述。 4、简述决策树方法的具体步骤。
答：具体步骤:（1）画一个方框作为出发点，称为决策点。从决策点画出若干条直线或折线，每条线代表一个行动方案，这样的直（折）线，称为方案枝。（2）在各方案枝的末端画一个圆圈，称为状态点，从状态点引出若干条直线或折线，每条线表示一种状态，在线旁边标出每一状态的概率，称为概率枝。 （3）把各方案在各种状态下的损益值标记在概率枝的末端。（4）把计算得到的每个方案的损益期望值标在状态点上，然后，通过比较，选出收益期望值最大（或损失期望值最小）的方案作为最优方案。 5、简述单纯形法的基本思路。
答：基本思路：确定可行域中的一个极点作为初始点（初始基本可行解），判断此极点是否为最优解，如不是则再找另一个使得其目标函数值更优的极点（称之为迭代），再判断此极点是否为最优解，直到找到一个极点为其最优解，或能判断出LP问题无最优解为止。
大工15秋《运筹学》开卷考试期末复习资料 第9页 共16页
大工15秋《运筹学》开卷考试期末复习资料
6、简述何谓最小支撑树问题，最小支撑树问题的常用方法有哪些。
答：如何找出网络的最小树就是最小支撑树问题。 最小支撑树问题可以采用避圈法和破圈法等方法进行求解，也可借助相关的运筹学软件包进行求解。 7、简述产销平衡运输问题的数学模型？
答：具有m个产地ai（i?1,2,?,m）和n个销地bj（j?1,2,?,n）的运输问题的数学模型为
minz???wijxij
i?1j?1mn?m(j?1,2,?,n)??xij?bj,1?i?n?(i?1,2,?m) s.t.??xij?ai,?j?1xij?0???对于产销平衡问题有
nm?b??ajj?1i?1i
运输问题有m?n个决策变量，m?n个约束条件。由于产销平衡条件，只有m?n?1个相互独立，因此，运输问题的基变量只有m?n?1个。 8、简述树的性质？
答：（1）任何树必存在次数为 1 的点；（2）具有n个节点的树 T 的边恰好为 n?1 条；（3）任何有n个节点，n?1 条边的连通图必是一棵树。 9、简述整数规划的求解方法有哪些？
答：整数规划的求解方法包括：（1）图解法；（2）分枝定（限）界法；（3）割平面法；（4）匈牙利法；（5）隐枚举法。
10、简述网络图的绘制原则和注意事项？
答：（1）节点标号原则：箭头节点的标号要大于箭尾节点的标号。（2）两个节点之间只能表示一道工序，只能划一条箭线。作业和箭线是一对一的关系。（3）全图只有一个起点、一个终点。（4）不能出现缺口与回路。（5）各项作业之间的关系：
1）作业a结束后可以开始b和c
大工15秋《运筹学》开卷考试期末复习资料 第10页 共16页
大工15秋《运筹学》开卷考试期末复习资料
2）作业c在a和b均结束后才能开始
3）ab两项作业结束后才可以开始c和d
4）作业c在a结束后即可进行，但作业d必须同时在a和b结束后才能开始
（6）从左到有，从上到下，尽量避免交叉。
五、计算题
1、某一最大化线性规划问题在利用单纯形法计算时得到表1。其中a,b,c,d,e,f为未知数，原问题中要求
大工15秋《运筹学》开卷考试期末复习资料 第11页 共16页
大工15秋《运筹学》开卷考试期末复习资料
各变量均非负。问a,b,c,d,e,f应满足什么条件下，有下面各解成立？
表1
CB XB x3 b f 2 6 x1 7 -1 x2 x3 1 0 0 0 x4 0 1 0 0 x5 e -1 -4 -3 x6 c -5 -3 0 0 1 0 x4 x6 cj?zj a b d （1）是非可行解； （2）是唯一最优解； （3）有无穷多最优解； （4）是退化基可行解；
（5）是可行解但非最优解，只有x1可以为换入变量且换出变量必为x6。
解：（1）当所有基变量取值均非负时的基解才是可行基解，故当f?0时，表中是非可行解。
（2）当现行解为可行解，且对应的非基变量的检验数均小于0时，线性规划问题才有唯一最优解，即f?0,b?0,d?0。
（3）当所有非基变量检验数都小于等于0且其中存在一个非基变量xj检验数等于0，而在xj的系数列向量中有大于0的分量时有无穷多最优解。所以f?0,b?0,d?0或f?0,d?0,b?0,c?0。
（4）现行解为退化基可行解的条件是基变量中含有零分量且所有的检验数均非正。所以
b?0,d?0,f?0。
（5）因是可行解，所以有f?0；非最优解且只有x1可以为换入变量，所以有b?0,d?0；只有x6可以为换出变量，所以有
f6f6?，故参数应满足：f?0,b?0,d?0，?。 7a7a2、已知：（1）运输问题的供需关系与单位运价表（见表1）； （2）用最小元素法求得表1的初始调运方案（见表2）；
试用闭回路法求其检验数，并判断此初始调运方案是否最优。
表1 供需关系与单位运价表
销地 产地 甲 乙 丙 丁 产量 大工15秋《运筹学》开卷考试期末复习资料 第12页 共16页
相关推荐：
loading