2017年沈阳师范大学数学与系统科学学院849线性规划考研导师圈点必考题汇编
● 摘要
一、计算题
1． 图所示的4座城市及其公路的连线情况，线上数字是两相邻城市每小时最多可能通过的车辆，试求从互一城市到第四城市的最大流量及安排。
数（以 1000辆为1个计量单位）
图
【答案】由图可知，城市1到城市4有3条路径。
最大流量为6000辆。
最大流量为2000辆。
最大流量为2000辆。
，由于在（2）（3）路径上，它们在③~④的最大流量和为14000辆，小于16000辆，故可行。故从第一城市到第四城市的最大流量为6000+2000+16000=24000辆，具体安排如路径（l ）（2）（3）所示。
2． 某科学试验可用l#、2#，3#三套不同仪器中的任一套去完成。每做完一次试验后，如果下次仍用原来的 仪器，则需要对该仪器进行检查整修而中断试验:如果下次换用另外一套仪器，则需拆装仪器，也要中断试验。 假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪器换下来隔一次再重新使用时，不会由于整修而 影响试验。设i#仪器换成j#仪器所需中断试验的时间为t ij ，如表所示。现要做4次试验，问应如何安排使用 仪器的顺序，使总的中断试验的时间最小?
表
【答案】设A 、B 、c 分别代表三套仪器l#、2#，3#，A i 表示在第i 次实验中用仪器A ，依此类推B i 、C i ，并设虚拟开始S 和结束点D 。则得如图所示网络图:
图
求总的中断试验的时间最小，即找最短路问题，利用Dijkstra 算法计算如下:
到S 点距离相同，
则
可同时标号
（4）
（5）比较
可得出，
最小，逆序追踪得使总的中断试验的时间最小
的使用顺序是:
3． 设有三个电视机厂生产同一种彩色电视机，日生产能力分别是:50，60，50（台），供应三个，从各分厂运往个门市部的单位运费如表所示，试安门市部，日销售量分别是:60，40，60（台）
排一个运费最低的运输计划。 若工厂1到门市部1的运价由9减为6，试寻求最优运输计划。
表
【答案】（l ）此问题是运输平衡问题。 第一步，用伏格尔法寻找得到初始基可行答:
表
第二步，用位势法计算各空格处的检验数为:
表
从所有非基变量的检验数可以看出都是非负数，其中存在一个0的检验数，说明该题有多重最优解。
（2）若工厂1到门市部1的运价由9减到6时，代入计算得第一步，用伏格尔法寻找得到初始基可行
表
第二步，用位势法计算各空格处的检验数为:
表
相关内容
相关标签