运筹学之单纯形法

0(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)T初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY单纯形法的解题思路2.1.1方程组形式的单纯形法maxZ=3X1+5X2X1+X3=82X2+X4=123X1+4X2+X5=36X1…X502.1单纯形法的基本思想单纯形法的三种形式：1）方程组形式；2）表格形式；3）矩阵形式。解：(1)、确定初始可行解B=(a3a4a5)=IZ-3X1-5X2=0X3=8-X1X4=12-2X2X5=36-3X1-4X2令X1=X2=0X0=(0,0,8,12,36)TZ0=0——初始可行解，简称初始解基本概念•条典、典式•检验数（1）基本可行解X0对应的可行基是一个m(=3）阶单位阵。（2）目标方程中所有基变量X3，X4，X5的系数全都为0。这两个条件简称为条典，把满足条典的线性方程组称为典式（方程组）。条典、典式检验数当目标方程中基变量系数全为0时，非基变量的系数可以作为检验当前的基本可行解是否最优的标志，称之为检验数。(2)、判定解是否最优Z-3X1-5X2=0当X1从0↗或X2从0↗Z从0↗∴X0不是最优解(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——离基变量。换基迭代公式：(1)、决定进基变量：minj=k，则Xk为进基变量j0(2)、决定离基变量：bi-aikXik0(i=1,2,…,m)Xikbiaik(aik0)θ=min=(aik0)biaikblalk则Xl为离基变量。最小比值θ(P55)下一组基:B1=(a3a2a5)Z-3X1-5X2=0(0)X1+X3=8①2X2+X4=12②3X1+4X2X5=36③接下来要让进基变量X2的系数列向量变为单位向量具体做法：（１）主元素所在行的所有元素都除以主元素（２）主元素所在列要变为单位向量,方法是采用行变换,即将主元素行的某个倍数加到另一行上去。概念：主元，换基运算，迭代P54（从一个基本可行解转换到另一个基本可行解）Z－３X1+5／２X４==３０（０）X１+X３==８①X２+１／2X４==6②３Ｘ１－２Ｘ４＋Ｘ５＝１２③得到新的基本可行解X1=(0,6,8,0,12)T(1)、决定进基变量：1=--3,X1进基(2)、决定离基变量：最小比值规则来确定主元与离基变量.则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=42。此时4=1/2,5=1,Z值不再增大了,X值是最优基本解即:X*=(4,6)T,Z*=42它与图解法结果一致0(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)T2.2单纯形法的计算过程2.2.1单纯形表例：Z=30X1+20X2-X1+3X2+X3=10-3X1+2X2+X4=15初始基B0=(a3a4)X(0)=(0,0,10,15)TZ0=0选中X1从0↗，X2=0X3=10-(-X1)0X4=15-(-3X1)0求X1，X1→+,Z→+Z-30X1-20X2=02.2.3单纯形法计算之例2-3人工变量法(ArtificialVariable)一、人工变量法在单纯形法中,首先要求找到一个m阶排列阵,但是往往做不到.如何找到单位阵？•目标函数：Maxz=c1x1+c2x2+…+cnxn•约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥02.基本过程:1）加入人工变量;2）通过单纯形法的迭带,将虚拟的人工变量从原来的基变量中替换出去,变成非基变量,使每一个人工变量都等于0.反之,如果不能都变为非基变量,表明原问题无可行解.(一)、大M法：2.4单纯形法补遗2.4.1进基变量的相持及其突破minj=k若出现两个或更多个j0同时达到j0最小，而相持不下时，任选一个作为进基。2.4.2离基变量的相持及其突破----退化情形目标函数Maxz=3x1+5x2约束条件x1+x3=8s.t.2x2+x4=123x1+4x2+x5=24x1，x2，x3，x4，x502.4.2离基变量的相持及其突破----退化情形突破离基变量必然立即导致一个退化的基本可行解，这就有可能造成单纯形法的迭代步骤陷入一个周而复始的循环过程。避免循环的方法有：1。摄动法2。辞典序法3。Bland法等摄动法避免循环的规则：从相持的离基变量中选择下标最大者离基。2.4.3多重最优解判定LP模型是否有多重最优解是必要的。如何判定LP模型是否有多重最优解？如何找到？(1)、例maxZ=X1+2X2X14X23X1+2X28X1,X20X1+X3=4X2+X4=3X1+2X2+X5=8X1…X5012000X1X2X3X4X5CBXB0-1-20000X34101000X430(1)0100X5812001CBXB6-100200X34101002X23010100X52(1)00-21(接下表)12000X1X2X3X4X5CBXB8000010X32001(2)-12X23010101X12100-21CBXB8000010X41001/21-1/22X2201-1/201/21X1410100X(1)=(2,3)Z(1)=8X(2)=(4,2)Z(2)=8无穷多解全部解：X=α+(1-α)(0α1)2432(2)、例：求maxZ=-X1+X2-X3+3X5X2+X3-X4+2X5=6X1+2X2-2X4=52X2+X4+3X5+X6=8X1…X60-11-1030X1X2X3X4X5X6CBXB-110-403-50-1X36011-120-1X15120-2000X68020131CBXB7/30-2/3014/305/3-1X32/30-1/31-5/30-2/3-1X15120-2003X58/302/301/311/3CBXB41/300405/3-1X33/21/601-20-2/31X25/21/210-1003X51-2/300111/3(3)、maxZ=10X1+12X23X1+4X264X1+X223X1+2X23X1,X201012000X1X2X3X4X5XB0-10-12000θiX363(4)1003/2X42410102/1X53320013/2XB18-10300θiX23/23/411/4002X41/213/40-1/4102/13X50(3/2)0-1/2010XB18008/302/3X23/2011/20-1/2X41/2005/61-13/6X1010-1/302/3退化解X*=(0,3/2,0,1/2,0)TZmax=18例：maxZ=-3/4X4+20X5-1/2X6+6X7X1+1/4X4-8X5-X6+9X7=0X2+1/2X4-12X5-1/2X6+3X7=0X3+X6=1X1…X70(a1a2a3)(a4a2a3)(a4a5a3)(a6a5a3)(a6a7a3)(a1a7a3)(a1a2a3)(4)例：maxZ=4X1+X2-X1+X22X1-4X24X1-2X28X1,X2041000X1X2X3X4X5CBXB0-4-10000X32-111000X44(1)-40100X581-2001160-170400X360-31104X141-40100X540(2)0-1150000-9/217/20X312001-1/23/24X112100-121X22010-1/21/2本问题无界。X1X2OZ=0判定无解条件：当进行到最优表时，仍有人工变量在基中，且≠0，则说明原问题无可行解。例：maxZ=6X1+4X22X1+3X21004X1+2X2120X1=14X222X1X20maxZ=6X1+4X22X1+3X2+X3=1004X1+2X2+X4=120X1=14X2-X5=22X1…X50maxZ=6X1+4X2-MX6-MX72X1+3X2+X3=1004X1+2X2+X4=120X1+X6=14X2-X5+X7=22X1…X7064000-M-MX1X2X3X4X5X6X7CBXB-36M-M-6-M-400M000X310023100000X41204201000-MX614(1)000010-MX7220100-101CBXB84-22M0-M-400M6+M00X37203100-200X46402010-406X1141000010-MX7220(1)00-101CBXB1720000-46+M4+M0X360010(3)-2-30X42000012-4-26X11410000104X2220100-101CBXB180004/300M-10/3M0X52001/301-2/3-10X41600-2/310-8/306X11410000104X224011/300-2/3-2(二)、两阶段法：原问题maxZ=Cjxjj=1nxj0j=1naijxj=bi(i=1,2,…,m)引入的人工变量后的LP问题分为两个阶段来求解Ⅰ阶段ⅠmaxZ=-X1+2X2X1+X22-X1+X21X23X1X20例：第(1)阶段：minw=-X6-X7X1+X2-X3+X6=2-X1+X2-X4+X7=1X2+X5=3X1…X7000000-1-1X1X2X3X4X5X6X7CBXB-30-211000-1X6211-10010-1X71-1(1)0-10010X530100100CBXB-1-201-1002-1X61(2)0-1101-10X21-110-10010X52100110-1XB000000110X11/210-1/21/201/2-1/20X23/201-1/2-1/201/21/20X53/200-1/21/21-1/2-1/2-12000X1X2X3X4X5CBXB3/2001/23/20-1X11/210-1/2(1/2)02X23/201-1/2-1/200X53/2001/21/21XB4-30200X4120-110X2211-100X51-10(1)01XB61000-2X4210011X2301001X31-10101例：maxZ=2X1+X25X1+10X282X1+2X21X1，X20第(1)阶段：minW=X55X1+10X2-X3+X5=82X1+2X2+X4=1X1…X5000001X1X2X3X4X5CBXB8-5-101001X58510-1010X412(2)010XB3501501X53-50-1-510X21/21101/20X2X1O第1阶段最优基B*min=*(1)、*﹥0(2)、*=0yi≡0(i=1,2,…,m)①B*基变量无人工变量②B*基变量含人工变量yr单纯形表中，yr+arkyk+arjxj=0(﹡)k∈Jj∈JJ：非基变量下标集合1)arj全=0(﹡)式多余方程2)arj有0元，设为ars0以ars为主元，换基迭代，最后得到①例、求maxZ=-4X1-3X31/2X1+X2+1/2X3-2/3X4=23/2X1+3/4X3=33X1-6X2+4X4=0X1,X2,X3,X40满足0000111X1X2X3X4y1y2y3CBXB5-5