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

一、计算题

1． 用动态规划方法求解非线性规划问题:

【答案】考虑到该题为整数动态规划，适合列表计算 （1）K=3时，

表

（2）k=2时，

表

（3）K=1时

表

所以，

2． 有一线性方程组如下

得到最大目标函数值16。

现欲用无约束极小化方法求解，试建立数学模型并说明计算原理。

【答案】（1）建立数学模型

（2） ①令②

若

以梯度法为例解无约束极值问题，计算原理如下：

为初始近似点，取精度，则极小点

为。一般，

若

，则要找下一点

③设迭代至

，若

，需要求步长

。

=0.02 ，

若

，则要找下一

点

，则极小点

为

。

若

或者对度为止。

求导，并令等于0，则可求得最佳步长

。以②为判断准则，重复迭代，直至满足精

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 城前面的那个城市。