当前位置:首页 >> 信息与通信 >>

单纯形方法(Simplex Method)Matlab 仿真详解


最近在上最优理论这门课,刚开始是线性规划部分,主要的方法就是单纯形方法,学完 之后做了一下大 M 算法和分段法的仿真,拿出来与大家分享一下。单纯形方法是求解线性 规划问题的一种基本方法。单纯形方法基本步骤如下: 1) 将所给的线性规划问题化为标准形式:

min f ( x) ? cT x s.t. Ax ? b x?0
s.t.是英文 subjec

t to 的简写,意思是受约束,也就是说第一个方程(目标函数)受到后 面两个方程的约束。 对于求最大值问题可以将目标函数加负号转换为最小值问题。

max f ( x) ? cT x?min f ( x) ? ?cT x
其他的问题就是将实际问题中的不等式约束改为等式约束, 主要方法是引进松弛变量和剩余 变量,以及将自有变量转换为非负变量。
n

①对于不等式

?a x
j ?1 ij

j

? bi , i ? 1, 2,? m , 引入松弛变量将其变为等式形式如下:

?a x
j ?1 ij
②对于不等式

n

j

? xn ?i ? bi , i ? 1, 2,? m i ? 1, 2,? m

xn ?i ? 0,

?a x
j ?1 ij

n

j

? bi , i ? 1, 2,? m , 引入剩余变量将其变为等式形式如下:

?a x
j ?1 ij

n

j

? xn ?i ? bi , i ? 1, 2,? m i ? 1, 2,? m

xn ?i ? 0,

③若变量为自有变量(可取正、负或零,符号无限制) ,则引入两个非负变量将其表示如下:

? x j ? x?j ? x?? j ? ? x?j ? 0 ? ?? ?x j ? 0
2)找出一个初始可行基 B,作出单纯形表,这里假设输入的线性规划问题已经有初始可行 基。

? cT 0 ? S?? ? A b? ? ?
3)测试所有的检验数(目标函数的系数 C) ,记录检验数中的正数,若全部小于等于 0,则 已经找到最优解,计算终止。否则转至 4) 。 4)测试所有为正的检验数,若在单纯性表中,其所在的列中其他元素全部小于等于 0,则 此问题无最优解,计算终止,否则转至 5) 。 5) 找出检验数中的最大值, 此最大值元素所在列为 A(i,:), 令约束条件中约束向量 b 与 A(i,:) 的比值为向量 r,向量 r 中为正的最小值为 h,计算过程如下图。 S 单纯形表 X3 X4 X5 X1 1/14 1/7 1 X2 1/7 1/12 1 X3 1 0 0 X4 0 0 1 0 X5 0 0 0 1 0 1 1 8 f(检验数) 5 10(最大值) 0

表格中黄色部分组成的向量点除(对应元素相除)红色部分,得到向量(7,12,8) ,那么 7 就是我们要找的那个元素,此时记录元素大小 h 和坐标(i,j),注意是在 S 表中行号和列号, 此处是 2 和 2(如果有多个相等的最小值则任取一个即可) 。 这个元素 1/7 就是所谓的转轴元(或称基本元) ,找到他之后要围绕他进行一系列的行变换, 称之为换基。步骤如下: ①使转轴元变为 1,方法很简单,就是让本行所有元素同时除以转轴元 1/7。 ②把转轴元所在列的其他元素都变为 0,做法是通过一个循环,遍历每一个行(自身所在行 除外) ,每行中与转轴元同列的元素为 a,令每行减去转轴元所在行的第 a 倍即可。转至 3) 。 理论部分到此为止,大家有不懂的再去百度或者查书吧。。 。 matlab 仿真程序编写: 此程序假设输入的问题已经有了基本可行解! %Simplex Method function [x,y]=Simplex(f,A,b) %输入 f 是检验数的数组,1*n 维 %输入 A 是约束矩阵, m*n 维 %输入 b 是约束向量, 1*m 维 %输出 x 是解向量 %输出 y 是最优解

%判断输入维数是否相符 %做初始单纯形表 format rat %将结果以分数表示 S=[f 0;A b']; [n,m]=size(S); %判断检验数 r<=0 r=find(f>0); len=length(r); %有大于 0 的检验数则进入循环 while(len) %检查非负检验数所对列向量元素是否都小于等于 0 for k=1:length(r) d=find(S(:,r(k))>0); if(length(d)+1==2) error('无最优解!!') ! %break; end end %找到检验数中最大值 [Rk,j]=max(S(1,1:m-1)); %b 与最大值所在列的比值 rb=S(2:n,m)./S(2:n,j); %把比值中的负数都变无穷,便于寻找最小正值 for p=1:length(rb) if(rb(p)<0) rb(p)=Inf; end end [h,i]=min(rb);%列向量比值最小值 % i+1 为转轴元行号(在 S 中),j 为转轴元列号 i=i+1; %进行换基,转轴元置 1 S(i,:)=S(i,:)./S(i,j); %转轴元所在列其他元素都置 0 for k=1:n if(k~=i) S(k,:)=S(k,:)-S(i,:)*S(k,j); end end %判断检验数 r<=0 r=find(S(1,1:m-1)>0); len=length(r); end %检验数全部非正,找到最优解

%初始化解向量,非基变量置 0 x=zeros(1,m-1); for i=1:m-1 %找到基变量,每列中只有一个 1,其他全为 0,则 1 为基变量 j=find(S(:,i)==1);%每列中 1 的个数 k=find(S(:,i)==0);%每列中 0 的个数 if((length(j)+1==2)&&(length(k)+1==n)) %i 为基变量列号,j 是行号 x(i)=S(j,m);%基变量的值为 S 表基变量所在行最右端的值 end end y=S(1,m);%最优解为检验数所在行最右端的数 S end


相关文章:
毕业论文—基于单纯形法的PID控制器参数优化设计
MATLAB 环境下的仿真结果表明, 寻优后的系统具有...关键字:PID;单纯形法;MATLAB;目标函数 Design of ...The simplex method, which is usually applied to ...
线性规划单纯形法matlab解法
线性规划单纯形法matlab解法_数学_自然科学_专业资料。线性规划单纯形法matlab解法线性规划单纯形法 matlab 解法 %单纯形法 matlab 程序-ssimplex % 求解标准型线性...
单纯形法matlab程序
单纯形法matlab程序_自然科学_专业资料。用matlab程序写单纯形法只用最基本的循环,加减乘除运算,没有打包程序的应用便于比较运算量和存储空间 ...
单纯形法的matlab实现(极小化问题)
单纯形法matlab实现(极小化问题)_数学_自然科学_专业资料。单纯型算法 最优化 实验报告 实验题目: 学生姓名: 学号: 单纯形法matlab 实现 实验时间: 2013-...
作业1—单纯形法
作业1—单纯形法_院校资料_高等教育_教育专区。课程编号 14S15C0205 学位层次 ...单纯形法及 MATLAB 实现单纯形法(simplex method)由美国数学家 G.B.丹齐克于 ...
单纯形法matlab程序
单纯形法matlab程序_计算机软件及应用_IT/计算机_专业资料。function Z=dcxf(c,A,N) %定义函数名称为dcxf。 l=length(N); CB=c(N(1):N(l)) [m,n]...
单纯形法及其应用
关键词:单纯形法;单纯形表;最优性 The Simplex Method and its Application ...的准确性.用计算机辅助运算单纯形法方法有利用 Excel 软件或利用 MATLAB 实现...
matlab通信仿真常用函数
matlab通信仿真常用函数_信息与通信_工程科技_专业资料。matlab通信仿真常用函数的...(旧版) fminunc 拟牛顿法求多变量函数极小值点 fminsearch 单纯形法求多变量...
实验报告(单纯形法的matlab程序)
实验报告(单纯形法的matlab程序)_数学_自然科学_专业资料。实验一:线性规划单纯形算法一、实验目的通过实验熟悉单纯形法的原理,掌握 Matlab 循环语句的应用,提高编 ...
单纯形表格法:simplexTab
转步骤 2. σk 程序: 单纯形表格 MATLAB 程序: simplexTab MATLAB 优化库函数都是以最小化为标准,所以 simplexTab ( mat, numFreeVar ) 程序 也以最小...
更多相关标签:
simplex method | simplex method算法 | dual simplex method | simplex method wiki | 单纯形法例题详解 | 对偶单纯形法例题详解 | 单纯形法例题详解ppt | 单纯形法迭代原理详解 |