单纯形法大M法两阶段法

目录单纯形算法计算步骤初始可行基的确定大M法两阶段法4231线性规划的单纯形算法计算流程初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY线性规划解的概念12(,)(,,P)BBNBPP分解m若A=，其中…，可逆，称为基矩阵1B2BNNnxxxX,xxxx基相应地＝为，为变量非基变量B-11BNBNNx,xxxBxxbBB代入约束：(B,N)即+N=b,＝b-N-1B-1NBNxBbxxBx0令=0,＝b，称x=为基本解-1BNxBbBx0基本可行解若x=0称为，为可行基1.初始基本可行解的确定线性规划标准型：minZ=CXAX=bX≥0从系数矩阵A中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,……Pm)。进行等价变换－－约束方程两端分别左乘B－1.-11BNBNxxxBxBB即+N=b,＝b-N-1NBbx0(0)令=0,得初始基本可行解x-1-10Bb(,)Bb0NBBccc(0)对应的目标函数值z=cx2.最优性检验-11BNAXxBxB由=b,＝b-N，其目标函数值：BBNNx(,)x+xxNBBNccccz=cx-1-1NN(Bb-BNx)+xBNcc-1-1NBb(BN)xBBNccc－－-10N+(BN)xNBzcc-10jjjR+(BP)x,jBzccR非基变量下标集-1NBNNBcc记-1jBjBjccPjR即，(0)0,jjx，判别准则：当则得到最优解否则继续寻找改进的基为检验数本可行解-1BBBB0Bcc注＝3.基变换取某一非基变量xk→换入基（即让xk0，其余非基变量仍为0），同时再从基变量中换出一个变量xBr→作为非基变量。如何求换入变量xk和换出变量xBr？kmin{|0},0,0jjjRk选令x其余非基变量＝-11BNAXxBxB由=b,＝b-Nkxk＝b-A-11-11kkK0BxBPx0BBBKx＝b-（,P,）b-3.基变换kbaxbaB111kBBmmmkx更详细地x=＝x-10jj0jjR+(BP)x+TjBkzzcczx从目标函数看xk越小越好，但从可行性看xk又不能任意小。若aik≤0,i=1,…，m,xk可任意取值，此时问题是无界的；若aik0,为保证可行性，即xBi=bi-aikxk≥0，应取ikikbxa=min{|0}irikikbaa令rrkba重复上述过程，直至所有的σj均≥0，得到最优解。注意：xBr=0总结计算步骤：给定初始基步1.令xN=0,，xB=B-1b=b，z0=cBxB；步2.检验数σj=cj-cBB-1Pj，σj≥0，停止，得最优解，否则取σk＝min{σj}，转步3；步3.解ak=B-1Pk，若ak≤0，停止,不存在有限最优解.否则转步4.计算xk进基，xBr离基，用Pk替代PBr得新的可行基B步5.以ark为主元素进行迭代.转步2新可行解：x=(xB1,…xBr-1,0,xBr+1,…,xBm,0,…，0,xk,0,…，0)min{|0}irikikbaa＝rrkba单纯形法流程图初始可行基开始以ark为主元素进行迭代得到最优解得到最优解YYNN所有σj≥0？所有ark≤0?计算σk＝min{σj|σj0}min{|0}irikikbaa＝rrkba单纯形法例题例3.2求解线性规划问题将线性规划问题化为标准形式作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下：12121212max()2328416..4120fXxxxxxstxxx，，，，，．12345123142512345min[()]2300028416..4120fXxxxxxxxxxxstxxxxxxx，，，，，，，，．CBXBb－2－3000x1x2x3x4x50x381210040x41640010－0x5120[4]00130－2－3000单纯形法例题0x32[1]010－1/220x416400104－3x2301001/4－9－20003/4－2x121010－1/2－0x4800－41[2]4－3x2301001/412130020－1/4－2x141001/400x５400－21/21－3x22011/2－1/8014003/21/80表最后一行的检验数均为正，这表示目标函数值已不可能再减小，于是得到最优解，目标函数值．*42004TX［，，，，］14)(*Xf初始可行基的确定若系数矩阵A中含有一个子矩阵是单位矩阵Im,则取Im为初始可行基。对于约束条件是“≤”形式的不等式，引入松弛变量将其转换为标准型，再将系数矩阵中松弛变量对应的单位矩阵取为初始可行基。对于约束条件是“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人工变量，即对不等式约束就减去一个非负的剩余变量后，再加入一个非负的人工变量；对等式约束再加入一个非负的人工变量，总可得到一个单位矩阵作为初始可行基。大M法和两阶段法如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。人工变量只起过渡作用，不应影响决策变量的取值。两种方法可控制人工变量取值使用，尽快地把人工变量减小到零。•大M法•两阶段法大M法minz=-3X1+X2+X3x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0minz=-3X1+X2+X3+0x4+0x5–Mx6–Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，x2，x3，x4，x5，x6，x7≥0大M单纯形法要求将目标函数中的人工变量被指定一个很大的目标函数系数（人工变量与松弛剩余变量不同之处）。两阶段法minz=-3X1+X2+X3x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0minz=x6+x7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，x2，x3，x4，x5，x6，x7≥0第一阶段，构筑一个只包括人工变量的目标函数,在原约束条件下求解，如果计算结果是人工变量均为0，则继续求解；进入第二阶段，如果人工变量不为0，说明原问题无解。目的是为原问题求初始基可行解。第二阶段，在此基可行解基础上对原目标函数进行优化。习题三2.(1)用单纯形法求解线性规划问题：将线性规划问题化为标准形式作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下：习题三作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下：此时，σ均为正，目标函数已不能再减小，于是得到最优解为：x*=(1,1.5,0,0)T目标函数值为：f(x*)=17.5习题三3.(1)分别用单纯形法中的大M法和两阶段法求解下列线性规划问题：解：大M法：把原问题化为标准形式，并加入人工变量如下：习题三因为M是一个很大的正数，此时σj均为正,所以，得到最优解：x*=(0,0,1,1,)T，最优值为f(x*)=−3习题三解：两阶段法：首先，构造一个仅含人工变量的新的线性规划如下：按单纯形法迭代如下：习题三最优解为：x*=(0,0,1,1,0,0)T，最优值：g(x)=0因人工变量x5=x6=0，则原问题的基可行解为:x=(0,0,1,1,)T,进入第二阶段计算如下表所示：由上表可知，检验数均大于等于0，所以得到最优解：x*=(0,0,1,1,)T最优值为f(x*)=−3。linprog函数求解线性规划问题其中，f,x,b,beq,lb,ub为向量,A,Aeq为矩阵。x=linprog(f,A,b)功能：求解最小化问题minf*x条件A*x≤b。x=linprog(f,A,b,Aeq,beq)功能：求解最小化问题minf*x条件A*x≤bAeq*x=beq，如果没有不等式就设置A=[]和b=[]；没有等式就设置Aeq=[],beq=[]x=linprog(f,A,b,Aeq,beq,lb,ub)功能：求解最小化问题minf*x条件A*x≤bAeq*x=beqlb≤x≤ub，决策变量有上下限时，如果没有不等式就设置A=[]和b=[]；没有等式就设置Aeq=[],beq=[]x=linprog(f,A,b,Aeq,beq,lb,ub,x0)功能：求解最小化问题minf*x条件A*x≤bAeq*x=beqlb≤x≤ub，如果没有不等式就设置A=[]和b=[]。设置初始点x0。[x,fval]=linprog(...)功能：返回目标函数最优解x，和在x处的值：fval=f'*x.