资源描述：
《2019年 《管理运筹学》课件02单纯形法 .ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章单纯形法SimplexMethodSM1第2章单纯形法2.1单纯形法的基本思想2.2单纯形法的计算过程2.3人工变量法2.4单纯形法补遗第2章单纯形法2第2章单纯形法2.1单纯形法的基本思想单纯形法有三种形式：①方程组形式②表格形式③矩阵形式2.1.1方程组形式的单纯形法思路：由一个基本可行解转化为另一个基本可行解。s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1，x2，x3，x4，x5≥0maxz=3x1+5x2z-3x1-5x2=0例1范例等价改写为s.t.z-3x1-5x2=0x1+x3=82x2+x4=123x1+4x2+
2、x5=36x1，x2，x3，x4，x5≥0maxz目标方程3第2章单纯形法2.1单纯形法的基本思想00010001典式条典⑴当前基：m阶排列阵⑵目标方程中：一切基变量的系数σj=0Z-3x1-5x2=0x1+x3=8①2x2+x4=12②3x1+4x2+x5=36③(Ⅰ)0最优性检验：一切σj≥0？初始基本可行解X0=(0,0,8,12,36)Tz0=0排列阵：每行每列有且仅有一个元素为1，其余元素全为0的方阵。σ1=-3<0σ2=-5<0当前解X0非优；+0x3+0x4+0x5须由X0转化为另一个基本可行解X1。满足条典的方程组称为典式(方程组)。思路：让
3、X0中的一个非基变量进基，去替换原来的一个基变量（离基）。4第2章单纯形法2.1单纯形法的基本思想x1仍为非基变量，其值为0。x3=8x4=12-2x2x5=36-4x2→x2≤12/2→x2≤36/4离基（最小比值规则）：x2≤min{－，12/2，36/4}=6x2=min{－，12/2，36/4}=6－x4x4为离基变量进基（最小检验数规则）：在负检验数中选择最小的进基。min{σj︱σj<0}=σk→xk进基min{-3，-5}=-5=σ2→x2进基≥0≥0≥0==12X1=(120,6,8,0,)Tz-3x1-5x2=0x1+x3=8①2x2+x4
4、=12②3x1+4x2+x5=36③(Ⅰ)0由①②③有5第2章单纯形法2.1单纯形法的基本思想主方程0主列进基主元z-3x1-5x2=0x1+x3=82x2+x4=123x1+4x2+x5=36(Ⅰ)-69比值min离基以主列中正值元素为分母，同行右端常数为分子，求比值；按最小比值规则确定主方程和主元素，以及离基变量。6第2章单纯形法X0=(0,0,8,12,36)Tz0=0(Ⅱ)x1+x3=8①3x1-2x4+x5=12③得X1=z0=30称为单纯形法的一次迭代。z-3x1-5x2=0x1+x3=8①2x2+x4=12②3x1+4x2+x5=36③(Ⅰ)2
5、0x2+x4=6②12z-3x1+x4=30052(120,6,8,0,)T换基运算——方程组的初等变换目的是把主列变为单位向量：主元变为1，其余变为0。用换基运算将X0转化为另一个基本可行解X1。00102.1单纯形法的基本思想7第2章单纯形法2.1单纯形法的基本思想(Ⅲ)x1-x4+x5=4③2313x2+x4=6②12(Ⅱ)x1+x3=8①3x1-2x4+x5=12③x2+x4=6②12z-3x1+x4=30052x3+x4-x5=4①2313z+x4+x5=42012得X*=(4,6,4,0,0)Tz*=428-4min比值108第2章单纯形法2.1
6、单纯形法的基本思想2.1.2单纯形法的几何意义D(0,6)O(0,0)C(4,6)B(8,3)A(8,0)x1x2z=0脊线(4,6,4,0,0)T(0,0,8,12,36)T(0,6,8,0,12)Tz法向或棱线9第2章单纯形法2.2.1单纯形表范例:基于典式标准形cj基解x1x2x3x4x535000比值10100x3x4x58123602010000340010000-3-5检验行CBb352.2单纯形法的计算过程s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1，x2，x3，x4，x5≥0maxz=3x1+5x2z0=CBbT检验
7、行计算公式σj=CBaj-cj,Tj=1,2,…,n10第2章单纯形法2.2单纯形法的计算过程初始单纯形表的一般形式11第2章单纯形法2.2单纯形法的计算过程2.2.2单纯形法的计算步骤1°把LP问题化为标准形。2°在系数阵中找出或构造一个m阶排列阵作为初始可行基，建立初始单纯形表。3°最优性检验:若所有检验数σj≥0，就得到一个最优基本解，停止计算；否则转4°。4°解无界判断:在所有σj<0中,只要有一个σr<0所对应的系数列向量ar≤0，即一切air≤0，i=1,2,…,m则该LP问题解无界，停止计算；否则转5°。预备步骤迭代步骤12第2章单纯形法2.2
8、单纯形法的计算过程5°确定主元●先按最小检验数规则m
