自由模板最优化方法课程论文.doc
《自由模板最优化方法课程论文.doc》由会员分享，可在线阅读，更多相关《自由模板最优化方法课程论文.doc（14页珍藏版）》请在冰点文库上搜索。
四川理工学院
《最优化方法》课程论文
题目：
线性规划的单纯形算法
姓名：
专业：
统计学
班级：
2011级1班
学号：
完成日期：
2014年6月27日
四川理工学院理学院
二O一四年六月
摘要
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。
是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。
为了得到线性目标函数的极值，我们有多重方法。
本文采用单纯性算法求解线性规划问题，并通过Matlab软件编写程序进行求解。
关键词：
线性规划单纯性算法Matlab编程
目录
一、单纯性方法简介 1
1.1单纯性方法提出 1
1.2单纯性方法的基本思想和步骤 1
1.2.1基本思想 1
1.2.2计算步骤 1
二、问题的提出与分析 1
2.1问题提出 1
2.2问题分析 2
三、程序设计 2
3.1算法设计 2
3.2算法框图 3
3.3程序编制 4
四、结果分析 6
4.1设计结果 6
4.2进一步讨论和验证 8
五、结束语 8
5.1设计的优缺点 8
5.2收获与总结 9
参考文献 10
附录 11
一、单纯性方法简介
1.1单纯性方法提出
单纯形法，求解线性规划问题的通用方法。
单纯形是美国数学家G.B.丹齐克于1947年首先提出来的,这是20世纪数学界最重大的成果之一。
由于这一方法的有效性，几十年来一直在几乎所有的领域得到广泛应用。
它的理论根据是：
线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。
顶点所对应的可行解称为基本可行解。
1.2单纯性方法的基本思想和步骤
1.2.1基本思想
单纯形法的基本思想是：
先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。
因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。
如果问题无最优解也可用此法判别。
1.2.2计算步骤
1、对于一般的的线性规划，将其化为标准型；
2、求出初始基本可行解；
3、先检验其最优性；
4、如果不是最优的，则从取负值的非基变量中选取一个最负确定为入基变量；
5、选好入基变量后，再在基变量中选取一个出基变量；
6、选好入基变量和出基变量后，进行高斯消去，得到新的可行解；
7、重复以上过程，直至找到最优解。
、
二、问题的提出与分析
2.1问题提出
本文运用单纯性算法求解下列问题：
Max
s.t
并编写MATLAB程序求解。
2.2问题分析
在用单纯性算法解决现行规划问题时，我们通常考察标准形现行规划问题，其标准形如下：
现在将本文所讨论的线性规划化为标准线性规划的形式：
Min
S.t.
其中
A=[230100
024010
325001]
，
三、程序设计
3.1算法设计
1、解，求得，令，计算目标函数值,以记的第i个分量；
2、计算单纯性乘子w，,得到,对于非基变量，计算判别系数，令，R为非基变量集合，若判别系数，则得到一个最基本可行解，运算结束；否则，转到下一步
3、解，得到；若，即的每一个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤4;
4、确定下标r，使，为出基变量，为入基变量，用替换，得到新的基矩阵B，返回步骤1。
3.2算法框图
开始
初始可行解
令
计算单纯形乘子，计算判别数（非基变量）令
是
得到最优解
解方程，得到。
否
是
不存在有限最优解
确定下标，是
否
为进基变量，用替换，得到新的基矩阵
3.3程序编制
A=input（'A='）;
b=input（'b='）;
c=input（'c='）;
formatrat
[m,n]=size（A）;
E=1:
m;E=E';
F=n-m+1:
n;F=F';
D=[E,F];
X=zeros（1,n）;
if（nfprintf（'不符合要求需引入松弛变量'）
flag=0;
else
flag=1;
B=A（:
n-m+1:
n）;
cB=c（n-m+1:
n）;
whileflag
w=cB/B;
panbieshu=w*A-c
[z,k]=max（panbieshu）;
fprintf（'b''./（B\\A（:
%d））为',k）;
b'./（B\A（:
k））
if（z<0.000000001）
flag=0;
fprintf（'已找到最优解!
\n'）;
xB=（B\b'）';
f=cB*xB';
fori=1:
n
mark=0;
forj=1:
m
if（D（j,2）==i）
mark=1;
X（i）=xB（D（j,1））;
end
end
ifmark==0
X（i）=0;
end
end
fprintf（'基向量为:
'）;X
fprintf（'目标函数值为:
'）;f
else
if（B\A（:
k）<=0）
flag=0;
fprintf（'\n此问题不存在最优解!
\n'）;else
b1=B\b';
temp=inf;
fori=1:
m
if（（A（i,k）>0）&&（b1（i）/（A（i,k）+eps））temp=b1（i）/A（i,k）;r=i;
end
end
fprintf（'x（%d）进基，x（%d）退基\n',k,D（r,2））;B（:
r）=A（:
k）;
cB（r）=c（k）;
D（r,2）=k;
end
end
end
end
四、结果分析
4.1设计结果
在命令窗口中输入：
A=[2,3,0,1,0,0;0,2,4,0,1,0;3,2,5,0,0,1]
b=[1200,800,2000]
得到如下结果:
我们可以看到，程序经过4次换基迭代，得到目标函数的最优值为-2600，即目标函数的最小值为-2600。
从而，原问题的最大值为2600。
4.2进一步讨论和验证
对于MATLAB程序的正确性与软件运行的可行性。
由于计算量并不是很大，我们通过单纯性表进行手工计算。
经过几次换基迭代，我们选取的入基变量和出基变量与以上软件运行过程得到的结果完全相同。
由此，我们可以认定目标函数的最小值为-2600，即原问题的最大值为2600。
五、结束语
5.1设计的优缺点
设计优点：
1、设计的程序是根据课本的步骤编写的；
2、程序的编制能得到正确结果；
3、编制的程序得到的结果中具体体现每一步的出基变量与入基变量，清晰明了；
设计缺点：
1、不能直观的反应迭代步数，如若迭代次数过多，则想要了解迭代步数则比较麻烦；
2、不能给出完整的单纯性表。
5.2收获与总结
通过本次课程论文设计，让我对单纯性法有了进一步的了解，明确了它的具体思想理论，算法步骤。
此外，通过此次课程设计，初次接触了MATLAB软件，让我对MATLAB软件有了初步的了解，此次论文的完成，主要是通过根据算法设计，编制MATLAB程序，通过MATLAB软件对模型求解。
因此，此次设计的最大问题在于怎样设计算法程序，但这对于我们来说难度还是比较大，所以，此次的单纯性算法程序直接利用网上给出的算法程序进行设计。
但网上的很多程序也存在很多问题，需要在一次一次的错误中不断的更正问题，直到最后得到模型正确的结果。
由于对MATLAB软件的不了解，对于程序设计的优缺点不是很明白。
而对于以后，还是希望能多学习一下软件的知识，能够深入了解一下软件的程序设计以及问题分析。
参考文献
[1][精通MATLAB最优化计算（第二版）]龚纯等
[2]
升级会员 