《规划论吕世林》PPT课件.ppt

线性规划 linearprogramming 与单纯形法 例 生产计划问题 如何合理使用有限的人力 物力和资金 使得收到最好的经济效益 如何合理使用有限的人力 物力和资金 以达到最经济的方式 完成生产计划的要求 一线性规划问题及其数学模型1问题的提出 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 人力约束9X1 4X2 360设备约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 以上两个问题的共同特征 每一个问题都用一组决策变量表示某一方案 这组决策变量的值就代表一个具体方案 一般变量取值是非负且连续的 这些问题中的所有参数都是确定的 不包含随机因素 存在一定的约束条件 可以用一组线性等式或线性不等式来表示 都有一个要求达到的目标 可用决策变量的线性函数 目标函数 来表示 按问题的不同 要求目标函数实现最大化或最小化 满足以上三个特征的数学模型称为线性规划的数学模型 线性规划数学模型三要素 决策变量 约束条件 目标函数 线性规划的一般模式 目标函数 max min Z c1x1 c2x2 c3x3 cnxn约束条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bn非负性约束 x1 0 x2 0 xn 0 线性规划 LP 是在有限资源的条件下 合理分配和利用资源 以期取得最佳的经济效益的优化方法 2线性规划图解法 已知 y ax b是一条直线 同理 Z 70 x1 120 x2 x2 70 120 x1 Z 120也是一条直线 以Z为参数的一族等值线 9x1 4x2 360 x1 360 9 4 9x2是直线x1 360 9 4 9x2下方的半平面 所有半平面的交集称之为可行域 可行域内的任意一点 就是满足所有约束条件的解 称之为可行解 例1图示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 概念 1 可行解 满足所有约束条件的解 2 可行域 即可行解的集合 所有约束条件的交集 也就是各半平面的公共部分 满足所有约束条件的解的集合 称为可行域 3 基解 约束条件的交点称为基解 直观 4 基可行解 基解当中的可行解 5 凸集 集合内任意两点的连线上的点均属于这个集合 如 实心球 三角形 结论 可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形 3线性规划的标准型 代数式maxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0j 1 2 n 和式 maxZ cjxj aijxj bii 1 2 mxj 0j 1 2 n 向量式 maxZ CX pjxj bii 1 2 mxj 0j 1 2 nC c1 c2 c3 cn X X1 X2 X3 Xn TPj a1j a2j anj T 矩阵式 maxZ CXAX bX 0其中 b b1 b2 bm T a11a12 a1nA a21a22 a2n am1am2 amn 000 0 非标准型转化为标准型 目标函数极小化转为极大化 minZ max Z 一个数的极小化等价于其相反数的极大化 不等式约束的转化 aijxj bi加入松弛变量 aijxj bi减去剩余变量非正变量 即xk 0则令x k xk自由变量 即xk无约束 令xk x k x k 标准型的特征 目标函数极大化 约束条件为等式 决策变量非负 非标准型转化举例之一 MaxZ 70X1 120X2maxZ 70X1 120X29X1 4X2 3609X1 4X2 X3 3604X1 5X2 2004X1 5X2 x4 2003X1 10X2 3003X1 10X2 x5 300X1 0X2 0Xj 0j 1 2 5 非标准型转化举例之二 MinZ x1 2x2 3x3maxZ x 1 2x2 3 x 3 x 3 x1 x2 x3 9 x 1 x2 x 3 x 3 x4 9 x1 2x2 x3 2x 1 2x2 x 3 x 3 x5 23x1 x2 3x3 5 3x 1 x2 3 x 3 x 3 5x1 0 x2 0 x3无约束x 1 0 x2 0 x 3 0 x 3 0 x4 0 x5 0 4基可行解 基解的概念 不失一般性 设B是A的前m列 即B p1 p2 pm 其相对应的变量XB x1 x2 xm T 称为基变量 其余变量XN Xm 1 Xn T称为非基变量 令所有非基变量等于零 则X x1 x2 xm 0 0 T称为基解 基可行解的概念 基可行解 基解可正可负 负则不可行 违背非负性约束条件 称满足所有约束条件的基解为基可行解 退化的基可行解 若某个基变量取值为零 则称之为退化的基可行解 基解的数目 最多 n m n m 基可行解说明 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5这里m 3 n 5 Cmn 10 基 p3 p4 p5 令非基变量x1 x2 0 则基变量x3 360 x4 200 x5 300 可行解基 p2 p4 p5 令非基变量x1 0 x3 0基变量x2 90 x4 250 x5 600 非可行解基 p2 p3 p4 令非基变量x1 x5 0 则基变量x2 30 x3 240 x4 50 可行解 图 二单纯形法 1初始基可行解的确定从系数矩阵中找到一个可行基B 不妨设B由A的前m列组成 即B P1 P2 Pm 进行等价变换 约束方程两端分别左乘B 1得X1 a 1m 1xm 1 a 1nxn b 1x2 a 2m 1xm 1 a 2nxn b 2 xm a mm 1xm 1 a mnxn b m令非基变量为0 得基可行解X 0 b1 b2 bm 0 0 Tz0 cibi 2最优性检验 LP经过若干步迭代 成为如下形式 X1 a 1m 1xm 1 a 1nxn b 1x1 b 1 a 1jxjx2 a 2m 1xm 1 a 2nxn b 2x2 b 2 a 2jxj xm a mm 1xm 1 a mnxn b mxm b m a mjxj 一般性表示 xi b i a ijxji 1 2 m将xi代入目标函数得 Z cjxj cixi cjxj ci b i a ijxj cjxj cibi cj cia ij xj令 j cj cia ijz0 cibi 则Z z0 jxj j判别准则 j 0时 达到最优解 j为检验数 3基变换若存在 j 0 则取max j K 相应之非基变量XK若取非零 将使Z增加 故令XK进基 令XK 0 其余非基变量保持为零 XK原是非基变量 取零值 若XK 0将迫使某个原基变量为零 当XK取值超过任意b i a ik时 将破坏非负性条件 于是令 min b i a ik a ik 0 b L a Lk 这时原基变量XL 0 由基变量变成非基变量 a Lk处在变量转换的交叉点上 称之为枢轴 主 元素 单纯形法解题举例 单纯形表的格式 4单纯形法的计算步骤 找到初始可行基 建立单纯形表计算检验数 若所有 j 0则得最优解 结束 否则转下步若某 K 0而P K 0 则最优解无界 结束 否则转下步根据max j K原则确定XK进基变量 根据 规则 min b i a ik a ik 0 b L a Lk确定XL为出基变量以a Lk为枢轴 主 元素进行迭代 回到第二步 非线性规划 参考