《第3章(单纯形法的运用与改进)1.ppt》由会员分享，可在线阅读，更多相关《第3章(单纯形法的运用与改进)1.ppt（92页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3 单纯形法的运用与改进单纯形法的运用与改进u 初始可行基与人工变量法初始可行基与人工变量法u 求上界变量的单纯形法求上界变量的单纯形法u 单纯形法的讨论单纯形法的讨论u 单纯形法的矩阵描述单纯形法的矩阵描述u 改进单纯形法改进单纯形法x2x1zo4/5/202313 单纯形法的运用与改进3.1 初始可行基与人工变量法初始可行基与人工变量法u 辅助问题及人工变量辅助问题及人工变量u 两阶段法两阶段法u 大大 法法u 多余约束的剔除多余约束的剔除u 极小化问题的直接求解极小化问题的直接求解4/5/202323 单纯形法的运用与改进3.1.1 辅助问题及人工变量辅助问题及人工变量(A)max z=
2、c1 x1+c2 x2+cn xn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0(B)max =-xn+1-xn+2-xn+ms.t.a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 am1x1+amnxn +xn+m=bm x1 xn 0,xn+1 xn+m 0 X0=(x10,x20,xn0)T Y 0=(x10,x20,xn0,0,0)T 0=0X=(x1,x2,xn)T =0 Y=(x1,x2,xn,xn+1,xn+m)T4/5/202333
3、单纯形法的运用与改进辅助问题的性质辅助问题的性质 问题问题(B)是问题是问题(A)的辅助问题，的辅助问题，(B)中的单位矩阵称为人工基，它对应中的单位矩阵称为人工基，它对应的的m个变量叫做人工变量个变量叫做人工变量(artificial variables)。辅助问题辅助问题(B)有两个特点：有两个特点：(i)约束方程为典式，表明有可行约束方程为典式，表明有可行解；解；(ii)目标函数有上界，一定有最优目标函数有上界，一定有最优解。解。(B)max =-xn+1-xn+2-xn+ms.t.a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 am1x1+amnx
4、n +xn+m=bm x1 xn 0,xn+1 xn+m 0 B 0=(Pm+1,Pm+2,Pn)Y(0)=(0,0,b1,b2,bm)T 4/5/202343 单纯形法的运用与改进辅助问题的性质辅助问题的性质 问题问题(B)是问题是问题(A)的的辅助问题，辅助问题，(B)中的单位中的单位矩阵称为人工基，它对应矩阵称为人工基，它对应的的m个变量叫做人工变量个变量叫做人工变量(artificial variables)。辅助问题辅助问题(B)有两个有两个特点：特点：(i)约束方程为典式，约束方程为典式，表明有可行解；表明有可行解；(ii)目标函数有上界，目标函数有上界，一定有最优解。一定有最优解
5、。(B)max =-xn+1-xn+2-xn+ms.t.a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 am1x1+amnxn +xn+m=bm x1 xn 0,xn+1 xn+m 0 B 0=(Pm+1,Pm+2,Pn)Y(0)=(0,0,b1,b2,bm)T 4/5/202353 单纯形法的运用与改进原理与应用原理与应用 定理定理3.1 问题问题(A)有可行解的充要条有可行解的充要条件是：问题件是：问题(B)的目标函数最优值等于零。的目标函数最优值等于零。推论推论3.1 问题问题 (B)的最优基的基变的最优基的基变量组中不含人工变量，则这个最优基和相量
6、组中不含人工变量，则这个最优基和相应的基最优解分别是问题应的基最优解分别是问题(A)的可行基和的可行基和基可行解。基可行解。4/5/202363 单纯形法的运用与改进原理与应用原理与应用(续续)结论结论3.1 问题问题(B)的最优基的第的最优基的第l个基变量个基变量为人工变量，并且目标函数最优值等于零，而最为人工变量，并且目标函数最优值等于零，而最优单纯形表中非人工变量在第优单纯形表中非人工变量在第 l 行的系数全为零，行的系数全为零，则表示问题则表示问题(A)的第的第 l 个约束方程是多余的，应个约束方程是多余的，应予删除。予删除。标准形式线性规划问题的标准形式线性规划问题的 m个约束方程被
7、假个约束方程被假设为是相互独立的，上述结论中的情形在理论上设为是相互独立的，上述结论中的情形在理论上不会出现，但在实际中经常碰到。不会出现，但在实际中经常碰到。4/5/202373 单纯形法的运用与改进3.1.2 两阶段法两阶段法 依据推论依据推论3.1，可将问题，可将问题(A)的求解分为两阶的求解分为两阶段：段：阶段阶段 1 从人工基开始，用单纯形法求解问从人工基开始，用单纯形法求解问题题(B)，或是得到问题或是得到问题(A)的一个可行基和相应的的一个可行基和相应的基可行解，或是证实问题基可行解，或是证实问题(A)沒有可行解；沒有可行解；阶段阶段 2 从阶段从阶段1得到的初始可行基出发，用得
8、到的初始可行基出发，用单纯形法寻找问题单纯形法寻找问题(A)的最优解，或是查明问题的最优解，或是查明问题(A)沒有最优解。沒有最优解。4/5/202383 单纯形法的运用与改进两阶段法算例两阶段法算例例例3.1 用两阶段法求解问题用两阶段法求解问题max z=3 x1-x2-x3 s.t.x1-2x2+x3+x4 =11 -4x1+x2+2 x3 -x5=3 -2x1 +x3 =1 x1,x2,x50得得:max z=3 x1-x2-x3 s.t.3x1 +x4-2 x5=12 x2 -x5=1 -2x1 +x3 =1 x1,x2,x50解：解：max =-x6-x7 s.t.x1-2x2+x
9、3+x4 =11 -4x1+x2+2x3 -x5+x6 =3 -2x1 +x3 +x7=1 x1,x2,x704/5/202393 单纯形法的运用与改进表表3.1 求可行解求可行解(阶段阶段 I)4/5/2023103 单纯形法的运用与改进表表3.2 求最优解求最优解(阶段阶段 II)4/5/2023113 单纯形法的运用与改进3.1.3 大大 法法 大大 法是将原问题及其辅助问题合并，法是将原问题及其辅助问题合并，集线性规划问题可行解和最优解的求证于集线性规划问题可行解和最优解的求证于一役。一役。大大 法也称罚函数法。法也称罚函数法。4/5/2023123 单纯形法的运用与改进大大 法算例法
10、算例 例例3.1 max z=3 x1-x2-x3 s.t.x1-2x2+x3+x4 =11 -4x1+x2+2 x3 -x5=3 -2x1 +x3 =1 x1,x2,x50 解：解：max z=3 x1-x2-x3+0 x4+0 x5-M x6-M x7 s.t.x1-2x2+x3+x4 =11 -4x1+x2+2x3 -x5 +x6 =3 -2x1 +x3 +x7 =1 x1,x2,x70 辅助问题辅助问题max =-x6-x7s.t.x1-2x2+x3+x4 =11 -4x1+x2+2x3 -x5+x6 =3 -2x1 +x3 +x7=1 x1,x2,x704/5/2023133 单纯形
11、法的运用与改进大大 法的机理法的机理 形象地解释，变量在目标函数中的价值系数愈大，其形象地解释，变量在目标函数中的价值系数愈大，其对目标函数值的贡献愈大，则被录用为最优解的基变量的对目标函数值的贡献愈大，则被录用为最优解的基变量的可能性愈大。人工变量都是初始基变量，为了尽可能将人可能性愈大。人工变量都是初始基变量，为了尽可能将人工变量从基变量组中换出，通常把人工变量在合并问题目工变量从基变量组中换出，通常把人工变量在合并问题目标函数中的系数赋一个绝对值标函数中的系数赋一个绝对值 M 充分大的负数充分大的负数 M，M 称为惩罚因子。在代过程中，其价值系数称为惩罚因子。在代过程中，其价值系数 M
12、将迫使次将迫使次人工变量逐步换出基变量组，换出一个就删除一个。在这人工变量逐步换出基变量组，换出一个就删除一个。在这种机制下，如果人工变量仍留在最优基的基变量组中，则种机制下，如果人工变量仍留在最优基的基变量组中，则可断定原问题沒有可行解。可断定原问题沒有可行解。4/5/2023143 单纯形法的运用与改进表表3.3 大大 法法 的求解过程的求解过程 3 -1 -1 0 0 -M -M3-4M -1+M -1+2M 0 -M 0 -M4/5/2023153 单纯形法的运用与改进表表3.3 大大 法的求解过程法的求解过程(续续 1)4/5/2023163 单纯形法的运用与改进表表3.3 大大 法
13、的求解过程法的求解过程(续续 2)4/5/2023173 单纯形法的运用与改进大大 法的运用法的运用 例例例例3.23.2 将规划问题转化为将规划问题转化为(LP)的标准形式的标准形式。max z=x1+|x2|+x3 s.t.x1-x2+x32 2x1+3x2+x33 x10,1x334/5/2023213 单纯形法的运用与改进令：令：x2=x2-x2,x20,x20 x3=x3+1 0 x3 2 max z=1+x1+x2+x2+x3-Mx4-Mx4 s.t.x1-x2+x2+x3+x4-x4 =1 2x1+3x2-3x2+x3 +x5 =2 x3 +x6=2 x1,x2,x2,x3,x4
14、,x4,x5,x60设：设：x4=x4-x4,x40,x40 x5 0 x6 0令：令：z=z+1max z=1+x1+x2+x2+x3 s.t.x1-x2+x2+x3 1 2x1+3x2-3 x2+x3 2 x3 2 x1,x2,x2,x30 max z=x1+|x2|+x3 s.t.x1-x2+x32 2x1+3x2+x33 x10,1x33问题转化流程图问题转化流程图max z=x1+x2+x2+x3-Mx4-Mx44/5/2023223 单纯形法的运用与改进3.1.4 多余约束的剔除多余约束的剔除 线性规划问题的标准形式定义为线性规划问题的标准形式定义为max z=c1 x1+c2 x
15、2+cj xj+cn xn (1.1)s.t.a11x1+a12x2+a1 jxj+a1nxn=b1 a21x1+a22x2+a2 jxj+a2nxn=b2 (1.2)am1x1+am2x2+amjxj+amnxn=bm x1,x2,xj,xn0 (1.3)注：注：A=(P1,P2,Pm,Pm+1,Pn)是约束方程是约束方程(1.2)的的 mn系数矩阵，其秩为系数矩阵，其秩为 m。4/5/2023233 单纯形法的运用与改进多余约束的算例多余约束的算例 例例3.3 采用两阶段法和大采用两阶段法和大M法求解法求解线性规划问题。线性规划问题。max z=x1+x2+2x3+3x4 s.t.3x1+
16、2x2+x3+3x4=9 x1 +x2 +x3 =3 4x1+3x2+2x3+3x4=12 x1 x4 04/5/2023243 单纯形法的运用与改进算例问题的两阶段法求解算例问题的两阶段法求解例例例例3.33.3 max z=x1+x2+2x3+3x4 s.t.3x1+2x2+x3+3x4=9 x1 +x2 +x3 =3 4x1+3x2+2x3+3x4=12 x1 x4 0得得：max z=x1+x2+2x3+3x4 s.t.-(1/3)x2-(2/3)x3+x4=0 x1 +x2 +x3 =3 x1,x2,x40解：解：max z=-x5-x6-x7 s.t.3x1+2x2+x3+3x4+
17、x5 =9 x1 +x2 +x3 +x6 =3 4x1+3x2+2x3+3x4 +x7=12 x1 x7 04/5/2023253 单纯形法的运用与改进表表3.4 求可行解求可行解(阶段阶段 I)4/5/2023263 单纯形法的运用与改进表表3.5 求最优解求最优解(阶段阶段 II)4/5/2023273 单纯形法的运用与改进3.1.5 极小化问题的直接求解极小化问题的直接求解例例例例3.43.4 用两阶段法求解问题用两阶段法求解问题min z=-3 x1+x2+x3 s.t.x1-2x2+x3+x4 =11 -4x1+x2+2 x3 -x5=3 -2x1 +x3 =1 x1,x2,x50得
18、得:min z=-3 x1+x2+x3 s.t.3x1 +x4-2 x5=12 x2 -x5=1 -2x1 +x3 =1 x1,x2,x50解：解：min =x6+x7 s.t.x1-2x2+x3+x4 =11 -4x1+x2+2x3 -x5+x6 =3 -2x1 +x3 +x7=1 x1,x2,x704/5/2023283 单纯形法的运用与改进表表3.6 求可行解求可行解(阶段阶段 I)4/5/2023293 单纯形法的运用与改进表表3.7 求最优解求最优解(阶段阶段 II)4/5/2023303 单纯形法的运用与改进3.2 求变量有上界的单纯形法求变量有上界的单纯形法 标准形式线性规划问题
19、的决策变量都标准形式线性规划问题的决策变量都有非负限制，即有下界为零的限制。如果有非负限制，即有下界为零的限制。如果同时要求决策变量不大于某个正数，则问同时要求决策变量不大于某个正数，则问题称为变量有上界的线性规划问题。题称为变量有上界的线性规划问题。4/5/2023313 单纯形法的运用与改进上界问题的模型上界问题的模型 变量有上界的线性规划问题为变量有上界的线性规划问题为max z=c1 x1+c2 x2+cj xj+cn xn (1.1)s.t.a11x1+a12x2+a1 jxj+a1nxn=b1 a21x1+a22x2+a2 jxj+a2nxn=b2 (1.2)am1x1+am2x2
20、+amjxj+amnxn=bm 0 xj dj,j=1,2,n (1.3)其中：其中：aij，bi，cj，dj都是常数都是常数，xj 是未知变量。是未知变量。4/5/2023323 单纯形法的运用与改进3.3 单纯形法的讨论单纯形法的讨论4/5/2023333 单纯形法的运用与改进3.3.1 单纯形法的几何特征单纯形法的几何特征 单纯形法只关注问单纯形法只关注问题可行域的顶点，可行题可行域的顶点，可行域的其他点可以用顶点域的其他点可以用顶点的凸组合来表示。用单的凸组合来表示。用单纯形法求解线性规划问纯形法求解线性规划问题就是以一定的方式去题就是以一定的方式去访问这些顶点。访问这些顶点。4/5/
21、2023343 单纯形法的运用与改进单纯形法算例单纯形法算例 (附：图附：图3.8)例例例例3.5 3.5 用单纯形法求解问题用单纯形法求解问题max z=3x1+2x2s.t.-x1+2x2+x3 =4 3x1+2x2 +x4 =14 x1-x2 +x5=3 x1,x2,x50X(0)=(0,0,4,14,3)TX(1)=(3,0,7,5,0)TX(2)=(4,1,6,0,0)TX(3)=(5/2,13/4,0,0,15/4)T4/5/2023353 单纯形法的运用与改进单纯形法算例单纯形法算例 (附：图附：图3.9)max z=3x1+2x2s.t.-x1+2x2+x3 =4 3x1+2x
22、2 +x4 =14 x1-x2 +x5=3 x1,x2,x50X(0)=(0,0,4,14,3)TX(4)=(0,2,0,10,5)TX(3)=(5/2,13/4,0,0,15/4)TX(2)=(4,1,6,0,0)T4/5/2023363 单纯形法的运用与改进 B=(P2,P1,P3)CB=(c2,c1,c3)=(2,3,0)单纯形法算例单纯形法算例 (附：图附：图3.9)-1 2 1=3 2 0 1 -1 00 1/5 -3/5B-1=0 1/5 2/5 1 -1/5 8/50 1/5-3/50 1/5 2/51-1/5 8/5B-1P1=-1310=1 00 1/5-3/50 1/5 2
23、/51-1/5 8/5B-1P2=22-11=0 00 1/5-3/50 1/5 2/51-1/5 8/5B-1P3=1000=0 10 1/5-3/50 1/5 2/51-1/5 8/5B-1P4=0101/5=1/5 -1/50 1/5-3/50 1/5 2/51-1/5 8/5B-1P5=001-3/5 =2/5 8/50 1/5-3/50 1/5 2/51-1/5 8/5B-1b=41431=4 64/5/2023373 单纯形法的运用与改进图图3.1 单纯形法的几何解释单纯形法的几何解释-x1+x2=1例例例例1.31.3 图解变形图解变形max z=3x1+2x2s.t.-x1+2
24、x2 4 3x1+2x2 14 x1-x2 3 x1,x2 x50Ox1x2-Q2(4,1)Q3(5/2,13/4)Q4 (0,2)Q1(3,0)X(0)=(0,0,4,14,3)T X(1)=(3,0,7,5,0)T X(2)=(4,1,6,0,0)TX(3)=(5/2,13/4,0,0,15/4)T4/5/2023383 单纯形法的运用与改进图图3.2 单纯形法的弊端单纯形法的弊端Ox1x21212-1-1Q4/5/2023393 单纯形法的运用与改进3.3.2 退化退化 单单纯纯形形法法计计算算中中用用 规规则则确确定定换换出出变变量量时时，有有时时存存在在2个个以以上上相相同同的的最最
25、小小比比值值，这这样样在在下下一一次次迭迭代代中中就就有有一一个个或或几几个个基基本本量量等等于于零零，这这就就出出现现退退化化解解。这这时时换换出出变变量量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。，迭代后目标函数值不变。这时不同基表示为同一顶点。当当线线性性规规划划问问题题存存在在最最优优解解时时，在在非非退退化化的的情情况况下下，单单纯纯形形法法的的每每次次迭迭代代都都使使目目标标函函数数值值严严格格上上升升，经经过过有有限限次次迭迭代代，必必定定达达到到最最优优值值；而而对对于于退退化化情情况况，即即使使存存在在最最优优解解，也也有有可可能能出出现现循循环环现现象象，即
26、即迭迭代代过过程程总总是是重重复复解解的的某某一一部部分分序序列列，目目标标函函数数值值总总是是保保持持不不变变，永永远远达达不不到到最最优解。优解。4/5/2023413 单纯形法的运用与改进1.循环示例循环示例 1955年年，E.Beale找找到到了了一一个个至至今今为为止止最最简约的循环示例，展示如下。简约的循环示例，展示如下。例例例例3.63.6 用用单单纯纯形形法法求求解解下下述述线线性性规规划划问问题题，按这样的迭代规则：按这样的迭代规则：1.当不止当不止1个的个的j同时是正的时，选其同时是正的时，选其中绝对值最大的中绝对值最大的j对应的变量对应的变量 xj 作为换入变作为换入变量
27、；量；2.如果有如果有1个以上的基变量同时使个以上的基变量同时使达到达到最小，就取下标较小的那个基变量作为换出最小，就取下标较小的那个基变量作为换出变量。变量。4/5/2023423 单纯形法的运用与改进循环示例（续循环示例（续 1）Max z=(3/4)x1-150 x2+(1/50)x3-6x4s.t.(1/4)x1-60 x2-(1/25)x3+9x4+x5 =0 (1/2)x1-90 x2-(1/50)x3+3x4 +x6 =0 x3 +x7=1 xj0 (j=1,2,7)4/5/2023433 单纯形法的运用与改进循环示例（续循环示例（续 2）解：在这个例子中有一个很明显的可行解：在
28、这个例子中有一个很明显的可行基基 B=(P5,P6,P7)=(e1,e2,e3),相应的基相应的基可行解可行解X(0)=(0,0,0,0,0,0,1)T，而这是一个而这是一个退化基可行解。从这个可行基开始进行迭代，退化基可行解。从这个可行基开始进行迭代，表表3.4给出了前给出了前6 次的迭代的计算结果。在迭次的迭代的计算结果。在迭代过程中出现了代过程中出现了 6 个不同的基，而基解始终个不同的基，而基解始终没有变化。表中的没有变化。表中的6个基发生了循环，这个基发生了循环，这6个个基与同一个基解基与同一个基解X(0)=(0,0,0,0,0,0,1)T 相对相对应。应。4/5/2023443 单
29、纯形法的运用与改进表表3.10 循环循环4/5/2023453 单纯形法的运用与改进表表3.10 循环（续）循环（续）4/5/2023463 单纯形法的运用与改进2.解决循环的规则解决循环的规则 计算过程的循环现象尽管极少出现，但还是计算过程的循环现象尽管极少出现，但还是有可能的。如何解决这个问题，先后有人提出了有可能的。如何解决这个问题，先后有人提出了各种方法。这些方法早期有各种方法。这些方法早期有 “辞典序法辞典序法“，1952 年由年由 A.Charnes 提出的提出的 “摄动法摄动法“。1974年，勃兰特年，勃兰特(Bland)提出了一种避免循环的简便提出了一种避免循环的简便方法，称为
30、勃兰特规则。该方法当时在国际上引方法，称为勃兰特规则。该方法当时在国际上引起了广泛关注，被认为是线性规划领域中一项重起了广泛关注，被认为是线性规划领域中一项重要成果。要成果。4/5/2023473 单纯形法的运用与改进勃兰特勃兰特(Bland)规则规则 勃兰特勃兰特(Bland)规则规则 用单纯形法求解线性用单纯形法求解线性规划问题时按如下规则进行规划问题时按如下规则进行(l,k)旋转变换：旋转变换：1.在所有在所有j 0中中,选取下标最小的选取下标最小的j对应的对应的变量变量 xj 作为换入变量，即作为换入变量，即 k=min j|j 0,1 j n 2.如果有如果有1个以上的基变量同时使个
31、以上的基变量同时使达到最达到最小，就取下标较小的那个基变量作为换出变量，小，就取下标较小的那个基变量作为换出变量，即即 l=min Ji|(bi0/bik)=,1 i m 4/5/2023483 单纯形法的运用与改进3.3.3 算法复杂性理论算法复杂性理论 算法复杂性理论就是研究算法计算工作量的大小，算法复杂性理论就是研究算法计算工作量的大小，该理论依据算法计算工作量该理论依据算法计算工作量 (或计算时间或计算时间)的确上限与的确上限与问题规模参数问题规模参数 (变量数或方程数变量数或方程数)n 或或 m 的函数关系将的函数关系将算法分为两类：算法分为两类：u有效算法有效算法(多项式算法多项式
32、算法)算法计算工作量与问题规模呈多算法计算工作量与问题规模呈多项式函数关系，可表示为项式函数关系，可表示为 0(kna):k0na+k1na-1+ka-1n1+kan0,(a 1)u无效算法无效算法(指数算法指数算法)算法计算工作量与问题规模呈指数算法计算工作量与问题规模呈指数函数关系，即为函数关系，即为 0(kan):k0an+k1an-1+kn-1a1+kna0,(a 1)4/5/2023493 单纯形法的运用与改进适度增长与恶性膨胀适度增长与恶性膨胀u假设假设 a=2(1)，则有：则有：n n2 2n 1 1 2 2 4 4 3 9 8 8 64 256 16 256 65536 4/5
33、/2023503 单纯形法的运用与改进有效算法与无效算法有效算法与无效算法 求解求解 n 阶线性方程组的高斯消去法是一个多项式算阶线性方程组的高斯消去法是一个多项式算法，它的计算量为法，它的计算量为 (1/3)n3 的加法，的加法，(1/3)n3 的乘法，的乘法，(1/2)n2 的除法，即为的除法，即为0(k n3)。具有具有m 个约束个约束 n 个变量的线性规划问题可能有个变量的线性规划问题可能有 Cnm=n!/m!(n-m)!个基。显然个基。显然Cnm可表示为可表示为 Cnm=(n/m)(n-1)/(m-1)(n-m+1)/1 =a m,(a 1)这表明基的个数与问题规模是指数函数关系。这
34、表明基的个数与问题规模是指数函数关系。4/5/2023513 单纯形法的运用与改进单纯形法的计算复杂性单纯形法的计算复杂性 求解线性规划问题的单纯形法一般只需求解线性规划问题的单纯形法一般只需 m (3/2)m 次迭代就可以得到结果，实际效果令人次迭代就可以得到结果，实际效果令人相当满意。单纯形法是否为多项式算法人们一直相当满意。单纯形法是否为多项式算法人们一直不能从理论上加以肯定。不巧，在不能从理论上加以肯定。不巧，在1972年年 V.Klee 和和 G.Minty 构造了一个构造了一个 n 个变量个变量 2 n 个不等个不等式约束的例子，用单纯形法求解此线性规划时，式约束的例子，用单纯形法
35、求解此线性规划时，其计算次数为其计算次数为 2n。因此，不能肯定单纯形法是好因此，不能肯定单纯形法是好算法。算法。4/5/2023523 单纯形法的运用与改进求解线性规划问题的多项式求解线性规划问题的多项式算法 既然单纯形法不算好算法，于是就产生一个既然单纯形法不算好算法，于是就产生一个新问题，线性规划是否有多项式算法？新问题，线性规划是否有多项式算法？1979 年年苏联科学院计算中心的哈其扬苏联科学院计算中心的哈其扬(L.G.Khachian)发表了发表了 “求解线性规划问题的多项式算法求解线性规划问题的多项式算法”一文，解决了这一问题。不久后，一文，解决了这一问题。不久后，N.Karmar
36、kar又提出一种新的多项式算法。又提出一种新的多项式算法。u 1979年年 哈其扬哈其扬 椭球法椭球法 0(n6 L2)u 1984年年 卡玛卡卡玛卡 內点法內点法 0(n3.5 L2)4/5/2023533 单纯形法的运用与改进否定之否定否定之否定 依据算法复杂性理论，哈其扬证明了自己的椭球算依据算法复杂性理论，哈其扬证明了自己的椭球算法是一个有效的多项式算法。但是，在实际应用时椭球算法是一个有效的多项式算法。但是，在实际应用时椭球算法的迭代次数比单纯形法要多得多。这就产生了一个悖论：法的迭代次数比单纯形法要多得多。这就产生了一个悖论：有效算法不好用，好用算法又无效。有效算法不好用，好用算法
37、又无效。由于上述原因，算法复杂性理论本身遭到质疑，悖论由于上述原因，算法复杂性理论本身遭到质疑，悖论产生的原因在于该理论是从产生的原因在于该理论是从“状况最坏状况最坏”的极端情形来评的极端情形来评价问题。为了克服这种弊端，人们根据统计学原理又提出价问题。为了克服这种弊端，人们根据统计学原理又提出了平均复杂度理论，即评价算法好坏应按平均计算工作量了平均复杂度理论，即评价算法好坏应按平均计算工作量判别。判别。4/5/2023543 单纯形法的运用与改进各有千秋各有千秋u椭球算法实用价值不大，但理论上意义重大。因椭球算法实用价值不大，但理论上意义重大。因此，哈其扬在此，哈其扬在1982年的年的 11
38、次国际数学规划会议上次国际数学规划会议上获得获得Fulkerson奖。奖。u卡玛卡法是一个名符其实的好算法。对于小型问卡玛卡法是一个名符其实的好算法。对于小型问题虽比单纯形法稍逊一筹，但求解大规模问题的题虽比单纯形法稍逊一筹，但求解大规模问题的速度比单纯形法快得多。速度比单纯形法快得多。u按照平均复杂度理论，单纯形法成了名正言顺的按照平均复杂度理论，单纯形法成了名正言顺的好算法。事实上，卡玛卡法和单纯形法是两个内好算法。事实上，卡玛卡法和单纯形法是两个内外有别的实用算法。外有别的实用算法。4/5/2023553 单纯形法的运用与改进图图3.3 外点法与內点法外点法与內点法-x1+x2=1例例例
39、例 求解问题求解问题max z=c1x1+c2x2s.t.a11x1+a12x2 b1 a21x1+a22x2 b2 a31x1+a32x2 b3 x1,x2 x30Ox1x2-外点法求解路径外点法求解路径内点法求解路径内点法求解路径4/5/2023563 单纯形法的运用与改进当前研究方向当前研究方向u线性规划的内点算法线性规划的内点算法 许国志：通过非许国志：通过非线性规划解决线性问题，其成功是对数线性规划解决线性问题，其成功是对数学思想的革新。学思想的革新。u大规模问题的分解算法大规模问题的分解算法u大型复杂问题的近似算法大型复杂问题的近似算法4/5/2023573 单纯形法的运用与改进3
40、.4 单纯形法的矩阵描述单纯形法的矩阵描述 本节介绍用矩阵来描述单纯形法的运本节介绍用矩阵来描述单纯形法的运算机理。单纯形法的矩阵描述有助于加深算机理。单纯形法的矩阵描述有助于加深对单纯形法的理解和探讨对单纯形法的改对单纯形法的理解和探讨对单纯形法的改进。进。4/5/2023583 单纯形法的运用与改进 a11x1+a12x2+a1m xm+a1 m+1xm+1+a1kxk+a1nxn=b1 a21x1+a22x2+a2m xm+a2 m+1xm+1+a2kxk+a2nxn=b2 am1x1+am2x2+ammxm+am m+1xm+1+amkxk+amnxn=bmz=c1x1+c2 x2+c
41、m xm+cm+1 xm+1+ckxk+cnxn x1 +b1 m+1xm+1+b1kxk+b1nxn=b10 x2 +b2 m+1xm+1+b2kxk+b2nxn=b20 xm+bm m+1xm+1+bmkxk+bmnxn=bm0z=z0+0 x1+0 x2+0 xm+(c cm+1-zm+1)xm+1+(c cn-zn)xn z0+0 x1+0 x2+0 xm+(c cm+1-zm+1)xm+1+(c cn-zn)xn=z -z+0 x1+0 x2+0 xm+(c cm+1-zm+1)xm+1+(c cn-zn)xn=-z0线性规划问题的单纯形法表达线性规划问题的单纯形法表达4/5/202
42、3593 单纯形法的运用与改进表表3.11 单纯形表的作用单纯形表的作用4/5/2023603 单纯形法的运用与改进线性规划问题的矩阵形式线性规划问题的矩阵形式(I)max z=CXs.t.AX=b X 0max z=CB XB+CN XNs.t.BXB+N XN=b XB 0,XN 0 A=(B,N)X=(XB,XN)C=(CB,CN)B=(P1,P2,Pm)N=(Pm+1,Pm+2,Pn)XB=(x1,x2,xm)T XN=(xm+1,xm+2,xn)T CB=(C1,C2,Cm)CN=(Cm+1,Cm+2,Cn)4/5/2023613 单纯形法的运用与改进约束条件的变换关系约束条件的变换
43、关系(I)BXB+N XN=b XB+B-1N XN=B-1bB-1BXB+B-1N XN=B-1bI XB+B-1N XN=B-1bXB+B-1N XN=B-1bXB=B-1b-B-1N XN 4/5/2023623 单纯形法的运用与改进目标函数的变换关系目标函数的变换关系(I)z=CB XB+CN XNz =CBB-1b+(CN-CB B-1N)XN-z +(CN-CB B-1N)XN =-CBB-1bXB=B-1b-B-1N XN z=CB XB+CN XN=CB(B-1b-B-1N XN)+CN XN z=CBB-1b+(CN-CB B-1N)XNCBB-1b+(CN-CB B-1N)
44、XN=z4/5/2023633 单纯形法的运用与改进单纯形法的矩阵描述单纯形法的矩阵描述(I)XB +B-1N XN =B-1b-z +(CN-CB B-1N)XN =-CBB-1b I B-1N B-1b 0 CN-CB B-1N -CBB-1bT(B)=4/5/2023643 单纯形法的运用与改进线性规划问题的矩阵形式线性规划问题的矩阵形式(II)max z=CXs.t.AX=b X 0max z=CB XB+cm+1xm+1+cnxn s.t.BXB+Pm+1xm+1+Pnxn=b XB 0,xm+1,xn0 4/5/2023663 单纯形法的运用与改进约束条件的变换关系约束条件的变换关
45、系(II)BXB +Pm+1xm+1 +Pnxn =b XB +B-1Pm+1 xm+1+B-1Pnxn=B-1bB-1BXB+B-1Pm+1xm+1+B-1Pnxn=B-1b XB+B-1Pm+1xm+1+B-1Pnxn=B-1b XB=B-1b-B-1Pm+1 xm+1-B-1Pnxn4/5/2023673 单纯形法的运用与改进目标函数的变换关系目标函数的变换关系(II)z=CB XB+cm+1xm+1+cnxnz=CBB-1b+(cm+1-CB B-1Pm+1)xm+1+(cn-CB B-1Pn)xn-z+(cm+1-CB B-1Pm+1)xm+1+(cn-CB B-1Pn)xn=-CB
46、B-1bXB=B-1b-B-1Pm+1 xm+1-B-1Pnxnz=CB(B-1b-B-1Pm+1 xm+1-B-1Pnxn)+(cm+1 xm+1+cn xn)z=CBB-1b+(cm+1-CB B-1Pm+1)xm+1+(cn-CB B-1Pn)xn CBB-1b+(cm+1-CB B-1Pm+1)xm+1+(cn-CB B-1Pn)xn=z4/5/2023683 单纯形法的运用与改进单纯形法的矩阵描述单纯形法的矩阵描述(II)XB +B-1Pm+1 xm+1 +B-1Pnxn =B-1b-z+(cm+1-CB B-1Pm+1)xm+1+(cn-CB B-1Pn)xn=-CBB-1b I
47、B-1N B-1b 0 CN-CB B-1N -CBB-1bT(B)=I B-1Pm+1 B-1Pk B-1Pn B-1b0 cm+1-CBB-1Pm+1 ck-CBB-1Pk cn-CB B-1Pn -CBB-1b4/5/2023693 单纯形法的运用与改进表表3.12 单纯形表的数值形式单纯形表的数值形式4/5/2023723 单纯形法的运用与改进单纯形表的计算公式单纯形表的计算公式(I)b1 0 B-1b=bi 0 bm 0 j j=cj-CB B-1 Pj =(B B,N N)=(CB-CB B-1B,CN-CB B-1N)=(0,CN-CB B-1N)b1 j B-1Pj=bi j
48、bmj4/5/2023733 单纯形法的运用与改进单纯形表的计算公式单纯形表的计算公式(II)b1 0 B-1b=bi 0 bm 0 j j=cj-CB B-1 Pj =(B B,N N)=(CB-CB B-1B,CN-CB B-1N)=(0,CN-CB B-1N)=0,(cm+1,cn)-CB B-1(Pm+1,Pm+2,Pn)b1 j B-1Pj=bi j bmj4/5/2023743 单纯形法的运用与改进算算 例例 例例3.7 已知线性规划问题已知线性规划问题 max z=2x1+3x2 s.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x50的
49、一个基的一个基 B=(P1,P5,P2)，试求试求B的逆的逆B-1，并构造相应的单纯形表并构造相应的单纯形表T(B)。4/5/2023753 单纯形法的运用与改进单纯形法算例单纯形法算例 (附：表附：表3.13)max z=2x1+3x2s.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x501 0 0=0 1 0 0 0 1B0=(P3,P4,P5)1 0 2=0 1 0 0 0 4B1=(P3,P4,P2)1 0 2=4 1 0 0 0 4B2=(P1,P4,P2)1 0 2=4 0 0 0 1 4B3=(P1,P5,P2)4/5/2023763
50、单纯形法的运用与改进单纯形法算例单纯形法算例 (附：表附：表3.13)B=(P1,P5,P2)CB=(c1,c5,c2)=(2,0,3)=0-(3/2,1/8,0)001=0-0=-05 =c5-CB B-1 P5=0-(3/2,1/8,0)010=0-1/8=-1/84 =c4-CB B-1 P4=3-(3/2,1/8,0)204=3-3=02 =c2-CB B-1 P2=2-(3/2,1/8,0)140=2-2=01 =c1-CB B-1 P1 0 1/4 0-2 1/2 11/2-1/8 0B-1P5=0010 =1 0 0 1/4 0-2 1/2 11/2-1/8 0B-1P4=010