线性规划及单纯形法.ppt

1 1线性规划问题及其数学模型 e g 1资源的合理利用问题 问 如何安排生产计划 使工厂获总利润最大 表1产品资源甲乙库存量A1360B1140单件利润1525 某工厂在下一个生产周期内生产甲 乙两种产品 要消耗A B两种资源 已知每件产品对这两种资源的消耗 这两种资源的现有数量和每件产品可获得的利润如表1 2 第二章线性规划及单纯形法 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 解 设x1 x2为下一个生产周期产品甲和乙的产量 约束条件 Subjectto x1 3x2 60 x1 x2 40 x1 x2 0 目标函数 z 15x1 25x2 表1产品资源甲乙库存量A1360B1140单件利润1525 决策变量 3 1线性规划问题及其数学模型 e g 2营养问题 假定在市场上可买到B1 B2 Bnn种食品 第i种食品的单价是ci 另外有m种营养A1 A2 Am 设Bj内含有Ai种营养数量为aij i 1 m j 1 n 又知人们每天对Ai营养的最少需要量为bi 见表2 表2食品最少营养B1B2 Bn需要量A1a11a12 a1nb1A2a21a22 a2nb2 Amam1am2 amnbm单价c1c2 cn 试在满足营养要求的前提下 确定食品的购买量 使食品的总价格最低 4 第二章线性规划及单纯形法 表2食品最少营养B1B2 Bn需要量A1a11a12 a1nb1A2a21a22 a2nb2 Amam1am2 amnbm单价c1c2 cn 解 设xj为购买食品Bj的数量 j 1 2 n i 1 2 m xj 0 j 1 2 n 0 xj lj 5 1线性规划问题及其数学模型 三个基本要素 Note 1 善于抓住关键因素 忽略对系统影响不大的因素 2 可以把一个大系统合理地分解成n个子系统处理 1 决策变量xj 0 2 约束条件 一组决策变量的线性等式或不等式 3 目标函数 决策变量的线性函数 6 第二章线性规划及单纯形法 max min z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn 或 b1a21x1 a22x2 a2nxn 或 b2 am1x1 am2x2 amnxn 或 bmxj 0 j 1 2 n 其中aij bi cj i 1 2 m j 1 2 n 为已知常数 7 1线性规划问题及其数学模型 线性规划问题的标准形式 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0 j 1 2 n bi 0 i 1 2 m 特点 1 目标函数为极大化 2 除决策变量的非负约束外 所有的约束条件都是等式 且右端常数均为非负 3 所有决策变量均非负 8 第二章线性规划及单纯形法 如何转化为标准形式 1 目标函数为求极小值 即为 因为求minz等价于求max z 令z z 即化为 2 约束条件为不等式 xn 1 0松弛变量 如何处理 9 1线性规划问题及其数学模型 右端项bi 0时 只需将等式两端同乘 1 则右端项必大于零 4 决策变量无非负约束 设xj没有非负约束 若xj 0 可令xj xj 则xj 0 又若xj为自由变量 即xj可为任意实数 可令xj xj xj 且xj xj 0 10 第二章线性规划及单纯形法 e g 3 试将LP问题 minz x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0化为标准形式 解 令x3 x4 x5其中x4 x5 0 对第一个约束条件加上松弛变量x6 对第二个约束条件减去松弛变量x7 对第三个约束条件两边乘以 1 令z z把求minz改为求maxz maxz x1 2x2 3x4 3x5s t x1 x2 x4 x5 x6 7x1 x2 x4 x5 x7 23x1 x2 2x4 2x5 5x1 x2 x4 x5 x6 x7 0 11 1线性规划问题及其数学模型 LP的几种表示形式 12 2线性规划问题的图解法 定义1在LP问题中 凡满足约束条件 2 3 的解x x1 x2 xn T称为LP问题的可行解 所有可行解的集合称为可行解集 或可行域 记作D x Ax b x 0 定义2设LP问题的可行域为D 若存在x D 使得对任意的x D都有cx cx 则称x 为LP问题的最优解 相应的目标函数值称为最优值 记作z cx 13 2线性规划问题的图解法 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 40 0 0 0 B C 30 10 O L1 L2 Z 250 目标函数变形 x2 3 5x1 z 25 x2 x1 最优解 x1 30 x2 10最优值 zmax 700 B点是使z达到最大的唯一可行点 14 第二章线性规划及单纯形法 LP问题图解法的基本步骤 1 在平面上建立直角坐标系 2 图示约束条件 确定可行域和顶点坐标 3 图示目标函数 等值线 和移动方向 4 寻找最优解 15 2线性规划问题的图解法 maxz 3x1 5 7x2s t x1 1 9x2 3 8x1 1 9x2 3 8x1 1 9x2 11 4x1 1 9x2 3 8x1 x2 0 x1 x2 o x1 1 9x2 3 8 x1 1 9x2 3 8 x1 1 9x2 11 4 7 6 2 D 0 3x1 5 7x2 maxZ minZ 3 8 4 34 2 3x1 5 7x2 可行域 x1 1 9x2 3 8 0 2 3 8 0 绿色线段上的所有点都是最优解 即有无穷多最优解 Zman 34 2 16 第二章线性规划及单纯形法 maxz 2x1 2x2s t 2x1 x2 2 x1 4x2 4x1 x2 0 O x1 x2 Note 可行域为无界区域 目标函数值可无限增大 即解无界 称为无最优解 可行域为无界区域一定无最优解吗 17 2线性规划问题的图解法 由以上两例分析可得如下重要结论 1 LP问题从解的角度可分为 有可行解 无可行解 a 有唯一最优解b 有无穷多最优解c 无最优解 2 LP问题若有最优解 必在可行域的某个顶点上取到 若有两个顶点上同时取到 则这两点的连线上任一点都是最优解 18 2线性规划问题的图解法 图解法优点 直观 易掌握 有助于了解解的结构 图解法缺点 只能解决低维问题 对高维无能为力 19 3线性规划问题解的基本性质 讨论如下LP问题 其中 系数矩阵 决策向量 假设A的秩为m 且只讨论m n的情形 什么意思 为什么 20 第二章线性规划及单纯形法 定义3在上述LP问题中 约束方程组 2 的系数矩阵A的任意一个m m阶的非奇异的子方阵B 即 B 0 称为LP问题的一个基阵或基 称pi i 1 2 m 为基向量 xi i 1 2 m 为基变量 xj j m 1 n 为非基变量 pj j m 1 n 为非基向量 记 则A B N 21 3线性规划问题解的基本性质 A B N xB x1 xm T xN xm 1 xn T 则 代入约束方程 2 得 自由变量 独立变量 令 称 4 为相应于基B的基本解 22 第二章线性规划及单纯形法 是可行解吗 maxz x1 2x2 3x4 3x5s t x1 x2 x4 x5 x6 7x1 x2 x4 x5 x7 23x1 x2 2x4 2x5 5x1 x2 x4 x5 x6 x7 0 令x1 x2 x4 0 如果B 1b 0 则称 4 为相应于基B的基可行解 此时的基B称为可行基 23 3线性规划问题解的基本性质 基本解唯一吗 最多有多少 称它是非退化的解 反之 如果有一个基变量也取零值 则称它是退化的解 一个LP问题 如果它的所有基可行解都是非退化的就称该是非退化的 否则就称它是退化的 24 第二章线性规划及单纯形法 LP问题解的基本性质 Ax 0 定理2 定理3称为LP问题的基本定理 定理2证明 向前 定理3证明 LP问题是一个组合优化问题 25 3线性规划问题解的基本性质 定理2证明 设x x1 x2 xn T是LP问题的一个可行解 如果x 0 则由定理1知 它是LP问题的一个基可行解 定理成立 如果x 0 不妨设x的前k个分量为非零分量 则有x1p1 x2p2 xkpk b 及x1 0 x2 0 xk 0 分两种情况讨论 如果p1 p2 pk线性无关 即x的非零分量对应的列向量线性无关 则由定理1知 它是LP的一个基本可行解 定理成立 2 如果p1 p2 pk线性相关 则必存在一组不全为零的数 1 2 k使得 26 第二章线性规划及单纯形法 假定有 i 0 取 作 其中 由 6 式知 必有 即 又因为由 5 式知 故有 即 也是LP的两个可行解 27 3线性规划问题解的基本性质 再由的取法知 在式 7 的诸式中 至少有一个等于零 于是所作的可行解中 它的非零分量的个数至少比x的减少1 如果这些非零分量所对应的列向量线性无关 则为基可行解 定理成立 否则 可以从出发 重复上述步骤 再构造一个新的可行解 使它的非零分量的个数继续减少 这样经过有限次重复之后 必可找到一个可行解使它的非零分量对应的列向量线性无关 故可行解必为基可行解 证毕 返回 28 3线性规划问题解的基本性质 定理3证明 设 是LP的一个最优解 如果x 是基本解 则定理成立 如果x 不是基本解 则由定理2的证明过程可构造两个可行解 它的非零分量的个数比x 的减少 且有 又因为x 是最优解 故有 由式 8 和 9 知 必有 即x 1 x 2 仍为最优解 如果x 1 或x 2 是基可行解 则定理成立 否则 按定理2证明过程 可得基可行解x s 或x s 1 使得 即得基可行解x s 或x s 1 为最优解 返回 29 第二章线性规划及单纯形法 LP问题解的几何意义 定义5设集合是n维欧氏空间中的一个点集 如果及实数 则称S是一个凸集 几何意义 如果集合中任意两点连线上的一切点都在该集合中 则称该集合为凸集 Note 空集和单点集也是凸集 30 3线性规划问题解的基本性质 定义6设则称 为点的一个凸组合 31 第二章线性规划及单纯形法 定理5设D为LP问题的可行解集 则x是D的极点的充分必要条件是x为LP问题的基可行解 prove 此时 该LP问题有无穷多最优解 32 3线性规划问题解的基本性质 Note 1 如何判断LP问题有最优解 2 计算复杂性问题 设有一个50个变量 20个约束等式的LP问题 则最多可能有个基 即约150万年 33 4单纯形法的基本原理 单纯形法 SimplexMethod 是1947年由G B Dantzig提出 是解LP问题最有效的算法之一 且已成为整数规划和非线性规划某些算法的基础 基本思路 基于LP问题的标准形式 先设法找到一个基可行解 判断它是否是最优解 如果是则停止计算 否则 则转换到相邻的目标函数值不减的一个基可行解 两个基可行解相邻是指它们之间仅有一个基变量不相同 34 第二章线性规划及单纯形法 单纯形法引例 首先 化原问题为标准形式 x3 x4是基变量 基变量用非基变量表示 x3 60 x1 3x2x4 40 x1 x2 代入目标函数 z 15x1 25x2 令非基变量x1 x2 0 z 0基可行解x 0 0 0 60 40 T 是最优解吗 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 maxz 15x1 25x2 0 x3 0 x4s t x1 3x2 x3 60 x1 x2 x4 40 x1 x2 x3 x4 0 35 4单纯形法的基本原理 z 15x1 25x2x3 60 x1 3x2x4 40 x1 x2 因为x2的系数大 所以x2换入基变量 x3 60 3x2 0 x4 40 x2 0 谁换出 如果x4换出 则x2 40 x3 60 不可行 如果是 会怎样 如果x3换出 则x2 20 x4 20 最小比值法则 所以x3换出 基变量用非基变量表示 代入目标函数 z 500 20 3x1 25 3x3 令非基变量x1 x3 0 z 500基可行解x 1 0 20 0 20 T 大于零 36 第二章线性规划及单纯形法 因为x1的系数大 所以x1换入基变量 所以x4换出 基变量用非基变量表示 代入目标函数 z 700 5x3 10 x4 令非基变量x3 x4 0 z 700基可行解x 2 30 10 0 0 T 因为非基变量的系数都小于零 所以x 2 30 10 0 0 T是最优解zmax 700 37 4单纯形法的基本原理 目标函数用非基变量表示时 非基变量的系数称为检验数 40 0 0 0 0 20 A B C 30 10 O L1 L2 Z 250 x2 x1 x 0 0 0 60 40 Tz 0 x 1 0 20 0 20 Tz 500 x 2 30 10 0 0 Tz 700 38 第二章线性规划及单纯形法 单纯形法的基本原理 称 1a 2a 3a 为LP问题对应于基B的典则形式 典式 Ax b 基变量用非基变量表示 代入目标函数 39 4单纯形法的基本原理 如果记 则典式 1a 2a 3a 可写成 40 第二章线性规划及单纯形法 定理7在LP问题的典式 1b 3b 中 如果有 则对应于基B的基可行解 是LP问题的最优解 记为 相应的目标函数最优值z z 0 此时 基B称为最优基 41 4单纯形法的基本原理 定理8在LP问题的典式 1b 3b 中 是对应于基B的一个基可行解 如果满足下列条件 1 有某个非基变量xk的检验数 k 0 m 1 k n 2 aik i 1 2 m 不全小于或等于零 即至少有一个aik 0 i 1 2 m 3 0 i 1 2 m 即x 0 为非退化的基可行解 则从x 0 出发 一定能找到一个新的基可行解 42 第二章线性规划及单纯形法 定理9在LP问题的典式 1b 3b 中 如果检验数满足最优准则 j 0 j m 1 n 且其中有一个 k 0 m 1 k n 则该LP问题有无穷多个最优解 这在应用中很有价值 则该LP问题解无界 无最优解 43 5单纯形法的计算步骤 单纯形表 44 第二章线性规划及单纯形法 如何得到单纯形表 B 1b cBB 1b 检验数 BN cBcN IB 1N 0cN cBB 1N 45 5单纯形法的计算步骤 e g 4列出如下LP问题的初始单纯形表 maxz 4x1 3x2 2x3 5x4s t x1 3x2 x3 2x4 54x1 2x2 3x3 7x4 17x1 x2 x3 x4 0 不妨已知x3 x4为可行基变量 1 7 0 1 2 6 31 0 5 2 1 17 1 0 1 1 4 0 12 x 0 0 0 1 2 T z0 12 46 第二章线性规划及单纯形法 单纯形法求解LP问题的计算步骤 Step1找出初始可行基 列初始单纯形表 确定初始基可行解 Step2检验各非基变量xj的检验数 j 如果所有的 j 0 j 1 2 n 则已求得最优解 停止计算 否则转入下一步 Step3在所有的 j 0中 如果有某个 k 0 所对应的xk的系数列向量p k 0 即a ik 0 i 1 2 m 则此问题解无界 停止计算 否则转入下一步 47 5单纯形法的计算步骤 Step4根据 确定xk为换入基变量 又根据最小比值法则计算 确定xr为换出基变量 转入下一步 Step5以为主元进行换基变换 用初等行变换将xk所对应的列向量变换成单位列向量 即 同时将检验数行中的第k个元素也变换为零 得到新的单纯形表 返回Step2 48 第二章线性规划及单纯形法 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 maxz 15x1 25x2 0 x3 0 x4s t x1 3x2 x3 60 x1 x2 x4 40 x1 x2 x3 x4 0 0 0 x2 1 3 500 x1 0 700 1 2 检验数都小于等于零 x 2 为最优解zmax 700 60 3 40 1 25 3 1 3 1 20 0 0 1 3 1 20 20 3 25 3 0 20 1 3 20 2 3 15 2 3 2 3 1 0 1 2 3 2 30 0 1 2 10 0 5 10 49 5单纯形法的计算步骤 思考 在单纯形法中根据 确定xk为进基变量 是否在这次变换中 使目标函数值提高最大 如果不是 应选择哪个变量进基 保证这次变换使得目标函数值提高最大 目标函数值能提高多少 50 6单纯形法的进一步讨论 一 初始可行基的求法 maxz c1x1 c2x2 cnxn 1c s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 2c am1x1 am2x2 amnxn bmxj 0 j 1 2 n 3c a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmxj 0 j 1 2 n n 1 n m 人工变量 1 试算法 人造基本解 x0 0 0 0 b1 bm T 2 人工变量法 51 6单纯形法的进一步讨论 1 大M法 惩罚法 maxw c1x1 c2x2 cnxn M xn 1 xn m s t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmxj 0 j 1 2 n n 1 n m M是一个充分大的正数 结论 设 为上述问题的最优解 则 为原问题的最优解 这时的目标函数值为最优值 则原问题无可行解 不全为零 52 第二章线性规划及单纯形法 e g 5 用大M法求解 maxz 3x1 x2 x3s t x1 2x2 x3 11 4x1 x2 2x3 3 2x1 x3 1x1 x2 x3 0 maxz 3x1 x2 x3 0 x4 0 x5 Mx6 Mx7s t x1 2x2 x3 x4 11 4x1 x2 2x3 x5 x6 3 2x1 x3 x7 1xj 0 j 1 2 7 解 引入松弛变量x4 x5和人工变量x6 x7得 3 4M M 1 2M 1 0 M 0 M 3M 3 6M M 1 3M 1 0 M 0 0 4M 11 1 3 2 1 1 x3 1 1 3 2 0 1 1 0 0 1 10 0 1 0 0 1 1 2 1 1 M 1 0 0 M 1 3M M 1 1 1 1 x2 1 3 0 0 1 2 2 5 12 1 0 0 0 1 1 M 2 1 12 3 x1 3 0 0 1 3 2 3 2 3 5 3 4 0 0 1 2 3 4 3 4 3 7 3 9 0 0 0 1 3 1 3 2 3 M 2 3 1 0 1 M 1 3 M 200 0 2M 0 由于人工变量x6 x7 0 所以 得原问题的最优解x 4 1 9 0 0 T目标函数最优值zmax 2 Note 在计算过程中 某个人工变量一旦变为非基变量 则该列可被删去 53 6单纯形法的进一步讨论 2 两阶段法 第一阶段 maxz c1x1 c2x2 cnxn 1c s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 2c am1x1 am2x2 amnxn bmxj 0 j 1 2 n 3c maxw xn 1 xn 2 xn m 1d s t a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 2d am1x1 am2x2 amnxn xn m bmxj 0 j 1 2 n n 1 n m 3d 判断原LP问题 1c 3c 是否存在可行解 如果存在就找出一个初始基可行解 解之可得 a 如果wmax 0 则原问题无可行解 停止计算 b 如果wmax 0 且人工变量都不是基变量 则转入第二阶段 54 第二章线性规划及单纯形法 c 如果wmax 0 但仍有取零的人工变量为基变量 x1x2 xnxn 1 xn k xn mba l1a l2 a lna ln 1 1 a n m0 如xn k 0是基变量 在最终单纯形表中 a l1a l2 a ln不可能全为零 必有某个a lj 0 这时xj不是基变量 与xn k交换即可 第二阶段 从第一阶段所求得的初始可行基出发 求解原问题 55 6单纯形法的进一步讨论 二 关于退化和循环 1955年Beale给出如下例子 最优解 B0 P1 P2 P3 作为初始可行基 经6次迭代又得B0 56 第二章线性规划及单纯形法 Bland法则 对极大值问题而言 则选择xk作为进基变量 57 7线性规划应用举例 e g 6生产计划问题 某工厂明年根据合同 每个季度末向销售公司提供产品 有关信息如表 若当季生产的产品过多 季末有积余 则一个季度每积压一吨产品需支付存贮费0 2万元 现该厂考虑明年的最佳生产方案 使该厂在完成合同的情况下 全年的生产费用最低 试建立线性规划模型 58 第二章线性规划及单纯形法 解 方法一 设工厂第j季度生产产品xj吨 需求约束 第一季度末需交货20吨 x1 20 第二季度末需交货20吨 x1 20 x2 20 这是上季末交货后积余 第三季度末需交货30吨 x1 x2 40 x3 30 第四季度末需交货10吨 x1 x2 x3 70 x4 10 生产能力约束 0 xj ajj 1 2 3 4 生产 存储费用 第一季度 15x1第二季度 14x2 0 2 x1 20 第三季度 15 3x3 0 2 x1 x2 40