单纯形法（第三章线性规划2）

一、求解 LP问题的单纯形法1.单纯形法的求解原理 单纯形法引例标准化1Step2. 确定换入换出变量，进行第一次迭代 Step1. 确定初始基可行解。 初始基可行解为： X1=(0 0 360 200 300)T f1=0*f2 =360 Step3.确定新的换入换出变量，进行第二次迭代*目标函数值 f 3 = 428。即当 A产品生产 20kg， B产品生产 24kg， 工厂才能获得最大利润 428百元。 x3=84代表煤的剩余量为 84t， x4 = x5 = 0表示电力和劳动日完全利用，没有剩余。X3为最优解2.单纯形法的主要步骤Step1. 标准化，找初始基可行解，建立初始的单纯形表；n 对于 (max , )， 松弛变量对应的列构成一个单位阵Step2.检验当前基可行解是否为最优解n 所有检验数 j 0， 则得到最优解 （ 若存在 k 0，且 pk 0,则该问题无最优解，停止计算） 否则进行下一步。Step3.换基迭代（改进基可行解）n 从 j 0 中找最大者 k ，其对应变量 xk称为 换入变量 （若最大判别数有同样大的，选对应下标小的变量为换入变量 )n xk所在 列称为主元列n 确定换入变量的最大值和换出变量n 最小比值原则5n 设第 l 行使 最小，则第 l 行对应的基变量 x l称为 换出变量 ，第 l 行称为主元行， alk 称为主元。Step4.迭代过程n 迭代过程以主元 alk为中心进行，即要将主元 alk变为 1， 主列 上其它元素变为 0，得到一个新的单纯形表，同时得到一个新的基可行解。n 转回 Step2。63. 单纯形表及其格式7max f =40x1+ 50x2x1+2x2 303x1+2x2 602x2 24x1 , x2 0例 1 用单纯形法求解下列 LP问题x1 +2x2 +x3 =30 3x1 +2x2 +x4 =602x2 + +x5 =24 x1 , , x5 0max f =40x1+ 50x2+0x3 +0x4+0x5标准化建立初始单纯形表xj x1 x2 x3 x4 x5 bx3 1 2 1 0 0 30x4 3 2 0 1 0 60x5 0 2 0 0 1 2440 50 0 0 0 0基变量*30/2=1560/2=3024/2=1240 50 0 0 0000第一步迭代xj x1 x2 x3 x4 x5 bx3 1 0 1 0 -1 6x4 3 0 0 1 -1 36x2 0 1 0 0 0.5 1240 0 0 0 -25 -600基变量6/1=636/3=12_40 50 0 0 00050第二步迭代xj x1 x2 x3 x4 x5 bx1 1 0 1 0 -1 6x4 0 0 -3 1 2 18x2 0 1 0 0 0.5 120 0 -40 0 15 -840基变量18/2=912/0.5=24_40 50 0 0 040050第三步迭代xj x1 x2 x3 x4 x5bx1 1 0 -0.5 0.5 0 15x5 0 0 -1.5 0.5 1 9x2 0 1 0.75 -0.25 0 7.50 0 -17.5 -7.5 0 -975基变量该问题的最优解为： X=(15, 7.5, 0, 0, 9)T40 50 0 0 040050例 2 用单纯形法求解下列 LP问题xj x1 x2 x3 x4 x5 bx3 -2 1 1 0 0 4x4 1 -1 0 1 0 2x5 -3 1 0 0 1 31 1 0 0 0 0基变量1 1 0 0 00000 -1 2 893-200 2 -1 -211该问题具有无界解例 2 用单纯形法求解下列 LP问题n max f =x1+ x2+2x3 -x4x1 +x3 - x4 =1 -x1 +x2 +2x4 =0x1 , , x4 0max f =x1+ x2+2x3 -x4 2 -x4xjx1 x2 x3 x4 bx3x21 0 1 -1-1 1 0 2100 0 0 -1 -2基变量xjx1 x2 x3 x4 bx1x21 0 1 -10 1 1 1110 0 0 -1 -2此问题具有无穷多最优解 max f =2总结：解的判别1、 最优解的判别：若 X（ x1x2. xn） T为对应于基 B的一个基可行解，且所有 j 0， 则 X为最优解。2、无穷多最优解的判别：若 X（ x1x2. xn） T为 一个基可行解，存在所有 j 0， 又 存在某一非基变量 xk对应的判别数 k = 0,则此 LP问题有无穷多解。3、无界解的判别：若 X（ x1x2. xn） T为一个基可行解，其中 某个非基变量 xk对应的判别数 k 0， 且 对应的系数矩阵 aik 0,则此 LP问题具有无界解。（或称无最优解，最优解 无穷）4 .人工变量的引入及其解法当约束条件为 “”型，引入剩余变量和人工变量n 由于所添加的剩余变量的系数为 1，不能构成初始基变量，为此引入一个人为的变量（注意，此时约束条件已为 “=”型），以便取得初始基变量，故称为人工变量n 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定n 两种方法n 大 M法n 两阶段法20（ 1）两阶段法：作辅助问题解题过程：第一阶段：求解辅助问题当进行到最优表时， 若 =0, 则得到原问题的一个基本可行解，转入第二阶段。 若 0, 则判定原问题无可行解。max = -y1 - y2- - ym从第一阶段得到的基本可行解开始，继续用单纯形法进行迭代，直到找出原问题的最优解或判断具有无界解。第二阶段 :例 3 用两阶段法求解下列 LP问题引入人工变量 x6 , x7构造下列辅助问题：xj x1 x2 x3 x4 x5 x6 x7 B-1bx4x6x71 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 11131- -6 1 3 0 -1 0 0 4-f 3 -1 -1 0 0 0 0 030 0 -2 13 0 -1 100 0 -3 11 0 1 1xj x1 x2 x3 x4 x5 x6 x7 B-1bx4x6x73 -2 0 1 0 0 -10 1 0 0 -1 1 -2-2 0 1 0 0 0 11011- 0 1 0 0 -1 0 -3 1-f 1 -1 0 0 0 0 1 130 0 -212-120 -2 -50 0 00 -1 1 -1 2-12xj x1 x2 x3 x4 x5 B-1bx4x2x33 0 0 1 -20 1 0 0 -1 -2 0 1 0 01211-f 1 0 0 0 -1 2x1 1/3 -2/3 410 2/3 -4/30 -1/3 -1/3 -29得到原问题的最优解为： X*=（ 4 1 9 0 0） Tf * =2（ 2） 大 M法 :