运筹学第一章 单纯形法进一步讨论ppt课件.ppt
《运筹学第一章 单纯形法进一步讨论ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学第一章 单纯形法进一步讨论ppt课件.ppt(24页珍藏版)》请在三一办公上搜索。
1、单纯形法进一步讨论,窦志武,云南财经大学 物流学院,单纯形法的进一步讨论人工变量法,人工变量法:前面讨论了在标准型中系数矩阵有单位矩阵,很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的变量称为人工变量,构成的可行基称为人工基,用大M法或两阶段法求解,这种用人工变量作桥梁的求解方法称为人工变量法。,例: min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2 -x3=3 x1+2x2 = 4 x1+2x2=4 x10, x2
2、0 xj0, (j=1,2,3,4),max z=-2x1-3x2+0 x3 -M x4-M x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5),引进人工变量,及M非常大正系数,模型转变为,这种处理方法称为大M法,以下则可完全按单纯形法求解。,1大M法,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,例1.10 用大M法解下列线性规划,解:首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵,无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量,得到人工变量单纯形法数学模型:,其中:M是一个
3、很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;再用前面介绍的单纯形法求解该模型,计算结果见下表。,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,例1.11 用大M法解下列线性规划,解:首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵,无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量,得到人工变量单纯形法数学模型:,其中:M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;再用前面介绍的单纯形法求解该模型,计算结果见下表。,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论
4、人工变量法,单纯形法的进一步讨论两阶段法,用计算机处理数据时,只能用很大的数代替M,可能造成计算机上的错误,故多采用两阶段法。,第一阶段: 在原线性规划问题中加入人工变量,构造如下模型:,对上述模型求解(单纯形法),若=0,说明问题存在基可行解,可以进行第二个阶段;否则,原问题无可行解,停止运算。,单纯形法的进一步讨论两阶段法,第一阶段的线性规划问题可写为:,第一阶段单纯形法迭代的过程见下表,单纯形法的进一步讨论两阶段法,单纯形法的进一步讨论两阶段法,第二阶段: 在第一阶段的最终表中,去掉人工变量,将目标函数的系数换成原问题的目标函数系数,作为第二阶段计算的初始表(用单纯形法计算)。,例:,单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学第一章 单纯形法进一步讨论ppt课件 运筹学 第一章 单纯 进一步 讨论 ppt 课件
链接地址:https://www.31ppt.com/p-1465904.html