作业1—单纯形法

课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第1页共7页1单纯形法及MATLAB实现单纯形法(simplexmethod)由美国数学家G.B.丹齐克于1947年首先提出来,其基本思路:将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。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,课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第2页共7页2在点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课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第3页共7页3表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,然后进行主元消去,得到新单纯形表.表的最后一行是判别数和函数目标值.4.实验流程图及其MATLAB实现1.流程图:开始初始基本可行解B解bxBB,求得_1bbBxB,令0Nx,计算目标函数值BBxcf0c-zkk求单纯形乘子w,解BcwB,得到1BcwB.对于所有非基变量,计算判别数jjjjjcc-zpw.令}c-{zmaxc-zjjRjkkYN课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第4页共7页42.代码及数值算例:(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);%右端解kkpBy,得到k1kpBy0ky赋ikiyb以正的大值N现行基本可行解是最优解确定下标r,使xk=0minikikikyybybrrrBx为离基变量,kx为进基变量.用kp替换rBp,得到新的基矩阵BNYmin=NN问题不存在有限最优解Y课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第5页共7页5forj=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用单纯形方法解下列问题课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第6页共7页6.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=课程编号14S15C0205课程名称化工设备优化设计学期2016年春学位层次硕士适合专业化工过程机械第7页共7页73t=-2.2500000-1.5000-1.7500f=-19x=0125f=-19五．总结:在单纯形法求解过程中,每一个基本可行解x都以某个经过初等行变换的约束方程组中的单位矩阵为可行基.对于极大化的线性规划问题,先标准化,即将极大化问题变换为极小化问题:cxcx-minmax然后利用单纯形方法求解.