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

在年度计划按月分配时一般要考虑:1）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。 最优解：使目标函数达到最小值的基本可行解。 例：图5.1中的点C为最优解，对应的目标函数值为-33/4. 线性规划的两个重要性质 线性规划可行解的集合构成一个凸集，且这个凸集是凸多面体，它的每一个顶点对应于一个基本可行解，即顶点与基本可行解相当。 线性规划的最优解如果存在，必然在凸集的某个顶点（即某个基本可行解）上达到。　　　 一、单纯形法的基本思想 　　　从一个初始基本可行解X0出发，寻找目标函数有较大下降的一个新的基本可行解X1,代替原来的基本可行解X0，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。 采用单纯形法求解线性规划问题，主要应解决以下三个问题： （1）如何确定初始基本可行解； （2）如何由一个基本可行解迭代出另一个基本可行解，同时保证目标函数的下降性； （3）如何判断一个基本可行解是否为最优解。 　　　但是，在实际的线性规划问题中，其变量的个数n和约束方程的个数m都是很大的，其基本可行解的数目非常多，即使采用计算机也难以实现；同时，仅仅考察基本可行解，也不能确定问题何时有无界解。 　　　故没有必要找出所有的基本可行解以求得最优解，而是采用一定的方法如单纯形法来解决这个问题。 一、基本解到基本解的转换 把约束条件展开： §5-2 基本可行解的转换 采用高斯-约当法(Gauss-Jordan)进行消元： 此过程称作对变量xk进行转轴运算， xk称为转轴变量， alk称为转轴元素。 选取另一变量作为转轴变量进行第二次转轴运算，并反复此过程，我们将得到： 这一方程组称为正则方程组（高斯-亚当消元过程）。从而得到一组基本解(基本解中所有基本变量的全体称为基)： 基本变量 如果此时继续对上述形式的方程组进行附加的一次转轴运算，例如选取作 （ (tm)为转轴元素，此时xt进入基， xs出基。这样就完成了从一个基本解到另一个基本解的转换 解：用a11, a22作为轴元素进行两次转轴运算： 例：给定如下方程组，试进行基本解的转换运算。 得到一组基本解： x1=-12 x2=-20 x3=x4=x5=0 用a11，a25作为轴元素进行第三次转轴运算： 又得到一组基本可行解： x1=3 x5=5 x2=x3=x4=0 此时x5进入基， x2出基。 二、基本可行解到基本可行解的转换 当已经得到一组基本可行解，若要求把xk选进基本变量，并使下一组基本解是可行解的话，则在第k列要选取不为任何负值的元素作为转轴元素 alk作为转轴元素进行转轴运算： 方程组第一行发生的变化： alk作为轴元素，xk选进基本变量后， xk的取值由零变成了 一个正值 ，则原来各基本变量的取值变为: 若是基本可行解, 应该保证各差值最小者为零 : 决定了离基变量为xi 若想用xk取代xl成为可行解中的基本变量，就应该选 所对应的行成为转轴行，即所选取的行要满足条件: 规则 例： 基本可行解： x1=3 x5=5 x2=x3=x4=0 基本变量x1、x5 基本可行解的转换： 1）x2、x4系数全部为负，只能选取x3所在的第3列为转轴行 2） , 由于 ，则取第一行为转轴行, 于是取a13=2为转轴元素，使x3取代x1成为基本变量。 经转轴运算得： 得基本可行解： 结论：可把松驰变量作为初始基本可行解中的一部分基本 变量。 三、初始基本可行解的求法 原始约束条件: 引入松驰变量: 可得一组基本可行解： §5-3 单纯形方法 Page ? * * Page ? * * 5-1 线性规划的标准形式与基本性质 5-2 基本可行解的转换 5-3 单纯形方法及应用举例 　第五章　线性规划　 目标函数和约束条件都是线性的，像这类约束函数和目