1.2-3单纯形法图解法及原理

1线性规划模型隐含的假设：比例性：决策变量变化引起目标的改变量与决策变量改变量成正比。可加性：每个决策变量对目标和约束的影响独立于其它变量。连续性：每个决策变量取连续值。确定性：线性规划中的参数aij,bi,ci为确定值。2第二节单纯形法原理----图解法图解法：是用画图的方式求解线性规划的一种方法。只能用于求解两个变量的LP问题31）作出可行域2）作出一条目标函数的等值线3）平行移动目标函数的等值线，求出最优解图解法基本步骤：4例1.数学模型maxZ=50x1+30x2s.t.4x1+3x21202x1+x250x1,x205x2504030201010203040x14x1+3x2120由4x1+3x2120x10x20围成的区域6x2504030201010203040x12x1+x2504x1+3x21207x2504030201010203040x12x1+x2504x1+3x2120可行域同时满足：4x1+3x21202x1+x250x10x20的区域——可行域8x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形2x1+x2504x1+3x21209x2504030201010203040x1可行域目标函数是以Z作为参数的一组平行线x2=Z/30-（5/3）x12x1+x2504x1+3x212010x2504030201010203040x1可行域当Z值不断增加时，该直线x2=Z/30-（5/3）x1沿着其法线方向向右上方移动。2x1+x2504x1+3x212011x2504030201010203040x1可行域当该直线移到Q2点时，Z（目标函数）值达到最大：MaxZ=50*15+30*20=1350此时最优解（x1，x2）=（15，20）Q2（15，20）有唯一最优解2x1+x2504x1+3x212012例2解线性规划0,052222..max2121212121xxxxxxxxtsxxz1x2x01A2A3A4A2221xx3z5.1z0z521xx2221xxDTx4,1有唯一最优解13对于线性规划问题，我们定义：可行解：满足全部约束条件的决策向量XRn。可行域：全部可行解构成的集合。（它是n维欧氏空间Rn中的点集，而且是一个“凸多面体”)最优解：使目标函数达到最优值（最大值或最小值，并且有界）的可行解。无界解：若求极大化则目标函数在可行域中无上界；若求极小化则目标函数在可行域中无下界。144z21,AA1x2x01A2A3A4A2221xx521xx2221xxD0,052222..max2121212121xxxxxxxxtsxxz2124minxxz有无穷多最优解例3解线性规划Z=0Z=-215例4解线性规划1x2x00,0331..2min21212121xxxxxxtsxxz121xxAB3321xx212xxzD有无界解16例5：MaxZ=3X1-2X2X1+X2=12X1+2X2=8X1,X2=0无可行解1x2x082221xx121xx17结论：1、线性规划问题的可行域为凸集2、若有最优解一定可以在其可行域的顶点上得到线性规划问题解的几种情况：1、有唯一最优解2、有无穷多最优解3、无可行解4、无最优解18第三节单纯形法----原理单纯形法：单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。19定义1：基(基阵)——由A中一个子矩阵B是可逆矩阵，则方阵B称为LP问题的一个基。A=(P1…PmPm+1…Pn)=(BN)基向量非基向量…X=(X1…XmXm+1…Xn)T=(XBXN)T基变量非基变量XBXN…线性规划问题解的概念20例1、X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50121003201002001P1P2P3P4P5A=21AX=b的求解A=(BN)X=(XBXN)TXBXN(BN)=bBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN22定义2：基本解——对应于基B，X=为AX=b的一个解。B-1b0定义3：基本可行解——基B，基本解X=若B-1b0，称基B为可行基。最优解、最优基B-1b0※基本解中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!23X1X2X3X4X5X=b=306024B=(P3P4P5)=I可逆基N=(P1P2)X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2例1：24令X1=X2=0,X3=30,X4=60,X5=24X===XN0XBB-1b00306024121又：Ｂ1=(P1P2P3)=320020|B1|=6≠0,B可逆25X1=12-(1/3X4-1/3X5)X2=12-(1/2X5)X3=-6-(-1/3X4-2/3X5)令X4=X5=0X=(12,12,-6,0,0)TZ=40X1+50X2=40[12-(1/3X4-1/3X5)]+50[12-1/2X5]=1080+(-40/3X4-35/3X5)基本解，但不可行26例2：给定约束条件-X3+X4=0X2+X3+X4=3-X1+X2+X3+X4=2Xj0(j=1,2,3,4)求出基变量是X1,X3,X4的基本解，是不是可行解？270-11解：B=(P1P3P4)=011-11101-10B-1=-1/21/2031/21/202b=28X1X3=B-1bX4XB=01-101=-1/21/203=3/21/21/2023/2∴X=(1,0,3/2,3/2)T是29定义1：凸集——D是n维欧氏空间的一个集合X(1),X(2)∈D,若任一个满足X=X(1)+(1-)X(2)(01)有X∈D线性规划问题的几何意义30X(1),X(2),…,X(k)是n维欧氏空间中的k个点，若有一组数µ1,µ2,…,µk满足0µi1(i=1,…,k)定义2µi=1ki=1有点X=µ1X(1)+…+µkX(k)则称点X为X(1),X(2),…,X(k)的凸组合。凸组合31凸集D,点XD，若找不到两个不同的点X(1),X(2)D使得X=X(1)+(1-)X(2)(01)则称X为D的顶点。定义3顶点32定理1：LP问题的可行解域一定是凸集。引理1：线性规划问题的可行解X为基可行解的充分必要条件是：X的非零分量(=0)所对应的系数矩阵A的列向量是线性无关。？33定理2：线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。引理2：D为有界凸多面集，XD，X必可表为D的顶点的凸组合。定理3：可行域有界，最优值必可在顶点得到34定理2：可行域中点X是顶点X是基本可行解。定理3：LP有最优解，必定可以在可行域(凸多面集)的顶点得到。可行解基本解定理1：LP问题的可行域一定是凸集(凸多面集)