階石法

運輸問題不僅是最優化模型中最為普遍的一類問題而且經常作為某些複雜最優化問題(如旅行商問題)的子問題出現，具有極其廣泛的應用。各類文獻上針對運輸問題的算法比較多，但是哪種方法對於運輸問題更有效還沒有定論。一般對同一個問題如果有多個算法可以解決時，偏向選擇執時間上界較小的算法。但是實踐中，很多情況下算法中基本操作重複執行的次數隨問題的輸入數據集不同而改變，使得在實用時需根據不同情況選擇適用的算法。算法主要有階石法與元素判別值分配法。 ^[1] 

階石法算法檢驗數的求解實現是基於行序為主序，通過對執行過程中一次循環時間與循環次數的分析表明，對於m×n= C常數的運輸問題，雖然問題中矩形的長寬比率P加大，使得決定哪一個非基變量進入基中所需時間增加而導致一次單純形迭代所需要的時間增加，但是因為在通常運輸密度條件下，矩形運輸問題所含的未知變量的個數比方型運輸問題少，所以迭代次數明顯減少，算法的執行時間減少。而對於常數的運輸問題，隨着問題中矩形的長寬比率P加大，一次單純形迭代中不僅決定哪一個非基變量要進入基中所需時間增加，而且由於矩形問題比方型問題含有更多的約束方程參數，所以基變量個數增加。則算法定義在基變量上的操作時間增加，使得算法中第三步到第六步的每一個循環時間顯著增加。雖然矩形運輸問題所含的未知變量的個數比方型運輸問題減少，但是不能補償一次循環時間增加而導致的算法整體執行時間增加量，所以階石法算法的執行時間增大。另外階石法實際上是一種特殊的單純形方法，所以從單純形方法的角度分析，在最壞情況下它時間複雜性可能達到指數級。 ^[2] 

按照自頂向下逐步求精的原則，在研究運算步驟時，首先考慮算法頂層的運算步驟，然後再考慮底層的運算步驟。頂層的運算步驟是指定義在數據模型級上的運算步驟，或者叫宏觀運算，它們組成算法的主幹部分。表達頂層運算步驟這部分算法的程序就是主程序，其中涉及的數據是數據模型中的一個變量，暫時不關心它的數據結構；涉及的運算以數據模型中的數據變量作為運算對象，或作為運算結果，或二者兼而有之。底層的運算步驟是指頂層抽象的運算的具體實現。它們依賴於數據模型的結構，是頂層運算的細化。頂層算法每個組成步驟可以看作是一個標準子程序模塊，每個子程序可以有多個不同的底層算法實現。 ^[2] 

用計算機解決一個確定的數學問題，需要設計問題求解的方法即算法設計。這一步要求建立問題的求解模型，確定問題的數據模型並在此模型上定義一組運算。接着藉助於對這組運算的調用和控制，形成算法並用自然語言來表述.然後將非形式自然語言標的算法轉變為一種程序設計語言表達的算法。一般來説，算法的執行效率受3個因素的制約：