单纯形法的矩阵描述及改进单纯形法介绍.ppt

第一节 单纯形法的矩阵描述 及改进单纯形法介绍,单纯形法的矩阵描述 改进单纯形法介绍,返回,继续,单纯形法的矩阵描述,不妨设基为,基变量,非基变量,设线性规划问题,则,单纯形法的矩阵描述,其中,令 得当前的基解为：,当前基解,约束方程组,当前目标值,目标函数,令 得当前的目标函数值为：,单纯形法的矩阵描述,当前检验数,单纯形法的矩阵描述,检验数,其中,当前 对应的系数列,矩阵单纯形法计算的描述,线性规划问题,化为标准型，引入松弛变量,初始单纯形表,初始基变量,矩阵单纯形法计算的描述,当基变量为 时，新的单纯形表,矩阵单纯形法计算的描述,当前检验数,当前基解,修正单纯形法简介,原因： 单纯形法的目的是要求问题的最优解， 而在迭代过程中，单纯形表中的某些列与 求最优解关系不大。因此，对单纯形法进 行修正。,需要换入的变量对应的列,思路： 每次迭代关键求出,修正单纯形法的优点： 能够从问题的原来参数（A，b，C）， 计算出单纯形表中所有的数据，只要导出 即可。 单纯形表中的任一数字，只要作部分的矩阵乘法即可获得。,修正单纯形法简介,有关公式：,当换入变量 ，换出变量 时， 新的 为：,修正单纯形法简介,单纯形乘子（行向量）,其中,确定新的换入变量,确定新的换出变量,有关公式：,修正单纯形法简介,修正单纯形法要点： 寻求初始可行解，方法与单纯形法相同。 其迭代过程如下： 确定换入变量，方法与单纯形法相同。 确定换出变量，方法与单纯形法相同。 确定新的基可行解： 首先导出B-1 然后计算XB= B-1 b 迭代终止原则与单纯形法相同。,修正单纯形法简介,第二节 变量有界的 大规模线性规划,返回,1、基本可行解概念的推广,考虑线性规划问题：,A为m*n,秩为m,基本解X(0) ：X(0)为AX=b的一个解，其中m个分量对应A 的列线性无关，其余n-m个分量取上界或下界值。,基本可行解X(0) ：基本解X(0) 中m个基变量的值介于上下 界之间。,推广基本可行解的表达式：,推广基本可行解集与可行域凸集K的极点集等价,2、基本可行解的改进,设X(0)是一个基本可行解,目标函数值,讨论最优性条件,换入变量？ 换出变量？,设x是线性规划（LP）的一个基本可行解，若对每个取下界值的非基变量，有 对每个取上界值的非基变量，有 则x是最优解。,讨论最优性条件,3、计算步骤,例、解下列线性规划问题：,第三节 可分解的 大规模线性规划,返回,学生讨论报告,线性规划应用 数据包络分析法,数据包络分析法（Data Envelopment Analysis, 简称DEA），是著名运筹学家 A.Charnes和W.W.Copper等学者以“相对效率”概念为基础，以凸分析和线性规划为工具，根据多指标投入和多指标产出对相同类型的单位（部门）进行相对有效性或效益评价的一种新的系统分析方法。它是处理多目标决策问题的好方法。,重要概念,决策单元（Decision Making Units,简称DMU） 一个经济系统可以看成一个单元在一定可能范围内，通过投入一定数量的生产要素并产出一定数量的产品的活动，这样的单元就被称为决策单元。(当然，一个单元的不同时间阶段也可以看做是不同的决策单元）。 特点： 具有一定的输入和输出 在将输入转换成输出的过程中，努力实现自身的决策目标。,重要概念,决策单元的相对有效性 评价的依据是决策单元的“输入”和“输出”数据，根据输入和输出数据来评价决策单元的优劣。 决策单元的相对有效性（即决策单元的优劣）被称为DEA有效，它用数学规划模型计算比较决策单元之间的相对效率，为评价对象作出评价。,DEA步骤,假设 设某个DMU的输入向量为 , 输出向量为 。 则n个 （ ）对应的输入、输出向量分别为： 而且 即每个决策单元都有m种类型的输入以及s种类型的输出 为第j个决策单元对第i种类型输入的投入量； 为第j个决策单元对第r种类型输出的产出量。 这些都是已知的数据。,DEA步骤,假设 现在，我们是要最优化这些决策单元，那么我们假设一个假想决策单元 满足产出最大，同时投入最小。在此基础上，我们来判断 是否真的满足该条件。,因此，我们假设该决策单元的第i项投入为 产出为 且,构造数学模型 我们进行检验，先假设存在其他的决策单元组合的产出不低于 而且投入尽可能的比 小，构造数学模型如下：,求解并判断 当求解结果为 时，说明存在其他的决策单元比该决策单元更满足条件，所以，该 决策单元非DEA有效； 当 时，该 决策单元DEA有效。并可以根据所求得的最优解重新分配各决策单元的比例，也就是系数 ,再生成新的决策单元 ，又继续检验。,习题 例8 振华银行的4个分理处的投入产出情况如表1-16所示。要求分别确定各分理处的运行是否DEA有效。,表1-16 产出单位：处理笔数/月,解：根据数据包络法，我们假设构造一个决策单元组合， 使得其第i个项的投入为 第r项的产出为 且 然后，让我们以分理处1为例，将分理处1作为 ，来判断分理处1的运行是否 DEA有效。建立数学模型如下：,将该模型代入到Excel电子表格中进行求解得=1。,同理分别以分理处2，3，4作为要衡量的决策单元，得=0.966，1，1。 因此，这几个分理处的有效性见下表：,DEA在评价城市发展的可持续性中的应用,案例背景分析 目前对城市可持续发展影响最大的是环境问题。所以，我们把城市的可持续发展系统视作DEA中的一个决策单元，它具有特定的输入输出，在将输入转化成输出的过程中，努力实现系统的可持续发展目标。现在，我们利用DEA方法对天津市的可持续发展进行评价。在这里选取具有代表性的指标作为输入变量和输出变量。 输入变量：政府财政收入占GDP的比重、环保投资占GDP的比重、每千人科技人员数； 输出变量：经济发展（用人均GDP表示）、环境发展（用城市环境质量指数表示，在计算过程中，城市环境指数的数值作了归一化处理）。（具体数值见下表）,同样的,我们以序号1（1990年）为例建立数学模型,同样将该模型