运筹学期末考试试卷(B)卷

实用文档文案大全福建农林大学考试试卷（B）卷学年第学期课程名称：运筹学考试时间120分钟专业年级班学号姓名题号一二三四五六七八九总得分得分评卷人签字复核人签字1.目标规划模型中，目标约束axddg中的g称为目标值。2.线性规划问题的单纯形法中,有最优解的判别准则是所有检验数非负且最优值为常数。3.如果流ijff中所有0ijf，则称f是零流。4.如果001020(,,...,)mBPPP，tB为最优基，则1tB为01020(,,...,)tttmPPP。5.无向图中的环是端点重合的边。得分二、单项选择题（选择正确答案的字母填入空格处，每小题2分，共10分）1.线性规划的非对称形式的原问题和对偶问题数学模型中，互补松弛性的描述式为C。A.****0,0ssyxyxB.**0syxC.**0syxD．**0yx2.若11(,)VV为最大截集，则C。A.11(,)cVV为最小截量B.11(,)cVV为最大流流量C.11(,)cVV为11(,)VV的截量D.11(,)cVV为最小截量3.最短路求解的主要内容是D。A.关键路线B.最短路线C.最短路长D.最短路线和最短路长4.线性规划问题的价值系数变化后，当最优表中B不发生变化。A.非基变量检验数B.限定常数、技术系数和基变量检验数得分一、填空题（每空2分，共10分）实用文档文案大全C.检验数D.目标函数值的相反数5.网络计划中关键工序aij的TFijC。A.0B.0C.=Lj-Ei-TijD.=Lj得分三、判断题（正确打“√”；错误打“×”；每小题2分，共10分）1.在增广链上确定的流量调整量只能是负的。（×）2.目标规划模型中必须有目标约束。（√）3.线性规划问题有最优解。（×）4.网络计划中，非关键路线上工序的施工时间延长可能导致工期延长。（√）5.树中可能存在环。（×）得分四、问答题（每小题5分，共20分）1.闭回路的定义及应用。m×n表可以划分为m×n个格，一个格也可以称为一个点，在不同的m×n表中，格或点代表不同的含义。取产销平衡表来介绍闭回路定义。在产销平衡表中取偶数个点jpipjijixxx,1,10,0,...,,，若这些点满足,10ii21jj,32ii43jj……,)1(ippi0jjp或满足,10jj21ii,32jj43ii实用文档文案大全……,)1(jppj0iip则称这些点构成一条闭回路。闭回路用来进行方案调整，计算检验数，判断可行解是否基本解等等。2.最大流问题的线性规划模型。max()0()..01,2,,()sjjsijijijsjjsaAavffcaAvfisstffinvfit3.线性规划模型的特点。略。4.目标规划模型中目标约束的结构。略。得分五、（第一小题5分，第二小题3分，第三小题2分，共10分）对)(P：要求：1.12,1,1ccc，用单纯形法求解；2.画出可行域；3.指出12,ccc变动下的最优解。1122121212min10():..5,0zcxcxxxPstxxxx解：⑴单纯形法求解如下：实用文档文案大全○0cj-1-100-MθcBxBbx1x2x3x4x50-Mx3x510511100○1-10-1110/15/1z5M-1+M-1-M0-M0○1cj-1-100-MθcBxBbx1x2x3x4x50-1x3x1550211-1○1-10-1110/15/1z50-20-11-M**(5,0,5,0,0),5Txz。2.可行域如下：实用文档文案大全3.12,ccc变动下的最优解。序号最优解1(1)ABxx3/42Ax343/23(1)ADxx3/24Dx1/2145(1)BDxx1/46Bx1434说明：Pc。得分六、（10分）用破圈法或避圈法求图1的最大生成树，并指出其权重和（10分）x2x1o551010ABDββββP实用文档文案大全解：⑴避圈法：首先确定应选的边数为顶点数减1，即应选7条边。所选的边染上红色，旁边标明选边序号，结果如下图所示。最大生成树权为85.⑵避圈法略。得分七、（10分）对)(OP，要求1．求解2．给出一个合理的实际意义。1112212111222121122min()10():..25,,,,,0zPddPdxxddOPstxxddxxdddd15V6443121597163V35V7V2V1V4V5V8154104图1①②③④⑥⑦15V6443121597163V35V7V2V1V4V5V8154104图1⑤实用文档文案大全解：⒈⑴单纯形法求解过程见下表，据下表得。}5,0{,)0,10(2PzxTjc00P1P10P2θBCBXb1x2x1d1d2d2dP11d10111－1001002d5○12001－15P1P2－100－1－10200000001jc00P1P10P2θBCBXb1x2x1d1d2d2dP11d50－11－1－1○1501x512001－1－P1P2－5001021－1000001P22d50－11－1－1○101x10111－100P1P20－500110001－1110⑵图解法相关图形见图2。⑴考虑硬约束，可行域为第一限象；⑵考虑P1，最优解在直线AB上；⑶考虑P2，最优解在点A上。因此，。}5,0{,)0,10(2PzxT实用文档文案大全x2③10B2d－2dE④ODA10x11d－1d图2⒉略。得分八、（10分）（教材P155例7）有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为g,与年初投入生产的机床数量u1的关系为g=g(u1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率，0a1,设a=0.7).在低负荷下生产时,产品的年产量为h,和投入生产的机床数量u2的关系为h=h(u2)=5u2,相应的机床完好率为b(0b1,设b=0.9),一般情况下ab。假设某厂开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。解：首先构造这个问题的动态规划模型。⑴变量设置①设阶段变量k表示年度，因此，阶段总数n=5。②状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时实用文档文案大全的完好机床数量。③决策变量uk，表示第k年度中分配于高负荷下生产的机床台数。于是sk-uk便为该年度中分配于低负荷下生产的机床台数。这里uk与uk均取连续变量，当它们有非整数数值时．可以这样理解：如sk＝0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.4时，就表示一台机床在k年度只有4/10的时间于高负荷下工作。⑵状态转移方程为⑶允许决策集合,kkkkksuusD0)(⑷目标函数。设vk(sk,uk)为第k年度的产量，则vk(sk,uk)=8uk+5(sk-uk),因此，目标函数为),(),(),()(555111,usvusvusvsvkkkkkkknk⑸递推方程。令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系：)(),(max)(11)(kkkkksDukksfusvsfkkk1,2,3,4,5k0)(66sf⑹边界条件：s1＝1000，s6≥0。分阶段求解见下表。k)(),(11kkkkksfusv*ku)(kksf555555530)(58suusu5s85s444444442.124.1)](9.07.0[8)(584suusuusu4s13.64s)(9.07.0)(1kkkkkkkusuusbaus实用文档文案大全33333333324.1728.0)](9.07.0[6.13)(58suusuusu3s17.523s222222222768.20504.0)](9.07.0[52.17)(58suusuusu020.7682s1111111116912.231536.1)](9.07.0[768.20)(58suusuusu023.69121s由表5可得最优策略：397,567,810,0,0)1000(1p。目标函数最优值：2.23691)1000(1f个。得分九、（10分）对表1，用表上作业法求解。表1销地产地ⅠⅡⅢⅣ产量（万吨）A631275B43956C91013－5需求（万吨）455不限'解：根据产销平衡可知表1中不限应取为2，—应取为M，因此问题的基础数据表等价与表2：表2销地产地ⅠⅡⅢⅣ产量（万吨）A631275B43956C91013M5需求（万吨）4552⑴关于0x的计算实用文档文案大全用伏格尔法确定0x差额表1销地产地ⅠⅡⅢⅣ行差额A6○31273B43951C91013M1列差额2032差额表2销地产地ⅠⅡⅢⅣ行差额A6○31273-B439○511C91013M14列差额250-342M-5说明：决定,AIIx和,AIVx两个数字格，后者是补零的格。差额表3销地产地ⅠⅡⅢⅣ行差额A61273-B○439○5115C91013M144实用文档文案大全列差额2550-3442M-5差额表4销地产地ⅠⅡⅢⅣ行差额A61273-B39○5115C910○13M144列差额2550-3442M-50x销地产地ⅠⅡⅢⅣ产量（万吨）A5050B42640C0550需求（万吨）40505020注意空格11x检验数为零，但取它为入基变量时调整量为零，所以最优解唯一，为0x，最优值*534425513106z实用文档文案大全位势（0）销地产地ⅠⅡⅢⅣ行位势A(6)3(10)70B4（1）（8）5－2C9（6）13(10)3列位势63107检验数（0）销地产地ⅠⅡⅢⅣA02B21C4M-10