2016年中国民航大学空中交通管理学院运筹学复试笔试仿真模拟题
● 摘要
一、计算题
1． 证明如下序列不可能是某个简单图的次的序列: （l ）7，6，5，4，3，2; （2）6，6，5，4，3，2，l ; （3）6，5，5，4，3，2，l 。 【答案】（1）由定理知，能是图的次序列。
（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。 （3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。
； v 2与v 1之间存在边e 12:，而①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7）
v 7的次为1，所以必不与v 1外的其他点相连。因而，v 2与除v 1，v 7外的四点之间各有一条连线。 至此，v l 、v 2与v 3、v 4、v 5和v 6中任意一个就组成了环，则G 不是简单图。
②假定G 中无环，则根据情形①的分析，v 1的关联边中必存在重复边。从而G 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。
2． 在N 个地点中选t 个（N>t）建厂，在那i 个地点建厂（1=1，2，……N ）所需投资为万元，占地亩， 建成以后的生产能力为p i 万吨，现在有总投资1万元，土堤L 亩，应如何选择厂址使建成后总生产能力最大。
【答案】引入0-1变量xi （i=l，2，. ……，t ） 令
目标函数为：
为偶数，而在此序列中，
为奇数，所以此序列不可
3． 某工厂有两条生产线生产某一产品，第一生产线每小时生产2个单位产品，第二生产线每小时生产1/2单位产品，正常开工每周40小时，每单位产品获利100元。设: （1）第1目标是生产180个单位产品;
（2）第2目标是限制第一条生产线每周加班不得超过10小时; （3）第3目标避免开工不足;
（4）最后目标是加班时数达到最少。假定两条生产线的开工费用相同。 试建立上面问题的数学模型。
【答案】设第一条生产线每周开工x , 小时，第二条生产线每周开工x2小时，分别赋予四个目标P 1、P 2、P 3、P 4优先因子。
4． 某工厂生产三种产品，各产品重量与利润关系如表所示，现将此三种产品运往市场出售，运输能 力总重量不超过6吨，问如何安排运输使总利润最大。
表
、
【答案】设运输三种产品的重量分别为x 1，x 2，x 3，则可建立数学模型
用动态规划方法来求解，此问题转化成求f 3（6）。 ①计算f 3（6）。
可见，要计算f 3（6），必须先求f 2（6），f 2（2）。 ②计算f 2（6），f 2（2）。
可见，要求f 2（6），f 2（2），必须先求出f 1（6），f 1（3），f 1（0），f 1（2）。 ③计算f 1（6），f 1（3） ，f 1（0），f 1（2）。
④所以，
f 2（2）=f1（2）=80, 此时x 1=1，x 2=0，x 3=1 ⑤计算得
于是，最佳运输方案有两个:
。
5． 设某人有400万元资金，计划在四年内全部用到投资中去。己知在一年内若投资用去x 万元，就能获 得
万元的效用。每年没有用掉的金额，连同利息（年利息10%）可再用于下一年的投资。而每年己打算用于投资的金额不计利息。试制订金额的使用计划，而使四年内获得的总效用最大。 （l ）用动态规划方法求解; （2）用拉格朗日乘数法求解;
（3）比较两种解法，并说明动态规划方法有哪些优点。 【答案】（l ）用动态规划方法解。
2，3，4; 设状态变量s k 为第k 年年初可供投资金额，将问题划分为四个阶段k=1，
决策变量x k 为第k 年实际用于投资的金额; 设最优值函数的最大效用。
该问题的递推公式为:
当k=4时，当k=3时，令所以
x 1=0，x 2=0，x 3=0，此时，
;
表示从第k 年至第4年末所得到
得极大值点