《北航《运筹学试卷A》期末试题&参考答案.docx》由会员分享，可在线阅读，更多相关《北航《运筹学试卷A》期末试题&参考答案.docx（15页珍藏版）》请在三一文库上搜索。
1、-精选文档 - 运筹学试卷 A 参考答案一、对线性规划问题max z4x15x2c3 x3s.t.x12x2x3b1a21 x13x22x318x1, x2 , x30在第 1 个约束中引入人工变量x4 ，第 2 个约束中引入松弛变量x5 ，采用大 M 法利用单纯形表求解得到了最优解，单纯形表完整的迭代过程见下表：c j45c3M0CBX Bbx1x2x3x4x5Mx4b1121100x518a213201cjzj4 M5 2Mc3M00c j45c3M0CBX Bbx1x2x3x4x55x2b1 / 21/211/21/200x53a21 3 / 201/23/21cjzj3/20c35 /
2、 2M5 / 20c j45c3M0CBX Bbx1x2x3x4x54x1b1121100x58013/211cjzj032M40（1 ）试根据上述求解过程单纯形表，确定参数a21 ， b1 和 c3 的值，以及该问题可编辑-精选文档 -的最优解；（2 ）以上述线性规划问题为原问题，写出其对偶问题；（3 ）利用对偶性质， 求出对偶问题的最优解。（本题共 25 分，第 1 小题 15 分，第 2、3 小题各 5 分）解：（ 1）由最终单纯形表 x3 的判别数 c342 ，得到 c32 ；由中间单纯形表右端项的初等行变换规则：3 183b1 ，得到 b110 ；2由中间单纯形表到最终单纯形表的变换
3、规则：a21310 ，得到2( 1)2a21 1 ；该问题的最优解： x1*10 ， x2*0 ， x3*0（ 2）对偶问题：min w10 y118y2s.t.y1y242y13 y25y12y22y1无约束 , y20（ 3）依据互补松弛定理。 在最优解处，原问题第 2 个约束为严格不等式， 故 y20 。由于 x1*0，故对偶问题第1个约束为等式， y1y2 4 ，得到 y1 4 。故对偶问题的最优解为 y1*4， y2*0 。二、用分支定界法求解如下整数规划问题IP :max z2x13x2s.t.x1x262x14x217LPx1 , x20x1 , x2为整数可编辑-精选文档 -先
4、解其松弛问题LP，得最优解 x1*7 / 2 ， x2*5/ 2 ，不满足整数要求。显然x10 ，x20 为问题 IP 的一个可行解。（1 ）依据以上信息，给出问题IP 最优目标函数值的初始上下界；（2 ）写出针对 x2 的分支子问题；（3 ）基于上述分支子问题，完成问题IP 的求解（提示：可用图解法） ，给出最优解并更新最优目标函数值的上下界。 （本题共 10 分，第 1 小题 2 分，第 2 小题 3分，第 3 小题 5 分）解：（ 1）将松弛问题最优解代入目标函数， z 273514 1 ；222x1 0 ， x2 0 为 IP 的一个可行解，对应的 z0 ；故最优目标函数值：0 z*1
5、412（ 2）分支子问题B1 :max z2x13x2B2 :max z2x13x2s.t.x1x26s.t.x1x262x14x2172x14x217x22x23x1 , x20x1 , x2 0x1 , x2为整数x1, x2为整数（ 3）用图解法（略）求得：B1 松弛问题最优解x14, x22 ，恰好满足整数要求，不必再探测，对应目标值z 14 ；更新最优目标函数值上下界： 14 z*14 12B2 松弛问题最优解x15 / 2, x23，不满足整数要求。可编辑-精选文档 -对应目标值 z253314 ，不大于已知的 z* 的 下界，故不可能找到更好的2解，不必再探测。所有子问题探测完毕
6、，得到最优解：x14, x22三、已知约束非线性优化问题minf ( x)( x12) 2(x2 3)2s.t. x2(x12)20x2x10（1 ）判断该问题是否为凸规划；（2 ）写出该问题的Kuhn-Tucker条件；（3 ）利用 Kuhn-Tucker条件，求出该问题的 K-T 点和最优解。（本题共 15 分，每小题 5 分）解：（ 1）易证不等式约束函数x2( x12) 2 为凹函数，满足x2( x12)20 的点的集合不是凸集，故该问题不是凸规划。（ 2）重写原问题，以便套用K-T 条件：min f (x)( x12)2( x2 3)2s.t. g (x)(x12)2x2 0h( x
7、)x1x20K-T 条件：2( x12)2(x12)02( x23)（梯度条件）0( x12)2x20（互补松弛条件）0（不等式约束乘子非负条件）可编辑-精选文档 -( x12)2x20x1x20（可行性条件，可不写）（ 3）讨论：0( x12) 2x20x11x14x1x20x2和x241x11x14根据梯度条件可求出配套的Lagrange乘子：x21x242和224这两个点均为 K-T 点。02(x12)0x15/ 22(x23)0x25 / 2x1x201检查可行性： ( x12)2x2 = ( 52)2590 ，不满足不等式约束，故不可能是224K-T 点。因此，该问题有两个 K-T
8、点：x11和x14。x21x24它们具有相同的目标函数值，故都是该问题最优解，最优目标值为5。四、已知 A 点到 E 点单行线交通网络如下图所示， 箭线旁的数字表示该线路的距离。B16C14423A5B 2C25E13810B 3C34可编辑-精选文档 -(1) 用动态规划的逆推解法求出从 A 点到 E 点的最短路，要求列出计算过程。(2) 用图论中求最短路的 Dijkstra 算法求 A 点到 E 点的最短路，在算法执行过程中得到如下结果（ P 代表永久标号， T 代表临时标号，代表回溯指针）：P(B 1)=4T(C 1)=10(C1)= B 1(B1 )=AB16C14T(E)=+P(A)
9、=0T(B 2)=5T(C 2)=824(E)=M(C2 )=B 1(A)=0(B2)=A3A5B 2C25E13P(B 3)=3T(C 3)=7(B3)=A(C3)= B 3108B 34C3指出下一步迭代应将哪个点的临时标号T 修改为永久标号 P，列出算法终止时各点的标号值及指针（）值（不要求列出计算过程） 。（本题共 20分，每小题 10 分）解：（ 1）分 3 个阶段，最优指标值为各点到E 点的最短距离。初始状态 s1A ，状态转移方程 sk 1uk (sk )当 k 3 时：f3 (C1)2 ， u3 (C1)Ef3 (C2 )5 ， u3 (C2 )E可编辑-精选文档 -f3 (C
10、3 )10 ， u3 (C3 )E当 k 2 时：f2 (B1)min 6f3 (C1 ), 4f3 (C2 )min 62, 458 ， u2 (B1)C1f2 (B2 )min 3f3 (C1 ),1f3 (C3)min 32, 1105 ， u2 (B2 )C1f2 (B3)min 8f3 (C2 ), 4f3(C3 )min 85, 41013 ， u2 (B3 )C2当 k 1时：f1 (A)min 4f 2 ( B1 ), 5f2 (B2 ), 3f2 (B3 )min 48, 55,31310 ， u1 ( A)B2故 A 到 E 的最短距离为 10 ，最短路为： AB2C1E
11、。（ 2）下一步迭代应将 B2 点的临时标号 T 修改为永久标号 P。算法终止时各点的标号值及指针（）值如下：P( A)0 ； P(B1)4 ， P(B2 )5 ， P( B3)3 ； P(C1 )8 ， P(C2 )8 ， P(C3 )6 ；P( E)10( A) 0 ； ( B1)A ， ( B2 )A ， (B3 )A ； (C1 )B2 ， (C2 )B1 ， (C3 )B2 ；( E)C1五、某杂货店设置了一个小型停车场，有3 个车位。杂货店不营业时停车场关闭。在营业时间，当停车场未满时，车辆可进入停车场使用停车位，平均每小时有两个停车位被占用；若停车场已满，则到达的车辆会离开且不再
12、回来。据统计，0 ， 1，2 ，3 个停车位被占用的概率分别为：P00.2 ， P10.3 ， P20.3 ， P30.2可编辑-精选文档 -（ 1）将停车场看作一个排队系统，说明该排队系统中顾客是什么？服务台又是什么？有多少个服务台？系统容量有多大？（2 ）确定该系统的基本性能指标：期望队长Ls ，期望排队长 Lq ，顾客平均等待时间 Wq ，顾客平均逗留时间Ws 。（3 ）该杂货店对驾车购物顾客的损失率是多少？（本题共10 分，第 1 小题 2分，第 2 小题 6 分，第 3 小题 2 分）解：（ 1）该排队系统中顾客是车辆，服务台是停车位，有3 个服务台，系统容量为3。3（ 2）期望队长
13、 LsnPnP12P23P30.320.330.21.5n 0期望排队长 Lq =0顾客等待时间 Wq011（小时）顾客平均逗留时间 Ws Wq00.52（ 3）该杂货店对驾车购物顾客的损失率就是停车场满员的概率0.2 。六、设矩阵对策 G S1, S2 ; A 中，局中人 I 策略集为 S11, 2 , 3 ，局中人 II 策略43集为 S21, 2 ，局中人 I 的赢得矩阵 A21。13（1 ）用图解法求解该矩阵对策，给出局中人II 的最优策略及矩阵对策的值；（2 ）根据（ 1 ）的结果，确定局中人I 的最优策略。（本题共 10 分，每小题 5分）可编辑-精选文档 -解：（ 1）令局中人
14、II 的混合策略为 ( y,1 y)T ，图解法（略）得到 y2 / 5 。T局中人 II 的最优策略为2,3，对策的值 VG7 。555（ 2）设局中人I的混合策略为 ( x1 , x2 , x3 )T 当局中人 I 采取策略1 ，期望赢得为423 31VG （严格不等式），故 x1 =0 。（ 或由图直接得出此结论亦可 ）555由于局中人 II的最优策略 y10 ， y2 0 ，故有2x2x3VG ，在加上概率归一条x23x3VG件 x2x3 1，解得x24/ 5x21/ 5故局中人 I 的最优策略为 0, 4,1T（通过其它思路求出亦可 ）55七、已知决策收益表如下：状态状态 1状态 2
15、状态 3概率0.30.50.2方案 120128方案 216ab方案 3121212a, b为两个待定参数， a12 ，b8 。已知此问题的完全情报价值为1.6 ，拥有完全情报时的期望收益为16.4 。若按最大期望收益准则决策，其结果为选择方案2。试求 a、b 之值。 (本题共 10 分)解：可编辑-精选文档 -如果拥有完全情报，则对应状态1、状态 2、状态 3 时，所获得的收益分别为：max(20,16,12)=20，max(12, a,12)= a， max(8, b ,12)=max( b ,12) 。则完全情报下的期望收益为：EVWPI =0.3 20+0.5 a+0.2 max(b,
16、12)只拥有原始情报时，方案2 为最优方案，则期望收益为：EVWOI=0. 3 16+0.5 a+0.2 b完全情报价值 EVPI=1.6 ，拥有完全情报时的期望收益EVWPI=16.4 ，因此：EVWPI =0.3 20+0.5 a+0.2 max(b,12)=16.4EVPI=EVWPI- EVWOI=16.4-(0.3 16+0.5 a+0.2 b )=1.6上述两式化简为：0.5 a+0.2 max(b,12)=10.40.5 a+0.2 b=10分情况讨论：（ 1） b12 ，则有： 0.5a+0.2 b =10.4 且 0.5 a+0.2 b =10 ，不可能成立，舍去。（ 2）b 12 ，则有：0.5 a +0.2 12=10.4且 0.5a+0.2 b=10 ，得到 a=16 andb=10 。综上， a=16, b=10 。可编辑