前言
最优化算法对偶单纯形法的matlab实现：
要读懂本文代码需要了解：nchoosek，setdiff，eye等函数在matlab中的作用，以及/符号在矩阵运算中的作用。
一、单纯形法表格
在高等教育出版社《最优化方法》一书中提到的单纯形法表格如下图所示：
其中：c为目标函数系数, A为约束方程组系数矩阵, b为约束方程组常数项。
1.1可立即读出最优解和最优值的表格具备的特点
① 中心部位有单位子块
② 右列元素非负
③ 底行相应于单位子块的位置为0
④ 底行其他元素非负
二、对偶单纯形法的步骤（流程图）
三、对偶单纯形法的matlab实现
3.1对偶单纯形法matlab代码
function [xm,fm,noi] = duioudcxf(A,b,c)
%% 介绍
% 对偶单纯形法求解标准形线性规划问题: min cx s.t. Ax=b x>=0
% 输入参数: c为目标函数系数, A为约束方程组系数矩阵, b为约束方程组常数项
% 输出参数: xm为最求解，fm为最优函数值，noi为迭代次数
%% 准备
format rat %元素使用分数表示
[m,n] = size(A); %m约束条件个数, n决策变量数
v=nchoosek(1:n,m); %创建一个矩阵，该矩阵的行由每次从1:n中的n个元素取出k个取值的所有可能组合构成。矩阵 C 包含 m!/((n–m)! m!) 行和 m列
index_Basis=[];
%% 提取可行解所在列
for i=1:size(v,1) %n取m的种类
if A(:,v(i,:))==eye(m) %在中心部位A中取v的第i种取法取出m列判断是否存在m*m大小的单位矩阵
index_Basis=v(i,:); %存在单位矩阵的取法保存在列表index_Basis中
end
end
%% 提取非基变量索引
ind_Nonbasis = setdiff(1:n, index_Basis); %非基变量的索引,返回在1:n中出现而不在index_Basis(即基变量索引中出现的元素)，并从小到大排序
noi=0;
while true
x0 = zeros(n,1);
x0(index_Basis) = b; %初始基可行解
cB = c(index_Basis); %提取基向量在目标函数的系数cB
%% 判断最优解
if ~any(b < 0) %此基可行解为最优解, any存在某个<0
xm = x0;
fm = c'*xm;
return
end
%% 判断问题是否有解
index=find(b<0);
for i = 1:numel(index)
if all(A(index(i),:)>=0) %在b<0的元素,所对应行所有元素都大于0
xm=[];
fm = []; %原问题无可行解，对偶问题存在无界解
return
end
end
%% 选择进基变量，选择离基变量
Sigma = zeros(1,n);
Sigma(ind_Nonbasis) = c(ind_Nonbasis)' - cB'*A(:,ind_Nonbasis); %计算检验数
[~,q] = min(b); %选出b中最小的数
r = index_Basis(q); %确定离基变量索引r
Theta = Sigma ./ A(q,:); %计算b/ai
Theta(Theta>=0) =-1000000; %剔除ai>0的部分
[~,s] = max(Theta); %筛选出最大的b/ai,确定进基变量索引s, 主元为A(q,s)
%% 换基
index_Basis(index_Basis == r) = s; %原先基变量为r的索引更换成新的基变量索引s
ind_Nonbasis = setdiff(1:n, index_Basis); %筛选出非基变量索引
%% 核心——旋转运算
A(:,ind_Nonbasis) = A(:,index_Basis) \ A(:,ind_Nonbasis); %核心——非基变量的部分等于（=）基变量索引的矩阵的逆乘剩余非基变量的矩阵
b = A(:,index_Basis) \ b; %核心——约束方程组常数项(=)基变量索引的矩阵的逆乘原约束方程常数项目
A(:,index_Basis) = eye(m); %核心——基变量索引的矩阵更换成单位矩阵
noi=noi+1;
end
end
3.2测试例题
clc,clear;
A=[-2 -4 -5 -1 1 0 0;
-3 1 -7 2 0 1 0;
-5 -2 -1 -6 0 0 1];
b=[0 -2 -15]';
c=[3 2 1 4 0 0 0]';
[xm,fm,noi] = duioudcxf(A,b,c);
disp('最优解为：');
disp(xm);
disp('最优函数值为：');
disp(fm);
disp('迭代次数为：');
disp(noi);
3.3结果
文章来源：https://www.toymoban.com/news/detail-414832.html
总结
以上就是对偶单纯形法的matlab实现，有什么疑惑的地方可以私信或者评论区提问，需要流程图的也可以私信我。
本文参考的相关文章链接：最优化算法单纯形法的matlab实现（单纯形法看这一篇就够了)文章来源地址https://www.toymoban.com/news/detail-414832.html
到了这里，关于最优化算法对偶单纯形法的matlab实现（对偶单纯形法看这一篇就够了)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
