一、单项选择题（本大题共6小题，每小题3分，共18分）
1、设线性规划的约束条件为。
下列选项中属于其可行解的是（ c ）。
a．（1，1，1，1）
b．（1，2，1，1）
c．（1，2，0，3）
d．（0，2，2，4）
2、下列图形所包含的区域不属于凸集的是（ b ）。
a．正方形。
b．五角星。
c．圆。d．五边形。
3、已知下表是制订生产计划问题的一张lp最优单纯形表（极大化问题，约束条件均为“≤”型不等式），其中x4、x5、x6为松弛变量。
其对偶问题的最优解为（ c ）。
a．（0, 0, 0, 4, 0, 9）t
b．（0, 0, 0, -4, 0, -9）t
c．（4, 0, 9, 0, 0, 0）t
d．（-4, 0, -9, 0, 0, 0）t
4、对m个产地，n个销地的平衡运输问题，其基变量的个数为（ d ）。
a．m-nb．m+n
c．mnd．m+n-1
5、以下关于子图和部分图的叙述中，正确的是（ a ）。
a．图g1是图g2的部分图，那么g1也是g2的子图。
b．图g1是图g2的子图，那么g1也是g2的部分图。
c．图g1=是图g2=的子图，则v1=v2
d．图g1=是图g2=的部分图，则e1=e2
6、求网络图上任意两点之间最短距离的常用算法为（ b ）。
a．dijkstra算法。
b．矩阵算法。
c．破圈法。
d．避圈法。
二、判断题（本大题共5小题，每小题3分，共15分）
1、如果线性规划的原问题具有无界解，则其对偶问题一定存在可行解。 （错 ）
2、线性规划问题的最优解一定是可行解。 （对 ）
3、整数规划问题的求解可以先不考虑对变量的整数约束，作为一般性线性规划问题来求解，当解为非整数时可通过四舍五入或凑整方法得到最优解。 （错 ）
4、具有n个顶点的树的边数恰好为（n-1）条。 （对 ）
5、动态规划中运用**法的顺推方法和网络最短路径的标号法上是一致的。 （错 ）
三、名词解释题（本大题共5小题，每小题4分，共20分）
1、凸集：如果集合c中任意两个点x1、x2，其连线上的所有点也都是集合c中的点，称c为凸集。
2、完全图：一个简单图中若任意两点之间均有边相连，称为完全图。
3、关键路线：网络图中从最初事件到最终事件的不同的路中，作业总时间延续最长的一条路称关键路线。
4、网络图的合并：把若干个局部网络图归并成一个网络图称为网络图的合并。
5、决策：某阶段初从给定状态出发，决策者在面临的若干种不同方案中做出的选择称为决策。
四、简答题（本大题共4小题，每小题8分，共32分）
1、简述规划问题数学模型的组成要素？
答：规划问题的数学模型包括三个组成要素：（1）决策变量，指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量；（2）目标函数，指问题要达到的目的要求，表示为决策变量的函数；（3）约束条件，指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。
2、简述原问题与对偶问题的关系？
答：（1）原问题中求目标函数极大化，对偶问题中为求目标函数极小化；（2）原问题中约束条件个数等于对偶问题中变量的个数，原问题中变量的个数等于对偶问题中的约束条件个数；（3）原问题中约束条件符号为≤，对偶问题中约束条件符号为≥；（4）原问题目标函数的系数是其对偶问题约束条件的右端项，而原问题约束条件的右端项则是其对偶问题目标函数的系数。
3、简述分支定界法的基本步骤？
1）寻找替代问题并求解。方法是放宽或取消原问题的某些约束，找出一个替代问题；（2）分枝与定界。将替代问题分成若干子问题，对子问题也要求容易求解，且各子问题的解的集合和要包含原问题的解集。
然后对每个子问题求最优解，如该解满足原问题的约束，即找到了一个原问题的可行解，否则。
该解为所属分枝的边界值；如果所有子问题的最优解均非原问题的可行解，则选取其边界值最大或最小的子问题进一步再细分子问题求解。分枝过程一直进行下去，直到找到一个原问题的可行解为止。如果计算中同时出现两个以上可行解，则选取其中最大或最小的一个保留；（3）剪枝。
将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去。如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题的最优解。否则回到第二步，选取边界值最优的一个继续分枝。
如果计算中又出现新的可行解时，则与原可行解比较，保留最优的，并重复上述步骤。
4、简述计划评审法的优点？
1）能够直观清晰的反映计划各部门或各项工作之间的相互联系制约，便于掌握计划的全盘情况；
2）反映了某一部门或某一项工作在全局中的地位和影响，便于发现薄弱环节并进行控制、管理；
3）这种计划的编制可利用计算机进行数据推理运算，因此便于进行各种方案的分析比较。一旦发现某项工作偏离计划时，及时采取措施，保证整个计划按时完成。
五、计算题（本大题1小题，共15分）
1、试用dijkstra算法求图1中到的最短路。
图11．答：用dijkstra算法的步骤如下：
1）从点出发，对标号，将=0标注在旁的小方框内。令，其余点属于（见图1（a））；
2）同相邻的未标号点有。 ，即对点标号，将的值标注在旁的小方框内。将加粗，并令，（见图1（b））；
3）同标号点相邻的未标号点有，因有。
故对点标号，将的值标注在旁的小方框内。将加粗，并令，（见图1（c））；
4）同标号点相邻的未标号点有，因有。
故对点标号，将的值标注在旁的小方框内。将加粗，并令，（见图1（d））；
5）同标号点相邻的未标号点有，因有。
故对点标号，将的值标注在旁的小方框内。将加粗，并令，（见图1（e））；
6）同标号点相邻的未标号点有，因有。
故对点标号，将的值标注在旁的小方框内。将加粗，并令，（见图1（f））；
图17）同各标号点相邻的未标号点只有，因有。
故对点标号，将的值标注在旁的小方框内。将或者加粗，并令，（见图2）。
图2中的粗线表示从点到网络中其他各点的最短路，各点旁方框中的数字是从点到各点的最短距离。
图2一、单项选择题（本大题共6小题，每小题3分，共18分）
1、线性规划。
的对偶问题为（ d ）。a． b．
c．d．
2、**性规划问题的计算中，解的情况可能会出现以下哪种：（ d ）
a．唯一最优解。
b．无穷多最优解。
c．无界解。
d．以上情况都有可能。
3、若线性规划问题的可行域存在，则可行域是一个（ a ）。
a．凸集。b．整数集。
c．有限集。
d．无限集。
4、用表上作业法求解运输问题时，如果所有的检验数都（ b ），得到最优方案。
a．小于零。
b．大于等于零。
c．等于零。
d．不为零。
5、分配问题中如果人数大于任务数，应采取的措施是（ c ）。
a．删除人。
b．增添假想人。
c．增添假想任务。
d．以上都可以。
6、以下关于树的性质的叙述中，正确的是（ a ）。
a．任何树中必存在次为1的点。
b．具有n个顶点的树的边数恰好为（n+1）条。
c．任何具有n个点、（n-1）条边的简单图是树图。
d．树图的任意两个点之间都至少有一条通路。
二、判断题（本大题共5小题，每小题3分，共15分）
1、用单纯形法求解线性规划时，不论是极大化或是极小化问题，均用最小比值原则确定出基变量。 （对 ）
2、可以用解运输问题的表上作业法求解分配问题。 （对 ）
3、要求至少达到目标值的目标函数是max z=d+。 错 ）
4、目标规划的数学模型与线性规划的基本相同，所以用单纯形法求解时的方法步骤也基本相同。 （对 ）
5、无孤立点的图一定是连通图。 （错 ）
三、名词解释题（本大题共5小题，每小题4分，共20分）
1、割：将容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。
2、网络图的简化：把图中的一组作业简化为一个“组合”的作业。
3、增广链：如果在网络的发点和收点之间能找出一条链，在这条链上所有指向为s→t的弧，存在f0，这样的链称为增广链。
4、最短路问题：从给定的网络图中找出任意两点之间距离最短的一条路称为最短路问题。
5、偶图：如果图的顶点能分成两个互不相交的非空集合v1和v2，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图）
四、简答题（本大题共4小题，每小题8分，共32分）
1、简述单纯形法的计算步骤？
答：单纯形法的计算步骤如下：第一步，求出线性规划的初始基可行解，列出初始单纯形表；第二步，进行最优性检验；第三步，从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表；第四步，重复第。
二、三步一直到计算终止。
2、简述用表上作业法求解运输问题的初始方案的给定方法及其基本思路？
答：（1）最小元素法。最小元素法的基本思想是就近**，即从单位运价表中最小的运价开始确定供销关系，以此类推，一直到给出全部方案为止。
2）vogel法。从运价表上分别找出每行与每列的最小两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和**数量。当产地或销地中有一方数量上**完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤。
3、简述灵敏度分析的步骤？
答：（1）将参数的改变计算反映到最终单纯形表上来；
2）检查原问题是否仍为可行解；
3）检查对偶问题是否仍为可行解；
4）按照下表所列情况得出结论和决定继续计算的步骤。
4、简述用避圈法在给定的图中寻找最小部分树的基本步骤？
答：（1）从图中任选一点，让，图中其余点均包含在中；
2）从v与的连线中找出最小边，这条边一定包含在最小部分树内，不妨设最小边为，将加粗，以标记是最小部分树内的边；
3）令；4）重复两步，一直到图中所有点均包含在v中为止。
五、计算题（本大题1小题，共15分）
1、已知线性规划问题。
1）写出其对偶问题。
2）已知原问题最优解为，试根据对偶理论，直接求出对偶问题的最优解。
1．答：（1）原问题用矩阵形式写出：
根据对偶问题的定义，原问题的对偶问题用矩阵形式表示为。
即原问题的对偶问题为。
2）对偶定理：如果原问题有最优解，则对偶问题也一定具有最优解，且有。把。
带入原问题得。且可求得原问题中第三个约束条件为严格不等式，则，得到。
解得。因此，对偶问题的最优解为。
运筹学试卷 物流运筹学
2012 2013学年第一学期。运筹学 试卷。试卷 自拟送卷人 唐文广打印 校对 唐文广。一 6分 已知线性规划模型。写出该问题的对偶问题。二 15分 用单纯形法求解下面线性规划问题 作1张表即可 三 10分 求解下面标准指派问题，其中效率矩阵为。四 15分 某项工程由a b i j k等11项工序...
运筹学试题与案例集 运筹学
20xx年运筹学试题与案例集 天津。全国运筹学精品课程建设与题库案例交流研讨会运筹学试题与案例集 内部交流资料 中国运筹学会教育普及工作委员会 天津运筹学会 天津工业大学 20xx年5月 全国运筹学精品课程建设与题库案例交流研讨会 2010.05 目录 第一部分运筹学试题4 试题 1 北京工商大学4...
运筹学作业
运筹学关于库存的分析。主讲 秦舟 200900709071 摘要 关键词编辑 梁海琳 200900709074 模型制作 软件求解 欧迅 200900709077 秦舟 200900709071 理论综述与结果分析 林建佳 200900709069 秦普满 200900709067 参考文献与结论 ...