2016年华中科技大学环境科学与工程学院828运筹学考研内部复习题及答案
● 摘要
一、简答题
1． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界
域（称为分支）的方法，逐步减小和增大
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T
，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）
（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。 3． 试写出求解最短径路的Dijkstra 算法的步骤。 ; 。分支定界法就是将B 的可行域分成子区:， 最终求到z*。
二、证明题
4． . 令
试证
【答案
】为一组
使得
用左乘上式，并且由共轭关系可知： A 共轭向量，它们必线性无关。
则。 ，A 为为一组A 共轭向量（假定为列向量）对称正定矩阵，
令
由
知BA=E，所以
故得证。
5． 设m*m对策的矩阵为
。
其中，当时，当i=j时，证明此对策的最优策略为
【答案】由题意知，
，所以A 没有鞍点，故令最优混合策略
，则
即