2016年南昌航空大学数学与信息科学学院综合试卷之运筹学复试笔试仿真模拟题
● 摘要
一、计算题
1． 用图解法求解下列线性规划，并指出该问题所有基可行解在图中的位置。
【答案】如图所示可得阴影部分即为可行域，且可知在A （2，2）处取得最小值18。
，，基可行解有3个，分别是（6，0）（2，2）（0，6）
2． 图中V s 表示仓库，V t 表示商店. 现要从仓库运10单位的物资到商店，应如何调运才能使运费，其中C ij ，表示交通线上运输能力限制，b ij 最省（图 中弧表示交通线，弧旁的数字为（C ij ，b ij ）表示单位运价）。
图
【答案】（l ）从f （）={0}开始，做L （f （））如图1，用Dijkastra 算法求得L （f （））网络中最短
第 2 页，共 60 页
路为整，结果见
，在网络中相应的可增广链，如图2所示:
上用最大流算法进行流的调
图
1
图2
（2）作
（2），
如图1，找出最短路为，在网络内相应的可增广链上进行调整，得到流f
如图2所示:
图1
第 3 页，共 60 页
图2
（3）作得到 流
与如图1，找出最短路为，如图2所示
，在网络内相应的可增广链上进行调整，
图
1
图
2
即为所求的最小费用流。
第 4 页，共 60 页
相关内容
相关标签