- 1、本文档共104页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
由上例我们可以归纳出单纯形算法的步骤如下: 1 用标准形式表示问题 2 从含有初始基可行解的典范型方程组开始建立初始单纯形表示(注:对不易找到初始基的问题,将专门讨论) 3 应用内积规则求检验数 5 如有σj为负值,选取σj绝对值最大的一列为枢轴列,使这一列对应的变量为进基变量。 6 应用最小比值规则,决定枢轴行,使这一行的基变量出基。最小比值原则就是指,若进基变量为xr 。r列的系数为 解:利用单纯形表迭代得 解:对后面两个约束方程引进松弛变量x5, x6化为: 作业: 1. 如果所有判别数 。则由定理1(最优性判别定理)知当前的初始基本可行解是最优解,计算步骤终止。 2. 如果 可构造新的可行解. 先证明一个结论: 基变量对应的检验数: 下面再分两种情形讨论: 定理2.设B是(SLP)的一个可行基,若某非基变量 的判别数 且 。则此(SLP)问题的目标函数无上界无最优解 .(定理中的判别数 不一定是最小判别数, ) . 这个定理我们已经在上面作过讨论,下面再进行一次证明. (SLP)的目标函数无上界,因而问题无最优解。 解:引进松弛变量x4, x5化为 关于单纯行的迭代公式: 先回顾单纯形表格形式(SLP) 单纯形表实际上就是基B典则形式的一种表格表示方式,由此表立刻可以写出关于基B的典则形式来: 若对所有非基变量的检验数 ,则无论将哪个非基变量换为基变量都不可能将目标函数值增加,因而此时的基可行解即为最优。 因 (Ⅴ)恒成立. 下面进一步导出迭代前后可行基B以及B’对应各值之间迭代关系式。 是基B的单纯形表中各值。 用 表示基B’的单纯形表中各值,则B’的典则形式的m个等式约束应为: (Ⅶ) 将(Ⅶ)与(Ⅲ)(Ⅳ)对比可得去: 对于目标函数值: 则上面变换公式(1)(2)(3)可以统一成下面的枢 轴运算公式: 这个公式可采用下面的直观记忆方法: 那么当 的k不止一个时,怎样确定入基变量呢?理论上讲任选一个k就行了,但人们往往希望越大越好而目标函数增大值为: 因此我们希望选取 k 使(5)使右端极大,但是 : 经验表明,这样选取的 k 效果良好,能用较少的迭代次数求得最优解。 我们前面曾经指出单纯形算法是在极点上进行迭代的过程。下面将不加证明地给出一个定理说明对于非退化的基本可行解,迭代是沿着可行域的相邻极点进行迭代。 为此先给出相邻极点的概念。 定义3:设 是n维欧氏空间中多面凸集R的不同两点,Z是以 为端点的线段上的任一点,当它能表成R中异于Z的两点的出组合 即 我们再来综述一下前面所讲的内容: 如果有一个(LP)问题,且非退化,当能找到它的一个可行基B后,就一定可以解决这个(LP)问题了。因为可行基B必属于
您可能关注的文档
- 鲁教版化学元素与人体健康.ppt
- 鲁教版小学语文四年级上册《古诗词三首》课件 (2).ppt
- 第三章护理道德基本原则和规范.ppt
- 鲁教版必修二第三单元第一节《农业生产与地理环境》.ppt
- 鲁教版语文五年级下册《两小儿辩日》课件.ppt
- 第三章教育与人的身心发展.ppt
- 鲁教版语文五年级下册《桃花心木》课件.ppt
- 鲁教版语文四年级下册《小苗与大树的对话》课件.ppt
- 鲁教版语文四年级下册《钓鱼的启示》课件.ppt
- 第三章放射性制剂.ppt
- 第十一章 电流和电路专题特训二 实物图与电路图的互画 教学设计 2024-2025学年鲁科版物理九年级上册.docx
- 人教版七年级上册信息技术6.3加工音频素材 教学设计.docx
- 5.1自然地理环境的整体性 说课教案 (1).docx
- 4.1 夯实法治基础 教学设计-2023-2024学年统编版九年级道德与法治上册.docx
- 3.1 光的色彩 颜色 电子教案 2023-2024学年苏科版为了八年级上学期.docx
- 小学体育与健康 四年级下册健康教育 教案.docx
- 2024-2025学年初中数学九年级下册北京课改版(2024)教学设计合集.docx
- 2024-2025学年初中科学七年级下册浙教版(2024)教学设计合集.docx
- 2024-2025学年小学信息技术(信息科技)六年级下册浙摄影版(2013)教学设计合集.docx
- 2024-2025学年小学美术二年级下册人美版(常锐伦、欧京海)教学设计合集.docx
文档评论(0)