单纯形法PPT幻灯片课件

《单纯形法PPT幻灯片课件》由会员分享，可在线阅读，更多相关《单纯形法PPT幻灯片课件（111页珍藏版）》请在金锄头文库上搜索。

1、第五章单纯形法 一 问题的提出二 单纯形法的基本思路和原理三 单纯形法的表格形式四 人工变量法五 几种特殊情况 1 一 问题的提出 图解法只能解决二维的线性规划问题 那更多变量的问题怎么办 jsj 通过代数算法搜寻最优解 单纯形法 就是这样的一种代数搜寻法 线性规划问题的解一般有无穷多个 如果不缩小搜寻范围 工作量太大 我们首先将最优解缩小在一个有限的范围 2 一 问题的提出 回顾图解法 我们知道 最优解必定在可行域的顶点上取得 而顶点的个数总是有限的 多维线性规划问题的可行域也存在有限个顶点 如果能够从一个顶点开始 通过某种方式向更优顶点转移 总会找到最优点 首先面临的问题 如何通过代数方法

2、找到第一个顶点 3 一 问题的提出 图解法中的例1 5模型为 Maxz 50 x1 100 x2s t 1 x1 1 x2 3002 x1 1 x2 4000 x1 1 x2 250 x1 0 x2 0 4 一 问题的提出 从其标准形的解向量开始研究 Maxz 50 x1 100 x2s t 1 x1 1 x2 1 x3 0 x4 0 x5 3002 x1 1 x2 0 x3 1 x4 0 x5 4000 x1 1 x2 0 x3 0 x4 1 x5 250 xj 0 j 1 2 3 4 5 5 一 问题的提出 顶点对应的解向量有何代数特征 O 0 0 300 400 250 A 0 250

3、50 150 0 B 50 250 0 50 0 C 100 200 0 0 50 D 200 0 100 0 50 答案 都有两个变量取值为0 且非负 X1 X2 O 0 0 A 0 250 B 50 250 C 100 200 D 200 0 6 一 问题的提出 既然顶点解向量中有两个变量取值为0 而标准形中又有三个约束方程 是否可以直接通过这种方式找顶点 如令x1 0 x2 0 则x3 300 x4 400 x5 250可得到解 0 0 300 400 250 7 一 问题的提出 又如 令x3 0 x5 0 由约束条件 x1 x2 x3 3002x1 x2 x4 400 x2 x5 25

4、0可得到解 50 250 0 50 0 8 一 问题的提出 若令x2 0 x5 0 会怎样 由约束方程可知 x1 x2 x3 300 x1 x3 3002x1 x2 x4 400 2x1 x4 400 x2 x5 250 0 250 显然不能得到相应的解 9 一 问题的提出 为什么令x2 0 x5 0时不能得到解 因为其余三个变量的系数列向量为该矩阵是非可逆矩阵 即去掉x2和x5后的三个约束方程线性相关 这种情况下得不到解 10 一 问题的提出 既然如此 如果我们在技术矩阵中取出三列 组成一个可逆阵 令其余两列对应的变量为零 则一定可以得到一个解 11 一 问题的提出 如 取1 2 3列得到

5、此矩阵为可逆阵 故令x4 0 x5 0 一定可以得到一个解 对应的解为 75 250 25 0 0 12 一 问题的提出 基的概念 已知A是约束条件的m n阶系数矩阵 其秩为m 设B是A矩阵中的一个非奇异 可逆 的m m阶子矩阵 则称B为线性规划问题的一个基 B由A中的m个线性无关列向量组成 13 一 问题的提出 一个基对应一组概念 非基变量 基变量 基向量 非基向量 对应基本解 0 0 300 400 250 14 一 问题的提出 0 0 300 400 250 0 300 0 100 50 0 400 100 0 150 0 250 50 150 0 300 0 0 200 50 200

6、0 100 0 50 不存在 100 200 0 0 50 50 250 0 50 0 75 250 25 0 0 基本解 是 x3 x5 p3 p5 x1 x2 x4 p1 p2 p4 B2 p1 p2 p4 是 x3 x4 p3 p4 x1 x2 x5 p1 p2 p5 B3 p1 p2 p5 是 x1 x2 p1 p2 x3 x4 x5 p3 p4 p5 B10 p3 p4 p5 否 x1 x3 p1 p3 x2 x4 x5 p2 p4 p5 B9 p2 p4 p5 否 x1 x4 p1 p4 x2 x3 x5 p2 p3 p5 B8 p2 p3 p5 是 x1 x5 p1 p5 x2

7、x3 x4 p2 p3 p4 B7 p2 p3 p4 否 x2 x3 p2 p3 x1 x4 x5 p1 p4 p5 B6 p1 p4 p5 是 x2 x4 p2 p4 x1 x3 x5 p1 p3 p5 B5 p1 p3 p5 x2 x5 p2 p5 x1 x3 x4 p1 p3 p4 B4 p1 p3 p4 否 x4 x5 p4 p5 x1 x2 x3 p1 p2 p3 B1 p1 p2 p3 是否可行 非基变量 非基向量 基变量 基向量 基 15 一 问题的提出 基本解可能可行 也可能不可行 满足非负约束条件的基本解叫基本可行解 相应的基称为可行基 否则为非可行基 16 一 问题的提出

8、A 0 250 50 150 0 B 50 250 0 50 0 C 100 200 0 0 50 D 200 0 100 0 50 O 0 0 300 400 250 E 75 250 25 0 0 F 0 300 0 100 50 G 0 400 100 0 150 H 300 0 0 200 50 17 一 问题的提出 线性规划解的集合关系 基本解 最优解 基本可行解 可行解 18 一 问题的提出 显然 将搜索范围控制在基本可行解内 将大大减少搜索工作量 但是 即使取得一个基 得到的解还不一定可行 如何才能保证取得一个可行基呢 19 一 问题的提出 总结 1 可行域顶点对应的解必为基本可

9、行解 有n m个变量取值为0 满足非负条件 2 一个基对应一组基本解 可能可行 也可能不可行 3 最优解必定在基本可行解中 20 二 单纯形法的基本思路和原理 单纯形法的基本思路 首先找到一个顶点 然后判断它是否最优 如果不是 则通过更换顶点的方式找到更优的顶点 直到找到最优顶点 21 二 单纯形法的基本思路和原理 第一步 找到一个顶点 初始基本可行解 22 二 单纯形法的基本思路和原理 思考 1 令n m个变量为0 非基变量 是否一定可以找到 答案 不一定 如例中x2 0 x5 0时不能得到解 可行的办法 找到一个基 23 二 单纯形法的基本思路和原理 2 一个基是否一定对应可行域顶点 答案

10、 不一定 必须是可行基 一般来说 判断一个基是否是可行基 需要在求出其基本解后才能判断 24 二 单纯形法的基本思路和原理 3 那有没有办法在求出解之前保证我们取得的基为可行基 解决办法 保证右端项非负 找到一个单位矩阵 必定是一个可行基 25 二 单纯形法的基本思路和原理 如范例系数阵 存在3阶单位阵 初始可行基 右端项非负 26 二 单纯形法的基本思路和原理 基本可行解为 0 0 300 400 250 此可行基称为初始可行基 对应的解称为初始基本可行解 初始基本可行解在上页矩阵中一目了然 27 二 单纯形法的基本思路和原理 第二步 最优性检验 28 二 单纯形法的基本思路和原理 对应于每

11、一组基本解 目标函数都可以表示成非基变量的函数 称为典式 如 初始基本可行解 0 0 300 400 250 其非基变量为x1 x2目标函数为Maxz 50 x1 100 x2 29 二 单纯形法的基本思路和原理 典式Z 50 x1 100 x2如果x1增加1 Z会怎样 答案 Z增加50 如果x2的值增加1 Z会怎样 答案 Z增加100 30 二 单纯形法的基本思路和原理 x1 x2的取值是否有增加的可能 分析 该解中非基变量x1 x2的取值为0 其值完全有可能增加 说明此时目标函数值还有增加的可能 没有达到最优 31 二 单纯形法的基本思路和原理 再如 基本解 50 250 0 50 0 其

12、非基变量为x3 x5由约束方程可得 x1 50 x3 x5x2 250 x5目标函数为Maxz 50 x1 100 x2 27500 50 x3 50 x5 32 二 单纯形法的基本思路和原理 典式Z 27500 50 x3 50 x5如果x3增加1 Z会怎样 答案 Z减少50 如果x5的值增加1 Z会怎样 答案 Z减少50 可见要使Z增加 只有使x3和x5减少 33 二 单纯形法的基本思路和原理 x3 x5的取值是否有减少的可能 分析 该解中非基变量x1 x2的取值为0 其值不可能再减少 所以Z值不可能再增加 说明此基本解对应的目标函数值已经达到最优 34 二 单纯形法的基本思路和原理 由以

13、上分析 可见 完全可以由典式中的系数来判断解是否最优 如 Z 50 x1 100 x2系数 0 未达到最优 Z 27500 50 x3 50 x5系数 0 达到最优 这些系数我们称为检验数 35 二 单纯形法的基本思路和原理 检验数的概念 若只用非基变量来表示目标函数 将所有基变量从目标函数中用非基变量替换出去 此时目标函数中各非基变量的系数即为各非基变量的检验数 把变量xj的检验数记为 j 显然基变量的检验数为0 36 二 单纯形法的基本思路和原理 最优解判别准则 对于求最大目标函数的问题中 对于某个基本可行解 若所有检验数 j 0 则这个基本可行解是最优解 对于求最小目标函数的情况 当所有

14、非基变量检验数 j 0时 目标值最优 对应的基本可行解为最优解 37 二 单纯形法的基本思路和原理 第三步 基变换 38 二 单纯形法的基本思路和原理 在保证右端常数项非负前提下 基变量与非基变量互换 换基 使检验数由正 非最优 变为非正 最优 为了换基 就要合理的确定进基变量和出基变量 39 二 单纯形法的基本思路和原理 进基变量的确定 最大检验数原则 确保目标值增加最快 例中初始解 1 50 2 100 则选x2入基 40 二 单纯形法的基本思路和原理 出基变量的确定 最小比值原则min 300 1 400 1 250 1 250 x5出基 以进基变量系数列中的正数为分母 以相应的方程右端

15、常数为分子 系数为0和负不考虑 41 二 单纯形法的基本思路和原理 范例中 确定了x2为入基变量后 把约束方程1 x1 1 x2 1 x3 0 x4 0 x5 3002 x1 1 x2 0 x3 1 x4 0 x5 4000 x1 1 x2 0 x3 0 x4 1 x5 250中入基变量x2的正系数除以对应的右端常数 得b1 a12 300 1 300b2 a22 400 1 400b3 a32 250 1 250其中b3 a32的值最小 故确定原基变量中第三个约束方程中的基变量x5为出基变量 42 二 单纯形法的基本思路和原理 得到新的基 p2 p3 p4 令x1 x5 0 得x2 x3 3

16、00 x2 x4 400 x2 250求得新的基本可行解 0 250 50 150 0 目标函数值z 50 x1 100 x2 50 0 100 250 25000目标函数值得到了改进 43 思考 若不按最小比值法确定出基变量会怎么样 请大家计算一下 若在第一次迭代中不选x5出基 而让x3或x4出基 会出现什么情况 44 二 单纯形法的基本思路和原理 若让x3出基 则新的基为 p2 p4 p5 求得解为 0 300 0 100 50 非可行 若让x4出基 则新的基为 p2 p3 p5 求得解为 0 400 100 0 150 非可行 结论 按最小比值原则确定出基变量 可确保解可行 45 二 单纯形法的基本思路和原理 事实上 若取得的基不是单位阵 也可以通过初等行变换 将其化为单位阵 如基 p1 p2 p4 46 二 单纯形法的基本思路和原理 显然 该基本解为 50 250 0 50 0 47 二 单纯形法的基本思路和原理 如此迭代直到所有检验数均非正 则找到了线性规划问题的最优解 48 二 单纯形法的基本思路和原理 单纯形法求解思路总结 第一步找到初始可行基 单位阵 第二步检验解是否为