2016年首都经济贸易大学903管理学综合之《运筹学教程》考研必备复习题库及答案
● 摘要
一、计算题
1． 用运输问题的表上作业法求解线性规划问题:
【答案】由题意，得到运价表为:
由此可得，该问题是个运输平衡问题。
第一步，用沃格尔法得到初始方案为
第二步，用位势法得到初始方案中非基变量的检验数为
从上述计算可得，所有非基变量的检验数均大于0，所以该初始方案就是最优方案。
x 13=20，x 22=15，x 23=5
2． 用标号法求点V l 到点v 7的最大流，弧旁数字分别表示流量和容量。
图
即x ll =10，
【答案】（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。
3． 某软件公司可承揽四个软件开发项目，每一项目均由A ，B ，C ，D 四个模块中的不同模块构成。对于 项目中的共有模块，只需研发一次就可以为所有需要的项目服务. 各项目售价与模块构成及各模块研发成本如表1 、表2所示. 那么这家公司应选择承揽哪些项目才能使利润最大化? 试就这一问题建立相应的数学模型。
表1
相关内容
相关标签