机械优化设计第五章(哈工大―孙靖民)课件

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）m>n,无解3）m<n,无穷解二、线性规划的标准形式将一般形式的线性规划化为标准形式的方法x3为松弛变量约束条件为“”时：约束条件包括两部分：一是等式约束条件，二是变量的非负要求，它是标准形式中出现的唯一不等式形式x3为剩余变量约束条件为“”时：(2)变量3x1'-3x1"+2x28x1'

-x1"-4x2

14x1',x1",

x2

01、x

0，令x’＝-x。3x1+2x28x1-4x214x202、x取值无约束，令x=x'-x"3x1'-3x1"+2x2+x3=8

x1'

-x1"-4x2+x4=14x1',x1",x2,x3,x40例如：x1'

+x211x1'16x1',x20（3）x两边有约束的情况。x1+x25-6x110x20-6+6x1+6

10+6

令x1'

=x1+6

0x1'

16(4)右端常数右端项b＜0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。三、线性规划的基本性质图5.1线性规划的几何意义图5.1线性规划的几何意义通过顶点Ｃ的直线满足上述条件，故点Ｃ是该问题的最优解。序号123456变量值x10005415/4x20312003/4x3150-45030x424180-600图5.1中对应的顶点ODEBAC可行域可行解：同时满足所有约束条件的任何一个解x=[x1,x2,…,xn]T。例：多边形OACD域中任意一个解。基本可行解：如果基本解还满足非负条件xj≥0(j=1,2,…,n),则称之为基本可行解（既是基本解，又是可行解）。例：表5-1中列出的4个解(或图6.1对应的4个顶点A、C、D、O)。基本解：令线性规划标准形式中任意(n-m)个变量等于零，若剩余的m个变量构成的m个线性方程有唯一解，则称由此得到的n个变量的解为基本解。例：表5-1中列出的６个解(或图6.1对应的６个顶点A、B、C、D、E、O)。最优解：使目标函数达到最小值的基本可行解。例：图5.1中的点C为最优解，对应的目标函数值为-33/4.线性规划问题的以上几个解的关系，可用下图来描述：基本解共10个,每个基本解中有n-m＝2变量取零值。基本可行解5个线性规划的两个重要性质线性规划可行解的集合构成一个凸集，且这个凸集是凸多面体，它的每一个顶点对应于一个基本可行解，即顶点与基本可行解相当。线性规划的最优解如果存在，必然在凸集的某个顶点（即某个基本可行解）上达到。

因此，线性规划的最优解不必在可行域整个区域内搜索，只要在它的有限个基本可行解（顶点）中去寻找即可。但是，在实际的线性规划问题中，其变量的个数n和约束方程的个数m都是很大的，其基本可行解的数目非常多，即使采用计算机也难以实现；同时，仅仅考察基本可行解，也不能确定问题何时有无界解。故没有必要找出所有的基本可行解以求得最优解，而是采用一定的方法如单纯形法来解决这个问题。一、基本解到基本解的转换把约束条件展开：§5-2基本可行解的转换采用高斯-约当法(Gauss-Jordan)进行消元：此过程称作对变量xk进行转轴运算，

xk称为转轴变量，

alk称为转轴元素。选取另一变量作为转轴变量进行第二次转轴运算，并反复此过程，我们将得到：这一方程组称为正则方程组（高斯-亚当消元过程）。从而得到一组基本解(基本解中所有基本变量的全体称为基)：基本变量如果此时继续对上述形式的方程组进行附加的一次转轴运算，例如选取作（

(t>m)为转轴元素，此时xt进入基，

xs出基。这样就完成了从一个基本解到另一个基本解的转换解：用a11,

a22作为轴元素进行两次转轴运算：例：给定如下方程组，试进行基本解的转换运算。得到一组基本解：

x1=-12

x2=-20

x3=x4=x5=0用a25作为轴元素进行第三次转轴运算：又得到一组基本可行解：

x1=3

x5=5

x2=x3=x4=0此时x5进入基，

x2出基。二、基本可行解到基本可行解的转换当已经得到一组基本可行解，若要求把xk选进基本变量，并使下一组基本解是可行解的话alk作为转轴元素进行转轴运算：方程组第一行发生的变化：若想用xk取代xl成为可行解中的基本变量，即所选取的行要满足条件:规则例：基本可行解：

x1=3

x5=5

x2=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个变量组成基本可行解的基本变量相应的目标函数值为:经过转轴运算得到另一组基本可行解为:其中：进基变量xk出基变量xs对应的目标函数为:由于要求∴结论:一旦所有的,即可停止转轴运算,对应的可行解就是最优解。r是对线性规划问题的解进行最优性检验的标志，称之