运筹学单纯形概念(名校义).PPTVIP

第四讲 单纯形概念 §1 基本假设：非退化阵 §2 单纯形算法 §1 基本假设：非退化阵（1） 在推导单纯形算法时，在理论上作出非退化假设。 标准规划形式： 其中，A为m行n列， mn 则作2个假设： 1．A阵的秩为m，即m行线性独立。 2．b(m维向量)是不少于m列的线性组合，即在 中，X至少有m个正分量。 §1 基本假设：非退化阵（2） 第1个假设表明，AX=b总是有解，如果该假设失败，则有下 述两种情况： ① 不独立，或者 ② 不合理 例如， ，显然两行成正比例，A阵秩为1。 若有AX=b，b=(b1,b2)T，必有2种情况： 设b2=2b1，说明不独立。 b2≠2b1，产生矛盾，不合理。 §1 基本假设：非退化阵（3） 对于这个假设失败,可作如下处理:如行间不独立,可消去一 行或几行,使之独立；如果不合理,则方程无解,不考虑。 第2个假设表明，可行解的正分量个数不少于m个，若失败， 即为退化问题。例如方程 (1) §1 基本假设：非退化阵（4） 则b= 可由a3= 单独组合而成，即可得可行解X= 。 这种现象有时会给单纯形算法造成困难。 其解决方法是对b加一小扰动，即令b = ， 这样就会使假设2成立。 后面在推导单纯形算法时，都指非退化情况，除非加以特殊说明。 §2 单纯形算法（1） 单纯形算法根据寻找基础可行解的步骤可分为大M（T）法和 两阶段法，这两个方法无本质区别，下面主要阐述两阶段法。 两阶段法的主要步骤为两项： ??? 找出规划的第1个基础可行解或证明无可行解； ?从第1个基础可行解开始，逐步找了最优解或证明无最优解。 这两项工作可在有限步数内完成。现分别叙述这两个阶段是如 何完成的。 1．进行第一阶段——找出第1个基础可行解（假设第2阶段已经会作。）设在规划中的约束部分 §2 单纯形算法（2） (2) 其中，bi0(否则该方程乘以-1) 为了求出这个原规划的第1个基础可行解，可据此构造一个新规 划： §2 单纯形算法（3） 则这个新规划的第1个基础可行解可立即得到： xj=0 (j=1,…,n) zi=bi (i=1,…,m) (4) 新规划具有m个方程，m+n个未知量，其矩阵表达式为 §2 单纯形算法（4） 由于新规划的构成本身可提供第1个基础可行解，于是便可采用 第2阶段法去寻求新规划的最优解。其寻优结果有2种可能性： ①min =0,则新规划最优解（X*，Z*）的X*必是原规划的1个 基础可行解。 ②min 0，则说明原规划无可行解。 [例1-5]原规划为： (6) 则新规划为： (7) 新规划最优解为：z1=3，x1=0，x2=0。 ∵z10。故原规划无可行解。 §2 单纯形算法（5） 2．进行第2阶段——寻找最优解 1．在叙述寻优步骤前，首先引入非退化定理（略）。 ??? ① 非退化定理 ② 阶段2的进行步骤 令X是非退化阵A的标准线性基础可行解，则可由此导出最优 解X* 。 设在规划：AX=b，X0，CTX=min中，B是可行解中取正值分 量的角标j之集合。 即： B={j：xj0} §2 单纯形算法（6） 显然，如果A阵具有m行且B含m项，则称B是基础解集， ∣B∣=m。因此，基础解X依赖于基础解集B中的j所对应的列aj， 又称基础列，这m个基础列组成m×n矩阵，这是一个可逆阵。 [例1-7] 给出约束条件阵为： 若给定基础可行解XT=[1,0,1],则x10，x30,其基础解集 B={1,3}，B有2项，∣B∣=2。则解X依赖于两列（1，3列） 组成的基础阵 §2 单纯形算法（7）