资源描述：
《单纯形法（1基本思路和原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章单纯形法SinglexMethod第五章单纯形法由美国数学家丹捷格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代数算法－－单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解.我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。第五章单纯形法5.1单纯形法的基本思路和原理§5.1单纯形法的基本思路和原理线性规划问题(Ｅ)(Ｆ)(Ｇ)(i=1,…，m)(j=1,…，n)可行解：满足上述约束条件（Ｆ）
2、，（Ｇ）的解 ，称为线性规划问题的可行解．全部可行解的集合称为可行域．§5.1单纯形法的基本思路和原理线性规划问题(Ｅ)(Ｆ)(Ｇ)(i=1,…，m)(j=1,…，n)最优解：使目标函数（Ｅ）达到最大值的可行解称为最优解．§5.1单纯形法的基本思路和原理基：设Ａ为约束方程组（Ｆ）的m×n阶系数矩阵，（设n＞m），其秩为m，Ｂ是矩阵Ａ中的一个m×m的满秩子矩阵，称Ｂ是线性规划问题的一个基．不失一般性，设Ｂ中的每一个列向量Ｐj（j＝１，…，m）称为基向量，与基向量Ｐj对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。§5.1单纯形法的基本思路和原理标准形式为:
3、目标函数：maxz=50x1+100x2+0s1+0s2+0s3约束条件：x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0。这是由三个五元线性方程组成的方程组，它的系数矩阵为:Ｂ中的每一个列向量p3,p4,p5是基向量，与其对应的变量s1,s2,s3是基变量。除了基变量以外的变量x1,x2是非基变量。§5.1单纯形法的基本思路和原理可以看到s1,s2,s3的系数列向量这是由三个五元线性方程组成的方程组，它的系数矩阵为:是线性独立的,这些向量构成一个基§5.1单纯形法的基本思路和原理基：设Ａ为约束方程组（Ｆ）的m×n阶系数矩阵，（设n＞m
4、），其秩为m，Ｂ是矩阵Ａ中的一个m×m的满秩子矩阵，称Ｂ是线性规划问题的一个基．不失一般性，设Ｂ中的每一个列向量Ｐj（j＝１，…，m）称为基向量，与基向量Ｐj对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。在此例题中：都是该线性规划的一个基。这些基都是由3个线性无关的系数列向量组成的,对应的基变量分别为x1,x2,s1;s1,s2,s3;x2,s1,s2。§5.1单纯形法的基本思路和原理基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。我们找到A
5、的一个基:令这个基的非基变量x1,s2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b即:求解,即可得到基变量的唯一一组解:x2=400,s1=-100,s3=-150加上非基变量:x1=0,s2=0,得到此线性规划的一个基解.x1=0,x2=400s1=-100s2=0s3=-150我们找到A的一个基:令这个基的非基变量x1,x2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b即:求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.x1=0,x2=0,s1=300s2=400s3=2
6、50§5.1单纯形法的基本思路和原理基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。§5.1单纯形法的基本思路和原理线性规划问题(Ｅ)(Ｆ)(Ｇ)(i=1,…，m)(j=1,…，n)基可行解：满足变量非负约束条件(G)的基解称为基可行解。可行基：对应于基可行解的基称为可行基。我们找到A的一个基:令这个基的非基变量x1,x2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b即:求解,即可得到基变量的唯一一组解:x2=400,s1=-100,s3=-150加上非
7、基变量:x1=0,s2=0,得到此线性规划的一个基解.x1=0,x2=400,s1=-100,s2=0,s3=-150,我们找到A的一个基:令这个基的非基变量x1,x2为零,这时约束方程就变为基变量的约束方程:矩阵方程AX=b即:求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.x1=0,x2=0,s1=300s2=400s3=250x1=0,x2
