数学模型1-2单纯形法.pdf

1 单纯形法单纯形法 a11X1 a12X2 a1nXn b1 a21X1 a22X2 a2nXn b2 am1X1 am2X2 amnXn bm Xj 0 j 1 2 n MaxZ C1X1 C2X2 CnXn 2 可行解集 定义域 是什么 即由约束方程AX b所定 义的点集 称之为可行解集 空集 约束条件存在矛盾 无界集合 目标函数没有有限最优解 非空有界集合 有界闭凸集 凸集 连接集合中任意两点的直线仍然在集 合之中 3 基本思想 凸集的顶点 一个点不能够成为集合中两 点的中点 线性目标函数显然是连续函数 目标函数在顶点上达到最优值 如何检查各个顶点上的值以找到最优解 单纯形法实现了从顶点到使目标函数更大 的顶点上的跳跃 最终导致一个最优解 4 几个定义 线性方程组AX b基本解 设A的秩为m 线性方程组AX b的解向量X X1 X2 Xn n m个分量为0 其余m个分量对应于 A的m个线性无关列 取0的n m个分量称为 非基本变量 自由变量 其余的分量称 为基本变量 基本可行解 约束方程Ax b的基本解 5 一个定理 证明概要 1 证明基本可行解必然是顶点 若不然 x ay 1 a z 可得到x y z得到矛盾 2 证明可行解集顶点x是基本可行解 即要 说明在矩阵A中 顶点的所有正分量所在的列 线性无关 若相关 可以构造两个点y z 使 得 x y z 2与x为顶点矛盾 基本可行解顶点 6 定理证明 基本可行解是顶点 不妨设x x1 xm 0 0 若不然 如果 x y 1 z 由非负性 可以得到y和z 也有类似的形式 且非0分量对应于A的m 个线性无关列 又Ax Ay Az b 所以 x y z 矛盾 7 定理证明 续 顶点是基本可行解 即要说明如果x x1 x2 xn 是顶点 则x所有 正分量所对应的A的列一定线性无关 不妨 设x有k个非0分量 且不妨认为是前k个 对应的A的前k列为Aj j 1 2 k 则 8 定理证明 续 若A1 Ak线性相关 存在不全为0的系数cj j 1 2 k 使得c1A1 ckAk 0故对任 意d 0有 从而有x y z 2 x不是顶点 矛盾 9 单纯形法演示单纯形法演示 maxZ 40X1 50X2 X1 2X2 X3 30 3X1 2X2 X4 60 2X2 X5 24 X1 X5 0 10 解 1 确定初始可行解 B P3 P4 P5 I Z 0 40X1 50X2 X3 30 X1 2X2 X4 60 3X1 2X2 X5 24 2 X2 令X1 X2 0 X 1 0 0 30 60 24 T Z 1 0 11 2 判定解是否最优 Z 0 40X1 50X2 当X1从0 或X2从0 Z从0 X 1 不是最优解 12 3 由一个基本可行解 另一个基本可行解 50 40 选X2从0 X1 0 X3 30 2X2 0 X2 30 2 X4 60 2X2 0 X2 60 2 X5 24 2X2 0 X2 24 2 X2 min 30 2 60 2 24 2 12 X2进基本变量 X5出基本变量 13 Z 600 40X1 25X5 X3 6 X1 X5 X4 36 3X1 X5 X2 12 1 2X5 令X1 X5 0 X 2 0 12 6 36 0 T Z 2 600 B2 P3 P4 P2 14 2 判断 40 0 X 2 不是最优解 3 选X1从0 X5 0 X3 6 X1 0 X4 36 3X1 0 X2 12 0 X1 min 6 1 36 3 12 0 6 X1进基本变量 X3出基本变量 15 B3 P1 P4 P2 Z 840 40X3 15X5 X1 6 X3 X5 X4 18 3X3 2X5 X2 12 1 2X5 令X3 X5 0 X 3 6 12 0 18 0 T Z 3 840 16 2 15 0 X 3 不是最优解 3 选X5从0 X3 0 X1 6 X5 0 X4 18 2X5 0 X2 12 1 2 X5 0 X5 min 18 2 12 1 2 9 X5进基本变量 X4出基本变量 17 B4 P1 P5 P2 Z 975 35 2X 3 15 2X 4 X1 15 1 2X3 1 2X 4 X5 9 3 2X3 1 2X 4 X2 15 2 3 4X3 1 4X4 令X3 X4 0 X 4 15 15 2 0 0 9 T Z 4 975 18 单纯形表 C1 C2 Cm Cm 1 Cm k Cn X1 X2 Xm Xm 1 Xm k Xn CB XB Z0 0 0 0 m 1 m k n C1 X1 b1 1 0 0 a1 m 1 a1 m k a1 n C2 X2 b2 0 1 0 a2 m 1 a2 m k a2 n Cr Xr br 0 0 0 ar m 1 ar m k ar n Cm Xm bm 0 0 1 am m 1 am m k am n 19 40 50 0 0 0 X1 X2 X3 X4 X5 q CB XB 0 40 50 0 0 0 0 X330 1 2 1 0 0 15 0 X4 603 2 0 1 0 30 0 X5 24 0 2 0 0 1 12 XB 600 40 0 0 0 25 0 X3 6 1 0 1 0 1 6 0 X4 36 3 0 0 1 1 12 50 X2 12 0 1 0 0 1 2 840 0 0 40 0 15 40 X1 6 1 0 1 0 1 0 X4 18 0 0 3 1 2 9 50 X2 12 0 1 0 0 1 224 20 XB 975 0 0 35 2 15 2 0 40 X1 15 1 0 1 2 1 2 0 0 X5 9 0 0 3 2 1 2 1 50 X2 15 2 0 1 3 4 1 4 0 本问题的最优解 X 15 15 2 0 0 9 T Z 975 21 0 0 0 X2 X1 A D C B X2 X1 A D C B 0 12 6 12 15 7 5 22 单纯形法基本步骤 1 定初始基 初始基本可行解 3 若有 k 0 向量Pk的分量全 0 停 原线 性规划问题没有有限最优解 否则转 4 2 对应于非基变量检验数 j全 0 若是 停 得到最优解 若否 转 3 23 min ai m k 0 bi ai m k br ar m k 确定Xr为换出基本变量 ar m k为主元 寻找最小比值 max j m k 选取Xm k 为换入基本变量 j 0 4 24 5 做初等行变换 用新的非基本变量表示 基本变量和目标函数 转 2 25 单纯形法原理 单纯形法的关键 如何决定进基本变量和出基本变量 如何停止迭代 26 不妨设初始基本变量为XB X1 X2 Xm XN Xm 1 Xm 2 Xn 令相应的矩阵分块 为 对线性规划模型 27 28 两个记号 记 记 29 两个重要公式 XB B 1 b B 1 NXN Z CBTB 1 b CNT CBTB 1 N XN 当XN 0时 B 1 b 0 X Z CBTB 1 b 30 基本变量选择 进基本变量 从0变为非零 看其对目标函 数的影响 故取 k 0中最大的那一个所对应 的变量Xm k进基本变量 出基本变量 固定现有的非基本变量为零 进基本变量Xm k除外 看现有基本变量如 何随Xm k变化 哪一个最先达到零 就被选 中为出基本变量 同时 条件Pk a1 m k a2 m k am m k 0的要求就不难理解了 否则 所有的现有基本变量不可能变为零 31 停止规则 定理1 对解X 1 若检验数 j j m 1 n 全部 0 则X 1 为最优解 定理2 对X