哈尔滨工业大学运筹学教案教案

1、检验数的概念和计算检验数的概念和计算最优性判别最优性判别基变换（换入变量和换出变量的确定）基变换（换入变量和换出变量的确定）旋转变换旋转变换2022-7-5管理运筹学课程组管理运筹学课程组 39231 基本思想 对于一个标准型标准型LP问题，从一个初始基可行解初始基可行解出发，判断判断其是否为最优解，若是则结束；否则求一个与其“相邻相邻”的、的、改进的基可行解改进的基可行解。再判断这个解是否最优，若是则结束，否则再求一个“相邻”的、改进的基可行解如此迭代下去，直到找到基最优解基最优解或判定问题无解为止。x1x204Q2(4,2)Q1Q3Q44x1=164x2=1

2、2x1+2x2=82x1+3x2=03Q2如例如例1，O Q1 Q2或或 O Q4 Q3 Q22022-7-5管理运筹学课程组管理运筹学课程组 393单纯形法要解决的三方面的问题：单纯形法要解决的三方面的问题：（1）如何确定）如何确定初始的基可行解初始的基可行解？（2）如何进行解的）如何进行解的最优性判别最优性判别？（3）如何寻找）如何寻找改进的基可行解改进的基可行解？2022-7-5管理运筹学课程组管理运筹学课程组 39432 确定初始基可行解确定初始基可行解 定义：线性规划规范型，当线性规划标准型： Max z = Max z

3、 = CXCX1.0njjjP xbs tX2022-7-5管理运筹学课程组管理运筹学课程组 395其中系数矩阵A=P1，P2，Pn中含有一单位矩阵I，不妨设单位矩阵I1210.000.0,.00.1mP PP即为一即为一初始可行基初始可行基。令非基变量取值为零，便。令非基变量取值为零，便得到一组得到一组基可行解基可行解。 2022-7-5管理运筹学课程组管理运筹学课程组 3963.23.2最优性检验和解的判别最优性检验和解的判别 对标准型的一般线性规划问题，经过变换、迭代，总可将线性规划约束条件中非基变量移至方程右边，得如下形式

4、：即：即：111,111222,112,11.mmnnmmnnmmm mmmnnxbaxaxxbaxaxxbaxax,1niiijjjmxbax其中其中i=1，2，m2022-7-5管理运筹学课程组管理运筹学课程组 3972022-7-5管理运筹学课程组管理运筹学课程组 398 nmjjjxzz10 棗 z 与与当当前前非非基基变变量量的的关关系系 由此可知，若存在 j 0(m+1 j n)，则有 xj 0，其其它它非非基基变变量量仍仍为为零零的的可可行行解解，其目标函数值,zxzzjj00 这说明当前解不是最优解。若所有 j 0

5、(m+1 j n)，则 z0为可行解所能取得的目标函数最大值，说明当前解是最优解。故称 j 为检验数。将基变量的系数 0 也视为其检验数，可得： 注意：注意：xj的检验数的检验数 是当是当z表示为非基变量的函数时目标函表示为非基变量的函数时目标函数中数中xj的系数。基变量的检验数为零。的系数。基变量的检验数为零。 2022-7-5管理运筹学课程组管理运筹学课程组 399为对应于基为对应于基B的一个基可的一个基可(0)12 ,.,0,.,0TmXb bb若若 行解，对于一切行解，对于一切 1,.,jmn有检验数有检验数 , 0j则则 ）（ 0X为最优解。为最优解。

6、 定理定理5:（最优解的判别定理）（最优解的判别定理）2022-7-5管理运筹学课程组管理运筹学课程组 3910 定理定理 6 （无穷多最优解的判别定理）（无穷多最优解的判别定理） 若若 对应于基对应于基B的一个基可的一个基可 行解，对于一切行解，对于一切 ，有检验数，有检验数 且存在某个非基变量对应的检验数且存在某个非基变量对应的检验数 =0，则该，则该 线性规划问题有无穷多个最优解线性规划问题有无穷多个最优解。(0)12 , ,., ,0,.,0TmXb bb1,.,jmnmk, 0j2022-7-5管理运筹学课程组管理运筹学课程组 ftp:/211.71.

7、69.23911无穷多最优解判别定理无穷多最优解判别定理：TmbbbX)0 , 0 ,(21)0(若若B的一个基可行解，且对一切的的一个基可行解，且对一切的 j=m+1,.,n有有为对应于基为对应于基, 0j又存在某个非基变量的检验数又存在某个非基变量的检验数, 0km则线性规划则线性规划问题有无穷多最优解。问题有无穷多最优解。证明：证明：kmx非基变量非基变量新基可行解新基可行解)1(X新的目标函数新的目标函数值不变值不变换入换入)1(X,)0(X两个最优解两个最优解，连线上的所有点均是最优连线上的所有点均是最优解。2022-7-5管理运筹学课程组管理运筹学课程组 ftp:/211.71.6

8、9.23912定理定理 7 （无界解的判别定理）（无界解的判别定理）若若 为对应于基为对应于基B的一个基可行解，的一个基可行解，存在某个非基变量对应的检验数存在某个非基变量对应的检验数 0，并且对应的，并且对应的变量系数变量系数 ， 则该线性规划问题则该线性规划问题有无界解（或无最优解）。有无界解（或无最优解）。(0)12 , ,., ,0,.,0TmXb bbm k,0i m ka1 , 2 , . . . ,im2022-7-5管理运筹学课程组管理运筹学课程组 3913无界解的判别定理：无界解的判别定理：若TmbbbX)0 , 0 ,(21)0(一个基可行解

9、，有一个, 0,kmia为对应于基B的, 0km并且对i=1,.,m有那么线性规划问题具有无界解（无最优解）。证明：构造新的解kmjnmjabxjkmkmiii且, 1, 0, 0,)1()1(,)1(lllxxi=1,2,m2022-7-5管理运筹学课程组管理运筹学课程组 3914验证可行性：因为i,m,000 ，而而xj =0(m+1 j n，j k)，要保持，要保持xi 0 ( i=1，2，,m)，即，即必须必须 于是，当于是，当 为换出变量。为换出变量。若所有若所有 则则xk 可取无穷大，问题无最优解。可取无穷大，问题无最优解。min0ilkikiklk

10、bbxaaa0ika ,0,lklllkbxxxa2022-7-5管理运筹学课程组管理运筹学课程组 3917换出变量确定方法换出变量确定方法: : 一般，计算一般，计算 = =lklikikiiabaabmin 0，第，第 l 个约束个约束对应的基变量为换出变量。对应的基变量为换出变量。2022-7-5管理运筹学课程组管理运筹学课程组 39183 迭代迭代 确定换入变量：当确定换入变量：当 ，确定，确定 换入变量；换入变量；确定换出变量：当确定换出变量：当 ，确定，确定 换入变量；换入变量；将交叉元素（主轴元素）将交叉元素（主轴元

11、素） 单位化，单位化，(旋转旋转)kxlxlklikikiabaab0minka1kj )0max(2022-7-5管理运筹学课程组管理运筹学课程组 3919即乘以初等矩阵。重复上述步骤直到所有的检验数即乘以初等矩阵。重复上述步骤直到所有的检验数满足最优条件，得最优解。满足最优条件，得最优解。2022-7-5管理运筹学课程组管理运筹学课程组 3920最优性判别定理：最优性判别定理： 若基可行解对应的检验数若基可行解对应的检验数 0 ( j=1，2，,n),n)，则此解是最优解，否则不是最优解。，则此解是最优解，否则不是最优解。j 换换入入变变量量的的确确定定方方法法： 一一般般，当当jmaxj |j 0= k，取取 xk为为换换入入变变量量。 换出变量确定方法换出变量确定方法: : 一般，计算一般，计算 = =lklikikiiabaabmin 0，第，第 l 个约束个约束对应的基变量为换出变量。对应的基变量为换出变量。结论结论:2022-7-5管理运筹学课程组管理运筹学课程组 ftp:/211.7