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

一、简答题

1． 简述求解最小费用最大流的赋权网络设置方法。

【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点， 每条边用两条方向相反的有向边代替，各边的权

②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令

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

【答案】

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

按如下规则:

二、计算题

3． 某厂有100台设备，可用于加工甲、乙两种产品。根据以往经验这些设备都用于加工甲产品时，每季度 末损坏1/3台; 而都用于加工乙产品时，每季度末损坏1/10台，损坏的设备当年不能修复。每台机器一季度用于 加工甲产品可获利10百元; 加工乙产品可获利7百元。问如何安排各季度加工甲、乙产品的设备台数，才能使 全年获得最大? （用动态规划方法求解）

【答案】该问题可以分为4个阶段。k 表示季度，状态变量s k 表示k 年初拥有的可投入最大机器数量，决策变量 x k 表示第k 季度的分配在用产品的设备数量，则s k -u k 为分在乙产品的设备数量。

状态转移方程:

K 阶段允许决策集合为：

指数

为第k 季度初从s k 出发到第4季度结束最大产值

当k=4时，

即在第4年全部要

4． 已知线性整数规划:

其相应伴随规划的最优解为:x l =0，x 2=7及单纯形表为

表

（1）对x 2进行分枝，写出相应的分枝规划（不要求求解）: （2）由最优单纯形表的第二个方程推导出割平面方程。 【答案】（l ）对x 2进行分枝，则得问题B 1和B 2。

（2）得 化成，最终得割平面方程

5． 某科学试验可用l#、2#，3#三套不同仪器中的任一套去完成。每做完一次试验后，如果下次仍用原来的 仪器，则需要对该仪器进行检查整修而中断试验:如果下次换用另外一套仪器，则需拆装仪器，也要中断试验。 假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪器换下来隔一次再重新使用时，不会由于整修而 影响试验。设i#仪器换成j#仪器所需中断试验的时间为t ij ，如表所示。现要做4次试验，问应如何安排使用 仪器的顺序，使总的中断试验的时间最小?

表

【答案】设A 、B 、c 分别代表三套仪器l#、2#，3#，A i 表示在第i 次实验中用仪器A ，依此类推B i 、C i ，并设虚拟开始S 和结束点D 。则得如图所示网络图: