3运筹学第二章单纯形法及进一步讨论.ppt

1、运筹学基础,1,第二章 线性规划,单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结,运筹学基础,2,第二章 线性规划,单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结,3,(一)单纯形法的基本思路,3.1 单纯形法,运筹学基础,思路：首先求出一个顶点(基可行解)，并判断是否是最优解，如果是求解结束，如果不是就进行下一步；第二步转换到另一个顶点(另一个基可行解)，并判断是否是最优解，如果是求解结束，如果不是就重复进行第二步，直至目标函数达到最优。,具体工作： (1) 如何求出初始基可行解？ (2) 如何判断一个基可行解是否是最优？ (3) 如何从一基可行解转换

2、到另一更优的基可行解？,4,(二)单纯形法的求解方法,1. 确定初始基可行解，只要找出初始可行基。,(1) 直接观察法：,从系数矩阵 A 中直接观察出一个初始基,3.1 单纯形法,运筹学基础,5,（2）化标准型法,如果所有约束条件都是“”形式的不等式，则可以利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。重新对 xj 及 aij 进行编号，可得下列方程组：,从中可得单位矩阵,运筹学基础,6,（2）化标准型法,以B作为可行基。将(2.3)移项得,令xm+1= = xn=0 则,xi = bi ( i=1，2，m),又因bi0 (标准型中规定)，则得一初始基可行解,X=(b1,b2, ,

3、bm,0,0)T,运筹学基础,7,（3）人工变量法,当所有约束条件都是“”形式的不等式或等式约束时，如果不存在单位矩阵，就采用人工变量法: 对不等式约束左端减去一个非负的剩余变量，再加上一个非负的人工变量； 对等式约束左端再加上一个非负的人工变量。 这样就可以得到一个单位矩阵，即总能得到一个初始可行基。,运筹学基础,8,（3）人工变量法,设线性规划问题的约束条件是,分别对各约束方程加人工变量 xn+1, xn+2, , xn+m可得,运筹学基础,9,以xn+1， xn+m为基变量，可得到一个单位矩阵,令 x1 = x2 = = xn = 0，可得(2.6)式的一个初始基可行解 X(0) = (

4、 0，0， ，0，b1，b2， ， bm )T,以此基可行解为起始点转换到(2.5)的基可行解。,（3）人工变量法,运筹学基础,10,2. 最优性检验与解的判别,线性规划问题的求解结果,唯一最优解,无穷多最优解,无界解,无可行解,如何判别？,运筹学基础,11,2. 最优性检验与解的判别,线性规划问题的求解结果,唯一最优解,无穷多最优解,无界解,无可行解,如何判别？,由上述初始基可行解确定的讨论，可知约束方程组变成下面的形式：,运筹学基础,12,由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。,转

5、换迭代过程中的一般形式为：,运筹学基础,13,由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。,把(2.7)式代入目标函数,中可得,运筹学基础,14,令,于是,再令,则,运筹学基础,15,假设X(0)=( b1, b2, , bm, 0, , 0)T 是一个基可行解，则有下列判断定理：,1. 最优解：如果对一切 j=m+1，n 有 j0，则X(0)为最优解(注意，这里是针对目标函数求极大而言的)。,2. 无穷多最优解：如果对一切 j=m+1，n 有j0，又存在 m+k=0，则线性规划问题有无穷多

6、最优解。,3. 无界解：如果有一个m+k0，且对 i=1,m 有ai,m+k0，则线性规划问题有无界解(无最优解)。,运筹学基础,运筹学基础,16,3. 基变换,基变换：在单纯形法求解中，如果得到了某一个基可行解，并判断了它不是最优解，就要从该基变换成另一个更优的基并求出新的基可行解。 方法：第一步确定换入非基变量；第二步确定换出基变量；第三步将所确定的一对变量对应的系数列向量对换得到新的基，求出新的基可行解。,17,(1) 换入变量的确定,再看 (2.8)式,其中,当某些j0时， xj 增加会使目标函数值增加，我们就要从中确定一个非基变量xj换到基变量中。方法： 把j值最大者所对应的变量换入

7、。即,若 则对应的变量 xk 为换入变量, 这样的迭代速度最快。,运筹学基础,18,(2) 换出变量的确定,设B(p1,p2, ,pm) 是一个基，与之对应的基可行解为X(0)=(x1(0), x2(0), , xm(0) , 0, ,0 )T 。pm+1,pm+2, ,pm+t , ,pn为非基向量。,设确定pm+t 为换入非基向量。于是,其中im+t为一组不全为0的数 ( j=1，m)。,运筹学基础,19,不妨设为一正数，则有恒等式,或,根据(2.9)可如下确定换出变量：,令,确定xl为换出变量。,注意：, pj ( j = 1，m, j l )，pm+t 线性无关； 存在基可行解。,运筹

8、学基础,20,注意：, pj ( j =1，m, j l )，pm+t 线性无关；存在基可行解。,：假设pj ( j=1，m, jl)，pm+t 线性相关，则存在不全为0的数j使得,又因,所以有,这说明 p1, p2, , pm 线性相关。矛盾,由,构成的 X(1) 是一个基可行解。,运筹学基础,21,4基变换的系数矩阵法,以下列形式的约束方程组进行讨论。,mm单位矩阵,是基， x1, x2, , xm是基变量。可得基可行解X(0)=(b1,b2, ,bm,0,0)T。,运筹学基础,22,如果X(0)不是最优，则需作基变换。设 xk 为确定的换入变量，显然 为,在迭代过程中 可表示为,于是可确

9、定 xl 为换出变量。,下面就要把xk，xl所对应的向量pk=(a1k,a2k, ,amk)T 和pl=(0, , 1, ,0)T 进行交换，并且要把pk变为单位向量。,我们将通过系数矩阵的增广矩阵进行初等变换来实现。,运筹学基础,23,(2.10)式的增广矩阵为,24,交换步骤：,将(2.11)式中第 l 行除以 alk ；将(2.11)式中 xk 列的各元素，除了 alk 变换为1以外，其它都应变为0 。第i 行 ( il ) 的变换是：将用(第 i 行)(经过变换以后的第 l 行乘以aik)。,运筹学基础,25,经过变换以后系数矩阵各元素的变换关系式：,运筹学基础,26,经过变换后的新增

10、广矩阵为：,新的基可行解：,由(2.12)式可知x1 ， ， xk ， ， xm的系数列向量构成mm单位矩阵，它是可行基。于是得到一个基可行解X(1)：,X(1)=(b1, ,bl-1 ,0, bl+1 , bm , 0, bl ,0 , 0)T,把元素alk称为主元素，它所在的列称为主列，它所在的行称为主行。,运筹学基础,27,(三)单纯形法的计算步骤,1. 单纯形表,将约束方程组与目标函数组成n+1个变量，m+1个方程的方程组。,将上述方程组写成增广矩阵,运筹学基础,运筹学基础,28,将 z 看作不参与基变换的基变量，它与x1，x2，xm的系数构成一个基。采用初等行变换将c1 c2 cm

11、变换为零，使其对应的系数矩阵为单位矩阵。可得：,根据上述增广矩阵设计计算表：,非基变量检验数j 。,29,计算表11：,XB列中填入基变量，这里是x1，x2，xm；,CB列中填入基变量的价值系数，它们与基变量对应；,b列中填入约束方程组右端的常数；,cj行中填入基变量的价值系数c1， c2， cn；,i列中的数字是在确定换入变量后，按 规则计算后填入；,最后一行称为检验数行，对应各非基变量。,非基变量检验数j 。,运筹学基础,30,2. 计算步骤,(1) 找出初始可行基，确定初始基可行解，建立初始单纯形表。,(2) 检验各非基变量 xj 的检验数 j=cj,如果 j0 ，j=m+1，,，n；则

12、已得到最优解，可停止计算。否则转入下一步。,(3) 存在 j0 ，j=m+1，n 中，若存在某个 k 对应 xk 的系数向量pk0，则问题无解，停止计算。否则，转入下一步。,(4) 根据max( j0)= k ，确定xk 为换入变量，按 规则计算,可确定xl为换出变量。转下一步。,(5) 以 alk 为主元素进行迭代，把 xk 所对应的列向量,第 l 行,将XB列中的 xl 换为 xk，得到新的单纯形表。,在得到最优解或确定无界解之前，重复(2)(5)。,运筹学基础,31,3举例,例 求下列线性规划问题的解,(1) 确定初始基可行解：,由标准型中的约束方程组可知变量x3，x4， x5,所对应的

13、系数向量构成33单位矩阵为一基。可得初始基可行解,X(0)=(0，0，8，16，12)T,据此生成单纯形表,表11：,2,3,4,3,0,运筹学基础,32,表12：,基可行解 X(1)=(0，3，2，16，0)T,2,-3/4,2,4,-9,表11：,2,3,4,3,0,运筹学基础,33,表13：,基可行解 X(2)=(2，3，0，8，0)T,2,1/4,4,12,13,运筹学基础,34,表14：,最优解 X(3)=(4，2，0，0，4)T ，z=14,3/2,1/8,14,运筹学基础,运筹学基础,35,单纯形法小结,求解过程 确定初始基可行解 判断是否是最优解 是，求解结束；（或者无最优解）

14、 否。确定换入换出变量 基变换，得到新的可行基 转入第二步，重复。,运筹学基础,36,第二章 线性规划,单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结,37,3.2 人工变量法,运筹学基础,（3.13）,在前面我们讲过由人工变量法构造初始可行基，若线性规划问题的约束条件为,然后人为的加上变量 xn+1，xn+2，xn+m后得到,(3.14),38,3.2 人工变量法,运筹学基础,若人工变量0，(3.14)与(3.13)不等价，即对原LP问题的约束条件进行了“篡改”，不是希望的。但又需添加人工变量，得到初始可行基。,为保证它与原LP问题得到的最优解一致，需要将人工变量从基变量

15、中逐个替换出来。 若经过基变换后，基变量中不再含有非零的人工变量，这表示原问题有解；若在最终的表中当所有的检验数 0，但在其中还有某个非零人工变量，这表示无可行解。,39,3.2 人工变量法,运筹学基础,在引入人工变量的同时修改目标函数，规定人工变量在目标函数中的系数为(M )(M0的大数)。即,这种方法叫大M法。作了上述变换之后，再用单纯形法把人工变量从基变量中转换出去，然后求原问题的最优解。,3.2.1 大M法,40,3.2 人工变量法,运筹学基础,例：用大 M 法求解如下线性规划问题,41,3.2 人工变量法,运筹学基础,解：在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到,

16、其中M是一个任意大的正数。,42,3.2 人工变量法,运筹学基础,建立单纯形表：,-3+6M,1-M,1-3M,M,1,11,3/2,1,43,3.2 人工变量法,运筹学基础,单纯形表2：,-1,1-M,3M-1,M,1,-,1,-,44,3.2 人工变量法,运筹学基础,单纯形表3：,-1,M-1,M+1,1,3,4,-,-,45,3.2 人工变量法,运筹学基础,单纯形表4：,1/3,M-1/3,M-2/3,1/3,2,最优解 X =(4,1,9,0,0,0,0)，Zmin = -2。,46,3.2 人工变量法,运筹学基础,3.2.2 两阶段法,用计算机求解含有人工变量的线性规划问题时，只能用

17、很大的数代替M，这就可能造成计算上的错误。 引入两阶段法求解。,47,3.2 人工变量法,运筹学基础,第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。即,再利用单纯形法求解上述模型，若最优值为0，则原问题有解，可进行第二阶段计算。否则原问题无可行解。,48,3.2 人工变量法,运筹学基础,3.2.2 两阶段法,第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。即,再利用单纯形法求解上述模型，若最优值为0，则原问题有解，可进行第二阶段计算。否则原问题无可行解。,第

18、二阶段，将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。,各阶段的计算方法与前面的单纯形法相同。,49,3.2 人工变量法,运筹学基础,3.2.2 两阶段法,例：用两阶段法求解线性规划问题,50,3.2 人工变量法,运筹学基础,解：添加人工变量，给出第一阶段的数学模型为,51,3.2 人工变量法,运筹学基础,用单纯形法求解得到的最后结果为：,此时，得到的最优解为 =0，X =（0，1，1，12，0，0，0），它是原LP问题的基可行解，因此可以进行第二阶段的计算。,52,3.2 人工变量法,运筹学基础,第二阶段的初始单纯形表为：,0 1 1,运筹学基础,53,第二章 线性规划,单纯形法 人工变量法 退化问题 检验数的几种表现形式 单纯形法总结,54,3.3 退化问题,运筹学基础,(1) 什么是退化？,当基解基可行解最优基可行解中有基变量为0时，即出现退化。,当出现退化时，可能出现计算过程的循环，便永远达不到最优解。,55,3.3 退化问题,运筹学