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