2017年长安大学运筹学考研复试核心题库
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
2． 简述对偶问题的“互补松弛性”。
【答案】互补松弛性:若当且仅当为
最优解。
分别是原问题和对偶问题的可行解。那么
，
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
二、计算题
3． 某工厂有1000台机器，拟分四个阶段使用。已知在每个阶段有两种生产任务，进行第一种生产时每台机 器可收益9千元，其机器报废率为0.3，而进行第二种生产时每台机器可收益6千元， 其机器报废率为0.1。问怎 样分配机器，使收益最大? （要求写出动态规划模型的基本要素并求解）
【答案】将此题看成一个4个阶段决策问题。令s k 为状态变量，它表示第k 阶段初拥有的完好机器数量，决策变量u k 为第k 阶段分配给第一种生产的机器数量，于是S k -U K 为该阶段分配给第二种生产的机器数量。
状态转移方程为v K =guk +6（s K -u k ） 令最优值函数
表示由机器数量s k 出发，从第k 阶段开始到第4阶段结束时所获得的收
益最大值，故 有递推关系式:
因是
的线性单调增函数，故得最优解
相应的
，设v k 为第k 阶段的收益，则
故得最优解
，相应的有
计算结果表明，第1阶段将r000台机器投入第二种生产，第2阶段将900台机器投入到第二种生产，第3 阶段将sro 台机器投入到第一种生产，第4阶段将567台机器投入到第一种生产。可得最大收益为23793千元。
4． 某建筑公司最近几年的发展重点是承接中东等地区的建筑项目。公司需要一种大型的建筑设备，该设备 今后4年的购买价格（预测值）分别为（5 .0，5.3，5.7，6.0）（万元）（产品购买价+运输到工地的费用）。如该设备连 续使用，其第i 年的使用费及维修费分别为（l ，1.7，2.5，3.3）（万元），由于路途遥远，淘汰后的设备就在当地折价 处理了，使用满i 年的设备处理价格为（3.3，2.5，1.5，0.8）（万元）. 公司在制定一个4年的设备购买计划，你有什 么建议? （限用图论理论，写出算法，计算过程，最终结论，最佳总费用）
【答案】可以把这个问题转化为最短路问题，根据题意绘制如下赋权有向图。
图
采用Dijksra 算法计算图1中的最短路为:
=0; 对其余点进行T 标号，
（l ）对起点1进行P 标号，即p （l ）即检查点1，进行T 标号：（2）点2获得P 标号，. （3）点3获得P 标号，（4）点4获得P 标号，（5）点5获得P 标号，）上图中的最短路为
检查点2，修改T 标号:检查点3，修改T 标号:检查点4，无需修改T 标号。 求解结束。
。即第一年初购进一台设备，第三年初淘汰掉并购置新设备，直
至第四年末淘汰 掉。最佳总费用11.1万元。
5． 有4个工人，要指派他们分别完成4项工作，每个人做各项工作所消耗的时间如表所示。问指派哪个人去完成哪项工作，可使总的消耗时间为最小?
表
【答案】第一步:将系数矩阵进行变换为
第二步:进行试指派，得到
因为m=3 第三步：做最少的直线覆盖所有的0元素，并进行再指派 指派成功，此项工作有多种指派方案，minz=70，指派矩阵如下:
相关内容
相关标签