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

篇1

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

中圖分類號： O15 文獻標識碼：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 文獻標識碼：A

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

1 引言

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

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

2 線性規(guī)劃問題的數(shù)學模型及其標準形式

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

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

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

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

5 結(jié)語

在單純形法的基礎(chǔ)上，提出了一種線性規(guī)劃問題的分塊并行求解算法，新算法具有良好的加速比和易于實現(xiàn)的特點，理論分析及相關(guān)實驗均表明它是有效的。

參考文獻：

1?范玉妹，徐爾，趙金玲等.數(shù)學規(guī)劃及其應用（第3版）[M].北京：冶金工業(yè)出版社，2009，1-7.

2?張香云.線性規(guī)劃[M].杭州：浙江大學出版社，2009，1-173.

3?杜紅.應用運籌學 [M].杭州：浙江大學出版社，2010，19-72.

4?張惠恩.管理線性規(guī)劃[M].大連：東北財經(jīng)大學出版社，2001，1-91.

5?胡運權(quán).運籌學教程[M].北京：清華大學出版社，2007，11-14.

6?龐碧君.線性規(guī)劃與隨機線性規(guī)劃[M].鄭州： 鄭州大學出版社，2007，17-55.

7?周偉明.多核計算與程序設(shè)計[M].武漢：華中科技大學出版社，2009，75-124.

8?武漢大學多核架構(gòu)與編程課程組編.多核架構(gòu)與編程技術(shù)[M].武漢：武漢大學出版社，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è)法

Key words： physical distribution；modeling；table dispatching method

中圖分類號：F224.3 文獻標識碼：A 文章編號：1006-4311（2015）36-0105-03

0 引言

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

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

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

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

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

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

根據(jù)模型，物資調(diào)運的方案有多種，即有多個解，但如何能從多個解中尋找到滿足條件的最優(yōu)解，這才是最為關(guān)鍵的問題。為了尋找出最優(yōu)解，需要使用一種迭代法，一般將迭代過程在表格中進行，通過不斷地調(diào)整方案，最后得到最優(yōu)方案，這種方法多稱為“表上作業(yè)法”。目前表上作業(yè)法為求解物資調(diào)運問題的一種簡便而實用的方法，下面將具體介紹如何用表上作業(yè)法求解物資調(diào)運問題。

表上作業(yè)法要求先整理出產(chǎn)銷平衡表和單位運費表，再根據(jù)產(chǎn)銷平衡表和運費表編制出初始調(diào)運方案。初始方案不一定是最優(yōu)方案，需要檢驗方案是否為最優(yōu)，若不是最優(yōu)的，則需在初始方案上進行調(diào)整，調(diào)整后再檢驗，經(jīng)過若干次調(diào)整檢驗，終能得到最優(yōu)的調(diào)運方案。 運用表上作業(yè)法求得物資調(diào)運問題的最優(yōu)解，需要解決三個關(guān)鍵問題：一是初始調(diào)運方案如何制定；二是怎樣判斷方案是否為最優(yōu)；三是如方案不是最優(yōu)，怎樣調(diào)整出最優(yōu)。接下來將重點從這三個方面來分析物資調(diào)運問題的解法。

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

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

①從運費表所有元素中選取最小元素。

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

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

注意：1）每在初始調(diào)運方案中填入一個數(shù)字，運費表中至少有一列或一行被滿足，劃去該行或該列的元素，直到運費表全部被劃完，此時初始調(diào)運方案表中有填數(shù)字的格數(shù)是m+n-1。

2）如果某行或列的供應量都已經(jīng)滿足，但該行或列還未被劃去，應在初始調(diào)運方案表內(nèi)相應位置填入0，然后再劃去該行或列，并將填0的格子與其他填數(shù)的格子同等對待，保證每填入一個數(shù)，只能劃去一行或一列。

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

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

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

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

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

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

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

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

3 調(diào)整

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

調(diào)整過程是在初始調(diào)運方案中進行，首先將檢驗數(shù)中最小負值對應的初始調(diào)運方案處找到，作出對應空格的閉合回路。奇數(shù)次轉(zhuǎn)向點中最小運量作為調(diào)整量，所有奇數(shù)次轉(zhuǎn)向點運量減去調(diào)整量，偶數(shù)次轉(zhuǎn)點運量加上該調(diào)整量，得到新的調(diào)運方案。（表4）

新調(diào)運方案依然無法確定其是否為最優(yōu)方案，所以仍需對新方案繼續(xù)求檢驗數(shù)以便再次檢驗，如所有檢驗數(shù)非負，則為最優(yōu)方案，若有負數(shù)的檢驗數(shù)，則繼續(xù)一次次調(diào)整，再檢驗，直到得到最優(yōu)方案。新方案對應的檢驗數(shù)如表5所示。

從新方案對應的檢驗數(shù)來看，所有的檢驗數(shù)均非負，故此新方案已是最優(yōu)方案。即從A1倉庫分別運50箱和20箱到B3和B4超市；從A2分別運30箱和10箱到B1和B4超市；從A3倉庫分別運60箱和30箱到B2和B4超市。其最小總運費為：30×1+60×4+50×3+20×10+10×8+30×5=850元。

運用表上作業(yè)法求解物資調(diào)運過程，從確定初始調(diào)運方案到檢驗是否為最優(yōu)，不是則調(diào)整出最優(yōu)，整個思維過程不僅僅適用于求總運費最省的情形，同樣適用于求耗時最少或是路程最短問題。表上作業(yè)法雖然為求解物資調(diào)運問題的一種行之有效的方法，但是仍然有不少問題需要解決，比如如何能一次得到最優(yōu)方案，規(guī)避調(diào)整多次的情形；產(chǎn)銷不平衡又如何解決等等，這些都是值得繼續(xù)探討的問題。

參考文獻：

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