运筹学第2章 单纯形法

1、赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院管理运筹学管理运筹学 模型与方法模型与方法第第2 2章单纯形法章单纯形法2.12.1基本思想基本思想2.22.2基本方法基本方法2.32.3其它法则其它法则2021-9-42单纯形法单纯形法内容内容原本方法原本方法对偶方法对偶方法形式形式方程组形式方程组形式表格形式表格形式矩阵形式矩阵形式2.1 单纯形法单纯形法的基本思路的基本思路2021-9-44求出一个初始基可行解判断基可行解是否最优求目标值得以改善的基可行解结束需要解决的问题需要解决的问题： (1)(1)如何确定初始的基可行解？如何确定初始的基可行解？ (2)(2)目标函数何时达到

2、最优目标函数何时达到最优判断标准是什麽？判断标准是什麽？ (3)(3)为了使目标函数逐步变优，怎么转移？为了使目标函数逐步变优，怎么转移？2021-9-45 单纯形法的单纯形法的基本思路基本思路：1.1.从可行域中某一个从可行域中某一个顶点顶点开始，开始，判断判断此顶点是否是最优解，此顶点是否是最优解，2.2.如不是如不是, ,则再找另一个使得其目标函数值更优的顶点，称之为则再找另一个使得其目标函数值更优的顶点，称之为迭代迭代，再判断此点是否是最优解。再判断此点是否是最优解。3.3.直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，直到找到一个顶点为其最优解，就是使得其目标函数值最优的

3、解，或者能判断出线性规划问题无最优解为止。或者能判断出线性规划问题无最优解为止。2021-9-46线性规划的典式线性规划的典式njxbxaxaxbxaxaxbxaxaxtsxcxcxczjmnmnmmmmnnmmnnmmnn, 2 , 1, 0. .max(min)11,2211, 221111, 112211标准形为标准形为典式的充要条件典式的充要条件：系数矩阵中存在一个满秩单位阵。：系数矩阵中存在一个满秩单位阵。典式标准形是单纯形法的唯一必要前提。典式标准形是单纯形法的唯一必要前提。基本性质基本性质：1.1.线性规划问题的可行域是凸集。线性规划问题的可行域是凸集。2.2.标准形线性规划的基

4、本可行解与可行域的极点互相对应标准形线性规划的基本可行解与可行域的极点互相对应。3.3.线性规划的线性规划的基本定理基本定理 对标准形线性规划问题（对标准形线性规划问题（M M）：）：若有可行解，则必有基本可行解；若有可行解，则必有基本可行解；若有最优解，则必有最优基本解。若有最优解，则必有最优基本解。4.4.若若LPLP问题的可行域问题的可行域RR，则，则R R至少有一个极点。至少有一个极点。5.5.LPLP问题可行域问题可行域R R的极点为有限个。的极点为有限个。2021-9-48 nxxX11jmjaAa mbbb1opt () . .0TZCXAXbs tX （）nccC12.2 单纯

5、形法的基本方法（表格形式）单纯形法的基本方法（表格形式）2021-9-49情况一：情况一： 约束条件约束条件为为 1 1、确定初始基可行解、确定初始基可行解对于每个条件加上对于每个条件加上松弛变量松弛变量, ,在约束系数矩阵中的在约束系数矩阵中的单位矩阵单位矩阵可以构成可以构成初始基初始基m ax . .0 TZCXA Xbs tX2021-9-410例例2-1 2-1 max z=3x max z=3x1 1+ 2x+ 2x2 2 s.t. x s.t. x1 1 +x +x3 3 =6=6 2x 2x2 2 +x+x4 4 =8=8 2x2x1 1+3x+3x2 2 +x+x5 5=18=

6、18 x xj j0 0 （j=1,2,3,4,5j=1,2,3,4,5）2021-9-411它的系数矩阵它的系数矩阵 其中其中a aj j为系数矩阵为系数矩阵A A第第j j列的向量。列的向量。A A的秩为的秩为3,A3,A的秩的秩m m小于此小于此方程组的变量的个数方程组的变量的个数n n。6818 b T x x x x x X54321 ( 3 2 0 0 0 )C 可看出 x3, x4 和 x5 的系数列向量构成一个基:100010001Bu当令非基变量当令非基变量 x1， x2为零时为零时,可得可得 x3= 6 ， x4 =8 , x5= 18 u（0，0，6，8，18）是）是初始

7、基本可行解初始基本可行解1234510100(,)0201023001Aaaaaa判断已求得的基本可行解是否是最优解。判断已求得的基本可行解是否是最优解。（1 1）最优性检验的依据）最优性检验的依据检验数检验数j（2 2）最优解判别定理）最优解判别定理对于求对于求最大最大目标函数的问题中，对于某个基本可行解，如果目标函数的问题中，对于某个基本可行解，如果所有所有检验数检验数 ，则这个基本可行解是，则这个基本可行解是最优解最优解。0j对于求目标函数对于求目标函数最小值最小值的情况，只需的情况，只需 j0 01=CmTjiijjBjjicacac011=mmTjjiiBjizc xcb C b01

8、njjj mzzx2 2、最优性检验、最优性检验CBcjc1c2cmcm+1cn比值比值bi/aik基基bx1x2xmxm+1xnc1x1b1100a1,m+1a1nc2x2b2010a2,m+1a2ncmxmbm001am,m+1amn000TjBjjC ac1mn0TBzC b3 3、 基变换基变换(1)(1)入基变量的入基变量的确定确定最小检验数规则最小检验数规则 从最优解判别定理知道，当某个从最优解判别定理知道，当某个j0时，非基变量时，非基变量xj变为基变为基变量不取零值可以使目标函数值增大，故我们要选基变量不取零值可以使目标函数值增大，故我们要选基检验检验数数小于小于0 0的非基变

9、量换到基变量中去（称之为入基变量）。若有的非基变量换到基变量中去（称之为入基变量）。若有两个两个以上以上j0的，的，则为了使目标函数增加得更大些，一般选则为了使目标函数增加得更大些，一般选其中其中的的j最小者最小者的非基变量为入基变量的非基变量为入基变量。在本例题中在本例题中1=-3=-3是是检验数中检验数中最小的负数最小的负数，故选，故选x x1 1为为入基变量入基变量。同时，入基变量同时，入基变量xk的系数列向量的系数列向量ak为为主列主列。2021-9-414min0jjk (2)(2)出出基变量和主元的确定基变量和主元的确定最小比值规则最小比值规则确定出基变量的方法确定出基变量的方法：

10、把已确定的入基变量在各约束方程中的：把已确定的入基变量在各约束方程中的正的系数正的系数除除其其所在约束方程中的所在约束方程中的常数常数项值项值，把其中，把其中最小比值最小比值所在的约束所在的约束方程中方程中的的原基变量确定为原基变量确定为出基变量出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的这样在下一步迭代的矩阵变换中可以确保新得到的bi值都大于等于零。值都大于等于零。出基变量出基变量xl所在行的系数所在行的系数alj构成构成主行。主行。确定主元的方法确定主元的方法：主行主行（最小比值所在的约束方程）与（最小比值所在的约束方程）与主列主列（入基变量（入基变量系数列）交于系数列）交于al

11、k为为主元。主元。基变换通过初等变换实现，目标：将主列化为单位向量（基变换通过初等变换实现，目标：将主列化为单位向量（alk=1=1），以符），以符合典式合典式2021-9-415min0ilikiklkbbaaax1为为入基变量入基变量，我们把各约束方程中，我们把各约束方程中x1的的为正的系数除对应的常为正的系数除对应的常量，量，得得所以，所以，出基变量出基变量应为应为x3，主元为主元为a133111316186,9.12bbaa2021-9-416例例2-1 2-1 max z=3x1+ 2x2 s.t. x1 +x3 =6 2x2 +x4 =8 2x1+3x2 +x5 =18 xj0 （

12、j=1,2,3,4,5）cj32000bi/aikXBbx1x2x3x4x50 x36101000 x48020100 x518230010-3-2000j例例2-2 2-2 BC初始单纯形表初始单纯形表cj32000bi/aikXBbx1x2x3x4x50 x36010060 x4802010-0 x5182300190-3-2000BCj3x1610100-0 x480201040 x560-2012180-2300j3x16101000 x44004/31-2/32x2201-2/301/322005/302/3j*6204022XZ 2021-9-419情况二：情况二： 约束条件约束条

13、件为为 ，= =12121212max2322. .23,0zxxxxstxxxx标准化标准化121231241234max2322. .23,0zxxxxxstxxxxxxx非典式非典式例例2-32-3添加人工变量添加人工变量12123512412345max2322. .23,0zxxxxxxstxxxxxxxx0(0,0,0,3,2)TX 1 1、大、大M法法125123512412345max2322. .23,0zxxMxxxxxstxxxxxxxx添加添加人工变量人工变量x5来人为的创造一个单位矩阵作为基来人为的创造一个单位矩阵作为基M叫做叫做罚因子罚因子，任意大的数。，任意大的数

14、。人工变量只能取零值。人工变量只能取零值。必须把必须把x5从基变量中换出去，否从基变量中换出去，否则无解。则无解。例例2-2-3 3cj3200-Mbi/aikXBbx1x2x3x4x5-Mx521-10110 x43-12010-2M-2M-3-M-2M00BCj3x1111/2-1/201/20 x4405/2-1/211/230-1/2-3/203/2+Mj解无界解无界可删除可删除2 2、两阶段法、两阶段法将将加入人工变量后的线性规划划分两阶段加入人工变量后的线性规划划分两阶段求解。求解。第一阶段第一阶段：判断判断原线性规划是否有基可行解原线性规划是否有基可行解，方法是先求解下列线性规划

15、，方法是先求解下列线性规划问题问题2021-9-4235123512412345max22. .23,0 xxxxxstxxxxxxxx 例例2-42-4（2-32-3）*0*=0若若 ，则原问题无可行解，则原问题无可行解若若 ，则原问题有可行解，则原问题有可行解若基列中不存在人工变量，直接转入第二阶段；若基列中不存在人工变量，直接转入第二阶段；若基列中存在人工变量若基列中存在人工变量xBl，该行该行xBl前系数都为前系数都为0 0，删除，删除xBl对应的行和列；对应的行和列；该行该行xBl前系数不都为前系数不都为0 0，alk 0, ,以以alk为主元换基作运算。为主元换基作运算。cj000

16、0-1bi/aikXBbx1x2x3x4x5-1x52-2-1-1010 x43-12010-221100jBC无可行解无可行解cj0000-1bi/aikXBbx1x2x3x4x5-1x50000010 x43-12010000000jBCcj0000-1bi/aikXBbx1x2x3x4x5-1x5000-2010 x4312-210000100jBCcj0000-1bi/aikXBbx1x2x3x4x5-1x521-10110 x43-12010-2-2-1100BCj0 x1111/2-1/201/20 x4405/2-1/211/2000001j例例2-42-4（2-32-3）第二阶

17、段第二阶段：求解原问题，：求解原问题，1.1.删除删除第一阶段第一阶段最终单纯形表中的人工变量各列、最终单纯形表中的人工变量各列、cj列、列、cj行、检行、检验行；验行；2.2.将将cj换成原问题的换成原问题的cj；3.3.重新计算。重新计算。cj3200bi/aikXBbx1x2x3x43x1111/2-1/200 x4405/2-1/2130-1/2-3/20BCj 2021-9-4291 1、无、无可行解可行解2.3 单纯形法的其它法则单纯形法的其它法则最优解里有人工变量大于零，则此线性规划无可行解。最优解里有人工变量大于零，则此线性规划无可行解。例例2-52-5cj0000-1bi/a

18、ikXBbx1x2x3x4x5-1x5000-2010 x4312-210-300100 2021-9-4302 2、无界解、无界解 在求目标函数最大值的问题中，所谓无界解是指在约束条件在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下目标函数值可以取任意的大。存在着一个存在着一个小小于零的检验数于零的检验数，并且，并且该列的系数向量的每个元素该列的系数向量的每个元素都小于或等于零都小于或等于零，则此线性规划问题是，则此线性规划问题是无界无界的，一般地说此类的，一般地说此类问题的出现是由于问题的出现是由于建模的错误所引起建模的错误所引起的。的。例例2-42-4c

19、j3200bi/aikXBbx1x2x3x43x1111/2-1/200 x4405/2-1/2130-1/2-3/20 12121212max1. .22,0zxxxxstxxx x2021-9-4313 3、退化退化问题（相持）问题（相持） 在单纯形法计算过程中在单纯形法计算过程中，u确定入基变量时，存在确定入基变量时，存在检验数相等检验数相等u确定出确定出基变量时基变量时有时，有时，存在存在两个以上的相同的最小两个以上的相同的最小比值比值例例2-62-6cj1100bi/aikXBbx1x2x3x40 x31111010 x4210110-1-100 2021-9-433勃兰特勃兰特(

20、(E.Beale)E.Beale)法则法则: :把松弛变量（剩余变量）、人工变量都用把松弛变量（剩余变量）、人工变量都用x xj j表示，一般松弛表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：下两个规则：（1 1）在所有）在所有检验检验数数小于小于零的非基变量中零的非基变量中，任选，任选一一个作为个作为入基入基变量变量。（2 2）在存在两个和两个以上）在存在两个和两个以上最小比值最小比值时，选一个时，选一个下标下标最大最大的的基变量为基变量为出基变量出基变量。 这样就一定能避免出现循环。这样就一定能避免出现循环。 2021-9-4344 4、无穷多无穷多最优解最优解例例2-72-7非基变量的检验数等于零，非基变量的检验数等于零，这样我们可以断定此