线性规划单纯形法VIP免费

Page1单纯形法的计算步骤单纯形法的计算步骤单纯形表jcnmmcccc11BcBXbmcc1mxx1mbb1nmmxxxx11im1mnmmnmaaaa1,11,1100100ijijjaccj0kjkjiiaab其中：Page2单纯形法的计算步骤单纯形法的计算步骤例1.8用单纯形法求下列线性规划的最优解0,1241648232max21212121xxxxxxxxZ解：1）将问题化为标准型，加入松驰变量x3、x4、x5则标准型为:0,,,,1241648200043max54321524132154321xxxxxxxxxxxxxxxxxZPage3单纯形法的计算步骤单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。11311421531()2(010400)2ccacacacj23000θiCBXBbx1x2x3x4x50x381210040x41640010--0x51204001323000Z=0检验数j3)400020(3)(32522412322acacacc2)004010(2)(31521411311acacaccPage4单纯形法的计算步骤单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。0j4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表①确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。0j}0|max{jjk0minikikiLaabPage5单纯形法的计算步骤单纯形法的计算步骤③用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。④5）重复3）、4）步直到计算结束为止。Page6单纯形法的计算步骤单纯形法的计算步骤（表1-3）cj23000θicB基变量bx1x2x3x4x50x38121000x416400100x5120400123000Z=0表1-40x320x4163x23j换入列bi/ai2，ai2>043换出行将4化为1，本列的其他值化为010201/401－1/2100－3/4j04001000第一步：将第三行除以4第二步：将第一行减去第三行乘以2Page7单纯形法的计算步骤单纯形法的计算步骤（表1-4）Cj23000θicB基变量bx1x2x3x4x50x321010-1/20x416400100x2301001/42000-3/4Z=9表1-52x120x43x23j换入列bi/ai2，ai2>0换出行10001/401－1/210-21/4j000-41200将4化为0第一步：将第二行减去第一行乘以4248Page8单纯形法的计算步骤单纯形法的计算步骤（表1-5）Cj23000θicB基变量bx1x2x3x4x50x121010-1/20x4800-4120x2301001/400-201/4Z=13表1-62x10x53x2j换入列换出行1001/2000010-3/20j-1/800-21/211/4将2化为1，本列的其他值化为0第一步：将第二行除以244第二步：将第一行加上第二行乘以1/2第三步：将第三行减去第二行乘以1/442-1/8Page9单纯形法的计算步骤单纯形法的计算步骤表1-6中所有的都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（4，2，0，0，4）T是最优解，Z=14是该线性规划的最优值。jPage10单纯形法的计算步骤单纯形法的计算步骤例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-6中所有的都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（25，35/3，0，0，0）T是最优解，Z=95/3是该线性规划的最优值。jPage13单纯形法的计算步骤单纯形法的计算步骤学习要点：1.线性规划解的概念以及3个基本定理2.熟练掌握...