运筹学——3.单纯形矩阵描述与改进单纯形法

运筹学复习一、单纯形方法（表格、人工变量、基础知识）线性规划解的情况：唯一最优解、多重最优解、无界解、无解。

其中，可行域无界，并不意味着目标函数值无界。

无界可行域对应着解的情况有：唯一最优解、多重最优解、无界解。

有界可行域对应唯一最优解和多重最优解两种情况。

线性规划解得基本性质有：满足线性规划约束条件的可行解集（可行域）构成一个凸多边形；凸多边形的顶点（极点）与基本可行解一一对应（即一个基本可行解对应一个顶点）；线性规划问题若有最优解，则最优解一定在凸多边形的某个顶点上取得。

单纯形法解决线性规划问题时，在换基迭代过程中，进基的非基变量的选择要利用比值法，这个方法是保证进基后的单纯型依然在解上可行。

换基迭代要求除了进基的非基变量外，其余非基变量全为零。

检验最优性的一个方法是在目标函数中，用非基变量表示基变量。

要求检验数全部小于等于零。

“当x 1由0变到45/2时，x 3首先变为0，故x 3为退出基变量。

”这句话是最小比值法的一种通俗的说法，但是很有意义。

这里，x 1为进基变量，x 3为出基变量。

将约束方程化为每个方程只含一个基变量，目标函数表示成非基变量的函数。

单纯型原理的矩阵描述。

在单纯型原理的表格解法中，有一个有趣的现象就是，单纯型表中的某一列的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的m*m 矩阵与其最初的那一列向量的乘积。

最初基变量对应的基矩阵的逆矩阵。

这个样子：'1222 1 0 -32580 1 010 0 158P B P -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦５１＝５所有的检验数均小于或等于零，有最优解。

但是如果出现非基变量的检验数为0，则有无穷多的最优解，这时应该继续迭代。

解的结果应该是：X *= a X 1*+(1-a)X 2* （0<=a<=1）说明：最优解有时不唯一，但最优值唯一；在实际应用中，有多种方案可供选择；当问题有两个不同的最优解时，问题有无穷多个最优解。

对偶单纯形法与单纯形法对比分析1．教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解2．教学内容：1）对偶单纯形法的思想来源 2）对偶单纯形法原理3．教学进程：1）讲述对偶单纯形法解法的来源：所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。

2）为什么要引入对偶单纯形法：单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点： （1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算； （2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。

由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w 。

据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。

我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函数的最优值。

那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即达到了目标函数的最优值。

其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。

运筹学单纯形法例题求解过程摘要：一、运筹学单纯形法概述二、单纯形法求解步骤1.确定基变量和初始基本可行解2.编制初始单纯形表3.判断基本可行解是否为最优解4.迭代求解最优解三、例题求解过程1.题目描述2.化为标准型3.建立初始单纯形表4.迭代计算四、总结正文：一、运筹学单纯形法概述运筹学单纯形法是一种求解线性规划问题的方法，它的主要思想是通过不断迭代，逐步优化基变量的值，从而求得问题的最优解。

单纯形法可以有效地解决具有如下特点的问题：目标函数线性，约束条件线性，变量非负。

二、单纯形法求解步骤1.确定基变量和初始基本可行解在求解线性规划问题时，首先需要确定基变量，即在约束条件方程组中，选择一部分变量作为基变量，用于表示其他变量。

通过寻找或构造单位矩阵的方法，可以确定基变量，从而求出初始基本可行解。

2.编制初始单纯形表基于初始基本可行解和线性规划模型提供的信息，可以编制初始单纯形表。

单纯形表包含了基变量、非基变量、目标函数系数、约束条件系数和检验数等信息，用于描述问题的基本情况。

3.判断基本可行解是否为最优解通过检验数cj-zj 来判断基本可行解是否为最优解。

如果所有非基变量的检验数cj-zj<0，说明已经达到最优解，计算停止。

如果存在cj-zj>0，但所有cj-zj>0 所在列对应的所有aij<0，说明无最优解，计算停止。

如果至少存在一个cj-zj>0，并且所对应的所有j 列中至少有一个aij>0，说明没有达到最优解，需要继续迭代求解。

4.迭代求解最优解在迭代过程中，首先需要确定换入变量，即选择最大检验数对应的非基变量。

然后，利用特定公式计算出换出变量，即在基变量中选择一个与换入变量对应的变量进行替换。

接着，生成新的单纯形表，将换入变量和换出变量进行置换后，调整新基变量对应的矩阵为单位矩阵。

最后，重新计算检验数和目标函数值，返回第二步，直至找到最优解。

三、例题求解过程假设有一个线性规划问题，目标函数为MINfx1x2Mx4Mx6，约束条件为：3x1 + 4x2 ≤ 122x1 + 3x2 ≤ 10x1, x2 ≥ 0首先，将约束条件化为标准型：3x1 + 4x2 + s1 = 122x1 + 3x2 + s2 = 10x1, x2 ≥ 0然后，建立初始单纯形表：| 基变量| 非基变量| 目标函数系数| 约束条件系数| 检验数| ---------------------------------------------------------------------行1 | x1 | s1 | -3 | -4 | -12 |行2 | x2 | s2 | -4 | -3 | -10 |行3 | x1 | x2 | 0 | 0 | 0 | 行4 | s1 | x2 | 0 | 3 | 0 | 行5 | s2 | x1 | 0 | 2 | 0 | 根据初始单纯形表，可以得到初始基本可行解为：x1 = 0, x2 = 0接下来，判断基本可行解是否为最优解：c1 = -12, c2 = -10, c3 = 0, c4 = 0, c5 = 0由于c3、c4 和c5 都小于等于0，所以基本可行解不是最优解，需要继续迭代求解。

运筹学第2章单纯形法 2.1 单纯形法的基本思想该方法简捷、规范，是举世公认的解决LP问，题行之有效单纯形法（Simplex Method）是美国著名运筹学家丹捷格（Dantzig）1947年首先提出的通用方法。

单纯形法不仅是解决LP问题的最基本的算法之一，而且成为解决整数规划和非线性规划某些算法的基础。

2、单纯形法的3种形式——方程组形式（代数形式）、表格形式、矩阵形式3、单纯形法的基本思路——基于LP问题的标准形，先设法找到某个基本可行解（称为初始基本可行解）；开始实施从这个基本可行解向另一个基本可行解的转换，要求这种转换不仅容易实现，而且能改善（至少保持）目标函数值；继续寻找更优的基本可行解，进一步改进目标函数值。

当某一个基本可行解不能再改善时，该解就是最优解。

（或者是出现无可行解、无最优解、无穷多最优解的情况）2.1.1 方程组形式的单纯形法例1 一个企业需要同一种原材料生产甲、乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，获得的利润也不相同（如下表）。

请问，该企业应如何安排生产计划，才能使获得的利润达到最大？解：该问题的LP模型为：将该问题的LP模型化为标准形⎪⎩⎪⎨⎧≥≤+≤++=,1202410032..4621212121xxxxxxt sxxzm ax函数约束的增广矩阵为：很显然 R （A ） = R （A ，b ）= 2 < 5，即该方程组有无穷多组解。

系数矩阵为：决策变量向量为：选取 为基，则 为基变量， 为非基变量令非基变量 ，则可以得到一基本 可行解为： 下面的计算都是以它为初始点逐次实施转换，故将其称为初始基本可行解。

此时，Z=0，其经济含义为：该企业没 有安排甲、乙两种产品的生产，当然也就没有利润可言。

条典☐ 初始基本可行解所对应的可行基是一个m 阶的单位阵； ☐ 目标函数表达式中所有的基变量的系数全部为0。

☐ 这是单纯形法所必需的！！！ ☐ 分析目标函数表达式☐ 非基变量的系数都是正数，若将它们转换为基变量，目标函数值则就会可能增加。