2016年四川理工学院经济与管理学院813运筹学考研冲刺密押卷及答案
● 摘要
一、证明题
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． 假设线性规划问题为:
其中
，秩
运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。 【答案】一般情况下，经过迭代后解变为
再将上式代入目标函数式，整理后得到
令于是
再令则
第 2 页，共 18 页
这样当所有非基变量的检验数即3． 设线性规划问题解。
【答案】其对偶问题为
时，此时的解就为最优解。
1
有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优
设是原问题的最优解，则其对应的基矩阵B 必存在
，由此得
，即可得，
这时Y 是对偶问题的可行解，它使由于原问题的最优解
，使目标函数取值
，即是对偶
问题的最优解，因此单纯形乘子4． 设
是正定二次函数
，是对偶问题的最优解。
。试证:若
关于Q 共扼
分别
在两条平行
于方向P 的直线上的极小点，则方向p 与方向【答案】因为则有从而又由于则有
5． 设m*m对策的矩阵为
分别是f （x ）在两条平行于方向P 的直线上的极小点， ，
其中，当时，当i=j时，证明此对策的最优策略为
【答案】由题意知，
，所以A 没有鞍点，故令最优混合策略
第 3 页，共 18 页