最优化方法课件053详解.ppt

§5.5 初始基可行解的求法 对于线性规划问题 min cTx s.t. Ax≤b(b≥0) x≥0 5.5.1 大M单纯形法 对于线性规划问题 考虑辅助规划中的目标函数 大M方法算例 例5.5.1 用大M单纯形法求解线性规划 min f(x)=-3x1+x2+x3 s.t. x1-2x2+x3 ≤11 -4x1+x2+2x3-x4=3 -2x1 +x3 =1 x1,x2,x3,x4≥0 单纯形方法求解 第一步的判别数:s1=-3-1·0-(-4)M-(-2)M=6M-3 类似地可以给出其它各个判别数. 续表 求得辅助规划问题的最优解为 (4,1,9,0,0,0,0)T ,原线性规划的最优解为(4,1,9,0)T,最优值为-3·4+1·3+1·9=-2. 5.5.2 两阶段单纯形法 对于线性规划问题 两阶段法算例 例5.5.2 用两阶段法求解线性规划min 4x1+x2+x3s.t. 2x1+x2+2x3=4 3x1+3x2+x3=3x1,x2,x3≥0 单纯形表 单纯形表 求解原线性规划的单纯形表 得到原线性规划的最优解x*=(0,2/5,9/5)T,最优值f*=11/5. 引入松弛变量化为标准型 min cTx s.t. Ax+IxS=b x,xS≥0 其中I是单位矩阵,xS=(xn+1,···,xn+m)T.则可以将xS作为基变量,以(0, ···,0,b1,···,bm)T为初始基可行解进行单纯形迭代. 对于一般的线性规划问题,无法简单给出初始基可行解. 初始基可行解的确定 人工变量法 单纯形法是从一个初始基可行解开始的，如果在线性规划问题的系数矩阵中不存在一个m阶单位矩阵，即很难找到一个初始可行基怎么办？ 思路：人为构造一个单位矩阵 人工变量 人工变量 引入人工变量xn+1,···,xn+m,构造辅助线性规划问题 充分大的数 称为罚函数 M是相当大的正数(可以理解为正无穷),对人工变量起到惩罚的作用,逼迫辅助线性规划的最优解中人工变量均为0. 定理：若辅助规划的最优解(x1,x2,···,xn+m)中人工变量不全为0(设xr≠0),则原规划无可行解. 如若不然,设原规划有可行解 则 是辅助规划可行解. 引入松弛变量x5,人工变量x6,x7,构造辅助线性规划 min –3x1+x2+x3+Mx6+Mx7 s.t. x1-2x2 +x3 +x5 =11 –4x1+x2+2x3-x4 +x6 =3 –2x1 +x3 +x7=1 x1, ···,x7≥0 注:根据线性规划问题本身的形式,可以少引进 一些人工变量. 1 -2 1 0 1 0 0 -4 1 2 -1 0 1 0 -2 0 1 0 0 0 1 11 3 1 x5 x6 x7 0 M M x1 x2 x3 x4 x5 x6 x7 b xB cB -3 1 1 0 0 M M cj sj 6M-3 -M+1 -3M+1 M 0 0 0 qi 11 3/2 1 x3进基, x7离基,标出主元. ( ) 注:人工变量一旦离基,则在迭代时不再参与计算. 6M-3 -M+1 -3M+1 M 0 0 0 s j 1 -2 1 0 1 0 0 -4 1 2 -1 0 1 0 -2 0 (1) 0 0 0 1 11 3 1 x5 x6 x7 0 M M x1 x2 x3 x4 x5 x6 x7 b xB cB -3 1 1 0 0 M M cj