規劃論

規劃論

規劃論是運籌學的一個分支。研究對現有資源進行統一分配、合理安排、合理調度和最優設計以取得最大經濟效果的數學理論方法。如某項確定的任務,怎樣以最少的人力、物力去完成; 或是對給定的人力、物力要求能最大限度地發揮作用從而能夠完成儘可能多的任務。一般地可以歸結為:在滿足既定目標的要求下,按照某一衡量指標尋求最優方案的問題。將必須滿足的既定目標的要求稱為約束條件,將衡量指標稱為目標函式,用數學語言來描述即為: 求目標函式在一定約束條件下的極值問題。

基本介紹

  • 中文名:規劃論
  • 外文名:programming theory
  • 又稱:數學規劃
  • 分類:線性 非線性等
  • 套用:經濟管理、工程設計和過程控制
簡介,線性規劃,起源,基礎理論,套用,非線性規劃,起源,算法,學科發展,

簡介

規劃論又稱“數學規劃”。運籌學的一個分支。研究在所給定的條件下,如何按某一衡量指標來尋求計畫管理工作中的最優方案。通常稱必須滿足的條件為“約束條件”,衡量指標為“目標函式”。包括線性規劃、非線性規劃、整數規劃、動態規劃、組合規劃、隨機規劃、多目標規劃等。在經濟管理、工程設計和過程控制等方面有廣泛套用。
如今,最簡單的規劃論技巧即線性規劃已被列入高中數學教材,其實教材當中也包括了部分非線性規劃的因素,教會學生用直觀的方法給出問題的最優解。這種思想在物理學裡也經常用到,在那裡常被稱為“圖解法”。這種思想重在分析,通過分析來減少運算量,較列出函式關係求極值的方法要更高明,是一種很有用的思想。

線性規劃

起源

研究線性規劃最早的是蘇聯的康脫洛維奇,1939年,他發表了《生產組織與計畫中的數學方法》一書。主要討論了工具機、負荷、下料運輸等問題。但他提出的問題在當時並未引起人們的注意。他自己也未能提出一個統一的求解方法。在第二次世界大戰期間,由於軍事運輸的需要,提出線性問題的解法,美國的經濟學家柯普曼(Koupman)也研究了運輸問題。直到1947年,美國的G.B.Dantzig提出了求解線性規劃的單純形法,才使線性規劃這門學科在理論上趨於成熟,並成功地運用到了工業、交通、農業、軍事等各個領域內,使線性規劃的理論與方法成為管理科學的重要內容。在當今電子技術高度發展的信息社會中,線性規劃給人類在經濟管理、生產管理、人才事務管理等方面發揮了巨大作用。現在對於成千上萬個約束條件、成千上萬個變數的線性規劃問題在計算上已沒有任何問題。據20世紀80年代末美國一個雜誌對全美500家大公司的調查,線性規劃的套用範圍名列前茅,有85%的公司頻繁使用線性規劃。

基礎理論

線性規劃問題是在一組線性約束條件的限制下,求一線性目標函式最大或最小的問題。 在解決實際問題時,把問題歸結成一個線性規劃數學模型是很重要的一步,但往往 也是困難的一步,模型建立得是否恰當,直接影響到求解。而選適當的決策變數,是我 們建立有效模型的關鍵之一。 建立數學模型的步驟:
(1)分析實際問題;(2)確定決策變數;(3)找出約束條件;(4)確定目標函式;(5)整理寫出數學模型。

套用

線性規劃主要套用在以下幾個方面:
(1)在某一企業內部,如何配合產品的銷售時間,在各部門的原料,產品的存儲,分配的數量等最為合理。
(2)在某一企業生產的產品數量(或產值),如何使現有的設備,人力,原料等條件限制下,合理組織生產,使經濟效益最高。
(3)在某地的交通網中,如何合理組織運輸,使運費最小。
(4)在市場上產品的(或原料)價格變動時,對於這些變動,企業如何做出最優決策。
(5)合理下料問題,即利用某種原料下料時,如何達到既滿足要求,又使原料最少。
(6)配料問題,即生產由各種原料生產的的產品時(如混合飼料等)時,如何既滿足規定的質量的標準,又使產品的成本最低。
(7)庫存問題,在倉庫的容量及其他條件的限制下,確定庫存物資的品種,數量,期限,使庫存的效益最高。
(8)在投入產出問題中,引進某一目標函式,制定最優的企業(或地區)經濟計畫。

非線性規劃

起源

非線性規劃是具有非線性約束條件或目標函式的數學規劃,是運籌學的一個重要分支。非線性規劃是20世紀50年代才開始形成的一門新興學科。70年代又得到進一步的發展。非線性規劃在工程、管理、經濟、科研、軍事等方面都有廣泛的套用,為最優設計提供了有力的工具。非線性規劃研究一個 n元實函式在一組等式或不等式的約束條件下的極值問題,且目標函式和約束條件至少有一個是未知量的非線性函式。
非線性規劃是20世紀50年代才開始形成的一門新興學科。1951年H.W.庫恩和A.W.塔克發表的關於最優性條件(後來稱為庫恩-塔克條件)的論文是非線性規劃正式誕生的一個重要標誌。在50年代還得出了可分離規劃和二次規劃的n種解法,它們大都是以G.B.丹齊克提出的解線性規劃的單純形法為基礎的。50年代末到60年代末出現了許多解非線性規劃問題的有效的算法,70年代又得到進一步的發展。非線性規劃在工程、管理、經濟、科研、軍事等方面都有廣泛的套用,為最優設計提供了有力的工具。20世紀80年代以來,隨著計算機技術的快速發展,非線性規劃方法取得了長足進步,在信賴域法、稀疏擬牛頓法、並行計算、內點法和有限存儲法等領域取得了豐碩的成果。

算法

對於一個實際問題,在把它歸結成非線性規劃問題時,一般要注意如下幾點:
(i)確定供選方案:首先要收集同問題有關的資料和數據,在全面熟悉問題的基礎上,確認什麼是問題的可供選擇的方案,並用一組變數來表示它們。
(ii)提出追求目標:經過資料分析,根據實際需要和可能,提出要追求極小化或極大化的目標。並且,運用各種科學和技術原理,把它表示成數學關係式。
(iii)給出價值標準:在提出要追求的目標之後,要確立所考慮目標的“好”或 “壞”的價值標準,並用某種數量形式來描述它。
(iv)尋求限制條件:由於所追求的目標一般都要在一定的條件下取得極小化或極大化效果,因此還需要尋找出問題的所有限制條件,這些條件通常用變數之間的一些不等式或等式來表示。

學科發展

數學規劃問題是指在一定約束條件下最大化或最小化某一目標函式的問題,其變數可能是連續或離散的.研究這類問題的數學性質、求解算法和具體實現以及套用這些算法解決實際問題的學科統稱為數學規劃。數學規劃的一個“近似”或通俗的名字是“最最佳化”。
數學規劃問題求解“最優”的特徵決定了其套用的廣泛性。早在18世紀,著名數學家歐拉就曾說:宇宙萬物無不與最小化或最大化的原理有關係。經濟社會中,在有限的資源下求解最優的計畫、路線、組合和策略等問題都可以歸結為數學規劃問題。數學規劃的套用遍及工程、經濟、金融、管理、醫藥和軍事等領域。可以說,數學規劃的原理滲入到社會發展的各個方面,甚至在我們的日常生活里也有各種各樣的最最佳化問題。
在學科分類上,一般把數學規劃看成是運籌學的一個分支,是運籌學的基礎學科。在管理科學中,數學規劃是最常用的建模方法和工具,與統計和模擬仿真一起組成三大基本方法和技術。由於數學規劃與數學理論的天然聯繫,也可以把數學規劃看成是套用數學的一個分支。在國際上,數學規劃的研究活動分布在運籌學、管理科學、套用數學、計算機科學和電子工程等領域。在一些國際大型學術組織中,如美國運籌與管理科學學會(INFORMS)、國際運籌學會聯合會(IFORS)、歐洲運籌學會(EURO)、美國工業與套用數學聯盟(SIAM)和美國計算機科學學會(ACM)等,數學規劃都是非常活躍的研究方向和分支。

相關詞條

熱門詞條

聯絡我們