单纯形法的matlab实现(极小化问题)

实验报告实验题目:单纯形法的matlab实现学生姓名:学号:实验时间:2013-4-15一．实验名称:单纯形法的MATLAB实现二．实验目的及要求:1.了解单纯形算法的原理及其matlab实现.2.运用MATLAB编辑单纯形法程序解决线性规划的极小化问题,求出最优解及目标函数值.三．实验内容:1.单纯形方法原理:单纯形方法的基本思想,是从一个基本可行解出发,求一个使目标函数值有所改善的基本可行解;通过不断改进基本可行解,力图达到最优基本可行解.对问题.0,As.t.defminxbxcxf其中A是一个m×n矩阵,且秩为m,c为n维行向量,x为n维列向量,b为m维非负列向量.符号“def”表示右端的表达式是左端的定义式,即目标函数f的具体形式就是cx.记),...,,(n21pppA令A=(B,N),B为基矩阵,N为非基矩阵,设0B1-)0(bx是基本可行解,在)0(x处的目标函数值bcbcccxf1-B1-NB)0(0B0B),(,其中Bc是c中与基变量对应的分量组成的m维行向量;Nc是c中与非基变量对应的分量组成的n-m维行向量.现由基本可行解)0(x出发求解一个改进的基本可行解.设NBxxx是任一可行解,则由bAx得到N1-1-BNBBxbx,在点x处的目标函数值Rjjjjfxxcccxfx)cz(),(0NBNB,其中R是非基变量下标集,jjpc1-BBz.2.单纯形方法计算步骤:首先给定一个初始基本可行解,设初始基为B,然后执行下列主要步骤:（1）解bxBB,求得_1bbBxB,令0Nx,计算目标函数值BBxcf.（2）求单纯形乘子w,解BcwB,得到1BcwB.对于所有非基变量,计算判别数jjjjjcc-zpw.令}c-{zmaxc-zjjRjkk.若0c-zkk,则对于所有非基变量0c-zjj,对应基变量的判别数总是为零,因此停止计算,现行基本可行解是最优解.否则,进行下一步.（3）解kkpBy,得到k1kpBy,若0ky,即ky的每个分量均非正数,则停止计算,问题不存在有限最优解.否则进行步骤（4）.（4）确定下标r,使xk=0minikikikyybybrr,rBx为离基变量,kx为进基变量.用kp替换rBp,得到新的基矩阵B,返回步骤（1）.3.单纯形方法表格形式:表3.1.1fBxNx右端Bx0mINB-1b-1Bf10N-1Bc-NBcb-1BBc表3.1.2（3.1.1略去左端列后的详表）BmBrB1xxxkjxxmr1BBBxxx100010001mkmjrkrjkjyyyyyy11___1mrbbbf000kkjjc-zc-zbcB假设0B1-bb,由上表得0,NBxbx.若0c-NBcN-1B,则现行基本可行解是最优解.若0c-NBcN-1B,则用主元消去法求改进的基本可行解.先根据}c-{zmaxc-zjjRjkk选择主列,再根据0minikikikyybybrr找主行,主元为rky,然后进行主元消去,得到新单纯形表.表的最后一行是判别数和函数目标值.四．实验流程图及其MATLAB实现:1.流程图:开始初始基本可行解B解bxBB,求得_1bbBxB,令0Nx,计算目标函数值BBxcf0c-zkk解kkpBy,得到k1kpBy0ky赋ikiyb以正的大值N求单纯形乘子w,解BcwB,得到1BcwB.对于所有非基变量,计算判别数jjjjjcc-zpw.令}c-{zmaxc-zjjRjkk现行基本可行解是最优解确定下标r,使xk=0minikikikyybybrrrBx为离基变量,kx为进基变量.用kp替换rBp,得到新的基矩阵BYNNYmin=NN问题不存在有限最优解Y2.代码及数值算例:(1)程序源代码:function[x,f]=DCmin(c,A,b,AR,y0,d)%x:最优解%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;%%========选取主元==========%%%---------选取主列---------%[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=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用单纯形方法解下列问题.43210x4x-2xx-84xx-2x10x-2xxxs.t.xx2-minxj3213214321321，，，，，，，j引进松弛变量x5,x6,问题标准化:.6543210x.4xx-2xx-8x4xx-2x10x-2xxxs.t.xx2-minxj632153214321321，，，，，，，，j(i)输出命令:c=[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.000001.00000.500010.0000-0.50001.0000-2.0000000.50002.0000k=2t=00300-1f=-4B=1.5000001.00000-0.50008.00000.750001.000000.50000.25005.00001.00001.0000001.00001.000012.0000k=3t=-2.2500000-1.5000-1.7500f=-19x=0125f=-19五．总结:在单纯形法求解过程中,每一个基本可行解x都以某个经过初等行变换的约束方程组中的单位矩阵为可行基.对于极大化的线性规划问题,先标准化,即将极大化问题变换为极小化问题:cxcx-minmax然后利用单纯形方法求解.六．参考文献:陈宝林编著《最优化理论与算法》清华大学出版社2005年10月第2版