最优化算法单纯形法的matlab实现(单纯形法看这一篇就够了)
最优化算法——单纯形法,看这一篇就够了。有疑惑的小伙伴可以评论区提问,觉得该文章对你有帮助的小伙伴可以点赞收藏。
文章共1,596字 · 阅读需要大约6分钟
一键AI生成摘要,助你高效阅读
问答
·
前言
最优化算法单纯形法的matlab实现:
要读懂本文代码需要了解:nchoosek,setdiff,eye等函数在matlab中的作用,以及/符号在矩阵运算中的作用。
一、单纯形法表格
在高等教育出版社《最优化方法》一书中提到的单纯形法表格如下图所示:
其中:c为目标函数系数, A为约束方程组系数矩阵, b为约束方程组常数项。
1.1可立即读出最优解和最优值的表格具备的特点
① 中心部位有单位子块
② 右列元素非负
③ 底行相应于单位子块的位置为0
④ 底行其他元素非负
二、单纯形法的步骤(流程图)
三、单纯形法的matlab实现
3.1单纯形法matlab代码
function [xm,fm,noi] = dcxf(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) %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,即目标函数在基变量处对应的系数
Sigma = zeros(1,n); %Sigma为检验数向量
Sigma(ind_Nonbasis) = c(ind_Nonbasis)' - cB'*A(:,ind_Nonbasis); %计算检验数(非基变量),因为基变量对应的初始检验数一定为0
[~, s] = min(Sigma); %选出最大检验数, 确定进基变量索引s;~表示忽略第一个参数(即最大值),s是索引
Theta = b ./ A(:,s); %计算b/ai(点除)
Theta(Theta<=0) = 10000;
[~, q] = min(Theta); %选出最小θ
q = index_Basis(q); %确定出基变量在系数矩阵中的列索引el, 主元为A(q,s)
%% 判断是否是最优解
if ~any(Sigma < 0) %所有检验数都小于0,此基可行解为最优解, any表示存在某个检验数>0
xm = x0;
fm = c' * xm; %算出最优解
return
break
end
%% 判断是否有解
if all(A(:,s) <= 0) %表示检验数这一列每个数都<=0,有无界解
xm = [];
break
end
%% 换基
index_Basis(index_Basis == q) = 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,m); %核心——基变量索引的矩阵更换成单位矩阵
noi=noi+1;
end
end
3.2测试例题
clc,clear;
A=[ 1 1 1 1 0 0;
2 1 -1 0 1 0;
-1 3 0 0 0 1];
b=[12 6 9]';
c=[-1 2 -1 0 0 0]';
[xm,fm,noi] = dcxf(A,b,c);
disp('最优解为:');
disp(xm);
disp('最优函数值为:');
disp(fm);
disp('迭代次数为:');
disp(noi);
3.3结果
总结
以上就是单纯形法的matlab实现,有什么疑惑的地方可以私信或者评论区提问,需要流程图的也可以私信我。
本文参考的相关文章链接:运筹学—单纯形法matlab实现
更多推荐
已为社区贡献1条内容
所有评论(0)