2018年安徽工业大学管理科学与工程学院875运筹学考研基础五套测试题
● 摘要
一、简答题
1． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。
【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因
，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:
可见，当Cr 变化成△Cr 后，最终表中的检验数是:
2． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
3． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。 4． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、证明题
5． 设
是正定二次函数
。试证:若
关于Q 共扼
分别
在两条平行
于方向P 的直线上的极小点，则方向p 与方向
【答案】因为则有从而又由于则有
6． 设线性规划问题解。
【答案】其对偶问题为设
，
即可得
，由此得
，即是
，
使
1
有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优
分别是f （x ）在两条平行于方向P 的直线上的极小点， ，
是原问题的最优解，则其对应的基矩阵B
必存在，这时Y 是对偶问题的可行解，它使
由于原问题的最优解，使目标函数取值
对偶问题的最优解，因此单纯形乘子
为函数以
，是对偶问题的最优解。
，有
7． 证明:矩阵对策G={S1，S 2; A}在混合策略意义下有解的充要条件是:存在
的一个鞍点，即对一切
【答案】（l ）先证明充分性 对任意X , Y 均有
，故得出
又所以，
另一方便，对任何X ，Y 有
① ，所以得
②
由不等式①、②
，
（2）再证必要性。设有X*，Y*，使得
则由
，有
所以对任意X ，Y ，有
综上得证。
三、计算题
8． 已知A 、B 各自的纯策略及A 的赢得矩阵如表所示，求双方的最优策略及对策值。
表
【答案】在A 的赢得矩阵中第4列优超于第2列，第l 列优超于第3列，故可划去第2列和第3列，得到新的赢得矩阵
对于A 1，第2行优超于第4行，因此去掉第4行，得到
对于A 2，易知无最优纯策略，用线性规划的方法求解，其相应的相互对偶的线性规划模型如下:
相关内容
相关标签