《作业1—单纯形法.doc》由会员分享，可在线阅读，更多相关《作业1—单纯形法.doc（7页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上单纯形法及MATLAB实现单纯形法(simplex method)由美国数学家G.B.丹齐克于1947年首先提出来,其基本思路:将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。1.单纯形法的基本原理单纯形方法的基本思想, 是从一个基本可行解出发, 求一个使目标函数值有所改善的基本可行解; 通过不断改进基本可行解, 力图达到最优基本可行解.对问题 其中A是一个mn矩阵, 且秩为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.单纯形方法表格形式: 表 3.1.1右端010表 3.1.2（3.1.1略去左端列后的详表） 假设, 由上表得. 若, 则现行基本可行解是最优解. 若, 则用主元消去法求改进的基本可行解. 先根据选择主列, 再根据找主行, 主元为, 然后进行主元消去, 得到新单
4、纯形表. 表的最后一行是判别数和函数目标值. 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维列向量%
5、AR: 松弛变量系数矩阵% 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
6、,q); 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) 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
7、 4k = 1t = -1 2 -1 0 0 0f = 0B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 1.5000 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五总结: 在单纯形法求解过程中, 每一个基本可行解x都以某个经过初等行变换的约束方程组中的单位矩阵为可行基. 对于极大化的线性规划问题, 先标准化, 即将极大化问题变换为极小化问题: 然后利用单纯形方法求解. 专心-专注-专业
