完整word版)中南大学12级运筹学试题(附答案)中南大学考试试题2013 —-2014 学年 下 学期 时间120分钟 运筹学 课程 48 学时 3 学分 考试形式： 闭 卷 专业年级: 商学院12级 总分100分，占总评成绩70%一、 对下列线性规划模型（1)求上述线性规划的最优解（20分）（2） 写出上述线性规划的对偶规划模型，并求出其最化解（15分）答案及评分标准：（1）无最优解标准化正确 5分利用对偶单纯形法，大M法或二阶段单纯形法求解结果正确 15分方法正确结果不正确 8—15分使用对偶单纯形法求解 0分2）上述规划问题无解写出对偶单纯形 10分指出无解 5分二、某工厂要对一种产品制定今后三个时期的生产计划，据估计在今后的三个时期内，市场对该产品的需求量如下:时期(k）123需求量234假定该厂生产每批次产品的固定成本为3（千元)，如不生产就为0；每单位产品成本为1（千元）；每个时期生产能力所允许的最大生产批量不超过5个单位；每个时期期末未售出的产品,每单位需付存储费0.5（千元）还假定在第一个时期的初始库存量为0，第三个时期之末的库存量也为0。
试问该厂该如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小答案及评分标准:解：需求量 D1=2；D2=3；D3=4.(1）阶段n: 1，2，3,4（2）状态Sn： S1={0｝; S2=S1+X1-D1=｛0，1,2，3｝; S3=S2+X2—D2=｛0,1，2,3，4}； S4=S3+X3-D3=｛0｝； （得分点:4分）（3）决策 X1=｛2，3,4，5}; X2={0,1,2,3，4，5}; X3={0,1，2,3,4｝ (得分点：3分)（4）状态转移方程：Sn+1=Sn+Xn-Dn （得分点:1分)（5）阶段指标函数：rn(Xn)=3+1＊Xn+05Sn， Xn〉0 =0.5Sn, Xn=0 （得分点：2分）(6)指标函数递推方程：, (得分点:2分）利用表格计算，从最后一个阶段开始, n=3时：S3+X3—D3=0， 即X3=4—S3 （得分点：2分) X3 S30123407+0=77416+0.5=6。
565325+0.5*2=66234+0.5＊3=555.5140+05*4=220n=2时:S2+X2≥D2=3, 即X2≥3-S2；S3=S2+X2—3 （得分点：3分） X2 S201234506+7=137+6.5=1358+6=1413315.5+7=12.56.5+6.5=137.5+6=135=14125225+7=126+6.5=1257+6=138+55=13.59+2=1111531.5+7=85=126.5+6=12.575=138.5+2=1058.50n=1时：S1+X1≥D1=2， 即X1≥2；X1〈=5; S2=S1+X1-2=X1-2 （得分点:1分） X1 S1234505+13=186+12.5=18.57+11=188+8.5=16.51655最优策略为：X*=｛X1＊，X2*，X3＊}=｛5,0，4｝ （得分点:1分）Z＊=165 （得分点：1分）三、现从A1，A2,A3三个产粮区向B1，B2，B3，B4四个地区运送粮食，已知三个产粮区可提供的粮食分别为9，5，7（万吨），四个地区的粮食需求量分别为3，8，4，6（万吨），产粮地到需求地的单位运价(万元）如下表所示，请问如何调运才能使总运费最小？（15分)销地产粮地B1B2B3B4产量A1291189A214525A395367需求量3846解：（1)用最小元素法得到初始调运方案如下： 销地产粮地B1B2B3B4产量A1×5×49A23××25A3×34×7需求量3846 21总运费：Z（1） = 5×9 + 4×8 + 3×1 + 2×2 +3×5 +4×3 = 111（2）求得空格的检验数如下：l11=－5，l13=4，l22=1，l23=4，l31=6，l34=2选l11=－5对应的空格x11入基，在x11的闭回路中，标正号的格子增加3，标负号的格子减少3，得新调运方案如下:销地产粮地B1B2B3B4产量A135×19A2×××55A3×34×7需求量3846 21总运费：Z（2) = 3×2 + 5×9 +1×8 + 5×2 +3×5 +4×3 =96（3）求得新调运方案空格的检验数如下：l13=4，l21=5，l22=1，l23=4，l31=11，l34=2全部空格检验数均为非负，当前调运方案为最优： x11 = 3,x12 = 5，x14= 1,x24= 5,x32= 3，x33= 4 Z＊ = 3×2 + 5×9 +1×8 + 5×2 +3×5 +4×3 =96四、有5项工作要分派给5个人完成，每人只能作一项工作，每项工作也只能由一个人完成，各人完成各项工作获得的利润见下表.请问应如何安排人选才能使完成这5项工作所获得的总利润最大？（15分）任务人员 利润ABCDE甲乙丙丁戊513101513127491081461116121391377128145解： 5 12 8 12 7 13 7 14 13 12 10 4 6 9 8 （Cij)＝ 15 9 11 13 14 13 10 16 7 5缩减矩阵B： 11 4 8 4 9 3 9 2 3 4 6 12 10 7 8 B＝（bij)＝ 1 7 5 3 2 3 6 0 9 11Ö 7 0 4 0 4 1 7 0 1 1Ö 0 6 4 1 1 0 6 4 2 0Ö 3 6 0 9 10 7 0 5 0 4 0 6 0 0 0 0 6 5 1 1 0 6 5 2 0 2 5 0 8 9 即：甲－B，乙－D，丙－A,丁－E，戊－C最大利润:Z*=12+13+10+14+16=65五、求下列容量网络从源点S到汇点T的最大流和最小割,弧旁权值为弧容量。
15分）82154936752198535S12435T67 解：第一步,给出初始可行流，如下图所示 (5分）58,3+3+22,11,15,54,29,53,36,5+17,55,52,01,09,2+5+18,5+35,03,3S12435T67第二步，判断初始可行流是否最大流,由于找不到增广链，所以初始可行流为最大流. （5分）第三步，求最小割和最大流量，在可以标号的点集｛S，1，2，3，4,5,6,7｝和不能标号的点集{T｝之间画一条割线，形成最小割Smin=｛(6，T）， (4，T）, （7,T)｝，其容量=5+8+6=19如下图所示37，59,512,065，53,35，08，5+3T4S3，38，3+3+251,09，2+5+14,2726,5+15，51，12，15由最大流—最小割定理得：最大流量为Q（F*）==19 （5分）2。