- 相關推薦
單純形解線性規劃問題及其編程實現
目 錄
摘要 1
前言 2
1 線性規劃問題及其數學模型 3
1.1 問題提出 3
1.2 模型建立 3
1.3 線性規劃模型的幾種形式 4
1.3.1 1般形式 4
1.3.2 標準形式 4
1.3.3 1般形式化標準形式 5
2 線性規劃問題解的概念 7
3 單純形法解線性規劃問題 8
3.1 單純形法的基本思路 8
3.2 普通單純形法原理 8
3.3 單純形表 9
3.4 單純形法的進1步討論——大M法 12
3.5 單純形法的程序實現 14
3.5.1 算法描述 14
3.5.2 程序實現 15
4 結論 17
參考文獻 18
致謝 19
附錄 20
摘 要
線性規劃是運籌學中數學規劃的基礎部分，是運籌學中興起較早并且應用廣泛的1個部分。事實上，線性規劃就是用數學為工具，來研究1定條件下，如何實現目標最優化。本文以經濟生活中1個常見的實例為依據，建立線性規劃模型，通過引入普通單純形法，依次迭代并判斷，逐步逼近，最后得到最優解。然后，介紹了求解1般線性規劃問題的大M單純形法（簡稱大M法），并舉1例說明大M法的基本思路：通過添加人工變量使得標準化后的系數矩陣1定含有單位矩陣，從而得到1組基變量和初始基本可行解。由于人工變量是人為添加的，為了不改變原問題，在目標函數中消去人工變量，并將人工變量由初始的基變量化成非基變量，使之取值為0，然后用普通單純形法求解。最后，本文還實現了用大M單純形法的程序解線性規劃問題。
關鍵字：線性規劃；單純形法；大M法。
Abstract
The Linear programming is a fundamental part of mathematical programming in the Operations research . It is also an early-emerging and an extensively-applied part in the Operations research . In fact , the Linear programming uses mathematics as the tool and studies how to achieve the goal optimization under certain conditions . This paper took a common example in economic life as the basis , and established a linear programming model , through introducing the Ordinary Simplex Method , iterated and judged in turn , then approached gradually and at last got the optimal solution . Later , this article illustrated the Big M simplex method ( the i.e. Big M method ), which could solve the general linear programming problems and developed simultaneously an example to explain the basic mentality of the Big M method . Then , the essay added some artificial variables in order that the standardized coefficient matrix include a unitary matrix from which a group of base variables and the initial basic feasible solution could be obtained very easily . Because the artificial variables was the artificial addendum , in order not to change the original question , this paper eliminated the artificial variables in the objective function , and turned the artificial variables from the initial base variables to the non-base variables whose value is zero , then , use the Ordinary simplex method to get the solution . Finally , this article realized to solve the linear programming problems in the procedure of the Big M simplex method .
Keywords ：Linear Programming ; Simplex method ; Big M method .
前言
20世紀30年代末，蘇聯數學家康特羅維奇研究交通運輸及機械加工等部門的生產管理工作，于1939年寫了《生產組織與計劃中的數學方法》1書初稿，為線性規劃建立數學模型及解法奠定基礎,自此開始，線性規劃經過不斷的應用和發展，在工業、農業生產管理，交通運輸的指揮調度，資源開發，商業和銀行等領域得到廣泛應用，顯著提高了企業的經濟效益。隨著生產規模的擴大和經濟事務變得日益繁雜，對線性規劃提出了更多的理論要求，又促使這門學科迅速發展和完善。線性規劃不斷發展，適用領域不斷拓寬，從解決技術問題的最優化設計，到工業、農業、商業、交通運輸業、軍事、經濟計劃及管理等領域都發生著作用，已成為現代科學管理的重要基礎理論。
例如，在生產管理和經濟活動中，經常遇到這些問題，如生產計劃問題，即如何合理利用有限的人、財、物等資源，以便得到最好的經濟效果；材料利用問題，即如何下料使用材最少；配料問題，即在原料供應量的限制下如何獲取最大利潤；勞動力安排問題，即如何用最少的勞動力來滿足工作的需要；運輸問題，即如何制定調運方案，使總運費最小；投資問題，即從投資項目中選取方案，使投資回報最大等等。對于這些問題，都能建立相應的線性規劃模型。事實上，線性規劃就是利用數學為工具，來研究在1定條件下，如何實現目標最優化。
解線性規劃問題目前最常見的方法有兩種，圖解法和單純形法。然而，由于圖解法不適用于求解大規模的線性規劃問題，其實用意義不大。在電子計算機高速發展的今天，我們希望找到更適用和更快捷的解決線性規劃問題的途徑，并用計算機來實現。這就是本文要解決的課題。
【單純形解線性規劃問題及其編程實現】相關文章：
W78E516及其在系統編程的實現03-18
JTAG口及其對Flash的在線編程03-19
常微分方程初值問題數值解的可視化實現03-07
以根的分布為題設的線性規劃問題03-01
V-BLAST的實現及其檢測03-07
多種數制顯示的匯編語言編程實現03-19
地鐵控制基標歸化改正原理及編程實現03-19
多制式語音編碼及其DSP實現03-18