2017年西安石油大学946运筹学之运筹学教程考研复试核心题库
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点， 每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 简述影子价格的经济含义。
【答案】影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影 子价格对市场具有调节作用，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资 源用于扩大生产; 而当某种资源的市场价高于企业影子价格时，则企业的决策者应把己有资源卖掉。
按如下规则:
二、计算题
3． 求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程最短。
表
【答案】从1城出发最后回到l 城中间要经过五个城市，因此将该问题划分5个阶段，阶段变量k=l，2，3，4，5; 记从
示到达i 城之前中途所经过的城市的 集合，则有
表示由1城到i 城的中间城市集合; S 表。
因此，可选取（i ，S ）作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数人（i ，S ）为从1城开始经由k 个中间城市的S 集到i 城的最短路线的距离，则可写出动态规划的递推关系为
边界条件为由边界条件可知
（l ）当k=l时，从1城开始，中间经过一个城市到达i 城的最短距离为
（2）当k=2时，从1城开始，其间经过两个城市（此两城市的顺序任意）到达i 城的最短距离为
所以，所以，所以，所以，所以，所以，所以，所以，
。
。为最优决策函数，它表示从1城开始经k 个中间城市的s
集到i 城的最 短路线上紧挨着i 城前面的那个城市。
。
。
。
。
。
。
。
所以，所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。
。
所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。