单纯形法的matlab实现

《单纯形法的matlab实现》由会员分享，可在线阅读，更多相关《单纯形法的matlab实现（10页珍藏版）》请在装配图网上搜索。

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

2、列向量.符号“”表示右端的表达式是左端的定义式 ，即目标函数f的具体形式就是ex. 记A （Pi，P2，.，Pn）令A=（B，N），B为基矩阵，N为非基矩阵，设（o） B 1bx0是基本可行解，在x（0）处的目标函数值cx(0)(cb,Cn) BbCbB-%,其中cB是c中与基变量对应的分量组成的m维行向量；cn是c中与非基变量对应的分量组成的n-m维行向量.现由基本可行解 x（0）出发求解一个改进的基本可行解.Xb设X是任一可行解，则由Ax b得到XnXb B-1b B-1NXn ,在点x处的目标函数值Xbf CX （Cb,Cn）fo（Zj Cj）Xj ,Xnj R其中R是非基变量下标集，Z

3、j CBB-1Pj.2. 单纯形方法计算步骤：首先给定一个初始基本可行解，设初始基为B,然后执行下列主要步骤：（1 ）解BXb b,求得Xb B 1b b,令Xn 0,计算目标函数值f CbXb .（2）求单纯形乘子 W,解wB Cb ,得到w CbB 1 .对于所有非基变量，计算判别数Zj-Cj WjPj Cj.令Zk-Ck max.若Zk-Ck 0,则对于所有非基变量 Zj-Cj 0,对应基变量的判别数总是为零，因此停止计算，现行基本可行解是最优解.否则，进行下一步.（3）解Byk pk，得到yk B 1pk,若yk 0,即yk的每个分量均非正数，则停止计算,问题不存在有限最优解.否则进行

4、步骤（4）（4 ）确定下标r,使brdXk =min yik 0yrkyikXBr为离基变量，Xk为进基变量用Pk替换PBr，得到新的基矩阵B,返回步骤（1 ）3. 单纯形方法表格形式表 fXBXN右 端Xb0Im-1B NB-1bf10r-1CbB N - CnCbB-%表3.1.2（ 略去左端列后的详表）XB1XBrXBmXjxkXB1100y1j%kbiXBr010YrjyrkbrXBm001ymjymkbmf000Zj-CjZk -CkCBb假设b B-1b 0,由上表得Xb b,XN 0.1若CbB- N -Cn 0 ,则现行基本可行解是最优解.1若CbB- N-Cn 0 ,则用主元

5、消去法求改进的基本可行解.先根据bbZk-CkmaRxZj-Cj选择主列，再根据一Jmin 亠yik 0找主行，主元为yk,然后yrkyik进行主元消去，得到新单纯形表.表的最后一行是判别数和函数目标值四. 实验流程图及其 MATLAB实现:1.流程图:初始基本可行解B1 一解BXb b,求得Xb B b b,令Xn 0 ,计算目标函数值f CbXb求单纯形乘子 w,解wB cB ,得到w CbB 1.对于所有非基变量，计算判别数 Zj-Cj WjPj Cj .令 Zk - Ck maRXZj_Cjyk 01rbb确定下标r,使xk=min yrkyikyik0b赋一-以正的大值NyikxB为

6、rJ离基变量,Xk为进基变量用Pk替换PBr，得到新的基矩阵Bc/ rx -rrt f 也 J /古曲（1）程序源代码:fun ctio nx,f=DCmi n(c,A,b,AR,yO,d)% x:最优解% f:目标函数最优值% c:目标函数系数向量% A:系数矩阵% b: m维列向量% AR:松弛变量系数矩阵% y0:基矩阵初始向量% d:补充向量(非目标系数向量 ，为一零向量)N=10000;B=A,AR,b;m, n=size(B);C=c,d;y=y;x=zeros(1,le ngth(c);for k=1:Nk;z=B(:,e nd); % 右端for j=1:n-1t(j)=y*B

7、(:,j)-C(j);% 检验数puNUOA)X so yss唳團ww0 - )ds_p mlljnon -)eLPJL M 山NON -)elpux (Z)6U帀(M)X)6U一七_(pue.?)8HZ %+% pu m puL !3qOHVexTOE t pu puEPH-OJ 令 d)8、(CL)8c)83)0宜Mu-Elldrooq 一pupu _(b-d)8、(d)zd) so zH(d)0v(b-d)8 七ILLLUdOJ %1R州畀娯沪 % 眾BKX% pgM exelubaJLld-e %忌州畀娯沪MHH SINA上pu(2)数值算例:例用单纯形方法解下列问题min Xi -2

8、x2 x3s.t. Xi X2-2X3 X410,2xi -X2 4x38,-Xi 2X2-X34,Xj 0, j 1,2,3,4.引进松弛变量X 5 , X 6 ,问题标准化：minX1 -2x2 X3s.t.X1X2-2X3 X410,2x1-X2 4x3X58,-X12X2 -X3X64.Xj0, j123,4,5,6.(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=00 0; x,f=DCmi n(c,A,b,AR,y0,d)(ii)运行结果:11-2102-1401-

9、12-400k =1t =-12-100f =0B =1.5000001.500002.0000-0.50001.0000-2.0000b =01008141.00000-0.50008.000001.00000.500010.0000000.50002.0000t =0030 0f =-4B =1.5000000.750001.00001.00001.00000k =3t =-2.250000f =-19x =0125f =-192-11.00000-0.50008.000000.50000.25005.000001.00001.000012.00000-1.5000-1.7500五. 总结：在单纯形法求解过程中，每一个基本可行解x都以某个经过初等行变换的约束方程组中的单位矩阵为可行基对于极大化的线性规划问题，先标准化，即将极大化问题变换为极小化问题：max cx min -cx然后利用单纯形方法求解六. 参考文献：