单纯形法大M法两阶段法课件

目录目录单纯形算法计算步骤单纯形算法计算步骤初始可行基的确定初始可行基的确定 大大M法法 两阶段法两阶段法 4231目录单纯形算法计算步骤初始可行基的确定 大M法 两阶段法 线性规划的单纯形算法线性规划的单纯形算法 计算流程初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解?结束结束沿边界找新沿边界找新的基本可行解的基本可行解N NY Y线性规划的单纯形算法 计算流程初始基本可行解是否最优解或结束线性规划解的概念线性规划解的概念线性规划解的概念1.1.初始基本可行解的确定初始基本可行解的确定线性规划标准型：minZ=CX AX=b X 0从系数矩阵A中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,Pm)。进行等价变换约束方程两端分别左乘B1.1.初始基本可行解的确定线性规划标准型：minZ=CX 2.2.最优性检验最优性检验2.最优性检验3.基变换基变换取某一非基变量xk换入基（即让xk0，其余非基变量仍为0），同时再从基变量中换出一个变量xBr作为非基变量。如何求如何求换入入变量量xk和和换出出变量量xBr？3.基变换取某一非基变量xk换入基（即让xk0，其余非3.基变换基变换从目标函数看从目标函数看x xk k越小越好，但从可行性看越小越好，但从可行性看x xk k又不能任意小。又不能任意小。若若a aikik0,i=1,0,i=1,，m,xm,xk k可任意取值，此时问题是无界的；可任意取值，此时问题是无界的；若若a aikik0,0,为保证可行性，即为保证可行性，即x xBiBi=b=bi i-a-aikikx xk k00，应取，应取重复上述过程，直至所有的j均0，得到最优解。注意：xBr=03.基变换从目标函数看xk越小越好，但从可行性看xk又不能总结计算步骤：给定初始基总结计算步骤：给定初始基步步1.1.令令x xN N=0=0,，x xB B=B=B-1-1b=bb=b，z z0 0=c=cB Bx xB B；步步2.2.检验数检验数j j=c=cj j-c-cB BB B-1-1 P Pj j，j j0 0，停止，得最优解，否则取，停止，得最优解，否则取k kminminj j，转步，转步3 3；步步3.3.解解a ak k=B=B-1-1P Pk k，若，若a ak k00，停止，停止,不存在有限最优解不存在有限最优解.否则转否则转步步4.4.计算计算 x xk k进基，进基，x xBrBr离基，用离基，用P Pk k替代替代P PBrBr得新的可行基得新的可行基B B 步步5.5.以以a arkrk为主元素进行迭代为主元素进行迭代.转步转步2 2 新可行解：新可行解：x=(xB1,xBr-1,0,xBr+1,xBm,0,x=(xB1,xBr-1,0,xBr+1,xBm,0,，0,xk,0,0,xk,0,，0)0)总结计算步骤：给定初始基步1.令xN=0,，xB=B-1b=单纯形法流程图单纯形法流程图初始可行基开始以ark为主元素进行迭代得到最优解得到最优解YYNN所有j0？所有ark0?计算kminj|j0单纯形法流程图初始可行基开始以ark为主元素进行迭代得到最优单纯形法例题单纯形法例题 例 3.2 求解线性规划问题将线性规划问题化为标准形式作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下：CBXBb23000 x1x2x3x4x50 x381210040 x416400100 x512040013023000单纯形法例题 例 3.2 求解线性规划问题CBXBb23单纯形法例题单纯形法例题 0 x3210101/220 x4164001043x2301001/4920003/42x1210101/20 x480041243x2301001/4121300201/42x141001/400 x40021/213x22011/21/8014003/21/80表最后一行的检验数均为正，这表示目标函数值已不可能再减小，于是得到最优解，目标函数值 单纯形法例题 0 x3210101/220 x416400初始可行基的确定初始可行基的确定 若系数矩阵A中含有一个子矩阵是单位矩阵Im,则取Im为初始可行基。对于约束条件是“”形式的不等式，引入松弛变量将其转换为标准型，再将系 数矩阵中松弛变量对应的单位矩阵取为初始可行基。对于约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，可 采用人工变量，即对不等式约束就减去一个非负的剩余变量后，再加入一个 非负的人工变量；对等式约束再加入一个非负的人工变量，总可得到一个单位 矩阵作为初始可行基。初始可行基的确定 若系数矩阵A中含有一个子矩阵是单位矩阵Im大大M法和两阶段法法和两阶段法 如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解 题时应先加入人工变量，人工地构成一个单位向量组。人工变量只起过渡作用，不应影响决策变量的取值。两种方法可控制人工变量取值使用，尽快地把人工变量减小到零。大M法 两阶段法大M法和两阶段法 如果线性规划模型中约束条件系数矩阵中不存在大大M法法 min z=-3X1+X2+X3 x1-2x2+x3 11 -4x1+x2+2 x3 3 -2x1+x3=1 x1，x2，x3 0 min z=-3X1+X2+X3+0 x4+0 x5 Mx6 Mx7 x1-2x2+x3+x4 =11 -4x1+x2+2 x3 -x5+x6 =3 -2x1+x3 +x7 =1 x1，x2，x3，x4，x5，x6，x7 0大M单纯形法要求将目标函数中 的人工变量被指定一个很大的 目标函数系数（人工变量与松 弛剩余变量不同之处）。大M法 min z=-3X1+X2+X3 两阶段法两阶段法 min z=-3X1+X2+X3 x1-2x2+x3 11 -4x1+x2+2 x3 3 -2x1+x3=1 x1，x2，x3 0 min z=x6+x7 x1-2x2+x3+x4 =11 -4x1+x2+2 x3 -x5+x6 =3 -2x1+x3 +x7 =1 x1，x2，x3，x4，x5，x6，x7 0第一阶段，构筑一个只包括人工变量 的目标函数,在原约束条件下求解，如果计算结果是人工变量均为0，则 继续求解；进入第二阶段，如果人工 变量不为0，说明原问题无解。目的 是为原问题求初始基可行解。第二阶段，在此基可行解基础上对原 目标函数进行优化。两阶段法 min z=-3X1+X2+X3 习题三习题三 2.(1)用单纯形法求解线性规划问题：将线性规划问题化为标准形式 作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下：习题三 2.(1)用单纯形法求解线性规划问题：习题三习题三 作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下：此时，均为正，目标函数已不能再减小，于是得到最优解为：x*=(1,1.5,0,0)T目标函数值为：f(x*)=17.5习题三 作初始单纯形表，按单纯形法计算步骤进行迭代，结果如习题三习题三 3.(1)分别用单纯形法中的大 M 法和两阶段法求解下列线性规划问题：解：大 M 法：把原问题化为标准形式，并加入人工变量如下：习题三 3.(1)分别用单纯形法中的大 M 法和两阶段法求解习题三习题三 因为 M 是一个很大的正数，此时j 均为正,所以，得到最优解：x*=(0,0,1,1,)T，最优值为 f(x*)=3习题三 因为 M 是一个很大的正数，此时j 均为正,所以习题三习题三 解：两阶段法：首先，构造一个仅含人工变量的新的线性规划如下：按单纯形法迭代如下：习题三 解：两阶段法：首先，构造一个仅含人工变量的新的线性习题三习题三 最优解为：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。习题三 最优解为：x*=(0,0,1,1,0,linprog函数求解函数求解线性性规划划问问题 其中，f,x,b,beq,lb,ub为向量,A,Aeq为矩阵。x=linprog(f,A,b)功能：求解最小化问题 min f*x 条件 A*x b。x=linprog(f,A,b,Aeq,beq)功能：求解最小化问题 min f*x 条件 A*x b Aeq*x=beq，如果没有不等式就设置A=和b=；没有等式就设置 Aeq=,beq=x=linprog(f,A,b,Aeq,beq,lb,ub)功能：求解最小化问题 min f*x 条件 A*x b Aeq*x=beq lb x ub，决策变量有上下限时，如果没有不等式就设置A=和b=；没有等式就设置 Aeq=,beq=x=linprog(f,A,b,Aeq,beq,lb,ub,x0)功能：求解最小化问题 min f*x 条件 A*x b Aeq*x=beq lb x ub，如果没有不等式就设置A=和b=。设置初始点x0。x,fval=linprog(.)功能：返回目标函数最优解x，和在x处的值：fval=f*x.linprog函数求解线性规划问题 其中，f,x,b