《运筹学教学资料》运筹学第1章5-6节[2014].ppt

-1- China University of Mining and Technology 运筹学第一章第一章线性规划线性规划§1 线性规划问题及其模型§2 线性规划问题几何意义§3 单纯形法§4 单纯形法计算步骤§5 单纯形法进一步讨论§6 应用举例-2- China University of Mining and Technology 运筹学 单纯形法进一步讨论学习要点: --人工变量法: 两阶段法、大 M法; -3- China University of Mining and Technology 运筹学?单纯形法是依据可行基迭代而设计的?即从一个基可行解构造另一个使目标函数值更好的基可行解。?如何寻找第一个基可行解(an initial basic feasible solution) 呢? 1 2 3 1 4 2 1 2 3 4 3 2 18 4 2 12 , , , 0 x x x x x x x x x x ? ? ???? ??????????初始基不明显, 或者松弛变量个数比约束方程个数少的情况,问题又应该如何解决? ?在解决线性规划问题时会碰到下面一种情况: 单纯形法进一步讨论-4- China University of Mining and Technology 运筹学解决方法一: 通过初等行变换,变换出一组 m个线性不相关的向量来组成 m 阶初始基矩阵。不利于计算机编程实现,因为如何确定“一组 m个线性不相关的向量”是很随机的问题,手工解决比较方便,在程序上的实现就很困难。解决方法二: 两阶段法和大 M法(the Big M Method )。当约束方程的系数矩阵 A不包含一个同阶的单位矩阵,我们就需要引入若干非负变量,又称为人工变量( an artificial variable ),从而构造出一个新的线性规划问题,使其容易找出一个初始基可行解。单纯形法进一步讨论-5- China University of Mining and Technology 运筹学?人工变量法?如果约束条件全为“≤”,且右边常数全为非负, 则引进的松弛变量就可以作为初始的基变量,得到一个初始的基础可行解。?如果约束条件有“=”,右边常数全为非负,则需要加上非负人工变量,建立辅助问题。?如果约束条件有“≥”,右边常数全为非负,则需要减去非负人工变量,建立辅助问题。单纯形法进一步讨论-6- China University of Mining and Technology 运筹学两阶段法:假定约束方程的系数矩阵 A不包含同阶的单位矩阵 nnxcxcxcz???? 2211 max 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 2 . . 0, 0, , 0 n n n n m m mn n m n a x a x a x b a x a x a x b s t a x a x a x b x x x ? ?????? ???????? ????? ? ???????????加入人工变量?? 11 1 12 2 1 1 1 21 1 22 2 2 2 2 1 1 2 2 0 1, 2, , n n n n n n m m mn n n m m j a x a x a x x b a x a x a x x b a x a x a x x b x j n m ????? ?????? ????????? ??????? ???????????改变目标函数 1 2 min ' n n n m z x x x ? ? ?? ????初始基目标函数在可行域上有一个明显的下界所以它一定有最优解,利用单纯形法可以求解。此为第一阶段,求解后进入第二阶段。' 0 z? 初始基的确定: 单纯形法进一步讨论-7- China University of Mining and Technology 运筹学?引进松弛变量,使约束条件全为等式。?引进人工变量,建立辅助问题。辅助问题的目标函数为各人工变量之和(仅含人工变量)。?用人工变量作为辅助问题的初始基变量,用单纯形法求解辅助问题,得到辅助问题的最优解和最优解的目标函数值。?如果辅助问题最