例某公司承担4条航线的运输任务，假设所有航线都 使用同一种船只，已知各条航线的起点城市和终点 城市及每天的航班数如表1所示，各城市间的航行时 间如表2所示，船只在运行过程中每次装船及卸船时 间均为1天.问该公司至少应配备多少条船才能满足 有航线运输的需求？ 表2各城市间的航行时间 每天 至 D E 航线 起点 终点 城市 城市 航班 从 B 数 A 0 1 2 14 7 7 1 E D 3 B 0 13 8 8 B C 2 24 3 30 150 5 5 3 A F 1 13 17 20 4 D B E 7 8 5 0 3 8 5 20 3
1 例 某公司承担4条航线的运输任务，假设所有航线都 使用同一种船只，已知各条航线的起点城市和终点 城市及每天的航班数如表1所示，各城市间的航行时 间如表2所示，船只在运行过程中每次装船及卸船时 间均为1天. 问该公司至少应配备多少条船才能满足 所表有1 航线运输的需求？ 航线 起点 城市 终点 城市 每天 航班 数 1 2 3 4 E B A D D C F B 3 2 1 1 表2 各城市间的航行时间 至 从 A B C D E F A B C D E F 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0
解该公司所需船只可分为两部分： (1)各航线载货船只航行、装船、卸船所占用的船只，例 如航线1，在港口E装货1天，在E,D间航行17天，在D御货1天 ,总计19天，每天3个航班，故该航线需要载货船只数57.对 其它航线逐一分析，所需船只列入表3中，将各航线所需船只 数相加，累计共需91条船 表3各航线航行、装船、卸船所占用的船只 航线 装船天数 卸船天数 航行天数 小计 航班数 所需船只 1 1 1 17 19 5 23 1 1 37 4 1 111 13 595 321 10 1 915 2
2 解 该公司所需船只可分为两部分： （1）各航线载货船只航行、装船、卸船所占用的船只，例 如航线1，在港口E装货1天，在E,D间航行17天，在D卸货1天 ，总计19天，每天3个航班，故该航线需要载货船只数57. 对 其它航线逐一分析，所需船只列入表3中，将各航线所需船只 数相加，累计共需91条船. 表3各航线航行、装船、卸船所占用的船只 航线 装船天数 卸船天数 航行天数 小计 航班数 所需船只 1 2 3 4 1 1 1 1 1 1 1 1 17 3 7 13 19 5 9 15 3 2 1 1 57 10 9 15
(2)各港口之间调度所需船只数.这由每天到达某一港口的船 只数与它所需发出的船只数不相等而产生的，例如城市A每天 没有到达的船只，但却需要1艘船发出，因而差额数为-1.对其 它港口进行类似分析，各港口每天到达船只数、需求船只数及 其差额数如表4所示」 表4各港口每天到达船只数、需求船只数及其差额 城市 A B C D E F 每天到达 0 1 2 3 0 1 每天需要 1 2 0 1 3 0 差额数 -1 -1 2 2 3 1 将船由多余船只的港口C,D,F调往需用船只的港口A,B,E为空 驶行使，应采用合理的调度方案，使周转的空船数最少.为此 建立表5所示的运输问题，其单位运价取为相应一对港口城市 之间的航行时间（天数）
3 （2）各港口之间调度所需船只数. 这由每天到达某一港口的船 只数与它所需发出的船只数不相等而产生的，例如城市A每天 没有到达的船只，但却需要1艘船发出，因而差额数为-1. 对其 它港口进行类似分析，各港口每天到达船只数、需求船只数及 其差额数如表4所示. 表4 各港口每天到达船只数、需求船只数及其差额 城市 A B C D E F 每天到达 每天需要 差额数 0 1 -1 1 2 -1 2 0 2 3 1 2 0 3 -3 1 0 1 将船由多余船只的港口C,D,F调往需用船只的港口A,B,E为空 驶行使，应采用合理的调度方案，使周转的空船数最少. 为此 建立表5所示的运输问题，其单位运价取为相应一对港口城市 之间的航行时间（天数）
表5 至 从 A B E 多余船只数 2 3 5 2 14 13 17 D 2 7 8 3 F 缺少船只数 3 用表上作业法求解该运输问题可得两个最优解，如表6 所示（括号中为另一个最优方案），按这两个方案调运 多余船只，其目标函数值等于40，说明各港口之间的调 度所需船只至少为40艘
4 表5 至 从 A B E 多余船只数 C 2 3 5 2 D 14 13 17 2 F 7 8 3 1 缺少船只数 1 1 3 用表上作业法求解该运输问题可得两个最优解，如表6 所示（括号中为另一个最优方案），按这两个方案调运 多余船只，其目标函数值等于40，说明各港口之间的调 度所需船只至少为40艘
表6最优调运方案 至 A B E 多余船只数 2 3 5 C (1) 2(1) 2 14 13 17 D 1 1(1) (1) 2 7 8 3 F 1(1) 缺少船只数 1 3 综合以上两部分的要求，在不考虑维修、储备等情况下，该 公司至少需配备131条船只，才能满足4条航线正常运输的需 要
5 表6 最优调运方案 至 从 A B E 多余船只数 C （1） 2 3 2（1） 5 2 D 1 14 1（1） 13 （1） 17 2 F 7 8 1（1） 3 1 缺少船只数 1 1 3 综合以上两部分的要求，在不考虑维修、储备等情况下，该 公司至少需配备131条船只，才能满足4条航线正常运输的需 要