运筹学第2讲：图解法及单纯形法基本概念

第2讲：图解法及单纯形法基本概念浙江工业大学经贸管理学院曹柬1可编辑ppt一、图解法：确定直角平面坐标系，图示非负约束条件图示约束条件，找出可行域图示目标函数，确定最优解maxz=2x1+x2s.t.x1+x2≤56x1+2x2≤245x2≤15

x1,x2≥0例1：运筹学第2讲：图解法及单纯形法基本概念图解法仅适于两个变量的LP模型从图解法中可以看出LP模型的解的情况2可编辑ppt二、LP模型解的几种情况一、惟一最优解二、无穷多最优解三、无界解四、无可行解运筹学第2讲：图解法及单纯形法基本概念3可编辑pptminz=2x1+3x2s.t.x1+x2≥350,x1≥1252x1+x2≤600,x1≥0，x2≥0。x1x2600600100100300300x1=1252x1+x2=600x1+x2=350解线性方程组x1+x2=3502x1+x2=600得最优解x1=250

x2=100最优值

z=800可行域例2：Z=2x1+3x2惟一最优解运筹学第2讲：图解法及单纯形法基本概念A4可编辑pptmaxz=x1+x2s.t.x1+x2≤5，2x1+x2≤85x2≤15，x1,x2≥0无穷多最优解x1x2661133x1+x2=52x1+x2=85x2=15可行域z=x1+x2AB线段AB上的任意一点都是模型的解例3：运筹学第2讲：图解法及单纯形法基本概念5可编辑pptmaxz=x1+x2s.t.-2x1+x2≤2，x1-3x2≤3

x1,x2≥0无界解x1x2661133-2x1+x2=2z=x1+x2可行域伸展到无穷，则z也可增大到无穷，即最优解无界x1-3x2=3可行域运筹学第2讲：图解法及单纯形法基本概念例4：原因为模型中缺乏必要的约束条件6可编辑pptmaxz=x1+x2s.t.x1+x2≤2，2x1+2x2≥6

x1,x2≥0无可行解x2x1331122x1+x2=2不存在满足所有约束条件的可行域，即解无可行域，模型无解2x1+2x2=6例5：运筹学第2讲：图解法及单纯形法基本概念原因是约束条件之间有矛盾7可编辑ppt无界解：LP模型存在可行域，模型有解，但解无界，趋于无穷，即无最优解无可行解(无解)：LP模型不存在可行域，模型无解。运筹学第2讲：图解法及单纯形法基本概念8可编辑ppt三、单纯形法的几个基本概念可行解、可行域、最优解、最优值（P11）运筹学第2讲：图解法及单纯形法基本概念基(阵)（P14）基向量、基变量、基变矢、非基变量、非基变矢（P14）基解、基可行解、可行基（P14）9可编辑ppt例6：运筹学第2讲：图解法及单纯形法基本概念将原模型改为标准型：maxz=3x1+5x2s.t.x1

≤8 2x2≤123x1+4x2≤36

x1,x2≥0其中，x3,x4,x5为松弛变量maxz=3x1+5x2+0x3+0x4+0x5s.t.x1

+x3=8 2x2+x4=123x1+4x2+x5=36

xj≥0，j=1,2,…,510可编辑ppt运筹学第2讲：图解法及单纯形法基本概念则模型的系数矩阵为n=5,m=3,rA=311可编辑ppt运筹学第2讲：图解法及单纯形法基本概念令P=(P3,P4,P5)=，rP=3=rA=mP3,P4,P5是三个基向量与P3,P4,P5相对应的三个变量x3,x4,x5是基变量XB=[x3,x4,x5]T是基变矢XN=[x1,x2]T是非基变矢得到XB=[x3,x4,x5]T=[8,12,36]T其也是基可行解此时，z=0P是一个基,(1)令XN=[x1,x2]T=[0,0]T,x1,x2是非基变量,对应的可行基为P=(P3,P4,P5),则为基解,12可编辑ppt运筹学第2讲：图解法及单纯形法基本概念P’=(P2,P3,P5)=XB’=[x2,x3,x5]T是基变矢XN’=[x1,x4]T是非基变矢得到XB’=[x2,x3,x5]T=[6,8,12]T也是基可行解此时，z=30P’是一个基(2)令XN’=[x1,x4]T=[0,0]T,对应的可行基为P’=(P2,P3,P5),则为基解,若用P2替换P4，则P2,P3,P5是三个基向量13可编辑ppt运筹学第2讲：图解法及单纯形法基本概念P’’=(P1,P2,P3)=XB’’=[x1,x2,x3]T,XN’’=[x4,x5]T得到XB’’=[x1,x2,x3]T=[4,6,4]T此时，z=42(3)令XN’’=[x4,x5]T=[0,0]T,若用P1替换P5，则得到基解14可编辑ppt运筹学第2讲：图解法及单纯形法基本概念

可不断变换可行基，并求得相应的基可行解（每个基可行解对应于可行域上的一个顶点），直至得到满足非负条件的最优解，这就是单纯形法的基本思想。P’’’=(P2,P3,P4)=(4)若用P4替换P1，则得到为基解，但不是基可行解此时，z=45，解无效15可编辑ppt四、几个基本定理凸集：集合C中任意两点间x1、x2，其连线上的所有点ax1+(1-a)x2(0≤a≤1)也是C中的点，则C为凸集定理一：线性规划问题的可行解集为凸集定理二：线性规划问题的基可行解对应于可行域的顶点定理三：线性规划问题如有最优解，则一定在其可行域的顶点上达到。如果几个顶点都是最优解，则在这些顶点的