运筹学单纯形法.ppt

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

1、关于运筹学单纯形法现在学习的是第1页，共48页基向量、非基向量、基变量、非基变量：称pj(j=1,2,m）为基向量，其余称为非基向量；与基向量pj(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页，共48页定定理理2：X是是

2、线线性性规规划划问问题题的的基基可可行行解解的的充充要要条条件件是是它它对对应应于于可可行行域域D的的顶顶点点。（线线性性规规划划问问题题的的基基可可行解行解X 对应于可行域对应于可行域D的顶点。）的顶点。）定定理理3：若若可可行行域域有有界界,线线性性规规划划问问题题的的目目标标函函数数一一定可以在其可行域的顶点上达到最优定可以在其可行域的顶点上达到最优.现在学习的是第4页，共48页3 单纯形法（单纯形法（Simplex Method）例子：例子：求解线性规划问题 线性规划问题的最优解，可以从基可行解中找到 图解法有局限性；枚举法计算量大；3.1 单纯形法的引入单纯形法的引入0Q4Q3112

3、3234Q2Q1X1X2x1+2x2=84x1=164x2=12现在学习的是第5页，共48页解:首先首先:将该问题化成标准形第二第二:找初始可行解(即一个顶点)。系数矩阵 A=(p1 p2 p3 p4 p5)矩阵形式现在学习的是第6页，共48页 因为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=x2=0，则有z=0。这时得到一个基可行解X(0)=(0,0,8,16,12)

4、T-原点第三第三:判别 从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步现在学习的是第7页，共48页第四第四:换基底(旋转迭代)确定换入变量：由于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和x5对调，即将x5 换出。有 x3 =2-x1+1/2x5 x4 =16-

5、4x1 (b)x2 =3-1/4 x5 现在学习的是第8页，共48页 将(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 现在学习的是第9页，共48页只要选 x1=min2，16/4，-=2上式就成立，因为x1=2时，基变量x3=0，从而由x1换出x3，得 x1 =2-x3+1/2x5 4x1 +x4=16 (c)x2

6、 =3-1/4 x5高斯消去法（行变换）得 x1 =2-x3+1/2x5 x4 =8-2 x5+4 x3 x2 =3-1/4 x5 现在学习的是第10页，共48页代入目标函数中，得 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 现在学习的是第11页，共48页只要取x5=min-，8/2，12=4就有上式成立。x5=4时，x4=0，故决定用x5换x4 x1 =4-1/4 x4 x5=4

7、-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。现在学习的是第12页，共48页从实际例子中分析单纯形法原理的基本框架为第一步：将线性规划模型变换成标准型，确定一个初始可行解（顶点）。第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。第三步：从初始基可行解向相邻的基可行解（顶点）转 换，且使目标值有所改善目标函数值增加，重复第二和第三步直到找到最优解。现在学习的是第13页，共48页3.2 初始可行基的确定初

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

9、m,m+1xm+1+amnxn=bm xj0，j=1,2,n显然得到一个mm单位矩阵注意：aij和bi已经变化现在学习的是第17页，共48页移项整理得 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现在学习的是第18页，共48页非基向量可以用基向量的线性组合表示将(3)式乘以一个正的数0,得到记初始基可行解为X(0),有该解满足约

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

11、3、无界解；4、无可行解。何时达最优解,何种最优解？3.4 最优性检验和判别定理最优性检验和判别定理现在学习的是第22页，共48页将基本可行解X(0)和X(1)分别代入目标函数得由此j称做检验数,是对线性规划问题的解进行最优性检验的标志.现在学习的是第23页，共48页最优解的判别定理最优解的判别定理：且对一切的 j=m+1,.,n有则X(0)为最优解。若 是一个基可行解，现在学习的是第24页，共48页无穷多最优解判别定理无穷多最优解判别定理：若 是一个基可行解，且对一切的 j=m+1,.,n 有又存在某个非基变量的检验数 则线性规划问题有无穷多最优解。现在学习的是第25页，共48页无界解的判别

12、定理无界解的判别定理：现在学习的是第26页，共48页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变成单位向量，为此,只要对系数矩阵的增广阵进行“行”的初等变换即可。行变换的定义：现在学习的是第27页，共48页(第s行)*1/ask得

13、:当is时,(第i行)-(第s行)*aik现在学习的是第28页，共48页经过初等变换后,新的增广矩阵是现在学习的是第29页，共48页4 单纯形法的计算步骤和单纯形表单纯形法的计算步骤和单纯形表约束方程组和目标函数组成 n+1个变量,m+1个方程的方程组该方程组对应的增广矩阵是现在学习的是第30页，共48页现在学习的是第31页，共48页现在学习的是第32页，共48页5 单纯形法的进一步讨论单纯形法的进一步讨论 人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，xn+m 人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是

14、最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。现在学习的是第34页，共48页1、大M法方方法法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。理理由由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。例1：用大M法求解如下线性规划问题现在学习的是第35页，共48页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 M 1 6xx4 x310 3 -2 0 1 0 0 -11 0 1 0 0 -1 1 -2 1

15、 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 -2 0 1 0 0 0 1cj0MMX4X6X7 b CBXBX1X2X3X4X5X6X7i -

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

17、段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，用单纯形法计算，直到得到最优解为止。现在学习的是第38页，共48页第一阶段：求解辅助规划问题现在学习的是第39页，共48页 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

18、0 -1 1 -2 1 -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-zj现在学习的是第40页，共48页12 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是

19、人工变量，第一阶段求解的最优结果是=0，因此得最优解为：第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。最优解为：最优值为：z=-2现在学习的是第41页，共48页两阶段法：辅助规划；去掉人工变量，单纯形法。现在学习的是第42页，共48页对目标函数求max的线性规划问题,用单纯形法计算步骤的框图现在学习的是第43页，共48页唯一最优解唯一最优解 N NN YYY添添加加松松弛弛变变量量、人人工工变变量量,列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量对应的检验数对应的检验数 j所有所有 j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基变某非基变量检验数

20、量检验数为零为零无可行解无可行解无穷多最优解无穷多最优解对某对某 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现在学习的是第44页，共48页感谢大家观看现在学习的是第48页，共48页