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

一、简答题

1． 试写出标准指派问题的线性规划问题。

【答案】

A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:

2． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;

【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，

则

最优方案不发生变化。

二、计算题

3． 某整数规划模型如下:

其最优解为x=（18/7，19/7）。试用分枝定界法写出后续的两个分枝模型。 【答案】选择x l =18/7进行分支，问题B

l

则得问题B l ，B 2

T

问题B

2

4． 有A 、B 、C 、D 四种零件均可在设备甲或设备乙上加工。已知这两种设备上分别加工一个零件的费用 如表5一12所示。又知设备甲或设备乙只要有零件加工就需要设备的启动费用，分别为100元和巧0元。现要求 加工四种零件各3件，问应如何安排生产使总的费用最小? 请建立该问题的线性规划模型（不需求解）。加工一个 零件的费用（单位:元）

表

【答案】设i=1，2，3，4分别表示产品A 、B 、C 、D ; j=1，2表示设备甲、乙; x ij 表示产品i 在设备j 上生产的个数，

则得线性规划模型如下:

其中

5． 已知A 、B 两人对策时对A 的赢得矩阵如下，求双方各自的最优策略及对策值。

【答案】该对策为混合对策。利用优超原则，由于第三行优超第一行和第四行，故可划去第1、4行，得到新的赢得矩阵

由A l 可知，第2列优超第1列，第4列优超第3列，故可划去第1、3列，得到新的赢得矩阵

由A 2可知，第2列优超第1列，故可划去第l 列，得到新的赢得矩阵

由A 3可知，第2行优超第1行，故可划去第1行，得到新的赢得矩阵

故原矩阵对称的解为

6． 有10个城市，它们在坐标系中的位置如表所示，试完成以下工作。

（l ）用C 一W 节约算法求出经过每个城市一次且仅一次的一条最短线路。

（2）用Norback 和Love 提出的几何法，求出经过上述每个城市一次且仅一次的最短线路。 （3）比较上述两种方法得出的结果，并设计一种启发式方法，对上述较差的结果进行改进。

表

【答案】（l ）计算各点对之间的欧氏距离c ij ，计算结果如表所示。

表

取城市1为基点，利用公式如表所示。

。计算将弧表

插入线路中的节约值，