1.4 单纯形法计算步骤

第1页§1.4单纯形法计算步骤1.将非标准型线性规划化为标准型2.确定初始基可行解：一般设松弛变量为初始基可行解3.判断：若所有的非基变量的检验数σj≤0，则此解为LP的最优解，若存在某一非基变量的检验数σj0，则问题还没有达到最优解，需进行改进4.迭代：选换入变量max{cj-zj/cj-zj0}假设xk为换入变量；选换出变量θ＝min{bi/aik，aik＞0}，假设选取xl为换出变量；然后迭代，使得alk＝1，其余aik为01mjjiijicca记第2页4.1单纯形表单纯形表为了便于理解各种计算关系，设计一种计算表，称为单纯形表。第3页4.1单纯形表X1+a1,m+1Xm+1+…+a1nXn=b1X2+a2,m+1Xm+1+…+a2nXn=b2Xm+am,m+1Xm+1+…+amnXn=bm………………………………-Z+c1X1+…+cmXm+cm+1Xm+1+…+cnXn=0Z=c1X1+…+cmXm+cm+1Xm+1+…+cnXn第4页4.1单纯形表增广矩阵-zx1x2…xmxm+1…xnb010…0a1,m+1…a1nb1001…0a2,m+1…a2nb2………………………000…1am,m+1…amnbm1c1c2…cmcm+1…cn0非基变量基变量如何用非基变量表示目标函数？第5页4.1单纯形表-zx1x2…xmxm+1…xnb010…0a1,m+1…a1nb1001…0a2,m+1…a2nb2………………………000…1am,m+1…amnbm100…0σm+1…σnm1i-cibim1i其中σj=cj-ciaij第6页4.1单纯形表c1…cmcm+1…cncjθCBxBbx1…xmxm+1…xnc1c2cm…x1x2xm…b1b2bm…100…001……………a1,m+1a2,m+1am,m+1……………a1na2namn…θ1θ2θm…zm1icibi0…0σm+1…σn第7页4.1单纯形表课堂练习写出线性规划问题的初始单纯形表第8页4.1单纯形表MaxZ=10X1+3X2+4X3X1、X2、X3≥03X1+6X2+2X3≤199X1+3X2+X3≤9第9页4.1单纯形表MaxZ=10X1+3X2+4X3X1、X2、X3、X4、X5≥03X1+6X2+2X3+X4=199X1+3X2+X3+X5=9化成标准型第10页4.1单纯形表103400cjθCBxBbx1x2x3x4x5z00x4x539632110011990103400m1iσj=cj-ciaijm1icibiz=第11页4.2计算步骤单纯形法基本步骤(1)寻找初始可行基，初始基可行解，建立初始单纯形表。(3)若有σk0，σk对应的Pk0，停，此问题无界；否则转(4)(2)对应于所有非基变量检验数σj0。若是，停，得到最优解；若否，转(3)。第12页4.2计算步骤单纯形法基本步骤θ=minaik0=biaikblalk定Xl为换出变量，alk为主元。由最小θ比值法求：Maxσj=σk→Xk换入变量σj0(4)第13页4.2计算步骤单纯形法基本步骤获得新的基可行解，转(2)(5)以alk为中心，换基迭代Pk=(a1k,a2k,…,amk)T变成单位向量第14页4.2计算步骤单纯形法实例MaxZ=2X1+3X24X1≤164X2≤12X1、X2≥0X1+2X2≤8第15页4.2计算步骤单纯形法实例23000cjθCBxBbx1x2x3x4x5z000x3x4x5140204100010001816120230004--3X(0)=(0,0,8,16,12)T第16页4.2计算步骤单纯形法实例23000cjθCBxBbx1x2x3x4x5z000x3x4x5140204100010001816120230004--3131/40-1/22x23902-3/424--X(1)=(0,3,2,16,0)T第17页4.2计算步骤单纯形法实例23000cjθCBxBbx1x2x3x4x5z003x3x4x2140001100010-1/201/42163-92000-3/424--x120-428130-21/4--412X(2)=(2,3,0,8,0)T第18页4.2计算步骤单纯形法实例23000cjθCBxBbx1x2x3x4x5z203x1x4x21000011-40010-1/221/4283-1300-201/4--412x5011/2-2401/4040-1/81/22140-3/2-1/8最优解X*=(4,2,0,0,4)T第19页4.2计算步骤课堂练习用单纯形法求解线性规划问题第20页4.2计算步骤103400cjθCBxBbx1x2x3x4x5z00x4x539632110011990103400第21页103400cjθCBxBbx1x2x3x4x5z00x4x53963211001199010340019/31103400cjθCBxBbx1x2x3x4x5z00x4x53963211001199010340019/31x11011/31/91/91055/3-1/316100-1/326/9-10/948/59第22页103400cjθCBxBbx1x2x3x4x5z010x4x10151/35/31/910-1/31/9161100-1/326/90-10/948/59103400cjθCBxBbx1x2x3x4x5z010x4x10151/35/31/910-1/31/9161-100-1/326/90-10/948/59x34193190-150-21360-26-9-4