第二章-单纯形法(1基本思路和原理)

第二章单纯形法SinglexMethod第二章单纯形法由美国数学家丹捷格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代数算法－－单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解.我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。第五章单纯形法5.1单纯形法的基本思路和原理§5.1单纯形法的基本思路和原理线性规划问题0max11jnjijijnjjjxbxaxcz(Ｅ)(Ｆ)(Ｇ)(i=1,…，m)(j=1,…，n)可行解：满足上述约束条件（Ｆ），（Ｇ）的解，称为线性规划问题的可行解．全部可行解的集合称为可行域．TnxxX,,1§5.1单纯形法的基本思路和原理线性规划问题0max11jnjijijnjjjxbxaxcz(Ｅ)(Ｆ)(Ｇ)(i=1,…，m)(j=1,…，n)最优解：使目标函数（Ｅ）达到最大值的可行解称为最优解．§5.1单纯形法的基本思路和原理基：设Ａ为约束方程组（Ｆ）的m×n阶系数矩阵，（设n＞m），其秩为m，Ｂ是矩阵Ａ中的一个m×m的满秩子矩阵，称Ｂ是线性规划问题的一个基．不失一般性，设mmmmmaaaaPPB11111,,Ｂ中的每一个列向量Ｐj（j＝１，…，m）称为基向量，与基向量Ｐj对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。§5.1单纯形法的基本思路和原理标准形式为:目标函数：maxz=50x1+100x2+0s1+0s2+0s3约束条件：x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0。这是由三个五元线性方程组成的方程组，它的系数矩阵为:.100100101200111),,,,(54321pppppAＢ中的每一个列向量p3,p4,p5是基向量，与其对应的变量s1,s2,s3是基变量。除了基变量以外的变量x1,x2是非基变量。§5.1单纯形法的基本思路和原理.1005p.0013p可以看到s1,s2,s3的系数列向量这是由三个五元线性方程组成的方程组，它的系数矩阵为:.0104p.100100101200111),,,,(54321pppppA是线性独立的,这些向量构成一个基100010001,,543pppB§5.1单纯形法的基本思路和原理基：设Ａ为约束方程组（Ｆ）的m×n阶系数矩阵，（设n＞m），其秩为m，Ｂ是矩阵Ａ中的一个m×m的满秩子矩阵，称Ｂ是线性规划问题的一个基．不失一般性，设mmmmmaaaaPPB11111,,Ｂ中的每一个列向量Ｐj（j＝１，…，m）称为基向量，与基向量Ｐj对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。在此例题中：都是该线性规划的一个基。.100100101200111),,,,(54321pppppA这些基都是由3个线性无关的系数列向量组成的,对应的基变量分别为x1,x2,s1;s1,s2,s3;x2,s1,s3。010012111100010001101001011§5.1单纯形法的基本思路和原理基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。021nmmxxx0BTmbxxX,,1TmbxxX0,,0,,,11010010113B25040030010010010120011132121sssxx我们找到A的一个基:令这个基的非基变量x1,s2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b25040030000100100101200111312ssx25040030032212sxxsx即:求解,即可得到基变量的唯一一组解:x2=400,s1=-100,s3=-150加上非基变量:x1=0,s2=0,得到此线性规划的一个基解.x1=0,x2=400s1=-100s2=0s3=-1501000100012B25040030010010010120011132121sssxx我们找到A的一个基:令这个基的非基变量x1,s2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b25040030000100100101200111321sss250400300321sss即:求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.x1=0,x2=0,s1=300s2=400s3=250§5.1单纯形法的基本思路和原理基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。021nmmxxx0BTmbxxX,,1TmbxxX0,,0,,,1§5.1单纯形法的基本思路和原理线性规划问题0max11jnjijijnjjjxbxaxcz(Ｅ)(Ｆ)(Ｇ)(i=1,…，m)(j=1,…，n)基可行解：满足变量非负约束条件(G)的基解称为基可行解。可行基：对应于基可行解的基称为可行基。1010010113B25040030010010010120011132121sssxx我们找到A的一个基:令这个基的非基变量x1,x2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b25040030000100100101200111312ssx25040030032212sxxsx即:求解,即可得到基变量的唯一一组解:x2=400,s1=-100,s3=-150加上非基变量:x1=0,s2=0,得到此线性规划的一个基解.x1=0,x2=400,s1=-100,s2=0,s3=-150,1000100012B25040030010010010120011132121sssxx我们找到A的一个基:令这个基的非基变量x1,x2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b25040030000100100101200111321sss250400300321sss即:求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.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,基可行解不是基可行解1010010113B1000100012B均为基可行基不是可行基由于在这个基解中s1＝－100，s3＝－150，不满足该线性规划最后一个变量非负的约束条件，显然不是此线性规划的可行解，一个基解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。§5.1单纯形法的基本思路和原理§5.1单纯形法的基本思路和原理定理:线性规划问题的基可行解X对应线性规划问题可行域的顶点.在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基可行解，第一个找到的可行域的顶点叫做初始基可行解。§5.1单纯形法的基本思路和原理例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解：maxz=2x1+3x2+x3x1+x3=5x1+2x2+x4=10x2+x5=4x1-5≥0410510010010210010154321xxxxx矩阵方程:1000100011B我们找到A的一个基:令这个基的非基变量x1,x2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b410500100100102100101543xxx得到基解:x1=0,x2=0,x3=5x4=10x5=4410510010010210010154321xxxxx代入目标方程式:maxz=2x1+3x2+x3,得到Z=5§5.1单纯形法的基本思路和原理x1x2x3x4x5z是否基可行解①0051045√②0452017√③5005410√④0550-120×⑤100-50415×⑥52.5001.517.5√⑦540-3022×⑧2430019√0011020102B410510010010210010154321xxxxx410500100100102100101432xxx我们找到A的一个基:令这个基的非基变量x1,x5为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b得到基解:x1=0,x2=4,x3=5x4=2x5=0代入目标方程式:maxz=2x1+3x2+x3,得到Z=17410252423xxxx即:§5.1单纯形法的基本思路和原理x1x2x3x4x5z是否基可行解①0051045√②0452017√③5005410√④0550-120×⑤100-50415×⑥52.5001.517.5√⑦540-3022×⑧2430019√§5.1单纯形法的基本思路和原理单纯形法的基本思路：•从可行域中某一个顶点开始，判断此顶点是否是最优解，•如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。•直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。§5.1单纯形法的基本思路和原理定理:线性规划问题的基可行解X对应线性规划问题可行域的顶点.找顶点就是找基可行解§5.1单纯形法的基本思路和原理一、找出一个初始基可行解在第二章的例1中我们得到以下数学模型：例1.目标函数：maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0§5.1单纯形法的基本思路和原理标准形式为:目标函数：maxz=50x1+100x2+0s1+0s2