运筹学第2章 单纯形法.pptx

管理运筹学 ——模型与方法赵明霞山西大学经济与管理学院第2章　单纯形法2.1　基本思想2.2　基本方法2.3　其它法则2.1 单纯形法的基本思路单纯形法内容原本方法对偶方法形式方程组形式表格形式矩阵形式求出一个初始基可行解判断基可行解是否最优结束求目标值得以改善的基可行解需要解决的问题： (1)如何确定初始的基可行解？ (2)目标函数何时达到最优——判断标准是什麽？ (3)为了使目标函数逐步变优，怎么转移？ 单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。线性规划的典式标准形为典式的充要条件：系数矩阵中存在一个满秩单位阵。典式标准形是单纯形法的唯一必要前提。基本性质：线性规划问题的可行域是凸集。标准形线性规划的基本可行解与可行域的极点互相对应。线性规划的基本定理 对标准形线性规划问题（M）：若有可行解，则必有基本可行解；若有最优解，则必有最优基本解。若LP问题的可行域R≠Φ，则R至少有一个极点。LP问题可行域R的极点为有限个。2.2 单纯形法的基本方法（表格形式）情况一： 约束条件为 ≤1、确定初始基可行解对于每个条件加上松弛变量,在约束系数矩阵中的单位矩阵可以构成初始基例2-1  max z=3x1+ 2x2 s.t. x1 +x3=6 2x2+x4=8 2x1+3x2+x5=18 xj≥0 （j=1,2,3,4,5）它的系数矩阵 其中aj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n。可看出 x3, x4 和 x5 的系数列向量构成一个基:当令非基变量 x1， x2为零时,可得 x3= 6 ， x4 =8 , x5= 18 （0，0，6，8，18）是初始基本可行解2、最优性检验判断已求得的基本可行解是否是最优解。（1）最优性检验的依据——检验数σj（2）最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数，则这个基本可行解是最优解。对于求目标函数最小值的情况，只需 σj≤0CBcjc1c2…cmcm+1…cn比值bi/aik基bx1x2…xmxm+1…xnc1x1b110…0a1,m+1…a1nc2x2b201…0a2,m+1…a2ncmxmbm00…1am,m+1…amn00…0……………………………3、 基变换(1)入基变量的确定——最小检验数规则 从最优解判别定理知道，当某个σj0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数小于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上σj0的，则为了使目标函数增加得更大些，一般选其中的σj最小者的非基变量为入基变量。在本例题中σ1=-3是检验数中最小的负数，故选x1为入基变量。同时，入基变量xk的系数列向量ak为主列。(2)出基变量和主元的确定——最小比值规则确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bi值都大于等于零。出基变量xl所在行的系数alj构成主行。确定主元的方法：主行（最小比值所在的约束方程）与主列（入基变量系数列）交于alk为主元。基变换通过初等变换实现，目标：将主列化为单位向量（alk=1），以符合典式例2-1  max z=3x1+ 2x2 s.t. x1 +x3=6 2x2+x4=8 2x1+3x2+x5 =18 xj≥0 （j=1,2,3,4,5）x1为入基变量，我们把各约束方程中x1的为正的系数除对应的常量，得所以，出基变量应为x3，主元为a13例2-2 初始单纯形表cj32000bi/aikXBbx1x2x3x4x50xxx0-3-2000cj32000bi/aikXBbx1x2x3x4x50x36①010060xx90-3-20003x1610100-0x0x560③-3x1x44004/31-2/32x2201-2/301/322005/302/3情况二： 约束条件为≥，=例2-3标准化非典式添加人工变量1、大M法例2-3添加人工变量x5来人为的创造一个单位矩阵作为基M叫做罚因子，任意大的数。人工变量只能取零值。必须把x5从基变量中换出去，否则无解。cj3200-Mbi/aikXBbx1x2x3x4x5-Mx52②1-10110x43-12010-2M-2M-3-M-2M003x1111/2-1/201/20x4405/2-1/211/230-1/2-3/203/