运筹学考试题b卷及答案

运筹学期末考试题（b卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、单项选择题（每小题1分，共10分）1：下列关于运筹学的缺点中，不正确的是（）在建立数学模型时，若简化不慎，用运筹学求得的最优解会因与实际相差大而失去意义运筹学模型只能用借助计算机来处理有时运筹学模型并不能描述现实世界由于运筹学方法的复杂性使一些决策人员难以接受这些解决问题的方法TOC\o"1-5"\h\z2：在下面的数学模型中，属于线性规划模型的为（）maxS=4X+YminS=3X+YmaxS=X2+Y2minS=2XYA.<s.t.XY<3B.<s.t.2X-Y>-1C.<s.t.X-Y<2D.<s.t.X+Y>3、X,Y>0、X,Y>0X,Y>0〔X,Y>0TOC\o"1-5"\h\z3.线性规划一般模型中，自由变量可以用两个非负变量的（）代换。和B.商C.积D.差4：以下关系中，不是线性规划与其对偶问题的对应关系的是（）。约束条件组的系数矩阵互为转置矩阵一个约束条件组的常数列为另一个目标函数的系数行向量两个约束条件组中的方程个数相等约束条件组的不等式反向TOC\o"1-5"\h\z5.对偶问题的对偶是（）A.原问题B.解的问题C.其它问题D.基本问题6：若原问题中气＞0，那么对偶问题中的第i个约束一定为（）A.等式约束B.、将”型约束C.、'2”约束D.无法确定7：若运输问题已求得最优解，此时所求出的检验数一定是全部（）A.小于或等于零B.大于零C.小于零D.大于或等于零8：考虑某运输问题，其需求量和供应量相等，且供应点的个数为m，需求点的个数是n。若以西北角法求得其初始运输方案，则该方案中数字格的数目应为（）A.（m+n）个B,（m+n-1）个C.（m-n）个D.（m-n+1）个9：关于动态规划问题的下列命题中错误的是（）A、动态规划分阶段顺序不同，则结果不同B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：若P为网络G的一条流量增广链，则P中所有逆向弧都为G的（）C.零流弧D.不饱和边A.非零流弧B.饱和边二、判断题（每小题1分，共10分）1：如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（）2：线性规划问题的每一个基解对应可行域的一个顶点（）3：若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解（）4：对偶问题的对偶问题一定是原问题。（）5：任何线性规划问题存在并具有唯一的对偶问题。（）6：运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。（）7：动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。（）8：一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段，如将决定七的值作为第一阶段，决定气的值作为第二阶段等。（）9：在任意图中，当点集确定后，树是图中边数最少的连通图。（）10：求网络最大流的问题可以归结为求解一个线性规划模型。（）三、填空题（每空1分，共15分）1：满足所有约束条件的一组值称为线性规划的，这些解中，使目标函数取得最大或最小值的解称为线性规划问题的。C.零流弧D.不饱和边2：在单纯形法中，初始基可能由、和三种类型的变量组成。3：若原始问题可行，则其目标函数无界的充要条件是对偶问题；若对偶问题为无界解，其原问题为。4：在运输问题模型中，计算检验数的方法一般有和两种方法。5：动态规划方法的步骤可以总结为：逆序求解，顺序求、和6：树的任意两个顶点之间有且只有一条。7：网络中满足容量限制条件和中间点平衡条件的弧上的流称。四、计算题（每小题15分，45分）1：已知线性规划：maxz=3x+2x—x+2xV43X+2X<12S.t.\12X1-X2<3X,X>0（a）：用单纯形方法求解该线性规划问题的最优解和最优值；（b）：写出线性规划的对偶问题；（c）：求解对偶问题的最优解和最优值。2：今有1000台机床，要投放到A、B两个生产部门，计划连续使用3年。已知对A部门投入uA台机器时的年收益是g（uA）=4匕（元），机器的完好率a=0.5，相应的B部门的年收益是叫）=2u注元），完好率b=爵。试求3年间总收益最大的年度机器分配3：用破圈法和生长法求下图的最短树。%8v4五、问答题（每小题5分，共10分）简述动态规划建模的一般过程和最优性原理。网络最短路线问题的求解有多种方法，一般有狄克斯拉算法、海斯算法和福德算法。试分析各自适用的范围和优缺点。期末考试参考答案及评分标准（b卷）单项选择题（每小题1分，共10分）TOC\o"1-5"\h\z1.B2.B3.D4.C5.A6.C7.D8.B9.A10.A判断题（每小题1分，共10分）1.T2.F3.F4.T5.T6.F7.T8.F9.T10.T填空题（每空1分，共15分）1：可行解、最优解；2：决策变量、松弛变量、人工变量；3：没有可行解、无可行解；4：闭回路法、位势法；5：最优目标函数、最优策略、最优路线、最优目标函数值；6：初等链;7：可行流。计算题（每小题15分，45分）1：解a）:[18,3,32,0,0]555.18“3smaxz=3x—+2x=1255（5分）b）:其对偶问题为minw=4y+12y+3yF+3y2+^3-3s.t.<2y1+2y2-y3-2y,y,y-0、123（5分）c）：y*=[0,1,0]，（5分）w*=z*=4x0+12x1+3x0=c）：（5分）2：解该问题可以作为三段资源分配问题，每个年度是一个阶段。k阶段状态变量气取为该年度初完好的设备数，决策变量u取为该年度投入A活动的设备数,则有0<气<1000，0<u<x。状态转移方程为：x=0.5"+0.9（x-u）；相应的动态规划基本方程为:kkk+1kkkf（x）=max{4u2+2（x一u）2+f（x）}kkkkkk+1k+1u

k其中：x^1=0.5uk+0.9（x^-uk）（3分）首先逆序求解条件最有目标函数值集合和条件最有决策集合：k=3时，0<u<x，注意到f（x）=0，有f（x）=max｛4u2+2（x一u）2｝。最大值334433333u3发生在［0,x］的端点。3u=0时，4u2+2（x一u）2=2x2，而u=x时，4u2+2（x一u）2=4x2TOC\o"1-5"\h\z33333333333可知：f（x3）=4x2，u'3（x3）=x3（3分）k=2时，0<u<x,注意到x=0.5u+0.9（x一u）和上面求出的f（x），有22322233f（x）=max{4u2+2（x一x）2+f（0.5u+0.9（x一u））}

222223222u2=max{4u2+2（x一x）2+4[0.5u+0.9（x一u）]2}222222u2最大值发生在［0,x2］的端点。比较％=0和％=X2时｛｝内的值可知:（3分）（3分）f（x）=5.24x2,u（x）=0k=1时，0<u<x，注意到x=0.5u+0.9（x一u）和上面求出的f（x），有TOC\o"1-5"\h\z112111（3分）（3分）f（x）=max{4u2+2（x一x）2+f（0.5u+0.9（x一u））}

111112111u1=max{4u2+2（x一x）2+5.24[0.5u+0.9（x一u）]2}111111u1最大值发生在［0,x1］的端点。比较u1=0和u1=x1时｛｝内的值可知:f1（x1）=6.24444x2,〈（气）=0由于x1=1000已知，因此条件最优目标函数值阜气）就是整个计划周期内的最大收益R*，其值为：R*=f(x)=6.2444x10002=6244400

ii

・•・u*=u1(1000)=0,

x*=0.5u*+0.9(x*-u*)=900,

u*=u、(900)=0,

x*=0.5u*+0.9(x-u*)=810,

u*=u'3(810)=810,

x*=0.5u*+0.9(x*-u*)=405,最优分配方案时第一年把1000设备全部投放到部门B,阶段收入为200万元，年末完好设备900台；第二年把900台完好设备全部全部投入部门B，年收入162万元，年末完好设备810台；第三年把810台完好设备全部投入部门A，年收入为262.44万元，年末完好设备为405台。三年总收入最大为624.44万元。——(3分)3：解破圈法(1)：取圈v,v,v,v，去掉边［v,v］。(2)：取圈v,v,v,v，去掉边［v,v］。TOC\o"1-5"\h\z123113243224（3）：取圈v,v,v,v，去掉边［v,v］。（4）：取圈v,v,v,v,v，去掉边［v,v］。2352253455334在图中已无圈，此时，p=6，而q=p-1=5，因此所得的是最短树。结果如下图，其树的总长度为12。.(6分)七-■.------(3分)生长法根据生长法的基本原理，得以下计算表vvvvvS1{2}6888v23898S2{3}898v3538S35{3}8

vS4vS581vS4vS5815{1}3{3}1：动态规划建模应完成如下工作:（1）：确定阶段与阶段变量，阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量肱表示。（2）：明确状态变量和状态可能集合。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。（3）：确定决策变量和决策允许集合。（4）：确定状态转移方程。（5）：明确阶段效应和目标。最优化原理：“最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列比构成最优策略。”最优化原理的含义就是，最优策略的任何一部分子策略，也是相应初始状态的最优策略。每个最优策略只能由最优子策略构成。j12：狄克斯拉算法适用的问题是所有满足I..>0的网络，算法能求出v到所有其他点的最短距离，特别的，