《机械优化设计 第5版 教学课件 ppt 作者 孙靖民 第5章线性规划》由会员分享，可在线阅读，更多相关《机械优化设计 第5版 教学课件 ppt 作者 孙靖民 第5章线性规划（56页珍藏版）》请在金锄头文库上搜索。
1、机械优化设计,第五章 线性规划,第五章 线性规划,目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。,第五章 线性规划,解：设生产A、B两产品分别为x1, x2台，则该问题的优化数学模型为：,例5-1： 某工厂要生产A、B两种产品，每生产一台产品A 可获产值2万元；
2、需占用一车间工作日3天，二车间工作日6天；每生产一台产品B 可获产值1万元；需占用一车间工作日5天，二车间工作日2天。现一车间可用于生产A、B产品的时间15天，二车间可用于生产A、B产品的时间24天。试求出生产组织者安排A、B两种产品的合理投资产数，以获得最大的总产值。,第一节 线性规划的标准形式与基本性质,一、线性规划实例,例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？,分析：每
3、天生产的甲、乙两种产品分别为 件,（工时约束）,（电力约束）,（材料约束）,(利润最大),将其化成线性规划标准形式：,求,使,且满足,例5-3：某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？,日利润最大,生产能力限制,劳动力限制,变量非负,解: 设甲、乙两种产品的日产件数分别为,s.t.,建模例1： 某公司有钢材、铝材、铜材1200t，800t和650t，拟调往物资紧张的地区甲、乙
4、、丙。已知甲、乙、丙对上述物资的总需求分别为：900t，800t和1000t。各种物资在各地销售每吨的获利如下表所示。试问公司应如何安排调运计划，才能获利最大？建立该问题的数学模型。,物资,获利,地区,建模例2： 某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定5月份的生产计划，已知合同甲为：A产品1000件，单件价格为500元，违约金为100元/件；合同乙为：B产品500件，单件价格为400元，违约金为120元/件；合同丙为：B产品600件，单件价格为420元，违约金为130元/件；C产品600件，单件价格为400元，违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况
5、见下表。试以利润为目标，建立该工厂的生产计划线性规划模型 。,建模例3： 成批生产企业年度生产计划的按月分配 。 在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。 在年度计划按月分配时一般要考虑:1）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个
6、月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。,线性规划数学模型的一般形式：,求,使,且满足,说明： 1）m=n,唯一解 2）mn,无解 3）mn,无穷解,二、线性规划的标准形式,将一般形式的线性规划化为标准形式的方法,x3为松弛变量,约束条件为“ ”时：,约束条件包括两部分：一是等式约束条件，二是变量的非负要求，它是标准形式中出现的唯一不等式形式,x3为剩余变量,约束条件为“ ”时：,(2) 变量,1、x 0，令x- x。,2、x取值无约束，令x= x- x“,例如：,（3）x两边有约束的情况。,-6+6 x1+6 10+6 令x1
7、 = x1 +6 0 x1 16,(4) 右端常数,右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。,三、线性规划的基本性质,通过顶点的直线满足上述条件，故点是该问题的最优解。,可行解：同时满足所有约束条件的任何一个解x=x1,x2,xnT。例：多边形OACD域中任意一个解。,基本可行解：如果基本解还满足非负条件xj0(j=1,2,n),则称之为基本可行解（既是基本解，又是可行解）。 例：表5-1中列出的4个解(或图6.1对应的4个顶点A、C、D、O)。,基本解：令线性规划标准形式中任意 (n-m)个变量等于零，若剩余的m个变量构成的m个线性方程有唯一解，则称由此得到的
8、n个变量的解为基本解。例：表5-1中列出的个解(或图6.1对应的个顶点A、B、C、D、E、O)。,基、基向量、基变量与非基变量 基：在系数矩阵A中，选择m列线性无关向量构成mm阶非奇异子矩阵B,则称B为线性规划的一个基。 基向量：组成基B的列向量pj(j=1,2,m)。 基变量：与基向量对应的变量xj(j=1,2,m)。用xB表示。 非基变量：除基变量外的其余(n-m)个变量。用xN表示。,最优解：使目标函数达到最小值的基本可行解。 例：图5.1中的点C为最优解，对应的目标函数值为-33/4.,基变量和非基变量是相对于基而言的。,线性规划问题的以上几个解的关系，可用下图来描述：,基本解共10个
9、,每个基本解中有n-m2变量取零值。基本可行解5个,线性规划的两个重要性质 线性规划可行解的集合构成一个凸集，且这个凸集是凸多面体，它的每一个顶点对应于一个基本可行解，即顶点与基本可行解相当。 线性规划的最优解如果存在，必然在凸集的某个顶点（即某个基本可行解）上达到。,图5.2 线性规划解的特殊情形,因此，线性规划的最优解不必在可行域整个区域内搜索，只要在它的有限个基本可行解（顶点）中去寻找即可。,但是，在实际的线性规划问题中，其变量的个数n和约束方程的个数m都是很大的，其基本可行解的数目非常多，即使采用计算机也难以实现；同时，仅仅考察基本可行解，也不能确定问题何时有无界解。 故没有必要找出所
10、有的基本可行解以求得最优解，而是采用一定的方法如单纯形法来解决这个问题。,一、从一个基本解转到另一个基本解 把约束条件展开：,第二节 基本可行解的转换,采用高斯-约当法(Gauss-Jordan)进行消元：,此过程称作对变量xk进行转轴运算， xk称为转轴变量， alk称为转轴元素。,选取另一变量作为转轴变量进行第二次转轴运算，并反复此过程，我们将得到：,这一方程组称为正则方程组（高斯-亚当消元过程）。从而得到一组基本解(基本解中所有基本变量的全体称为基)：,基本变量,如果此时继续对上述形式的方程组进行附加的一次转轴运算，例如选取作 （ (tm)为转轴元素，此时xt进入基， xs出基。这样就完
11、成了从一个基本解到另一个基本解的转换,解：用a11, a22作为轴元素进行两次转轴运算：,例：给定如下方程组，试进行基本解的转换运算。,得到一组基本解： x1=-12 x2=-20 x3=x4=x5=0,用a25作为轴元素进行第三次转轴运算：,又得到一组基本可行解： x1=3 x5=5 x2=x3=x4=0 此时x5进入基， x2出基。,二、从一个基本可行解转到另一个基本可行解,当已经得到一组基本可行解，若要求把xk选进基本变量，并使下一组基本解是可行解的话，则在第k列要选取不为任何负值的元素作为转轴元素,alk作为转轴元素进行转轴运算：,方程组第一行发生的变化：,alk作为轴元素，xk选进基
12、本变量后， xk的取值由零变成了 一个正值 ，则原来各基本变量的取值变为:,若是基本可行解, 应该保证各差值最小者为零 :,决定了离基变量为xi,若想用xk取代xl成为可行解中的基本变量，就应该选 所对应的行成为转轴行，即所选取的行要满足条件:,规则,例：,基本可行解： x1=3 x5=5 x2=x3=x4=0 基本变量x1、x5 基本可行解的转换： 1）x2、x4系数全部为负，只能选取x3所在的第3列为转轴行 2） , 由于 ，则取第一行为转轴行, 于是取a13=2为转轴元素，使x3取代x1成为基本变量。,经转轴运算得：,得基本可行解：,结论：可把松驰变量作为初始基本可行解中的一部分基本 变
13、量。,三、初始基本可行解的求法,原始约束条件:,引入松驰变量:,可得一组基本可行解：,一、单纯形法的基本思想 从一个初始基本可行解X0出发，寻找目标函数有较大下降的一个新的基本可行解X1,代替原来的基本可行解X0，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。,第三节 单纯形方法,采用单纯形法求解线性规划问题，主要应解决以下三个问题： （1）如何确定初始基本可行解； （2）如何由一个基本可行解迭代出另一个基本可行解，同时保证目标函数的下降性； （3）如何判断一个基本可行解是否为最优解。,二.最优解规则,对应一组基
14、本可行解： 前m个变量组成基本可行解的基本变量 相应的目标函数值为:,经过转轴运算得到另一组基本可行解为:,其中：,进基变量xk 出基变量xs,对应的目标函数为:,由于要求,结论:一旦所有的 , 即可停止 转轴运算,对应的可行解就是最优解。r是 对线性规划问题的解进行最优性检验的标 志，称之为检验数。,具体计算时应选取:,由于有可能同时有几组 都为负值,最速变化规则,1）最速变化规则决定进基的非基本变量,结论：,2） 规则决定了出基的基本变量,3）若对基本可行解X，所有检验数rk 0，则X 为最优解。,例5-3某建筑单位拟盖一批二人、三人和四人的宿舍单元，要确定每一种宿舍单元的数目，以获得最大
15、利润。其限制条件如下：1）预算不能超过9000千元。2）宿舍单元总数不得少于350套。3）每类宿舍单元的百分比为：二人的不超过总数的20%，三人的不超过总数的60%，四人的不超过总数的40%（百分比总和超过100，这是上限）。4）建造价格为：二人的宿舍单元是20千元，三人的宿舍单元是25千元，四人的宿舍单元是30千元。5）净利润为：二人的宿舍单元是2千元，三人的宿舍单元是3千元，四人的宿舍单元是4千元。 解：略,第四节 单纯形法应用举例,修正单纯形法的迭代过程如下：,第五节 修正单纯形法,（1）根据问题的需要，加入松弛变量或人工变量，写出初始基方阵E，求E-1和基本解 （2）计算 和 ，对应于非基本变量计算相应的 。若所有 （对极小化问题），则x为最优解；否则转至步骤（3）。 （3）选取进入新的基方阵的 ，找出 ，计算 。若所有 ，则无解；否则转至步骤（4）。,修正单纯形法的迭代过程如下：,第五节 修正单纯形法,（4）计算 ，选取离开 基方阵的 ，形成新的基方阵 ，转至步骤（5）。 （5）计算新的矩阵 的逆矩阵 和 。每迭代一次，就构成一个新的逆矩阵。 然后转至步骤（1）重复计算，直到求得最优解和相应的目标函数值（极小值或极大值）。,E
