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

第2讲：图解法及单纯形法基本概念浙江工业大学经贸管理学院曹柬图解法：确定直角平面坐标系，图示非负约束条件图示约束条件，找出可行域图示目标函数，确定最优解maxz=2x1+x2s.t.x1+x2≤56x1+2x2≤245x2≤15x1,x2≥0例1：运筹学第2讲：图解法及单纯形法基本概念图解法仅适于两个变量的LP模型从图解法中可以看出LP模型的解的情况惟一最优解无穷多最优解无界解无可行解运筹学第2讲：图解法及单纯形法基本概念LP模型解的几种情况惟一最优解minz=2x1+3x2s.t.x1+x2≥350,x1≥1252x1+x2≤600,x1≥0，x2≥0。x1x2600100300x1=1252x1+x2=600x1+x2=350解线性方程组x1+x2=3502x1+x2=600得最优解x1=250x2=100最优值z=800可行域例2：Z=2x1+3x2运筹学第2讲：图解法及单纯形法基本概念A无穷多最优解maxz=x1+x2s.t.x1+x2≤5，2x1+x2≤85x2≤15，x1,x2≥0x1x2613x1+x2=52x1+x2=85x2=15可行域z=x1+x2AB线段AB上的任意一点都是模型的解例3：运筹学第2讲：图解法及单纯形法基本概念maxz=x1+x2s.t.-2x1+x2≤2，x1-3x2≤3x1,x2≥0无界解x1x2613-2x1+x2=2z=x1+x2可行域伸展到无穷，则z也可增大到无穷，即最优解无界x1-3x2=3可行域运筹学第2讲：图解法及单纯形法基本概念例4：原因为模型中缺乏必要的约束条件maxz=x1+x2s.t.x1+x2≤2，2x1+2x2≥6x1,x2≥0无可行解x2x1312x1+x2=2不存在满足所有约束条件的可行域，即解无可行域，模型无解2x1+2x2=6例5：运筹学第2讲：图解法及单纯形法基本概念原因是约束条件之间有矛盾无界解：LP模型存在可行域，模型有解，但解无界，趋于无穷，即无最优解无可行解(无解)：LP模型不存在可行域，模型无解。运筹学第2讲：图解法及单纯形法基本概念01可行解、可行域、最优解、最优值（P11）03基向量、基变量、基变矢、非基变量、非基变矢（P14）02基(阵)（P14）04基解、基可行解、可行基（P14）运筹学第2讲：图解法及单纯形法基本概念单纯形法的几个基本概念例6：运筹学第2讲：图解法及单纯形法基本概念将原模型改为标准型：maxz=3x1+5x2s.t.x1≤8 2x2≤123x1+4x2≤36x1,x2≥0其中，x3,x4,x5为松弛变量maxz=3x1+5x2+0x3+0x4+0x5s.t.x1+x3=8 2