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

1、实验报告实验题目 :单纯形法的matlab 实现学生 :学号:实验时间 :2013-4-15一实验名称 :单纯形法的 MATLAB实现二实验目的及要求 :1.了解单纯形算法的原理及其matlab 实现 .2.运用 MATLAB 编辑单纯形法程序解决线性规划的极小化问题, 求出最优解及目标函数值 .三实验容 :1. 单纯形方法原理 :单纯形方法的基本思想 , 是从一个基本可行解出发 , 求一个使目标函数值有所改善的基本可行解 ; 通过不断改进基本可行解 , 力图达到最优基本可行解 . 对问题minf def cxs.t.Axb,x0.其中 A 是一个 m× n 矩阵 , 且秩为 m,c

2、 为 n 维行向量 , x 为 n 维列向量 , b 为 m 维非负列向量 . 符号“”表示右端的表达式是左端的定义式, 即目标函数f 的具体形式就是 cx .记A ( p1, p2 ,., pn )令 A =(B,N), B 为基矩阵 , N 为非基矩阵 , 设x( 0)B -1b0是基本可行解 , 在 x(0 ) 处的目标函数值f 0 cx( 0)(cB,cN )B-1b-1cB B b ,0其中 cB 是 c 中与基变量对应的分量组成的m 维行向量 ;cN 是 c 中与非基变量对应的分量组成的 n-m 维行向量 .现由基本可行解 x(0)出发求解一个改进的基本可行解.设 xxB是任一可行

3、解 , 则由 Ax b 得到xNxBB-1b B-1N xN ,在点 x 处的目标函数值fcx (cB , cN )xBf 0(z j c j ) x j ,xNj R其中 R 是非基变量下标集,z jcB B-1 p j .2. 单纯形方法计算步骤 :首先给定一个初始基本可行解, 设初始基为 B, 然后执行下列主要步骤:）解 BxBb , 求得 xBB 1b_（1b , 令 xN0 ,计算目标函数值 f cB xB .（2）求单纯形乘子w , 解 wBc B , 得到 wcB B 1. 对于所有非基变量,计算判别数z j - c j w j p jcj . 令zk - ckmaxz j- c

4、j j R.若 zk - ck0 , 则对于所有非基变量z j- cj0, 对应基变量的判别数总是为零, 因此停止计算 , 现行基本可行解是最优解. 否则 , 进行下一步 .（3）解 Bykpk , 得到 ykB 1 pk ,若 yk0, 即 yk 的每个分量均非正数,则停止计算 ,问题不存在有限最优解. 否则进行步骤（4） .（4）确定下标r, 使x k =brminbi yik 0 ,yrkyikxB r 为离基变量,x k 为进基变量 . 用 pk 替换 pB r , 得到新的基矩阵B, 返回步骤（ 1） .3. 单纯形方法表格形式 :表 3.1.1fxBxN右端xBI mB -1NB-

5、1b0fcB B-1 N - cNcB B -1b10表（略去左端列后的详表）xB 1xBrxBmx jxkxB 1100y1 jy1k_b1xB r010yrjyrk_brxB m001ymjymk_bmf000zj - cjzk - ckcB b假设 bB-1b 0 ,由上表得 xB b, xN0 .若 cB B-1 N - cN0, 则现行基本可行解是最优解 .若 cB B -1N - cN0, 则用主元消去法求改进的基本可行解.先 根 据zk - ckmaxz j - cj brbiyik 0找主行 , 主元为 yrk , 然后jR选择主列 , 再根据minyrkyik进行主元消去 ,

6、 得到新单纯形表. 表的最后一行是判别数和函数目标值.四实验流程图及其MATLAB实现 :1. 流程图 :开始初始基本可行解B_解 BxBb , 求得 xBB 1bb , 令 xN0 , 计算目标函数值fcB xB求单纯形乘子 w , 解 wBcB , 得到 w cB B 1. 对于所有非基变量 , 计算判别数 zj - c jw j pj c j . 令zk - ckmaxz j - c jj RNzk - ck0Y解 By kpk , 得到 yk B 1 pk现行基本可行解是最优解NYyk0确定下标 r, 使 x k =brminbi yik 0赋 bi以正的大值 NyrkyikyikNY

7、min=N问题不存在有限最优解x B r 为离基变量 , x k 为进基变量 . 用 pk 替换 pBr , 得到新的基矩阵B2. 代码及数值算例 :(1) 程序源代码 :functionx,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(:,e

8、nd);%右端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);endendbeta,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(

9、:,end);iflength(x(W)=length(Z)x=char('NONE');f=char('NONE');disp('不存在有限最优解' );elsex(W)=Z'end(2) 数值算例 :例用单纯形方法解下列问题minx 1 - 2x 2x 3s.t.x1x 2 -2x3x 4，102x 1 - x 24x3，8- x12x2 - x3，4x j，0j 1 2 3 4.引进松弛变量 x 5 , x6 ,问题标准化 :minx1 - 2x 2x 3s.t.x1x 2-2x3x 4，102x1- x 24x3x5，8- x12

10、x 2 - x3x64.x j，0 j123456.(i) 输出命令 :>> c=1 -2 1;A=1 1 -2 1;2 -1 4 0;-1 2 -4 0;b=10;8;4;AR=0 0;1 0;0 1;y0=0 0 0;d=0 0 0;>> 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