答案200920102下沙管理运筹学期终试卷B

1、专业、班级： 学号： 姓名：密 封 线浙江财经学院20092010学年第二学期 管理运筹学 课程期末考试试卷标准答案（B卷）考核方式： 闭卷 考试日期：2010年 7 月6 日适用专业、班级：08信息管理1、2班、09信息C班一、 判断题（每小题2分，共10分）：×× ×二、 运输问题（10分）解：先用最小元素法求此问题的初始基本可行解：6591120604040销量（吨）50360250x14x131产量（吨）A4A3A2A1百元/吨912967377 40 20 10 20 40 30最小费用法求的初始方案总运费为：Z=9×30+6×20+

2、3×40+7×20+6×40+9×10=980按题目要求用位势法，作最优解检验：659116956Vj03-220x14x131UiA4A3A2A1百元/吨912967377 40 20 10 20 40 30 （3） （7） （3） （0） （5） （3）所有检验数0， 该方案已是最优方案，不需要再调整。（3）最优方案的运费Z=9×30+6×20+3×40+7×20+6×40+9×10=980三、 指派问题（10分）解：根据题意，改进效率矩阵如下，它是标准形式的指派问题，所以利用匈牙利解法求解

3、如下： 最优解矩阵为： 即 ：甲做C ，乙做B ，丙做D，丁做A. 最优值为：48四、 对策论（10分） 2 4 0 -24 8 2 6-2 0 4 2-4 -2 -2 04 8 4 6-22-2-4maxmaxmin24A= min解： 可见此对策问题不存在纯策略意义下的平衡解。令x1 ，x2，x3，x4分别表示方采取各纯策略的概率; y1， y2 ， y3 ， y4分别表示方采取各纯策略的概率;假设方期望赢得为V ，令x i = xi / V (i=1,2,3，4) yj = yj / V (j=1,2,3，4)则此对策问题对策双方最优混合策略表示为一个互为对偶的线性规划模型如下：minZ

4、= x1 + x2 +x3 +x4 2 x1 + 4x2 -2x3 +4x4 1 4x1 +8x2 +0x3 -2x41 0 x1 +2x2 +4x3 -2x4 1-2 x1+6x2 +2x3 +0x4 1 x1,x2 , x3 ，x40maxW= y1 + y2 +y3 +y4 2y1+4 y2+0y3 -2y41 4y1+8y2 +2y3 +6y41 -2y1+0y2 +4y3 +2y4 14y1-2y2 -2y3 +0y4 1 y1,y2 , y3，y4 0五、 动态规划（10分）解: 建立动态规划逆序递推基本方程（1）划分阶段：按营业区将原问题划分为三个阶段 n=3 k=1,2,3k=

5、1k=2k=3s1s2s3x3x2x1f3(s3) f2(s2) s4f1(s1) （2）确定状态变量：sk表示分配用于第k营业区到第三营业区的总的增设销售店数，则：s1=6; s2=2，3，4; s3=1，2，3; （3）确定决策变量：xk(sk)表示增设给第k营业区的销售店数，则：x1(s1)： x1(6)=2，3，4；x2(s2)： x2(2)=1； x2(3)=1，2；x2(4)=1，2，3；x3(s3)： x3(1)=1；x3(2)=2；x3(3)=3；（4）确定状态转移方程： 由分析可知该问题的状态转移方程为：sk+1 =sk uk（5）确定最优指标函数：阶段指标： dk(xk,)

6、-表示第k区增设销售店为xk个时创造的利润；最优指标函数：fk (sk)- 表示增设给第k区到第3区总销售店数为sk时,采用最优策略时，创造的最大利润；最优指标函数：f1 (s1)- 表示增设给3个营业区s1个销售店时,采用最优策略时，创造的最大利润；（6）动态规划逆序递推基本方程为：fk (sk)=maxdk(uk)+fk+1 (sk+1) k=3,2,1 f 4 (s4)=0（6，2）（2，1）v21v1v7v4v57216523v3569v6六、 图论（20分）（3，4）（8，3）（0，s）（6，6）（2，1）解：a) v1标以(0,s)已标号点集合I =v1 未标号点集合J= v2，

7、v3 ，v4，v5，v6，v7 弧集合：A=(vi，vj)|viI, vj J= ( v1,v2)，(v1,v4) ，(v1,v5) 计算： s12 =l1 +c12=0+1=1；S14 =l1 +c14=0+2=2 ；S15 =l1 +c15=0+7=7标注V2（1，1）b) 已标号点集合I =v1，v2未标号点集合J= v3 ，v4，v5，v6，v7 弧集合：A=(vi，vj)|viI, vj J= (v1,v4) ，(v1,v5), ( v2,v4)，( v2,v3) 计算： S14 =l1 +c14=0+2=2 ；S15 =l1 +c15=0+7=7；S24 =l2 +c24=1+6=

8、7；S23 =l2 +c23=1+5=6标注V4（2，1），c) 已标号点集合I =v1，v2,v4未标号点集合J= v3 ，v5，v6，v7 弧集合：A=(vi，vj)|viI, vj J= (v1,v5)，( v2,v3) ，(v4,v5), ( v4,v6) , ( v4,v3) 计算： S15 =l1 +c15=0+7=7 ；S23 =l2 +c23=1+5=6；S45 =l4 +c45=2+5=7S46 =l4 +c46=2+1=3；S43 =l4 +c43=2+6=8标注V6（3，4），d) 已标号点集合I =v1，v2,v4，v6未标号点集合J= v3 ，v5 ，v7 弧集合：A

9、=(vi，vj)|viI, vj J= (v1,v5)，( v2,v3) ，(v4,v5) , ( v4,v3) , ( v6,v7) 计算： S15 =l1 +c15=0+7=7 ；S23 =l2 +c23=1+5=6；S45 =l4 +c45=2+5=7S43 =l4 +c43=2+6=8；S67 =l6 +c67=3+9=12标注V3（6，2）e) 已标号点集合I =v1，v2,v3,v4，v6 未标号点集合J=v7，v5 弧集合：A=(vi，vj)|viI, vj J= (v1,v5)，(v6,v5)， (v4,v5) ，(v3,v7)， ( v6,v7) 计算： S15 =l1 +c

10、15=0+7=7 ；S65 =l6 +c65=3+3=6；S45 =l4 +c45=2+5=7；S37 =l3 +c37=7+2=9 ；S67 =l6 +c67=3+9=12标注V5（6，6）f) 已标号点集合I =v1，v2,v3,v4，v5，v6 未标号点集合J=v7 弧集合：A=(vi，vj)|viI, vj J= (v3,v7)， ( v6,v7) 计算：S37 =l3 +c37=6+2=8 ；S67 =l6 +c67=3+9=12标注V7（8，3）g) 已标号点集合I =v1，v2,v3,v4，v5，v6， v7 未标号点集合J= 弧集合：A=(vi，vj)|viI, vj J= 结

11、束 最后V7（8，3）反推得到最短路径是v1v2v3v7，v1到v7最短距离为8七、 灵敏度分析（20分） (1) 设x1、 x2分别表示兴隆股份有限公司计划生产A、B两种产品的数量，则根据题意，建立以下线形规划模型： Max Z=20x1+ 30x2 x1 + 2x2120 s.t. x1 70 x250 x1、x2 0先将上述问题化成标准形式有：Max Z=20x1+ 30x2+0x3+ 0x4+0x5 x1 + 2x2+ x3 =120 s.t. x1 + x4 =70 x2 + x5=50 x1、x2、x3、x4、x50列出初始单纯形表为：Cj à2030000CBxBbx1

12、x2x3x4x5000x3x4x51207050110201100010001j à2030000由给定的最终单纯形表可知原问题的最优解为X*=(70,25, 0,0,25) T，代入目标函数得Z*=2150，也就是说，该公司应制造A产品70 单位，B食品25单位，获取的利润最大，最大利润是2150。（2）由题意可知，相当于增加一个新的约束条件：0.2x1 + 0.1x216首先将原问题的最优解X*=(70,25, 0,0,25) T代入约束条件0.2x1 + 0.1x216中，可知条件左侧等于16.5，不满足约束条件，所以将其化为标准型：0.2x1 + 0.1x2+ x6=16直接

13、反映到终表中：Cj à20300000CBxBbx1x2x3x4x5x6200300x1x5x2x670252516100 0.20010.10-1/2 1/2011/2-1/2001000001j à00-15-500经过计算得单纯形表：Cj à20300000CBxBbx1x2x3x4x5x6200300x1x5x2x6702525-0.5100 000100-1/2 1/2-0.0511/2-1/20.2501000001j à00-15-500利用对偶单纯形法继续迭代：Cj à20300000CBxBbx1x2x3x4x5x620030

14、0x1x5x2x370262010100 0001000 011-22-501000-1010-20j à000-800-300所以增加这一道工序后，最优解为X*=(70,20, 10,0,26) T，最优值为Z*=2120。（3）将A产品的单位价格的变化直接反映到终表中Cj à1030000CBxBbx1x2x3x4x510030x1x5x2702525100 0010-1/2 1/211/2-1/2010j à00-1550利用单纯形法继续迭代，得出：Cj à1030000CBxBbx1x2x3x4x510030x1x4x2205050100 0011-1 0010-221j à00-100-10最优解为X*=(20,50, 0,50,0) T，最优值为Z*=1700。所以当A产品的单位