• / 24
  • 下载费用:10 金币  

单纯形法、大M法、两阶段法.ppt

关 键 词:
单纯形法、大M法、两阶段法.ppt
资源描述:
线性规划的单纯形算法,目录,单纯形算法计算步骤,初始可行基的确定,大M法,两阶段法,4,2,3,1,线性规划的单纯形算法,计算流程,线性规划解的概念,,1. 初始基本可行解的确定,线性规划标准型: minZ=CX AX=b X ≥0 从系数矩阵A中找到一个可行基B,不妨设B由A的前m列组成, 即B=(P1,P2,……Pm)。进行等价变换--约束方程两端分别左乘B-1.,,2. 最优性检验,,3. 基变换,取某一非基变量xk→换入基(即让xk0,其余非基变量仍为0),同时再从基变量中换出一个变量xBr→作为非基变量。,如何求换入变量xk和换出变量xBr?,3. 基变换,从目标函数看xk越小越好,但从可行性看xk又不能任意小。若aik≤0,i=1,…,m,xk可任意取值,此时问题是无界的;若aik0,为保证可行性,即xBi=bi-aikxk≥0,应取,,重复上述过程,直至所有的σj均≥0,得到最优解。,注意:xBr=0,总结计算步骤:给定初始基,步1.令xN=0,,xB=B-1b=b,z0=cBxB ; 步2.检验数σj=cj-cBB-1 Pj,σ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),,单纯形法流程图,单纯形法例题,例 3.2 求解线性规划问题将线性规划问题化为标准形式作初始单纯形表,按单纯形法计算步骤进行迭代,结果如下:,单纯形法例题,,表最后一行的检验数均为正,这表示目标函数值已不可能再减小,于是得到最优解,目标函数值 .,初始可行基的确定,若系数矩阵A中含有一个子矩阵是单位矩阵Im,则取Im为初始可行基。对于约束条件是“≤”形式的不等式,引入松弛变量将其转换为标准型,再将系数矩阵中松弛变量对应的单位矩阵取为初始可行基。对于约束条件是“≥”形式的不等式及等式约束情况,若不存在单位矩阵时,可采用人工变量,即对不等式约束就减去一个非负的剩余变量后,再加入一个非负的人工变量;对等式约束再加入一个非负的人工变量,总可得到一个单位矩阵作为初始可行基。,大M法和两阶段法,如果线性规划模型中约束条件系数矩阵中不存在单位向量组,解题时应先加入人工变量,人工地构成一个单位向量组。人工变量只起过渡作用,不应影响决策变量的取值。两种方法可控制人工变量取值使用,尽快地把人工变量减小到零。,大M法两阶段法,大M法,,,,大M单纯形法要求将目标函数中的人工变量被指定一个很大的目标函数系数(人工变量与松弛剩余变量不同之处)。,两阶段法,,,,第一阶段,构筑一个只包括人工变量的目标函数,在原约束条件下求解, 如果计算结果是人工变量均为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)功能:求解最小化问题 min f*x 条件 A*x ≤ b。 x = linprog(f,A,b,Aeq,be
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:单纯形法、大M法、两阶段法.ppt
链接地址:https://www.weizhuannet.com/p-9836670.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开