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

一、简答题

1． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若分别是原问题和对偶问题的可行解。那么，当且仅当为最优解。

2． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】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 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

二、计算题

3． 某厂生产A 、B 两种产品，需经过金工和装配两个车间加工，有关数据如表所示. 产品B 无论生产 批量大小，每件产品生产成本总为400元。产品A 的生产成本分段线性:第1件至第70件，每件成本为200元; 从第71件开始，每件成本为190元。试建立线性整数规划模型，使该厂生产产品的总利润最大。

表

【答案】设x l ，x 2为产品A 、B 的个数，

则建立线性整数规划模型如下:

4． 已知有m 个生产地点A i ，i=1，…，m ，可供应某种物资，其供应量为a i ，i=1，…，m ; 有n 个销售地B j ，j=l，…，n ，需要该种物资，其需要量为b j ，j=l，…，n ; 从各生产点往需求点发运时，均需经过P 个中间编组站之一转运，若启用第k 个编组站，不管转运量多少，均发生固定费用f k ，而第k 个编组站的转运容量为Q k （k=1，…，p ）。从A i 到P k 及P k 到B i 运输单位物资的运价分别为c ik 和c kj ，现要制定一个使总运费最小的调运方案。建立该问题的混合整数规划数学模型。

【答案】设

示编组站k 运往销售点j 的运量。则得模型

表示销售点i 运往编组站k 的运量，x kj 表

5． 用线性规划方法求解下列矩阵对策，其中A 为

【答案】（l ）在A 中，第2列优超于第3列，故可划去第3列，得到新的赢得矩阵

可将问题化为如下两个互为对偶的线性规划问题。

利用单纯形方法求解问题（D ），迭代过程如表所示。

表

从上表中可得到问题（D ）的解为

由表中最终单纯形表可知，问题（P ）的解为

又因为开始就划去第3列，所以，于是

（2）在A 中，由于第l 列优超于第3列，故可划去第3列，得到新的赢得矩阵

可将问题化为如下两个互为对偶的线性规划问题。