怎样把事情做到最好.pptVIP

OR1*非标准型转化为标准型目标函数极小化转为极大化：minZ=－max(－Z)，一个数的极小化等价于其相反数的极大化。不等式约束的转化：∑aijxj≤bi加入松弛变量∑aijxj≥bi减去剩余变量非正变量：即xk≤0则令x’k=－xk自由变量：即xk无约束，令xk=x’k－x”k第29页，共70页，星期日，2025年，2月5日OR1*非标准型转化举例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2≤2004X1+5X2+x4=2003X1+10X2≤3003X1+10X2+x5=300X1≥0X2≥0Xj≥0j=1,2,…,5第30页，共70页，星期日，2025年，2月5日OR1*非标准型转化举例之二minZ=x1+2x2-3x3maxZ’=x’1－2x2+3(x’3－x”3)x1+x2+x3≤9－x’1+x2+x’3－x”3+x4=9-x1-2x2+x3≥2x’1－2x2+x’3－x”3-x5=23x1+x2-3x3=5－3x’1+x2－3(x’3－x”3)=5x1≤0x2≥0x3无约束x’1≥0x2≥0x’3≥0x”3≥0x4≥0x5≥0第31页，共70页，星期日，2025年，2月5日OR1*2.1.4基可行解基的概念：如前所述LP标准型和式：maxZ=∑cjxj∑aijxj=bixj≥0j=1,2,…,n矩阵式：maxZ=CXAX=bX≥0约束方程的系数矩阵A的秩为m，且mn。设A=B+N，B是A中m?m阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。nj=1nj=1第32页，共70页，星期日，2025年，2月5日OR1*基解的概念不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0)T称为基解。第33页，共70页，星期日，2025年，2月5日OR1*基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!第34页，共70页，星期日，2025年，2月5日OR1*例题6基可行解说明maxZ=70X1+120X2P1P2P3P4P59X1+4X2+X3=360941004X1+5X2+x4=200A=450103X1+10X2+x5=300310001Xj≥0j=1,2,…,5这里m=3,n=5。Cmn=10第35页，共70页，星期日，2025年，2月5日OR1*例题6基可行解说明基（p3,p4,p5），令非基变量x1,x2=0，则基变量x3=360,x4=200,x5=300,可行解基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=－250,x5=－600.非可行解基（p2,p3,p4），令非基变量x1,x5=0，则基变量x2=30,x3=240,x4=50,可行解（P21图）第36页，共70页，星期