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

1、机械优化设计何军良何军良 上海海事大学上海海事大学Shanghai Maritime University 1909 2009 2004 1912 1958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目 录CONTENTS一维搜索方法无约束优化方法线性规划 约束优化方法 第四章 无约束优化方法 线性规划的标准形式与基本性质02 基本可行解的转换 单纯形方法 单纯形方法应用举例030405 修正单纯形法06 概述014（1） 定义5.1 概述目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广

2、泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。5（2） 主要研究的问题5.1 概述一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。 实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（ max 或 min ）。6（3） 线性规划模型建立5.1 概述建模步

3、骤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

4、天。试求出生产组织者安排A、B两种产品的合理投资产数，以获得最大的总产值。max. .zxxstxxxxxx12121212235156224008（1） 线性规划实例5.2 标准形式与基本性质例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？ 12,x x1212(,)60120maxf x xxx112()94360gXxx分析：每天生产的分别为 件 （工时约束）（电力约束）（材料

5、约束）(利润最大)212()310300gXxx312()45200gXxx9（1） 线性规划实例5.2 标准形式与基本性质将其化成线性规划标准形式：12394360 xxx124310300 xxx12545200 xxx求T12xxx12min( )60120f xxx 使且满足0(1,2,3,4,5)ixi 10（1） 线性规划实例5.2 标准形式与基本性质例5-3：某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元

6、。问工厂如何组织生产才能获得最大利润？日利润最大生产能力限制劳动力限制变量非负.,21xx解: 设甲、乙两种产品的日产件数分别为0,2432798040)(max212121221xxxxxxRDXxxXFs.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元，违

7、约金为90元/件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的生产计划线性规划模型 。工序1工序2工序3原材料1 原材料2其他成本产品A /件2323410产品B /件1132310产品C /件2124210总工时或原材料460040006000100008000工时或原材料成本（元）151010204012（1） 线性规划实例5.2 标准形式与基本性质例5-5：成批生产企业年度生产计划的按月分配 。在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按

8、月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。 在年度计划按月分配时一般要考虑:1）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。13（2） 线性规划的标准形式5.2 标准形式与基本性质max(min)zc xc xc xnn112211112211211222221122. .(. )(. )(.

9、 )nnnnmmmnnms ta xa xa xba xa xa xba xaxa xb 0,11nxxx14（2） 线性规划的标准形式5.2 标准形式与基本性质矩阵形式max(min)( , ) 0zCXAXbX nxxxX21决策变量常数项nbbbb21系数矩阵nmijmnmmnnaaaaaaaaaaA212222111211价值系数ncccC21其中：15（2） 线性规划的标准形式5.2 标准形式与基本性质矩阵形式的另一种表示ncccC21nxxxX21nbbbb21mnmmnnaaaaaaaaaA212222111211max (min)zCTX s.t. AX(,)b X016（2）

10、 线性规划的标准形式5.2 标准形式与基本性质线性规划的向量形式设则得LP的向量形式： j P = b=jjmmjababba1122max(min)( , ). .(, ,. )njjjnjjjjzc xP xbstxjn 1101 217（2） 线性规划的标准形式5.2 标准形式与基本性质线性规划数学模型的一般形式：11112211211222221122nnnnmmmnnma xa xa xba xa xaxbaxaxaxb求T12nxx xx1122()m innnfxc xc xc x使且满足0(1,2, )ixin 0(1,2,)jbjm 说明：1）m=n,唯一解2）mn,无解3）

11、mm)为转轴元素，此时xt进入基， xs出基。这样就完成了从一个基本解到另一个基本解的转换sta5.3 基本可行解的转换40（1） 基本解到基本解的转换5.3 基本可行解的转换1234512345541322058xxxxxxxxxx解：用a11, a22作为轴元素进行两次转轴运算：例：给定如下方程组，试进行基本解的转换运算。134523450723120123420 xxxxxxxx 得到一组基本解： x1=-12 x2=-20 x3=x4=x5=041（1） 基本解到基本解的转换5.3 基本可行解的转换用a25作为轴元素进行第三次转轴运算：1234234531203441303544xxx

12、xxxxx又得到一组基本可行解： x1=3 x5=5 x2=x3=x4=0此时x5进入基， x2出基。121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxaxa xbxxx111211001lnmnlmmlkknlmmmmmkknmaxa xa xbxxxaxaxaxb当已经得到一组基本可行解，若要求把xk选进基本变量，并使下一组基本解是可行解的话，则在第k列要选取不为任何负值的元素作为转轴元素。5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换alk作为转轴元素进行转轴运算：121211111122112212100

13、010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxaxa xbxxx1112110101lnmnlmlmnlklklkmmmmmkkknmaabxxaaaxxxaxaxaxxb5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换1121111111211000100nlnmmmkknlmlmmnlklklkkxxxaxa xa xbaabxxxxaaaxx1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x5.3 基本可行解的转换（2） 基本可行解到基本可行解

14、的转换方程组第一行发生的变化：1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x1112111111121111111100()0()000lnnlnlmmmkmkknlklklmlmkmkkknklkllklklkkbbaaaaxxxaaxxaaxaaaabxxxaxa xaxaaaa5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换alk作为轴元素，xk选进基本变量后， xk的取值由零变成了一个正值 ，则原来各基本变量的取值变为:llkba11111222220000lllkk

15、llkkkkkkkkmmmkkmmkxxba xbaxbaxbaxbaxbaxba xba若是基本可行解, 应该保证各差值最小者为零 :min ()0iikibaminikiikbxa 决定了非基变量为xi5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换若想用xk取代xl成为可行解中的基本变量，就应该选 所对应的行成为转轴行，即所选取的行要满足条件:0llkba0lkamin ()lkllkbxa规则规则5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换例：例：1234234531203441303544xxxxxxxx基本可行解： x1=3 x5=5 x2=x3=x4=

16、0基本变量x1、x5 基本可行解的转换： 1）x2、x4系数全部为负，只能选取x3所在的第3列为转轴行 2） , 由于 ，则取第一行为转轴行, 于是取a13=2为转轴元素，使x3取代x1成为基本变量。3523minikiikbxa5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换经转轴运算得：12341245131302882373102882xxxxxxxx得基本可行解： 351243122xxxxx 5.3 基本可行解的转换（2） 基本可行解到基本可行解的转换结论：可把松驰变量作为初始基本可行解中的一部分基本变量。12312352100,1,2,3ixxxxxxxi 123412

17、350520100,1,2,3,4,5ixxxxxxxxxi 451235,10,0 xxxxx原始约束条件:引入松驰变量:可得一组基本可行解：5.3 基本可行解的转换（3） 初始基本可行解的求法515.3 单纯形方法及应用举例要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过 个），但当m和n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。单纯形法的基本思路是：从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。按照单纯形法的思路求

18、解线性规划问题, 要解决三个技术问题：（1）给出第一个基本可行解；（2）转换到另一个基本可行解；（3）检验一个基本可行解是否是最优解。mnC525.3 单纯形方法及应用举例把线性规划问题变成标准形，观察是否每个约束方程中都有独有的、系数为1的变量。p 如果是，则取这些变量作为基变量，便得到一个基本可行解；p 否则，就给没有这种变量的约束条件添加一个人工变量，同时修改目标函数。（1）确定初始基可行解535.3 单纯形方法及应用举例（1）确定初始基可行解1 122max(min)nnZc xc xc x11 11221121 1222221 122( , )( , ).( , )0,(1,2, )

19、nnnnmmmnnmja xa xa xba xa xa xbsta xa xa xbxjn 11,111,122,112,2,11,.0 (1,2, )mmn nmmn nmm mmm n nmjxaxa xbxaxa xbstxaxaxbxjn1 122maxnnZc xc xc x标准形变化545.3 单纯形方法及应用举例（1）确定初始基可行解 0 0 0 0 1 0 0 0 0 0 1 mnmnmmmnaaaaAaa11121211首先有假定的系数矩阵A中包含一个m阶单位矩阵，即有m个单位列向量，那么这m个单位列向量所对应的基本可行解是一个基本可行解。设A的前m列为单位向量，即：（1）

20、555.3 单纯形方法及应用举例（1）确定初始基可行解显然， 是（L,P）的一个基本可行解，其中， 。我们就从这个初始基本可行解，开始单纯形法的迭代（搜索） 的第一步。从（1）式中求解出：(, , )TmXb bb11200ib 0,mxxx12即mmn nmmn nmmmmmmn nxbaxa xxbaxa xxbaxa x11111122211211 （2） 取非基变量等于零，得到初始基可行解565.3 单纯形方法及应用举例（2）基可行解转换基可行解转换是从一个基可行解转换为相邻的基可行解（即从一个顶点转到另一个顶点）。p 定义：两个基可行解是相邻的，如果它们之间变换且仅变换一个基变量。p

21、 规则： 规则。575.3 单纯形方法及应用举例（2）基可行解转换 规则1 0 0 0 .a. 0 1 0 0 .a. .0 0 0 1 .a. mjnm2jnmmmm,jmnaabaabAbaa1111212211P1 P2 P3 Pm Pm+1 Pj Pn bmin/|,/iikikllkbaimaba10585.3 单纯形方法及应用举例（3）最优性检验和解的判别将基可行解X(0)和X(1)分别代入目标函数得：(0)01miiic xz(1)00111(0)1mmmiiijjiijiijiiimjiijic xacc xccaccazz1mjiijicca被称为检验数，通常简写为 或()j

22、jczj如果单纯形表最后一行中的 都满足 ，则对应的基本可行解是最优解；否则，就不是最优解。j0j595.3 单纯形方法及应用举例用单纯形法求解线性规划问题的具体步骤如下： 找出初始可行基，确定初始基本可行解，建立初始单纯形表；转。 检验对应于非基变量的检验数 。若 （xj为非基变量）都成立，则当前单纯形表对应的基本解就是最优解，停止计算；否则转。 在所有 中，若最大 对应的xk的系数ai k0 (i=1,2,m)，则此问题为无界解（无解），停止计算；否则转。j0j0jk605.3 单纯形方法及应用举例 根据 确定xk为换入变量；根据规则确定相应的换出变量。转。 以aik为中心元素进行变换，并

23、得到中心元素aik旋转运算得到新的单纯形表。转 max(0)jk单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是，则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。615.3 单纯形方法及应用举例单纯形表的格式：迭代次数XBCBx1x2xnb比值C1C2Cn0 x1C1a11a12a1nb11x2C2a21a22a2nb22.xmCmam1am2amnbmmZjZjZjZjj12n625.3 单纯形方法及应用举例（4）单纯形应用举例例5-6：用图

24、解法和单纯形法求如下线性规划问题的最优解。12121212M ax437. .429,0Zxxxxs txxxx635.3 单纯形方法及应用举例（4）单纯形应用举例0123456712345(2.25,0)4x1+x2=91、图解法求解645.3 单纯形方法及应用举例（4）单纯形应用举例2、单纯形法求解迭代次数基变量CBx1x2x3x4b比值01310742019Zjj12121212M a x437. .429,0Zxxxxs txxxx655.3 单纯形方法及应用举例（4）单纯形应用举例2、单纯形法求解迭代次数基变量CBx1x2x3x4b比值41000 x3013107x4042019Zj

25、00000j4100 填目标函数系数、填基变量列、填CB列； 计算Zj 、计算检验数。665.3 单纯形方法及应用举例（4）单纯形应用举例2、单纯形法求解迭代次数基变量CBx1x2x3x4b比值41000 x30131077x40420199/4Zj00000j4100最优吗？查什么？不是！谁进基？检验数最大的x1进基，谁出基？x1的系数有正的吗？求比值？基变量列中 x4 换为 x1；改CB列， 0 换为 4 675.3 单纯形方法及应用举例（4）单纯形应用举例2、单纯形法求解迭代次数基变量CBx1x2x3x4b比值41000 x30131077x40420199/4Zj00000j4100迭

26、代次数基变量CBx1x2x3x4b比值41001x3002.51-0.254.75x1410.500.252.25Zj42019j0-10-1685.3 单纯形方法及应用举例（4）单纯形应用举例例5-7：用单纯形法求如下线性规划问题的最优解。121221212M a x5 04 0351 5 02 0. .853 0 0,0Zxxxxxs txxxx695.3 单纯形方法及应用举例（4）单纯形应用举例3x1+5x2+x3= 150 x2+x4= 208x1+5x2+x5= 300Max Z=50 x1+40 x2+0 x3+0 x4+0 x5标准化x1，x2，x3，x4，x5 0705.3 单

27、纯形方法及应用举例（4）单纯形应用举例迭代次数基变量CBx1x2x3x4x5b比值50400000 x3035100150150/5x400101020-x5085001300300/8Zj000000j5040000当前基本可行解：(0, 0, 150, 20, 300) ， Z=0。715.3 单纯形方法及应用举例（4）单纯形应用举例迭代次数基变量CBx1x2x3x4x5b比值50400001x30025/810-3/875/212x40010102020 x15015/8001/875/260Zj50125/40025/41875j035/400-25/4当前基本可行解：(75/2, 0

28、, 75/2, 20, 0) ， Z=1875。725.3 单纯形方法及应用举例（4）单纯形应用举例迭代次数基变量CBx1x2x3x4x5b比值50400001x240018/250-3/2512x4000-8/2513/258x15010-5/2505/2530Zj504014/5026/51980j00-14/50-26/5当前解：(30, 12, 0, 8, 0) ，为最优， Z*=1980。73例5-8：用单纯形法求如下线性规划问题的最优解。12121212M ax2328416. .412,0Zxxxxxs txxx5.3 单纯形方法及应用举例（4）单纯形应用举例74迭代次数基变量C

29、Bx1x2x3x4x5b比值230001x301010-1/222x4040012164x2301001/43-j2000-3/49迭代次数基变量CBx1x2x3x4x5b比值230000 x301210084x404001116-x5004001123j2300005.3 单纯形方法及应用举例（4）单纯形应用举例75迭代次数基变量CBx1x2x3x4x5b比值230001x121001/404x5000-21/214x23011/2-1/802j00-3/2-1/8014迭代次数基变量CBx1x2x3x4x5b比值230000 x121010-1/22-x4000-41284x2301001

30、/4312j00-201/413此问题的最优解为:x1*=4, x2*=2, x5*=4， x3*= x4*= x1*=0, z*=2 4+3 2=145.3 单纯形方法及应用举例（4）单纯形应用举例765.4 单纯形方法的特殊情况最终产生最优值的单纯形表中，某一非基本变量的检验数为0，意味着作任何增大，目标函数的最优值不变。此时线性规划问题的最优解并不唯一，有多重最优解。（见例题）（1）无穷最优解例5-9：用单纯形法求如下线性规划问题的最优解。12341231241234Min3224. .36,0Zxxxxxxxs txxxxxxx775.4 单纯形方法的特殊情况解：另Z = -Z，将原线

31、性规划问题变为MAX形式。（1）无穷最优解12341231241234Max3224. .36,0Zxxxxxxxs txxxxxxx 迭代次数基变量CBx1x2x3x4b比值-3-1-1-10 x3-1-221042x4-1310166j-2200-8785.4 单纯形方法的特殊情况（1）无穷最优解迭代次数基变量CBx1x2x3x4b比值-3-1-1-11x2-1-111/202-x4-140-1/2141j00-10-6迭代次数基变量CBx1x2x3x4b比值-3-1-1-12x2-1013/81/43x1-310-1/81/41j00-10-6最优解为：X1*=（0 2 0 4） X2*

32、=（1 3 0 0）所以： X*=X1*+（1-）X2*，其中0 0的非基变量中选取下标最小的进基； 当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环，当然，这样也可能使收敛速度降低。855.4 单纯形方法的特殊情况（4）总结1、在迭代过程中要保持常数列向量非负，这能保证基解的非负性。最小比值能做到这一点。2、主元素不能为0，因为行的初等变换不能把0变成1。3、主元素不能为负数，因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。4、每一步运算只能用矩阵初等行变换。865.5 单纯形方法进一步讨论所给LP的标准型中约束矩阵中没有现成的可行基怎么办？

33、人工变量法针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。（1）人工变量法12312312123M in224. .26,0Zxxxxxxs txxxxx 1231234121234Min224. .26,0Zxxxxxxxs txxxxxx 标准化规范化1规范化2123234121234Min2516. .26,0Zxxxxxxs txxxxxx 123123412512345Min224. .26,0Zxxxxxxxs txxxxxxxx 87（1）人工变量法但是，对于用单纯形法求解LP问题：1312312323123M a x3421. .39,0Zxxxxxxxxs txxxxx首先，转化成标准形式：12345123412352312345M a x3000421. .39,0Zxxxxxxxxxxxxxs txxxxxxx 5.5 单纯形方法进一步讨论88（1）人工变量法再强行加上人工变量，使其出现