《单纯形方法(simplex method)matlab 仿真详解》由会员分享，可在线阅读，更多相关《单纯形方法(simplex method)matlab 仿真详解（4页珍藏版）》请在金锄头文库上搜索。
1、最近在上最优理论这门课，刚开始是线性规划部分，主要的方法就是单纯形方法，学 完之后做了一下大 M 算法和分段法的仿真，拿出来与大家分享一下。单纯形方法是求解线 性规划问题的一种基本方法。单纯形方法基本步骤如下：1） 将所给的线性规划问题化为标准形式：min( ) . . 0Tf xc x stAxb x s.t.是英文 subject to 的简写，意思是受约束，也就是说第一个方程（目标函数）受到后 面两个方程的约束。 对于求最大值问题可以将目标函数加负号转换为最小值问题。max( )min( )TTf xc xf xc x 其他的问题就是将实际问题中的不等式约束改为等式约束，主要方法是引进松
2、弛变量和剩 余变量，以及将自有变量转换为非负变量。对于不等式，引入松弛变量将其变为等式形式如下： 1b ,1,2,nijji ja ximL1b ,1,2,0,1,2,nijjn ii jn ia xximxim LL对于不等式，引入剩余变量将其变为等式形式如下： 1b ,1,2,nijji ja ximL1b ,1,2,0,1,2,nijjn ii jn ia xximxim LL若变量为自有变量（可取正、负或零，符号无限制） ，则引入两个非负变量将其表示如下：00jjjjjxxxxx 2）找出一个初始可行基 B，作出单纯形表，这里假设输入的线性规划问题已经有初始可行 基。0TcSA b3）
3、测试所有的检验数（目标函数的系数 C） ，记录检验数中的正数，若全部小于等于 0， 则已经找到最优解，计算终止。否则转至否则转至 4） 。 4）测试所有为正的检验数，若在单纯性表中，其所在的列中其他元素全部小于等于 0，则 此问题无最优解，计算终止，否则转至否则转至 5） 。5）找出检验数中的最大值，此最大值元素所在列为 A(i,:)，令约束条件中约束向量b与 A(i,:)的比值为向量 r，向量 r 中为正的最小值为 h，计算过程如下图。S 单纯形 表X1X2X3X4X5f（检验数） 510（最大值）0000X31/141/71001X41/71/120101X5110018表格中黄色部分组成
4、的向量点除（对应元素相除）红色部分，得到向量（7,12,8） ，那么 7 就是我们要找的那个元素，此时记录元素大小 h 和坐标(i,j)，注意是在 S 表中行号和列号， 此处是 2 和 2（如果有多个相等的最小值则任取一个即可） 。 这个元素 1/7 就是所谓的转轴元（或称基本元） ，找到他之后要围绕他进行一系列的行变换， 称之为换基换基。步骤如下： 使转轴元变为 1，方法很简单，就是让本行所有元素同时除以转轴元 1/7。 把转轴元所在列的其他元素都变为 0，做法是通过一个循环，遍历每一个行（自身所在 行除外） ，每行中与转轴元同列的元素为 a，令每行减去转轴元所在行的第 a 倍即可。转至转至
5、 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=siz
6、e(S); %判断检验数 r0); len=length(r); %有大于 0 的检验数则进入循环 while(len)%检查非负检验数所对列向量元素是否都小于等于 0for k=1:length(r)d=find(S(:,r(k)0);if(length(d)+1=2)error(无最优解！) %break;endend%找到检验数中最大值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);len=length(r); end%检验数全部非正，找到最优解%初始化解向量，非基变量置 0x=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)%基变量的值为 S 表基变量所在行最右端的值endendy=S(1,m);%最优解为检验数所在行最右端的数S end
