最优化课程论文

精品文档 1欢迎下载 求解线性规划的单纯形法求解线性规划的单纯形法 摘摘 要要 线性规划就是用数学为工具 来研究一定限制条件下 如何实现某一线性目标 最优化 单纯形法是求解线性规划的主要算法 文章从单纯形法的思想出发 详细论 述了单纯形法 的主体步骤 并借助单纯形表通过例题加以说明 求解思路是 通过 添加人工变量使得标准化后的系数矩阵一定含有单位矩 阵 从而得到一组基变量和初 始基本可行解 由于人工变量是人为添加的 为了不改变原问题 在目标函数中 消去 人工变量 并将人工变量由初始的基变量化成非基变量 使之取值为零 然后用普通 单纯形法求解 关键词 关键词 线性规划 单纯形法 单纯形表 步骤 1 1 迭代原理迭代原理 从一个初始的基本可行解出发 经过判断 如果是最优解 则结束 否则经过基 变换得到另一个目标函数值改善的基本可行解 如此一直进行下去 直到找到最优解 2 2 迭代步骤 迭代步骤 第 1 步 求初始基可行解 列出初始单纯形表 第 2 步 最优性检验 第 3 步 从一个基本可行解转换到相邻的目标函数值更大的 基本可行解 列出新的单纯形表 第 4 步 重复第 2 3 步 一直到计算结束为止 2 12 1 确定初始基本可行解确定初始基本可行解 由于可行解是由一个可行基决定的 因此 确定初始基可行解 X0 相当于确定一 个初始可行基 B0 确定方法 若系数矩阵 A 中含单位矩阵 I 则取 B0 I 若 A 中不 含 I 则可用人工变量法构 造一个 I 2 22 2 最优性检验最优性检验 用目标来检验解的优劣 在 A 中取定一个基矩阵 B 则决策向量 X 可分块为 相应的价 格向量 C 也分块为 CB CN 把这个分块矩阵的形式乘出来 就是 Z CX CB CN CBXB CNXN 不妨设 B 表示 A 中的前 m 列 则可记 A B N 其中 N 为非基矩阵 约束中的 AX b 可 表示为 B N b 即 XB B 1b B 1NXN 经整理得 Z CB B 1b B 1NXN CNXN CBB 1b CN CBB 1N XN 在这个式子中不难分析出 后边一项 XN 的系数 CN CBB 1N 当这个向量均为 0 分量时 这 时只有当 XN 取 0 时 使 Z 值最大 也 就是当 XN 统统取 0 时的这个基本可行解是最优的 而当这个系数向量其中有某分量 是 0 的时候 我们可以分析得到 当前 XN 统统取 0 的这个基本可行解 不是最优 因此 我们可以用 XN 的系数向量 CN CBB 1N 的符号来判断当前基可行解是不是最 优 把这个系数向量叫做检验数向量 记为 当 0 时 当前解为最优解 最 优性检验的方法 1 计算每个变量 xj 的检验数 j Cj CBB 1Pj 其中 Pj 为 A 中的第 j 列 2 若所有 j 0 则 当前解为最优 否则 如果至少有一个 j 0 当前解不是最优 转入第三步 2 32 3 寻找更好的基本可行解寻找更好的基本可行解 由于基本可行解与基对应 即寻找一个新的基可行解 相当于从上一个基 B0 变 精品文档 2欢迎下载 换为下一个新 的基 B1 因此 本步骤也可称为基变换 在基变换的过程中要遵循这 样的原则 保证改善目标 再者保证基变换后的解可行 具体变换的方法就是将系 数矩阵 A P1 P2 Pi Pk Pn 中非基向量部分的某一列和基向量中的 某一列互换 而且每次只换一列 在基向量的行列中出 去一个进一个 这个基变换 的过程就是确定进基出基 具体方法 首先决定进基 令正检验数 中最大的那个所 对应的 Pk 进基 然后决定出基 令检验比 i 中最小的对应的行 Ps 出基 其中 i B 1b i B 1Pk i B 1Pk i 0 也就是对应分量之比 在用单纯形法求解线性规划问题之前 有一个预备步骤就是将模型变为标准型 虽然 可以由 基本的计算求出线性规划问题的最优解 但是为了更加简单 清楚 这个算 法的过程我们通过表 格的形式来实现 即所谓的单纯形表 例例 用单纯形法求解下面线性规划问题 以 max 为例 maxZ 7X1 12x2 s t 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 x1 x2 0 解 化为标准型 maxZ 7X1 12X2 0X3 0X4 0X5 s t 9x1 4x2 x3 360 4x1 5x2 x4 200 3x1 10 x2 x5 300 x1 x2 x3 x4 x5 0 单纯形表 第一个基是 I 初始表填完后 第一个基本可行解 X 0 0 360 200 300 T 这个解是否为 最优呢 要计算检验数进行检验 以第一个检验数 1 为例来加 以说明 1 C1 CBB 1P1 7 0 0 0 9 4 3 T 7 同理求出其余几个检验数分别为 12 0 0 0 如果检验数的符号均 0 则当前这个基本可 行解最优 否则不是最优 我们看到这张表不是最优 还需 继续进行 那么继续进行就需转到第 三个步骤基变换 主要是确定进基和出基 确 定进基是在正检验数中选择最大的那个 我们这道 题是 12 这个 12 所对应的向量是 P2 对应的变量 x2 就进基 它刚才是非基变量 确定了进基之 后 就可以计算检验 精品文档 3欢迎下载 比 就是用 B 1b 比上已决定进基的列 B 1P2 也就是每个分量对应之比 360 比 4 等于 90 200 比 5 等于 40 300 比 10 等于 30 在检验比中找到最小的一个 值 也就 是 30 它所在的这一行相应的最左边的这个 x5 就是出基变量 进基列和出 基行在这个表上的一个 交叉元就是 10 这个交叉元用一个括号括起来 这个元就称 为主元素 这个元就作为下边迭代计 算的一个出发点 简称为主元 怎样由这个主 元迭代计算得到下一张单纯形表呢 原则是 首先 把这个主元用初等行变换的方法 把它消成 1 然后拿这个主元还是初等行变换的方法把它所在的 列的其余元素消成 0 下面我们把下一张表画出来 它的形式和上一张表是一样的 表头不用重 画 紧 接上一张表 计算发现仍有一个正检验数 3 4 这张表不是最优 仍需进行换基迭代 以交叉元 2 5 作为主 元进行迭代计算得到下一张表 新的一张表的数据计算完毕 得出 X 20 24 84 0 0 T 通过计算表中检验数 均 0 当前表 为最优 所以最优解 X 20 24 84 0 0 T Z 0 7 12 84 20 24 T 428 3 3 小结小结 单纯形法是解线性规划问题的一种有效的方法 它需要一个已知的基本可行解 并 需把原始线 性规划问题化为标准式 而在一般情况下线性规划 问题并无明显的基本 可行解 则需增加人工变量以 获得基本可行解 这样可能增加计算量 因而需要 改 进算法 同时 实际生活中的线性规划问题规模 较大 即变量个数和约束条件都多 当用计算机进 行计算时会占据大量的内存空间 在迭代过程中 实际上有很多计算 是多余的 当迭代次数增多时 累计误差就会增加 进而会影响计算精度 针对这 一问题 算法也需改进 因此 单纯形法解线性规 划问题的算法仍需更进一步的探 究与改良 这将对 解决线性规划问题非常有意单纯形法的提出使得线性规划在理论 上已趋向成熟 实际上的应用日益广泛与深入 应用单 纯形法解决线性规划问题时 要灵活多变 根据实际背景进行分析 以上只以 max 型为例 当线性 规划模型为 min 型时 有所改变 需要做进一步探讨 参考文献参考文献 精品文档 4欢迎下载 1 钱颂迪 运筹学 M 2 版 北京 清华大学出版社 1990 2 牛映武 运筹学 M 西安 西安交通大学出版社 1994 3 Duckworth W E Gear A E Lockett A G A guide to operational research M 3rd ed London Chapman and Hall Ltd 1978 4 篮益中 线性代数引论 M 北京 北京大学出版社 1981