【運籌學】單純形法之大M法和兩階段法
在上一篇文章中，
張敬信：【運籌學】單純形法求解線性規劃問題的Matlab實現
討論了單純形法求解線性規劃問題，但是它需要約束係數矩陣包含一個單位矩陣，對應的變數指定為初始基變數。一般情況下，是不能保證這一點的，因此需要引入人工變數法，即添加人工變數構造出單位矩陣。
求解帶有人工變數的線性規劃問題，通常有兩種方法：大M法和兩階段法。
一、大M法
例如，
引入人工變數
Matlab實現：
不需要重新寫函數，調用上次的 SimplexMax 函數（見上一篇），就能實現。
%% 大M法
M = 10000;
A = [3 2 -3 1 0; 1 -2 1 0 1];
b = [6; 4];
c = [3 -1 -2 -M -M];
ind = [4 5];
[x, z, ST, ca] = SimplexMax(c, A, b, ind)
運行結果：
當然也可以進一步把單純形表 ST 寫入 Excel（見上一篇略）。
註：若運行結果不正確，是中間遇到兩個相同的最小 ,默認的最小下標不對，需要選另一個下標。另外，使用大M法時，需要用最大數代替M，但當某些係數與之較接近時，還是可能會出錯。
二、兩階段法
所以，兩階段法無非就是調用兩次 SimplexMax 函數（見上一篇），從第一次返回結果中，取出需要的信息用於第二次的輸入，把這個銜接做好即可。
例如，
注意：原問題目標函數無論是求MAX還是求MIN，構造的 第一階段問題目標函數都是求最小MIN。
用單純形法求解若所得可行解目標函數值為0，表明原規劃問題有基可行解。轉入第二步：去掉人工變數，得到第二階段的單純形表，繼續用單純形法求解。
Matlab實現：
%% 第一階段
A1 = [1 1 -1 0 0 1 0; 1 0 0 -1 0 0 1; 2 1 0 0 1 0 0];
b1 = [350; 125; 600];
c1 = [0 0 0 0 0 -1 -1];
ind1 = [6 7 5];
[x1, z1, ST1, ca1] = SimplexMax(c1, A1, b1, ind1)
運行結果：
%% 第二階段
A2 = ST1(end-m1:end-1,4:end-3); %2個人工變數, 2+1
b2 = ST1(end-m1:end-1,3);
c2 = [-2 -3 0 0 0];
ind2 = ST1(end-m1:end-1,2);
[x2, z2, ST2, ca2] = SimplexMax(c2, A2, b2, ind2)
運行結果：
也可以進一步，把兩個單純形表 ST1 和 ST2 寫入一個 Excel文件（注意錯開位置，略）。
————————————————————————————
主要參考文獻：
胡運權，運籌學原理及應用（第六版），及其課件
————————————————————————————————
原創作品，轉載請註明，版權所有，禁止盜用。
推薦閱讀：
