运筹学02单纯形法.ppt

1、设线性规划的标准形式： max z=cjxj (1) s.t.aijxj=bi i=1,2,m (2) xj0 j=1,2,n (3) 可行域：由约束条件(2)、(3)所围成的区域； 可行解：满足(2)、(3)条件的解X=(x1，x2，xn)T为可行解； 基：设A是约束条件方程组的mn维系数矩阵,其秩为m，B是A中mm阶非奇异子矩阵，则称B为线性规划问题的一个基。 设,复习: 线性规划问题解的概念,基向量、非基向量、基变量、非基变量： 称pj(j=1,2,m）为基向量，其余称为非基向量； 与基向量pj(j=1,2,m）对应的xj称为基变量，其全体写成XB=（x1，x2，xm）T；否则称为非基变

2、量，其全体经常写成XN。 基解：对给定基B,设XB是对应于这个基的基变量 XB=(x1，x2，xm)T； 令非基变量xm+1=xm+2=xn=0， 由（2）式得出的解X=（x1，x2，xm，0，0）T 称为基解。 基可行解：所有决策变量满足非负条件(xj 0)的基解, 称作基可行解。 可行基：基可行解所对应的基底称为可行基。,写出下述线性规划问题对应的基、基变量、基解、基可行解和可行基。,定理2：X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X 对应于可行域D的顶点。） 定理3：若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优.,3

3、 单纯形法（Simplex Method）,例子：求解线性规划问题,线性规划问题的最优解，可以从基可行解中找到 图解法有局限性； 枚举法计算量大；,3.1 单纯形法的引入,解: 首先:将该问题化成标准形,第二: 找初始可行解(即一个顶点)。 系数矩阵 A=(p1 p2 p3 p4 p5),矩阵形式,因为p3 ，p4， p5 线性独立，故B=( p3 , p4, p5)构成一个基底，对应的基变量x3，x4， x5解出来为（用非基变量表示基变量） x3 =8- x1-2x2 x4 =16-4x1 (a) x5 =12- 4x2 将(a)代入目标函数中得 z=0+2x1+3x2 令非基底变量 x1=

4、x2=0，则有z=0。这时得到一个基可行解 X(0) =(0,0,8,16,12) T -原点,第三:判别 从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步,第四:换基底(旋转迭代) 确定换入变量：由于z=0+2x1+3x2 中非基底变量x2系数贡献最大3，故换入基底为x2。 换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4， x50。 x3 =8- 2x2 0 x4 =16 0 x5 =12- 4 x2 0 由此，只要选择 x2 =min (8/2，-，12/4)=3，对应基底变量x5 =0，从而确定用x2和x

5、5对调，即将x5 换出。有 x3 =2- x1+1/2x5 x4 =16-4x1 (b) x2 =3- 1/4 x5,将(b)代入目标函数中得 z=9+2x1-3/4x5 令非基变量为零，又得到另一个基可行解 X(1) =(0,3,2,16,0) T 顶点Q4,返回 第三步：非基变量x1的系数是正的，还可增大， X (1) 不是最优解。重复上述步骤。由于x1的系数是正的，从而x1为转入变量，再由 x3 =2- x1 0 x4 =16- 4 x1 0 x2 =3 0,只要选 x1=min2，16/4，-=2 上式就成立，因为x1= 2时，基变量x3=0，从而由x1换出x3，得 x1 =2- x3

6、 +1/2x5 4x1 +x4 =16 (c) x2 =3- 1/4 x5 高斯消去法（行变换）得,x1 =2- x3 +1/2x5 x4 =8-2 x5 +4 x3 x2 =3- 1/4 x5,代入目标函数中，得 z=13-2 x3 +1/4x5 令非基变量x3= x5=0，又得到另一个基可行解X(2) X(2) =(2,3,0,8,0) T 新顶点Q3 同理，返回第三步，再迭代，x5作为转入变量 x1 =2+1/2x5 0 x4 =8-2 x5 0 x2 =3- 1/4 x5 0,只要取 x5=min-，8/2，12=4 就有上式成立。 x5=4时， x4=0，故决定用x5换x4 x1 =

7、4- 1/4 x4 x5 =4-1/2 x4 +2 x3 x2 =2+1/8 x41/2 x3 代入得 z=14-3/2 x3 1/8 x4 ，令x3 ，x4=0得z=14。新基可行解为 X(3) =(4,2,0,0,4) T 为最优解，新顶点Q2 最优目标值z=14 。,从实际例子中分析单纯形法原理的基本框架为 第一步：将线性规划模型变换成标准型，确定一个初始可行解（顶点）。 第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。 第三步：从初始基可行解向相邻的基可行解（顶点）转 换，且使目标值有所改善目标函数值增加，重复第二和第三步直到找到最优解。,3.2 初始可行基的确定,设线性

8、规划问题：, 为了确定初始基可行解，首先要找出初始可行基，其方法如下：从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基,确定初始可行基的几种方法：, 形式的不等式 形式的不等式 =的情形 观察,“小加大减+人造”, 约束是形式的不等式，可以利用化标准型的方法，左端加一个松弛变量，经过整理，重新对xj及aij（i=1,2,m；j=1， 2，n）进行调整编号，则可得下列方程组,“小加”,x1 +a1,m+1xm+1+a1nxn=b1 x2 +a2,m+1xm+1+a2nxn=b2 xm +am,m+1xm+1+amnxn=bm xj0，j=1,2,n,显然得到一个mm单位矩阵,注意：a

9、ij和bi 已经变化,移项整理得 x1 = b1-a1,m+1xm+1-a1nxn x2 = b2a2,m+1xm+1-a2nxn xm = bmam,m+1xm+1-amnxn 令xm+1=xm+2=xn=0，可得 x i=bi （i=1，2，m） 又因bi0，所以得到一个初始基可行解： X（0）=（x1 x2 xm 0 0)T = (b1 b2 bm 0 0)T,非基向量可以用基向量的线性组合表示 将(3)式乘以一个正的数0,得到,记初始基可行解为X(0),有 该解满足约束方程, 即,3.3 从初始基可行解转换为另一基可行解,(4)式和(1)式相加,整理后得到 由(5)式可以找到满足约束方

10、程的另一个点X(1),其中是点X(1)的第j个坐标值,要使X(1)是一个基本可行解,则要求 并且这m个等式中至少要有一个等号成立 当 时,(6)式必然成立 当 时,令 因此有 所以X(1)中的正分量最多有m个,可证明m个向量P1, , Ps-1, Ps+1, ,Pm, Pj 线性无关,按照式(7)确定值, X(1)就是一个新的基可行解.,何时达最优解, 何种最优解？,3.4 最优性检验和判别定理,将基本可行解X(0)和X(1)分别代入目标函数得 由此 j称做检验数,是对线性规划问题的解进行最优性检验的标志.,最优解的判别定理：,且对一切的 j=m+1,.,n有,则X(0) 为最优解。,若 是一

11、个基可行解，,无穷多最优解判别定理：,若 是一个基可行解，,且对一切的 j=m+1,.,n 有,又存在某个非基变量的检验数 则线性规划问题有无穷多最优解。,无界解的判别定理：,3.5 基变换 换入变量的确定: max(j0)= k, j=m+1,n; xk是换入变量(也可任选). 换出变量的确定: 确定换出变量的原则是保持解的可行性,就是说要使原基可行解的某一正分量xs变成零,同时保持其它的分量均非负(换基原则) min(xi/aij|aij0)= xs/asj=, s1,2,m (最小比值准则,或准则),3.6 旋转运算 在确定换入变量xk和换出变量xs以后，要把xk所对应的系数列向量pk变

12、成单位向量，为此,只要对系数矩阵的增广阵进行“行”的初等变换即可。行变换的定义：,(第s行)*1/ask得: 当is时,(第i行)-(第s行)*aik,经过初等变换后,新的增广矩阵是,4 单纯形法的计算步骤和单纯形表 约束方程组和目标函数组成 n+1个变量,m+1个方程的方程组,该方程组对应的增广矩阵是,确定初始单纯形表后可以得到初始基可行解x0, 若有某个非基底变量xk对应的检验数k=(ck-zk)0,则当前解不是最优解，取使目标增长最大的非基底变量进入基底。 根据 确定xk为换入变量 根据 确定xs为换出变量 将xk对应的列向量Pk=(a1k,ask,ank)T变换为 aik=0，i s

13、aik=1，i=s 重复上述步骤直到所有的检验数满足最优条件，得最优解。,5 单纯形法的进一步讨论,人工变量法（确定初始可行基）：,原约束方程：AX=b,加入人工变量：xn+1，xn+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。,1、大M法 方法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。,理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。,例1：用大M法求解如

14、下线性规划问题,cj,最优解是,目标函数为-2。,2、两阶段法 第一阶段： 建立一个辅助线性规划并求解，以此判断原线性规划是否存在可行解。 辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准型的约束条件。 所有人工变量都变成非基变量，目标函数值为0，原问题存在基可行解。转到第二阶段。 若目标函数值不为0，至少有一个人工变量不能从基变量中转出，原问题没有可行解。停止。 第二阶段： 从第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，用单纯形法计算，直到得到最优解为止。,第一阶段：求解辅助规划问题,cj,x6，x7是人工变量，第一阶段求解的最优结果是=0，因此得最优解为：,第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。,最优解为：,最优值为： z= -2,两阶段法：辅助规划； 去掉人工变量，单纯形法。,对目标函数求max的线性规划问题,用单纯形法计算