单纯形法简介

单纯形法简介单纯形法简介,及其基本原理步骤

大家好,欢迎来到IT知识分享网。

原理

考虑目标函数,

maxz=3x1+4x2



增加

x1


x2
的值都将改进

z
的值,单纯形法的设计要求每次都选择使



z

值有最大改善的那个变量。意味着在上述目标函数中,首先选择增加

x2
的值。

基础

通过对问题约束施加以下两项要求来方便单纯形法的计算:
1. 所有的约束都是等式,并且具有非负右端项
2. 所有变量都是非负的

松弛化

将不等式转化为带有非负右端项的等式约束

  • 为了把 不等式约束转换为等式约束,在不等式的左端,增加非负的松弛变量。
  • 不等式约束转换为等式约束,在不等式的左端,减去非负的剩余变量。

基本术语

mn 阶方程组定义的解空间中,基本解对应解空间的角点,设定 nm 个变量等于零,求解剩下的 m 个变量的

m
阶方程组。因此角点的最大数目为 Cmn 。其中 nm 个零变量称为非基变量,剩余 m 个变量称为基变量

实例



maxz=5x1+4x2s.t.6x1+4x224x1+2x26x1+x11x22x1,x20

松弛化后,

maxz=5x1+4x2+0s1+0s2+0s3+0s4s.t.6x1+4x2+s1=24x1+2x2+s2=6x1+x1+s3=1x2+s4=2x1,x2,s1,s2,s3,s40



初始单纯形表表示为:


这里写图片描述

目标函数 z=5x1+4x2 表明, x1 作为进基变量,可以最大程度增 z

x1
成为进基变量后,当前的某个基变量就必须离开,变成取值为零的非基变量。确定离基变量的技巧,计算方程的右端项与相应的在进基变量 x1 下方约束系数的非负比(实际上计算的比值是这些约束关于进基变量 x1 轴的截距),

s1s2s3s4611024612246=461=611=1()20=(0)



进基变量和离基变量的交换过程由高斯-若尔当行计算完成。其中进基变量所在列为枢轴列,离基变量所在行为枢轴行,处于枢轴行列交叉位置的元素为枢轴元素(高斯-若尔当行计算具体步骤看基本步骤部分)。由此得到新的单纯形表,


这里写图片描述

第三次迭代得到最优结果,
这里写图片描述
这里写图片描述

基本步骤

  • 最优性条件 在极大化(极小化)问题中,进基变量是 z 行中具有最小负值(最大正值)系数的非基变量,如有多个则选其一。当非基变量的所有

    z
    行系数是非负(非正)时,迭代达到最优。
  • 可行性条件 对于极大化问题和极小化问题,离基变量都是具有最小非负比(有严格正分母)的基变量。
  • 高斯-若尔当行计算
    1. 枢轴行。
      (a) 在基列中,用进基变量替换离基变量。
      (b) 新的枢轴行 = 当前枢轴行 / 枢轴元素
    2. 包括 z <script type=”math/tex” id=”MathJax-Element-22″>z</script>的所有其他行
      新行 = 当前行 – 枢轴列元素 * 新的枢轴行

单纯形法的步骤如下:
S1: 确定初始基本可行解
S2: 用最优性条件选择一个进基变量。如果没有进基变量,停止计算,上一个解就是最优的。否则,转到S3.
S3: 用可行性条件选择离基变量。
S4: 用高斯-若尔当运算确定新的基本解,转到S2。

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/15564.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信