运筹学之单纯形法.ppt

《运筹学之单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章单纯形法美国著名的运筹学家丹茨格1947年提出的.10(0,0)X2X1DABC(0,6)(4,6)(8,3)X0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX2=(4,6,4,0,0)T2初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY单纯形法的解题思路32.1.1方程组形式的单纯形法maxZ=3X1+5X2X1+X3=82X2+X4=123X1+4X2+X5=36X1…X502.1单纯形法的基本思想单纯形法的三种形式：1）方程组形式；2）表格形式；3）矩阵形式。4解：(1)、确

2、定初始可行解B=(a3a4a5)=IZ-3X1-5X2=0X3=8-X1X4=12-2X2X5=36-3X1-4X2令X1=X2=0X0=(0,0,8,12,36)TZ0=0——初始可行解，简称初始解5基本概念条典、典式检验数6（1）基本可行解X0对应的可行基是一个m(=3）阶单位阵。（2）目标方程中所有基变量X3，X4，X5的系数全都为0。这两个条件简称为条典，把满足条典的线性方程组称为典式（方程组）。条典、典式7检验数当目标方程中基变量系数全为0时，非基变量的系数可以作为检验当前的基本可行解是否最优的标志，称之为检验数。8

3、(2)、判定解是否最优Z-3X1-5X2=0当X1从0↗或X2从0↗Z从0↗∴X0不是最优解9(3)、由一个基可行解→另一个基可行解。∵-5<-3选X2从0↗，X1=0X3=8X4=12-2X20X212/2X5=36-4X20X236/4X2=min(--,12/2,36/4)=6概念：X2——进基变量，X4——离基变量。10换基迭代公式：(1)、决定进基变量：minj=k，则Xk为进基变量j<0(2)、决定离基变量：bi-aikXik0(i=1,2,…,m)Xikbiaik(aik>0)11θ=min=(

4、aik>0)biaikblalk则Xl为离基变量。最小比值θ(P55)12下一组基:B1=(a3a2a5)Z-3X1-5X2=0(0)X1+X3=8①2X2+X4=12②3X1+4X2X5=36③13接下来要让进基变量X2的系数列向量变为单位向量具体做法：（１）主元素所在行的所有元素都除以主元素（２）主元素所在列要变为单位向量,方法是采用行变换,即将主元素行的某个倍数加到另一行上去。概念：主元，换基运算，迭代P54（从一个基本可行解转换到另一个基本可行解）14Z－３X1+5／２X４==３０（０）X１+X３==８①X２+１／2X

5、４==6②３Ｘ１－２Ｘ４＋Ｘ５＝１２③15得到新的基本可行解X1=(0,6,8,0,12)T(1)、决定进基变量：1=--3,X1进基(2)、决定离基变量：最小比值规则来确定主元与离基变量.16则Xl为进基变量。MIN(8/1,-,12/3)=12/3此时可以确定X5为离基变量Z+1/2X4+X5=42X3+2/3X4-1/3X5=4X2+1/2X4=6X1-2/3X4+1/3X5=4令X4=X5=0X=(4,6,4,0,0)TZ=4217。此时4=1/2,5=1,Z值不再增大了,X值是最优基本解即:X*=(4,6)T,

6、Z*=42它与图解法结果一致180(0,0)X2X1DABC(0,6)(4,6)(8,3)2.1.2单纯形法的几何意义X0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX2=(4,6,4,0,0)T192.2单纯形法的计算过程2.2.1单纯形表20212223例：Z=30X1+20X2-X1+3X2+X3=10-3X1+2X2+X4=15初始基B0=(a3a4)X(0)=(0,0,10,15)TZ0=024选中X1从0↗，X2=0X3=10-(-X1)0X4=15-(-3X1)0求X1，X1→+,Z→+

7、Z-30X1-20X2=0252.2.3单纯形法计算之例2627282930312-3人工变量法(ArtificialVariable)一、人工变量法在单纯形法中,首先要求找到一个m阶排列阵,但是往往做不到.如何找到单位阵？32目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥033342.基本过程:1）加入人工变量;2）通过单纯形法的迭带,将虚拟的人工变量

8、从原来的基变量中替换出去,变成非基变量,使每一个人工变量都等于0.反之,如果不能都变为非基变量,表明原问题无可行解.35(一)、大M法：363738392.4单纯形法补遗2.4.1进基变量的相持及其突破minj=k若出现两个或更多个j<0同时达到j<0最小，而相持不下