最优化理论与方法2单纯形法

最优化理论与方法2单纯形法

ID:42085933

大小:2.35 MB

页数:18页

时间:2019-09-07

最优化理论与方法2单纯形法_第1页
最优化理论与方法2单纯形法_第2页
最优化理论与方法2单纯形法_第3页
最优化理论与方法2单纯形法_第4页
最优化理论与方法2单纯形法_第5页
资源描述:

《最优化理论与方法2单纯形法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第2章线性规划的基本性质o2.1标准形式及图解法o2.2基本性质2.1标准形式o一般线性规划问题总可以写成下列标准形式:nmincjxjj1n(2.1.1)s.t.aijxjbii1,...,mj1x0j1,...,njo用矩阵表示:mincxs.t.Axb(2.1.2)x0其中,A是mXn矩阵,c是n维行向量,b是m维列向量。为了计算方便,一般假设b0,即b的每个分量都是非负数。表示定理o设S{x

2、Axb,x0}为非空多面集,则有:(1)(k)n极点集非空,且存在有限个极点x,...,x.n极方向集为空集的充要条件是S有界。若

3、S无界,则存在有限个极方向(1)(l).d,...,dnx∈S的充要条件是:kl(j)(j)xjxjdj1j1kj1,j10,j1,...,k,j0,j1,...,l.j定理与结论o线性规划的可行域是凸集。o设线性规划(2.1.2)的可行域非空,则有下列结论:(j)n线性规划(2.1.2)存在有限最优解的充要条件是所有cd为非负数,(j)其中d是可行域的极方向。n若线性规划(2.1.2)存在有限最优解,则目标函数的最优值可在某个极点上达到。(最优极点)极点是个几何概念,直观性强,但不便于演算,因此需要研究极点的代数含义。

4、基本可行解o又若1,则称Bb0xB1bBxB1box称为方程组的一个基本解;xB为约束条件x0Nx0NoB称为基矩阵,简称基;Axb,x0的基本可行解,oxB的各分量称为基变量;称B为可行基矩阵,o基变量的全体x,x,...,x称为一组基;B1B2BmxB,xB,...,xB为一组可行基;12moxN的各分量称为非基变量;o若1,则称基本可行解是非退化的Bb0基本可行解;1o若Bb0且至少有一个分量是零,则称此时的基本可行解是退化的基本可行解;同时,此基本可行解对应的基被称为退化的

5、可行基。基本可行解的个数o若A是mXn矩阵,A的秩为m时,基本可行解的个数不会超过:nn!mm!(nm)!定理与推理o线性规划的可行域是凸集。o设线性规划(2.1.2)的可行域非空,则有下列结论:(j)n线性规划(2.1.2)存在有限最优解的充要条件是所有cd为非负数,(j)其中d是可行域的极方向。n若线性规划(2.1.2)存在有限最优解,则目标函数的最优值可在某个极点上达到。(最优极点)o线性规划的可行域的极点集与基本可行解集等价;o当线性规划(2.1.2)有可行解,则一定存在基本可行解。o当线性规划(2.1.2)存在最优解时,则一定存在

6、一个基本可行解是目标函数的最优解。(最优基本可行解)第3章单纯形方法o3.1单纯形方法原理o3.2两阶段法o3.3修正单纯形法单纯形方法的基本思想o就是,从一个基本可行解出发,求一个使目标函数值有所改变的基本可行解;通过不断改进基本可行解,力图达到最优基本可行解。o怎样实现基本可行解的转换?minfcxs.t.Axb表格形式的单纯形法x0minfminf11s.t.fcxcx0s.t.xBNxBbBBNNBN11BxBNxNbf0xB(cBBNcN)xNcBBbx0,x0x0,x0BNBNfxx右端BNx0IB

7、-1NB-1bBmf10cB-1N-ccB-1bBNBo显然,在单纯形表中包含了单纯形方法所需的全部数据。表格形式的单纯形法进基变量离基xBxBxBxjxk1rm变量x100yybB11j1k1x010yybBrrjrkrx001yybBmmjmkmf000zjcjzkckcBb主元brbizcmax{zc}xmin

8、y0kkjjkikyyrkiko显然,在单纯形表中包含了单纯形方法所需的全部数据。表格形式的单纯形法o解的几种情况在单纯形表上的体现(min型

9、):n唯一最优解:终表非基变量判别数均小于零;n多重最优解:终表非基变量判别数中有等于零的;n无界解:任意表有正判别数相应的系数列均非正。omax型单纯形表与min型的区别仅在于:判别数反号,即,n令负判别数中最小的对应的变量进基;n当判别数均大于等于零时为最优。两阶段法o用单纯形法消去人工变量(如果可能),即把人工变量变为非基变量,求出原问题的一个基本可行解;xn首先引入人工变量。令Axxab,即(A,I)bmxx0,x0aax0,x0an消去人工变量的一种方法是解如下第一阶段问题:设得到的最优基本可行解是TTT,此T(x,x)

10、minexaa时必有下列三种情况之一:s.t.Axxb(1)x

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

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

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