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

一、计算题

1． 判断表1和表2中给出的调运方案能否作为用表上作业法求解时的初始解? 为什么?

表1 表

2

【答案】 表1中有5个基格，而要作为初始解，应有调运方案不能 作为表上作业法的初始解; 表 2中，有10个数基格，而理论上只应有案不能作为表上作业法的初始解。

2． 线性规划问题

当t l =t2=0时，该问题的最优单纯型表如表所示。

表

个基格，所以表给出的

个，多出了一个，所以表2给出的调运方

（l ）确定所有参数，并写出该线性规划问题; （2）当t 2=0时，分析使最优解不变的t 1的变化范围; （3）当t 1=0时，分析使最优基不变的t 2的变化范围。

【答案】（l ）由最优单纯型表得出，x l 和x 3为基变量x B ，则对应初始单纯形表中为:

由最优单纯型表得到由由由由

，得, 得

, 得, 得

, 所以, 求得, 解得, 解得

，即

,

综上，当t l =t2=0时，线性规划为

（2）x 1是基本量，它的系数变化会影响到检验数的变化。若使最优解不变，应有:

, 解得

（3）

将其反映到最终单纯形表中，其b 列数字为:

当b ≥0时问题的最优解不变，解得

3． 己知有六台机床x l ，x 2，…，x 6，六个零件y 1，y 2，…，y 6。机床x 1可加工零件y 1; x 2可加工零件y l ，y 2; x 3可加工零件y l ，y 2，y 3，x 4可加工零件y 2; x 5可加工零件y 2，y 3，x 4; x 6可加工零件y 2，y 5，y 6。现在要求制订一个加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件加工。试把这个问题化为求网络最大流的问题，求出能满足上述条件的加工方案。

【答案】依题意，画出最大容量的网络图，并令（l ）标号过程。进行标号，并找出增广链:

因v t 已标号，转入调整过程。

，如图所示。

图

（2

）调整过程。按点的第一个标号找到一条增广链

整:

。按照

在

上调

调整后得如图所示的可行流，对这个可行流进入重新标号，寻找增广链。

图

反复标号过程和调整过程，最后得到如图所示的结果。

图

可知，最优加工方案为:机床x1加工零件y1，机床x2加工零件y2，机床x3加工零件y3，机床x5加工零件y4，机床x6加工零件y6，机床x4不加工零件，零件y5没有机床加工。 最大流量是V （f ）=5。