- 相關推薦
單純形解線性規(guī)劃問題及其編程實現(xiàn)
目 錄
摘要 1
前言 2
1 線性規(guī)劃問題及其數(shù)學模型 3
1.1 問題提出 3
1.2 模型建立 3
1.3 線性規(guī)劃模型的幾種形式 4
1.3.1 1般形式 4
1.3.2 標準形式 4
1.3.3 1般形式化標準形式 5
2 線性規(guī)劃問題解的概念 7
3 單純形法解線性規(guī)劃問題 8
3.1 單純形法的基本思路 8
3.2 普通單純形法原理 8
3.3 單純形表 9
3.4 單純形法的進1步討論——大M法 12
3.5 單純形法的程序?qū)崿F(xiàn) 14
3.5.1 算法描述 14
3.5.2 程序?qū)崿F(xiàn) 15
4 結(jié)論 17
參考文獻 18
致謝 19
附錄 20
摘 要
線性規(guī)劃是運籌學中數(shù)學規(guī)劃的基礎部分，是運籌學中興起較早并且應用廣泛的1個部分。事實上，線性規(guī)劃就是用數(shù)學為工具，來研究1定條件下，如何實現(xiàn)目標最優(yōu)化。本文以經(jīng)濟生活中1個常見的實例為依據(jù)，建立線性規(guī)劃模型，通過引入普通單純形法，依次迭代并判斷，逐步逼近，最后得到最優(yōu)解。然后，介紹了求解1般線性規(guī)劃問題的大M單純形法（簡稱大M法），并舉1例說明大M法的基本思路：通過添加人工變量使得標準化后的系數(shù)矩陣1定含有單位矩陣，從而得到1組基變量和初始基本可行解。由于人工變量是人為添加的，為了不改變原問題，在目標函數(shù)中消去人工變量，并將人工變量由初始的基變量化成非基變量，使之取值為0，然后用普通單純形法求解。最后，本文還實現(xiàn)了用大M單純形法的程序解線性規(guī)劃問題。
關鍵字：線性規(guī)劃；單純形法；大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年代末，蘇聯(lián)數(shù)學家康特羅維奇研究交通運輸及機械加工等部門的生產(chǎn)管理工作，于1939年寫了《生產(chǎn)組織與計劃中的數(shù)學方法》1書初稿，為線性規(guī)劃建立數(shù)學模型及解法奠定基礎,自此開始，線性規(guī)劃經(jīng)過不斷的應用和發(fā)展，在工業(yè)、農(nóng)業(yè)生產(chǎn)管理，交通運輸?shù)闹笓]調(diào)度，資源開發(fā)，商業(yè)和銀行等領域得到廣泛應用，顯著提高了企業(yè)的經(jīng)濟效益。隨著生產(chǎn)規(guī)模的擴大和經(jīng)濟事務變得日益繁雜，對線性規(guī)劃提出了更多的理論要求，又促使這門學科迅速發(fā)展和完善。線性規(guī)劃不斷發(fā)展，適用領域不斷拓寬，從解決技術問題的最優(yōu)化設計，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事、經(jīng)濟計劃及管理等領域都發(fā)生著作用，已成為現(xiàn)代科學管理的重要基礎理論。
例如，在生產(chǎn)管理和經(jīng)濟活動中，經(jīng)常遇到這些問題，如生產(chǎn)計劃問題，即如何合理利用有限的人、財、物等資源，以便得到最好的經(jīng)濟效果；材料利用問題，即如何下料使用材最少；配料問題，即在原料供應量的限制下如何獲取最大利潤；勞動力安排問題，即如何用最少的勞動力來滿足工作的需要；運輸問題，即如何制定調(diào)運方案，使總運費最小；投資問題，即從投資項目中選取方案，使投資回報最大等等。對于這些問題，都能建立相應的線性規(guī)劃模型。事實上，線性規(guī)劃就是利用數(shù)學為工具，來研究在1定條件下，如何實現(xiàn)目標最優(yōu)化。
解線性規(guī)劃問題目前最常見的方法有兩種，圖解法和單純形法。然而，由于圖解法不適用于求解大規(guī)模的線性規(guī)劃問題，其實用意義不大。在電子計算機高速發(fā)展的今天，我們希望找到更適用和更快捷的解決線性規(guī)劃問題的途徑，并用計算機來實現(xiàn)。這就是本文要解決的課題。
【單純形解線性規(guī)劃問題及其編程實現(xiàn)】相關文章：
W78E516及其在系統(tǒng)編程的實現(xiàn)03-18
JTAG口及其對Flash的在線編程03-19
常微分方程初值問題數(shù)值解的可視化實現(xiàn)03-07
以根的分布為題設的線性規(guī)劃問題03-01
V-BLAST的實現(xiàn)及其檢測03-07
多種數(shù)制顯示的匯編語言編程實現(xiàn)03-19
多制式語音編碼及其DSP實現(xiàn)03-18