运筹学4单纯形法迭代原理
- 格式:ppt
- 大小:589.50 KB
- 文档页数:15
单纯形法原理及步骤单纯形法,求解线性规划问题的通用方法。
单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。
它的理论根据是:线性规划问题的可行域是n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。
顶点所对应的可行解称为基本可行解。
单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。
因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。
如果问题无最优解也可用此法判别。
单纯形法是从某一基可行解出发,连续地寻找相邻的基可行解,直到达到最优的迭代过程,其实质是解线性方程组。
概述:根据单纯形法的原理,在线性规划问题中,决策变量(控制变量)x1,x2,…x n的值称为一个解,满足所有的约束条件的解称为可行解。
使目标函数达到最大值(或最小值)的可行解称为最优解。
这样,一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值(或最小值)。
求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一:①存在着一个最优解;②存在着无穷多个最优解;③不存在最优解,这只在两种情况下发生,即没有可行解或各项约束条件不阻止目标函数的值无限增大(或向负的方向无限增大)。
单纯形法的一般解题步骤可归纳如下:①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解。
②若基本可行解不存在,即约束条件有矛盾,则问题无解。
③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。
④按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善),即得到问题的最优解。
⑤若迭代过程中发现问题的目标函数值无界,则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。
单纯形法求解原理过程第一篇:单纯形法求解原理过程单纯形法需要解决的问题:如何确定初始基本可行解;如何由一个基本可行解迭代出另一个基本可行解,同时使目标函数获得较大的下降;如何判断一个基本可行解是否为最优解。
min f(X)=-60x1-120x2 s.t.9x1+4x2+x3=360 3x1+10x2+x4=300 4x1+5x2+x5=200 xi≥0(i=1,2,3,4,5)(1)初始基本可行解的求法。
当用添加松弛变量的方法把不等式约束换成等式约束时,我们往往会发现这些松弛变量就可以作为初始基本可行解中的一部分基本变量。
例如:x1-x2+x3≤5 x1+2x2+x3≤10xi≥0 引入松弛变量x4,x5后,可将前两个不等式约束换成标准形式 x1-x2+x3+x4=5 x1+2x2+x3+x5=10xi≥0(i=1,2,3,4,5)令x1=x2=x3=0,则可立即得到一组基本可行解x1=x2=x3=0,x4=5,x5=10 同理在该实例中,从约束方程式的系数矩阵⎡94100⎤⎥A=[P1,P2,P3,P4,P5]=⎢310010⎢⎥⎢⎣45001⎥⎦中可以看出其中有个标准基,即⎡100⎤⎥B=⎢010⎢⎥⎢⎣001⎥⎦与B对应的变量x3,x4,x5为基本变量,所以可将约束方程写成X3=360-9x1-4x2 x4=300-3x1-10x2 x5=200-4x1-5x20 若令非基变量x1=x2=0,则可得到一个初始基本可行解X0 TX=[0,0,360,300,200]判别初始基本可行解是否是最优解。
此时可将上式代入到目标函数中,得: F(X)=-60x1-120x20对应的函数值为f(X)=0。
0由于上式中x1,x2系数为负,因而f(X)=0不是最小值。
因此所得的解不是最优解。
011(2)从初始基本可行解X迭代出另一个基本可行解X,并判断X 是否为最优解。
从一个基本可行解迭代出另一个基本可行解可分为两步进行:第一步,从原来的非基变量中选一个(称为进基变量)使其成为基本变量;第二步,从原来的基本变量中选一个(称为离基变量)使其成为新的非基变量。
单纯形算法的一般原理单纯形法的基本思路是有选择地取基本可行解,即是从可行域的一个极点出发,沿着可行域的边界移到另一个相邻的极点,要求新极点的目标函数值不比原目标函数值差。
考虑到如下线性规划问题:其中A一个m ×n 矩阵,且秩为m ,b总可以被调整为一个m 维非负列向量,C为n 维行向量,X为n 维列向量。
根据线性规划基本定理:如果可行域D={ X∈Rn / AX=b,X≥0}非空有界,则D上的最优目标函数值Z=CX一定可以在D的一个顶点上达到。
这个重要的定理启发了Dantzig 的单纯形法,即将寻优的目标集中在D 的各个顶点上。
Dantzig 的单纯形法把寻优的目标集中在所有基本可行解(即可行域顶点)中。
其基本思路是从一个初始的基本可行解出发,寻找一条达到 最优基本可行解的最佳途径。
单纯形法的一般步骤如下:(1)寻找一个初始的基本可行解。
(2)检查现行的基本可行解是否最优,如果为最优,则停止迭代,已找到最优解,否则转一步。
(3)移至目标函数值有所改善的另一个基本可行解,然后转会到步骤(2)。
求解思想如下图所示:maxZ=CX AX=b X 0⎧⎨≥⎩确定初始的基本可行解等价于确定初始的可行基,一旦初始的可行基确定了,那么对应的初始基本可行解也就唯一确定为了讨论方便,不妨假设在标准型线性规划中,系数矩阵A中前m 个系数列向量恰好构成一个可行基,即A=(BN),其中B=(P1,P2,…Pm )为基变量x1,x2,…xm 的系数列向量 构成的可行基,N=(Pm+1,Pm+2, …Pn)为非基变量xm+1,xm+2, …xn 的 系数列向量构成的矩阵。
那么约束方程AX=b 就可表示为:用可行基B的逆阵B-1左乘等式两端,再通过移项可推得:若令所有非基变量 ,则基变量由此可得初始的基本可行解B B N N X AX=(BN)=BX +NX =b X ⎛⎫ ⎪⎝⎭-1-1B N X =B b-B NX N X =0-1B X =B b 1B b X=0-⎛⎫ ⎪⎝⎭-1-1-1B N B N N B AX=b BX +NX =b X =B b-B NX X =0,X =B b →→→● 问题:➢ 要判断m 个系数列向量是否恰好构成一个基并不是一件容易的事。
单纯形法是一种线性规划的求解方法,它通过逐步优化目标函数值,找到满足约束条件的最优解。
简单来说,单纯形法就是在一个由线性方程组定义的多维空间中移动一个“顶点”,直到找到一个最优解。
在单纯形法中,每次迭代都会将当前的“顶点”沿着一个“可行方向”移动,直到找到一个更好的解。
这个“可行方向”是指当前解中有一些变量取得了非基变量的值为0,而这些变量可以通过增大或减小使目标函数值变得更小(或更大)。
在每一步迭代中,单纯形法会选择一个非基变量进入基变量集合,并选择一个基变量离开基变量集合,然后通过高斯消元法更新线性方程组,找到新的基解。
如果新的基解仍然满足约束条件,则继续迭代,否则找到最优解。
总之,单纯形法是一种迭代的求解方法,通过不断移动“顶点”来优化目标函数,直到找到最优解。
在每一步迭代中,单纯形法都会选择一个非基变量进入基变量集合,并选择一个基变量离开基变量集合,然后通过高斯消元法更新线性方程组,找到新的基解。