《管理运筹学》课件02-单纯形法.ppt
第2章 单纯形法,1,第二章 单纯形法,Simplex Method,SM,第2章 单纯形法,2,2.1 单纯形法的基本思想2.2 单纯形法的计算过程2.3 人工变量法2.4 单纯形法补遗,第2章 单纯形法,第2章 单纯形法,3,2.1 单纯形法的基本思想,单纯形法有三种形式：方程组形式 表格形式 矩阵形式2.1.1 方程组形式的单纯形法思路：由一个基本可行解转化为另一个基本可行解。,z-3x1-5x2=0,例1 范例,等价改写为,目标方程,第2章 单纯形法,4,2.1 单纯形法的基本思想,0 00 1 00 0 1,典式,条 典,当前基：m阶排列阵 目标方程中：一切基变量 的系数 j=0,最优性检验：,一切j 0？,初始基本可行解 X0=(0,0,8,12,36)T z0=0,排列阵：每行每列有且仅有一个元素为1，其余元素全为0 的方阵。,1=-3 0,2=-5 0,当前解 X0 非优；,+0 x3+0 x4+0 x5,须由X0 转化为另一个基本可行解 X1。,满足条典的方程组称为典式(方程组)。,思路：让X0 中的一个非基变量进基，去替换原来的一个基变量（离基）。,第2章 单纯形法,5,2.1 单纯形法的基本思想,x1仍为非基变量，其值为0。,x2 12/2 x2 36/4,离基（最小比值规则）：x2 min，12/2，36/4=6 x2=min，12/2，36/4=6,x4,x4为离基变量,进基（最小检验数规则）：在负检验数中选择最小的进基。min jj0=k xk 进基 min-3，-5=-5=2 x2 进基,0,0,0,=,=12,X1=,(,12,0,6,8,0,)T,由 有,第2章 单纯形法,6,2.1 单纯形法的基本思想,主方程,0,主列,主元,z-3x1-5 x2=0,x1+x3=8,2 x2+x4=12,3x1+4 x2+x5=36,(),-69,比值,min,以主列中正值元素为分母，同行右端常数为分子，求比值；,按最小比值规则确定主方程和主元素，以及离基变量。,第2章 单纯形法,7,X0=(0,0,8,12,36)T z0=0,(),x1+x3=8,3x1-2x4+x5=12,得,X1=,z0=30,称为单纯形法的一次迭代。,(,12,0,6,8,0,)T,换基运算方程组的初等变换目的是把主列变为单位向量：主元变为1，其余变为0。,用换基运算将X0 转化为另一个基本可行解 X1。,0010,2.1 单纯形法的基本思想,第2章 单纯形法,8,2.1 单纯形法的基本思想,(),(),x1+x3=8,3 x1-2x4+x5=12,得,X*=(4,6,4,0,0)T,z*=42,8-4,min,比值,10,第2章 单纯形法,9,2.1 单纯形法的基本思想,2.1.2 单纯形法的几何意义,z=0,脊线,(4,6,4,0,0)T,(0,0,8,12,36)T,(0,6,8,0,12)T,z 法向,或棱线,第2章 单纯形法,10,单纯形表范例:基于典式标准形,cj,基,解,x1 x2 x3 x4 x5,3 5 0 0 0,比 值,1 0 1 0 0,x3x4 x5,81236,0 2 0 1 0,00 0,3 4 0 0 1,0 0 0,0,-3,-5,检验行,CB,b,3,5,2.2 单纯形法的计算过程,检验行计算公式,j=1,2,n,第2章 单纯形法,11,2.2 单纯形法的计算过程,初始单纯形表的一般形式,第2章 单纯形法,12,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。,预备步骤,迭代步骤,第2章 单纯形法,13,2.2 单纯形法的计算过程,5 确定主元 先按最小检验数规则 min jj 0=k 确定进基变量 xk 和主列ak；再按最小比值规则,确定主元al k,同时也就确定第l 行的基变量 xr 离基。6 以al k为主元对当前表格进行一次换基运算，得到 一个新单纯形表，返3。,迭代步骤,第2章 单纯形法,14,2.2 单纯形法的计算过程,2.2.3 单纯形法计算之例范例 第0次迭代,-6 9,min,2,第2章 单纯形法,15,2.2 单纯形法的计算过程,第一次迭代,x3x2 x5,05 0,1/2,8 1 0 1 0 0,-2,5/2,4,min,1,6,0,0,0,12,3,0,0,1,30,-3,0,0,0,8,-,第2章 单纯形法,16,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 0,05 0,3 0 0-2 1,30-3 0 0 5/2 0,x3x2 x1,05 3,6 0 1 0 1/2 0,4 0 0 1 2/3-1/3,4 1 0 0-2/3 1/3,42 0 0 0 1/2 1,8-4,min,3,X*=(4,6,4,0,0)T,z*=42,第二次迭代,第2章 单纯形法,17,2.2 单纯形法的计算过程,cj,基,解,x1 x2 x3 x4,3 2 0 0,-2 1 1 0,x3x4,23,1-3 0 1,00,0-3-2 0 0,1,3 1-3 0 1,x3x1,03,8 0-5 1 2,9 0-11 0 3,解无界,例2 求解下述LP问题,第2章 单纯形法,18,2.3 人工变量法,考虑标准型(M)：分别给每个约束方程硬性加入一个非负变量 a11x1+a12x2+a1nxn+xn+1=b1(0)a12x1+a22x2+a2nxn+xn+2=b2(0)am1x1+am2x2+amnxn+xn+m=bm(0),n个,xn+1,xn+2,xn+m 称为人工变量。初始基本可行解：(人造基本解)X0=(0,0,0,b1,b2,bm)T,(2.1),第2章 单纯形法,19,基本思想：人造解 X0 不是原LP问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即 人工变量xn+1=xn+2=xn+m=0），则X0的 前n个分量就构成原LP问题的一个基本可行解。反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原LP问题无可行解。,2.3 人工变量法,第2章 单纯形法,20,2.3 人工变量法,大M法 在原问题的目标函数中添上全部人工变量，并令其系数 都为-M，而M是一个充分大的正数。即 max z=c1x1+c2x2+c3x3+cnxn M(xn+1+xn+2+xn+m)由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系数的人工变量从基变量中替换出去。,若迭代最终得到最优解X*，而且基变量中不含有人工变量，则X*的前n个分量就构成原问题的一个最优基本解；否则，原问题无可行解。若迭代结果是解无界，而且基变量中不含有人工变量，则原问题也解无界；否则，原问题无可行解。,第2章 单纯形法,21,2.3 人工变量法,例3 用大M法求解下述LP问题 max z=3x1 x2 2x3 3x1+2x2 3x3=6 x1 2x2+x3=4 x1，x2，x3 0,max z=3x1 x2 2x3,3x1+2x2 3x3+x4=6,Mx4,x1 2x2+x3+x5=4,Mx5,x1，x2，x3，x4，x5 0,s.t.,解,s.t.,第2章 单纯形法,22,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 0,24,3,2 1 2/3-1 1/3 0,x1x5,0-M,2 0-8/3 2-1/3 1,6-2M 0 8M/3+3-2M-1 4M/3+1 0,2,3-2,x1x3,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/2,min,X*=(3,0,1)T,z*=7,第2章 单纯形法,23,2.3 人工变量法,两阶段法 阶段 求解人造极大问题 max w=-xn+1-xn+2-xn+m s.t.(2.1)因为人工变量 xn+1,xn+2,xn+m 0 所以 max w 0,(1)若w*0，则原问题无可行解，停止计算；(2)若w*=0，且人工变量都不是基变量，则转入阶段：求解原问题；,第2章 单纯形法,24,2.3 人工变量法,(3)若w*=0，但“基列”存在人工变量，例如该列第l 行的基变量 xBl是人工变量，同时该行的前n个系数al j全都是0，这说明 原问题的该约束方程式多余的，那么删去第l 行及xBl列，类 似情况全都这样删去相应行、列；转入阶段；(4)若w*=0，且存在人工变量xBl是基变量，但该行的前n个系数 中存在al k0，则以al k为主元进行一次换基运算，可使原变 量xk取代人工变量xBl作为基变量，类似可将这类人工变量全 部都由基变量变为非基变量；转入阶段。,第2章 单纯形法,25,阶段 求解原问题 建立原问题的初始单纯形表。只需把阶段的最末单纯形表修改如下：(1)删去人工变量 xn+1，xn+2，xn+m诸列；(2)把cj行与cj列的数字换成原问题目标函数的相应系数;(3)重新计算z0和j，用以取代原检验行中相应数字。然后用单纯形法进行迭代，直到运算结束。,2.3 人工变量法,s.t.,3x1+2x2 3x3+x4=6,x1 2x2+x3+x5=4,x1，x2，x3，x4，x5 0,例4,max w=x4,x5,第2章 单纯形法,26,2.3 人工变量法,cj,基,解,x1 x2 x3 x4 x5,0 0 0-1-1,比 值,3 2-3 1 0,x4x5,64,1-2 1 0 1,-1-1,-10-4 0 2 0 0,24,3,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 0,2,min,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 1,第2章 单纯形法,27,2.3 人工变量法,阶段：求解原问题,X*=(3,0,1)T,z*=7,3-1-2,3-2,7 0 5/3 0,第2章 单纯形法,28,2.4 单纯形法补遗,进基变量的相持及其突破,进基变量按最小检验数规则选定，如果出现两个或更多个j0同时达到最小而相持时,则应：,从相持的检验数k 所对应的变量 xk中,任选一个作为进基量。,第2章 单纯形法,29,2.4 单纯形法补遗,离基变量的相持及其突破退化与循环,6 3/4 1 0 0 1/4,x3x4 x2,00 5,0-3/2 0 0 1-1/2,8 1 0 1 0 1,30 3/4 0 0 0 5/4,X*=(0,6,8,0,0)T,z*=30,第2章 单纯形法,30,突破离基变量的相持是一重要问题，关键在于突破离基变量的相持必然导致一个退化的基本可行解，这就有可能造成单纯形法的迭代步骤陷入一个周而复始的循环过程。避免循环的方法有：摄动法；辞典序法；布兰德法根据摄动法，避免循环的准则是：,2.4 单纯形法补遗,从相持的离基变量中，选择下标最大者离基。,第2章 单纯形法,31,定理1 多重最优解判别准则 在最优单纯形表中：若有一个或更多个非基变量xj的检验数j=0，则该问题有无穷多个最优解；,2.4 单纯形法补遗,多重最优解,每次都选一个这样的 xj 进基，就能得到其它最优基本解；若问题有r 个最优极点解Xi*，则该LP问题有无穷多个最优解，且其中任一最优解X*都能表示成这r 个最优极点解的凸组合：,0 i 1，i=1,2,r,且ui=1,其中：,X*=1X1*+2X2*+r Xr*,第2章 单纯形法,32,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 0,00 0,3 4 0 0 1,0-3-4 0 0 0,-6 9,min,2,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 0,8-4,min,3,第2章 单纯形法,33,2.4 单纯形法补遗,cj,基,解,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 0,04 3,4 1 0 0-2/3 1/3,36 0 0 0 0 1,6 12-,min,2/3,3 0 1-3/4 0 1/4,x4x2 x1,04 3,6 0 0 3/2 1-1/2,8 1 0 1 0 0,36 0 0 0 0 1,X1*=(4,6)T,X2*=(8,3)T,第2章 单纯形法,34,2.4 单纯形法补遗,X1*=(4,6)T,X2*=(8,3)T,0,1,X*=(8-4,3+3)T,0,1,
