第四讲：单纯形法ZY

第二节单纯形法SimplexMethod2.1单纯形法的基本思想2.2单纯形法的代数形式2.3单纯形法的表格形式2.4单纯形法补遗2.5单纯形法的矩阵形式2.6人工变量法第2章单纯形法22.1.1单纯形法的几何意义第2章单纯形法3D(0,6)O(0,0)C(4,6)B(8,3)A(8,0)x1x2z=0角点（CP）z法向角（顶）点可行解（CPF）D(0,9)F(12,0)G(8,6)最优解性质1：顶点可行解与最优解的关系◦若线性规划问题的可行域有界，则至少有一个顶点可行解和最优解，而且最优的顶点可行解一定是最优解。若一个线性规划问题有唯一最优解，则最优解一定是顶点可行解；若有多重最优解，则其中至少有两个最优解是顶点可行解。性质2：最优性检验◦若线性规划问题至少有一个最优解，那么对于当前的顶点可行解来说，如果与它相邻的顶点可行解都不比它更好（以Z衡量），则该顶点可行解是最优解。第2章单纯形法4NO找到相邻的CPF解最优性检验当前的CPF是最优解吗？开始找到初始的CPF解第2章单纯形法5YES停止Q1：初始基本可行解如何找？◦标准型◦基本解Q2：怎样判断最优？◦最优性条件Q3：如何找下一个相邻的基本可行解？◦确定移动的方向◦确定在何处停下◦确定新的基本可行解第2章单纯形法6第1章线性规划的基本性质7maxz=c1x1+c2x2+c3x3+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1(≥0)a21x1+a22x2+…+a2nxn=b2(≥0)………am1x1+am2x2+…+amnxn=bm(≥0)x1,x2,…,xn≥0简记为：maxz=∑cjxjj=1ns.t.∑aijxj=bi,i=1,2,…,mj=1nxj≥0,j=1,2,…,nmaxz=CTXs.t.AX=bX≥0(M1):(M2):(M3):标准型有什么特点？目标函数最大化约束条件是等式右端常数非负数决策变量要非负第2章单纯形法8第1章线性规划的基本性质9非标准形LP问题的标准化一、目标函数minz=CTX令z′=－zmaxz′=－CTX例：minz=3x1＋2x2maxz′=－3x1－2x2二、函数约束⑴bi0两边同时乘以-1⑵约束为≤形式加上松弛变量⑶约束为≥形式减去剩余变量三、决策变量若xk≤0,令xk=－xk′,则xk′≥0若xk为自由变量,令xk=xk′－xk〞且xk′,xk〞≥0•xx*f(x)-f(x)第1章线性规划的基本性质10z=3x1+5x2maxx1≤82x2≤123x1+4x2≤36x1，x2≥0s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1，x2，x3，x4，x5≥0s.t.z=3x1+5x2max例2-1+0x3+0x4+0x5第1章线性规划的基本性质11minz=x1＋2x2－3x3x1＋2x2－x3≤52x1＋3x2－x3≥6－x1－x2＋x3≥－2x1≥0,x3≤0s.t.解:maxz′=－x1－2x2＋3x3s.t.x1＋2x2－x3+x4=52x1＋3x2－x3-x5=6x1＋x2－x3+x6=2x1,x4,x5,x6≥0,x3≤0将下述LP问题化成标准形例2-2第1章线性规划的基本性质12令x2=x2′－x2〞，且x2′，x2〞≥0x3=-x3′代入上式中，得maxz′=－x1－2x2′+2x2〞－3x3′x1+2x2′－2x2〞+x3′+x4=52x1+3x2′－3x2〞+x3′－x5=6x1+x2′－x2〞+x3′+x6=2x1,x2′,x2〞,x3′,x4,x5,x6≥0s.t.将以下线性规划问题转化为标准形式0,453232..32min31321321321321xxxxxxxxxxxtsxxxz0,,,'',',4'''5'''3232'''..''3'32'max543221322153221432213221xxxxxxxxxxxxxxxxxxxxtsxxxxz解：设z=-z,x2=x2-x2,x20,x20,x40,x50,则有1.凸集与顶点的概念设S是n维空间中的一个点集。若对任意n维向量X1∈S,X2∈S，且X1≠X2，以及任意实数（0≤λ≤1），有X=λX1+(1-λ)X2∈S则称S为n维空间中的一个凸集（ConvexSet）。点X称为点X1和X2的凸组合。几何意义:凸集S中的任意两个不相同的点连线上的点（包括这两个端点），都位于S之中。1.线性规划的解的概念可行解:满足LP问题所有约束条件的解。可行解的集合称为可行域。最优解:使目标函数达到最优的可行解。基本解:只适用于标准形LP问题（M）。扩展解：原始变量取值加上松弛（剩余变量）取值后形成的解。基本解是一个扩展后的顶点解。基本可行解是扩展的顶点可行解。第1章线性规划的基本性质152.基本解基本解的来源：◦代数形式：（范例）变量个数—方程个数=5-3=2（自由度）方程组联立求解，3个变量值，另外两个变量任意取值。单纯形法将这两个任意值设为0，作为非基变量.3个有值的变量称为基变量。◦矩阵形式：对于线性规划的约束条件AX=b，X≥0设B是A矩阵中的一个非奇异的m×m子矩阵，则称B为线性规划的一个基。与B的列向量所对应的变量叫做基变量，除基变量之外的变量称为非基变量。基本解的性质每个变量都可以作为基变量或者非基变量。基变量的个数=约束条件数（m）非基变量个数=变量数（n）-约束条件数（m）非基变量的值设为0，基变量的值是方程组的解。如果基变量满足非负约束，则称为基本可行解。第2章单纯形法16第1章线性规划的基本性质17范例A=101000201034001x1x2x3x4x5a1a2a3a4a5令x1,x2为0,则称x3,x4,x5为基变量，而x1,x2为非基变量。其中B0=（a3,a4,a5）为基（|B0|≠0）,称a3,a4,a5为基向量，而a1,a2为非基向量；(2)基本解范例的标准形第1章线性规划的基本性质18maxz=3x1+5x2s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0取B0=（a3,a4,a5）（系数矩阵）为基，令非基变量x1=x2=0,可解得基变量x3=8，x4=12，x5=36则得一特解X0=(0，0，8，12，36)T称为一个(关于B0为基的)基本解。也可取B1=(a2,a3,a4)为基,令非基变量x1=x5=0得X1=(0，9，8，-6，0)T还可取B2=(a1,a2,a3)为基,令非基变量x4=x5=0得X2=(4，6，4，0，0)T等等。退化的基本可行解基本(可行)解：满足非负性约束的基本解。如X0，X2；而X1不可行。对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为0，则称其为一个退化的基本(可行)解，否则为非退化的。如设：X=(0，6，5，0，0)T是一个基本可行解，其中x5=0为基变量，则该X为退化的基本可行解。相邻的基本可行解当非基变量只有一个不同时，两个基本解是相邻的。有一个变量从基变量变为非基变量，另一个变量从非基变量变为基变量，其他变量的属性不变，但是数值可能改变。第1章线性规划的基本性质19非退化的基本(可行)解，有m个非0分量基变量有n–m个0分量非基变量第1章线性规划的基本性质20基本可行解对应的基，称为可行基；最优基本解对应的基，称为最优基。如：基B0=(a2,a3,a4)对应X0=(0，0，8，12，36)T可行基B1=(a2,a3,a4)对应X1=(0，9，8，-6，0)T不可行基B2=(a1,a2,a3)对应X2=(4，6，4，0，0)T为可行基为非可行基为最优基x*x*B*选择原点：◦令决策变量x1=x2=0得：X0=(0，0，8，12，36)T选择单元阵作为初始基：令非基变量x1=x2=0得：X0=(0，0，8，12，36)T第2章单纯形法21123451010002010(,,,,)34001Aaaaaa345100010(,,)001Baaa非最优：增加非基变量的值，可以使得目标函数Z值增加◦基变量在目标函数中的系数为0◦非基变量在目标函数中的系数≤0.（注意：目标函数形式z=3x1+5x2）◦若目标函数为方程形式：z-3x1-5x2=0，则需非基变量的系数≥0第2章单纯形法22检验数迭代步骤1：确定移动的方向例：z=3x1+5x2◦选择x1？Z的增长率=3◦选择x2？Z的增长率=5◦5＞3，选择x2！入基变量的选择：◦选择非基变量的系数最大的！第2章单纯形法23确定入基变量检验数的绝对值哦~~~迭代步骤2：确定在何处停下◦增加x2的值，x1=0◦所有变量非负令x2=6，从而x4=0出基变量的选择：◦最小比值法第2章单纯形法24确定出基变量133244212552882+=121223+4+=36364xxxxxxxxxxxx32422522812122=6236364=94xxxxxxxx无限制最小比值法迭代步骤3：确定新的基本可行解原方程寻找新的基本可行解：◦初等数学变换第2章单纯形法25121324125(0)3-5=0(1)8(2)2+=12(3)3+4+=36Zxxxxxxxxx初等数学变换初始BF解新的BF解非基变量（Non-basics）x1=0，x2=0x1=0，x4=0基变量（Basics）x3=8，x4=12，x5=36x3=？，x2=6，x5=？1413241455(0)3+=302(1)81(2)+=62(3)3-2+=12Zxxxxxxxxx812X*=（0,6,8,0,12）Z*=30新方程第2章单纯形法26单纯形法有三种形式：①方程组形式②表格形式③矩阵形式2.3.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+x5=36x1，x2，x3，x4，x5≥0maxz目标方程第2章单纯形法27100010001典式条典⑴当前基：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=-30σ2=-50当前解X0非优；+0x3+0x4+0x5须由X0转化为另一个基本可行解X1。满足条典的方程组称为典式(方程组)。思路：让X0中的一个非基变量进基，去替换原来的一个基变量（离基）。第2章单纯形法28x1仍为非基变量，其值为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︱σj0}=σk→xk进基min{-3，-5}=-5=σ2→x2进基≥0≥0≥0==12X1=(120,6,8,0,)Tz-3x1-5x2=0x1+x3=8①2x2+x4=12②3x1+4x2+x5=36③(Ⅰ)0由①②③有第2章单纯形法29主方程0主列进基主元z-3x1-5x2=0x1+x3=82x2+x4=123x1+4x2+x5=36(Ⅰ)-69比值min离基以主列中正值元素为分母，同行右端常数为分子，求比值；按最小比值规则确定主方程和主元素，以及离基变量。第2章单纯形法30