您的瀏覽器不支援javascript 跳到主要內容
::: 線性規畫 - 教育百科

詞條名稱:線性規畫

開啟關聯 收藏

國家教育研究院辭書
基本資料
英文: Linear Programming,簡稱LP
作者: 彭慰
日期: 1995年12月
出處: 圖書館學與資訊科學大辭典
辭書內容
名詞解釋:
  線性規畫是作業研究(Operations Research,簡稱OR)中最有效而通用的工具,其應用之廣泛與普遍為其他作業研究模型所不及。一般應用線性規畫的問題,是如何利用有限的資源(人、財、物),做最有效的調配與應用,以求得最大利潤;或是如何滿足特定的需求,以求成本最小。這種求解的技巧即是線性規畫,用以解決限制式最佳化的問題。
  線性規畫最初起源於1920年代,當時經濟學家里昂提夫(Leontief)的投入--產出分析法,已具有線性規畫的雛形。在1941年及1942年,希區考克(Hitchcock)與肯托諾夫(Kantorovitch)分別用在運輸問題求解,後來有人曾用線性規畫解最經濟營養問題,但都未能將之整理為有系統的理論。直到1947年,美國空軍作業研究小組,研究空軍調配問題,數學家丹企(George Dantzig)教授才研究出線性規畫的一般型式,並且設計出簡算法(Simplex Method)為線性規畫模型的求解程序。故後人稱丹企為「線性規畫之父」。三十多年來線性規畫已奠立了理論基礎,並為工商企業所重用,圖書館管理亦運用於館舍規畫、交通運輸及人力運用。
  線性規畫包括一系列獲致問題最佳解答的步驟。有許多種不同線性規畫的技巧,有些是針對特定目的發展出來的(如求出特定類型問題之解答),而其他的則更適用於一般問題。線性規畫模型沒有包含機率變數,是確定性模型,其模型有一套方法求最佳方案,故亦為分析模型,該方法(簡算法)是選擇決策變數(可控制變數)的值,滿足限制條件,達到最佳目標涵數值。線性規畫模型的使用,有助於生產管理者在許多不同場合下作決策。包括稀有資源的調配、工作指派的問題、運輸問題(從多個起點站運貨至多個終點站的配銷計畫)、混合問題(石油製品、營養食譜)、投資問題、行銷問題(廣告額)、裝載問題(不同物品裝到貨船或倉庫的裝載計畫)以及水資源、工廠位置、學校交通車、天氣預測等問題皆可用線性規畫求得其數學模型之最佳解答。線性規畫模型是線性規畫問題之數學表示,其組成包含4種成分:一為目標,二為決策變數,三為限制式,四為參數。線性規畫演算法必須具有單一目標如利潤極大化,或成本極小化,每單位投入或產出的成本、利潤等等以目標函數表示之。決策變數代表可供決策者選擇的變數,通常是以投入或產出表示。限制式包括3種:小於或等於(≦),大於或等於(≧),及等於(=)。線性規畫模型由目標數學式與限制式數學式所組合而成,這些數學式係由代表決策變數與數值(稱為參數)的符號所組合而成。參數為固定值,已知其固定值,求解線性規畫模型。線性規畫一般用之2種求解技巧模型為圖解式線性規畫與簡算法。前者用於求解2個變數的問題,而簡算法可以處理2個以上變數的問題,在解決實際問題時較有用。有關線性規畫之模型請參考管理科學、生產管理--作業研究方面之專著,茲舉其中一例供參考:
資料來源: 國家教育研究院_線性規畫
授權資訊: 資料採「 創用CC-姓名標示- 禁止改作 臺灣3.0版授權條款」釋出