大型規劃

包括大型線性規劃和大型非線性規劃。數學規劃得到廣泛應用的，主要原因是存在求解大型問題的有效的計算機程序。求解大型問題的關鍵是利用問題的特殊結構。大型線性規劃問題的約束矩陣一般都十分稀疏（即大多數元素是零），且非零元素按一定次序排列，例如，除少數的行和列外，均沿主對角線排列。大型非線性規劃一般也是稀疏結構，且線性項的比例很高，非線性項也有特殊結構，如可分結構等。

大型線性規劃求解大型線性規劃問題的方法可分為兩類：直接法和分解法。直接法是用一個現存的算法來求解一類特定的問題。大型線性規劃問題多采用直接法求解，基本工具是改進單純形法，主要計算問題是求逆程序。在特殊的矩陣結構下只需要存儲一個約化矩陣。實用計算機程序能有效地求解 8000～16000行的大型線性規劃問題。若模型具有廣義上界結構，可用廣義上界算法GUB求解規模更大的問題。

分解法又稱分塊法，它的主導思想是把原系統分成若干獨立的子系統求解，再用適當的方法來考慮各子系統之間的影響。1970年美國數學家M.D.梅薩羅維茨提出分解－協調算法。這種算法的設計思想來自大系統的多級遞階控制結構。首先把原問題分解成若干相對獨立的子問題，稱為一級子問題，分別求解，然後再用適當的方法定義一個或若干個二級子問題，來協調一級子問題之間的相互影響，以得到原問題的解。60年代中期曾廣泛流行過的丹齊克－沃爾夫分解算法，現在只有少量商業上的應用。其主要原因是這種算法在計算上存在不穩定性和計算機程序的複雜性。

大型非線性規劃求解大型非線性規劃的方法有兩類：可分規劃和近似規劃。可分規劃的特點是任一非線性函數都是可分的，即

式中Δy =y-y0，而墷gi是gi的梯度向量。用此線性化函數代替每個gi，就把原問題約化為線性規劃問題。規定Δy的上界和下界，即－ε≤Δy≤ε，求解此線性規劃，得到Δy，把它加到y0上得到新的基點,計算對應的梯度向量墷gi，必要時可減小ε,然後重複上述過程。現在已有近似規劃的通用程序和專用程序。

大型網絡流問題利用線性規劃基變量的樹結構，可用單純形法求解有數十萬個節點或弧的網絡問題。其解法比最有效的網絡算法更快。