运筹学 二章二节单纯形法

null第二节 单纯形法第二节 单纯形法 单纯形法是求解线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 的主要算法，1947 年由美国斯坦福大学教授丹捷格（G.B.Danzig） 提出。 尽管在其后的几十年中，又有一些算法问世， 但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率。null1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型： 标准型的特征：Max型、等式约束、非负约束一、单纯形法的预备知识null标准型的矩阵表示：其中null非标准形式如何化为标准型？1) Min型化为Max型 加负号 因为，求一个函数 的极小点，等价于求该 函数的负函数的极大点。注意： Min型化为Max型求解后，最优解不变，但最优值差负号。 如原问题可化为null2) 对≤约束，可添加松弛变量构成等式约束 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：以例1中煤的约束为例之所以“不等”是因为左右两边有一个差额，称为“松 弛量”，若在左边加上这个松弛量，则化为等式。而这 个松弛量也是变量，记为X3 ，则有问题：它的实际意义是什么？ X3称为松弛变量，它的价格系数c3=0。 —— 煤资源的“剩余”。null3) 对≥约束，可添加剩余变量构成等式约束例如，对约束减去剩余变量x4≥0，构成等式约束同样，剩余变量的价格系数c4=0。5）若某一常数项 b i<0这时只要在b i相对应的约 束方程两边乘上-1。 6) 若x≤0,则令x′= -x null练习1：请将例1的约束化为标准型易见，增加的松弛变量的系数恰构成一个单位阵I。null一般地，记松弛变量的向量为 Xs，则问题：松弛变量在目标中的系数为何？—— 0。null练习2：将下面非标准线性规划化为等价的标准型①将目标函数转化为求极大型，即得②对第一个约束添加松弛变量x4≥0，得③对第二个约束减去剩余变量x5≥0，得④对自由变量 x3，令min z= - x1+3x2-7x3max z′= x1 - 3x2+7x3x1 - 2x2 + 3x3 + x4 = 72x1 - x2 + x3 – x5 = 4x3 = x3′ - x3〞， x3′≥0，x3〞≥0null原规划化为标准型：max z′= x1 - 3x2+7x3′- 7x3″练习2：将下面非标准线性规划化为等价的标准型min z= - x1+3x2-7x3练习3：练习3：minZ=x1+2x2-3x3 x1+x2+x3 ≤9 -x1-2x2+x3 ≥2 3x1+x2-3x3=5 x1≤0，x2≥0， x3无约束令x1=-x1'，x3=x3' -x3" Z=-Z'。maxZ'=x1'-2x2＋3(x3'- x3") -x1'+x2+x3'- x3"＋x4 =9 x1'-2x2+ x3'- x3" - x5 = 2 -3 x1' +x2-3(x3'- x3" ) =5 x1 ' x2 x3' x3 " x4 x5 ≥0标准型为:2.基本概念2.基本概念（1）可行解与最优解 直观上，可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优的方案。null假设n≥m，且系数矩阵的秩为m，用Pj表示A中第j列的列向量，即由此，矩阵A可表示为A=[P1 P2 … Pn]（2）基矩阵与基变量（2）基矩阵与基变量基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB； 非基变量：与非基向量对应的变量称非基变量，记其 组成的向量为XN。基矩阵(基)：设A是m×n阶约束系数矩阵（m≤n）,秩为m。 A=（ P1,P2,…,Pn ）,则A中m阶可逆子阵 B=（ P1,P2,…,Pm ）为线性规划的一个基。其余部分称为非基矩阵，记为N null—— 6个。一般地，m×n 阶矩阵A中基的个数最多有多少个？问题：本例的A中一共有几个基？p16null（3）基本解与基本可行解当A中的基B取定后，不妨设B表示中的前m列，则可记A=（B N）,相应地 X= (XB XN)T即当取XN=0时，有可见：一个基本解是由一个基决定的。 注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解（简称基可行解）， 对应于基可行解的基称为可行基。null例4：在上例中求相应于基B1和B2的基本解，它们是否基本可行解？上二组概念间的联系：上二组概念间的联系：几种解之间的关系：问题：基本可行解是可行域中的哪些点？3.基本定理3.基本定理（1）线性规划的可行域是一个凸多面体。（2）线性规划的最优解（若存在的话）必能在可行 域的角点获得。（3）线性规划可行域的角点与基本可行解一一对应。 因此，在角点中寻找最优点即可转化为在所有基本可行解中寻找最优解。因此，只需考虑所有基本可行解就够了二、单纯形法的步骤二、单纯形法的步骤 单纯形法是一种迭代的算法，它的思想是在可行域的角点——基本可行解中寻优。由于角点是有限个（为什么？），因此，算法经有限步可终止。1.确定初始基可行解1.确定初始基可行解 由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。问题：若B0=I，则X0=？方法：若A中含I，则B0=I，由此可得初始基本可行解 若A中不含I，则可用人工变量法构造一个I。null2. 最优性检验问题：用什么检验？把目标函数用非基变量表示。null 因此，对给定的一个可行基B(即给定一个基本可行解XB=B-1b, XN=0)，判别它是否最优，（2）若所有σj≤0时，这个基本可行解为优；反之，若有某一检验数σ k ＞0，则此解一定不是最优, 转3。2. 最优性检验（续）（1）只需计算每一非基变量 x j 的检验数z3. 寻找更好的基可行解3. 寻找更好的基可行解 由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因 此，本步骤也称为基变换。（基变换）null 以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型(2) 确定初始基可行解、检验null 以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型(2) 确定初始基可行解、检验null（3）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。null练习：对于下面的线性规划（1）用图解法求解； （2）将模型化为标准型； （3）用单纯形法步骤求出其最优解，并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点。三、单纯形表三、单纯形表 单纯形表是基于单纯形法的步骤 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的计算格式，是单纯形法的具体实现。回顾单纯形法步骤null单纯形表的主要结构：问题：第一张表的B-1=？——单位阵I。检验数的公式是什么？按上式计算基变量检验数为0B-1Pj 在哪里？--B-1A 中的 j 列例5：用单纯形法求解例1例5：用单纯形法求解例1问题：标准模型的A中是否含I？——松弛变量系数恰好构成I。例5：用单纯形法求解例1例5：用单纯形法求解例1初始单纯型表：化为标准型——松弛变量系数恰好构成I。null下一张表将通过实行初等行变换（称高斯消去）得到。 方法是：先将主元消成1，再用此1将其所在列的其余元消成0。[ ]主元null[ ][ ]以10为i主元进行初等行变换null[ ][ ]以 为主元进行初等行变换0 0 0 -1.36 -0.52 2.5null 练习：用单纯形法求解下面的线性规划 null[ ]单纯形表：null【 】【 】null【 】【 】Min型单纯形表：Min型单纯形表： Min型单纯形表与Max型的区别仅在于：检验数反号，即 -当检验数均大于等于零时为最优； -令负检验数中最小的对应的变量进基。 四、大M法四、大M法1 ．问题设问题：A中不含 I例如， 用单纯形法求解线性规划null例如， 用单纯形法求解线性规划 解： 首先增加松弛变量与剩余变量x4、x5，将模型约束化为标准型null2 ．方法 在第二、第三个约束方程左边分别添加人工变量x6＞0、x7＞0。 在求极大型M问题中，人工变量在目标函数中系数均为-M；在求极小型min问题中，系数均为M，其中M是很大很大的正数。null[ ]1 -2 2 1 0 0 0-2 1 1 0 -1 1 0-1 0 1 0 0 1 1-4+3M 3-M 2-2M 0 -M 0 0null[ ][ ]1 -2 2 1 0 0 0-2 1 1 0 -1 1 0-1 0 1 0 0 1 1-4+3M 3-M 2-2M 0 -M 0 04 3 -2 0 1 0 0 -22 -1 1 0 0 -1 1 -12 -1 0 1 0 0 0 1-2+M 3-M 0 0 M 0 2M-228 1 0 0 1 -2 2 -42 -1 1 0 0 -1 1 -12 -1 0 1 0 0 0 11 0 0 0 3 M-3 M+1null①最优解的基变量中含有人工变量，可以证明此情况下，原问题无可行解； ②最优解的基变量中不含人工变量，即人工变量均为零，可以证明在此情况下，从最优解中去掉人工变量即为原问题的最优解 使用大M法会出现下列两种情况：p26解的几种情况在单纯形表上的体现（Max型）：解的几种情况在单纯形表上的体现（Max型）：唯一最优解：终表非基变量检验数均小于零； 多重最优解：终表非基变量检验数中有等于零的；(书例2.12) null练习：用单纯形法求解下面的线性规划 null[ ]问题：本题的单纯形终表检验数有何特点？ —— 非基变量x2 的检验数等于零。解的几种情况在单纯形表上的体现（Max型）：解的几种情况在单纯形表上的体现（Max型）：唯一最优解：终表非基变量检验数均小于零； 多重最优解：终表非基变量检验数中有等于零的；(书例2.12) 无界解：任意表有正检验数相应的系数列均非正。(书例2.13) 无解：用人工变量法求解，人工变量模型的最优解基中含有人工变量 退化解：在单纯形终表中，最优解为 若其中某分量b´k=0，则称此解为一个退化解