05机械优化设计第五章(哈工大—孙靖民).ppt

第五章线性规划 目标函数和约束条件都是线性的 像这类约束函数和目标函数都是为线性函数的优化问题 称作线性规划问题 它的解法在理论和方法上都很成熟 实际应用也很广泛 虽然大多数工程设计是非线性的 但是也有采用线性逼近方法求解非线性问题的 此外 线性规划方法还常被用作解决非线性问题的子问题的工具 如在可行方向法中可行方向的寻求就是采用线性规划方法 当然 对于真正的线性优化问题 线性规划方法就更有用了 第五章线性规划 解 设生产A B两产品分别为x1 x2台 则该问题的优化数学模型为 例5 1 某工厂要生产A B两种产品 每生产一台产品A可获产值2万元 需占用一车间工作日3天 二车间工作日6天 每生产一台产品B可获产值1万元 需占用一车间工作日5天 二车间工作日2天 现一车间可用于生产A B产品的时间15天 二车间可用于生产A B产品的时间24天 试求出生产组织者安排A B两种产品的合理投资产数 以获得最大的总产值 5 1线性规划的标准形式与基本性质 一 线性规划实例 例5 2 生产甲种产品每件需使用材料9kg 3个工时 4kw电 获利润60元 生产乙种产品每件需用材料4kg 10个工时 5kw电 可获利120元 若每天能供应材料360kg 有300个工时 能供200kw电 试确定两种产品每天的产量 使每天可能获得的利润最大 分析 每天生产的甲 乙两种产品分别为件 工时约束 电力约束 材料约束 利润最大 将其化成线性规划标准形式 求 使 且满足 例5 3 某厂生产甲 乙两种产品 已知 两种产品分别由两条生产线生产 第一条生产甲 每天最多生产9件 第二条生产乙 每天最多生产7件 该厂仅有工人24名 生产甲每件用2工日 生产乙每件用3工日 产品甲 乙的单件利润分别为40元和80元 问工厂如何组织生产才能获得最大利润 日利润最大 生产能力限制 劳动力限制 变量非负 解 设甲 乙两种产品的日产件数分别为 s t 建模例1 某公司有钢材 铝材 铜材1200t 800t和650t 拟调往物资紧张的地区甲 乙 丙 已知甲 乙 丙对上述物资的总需求分别为 900t 800t和1000t 各种物资在各地销售每吨的获利如下表所示 试问公司应如何安排调运计划 才能获利最大 建立该问题的数学模型 物资 获利 地区 建模例2 某工厂生产A B C三种产品 现根据订货合同以及生产状况制定5月份的生产计划 已知合同甲为 A产品1000件 单件价格为500元 违约金为100元 件 合同乙为 B产品500件 单件价格为400元 违约金为120元 件 合同丙为 B产品600件 单件价格为420元 违约金为130元 件 C产品600件 单件价格为400元 违约金为90元 件 有关各产品生产过程所需工时以及原材料的情况见下表 试以利润为目标 建立该工厂的生产计划线性规划模型 建模例3 成批生产企业年度生产计划的按月分配 在成批生产的机械制造企业中 不同产品劳动量的结构上可能有很大差别 如 某种产品要求较多的车床加工时间 另一种产品的劳动量可能集中在铣床和其他机床上 因此 企业在按月分配年度计划任务时 应考虑到各种设备的均衡且最大负荷 在年度计划按月分配时一般要考虑 1 从数量和品种上保证年度计划的完成 2 成批的产品尽可能在各个月内均衡生产或集中在几个月内生产 3 由于生产技术准备等方面原因 某些产品要在某个月后才能投产 4 根据合同要求 某些产品要求在年初交货 5 批量小的产品尽可能集中在一个月或几个月内生产出来 以便减少各个月的品种数量等等 如何在满足上述条件的基础上 使设备均衡负荷且最大负荷 线性规划数学模型的一般形式 求 使 且满足 说明 1 m n 唯一解2 m n 无解3 m n 无穷解 二 线性规划的标准形式 将一般形式的线性规划化为标准形式的方法 x3为松弛变量 约束条件为 时 约束条件包括两部分 一是等式约束条件 二是变量的非负要求 它是标准形式中出现的唯一不等式形式 x3为剩余变量 约束条件为 时 2 变量 1 x 0 令x x 2 x取值无约束 令x x x 例如 3 x两边有约束的情况 6 6 x1 6 10 6令x1 x1 60 x1 16 4 右端常数 右端项b 0时 只需将等式或不等式两端同乘 一1 则等式右端项必大于零 三 线性规划的基本性质 通过顶点 的直线满足上述条件 故点 是该问题的最优解 作目标函数的等值线 可行解 同时满足所有约束条件的任何一个解x x1 x2 xn T 例 多边形OACD域中任意一个解 基本可行解 如果基本解还满足非负条件xj 0 j 1 2 n 则称之为基本可行解 既是基本解 又是可行解 例 表5 1中列出的4个解 或图5 1对应的4个顶点A C D O 基本解 令线性规划标准形式中任意 n m 个变量等于零 若剩余的m个变量构成的m个线性方程有唯一解 则称由此得到的n个变量的解为基本解 例 表5 1中列出的 个解 或图5 1对应的 个顶点A B C D E O 基 基向量 基变量与非基变量基 在系数矩阵A中 选择m列线性无关向量构成m m阶非奇异子矩阵B 则称B为线性规划的一个基 基向量 组成基B的列向量pj j 1 2 m 基变量 与基向量对应的变量xj j 1 2 m 用xB表示 非基变量 除基变量外的其余 n m 个变量 用xN表示 最优解 使目标函数达到最小值的基本可行解 例 图5 1中的点C为最优解 对应的目标函数值为 33 4 基变量和非基变量是相对于基而言的 线性规划问题的以上几个解的关系 可用下图来描述 基本解共10个 每个基本解中有n m 2变量取零值 基本可行解5个 线性规划的两个重要性质线性规划可行解的集合构成一个凸集 且这个凸集是凸多面体 它的每一个顶点对应于一个基本可行解 即顶点与基本可行解相当 线性规划的最优解如果存在 必然在凸集的某个顶点 即某个基本可行解 上达到 图5 2线性规划解的特殊情形 因此 线性规划的最优解不必在可行域整个区域内搜索 只要在它的有限个基本可行解 顶点 中去寻找即可 但是 在实际的线性规划问题中 其变量的个数n和约束方程的个数m都是很大的 其基本可行解的数目非常多 即使采用计算机也难以实现 同时 仅仅考察基本可行解 也不能确定问题何时有无界解 故没有必要找出所有的基本可行解以求得最优解 而是采用一定的方法如单纯形法来解决这个问题 一 基本解到基本解的转换把约束条件展开 5 2基本可行解的转换 采用高斯 约当法 Gauss Jordan 进行消元 此过程称作对变量xk进行转轴运算 xk称为转轴变量 alk称为转轴元素 选取另一变量作为转轴变量进行第二次转轴运算 并反复此过程 我们将得到 这一方程组称为正则方程组 高斯 亚当消元过程 从而得到一组基本解 基本解中所有基本变量的全体称为基 基本变量 如果此时继续对上述形式的方程组进行附加的一次转轴运算 例如选取作 t m 为转轴元素 此时xt进入基 xs出基 这样就完成了从一个基本解到另一个基本解的转换 解 用a11 a22作为轴元素进行两次转轴运算 例 给定如下方程组 试进行基本解的转换运算 得到一组基本解 x1 12x2 20 x3 x4 x5 0 用a11 a25作为轴元素进行第三次转轴运算 又得到一组基本可行解 x1 3x5 5x2 x3 x4 0此时x5进入基 x2出基 二 基本可行解到基本可行解的转换 当已经得到一组基本可行解 若要求把xk选进基本变量 并使下一组基本解是可行解的话 则在第k列要选取不为任何负值的元素作为转轴元素 alk作为转轴元素进行转轴运算 方程组第一行发生的变化 alk作为轴元素 xk选进基本变量后 xk的取值由零变成了一个正值 则原来各基本变量的取值变为 若是基本可行解 应该保证各差值最小者为零 决定了离基变量为xi 若想用xk取代xl成为可行解中的基本变量 就应该选所对应的行成为转轴行 即所选取的行要满足条件 规则 例 基本可行解 x1 3x5 5x2 x3 x4 0基本变量x1 x5基本可行解的转换 1 x2 x4系数全部为负 只能选取x3所在的第3列为转轴行2 由于 则取第一行为转轴行 于是取a 13 2为转轴元素 使x3取代x1成为基本变量 经转轴运算得 得基本可行解 结论 可把松驰变量作为初始基本可行解中的一部分基本变量 三 初始基本可行解的求法 原始约束条件 引入松驰变量 可得一组基本可行解 一 单纯形法的基本思想从一个初始基本可行解X0出发 寻找目标函数有较大下降的一个新的基本可行解X1 代替原来的基本可行解X0 如此完成一次迭代 随后作出判断 如果未达到最优解 则继续迭代下去 因为基本可行解的数目有限 所以经过有限次迭代一定能达到最优解 5 3单纯形方法 采用单纯形法求解线性规划问题 主要应解决以下三个问题 1 如何确定初始基本可行解 2 如何由一个基本可行解迭代出另一个基本可行解 同时保证目标函数的下降性 3 如何判断一个基本可行解是否为最优解 二 最优解规则 对应一组基本可行解 前m个变量组成基本可行解的基本变量相应的目标函数值为 经过转轴运算得到另