第三章 单纯形方法 §1 单纯形方法原理 §2 两阶段法与大M法 §3 退化情形 §4 修正单纯形法
第三章 单纯形方法 ◼ §1 单纯形方法原理 ◼ §2 两阶段法与大M 法 ◼ §3 退化情形 ◼ §4 修正单纯形法
§1单纯形法的基本原理 单纯形法(Simplex Method)是1947 年由G.B.Dantig提出，是解LP问 题最有效的算法之一，且已成为整数 规划和非线性规划某些算法的基础。 基本思路： 基于LP问题的标准形式，先设法找到一个基可 行解，判断它是否是最优解，如果是则停止计算；否 则，则转换到相邻的目标函数值不减的一个基可行解 (两个基可行解相邻是指它们之间仅有一个基变量不 相同)
§1 单纯形法的基本原理 单纯形法（Simplex Method）是1947 年由 G.B. Dantzig 提出，是解 LP 问 题最有效的算法之一，且已成为整数 规划和非线性规划某些算法的基础。 基本思路： 基于 LP 问题的标准形式，先设法找到一个基可 行解，判断它是否是最优解，如果是则停止计算；否 则，则转换到相邻的目标函数值不减的一个基可行解. （两个基可行解相邻是指它们之间仅有一个基变量不 相同）
第三章 单纯形法 单纯形法引例 minf=-15x1-25x2+0x3+0x4 s.t. x1+3x2+X3 =60 首先，化原问 X1+X2 +x4=40 题为标准形式： X1,X2,X3,X4≥0 =(PiP.Ps-Pa) B=(P,P4)是可行基， x,x4是基变量. 是最优解吗 基变量用非基变量表示： x3=60-x1-3x2 x4=40-x1-X2 代入目标函数：f=-15x125x2 令非基变量x1=x20f-0基可行解x和=(0,0,60,40)
第三章 单纯形法 单纯形法引例 首先，化原问 题为标准形式： ( 1 2 3 4 ) 1 3 1 0 , , , 1 1 0 1 A p p p p = = x3 , x4 是基变量. B p p = ( 3 4 , )是可行基， 基变量用非基变量表示： x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2 代入目标函数： f = -15 x1 -25 x2 令非基变量 x1= x2=0 f=0 基可行解 x (0)=(0,0,60,40)T 是最优解吗？ max z = 15x1 +25x2 s.t. x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1，x2 ≥ 0 min f = -15x1 - 25x2 + 0x3 + 0x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1，x2 , x3 , x4≥ 0
§1.1单纯形法的基本原理 f=-15x1-25x2 因为x2的系数小，所以x2换入基变量。 x3=60-x1-3x2 谁换出？ x3=60-3x2≥0 x4=40-x1-X2 x4=40-x2≥0 如果x4换出，则x2=40,x3=60,不可行。 如 2=20,x4=20。 小于零！ 0 40 13 20所以x3换出。 最小比值法则 基变量用非基变量表示： x=20-⅓x-⅓x x4=20-2⅓x+⅓x 代入目标函数：f=-50020/3)x1+25/3x3 令非基变量x1=x30 f=-300 基可行解x=(0,20,0,20)
§1.1 单纯形法的基本原理 f = -15 x1 -25 x2 x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2 因为x2 的系数小，所以x2 换入基变量。 x3 = 60 - 3x2 ≥ 0 x4 = 40 - x2 ≥ 0 谁换出？ 如果 x4 换出，则x2 = 40， x3 = -60，不可行。 如果 x3 换出，则x2 = 20， x4 = 20。 2 60 40 min , 20 3 1 x = = 取 所以 x3 换出。 最小比值法则 基变量用非基变量表示： 2 1 3 4 1 3 20 1 1 3 3 20 2 1 3 3 x x x x x x = − − = − + 代入目标函数： f = -500-20/3 x1+ 25/3 x3 令非基变量 x1= x3=0 f= -500 基可行解 x (1)=(0,20,0,20)T 小于零！
第三章 单纯形法 f=-500-23x+253x 因为x1的系数小，所以x1换入基变量 2020 x=20-为x-为x 因 x=min 323 =30 x=20-23x+⅓x 所以x4换出。 x=30+x-32x。 基变量用非基变量表示： x=10-5x+5x 代入目标函数： f=-700+5x3+10x4 令非基变量x3=x4=0 f-700基可行解x2=(30,10,0,0) 因为非基变量的系数都大于零， 所以 x2=(30,10,0,0)T是最优解 fmim=-700,2ma=700
第三章 单纯形法 1 3 2 1 3 4 1 3 20 25 500 3 3 20 1 1 3 3 20 2 1 3 3 f x x x x x x x x = − − + = − − = − + 因为x1 的系数小，所以x1 换入基变量。 1 20 20 min , 30 1 2 3 3 x = = 因 所以 x4 换出。 基变量用非基变量表示： 1 3 4 2 3 4 30 1 3 2 2 10 1 1 2 2 x x x x x x = + − = − + 代入目标函数： f = -700 + 5 x3 +10 x4 令非基变量 x3= x4=0 f=-700 基可行解 x (2)=(30,10,0,0)T 因为非基变量的系数都大于零， 所以 x (2)=(30,10,0,0)T 是最优解 fmin =-700，zmax=700