單純演算法第四講視頻

1. 誰有「演算法分析與設計在線視頻教程」的下載地址。

演算法分析與設計在線視頻教程(附下載）局乎稿[下載注意]要復制地址而不是點擊鏈接,復制時要包括前面的 mms://,否則下載不了.

演算法分析與設計 第一講 演算法引論
mms://www.scopen.net/scddip/sffxysj/sffxysj1/Opene.asf
演算法分析與設計 第二講 遞歸於分治策略
mms:/頃鬧/www.scopen.net/scddip/sffxysj/sffxysj2/Opene.asf
演算法分析與設計 第三講 分治法的基本思想
mms://www.scopen.net/scddip/sffxysj/sffxysj3/Opene.asf
演算法分析與設計 第四講 Strassen矩陣乘法
mms://www.scopen.net/scddip/sffxysj/sffxysj4/Opene.asf
演算法分析與設計 第五講 動態規劃
mms://www.scopen.net/scddip/sffxysj/sffxysj5/Opene.asf
演算法分析與設計 第六講 貪心演算法
mms://www.scopen.net/scddip/sffxysj/sffxysj6/Opene.asf
演算法分析與設計 第七講 回溯法
mms://www.scopen.net/scddip/sffxysj/sffxysj7/Opene.asf
演算法分析與設計 第八講 分支限界法
mms://www.scopen.net/scddip/sffxysj/sffxysj8/Opene.asf

我試過了,可以下載,速度還可以
如果你不能下載桐孝的話,可能是你的網路有問題.我可以幫你下載之後再傳給你.
另外:
這里還有一個可以在線觀看的地址:

http://www.oa7t.com/bbs/forum-41-1.html
裡面的視頻全部可以在線觀看,可以點上面這個連接,也可以點下面這些地址:
http://219.144.186.219/sfsjyfx/1/content.htm 第1集
http://219.144.186.219/sfsjyfx/2/content.htm 第2集
http://219.144.186.219/sfsjyfx/3/content.htm 第3集
http://219.144.186.219/sfsjyfx/4/content.htm 第4集
http://219.144.186.219/sfsjyfx/5/content.htm 第5集

http://219.144.186.219/sfsjyfx/6/content.htm 第6集
http://219.144.186.219/sfsjyfx/7/content.htm 第7集
http://219.144.186.219/sfsjyfx/8/content.htm 第8集
http://219.144.186.219/sfsjyfx/9/content.htm 第9集
http://219.144.186.219/sfsjyfx/10/content.htm 第10集

http://219.144.186.219/sfsjyfx/11/content.htm 第11集
http://219.144.186.219/sfsjyfx/12/content.htm 第12集
http://219.144.186.219/sfsjyfx/13/content.htm 第13集
http://219.144.186.219/sfsjyfx/14/content.htm 第14集
http://219.144.186.219/sfsjyfx/15/content.htm 第15集

http://219.144.186.219/sfsjyfx/16/content.htm 第16集
http://219.144.186.219/sfsjyfx/17/content.htm 第17集
http://219.144.186.219/sfsjyfx/18/content.htm 第18集
http://219.144.186.219/sfsjyfx/19/content.htm 第19集
http://219.144.186.219/sfsjyfx/20/content.htm 第20集

http://219.144.186.219/sfsjyfx/21/content.htm 第21集
http://219.144.186.219/sfsjyfx/22/content.htm 第22集
http://219.144.186.219/sfsjyfx/23/content.htm 第23集
http://219.144.186.219/sfsjyfx/24/content.htm 第24集
http://219.144.186.219/sfsjyfx/25/content.htm 第25集

http://219.144.186.219/sfsjyfx/26/content.htm 第26集
http://219.144.186.219/sfsjyfx/27/content.htm 第27集
http://219.144.186.219/sfsjyfx/28/content.htm 第28集
http://219.144.186.219/sfsjyfx/29/content.htm 第29集
http://219.144.186.219/sfsjyfx/30/content.htm 第30集

http://219.144.186.219/sfsjyfx/31/content.htm 第31集
http://219.144.186.219/sfsjyfx/32/content.htm 第32集
http://219.144.186.219/sfsjyfx/33/content.htm 第33集
http://219.144.186.219/sfsjyfx/34/content.htm 第34集
http://219.144.186.219/sfsjyfx/35/content.htm 第35集

http://219.144.186.219/sfsjyfx/36/content.htm 第36集
http://219.144.186.219/sfsjyfx/37/content.htm 第37集
http://219.144.186.219/sfsjyfx/38/content.htm 第38集
http://219.144.186.219/sfsjyfx/39/content.htm 第39集
http://219.144.186.219/sfsjyfx/40/content.htm 第40集

http://219.144.186.219/sfsjyfx/41/content.htm 第41集
http://219.144.186.219/sfsjyfx/42/content.htm 第42集
http://219.144.186.219/sfsjyfx/43/content.htm 第43集
http://219.144.186.219/sfsjyfx/44/content.htm 第44集
http://219.144.186.219/sfsjyfx/45/content.htm 第45集

http://219.144.186.219/sfsjyfx/46/content.htm 第46集
http://219.144.186.219/sfsjyfx/47/content.htm 第47集
http://219.144.186.219/sfsjyfx/48/content.htm 第48集
http://219.144.186.219/sfsjyfx/49/content.htm 第49集
http://219.144.186.219/sfsjyfx/50/content.htm 第50集

http://219.144.186.219/sfsjyfx/51/content.htm 第51集
http://219.144.186.219/sfsjyfx/52/content.htm 第52集
http://219.144.186.219/sfsjyfx/53/content.htm 第53集
http://219.144.186.219/sfsjyfx/54/content.htm 第54集
http://219.144.186.219/sfsjyfx/55/content.htm 第55集

http://219.144.186.219/sfsjyfx/56/content.htm 第56集
http://219.144.186.219/sfsjyfx/57/content.htm 第57集

2. LP問題進階 Part 1 | 單純形法

為方便查閱，再link一下 教材 。

假設我們討論的LP問題有 個變數與 個限制條件。

基本概念部分大概就是這些。第一次看不用要求自己完全理解，不妨先繼續往下學習再慢慢理解這些概念罩培。

單純形方法的示意圖如下：

我們先從一下四點直觀的認識入手。

由於書上根本就沒有優化操作的概念，所以在此我自己給出其定義：

我們稱增加的這個非基本變數為 輸入變數 ，變為0的這個基本變數為 輸出變數 。因為輸入變數取代了輸出變數成為新的基。（基的定義可以在前面找到。）
通俗一點地說就是選擇一個非基本變數，讓其不斷增加，要求：

回到主題。之前提到單純形法即對一個基本解實施若干次優化操作後得到最優解的過程。我們先不考慮最優解的存在性，且斷言： 任意非基本變數增加不使得目標函數增加等價於目標函數取得最大值。 這是因為由於符號的限制，非基本變數只能增加，而所有的變數都可以被非基本變數表示。因此非基本變數的增加包含了所有變數的各種變化。

當無法再進行優化操作時有兩種可能。一種是任意非基本變數的增加不使得態悶咐目標函數增加。此時目標函數取最大值。另外一種情況是任意非基本變數的增加不使得某一基本變數變為0。注意， LP問題的標准形式中對於變數的所有限制最終都會歸結於符號限制 ，因此若基本變帆純量不會變為0，則非基本變數可以無限地增加。 此時LP問題無界。

還有一點需要注意的是優化操作一定會在有限步後結束，之後會講到這一點。

經過上述討論我們對單純形演算法的核心步驟應該有一個大致的了解了。

下面是一個小小的總結

單純形演算法到此結束

3. 線性規劃之單純形法

單純形法應用在線性規劃的標准模型上，任何一個線性規劃的一般形式都可以化為標准模型。
線性規劃模型的一般形式為：

把它轉換為標准型是要求所有的約束都是等式約束，且所有的決策變數非負。
如下面的形式：

舉個例子：

那麼很容易就可以寫出這個線性規劃問題的數學模型：

再重復一遍，線性規劃的標准型必為以下形式：

對於標准型我們有兩個基本假設：
1. 系數矩陣A的行向量線性無關。
2. 系數矩陣A的列數大於其行數，即n>m。因為如果n<m，那麼不滿足1, 如果n=m，那麼該線性規劃問題有唯一解，既然有唯一解，那就沒有優化的必要了。所以，必有n>m。

回到剛才那個例子，我們可以將找個標准型寫為如下形式：

這個例子m = 3, n = 5。那麼我們可以用三個變數表示所有的五個變數，這三個變數我們稱之為基變數。上圖中，x3, x4, x5的系數是一個單位陣。我們把這種形式的等式約束稱為典式。
觀察這個典式，我們可以很容易的看出其一個基本可行解：(0, 0, 15, 24, 5)T，即非基變數等於0，基變數等於等式右邊的常數。這個解，我們可以把它想像成基本可行解區域的一個頂點，我們知道最優解也在頂點上，那麼我們只要沿著邊界找這個最優頂點就可以了。

對於頂點(0, 0, 15, 24, 5)T，它的x3, x4, x5是基變數，那麼與該頂點相鄰的其他頂點的基變數有什麼關系呢？事實上，與之相鄰的頂點的所有基變數中只有一個基變數發生了變化。這是可以驗證的。所以，接下來的工作就是從x1, x2中選一個非基變數進基成為基變數，從x3, x4, x5中選一個基變數出基成為非基變數。

那麼問題來了，我們怎麼選擇進基變數和出基變數？

假設我們想要x2進基，那麼根據基本可行解的表示式，我們必須通過初等行變換的形式讓x2隻出現在一個等式約束中，就是把x2的系數變成(1,0,0)T或(0,1,0)T或(0,0,1)T的形式。
假設我們把x2變成(0,0,1)T的形式，初等行變換後得到：

現在對於例子

我們得到了兩個基本可行解X1 = (0,0,15,24,5)T, X2 = (0,3,0,18,2)T，記目標函數f(X) = 2x1 + x2 + 0x3 + 0x4 + 0x5
則f(X1) = 0, f(X2) = 3
那麼我們怎麼找到最優解呢？
我們知道 X2 = (0,3,0,18,2)T 的約束的表示式為：

發現什麼沒有？

對於可行解X2 = (0,3,0,18,2)T，x1，x3是非基變數啊，非基變數是0啊。但是，我們下一步不是選擇進基變數嗎，進基變數不是從非基變數里選嗎，我們選x1啊，為啥？x1的系數是正數2啊！我們這個例子是求z的最大值，如果x1進基，那麼必然會讓f(X)增大，因為我們的決策變數都是正數，正數乘正數還是正數，增量肯定是大於0的。我們看到x3的系數是-0.2，如果讓x3進基的話，增量肯定是小於0的。

如果x1, x3的系數都大於0怎麼辦？那隨便選啊。
如果x1，x3的系數都小於0怎麼辦？哈哈，有人可能就意識到了，非基變數的系數都小於0，選誰進基都會造成f(X)變小，我們不是求最大嗎？那我們誰也不選啊，這個問題已經結束了，我們已經找到最優解了！

所以，選擇進基變數的問題，以及判斷找到最優解的問題就都解決了。

我們一般使用單純形表來直觀表示這個過程。
還是可行解X2 = (0,3,0,18,2)T，它對應的單純形表如下：

最左邊一列是基變數，最右邊一列是約束右邊的常數項，中間一坨是決策變數的系數。最下邊一行是目標函數z = 2x1 + x2 + 0x3 + 0x4 + 0x5。最下面一行決策變數的系數我們稱之為檢驗數。
我們通過行變換將最後一行的基變數前面系數變成0，就得到下面的單純形表：

從這個表中我們可以得到以下信息：

然後通過剛才的方法讓x3進基，得到新的基本可行解的單純形表：

從這個表我們可以得知：

至此，我們已經得到該問題的最優解X4。

我們知道，對於一個基本可行解，一般情況下它的基變數是大於0，非基變數等於0。退化情況是，我們有一個基變數也等於0。那麼，這個基本可行解就會對應於多個可行基陣。
舉個例子：

X = （3，3，0，0，0）T是該問題的可行解
我們可以令x3,x4為非基變數， 也可以令x3,x5或x4,x5為非基變數。

退化情況存在的問題在於，經過一次進出基迭代後得到的是同一個基本可行解，因此有可能出現迭代演算法在一個基本可行解的幾個基矩陣之間循環不止的情況。

所以，保證單純形法收斂的充分條件是：在迭代過程中產生的每個基本可行解的基變數數值都嚴格大於0。

在迭代過程中，如果某一個決策變數的系數都小於0了，這代表什麼？
舉例：

如上圖，我們可以把x2放在等式右邊，看出什麼沒有？x2可以趨於無窮大。

如上圖， 非基變數x4的檢驗數為0了，根據最優性條件，讓其進基並不能繼續優化目標函數值。但是，x4進基後還是會得到一個基本可行解，且目標函數值與當前結果相同。這意味這什麼？
目標不能再優化，但是又有不同的基本可行解，啥意思？說明該問題有無窮多個最優解。

所以， 對於求max的線性規劃問題，如果所有檢驗數均滿足<=0，則說明已經得到了最優解，若此時某非基變數的檢驗數=0，則說明該優化問題有無窮多最優解。

單純形法是從一個初始的基本可行解開始的，出基入基，知道找到最優可行解。
問題是，我們怎麼得到那個初始的基本可行解啊？
最基本的方法是 添加人工變數
假設原問題的約束是這樣的：
x1 + 2x2 + 3x3 = 1
2x + x3 = 2
那麼我們再加兩個變數x4, x5，把約束變成這樣：
x1 + 2x2 + 3x3 + x4 = 1
2x + x3 + x5 = 2
我們就把約束變成了典式，可以直接得到一個基本可行解(0,0,0,1,2)T，找個基本可行解的基變數是x4, x5，那麼接下來的工作就是通過出基入基把x4,x5都變成非基變數，這樣它們的值就可以為0， 從而得到原問題的可行解。
現在有個問題，如果在最優表中，基變數中仍含有人工變數，這說明啥？

這說明，原問題根本就無解。

4. 單純形方法

單純形法是求解線性規劃問題最常用、最有效的演算法之一。

單純形法最早由 George Dantzig於1947年提出，近70年來，雖有許枯歷脊多變形體已經開發，但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在，則一定可以在其可行區域的頂點中找到。基於此，單純形法的基本思路是：先找出可行域的一個頂點，據一定規則判斷其是否最優；若否，則轉換到與之相鄰的另一頂點，並使目標函數值更優；如沒滲此下去，直到找到某最優解為止。

為了用選代法求出線性規劃的最優解，需要解決以下三個問題：

(1)最優解判別准則，即迭代終止的判別標准；

(2)換基運算，即從一個基可行解迭代出另一個基可行解的方法；

(3)進基列的選擇，即選擇合適的列以進行換基運算，可以使目標函數值有較大下降。

改進單純形法：
原單純形法不是很經濟的演算法。1953年美國數學家G.B.丹捷格為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了爛純在計算機上的存儲量。

5. 單純形法的原理

單純形法的原理如下：

首先設法找到一個（初始）基可行解，然後再根據最優性理論判斷這個基可行解是否最優解。若是最優解，則輸出結果，計算停止。

若不是最優解，則設法由當前的基可行解產生一個目標值更搜跡優的新的基可行解，再利用最優性理論對所得的新基可行解進行判斷，看其是否最優解，這樣就構成一個迭代演算法。

由於基可行解只有有限個，而每次目標值都有所改進，因而必可在有限步內終止。如果原問題確有最優解，必可在有限步內達到，且計算量大大少於窮舉法；若原問題無最優解，也可根據最優性理論及時發現，停止計算，避免錯誤及無效運算。坦納"

單純讓漏沒形法是求解線性規劃問題最常用、最有效的演算法之一。單純形法最早由 George Dantzig於1947年提出，近70年來，雖有許多變形體已經開發，但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在，則一定可以在其可行區域的頂點中找到。

基於此，單純形法的基本思路是：先找出可行域的一個頂點，據一定規則判斷其是否最優；若否，則轉換到與之相鄰的另一頂點，並使目標函數值更優；如此下去，直到找到某最優解為止 。