單純形解線性規(guī)劃問題及其編程實現(xiàn)

1、單純形解線性規(guī)劃問題及其編程實現(xiàn) 目    錄摘要 1前言 21 線性規(guī)劃問題及其數(shù)學模型 31.1 問題提出 31.2 模型建立 31.3 線性規(guī)劃模型的幾種形式 41.3.1 1般形式 41.3.2 標準形式 41.3.3 1般形式化標準形式 52 線性規(guī)劃問題解的概念 73 單純形法解線性規(guī)劃問題 83.1 單純形法的基本思路 83.2 普通單純形法原理 83.3 單純形表 93.4 單純形法的進1步討論大m法 

2、;123.5 單純形法的程序?qū)崿F(xiàn) 143.5.1 算法描述 143.5.2 程序?qū)崿F(xiàn) 154 結(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法的基本思路：通過添加人

3、工變量使得標準化后的系數(shù)矩陣1定含有單位矩陣，從而得到1組基變量和初始基本可行解。由于人工變量是人為添加的，為了不改變原問題，在目標函數(shù)中消去人工變量，并將人工變量由初始的基變量化成非基變量，使之取值為0，然后用普通單純形法求解。最后，本文還實現(xiàn)了用大m單純形法的程序解線性規(guī)劃問題。關鍵字：線性規(guī)劃；單純形法；大m法。abstractthe linear programming is a fundamental part of mathematical programming in the operations research . it is also an early-emerging a

4、nd 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

5、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

6、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 o

7、btained 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

8、 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ù)學

9、家康特羅維奇研究交通運輸及機械加工等部門的生產(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)運方案，使總運費最?。煌顿Y問題，即從投資項目中選取方案，使投資回報最大等等。對于這些問題，都能建立相應的線性規(guī)劃模型。事實上，線性規(guī)劃