二. 對偶單純形法的 Matlab 實現

演算法步驟與單純形法基本是類似的，除了進出基的判斷規則有變化，所以，對 SimplexMax 函數稍加修改即可。

優點：

1. 代碼採用向量化Matlab語言實現，非常簡潔；
2. 可以把整個單純形表直接保存下來，再輸出到Excel非常方便。

缺點（歡迎指正）：

1. 各種特殊解的情況，暫時沒有討論全面；
2. 測

function [x,z,ST,res_case] = DualSimplexMax(c,A,b,ind_B)
% 對偶單純形法求解標準形線性規劃問題: max cx s.t. Ax <= b x>=0
% 輸入參數: c為目標函數係數, A為約束方程組係數矩陣, b為約束方程組常數項, ind_B為基變數索引
% 輸出參數: x最優解, z最優目標函數值, ST存儲單純形表數據, res_case=0表示有最優解

[m,n] = size(A); %m約束條件個數, n決策變數數
ind_N = setdiff(1:n, ind_B); %非基變數的索引
ST = [];
format rat
% 循環求解
while true
x0 = zeros(n,1);
x0(ind_B) = b; %初始基可行解
cB = c(ind_B); %計算cB
Sigma = zeros(1,n);
Sigma(ind_N) = c(ind_N) - cB*A(:,ind_N); %計算檢驗數
[~,q] = min(b); %選出最小的b
r = ind_B(q); %確定出基變數索引r
Theta = Sigma ./ A(q,:); %計算θ
Theta(Theta<=0) = 10000;
[~,s] = min(Theta); %確定進基變數索引s, 主元為A(q,s)
vals = [cB,ind_B,b,A];
vals = [vals; NaN, NaN, NaN, Sigma];
ST = [ST; vals];
if ~any(b < 0) %此基可行解為最優解, any存在某個>0
x = x0;
z = c * x;
res_case = 0;
return
end
% 換基
ind_B(ind_B == r) = s; %新的基變數索引
ind_N = setdiff(1:n, ind_B); %非基變數索引
% 更新A和b
A(:,ind_N) = A(:,ind_B) A(:,ind_N);
b = A(:,ind_B) b;
A(:,ind_B) = eye(m,m);
end

測試實例：

改寫為目標最大化，並化為標準型：

A = [-2 -4 0 1 0; -2 0 -5 0 1];
b = [-2; -3];
c = [-12 -16 -15 0 0];
ind = [4 5];
[x, z, ST, ca] = DualSimplexMax(c, A, b, ind)

運行結果：

也可以進一步將對偶單純形表 ST 寫入Excel（略）。

主要參考文獻：

胡運權，運籌學原理及應用（第六版），及其課件

對偶單純形法詳解，百度文庫

[圖文]對偶單純形法詳解 - 百度文庫?

wenku.baidu.com

————————————————————————————————

原創作品，轉載請註明，版權所有，禁止盜用。

推薦閱讀：