《机械优化设计线性规划培训课件.ppt》由会员分享，可在线阅读，更多相关《机械优化设计线性规划培训课件.ppt（95页珍藏版）》请在金锄头文库上搜索。
1、,何军良,2,目 录,CONTENTS,第四章 无约束优化方法,线性规划的标准形式与基本性质,02,基本可行解的转换,单纯形方法,单纯形方法应用举例,03,04,05,修正单纯形法,06,概述,01,4,（1） 定义,5.1 概述,目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。 虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。 此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性
2、规划方法就更有用了。,5,（2） 主要研究的问题,5.1 概述,一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。 另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。 实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（ max 或 min ）。,6,（3） 线性规划模型建立,5.1 概述,建模步骤,1 确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量。 2 找出所有限定条件：即决策变量受到的所有的约束； 3 写出目标函数：即问题所要达到的目标，并明确是max
3、 还是 min。,7,（1） 线性规划实例,5.2 标准形式与基本性质,解：设生产A、B两产品分别为x1, x2台，则该问题的优化数学模型为：,例5-1： 某工厂要生产A、B两种产品，每生产一台产品A 可获产值2万元；需占用一车间工作日3天，二车间工作日6天；每生产一台产品B 可获产值1万元；需占用一车间工作日5天，二车间工作日2天。现一车间可用于生产A、B产品的时间15天，二车间可用于生产A、B产品的时间24天。试求出生产组织者安排A、B两种产品的合理投资产数，以获得最大的总产值。,8,（1） 线性规划实例,5.2 标准形式与基本性质,例5-2：生产甲种产品每件需使用材料9kg、3个工时、4
4、kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？,分析：每天生产的甲、乙两种产品分别为 件,（工时约束）,（电力约束）,（材料约束）,(利润最大),9,（1） 线性规划实例,5.2 标准形式与基本性质,将其化成线性规划标准形式：,求,使,且满足,10,（1） 线性规划实例,5.2 标准形式与基本性质,例5-3：某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅
5、有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？,日利润最大,生产能力限制,劳动力限制,变量非负,解: 设甲、乙两种产品的日产件数分别为,s.t.,11,（1） 线性规划实例,5.2 标准形式与基本性质,例5-4：某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定5月份的生产计划，已知合同甲为：A产品1000件，单件价格为500元，违约金为100元/件；合同乙为：B产品500件，单件价格为400元，违约金为120元/件；合同丙为：B产品600件，单件价格为420元，违约金为130元/件；C产品600件
6、，单件价格为400元，违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的生产计划线性规划模型 。,12,（1） 线性规划实例,5.2 标准形式与基本性质,例5-5：成批生产企业年度生产计划的按月分配 。 在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。 在年度计划按月分配时一般要考虑:1）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产
7、；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。,13,（2） 线性规划的标准形式,5.2 标准形式与基本性质,14,（2） 线性规划的标准形式,5.2 标准形式与基本性质,矩阵形式,决策变量,常数项,系数矩阵,价值系数,其中：,15,（2） 线性规划的标准形式,5.2 标准形式与基本性质,矩阵形式的另一种表示,max (min) zCTX s.t. AX(,)b X0,16,（2） 线性规划的标准形
8、式,5.2 标准形式与基本性质,线性规划的向量形式,设,则得LP的向量形式：,17,（2） 线性规划的标准形式,5.2 标准形式与基本性质,线性规划数学模型的一般形式：,求,使,且满足,说明： 1）m=n,唯一解 2）mn,无解 3）mn,无穷解,18,（2） 线性规划的标准形式,5.2 标准形式与基本性质,标准型特征： 目标函数极大化 约束条件为等式 决策变量非负 资源向量非负,maxZ=CX St. AX=b X 0,19,（2） 线性规划的标准形式,5.2 标准形式与基本性质,x3为松弛变量,约束条件为“ ”时：,约束条件包括两部分：一是等式约束条件，二是变量的非负要求，它是标准形式中出
9、现的唯一不等式形式。,将一般形式的线性规划化为标准形式的方法,（1）如果有不等式约束,则可加上新的变量,此时称xn+i为松弛变量，把他们全,变为等式约束,20,（2） 线性规划的标准形式,5.2 标准形式与基本性质,约束条件为“ ”时：,（2）如果有不等式约束,则可减去新的变量,此时称xn+i为剩余变量，把他们全,变为等式约束,x3为剩余变量,21,（2） 线性规划的标准形式,5.2 标准形式与基本性质,（3）如果有变量,1、x 0，令x - x。,2、x取值无约束，令x= x- x“,如：,22,（2） 线性规划的标准形式,5.2 标准形式与基本性质,（4）x两边有约束的情况。,-6+6 x
10、1+6 10+6 令x1 = x1 +6 0 x1 16,（5）右端常数。,右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。,23,（2） 线性规划的标准形式,5.2 标准形式与基本性质,例5-1的数学模型可化为如下的标准形式,用矩阵和向量表示则有：,24,（3） 线性规划的基本性质,5.2 标准形式与基本性质,以例5-1为例，用图解法解释线性规划的几何意义，并与代数法得到的解加以对照说明,25,（3） 线性规划的基本性质,5.2 标准形式与基本性质,通过顶点的直线满足上述条件，故点是该问题的最优解。,令松弛变量x3=0，x4=0,画出上述约束方程的图线。 取Z为不同的
11、常数，可画出一系列平行直线。在此直线族中，确定出一条直线满足以下条件，即：尽可能远离原点O，且与多边形OACD至少有一交点。,26,（3） 线性规划的基本性质,5.2 标准形式与基本性质,用代数法解联立方程组。设变量个数为n，方程个数为m，令p=n-m，为使方程组有唯一解，让p个变量等于0。,在例5.1中，p=4-2=2，因此，若4个变量中使任意两个等于0，则必存在两个变量组的唯一解。,下表列出了6个可能的解，其中4个解恰好等于多边形的4个顶点，余下的2个解违反了变量非负的条件。,27,（3） 线性规划的基本性质,5.2 标准形式与基本性质,可行解：同时满足所有约束条件的任何一个解x=x1,x
12、2,xnT。例：多边形OACD域中任意一个解。 基本解：令线性规划标准形式中任意(n-m)个变量等于零，若剩余的m个变量构成的m个线性方程有唯一解，则称由此得到的n个变量的解为基本解。例：上表5列出的个解(或图对应的个顶点A、B、C、D、E、O)。 基本可行解：如果基本解还满足非负条件xj0(j=1,2,n),则称之为基本可行解（既是基本解，又是可行解）。例：表中列出的4个解(或图6.1对应的4个顶点A、C、D、O)。,28,（3） 线性规划的基本性质,5.2 标准形式与基本性质,最优解：使目标函数达到最小值的基本可行解。例：图中的点C为最优解，对应的目标函数值为-33/4. 基、基向量、基变
13、量与非基变量 基：在系数矩阵A中，选择m列线性无关向量构成mm阶非奇异子矩阵B,则称B为线性规划的一个基。 基向量：组成基B的列向量pj(j=1,2,m)。 基变量：与基向量对应的变量xj(j=1,2,m)。用xB表示。基变量取正值。 非基变量：除基变量外的其余(n-m)个变量。用xN表示。非基变量取零。,29,（3） 线性规划的基本性质,5.2 标准形式与基本性质,基变量和非基变量是相对于基而言的。,30,（3） 线性规划的基本性质,5.2 标准形式与基本性质,线性规划问题的以上几个解的关系，可用下图来描述：,31,（3） 线性规划的基本性质,5.2 标准形式与基本性质,32,（3） 线性规
14、划的基本性质,5.2 标准形式与基本性质,基本解共10个,每个基本解中有n-m2变量取零值。基本可行解5个。,33,（3） 线性规划的基本性质,5.2 标准形式与基本性质,线性规划的两个重要性质 线性规划可行解的集合构成一个凸集，且这个凸集是凸多面体，它的每一个顶点对应于一个基本可行解，即顶点与基本可行解相当。 线性规划的最优解如果存在，必然在凸集的某个顶点（即某个基本可行解）上达到。,34,（3） 线性规划的基本性质,5.2 标准形式与基本性质,线性规划解的特殊情形,因此，线性规划的最优解不必在可行域整个区域内搜索，只要在它的有限个基本可行解（顶点）中去寻找即可。,35,（3） 线性规划的基
15、本性质,5.2 标准形式与基本性质,但是，在实际的线性规划问题中，其变量的个数n和约束方程的个数m都是很大的，其基本可行解的数目非常多，即使采用计算机也难以实现；同时，仅仅考察基本可行解，也不能确定问题何时有无界解。 故没有必要找出所有的基本可行解以求得最优解，而是采用一定的方法如单纯形法来解决这个问题。,36,（1） 基本解到基本解的转换,5.3 基本可行解的转换,把约束条件展开,37,（1） 基本解到基本解的转换,采用高斯-约当法(Gauss-Jordan)进行消元：,此过程称作对变量xk进行转轴运算， xk称为转轴变量， alk称为转轴元素。,5.3 基本可行解的转换,38,（1） 基本
16、解到基本解的转换,选取另一变量作为转轴变量进行第二次转轴运算，并反复此过程，我们将得到：,这一方程组称为正则方程组（高斯-约当消元过程）。从而得到一组基本解(基本解中所有基本变量的全体称为基)：,基本变量,非基本变量,5.3 基本可行解的转换,39,（1） 基本解到基本解的转换,如果此时继续对上述形式的方程组进行附加的一次转轴运算，例如选取作 (tm)为转轴元素，此时xt进入基， xs出基。这样就完成了从一个基本解到另一个基本解的转换,5.3 基本可行解的转换,40,（1） 基本解到基本解的转换,5.3 基本可行解的转换,解：用a11, a22作为轴元素进行两次转轴运算：,例：给定如下方程组，试进行基本解的转换运算。,得到一组基本解： x1=-12 x2=-20 x3=x4=x5=0,4
