单纯形法的计算步骤

Page1单纯形法的计算步骤例1.8用单纯形法求下列线性规划的最优解0,30340243max21212121xxxxxxxxZ解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:0,,,30340243max432142132121xxxxxxxxxxxxZPage2单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400θicB基bx1x2x3x40x34021100x430130134003)1020(3)(2141131acacc1检验数jPage3单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。0j4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表①确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。0j}0|max{jjk0minikikiLaabPage4单纯形法的计算步骤③用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。Page5单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2jjj换入列bi/ai2，ai204010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1Page6单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、、解：首先将数学模型化为标准形式5,,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。Page7单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：7,,2,1,012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj－其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。Page8单纯形法的进一步讨论－人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→jj→jjPage9单纯形法的进一步讨论－人工变量法单纯性法小结:建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj≤0bi≥0bi0≤=≥maxZminZxsxa求解图解法、单纯形法单纯形法不处理令xj=xj′-xj″xj′≥0xj″≥0令xj’=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=－maxz′0-M