以时間为标准解运輸問題

編制运輸計划时,实际上在許多重要場合下,极其需要节省时間。例如,在运輸易腐烂的食品时,必須以尽可能最少的时間,把它們送到被指定的地点。时間也是谷物收获运动中很重要的因素,必須最快地把谷物送到貯备处。这种問題就是以时間为标准的运輸問題。下面研究解以时間为标准的运輸問題的某些算法中的一个。問題的提出与解决。 設有m个同类貨物的发点和n个收点。用a_1,a_2,…,a_i,…,a_m分别表示第一个,第二个,…,第i个,…,第m个发点的貨物量,而用b_1,b_2,…,b_j,…,b_n分别表示应当运到第一个,…,第j个,…,第n个收点的貨物量。设t_(ij)是把貨物从第i个发点运到第j个收点的时間(天,小时),而x_(ij)表示我們計划从第i个发点运往第j个收点的貨物量。要求寻找最优运輸計划,也就是找一組非負数x~(ij),使得把一切貨物运到收点所必須的时間是最少的。