第五章单纯形法1基本思路和原理

1、第五章 单纯形法singlex method第五章第五章 单纯形法单纯形法由美国数学家丹捷格由美国数学家丹捷格(g.b.dantzig)(g.b.dantzig)提出的，得到最提出的，得到最广泛应用的线性规划的代数算法广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。学发展史上最辉煌的一笔。 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解. 我们在第三章所介绍的线性规划问题的计算我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以机解法就是基于单纯形法编程来解决可以含有上千

2、个决策变量的及上千个约束条件含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。的复杂的线性规划问题。第五章第五章 单纯形法单纯形法 5.1 单纯形法的基本思路和原理5.1 单纯形法的基本思路和原理线性规划问题线性规划问题 0max11jnjijijnjjjxbxaxcz()()()(i=1,，m)(j=1,，n)可行解：可行解：满足上述约束条件（），（）的解满足上述约束条件（），（）的解 ，称为线性规划问题的可行解全部可行解的集合称为可行域称为线性规划问题的可行解全部可行解的集合称为可行域tnxxx,15.1 单纯形法的基本思路和原理线性规划问题线性规划问题 0max11jnjijij

3、njjjxbxaxcz()()()(i=1,，m)(j=1,，n)最优解：最优解：使目标函数（）达到最大值的可行解称为最优解使目标函数（）达到最大值的可行解称为最优解5.1 单纯形法的基本思路和原理基：基：设为约束方程组（）的设为约束方程组（）的m mn n阶阶系数矩阵系数矩阵，（设，（设n nm m），），其其秩秩为为m m，是矩阵中的一个，是矩阵中的一个m mm m的的满秩子矩阵满秩子矩阵，称，称是线性规划问题的一个是线性规划问题的一个基基不失一般性，设不失一般性，设mmmmmaaaappb11111,中的每一个列向量中的每一个列向量j j（j j，m m）称为）称为基向量基向量，与基向，

4、与基向量量j j对应的变量对应的变量x xj j称为称为基变量基变量。线性规划中除了基变量以外的变。线性规划中除了基变量以外的变量称为量称为非基变量非基变量。5.1 单纯形法的基本思路和原理标准形式为:目标函数：目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3约束条件：约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。这是由三个五元线性方程组成的方程组，它的系数矩阵为:.100100101200111),(54321pppppa 中的每一个列向量中的每一个列向量p3,

5、 p4, p5 p3, p4, p5 是是基向量基向量，与其对，与其对应的变量应的变量s1, s2, s3s1, s2, s3是是基变量基变量。除了基变量以外的变量。除了基变量以外的变量x1, x1, x2x2是非基变量。是非基变量。5.1 单纯形法的基本思路和原理.1005p.0013p可以看到 s1, s2, s3的系数列向量这是由三个五元线性方程组成的方程组，它的系数矩阵为:.0104p.100100101200111),(54321pppppa是线性独立的,这些向量构成一个基100010001,543pppb5.1 单纯形法的基本思路和原理基：基：设为约束方程组（）的设为约束方程组（）

6、的m mn n阶阶系数矩阵系数矩阵，（设，（设n nm m），），其其秩秩为为m m，是矩阵中的一个，是矩阵中的一个m mm m的的满秩子矩阵满秩子矩阵，称，称是线性规划问题的一个是线性规划问题的一个基基不失一般性，设不失一般性，设mmmmmaaaappb11111,中的每一个列向量中的每一个列向量j j（j j，m m）称为）称为基向量基向量，与基向，与基向量量j j对应的变量对应的变量x xj j称为称为基变量基变量。线性规划中除了基变量以外的变。线性规划中除了基变量以外的变量称为非基变量。量称为非基变量。在此例题中：在此例题中： 都是该线性规划的一个都是该线性规划的一个基基。 .1001

7、00101200111),(54321pppppa这些这些基基都是由都是由3 3个线性无关的系数列向量组成的个线性无关的系数列向量组成的, ,对应的对应的基变量基变量分别为分别为 x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s2x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s2。 0100121111000100011010010115.1 单纯形法的基本思路和原理基解：基解：在约束方程组（在约束方程组（e e）中，令所有的非基变量：）中，令所有的非基变量：又因为有又因为有 ，根据克莱姆法则，由，根据克莱姆法则，由m m个约束方程可以解个约束方程可

8、以解出出m m个基变量的唯一解个基变量的唯一解 。将这个解加上非。将这个解加上非基变量取基变量取0 0的值有的值有 ，称，称x x为线性规划问为线性规划问题的基解。题的基解。021nmmxxx0btmbxxx,1tmbxxx0 , 0 ,11010010113b25040030010010010120011132121sssxx我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, s2 x1, s2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b2504003000010

9、0100101200111312ssx25040030032212sxxsx即即: :求解求解, ,即可得到基变量的唯一一组解即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150: x2= 400 , s1= -100 , s3= -150加上非基变量加上非基变量: x1= 0, s2 = 0, : x1= 0, s2 = 0, 得到此线性规划的一个基解得到此线性规划的一个基解. .x1=0,x2=400s1=-100s2=0s3=-1501000100012b25040030010010010120011132121sssxx我们找到我们找到a a 的一个

10、基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b25040030000100100101200111321sss250400300321sss即即: :求解求解, ,即可得到基变量的唯一一组解即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250: s1=300 , s2=-400 , s3=250加上非基变量加上非基变量: x1= 0, x2 = 0, : x1= 0, x2 = 0, 得到此线性规划的

11、一个基解得到此线性规划的一个基解. .x1=0,x2=0,s1=300s2=400s3=2505.1 单纯形法的基本思路和原理基解：基解：在约束方程组（在约束方程组（e e）中，令所有的非基变量：）中，令所有的非基变量：又因为有又因为有 ，根据克莱姆法则，由，根据克莱姆法则，由m m个约束方程可以解个约束方程可以解出出m m个基变量的唯一解个基变量的唯一解 。将这个解加上非。将这个解加上非基变量取基变量取0 0的值有的值有 ，称，称x x为线性规划问为线性规划问题的基解。题的基解。021nmmxxx0btmbxxx,1tmbxxx0 , 0 ,15.1 单纯形法的基本思路和原理线性规划问题线性

12、规划问题 0max11jnjijijnjjjxbxaxcz()()()(i=1,，m)(j=1,，n)基可行解：基可行解：满足变量非负约束条件满足变量非负约束条件 ( g ) ( g ) 的基解称为基可行解。的基解称为基可行解。可行基：可行基：对应于基可行解的基称为可行基。对应于基可行解的基称为可行基。1010010113b25040030010010010120011132121sssxx我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵

13、方程矩阵方程 ax = bax = b25040030000100100101200111312ssx25040030032212sxxsx即即: :求解求解, ,即可得到基变量的唯一一组解即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150: x2= 400 , s1= -100 , s3= -150加上非基变量加上非基变量: x1= 0, s2 = 0, : x1= 0, s2 = 0, 得到此线性规划的一个基解得到此线性规划的一个基解. .x1= 0,x2= 400,s1= -100,s2= 0,s3= -150,1000100012b25040030

14、010010010120011132121sssxx我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b25040030000100100101200111321sss250400300321sss即即: :求解求解, ,即可得到基变量的唯一一组解即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250: s1=300 , s2=-400 , s3=250加上非基变量加上非基变量:

15、 x1= 0, x2 = 0, : x1= 0, x2 = 0, 得到此线性规划的一个基解得到此线性规划的一个基解. .x1=0,x2=0,s1=300s2=400s3=250 x1=0,x2=0,s1=300s2=400s3=250均为基解均为基解x1= 0,x2= 400,s1= -100,s2= 0,s3= -150,基可行解基可行解不是基可行解不是基可行解1010010113b1000100012b均为基均为基可行基可行基不是可行基不是可行基 由于在这个基解中由于在这个基解中s s1 1100100，s s3 3150150，不满足该线，不满足该线性规划最后一个性规划最后一个变量非负的

16、约束条件变量非负的约束条件，显然不是此线性规划，显然不是此线性规划的的可行解可行解，一个，一个基解可以是可行解基解可以是可行解，也可以是非可行解也可以是非可行解，它，它们之间的主要区别在于其们之间的主要区别在于其所有变量所有变量的解是否满足的解是否满足非负的条件。非负的条件。5.1 单纯形法的基本思路和原理5.1 单纯形法的基本思路和原理 定理定理: : 线性规划问题的基可行解线性规划问题的基可行解 x x 对应线性规划问题可行域对应线性规划问题可行域的顶点的顶点. . 在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基可行解，第一个找到的可行域的顶点叫做初始

17、基可行解。 5.1 单纯形法的基本思路和原理 例：找出下述线性规划问题的全部基解，指出其中例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解：的基可行解，并确定最优解：max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0410510010010210010154321xxxxx矩阵方程矩阵方程: :1000100011b我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量

18、的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b410500100100102100101543xxx得到基解得到基解: :x1=0,x2=0,x3=5x4=10 x5=4410510010010210010154321xxxxx代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 z = 55.1 单纯形法的基本思路和原理x x1 10 00 05 50 010105 55 52 2x x2 20 04 40 05 50 02.52.54 44 4x x3 35 55 50 05 5-5-50 00 03 3x x4 410102 25 50 00

19、00 0-3-30 0 x x5 54 40 04 4-1-14 41.51.50 00 0z z5 5171710102020151517.517.522221919是否基可行是否基可行解解0011020102b410510010010210010154321xxxxx410500100100102100101432xxx我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x5 x1, x5 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b得到基解得到基解: :x1=0

20、,x2=4,x3=5x4=2x5=0代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 z =xxx即即: :5.1 单纯形法的基本思路和原理x x1 10 00 05 50 010105 55 52 2x x2 20 04 40 05 50 02.52.54 44 4x x3 35 55 50 05 5-5-50 00 03 3x x4 410102 25 50 00 00 0-3-30 0 x x5 54 40 04 4-1-14 41.51.50 00 0z z5 5171710102020151517.517.522221919是否基可

21、行是否基可行解解5.1 单纯形法的基本思路和原理单纯形法的基本思路：单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。5.1 单纯形法的基本思路和原理 定理定理: : 线性规划问题的基可行解线性规划问题的基可行解 x x 对应线性规划问题对应线性规划问题可行域的顶点可行域的顶点. . 找顶点就是找基可行解找顶点就是找基可行解 5.1 单纯形法的基本思路和原理一、找出一个初始基可行解一、找出一个初始基

22、可行解 在第二章的例在第二章的例1中我们得到以下数学模型：中我们得到以下数学模型：例例1.目标函数目标函数： max z = 50 x1 + 100 x2 约束条件约束条件： s.t. s.t. x1 + x2 300 2x1 +x2 400 x2 250 x1 ， x2 05.1 单纯形法的基本思路和原理标准形式为:目标函数：目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3约束条件：约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。这是由三个五元线性方程组成的方程组

23、，它的系数矩阵为:.100100101200111),(54321pppppa 一般说来判断一个基是否是可行基，只有在求出一般说来判断一个基是否是可行基，只有在求出其其基解基解后，当其基解后，当其基解所有变量所有变量的值都是大于等于零，的值都是大于等于零，才能判定这个解是才能判定这个解是基可行解基可行解，这个基是，这个基是可行基可行基。一、找出一个初始基可行解一、找出一个初始基可行解 5.1 单纯形法的基本思路和原理1010010113b25040030010010010120011132121sssxx我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1,

24、 s2 x1, s2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b25040030000100100101200111312ssx25040030032212sxxsx即即: :求解求解, ,即可得到基变量的唯一一组解即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150: x2= 400 , s1= -100 , s3= -150加上非基变量加上非基变量: x1= 0, s2 = 0, : x1= 0, s2 = 0, 得到此线性规划的一个基解得到此线性规划的一个基解.

25、.x1= 0,x2= 400,s1= -100,s2= 0,s3= -150,5.1 单纯形法的基本思路和原理由于在线性规划的标准型中要求由于在线性规划的标准型中要求 bj 大于等于零大于等于零，如果能找到一个基是单位矩阵，或者说一个基是由如果能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后单位矩阵的各列向量所组成（至于各列向量的前后顺序无关紧要的）那么显然所求得的基解一定是基顺序无关紧要的）那么显然所求得的基解一定是基可行解可行解. .1000100011b一、找出一个初始基可行解一、找出一个初始基可行解 0101000012b1000100012b250

26、40030010010010120011132121sssxx我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b25040030000100100101200111321sss250400300321sss即即: :求解求解, ,即可得到基变量的唯一一组解即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250: s1=300 , s2=-400 , s3=250加上非基变量加上

27、非基变量: x1= 0, x2 = 0, : x1= 0, x2 = 0, 得到此线性规划的一个基解得到此线性规划的一个基解. .x1=0,x2=0,s1=300s2=400s3=2501000100011b我们找到我们找到a a 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 ax = bax = b410500100100102100101543xxx得到基解得到基解: :x1=0,x2=0,x3=5x4=10 x5=4410510010010

28、210010154321xxxxx代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 z = 5这个单位矩阵或由单位矩阵各列向量组成的基一定这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。是可行基。实际上这个基可行解中的各个变量或等于某个实际上这个基可行解中的各个变量或等于某个 b bj j 或等于零。或等于零。 5.1 单纯形法的基本思路和原理一、找出一个初始基可行解一、找出一个初始基可行解 5.1 单纯形法的基本思路和原理单纯形法的基本思路：单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之

29、为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。5.1 单纯形法的基本思路和原理一、找出一个初始基可行解一、找出一个初始基可行解二、最优性检验二、最优性检验 所谓最优性检验就是判断已求得的基可行解是所谓最优性检验就是判断已求得的基可行解是否是最优解。否是最优解。5.1 单纯形法的基本思路和原理二、最优性检验二、最优性检验 1、最优性检验的依据检验数最优性检验的依据检验数 j 一般来说目标函数中既包括一般来说目标函数中既包括基变量基变量，又包括，又包括非基变非基变量量, ,现在我们要求只用非基变量来表示目标函数现在我

30、们要求只用非基变量来表示目标函数. .max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。5.1 单纯形法的基本思路和原理1、最优性检验的依据检验数最优性检验的依据检验数 j 一般来说目标函数中既包括一般来说目标函数中既包括基变量基变量，又包括，又包括非基变非基变量量, ,现在我们要求只用非基变量来表示目标函数现在我们要求只用非基变

31、量来表示目标函数. .l在约束等式中通过移项等处理就在约束等式中通过移项等处理就, ,用用非基变量非基变量来表示来表示基变量基变量，l用用非基变量非基变量的表示式代替目标函数中基变量，的表示式代替目标函数中基变量，目标目标函数中只含有非基变量函数中只含有非基变量. .l此时目标函数中所有变量的系数即为各变量的此时目标函数中所有变量的系数即为各变量的检验检验数数，把变量，把变量xixi的检验数记为的检验数记为 i i。5.1 单纯形法的基本思路和原理分析 max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250

32、x1, x2, s1, s2, s30。本例题中本例题中, ,由于初始可行解中由于初始可行解中x x1 1，x x2 2为非基变量，所以为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出此目标函数已经用非基变量表示了，不需要再代换出基变量了。基变量了。可知可知 1 15050， 2 2100100， 3 30 0， 4 40 0， 5 50 0。5.1 单纯形法的基本思路和原理本例题中本例题中, ,由于初始可行解中由于初始可行解中x x1 1，x x2 2为为非基变量非基变量，而，而x x3 3为为基变量基变量, ,应该应该在约束等式中通过移项处理在约束等式中通过移项处理, ,用用

33、非基变非基变量量来表示来表示基变量基变量, ,得到得到x x3 3 = 5 - = 5 - x x1 1 , ,代入目标函数得到代入目标函数得到z z = 5 + = 5 + x x1 1 + 3 + 3x x2 2 可知可知 1 11 1， 2 23 3， 3 30 0， 4 40 0， 5 50 0。max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 05.1 单纯形法的基本思路和原理二、最优性检验二、最优性检验 1、最优性检验的依据检验数最优性检验的依据检验数 j2 2、最优解判别定理、最优解判别定理 对于

34、求最大目标函数的问题中，对于某个基可行对于求最大目标函数的问题中，对于某个基可行解，如果所有检验数解，如果所有检验数 j j 0 0，则这个基可行解是最优解。，则这个基可行解是最优解。5.1 单纯形法的基本思路和原理2 2、最优解判别定理、最优解判别定理设用非基变量表示的目标函数为如下形式设用非基变量表示的目标函数为如下形式其中，其中，z0为常数项，为常数项，j是所有非基变量的下标集。由于所有的是所有非基变量的下标集。由于所有的xj的取值范围为大于等于零，当所有的的取值范围为大于等于零，当所有的j都小于等于零时，都小于等于零时，可知可知 是一个小于等于零的数，要使是一个小于等于零的数，要使 的

35、值最大，显然只的值最大，显然只 有为零。我们把这些有为零。我们把这些xj取为非基取为非基变量（即令这些变量（即令这些xj的值为零），的值为零），所求得的基可行解就使目所求得的基可行解就使目标标函函数数值值最大最大为为z0。 。jjjjxzz0 jjjjxjjjjxzz0 jjjjx在本例题中由于在本例题中由于 1 15050， 2 2100100 ，都大于零，显然，都大于零，显然这个基可行解不是最优解，所以需要找更好的基可行这个基可行解不是最优解，所以需要找更好的基可行解。解。 分析 max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 4

36、00 x2 +s3 = 250 x1, x2, s1, s2, s30。5.1 单纯形法的基本思路和原理5.1 单纯形法的基本思路和原理本例题中本例题中, ,由于初始可行解中由于初始可行解中x x1 1，x x2 2为为非基变量非基变量，而，而x x3 3为为基变量基变量, ,应该应该在约束等式中通过移项处理在约束等式中通过移项处理, ,用用非基变非基变量量来表示来表示基变量基变量, ,得到得到x x3 3 = 5 - = 5 - x x1 1 , ,代入目标函数得到代入目标函数得到z z = 5 + = 5 + x x1 1 + 3 + 3x x2 2 可知可知 1 11 1， 2 23 3

37、， 3 30 0， 4 40 0， 5 50 0。max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0 x1=0,x2=0,x3=5x4=10 x5=45.1 单纯形法的基本思路和原理一、找出一个初始基可行解一、找出一个初始基可行解二、最优性检验二、最优性检验 三、基变换三、基变换 定义定义: :两个基之间变换且仅变换一个基变量两个基之间变换且仅变换一个基变量, ,则称为相邻则称为相邻1000100012b1010010113bx1 x2 s1 s2 s3x1 x2 s1 s2 s3s1 s2 s3s1 s2

38、s3x2 s1 s3x2 s1 s3100100101200111a三、基变换三、基变换 通过检验，可知该初始基可行解不是最优解。通过检验，可知该初始基可行解不是最优解。以下介绍如何进行基变换找到另一个新的可行解，以下介绍如何进行基变换找到另一个新的可行解，具体的做法是从可行基中换一个列向量，得到一个具体的做法是从可行基中换一个列向量，得到一个新的可行基新的可行基. .u使得求解得到的新的基可行解，使得求解得到的新的基可行解，u使得其目标函数值更优。使得其目标函数值更优。为了换基就要确定为了换基就要确定换入变量换入变量与与换出变量换出变量。1 1、入基变量的确定、入基变量的确定p由最优判别定理

39、可知，当某个由最优判别定理可知，当某个 j j 00时，非基变时，非基变量量x xj j变为基变量不取零值可以使目标函数值增大变为基变量不取零值可以使目标函数值增大, ,故故要选基检验数大于要选基检验数大于0的非基变量换到基变量中去的非基变量换到基变量中去（称之为入基变量）。（称之为入基变量）。p若有两个以上的若有两个以上的j 0，则为了使目标函数增加得则为了使目标函数增加得更大些，一般选其中的更大些，一般选其中的j 最大者的非基变量为入最大者的非基变量为入基变量，基变量，5.1 单纯形法的基本思路和原理分析 max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1

40、 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。可知可知 1 15050， 2 2100100， 3 30 0， 4 40 0， 5 50 0。 在本例题中在本例题中 2 2100100是检验数中最大的正数，是检验数中最大的正数，故选故选 x x2 2为入基变量。为入基变量。5.1 单纯形法的基本思路和原理用用非基变量非基变量来表示来表示基变量基变量, ,得到得到x x3 3 = 5 - = 5 - x x1 1 , ,代入目标代入目标函数得到函数得到: :z z = 5 + = 5 + x x1 1 + 3 + 3x x2 2 可知可知 1

41、11 1， 2 23 3， 3 30 0， 4 40 0， 5 50 0。max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0 在本例题中在本例题中 2 23 3是检验数中最大的正数，故是检验数中最大的正数，故选选 x x2 2为入基变量。为入基变量。2、出基变量的确定出基变量的确定 在确定了在确定了x2为入基变量之后，我们要在原来的为入基变量之后，我们要在原来的3个基变量个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？量呢？

42、如果我们确定如果我们确定s1为出基变量，则新的基变量为为出基变量，则新的基变量为x2，s2，s3，因为非，因为非基变量基变量x1s10，则从下式则从下式求得基解：求得基解： x10， x2300，s10，s2100，s350。 显然这不是基可行解，所以显然这不是基可行解，所以s1不能作为出基变量不能作为出基变量。.250,400,30032222sxsxx 如果把如果把s3作为出基变量，则新的基变量为作为出基变量，则新的基变量为x2，s1，s2，因为非基变量因为非基变量x1s30，我们也可以从下式：，我们也可以从下式：求出基解：求出基解： x10， x2250，s150，s2150，s30。

43、因为此解满足非负条件，是基可行解，故因为此解满足非负条件，是基可行解，故s3可以确可以确定为出基变量。定为出基变量。 能否在求出基解以前来确定出基变量呢？能否在求出基解以前来确定出基变量呢？.250,400,30022212xsxsx确定确定出基变量出基变量的方法如下：的方法如下：n把已确定的把已确定的入基变量入基变量在各约束方程中的正的系数除在各约束方程中的正的系数除以其所在约束方程中的以其所在约束方程中的常数项的值常数项的值，n把其中最小比值所在的约束方程中的把其中最小比值所在的约束方程中的原基变量原基变量确定确定为为出基变量出基变量。n这样在下一步迭代的矩阵变换中可以确保新得到的这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。值都大于等于零。 在本例题中约束方程为在本例题中约束方程为 在第二步中已经知道在第二步中已经知道x2为入基变量，把约束方程中的为入基变量，把约束方程中的x2为正的系数除对应的常量，得为正的系数除对应的常量，得.250,4002,30032221121sxsxxsxx2501250400140