机械优化设计--第五章(第7次课)

机械优化设计2017年6月上海海事大学SHANGHAIMARITIMEUNIVERSITY何军良上海海事大学ShanghaiMaritimeUniversity19092009200419121958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目录CONTENTS一维搜索方法无约束优化方法线性规划约束优化方法第四章无约束优化方法线性规划的标准形式与基本性质02基本可行解的转换单纯形方法单纯形方法应用举例030405修正单纯形法06概述014（1）定义5.1概述目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。5（2）主要研究的问题5.1概述一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。6（3）线性规划模型建立5.1概述建模步骤1确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量。2找出所有限定条件：即决策变量受到的所有的约束；3写出目标函数：即问题所要达到的目标，并明确是max还是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两种产品的合理投资产数，以获得最大的总产值。max..zxxstxxxxxx12121212　2　　3515　　　6224　　0　　08（1）线性规划实例5.2标准形式与基本性质例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？12,xx1212(,)60120maxfxxxx112()94360gXxx分析：每天生产的甲、乙两种产品分别为件（工时约束）（电力约束）（材料约束）(利润最大)212()310300gXxx312()45200gXxx9（1）线性规划实例5.2标准形式与基本性质将其化成线性规划标准形式：12394360xxx124310300xxx12545200xxx求T12[]xxx12min()60120fxxx使且满足0(1,2,3,4,5)ixi10（1）线性规划实例5.2标准形式与基本性质例5-3：某厂生产甲、乙两种产品，已知：①两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；③产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？日利润最大生产能力限制劳动力限制变量非负.,21xx解:设甲、乙两种产品的日产件数分别为0,2432798040)(max212121221xxxxxxRDXxxXFs.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件，单件价格为400元，违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的生产计划线性规划模型。工序1工序2工序3原材料1原材料2其他成本产品A/件2323410产品B/件1132310产品C/件2124210总工时或原材料460040006000100008000工时或原材料成本（元）151010204012（1）线性规划实例5.2标准形式与基本性质例5-5：成批生产企业年度生产计划的按月分配。在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。在年度计划按月分配时一般要考虑:1）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。13（2）线性规划的标准形式5.2标准形式与基本性质max(min)zcxcxcxnn112211112211211222221122..(.)(.)(.)nnnnmmmnnmstaxaxaxbaxaxaxbaxaxaxb0,,11nxxx14（2）线性规划的标准形式5.2标准形式与基本性质矩阵形式max(min)(,)0zCXAXbXnxxxX21决策变量常数项nbbbb21系数矩阵nmijmnmmnnaaaaaaaaaaA212222111211价值系数ncccC21其中：15（2）线性规划的标准形式5.2标准形式与基本性质矩阵形式的另一种表示ncccC21nxxxX21nbbbb21mnmmnnaaaaaaaaaA212222111211max(min)z＝CTXs.t.AX≤(＝,≥)bX≥016（2）线性规划的标准形式5.2标准形式与基本性质线性规划的向量形式设则得LP的向量形式：jP=b=jjmmjababba1122max(min)(,)..(,,...)njjjnjjjjzcxPxbstxjn1101217（2）线性规划的标准形式5.2标准形式与基本性质线性规划数学模型的一般形式：11112211211222221122nnnnmmmnnmaxaxaxbaxaxaxbaxaxaxb求T12[]nxxxx1122()minnnfxcxcxcx使且满足0(1,2,,)ixin0(1,2,,)jbjm说明：1）m=n,唯一解2）mn,无解3）mn,无穷解18（2）线性规划的标准形式5.2标准形式与基本性质标准型特征：–目标函数极大化–约束条件为等式–决策变量非负–资源向量非负maxZ=CXSt.AX=bX≥019（2）线性规划的标准形式5.2标准形式与基本性质x3为松弛变量1236224xxx约束条件为“”时：126224xx约束条件包括两部分：一是等式约束条件，二是变量的非负要求，它是标准形式中出现的唯一不等式形式。将一般形式的线性规划化为标准形式的方法1122iiinniaxaxaxb　（1）如果有不等式约束则可加上新的变量0nix此时称xn+i为松弛变量，把他们全变为等式约束1122iiinnniiaxaxaxxb20（2）线性规划的标准形式5.2标准形式与基本性质约束条件为“”时：1122iiinniaxaxaxb　（2）如果有不等式约束则可减去新的变量0nix此时称xn+i为剩余变量，把他们全变为等式约束1122iiinnniiaxaxaxxbx3为剩余变量12101218xx123101218xxx21（2）线性规划的标准形式5.2标准形式与基本性质（3）如果有变量1、x0，令x'＝-x。2、x取值无约束，令x=x'-x3x1'-3x1+2x28x1'-x1-4x214x1',x1,x203x1+2x28x1-4x214x203x1'-3x1+2x2+x3=8x1'-x1-4x2+x4=14x1',x1,x2,x3,x40如：22（2）线性规划的标准形式5.2标准形式与基本性质（4）x两边有约束的情况。x1'+x211x1'16x1',x20x1+x25-6x110x20-6+6x1+610+6令x1'=x1+60x1'16（5）右端常数。右端项b＜0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。23（2）线性规划的标准形式5.2标准形式与基本性质12123124min2..351562240(1,2,3,4)jzxxstxxxxxxxj　　　　　　　　12121212max2..3515622400zxxstxxxxxx　　　　　　　　　　例5-1的数学模型可化为如下的标准形式123412343510,15,242,1,0,062013,65,21,00,1,,,AbcppppAppppＴＴＴＴＴ　　，　，　，　，　，　　用矩阵和向量表示则有：24（3）线性规划的基本性质5.2标准形式与基本性质1x2xoDBCAE图5.1线性规划的几何意义12123124min2..351562240(1,2,3,4)jzxxstxxxxxxxj　　　　　　　　以例5-1为例，用图解法解释线性规划的几何意义，并与代数法得到的解加以对照说明25（3）线性规划的基本性质5.2标准形式与基本性质1x2xoDBCAE线性规划的几何意义通过顶点Ｃ的直线满足上述条件，故点Ｃ是该问题的最优解。令松弛变量x3=0，x4=0,画出上述约束方程的图线。取Z为不同的常数，可画出一系列平行直线。在此直线族中，确定出一条直线满足以下条件，即：尽可能远离原点O，且与多边形OACD至少有一交点。26（3）线性规划的基本性质5.2标准形式与基本性质用代数法解联立方程组。设变量个数为n，方程个数为m，令p=n-m，为使方程组有唯一解，让p个变量等于0。在例5.1中，p=4-2=2，因此，若4个变量中使任意两个等于0，则必存在两个变量组的唯一解。序号123456变量值X10005415/4X20312003/4X3150-45030X424180-600图中对应的顶点ODEBAC下表列出了6个可能的解，其中4个解恰好等于多边形的4个顶点，余下的2个解违反了变量非负的条件。27（3）线性规划的基本性质5.2标准形式与基本性质1x2xoDBCAE可行域可行解：同时满