线性规划上课课件.ppt

MaxZ CXs t AX bX 0 基 基解 基可行解 可行基 线性规划问题的可行域D是凸集 顶点与基可行解相对应 线性规划问题的最优解 必定在D的顶点上达到 目标函数在多个顶点上达到最优值 这些顶点的凸组合也是最优值 有无穷多最优解 第3节线性规划 单纯形方法单纯形方法基本思路 从可行域中某个基可行解 一个顶点 开始 称为初始基可行解 线性规划 2 单纯形方法单纯形方法基本思路 从可行域中某个基可行解 一个顶点 开始 称为初始基可行解 如可能 从可行域中求出具有更优目标函数值的另一个基可行解 另一个顶点 以改进初始解 线性规划 2 单纯形方法单纯形方法基本思路 从可行域中某个基可行解 一个顶点 开始 称为初始基可行解 如可能 从可行域中求出具有更优目标函数值的另一个基可行解 另一个顶点 以改进初始解 继续寻找更优的基可行解 进一步改进目标函数值 当某一个基可行解不能再改善时 该解就是最优解 第三节线性规划 单纯形方法单纯形方法基本思路 1 从可行域中某个基可行解 一个顶点 开始 称为初始基可行解 2 如可能 从可行域中求出具有更优目标函数值的另一个基可行解 另一个顶点 以改进初始解 3 继续寻找更优的基础可行解 进一步改进目标函数值 当某一个基可行解不能再改善时 该解就是最优解 一 消去法例1 一个企业需要同一两种原材料生产甲乙两种产品 它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同 从而获得的利润也不相同 如下表 那么 该企业应如何安排生产计划 才能使获得的利润达到最大 解 数学模型maxZ 2x1 3x2s t x1 2x2 84x1 164x2 12x1 x2 0 解 引进松弛变量x3 x4 x5 0数学模型标准形式 maxZ 2x1 3x2s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 约束条件的增广矩阵为 121008 Ab 40010160400112显然r A r Ab 3 5 该问题有无穷多组解 令A P1 P2 P3 P4 P5 121004001004001X x1 x2 x3 x4 x5 A P1 P2 P3 P4 P5 121004001004001X x1 x2 x3 x4 x5 TB P3 P4 P5 100010001x3 x4 x5是基变量 x1 x2 是非基变量 用非基变量表示的方程 x3 8 x1 2x2x4 16 4x1 I x5 12 4x2Z 0 2x1 3x2称 I 为消去系统 令非基变量 x1 x2 T 0 0 T得基可行解 x 1 0 0 8 16 12 TZ1 0经济含义 不生产产品甲乙 利润为零 分析 Z 0 2x1 3x2 分别增加单位产品甲 乙 目标函数分别增加2 3 即利润分别增加2百元 3百元 增加单位产品对目标函数的贡献 这就是检验数的概念 增加单位产品乙 x2 比甲对目标函数的贡献大 检验数最大 把非基变量x2换成基变量 称x2为换入基变量 而把基变量x5换成非基变量 称x5为换出基变量 在选择出基变量时 一定保证消去系统为正消去系统 最小比值原则 增加单位产品甲 x2 比乙对目标函数的贡献大 检验数最大 把非基变量x2换成基变量 称x2为换入基变量 而把基变量x5换成非基变量 称x5为换出基变量 在选择出基变量时 一定保证消去系统为正消去系统 最小比值原则 事实上 当x1 0 有x3 8 2x2 0 x4 16 0 x5 12 4x2 0min 8 2 12 4 3 当x2 0时 x5 0 x5换出基变量 确定了换入变量x2 换出变量x5以后 得到新的消去系统 x3 2x2 8 x1 1 x3 2 x1 1 2 x5x4 16 4x1 2 即 x4 16 4x14x2 12 x5 3 x2 3 1 4 x5其中 1 1 2 3 Z 9 2x1 3 4 x5令新的非基变量 x1 x5 0 0 T得到新的基可行解 x 2 0 3 2 16 0 TS2 9经济含义 生产乙产品3个 获得利润9百元 这个方案比前方案好 但是否是最优 这个方案比前方案好 但是否是最优 分析 Z 9 2x1 3 4 x5非基变量x1系数仍为正数 确定x1为换入变量 在保证正消去系统的情况下 确定x3为换出变量 得到新的消去系统 这个方案比前方案 但是否是最优 分析 Z 180 x2 3 2 x4非基变量x2系数仍为负数 确定x2为换入变量 在保证常数项非负的情况下 x1换入 x5 0 有x3 2 x1 0 x4 16 4x1 0 x2 3 0min 2 4 2确定x3为换出变量 得到新的消去系统 x1 2 x3 1 2 x5x1 2 x3 1 2 x54x1 x4 16 即x4 8 4x3 2x5x2 3 1 4 x5x2 3 1 4 x5Z 13 2x3 1 4 x5令新的非基变量 x3 x5 0 0 T得到新的基可行解 x 3 2 3 0 16 0 TS3 13经济含义 生产甲产品2个 乙产品3个 获得利润1300元 分析 Z 13 2x3 1 4 x5x5系数仍为正数 确定x5为换入变量 在保证常数项非负的情况下 x5换入 x3 0 有x1 2 1 2 x5 0 x4 8 2x5 0 x2 3 1 4 x5 0min 4 12 4确定x4为换出变量 有x1 1 2 x5 2 x32x5 8 4x3 x4x2 1 4 x5 3 即 x1 4 1 4 x4x5 4 2x3 1 2 x4 x2 2 1 2 x3 1 8 x4Z 14 3 2 x3 1 8 x4得到新的消去系统目标函数中的非基变量的系数无正数 S4 14是最优值 x 4 4 2 0 0 4 T是最优解 该企业分别生产甲产品4个 乙产品2个可获得利润1400元 x2 50 40 30 20 10 x1 maxZ 2x1 3x2s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 Q1 Q2X4 X2Q4 X1O X3Q3 4x2 12 4x1 16 x1 2x2 8 X1 0 0 X2 0 3 X3 2 3 X4 4 2 二 已知初始可行基求最优解线性规划标准型的矩阵形式 MAXZ CX 1 s t AX b 2 X 0 3 a11a12 a1nb1A a21a22 a2nb b2 am1am2 amnbn c1x10c2x20Ct X 0 xn0并且r A m n 1 初始可行基的确定和最优解判别 不妨假设A B N B为一个基 相应地有XT XB XN C CB CN 由 1 17 1 18 Z CB CN XB XN T CBXB CNXNAX B N XB XN T BXB NXN b 因为B为一个基 B 0有XB B 1b B 1NXNZ CBXB CNXN CBB 1b CN CBB 1N XN令非基变量XN 0则X XB XN T B 1b 0 T为基解 其目标函数值为Z CBB 1b只要XB B 1b 0 X B 1b 0 T 0X为基可行解 B就是可行基 另外 若满足CN CBB 1N 0或CBB 1N CN 0则对任意的x 0有Z CX CBB 1b即对应可行基B的可行解x为最优解 定理 最优解判别准则 对于可行基B 若C CBB 1A 0则对应于基B的基可行解x就是基最优解 此时的可行基就是最优基 C CBB 1A为检验数 基变量的检验数 CB CBB 1B 0C CBB 1A 0 CN CBB 1N 换入基变量中 得到基可行解 定理 若检验数全小于等于零 且某一个非基变量的检验数为0 则线性规划问题有无穷多最优解 无穷多最优解情况 证明 某个非基变量 为最优解 故线性规划问题有无穷多最优解 为一基可行解 有一个变量Xm k对应 因 为可行解 定理 若存在检验数大于零 但所对应的换入变量Xm k的系数向量Pm k 0 则原问题无最优解 无界解的情况 证明 构造一个新的解 分量为 定理 若非基变量检验数严格小于零 则线性规划问题有唯一最优解 定理 若检验数全小于等于零 且某一个非基变量的检验数为0 则线性规划问题有无穷多最优解 定理 若某一个非基变量的检验数大于0 其系数列向量Pm k 0 则原问题无最优解 无界解的情况 线性规划为求最大化的标准型 线性规划为求最小化的标准型时 相应的结果 单纯形表 T B B 1bB 1ACBB 1bC CBB 1A B 1bIB 1NCBB 1b0CN CBB 1N注意 A B N 检验数 C CBB 1A 0 CN CBB 1N 非基变量检验数 CN CBB 1N 时 达到最优 单纯形表格 单纯形解题步骤 已知初始可行基 求最大化时一 作对应B的单纯形表 T B B 1bB 1ACBB 1bC CBB 1A B 1bIB 1NCBB 1b0CN CBB 1N 单纯形解题步骤 二 判别若检验数全小于等于零 则基B所对应的基础可行解X就是最优解 终止 若存在检验数大于零 但所对应的换入变量Xk的系数向量Pk 0 则原问题无最优解 终止 若存在检验数大于零 且对应的系数列有大于零的分量 则需要换基迭代 三 换基迭代确定换入变量Xk 其中max j 0 k xk为换入变量j 1 2 m确定换出基变量Xr 根据最小比值原则min bi aik aik 0 1 i m bl blkalk为主元素 Xl为换出基变量 对单纯形表T B 进行初等行变换 主元运算 得到新的单纯形表 经过上述有限次的换基迭代 就可得到原问题的最优解 或判定无最优解 例1 19求线性规划问题 maxZ 2x1 3x2s t x1 2x2 0 解 对目标函数标准化maxZ 2x1 3x2s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 012100A 4001004001 x1x2x3x4x5 NB 解 100B 010 Ib 8 16 12 T001x3x4 x5为基变量 CB 0 0 0 x1 x2为非基变量 有B 1 I B 1b b B 1A A 单纯性表如下 初始单纯性表TAB 1 为 x2换入 x5换出 得TAB 2 为 x1换入 x3换出 得TAB 3 为 x5换入 x4换出 得TAB 4 为 此时所有的检验数小于等于零 此时的基可行解X 4 2 0 0 4 T就是最优解 对应的目标函数值 Z 14就是最优值 对应的B4就是最优基 求最大化LP问题单纯形表解题步骤 一 LP问题化成标准型 列初始单纯形表 二 判别1 若检验数全小于等于零 则基B所对应的基础可行解X就是最优解 终止 2 若存在检验数大于零 但所对应的换入变量Xk的系数向量Pk 0 则原问题无最优解 终止 3 若存在检验数大于零 且对应的系数列有大于零的分量 则需要换基迭代 三 换基迭代1 确定换入变量Xk 其中max j 0 k xk为换入变量j 1 2 m2 确定换出基变量Xr 根据最小比值原则min bi aik aik 0 1 i m bl blkalk为主元素 Xl为换出基变量 对单纯形表T B 进行初等行变换 主元运算 得到新的单纯形表 经过上述有限次的换基迭代 就可得到原问题的最优解 或判定无最优解 定理 求最小化的最优解判别准则 1 若 C CBB 1A 0 则对应于基B的基础可行解x就是基础最优解 此时的可行基就是最优基 2 若检验数全大于等于零 且某一个非基变量的检验数为0 则线性规划问题有无穷多最优解 无穷多最优解情况 3 若存在检验数小于零 但所对应的换入变量Xm k的系数向量Pm k 0 则原问题无最优解 无界解的情况 确定换入变量时 找小于0中的最小者 例8线性规划问题 一 大M法 当原问题求最大化时 假定人工变量在目标函数中的系数为 M M为任意大正数 目标函数求最大化 必须把人工变量从基变量换出 否则 不可能实现最大化 当原问题求最小化时 假定人工变量在目标函数中的系数为M M为任意大正数 目标函数求最小化 必须把人工变量从基变量换出 否则 不可能实现最小化 例8线性规划问题 31100MM cj cj 31100MM 线性规划问题达到最优 最优解及最优值为 二 两阶段法 当用计算机求解含人工变量的线性规划问题时 只能用很大的数代替M 否则 会造成计算机的错误 而两阶段法避免了这一错误 第一阶段 不考虑原问题是否存在基可行解 给原线性规划问题加入人工变量 构造目标函数为人工变量的和 约束是原问题的约束 用单纯形法求解上述模型 若目标函数值为0 说明原问题有基可行解 进行第二阶段计算 否则 原问题无可行解 第二阶段 将第一阶段计算得到的最终表 除去人工变量 将目标函数行的系数 换为原问题的目标函数系数 作为第二阶段计算的初始表 例9线性规划问题 解 加入人工变量 给出第一阶段的线性规划模型 人工变量已经换出 则 0 得到基可行解 将第一阶段的人工变量取消 填入原问题的目标函数的系数 进行第二阶段运算 cj 0000011 人工变量已经换出 则 0 得到基可行解 将第一阶段的人工变量取消 即上表中划去人工变量所在列 填入原问题的目标函数的系数 进行第二阶段运算 cj 31100 最优解为 x1 4 x2 1 x3 9 最优值z 2 应用举例 例1配料问题某工厂要用三种原材料C P H混合调配出三种不同规格的产品A B D 已知产品的规格要求 产品单价 每天能供应的原材料数量及原材料单价见下表 该厂应如何安排生产 使利润收入为最大 解 设xij为产品A B D中含C P H的公斤数 列表如下 解 数学模型为 例2连续投资问题某部门有100万元 在今后五年内考虑给下列项目进行投资项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利104 项目B 从第三年初投资 到第五年末回收本利105 但规定最大投资额不超过40万元 项目C 从第二年初投资 到第五年末回收本利108 但规定最大投资额不超过30万元 项目D 五年内每年可购买国债 于当年末归还 并加息3 问该部门如何确定每年的投资计划 使五年末拥有的本金最大 解 设xiA xiB xiC xiD 分别表示第i年年初给项目A B C D的投资额 列表如下 数学模型为 人力资源分配的问题解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们建立如下的数学模型 目标函数 MinZ x1 x2 x3 x4 x5 x6s t x1 x6 60 x1 x2 70 x2 x3 60