资源描述：
《单纯形法matlab实现(极小化问题)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、实验报告实验题目:单纯形法的matlab实现学生姓名:学号:实验时间:2013-4-15一．实验名称:单纯形法的MATLAB实现二．实验目的及要求:1.了解单纯形算法的原理及其matlab实现.2.运用MATLAB编辑单纯形法程序解决线性规划的极小化问题,求出最优解及目标函数值.三．实验内容:1.单纯形方法原理:单纯形方法的基本思想,是从一个基本可行解出发,求一个使目标函数值有所改善的基本可行解;通过不断改进基本可行解,力图达到最优基本可行解.对问题其中A是一个m×n矩阵,且秩为m,为n维行向量,为n维列向量,
2、为m维非负列向量.符号“”表示右端的表达式是左端的定义式,即目标函数的具体形式就是.记令=(B,N),B为基矩阵,N为非基矩阵,设是基本可行解,在处的目标函数值,其中是中与基变量对应的分量组成的m维行向量;是中与非基变量对应的分量组成的n-m维行向量.现由基本可行解出发求解一个改进的基本可行解.设是任一可行解,则由得到,在点处的目标函数值,其中R是非基变量下标集,.1.单纯形方法计算步骤:首先给定一个初始基本可行解,设初始基为B,然后执行下列主要步骤:（1）解,求得,令,计算目标函数值.（2）求单纯形乘子,解,
3、得到.对于所有非基变量,计算判别数.令.若,则对于所有非基变量,对应基变量的判别数总是为零,因此停止计算,现行基本可行解是最优解.否则,进行下一步.（3）解,得到,若,即的每个分量均非正数,则停止计算,问题不存在有限最优解.否则进行步骤（4）.（4）确定下标r,使x=,为离基变量,为进基变量.用替换,得到新的基矩阵B,返回步骤（1）.1.单纯形方法表格形式:表3.1.1右端010表3.1.2（3.1.1略去左端列后的详表）假设,由上表得.若,则现行基本可行解是最优解.若,则用主元消去法求改进的基本可行解.先根据
4、选择主列,再根据找主行,主元为,然后进行主元消去,得到新单纯形表.表的最后一行是判别数和函数目标值.四．实验流程图及其MATLAB实现:1.流程图开始:初始基本可行解B解,求得,令,计算目标函数值求单纯形乘子,解,得到.对于所有非基变量,计算判别数.令YN解,得到现行基本可行解是最优解NY确定下标r,使x=赋以正的大值NYNmin=N问题不存在有限最优解为离基变量,为进基变量.用替换,得到新的基矩阵B2.代码及数值算例:(1)程序源代码:function[x,f]=DCmin(c,A,b,AR,y0,d)%x:
5、最优解%f:目标函数最优值%c:目标函数系数向量%A:系数矩阵%b:m维列向量%AR:松弛变量系数矩阵%y0:基矩阵初始向量%d:补充向量（非目标系数向量,为一零向量）N=10000;B=[A,AR,b];[m,n]=size(B);C=[c,d];y=y0;x=zeros(1,length(c));fork=1:Nk;z=B(:,end);%右端forj=1:n-1t(j)=y*B(:,j)-C(j);%检验数endt;f=y*z;%%========选取主元==========%%%---------选取主
6、列---------%[alpha,q]=max(t);q;W(k)=q;%x下标矩阵%-------------------------%%--------选取主元----------%forp=1:mifB(p,q)<=0r(p)=N;elser(p)=z(p)/B(p,q);endend[beta,p]=min(r);p;y(p)=C(q);%-------------------------%%%==========================%%B(p,:)=B(p,:)/B(p,q);fori=
7、1:mifi~=pB(i,:)=B(i,:)-B(p,:)*B(i,q);endendifmax(t)<=0break;endB;end%++++++++++++++++++++++++++++++++++++++%Z=B(:,end);iflength(x(W))~=length(Z)x=char('NONE');f=char('NONE');disp('不存在有限最优解');elsex(W)=Z';end(2)数值算例:例3.1.2用单纯形方法解下列问题引进松弛变量x,x,问题标准化:(i)输出命令:>>c
8、=[1-21];A=[11-21;2-140;-12-40];b=[10;8;4];AR=[00;10;01];y0=[000];d=[000];>>[x,f]=DCmin(c,A,b,AR,y0,d)(ii)运行结果:B=11-2100102-140108-12-40014k=1t=-12-1000f=0B=1.5000001.00000-0.50008.00001.500002.0
