第一节单纯形法的矩阵描述及改进单纯形法介绍.ppt
《第一节单纯形法的矩阵描述及改进单纯形法介绍.ppt》由会员分享,可在线阅读,更多相关《第一节单纯形法的矩阵描述及改进单纯形法介绍.ppt(36页珍藏版)》请在三一文库上搜索。
1、第一节 单纯形法的矩阵描述 及改进单纯形法介绍,单纯形法的矩阵描述 改进单纯形法介绍,返回,继续,单纯形法的矩阵描述,不妨设基为,基变量,非基变量,设线性规划问题,则,单纯形法的矩阵描述,其中,令 得当前的基解为:,当前基解,约束方程组,当前目标值,目标函数,令 得当前的目标函数值为:,单纯形法的矩阵描述,当前检验数,单纯形法的矩阵描述,检验数,其中,当前 对应的系数列,矩阵单纯形法计算的描述,线性规划问题,化为标准型,引入松弛变量,初始单纯形表,初始基变量,矩阵单纯形法计算的描述,当基变量为 时,新的单纯形表,矩阵单纯形法计算的描述,当前检验数,当前基解,修正单纯形法简介,原因: 单纯形法的
2、目的是要求问题的最优解, 而在迭代过程中,单纯形表中的某些列与 求最优解关系不大。因此,对单纯形法进 行修正。,需要换入的变量对应的列,思路: 每次迭代关键求出,修正单纯形法的优点: 能够从问题的原来参数(A,b,C), 计算出单纯形表中所有的数据,只要导出 即可。 单纯形表中的任一数字,只要作部分的矩阵乘法即可获得。,修正单纯形法简介,有关公式:,当换入变量 ,换出变量 时, 新的 为:,修正单纯形法简介,单纯形乘子(行向量),其中,确定新的换入变量,确定新的换出变量,有关公式:,修正单纯形法简介,修正单纯形法要点: 寻求初始可行解,方法与单纯形法相同。 其迭代过程如下: 确定换入变量,方法
3、与单纯形法相同。 确定换出变量,方法与单纯形法相同。 确定新的基可行解: 首先导出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)是一个基本可行解,目标函数值,讨论最
4、优性条件,换入变量? 换出变量?,设x是线性规划(LP)的一个基本可行解,若对每个取下界值的非基变量,有 对每个取上界值的非基变量,有 则x是最优解。,讨论最优性条件,3、计算步骤,例、解下列线性规划问题:,第三节 可分解的 大规模线性规划,返回,学生讨论报告,线性规划应用 数据包络分析法,数据包络分析法(Data Envelopment Analysis, 简称DEA),是著名运筹学家 A.Charnes和W.W.Copper等学者以“相对效率”概念为基础,以凸分析和线性规划为工具,根据多指标投入和多指标产出对相同类型的单位(部门)进行相对有效性或效益评价的一种新的系统分析方法。它是处理多目
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一节 单纯 矩阵 描述 改进 介绍
链接地址:https://www.31doc.com/p-2549076.html