管理运筹学 第一章线性规划及单纯形法.ppt

第一章线性规划及单纯形法LinearProgrammingandSimplexMethod 北京物资学院运筹学教学课件 北京物资学院信息学院李珍萍2017年2月 第一节线性规划问题的数学模型第二节两变量线性规划问题的图解法第三节线性规划问题的基本定理第四节单纯形法第五节单纯形法的进一步讨论第六节线性规划应用案例分析 本章内容 第一节线性规划问题的数学模型 线性规划是运筹学中研究较早 发展较快 应用较广 比较成熟的一个分支 它是一种合理利用和调配有限资源的数学方法 线性规划研究的问题 极大化问题 面对一定的资源 要求充分利用 以获得最大的经济效益 极小化问题 给定一项任务 要求统筹安排 尽量做到用最少的人力 物力资源去完成这一任务 一 引例 生产安排问题原料配比问题运输问题二 线性规划问题的结构特征三 线性规划问题的数学模型线性规划问题的一般形式线性规划问题的标准形式一般形式向标准形式的转化 本节内容安排 一 引例 例1 生产安排问题 某企业使用A B C三台机器生产甲 乙两种产品 已知未来两周内A B C三台机器的使用时间分别不得超过80 60 45小时 生产每单位产品所需要各台机器的加工时间及每单位产品的利润如下表所示 问企业如何安排未来两周的生产 才能使总利润达到最大 可控因素 生产两种产品的数量 设分别为x1 x2 目标是生产利润最大 设生产利润为z 利润函数为 限制条件 三台设备的使用时间不超过可利用机时设备A 2x1 4x2 80设备B 3x1 2x2 60设备C 3x1 45 蕴涵约束 产量为非负x1 0 x2 0 目标函数约束条件 设生产甲乙两种产品的数量分别为x1 x2单位 总利润为z 例2 原料配比问题 某企业使用三种原料B1 B2 B3配制某种食品 要求食品中蛋白质 脂肪 糖 维生素的含量分别不低于15 20 25 30单位 以上三种原料的单价以及每单位原料所含各种成分的数量如下表所示 问应如何配置食品 才能使成本最低 设x1 x2 x3分别表示原料B1 B2 B3的用量 z表示食品成本 该问题的数学模型为 例3 运输问题 设要从甲地调出物资2000吨 从乙地调出物资600吨 从丙地调出物资500吨 分别供应给A地1700吨 B地1100吨 C地200吨 D地100吨 已知每吨运费如下表所示 假定运费与运量成正比例 问怎样才能找到一个总运费最省的调拨计划 丙 17 26 38 43 15 37 51 51 乙 15 7 25 21 甲 D C B A 销地产地 单位 元 吨 用 i 1 2 3 j 1 2 3 4 分别表示从甲乙丙三个产地运往A B C D四个销地的物资数量 则该问题的数学模型为 简化表达式 二 线性规划问题的结构特征 1 都有一组决策变量 2 都有一组线性的约束条件 它们是线性等式或不等式 3 都有一个确定的目标 这个目标可以表示成决策变量的线性函数 根据问题不同 有的要求实现极大化 有的要求实现极小化 线性规划问题的本质 研究在一组线性约束下 一个线性函数的极值问题 所以称为线性规划linearprogramming LP 1 线性规划问题的一般形式 一般形式的简化表达 三 线性规划问题的数学模型 规范形式 极大化问题 极小化问题 2 线性规划的标准形式 标准形式的简化表达 标准形式的矩阵表达 标准形式的向量表达 标准形式的特点 1 目标函数极大化 2 约束条件全部是等式 3 所有的变量都是非负的 4 约束条件右端常数为非负的 3 一般形式向标准形式的转化 1 目标函数极大化 2 不等式约束化等式约束 对于形的不等式 可以在不等式的左边加上 减去 一个非负的变量使不等式化成等式 这样的变量称为松弛 剩余 变量 例如 3 自由变量化非负变量的差 自由变量可以用两个非负变量的差代替 例如对于一个符号无限制的变量 可以引进两个非负变量并设 4 约束条件右端的负常数化为正常数 对于右端常数为负数的约束 可以两端同时乘以 1 取值小于等于0的变量 可以用一个非负变量的相反数表示 例将下列LP问题化成标准形式 s t 课堂练习 将下列LP问题化成标准形式 作业 P46页习题1 4题 第二节两变量线性规划问题的图解法 一 几个概念二 两变量线性规划问题的图解法三 两变量线性规划问题解的性质 可行解 任何一组满足所有约束条件的决策变量值称为LP问题的一个可行解 最优解 使目标函数达到最大 小 值的可行解 最优值 最优解对应的目标函数值 可行域 所有可行解的集合称为可行域 一 几个概念 二 两变量LP问题的图解法 图解法是根据平面直角坐标系和二元一次方程 不等式 的特点设计的 1 图解法的一般步骤 1 建立直角坐标系 以为横轴 为纵轴 2 将约束条件在直角坐标系中表示 并找出可行域 3 作出目标函数的等值线簇 找出目标函数值的增加 或减小 方向 用箭头表示 4 确定出问题的最优解 若为极大 小 化问题 目标函数沿增加 减小 方向平移 与可行域的最后一个交点即为最优解 例1用图解法解下列线性规划问题 最优解x 10 15 T 最优值z 50 10 60 15 1400 0 10203040 102030 x2 x1 1 2 10 15 可行域有界 有唯一最优解 z 0 z 600 3 例2 无穷多最优解 x1 x2 例3 无有限最优解 x1 x2 可行域无界 有唯一最优解 x1 x2 例4 x1 x2 可行域为空 无可行解 例5 0 12345678 123456 x2 x1 42 课堂练习 用图解法求解 可行域是空集 可行域存在 则一定是一个凸多边形 无有限最优解 可行域一定无界 最优解存在且唯一 则一定在顶点上达到 最优解存在且不唯一 一定存在一个顶点是最优解 2 图解法求解两变量LP问题时可能出现的情况 三 两变量线性规划问题解的性质 1 两变量线性规划问题的可行域是若干个半平面的交集 它是一个有界或无界的凸多边形 并且有有限个顶点 2 对于给定的线性规划问题 如果它有最优解 最优解总可以在可行域的某个顶点上达到 第三节线性规划问题的基本定理 一 可行区域的几何结构二 基可行解及线性规划的基本定理 一 可行区域的几何结构 1 基本假设2 凸集及其性质3 可行域的凸性4 问题 1 基本假设 凸集 设S是n维欧氏空间的一个点集 若任意两点X 1 S X 2 S的连线上的一切点 X 1 1 X 2 S 0 1 则称S为一个凸集 性质 任意多个凸集的交集仍然是凸集 2 凸集及性质 顶点 设S是凸集 X S 若对任何X 1 S和X 2 S X 1 X 2 以及任何0 1 都有X X 1 1 X 2 则称X为凸集S的一个顶点 或极点 根据顶点的定义 长方形的四个角点就是长方形区域的全部顶点 而圆周上的点则是圆形区域的全部顶点 在平面区域中 每个顶点至少是两条直线的交点 3 可行域的凸性 定理1 若线性规划问题的可行域D X Rn AX b X 0 非空 则必为凸集 可以直接按照凸集的定义证明 也可以按照以下思路证明 可行域凸性的证明思路 超平面 给定b R1及非零向量a Rn 称集合H X Rn aTX b 是Rn中的一个超平面 超平面是二维空间中的直线 三维空间中的平面在高维空间中的推广 超平面是凸集 由超平面产生的两个闭的半空间H x Rn aTX b H x Rn aTX b 都是凸集 可行域是有限个超平面的交 因此可行域是凸集 4 问题 可行域顶点的个数是否有限 最优解是否一定在可行域顶点上达到 如何找到顶点 如何从一个顶点转移到另一个顶点 二 基可行解及线性规划的基本定理 基可行解的定义线性规划的基本定理问题 1 基可行解的定义 考虑标准形式的线性规划问题 基 A是约束方程组的系数矩阵 设n m 其秩为m B是A中的一个m阶满秩子方阵 称B是线性规划问题的一个基 B中每一个列向量称为一个基向量 与基向量对应的变量称为基变量 其余变量称为非基变量 不失一般性 设 则Pj j 1 2 m 是基向量 xj j 1 2 m 是基变量 xj j m 1 n 是非基变量 基解 在约束方程组中令所有的非基变量xm 1 xm 2 xn 0 得 此方程组有唯一解XB x1 x2 xm T 将这个解加上非基变量取0的值有X x1 x2 xm 0 0 T 称X为线性规划问题的基解 显然 基解中取非零值的变量个数不超过m 基解的总数不超过Cnm个 基可行解 满足非负约束的基解称为基可行解 可行基 对应于基可行解的基 基可行解 用矩阵形式表示的基解 考虑标准形式的线性规划问题 例如LP问题 是它的两个基 对应的基解分别为 可见X1是基可行解 故B1是可行基 而X2不是基可行解 故B2不是可行基 根据以上定义 2 线性规划的基本定理 引理 LP问题的可行解X是基可行解的充要条件是它的正分量所对应的A中的列向量线性无关 定理3 线性规划问题的基可行解对应可行域的顶点 X是基可行解 X是可行域的顶点 基可行解个数有限 定理4 若线性规划问题有有限最优值 则一定存在一个基可行解是最优解 定理2 若线性规划问题有非零可行解 则其必有基可行解 3 问题 如何得到第一个基可行解 如何判别一个基可行解是否最优 如果当前的基可行解不是最优 如何从一个基可行解转化到另一个基可行解 一 单纯形法的求解思路二 单纯形法的基本步骤及单纯形表 第四节单纯形法 确定初始基可行解最优性检验基可行解的改进 一 单纯形法的求解思路 当约束条件全部是 型不等式且右端常数非负 化成标准形后 约束条件系数矩阵含有单位子矩阵 可按照下列方法找到第一个基可行解 加上松弛变量 化为标准形式 1 确定初始基可行解 其约束条件系数矩阵为 令其中的单位矩阵作为基 可得初始基可行解 当线性规划问题的约束条件中含有 或 型约束时 化成标准形式后 约束条件系数矩阵中不含单位子矩阵 这时需要通过添加人工变量的方法寻找第一个可行基 本节第5节介绍 对于线性规划问题的标准形式 假设可行域非空 A为一m n实矩阵 r A m n 2最优性检验 假设B是一个可行基 不妨设B是由A的前m个列向量组成的 即A B N 则线性规划问题的等式约束AX b可以化成 两端同时左乘B 1 得 令 B 1b 则上式可以写成 上式所对应的约束方程称为对应于基B的典式 有了典式 就很容易写出线性规划问题的基解 其中 如果 0 则典式对应的基解X0是基可行解 从而B是可行基 当 0时 该基可行解为非退化的基可行解 问题 如何判断一个基可行解是否为最优解呢 目标函数Z CX可以化成 将约束方程组化成典式以后 对目标函数做相应变换 由于CB CBB 1B 0 令 则 其中z0是基可行解对应的目标函数值 是将目标函数中基变量消掉以后非基变量的系数 该系数是判断基可行解是否最优的依据 称为检验数 当所有检验数 j 0时 当前的基可行解为最优解 如果某个非基变量的检验数 j 0 而 ij 0 则原问题无界 如果某个非基变量的检验数 j 0 且至少存在一个i 使得 ij 0 则可以找到一个新的基可行解X1 使得CX1 CX 3 基可行解的改进 1 基的修改 进基变量 出基变量的选取准则 2 迭代 得到新基对应的典式 基的修改准则 新基与原有基有m 1个相同的基变量 只有一个基变量不同 进基变量 从非基变量变为基变量的变量 出基变量 由基变量变为非基变量的变量 1 进基变量的选取原则 最优性原则 若 k 0 则与 k相对应的变量xk是非基变量 当xk变为基变量时 它的值由0变为正数 比如说xk 0 其余的非基变量仍取值为零 由 3 4 式知 对应新解的目标函数值为z z0 K z0 显然 越大目标函数值越大 可行性原则 最小比值原则 的取值应保证新解仍然是基可行解 2 出基变量的选取原则 进基变量和出基变量的选取准则 0 10203040 102030 x2 10 15 例10 求解下列线性规划问题 x1 添加松弛变量 化成标准形式 典式 约束条件系数矩阵含单位矩阵 目标函数中基变量系数为0 第一个基可行解X0 0 0 80 60 45 T目标函数值为0对应可行域顶点O 0 0 0 10203040 102030 x2 10 15 x1 A B C D 让x2进基 不妨假设x2 x1仍为非基变量 目标函数值为60 从最优性角度看 越大越好 为了保持解的可行性 原先的基变量取值必须满足 综上得到 x3出基 新的基变量为x2 x4 x5对应的典式可以由方程组的初等变换得到 新的基可行解 X1 0 20 0 20 45 T 对应的目标函数值为1200 对应可行域A点 取x1为进基变量 x4为出基变量 新的基可行解 X1 10 15 0 0 15 T 对应的目标函数值为1400 对应可行域B点 检验数均非正 所以已得到最优解 当xk 0成为基变量以后 其余非基变量仍然取值为0 设新基对应的基可行解为X1 x11 xn1 T 则X1应满足约束条件 即 由于xi1必须是非负的 即 如果 ik 0 显然只要 0 就有xi1 i ik 0 对于 ik 0 就要求 所以 应满足 假定至少有一个aik 0 i 1 2 m 并且所有的 i 0 则 0 0 从最优性原则出发 让 取值尽量大 即取 然后把xt从原有的基中取出来 得到一组新的基可行解 X1使目标函数取值z1 z0 k 0 z0 迭代 新的基可行解对应的典式的确定 利用线性方程组的等价变换将约束条件和目标函数化成新基对应的典式 从而求出新的基可行解及相应的检验数 二 单纯形法基本步骤及单纯形表 Step1将线性规划问题化成标准形式下的典式 求出各个非基变量的检验数 Step2判断所有非基变量的检验数是否非正 若是 则结束 否则转step3 Step3选取一个检验数大于零的非基变量为进基变量 Step4若进基变量所对应的约束条件系数全为非正数 则原问题无界 结束 否则 按最小比值原则确定出基变量 Step5利用方程组的初等变换得到新的基对应的典式 基可行解和检验数 转step2 单纯形表 cn ibi j cj cn i 例11用单纯形表求解例1中的线性规划问题 解 先化成标准形式 最优解X 10 15 0 0 15 T 最优值1400 例2 利用单纯形法求下列线性规划问题 将该问题化成标准形式 也是典式 基变量是 x3 x4 x5 非基变量是x1x2 填入单纯形表求解 最优解X 2 3 2 0 0 T 最优值19 注意 1 在选取进基变量时 若有几个非基变量的检验数都是正数 则可以任意选取一个正检验数对应的非基变量作为进基变量 一般选取最大正检验数对应的非基变量 但实际情况表明这种策略不一定最好 2 在选取出基变量时 若有几个比值同时达到最小 可以任意选择一个 但在新的基可行解中这些对应分量均为零 从而新的基可行解是一个退化的基可行解 假若问题是非退化的 则不会出现这种情况 例12 用单纯形法求解线性规划问题 多解问题 解 化成标准形式 填入单纯形表求解 最优解X1 1 5 0 8 0 T 最优值6 最优解X2 5 1 8 0 0 T 最优值6 实际上X1与X2的连线上的任意点都是最优解 例13 用单纯形法求解线性规划问题 无有限最优解的情况 解 化成标准形 典式 X2的检验数为正 但约束条件中x2的系数全为负 因此该问题无有限最优解 作业P486 7 1 8 1 第五节单纯形法的进一步讨论 在给定的LP问题的标准形式中 如果约束条件系数矩阵A中含有一个m阶单位矩阵 并且b 0 则我们已经找到了一个明显的基可行解 并且约束方程组已经是典式 这时可以直接填入单纯形表中进行迭代 但是实际问题往往并非如此 因此我们需要寻找第一个基可行解 通常使用两种常用的方法求解第一个基可行解 一 大M法二 两阶段法 考虑标准形式的线性规划问题 一 大M法 原问题 辅助问题 人工变量 为了得到原问题的一个基可行解 只要将辅助问题的基可行解中的人工变量全部变为非基变量即可 为此 将人工变量加到辅助问题的目标函数中并赋予系数 M M可以看成惩罚系数 添加M以后 直接求解辅助问题 可能有两种情况 1 辅助问题的最优解中人工变量全部是非基变量 此时去掉人工变量直接得到原问题的最优解 2 在辅助问题的最优解中某些人工变量是基变量且取值非零 此时原问题无可行解 例14 用大M法求解下列线性规划问题 添加人工变量得辅助问题 例15 用单纯形法求解线性规划问题 添加人工变量 化成典式 所有的检验数都不大于零 人工变量X5仍留在基变量中且不为零 故原问题无可行解 二 两阶段法 第一阶段 寻找原问题的一个基可行解 第二阶段 求原问题的最优解 通过求解一个目标函数只含有人工变量的辅助问题实现 原问题 辅助问题 第一阶段解的情况 1 第一阶段人工变量取值为0 目标函数值也为0 此时得到原问题的第一个基可行解 结束第一阶段 去掉人工变量 进入第二阶段求原问题的最优解 2 第一阶段最优解的基变量中含有人工变量 表明原问题无可行解 例16 用两阶段法求解下列线性规划问题 第一阶段的线性规划问题为 第一阶段 用单纯形法求解辅助问题 得原问题的基可行解X 1 3 0 0 0 T 第二阶段 将上表中的人工变量去除 目标函数换成原问题的目标函数 从上表的最后一个单纯形表出发 继续计算 得原问题的最优解X 0 5 2 3 2 0 0 T 最优值是3 2 单纯形法计算小结 作业 P489 2 10 第六节线性规划应用案例分析 例17 混合配料问题 某糖果厂用原料A B C加工成三种不同牌号的糖果甲 乙 丙 已知各种牌号糖果中A B C的含量 原料成本 各种原料的每月限制用量 三种糖果的单位加工费如下表所示 问该厂每月生产这三种牌号的糖果各多少千克 才能获利最大 解 用i 1 2 3代表A B C三种原料 用j 1 2 3分别代表甲 乙 丙三种糖果 设xij为生产第j种糖果使用的第i种原料的质量 则问题的数学模型为 sets U 1 3 b Q V 1 3 c d link U V x endsetsdata b 21 51 Q 2000 2500 1200 c 0 50 40 3 d 3 42 852 25 enddatamax sum V j d j c j sum U i x i j sum U i b i sum V j x i j for U i sum V j x i j 0 6 sum U i x i 1 x 3 1 0 3 sum U i x i 2 x 3 2 0 5 sum U i x i 2 x 3 3 0 6 sum U i x i 3 Lingo程序 Globaloptimalsolutionfound Objectivevalue 5450 000Infeasibilities 0 000000Totalsolveriterations 6VariableValueReducedCostX 1 1 580 00000 000000X 1 2 1420 0000 000000X 2 1 193 33330 000000X 2 2 2306 6670 000000X 3 1 193 33330 000000X 3 2 1006 6670 000000 用单纯形法解得 例18 投资项目的组合问题 兴安公司有一笔30万元的资金 考虑今后3年内用于下列项目的投资 项目一 三年内的每年年初可投资 每年获利为投资额的20 其本利可一起用于下一年的投资 项目二 只允许第一年初投资 于第二年末收回 本利合计为投资额的150 但此类投资限额不超过15万元 项目三 允许于第二年初投资 于第三年末收回 本利合计为投资额的160 但限额投资为20万元 项目四 允许于第三年初投资 年末收回 可获利40 但限额为10万元 试为该公司确定一个使第三年末本利和为最大的投资组合方案 解 用xij表示第i年初投资到第j项目的资金数 则可得下列线性规划模型 求解得 max 1 2 x31 1 6 x23 1 4 x34 x11 x12 30 x21 x23 1 2 x11 x31 x34 1 2 x21 1 5 x12 x12 15 x23 20 x34 10 Globaloptimalsolutionfound Objectivevalue 58 00000Infeasibilities 0 000000Totalsolveriterations 6VariableValueReducedCostX3110 000000 000000X2320 000000 000000X3410 000000 000000X1116 666670 000000X1213 333330 000000X210 0000000 6000000E 01 例19 下料问题 工厂要制作100套专用钢架 每套钢架需要用长为2 9m 2 1m和1 5m的圆钢各一根 已知原料每根长7 4米 现考虑应如何下料 可使所用原料最省 解 设x1 x2 x3 x4 x5 x6 x7 x8分别表示按上述8种方案下料的原料根数 则 min x1 x2 x3 x4 x5 x6