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

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

2、表示右端的表达式是左端的定义式, 即目标函数的具体形式就是.记令=(B,N), B为基矩阵, N为非基矩阵, 设是基本可行解, 在处的目标函数值,其中是中与基变量对应的分量组成的m维行向量; 是中与非基变量对应的分量组成的n-m维行向量. 现由基本可行解出发求解一个改进的基本可行解. 设是任一可行解, 则由得到, 在点处的目标函数值, 其中R是非基变量下标集, . 2. 单纯形方法计算步骤: 首先给定一个初始基本可行解, 设初始基为B, 然后执行下列主要步骤: （1） 解, 求得, 令, 计算目标函数值. （2） 求单纯形乘子, 解, 得到. 对于所有非基变量, 计算判别数. 令. 若, 则对

3、于所有非基变量, 对应基变量的判别数总是为零, 因此停止计算, 现行基本可行解是最优解. 否则, 进行下一步. （3） 解, 得到, 若, 即的每个分量均非正数, 则停止计算, 问题不存在有限最优解. 否则进行步骤（4）. （4） 确定下标r, 使x=, 为离基变量, 为进基变量. 用替换, 得到新的基矩阵B, 返回步骤（1）. 3. 单纯形方法表格形式: 右端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: 最优解% f: 目标函数最优值% c: 目标函数系数向量% A: 系数矩阵% b: m维列向量% AR: 松弛变

5、量系数矩阵% y0: 基矩阵初始向量% d: 补充向量（非目标系数向量, 为一零向量）N=10000;B=A,AR,b;m,n=size(B);C=c,d;y=y0;x=zeros(1,length(c);for k=1:N k; z=B(:,end);%右端 for j=1:n-1 t(j)=y*B(:,j)-C(j);%检验数 end t; f=y*z; %=选取主元=% %-选取主列-% alpha,q=max(t); q; W(k)=q;%x下标矩阵 %-% %-选取主元-% for p=1:m if B(p,q)<=0 r(p)=N; else r(p)=z(p)/B(p,q)

6、; end end beta,p=min(r); p; y(p)=C(q); %-% %=% B(p,:)=B(p,:)/B(p,q); for i=1:m if i=p B(i,:)=B(i,:)-B(p,:)*B(i,q); end end if max(t)<=0 break; end B;end%+%Z=B(:,end);if length(x(W)=length(Z) x=char(' NONE');f=char(' NONE');disp(' 不存在有限最优解');else x(W)=Z'end(2) 数值算例:例 3.

7、1.2 用单纯形方法解下列问题 引进松弛变量x, x, 问题标准化: (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 = 1 1 -2 1 0 0 10 2 -1 4 0 1 0 8 -1 2 -4 0 0 1 4k = 1t = -1 2 -1 0 0 0f = 0B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 1.5000

8、 0 2.0000 0 1.0000 0.5000 10.0000 -0.5000 1.0000 -2.0000 0 0 0.5000 2.0000k = 2t = 0 0 3 0 0 -1f = -4B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 0.7500 0 1.0000 0 0.5000 0.2500 5.0000 1.0000 1.0000 0 0 1.0000 1.0000 12.0000k = 3t = -2.2500 0 0 0 -1.5000 -1.7500f = -19x = 0 12 5f = -19五总结: 在单纯形法求解过程中, 每一个基