单纯形法基本原理及实例演示ppt课件

单纯形法求解 动态演示 在求解LP问题时 有人给出了图解法 但对多维变量时 却无能为力 于是美国数学家G B Dantgig 丹捷格 发明了一种 单纯形法 的代数算法 尤其是方便于计算机运算 这是运筹学史上最辉煌的阶段 线性规划问题标准型的矩阵形式 MaxZ CX a s t AX b b X 0 c a11a12 a1nb1A a21a22 a2nb b2 am1am2 amnbm 一 关于标准型解的若干基本概念 基矩阵示例 0 0 0 0 3 2 0 2 0 0 0 1 0 1 0 x1 x2 x4 x3 0 0 1 3 0 0 3 2 1 目标函数 约束条件 行列式 0基矩阵 X1 x2 x3为基变量 x4为非基变量 因为B为基 故有XB B 1NXN B 1b 解得可行解XB B 1b B 1NXN 代入目标函数Z Z CBB 1b CN CBB 1N XN令非基变量XN 0 则有XT XB XN T B 1b 0 TZ CBB 1b 设A B N B为一个基 即线性无关向量组R A R B XT XB XN T XB为基变量 XN为非基变量 C CB CN CB为基变量系数 CN为非基变量系数 则有 Z CB CN XB XN T CBXB CNXNAX B N XB XN T BXB NXN b 1 单纯形法原理 Z CBB 1b CN CBB 1N XN 如果CN CBB 1N小于0 无论XN取任何大于0值 只会让Z变小 因此我们可以通过CN CBB 1N来判断Z取得是不是最大值 如果存在一个CN CBB 1N大于0 则说明Z的值会随着XN增大而增大 说明Z有调整的余地 定理一 若某个基本可行解所对应的检验向量CN CBB 1N 0 则这个基本可行解就是最优解 定理二 若某个基本可行解所对应的检验向量CN CBB 1N存在一个检验数 0 则该问题有无数多个最优解 定理三 若某个基本可行解所对应的检验向量Cj CBB 1Nj大于0 且aij 都小于0 则无解 为了矩阵形求逆计算方便 一般将B转化为单位矩阵 将线性规划问题化成标准型 找出或构造一个m阶单位矩阵作为初始可行基 建立初始单纯形表 计算各非基变量xj的检验数 j Cj CBPj 若所有 j 0 则问题已得到最优解 停止计算 否则转入下步 在大于0的检验数中 若某个 k所对应的系数列向量Pk 0 则此问题是无界解 停止计算 否则转入下步 根据max j j 0 k原则 确定xk为换入变量 进基变量 再按 规则计算 min bi aik aik 0 bl aik确定xBl为换出变量 建立新的单纯形表 此时基变量中xk取代了xBl的位置 以aik为主元素进行迭代 把xk所对应的列向量变为单位列向量 即aik变为1 同列中其它元素为0 转第 步 2 单纯形法的计算步骤 线性规划的例子 线性规划 标准化 引入变量 s1 s2 s3 提取系数 填入表格 s t C向量 CB CN XB XN 基B N CBB 1b CN CBB 1N XN 每个非基变量的检验值 初始单纯形表 初始单纯形表 目标函数系数区 约束条件系数区 右端系数 检验系数区 基变量区 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 0 0 0 0 0 初始单纯形表 50 初始单纯形表 可行解XB B 1b B 1NXN 0 初始单纯形表 可行解XB B 1b B 1NXN 0 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 x1 50 x1 50 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 表格中 检验系数 j全部小于或等于0 根据判断规则 Z值为最优值 Z 2