最优化课程论文

最优化课程论文

ID:33041773

大小:67.02 KB

页数:3页

时间:2019-02-19

最优化课程论文_第1页
最优化课程论文_第2页
最优化课程论文_第3页
资源描述:

《最优化课程论文》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、求解线性规划的单纯形法摘要:线性规划就是用数学为工具,来研究一定限制条件下,如何实现某一线性目标最优化。单纯形法是求解线性规划的主要算法,文章从单纯形法的思想出发,详细论述了单纯形法的主体步骤,并借助单纯形表通过例题加以说明。求解思路是:通过添加人工变量使得标准化后的系数矩阵一定含有单位矩阵,从而得到一组基变量和初始基木可行解。由于人工变量是人为添加的,为了不改变原问题,在目标函数中消去人工变量,并将人工变量由初始的基变量化成非基变量,使之取值为零,然后用普通单纯形法求解。关键词:线性规划;单纯形法;单纯形表;步骤1.迭代原理从一个

2、初始的基本可行解出发,经过判断,如果是最优解,则结束;否则经过基变换得到另一个目标函数值改善的基木可行解,如此一肓进行下去,肓到找到最优解。2.迭代步骤第1步:求初始基可行解,列出初始单纯形表。第2步:最优性检验。第3步:从一个基本可行解转换到相邻的目标函数值更大的基木可行解,列出新的单纯形表。第4步:重复第2、3步,一直到计算结束为止。2.1确定初始基本可行解由于可行解是由一个可行基决定的,因此,确定初始基可行解X0相当于确定一个初始可行基B0。确定方法:若系数矩阵A中含单位矩阵I,则取BO=I;若A中不含I,则可用人工变量法构造

3、一个I。2.2最优性检验用口标来检验解的优劣。在A屮取定一个基矩阵B,则决策向量X可分块为!〃,相应的价格向量C也分块为(CBCN),把这个分块矩阵的形式乘岀来,就是Z=CX=(CBCN)!〃=CBXB+CNXN,不妨设B表示A中的前m列,则可记A=(BN),其中N为非基矩阵,约朿中的AX=b可表示为(BN))!〃=b,即XB=B-lb-B-lNXN经整理得Z=CB(B-lb-B-INXN)+CNXN,=CBB-lb+(CN—CBB—IN)XN在这个式子屮不难分析出,后边一项XN的系数CN—CBB—1N,当这个向量均为W0分量时,这

4、时只有当XN取0时,使Z值最大,也就是当XN统统取0时的这个基本可行解是最优的,而当这个系数向量其中有某分量是>0的时候,我们可以分析得到,当前XN统统取0的这个基木可行解不是最优,因此,我们可以用XN的系数向量CN-CBB—17的符号来判断当前基可行解是不是最优,把这个系数向量叫做检验数向量,记为8,当5W0时,当前解为最优解。最优性检验的方法:(1)计算每个变量xj的检验数5j=Cj-CBB-lPj,其中Pj为A中的第j列;(2)若所有5jW0,贝U当前解为最优;否则,如果至少有一个5j>0,当前解不是最优,转入第三步。2.3寻

5、找更好的基本可行解由于基本可行解与基对应,即寻找一个新的基可行解,相当于从上一个基B0变换为下一个新的基B1,因此,本步骤也可称为基变换。在基变换的过程中要遵循这样的原则:保证改善目标,再者保证基变换后的解可行。具体变换的方法就是将系数矩阵A=(P1,P2,……Pi……Pk……Pn)中非基向量部分的某一列和基向量中的某一列互换,而且每次只换一列,在基向量的行列中出去一个进一个,这个基变换的过程就是确定进基出基。具休方法:首先决定进基,令正检验数中最大的那个所对应的Pk进基;然后决定出基,令检验比9i中最小的对应的行Ps出基,其中。i

6、=(B-lb)i/(B-lPk)i,(B-lPk)i>0,也就是对应分量之比。在用单纯形法求解线性规划问题Z前,有一个预备步骤就是将模型变为标准型,虽然可以由基本的计算求出线性规划问题的最优解,但是为了更加简单、清楚,这个算法的过程我们通过表格的形式来实现,即所谓的单纯形表。例:用单纯形法求解下面线性规划问题(以max为例)maxZ=7Xl+12x2s.t.:9x1+4x2^3604x1+5x2^2003x1+10x2^300xl,x220解:化为标准型:maxZ=7X1+12X2+0X3+0X4+0X5s.t.:9xl+4x2+x

7、3=3604xl+5x2+x4=2003xl+10x2+x5=300xl,x2,x3,x4,x520单纯形表:712000XBcBB-1bx.卷x?x$0X303609410090X.<02004501040X503003[10]001308712000第一个基是I,初始表填完后,第一个基木可行解X=(0,0,360,200,300)T,这个解是否为最优呢?要计算检验数进行检验。以第一个检验数§1为例来加以说明81=C1-CBB—1P1=7-(0,0,0)(943)1=7同理求出其余几个检验数分别为12、0、0、0。如果检验数的符号

8、均W0,则当前这个基本可行解最优,否则不是最优。我们看到这张表不是最优,还需继续进行。那么继续进行就需转到第三个步骤基变换,主要是确定进基和出基,确定进基是在正检验数中选择最大的那个,我们这道题是12,这个12所对应的向量是P2,对应

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。