第五章单纯形法 §1单纯形法的基本思路和原理 §2单纯形法的表格形式 §3求目标函数值最小的线性规划的问题的 单纯形表解法 ·§4几种特殊情况 管理蓦
管 理 运 筹 学 1 第五章 单 纯 形 法 • §1 单纯形法的基本思路和原理 • §2 单纯形法的表格形式 • §3 求目标函数值最小的线性规划的问题的 单纯形表解法 • §4 几种特殊情况
§1单纯形法的基本思路和原理 单纯形法的基本思路:从可行域中某一个顶点开始,判断此顶点是否是最优 解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此 点是否是最优解。直到找到一个顶点为其最优解,就是使得其目标函数值最优的 解,或者能判断出线性规划问题无最优解为止 通过第二章例1的求解来介绍单纯形法 在加上松弛变量之后我们可得到标准型如下: 目标函数:max50x1+100x 约束条件:x1+x2+s1=300, 2x1+x2+s2=400, x2+s3=250 X;≥0(j=1,2),s;≥0(j=1,2,3) 管理蓦
管 理 运 筹 学 2 §1 单纯形法的基本思路和原理 单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优 解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此 点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的 解，或者能判断出线性规划问题无最优解为止。 通过第二章例1的求解来介绍单纯形法: 目标函数： max 50x1 +100x2 约束条件：x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250. xj≥0 （j=1，2）,sj≥0 （j=1，2,3）
§1单纯形法的基本思路和原理 它的系数矩阵 00 A=(n1,P2P3P4,P3)=21010 01001 其中p;为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变 量的个数n,为了找到一个初始基本可行解,先介绍以下几个线性规划的 基本概念。 基:已知A是约東条件的m×n系数矩阵,其秩为m。若B是A中m×m阶非 奇异子矩阵(即可逆矩阵),则称B是线性规划问题中的一个基。 基向量:基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量:在A中除了基B之外的一列则称之为基B的非基向量。 基变量:与基向量p;相应的变量x,叫基变量,基变量有m个。 管理蓦
管 理 运 筹 学 3 它的系数矩阵 , 其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变 量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的 基本概念。 基： 已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非 奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。 §1 单纯形法的基本思路和原理 = = 0 1 0 0 1 2 1 0 1 0 1 1 1 0 0 ( , , , , ) A p1 p2 p3 p4 p5
§1单纯形法的基本思路和原理 非基变量:与非基向量p;相应的变量x,叫非基变量,非基变量有n-m个 由线性代数的知识知道,如果我们在约束方程组系数矩阵中找到一个 基,令这个基的非基变量为零,再求解这个m元线性方程组就可得到唯 的解了,这个解我们称之为线性规划的基本解。 在此例中我们不妨找到了 10)为A的一个基,令这个基的 B3=100 非基变量x1,S2为零。这时约束方程就变为基变量的约束方程 管理蓦 4
管 理 运 筹 学 4 非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。 由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个 基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一 的解了，这个解我们称之为线性规划的基本解。 在此例中我们不妨找到了 为A的一个基，令这个基的 非基变量x１，s2为零。这时约束方程就变为基变量的约束方程： = 1 0 1 1 0 0 1 1 0 B3 §1 单纯形法的基本思路和原理
§1单纯形法的基本思路和原理 x2+s1=300, x2=400, x+s2=250. 求解得到此线性规划的一个基本解: x1=0,x。=400,s1=-10 0 150 由于在这个基本解中s1=-100,s3=-150,不满足该线性规划s1≥0, 2≥0的约束条件,显然不是此线性规划的可行解,一个基本解可以是 可行解,也可以是非可行解,它们之间的主要区别在于其所有变量的解 是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行 解,并把这样的基叫做可行基。 管理蓦
管 理 运 筹 学 5 x2+s1=300， x2 =400， x2 +s3 =250. x1 =0，x2 =400，s1 =－100，s2 =0，s3 =－150 由于在这个基本解中s1 =－100，s3 =－150，不满足该线性规划s1≥0， s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是 可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解 是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行 解，并把这样的基叫做可行基。 §1 单纯形法的基本思路和原理