机械优化设计第五章(哈工大—孙靖民)教程分析.pptVIP

alk作为转轴元素进行转轴运算： 方程组第一行发生的变化： 若想用xk取代xl成为可行解中的基本变量，即所选取的行要满足条件: 规则 例： 基本可行解： x1=3 x5=5 x2=x3=x4=0 基本变量x1、x5 基本可行解的转换： 1）x2、x4系数全部为负，只能选取x3所在的第3列为转轴列 2） , 由于 ，则取第一行为转轴行, 于是取a13=2为转轴元素，使x3取代x1成为基本变量。 经转轴运算得： 得基本可行解： 结论：可把松驰变量作为初始基本可行解中的基本变量。 三、初始基本可行解的求法 原始约束条件: 引入松驰变量: 可得一组基本可行解： 一、单纯形法的基本思想 　　　从一个初始基本可行解X0出发，寻找目标函数有较大下降的一个新的基本可行解X1,代替原来的基本可行解X0，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。 §5-3 单纯形方法 采用单纯形法求解线性规划问题，主要应解决以下三个问题： （1）如何确定初始基本可行解； （2）如何由一个基本可行解迭代出另一个基本可行解，同时保证目标函数的下降性； （3）如何判断一个基本可行解是否为最优解。 二.最优解规则 对应一组基本可行解： 前m个变量组成基本可行解的基本变量 相应的目标函数值为: 经过转轴运算得到另一组基本可行解为: 其中： 进基变量xk 出基变量xs 对应的目标函数为: 由于要求 ∴ 结论:一旦所有的 ,即可停止 转轴运算,对应的可行解就是最优解。r是 对线性规划问题的解进行最优性检验的标 志，称之为检验数。 ∵ ∴ 具体计算时应选取: 由于有可能同时有几组 都为负值 最速变化规则 1）最速变化规则决定进基的非基本变量 结论： 2） 规则决定了出基的基本变量 3）若对基本可行解X，所有检验数rk≥ 0，则X 为最优解。 E N D Page ? * * Page ? * * 5-1 线性规划的标准形式与基本性质 5-2 基本可行解的转换 5-3 单纯形方法及应用举例 　第五章　线性规划　 目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。 　第五章　线性规划　 解：设生产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）m=n,唯一解 2）mn,无解 3）mn,无穷解 二、线性规划的标准形式 将一般形式的线性规划化为标准形式的方法 x3为松弛变量 约束条件为“? ”时： 约束条件包括