2006运筹试卷A习题分析及答案

12008—2009学年第1学期《运筹学》试卷专业班级姓名学号开课系室管理科学与工程考试日期题号一二三四五六总分得分阅卷人2一、名词解释（5×3=15分）1.基2.退化解3.影子价格4.偏差变量5.无后效性重点考察第一第二单元的基础概念记忆。二、判断题（1×10=10分）（正确的打√，错误的打×）1.原问题有可行解但无最优解，则其对偶问题无可行解。()2.若线性规划问题中的ib，jc值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况。（）3.对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为mnC。()4.若1、2是某线性规划问题的最优解，则)10()1(12111也是该问题的最优解。（）5.线性规划问题的可行解X对应线性规划问题可行域(凸集)的顶点。（）6．动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性。（）7．若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加7个单位时，相应的目标函数值将增大7k。（）8．整数规划中的指派问题最优解有这样的性质，若从系数矩阵(ijc)的一列（行）各元素中分别减去该列（行）的最小元素，得到新矩阵（ijb），那么以（ijb）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。（）9.结点最早时间与最迟时间相等的点连接的线路就是关键路线。（）网络规划10.已知线性规划问题maxZ=CX，AX≤b，X≥0，若X’是它的一个基本解，Y’是其对偶问题的基本解，则恒有CX≤Yb。（）三、线性规划问题（12分）3已知线性规划问题321325maxxxxZ0,,,,6525..543212532114321xxxxxkxxxxkxxxxts其中，21,kk为常数，已知最优单纯形表如表1所示。表1Cj52300jCBXBb1x2x3x4x5x50X1X530101b2100c-8-1fZ1500a-7decj—zj（1）请求出未知数a,b,c,d,e,f的值，并确定21,kk的值（8分）；（2）写出原规划的对偶规划（四、对偶问题与灵敏度分析（16分）已知线性规划问题212maxxxz0,37222.2112121xxxxxxxts的最终单纯形表如表2所示（1）写出对偶问题的最优解（3分）；（2）写出矩阵B及其逆矩阵1B（5分）；（3）若右端项变为2122'b，分析最优基的变化（8分）。表2Cb基bx1x2x3x4x52x250101/21/21x131000140x33001-1/23/2cj―zj000-1-2主要是单纯形法及对偶单纯形法的运五、运输问题（15分）已知运输问题的供需关系表与单位运价表如表3所示，试用表上作业法求解下面的运输问题。表3销地产地甲乙丙丁产量151351210023114108039612750销量30605060六、图解法求解目标规划问题（12分）某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1h，装配线每周计划开动40h,预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量30台，每台可获利40元，该厂确定的目标为：第一优先级：充分利用装配线，每周计划开动不小于40h；第二优先级：允许装配线加班，但加班时间每周尽量不超过10h；第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数2。试建立这问题的目标规划模型，并求解黑白和彩色电视机的产量。5七、网络图与优化（20分）作业名称作业内容紧前工序工序时间（天）A清理场地，准备施工—9B备料—8C车库地面施工A，B7D墙及房顶桁架预制B16E车库混凝土地面保养C25F竖立墙架D，E4G竖立房顶桁架F6H装窗及边墙F10I装门F4J装天花板G12K油漆H，I，J18L引道混凝土施工C8M引道混凝土保养L22N清理场地，竣工验收K，M4要求：1.绘制网络图，在图上计算各作业的最早开始和最迟开始时间，确定关键路线和总工期（10分）；2.若装天花板的施工时间从12天缩短到8天，对整个工程进度有何影响（3分）；3.为保证工期不拖延，装门这项作业最晚应从那一天开工（3分）；4.如果要求该项工程必须在75天内完工，是否应该采取措施，如果是，应该采取什么措施（4分）《运筹学》试卷A答案一、名词解释（5×3=15分）61.基：设A为约束方程组(2.2)的m×n阶系数矩阵，(设n＞m)，其秩为m，B是矩阵A中的一个m×m阶的满秩子系数矩阵，称B是线性规划问题的一个基。2.退化解：解Ｘ为基可行解，其非零分量的个数少于矩阵的秩Ｍ的个数，称解Ｘ为退化解。3.影子价格当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。4.偏差变量是表示实际值与目标值之间差距的变量。5.无后效性是指在动态规划中，当过程在时刻tk所处的状态为已知的条件下，过程在时刻t（ttk）处的状态只与过程tk时刻的状态有关，而与过程在时刻tk以前的状态无关。二、判断题（1×10=10分）1.对2.错对3.错4.对5.错6.对7.对8.对9.错10.对三、线性规划问题（12分）(1)解：a=-23，b=5，c=-10，d=-5，e=0，f=1，k1=30，k2=40。（8分）214030minyyz(2)s.t.3622555212121yyyyyyY1无约束，y2≥0（4分）四、对偶问题与灵敏度分析（16分）（1）对偶问题的最优解为Y=[0,1,2]T（3分）（2）010012121B2/32/111002/12/101B（5分）（3）127'1bBb，最优解为0,6,2321xxx，最优目标值为14z。（8分）五、运输问题（15分）利用最小元素法求得初始基可行解740307030104060309030605060此时：总运费为1260元最优解判断：最优解：30,6010,3020,50343224211413xxxxxx这时总运费最小，为1250元。六、图解法求解目标规划问题（12分）解：设21,xx分别表示黑白和彩色电视机的产量。这个问题的目标模型为：)2(min4332211ddPdPdPz0,,,302450402144233122211121iiddxxddxddxddxxddxx图略。该厂每周应装配彩色电视机24台，黑白电视机26台。七、网络图与优化（20分）JAM1236591110BL748CDKEFGHI8(1)总工期85天；（10分）(2)缩短4天（3分）(3)第59天（3分）(4)缩短关键线路上10天工时（4分）