圆通快递成都分公司难题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,圆通快递成都分公司难题,圆通快递成都分最近拓展了到北京的业务，全部采用航空路线（由于路线很多）各办事处将其已目前还能走的吨位的情况传到了成都分公司。根据此资料，成都公司要作出计划，最多能将多少快递物资从成都送往北京以及如何取道转机。下面是各地分公司还剩余的航空吨位的详细情况表：,成都,重庆,武汉,上海,西安,郑州,沈阳,昆明,广州,北京,成都,10,5,15,8,12,10,30,重庆,5,6,15,25,武汉,10,上海,15,8,西安,8,6,郑州,14,8,沈阳,18,昆明,8,10,广州,8,2,6,10,用图来描述就是,成,重,武,昆,上,广,西,郑,沈,京,8,5,10,15,8,12,10,30,5,6,15,25,10,15,8,8,6,14,18,8,10,8,2,6,10,发点,v,s,=,成都，收点,v,t,=,北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。,利用标号法（经,5,次迭代）可以得到从成都发送旅客到北京的最大流量如图所示,重,武,昆,上,广,西,郑,沈,京,成,30,10,0,6,12,2,8,0,12,5,10,6,10,10,6,0,0,0,10,8,0,18,10,10,0,