線性規畫
linear programming


　　一種製作數學模型的方法，適用於商業計畫和工業管理領域內有關定量的管理決策(也用於社會科學和一般科學)。線性規畫雖然起源於近代，但已迅速地變成應用數學的一個重要部分。1930年代末，坎托羅維奇(Leonid Kantorovich)和列昂捷夫(Wassily Leontief)分別第一次認真地嘗試把線性規畫的方法運用到制定生產計畫表和經濟學領域，但是他們的工作大都被忽視了。第二次世界大戰期間，線性規畫曾被軍用企業和其他為戰爭服務的企業廣泛地使用於各種問題，例如處理運輸問題，受一定限制(如裝運費用和可用性的限制)的物資的計畫和分配問題。這種廣泛的應用鼓勵了人們接受這個方法。線性規畫由於1947年丹齊克(G. Dantzig)引入單純形方法而獲得進一步的推動力，這個方法大大簡化了求解線性規畫問題的手續，並且引起了對它的廣泛的興趣。



　　線性規畫的方法是在物資分配和各種類型的計畫表的領域裡作出管理決策的一種重要工具。經理用線性規畫的工具代替必須進行反覆試驗以作出定量決策的方式，它迅速而準確地給予他的許多問題以最優答案。下面的問題說明了用反覆試驗的方式可能遭遇到的困難。一個經理必須分配70個人去做70件不同的工作，每個人對於一個特定的工作有不同的效率。為了達到最大的綜合效率，應當如何分配?這裡有70!種不同的分配方法，而70!比10100大，所以這個經理即使藉助於計算機來探討全部可能性，所需要的時間也會比他本人的壽命還長。



　　下面是可以按照線性規畫方法處理的問題的幾個簡化例子。



　　1.運輸問題︰3個工廠生產輪胎，每個工廠具有不同的生產能力；這些輪胎要運到4個車間裝配到汽車上，這些車間對於輪胎有不同的需要；從每個工廠到每個車間的運輸輪胎的費用是不同的。現在要找出每個工廠生產輪胎的數量和運到每個車間的輪胎的數量，使得生產能力得到合理使用，裝配要求得到滿足，而總的運輸費用最小。



　　2.生產計畫表︰工廠有3個車間，每個車間有不同的生產能力，生產5種不同類型的產品，產生不同的利潤；但是可得到的人力、物力是有限制的，生產這些產品所需要的原材料的數量也是有限制的。問題是應當如何分配工廠的物力、原材料和人力，使得生產的利潤最大?



　　3.網絡流問題︰兩個城市被公路網連接著，就交通和旅行費用來說，每條公路有不同的運輸能力，又可能有幾種不同的運輸方案把一批貨物從一個城市運送到另一個。問題是應當沿著幾條路線中的哪一條運送這批貨物，將使得費用最省或者旅行時間最短?



　　上面的每個問題，當陳述成數學形式時，都導致如下的問題︰要求找到稱為目標函數的線性表達式f＝c1x1＋…＋cnxn。在下述稱為約束條件的線性不等式的限制下所可能有的最優值(最大值或最小值視問題而定): a11x1＋…＋am1xm≦b1,………………………a1nx1＋…＋amnxm≦bn,xi≧0其中ai、bi、ci是由能力、需要、費用、利潤和其他要求以及問題的約束條件所決定的常數。



　　應用這個方法的基本假設是，在要求與可用性之間的各種關係都能夠用線性的術語表達。目標函數代表要最優化的量(極大或極小)；約束條件表示各種限制或要求；不等式和變量的數目依賴於問題的複雜性。為了得到這個問題的解，必須找到有關的線性方程組的解，然後在一定數目的頂點上求目標函數的值，從而確定目標函數的最大或最小值。在實際情形中，方程和變量的數目都可能很大，從而解聯立線性方程組的過程可能很長，即使用計算機也很費時間。直到1947年，才由丹齊克引進一種有效的新方法，它已被稱為關於求線性規畫問題的最優解的單純形方法。這個方法已經被改進並且一直是解線性規畫問題的基本方法。線性規畫方法的成功促進了人們發展各種方法去處理某些用線性規畫不易處理的最優化問題，這些方法是︰整數規畫、動態規畫、非線性規畫和不定性規畫。