《管理运筹学》课件02-单纯形法.ppt

《《管理运筹学》课件02-单纯形法.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》课件02-单纯形法.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第二章第二章 单纯形法单纯形法Simplex MethodSM1第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想2.2 单纯形法的计算过程单纯形法的计算过程2.3 人工变量法人工变量法2.4 单纯形法补遗单纯形法补遗第第2章章 单纯形法单纯形法2第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想 单纯形法有三种形式：单纯形法有三种形式：方程组形式方程组形式 表格形式表格形式 矩阵形式矩阵形式2.1.1 方程组形式的单纯形法方程组形式的单纯形法思路思路思路思路：由一个基本可行解转化为另一个基本可行解。由一个基本可行解转化为另一个基本可行解。s.t.x1 +x3 =8 2x

2、2 +x4 =12 3x1+4x2 +x5 =36 x1 ，x2 ，x3，x4，x5 0 max z=3x1+5x2z-3x1-5x2=0例例1 范例范例等价改写为等价改写为s.t.z -3x1-5x2 =0 x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 x1 ，x2 ，x3，x4，x5 0 max z目标方程目标方程3第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想1 0 020 1 030 0 1典式典式典式典式 条条条条 典典典典 当前基：当前基：m阶阶排列阵排列阵 目标方程目标方程中：一切基变量中：一切基变量 的系数的系数 j=0Z-3x1 -

3、5x2 =0 0 x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5=36 ()0最优性检验：最优性检验：一切一切一切一切 j 0？初始基本可行解初始基本可行解 X0=(0,0,8,12,36)T z0=0 0 排列阵排列阵：每行每列有且仅有一个元素每行每列有且仅有一个元素为为1 1 1 1，其余元素全为，其余元素全为0 0 0 0 的方阵。的方阵。1=-3 0 2=-5 0当前解当前解 X0 非优；非优；+0 x3+0 x4+0 x5须由须由X0 转化为另一个基本可行解转化为另一个基本可行解 X1。满足满足条典条典条典条典的的方程组方程组称为称为典式典式典式典式(方程组方程组

4、方程组方程组)。思路思路思路思路：让：让X0 中的一个中的一个非基变量非基变量进基进基，去替换原来的一个，去替换原来的一个基变量基变量基变量基变量（离基离基）。）。4第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想x1仍为非基变量，其值为仍为非基变量，其值为0。x3=8x4=12-2x2x5=36-4x2 x2 12/2 x2 36/4w 离基离基离基离基（最小比值规则最小比值规则最小比值规则最小比值规则）：x2 min，12/2，36/4 =6 x2 =min，12/2，36/4 =6 6 6 6 x4x4为为离基变量离基变量w 进基进基（最小检验数规则最小检验数规则最小检验数规

5、则最小检验数规则）：）：在在负检验数负检验数负检验数负检验数中选择中选择最小的最小的最小的最小的进基进基。min j j0 =k xk 进基进基 min-3，-5 =-5=2 x2 进基进基 0 0 0 0 0 0=12121212 X1=(120,6,8,0,)Tz-3x1 -5x2 =0 0 x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 ()0由由 有有5第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想主方程主方程主方程主方程 0主列主列进基进基主元主元 z-3x1 -5 x2 =0 x1 +x3 =8 2 x2 +x4 =12 3x1 +4 x2

6、 +x5 =36()-69比值比值比值比值min离基离基离基离基以以主列主列中中正值元素正值元素正值元素正值元素为为分母分母分母分母，同行，同行右端常数右端常数右端常数右端常数为为分子分子分子分子，求，求比值比值比值比值；按按最小最小最小最小比值比值比值比值规则规则规则规则确定确定主方程主方程主方程主方程和和主元素主元素主元素主元素，以及，以及离基变量离基变量离基变量离基变量。6第2章 单纯形法X X0 0 =(0,0,8,12,36 )=(0,0,8,12,36 )T T z z0 0 =0=0 ()x1 +x3 =8 3x1 -2x4 +x5 =12 得得X X1 1=z z0 0 =30

7、=30称为单纯形法的一次称为单纯形法的一次迭代迭代。z-3x1 -5x2 =0 x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 ()20 x2 +x4 =6 12 z-3x1 +x4 =30052(12120,0,6,6,8,8,0,0,)T T换基运算换基运算换基运算换基运算方程组方程组方程组方程组的的初等变换初等变换初等变换初等变换目的目的目的目的是把是把主列主列主列主列变为变为单位向量单位向量单位向量单位向量：主元：主元：主元：主元变变为为1，其余变为，其余变为0。用用换基运算换基运算换基运算换基运算将将X0 转化为转化为另一个基本另一个基本可行解可行解 X

8、X1 1。0 00 01 10 02.1 单纯形法的基本思想单纯形法的基本思想7第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想()x1 -x4 +x5=4 2 31 3x2 +x4 =6 12()x1 +x3 =8 3 x1 -2x4 +x5 =12 x2 +x4 =6 12 z-3x1 +x4 =30052 x3 +x4 -x5=4 2 31 3 z +x4 +x5=42012得得X X*=(4,4,6,6,4,4,0,0,0 0 )T T z*z*=42428 8-4 4min比值比值比值比值108第2章 单纯形法2.1 单纯形法的基本思想单纯形法的基本思想2.1.2 单纯形

9、法的几何意义单纯形法的几何意义D(0,6)O(0,0)C(4,6)B(8,3)A(8,0)x1x2z=0脊线脊线(4,6,4,0,0)(4,6,4,0,0)T T(0,0,8,12,36)(0,0,8,12,36)T T(0,6,8,0,12)(0,6,8,0,12)T Tz z 法向法向法向法向或或或或棱线棱线棱线棱线9第2章 单纯形法 单纯形表单纯形表范例范例:基于基于典式典式典式典式标准形标准形标准形标准形cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 81236 0 2 0 1 000 0 3 4 0 0 1 0 00

10、0 0 00 0-3 3-5 5检验行检验行C CB Bb b352.2 单纯形法的计算过程单纯形法的计算过程s.t.x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 x1 ，x2 ，x3，x4，x5 0 max z=3x1+5x2z z0 0=C CB Bb b T检验行检验行计算公式计算公式计算公式计算公式 j j =C CB Ba aj j -cj,Tj=1,2,n10第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程初始单纯形表初始单纯形表的一般形式的一般形式11第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程 2.2.2 单纯形法的计算

11、步骤单纯形法的计算步骤1 1 把把LP问题化为问题化为标准形标准形标准形标准形。2 2 在系数阵中找出或构造一个在系数阵中找出或构造一个mm阶阶阶阶排列阵排列阵排列阵排列阵作为初始作为初始 可行基，建立可行基，建立初始单纯形表初始单纯形表初始单纯形表初始单纯形表。3 3 最优性检验最优性检验最优性检验最优性检验:若所有检验数若所有检验数j 0，就得到一个，就得到一个 最优基本解，停止计算；否则转最优基本解，停止计算；否则转4。4 4 解无界判断解无界判断解无界判断解无界判断:在所有在所有j 0中中,只要有一个只要有一个r 0 所对应的系数列向量所对应的系数列向量 ar 0，即一切，即一切 ai

12、r 0，i=1,2,m 则该则该LP问题问题解无界解无界解无界解无界，停止计算；否则转，停止计算；否则转5。预预预预备备备备步步步步骤骤骤骤迭迭迭迭代代代代步步步步骤骤骤骤12第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程 5 5 确定主元确定主元确定主元确定主元 先按先按最小检验数规则最小检验数规则最小检验数规则最小检验数规则 min jj 0 =aikbial kbl迭迭迭迭代代代代步步步步骤骤骤骤13第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程2 2.2 2.3 3 单纯形法计算之例单纯形法计算之例范例范例 第第第第0 0 0 0次迭代次迭代次迭代次迭代cj

13、 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 812 36 0 2 0 1 000 0 3 4 0 0 1 0 -3 -5 0 0 0-6 9min214第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程第一次迭代第一次迭代第一次迭代第一次迭代cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 81236 0 2 0 1 000 0 3 4 0 0 1 0 -3 -5 0 0 0-6 9min2x3x2 x5 05 01/2 8 1 0 1 0 0-25/2

14、4min 1600012300130-30008-15第2章 单纯形法2.2 单纯形法的计算过程单纯形法的计算过程cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x2 x5 8612 0 1 0 1/2 005 0 3 0 0 -2 1 30 -3 0 0 5/2 0 x3x2 x1 05 36 0 1 0 1/2 04 0 0 1 2/3 -1/3 4 1 0 0 -2/3 1/342 0 0 0 1/2 18-4min3X*=(4,6,4,0,0)T,z*=42第第第第二二二二次次次次迭迭迭迭代代代代16第2章 单纯形法2.2 单纯形法

15、的计算过程单纯形法的计算过程s.t.max z=3x1+2x2 -2x1 +x2 2 x1-3x2 3 x1，x2 0 s.t.max z=3x1+2x2 -2x1 +x2 +x3 =2 x1-3x2 +x4 =3 x1，x2，x3，x4 0 cj 基基 解解 x1 x2 x3 x4 3 2 0 0 -2 1 1 0 x3x4 23 1 -3 0 100 0 -3 -2 0 01 3 1 1 -3 0 1x3x1 03 8 0 0 -5 1 2 9 0 0 -11 0 3解无界解无界例例2 2 求解下述求解下述LP问题问题17第2章 单纯形法2.3 人工变量法人工变量法 考虑考虑标准型标准型(

16、M)：分别给每个约束方程分别给每个约束方程硬性加入硬性加入硬性加入硬性加入一个非负变量一个非负变量 a11x1+a12x2+a1nxn +xn+1n+1 =b1(0)a12x1+a22x2+a2nxn +xn+2n+2 =b2(0)am1x1+am2x2+amnxn +xn+mn+m =bm(0)n个个 xn+1,xn+2,xn+m 称为称为人工变量人工变量。初始基本可行解：初始基本可行解：(人造基本解人造基本解人造基本解人造基本解)X X0 0=(0,0,0,b1,b2,bm)T(2 2.1 1)18第2章 单纯形法 基本思想：基本思想：基本思想：基本思想：人造解人造解 X0 不是原不是原L

17、PLP问题的基本可行解。问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即的人工变量都替换出去，都变为非基变量（即 人工变量人工变量xn+1=xn+2=xn+m=0），则），则X0的的 前前n个分量就构成原个分量就构成原LPLP问题的一个基本可行解。问题的一个基本可行解。反之，若经过迭代，不能把人工变量都变反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原为非基变量，则表明原LPLP问题问题无可行解无可行解。2.3 人工变量法人工变量法19第2章 单纯形法2.3 人工变量法人工变量法 大大M法法 在原问题

18、的目标函数中添上全部人工变量，并令其系数在原问题的目标函数中添上全部人工变量，并令其系数 都为都为-M，而而M是一个是一个充分大的正数充分大的正数。即。即 max z=c1x1+c2x2+c3x3 +cnxn M(xn+1+xn+2+xn+m)由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系数的人工变量从基变量中替换出去。数的人工变量从基变量中替换出去。若迭代最终得到若迭代最终得到最优解最优解最优解最优解X*X*，而且，而且基变量基变量基变量基变量中中不含有人工变量不含有人工变量不含有人工变量不含有人工变量，则，则X*X*的的前前

19、n个分量就构成原问题的一个个分量就构成原问题的一个最优基本解最优基本解最优基本解最优基本解；否则，原问题；否则，原问题无可行解无可行解无可行解无可行解。若迭代结果是若迭代结果是解无界解无界解无界解无界，而且，而且基变量基变量基变量基变量中中不含有人工变量不含有人工变量不含有人工变量不含有人工变量，则原问题也则原问题也解无界解无界解无界解无界；否则，原问题；否则，原问题无可行解无可行解无可行解无可行解。20第2章 单纯形法2.3 人工变量法人工变量法 例例3 3 用大用大M法求解下述法求解下述LPLP问题问题 max z=3x1 x2 2x3 3x1+2x2 3x3 =6 x1 2x2 +x3

20、=4 x1，x2，x3 0 max z=3x1 x2 2x3 3x1+2x2 3x3+x4 =6 Mx4x1 2x2 +x3 +x5 =4Mx5x1，x2，x3，x4，x5 0s.t.解解s.t.21第2章 单纯形法2.3 人工变量法人工变量法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 -M -M比比 值值 3 2 -3 1 0 x4x5 64 1 -2 1 0 1-M-M -10M -4M-3 1 2M+2 0 0243 2 1 2/3 -1 1/3 0 x1x5 0-M 2 0 -8/3 2 -1/3 16-2M 0 8M/3+3 -2M-1 4M/3+1 02 3-2 x

21、1x3 1 0 -4/3 1 -1/6 1/2 3 1 -2/3 0 1/6 1/2 7 0 5/3 0 M+5/6 M+1/2min X*=(3,0,1)T,z*=7 22第2章 单纯形法2.3 人工变量法人工变量法 两阶段法两阶段法 阶段阶段 求解求解人造极大问题人造极大问题 max w=-xn+1-xn+2-xn+m s.t.(2.1)(2.1)因为人工变量因为人工变量 xn+1,xn+2,xn+m 0 所以所以 max w 0(1)若若w*0，则原问题，则原问题无可行解无可行解，停止计算；，停止计算；(2)若若若若ww*=0*=0，且人工变量都不是基变量，则转入，且人工变量都不是基变量

22、，则转入阶段阶段：求解原问题求解原问题；23第2章 单纯形法2.3 人工变量法人工变量法(3)若若若若ww*=0 0，但，但“基列基列基列基列”存在人工变量，例如该列第存在人工变量，例如该列第l l 行的基变行的基变量量 xBl l是人工变量，同时该行的前是人工变量，同时该行的前n个系数个系数al l j全都是全都是0，这说明，这说明 原问题的该约束方程式多余的，那么删去第原问题的该约束方程式多余的，那么删去第l l 行及行及xBl l列，类列，类 似情况全都这样删去相应行、列；转入似情况全都这样删去相应行、列；转入阶段阶段；(4)若若若若ww*=0 0，且存在人工变量，且存在人工变量xBl

23、l是基变量，但该行的前是基变量，但该行的前n个系数个系数 中存在中存在al l k0，则以，则以al l k为主元进行一次换基运算，可使原变为主元进行一次换基运算，可使原变 量量xk取代人工变量取代人工变量xBl l作为基变量，类似可将这类人工变量全作为基变量，类似可将这类人工变量全 部都由基变量变为非基变量；转入部都由基变量变为非基变量；转入阶段阶段。24第2章 单纯形法 阶段阶段 求解求解原问题原问题原问题原问题 建立建立原问题原问题原问题原问题的的初始单纯形表初始单纯形表。只需把。只需把阶段阶段的的最末单纯形表最末单纯形表最末单纯形表最末单纯形表修改如下：修改如下：(1)删去人工变量删去

24、人工变量 xn+1，xn+2，xn+m诸列；诸列；(2)把把cj行与行与cj列的数字换成原问题目标函数的相应系数列的数字换成原问题目标函数的相应系数;(3)重新计算重新计算z0和和j，用以取代原检验行中相应数字。，用以取代原检验行中相应数字。然后用单纯形法进行迭代，直到运算结束。然后用单纯形法进行迭代，直到运算结束。2.3 人工变量法人工变量法s.t.3x1 +2x2 3x3+x4 =6x1 2x2 +x3 +x5 =4x1，x2，x3，x4，x5 0例例4 4max w=x4 x525第2章 单纯形法2.3 人工变量法人工变量法cj 基基 解解 x1 x2 x3 x4 x5 0 0 0 -1

25、 -1比比 值值 3 2 -3 1 0 x4x5 64 1 -2 1 0 1-1-1 -10 -4 0 2 0 0243 2 1 2/3 -1 1/3 0 x1x5 0-1 2 0 -8/3 2 -1/3 1-2 0 8/3 -2 4/3 02min 3-2 x1x3 0 0 -4/3 1 -1/6 1/2 0 1 -2/3 0 1/6 1/2 0 0 0 0 1 126第2章 单纯形法2.3 人工变量法人工变量法 阶段阶段：求解原问题：求解原问题 1 0 -4/3 1 3 1 -2/3 0 x1x3 X*=(3,0,1)T,z*=7 3 -1 -2 3-2 7 7 0 0 5/3 5/3 0

26、 0 x1 x2 x3cj基基解解27第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 进基变量进基变量进基变量进基变量的相持及其突破的相持及其突破 进基变量按最小检验数规则选定，如果出进基变量按最小检验数规则选定，如果出现两个或更多个现两个或更多个j0同时达到最小而相持时同时达到最小而相持时,则应：则应：从相持的检验数从相持的检验数k 所对应的变量所对应的变量 xk中中,任选一个任选一个作为进基量作为进基量。28第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 离基变量离基变量离基变量离基变量的相持及其突破的相持及其突破退化退化退化退化与与循环循环循环循环 cj 基基 解解 x1 x2 x3

27、 x4 x5 3 5 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 812 24 0 2 0 1 000 0 3 4 0 0 1 0 -3 -5 0 0 0-6 6min4 6 3/4 1 0 0 1/4x3x4 x2 00 5 0 -3/2 0 0 1 -1/2 8 1 0 1 0 1 30 3/4 0 0 0 5/4X*=(0,6,8,0,0)T,z*=30 29第2章 单纯形法 突破离基变量的相持突破离基变量的相持突破离基变量的相持突破离基变量的相持是一重要问题，关键在于是一重要问题，关键在于突破离基变量的相持必然导致一个突破离基变量的相持必然导致一个退化退化退化退化的基本可

28、行的基本可行解，这就有可能造成单纯形法的迭代步骤陷入一个解，这就有可能造成单纯形法的迭代步骤陷入一个周而复始的周而复始的循环循环循环循环过程。过程。避免避免循环循环循环循环的方法有：的方法有：摄动法摄动法；辞典序法辞典序法；布兰德法布兰德法根据根据摄动法摄动法，避免避免循环循环循环循环的的准则准则是：是：2.4 单纯形法补遗单纯形法补遗从相持的离基变量中，选择从相持的离基变量中，选择下标最大者下标最大者下标最大者下标最大者离基。离基。30第2章 单纯形法 定理定理定理定理1 1 1 1 多重最优解判别准则多重最优解判别准则多重最优解判别准则多重最优解判别准则 在在最优最优单纯形表单纯形表中中：

29、若有一个或更多个若有一个或更多个非基变量非基变量xj的检验数的检验数 j=0，则该问题有无穷则该问题有无穷多个最优解多个最优解；2.4 单纯形法补遗单纯形法补遗 多重最优解多重最优解每次都选一个这样的每次都选一个这样的 xj 进基进基，就能得到其它最优基本解就能得到其它最优基本解；若问题有若问题有r 个最优极点解个最优极点解Xi*，则该则该LPLP问题有无穷多个最优解，且问题有无穷多个最优解，且其中任一最优解其中任一最优解X*都能表示成这都能表示成这r 个最优极点解的凸组合：个最优极点解的凸组合：若该若该 xj在该表中的系数列向量在该表中的系数列向量 aj 0，则按单纯形法另作几次迭代，则按单

30、纯形法另作几次迭代，0 i 1，i =1,2,r,且且ui=1其中其中：X*=1X1*+2X2*+r Xr*31第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 cj 基基 解解 x1 x2 x3 x4 x5 3 4 0 0 0比比 值值 1 0 1 0 0 x3x4 x5 812 36 0 2 0 1 000 0 3 4 0 0 1 0 -3 -4 0 0 0-6 9min2 6 0 1 0 1/2 0 x3x2 x5 04 0 8 1 0 1 0 0 12 3 0 0 -2 1 24 -3 0 0 2 08-4 min332第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 cj 基基 解解

31、 x1 x2 x3 x4 x5 3 4 0 0 0比比 值值 4 0 0 1 2/3 -1/3 x3x2 x1 6 0 1 0 1/2 004 3 4 1 0 0 -2/3 1/3 36 0 0 0 0 0 16 12 -min2/3 3 0 1 -3/4 0 1/4x4x2 x1 04 3 6 0 0 3/2 1 -1/2 8 1 0 1 0 0 36 0 0 0 0 0 1X1*=(4,6)TX X2 2*=(8,3)T33第2章 单纯形法2.4 单纯形法补遗单纯形法补遗 X1*=(4,6)T,X2*=(8,3)T 0,1 X*=(8-4,3+3)T,0,1 8-4 3+34683X*=+(1-)=34第2章 单纯形法