单纯形法的计算步骤

Page12020/2/26单纯形法的计算步骤例1.10用单纯形法求下列线性规划的最优解0,30340243max21212121xxxxxxxxZ解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:0,,,30340243max432142132121xxxxxxxxxxxxZPage22020/2/26单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。ijijjaccσcj3400θicBXBbx1x2x3x40x34021100x43013013)1020(3)(21411311acacc检验数j003？ijijjaccσPage32020/2/26单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。0j4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表①确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。0j}0|max{jjk0minikikiLaabPage42020/2/26单纯形法的计算步骤③用换入变量Xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。数学解释经济解释检验数σj单位变量增加带来目标函数变化值单位产品产量增加带来的净利润变化值最小比值θj确保在迭代过程中所有变量的值非负，即每步得到的解均为基可行解。确保在增加产品产量的过程中，不超过现在的资源限量。Page52020/2/26单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2jjj换入列bi/ai2，ai204010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以3/5后得到103/5－1/51801－1/5－2/5400－1－1最优解：最优值：Page62020/2/26单纯形法的计算步骤例1.11用单纯形法求解02053115232.2max321321321321xxxxxxxxxtsxxxZ、、解：将数学模型化为标准形式：5,,2,1,02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出x4、x5可作为初始基变量，列单纯形表计算。Page72020/2/26单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x2j20－x221/3150120753017131/30－90－2j2560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3j最优解：最优值：Page82020/2/26单纯形法的进一步讨论－人工变量法一、人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。1、大M法通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解。Page92020/2/26单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、、解：首先将数学模型化为标准形式5,,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。Page102020/2/26单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：7,,2,1,012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj－其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。Page112020/2/26单纯形法的进一步讨论－人工变量法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2020/2/262、两阶段法在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为0，人工变量的系数为1，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅助目标函数值为0时为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以求出原来问题的解。2020/2/263)两阶段法的计算步骤（1）不考虑原问题是否存在基可行解，引进人工变量，构造辅助线性规划问题。（2）用单纯形方法求解辅助问题，若辅助问题的目标函数值w≠0，则原问题无可行解，停止计算。（3）若辅助问题目标函数的值w=0，则将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换原问题的目标函数系数，作为第二阶段的初始表。4）解的判断同单纯形法2020/2/26例4.2用两阶段法求解线性规划问题minΖ=-3x1+x2+x3s.t.x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1,x2,x3,≥0解：先在约束条件中加入人工变量，写出辅助规划问题。MinW=x6+x7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1xi≥0,i=1,2,…,72020/2/26用单纯形法进行第一阶段的计算如下表2020/2/26人工变量x6=x7＝0，第一阶段目标函数W=0，则(0，1，1，12，0)T是原线性规划问题的基可行解，转第二阶段的计算2020/2/26由表可得最优解为：x1=4，x2=1，x3=9；目标函数值Z=-2Page182020/2/26单纯形法的进一步讨论－人工变量法解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,且基变量中无非零的人工变量，则线规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,且基变量中无非零的人工变量，则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个σk0且aik≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在人工变量0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。2020/2/26二、退化、循环及其处理方法1、退化单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。2、退化迭代的特点（1）退化解的基变量中至少有一个取值为0。（2）退化迭代中基在不断变化但解始终不变。（3）退化迭代不会引起目标函数值的改进。3、防止循环迭代的方法（1）摄动法（2）字典顺序法（3）最小下标法Page202020/2/26单纯形法小结建立模型个数取值右端项等式或不等式极大或极小新加变量目标系数两个三个以上xj≥0xj无约束xj≤0bi≥0bi0≤=≥maxZminZxsxa求解图解法、单纯形法单纯形法不处理令xj=xj′-xj″xj′≥0xj″≥0令xj’=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=－maxz′0-M停止Ajjjzc:求0j所有kj即找出max)()0(0jika对任一)0(lklkiiaab计算lkxx替换基变量用非基变量新单纯形表列出下一个ax含有非零量中是否基变0j非基变量的有某个最优解一唯无可行解最优解无穷多是否环循否否否是是是循环无界解Page222020/2/26线性规划模型的应用一般而言，一个经济、管理问题需要满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述