線性多貨品問題的並行計算

Abstract

線性多貨品問題是一個求解最佳化的問題，它應用在許多方面，例如電子綱路，都市 的交通系統，鐵路系統等等。而在實際上，這種問題的行列常是數以千計，因此如何 在一個合理可以被接受的時間內求得解答是一個相當重要的問題。這個問題本身具有 一個特殊的特性叫block-angular 結構，我們可以利用Dantzig-Wolfe 所提出的分解 法則對這種結構加以平行處理來求得解答。但是這個分解法則如果被製作在不同架構 的多處理機的機器上，那我們所得到的效益也會有所不同。本論文則是製作在屬於Ti ghtly coupled system架構的Sequent 上所得到的結果，我們也將此結果和製作在Tr ansputer (屬於Loosely coupled system架構) 上所得到的結果加以討論並比較他們 的優缺點。我們不止報告了我們的結果，同時也提出了我們經驗給做更進一步研究的 人。