当前位置：问答库＞考研试题

一、证明题

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． 设是正定二次函数。试证:若关于Q 共扼 分别在两条平行于方向P 的直线上的极小点，则方向p 与方向

【答案】因为

则有从而

又由于

则有 分别是f （x ）在两条平行于方向P 的直线上的极小点， ， 二、计算题

3． 某规划线性规划问题:

（1）写出其对偶问题;

（2）推导出原问题与对偶问题中目标函数之间的关系。

【答案】（1）其对偶问题为:

（2）若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。

证明:由于两者均有可行解，根据弱对偶性的推论，对原问题的目标函数值具有上界，对偶问题的

目标函数 值具有下界，因此两者均具有最优解。又知当原问题为最优解时，其对偶问题的解为可行解，且有z=w。由最优 性知，这时两者的解均为最优解。

4． 以下为目标规划问题，试求以下问题。

（l ）用单纯形法求这问题的满意解;

（2）若目标函数变为而

有什么变化?

（3）若第一个目标约束的右端项改为120，这时原满意解又有什么变化?

【答案】（l ）建立初始单纯形表，在表中将检验数列按优先因子个数排成三行，并采用单纯形法进行进一步迭代， 求解过程如表1所示。

表

1 ，问原满意解

由表可知，为该目标规划的满意解。

（2）将变化的优先等级直接反代入上表的最终单纯形表中，再计算各变量的检验数，如下表所示。

表

目标函数变化后，各检验数均为非负，所以满意解不变，仍为

（3）首先计算：

。

将△b’的值代入表1中最终单纯形表的b 列中，并进一步迭代，如下表所示。

表

该目标规划的满意解变为

。