運籌學單純形法教程范文

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

篇1

關鍵詞：線性規劃問題；單純形法；分塊；并行求解

中圖分類號： 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

佛山職業技術學院校級科研基金資助項目： 2014KY017

1 引言

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

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

2 線性規劃問題的數學模型及其標準形式

2.1 線性規劃問題的數學模型

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

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

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

5 結語

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

參考文獻：

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

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

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

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

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

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

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

8?武漢大學多核架構與編程課程組編.多核架構與編程技術[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.

關鍵詞： 物資調運；建模；表上作業法

Key words： physical distribution；modeling；table dispatching method

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

0 引言

在物資調運過程中，完成指定點的調運任務是最基本的要求，在完成基本的任務之外，往往有更高的追求，比如如何使總運費最省？怎樣才能使得運輸時間最短？如何選擇運輸路徑使得運輸總距離最短等等。這些更高的追求往往是企業期望達到的目標，為了解決這些類似問題，有必要對物資調運的過程進行數學模型的建立，以期通過模型來理解和分析物資調運的過程，并為其找到解決的方法。現以具體的案例進行分析研究。

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

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

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

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

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

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

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

1 制定初始調運方案

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

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

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

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

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

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

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

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

2 檢驗調運方案是否為最優

檢驗的過程是在運費表中進行，在運費表中把對應于有調運數字的運費用圓圈圈起，通過閉回路法求檢驗數，根據檢驗數來檢驗方案是否為最優方案。

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

求檢驗數：從空格（即無調運對應處）出發，沿閉回路，將其對應的閉回路中偶數次轉向點對應的運費總和減去奇數次轉向點對應的運費總和，所得的差為該空格處檢驗數。

檢驗過程：如果所有的檢驗數均非負，則該方案為最優方案，反之，則不是最優，需調整。

表3為運用閉回路法求得的初始調運方案對應的檢驗數。

3 調整

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

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

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

從新方案對應的檢驗數來看，所有的檢驗數均非負，故此新方案已是最優方案。即從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元。

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

參考文獻：

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