2016年东南大学经济管理学院566运筹学考研复试题库
● 摘要
一、计算题
1． 己知有六台机床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。
2． 分析下列参数规划中当t 变化时最优解的变化情况。
（1）
（2）
（3）
（4）
【答案】 （1）在约束条件中分别加入松弛变量x 4，x 5，x 6，并将模型化为标准型为
令t=0，并利用单纯形法进行求解，如表所示。
表
所以，该线性规划问题的最优解为
映到最终表上，如表所示。
表
，将目标函数系数的变化直接反
当t≤1时，所有变量的检验数均不大于，最优解当t>1时，
程如表所示。
表 ； ，需进行进一步迭代，以x5为换出变量，x6为换入变量，进一步迭代过
相关内容
相关标签