单纯形法基本原理VIP免费

Page1单纯形法基本原理单纯形法基本原理凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。凸集凸集不是凸集顶点Page2单纯形法基本原理单纯形法基本原理定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理定理22：线性规划问题的基可行解：线性规划问题的基可行解XX对应可行域对应可行域((凸集凸集))的的顶点。顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）Page3单纯形法的计算步骤单纯形法的计算步骤单纯形法的思路单纯形法的思路找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个基本可行解转移到另一个基本可行解（找出更大的目标函数值）（找出更大的目标函数值）最优解最优解是是否否循循环环核心是：变量迭代核心是：变量迭代结束结束Page4单纯形法的计算步骤单纯形法的计算步骤单纯形表jcnmmcccc11BcBXbmcc1mxx1mbb1nmmxxxx11im1mnmmnmaaaa1,11,1100100ijijjaccj0kjkjiiaab其中：Page5单纯形法的计算步骤单纯形法的计算步骤例1.8用单纯形法求下列线性规划的最优解0,30340243max21212121xxxxxxxxZ解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:0,,,30340243max432142132121xxxxxxxxxxxxZPage6单纯形法的计算步骤单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400θicB基bx1x2x3x40x34021100x430130134003)1020(3)(2141131acacc1检验数jPage7单纯形法的计算步骤单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。0j4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表①确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。0j}0|max{jjk0minikikiLaabPage8单纯形法的计算步骤单纯形法的计算步骤③用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。Page9单纯形法的计算步骤单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2jjj换入列bi/ai2，ai2>04010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1Page10单纯形法的计算步骤单纯形法的计算步骤例1.9用单纯形法求解02053115232.2max321321321321xxxxxxxxxtsxxxZ、、解：将数学模型化为标准形式：5,,2,1,02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出x4、x5可作为初始基变量，列单纯形表计算。Page11单纯形法的计算步骤单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x2j20－xx22221/3150120753017131/30－90－2j2560xx1111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3jPage12单纯形法的计算步骤单纯形法的计算步骤学习要点：1.线性规划解的概念以及3个基本定理2.熟练掌握单纯形法的解题思路及求解步骤Page13单纯形法的进一步讨论－人工变量法单纯形法的进一步讨论－人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。Page14单纯形法的进一步讨论...