最优化第二章线性规划.ppt

第2章　线性规划 线性规划的历史 渊源要追溯到Euler、Liebnitz、Lagrange等 George Dantzig, Non Neumann(Princeton)和Leonid Kantorovich在1940’s创建了线性规划 1947年, George Dantzig于发明了单纯形法 1979年，L. Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法－椭球内点法) 1984年，Narendra Karmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者(投影内点法) 现在求解大规模、退化问题最有效的是原－对偶内点法 EX. 运输问题 EX. 化成标准形 线性规划问题解的几种情况 无界：没有有限最优解 不可行：没有可行解 单纯形法简介 1、确定初始的基本可行解 （4）求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量x3所对应的系数列向量 变换成换出变量x4所对应的单位向量 , 注意保持基变量x5的系数列向量 为单位向量不变。 第一行除以２ 第二行减去第一行 —————————————————————————— 可得改进的基本可行解。 　　　　　　　　　，基变量　　，　　　非基变量　　　　　。 　　　　　　　　　　　 　　　　　　　　　　　　　　　基本可行解 　　　　　　 目标函数值 易见目标函数值比原来的Z=-1增加了， 再转向步骤(2) （2）检验　　　　　　　　　 是否最优。 检验向量 　 　因为　　　　　　　， 　所以　　　　　　　　　　仍不是最优解。 （3）基本可行解　　　　　　　　　　的改进 ①??? 选取换入变量 　　因为　　　　　，取　　为换入变量。 ②??? 选取换出变量 　　　　　　　　　　　　　　　　　且　　　　 ， 　选取　为换出变量. （4）求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量　　所对应 　的系数列向量　　　　变换成换出变量　　所对应的单位向量 　　 , 第二行乘以２/５ 第一行减以第二行的１/２倍 —————————————————————————— 可得改进的基本可行解。 　　　　　　　　　，基变量　　　，非基变量 　　　　　　　　　　　　 　　　　　　　　　　　　　　基本可行解 　　　　　　 目标函数值 比Z=15增加了，再转向步骤(2) （2）检验　　　　　　　　　　 是否最优。 检验向量 　 　　　因为所有检验数均小于零， 　所以　　　　　　　　　　　　　是最优解， 单纯形表 　通过例１我们发现，在单纯形法的求解过程中，有下列重要指标： 每一个基本可行解的检验向量 根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。 每一个基本可行解所对应的目标函数值 通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。 当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知： 可将这些重要结论的计算设计成如下一个简单的表格， 即单纯形表来完成： CB CN- CBN 0 CBb Z θ1 θ2 . . θm N I b1 b2 . . bm X1 X2 ? . Xm C1 C2 . . Cm X m+1 Xm+2 ··· Xn X1 X2 ··· Xm b XB CB θ CN C 　例2、试利用单纯形表求例1中的最优解解： 　　 　　得初始的单纯形表： 　初始基本可行解　　　　　　　　　　，Z= -1， 1 2 2 1 0 8 x4 -1 3 0 4 0 0 -1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 -1