【線性規畫】

豐碩

【線性規畫】

 

LinearProgramming，簡稱LP

 

【辭書名稱】圖書館學與資訊科學大辭典

 

線性規畫是作業研究（OperationsResearch，簡稱OR）中最有效而通用的工具，其應用之廣泛與普遍為其他作業研究模型所不及。

 

一般應用線性規畫的問題，是如何利用有限的資源（人、財、物），做最有效的調配與應用，以求得最大利潤；

 

或是如何滿足特定的需求，以求成本最小。

 

這種求解的技巧即是線性規畫，用以解決限制式最佳化的問題。

 

線性規畫最初起源於1920年代，當時經濟學家里昂提夫(Leontief)的投入－－產出分析法，已具有線性規畫的雛形。

 

在1941年及1942年，希區考克(Hitchcock)與肯托諾夫(Kantorovitch)分別用在運輸問題求解，後來有人曾用線性規畫解最經濟營養問題，但都未能將之整理為有系統的理論。

 

直到1947年，美國空軍作業研究小組，研究空軍調配問題，數學家丹企(GeorgeDantzig)教授才研究出線性規畫的一般型式，並且設計出簡算法(SimplexMethod)為線性規畫模型的求解程序。

 

故後人稱丹企為「線性規畫之父」。

 

三十多年來線性規畫已奠立了理論基礎，並為工商企業所重用，圖書館管理亦運用於館舍規畫、交通運輸及人力運用。

 

線性規畫包括一系列獲致問題最佳解答的步驟。

 

有許多種不同線性規畫的技巧，有些是針對特定目的發展出來的（如求出特定類型問題之解答），而其他的則更適用於一般問題。

 

線性規畫模型沒有包含機率變數，是確定性模型，其模型有一套方法求最佳方案，故亦為分析模型，該方法（簡算法）是選擇決策變數（可控制變數）的值，滿足限制條件，達到最佳目標涵數值。

 

線性規畫模型的使用，有助於生產管理者在許多不同場合下作決策。

 

包括稀有資源的調配、工作指派的問題、運輸問題（從多個起點站運貨至多個終點站的配銷計畫）、混合問題（石油製品、營養食譜）、投資問題、行銷問題（廣告額）、裝載問題（不同物品裝到貨船或倉庫的裝載計畫）以及水資源、工廠位置、學校交通車、天氣預測等問題皆可用線性規畫求得其數學模型之最佳解答。

 

線性規畫模型是線性規畫問題之數學表示，其組成包含4種成分：一為目標，二為決策變數，三為限制式，四為參數。

 

線性規畫演算法必須具有單一目標如利潤極大化，或成本極小化，每單位投入或產出的成本、利潤等等以目標函數表示之。

 

決策變數代表可供決策者選擇的變數，通常是以投入或產出表示。

 

限制式包括3種：小於或等於（≦），大於或等於（≧），及等於（＝）。

 

線性規畫模型由目標數學式與限制式數學式所組合而成，這些數學式係由代表決策變數與數值（稱為參數）的符號所組合而成。

 

參數為固定值，已知其固定值，求解線性規畫模型。

 

線性規畫一般用之2種求解技巧模型為圖解式線性規畫與簡算法。

 

前者用於求解2個變數的問題，而簡算法可以處理2個以上變數的問題，在解決實際問題時較有用。

 

有關線性規畫之模型請參考管理科學、生產管理－－作業研究方面之專著，茲舉其中一例供參考： 

轉自:http://edic.nict.gov.tw/cgi-bin/tudic/gsweb.cgi?o=ddictionary