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

《单纯形法矩阵描述及改进单纯形法介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一节单纯形法的矩阵描述及改进单纯形法介绍单纯形法的矩阵描述改进单纯形法介绍返回继续单纯形法的矩阵描述不妨设基为基变量非基变量设线性规划问题则单纯形法的矩阵描述其中令得当前的基解为：当前基解约束方程组当前目标值目标函数令得当前的目标函数值为：单纯形法的矩阵描述当前检验数单纯形法的矩阵描述检验数其中当前对应的系数列矩阵单纯形法计算的描述线性规划问题化为标准型，引入松弛变量初始单纯形表非基变量基变量初始基变量矩阵单纯形法计算的描述基变量非基变量当基变量为时，新的单纯形表矩阵单纯形法计算的描述当前检验数当前基解修正单纯形法简介原因：单纯形法的目的是要求问题

2、的最优解，而在迭代过程中，单纯形表中的某些列与求最优解关系不大。因此，对单纯形法进行修正。需要换入的变量对应的列思路：每次迭代关键求出修正单纯形法的优点：能够从问题的原来参数（A，b，C），计算出单纯形表中所有的数据，只要导出即可。单纯形表中的任一数字，只要作部分的矩阵乘法即可获得。修正单纯形法简介有关公式：当换入变量，换出变量时，新的为：修正单纯形法简介单纯形乘子（行向量）其中确定新的换入变量确定新的换出变量有关公式：修正单纯形法简介修正单纯形法要点：寻求初始可行解，方法与单纯形法相同。其迭代过程如下：确定换入变量，方法与单纯形法相同。确定换出变量

3、，方法与单纯形法相同。确定新的基可行解：首先导出B-1然后计算XB=B-1b迭代终止原则与单纯形法相同。修正单纯形法简介第二节变量有界的大规模线性规划返回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是线性规

4、划（LP）的一个基本可行解，若对每个取下界值的非基变量，有对每个取上界值的非基变量，有则x是最优解。讨论最优性条件3、计算步骤例、解下列线性规划问题：第三节可分解的大规模线性规划返回学生讨论报告线性规划应用－－－数据包络分析法数据包络分析法（DataEnvelopmentAnalysis,简称DEA），是著名运筹学家A.Charnes和W.W.Copper等学者以“相对效率”概念为基础，以凸分析和线性规划为工具，根据多指标投入和多指标产出对相同类型的单位（部门）进行相对有效性或效益评价的一种新的系统分析方法。它是处理多目标决策问题的好方法。重要概念

5、决策单元（DecisionMakingUnits,简称DMU）一个经济系统可以看成一个单元在一定可能范围内，通过投入一定数量的生产要素并产出一定数量的产品的活动，这样的单元就被称为决策单元。(当然，一个单元的不同时间阶段也可以看做是不同的决策单元）。特点：具有一定的输入和输出在将输入转换成输出的过程中，努力实现自身的决策目标。重要概念决策单元的相对有效性评价的依据是决策单元的“输入”和“输出”数据，根据输入和输出数据来评价决策单元的优劣。决策单元的相对有效性（即决策单元的优劣）被称为DEA有效，它用数学规划模型计算比较决策单元之间的相对效率，为评价对

6、象作出评价。DEA步骤假设设某个DMU的输入向量为,输出向量为。则n个（）对应的输入、输出向量分别为：而且即每个决策单元都有m种类型的输入以及s种类型的输出为第j个决策单元对第i种类型输入的投入量；为第j个决策单元对第r种类型输出的产出量。这些都是已知的数据。DEA步骤假设现在，我们是要最优化这些决策单元，那么我们假设一个假想决策单元满足产出最大，同时投入最小。在此基础上，我们来判断是否真的满足该条件。因此，我们假设该决策单元的第i项投入为产出为且构造数学模型我们进行检验，先假设存在其他的决策单元组合的产出不低于而且投入尽可能的比小，构造数学模型如下

7、：求解并判断当求解结果为时，说明存在其他的决策单元比该决策单元更满足条件，所以，该决策单元非DEA有效；当时，该决策单元DEA有效。并可以根据所求得的最优解重新分配各决策单元的比例，也就是系数,再生成新的决策单元，又继续检验。习题例8振华银行的4个分理处的投入产出情况如表1-16所示。要求分别确定各分理处的运行是否DEA有效。分理处投入产出职员数营业面积（）储蓄存取贷款中间业务分理处11514018002001600分理处22013010003501000分理处3211208004501300分理处4201359004201500表1-16产出单位：

8、处理笔数/月解：根据数据包络法，我们假设构造一个决策单元组合，使得其第i个项的投入为第r项的产出为