2017年兰州财经大学运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）恰好是问题的最优解。
二、计算题
3． 图所示的4座城市及其公路的连线情况，线上数字是两相邻城市每小时最多可能通过的车辆，试求从互一城市到第四城市的最大流量及安排。
数（以 1000辆为1个计量单位）
图
【答案】由图可知，城市1到城市4有3条路径。
最大流量为6000辆。
最大流量为2000辆。
最大流量为2000辆。
，由于在（2）（3）路径上，它们在③~④的最大流量和为14000辆，小于16000辆，故可行。故从第一城市到第四城市的最大流量为6000+2000+16000=24000辆，具体安排如路径（l ）（2）（3）所示。
4． 设某人有400万元资金，计划在四年内全部用到投资中去。已知在一年内若投资用去x 万元，就能获得最大。
（l ）用动态规划方法求解; （2）用拉格朗日乘数法求解;
（3）比较两种解法，并说明动态规划方法有哪些优点。 【答案】（l ）用动态规划方法解。
将问题划分为四个阶段k=1，2，3，4; 设状态变量s k 为第k 年年初可供投资金额
，
; 决策变量x k 为第k 年实际用于投资的金额; 设最优值函数
年至第4年末所得到的最大效用。
该问题的递推公式为:
当k=4时，当k=3时，令所以当k=2时，令所以当k=1时，
得极大值点
所以
所以该问题的最优解为:
优值为z*=43万元。
（2）用拉格朗日乘子法求解如下。
万元的效用。每年没有用掉的金额，连同利息（年利息10%）可再用于下一年的投
资。而每年己打算用于投资的金额不计利息。试制订金额的使用计划，而使四年内获得的总效用
表示从第k
得极大值点
得极大值点
万元。 =153万元；其最
；又由题意知s 1=400，所以
=86万元，
=104万元，
=126万元
，获得效用为设第i （i=1，2，3，4）年用于投资的金额为x i （万元）掉的金额为y j （万元）（其中y 4=0）。于是可建立数学模型
（万元），没有用
设
其中
为拉格朗日乘子
，
和y j ，求偏导数，并令其为零，即
解得：
为拉格朗日函数。分别将L
对
由
得
，x 2*=104（万元），x 3*=126（万元），x 4*=153（万元）所以x l *=86（万元）。 （3）两种解法的比较: 两种方法的结果相同。
但用动态规划方法求解有如下优点: ①容易确定全局最优解;
②不仅能得到最终解，而且得到了包含所有子过程的一族解，这样便于分析结果，同时又大大节省了计算量。