单纯形法求解

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,线性规划的基本概念,可行解,feasible solution,最优解,optimal solution,基,basic,matrix (the basis),基解,basic,solution,基可行解,basic,feasible (BF) solution,可行基,feasible basic matrix,可行域,feasible region,2024/9/21,1,LP,的基本定理,定义 凸集（,convex set,），顶点（极点,corner point,）,定理1：线性规划问题的可行域是凸集,定理2：线性规划问题的最优解在极点上,定理3：若,LP,问题有最优解，一定存在一个基可行解是最优解。,凸集,凸集,不是凸集,极点,2024/9/21,2,单纯形表,基变量,C,1,C,2,C,m,C,m+1,C,m+k,C,n,X,1,X,2,X,m,X,m+1,X,m+k,X,n,C,B,X,B,-Z,0,0 0,0,m+1,m+k,n,C,1,X,1,b,1,1 0,0 a,1m+1,a,1m+k,a,1n,C,2,X,2,b,2,0 1,0 a,2m+1,a,2m+k,a,2n,C,r,X,r,b,r,0 0,0 a,rm+1,a,rm+k,a,rn,C,m,X,m,b,m,0 0,1 a,mm+1,a,mm+k,a,mn,2024/9/21,3,maxZ=40X,1,+50X,2,X,1,+2X,2,+X,3,=30,3X,1,+2X,2,+X,4,=60,2X,2,+X,5,=24,X,1,X,5,0,（2）列（初始）单纯形表,引例用单纯形法求解生产计划问题。解： （1）化标准型,2024/9/21,4,40 50 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 40 50 0 0 0 ,0,X,3,30 1 2 1 0 0 15,0,X,4,60,3,2 0 1 0 30,0,X,5,24 0 2 0 0 1 12,X,B,600 40 0 0 0 -25,0,X,3,6 1 0 1 0 -1 6,0,X,4,36 3 0 0 1 -1 12,50,X,2,12 0 1 0 0 1/2,840 0 0 -40 0 15,40,X,1,6 1 0 1 0 -1,0,X,4,18 0 0 -3 1 2 9,50,X,2,12 0 1 0 0 1/2 24,2024/9/21,5,40 50 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 40 50 0 0 0 ,0,X,3,30 1 2 1 0 0 15,0,X,4,60,3,2 0 1 0 30,0,X,5,24 0 2 0 0 1 12,X,B,600 40 0 0 0 -25,0,X,3,6 1 0 1 0 -1 6,0,X,4,36 3 0 0 1 -1 12,50,X,2,12 0 1 0 0 1/2,840 0 0 -40 0 15,40,X,1,6 1 0 1 0 -1,0,X,4,18 0 0 -3 1 2 9,50,X,2,12 0 1 0 0 1/2 24,2024/9/21,6,40 50 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 40 50 0 0 0 ,0,X,3,30 1 2 1 0 0 15,0,X,4,60,3,2 0 1 0 30,0,X,5,24 0 2 0 0 1 12,X,B,600 40 0 0 0 -25,0,X,3,6 1 0 1 0 -1 6,0,X,4,36 3 0 0 1 -1 12,50,X,2,12 0 1 0 0 1/2,840 0 0 -40 0 15,40,X,1,6 1 0 1 0 -1,0,X,4,18 0 0 -3 1 2 9,50,X,2,12 0 1 0 0 1/2 24,2024/9/21,7,40 50 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 40 50 0 0 0 ,0,X,3,30 1 2 1 0 0 15,0,X,4,60,3,2 0 1 0 30,0,X,5,24 0 2 0 0 1 12,X,B,-600 40 0 0 0 -25,0,X,3,6 1 0 1 0 -1 6,0,X,4,36 3 0 0 1 -1 12,50,X,2,12 0 1 0 0 1/2,-840 0 0 -40 0 15,40,X,1,6 1 0 1 0 -1,0,X,4,18 0 0 -3 1 2 9,50,X,2,12 0 1 0 0 1/2 24,2024/9/21,8,40 50 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 40 50 0 0 0 ,0,X,3,30 1 2 1 0 0 15,0,X,4,60,3,2 0 1 0 30,0,X,5,24 0 2 0 0 1 12,X,B,-600 40 0 0 0 -25,0,X,3,6 1 0 1 0 -1 6,0,X,4,36 3 0 0 1 -1 12,50,X,2,12 0 1 0 0 1/2,-840 0 0 -40 0 15,40,X,1,6 1 0 1 0 -1,0,X,4,18 0 0 -3 1 2 9,50,X,2,12 0 1 0 0 1/2 24,2024/9/21,9,X,B,-975 0 0 -35/2 -15/2 0,40,X,1,15 1 0 -1/2 1/2 0,0,X,5,9 0 0 -3/2 1/2 1,50,X,2,15/2 0 1 3/4 -1/4 0,(3)本问题的最优解,X =,(,X,1,X,2,X,3,X,4,X,5,),T,= (15, 15/2, 0, 0, 9),T,且,Z=975.,X,3,X,4,=,0,表示资源1 ，2用完,X,5,=,9,表示资源3剩余9.,图解分析见下。,2024/9/21,10,0,(0,0),X,2,X,1,A,D,C,B,(0,12),(6,12),(15,7.5),从一个基可行解到另一个基可行解,2024/9/21,11,单纯形法基本步骤,(1)、定初始基，初始基本可行解,(3)、,若有,k,0，,P,k,全,0，,停，,没有有限最优解； 否则转(4),(2)、对应于非基变量检验数,j,全,0。,若是，停，得到最优解；,若否，转(3)。,2024/9/21,12,=,min,a,im+k,0 =,b,i,a,im+k,b,r,a,rm+k,定,X,r,为换出变量，,a,rm+k,为,主元。,由最小,比值法求：,max,j,=,m+k,X,m+k,换入变量,j,0,(4)、,2024/9/21,13,转(2),m+k,0, ,a,1m+k,0,a,rm+k,1,a,mm+k,0,初等行变换,P,m+k,=,(5)、以,a,rm+k,为中心，换基迭代,2024/9/21,14,单纯形法的进一步讨论（简介）,(一)、大,M,法,the Big M Method,初始基本可行解的求法 - 加入人工变量,大,M,使人工变量 - 0,2024/9/21,15,例：用大,M,法求解下列问题。,maxZ,=,6X,1,+4X,2,2,X,1,+3X,2,100,4X,1,+2X,2,120,X,1,=,14,X,2,22,X,1,X,2,0,2024/9/21,16,解,： （1）,化标准型,maxZ,=,6X,1,+4X,2,2,X,1,+3X,2,+X,3,=,100,4X,1,+2X,2,+X,4,=,120,X,1,=,14,X,2,- X,5,=,22,X,1, X,5,0,2024/9/21,17,（2）加人工变量,X,6，,X,7,，,问题化为,maxZ,=,6X,1,+4X,2,-MX,6,-MX,7,2,X,1,+3X,2,+X,3,=,100,4X,1,+2X,2,+X,4,=,120,X,1,+X,6,=,14,X,2,- X,5,+X,7,=,22,X,1, X,7,0,（3）,单纯形求解,判定无解条件：当进行到最优表时，仍有人工变量在基中，且,0，,则说明原问题无可行解。,2024/9/21,18,原问题,maxZ= C,j,x,j,j=1,n,x,j, 0,j=1,n,a,ij,x,j,=,b,i,( i=1,2,m,),(二)、两阶段法,The Two-phase Method,2024/9/21,19,作辅助问题,minW= y,i,i=1,m,X,j ，,y,i, 0,j=1,n,a,ij,x,j,+,y,i,=,b,i,( i=1,2,m,),解题过程：,第1阶段：解辅助问题,当进行到最优表时，、若,W=0,则得到原问题的一个基本可行解，转入第,2,阶段。,、若,W0,则判定原问题无可行解。,2024/9/21,20,第1阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解,第2阶段：,以第一阶段得到的基础可行解为初始解，采用原单纯型法求解,2024/9/21,21,两阶段法原理：,(1)、辅助问题的基本可行解,X,(0),为最优解，对应,最小值,=0,则,X,(0),的前,n,个分量是原问题的基本可行解。,2024/9/21,22,小结与应用举例,小结,应用举例,2024/9/21,23,(1)、,LP,数学模型及标准型,maxZ=CX,AX=b (b,0,),X,0,(2)、,LP,问题解的性质：图解法分析,小结,2024/9/21,24,(3)、单纯形法：,1)、标准型中有单位基。,2)、标准型中没有单位基，用大,M,法加人工变量，使之构成单位基。,求,maxZ,时，目标中,M,X,j,求,minZ,时，目标中,M,X,j,3)、判定最优解定理：,maxZ,问题，检验数,j,0,minZ,问题，检验数,j,0,2024/9/21,25,4)、解的几种情况：,唯一解,无穷多解 （多重解 ）,无有限最优解 （无界解）,无可行解,2024/9/21,26,多重解,多个解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行,最优单纯型表中有非基变量的检验数为0,最优解的线性组合仍是最优解，即,X,=,aX,1,+,bX,2,，,a,+,b,=1,2024/9/21,27,无界解,可行区域不闭合(缺约束条件),单纯型表中入变量,x,j*,对应的列中所有,无可行解,约束条件互相矛盾，无可行域,单纯型表达到最优解检验条件时，人工变量仍在基变量中,2024/9/21,28,