《单纯形算法MATLAB编程报告.doc》由会员分享，可在线阅读，更多相关《单纯形算法MATLAB编程报告.doc（23页珍藏版）》请在三一文库上搜索。
1、机械优化设计课程作业 题 目： 单纯形程序算法 学 院： 机电工程学院 专 业： 机械工程 姓 名： 郑璐颖 学 号： 2015020287 指导老师： 王玉林 2016年 4 月 24 日基于MATLAB的单纯形算法实现1. 算法简述为求解下面线性规划问题：其中初始可行基为松弛变量对应的列组成. 对于一般标准线性规划问题:求解上述一般标准线性规划的单纯形算法步骤如下：对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤： (1).解,求得，(2).计算单纯形乘子w, ,得到,对于非基变量，计算判别数,可直接计算令 ,R为非基变量集合若判别数
2、 ,则得到一个最优基本可行解，运算结束；否则，转到下一步(3).解,得到；若,即的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使2. 算法框图初始化 初始可行基B 是 否 输出结果，得到最优解结束是否 不存在有限最优解确定下标r,使得 高斯迭代 3 计算程序Clear %清空工作区Clc %清空命令输入框A=input(A=);b=input(b=);c=input(c=);format rat %可以让结果用分数输出m,n=size(A); %取维数 E=1:m;E=E; F=n-m+1:n;F=F;D=E,F; %创建一个一一映射，为了结果能够标准
3、输出X=zeros(1,n); %初始化Xif(nm) %判断是否为标准型 fprintf(不符合标准形式需引入松弛变量) flag=0;else flag=1; B=A(:,n-m+1:n); %找基矩阵 cB=c(n-m+1:n); %基矩阵对应目标值的c while flag w=cB/B %计算单纯形乘子，cB/B=cB*inv(B),左除相当于求逆 panbieshu=w*A-c %计算判别数,后面没有加分号，就是为了计算后能够显示出来 z,k=max(panbieshu) % k作为进基变量下标 fprintf(确定下标并选择进基变量和离基变量为n,k); b./(BA(:,k)
4、%这个式子是为了确定进基变量和离基变量的下标 if(z0.00000000001) %为了使判别数尽可能趋近于零 flag=0; %所有判别数都小于0时达到最优解 fprintf( 已找到最优解!n); xB=(Bb); f=cB*xB; for i=1:n mark=0; for j=1:m if (D(j,2)=i) mark=1; X(i)=xB(D(j,1) %利用D找出xB与X之间的关系 end end if mark=0 X(i)=0; %如果D中没有X(i),则X(i)为非基变量，所以X(i)0 end end fprintf(基向量为:); X fprintf(目标函数值为:)
5、 ; f else if(BA(:,k)0) & (b1(i)/(A(i,k)+eps)temp ) temp=b1(i)/A(i,k); %找离基变量 r=i; end end fprintf(x(%d)进基，x(%d)离基n,k,D(r,2); %显示进基变量和离基变量 B(:,r)=A(:,k) cB(r)=c(k) %确定进基离基变量后，相应的基矩阵及新基对应的目标值的c也相应改变 D(r,2)=k; %改变D中的映射关系 end end endend【备注：文件名字为danchunxing11zly.m】4. 使用方法以及运算实例在命令窗口中输入 run danchunxing11z
6、ly，然后依次按照提示完成约束以及目标函数的矩阵。例1：min S.t 窗口输入 run danchunxing11zly A=1 1 -2 1 0 0;2 -1 4 0 1 0;-1 2 -4 0 0 1; b=10 8 4; c=1 -2 1 0 0 0运行结果为：w = 0 0 0 panbieshu = -1 2 -1 0 0 0 z = 2 k = 2 确定下标并选择进基变量和离基变量为ans = 10 -8 2 x(2)进基，x(6)离基B = 1 0 1 0 1 -1 0 0 2 cB = 0 0 -2 w = 0 0 -1 panbieshu = 0 0 3 0 0 -1 z
7、= 3 k = 3 确定下标并选择进基变量和离基变量为ans = 1/0 4 -2 x(3)进基，x(5)离基B = 1 -2 1 0 4 -1 0 -4 2 cB = 0 1 -2 w = 0 -3/2 -7/4 panbieshu = -9/4 0 0 0 -3/2 -7/4 z = 0 k = 2 确定下标并选择进基变量和离基变量为ans = 1/0 1/0 4 已找到最优解!xB = 8 5 12 f = -19 X = 0 12 0 0 0 0 X = 0 12 5 0 0 0 X = 0 12 5 8 0 0 基向量为:X = 0 12 5 8 0 0 目标函数值为:f = -19
8、 例2： max S.t 命令窗口中输入: run danchunxing11zlyA=1 1 2 1 0;1 4 -1 0 1b=6 4c=-2 -1 1 0 0运行结果为：w = 0 0 panbieshu = 2 1 -1 0 0 z = 2 k = 1 确定下标并选择进基变量和离基变量为ans = 6 4 x(1)进基，x(5)离基B = 1 1 0 1 cB = 0 -2 w = 0 -2 panbieshu = 0 -7 1 0 -2 z = 1 k = 3 确定下标并选择进基变量和离基变量为ans = 2 -4 x(3)进基，x(4)离基B = 2 1 -1 1 cB = 1 -2 w = -1/3 -5/3 panbieshu = 0 -6 0 -1/3 -5/3 z = 0 k = 1 确定下标并选择进基变量和离基变量为ans = 1/0 4 已找到最优解!X = 14/3 0 0 0 0 X = 14/3 0 2/3 0 0 基向量为:X = 14/3 0 2/3 0 0 目标函数值为:f = -26/3