第2章图解法与单纯形法改.pptVIP

第二章 线性规划的图解法与单纯形解法;2.1 线性规划问题的图解法;x1;2.1 线性规划问题的图解法;2.1 线性规划问题的图解法;2.1 线性规划问题的图解法;2.1 线性规划问题的图解法;2.1 线性规划问题的图解法;图解法虽然只能用来求解只具有两个变量的线性规划问题, 但它的解题思路和几何上直观得到的一些概念判断, 对下面要讲的求解一般线性规划问题的单纯形法有很大启示:;线性规划的基本性质; 线性规划的基本性质; 从可行域中的一个基可行解出发，判别它是否已经是最优解，如果不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。;【例2】用单纯形法求下列线性规划的最优解 ;单纯形法的计算步骤：;【解】首先化为标准型，加入松驰变量x3、x4则标准型为;单纯形法的计算步骤：;进基列 ;单纯形算法的计算步骤 ;2.2 线性规划单纯形法的原理与计算步骤;单纯形法的计算;最优解的判别定理;单纯形法的计算;最优解的判别定理;单纯形法的计算;XB ;唯一最优解的判断：最优表中所有非基变量的检验数 小于零,则线规划具有唯一最优解 。 多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。 无界解的判断: 某个 且aij≤０（i=1，2,…,m）则线性规划具有无界解;【练习1】 用单纯形法求解;Cj ;【练习2】求解线性规划;初始单纯形表为;【练习3】求解线性规划;; 表 (3)中λj全部非正,则最优解为:;单纯形法计算的矩阵描述;单纯形法计算的矩阵描述 ;单纯形法计算的矩阵描述;单纯形法计算的矩阵描述;单纯形法计算的矩阵描述;单纯形法计算的矩阵描述;人工变量法 人工变量法的基本思路是： 若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 ;线性规划求解的人工变量法;线性规划求解的人工变量法;;;;线性规划求解的大M法;;【例6】用大M法解 下列线性规划;【解】首先将数学模型化为标准形式;Cj;最优解X＝（31/3，13，19/3，0，0)T；最优值Z＝152/3;;线性规划求解的两阶段法;线性规划求解的两阶段法;??例】用两阶段单纯形法求解例【6】的线性规划。; 【解】标准型为;Cj ;最优解为 最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为;Cj ;【练习】用两阶段法求解线性规划。 ;【解】第一阶段问题为 ;Cj ;解的判断;【习题1】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%~55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。;解: 设xj（j=1,2，…，5）是第j 种矿石数量，得到下列线性规划模型 ;;;;;