運籌學演算法模型

Ⅰ 運籌學中大M法的理論依據是什麼

對於一般形式的線性規劃問題，化為標准型後，大M法和兩階段法都可以求解。如果手算求解，兩種演算法的應用沒有差別。

如果是計算機編程，首選兩階段演算法。原因是大M法可能會由於大M的取值而出現計算誤差。

在極大化問題中，對人工變數賦於一M作為其系數；在極小化問題中，對人工變數賦於一個M作為其系數，M為一任意大（而非無窮大）的正數。把M看作一個代數符號參與運算，用單純形法求解。

(1)運籌學演算法模型擴展閱讀：

用單純形法在改進目標函數的過程中，如果原問題存在最優解，必然使人工變數逐步變為非基變數，或使其值為零。目標函數值將不可能達到最小或最大。

在迭代過程中，若全部人工變數變成非基變數，則可把人工變數所在的列從單純形表中刪去，此時便找到原問題的一個初始基可行解。若此基可行解不是原問題的最優解，則繼續迭代，直至所有的檢驗數都小於等於0，求得最優解為止。

Ⅱ 運籌學中的圖論問題

很多實際的生產問題都能被抽象成一張大的圖。具體一點的例子，比如需要在若干個城市之間鋪設鐵路或者架設電網，那麼城市就是圖裡面的點，鐵路電網就是圖裡面的邊。抽象一點的例子，比如完成一個項目的過程中所有可能出現的狀態都可以視為一個點，而狀態到狀態之間的轉換就是邊。上一篇文章中我們說過運籌學是處理實際生產生活中遇到的問題的。一旦實際問題被抽象成了一個圖的模型（注意與機器學習裡面的圖模型區分開來），很多圖論裡面的演算法就可以用來解決實際問題，所以圖論是運籌學當中的一個很大的分支。今天我們就介紹一下幾個圖論的基本演算法及其在生產生活中的應用。

一最小生成樹

比如現在要在若干個村子之間架設電網，保證每個城市都通上電（先不考慮電網輸電能力大小）。雖然理論上講，任何兩個村子之間都可以架設電線，不過那樣的話成本很到，不劃算，我們需要在所有可能的連線裡面找到一組總長最短的邊，保證這些邊把每個村子都連上了。在圖論中，這是一個典型的最小生成樹問題。有兩種解決最小生成樹的方法，第一種辦法是把所有的邊按照從小到大的順序添加到圖裡面，如果產生迴路就舍棄它，直到覆蓋了所有的點。另一種方法是把圖上的邊按照從大到小的順序刪除，直到再刪下去就一定會產生離散的點為止。

二最短路徑

圖論中應用最廣的問題可能就是最短路徑問題了。地圖上很多城市之間都有道路相連，想從一個城市到另一個城市，往往有多種選擇，可是走那條路距離最短呢？如果地圖規模不大，我們可以一眼就看出來。可是隨著地圖規模變大，就很難再一眼看出來了，需要有嚴格的演算法保證找到最短路徑。目前已經有了很多種最短路徑演算法，他們的基本思想也不盡相同。以著名的Dijkstra演算法為例，它每次會選擇距離「所有已經選擇過了的點」中距離最近的下一個點，一步步的迭代下去。這個流程保證了演算法會按照距離出發點由近到遠的順序選擇每一個點。

三最大流-最小割問題

油氣輸送網路又許多不同的邊組成，每一條邊的運輸能力有限。輸送油氣資源的時候，為了最大化運輸量，需要合理安排通過每一條邊的油氣流量。這就是在一個網路尋找最大流的問題（等價於尋找最小割）。解決問題的想法很簡單，找到一組邊，它們把整個網路分成了兩部分，流的源和目的地址分屬於這兩個部分。我們稱這樣一組邊為圖的一個分割。由於所有的油氣流都要通過分割中的邊，所以最大流其實受制於分割的流通能力的。於是最大流應該等於流通能力最小的分割。剩下的問題，就是一步步調整，找到最小分割了。

Ⅲ 運籌學有哪些演算法

圖像法，單純形法，對偶單純法，兩階段法。
圖像法只能解一般的含兩個未知數的不等式。
後3種是解多個未知數的不等式。
運籌學還有整數規劃，一般有分支定界法，隱枚舉法，匈牙利法。
運輸問題——一般為產銷問題，用最小元素法先做，再用位勢法調整
目標規劃問題——先建模，再用單純形法解，一般現在用excel解決
動態規劃——逆序法，順序法
最小支撐樹圖——避圈法，破圈法
最短路問題——dijkstra演算法