第四节 单纯形法的计算步骤

12010年8月管理工程学院《运筹学》1◆单纯形法计算步骤◆单纯形表法：表格式单纯形法◆单纯形解法中的一些问题及其处理方法第四节单纯形法的计算步骤22010年8月管理工程学院《运筹学》2P14一、单纯形法的步骤对线性规划标准形式maxcTxs.t.Ax=bx≥0其中,c,xRnbRmAmn矩阵，秩（A）=m计算步骤如下：第一步：求出初始基可行解，列出初始单纯形表（非标准形式的首先化为标准形式再求），见表1-1。32010年8月管理工程学院《运筹学》3……0…0σj=cj-zja1na2n…amn………a1ja2j…amj………00⋮1⋱⋱10⋮0b1b2⋮bmx1x2⋮xmc1c2⋮cmxn…xj…xm…x1b基cBcn…cj…cm…c1cj→表1-142010年8月管理工程学院《运筹学》4第二步：最优性检验。如果表中所有检验数σj≤0，则表中基可行解就是问题的最优解，结束。否则转下一步。第三步：从一个基可行解到另一目标函数值更大的基可行解，列出新单纯形表。(1)确定换入基的变量。σk=max{σj│σj0}，对应变量xj作为换入基的变量(换入变量)。52010年8月管理工程学院《运筹学》5(2)确定换出基的变量。(保证bj≥0)令θ=min{bj/aik┃aik0}=bl/alk，（当有几个相等的最小值时，任选其一）确定xl是换出基的变量(换出基变量)。alk叫主元素。(3)换入变量替换基变量中换出变量（对行进行初等变换，最好写在表中右侧），得一个新的基可行解，对应新单纯形表如下：62010年8月管理工程学院《运筹学》6………………………………(cn-zn)´a1n´⋮a2n´⋮amn´xncn00⋮1⋮0xkck(cj-zj)´……(cl-zl)´…0σj=cj-zja1j´⋮a2j´⋮amj´………0⋮0⋮1………-a1k/alk⋮1/alk⋮-amk/alk⋱⋱1⋮0⋮0b1´⋮bk/alk⋮bm´x1⋮xk⋮xmc1⋮ck⋮cmxj…xm…xl…x1b基cBcj…cm…cl…c1cj→表1-272010年8月管理工程学院《运筹学》7其中：(1)(1.24)lkljljlkllaaaabb'',kklkmiikilklkklimliikikikilklllzcaacaacaccacaczc1111111'liaaaaaliaabbbiklkljijijiklklii''(1.25)(2)(3)82010年8月管理工程学院《运筹学》8第四步：重复第二、三步一直到计算结束。111'limliijiijijjjacacczc111limliikikikilkljaccacaamiikikmilkljijijaccaaacc11)()(kklkljjjzcaazc92010年8月管理工程学院《运筹学》9二、对规范形式的线性规划问题Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0bi0i=1,…,m102010年8月管理工程学院《运筹学》10加入松弛变量：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2…………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，xn，xn+1，…，xn+m≥0112010年8月管理工程学院《运筹学》11显然xj=0j=1,…,n;xn+i=bii=1,…,m是基本可行解对应的基是单位矩阵。以下是初始单纯形表：表1-2´122010年8月管理工程学院《运筹学》12其中：为检验数cn+i=0i=1,…,man+ii=1,an+ij=0(j≠i)i,j=1,…,m是初始基可行解。132010年8月管理工程学院《运筹学》13例1.8某厂计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时、A、B两种原料的消耗、资源的限制以及生产一个单位的产品Ⅰ、Ⅱ各获得的利润，如下表所示。250千克400千克300台时资源限制100元111Ⅱ50元021Ⅰ利润原料B原料A设备问工厂应分别生产多少个Ⅰ产品和Ⅱ产品才能使工厂获利最多。工厂目前要决策的问题：生产多少个Ⅰ产品和Ⅱ产品?用变量、分别表示生产Ⅰ产品和Ⅱ产品数量，1x2x则称1x和为决策变量。2x142010年8月管理工程学院《运筹学》14目标函数：2110050maxxxz约束条件：,30021xx,400221xx.0,021xx,2502x152010年8月管理工程学院《运筹学》15目标函数：21100500maxxxz约束条件：,300321xxx,4002421xxx.0,51xx,25052xx1.加松弛变量将LP变为标准形式162010年8月管理工程学院《运筹学》162.将标准式中的数据填入单纯形表格并迭代如下：125040030011主元（转轴元）i迭代次数Bc54321xxxxx000100500543xxx000111002101001001ib250400300Bxj000100500172010年8月管理工程学院《运筹学》17i迭代次数Bc54321xxxxx000100501543xxx000111002101001001ib250400300Bxj0001005002x1010-12001-150000-100-25000501502115050100182010年8月管理工程学院《运筹学》1800-2110100105-005-00i迭代次数Bc54321xxxxx000100502241xxx1000501010-1ibBxj5050250-27500192010年8月管理工程学院《运筹学》19所有的检验数,0j此基本可行解：.0,50,0,250,50,,,,54321TTxxxxx为最优解。.27500z最优目标函数值为：202010年8月管理工程学院《运筹学》20例1.2：用单纯形法求解线性规划问题212010年8月管理工程学院《运筹学》21解：首先在各约束条件上加上松弛变量，将上述问题化为标准形式222010年8月管理工程学院《运筹学》22则初始基可行解为并以此列出初始单纯形表(见表1-3)。表1-3230000cj-zj2210001201004000100[4]00010x3120x480x5160x612x1x2x3x4x5x6CB基b230000θicj→④'=④÷4①'=①-④'×2②'=②-④'×2③'=③⑤'=⑤-④'×35232010年8月管理工程学院《运筹学》23000-1.5-0.1250cj-zj001-1-0.25010000.250000-20.510100.5-0.12500x302x140x643x22000-1.500.25cj-zj001-200.5[1]0010-0.5000-41[2]010000.250x322x120x583x23x1x2x3x4x5x6CB基b230000cj→表1-5初等变换242010年8月管理工程学院《运筹学》24上表中由于所有σj0，表明已求得最优解x1=4，x2=2，x3=0，x4=0，x5=0，x6=4，Z=14。◆当确定x6为换入变量计算θ值时，有两个相同的最小值：2/0.5=4，8/2=4。任选其中一个作为换出变量时，则下面表中另一基变量的值将等于0，这种现象称为退化。含有一个或多个基变量为0的基可行解称为退化的基可行解。252010年8月管理工程学院《运筹学》25三、单纯形解法中一些问题及其处理方法◆换入变量的选择问题–检验数最大原则–下标最先原则◆换出变量的选择问题–比值最小原则–下标最先原则◆无换出变量的情况：无界解◆非基变量检验数有等于零:多个最优解情况