线性规划与单纯形法.ppt

一 线性规划问题及其数学模型 线性规划是运筹学的一个重要分支 线性规划在理论上比较成熟 在实用中的应用日益广泛与深入 特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后 线性规划的适用领域更为广泛了 从解决技术问题的最优化设计到工业 农业 商业 交通运输业 军事 经济计划和管理决策等领域都可以发挥作用 它已是现代科学管理的重要手段之一 例1 1生产计划问题 资源利用问题 某家具厂生产桌子和椅子两种家具 桌子售价50元 个 椅子销售价格30元 个 需要木工和油漆工两种工种 生产一个桌子需要木工4小时 油漆工2小时 生产一个椅子需要木工3小时 油漆工1小时 该厂每个月可用木工工时为120小时 油漆工工时为50小时 问如何组织生产才能使每月的销售收入最大 1 问题的提出 是问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 第1步 确定决策变量 设 桌子的产量 椅子的产量 利润 第2步 定义目标函数 MaxZ 50 x1 30 x2 第2步 定义目标函数 MaxZ 50 x1 30 x2 第3步 表示约束条件 4x1 3x2 120 木工工时限制 2x1 x2 50 油漆工工时限制 x1 x2 0 变量取非负值限制 该计划的数学模型maxZ 50 x1 30 x24x1 3x2 1202x1 x2 50 x1 x2 0 线性函数 线性等式线性不等式 线性规划 例1 2简化的环境保护问题靠近某河流有两个化工厂 见下图 流经第一化工厂的河流流量为每天500万立方米 在两个工厂之间有一条流量为每天200万立方米的支流 第一化工厂每天排放含有某种有害物质的工业污水2万立方米 第二化工厂每天排放这种工业污水1 4万立方米 从第一化工厂排出的工业污水流到第二化工厂以前 有20 可自然净化 根据环保要求 河流中工业污水的含量应不大于0 2 这两个工厂都需各自处理一部分工业污水 第一化工厂处理工业污水的成本是1000元 万立方米 第二化工厂处理工业污水的成本是800元 万立方米 现在要问在满足环保要求的条件下 每厂各应处理多少工业污水 使这两个工厂总的处理工业污水费用最小 建模型之前的分析和计算 设 第一化工厂每天处理工业污水量为x1万立方米 第二化工厂每天处理工业污水量为x2万立方米 数学模型 线性规模解决的问题 给定一定数量的人力 物力 财力等资源 研究如何充分利用 以发挥其最大效果已给定计划任务 研究如何统筹安排 用最少的人力 物力 财力去完成 线性规划数学模型三要素 决策变量 目标函数 约束条件 每一个线性规划问题都有一组决策变量 x1 x2 xn 这组决策变量的值就代表一个具体方案 有使用各种资源的约束条件 用等式或不等式表示 有一个要达到的目标 是决策变量的线性函数 实现最大化或最小化 2 线性规划问题的数学模型 一般形式 线性规划模型的表示形式 矩阵形式 标准形式 将一般线性规划化成标准形 简写形式 线性规划问题的一般形式 线性规划问题的简写形式 C 价值向量b 资源向量X 决策变量向量 线性规划的矩阵形式 a11a12 a1nb1A a21a22 a2nb b2 am1am2 amnbm c1x10c2x20C X 0 xn0 线性规划问题的标准形式maxZ c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 其中 bi 0 i 1 2 m 四点要求 将一般线性规划化成标准型 求max 等式约束 bi 0 xi 0 1 若目标函数是求最小值 minZ CTX令Z Z 则化成maxZ CTX 注意 因为minZ max Z 所以变换后的最优解不变 最优值变号 2 若约束条件是不等式 1 若约束条件是 不等式 则不等式左边 加上 非负的松驰变量 如 2X1 2X2 12令X3 12 2X1 2X2则有2X1 2X2 X3 12 2 若约束条件是 不等式 则不等式左边 减去 非负的松驰变量 如 10X1 12X2 18令X4 10X1 12X2 18则有10X1 12X2 X4 18 为了使添加松驰变量不影响原来的目标 添加松驰变量在目标函数中的系数为0 3 若约束条件右面的某一常数项bi 0 这时只要在bi相对应的约束方程两边乘 1 4 若变量xj无非负限制引进两个非负变量xj xj 0令xj xj xj 可正可负 任何形式的线性规划总可以化成标准型 例1 3将下列问题化成标准型 minZ x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 0 x2 0 x3无限制 例1 3将下列问题化成标准型 minZ x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 0 x2 0 x3无限制 min x3无限制 例1 3将下列问题化成标准型 maxZ x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 0 x2 0 x3无限制 例将下列问题化成标准型 maxZ x1 2x2 3x3 0 x4s t x1 x2 x3 x4 7x1 x2 x3 2 3x1 x2 2x3 5x1 0 x2 0 x3无限制 x4 0 例将下列问题化成标准型 maxZ x1 2x2 3x3 0 x4 0 x5s t x1 x2 x3 x4 7x1 x2 x3 x5 2 3x1 x2 2x3 5x1 0 x2 0 x3无限制 x4 0 x5 0 maxZ x1 2x2 3x3 3x3 0 x4 0 x5s t x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2x3 2x3 5x1 0 x2 0 x3 0 x3 0 x4 0 x5 0 令x3 x3 x3 例将下列一般形式划为标准形式 标准型习题P55 2 2 1 划为标准形式 二 LP问题的图解法 1 例 x2 40 30 20 10 10 20 30 x1 由4x1 3x2 120 x1 0 x2 0围成的区域 50 由2x1 x2 50 x1 0 x2 0围成的区域 x2 40 30 20 10 10 20 30 x1 由4x1 3x2 1202x1 x2 50 x1 0 x2 0围成的区域 可行域 50 可行域 满足约束条件的解称为可行解 全部可行解的集合称为可行域 x2 40 30 20 10 10 20 30 x1 该问题的可行域是由Q1 Q2 Q3 Q4作为顶点的凸多边形 50 可行域 Q1 0 0 Q2 25 0 Q4 0 40 Q3 15 20 x2 40 30 20 10 10 20 30 x1 目标函数Z 50 x1 30 x2是一组平行线 50 可行域 x2 40 30 20 10 10 20 30 x1 此组平行线沿其法线方向 50 30 右上方函数值Z增加 50 可行域 x2 40 30 20 10 10 20 30 x1 当该直线移到Q3 15 20 点时 Z值达到最大 maxZ 50 15 30 20 1350此时最优解X 15 20 50 Q3 15 20 二个重要结论 可行域是一个凸多边形 最优解必定能在某一个顶点上取得 2 LP问题的解 可行解 满足约束条件 包括非负条件 的一组变量值 称可行解 可行域 可行解的全体 最优解 使目标函数达到最大的可行解 最优值 将最优解代入目标函数得到的值 可行域为空集 无可行解 可行域非空 则有三种情况 1 有唯一解 顶点 2 有无穷多个解 两个顶点间的连线 3 无最优解 无界解 无最优解 x1 x2 无可行解 x2 40 30 20 10 10 20 30 x1 当目标函数由maxZ 50 x1 30 x2变成maxZ 40 x1 30 x2目标函数是同约束条件4x1 3x2 120平行的直线Q2与Q3之间都是最优解 50 Q3 15 20 Q2 25 0 无界解 x1 x2 无界解 若可行域无界 且目标函数值可增加 减少 到正无穷 负无穷 称这种无最优解的情况为无界解 注意 可行域无界 不一定无最优解 可行域非空有界 则必定有最优解 LP问题解的类型习题P55 2 1 三 单纯形法的基本思路和原理 一 单纯形法的基本思路从可行域中某一个顶点开始 判断此顶点是否是最优 如不是 则再找另一个使得其目标函数值更优的顶点 称之为迭代 再判断此点是否是最优解 直到找到一个顶点为其最优解 就是使得其目标函数值最优的解 或者能判断出线性规划问题无最优解为止 找出一个初始可行解 是否最优 转移到另一个目标函数 找更大的基本可行解 最优解 是 否 循环 直到找出为止 核心是 变量迭代 结束 例maxZ 2x1 3x2s t x1 2x2 44x1 84x2 6x1 x2 0 1 基本概念 划为标准型 maxZ 2x1 3x2 0 x3 0 x4 0 x5s t x1 2x2 x3 44x1 x4 84x2 x5 6x1 x2 x3 x4 x5 0 约束方程的系数矩阵 A P1 P2 P3 P4 P5 单位矩阵 A中存在一个不为零的三阶子式 A的秩为3 A是约束条件的m n阶系数矩阵 设r A m 且B是A的m阶非奇异的子矩阵 det B 0 则称矩阵B为线性规划问题的一个基 阵 1 基 阵 B 或 m n r A m 至少有一个m阶子式不为0 基B中的一列即称为一个基向量 基B中共有m个基向量 2 基向量与非基向量 B P3 P4 P5 基向量 3 基变量与非基变量 设A p1 p2 pn 若B pi1 pi2 pim 为A的基阵 则称x1 x2 xn中的xi1 xi2 xim为对应于B的基变量 其余的称为非基变量 B P3 P4 P5 x3 x4 x5是基变量 x1 x2 是非基变量 基向量 A p1 pmpm 1 pn B N 基向量非基向量 4 基 本 解 令非基变量取值为零 则基变量的取值可从AX b中唯一解得 如此的一组解称为对应于B的一个基 本 解 5 基可行解 若X0是一个基解 而且又是一个可行解 则称X0是一个基可行解 基可行解对应于可行域的顶点 退化的基可行解 问题 在基可行解中 非基变量的取值必定为零 基变量的取值是否必定大于零 若X0是一个基可行解 其基变量的取值全部大于零 则称X0是非退化的 否则称为退化的 解的关系 可行解 基解 基可行解 最优解 代数概念 几何概念 满足一个等式约束的解满足一个不等式约束的解满足一组不等式约束的解基解基可行解目标函数值等于一个常数的解组 约束直线约束半平面约束半平面的交集 凸多边形约束直线的交点可行域顶点目标函数等值线 一组平行线 举例 化为标准型 可行解 基解和基可行解举例 2 最优解的判断 检验数公式 或 最优解检验的依据是计算检验数 检验数的判别规则 max 若所有的 则基B所对应的基可行解就是最优解 若所有的 而非基变量的检验数满足条件 则该线性规划问题有唯一最优解 若所有的 又有某个非基变量的检验数 则该线性规划问题有无穷多最优解 若存在某个 又其对应的向量的所有分量 则该线性规划问题存在无界解 3 单纯形表 二 单纯形法的内容 1 初始基可行解的确定 假定基阵B为单位阵 2 最优解的判断 3 换基可行解的方法 例 cj 23000 x1x2x3x4x5 121004001004001 cB xB b x3x4x5 000 486 23000 4 2 6 4 3 x2 3 2 0 1 0 0 1 1 0 1 0 1 2 1 4 20 20 3 4 1 1 8 4 3 x2 3 2 0 1 0 0 1 1 0 1 0 1 2 1 4 00 201 4 6 4 2 3 x2 1 0 1 1 2 1 8 2 1 0 0 1 4 0 0 00 3 2 1 40 例 230000 12 2 8 2 12 4 3 x2 3 0 1 0 0 0 1 4 2 6 2 0 1 0 0 1 2 1 0 0 1 0 0 1 2 20000 3 4 6 2 2 16 4 000 201 4 13 4 412 001 201 210010 1 2000 412010001 4 2283 x3x1x5x2 0203 x1x2x3x4x5x6 b xB cB 230000 cj 000 201 4 13 4 412 001 201 210010 1 2000 412010001 4 2283 x3x1x5x2 0203 x1x2x3x4x5x6 b xB cB 230000 cj 例求线性规划问题 单纯形法解线性规划问题习题P55 2 2 1 无法给出初始基可行解 四 大M法 2 添加人工变量 3 修改目标函数 例 加入人工变量后 目的是找到一个单位向量 其目标价值系数要确定 但不能影响目标函数的取值 一般可采用两种方法处理 大M法和两阶段法 即假定人工变量在目标函数中的系数为 M 任意大正数 如基变量中还存在M 就不能实现极值 大M法 0 M 0 5 2M 3 4M 2 3M 17M 5 1 1 0 1 5 2 10 x6 M 7 0 0 1 1 1 1 7 X4 M x6 x5 x4 x3 x2 x1 b xB cB M 0 M 5 3 2 cj 一般而言 一个经济 管理问题凡是满足以下条件时 才能建立线性规划模型 要求解问题的目标函数能用数值指标来反映 且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的 这些约束可用线性等式或不等式描述 五 线性规划在工商管理中的应用 1 人力资源分配的问题 2 生产计划的问题 3 套裁下料问题 4 配料问题 5 投资问题 应用举例 1 人力资源分配的问题 例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 分析 不同上班班次时段的司机和乘务人员数 设xi表示第i班次时开始上班的司机和乘务人员数 例2 一家中型的百货商场 它对售货员的需求经过统计分析如下表所示 为了保证售货人员充分休息 售货人员每周工作5天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 设xi i 1 2 7 表示星期一至日开始工作的人数 2 生产计划的问题 例3 某公司面临一个是外包协作还是自行生产的问题 该公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司加工和装配的甲 乙两种产品的件数 求xi的利润 利润 售价 各成本之和产品甲全部自制的利润 23 3 2 3 15产品甲铸造外协 其余自制的利润 23 5 2 3 13产品乙全部自制的利润 18 5 1 2 10产品乙铸造外协 其余自制的利润 18 6 1 2 9产品丙的利润 16 4 3 2 7可得到xi i 1 2 3 4 5 的利润分别为15 10 7 13 9元 通过以上分析 可建立如下的数学模型 目标函数 Max15x1 10 x2 7x3 13x4 9x5约束条件 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 例5 现有一批某种型号的圆钢长8米 需要截取2 5米长的毛坯100根 长1 3米的毛坯200根 问如何才能既满足需要 又能使总的用料最少 设变量为第j种方法的所有原料件数 3 套裁下料问题 例6 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 解 共可设计下列5种下料方案 见下表 设x1 x2 x3 x4 x5分别为上面5种方案下料的原材料根数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5约束条件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 用软件计算得出最优下料方案 按方案1下料30根 按方案2下料10根 按方案4下料50根 即x1 30 x2 10 x3 0 x4 50 x5 0 只需90根原材料就可制造出100套钢架 注意 在建立此类型数学模型时 约束条件用大于等于号比用等于号要好 因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢 但它可能是最优方案 如果用等于号 这一方案就不是可行解了 例7 根据对77种食物所含的九种营养物 热量 糖与脂肪 蛋白质 钙 铁 维生素A 维生素B1 维生素B2 草酸与维生素C的成份及食物的市场价格调查 按照医生所提出的对每个人每天所需的营养要求 问怎样采购食物才能在保证营养要求的前提下花费最省 这就是营养问题或饮食问题 配料问题就是由此而推广来的 4 配料问题 解 设每天购买甲 乙 丙 丁四种食物的数量分别为x1 x2 x3 x4 即可列出如下的线性规划模型 例8 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 数据如右表 问 该厂应如何安排生产 使利润收入为最大 解 设xij表示第i种 甲 乙 丙 产品中原料j的含量 这样我们建立数学模型时 要考虑 对于甲 x11 x12 x13 对于乙 x21 x22 x23 对于丙 x31 x32 x33 对于原料1 x11 x21 x31 对于原料2 x12 x22 x32 对于原料3 x13 x23 x33 目标函数 利润最大 利润 收入 原料支出约束条件 规格要求4个 供应量限制3个 利润 总收入 总成本 甲乙丙三种产品的销售单价 产品数量 甲乙丙使用的原料单价 原料数量 故有目标函数MaxZ 50 x11 x12 x13 35 x21 x22 x23 25 x31 x32 x33 65 x11 x21 x31 25 x12 x22 x32 35 x13 x23 x33 15