最优化课件-精品文档.ppt

-1O24x1x224－▽z=(3,2)-2x1+x2=2x1-3x2=3-1O33（4）无可行解某些线性规划问题的可行域是空集,既不存在满足所有约束条件的点,这时问题无可行解,当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求,既不存在可行方案。（3）无界解（或称无最优解）无界解是指线性规划问题的最优解无界。若是极大化问题,则可使目标函数值z→+∝,极小化问题则可使目标函数值z→-∝,有无界解的线性规划问题的可行域通常是无界区域,但反之则不必然。1.标准线性规划模型(1)线性规划问题的标准形式:?其中(1.1)为目标函数，(1.2)为约束条件，(1.3)为非负条件，为称呼方便，有时将(1.3)也称为约束条件。（1.2）（1.3）1.3线性规划的标准形式（1.1）其中C=(c1,c2,…,cn)称为价值向量,X=(x1,x2,…,xn)T为决策变量向量,Pj=(a1j,x2j,…,xmj)T为决策变量xj所对应的消耗系数向量,b=(b1,b2,…,bm)T为资源向量。(2)紧凑格式:(3)向量格式:*其中为m×n阶矩阵(4)矩阵格式:C=(c1,c2,…,cn),X=(x1,x2,…,xn)T,b=(b1,b2,…,bm)T。2.非标准形式线性规划问题的标准化（1）极大化与极小化:原目标函数(2)?线性不等式与线性等式:其中xn+i为非负松弛变量,其中xn+k为非负剩余变量。*(3)非负变量与符号不受限制的变量若xi的符号不受限制,则可引进非负变量xi1,xi2,令xi=xi1-xi2,使线性规划里所有的变量都转化为有非负限制的变量。(4)右端项有负值的问题:在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以－1，得到:－ai1x1－ai2x2－…－ainxn=－bi。*例6:将下述线性规划问题化为标准型符号不受限制解:令,可将目标函数化为min型,令,其中*考虑一个标准的线性规划问题:1.4标准型线性规划的解其中Ｃ为n维行向量,Ｘ是n维列向量,ｂ是m维列向量,Ａ是m×n阶矩阵,假定满足m≤n,且Ｒ(Ａ)=m.*(2)最优解:使目标函数（1.4)达到最优值的的可行解称为最优解,最优解常用X*表示。?????(3)基:若Ｂ是Ａ中m×m阶非奇异矩阵,即|Ｂ|≠0,则称Ｂ是线性规划问题的一个基。可行解集称为线性规划问题的可行域。线性规划问题解的概念:(1)可行解:满足约束条件(1.5)，(1.6)的解称为线性规划问题的可行解。*一个线性规划的基通常不是唯一的,但是基的个数也不会超过Cnm个。一旦确定了线性规划的基,则相应的基向量、基变量和非基变量也就确定。若Ｂ是线性规划问题的一个基,那么Ｂ一定是由m个线性无关的列向量组成,不失一般性,可设称为基向量,与基向量Pj相对应的变量xj(j=1,2,…,m)称为基变量。*(4)基本解。设B是线性规划的一个基,若令n-m个非基变量等于0,则所得的方程组ＡＸ=b的解称为线性规划问题的一个基本解（简称基解）。有一个基就可以求得一个基本解。由基的有限性可知,基本解的个数也不会超过Cnm个。由于基本解中的非零分量可能是负数,所以基本解不一定是可行的。(5)基本可行解。满足非负条件的基本解称为基本可行解(简称基可行解)。与基本可行解对应的基成为可行基。基本可行解的非零向量的个数小于等于m,并且都是非负的。由于基本可行解的数目一般少于基本解的数目,因此可行基的数目也要少于基的数目。当基本可行解中有一个或多个基变量是取零值时,称