二章二节单纯形法

第二节 单纯形法单纯形法是求解线性规划的主要算法， 1947年由美国斯坦福大学教授丹捷格（ G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的 “ 市场 ” 占有率。1.线性规划的标准型用单纯形法求解线性规划的前提是先将模型化为标准型：标准型的特征： Max型、等式约束、非负约束一、单纯形法的预备知识标准型的矩阵表示：称为 决策变量向量 ， 称为 价格系数向量 , 称为 技术系数矩阵 , 称为 资源限制向量 。其中非 标准形式如何化为标准型？1) Min型化为 Max型 加负号因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意： Min型化为 Max型求解后，最优解不变，但最优值差负号。 如原问题 可化为2) 对 约束，可添加 松弛变量 构成等式约束分析： 以例 1中煤的约束为例之所以 “ 不等 ” 是因为左右两边有一个差额，称为 “ 松弛量 ” ，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为 X3 ， 则有问题： 它的实际意义是什么？X3称为松弛变量，它的价格系数 c3=0。 煤资源的 “ 剩余 ” 。3) 对 约束，可添加 剩余变量 构成等式约束例如，对约束减去剩余变量 x40，构成等式约束同样，剩余变量的价格系数 c4=0。4) 当模型中有某变量 xk 没有非负要求，称为自由 变量 , 则可令 5） 若某一常数项 b i0这时只要在 b i相对应的约束方程两边乘上 -1。6) 若 x0,则令 x= -x练习 1：请将例 1的约束化为标准型解：增加松弛变量 则 约束化为易见，增加的松弛变量的系数恰构成一个单位阵 I。一般地，记松弛变量的向量为 Xs， 则问题：松弛变量在目标中的系数为何？ 0 。练习 2：将下面非标准线性规划化为等价的标准型 将目标函数转化为求极大型，即 得 对第一个约束添加松弛变量 x40，得 对第二个约束减去剩余变量 x50，得 对自由变量 x3，令min z= - x1+3x2-7x3max z= x1 - 3x2+7x3x1 - 2x2 + 3x3 + x4 = 72x1 - x2 + x3 x5 = 4x3 = x3 - x3 ， x30， x3 0原规划化为标准型：max z= x1 - 3x2+7x3- 7x3练习 2：将下面非标准线性规划化为等价的标准型min z= - x1+3x2-7x3练习 3： minZ=x1+2x2-3x3x1+x2+x3 9-x1-2x2+x3 2 3x1+x2-3x3=5 x10， x20，x3无约束令 x1=-x1， x3=x3 -x3“ Z=-Z。maxZ=x1-2x2 3(x3- x3“)-x1+x2+x3- x3“ x4 =9x1-2x2+ x3- x3“ - x5 = 2-3 x1 +x2-3(x3- x3“ ) =5x1 x2 x3 x3 “ x4 x5 0标准型为 :2.基本概念（ 1）可行解与最优解直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。假设 nm，且系数矩阵的秩为 m，用 Pj表示 A中第 j列的列向量，即由此，矩阵 A可表示为 A=P1 P2 Pn（ 2）基矩阵与基变量基向量 ：基 B中的列；其余称非基向量。基变量 ：与基向量 Pj对应的决策变量 xj， 记其组成的 向量为 XB；非基变量 ：与非基向量对应的变量称非基变量，记其组成的向量为 XN。基矩阵 (基 )： 设 A是 mn 阶约束系数矩阵 （ mn ） ,秩为 m。 A=（ P1,P2, Pn ） ,则 A中 m阶可逆子阵B=（ P1,P2,P m ） 为线性规划的一个 基 。 其余部分称为 非基矩阵 ，记为 N 6 个。一般地， m n 阶矩阵 A中基的个数最多有多少个？问题：本例的 A中一共有几个基？p16（ 3）基本解与基本可行解当 A中的基 B取定后，不妨设 B表示中的前 m列，则可记A=（ B N） ,相应地 X= (XB XN)T约束中的 AX=b 可表示为即当取 XN=0时，有可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为 基本可行解 （简称基可行解），对应于基可行解的基称为 可行基 。例 4：在上例中求相应于基 B1和 B2的基本解，它们是否基本可行解？上二组概念间的联系：系数阵 A中可找出若干个基 B每个基 B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：可行解 基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？3.基本定理（ 1）线性规划的可行域是一个 凸 多面体。（ 2）线性规划的最优解（若存在的话）必能在可行域的 角点 获得。（ 3）线性规划可行域的 角点 与 基本可行解 一一对应。因此，在角点中寻找最优点即可转化为在所有基本可行解中寻找最优解。因此，只需考虑所有基本可行解就够了二、单纯形法的步骤单纯形法是一种迭代的算法，它的思想是在可行域的角点 基本可行解中寻优。由于角点是有限个 （为什么？ ），因此，算法经有限步可终止。1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，确定初始基可行解 X0相当于确定一个初始可行基 B0。问题：若 B0=I，则 X0=？方法： 若 A中含 I， 则 B0=I， 由此可得初始基本可行解若 A中不含 I， 则可用人工变量法构造一个 I。2. 最优性检验问题：用什么检验？ 把目标函数用 非基变量 表示。因此，对给定的一个可行基 B(即给定一个基本可行解 XB=B-1b, XN=0)，判别它是否最优，（ 2）若所有 j0时，这个基本可行解为优；反之，若有某一检验数 k 0，则此解一定不是最优 , 转 3。2. 最优性检验（续）（ 1）只需计算每一非基变量 x j 的检验数z3. 寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基 B0变换为下一个新的基 B1， 因此，本步骤也称为基变换。（基变换）进基出基以例 1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（ 1）先将模型化为标准型(2) 确定初始基可行解、检验以例 1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（ 1）先将模型化为标准型(2) 确定初始基可行解、检验（ 3）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。练习：对于下面的线性规划（ 1）用图解法求解；（ 2）将模型化为标准型；（ 3）用单纯形法步骤求出其最优解，并指出求解过程