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

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

2、;123.5 單純形法的程序?qū)崿F(xiàn) 143.5.1 算法描述 143.5.2 程序?qū)崿F(xiàn) 154 結(jié)論 17參考文獻(xiàn) 18致謝 19附錄 20摘  要線性規(guī)劃是運(yùn)籌學(xué)中數(shù)學(xué)規(guī)劃的基礎(chǔ)部分，是運(yùn)籌學(xué)中興起較早并且應(yīng)用廣泛的1個(gè)部分。事實(shí)上，線性規(guī)劃就是用數(shù)學(xué)為工具，來(lái)研究1定條件下，如何實(shí)現(xiàn)目標(biāo)最優(yōu)化。本文以經(jīng)濟(jì)生活中1個(gè)常見的實(shí)例為依據(jù)，建立線性規(guī)劃模型，通過(guò)引入普通單純形法，依次迭代并判斷，逐步逼近，最后得到最優(yōu)解。然后，介紹了求解1般線性規(guī)劃問(wèn)題的大m單純形法（簡(jiǎn)稱大m法），并舉1例說(shuō)明大m法的基本思路：通過(guò)添加人

3、工變量使得標(biāo)準(zhǔn)化后的系數(shù)矩陣1定含有單位矩陣，從而得到1組基變量和初始基本可行解。由于人工變量是人為添加的，為了不改變?cè)瓎?wèn)題，在目標(biāo)函數(shù)中消去人工變量，并將人工變量由初始的基變量化成非基變量，使之取值為0，然后用普通單純形法求解。最后，本文還實(shí)現(xiàn)了用大m單純形法的程序解線性規(guī)劃問(wèn)題。關(guān)鍵字：線性規(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世紀(jì)30年代末，蘇聯(lián)數(shù)學(xué)

9、家康特羅維奇研究交通運(yùn)輸及機(jī)械加工等部門的生產(chǎn)管理工作，于1939年寫了生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法1書初稿，為線性規(guī)劃建立數(shù)學(xué)模型及解法奠定基礎(chǔ),自此開始，線性規(guī)劃經(jīng)過(guò)不斷的應(yīng)用和發(fā)展，在工業(yè)、農(nóng)業(yè)生產(chǎn)管理，交通運(yùn)輸?shù)闹笓]調(diào)度，資源開發(fā)，商業(yè)和銀行等領(lǐng)域得到廣泛應(yīng)用，顯著提高了企業(yè)的經(jīng)濟(jì)效益。隨著生產(chǎn)規(guī)模的擴(kuò)大和經(jīng)濟(jì)事務(wù)變得日益繁雜，對(duì)線性規(guī)劃提出了更多的理論要求，又促使這門學(xué)科迅速發(fā)展和完善。線性規(guī)劃不斷發(fā)展，適用領(lǐng)域不斷拓寬，從解決技術(shù)問(wèn)題的最優(yōu)化設(shè)計(jì)，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃及管理等領(lǐng)域都發(fā)生著作用，已成為現(xiàn)代科學(xué)管理的重要基礎(chǔ)理論。例如，在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這些問(wèn)題，如生產(chǎn)計(jì)劃問(wèn)題，即如何合理利用有限的人、財(cái)、物等資源，以便得到最好的經(jīng)濟(jì)效果；材料利用問(wèn)題，即如何下料使用材最少；配料問(wèn)題，即在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)；勞動(dòng)力安排問(wèn)題，即如何用最少的勞動(dòng)力來(lái)滿足工作的需要；運(yùn)輸問(wèn)題，即如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小；投資問(wèn)題，即從投資項(xiàng)目中選取方案，使投資回報(bào)最大等等。對(duì)于這些問(wèn)題，都能建立相應(yīng)的線性規(guī)劃模型。事實(shí)上，線性規(guī)劃