運(yùn)籌學(xué)單純形法教程范文
時(shí)間:2023-10-25 17:23:27
導(dǎo)語(yǔ):如何才能寫好一篇運(yùn)籌學(xué)單純形法教程,這就需要搜集整理更多的資料和文獻(xiàn),歡迎閱讀由公務(wù)員之家整理的十篇范文,供你借鑒。
篇1
關(guān)鍵詞:線性規(guī)劃問(wèn)題;單純形法;分塊;并行求解
中圖分類號(hào): O15 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1672-3791(2016)04(b)-0000-00
Abstract: Simplex method is still the most effective and most commonly used algorithm for solving linear programming problems. Analysis of the calculation principle and process of the simplex method and the correlation operation and swapping based iterative process were divided into blocks, on this basis, design and implementation of the a kind of parallel processing algorithm for solving the mechanism of the linear programming problem. The practical application shows that the new algorithm has a good speedup, and is easy to be implemented in a computer with multi core architecture.
Key words: linear programming problem; simplex method; block; parallel solution
中圖分類號(hào):O151.21 文獻(xiàn)標(biāo)識(shí)碼:A
佛山職業(yè)技術(shù)學(xué)院校級(jí)科研基金資助項(xiàng)目: 2014KY017
1 引言
規(guī)劃問(wèn)題所涉及的是,對(duì)有限的資源進(jìn)行合理的利用或調(diào)配,從而達(dá)到所期望的目的。這些問(wèn)題的特點(diǎn)是,有大量的方案(解)滿足每個(gè)問(wèn)題的基本條件,究竟把哪一方案(解)選為最優(yōu),則與問(wèn)題中某一個(gè)實(shí)際要求或目標(biāo)有關(guān)[1]。而線性規(guī)劃(Linear Programming)問(wèn)題則是規(guī)劃問(wèn)題例,該類問(wèn)題的數(shù)學(xué)模型可用線性的關(guān)系式進(jìn)行描述。通常,線性規(guī)劃所研究的問(wèn)題有兩類,一類為資源(人力、物力、財(cái)力)是給定的,要求充分利用這些資源,最大限度地實(shí)現(xiàn)預(yù)期的目標(biāo)(產(chǎn)量、產(chǎn)值最大、利潤(rùn)最高等);另一類為任務(wù)是給定的,要求以消耗最少的資源(原料、工時(shí)、成本)來(lái)完成它。前一類問(wèn)題稱為極大值問(wèn)題,后一類問(wèn)題稱為極小值問(wèn)題[2-4]。
在線性規(guī)劃的解法中,單純形法是一個(gè)最著名的方法。它在理論上是完善和嚴(yán)格的,在實(shí)踐上是方便和有效的。注意到當(dāng)前的微機(jī)普遍具有多核計(jì)算架構(gòu),為更好地發(fā)揮這一特性,我們對(duì)線性規(guī)劃問(wèn)題中的單純形求解法進(jìn)行了分塊并行計(jì)算的改進(jìn)。
2 線性規(guī)劃問(wèn)題的數(shù)學(xué)模型及其標(biāo)準(zhǔn)形式
2.1 線性規(guī)劃問(wèn)題的數(shù)學(xué)模型
現(xiàn)實(shí)生活中的線性規(guī)劃問(wèn)題是各式各樣的,但經(jīng)過(guò)抽象處理后,它們普遍具有如下的共同特點(diǎn):表示問(wèn)題的最優(yōu)化的目標(biāo)指標(biāo)是線性函數(shù),表示約束條件的數(shù)學(xué)式子是一組變量 的線性等式或線性不等式組,為此,可以得到線性規(guī)劃問(wèn)題其數(shù)學(xué)模型的一般形式為[5]:
求一組決策變量 的值,使之滿足下列約束條件:
從圖2可知,單純形的分塊并行計(jì)算的加速比隨著計(jì)算規(guī)模的增加而增長(zhǎng),在矩陣 的階數(shù)為8000階時(shí),其加速比達(dá)到51.2%。
5 結(jié)語(yǔ)
在單純形法的基礎(chǔ)上,提出了一種線性規(guī)劃問(wèn)題的分塊并行求解算法,新算法具有良好的加速比和易于實(shí)現(xiàn)的特點(diǎn),理論分析及相關(guān)實(shí)驗(yàn)均表明它是有效的。
參考文獻(xiàn):
1?范玉妹,徐爾,趙金玲等.數(shù)學(xué)規(guī)劃及其應(yīng)用(第3版)[M].北京:冶金工業(yè)出版社,2009,1-7.
2?張香云.線性規(guī)劃[M].杭州:浙江大學(xué)出版社,2009,1-173.
3?杜紅.應(yīng)用運(yùn)籌學(xué) [M].杭州:浙江大學(xué)出版社,2010,19-72.
4?張惠恩.管理線性規(guī)劃[M].大連:東北財(cái)經(jīng)大學(xué)出版社,2001,1-91.
5?胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京:清華大學(xué)出版社,2007,11-14.
6?龐碧君.線性規(guī)劃與隨機(jī)線性規(guī)劃[M].鄭州: 鄭州大學(xué)出版社,2007,17-55.
7?周偉明.多核計(jì)算與程序設(shè)計(jì)[M].武漢:華中科技大學(xué)出版社,2009,75-124.
8?武漢大學(xué)多核架構(gòu)與編程課程組編.多核架構(gòu)與編程技術(shù)[M].武漢:武漢大學(xué)出版社,2010,23-96?
篇2
Abstract: Physical distribution process needs to allocate and transport the materials by the specified requirements and it needs the lowest cost. The table dispatching method can effectively solve the problems.
關(guān)鍵詞: 物資調(diào)運(yùn);建模;表上作業(yè)法
Key words: physical distribution;modeling;table dispatching method
中圖分類號(hào):F224.3 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1006-4311(2015)36-0105-03
0 引言
在物資調(diào)運(yùn)過(guò)程中,完成指定點(diǎn)的調(diào)運(yùn)任務(wù)是最基本的要求,在完成基本的任務(wù)之外,往往有更高的追求,比如如何使總運(yùn)費(fèi)最省?怎樣才能使得運(yùn)輸時(shí)間最短?如何選擇運(yùn)輸路徑使得運(yùn)輸總距離最短等等。這些更高的追求往往是企業(yè)期望達(dá)到的目標(biāo),為了解決這些類似問(wèn)題,有必要對(duì)物資調(diào)運(yùn)的過(guò)程進(jìn)行數(shù)學(xué)模型的建立,以期通過(guò)模型來(lái)理解和分析物資調(diào)運(yùn)的過(guò)程,并為其找到解決的方法。現(xiàn)以具體的案例進(jìn)行分析研究。
案例:某物流公司有三個(gè)倉(cāng)庫(kù),每天向四個(gè)超市供應(yīng)某種貨物,其供銷及單位運(yùn)費(fèi)(元/箱)見表1。要求設(shè)計(jì)出物資調(diào)運(yùn)方案,使得總運(yùn)費(fèi)最省。
現(xiàn)設(shè)每個(gè)發(fā)貨點(diǎn)運(yùn)往每個(gè)收貨點(diǎn)的具體物資的數(shù)量為xij(i=1,2,…m;j=1,2,…n),cij為其對(duì)應(yīng)的單位運(yùn)費(fèi)。根據(jù)案例中的已知信息可建立物資調(diào)運(yùn)問(wèn)題的數(shù)學(xué)模型:
通過(guò)上面案例的模型,可得到一般的物資調(diào)運(yùn)問(wèn)題模型如下:
現(xiàn)設(shè)有某種產(chǎn)品,它有m個(gè)發(fā)貨點(diǎn):A1,A2…Am,發(fā)貨量分別為a1,a2,…am,Ai表示第i個(gè)發(fā)貨點(diǎn),ai表示第i個(gè)發(fā)貨點(diǎn)的發(fā)貨量;它又有n個(gè)收貨點(diǎn):B1,B2…Bn,收貨量分別為b1,b2,…bn, Bj表示第j個(gè)收貨點(diǎn),bj表示第j個(gè)收貨點(diǎn)的收貨量;cij表示從Ai到Bj的單位運(yùn)費(fèi)。
從上述建模的過(guò)程可以看出,物資調(diào)運(yùn)問(wèn)題是一類特殊的線性規(guī)劃問(wèn)題,可以用一般的單純形法求解,但是應(yīng)去掉一個(gè)多余的約束條件,計(jì)算往往比較復(fù)雜,這里不予討論。
根據(jù)模型,物資調(diào)運(yùn)的方案有多種,即有多個(gè)解,但如何能從多個(gè)解中尋找到滿足條件的最優(yōu)解,這才是最為關(guān)鍵的問(wèn)題。為了尋找出最優(yōu)解,需要使用一種迭代法,一般將迭代過(guò)程在表格中進(jìn)行,通過(guò)不斷地調(diào)整方案,最后得到最優(yōu)方案,這種方法多稱為“表上作業(yè)法”。目前表上作業(yè)法為求解物資調(diào)運(yùn)問(wèn)題的一種簡(jiǎn)便而實(shí)用的方法,下面將具體介紹如何用表上作業(yè)法求解物資調(diào)運(yùn)問(wèn)題。
表上作業(yè)法要求先整理出產(chǎn)銷平衡表和單位運(yùn)費(fèi)表,再根據(jù)產(chǎn)銷平衡表和運(yùn)費(fèi)表編制出初始調(diào)運(yùn)方案。初始方案不一定是最優(yōu)方案,需要檢驗(yàn)方案是否為最優(yōu),若不是最優(yōu)的,則需在初始方案上進(jìn)行調(diào)整,調(diào)整后再檢驗(yàn),經(jīng)過(guò)若干次調(diào)整檢驗(yàn),終能得到最優(yōu)的調(diào)運(yùn)方案。 運(yùn)用表上作業(yè)法求得物資調(diào)運(yùn)問(wèn)題的最優(yōu)解,需要解決三個(gè)關(guān)鍵問(wèn)題:一是初始調(diào)運(yùn)方案如何制定;二是怎樣判斷方案是否為最優(yōu);三是如方案不是最優(yōu),怎樣調(diào)整出最優(yōu)。接下來(lái)將重點(diǎn)從這三個(gè)方面來(lái)分析物資調(diào)運(yùn)問(wèn)題的解法。
1 制定初始調(diào)運(yùn)方案
制定初始調(diào)運(yùn)方案目前有三種方法:最小元素法、西北角法、沃格爾法。從簡(jiǎn)單易理解角度出發(fā),習(xí)慣使用最小元素法(即尋找單位運(yùn)費(fèi)最小的點(diǎn)處優(yōu)先安排運(yùn)輸量,以節(jié)省運(yùn)費(fèi))制定初始調(diào)運(yùn)方案:
①?gòu)倪\(yùn)費(fèi)表所有元素中選取最小元素。
②尋找這個(gè)元素所在的行對(duì)應(yīng)的發(fā)貨量和列對(duì)應(yīng)的收貨量中的較小者,將較小者填入初始調(diào)運(yùn)方案中這個(gè)元素所對(duì)應(yīng)的空格處,并在運(yùn)費(fèi)表中劃去較小者所在的行或列。案例的運(yùn)費(fèi)表中最小的元素為1,1對(duì)應(yīng)的行的總發(fā)貨量為40箱,而列對(duì)應(yīng)的總收貨量為30箱,所以在初始調(diào)運(yùn)方案中將1對(duì)應(yīng)處即發(fā)點(diǎn)A2倉(cāng)庫(kù)處運(yùn)送30箱到B1超市,又因?yàn)榱袑?duì)應(yīng)的總收量為30箱,所以該列的總收量已經(jīng)全部滿足,該列的其余元素3和7對(duì)應(yīng)處則不再安排運(yùn)輸任務(wù),于是運(yùn)費(fèi)表中B1對(duì)應(yīng)列可以劃掉,以方便尋找運(yùn)費(fèi)表剩下元素中的最小元素。
③依此類推,直到收貨量和發(fā)貨量全部滿足。
注意:1)每在初始調(diào)運(yùn)方案中填入一個(gè)數(shù)字,運(yùn)費(fèi)表中至少有一列或一行被滿足,劃去該行或該列的元素,直到運(yùn)費(fèi)表全部被劃完,此時(shí)初始調(diào)運(yùn)方案表中有填數(shù)字的格數(shù)是m+n-1。
2)如果某行或列的供應(yīng)量都已經(jīng)滿足,但該行或列還未被劃去,應(yīng)在初始調(diào)運(yùn)方案表內(nèi)相應(yīng)位置填入0,然后再劃去該行或列,并將填0的格子與其他填數(shù)的格子同等對(duì)待,保證每填入一個(gè)數(shù),只能劃去一行或一列。
3)最后一個(gè)填入數(shù)字的格應(yīng)使行或列同時(shí)滿足。
通過(guò)上述制定初始方案過(guò)程,可以得到案例對(duì)應(yīng)的初始調(diào)運(yùn)方案如表2所示。
2 檢驗(yàn)調(diào)運(yùn)方案是否為最優(yōu)
檢驗(yàn)的過(guò)程是在運(yùn)費(fèi)表中進(jìn)行,在運(yùn)費(fèi)表中把對(duì)應(yīng)于有調(diào)運(yùn)數(shù)字的運(yùn)費(fèi)用圓圈圈起,通過(guò)閉回路法求檢驗(yàn)數(shù),根據(jù)檢驗(yàn)數(shù)來(lái)檢驗(yàn)方案是否為最優(yōu)方案。
閉回路的尋找方法如下:從任意一個(gè)空格出發(fā),沿水平或垂直方向前進(jìn),遇到有數(shù)字的格子轉(zhuǎn)向,經(jīng)過(guò)若干次轉(zhuǎn)向后,回到原來(lái)出發(fā)的空格,形成閉回路。注意:有數(shù)字的格子處可以轉(zhuǎn)向,也可以不轉(zhuǎn)向,但要轉(zhuǎn)向的地方必為有數(shù)字的格子處。
求檢驗(yàn)數(shù):從空格(即無(wú)調(diào)運(yùn)對(duì)應(yīng)處)出發(fā),沿閉回路,將其對(duì)應(yīng)的閉回路中偶數(shù)次轉(zhuǎn)向點(diǎn)對(duì)應(yīng)的運(yùn)費(fèi)總和減去奇數(shù)次轉(zhuǎn)向點(diǎn)對(duì)應(yīng)的運(yùn)費(fèi)總和,所得的差為該空格處檢驗(yàn)數(shù)。
檢驗(yàn)過(guò)程:如果所有的檢驗(yàn)數(shù)均非負(fù),則該方案為最優(yōu)方案,反之,則不是最優(yōu),需調(diào)整。
表3為運(yùn)用閉回路法求得的初始調(diào)運(yùn)方案對(duì)應(yīng)的檢驗(yàn)數(shù)。
3 調(diào)整
上面已經(jīng)提到,如果所有的檢驗(yàn)數(shù)均非負(fù),則該方案為最優(yōu)方案,無(wú)需調(diào)整。反之,只要任意一個(gè)(或多個(gè))檢驗(yàn)數(shù)是負(fù)數(shù),則需對(duì)初始調(diào)運(yùn)方案進(jìn)行調(diào)整。由初始方案對(duì)應(yīng)的檢驗(yàn)數(shù)表中可以看到,A2行B4列對(duì)應(yīng)處檢驗(yàn)數(shù)為-1,需要調(diào)整。
調(diào)整過(guò)程是在初始調(diào)運(yùn)方案中進(jìn)行,首先將檢驗(yàn)數(shù)中最小負(fù)值對(duì)應(yīng)的初始調(diào)運(yùn)方案處找到,作出對(duì)應(yīng)空格的閉合回路。奇數(shù)次轉(zhuǎn)向點(diǎn)中最小運(yùn)量作為調(diào)整量,所有奇數(shù)次轉(zhuǎn)向點(diǎn)運(yùn)量減去調(diào)整量,偶數(shù)次轉(zhuǎn)點(diǎn)運(yùn)量加上該調(diào)整量,得到新的調(diào)運(yùn)方案。(表4)
新調(diào)運(yùn)方案依然無(wú)法確定其是否為最優(yōu)方案,所以仍需對(duì)新方案繼續(xù)求檢驗(yàn)數(shù)以便再次檢驗(yàn),如所有檢驗(yàn)數(shù)非負(fù),則為最優(yōu)方案,若有負(fù)數(shù)的檢驗(yàn)數(shù),則繼續(xù)一次次調(diào)整,再檢驗(yàn),直到得到最優(yōu)方案。新方案對(duì)應(yīng)的檢驗(yàn)數(shù)如表5所示。
從新方案對(duì)應(yīng)的檢驗(yàn)數(shù)來(lái)看,所有的檢驗(yàn)數(shù)均非負(fù),故此新方案已是最優(yōu)方案。即從A1倉(cāng)庫(kù)分別運(yùn)50箱和20箱到B3和B4超市;從A2分別運(yùn)30箱和10箱到B1和B4超市;從A3倉(cāng)庫(kù)分別運(yùn)60箱和30箱到B2和B4超市。其最小總運(yùn)費(fèi)為:30×1+60×4+50×3+20×10+10×8+30×5=850元。
運(yùn)用表上作業(yè)法求解物資調(diào)運(yùn)過(guò)程,從確定初始調(diào)運(yùn)方案到檢驗(yàn)是否為最優(yōu),不是則調(diào)整出最優(yōu),整個(gè)思維過(guò)程不僅僅適用于求總運(yùn)費(fèi)最省的情形,同樣適用于求耗時(shí)最少或是路程最短問(wèn)題。表上作業(yè)法雖然為求解物資調(diào)運(yùn)問(wèn)題的一種行之有效的方法,但是仍然有不少問(wèn)題需要解決,比如如何能一次得到最優(yōu)方案,規(guī)避調(diào)整多次的情形;產(chǎn)銷不平衡又如何解決等等,這些都是值得繼續(xù)探討的問(wèn)題。
參考文獻(xiàn):
[1]傅維潼.物流數(shù)學(xué)[M].高等教育出版社,2006.
相關(guān)文章
1運(yùn)籌學(xué)課程教學(xué)模式與教學(xué)方法
2運(yùn)籌學(xué)教學(xué)現(xiàn)狀思考
相關(guān)期刊
-
運(yùn)籌與管理
主管:中國(guó)科學(xué)技術(shù)協(xié)會(huì)
級(jí)別:CSSCI南大期刊
影響因子:1.05
-
運(yùn)籌學(xué)學(xué)報(bào)
主管:中國(guó)科學(xué)技術(shù)協(xié)會(huì)
級(jí)別:北大期刊
影響因子:0.25
-
軍事運(yùn)籌與系統(tǒng)工程
主管:中國(guó)人民解放軍軍事科學(xué)院
級(jí)別:統(tǒng)計(jì)源期刊
影響因子:0.62
-
當(dāng)代金融家
主管:山西出版?zhèn)髅郊瘓F(tuán)有限責(zé)任公司
級(jí)別:省級(jí)期刊
影響因子:--