机械优化设计2-2.ppt

线性规划 线性规划：目标函数和约束条件都是线性的，对目标函数求优化问题。 第一节 线性规划的标准形式和基本性质 一、线性规划实例： 1、甲乙两种产品： 产品 材料 工时 用电 利润 甲X1 9kg 3h 4kWh 60元 乙X2 4kg 10h 5kWh 120元 总供应 360kg 300h 200kWh ? 约束条件： 2、有m个产粮区分别产粮 , 有n个贮粮区分别储粮 , 从i产粮区运到j贮粮区的每吨运费 ,求如何调拨粮食使运费最省? 设 从i产粮区运到j贮粮区的数量。 约束条件： (i=1,2,…,m)运出 (j=1,2,…,n)运进 二、线性规划的标准形式 线性规划数学模型的一般形式为 求设计变量 使目标函数 约束条件：且满足 同时 组成的向量互不相关（线性无关）。 也可写成如下的简化形式 求 使目标函数 要求满足约束条件 约束条件包括两部分： 一是等式约束条件 二是变量的非负要求，它是标准形式中出现的唯一不等式形式。 通过引入松弛变量将不等式约束化成上述等式约束形式。 线性规划问题的标准形式可写成如下的矩阵形式 求x使 其中， ，而0代表零向量。 三、线性规划的基本性质 在线性规划中有n个变量，m个方程，则当向量X 中n-m个变量为零时，其基本解个数 若基本解满足 ，称为基本可行解。 通过作图，在 平面内作出约束条件组成的多边形，作出 的等值线。 发现最优点取在多边形的顶点： 则 最优 基本变量：基本可行解中取正值的变量。可作为基底变量（列向量）。 非基本变量：基本可行解取零值的变量。 特殊情况下出现：无穷多最优解，无解，无可行解。 第二节 基本可行解的转换 一、从一个基本解转换到另一个基本解 对于约束条件组成的方程组， 采用高斯－约当（Gauss-Jordan）法进行消元，则上面方程将变成下列形式 重复进行这样的转轴运算，则可得： 这一方程称作正则方程组。 从而得到一组基本解： 若 非负，这组解为基本可行解。 前m个变量称作基本变量， 基本解中所有基本变量的全体称作它的基。 对于上述方程，可任选 为转轴元素，（s任意， ），xt作为转轴变量进行一次附加的转轴运算，就可实现该一个基本可行解转换到另一个基本可行解。 二、从一个基本可行解转到另一个基本可行解 对于上述方程，若 ，则该基本解为基本可行解。 如取 为转轴元素，xk为转轴变量，则由原基本可行解，用xk替换xl。 要保证替换后的基本解为基本可行解，则 因此 并使 θ规则 三、初始基本可行解的求法 简单方法：选择初始基本可行解时，把松弛变量选为基本变量即可；如还不行则引进人工变量。 第三节 单纯形法 对于可行解，目标函数可以写成： 如果还有另一组可行解，它的基本变量中包含有 ，即 其中的 。它对应的目标函数是 令 则 式中 －相对价值系数， 1、求极小值时：要求 ，则 是负值， 是负值，故 还没有到极小，还可以下降直至 为正值，才说明 到达极小值。 2、求极大值时：则相反， 为负值，才说明 到达极大值。 因此线性规划有以下两个原则： 1.θ规则：（确定转轴变量） 2.最速变化规则：（确定最优值） 当目标函数表示成只是非基本变量的函数时，对应于基本变量的系数 ，则 ，最速变化规则又可表示为 对于极大值问题，则最速变化规则应取max号。 1、某工厂用甲、乙两台机床，加工A、B、C三种零件，已知在一生产周期内甲只能工作80机时，乙只能工作100机时。一生产周期内要加工A、B、C的件数分别为70、50、20。两台机床加工每个零件的时间和成本如下表，问应如何安排两台机床生产一周期的加工任务，才能使成本最低？ 解：设甲机床生产A,B,C的零件的数量分别为： 则乙机床生产A,B,C的零件的数量分别为： 则： 生产成本为： 归纳为： 标准形式为： 经计算后： 第四节 单纯形法应用举例 约束条件： Ck 解 -60 -120 0 0 0 Cl P1 P2 P3 P4 P5 b θ 0 X3 9 4 1 0 0 360 90 0 X4 3 10 0 1 0 300 30 0 X5 4 5 0 0 1 200 40 f(ak) 0 0 0 0 0 r -60 -120 0 0 0 Ck 解 -60 -120 0 0 0 Cl P1 P2 P3 P4 P5 b θ 0 X3 -120 X2 0.3 1 0 0.1 0 3