《单纯形法的计算步骤ppt课件》由会员分享，可在线阅读，更多相关《单纯形法的计算步骤ppt课件（9页珍藏版）》请在金锄头文库上搜索。
1、Page 1单纯形法的计算步骤单纯形法的计算步骤例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为:Page 2单纯形法的计算步骤单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基基bx1x2x3x40x34021100x43013013400检验数检验数Page 3单纯形法的计算步骤单纯形法的计算步骤3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的
2、基可行解就是问题的最优解，计算停，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入作为换入变量，当有一个以上检验数大于变量，当有一个以上检验数大于0时，一般选择最大的一时，一般选择最大的一个检验数，即：个检验数，即： ，其对应的，其对应的xk作为作为换入变量。换入变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择 ，选最小的选最小
3、的对应基对应基变量作为换出变量。变量作为换出变量。Page 4单纯形法的计算步骤单纯形法的计算步骤用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。Page 5单纯形法的计算步骤单纯形法的计算步骤cj3400icB基变量基变量bx1x2x3x40x34021100x430130134000x34x23x14x2换入列换入列bi /ai
4、2，ai204010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 6单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在单位矩系数矩阵中不存在单位矩阵，无法建立初始单纯形阵，无法建立初始单纯形表。表。Page 7单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为
5、添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍绍的的单单纯纯形形法法求求解解该该模模型型，计计算算结结果果见见下下表。表。 Page 8单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0x63-650-101
6、3/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/3Page 9单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯性法小结单纯性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单纯单纯形法形法不不处处理理令令xj = xj - xj xj 0xj 0令令 xj =- xj不不处处理理约束条约束条件两端件两端同乘以同乘以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M
