《北航《运筹学试卷A》期末试题&参考答案》由会员分享，可在线阅读，更多相关《北航《运筹学试卷A》期末试题&参考答案（9页珍藏版）》请在金锄头文库上搜索。
1、 A 运筹学试卷A 参考答案一、对线性规划问题在第1个约束中引入人工变量，第2个约束中引入松弛变量，采用大M法利用单纯形表求解得到了最优解，单纯形表完整的迭代过程见下表：4501211001832010045051/211/21/200301/2-3/213/20045041211008013/2-110-3-20（1）试根据上述求解过程单纯形表，确定参数，和的值，以及该问题的最优解；（2）以上述线性规划问题为原问题，写出其对偶问题；（3）利用对偶性质，求出对偶问题的最优解。（本题共25分，第1小题15分，第2、3小题各5分）解：（1）由最终单纯形表的判别数，得到；由中间单纯形表右端项的初等行
2、变换规则：，得到；由中间单纯形表到最终单纯形表的变换规则：，得到；该问题的最优解：，（2）对偶问题：（3）依据互补松弛定理。在最优解处，原问题第2个约束为严格不等式，故。由于，故对偶问题第1个约束为等式，得到。故对偶问题的最优解为，。二、用分支定界法求解如下整数规划问题LP先解其松弛问题LP，得最优解，不满足整数要求。显然，为问题IP的一个可行解。（1）依据以上信息，给出问题IP最优目标函数值的初始上下界；（2）写出针对的分支子问题；（3）基于上述分支子问题，完成问题IP的求解（提示：可用图解法），给出最优解并更新最优目标函数值的上下界。（本题共10分，第1小题2分，第2小题3分，第3小题5分
3、）解：（1）将松弛问题最优解代入目标函数，；，为IP的一个可行解，对应的；故最优目标函数值：（2）分支子问题 （3）用图解法（略）求得：松弛问题最优解，恰好满足整数要求，不必再探测，对应目标值；更新最优目标函数值上下界：松弛问题最优解，不满足整数要求。对应目标值，不大于已知的的下界，故不可能找到更好的解，不必再探测。 所有子问题探测完毕，得到最优解：三、已知约束非线性优化问题（1）判断该问题是否为凸规划；（2）写出该问题的Kuhn-Tucker条件；（3）利用Kuhn-Tucker条件，求出该问题的K-T点和最优解。（本题共15分，每小题5分）解：（1）易证不等式约束函数为凹函数，满足的点的集
4、合不是凸集，故该问题不是凸规划。（2）重写原问题，以便套用K-T条件：K-T条件： （梯度条件） （互补松弛条件） （不等式约束乘子非负条件） （可行性条件，可不写）（3）讨论： 和 根据梯度条件可求出配套的Lagrange乘子： 和这两个点均为K-T点。 检查可行性：=，不满足不等式约束，故不可能是K-T点。因此，该问题有两个K-T点： 和 。它们具有相同的目标函数值，故都是该问题最优解，最优目标值为5。四、已知A点到E点单行线交通网络如下图所示，箭线旁的数字表示该线路的距离。1052481346354B3B1B2C1C2C3EA(1)用动态规划的逆推解法求出从A点到E点的最短路，要求列出计
5、算过程。(2)用图论中求最短路的Dijkstra算法求A点到E点的最短路，在算法执行过程中得到如下结果（P代表永久标号，T代表临时标号，l代表回溯指针）：1052481346354B3B1B2C1C2C3EAP(A)=0l(A)=0P(B1)=4l(B1)=AT(B2)=5l(B2)=AP(B3)=3l(B3)=AT(C1)=10l(C1)= B1T(C2)=8l(C2)=B1T(C3)=7l(C3)= B3T(E)=+l(E)=M指出下一步迭代应将哪个点的临时标号T修改为永久标号P，列出算法终止时各点的标号值及指针（l）值（不要求列出计算过程）。（本题共20分，每小题10分）解：（1）分3个
6、阶段，最优指标值为各点到E点的最短距离。初始状态，状态转移方程当时：，当时：，当时：，故A到E的最短距离为10，最短路为：。（2）下一步迭代应将点的临时标号T修改为永久标号P。算法终止时各点的标号值及指针（l）值如下：；，；，；，；，；五、某杂货店设置了一个小型停车场，有3个车位。杂货店不营业时停车场关闭。在营业时间，当停车场未满时，车辆可进入停车场使用停车位，平均每小时有两个停车位被占用；若停车场已满，则到达的车辆会离开且不再回来。据统计，0，1，2，3个停车位被占用的概率分别为：，（1）将停车场看作一个排队系统，说明该排队系统中顾客是什么？服务台又是什么？有多少个服务台？系统容量有多大？（
7、2）确定该系统的基本性能指标：期望队长，期望排队长，顾客平均等待时间，顾客平均逗留时间。（3）该杂货店对驾车购物顾客的损失率是多少？（本题共10分，第1小题2分，第2小题6分，第3小题2分）解：（1）该排队系统中顾客是车辆，服务台是停车位，有3个服务台，系统容量为3。（2）期望队长期望排队长=0顾客等待时间顾客平均逗留时间（小时）（3）该杂货店对驾车购物顾客的损失率就是停车场满员的概率0.2。六、设矩阵对策中，局中人I策略集为，局中人II策略集为，局中人I的赢得矩阵。（1）用图解法求解该矩阵对策，给出局中人II的最优策略及矩阵对策的值；（2）根据（1）的结果，确定局中人I的最优策略。（本题共1
8、0分，每小题5分）解：（1）令局中人II的混合策略为，图解法（略）得到。局中人II的最优策略为，对策的值。（2）设局中人I的混合策略为当局中人I采取策略，期望赢得为（严格不等式），故=0。（或由图直接得出此结论亦可）由于局中人II的最优策略，故有，在加上概率归一条件，解得故局中人I的最优策略为（通过其它思路求出亦可）七、已知决策收益表如下：状态状态1状态2状态3概率0.30.50.2方案120128方案216ab方案3121212为两个待定参数，。已知此问题的完全情报价值为1.6，拥有完全情报时的期望收益为16.4。若按最大期望收益准则决策，其结果为选择方案2。试求a、b之值。(本题共10分)
9、解：如果拥有完全情报，则对应状态1、状态2、状态3时，所获得的收益分别为：max(20,16,12)=20，max(12,a,12)=a，max(8, b,12)=max(b,12)。则完全情报下的期望收益为：EVWPI=0.320+0.5a+0.2max(b,12)只拥有原始情报时，方案2为最优方案，则期望收益为：EVWOI=0.316+0.5a+0.2b完全情报价值EVPI=1.6，拥有完全情报时的期望收益EVWPI=16.4，因此：EVWPI=0.320+0.5a+0.2max(b,12)=16.4EVPI=EVWPI- EVWOI=16.4-(0.316+0.5a+0.2b)=1.6上述两式化简为：0.5a+0.2max(b,12)=10.40.5a+0.2b=10分情况讨论：（1）b12，则有：0.5a+0.2b=10.4 且 0.5a+0.2b=10，不可能成立，舍去。（2）b12，则有：0.5a +0.212=10.4 且 0.5a+0.2b=10，得到a=16 and b=10。综上，a=16, b=10。
