2018年华东理工大学科技信息研究所819运筹学考研核心题库
● 摘要
一、计算题
1． 用标号法求点V 1到点v 7的最大流，弧旁数字分别表示流量和容量。
图
【答案】（l ）标号过程:
①首先给v l 标上（0，+∞）
②检查v 1在弧（v 1，v 5）上，v 5的标号为（v l ，7）
③检查v 5，在弧（v 5，v 7）上，v 7的标号为（v 5，6）
因v 7有了标号，故转入调整过程。
（2）调整过程 按点的第一个标号找到一条增广链，按可行流:
在上调整f. 调整后得如图所示的
图
（3）对得到的可行流人进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v 1，v 3）上，v 3的标号为（v l ，2）
③检查v 3，在弧（v 3，v 6）上，v 6的标号为（v 3，2）
④检查v 6，在弧（v 6，v 7）上，v :的标号为（v 6，2）
因v 7有了标号，故转入调整过程。
（4）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
图
（5）对得到的可行流几进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v l ，v 2）上，v 2的标号为（v l ，2）
③检查v 2，在弧（v 2，v 5）上，v 5的标号为（v 5，2）
④检查v 5，在弧（v 5，v 6）上，v 6的标号为（v 5，2）
⑤检查v 6，在弧（v 6，v 7）上，v 7的标号为（v 6，2）
因v 7有了标号，故转入调整过程。
（6）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
图
（7）对得到的可行流进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v l ，v 5）上，v 5的标号为（v l ，l ）
③检查v 5，在弧（v 5，v 6）上，v 6的标号为（v 5，l ）
④检查v 6，在弧（v 6，v 7）上，v :的标号为（v 6，l ）
因v 7有了标号，故转入调整过程。
（8）调整过程
按点的第一个标号找到一条增广链，按在上调整调整后得如图所示的可行流
图
标号过程无法继续进行下去，算法结束。最大流量为:3+6+7=16。
2． 已知线性规划问题
用单纯形法求解，得到最终单纯形表如表所示。
表
（1）求a 11，a 12，a 13，a 21，a 22 ，a 23，b 1，b 2 的值；
（2）求c 1，c 2，c3的值。
【答案】（l ）由题意可设初始单纯形表的增广矩阵为
最终单纯形表的增广矩阵为
对矩阵（）作初等行变换，使其第4，5列组成单位矩阵
相关内容
相关标签