16.网络最大流问题

民航运筹学_中国民用航空飞行学院中国大学mooc课后章节答案期末考试题库2023年1.同一目标约束的一对偏差变量，至少有一个取值为0。

参考答案:正确2.目标规划问题一定存在最优解参考答案:错误3.在目标规划求解中，若高级别目标不能满足时，其后的低级别目标也一定不能满足。

参考答案:错误4.对于只有两个决策变量的目标规划问题，可用图解法求解。

参考答案:正确5.在用单纯形法求解目标规划时，利用最小比值法确定换出变量。

参考答案:正确6.目标规划的满意解不可能出现（）参考答案:di+>0，di- >07.用图解法求解目标规划问题，满意解在图中可能是（）参考答案:（A）（B）（C）之一8.以下叙述不正确的是（）参考答案:目标规划模型用单纯形法求解时，某些情况也需增加人工变量9.以下叙述正确的是（）参考答案:目标规划模型的约束中含绝对约束和目标约束10.产地个数为m销地个数为n的平衡运输问题的系数矩阵为A，则有r(A)≤m+n－1。

参考答案:错误11.表示作业法实质上是求解运输问题的单纯形法。

参考答案:正确12.按最小元素法（或Vogel法）给出的初始基可行解，从每一个空格出发可以找到唯一的闭回路。

参考答案:正确13.下列结论正确的有( )参考答案:表上作业法使用的条件是产量等于销量的平衡问题_用位势法判断一个解是否最优时，得出的位势值存在且唯一_任何运输问题都存在可行解14.有m个产地n个销地的平衡运输问题模型具有特征有( )参考答案:有mn个变量，m+n个约束_系数矩阵的秩等于m+n-1_有m+n-1个基变量，mn－m－n+1个非基变量15.当迭代到运输问题最优解时，如果有某非基变量的检验数等于0，则说明该运输问题有（）参考答案:多重最优解16.在求解运输问题的表上作业法中，空格的检验数值应等于（）参考答案:（闭回路上奇数次顶点运价之和）-（闭回路上偶数次顶点运价之和）17.关于产销不平衡的运输问题，下列叙述正确的是（）参考答案:当产大于销时，只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可18.产销平衡的运输问题的数学模型系数矩阵的Pij中只有两个元素取1，其余为0，这两个1的元素位于（）参考答案:第i行和第m+j行19.运输问题是一类特殊的线性规划问题，因而求解的结果为（）参考答案:可能出现唯一最优解或多重最优解20.对偶单纯形法适用于下列线性规划：在求目标函数最大值时，所有非基变量的检验数都小于等于0，但存在某些基变量的值为负数参考答案:正确21.在对偶单纯形法中，因为总存在<0的bi，选取数值最小的作为第r行，令br=min{bi}，其对应变量xr为换出基的变量。

《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。

CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。

DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。

CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。

DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。

CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时，我们选中的每一条路线( )。

CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( )。

一．单纯性法一．单纯性法1.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 122121212max 25156224..5,0z x x x x x s t x x x x =+£ìï+£ïí+£ïï³î 2.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12121212max 2322..2210,0z x x x x s t x x x x =+-³-ìï+£íï³î 3.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 1234123412341234max 24564282..2341,,,z x x x x x x x x s t x x x x x x x x =-+-+-+£ìï-+++£íï³î4.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 123123123123123max 2360210..20,,0z x x x x x x x x x s t x x x x x x =-+++£ìï-+£ïí+-£ïï³î 5.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12312312123max 224..26,,0z x x x x x x s t x x x x x =-++++£ìï+£íï³î6.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12121212max 105349..528,0z x x x x s t x x x x =++£ìï+£íï³î7.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 16 分）分） 12121212max 254212..3218,0z x x x x s t x x x x =+£ìï£ïí+£ïï³î二．对偶单纯性法二．对偶单纯性法1.灵活运用单纯形法和对偶单纯形法解下列问题（共灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分）分）12121212max 62..33,0z x x x x s t x x x x =++³ìï+£íï³î 2.灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共 15 分）分） 121212212max 3510501..4,0z x x x x x x s t x x x =++£ìï+³ïí£ïï³î 3.用对偶单纯形法求解下列线性规划问题（共用对偶单纯形法求解下列线性规划问题（共 15 分）分） 1212121212min 232330210..050z x x x x x x s t x x x x =++£ìï+³ïï-³íï³ïï³î4.灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共 15 分）分） 124123412341234min 262335,,,0z x x x x x x x s t x x x x x x x x =+-+++£ìï-+-³íï³î5.运用对偶单纯形法解下列问题（共运用对偶单纯形法解下列问题（共 16 分）分） 12121212max 24..77,0z x x x x s t x x x x =++³ìï+³íï³î6.灵活运用单纯形法和对偶单纯形法解下列问题（共灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分）分） 12121212max 62..33,0z x x x x s t x x x x =++³ìï+£íï³î三．0-1整数规划整数规划1.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12345123451234512345123345max 567893223220..32,,,,,01z x x x x x x x x x x x x x x x s t x x x x x x x x x x x or =++++-++-³ìï+--+³ïí--+++³ï=î 2.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共 10 分） 12312312323123min 4322534433..1,,01z x x x x x x x x x s t x x x x x or =++-+£ì++³ïí+³ïï=î 3.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共 10 分） 1234512345123451234512345max 20402015305437825794625..81021025,,,,01z x x x x x x x x x x x x x x x s t x x x x x x x x x x =++++++++£ìï++++£ïí++++£ïï=î或 4.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12345123451234512345max 2534327546..2420,,,,01z x x x x x x x x x x s t x x x x x x x x x x =-+-+-+-+£ìï-+-+£íï=î或 5.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12341234123412341234min 25344024244..1,,,01z x x x x x x x x x x x x s t x x x x x x x x =+++-+++³ì-+++³ïí+-+³ïï=î或6.7.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 123451234513451245max 325232473438..116333z x x x x x x x x x x x x x x s t x x x x =+--+++++£ìï+-+£ïí-+-³ï 1231231231223max 3252244..346z x x x x x x x x x s t x x x x =-++-£ìï++£ïï+£íï+£ïï=四.K-T 条件条件1.利用库恩-塔克（K-T ）条件求解以下问题（共）条件求解以下问题（共 15 分）分）22121122121212max ()104446..418,0f X x x x x x x x x s t x x x x =+-+-+£ìï+£íï³î2.利用库恩-塔克（K-T ）条件求解以下非线性规划问题。

运筹学2012参考资料（客观题）一. 判断题1、LP 问题的每一个基解对应可行域的一个顶点。

（×）2、LP 问题的基本类型是“max ”型问题。

（×）3、LP 问题的的每一个基可行解对应可行域的一个顶点。

（ √ ）4、在单纯形计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量为负。

（ √ ）5、对取值为无约束的变量j x ，通常令j j j x x x '''=-，其中,0j j x x '''≥。

在用单纯形法求得的最优解中有可能出现0j x '>且0j x ''>。

（×） 6、在单纯形的计算中，选取最大正检验数1j B j C C B P σ-=-对应的变量j x 作为换入变量，将使目标函数值得到最快的增长。

（×）6、在单纯形的计算中，选取最大负检验数1B j jC B P C σ-=-对应的变量j x 作为换入变量，将使目标函数值得到最快的增长。

（×） 7、某LP 有且仅有有限个（大于等于2）最优解。

（×）8、某LP 模型的可行域非空有界，则其顶点中必存在最优解。

（ √ ）9、用大M 法处理人工变量时，若最终表上基变量中仍含有人工变量，则原问题无可行解。

（×）10、若可行域是空集，则表明存在矛盾的约束条件。

（ √ ） 11、用单纯形法求LP 问题，若最终表上非基变量的检验数均非正，则该模型一定有惟一最优解。

（×） 12、凡具备优化、限制、选择条件且能将有关条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型来处理。

（ √ ）13、用单纯形法求解LP 问题时，无论是求极大化问题还是求极小化问题，用来确定基变量的最小比值原则相同。

（ √ ）14、若X 是某LP 的最优解，则X 必为该LP 可行域的某一个顶点。

一、判断( 每题参考分值2.5分)1、要求不超过目标值的目标函数是minZ=d+。

（）A. 正确错误:【A】2、部分变量要求是整数的规划问题称为混合整数规划。

（）A. 正确错误:【A】3、若线性规划存在两个不同的最优解,则必有无穷个最优解。

（）A. 正确错误:【A】4、线性规划的最优解一定是基本最优解。

（）A. 正确错误:【B】5、m+n－1个变量构成基变量组的充要条件是它们不包含闭回路。

（）A. 正确错误:【A】6、线性规划可行域无界,则具有无界解。

（）A. 正确错误:【B】7、可行解集有界非空时,则在极点上至少有一点达到最优解。

（）A. 正确错误:【A】8、要求至少到达目标值的目标函数是max Z=d+。

（）A. 正确错误:【B】9、匈牙利法是对指派问题求最小值的一种求解方法。

（）A. 正确错误:【A】10、运输问题一定存在最优解。

（）A. 正确错误:【A】11、对偶问题具有无界解，则原问题无最优解。

（）A. 正确错误:【A】12、凡基本解一定是可行解。

（）A. 正确错误:【B】13、若线性规划无最优解则其可行域无界。

（）错误:【B】14、互为对偶问题，或者同时都有最优解，或者同时都无最优解。

（）A. 正确错误:【A】15、对偶问题无可行解，原问题具有无界解。

（）A. 正确错误:【B】16、匈牙利法是求解最小值的分配问题。

（）错误:【A】17、要求不超过目标值的目标函数是min Z=d-。

（）A. 正确错误:【B】18、互为对偶问题，原问题有最优解，对偶问题可能无最优解。

（）A. 正确错误:【B】19、在最大流问题中，最大流是唯一的。

（）错误:【B】20、匈牙利法求解指派问题的条件是效率矩阵的元素非负。

（）A. 正确错误:【A】21、正偏差变量大于等于零，负偏差变量小于等于零。

（）A. 正确错误:【B】22、一对正负偏差变量至少一个等于零。

（）错误:【A】23、求最小值问题的目标函数值是各分枝函数值的下界。

最⼤流问题的⼏种经典解法综述⼀、什么是最⼤流问题假设现在有⼀个地下⽔管道⽹络，有m根管道，n个管道交叉点，现在⾃来⽔⼚位于其中⼀个点，向⽹络中输⽔，隔壁⽼王在另外⼀个点接⽔，已知由于管道修建的年代不同，有的管道能承受的⽔流量较⼤，有的较⼩，现在求在⾃来⽔⼚输⼊的⽔不限的情况下，隔壁⽼王能接到的⽔的最⼤值？为解决该问题，可以将输⽔⽹络抽象成⼀个联通的有向图，每根管道是⼀条边，交叉点为⼀个结点，从u流向v的管道能承受的最⼤流量称为容量，设为cap[u][v]，⽽该管道实际流过的流量设为flow[u][v]，⾃来⽔⼚称为源点s，隔壁⽼王家称为汇点t，则该问题求的是最终流⼊汇点的总流量flow的最⼤值。

⼆、思路分析关于最⼤流问题的解法⼤致分为两类：增⼴路算法和预流推进算法。

增⼴路算法的特点是代码量⼩，适⽤范围⼴，因此⼴受欢迎；⽽预流推进算法代码量⽐较⼤，经常达到200+⾏，但运⾏效率略⾼，如果腹⿊的出题⼈要卡掉⼤多数⼈的code，那么预流推进则成为唯⼀的选择。

( ⊙ o ⊙ )咳咳。

先来看下增⼴路算法：为了便于理解，先引⼊⼀个引理：最⼤流最⼩割定理。

在⼀个连通图中，如果删掉若⼲条边，使图不联通，则称这些边为此图的⼀个割集。

在这些割集中流量和最⼩的⼀个称为最⼩割。

最⼤流最⼩割定理：⼀个图的最⼤流等于最⼩割。

⼤开脑洞⼀下，发现此结论显⽽易见，故略去证明（其实严格的证明反⽽不太好写，但是很容易看出结论是对的，是吧）。

这便是增⼴路算法的理论基础。

在图上从s到t引⼀条路径，给路径输⼊流flow，如果此flow使得该路径上某条边容量饱和，则称此路径为⼀条增⼴路。

增⼴路算法的基本思路是在图中不断找增⼴路并累加在flow中，直到找不到增⼴路为⽌，此时的flow即是最⼤流。

可以看出，此算法其实就是在构造最⼩割。

增⼴路算法⽽预流推进算法的思路⽐较奇葩（没找到⽐较好的图，只能⾃⾏脑补⼀下了。

= =#）：先将s相连的边流⾄饱和，这种边饱和的结点称为活动点，将这些活动点加⼊队列，每次从中取出⼀个点u,如果存在⼀个相邻点v是⾮活动点，则顺着边u->v 推流，直到u变为⾮活动点。

2014-2015复习一、名词解释（5道，15分）1.优化2.线性规划生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。

3.可行解:满足约束条件解为可行解。

4.可行域所有可行解的集合为可行域。

5.基:设A为约束条件②的m× n阶系数矩阵(m<n)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣ B∣≠0），称B是规划问题的一个基。

6.基本可行解:满足变量非负约束条件的基本解，简称基可行解。

7.影子价格在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。

8.灵敏度分析:当某一个参数发生变化后，引起最优解如何改变的分析。

可以改变的参数有：bi ——约束右端项的变化，通常称资源的改变；cj ——目标函数系数的变化，通常称市场条件的变化；pj ——约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。

9.运输问题10.整数规划要求一部分或全部决策变量取整数值的规划问题称为整数规划。

11.0-1规划决策变量只能取值0或1的整数规划。

12.松弛问题13.目标规划目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。

14.偏差变量15.链图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。

16.路链中所有顶点不相同，这样的链称为路17.最小生成树如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。

树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。

18.PERT网络图注重于对各项工作安排的评价和审查。

19.关键路线法各弧权重总和最大的路线，或称主要矛盾路线，它决定网络图上所有作业需要的最短时间。

大工22秋《运筹学》在线作业2-辅导资料-答案
试卷总分:100 得分:100
一、单选题 (共 5 道试题,共 40 分)
1.网络图中,每项活动的最晚完成时间等于其所有紧后活动最晚开始时间的( )。

A.最大值
B.最小值
C.平均值
D.总和
【本题-参考-答案】:B
2.截集中一切弧的容量之和称为( )。

A.最大流
B.截量
C.最小截量
D.最大截量
【本题-参考-答案】:B
3.下列有关网络图的说法中,错误的为( )。

A.网络图中所谓路径，就是从始点到终点之间相连节点的序列
B.为了完成整个项目的进度计划，需要找出其中最长的路径，即关键路径
C.关键路径上的活动称为项目的关键活动，是整个项目中的关键环节
D.网络中仅存在一条路径
【本题-参考-答案】:D
4.以下说法中不正确的为( )。

A.完成各个作业需要的时间最长的路线为关键路线
B.关键路线上的作业称为关键作业
C.所有关键作业的总时差为0
D.以上说法均不正确
【本题-参考-答案】:D
5.下列有关图的说法中,错误的为( )。

A.点表示所研究的事物对象
B.边表示事物之间的联系
C.无向图是由点及边所构成的图
D.无环的图称为简单图
【本题-参考-答案】:D
二、判断题 (共 15 道试题,共 60 分)
6.最大流问题是一个特殊的线性规划问题。

【本题-参考-答案】:正确
7.如果一个图由点及边所构成,则称之为有向图。

【本题-参考-答案】:错误。

《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ ）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（ ）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（ ）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。

CA.降低的 B .不增不减的 C .增加的 D .难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。

DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。

CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A ，B ，C 三相邻结点的距离分别为15km ，20km,25km ，则（ ）。

DA.最短路线—定通过A 点B.最短路线一定通过B 点C.最短路线一定通过C 点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈 C .存在三个圈 D .不含圈11.网络图关键线路的长度( )工程完工期。

CA.大于B.小于C.等于D.不一定等于 600 700300 500 400锅炉房12312.在计算最大流量时，我们选中的每一条路线( )。

分房间问题的解题思路引言分房间问题是一个在日常生活中经常遇到的问题，尤其是在有限的房间资源下，合理地分配房间是必不可少的。

本文将通过不同的角度和方法，深入探讨分房间问题的解题思路。

分房间问题的背景在许多场景中，如学生宿舍、旅馆、养老院等，需要将一定数量的人员分配到有限数量的房间中。

分房间问题的目标是找到一种合理的分配方式，使得每个人都有一个房间，并且不浪费任何空房间。

解题思路一：贪心算法贪心算法是一种常用的解决优化问题的算法，它通过每一步选择中的局部最优解，最终得到全局最优解。

在分房间问题中，可以按照以下步骤进行：1.将所有房间按照容量从小到大排序。

2.将所有人员按照人数从多到少排序。

3.依次将每个人员分配到容量最小的房间中。

4.如果有多个房间容量一样小的，则选择剩余容量最大的房间。

这种方法的优点是简单易实现，但不一定能得到最优解。

因为贪心算法只考虑了当前的最优选择，没有考虑到未来可能出现的更好的选择。

解题思路二：动态规划动态规划是一种利用已求解的子问题来求解更大规模问题的方法。

在分房间问题中，可以使用动态规划的思路来解决。

1.创建一个二维数组dp，其中dp[i][j]表示前i个人员分配到前j个房间的最优解。

2.初始化第一行和第一列的值为0，表示没有人员或没有房间时的最优解为0。

3.对于每个dp[i][j]，可以考虑两种情况：–不将第i个人员分配到第j个房间，此时dp[i][j] = dp[i][j-1]。

–将第i个人员分配到第j个房间，此时dp[i][j] = dp[i-1][j-1] + 1。

4.选择以上两种情况中的最大值作为dp[i][j]的值。

5.最终的最优解为dp[N][M]，其中N为人员数量，M为房间数量。

动态规划的优点是能够得到最优解，但需要额外的存储空间和计算时间。

解题思路三：网络流问题将分房间问题建模为网络流问题，可以通过最大流算法求解。

以下是解题步骤：1.创建一个源点s和一个汇点t。

《运筹学》作业答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

（√）2.线性规划问题的每一个基解对应可行解域的一个顶点。

（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。

（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。

（√）5.单纯形法计算中，如果不按最小比值规划选出基变量，则在下一个解中至少有一个基变量的值为负。

（√）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。

（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。

（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。

（╳）9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

（√）10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。

（√）二、线性规划建模题：1.某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有：甲商品不少于240件，乙商品不少于80台，丙商品不少于120吨。

已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部；从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台，丙商品2吨，运费160元/每部。

问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少解：设营业部每天应发往A、B两仓库各x1，x2部汽车,则有：12 121212min200160 47240 2280 621200(1,2)jW x xx xx xx xx j=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥=⎩2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是该企业计划用于此项广告宣传的经费预算是80万元，此外要求：①至少有200万人次妇女接触广告宣传；②电视广告费用不得超过50万元, ③电视广告至少占用三个单元一般时间和两个单元黄金时间, ④广播和报纸广告单元均不少于5个单元而不超过10个单元。

一、单项选择题1、下列叙述正确的是（）。

A．线性规划问题，若有最优解，则必是一个基变量组的可行基解B．线性规划问题一定有可行基解C．线性规划问题的最优解只能在最低点上达到D．单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A2、线性规划的变量个数与其对偶问题的（）相等。

A．变量目标函数B．变量约束条件C．约束条件个数D．不确定答案：C3、在利用表上作业法求各非基变量的检验数时，有闭回路法和（）两种方法。

A．西北角法B．位势法C．最低费用法D．元素差额法答案：B4、下列各项（）不是目标规划的特点。

A．多目标B．单一目标C．具有优先次序D．不求最优答案：B5、下列关于图的说法中，错误的为（）。

A．点表示所研究的事物对象B．边表示事物之间的联系C．无向图是由点及边所构成的图D．无环的图称为简单图答案：D6、利用单纯形法求解线性规划问题时，首先需要（）。

A．找初始基础可行基B．检验当前基础可行解是否为最优解C．确定改善方向D．确定入变量的最大值和出变量答案：A7、对偶问题最优解的剩余变量解值（）原问题对应变量的检验数的绝对值。

A．大于B．小于C．等于D．不能确定答案：C8、当某个非基变量检验数为零，则该问题有（）。

A．无解B．无穷多最优解C．退化解D．惟一最优解答案：B9、PERT 网络图中，（）表示一个工序。

A．节点B．弧C．权D．关键路线答案：B10、假设对于一个动态规划问题，应用顺推法以及逆推解法得出的最优解分别为P和D，则有（）。

A．P>D B．P<DC．P=D D．不确定答案：C11、下列有关线性规划问题的标准形式的叙述中错误的是（）。

A．目标函数求极大B．约束条件全为等式C．约束条件右端常数项全为正D．变量取值全为非负答案：C12、线性规划问题的数学模型由目标函数、约束条件和（）三个部分组成。

A．非负条件B．顶点集合C．最优解D．决策变量答案：D13、如果原问题有最优解，则对偶问题一定具有（）。

注意：1、运筹学考1、2、5、6章，题目都是书上的例题，这是判断题。

2、题型:填空，选择，判断，建模，计算。

3、发现选择题中一个错误，第6章第2题，答案应该C。

4、大部分建立模型和计算是第一章内容，加选择判断题目已经发给你们了，主要考对概念，性质，原理，算法的理解。

判断题一、线性规划1.若线性规划存在最优解则一定存在基本最优解2.若线性规划无界解则其可行域无界3.可行解一定是基本解4.基本解可能是可行解5.线性规划的可行域无界则具有无界解6.最优解不一定是基本最优解7.x j的检验数表示变量x j增加一个单位时目标函数值的改变量8.可行解集有界非空时,则在极点上至少有一点达到最优值9.若线性规划有三个最优解X(1)、X(2)、X(3)，则X=αX(1)+(1-α)X(3)及X=α1X(1)+α2X(2)+α3X(3)均为最优解,其中10.任何线性规划总可用大M单纯形法求解11.凡能用大M法求解也一定可用两阶段法求解12.两阶段法中第一阶段问题必有最优解13.两阶段法中第一阶段问题最优解中基变量全部非人工变量,则原问题有最优解14.任何变量一旦出基就不会再进基15.人工变量一旦出基就不会再进基16.普通单纯形法比值规则失效说明问题无界15.将检验数表示为λ＝C B B-1A－C的形式,则求极大值问题时基可行解是最优解的充要条件是λ≥018.当最优解中存在为零的基变量时,则线性规划具有多重最优解19.当最优解中存在为零的非基变量时,则线性规划具唯一最优解20.可行解集不一定是凸集21.将检验数表示为的形式,则求极小值问题时,基可行解为最优解当且仅当λj≥0，j＝1,2,…，n22.若线性规划存在基本解则也一定存在基本解可行解23.线性规划的基本可行解只有有限多个24.在基本可行解中基变量一定不为零25.123 123123123 max34 |25|5010100,0,0Z x x xx x xx x xx x x=+-++≤⎧⎪-+≥⎨⎪≥≥≥⎩是一个线性规划数学模型二对偶规划1.任何线性规划都存在一个对应的对偶线性规划2.原问题(极大值)第i个约束是“≥”约束，则对偶变量y i≥03.互为对偶问题，或者同时都有最优解，或者同时都无最优解4.对偶问题有可行解，则原问题也有可行解5.原问题有多重解，对偶问题也有多重解在以下6～10中，设X*、Y*分别是的可行解6.则有CX*≤Y*b7.CX*是w的下界8.当X*、Y*为最优解时，CX*=Y*b；9.当CX*=Y*b时，有Y*X s+Y s X*=0成立10.X*为最优解且B是最优基时，则Y*=C B B－1是最优解11.对偶问题有可行解，原问题无可行解，则对偶问题具有无界解12.原问题无最优解，则对偶问题无可行解13.对偶问题不可行，原问题无界解14.原问题与对偶问题都可行，则都有最优解15.原问题具有无界解，则对偶问题不可行16.若某种资源影子价格为零，则该资源一定有剩余17.原问题可行对偶问题不可行时，可用对偶单纯形法计算18.对偶单纯法换基时是先确定出基变量，再确定进基变量19.对偶单纯法是直接解对偶问题问题的一种方法20.对偶单纯形法比值失效说明原问题具有无界解21.在最优解不变的前提下，基变量目标系数c i的变化范围可由式确定22.在最优基不变的前提下，常数b r的变化范围可由式确定，其中为最优基B的逆矩阵第r列23.减少一约束，目标值不会比原来变差24.增加一个变量，目标值不会比原来变好25.当b i在允许的最大范围内变化时，最优解不变三、整数规划1.整数规划的最优解是先求相应的线性规划的最优解然后取整得到2.部分变量要求是整数的规划问题称为纯整数规划3.求最大值问题的目标函数值是各分枝函数值的上界4.求最小值问题的目标函数值是各分枝函数值的下界5.变量取0或1的规划是整数规划6.整数规划的可行解集合是离散型集合7. 0－1规划的变量有n个，则有2n个可行解8.6x1+5x2≥10、15或20中的一个值，表达为一般线性约束条件是6x1+5x2≥10y1+15y2+20y3，y1+y2+y3＝1，y1、y2、y3＝0或19. 高莫雷（R.E.Gomory）约束是将可行域中一部分非整数解切割掉10.隐枚举法是将所有变量取0、1的组合逐个代入约束条件试算的方法寻找可行解四、目标规划1.正偏差变量大于等于零，负偏差变量小于等于零2.系统约束中没有正负偏差变量3.目标约束含有正负偏差变量4.一对正负偏差变量至少一个大于零5.一对正负偏差变量至少一个等于零6.要求至少到达目标值的目标函数是max Z=d+7.要求不超过目标值的目标函数是 min Z=d-8.目标规划没有系统约束时，不一定存在满意解9.超出目标值的差值称为正偏差10.未到达目标的差值称为负偏差五、运输与指派问题1.运输问题中用位势法求得的检验数不唯一2.平衡运输问题一定有最优解3.不平衡运输问题不一定有最优解4.产地数为3，销地数为4的平衡运输问题有7个基变量5.m＋n－1个变量组构成一组基变量的充要条件是它们不包含闭回路6.运输问题的检验数就是其对偶变量7.运输问题的检验数就是对偶问题的松驰变量8.运输问题的位势就是其对偶变量9.不包含任何闭回路的变量组必有孤立点10.含有孤立点的变量组一定不含闭回路11.用一个常数k加到运价矩阵C的某列的所有元素上，则最优解不变12.令虚设的产地或销地对应的运价为一任意大于零的常数c(c>0),则最优解不变13.若运输问题的供给量与需求量为整数，则一定可以得到整数最优解14.按最小元素法求得运输问题的初始方案, 从任一非基格出发都存在唯一一个闭回路15.运输问题中运价表的每一个元素都分别乘于一个常数,则最优解不变16.运输问题中运价表的每一个元素都分别加上一个常数,则最优解不变17.5个产地6个销地的平衡运输问题有11个变量18.5个产地6个销地的平衡运输问题有30个变量19.5个产地6个销地的销大于产的运输问题有11个基变量20.产地数为3销地数为4的平衡运输中，变量组{x11,x13,x22,x33,x34}可作为一组基变量六、网络模型1.容量不超过流量2.最大流问题是找一条从起点到终点的路，使得通过这条路的流量最大3.容量C ij是弧（i，j）的最大通过能力4.流量f ij是弧（i，j）的实际通过量5.可行流是最大流的充要条件是不存在发点到收点的增广链6.截量等于截集中弧的流量之和7.任意可行流量不超过任意截量8.任意可行流量不小于任意截量9.存在增广链说明还没有得到最大流量10.存在增广链说明已得到最大流11.找增广链的目的是：是否存在一条从发点到收点的路，使得可以增加这条路的流量12.狄克斯屈拉算法是求最大流的一种标号算法13.破圈法是：任取一圈，去掉圈中最长边，直到无圈14.避圈法（加边法）是：去掉图中所有边，从最短边开始添加，加边的过程中不能形成圈，直到连通（n－1条边）15.连通图一定有支撑树16.P是一条增广链，则后向弧上满足流量f ≥017.P是一条增广链，则前向弧上满足流量f ij≤C ij18.可行流的流量等于每条弧上的流量之和19.最大流量等于最大流20.最小截集等于最大流量七、网络计划1.网络计划中的总工期是网络图中的最短路的长度2.紧前工序是前道工序3.后续工序是紧后工序4.虚工序不需要资源，是用来表达工序之间的衔接关系的虚设活动5.A完工后B才能开始，称A是B的紧后工序6. 单时差为零的工序称为关键工序7.关键路线是由关键工序组成的一条从网络图的起点到终点的有向路8.关键路线一定存在9.关键路线存在且唯一10.计划网络图允许有多个始点和终点11.事件i的最迟时间T L（i）是指以事件i为完工事件的工序最早可能结束时间12.事件i的最早时间T E（i）是以事件i为开工事件的工序最早可能开工时间13.工序（i，j）的事件i与j的大小关系是i < j14.间接成本与工程的完工期成正比15.直接成本与工程的完工期成正比16.17.18.19.20.1 线性规划1= "对"2= "对"3 = "错"4= "对"5= "错"6 = "对"7= "对"8= "对"9 = "对" 10= "对" 11= "对" 12 = "对" 13= "错" 14= "错" 15= "对" 16= "对" 17= "对" 18 = "错" 19= "错" 20 = "错" 21= "对" 22 = "错" 23= "对"24 = "错"25 = "错" 2对偶问题1="对"2= "错"3 = "对"4= "错"5 = "错"6= "错"7 = "错"8= "对"9= "对"10 = "对"11 = "对"12= "错"13 = "错"14 = "对"15 = "对"16 = "错"17 = "错"18= "对"19 = "错"20= "错"21= "对"22 = "错"23= "对"24= "错"25= "错"3 整数规划1= "错"2 = "错"3 = "对"4 = "对"5 = "对"6= "对"7 = "错"8= "对"9 = "对"10= "错4 目标规划1="错"2 = "对"3 = "对"4 = "错"5= "对"6 = "错"7= "错"8 = "错"9 = "对"10= "对"5 运输问题1 = "错"2 = "对"3 = "错"4 = "错" 5= "对"6 = "错"7 = "对"8 = "对" 9= "对" 10= "错"11 = "对"12 = "对"13 = "对"14 = "对"15 = "对"16 = "对"17 = "错"18 = "对"19 = "对" 6 网络模型1 = "错"2 = "错"3 = "对"4 = "对"5 = "对"6 = "错"7 = "对"8 = "错"9 = "对"10 = "错"11 = "对"12 = "错"13 = "对"14 = "对"15 = "对"16 = "错"17 = "错"18 = "错"19 = "错"7 网络计划1 = "错 "2 = "对"3 = "错"4 = "对"5= "错"6 = "错"7 = "对"8 = "对"9= "错"10 = "错"11 = "错"12= "对"12= "对"14 = "对"15 = "错"16 = "错"17 = "对"18 = "对"19 = "错"20 = "错" 20 = "错" 20 = "对"《运筹学》模拟试题及参考答案一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。

第一章测试1.运筹学发展史上的里程碑标志性事件是（）。

A:单纯形法、优选法B:单纯形法、统筹法C:单纯形法、计算机的普及与发展D:统筹法、优选法答案:C2.关于“齐王赛马”，下列说法正确的是（）。

A:标志着运筹学作为一门学科的产生B:齐王输了，说明齐王的马不行C:其余选项说法全对D:是中国历史上运筹学思想的一个应用案例答案:D3.关于运筹学与决策过程，下列说法对的是（）。

A:认清问题是决策过程的逻辑起点B:需要提供多个可选方案C:方案经评估后选出最优方案从而做出决策D:确定目标是决策过程的重要一环答案:ABCD4.运筹学是指（）。

A:为决策者提供有依据的最优方案，以实现最有效的管理。

B:是应用分析、试验、量化的方法C:对经济管理系统中的人力、物力、财力等资源进行统筹安排D:运筹学概念中，最主要的关键词是：量化、有依据、最优答案:ABCD5.运筹学中的决策过程包括（）。

A:发现并认清问题B:实践检验，返回修改方案C:制订评估标准，评估方案，选出最优方案D:提供解决问题的多个行动方案答案:ABCD6.认清问题是运筹学关于决策过程的逻辑起点，方案评估是其中心环节。

（）A:错B:对答案:B7.计算机的应用，标志着运筹学作为一门学科的产生。

（）A:对B:错答案:B8.运筹学被广泛应用，得益于计算机的发展与推广。

（）A:对B:错答案:A9.运筹学是关于线性规划问题的学科。

（）A:错B:对答案:A10.我国是在1957年开始成功应用运筹学于工商管理。

（）A:对B:错答案:A第二章测试1.下列说法只有一个是错误的，请指出来（）。

A:无可行解则无最优解B:无界解是指线性规划问题有解，但无最优解。

C:无界解有无数个最优解D:无可行解是指没有一个解能满足所有约束条件答案:C2.可行域是指：（）。

A:包含基本解的区域B:可行解的集合C:包含可行解的区域D:包含最优解的区域答案:B3.与对偶价格相关联的参数是（）。

A:约束条件常数项bB:目标函数系数cC:其余选项全对D:约束条件中的a答案:A4.关于等值线，下列说法正确的是：（）。

运筹学 复习题A一：单选题（本大题共10小题，每题3分，共30分）1．对线性规划问题标准型：maxZ=CX,AX=b,X ≥0,利用单纯形法求解时，每作一次换基迭代，都能保证它相应得目标函数值Z 必为（C ）A ．增大B ．减少C ．不减少D ．不增大 2．某二维线性规划问题的可行域为一正方形，则该问题的最优解（D ） A. 必在正方形的一条边上达到 B.必在正方形内部达到 C.必在正方形外部达到 D. 必在正方形的某个顶点达到 3．线性规划的对偶问题和原问题存在如下关系( A )A ．对偶问题的对偶是原问题 B.原问题存在可行解，对偶问题必存在可行解 C ．原问题无可行解，其对偶问题必无可行解 D ．原问题有最优解，则对偶问题也有最优解,且最优解相同 4．求解需求量大于供应量的运输问题不需要做的是( D )A ．虚设一个供应点B ．令虚设的供应点到任何需求点的单位运费为0C ．取虚设的供应点的供应量为恰当值D ．删去一个需求点5．线性规划解的情况，不包括以下哪一种？( B ) A ．恰好有一个最优解 B ．恰好有两个最优解 C ．无解 D ．无界解6．任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值( C )相应的线性规划的最大目标函数值。

A ．小于 B.大于 C.小于或等于 D.大于或等于 7．在利润最大化的生产计划中，下列说法错误的是( B )A.影子价格大于0的资源没有剩余B.有剩余的资源影子价格大于0；C.安排生产的产品机会成本等于利润D.机会成本大于利润的产品不安排生产。

8． 下列是关于标准的∞∞//1//M M排队模型的叙述，其中不正确的是( B )A ．顾客到达过程服从泊松分布 B.服务时间服从泊松分布C ．单通道即只有一个服务台 D. 排队长度及顾客来源无限制9． 如下表所示为大海和丽娟的“情侣博弈”，行策略表示大海的策略，列策略表示丽娟的策略，其中的数值为在不同局势下他们的益损值（或满意度）,前后两个数值分别表示大海、丽娟的益损值。

中南大学网络教育课程考试复习题及参考答案运筹学一、判断题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

[ ]2.线性规划问题的每一个基本解对应可行解域的一个顶点。

[ ]3.任何线性规划问题存在并具有惟一的对偶问题。

[ ]4.已知y i*为线性规划的对偶问题的最优解，若y i*＞0，说明在最优生产计划中第i种资源已完全耗尽。

[ ]5.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。

[ ]6.订购费为每订一次货所发生的费用，它同每次订货的数量无关。

[ ]7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。

[ ]8.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。

[ ]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。

[ ]10.用大M法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。

[ ]11.如图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[vi,vj]必不包含在最小支撑树内。

[ ] 12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。

[ ] 13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。

[ ] 14.在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。

[ ] 15.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。

[ ]16.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。

[ ]17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。