2016年青岛科技大学数理学院运筹学(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、计算题
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． 某公司预计下3个月对某种产品的需要量分别为150件、250件和300件。下3个月各月生产能力和生产费用等有关数据如表所示。产品的存储费为20元/件。试回答如下问题:
表
（l ）将其看作运输问题，画出其网络图;
（2）建立使总费用最小的生产与存储方案的数学模型;
（3）写出该问题的运输问题调运表，并用最小元素法列出问题的初始基可行解。
【答案】（l ）看作运输问题时，其网络图见图:
图
（2）根据（l ）中的网络图，令产地i 的产量为a i ，销地j 的销量为b i ，产地i 到销地j 的运输量
为x ij 、单位运费为c ij ，由于该问题为产大于销的运输问题，于是可建立如下数学模型:
（3）该问题的运输问题调运表为
表
由于该问题为产大于销的运输问题，所以增加一个虚拟的销地4，其销量为130，各产地到宝抓氰返的单位运价为0。得到产销平衡表为:
表
用最小元素法列出问题的初始基可行解为:
表