资源描述：
《运筹学第2讲：图解法及单纯形法基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2讲：图解法及单纯形法基本概念浙江工业大学经贸管理学院曹柬一、图解法：确定直角平面坐标系，图示非负约束条件图示约束条件，找出可行域图示目标函数，确定最优解maxz=2x1+x2s.t.x1+x2≤56x1+2x2≤245x2≤15x1,x2≥0例1：运筹学第2讲：图解法及单纯形法基本概念图解法仅适于两个变量的LP模型从图解法中可以看出LP模型的解的情况二、LP模型解的几种情况一、惟一最优解二、无穷多最优解三、无界解四、无可行解运筹学第2讲：图解法及单纯形法基本概念minz=2x1+3x2s.t.x1+x
2、2≥350,x1≥1252x1+x2≤600,x1≥0，x2≥0。x1x2600600100100300300x1=1252x1+x2=600x1+x2=350解线性方程组x1+x2=3502x1+x2=600得最优解x1=250x2=100最优值z=800可行域例2：Z=2x1+3x2惟一最优解运筹学第2讲：图解法及单纯形法基本概念Amaxz=x1+x2s.t.x1+x2≤5，2x1+x2≤85x2≤15，x1,x2≥0无穷多最优解x1x2661133x1+x2=52x1+x2=85x2=15可行域z=
3、x1+x2AB线段AB上的任意一点都是模型的解例3：运筹学第2讲：图解法及单纯形法基本概念maxz=x1+x2s.t.-2x1+x2≤2，x1-3x2≤3x1,x2≥0无界解x1x2661133-2x1+x2=2z=x1+x2可行域伸展到无穷，则z也可增大到无穷，即最优解无界x1-3x2=3可行域运筹学第2讲：图解法及单纯形法基本概念例4：原因为模型中缺乏必要的约束条件maxz=x1+x2s.t.x1+x2≤2，2x1+2x2≥6x1,x2≥0无可行解x2x1331122x1+x2=2不存在满足所有约束条
4、件的可行域，即解无可行域，模型无解2x1+2x2=6例5：运筹学第2讲：图解法及单纯形法基本概念原因是约束条件之间有矛盾无界解：LP模型存在可行域，模型有解，但解无界，趋于无穷，即无最优解无可行解(无解)：LP模型不存在可行域，模型无解。运筹学第2讲：图解法及单纯形法基本概念三、单纯形法的几个基本概念可行解、可行域、最优解、最优值（P11）运筹学第2讲：图解法及单纯形法基本概念基(阵)（P14）基向量、基变量、基变矢、非基变量、非基变矢（P14）基解、基可行解、可行基（P14）例6：运筹学第2讲：图解法及
5、单纯形法基本概念将原模型改为标准型：maxz=3x1+5x2s.t.x1≤82x2≤123x1+4x2≤36x1,x2≥0其中，x3,x4,x5为松弛变量maxz=3x1+5x2+0x3+0x4+0x5s.t.x1+x3=82x2+x4=123x1+4x2+x5=36xj≥0，j=1,2,…,5运筹学第2讲：图解法及单纯形法基本概念则模型的系数矩阵为n=5,m=3,rA=3运筹学第2讲：图解法及单纯形法基本概念令P=(P3,P4,P5)=，rP=3=rA=mP3,P4,P5是三个基向量与P3,P4,P5相
6、对应的三个变量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),则为基解,运筹学第2讲：图解法及单纯形法基本概念P’=(P2,P3,P5)=XB’=[x2,x3,x5]T是基变矢XN’=[x1,x4]T是非基变矢得到XB’=[x2,x3,x5]T=[6,8,12]T也
7、是基可行解此时，z=30P’是一个基(2)令XN’=[x1,x4]T=[0,0]T,对应的可行基为P’=(P2,P3,P5),则为基解,若用P2替换P4，则P2,P3,P5是三个基向量运筹学第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，则得到基解运筹学第2讲：图解法及单纯形法基本概念可不断变换可行
8、基，并求得相应的基可行解（每个基可行解对应于可行域上的一个顶点），直至得到满足非负条件的最优解，这就是单纯形法的基本思想。P’’’=(P2,P3,P4)=(4)若用P4替换P1，则得到为基解，但不是基可行解此时，z=45，解无效四、几个基本定理凸集：集合C中任意两点间x1、x2，其连线上的所有点ax1+(1-a)x2(0≤a≤1)也是C中的点，则C为凸集定理一：线性规划问题的可行解集为凸集定理二：线性规划问题的基可行解对应于可
