[经济学]第2章 纯真形法.ppt 96页

admin/2020-03-31/ 分类:英语口语/阅读:
运筹学第2章 纯真形法 本章常识内容 纯真形法的基本思维 纯真形法道理 纯真形法的计算过程 人工变量法 纯真形法补遗 2.1 纯真形法的基本思维 纯真形法(Simplex Method)是美国有名运 ...

  运筹学第2章 纯真形法 本章常识内容 纯真形法的基本思维 纯真形法道理 纯真形法的计算过程 人工变量法 纯真形法补遗 2.1 纯真形法的基本思维 纯真形法(Simplex Method)是美国有名运 筹学家丹茨格(Dantzig)1947年起首提出的。 该方法简捷、规范,是环球公认的处理LP问 题的通用有效算法。 纯真形法不只是处理LP后果的最基本的算法 之一,而且成为处理整数计划和非线性计划某 些算法的基础。 纯真形法的3种方法—— 方程组方法(代数方法) 表格方法 矩阵方法 纯真形法的基本思路—— 基于LP后果的规范形,先想法找到某个基本可行解(称为初始基本可行解); 末尾实施从这个基本可行解向另外一个基本可行解的转换,请求这类转换不只轻易完成,而且能改良(至少保持)目标函数值; 继续寻觅更优的基本可行解,进一步改良目标函数值。当某一个基本可行解不能再改良时,该解就是最优解。(或许是出现无可行解、无最优解、无量多最优解的状况) 2.1.1 方程组方法的纯真形法 例1 一个企业需求统一种原资料花费甲、乙 两种产品,它们的单位产品所需求的原资料 的数量及所消耗的加工时间各不相反,取得 的利润也不相反(以下表)。请问,该企业 应若何安插花费计划,才华使取得的利润达 到十分? 解:该后果的LP模型为 将该后果的LP模型化为规范形 函数束缚的增广矩阵为: 很明显 R(A)=R(A,b)=2 < 4,即 该方程组有没有量多组解。 系数矩阵为: 决定计划变量向量为: 拔取 为基矩阵 则 为基变量, 为非基变量 令非基变量 ,则可以掉掉落一基本 可行解为: 下面的计算都是以它为初始点逐次实施转 换,故将其称为初始基本可行解。 此时,Z=0,其经济含义为:该企业没 有安插甲、乙两种产品的花费,固然也 就没有益润可言。 条典 初始基本可行解所对应的可行基是一个m阶的单位阵; 目标函数表达式中一切的基变量的系数全部为0。 这是纯真形法所必须的!!! 剖析目标函数表达式 非基变量的系数都是正数,若将它们转换为基变量,目标函数值则就会能够添加。 经济含义:每辨别多花费一个单位产品甲、乙,目标函数值辨别添加6、4,即利润辨别添加600元、 400元。 添加的单位产品对目标函数的贡 献值,这就是考验数的概念。 只需目标函数表达式中还存在正考验数, 就需求把它所对应的非基演变变成基变量! 纯真形法一次只能把一个非基演变变成基变量 选择先将哪个非基演变变成基变量? 添加单位产品甲比添加单位产品乙对目 标函数值的贡献大年夜。(考验数大年夜) 通俗选择正系数十分所对应的阿谁非基 变量作为换入变量,将它换入到基变量中 去,与此同时还要肯定基变量中有一个要 换出来变成非基变量! 几个名词 进基、进基变量 离基、离基变量 十分考验数规矩 最小比值规矩 主元/主方程 迭代(扭转运算) 添加单位产品甲比乙对目标函数 的贡献值大年夜(600>400),故先把非 基变量 酿成基变量,称为让 进基,同时称 为进基变量。 十分考验数规矩 若记考验数为 ,个中包罗 基变量的考验数(它们全部为0),十分考验数规 则的数学表达式为: 关于本例,则有 故选择让 进基。 当肯定一个非基变量进基后,响应的就要 从基变量中换出某一个基变量,使其变成非 基变量,称为让该变量离基,同时称其为离 基变量。若何选择离基变量呢? 仍为非基变量即 当且仅当 时,原基变量中才有一个 变量等于0,即 ,故选择 离基。 因此可以肯定: 如许既肯定了离基变量,同时又保证其余的 基变量 ,也即保证了下面转换得 到的解依然是一个基本可行解。 记得:满足条典!!! 为了求得以 为基变量的一个新的 基本可行解,又为使其满足条典,以便考验 它可否最优,必须对方程组停止一番初等变 换,其主要目标是让进基变量 的系数列 向质变成单位向量。 在这里,我们把上式中的最小比值120/4 的分母4称为主元。主元地点方程为主方程。 换基运算 掉掉落: 令新的非基变量 ,掉掉落新的 基本可行解: 经济含义—— 只安插花费甲产品30个单位,此时可取得 利润180百元。 这个计划比前计划优,但可否曾经是最优? 剖析: 非基变量 的系数仍为正数,由十分考验数规矩,则肯定

阅读:

推荐文章

Recommend article
bet手机
微信二维码扫一扫
关注微信公众号
联系QQ:329435596 邮箱:329435596@qq.com Power by DedeCms
二维码
意见反馈 二维码