单纯形法基本原理课件.ppt

1、Page 1凸集：如果集合凸集：如果集合C中任意两个点中任意两个点X1、X2，其连线上的所有点，其连线上的所有点也都是集合也都是集合C中的点，称中的点，称C为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点Page 2定理定理1：若线性规划问题存在可行解，则该问题的可行域是：若线性规划问题存在可行解，则该问题的可行域是凸集。凸集。定理定理3：若问题存在最优解，一定存在一个基可行解是最优：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）解。（或在某个顶点取得）Page 3Page 4单纯形表单纯形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmx

2、xxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：Page 5例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解 0,30340243max21212121xxxxxxxxZ解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为: 0,30340243max432142132121xxxxxxxxxxxxZPage 62）求出线性规划的初始基可行解，列出初始单纯形表。）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基基bx1x2x

3、3x40 x34021100 x430130134003)1020(3)(2141131 acacc1 检验数检验数j Page 73）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。0 j4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个

4、以上检验数大于0时，一般选择最大的一个时，一般选择最大的一个检验数，即：检验数，即： ，其对应的，其对应的xk作为换入作为换入变量。变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择 ，选最小的选最小的对应基对应基变量作为换出变量。变量作为换出变量。0 j0|max jjk 0minikikiLaabPage 8用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。一个新的单纯形表。5）重复）重复3）、）

5、、4）步直到计算结束为止。）步直到计算结束为止。Page 9cj3400icB基变量基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2j j j 换入列换入列bi /ai2，ai204010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 10例例1.9 用单纯形法求解用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：解：将数学模型化为标准形式

6、： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。Page 11cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 12学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个

7、基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤Page 13人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大的变量称为人工变量，构成的

8、可行基称为人工基，用大MM法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。为人工变量法。Page 14例例1.10 用大用大M法解下列线性规划法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Pag

9、e 15故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型： 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 Page 16cj32-100-M-MCBXBbx1x2x

10、3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 17解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量

11、的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行

12、解。）退化解的判别：存在某个基变量为零的基本可行解。Page 18单纯性法小结单纯性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单纯单纯形法形法不不处处理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不处处理理约束条约束条件两端件两端同乘以同乘以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M停止停止A Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika对对任任一一)0( lklkiiaab 计计算算lkxx替替换换基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解