導(dǎo)語：如何才能寫好一篇運(yùn)籌學(xué)單純形法教程，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。

篇1

關(guān)鍵詞：線性規(guī)劃問題；單純形法；分塊；并行求解

中圖分類號： O15 文獻(xiàn)標(biāo)識碼：A 文章編號：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

中圖分類號：O151.21 文獻(xiàn)標(biāo)識碼：A

佛山職業(yè)技術(shù)學(xué)院校級科研基金資助項(xiàng)目： 2014KY017

1 引言

規(guī)劃問題所涉及的是，對有限的資源進(jìn)行合理的利用或調(diào)配，從而達(dá)到所期望的目的。這些問題的特點(diǎn)是，有大量的方案（解）滿足每個問題的基本條件，究竟把哪一方案（解）選為最優(yōu)，則與問題中某一個實(shí)際要求或目標(biāo)有關(guān)[1]。而線性規(guī)劃（Linear Programming）問題則是規(guī)劃問題例，該類問題的數(shù)學(xué)模型可用線性的關(guān)系式進(jìn)行描述。通常，線性規(guī)劃所研究的問題有兩類，一類為資源（人力、物力、財力）是給定的，要求充分利用這些資源，最大限度地實(shí)現(xiàn)預(yù)期的目標(biāo)（產(chǎn)量、產(chǎn)值最大、利潤最高等）；另一類為任務(wù)是給定的，要求以消耗最少的資源（原料、工時、成本）來完成它。前一類問題稱為極大值問題，后一類問題稱為極小值問題[2-4]。

在線性規(guī)劃的解法中，單純形法是一個最著名的方法。它在理論上是完善和嚴(yán)格的，在實(shí)踐上是方便和有效的。注意到當(dāng)前的微機(jī)普遍具有多核計算架構(gòu)，為更好地發(fā)揮這一特性，我們對線性規(guī)劃問題中的單純形求解法進(jìn)行了分塊并行計算的改進(jìn)。

2 線性規(guī)劃問題的數(shù)學(xué)模型及其標(biāo)準(zhǔn)形式

2.1 線性規(guī)劃問題的數(shù)學(xué)模型

現(xiàn)實(shí)生活中的線性規(guī)劃問題是各式各樣的，但經(jīng)過抽象處理后，它們普遍具有如下的共同特點(diǎn)：表示問題的最優(yōu)化的目標(biāo)指標(biāo)是線性函數(shù)，表示約束條件的數(shù)學(xué)式子是一組變量 的線性等式或線性不等式組，為此，可以得到線性規(guī)劃問題其數(shù)學(xué)模型的一般形式為[5]：

求一組決策變量 的值，使之滿足下列約束條件：

從圖2可知，單純形的分塊并行計算的加速比隨著計算規(guī)模的增加而增長，在矩陣 的階數(shù)為8000階時，其加速比達(dá)到51.2%。

5 結(jié)語

在單純形法的基礎(chǔ)上，提出了一種線性規(guī)劃問題的分塊并行求解算法，新算法具有良好的加速比和易于實(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].大連：東北財經(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?周偉明.多核計算與程序設(shè)計[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

中圖分類號：F224.3 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2015）36-0105-03

0 引言

在物資調(diào)運(yùn)過程中，完成指定點(diǎn)的調(diào)運(yùn)任務(wù)是最基本的要求，在完成基本的任務(wù)之外，往往有更高的追求，比如如何使總運(yùn)費(fèi)最?。吭鯓硬拍苁沟眠\(yùn)輸時間最短？如何選擇運(yùn)輸路徑使得運(yùn)輸總距離最短等等。這些更高的追求往往是企業(yè)期望達(dá)到的目標(biāo)，為了解決這些類似問題，有必要對物資調(diào)運(yùn)的過程進(jìn)行數(shù)學(xué)模型的建立，以期通過模型來理解和分析物資調(diào)運(yùn)的過程，并為其找到解決的方法?，F(xiàn)以具體的案例進(jìn)行分析研究。

案例：某物流公司有三個倉庫，每天向四個超市供應(yīng)某種貨物，其供銷及單位運(yùn)費(fèi)（元/箱）見表1。要求設(shè)計出物資調(diào)運(yùn)方案，使得總運(yùn)費(fèi)最省。

現(xiàn)設(shè)每個發(fā)貨點(diǎn)運(yùn)往每個收貨點(diǎn)的具體物資的數(shù)量為xij（i=1，2，…m；j=1，2，…n），cij為其對應(yīng)的單位運(yùn)費(fèi)。根據(jù)案例中的已知信息可建立物資調(diào)運(yùn)問題的數(shù)學(xué)模型：

通過上面案例的模型，可得到一般的物資調(diào)運(yùn)問題模型如下：

現(xiàn)設(shè)有某種產(chǎn)品，它有m個發(fā)貨點(diǎn)：A1，A2…Am，發(fā)貨量分別為a1，a2，…am，Ai表示第i個發(fā)貨點(diǎn)，ai表示第i個發(fā)貨點(diǎn)的發(fā)貨量；它又有n個收貨點(diǎn)：B1，B2…Bn，收貨量分別為b1，b2，…bn， Bj表示第j個收貨點(diǎn)，bj表示第j個收貨點(diǎn)的收貨量；cij表示從Ai到Bj的單位運(yùn)費(fèi)。

從上述建模的過程可以看出，物資調(diào)運(yùn)問題是一類特殊的線性規(guī)劃問題，可以用一般的單純形法求解，但是應(yīng)去掉一個多余的約束條件，計算往往比較復(fù)雜，這里不予討論。

根據(jù)模型，物資調(diào)運(yùn)的方案有多種，即有多個解，但如何能從多個解中尋找到滿足條件的最優(yōu)解，這才是最為關(guān)鍵的問題。為了尋找出最優(yōu)解，需要使用一種迭代法，一般將迭代過程在表格中進(jìn)行，通過不斷地調(diào)整方案，最后得到最優(yōu)方案，這種方法多稱為“表上作業(yè)法”。目前表上作業(yè)法為求解物資調(diào)運(yùn)問題的一種簡便而實(shí)用的方法，下面將具體介紹如何用表上作業(yè)法求解物資調(diào)運(yù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)過若干次調(diào)整檢驗(yàn)，終能得到最優(yōu)的調(diào)運(yùn)方案。 運(yùn)用表上作業(yè)法求得物資調(diào)運(yùn)問題的最優(yōu)解，需要解決三個關(guān)鍵問題：一是初始調(diào)運(yùn)方案如何制定；二是怎樣判斷方案是否為最優(yōu)；三是如方案不是最優(yōu)，怎樣調(diào)整出最優(yōu)。接下來將重點(diǎn)從這三個方面來分析物資調(diào)運(yùn)問題的解法。

1 制定初始調(diào)運(yùn)方案

制定初始調(diào)運(yùn)方案目前有三種方法：最小元素法、西北角法、沃格爾法。從簡單易理解角度出發(fā)，習(xí)慣使用最小元素法（即尋找單位運(yùn)費(fèi)最小的點(diǎn)處優(yōu)先安排運(yùn)輸量，以節(jié)省運(yùn)費(fèi)）制定初始調(diào)運(yùn)方案：

①從運(yùn)費(fèi)表所有元素中選取最小元素。

②尋找這個元素所在的行對應(yīng)的發(fā)貨量和列對應(yīng)的收貨量中的較小者，將較小者填入初始調(diào)運(yùn)方案中這個元素所對應(yīng)的空格處，并在運(yùn)費(fèi)表中劃去較小者所在的行或列。案例的運(yùn)費(fèi)表中最小的元素為1，1對應(yīng)的行的總發(fā)貨量為40箱，而列對應(yīng)的總收貨量為30箱，所以在初始調(diào)運(yùn)方案中將1對應(yīng)處即發(fā)點(diǎn)A2倉庫處運(yùn)送30箱到B1超市，又因?yàn)榱袑?yīng)的總收量為30箱，所以該列的總收量已經(jīng)全部滿足，該列的其余元素3和7對應(yīng)處則不再安排運(yùn)輸任務(wù)，于是運(yùn)費(fèi)表中B1對應(yīng)列可以劃掉，以方便尋找運(yùn)費(fèi)表剩下元素中的最小元素。

③依此類推，直到收貨量和發(fā)貨量全部滿足。

注意：1）每在初始調(diào)運(yùn)方案中填入一個數(shù)字，運(yùn)費(fèi)表中至少有一列或一行被滿足，劃去該行或該列的元素，直到運(yùn)費(fèi)表全部被劃完，此時初始調(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ù)的格子同等對待，保證每填入一個數(shù)，只能劃去一行或一列。

3）最后一個填入數(shù)字的格應(yīng)使行或列同時滿足。

通過上述制定初始方案過程，可以得到案例對應(yīng)的初始調(diào)運(yùn)方案如表2所示。

2 檢驗(yàn)調(diào)運(yùn)方案是否為最優(yōu)

檢驗(yàn)的過程是在運(yùn)費(fèi)表中進(jìn)行，在運(yùn)費(fèi)表中把對應(yīng)于有調(diào)運(yùn)數(shù)字的運(yùn)費(fèi)用圓圈圈起，通過閉回路法求檢驗(yàn)數(shù)，根據(jù)檢驗(yàn)數(shù)來檢驗(yàn)方案是否為最優(yōu)方案。

閉回路的尋找方法如下：從任意一個空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到有數(shù)字的格子轉(zhuǎn)向，經(jīng)過若干次轉(zhuǎn)向后，回到原來出發(fā)的空格，形成閉回路。注意：有數(shù)字的格子處可以轉(zhuǎn)向，也可以不轉(zhuǎn)向，但要轉(zhuǎn)向的地方必為有數(shù)字的格子處。

求檢驗(yàn)數(shù)：從空格（即無調(diào)運(yùn)對應(yīng)處）出發(fā)，沿閉回路，將其對應(yīng)的閉回路中偶數(shù)次轉(zhuǎn)向點(diǎn)對應(yīng)的運(yùn)費(fèi)總和減去奇數(shù)次轉(zhuǎn)向點(diǎn)對應(yīng)的運(yùn)費(fèi)總和，所得的差為該空格處檢驗(yàn)數(shù)。

檢驗(yàn)過程：如果所有的檢驗(yàn)數(shù)均非負(fù)，則該方案為最優(yōu)方案，反之，則不是最優(yōu)，需調(diào)整。

表3為運(yùn)用閉回路法求得的初始調(diào)運(yùn)方案對應(yīng)的檢驗(yàn)數(shù)。

3 調(diào)整

上面已經(jīng)提到，如果所有的檢驗(yàn)數(shù)均非負(fù)，則該方案為最優(yōu)方案，無需調(diào)整。反之，只要任意一個（或多個）檢驗(yàn)數(shù)是負(fù)數(shù)，則需對初始調(diào)運(yùn)方案進(jìn)行調(diào)整。由初始方案對應(yīng)的檢驗(yàn)數(shù)表中可以看到，A2行B4列對應(yīng)處檢驗(yàn)數(shù)為-1，需要調(diào)整。

調(diào)整過程是在初始調(diào)運(yùn)方案中進(jìn)行，首先將檢驗(yàn)數(shù)中最小負(fù)值對應(yīng)的初始調(diào)運(yùn)方案處找到，作出對應(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)方案依然無法確定其是否為最優(yōu)方案，所以仍需對新方案繼續(xù)求檢驗(yàn)數(shù)以便再次檢驗(yàn)，如所有檢驗(yàn)數(shù)非負(fù)，則為最優(yōu)方案，若有負(fù)數(shù)的檢驗(yàn)數(shù)，則繼續(xù)一次次調(diào)整，再檢驗(yàn)，直到得到最優(yōu)方案。新方案對應(yīng)的檢驗(yàn)數(shù)如表5所示。

從新方案對應(yīng)的檢驗(yàn)數(shù)來看，所有的檢驗(yàn)數(shù)均非負(fù)，故此新方案已是最優(yōu)方案。即從A1倉庫分別運(yùn)50箱和20箱到B3和B4超市；從A2分別運(yùn)30箱和10箱到B1和B4超市；從A3倉庫分別運(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)過程，從確定初始調(diào)運(yùn)方案到檢驗(yàn)是否為最優(yōu)，不是則調(diào)整出最優(yōu)，整個思維過程不僅僅適用于求總運(yùn)費(fèi)最省的情形，同樣適用于求耗時最少或是路程最短問題。表上作業(yè)法雖然為求解物資調(diào)運(yùn)問題的一種行之有效的方法，但是仍然有不少問題需要解決，比如如何能一次得到最優(yōu)方案，規(guī)避調(diào)整多次的情形；產(chǎn)銷不平衡又如何解決等等，這些都是值得繼續(xù)探討的問題。

參考文獻(xiàn)：

[1]傅維潼.物流數(shù)學(xué)[M].高等教育出版社，2006.