北航《运筹学试卷A》期末试题&参考答案.doc

《北航《运筹学试卷A》期末试题&参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、A《运筹学试卷A》参考答案一、对线性规划问题在第1个约束中引入人工变量，第2个约束中引入松弛变量，采用大M法利用单纯形表求解得到了最优解，单纯形表完整的迭代过程见下表：4501[2]1100183201004505[1/2]11/21/200301/2-3/213/20045041211008013/2-110-3-20（1）试根据上述求解过程单纯形表，确定参数，和的值，以及该问题的最优解；A（2）以上述线性规划问题为原问题，写出其对偶问题；（3）利用对偶性质，求出对偶问题的最优解。（本题共25分，第1小题15分，第2、3小

2、题各5分）解：（1）由最终单纯形表的判别数，得到；由中间单纯形表右端项的初等行变换规则：，得到；由中间单纯形表到最终单纯形表的变换规则：，得到；该问题的最优解：，，（2）对偶问题：（3）依据互补松弛定理。在最优解处，原问题第2个约束为严格不等式，故。由于，故对偶问题第1个约束为等式，，得到。故对偶问题的最优解为，。二、用分支定界法求解如下整数规划问题LP先解其松弛问题LP，得最优解，，不满足整数要求。显然，为问题IP的一个可行解。（1）依据以上信息，给出问题IP最优目标函数值的初始上下界；（2）写出针对的分支子问题；A（3）

3、基于上述分支子问题，完成问题IP的求解（提示：可用图解法），给出最优解并更新最优目标函数值的上下界。（本题共10分，第1小题2分，第2小题3分，第3小题5分）解：（1）将松弛问题最优解代入目标函数，；，为IP的一个可行解，对应的；故最优目标函数值：（2）分支子问题（3）用图解法（略）求得：松弛问题最优解，恰好满足整数要求，不必再探测，对应目标值；更新最优目标函数值上下界：松弛问题最优解，不满足整数要求。对应目标值，不大于已知的的下界，故不可能找到更好的解，不必再探测。所有子问题探测完毕，得到最优解：三、已知约束非线性优化问题

4、（1）判断该问题是否为凸规划；A（2）写出该问题的Kuhn-Tucker条件；（3）利用Kuhn-Tucker条件，求出该问题的K-T点和最优解。（本题共15分，每小题5分）解：（1）易证不等式约束函数为凹函数，满足的点的集合不是凸集，故该问题不是凸规划。（2）重写原问题，以便套用K-T条件：K-T条件：（梯度条件）（互补松弛条件）（不等式约束乘子非负条件）（可行性条件，可不写）（3）讨论：①Þ和根据梯度条件可求出配套的Lagrange乘子：和这两个点均为K-T点。②ÞA检查可行性：=，不满足不等式约束，故不可能是K-T点。

5、因此，该问题有两个K-T点：和。它们具有相同的目标函数值，故都是该问题最优解，最优目标值为5。四、已知A点到E点单行线交通网络如下图所示，箭线旁的数字表示该线路的距离。1052481346354B3B1B2C1C2C3EA(1)用动态规划的逆推解法求出从A点到E点的最短路，要求列出计算过程。(2)用图论中求最短路的Dijkstra算法求A点到E点的最短路，在算法执行过程中得到如下结果（P代表永久标号，T代表临时标号，l代表回溯指针）：1052481346354B3B1B2C1C2C3EAP(A)=0l(A)=0P(B1)=4

6、l(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分）A解：（1）分3个阶段，最优指标值为各点到E点的最短距离。初始状态，状态转移方程当时：，，，当时：，，，当时：，故A到E的最短距离为10，最短路为：。（2）下一步迭代应将点的临时标号T修改为永久

7、标号P。算法终止时各点的标号值及指针（l）值如下：；，，；，，；；，，；，，；A五、某杂货店设置了一个小型停车场，有3个车位。杂货店不营业时停车场关闭。在营业时间，当停车场未满时，车辆可进入停车场使用停车位，平均每小时有两个停车位被占用；若停车场已满，则到达的车辆会离开且不再回来。据统计，0，1，2，3个停车位被占用的概率分别为：，，，（1）将停车场看作一个排队系统，说明该排队系统中顾客是什么？服务台又是什么？有多少个服务台？系统容量有多大？（2）确定该系统的基本性能指标：期望队长，期望排队长，顾客平均等待时间，顾客平均逗留

8、时间。（3）该杂货店对驾车购物顾客的损失率是多少？（本题共10分，第1小题2分，第2小题6分，第3小题2分）解：（1）该排队系统中顾客是车辆，服务台是停车位，有3个服务台，系统容量为3。（2）期望队长期望排队长=0顾客等待时间顾客平均逗留时间（小时）（3）该杂货店对驾车购物顾客的损失率就是