浙江科技运筹学试卷试卷7答案.doc

浙江科技学院考试试卷 专业班级 学号 姓名 装订线 浙江科技学院 学年第 学期考试试卷 卷 考试科目 考试方式 完成时限 拟题人 审核人 批准人 年 月 院 年级 专业题序一二三四五六七八九十总分得分一、 填空题（215=30分）1、在八个候选运动员中选几个参加篮球比赛，若令Xi= 1 第I个运动员被选中0 第I个运动员未被选中用Xi的线性表达式表示下列要求：（1）从八个运动员中选五个参加比赛 Xi=5 (2)运动员2和3不能同时入选 X2+X31 。2、用表上作业法求解某运输问题时，请例举初始调运方案的确定方法有 西北角法 最小元素法 、 沃格尔法 。3、线性规划问题如果有唯一最优解，则单纯形计算表的终表中必然有_所有的非基变量检验数均小于0_；4、极大化的线性规划问题的可行解时，则对偶问题_为极小划_；5、在图论中树的概念为：连通且不含圈的无向图为树6、若整数规划的松驰问题的最优解不符合整数要求，假设Xi=bi不符合整数要求，INT（bi）是不超过bi的最大整数，则构造两个约束条件：XiINT（bi）1 和 XiINT（bi） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。7、已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式）其中X4,X5,X6为松驰变量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj-Zj000-40-9问：(1)对偶问题的最优解： Y(4,0,9,0,0,0)T （2）写出B-1= (3)Z*/b1= 4 ,这个数值的经济含义是 影子价格 (4)按最优计划完成任务时， 1，3 资源已消耗完， 2 资源还有剩余。二、 计算题（50分）1. 考虑如下线性规划问题（30分）Max z=10x1+5x2s.t. 3x1+4x295x1+2x28x1，x20回答以下问题：1）分别用图解法和单纯形法求出最优解,并指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。2）写出对偶问题。3）当b1由9变为15，最优解是否发生变化。4）c2有5变为6，是否影响最优解，如有影响，将新的解求出。1）图解法略单纯形法最优解为Cj10500CBXBbX1X2X3X40X39341030X4852018/5Cj-Zj105000X321/5014/51-3/53/210X18/512/501/54Cj-Zj010-25X23/2015/14-3/1410X1110-1/72/7Cj-Zj00-5/14-25/14最优解为X1=1,X23/2 2)对偶问题为Minz =9y1+8y2 3y1+5y2104y1+2y25y1,y203)当b1由9变为15X= 51/7 1/7基变量的值都大于0，所以最优解不变。4）c2有5变为63=-5/74=-11/7所有非基变量的检验数都小于0，所以最优解不变。2.某公司在三个地方的分厂A1、A2、A3生产同一种产品，需要把产品运送到四个销售点B1、B2、B3、B4去销售。各分厂的产量、各销售地的销量和各分厂运往各销地的每箱产品的运费如表。(10分)产 销B1B2B3B4产量/tA121172425300A210153019450A323212022450销量/t400250350200问应如何调运,可使得总运输费最小?解：初始解为B1B2B3B4产量/tA1200100300A240050450A3350100450销量/t400250350200计算非基变量检验数B1B2B3B4产量/tA19090300A20017-4450A36-100450销量/t400250350200由于X24,X32的检验数小于0所以不是最优解把X24作为新的基变量得B1B2B3B4产量/tA125050300A240050450A3350100450销量/t400250350200重新计算检验数B1B2B3B4产量/tA15010300A20430450A310700450销量/t4002503502003.求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（10分） V1 (4,4 ) V3 (9,6) (6,2) VS (3,1) (3,1) (2,2) Vt (5,3) (7,7)V2 (5,4) V4最优解为 (4,4) V1 V3 (9,7) (6,4) (3,0) (2,0) Vs Vt (5,4) (7,7) V2 V4 (5,5)最大流为11.三、建模题。（210=20分）1. 某厂准备用五种原料（A、B、C、D、E）冶炼一种新型合金。各种原料含有铅、锌、锡的成份及原料单价列表如下：原料成份及单价表原料成份ABCDE铅（%）3010501050锌（%）6020201010锡（%）1070308050单价（元/公斤）979108要求新型合金含铅30%；含锌20%；含锡50%。试建立合金耗费最小的配料最优化模型。解：需要A、B、C、D、E各X1,X2,X3,X4,X5Minz=9X1+7X2+9X3+10X4+8X50.3X1+0.1X2+0.5X3+0.1X4+0.5X5=0.3(X1+X2+X3+X4+X5)0.6X1+0.2X2+0.2X3+0.1X4+0.1X5=0.2(X1+X2+X3+X4+X5)0.1X1+0.7X2+0.3X3+0.8X4+0.5X5=0.5(X1+X2+X3+X4+X5)X1,X2,X3,X4,X502.某工厂有1000台机器，可以在高、低两种不同负荷下进行生产。假设在高负荷下生产时，产品的年产量S1和投入的机器数量Y1的关系为S1=8Y1，机器的完好率为0.7；在低负荷下生产时，产品的年产量S2和投入的机器数量Y2的关系为S2=5Y2,机器的完好率为0.9。现在要求制定一个5年生产计划，问应如何安排使在5年内的产品产量最高。试建立动态规划模型，不要求求解。解，设阶段K1，2，3，4，5状态变量Sk在第k个时期剩下的完好机器决策变量U