运筹学试卷H试题

中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第1页共6页中国计量学院200~200学年第学期《运筹学》课程考试试卷（H）开课二级学院：经管学院，考试时间：年___月__日时考试形式：闭卷√、开卷，允许带计算器、钢笔（圆珠笔）、学生证入场考生姓名：学号：专业：班级：一、单项选择题（共20分，每题2分）1、使函数Z=-X1+X2-4X3增加的最快的方向是（）A、（-1，1，-4）B、（-1，-1，-4）C、（1，1，4）D、（1，-1，-4）2、如果决策变量数相等的两个线规划的最优解相同，则两个线性规划（）A、约束条件相同B、目标函数相同C、最优目标函数值相同D、以上结论都不对3、maxZ=3x1+2x2,2x1+3x2=14,x1+0.5x2=4.5,x1,x2=0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是（）A、（4，1）B、（4，3）C、（3，2）D、（2，4）4、已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为（）A、—（λ1，λ2，……λn）B、（λ1，λ2，……λn））C、—（λn+1,λn+2,……λn+m）D、（λn+1,λn+2,……λn+m）5、下列正确的目标规划的目标函数是（）A、minZ=P1d1--P2d2-B、maxZ=P1d1-+P2d2-C、minZ=P1d1--+P2(d2--d2+)D、minZ=P1(d1-+d1+)+P2(d2-+d2-)6、下列说法正确的有（）A、运输问题的运价表第r行每个cij同时加上一个非0常数k，其最优调运方案变化。B、运输问题的运价表的所有cij同时乘以一个非0常数k，其最优调运方案不变。C、运输问题的运价表第p列每个cij同时乘以一个非0常数k，其最优调运方案不变。D、运输问题的运价表的所有cij同时乘以一个非0常数k，其最优调运方案变化。7、μ是关于可行流f的增广链，则在μ上有（）A、对任意（i，j）∈μ+，，有fij=cijB、对任意（i，j）∈μ+，，fijcijC、对任意（i，j）∈μ-，有fij=cijD、对任意（i，j）∈μ-，有fij=08、工序（i,j）的总时差R（i，j）等于（）A、TLF（i，j）-TEF（i，j）B、TEF（i，j）-TES（i，j）C、TLS（i，j）+TES（i，j）D、TL（j）-TE（i）+tij装订线中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第2页共6页9、用动态规划方法求背包问题时，以下正确的说法是（）A、将装载的物品品种数作为阶段数。B、将背包的容量作为决策。C、将背包的容量作为状态。D、将装载的物品品种数作为决策。10、对于不确定型的决策，某人采用乐观主义准则进行决策，则应在收益表中（）A、大中取大B、大中取小C、小中取大D、小中取小单项选择题答题表题号12345678910答案二、判断题，正确打√，错误打×,并将修改建议简写在对应题号下的改错栏。（20分，每题2分）1、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。（）2、当最优解中存在为0的基变量时，则线形规划具有多重最优解。（）3、检验数λj表示非基变量Xj增加一个单位时目标函数值的改变量。（）4、中国邮路问题是遍历每一个点的问题。()5、在折衷主义准则中，乐观系数α的确定与决策者对风险的偏好有关。()6、工序时间是随机的，期望值等于3种时间的算术平均值。()7、目标规划没有系统约束时，一定存在满意解。()8、整数规划中求最大值问题的目标函数值是各分支函数值的下界。（）9、在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）10、用动态规划求解一般线性规划问题是将变量数作为阶段数，资源限量作为状态变量。（）三、（20分）已知以下线性规划问题，maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8x1,x2≥0（1）用单纯形法求解下列线性规划问题。（10分）（2）写出上述线性规划问题的对偶问题。（4分）（3）求解上述线性规划问题的对偶问题的最优解。（6分）装中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第3页共6页四、（20分）在下面的运输问题中总需要量超过总供应量。假定对销地B1、B2和B3未满足需要量的单位罚款成本是3元/吨、2元/吨和1元/吨。求最小运费和最优的运输方案。五、（10分）某工厂生产Ⅰ，Ⅱ两种产品。已知有关数据见下表。ⅠⅡ拥有量运价（元/吨）B1B2B3产量（吨）A151710A264680A332515销量（吨）752050装中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第4页共6页原材料kg2111设备hr1210利润元/件810公司在决策时需考虑以下问题：p1：根据市场信息，产品Ⅰ销售有下降趋势，故产品Ⅰ产量不大于产品Ⅱ产量p2：尽可能利用设备，但不能加班p3：应尽可能达到并超过利润56元为确定生产计划，试建立该问题的目标规划模型(不需要求解)六、（10分）公司由于规模扩大，增设了几个新的部门，管理层决定对现有部门的电话内线重新铺设，现在一共有12个部门如下图所示，v1……v12代表12个部门办公室，图中的边是可能联网的途径，边上的赋权为这条路线的长度，单位为百米，请设计一个网络能联通12个部门,并能保证总的路线长度最短。347①②③④6251198⑤⑥⑦⑧4863⑨⑩⑾⑿724中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第5页共6页中国计量学院200~200学年第学期《运筹学》课程试卷（H）参考答案及评分标准开课二级学院：经管学院，学生班级：，教师：一、单项选择题（20分，每题2分）单项选择题答题表题号12345678910答案ADACDBBACA二、判断题（20分，每题2分）判断及改错题答题表题号12345678910答案√×√×√×√×√√改错最优解是退化或非基变量检验数为零遍历每一边等于(a+4m+b)/6是上界三、（20分）已知以下线性规划问题，maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8x1,x2≥0（4）用单纯形法求解下列线性规划问题。（10分）（5）写出上述线性规划问题的对偶问题。（4分）（6）求解上述线性规划问题的对偶问题的最优解。（6分）解：（1）首先，将问题化为标准型（4分）。加松弛变量x3，x4，得其次，列出初始单纯形表，计算最优值（4分）。中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第6页共6页由单纯形表一得最优解为x(1,3/2)T,z*35/2.（2分）（2）对偶问题为(4分)：minw＝9y1＋8y2st.3y1＋5y2≥104y1＋2y2≥5y1,y2≥0（3）用互补松弛地定理求出对偶问题的解为(6分,其中步骤4分，结果2分)：先化为标准型，则有minw＝9y1＋8y2st.3y1＋5y2–y3=104y1＋2y2–y4=5y1,y2，y3，y4≥0根据互补松弛定理有，x1*y3=0,x2*y4=0,x10,x20,则有：y3=y4=0，带入对偶问题标准型则有3y1＋5y2=104y1＋2y2=5则有：y1=5/14y2=25/14,minW=35/2.四、（20分）在下面的运输问题中总需要量超过总供应量。假定对销地B1、B2和B3未满足需要量的单位罚款成本是3元/吨、2元/吨和1元/吨。求最小运费和最优的运输方案。运价（元/吨）B1B2B3产量（吨）A151710A264680A332515销量（吨）752050中国计量学院200~~~200学年第学期《运筹学》课程试卷（H）第7页共6页解答：虚设供应地A4，虚设地运价为惩罚成本，则有最优方案为则有最优运输方案为X12=10,X21=60,X22=10,X23=10,X31=15,X43=40.最小运输费用为555。（步骤为15分，结果为5分）五、（10分）某工厂生产Ⅰ，Ⅱ两种产品。已知有关数据见下表。ⅠⅡ拥有量原材料kg2111设备hr1210利润元/件810公司在决策时需考虑以下问题：p1：根据市场信息，产品Ⅰ销售有下降趋势，故产品Ⅰ产量不大于产品Ⅱ产量p2：尽可能利用设备，但不能加班p3：应尽可能达到并超过利润56元为确定生产计划，试建立该问题的目标规划模型(不需要求解)解：minZ＝p1d1＋＋p2（d2-+d2+）+p3d3-（3分）2x1+x2≤11（1分）x1-x2+d1－-d1+=0（1分）x1+2x2+d2--d2+=10（1分）8x1+10x2+d3—-d3+=56（1分）x1,x2,di—,di+≥0,i=1.2.3（1分）有正负偏差变量、优先因子和minz即可得（2分）六、（10分）解：能联通12个部门的最短电话线路长实际为图形的最小支撑数的权值。34①②③④2511⑤⑥⑦⑧463⑨⑩⑾⑿24最小支撑树为，权值为35（步骤为5分，结果为5分）3B11B23B3产量0A15（2）【10】17（4）103A2【60】6【10】4【10】6800A3【15】32（1）5(2)15-2A43(2)2(3)【40】140销量752050