运筹学2024学年期末考试题A卷及答案.docx

《运筹学2024学年期末考试题A卷及答案.docx》由会员分享，可在线阅读，更多相关《运筹学2024学年期末考试题A卷及答案.docx（9页珍藏版）》请在优知文库上搜索。

1、运筹学2024年学年其次学期期末考试题（a卷）留意事项:1、答题前，考生务必将自己的姓名、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、单项选择题（每小题1分，共10分）1：在下面的数学模型中，属于线性规划模型的为（maxs.t.S = 4X +YXY3x,ominS = 3X + Y2X-Y-lx,omaxs.t.S = X2 +Y2X-Y2x,omin S = 2XYD. s.t. X +Y3X,Y0）上达到。D.几何点D.人工变量2.线性规划问题若有最优解，则肯定可以在可行域的（A.内点B.顶点C.外点3：在线性规划模

2、型中，没有非负约束的变量称为（）A.多余变量B.松弛变量C自由变量那么该线性规划问题最优4：若线性规划问题的最优解同时在可行解域的两个顶点处达到,解为（）C.无穷多个）相同。C.解结构D.有限多个D.解的重量个数A.两个B.零个5：原问题与对偶问题的最优（A.解B.目标值6：若原问题中F为自由变量，那么对偶问题中的第i个约束肯定为（）A.等式约束B.型约束C.约束D.无法确定7：若运输问题已求得最优解，此时所求出的检验数肯定是全部（）A.小于或等于零B,大于零C.小于零D.大于或等于零8：对于m个发点、n个收点的运输问题，叙述错误的是（）A.该问题的系数矩阵有mXn列B.该问题的系数矩阵有m+

3、n行C.该问题的系数矩阵的秩必为m+n-1D.该问题的最优解必唯一9：关于动态规划问题的下列命题中错误的是（）A、动态规划分阶段依次不同，则结果不同B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：若P为网络G的一条流量增广链，则P中全部正向弧都为G的（）A.对边B.饱和边 C.邻边D.不饱和边二、推断题（每小题1分，共10分）1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一样的。（J）2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（X）3：一旦一个人工变量在迭代中变

4、为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（）4：若线性规划问题中的,值同时发生变更，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的状况。（）5：若线性规划的原问题有无穷多最优解，则其对偶问题也肯定具有无穷多最优解。（）6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（）7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（X）8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。（）9：图论中的图不仅反映了探讨对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长

5、短曲直等都要严格留意。（X）10：网络最短路途问题和最短树问题实质上是一个问题。（）三、填空题（每空1分，共15分）1：线性规划中，满意非负条件的基本解称为_基本可行解_，对应的基称为可行基2：线性规划的目标函数的系数是其对偶问题的右端常数而若线性规划为最大化问题，则对偶问题为最小化问题_。3：在运输问题模型中，加+，2-1个变量构成基变量的充要条件是不含闭回路一。4：动态规划方法的步骤可以总结为：逆序求解.最优目标函数依次求一一最优策略、最优路途和最优目标函数值。5：工程路途问题也称为最短路问题，依据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有一函数一迭代法和一策

6、略迭代法两种方法,，6：在图论方法中，通常用一点_表示人们探讨的对象，用一边表示对象之间的某种联系。7：一个无圈且一连通的图称为树。四、计算题（每小题15分，45分）1：考虑线性规划问题：maxz=2x1+4x2+3xj3x1+4x2+2x3602x,+x22x340s.t.xl+3x2+2x380x1,x2,x30(a)：写出其对偶问题；(b)：用单纯形方法求解原问题；(c)：用对偶单纯形方法求解其对偶问题；(d)：比较(b)(c)计算结果。1：解a)：其对偶问题为minz=60)+40%SOy33m+2%+y324y+y2+3y34S.t.s2+2y2+2%3.Wy2，%NO（3分）b）：

7、用单纯形方法求解原问题时每步迭代结果：原问题解第一步(0,0,0,60,40,80)其次步(0,15,0,0,25,35)第三步(0,20/3,50/3,0,0,80/3)（5分）c）：用对偶单纯形方法求解对偶问题时每步迭代结果:对偶问题问题解第一步(0,0,0,-2,-4,-3)其次步(1,0,0,L0,-1)第三步(5/6,2/3,0,11/6,0,0)（5分）d）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此（b）、（c）的计算结果完全相同。（2分）2：某公司准备在三个不同的地区设置4个销售点，依据市场预料部门的估计，在不同的地区设置不同数量的销售店，每

8、月可得到的利润如下表所示。试问各个地区应如何设置销0162530320121721220101416172：解该问题可以作为三段决策问题，对1,2,3地区分别设置销售店形成1,2,3三个阶段。4表示给地区k设置销售店时拥有安排的数量，以表示给地区k设置销售店的数量。状态转移方程为：xk+i=xk-uk；阶段效应题中表所示；目标函数：maxR=fgt(以,)；其中取(以)表示在k地区设置个销售店时的收益；*=(3分)首先逆序求解条件最有目标函数值集合和条件最有决策集合：%=3时，0x34,O%x3,f3(x3)=max3(w3)+Z1U4)其中“3()=o于是有：Ao)=g3(0)=。，W3(O

9、)=O,0)=g3(D=1，=1，(2)=4g3(2)=14,w,3(2)=2,力(3)=g3(3)=16,u,3(3)=3,力(4)=g3(4)=17,m3(4)=4-(3分)Z=2时，024,0u2x2,f2x2)=max2(m2)+(x3),0u2x2于是有：-(0)=maxg2(W2)+4Q)=0,2(0)=0,0w2f2(D=maxg2(%)+力(&)=12,w2(l)=l,0u21&(2)=maxg2Q2)+力0)=22,m2(2)=1,0u22人=maxg2(%)+启曰)=27,w2(3)=2,0w23-(4)=maxg2(2)+Zlo)=3Lu2(4)=2or3.Om24(3分

10、)女=3时，x1=4,OM1X1=4,于是有：f(4)=max(wl)+(r2)=47w1(4)=2.(3分)0u4因此，最优的安排方案所能得到的最大利润位47,安排方案可由计算结果反向查出得：(4)=2,U2(I)=I=1。即为地区1设置两个销售店，地区2设置1各销售店，地区3设置1个销售店。3：对下图中的网络，分别用破圈法和生长法求最短树。(1)：取圈匕小，匕，匕，去掉边饵，匕。(2)：取圈人为，匕，彩，去掉边W2，！。(3)：取圈内，匕，%2,去掉边W2，匕。(4)：取圈匕，匕，%，%，匕，去掉边匕在图中已无圈，此时，P=6,而q=p-1=5,因此所得的是最短树。结果如下图，其树的总长度

11、为12。一一(6分)V4（3分）生长法依据生长法的基本原理，得以下计算表匕为v4V5V6S(26OOQOOOV2389OO&(3)8900匕530035(3)00V5OO1Sj51)V63SS(3据此也得到与破圈法相同的最短树。（6分）五、简答题（每小题10分,共20分）1.试述单纯形法的计算步骤，并说明如何在单纯形表上推断问题是具有唯一最优解、无穷多最优解和无有限最优解。解：1：单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。其次步：推断最优，检验各非基变量为的检验数%=Q号一若全部的丐,则基B为最优基，相应的基可行解即为基本最优解，计算停止。若全部的检验数,又存在某个非基变量的

12、检验数全部的=,则线性规划问题有无穷多最优解。若有某个非基变量的检验数并且所对应的列向量的全部重量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代当存在选队进基来改善目标函数。若检验数大于O的非基变量不止一个，则可以任选其中之一来作为进基变量。进基变量/确定后，按最小比值原则选择出基变量以。若比值最小的不止一个，选择其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或推断出没有有限最优解。-（3分）2.简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：2：最大流问题就是在肯定条件下，要求流过网络的物流、能量流或信息流等流量最大的

13、问题。假如已知流过弧的单位流量要发生与的费用，要求使总费用为最小的最大流流量安排方法。即在上述最大流问题上还应增加关于费用的目标：mino这种问题称为最小费用最大流问题。模型可以描述为：minmaxffi=sl=1if*，-fi=tOWXijWbij采纳对偶法求解最大流最小费用问题，其原理为：用福德一富克逊算法求出网络的最大流量，然后用Ford算法找出从起点匕到终点匕的最短增广链。在该增广链上，找出最大调整量,并调整流量，得到一个可行流。则此可行流的费用最小。假如此时流量等于最大流量，则目前的流就是最小费用最大流，否则应接着调整。对偶法的步骤归纳如下：第。步：用最大流方法找出网络最大流量，侬，并以0流作为初始可行流。第一步：对于当前可行流，绘制其扩展费用网络图。其次步：用FOrd算法求出扩展费用网络图中从。到匕的最短路。第三步：在最短路途对应的原网络中的增广链上，调整流量，得到新的可行流。第四步：绘制可行流图。若可行流的流量等于最大流量工皿，则己找到最小费用最大流，算法结束；否则从第一步起先重复上述过程