《第五章单纯形法1基本思路和原理ppt课件》由会员分享，可在线阅读，更多相关《第五章单纯形法1基本思路和原理ppt课件（60页珍藏版）》请在金锄头文库上搜索。
1、第五章 单纯形法Singlex Method第五章第五章 单纯形法单纯形法由美国数学家丹捷格由美国数学家丹捷格(G.B.Dantzig)(G.B.Dantzig)提出的，得到最提出的，得到最广泛运用的广泛运用的线性性规划的代数算法划的代数算法单纯形法，形法，这恐怕是在运筹恐怕是在运筹学开展史上最学开展史上最辉煌的一笔。煌的一笔。 对于只需两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解. 我我们在第三章所引在第三章所引见的的线性性规划划问题的的计算算机解法就是基于机解法就是基于单纯形法形法编程来程来处理可以理可以含有上千个决策含有上千个决策变量的及上千个
2、量的及上千个约束条件束条件的复的复杂的的线性性规划划问题。第五章第五章 单纯形法单纯形法5.1 单纯形法的根本思绪和原理5.1 单纯形法的根本思绪和原理线性性规划划问题 ()()()(i=1,，m)(j=1,，n)可行解：可行解：满足上述足上述约束条件，的解束条件，的解 ，称称为线性性规划划问题的可行解全部可行解的集合称的可行解全部可行解的集合称为可行域可行域5.1 单纯形法的根本思绪和原理线性规划问题线性规划问题 ()()()(i=1,，m)(j=1,，n)最最优解：解：使目的函数到达最大使目的函数到达最大值的可行解称的可行解称为最最优解解5.1 单纯形法的根本思绪和原理基：基：设为约束方程
3、束方程组的的mnmn阶系数矩系数矩阵，设n nm m，其秩其秩为m m，是矩，是矩阵中的一个中的一个mmmm的的满秩子矩秩子矩阵，称，称是是线性性规划划问题的一个基不失普通性，的一个基不失普通性，设中的每一个列向量中的每一个列向量j jj j，m m称称为基向量，与基向基向量，与基向量量j j对应的的变量量xjxj称称为基基变量。量。线性性规划中除了基划中除了基变量以外的量以外的变量称量称为非基非基变量。量。5.1 单纯形法的根本思绪和原理规范方式为:目的函数：max z = 50x1+100x2+0s1+0s2+0s3约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2
4、= 400 x2 +s3 = 250 x1, x2, s1, s2, s30。这是由三个五元线性方程组成的方程组，它的系数矩阵为: 中的每一个列向量中的每一个列向量p3, p4, p5 p3, p4, p5 是基向量，与其是基向量，与其对应的的变量量s1, s2, s3s1, s2, s3是基是基变量。除了基量。除了基变量以外的量以外的变量量x1, x1, x2x2是非基是非基变量。量。5.1 单纯形法的根本思绪和原理可以看到 s1, s2, s3的系数列向量这是由三个五元线性方程组成的方程组，它的系数矩阵为:是线性独立的,这些向量构成一个基5.1 单纯形法的根本思绪和原理基：基：设为约束方程
5、束方程组的的mnmn阶系数矩系数矩阵，设n nm m，其秩其秩为m m，是矩，是矩阵中的一个中的一个mmmm的的满秩子矩秩子矩阵，称，称是是线性性规划划问题的一个基不失普通性，的一个基不失普通性，设中的每一个列向量中的每一个列向量j jj j，m m称称为基向量，与基向基向量，与基向量量j j对应的的变量量xjxj称称为基基变量。量。线性性规划中除了基划中除了基变量以外的量以外的变量称量称为非基非基变量。量。在此例在此例题中：中： 都是都是该线性性规划的一个基。划的一个基。 这些基都是由些基都是由3 3个个线性无关的系数列向量性无关的系数列向量组成的成的, ,对应的基的基变量量分分别为 x1
6、, x2 , s1 ; s1, s2, s3; x2 ,s1,s2 x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s2。 5.1 单纯形法的根本思绪和原理基解：基解：在在约束方程束方程组E E中，令一切的非基中，令一切的非基变量：量：又由于有又由于有 ，根据克莱姆法那么，由，根据克莱姆法那么，由m m个个约束方程可以解束方程可以解出出m m个基个基变量的独一解量的独一解 。将。将这个解加上非个解加上非基基变量取量取0 0的的值有有 ，称，称X X为线性性规划划问题的基解。的基解。我我们找到找到A A 的一个基的一个基: :令令这个基的非基个基的非基变量量 x1, s2 x
7、1, s2 为零零, , 这时约束方程就束方程就变为基基变量量的的约束方程束方程: :矩矩阵方程方程 AX = b AX = b即即: :求解求解, ,即可得到基即可得到基变量的独一一量的独一一组解解: 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=-150我我们找到找到A A 的一个基的一个基: :令令这个基的非基个基的非基变量量
8、x1, x2 x1, x2 为零零, , 这时约束方程就束方程就变为基基变量量的的约束方程束方程: :矩矩阵方程方程 AX = b AX = b即即: :求解求解, ,即可得到基即可得到基变量的独一一量的独一一组解解: s1=300 , s2=-400 , s3=250: s1=300 , s2=-400 , s3=250加上非基加上非基变量量: x1= 0, x2 = 0, : x1= 0, x2 = 0, 得到此得到此线性性规划的一个基解划的一个基解. .x1=0,x2=0,s1=300s2=400s3=2505.1 单纯形法的根本思绪和原理基解：基解：在约束方程组在约束方程组E E中，令
9、一切的非基变量：中，令一切的非基变量：又由于有又由于有 ，根据克莱姆法那么，由，根据克莱姆法那么，由m m个约束方程可以解个约束方程可以解出出m m个基变量的独一解个基变量的独一解 。将这个解加上非。将这个解加上非基变量取基变量取0 0的值有的值有 ，称，称X X为线性规划问为线性规划问题的基解。题的基解。5.1 单纯形法的根本思绪和原理线性性规划划问题 ()()()(i=1,，m)(j=1,，n)基可行解：基可行解：满足足变量非量非负约束条件束条件 ( G ) ( G ) 的基解称的基解称为基可行解。基可行解。可行基：可行基：对应于基可行解的基称于基可行解的基称为可行基。可行基。我们找到我们
10、找到A A 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 AX = b AX = b即即: :求解求解, ,即可得到基变量的独一一组解即可得到基变量的独一一组解: x2= 400 , s1= -100 , s3= -150: x2= 400 , s1= -100 , s3= -150加上非基变量加上非基变量: x1= 0, s2 = 0, : x1= 0, s2 = 0, 得到此线性规划的一个基解得到此线性规划的一个基解. .x1= 0,x2=
11、400,s1= -100,s2= 0,s3= -150,我们找到我们找到A A 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x2 x1, x2 为零为零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 AX = b AX = b即即: :求解求解, ,即可得到基变量的独一一组解即可得到基变量的独一一组解: s1=300 , s2=-400 , s3=250: s1=300 , s2=-400 , s3=250加上非基变量加上非基变量: x1= 0, x2 = 0, : x1= 0, x2 = 0, 得到此线性规划的一个基
12、解得到此线性规划的一个基解. .x1=0,x2=0,s1=300s2=400s3=250x1=0,x2=0,s1=300s2=400s3=250均为基解均为基解x1= 0,x2= 400,s1= -100,s2= 0,s3= -150,基可行解基可行解不是基可行解不是基可行解均为基均为基可行基可行基不是可行基不是可行基 由于在由于在这个基解中个基解中s1s1100100，s3s3150150，不，不满足足该线性性规划最后一个划最后一个变量非量非负的的约束条件，束条件，显然不是此然不是此线性性规划划的可行解，一个基解可以是可行解，也可以是非可行解，它的可行解，一个基解可以是可行解，也可以是非可行
13、解，它们之之间的主要区的主要区别在于其一切在于其一切变量的解能否量的解能否满足非足非负的条件。的条件。5.1 单纯形法的根本思绪和原理5.1 单纯形法的根本思绪和原理 定理定理: : 线性性规划划问题的基可行解的基可行解 X X 对应线性性规划划问题可行域可行域的的顶点点. . 在在这里，可行域的里，可行域的顶点已不再像点已不再像图解法中那解法中那样直接可直接可见了。在了。在单纯形法中的可行域的形法中的可行域的顶点叫做基可行解，第一点叫做基可行解，第一个找到的可行域的个找到的可行域的顶点叫做初始基可行解。点叫做初始基可行解。 5.1 单纯形法的根本思绪和原理 例：找出下述例：找出下述线性性规划
14、划问题的全部基解，指出其中的的全部基解，指出其中的基可行解，并确定最基可行解，并确定最优解：解：max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0矩矩阵方程方程: :我我们找到找到A A 的一个基的一个基: :令令这个基的非基个基的非基变量量 x1, x2 x1, x2 为零零, , 这时约束方程就束方程就变为基基变量量的的约束方程束方程: :矩矩阵方程方程 AX = b AX = b得到基解得到基解: :x1=0,x2=0,x3=5x4=10x5=4代入目的方程式: max z = 2 x1 + 3 x2
15、+ x3, 得到 Z = 55.1 单纯形法的根本思绪和原理x x1 1x x2 2x x3 3x x4 4x x5 5z z是否基可行是否基可行解解0 00 05 510104 45 50 04 45 52 20 017175 50 00 05 54 410100 05 55 50 0-1-1202010100 0-5-50 04 415155 52.52.50 00 01.51.517.517.55 54 40 0-3-30 022222 24 43 30 00 01919我们找到我们找到A A 的一个基的一个基: :令这个基的非基变量令这个基的非基变量 x1, x5 x1, x5 为零为
16、零, , 这时约束方程就变为基变量这时约束方程就变为基变量的约束方程的约束方程: :矩阵方程矩阵方程 AX = b AX = b得到基解得到基解: :x1=0,x2=4,x3=5x4=2x5=0代入目的方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 17即即: :5.1 单纯形法的根本思绪和原理x x1 1x x2 2x x3 3x x4 4x x5 5z z是否基可行是否基可行解解0 00 05 510104 45 50 04 45 52 20 017175 50 00 05 54 410100 05 55 50 0-1-1202010100 0-5-50 04
17、415155 52.52.50 00 01.51.517.517.55 54 40 0-3-30 022222 24 43 30 00 019195.1 单纯形法的根本思绪和原理单纯形法的根本思形法的根本思绪：从可行域中某一个从可行域中某一个顶点开点开场，判，判别此此顶点能否是最点能否是最优解，解，如不是那么再找另一个使得其目的函数如不是那么再找另一个使得其目的函数值更更优的的顶点，点，称之称之为迭代，再判迭代，再判别此点能否是最此点能否是最优解。解。直到找到一个直到找到一个顶点点为其最其最优解，就是使得其目的函数解，就是使得其目的函数值最最优的解，或者能判的解，或者能判别出出线性性规划划问题
18、无最无最优解解为止。止。5.1 单纯形法的根本思绪和原理 定理定理: : 线性规划问题的基可行解线性规划问题的基可行解 X X 对应线性规划问题对应线性规划问题可行域的顶点可行域的顶点. . 找顶点就是找基可行解找顶点就是找基可行解 5.1 单纯形法的根本思绪和原理一、找出一个初始基可行解一、找出一个初始基可行解 在第二章的例在第二章的例1 1中我中我们得到以下数学模型：得到以下数学模型：例例1.目的函数：目的函数： max z = 50 x1 + 100 x2 约束条件：束条件： s.t. x1 + x2 300 2x1 +x2 400 x2 250 x1 ， x2 05.1 单纯形法的根本
19、思绪和原理规范方式为:目的函数：max z = 50x1+100x2+0s1+0s2+0s3约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。这是由三个五元线性方程组成的方程组，它的系数矩阵为: 普通普通说来判来判别一个基能否是可行基，只需在求出一个基能否是可行基，只需在求出其基解后，当其基解一切其基解后，当其基解一切变量的量的值都是大于等于零，都是大于等于零，才干断定才干断定这个解是基可行解，个解是基可行解，这个基是可行基。个基是可行基。一、找出一个初始基可行解一、找出一个初始基可行解 5.
20、1 单纯形法的根本思绪和原理我们找到我们找到A A 的一个基的一个基: :令令这个基的非基个基的非基变量量 x1, s2 x1, s2 为零零, , 这时约束方程就束方程就变为基基变量量的的约束方程束方程: :矩阵方程矩阵方程 AX = b AX = b即即: :求解求解, ,即可得到基即可得到基变量的独一一量的独一一组解解: x2= 400 , s1= -100 , s3= -150: x2= 400 , s1= -100 , s3= -150加上非基加上非基变量量: x1= 0, s2 = 0, : x1= 0, s2 = 0, 得到此得到此线性性规划的一个基解划的一个基解. .x1= 0
21、,x2= 400,s1= -100,s2= 0,s3= -150,5.1 单纯形法的根本思绪和原理由于在由于在线性性规划的划的规范型中要求范型中要求 bj bj 大于等于零，大于等于零，假假设能找到一个基是能找到一个基是单位矩位矩阵，或者，或者说一个基是由一个基是由单位矩位矩阵的各列向量所的各列向量所组成至于各列向量的前后成至于各列向量的前后顺序无关序无关紧要的那么要的那么显然所求得的基解一定是基然所求得的基解一定是基可行解可行解. .一、找出一个初始基可行解一、找出一个初始基可行解 我我们找到找到A A 的一个基的一个基: :令令这个基的非基个基的非基变量量 x1, x2 x1, x2 为零
22、零, , 这时约束方程就束方程就变为基基变量量的的约束方程束方程: :矩阵方程矩阵方程 AX = b AX = b即即: :求解求解, ,即可得到基即可得到基变量的独一一量的独一一组解解: s1=300 , s2=-400 , s3=250: s1=300 , s2=-400 , s3=250加上非基加上非基变量量: x1= 0, x2 = 0, : x1= 0, x2 = 0, 得到此得到此线性性规划的一个基解划的一个基解. .x1=0,x2=0,s1=300s2=400s3=250我我们找到找到A A 的一个基的一个基: :令令这个基的非基个基的非基变量量 x1, x2 x1, x2 为零
23、零, , 这时约束方程就束方程就变为基基变量量的的约束方程束方程: :矩阵方程矩阵方程 AX = b AX = b得到基解得到基解: :x1=0,x2=0,x3=5x4=10x5=4代入目的方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 5n这个个单位矩位矩阵或由或由单位矩位矩阵各列向量各列向量组成的基一定成的基一定是可行基。是可行基。n实践上践上这个基可行解中的各个个基可行解中的各个变量或等于某个量或等于某个 bj bj 或等于零。或等于零。 5.1 单纯形法的根本思绪和原理一、找出一个初始基可行解一、找出一个初始基可行解 5.1 单纯形法的根本思绪和原理单纯形法
24、的根本思形法的根本思绪：从可行域中某一个从可行域中某一个顶点开点开场，判，判别此此顶点能否是最点能否是最优解，解，如不是那么再找另一个使得其目的函数如不是那么再找另一个使得其目的函数值更更优的的顶点，点，称之称之为迭代，再判迭代，再判别此点能否是最此点能否是最优解。解。直到找到一个直到找到一个顶点点为其最其最优解，就是使得其目的函数解，就是使得其目的函数值最最优的解，或者能判的解，或者能判别出出线性性规划划问题无最无最优解解为止。止。5.1 单纯形法的根本思绪和原理一、找出一个初始基可行解一、找出一个初始基可行解二、最二、最优性性检验 所所谓最最优性性检验就是判就是判别已求得的基可行解能否已求
25、得的基可行解能否是最是最优解。解。5.1 单纯形法的根本思绪和原理二、最优性检验二、最优性检验 1、最优性检验的根据检验数 j 普通来说目的函数中既包括基变量，又包括非基变量,如今我们要求只用非基变量来表示目的函数.max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0max z = 50x1+100x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。5.1 单纯形法的根本思绪和原理1、最优性检验的根据检验数 j 普通来
26、说目的函数中既包括基变量，又包括非基变量,如今我们要求只用非基变量来表示目的函数.在约束等式中经过移项等处置就,用非基变量来表示基变量，用非基变量的表示式替代目的函数中基变量，目的函数中只含有非基变量.此时目的函数中一切变量的系数即为各变量的检验数，把变量xi的检验数记为i。5.1 单纯形法的根本思绪和原理分析 max z = 50x1+100x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。本例本例题中中, ,由于初始可行解中由于初始可行解中x1x1，x2x2为非基非基变量，所以量，所以此目的函数
27、曾此目的函数曾经用非基用非基变量表示了，不需求再代量表示了，不需求再代换出出基基变量了。量了。可知可知 1 15050， 2 2100100， 3 30 0， 4 40 0， 5 50 0。5.1 单纯形法的根本思绪和原理本例本例题中中, ,由于初始可行解中由于初始可行解中x1x1，x2x2为非基非基变量，而量，而x3x3为基基变量量, ,应该在在约束等式中束等式中经过移移项处置置, ,用非基用非基变量量来表示基来表示基变量量, ,得到得到x3 = 5 - x1 ,x3 = 5 - x1 ,代入目的函数得到代入目的函数得到z = 5 + x1 + 3x2 z = 5 + x1 + 3x2 可知
28、可知 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、最优解判别定理 对于求最大目的函数的问题中，对于某个基可行解，假设一切检验数j 0，那么这个基可行解是最优解。5.1 单纯形法的根本思绪和原理2 2、最优解判别定理、最优解判别定理设用非基用非基变量表示的目的函数量表示的目的函数为如下方式如下方式其中，其中，z0z0为常数常数项，J
29、J是一切非基是一切非基变量的下量的下标集。由于一切的集。由于一切的xjxj的取的取值范范围为大于等于零，当一切的大于等于零，当一切的 j j都小于等于零都小于等于零时，可知可知 是一个小于等于零的数，要使是一个小于等于零的数，要使 的的值最大，最大，显然只然只 有有为零。我零。我们把把这些些xjxj取取为非基非基变量即令量即令这些些xjxj的的值为零，所求得的基可行解就使目的函零，所求得的基可行解就使目的函数数值最大最大为z0z0。在本例题中由于在本例题中由于1 15050，2 2100 100 ，都大于零，显，都大于零，显然这个基可行解不是最优解，所以需求找更好的基可然这个基可行解不是最优解
30、，所以需求找更好的基可行解。行解。 分析 max z = 50x1+100x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。5.1 单纯形法的根本思绪和原理5.1 单纯形法的根本思绪和原理本例题中本例题中, ,由于初始可行解中由于初始可行解中x1x1，x2x2为非基变量，而为非基变量，而x3x3为基变量为基变量, ,应该在约束等式中经过移项处置应该在约束等式中经过移项处置, ,用非基变用非基变量来表示基变量量来表示基变量, ,得到得到x3 = 5 - x1 ,x3 = 5 - x1 ,代入目的函数得
31、代入目的函数得到到z = 5 + x1 + 3x2 z = 5 + x1 + 3x2 可知可知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 0x1=0,x2=0,x3=5x4=10x5=45.1 单纯形法的根本思绪和原理一、找出一个初始基可行解一、找出一个初始基可行解二、最二、最优性性检验 三、基三、基变换 定定义: :两个基之两个基之间变换且且仅变换一个基一个基变量量, ,那么称那么称为相相邻x1 x2 s1 s2 s3x1 x2 s1
32、 s2 s3s1 s2 s3s1 s2 s3x2 s1 s3x2 s1 s3三、基变换三、基变换 经过检验，可知该初始基可行解不是最优解。经过检验，可知该初始基可行解不是最优解。以下引见如何进展基变换找到另一个新的可行解，以下引见如何进展基变换找到另一个新的可行解，详细的做法是从可行基中换一个列向量，得到一个详细的做法是从可行基中换一个列向量，得到一个新的可行基新的可行基. .使得求解得到的新的基可行解，使得求解得到的新的基可行解，使得其目的函数值更优。使得其目的函数值更优。为了换基就要确定换入变量与换出变量。为了换基就要确定换入变量与换出变量。1 1、入基变量确实定、入基变量确实定由最优判别
33、定理可知，当某个由最优判别定理可知，当某个j 0j 0时，非基变量时，非基变量xjxj变为基变量不取零值可以使目的函数值增大变为基变量不取零值可以使目的函数值增大, ,故故要选基检验数大于要选基检验数大于0 0的非基变量换到基变量中去的非基变量换到基变量中去称之为入基变量。称之为入基变量。假设有两个以上的假设有两个以上的j 0j 0，那么为了使目的函数添，那么为了使目的函数添加得更大些，普通选其中的加得更大些，普通选其中的j j 最大者的非基变量最大者的非基变量为入基变量，为入基变量，5.1 单纯形法的根本思绪和原理分析 max z = 50x1+100x2 x1 + x2 +s1 = 300
34、 2x1 + 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是检验数中最大的正数，是检验数中最大的正数，应选应选 x2 x2为入基变量。为入基变量。5.1 单纯形法的根本思绪和原理用非基变量来表示基变量用非基变量来表示基变量, ,得到得到x3 = 5 - x1 ,x3 = 5 - x1 ,代入目代入目的函数得到的函数得到: :z = 5 + x1 + 3x2 z = 5 + x1 + 3x2 可知可知 1 11
35、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是检验数中最大的正数，应是检验数中最大的正数，应选选 x2 x2为入基变量。为入基变量。2、出基变量确实定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？假设我们确定s1为出基变量，那么新的基变量为x2，s2，s3，由于非基变量x1s10，那么从下式求得基解： x10， x230
36、0，s10，s2100，s350。 显然这不是基可行解，所以s1不能作为出基变量。 假假设把把s3作作为出基出基变量，那么新的基量，那么新的基变量量为x2， ，s1， ，s2，由于非基，由于非基变量量x1s30，我，我们也可以从下式：也可以从下式：求出基解：求出基解： x10， ， x2250， ，s150， ，s2150， ，s30。 。 由于此解由于此解满足非足非负条件，是基可行解，故条件，是基可行解，故s3可以确定可以确定为出基出基变量。量。 能否在求出基解以前来确定出基能否在求出基解以前来确定出基变量呢？量呢？确定出基变量的方法如下：确定出基变量的方法如下：把已确定的入基变量在各约束方
37、程中的正的系数除以把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为把其中最小比值所在的约束方程中的原基变量确定为出基变量。出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的这样在下一步迭代的矩阵变换中可以确保新得到的 bj bj 值都大于等于零。值都大于等于零。 在本例在本例题中中约束方程束方程为 在第二步中曾在第二步中曾经知道知道x2为入基入基变量，把量，把约束方程中的束方程中的x2为正的系数除正的系数除对应的常量，得的常量，得确定出基变量的方法如下：确定出基变量的方法如下：把已确定的
38、入基变量在各约束方程中的正的系数除以把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为把其中最小比值所在的约束方程中的原基变量确定为出基变量。出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的这样在下一步迭代的矩阵变换中可以确保新得到的 bj bj 值都大于等于零。值都大于等于零。5.1 单纯形法的根本思绪和原理一、找出一个初始基可行解一、找出一个初始基可行解二、最二、最优性性检验 三、基三、基变换 x1 x2 s1 s2 s3x1 x2 s1 s2 s3s1 s2 s3s1 s2 s3x
39、2 s1 s2x2 s1 s2 其中其中b3/a32的的值最小，所以可以知道在原基最小，所以可以知道在原基变量中系数向量量中系数向量为e3=(0, 0,1)T的基的基变量量s3为出基出基变量，量，这样可知可知x2， ，s1， ，s2为基基变量，量， x1， ，s3为非基非基变量。量。令非基令非基变量量为零，得：零，得： 求解得到新的基可行解：求解得到新的基可行解： x10， ， x2250， ，s150， ，s2150， ，s30。 。目的函数目的函数值为点点 50 x1+100 x225005.1 单纯形法的根本思绪和原理一、找出一个初始基可行解一、找出一个初始基可行解二、最二、最优性性检验
40、 三、基三、基变换 5.1 单纯形法的根本思绪和原理max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0 在本例题中在本例题中 2 23 3是检验数中最大的正数，应是检验数中最大的正数，应选选 x2 x2为入基变量。把约束方程中的为入基变量。把约束方程中的x2x2为正的系数为正的系数除对应的常量，得除对应的常量，得 其中其中b3/a32的的值最小，所以可以知道在原基最小，所以可以知道在原基变量中量中系数向量系数向量为p5=(0, 0,1)T的基的基变量量x5为出基出基变量，量，这样可知可知x2， ，x3， ，x4为基基变量，量， x1， ，x5为非基非基变量。令非基量。令非基变量量为零，得：零，得：求解得到新的基可行解：求解得到新的基可行解： x10， ， x24， ，x35， ，x42， ，x50。 。目的函数目的函数值为 3x2+x317 x3 = 5 2x2 +x4 =10 x2 =4max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0
