2016年东南大学土木工程学院972运筹学考研必备复习题库及答案
● 摘要
一、证明题
1． 己知九个人v 1，v 2，…，v 9中v 1和两个人握过手，v 2和v 3各和四个人握过手，v 4，v 5，v 6，v 7各和五个人握过手，v 8，v 9各和六个人握过手，证明这九个人一定可以找出三人互相握过手。
【答案】该问题可表述为一个包含9个点（每个人代表一个点）的图的问题。依题意知 d （v l ）=2，d （v 2）=d（v 3）=4，d （v 4）=d（v 5）=d（v 6）=d（v 7）=5，d （v 8）=d（v 9）=6 其中，边v i ，v j 〕代表v i 和v j 握过手。对于v 9，因为d （v 9）=6，所以v 4，v 5，v 6，v 7中至少有两个点与v 9之间 存在连线，设该两点为v 4和v 5。假设与v 4和与v 9相连的其他五点之间无边，
则
，与已知的 d （v 4）=5相矛盾，故假设不成立。即v 4与上述五点间必存在至少
两条边，设其中一点为v k ，则v k ，v 4，v 9两两相连，即存在三人之间互相握过手。
2． 证明:r （x ）二x12+x22是严格凸函数。
【答案】首先求导为（2x l ，2x 2:） 求海塞矩阵
为正定矩阵，所以f （x ）为严格凸函数
二、计算题
3． 某公司为了扩大市场，要举行一个展销会，会址打算选择在甲、乙、丙三地。获利情况除了与会址有关系外，还与天气有关。天气可区分为晴、普通、多雨三种（分别以N 1，N 2，N3表示）. 通过天气预报，估计三种天气情况可能发生的概率为0.25，0.50，0.25。其收益情况见表，（1）用期望值准则进行决策。（2）用矩阵法进行决策。（3）用决策树法进行决策。
表
，E （乙），E （丙），则
【答案】（1）设选择甲、乙、丙三地的期望收益分别为E （甲）
选择甲地的期望收益最大。所以，最优方案为选择甲地。
（2）令收益矩阵为R ，概率矩阵为P ，期望值矩阵为E ，由表可知
于是
（3）构造决策树，并将有关数据标在决策树上，如图所示
可见甲地的期望收益最大，所以按矩阵法决策的最优方案为选择甲地。
图
，则
令选址方案为甲、乙和丙，三地的期望收益分别为E （甲）、E （乙）和E （丙）
因为E （甲）最大，所以采用决策树法进行决策的最优选址方案为甲地。
4． 在有互相排斥的约束条件的问题中，如果约束条件是（≤）型的，我们可用加以y i M 项（y i 是0-1变量， M 是很大的常数）的方法统一在一个问题中。如果约束条件是（≥）型的，我们将怎样利用y i 和M 呢?
【答案】在互相排斥的约束条件问题中，如果约束条件是（≥）型，我们可以分别在m 个约束条件右端减去y i M ， 其中y i 是0-1变量，M 是充分大的正数，且。