(精品)运筹学02单纯形法.ppt

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

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为线性规划问题的一个基。设复习复习:线性规划问题解的概念线性规划问题解的概念B=(p1,p2,pm)a11 a12 a1m a21 a22 a2m am1 am2 amm基向量、非基向量、基变量、非基变量：称pj(j=1,2,m）为基向量，其余称为非基向量；与基向量pj(

2、j=1,2,m）对应的xj称为基变量，其全体写成XB=（x1，x2，xm）T；否则称为非基变量，其全体经常写成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 对应于可行域对

3、应于可行域D的顶点。）的顶点。）定定理理3：若若可可行行域域有有界界,线线性性规规划划问问题题的的目目标标函函数数一一定可以在其可行域的顶点上达到最优定可以在其可行域的顶点上达到最优.3 单纯形法（单纯形法（Simplex Method）例子：例子：求解线性规划问题 线性规划问题的最优解，可以从基可行解中找到 图解法有局限性；枚举法计算量大；3.1 单纯形法的引入单纯形法的引入0Q4Q31123234Q2Q1X1X2x1+2x2=84x1=164x2=12解:首先首先:将该问题化成标准形第二第二:找初始可行解(即一个顶点)。系数矩阵 A=(p1 p2 p3 p4 p5)矩阵形式 因为p3，p4

4、，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=x2=0，则有z=0。这时得到一个基可行解X(0)=(0,0,8,16,12)T-原点第三第三:判别 从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步第四第四:换基底(旋转迭代)确定换入变量：由于z=0+2x1+3x2 中非基底变量x2系数贡献最大3，故换入基底为x2。换入变量已定，必须从x

5、3，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和x5对调，即将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的系数是正的，从而

6、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+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/2

7、x5 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 =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。从实际例子中分析单纯形法原理的基本框架为第一步：将线性规划模型变换成标准型，确定一个初始可行解（顶点）。第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。第三步：从初

8、始基可行解向相邻的基可行解（顶点）转 换，且使目标值有所改善目标函数值增加，重复第二和第三步直到找到最优解。3.2 初始可行基的确定初始可行基的确定 设线性规划问题：为了确定初始基可行解，首先要找出初始可行基，其方法如下：从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+1

9、xm+1+a2nxn=b2 xm +am,m+1xm+1+amnxn=bm xj0，j=1,2,n显然得到一个mm单位矩阵注意：aij和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 从

10、初始基可行解转换为另一基可行解从初始基可行解转换为另一基可行解(4)式和(1)式相加,整理后得到由(5)式可以找到满足约束方程的另一个点X(1),其中是点X(1)的第j个坐标值要使X(1)是一个基本可行解,则要求并且这m个等式中至少要有一个等号成立当 时,(6)式必然成立当 时,令因此有所以X(1)中的正分量最多有m个,可证明m个向量P1,Ps-1,Ps+1,Pm,Pj 线性无关,按照式(7)确定值,X(1)就是一个新的基可行解.线性规划解的四种可能：1、有唯一解；2、无穷多最优解；3、无界解；4、无可行解。何时达最优解,何种最优解？3.4 最优性检验和判别定理最优性检验和判别定理将基本可行解

11、X(0)和X(1)分别代入目标函数得由此j称做检验数,是对线性规划问题的解进行最优性检验的标志.最优解的判别定理最优解的判别定理：且对一切的 j=m+1,.,n有则X(0)为最优解。若 是一个基可行解，无穷多最优解判别定理无穷多最优解判别定理：若 是一个基可行解，且对一切的 j=m+1,.,n 有又存在某个非基变量的检验数 则线性规划问题有无穷多最优解。无界解的判别定理无界解的判别定理：3.5 基变换基变换换入变量的确定:max(j0)=k,j=m+1,n;xk是换入变量(也可任选).换出变量的确定:确定换出变量的原则是保持解的可行性,就是说要使原基可行解的某一正分量xs变成零,同时保持其它的

12、分量均非负(换基原则)min(xi/aij|aij0)=xs/asj=,s1,2,m(最小比值准则,或准则)3.6 旋转运算旋转运算 在确定换入变量xk和换出变量xs以后，要把xk所对应的系数列向量pk变成单位向量，为此,只要对系数矩阵的增广阵进行“行”的初等变换即可。行变换的定义：(第s行)*1/ask得:当is时,(第i行)-(第s行)*aik经过初等变换后,新的增广矩阵是4 单纯形法的计算步骤和单纯形表单纯形法的计算步骤和单纯形表约束方程组和目标函数组成 n+1个变量,m+1个方程的方程组该方程组对应的增广矩阵是5 单纯形法的进一步讨论单纯形法的进一步讨论 人工变量法（确定初始可行基）：

13、原约束方程：AX=b加入人工变量：xn+1，xn+m 人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。1、大M法方方法法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。理理由由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。例1：用大M法求解如下线性规划问题11 1 -2 1 1 0 0 0 113 -4 1 2 0 -1 1 0 3/21 -2 0 1 0 0 0 1 10

14、 M 1 6xx4 x310 3 -2 0 1 0 0 -11 0 1 0 0 -1 1 -2 1 1 -2 0 1 0 0 0 1 -3 x1 1 x2 1 x3 4 1 0 0 1/3 -2/3 2/3 -5/3 1 0 1 0 0 -1 1 -2 9 0 0 1 0 2/3 4/3 -7/3 -3 1 1 0 0 M M -1 0 0 0 1 M-1 M+1 zj-cj 0 0 0 1/3 1/3 0 0 0 1/3 1/3 M-1/3-1/3 M-2/3-2/3 zj-cj 0 x4 1 x2 1 x3 12 3 0 0 1 -2 2 -5 4 1 0 1 0 0 -1 1 -2 1

15、-2 0 1 0 0 0 1cj0MMX4X6X7 b CBXBX1X2X3X4X5X6X7i -3+6M 1-M 1-3M 0 M 0 0cj-zj-1 1-M 0 0 M 0 3M-1cj-zj最优解是目标函数为-2。2、两阶段法第一阶段：第一阶段：建立一个辅助线性规划并求解，以此判断原线性规划是否存在可行解。辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准型的约束条件。所有人工变量都变成非基变量，目标函数值为0，原问题存在基可行解。转到第二阶段。若目标函数值不为0，至少有一个人工变量不能从基变量中转出，原问题没有可行

16、解。停止。第二阶段：第二阶段：从第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，用单纯形法计算，直到得到最优解为止。第一阶段：求解辅助规划问题 11 1 -2 1 1 0 0 0 113 -4 1 2 0 -1 1 0 3/21 -2 0 1 0 0 0 1 10 1 0 6xx4 x310 3 -2 0 1 0 0 -11 0 1 0 0 -1 1 -2 1 1 -2 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 zj-cj 0 x4 0 x2 0 x3 12 3 0 0 1 -2 2 -5 4 1 0 1 0 0 -1 1 -2 1

17、 -2 0 1 0 0 0 0cj0 1 1X4X6X7 b CBXBX1X2X3X4X5X6X7i 6 -1 -3 0 1 0 0cj-zj 0 -1 0 0 1 0 3cj-zj12 3 0 0 1 -2 41 0 1 0 0 -11 -2 0 1 0 0-3 1 1 2xx1 x3 4 1 0 0 1/3 -2/31 0 1 0 0 -1 9 0 0 1 2/3 -4/3 -3 1 1 0 0 cj0 1 1X4X2X3 b CBXBX1X2X3X4X5i -1 0 0 0 1cj-zj 0 0 0 1/3 1/3cj-zjx6，x7是人工变量，第一阶段求解的最优结果是=0，因此得最优解

18、为：第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。最优解为：最优值为：z=-2两阶段法：辅助规划；去掉人工变量，单纯形法。对目标函数求max的线性规划问题,用单纯形法计算步骤的框图唯一最优解唯一最优解 N NN YYY添添加加松松弛弛变变量量、人人工工变变量量,列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量对应的检验数对应的检验数 j所有所有 j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基某非基变量检变量检验数为验数为零零无可行解无可行解无穷多最优解无穷多最优解对某对某 j 0有有aij0无界解无界解令令 k=max j对对 所所 有有 aik0计计 算算 i=bi/aik令令 s=min ixs为换出变量为换出变量ask为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换基变量替换基变量xs;.对主元素行对主元素行(第第s行行)，令，令 bs/askbs;asj/askasj.对主元素列对主元素列(第第k列列)，令，令1ask；0其它元素其它元素 表中其它行列元素表中其它行列元素 令令 aij-asj/askaikaij bi-bs/askaikbiYN