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

《机械优化设计--第五章(第7次课).ppt》由会员分享，可在线阅读，更多相关《机械优化设计--第五章(第7次课).ppt（95页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、机械优化设计20172017年年6 6月月上上 海海 海海 事事 大大 学学SHANGHAI MARITIME UNIVERSITYSHANGHAI MARITIME UNIVERSITY何军良何军良2021/9/23 上海海事大学上海海事大学Shanghai Maritime University 1909 2009 2004 1912 19587机械优化设计中的几个问题1优化设计概述2优化设计的数学基础目 录CONTENTS3一维搜索方法4无约束优化方法5线性规划 6约束优化方法 2021/9/232第四章 无约束优化方法 线性规划的标准形式与基本性质02 基本可行解的转换 单纯形方法 单

2、纯形方法应用举例030405 修正单纯形法06 概述012021/9/23（1）定义5.1 概述目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。2021/9/234（2）主要研究的问题5.1 概述一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使

3、用它们，才能使完成的任务量为最大。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max 或 min）。2021/9/235（3）线性规划模型建立5.1 概述建模步骤1 确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量。2 找出所有限定条件：即决策变量受到的所有的约束；3 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。2021/9/236（1）线性规划实例5.2 标准形式与基本性质解：设生产A、B两产品分别为x1,x2台，则该问题的优化数

4、学模型为：例5-1：某工厂要生产A、B两种产品，每生产一台产品A 可获产值2万元；需占用一车间工作日3天，二车间工作日6天；每生产一台产品B 可获产值1万元；需占用一车间工作日5天，二车间工作日2天。现一车间可用于生产A、B产品的时间15天，二车间可用于生产A、B产品的时间24天。试求出生产组织者安排A、B两种产品的合理投资产数，以获得最大的总产值。2021/9/237（1）线性规划实例5.2 标准形式与基本性质例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300

5、个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？分析：每天生产的甲、乙两种产品甲、乙两种产品分别为 件 （工时约束）（电力约束）（材料约束）(利润最大)2021/9/238（1）线性规划实例5.2 标准形式与基本性质将其化成线性规划标准形式：求使且满足2021/9/239（1）线性规划实例5.2 标准形式与基本性质例5-3：某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产

6、才能获得最大利润？日利润最大生产能力限制劳动力限制变量非负解:设甲、乙两种产品的日产件数分别为s.t.2021/9/2310（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元/件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的

7、生产计划线性规划模型。工序1工序2工序3原材料1 原材料2其他成本产品A/件2323410产品B/件1132310产品C/件2124210总工时或原材料460040006000100008000工时或原材料成本（元）15101020402021/9/2311（1）线性规划实例5.2 标准形式与基本性质例5-5：成批生产企业年度生产计划的按月分配。在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。在年度计划按月分配时一般要考虑:1

8、）从数量和品种上保证年度计划的完成；2）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；3）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；4）根据合同要求，某些产品要求在年初交货；5）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。2021/9/2312（2）线性规划的标准形式5.2 标准形式与基本性质2021/9/2313（2）线性规划的标准形式5.2 标准形式与基本性质矩阵形式决策变量常数项系数矩阵价值系数其中：2021/9/2314（2）线性规划的标准形式5.2 标准形式与基本性质矩

9、阵形式的另一种表示max(min)zCTX s.t.AX(,)b X02021/9/2315（2）线性规划的标准形式5.2 标准形式与基本性质线性规划的向量形式设则得LP的向量形式：2021/9/2316（2）线性规划的标准形式5.2 标准形式与基本性质线性规划数学模型的一般形式：求使且满足说明：1）m=n,唯一解2）mn,无解3）mm)为转轴元素，此时xt进入基，xs出基。这样就完成了从一个基本解到另一个基本解的转换5.3 基本可行解的转换2021/9/2339（1）基本解到基本解的转换5.3 基本可行解的转换解：用a11,a22作为轴元素进行两次转轴运算：例：给定如下方程组，试进行基本解的

10、转换运算。得到一组基本解：x1=-12 x2=-20 x3=x4=x5=02021/9/2340（1）基本解到基本解的转换5.3 基本可行解的转换用a25作为轴元素进行第三次转轴运算：又得到一组基本可行解：x1=3 x5=5 x2=x3=x4=0此时x5进入基，x2出基。2021/9/2341当已经得到一组基本可行解，若要求把xk选进基本变量，并使下一组基本解是可行解的话，则在第k列要选取不为任何负值的元素作为转轴元素。5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/23alk作为转轴元素进行转轴运算：5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/

11、9/235.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/23方程组第一行发生的变化：5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/23alk作为轴元素，xk选进基本变量后，xk的取值由零变成了一个正值 ，则原来各基本变量的取值变为:若是基本可行解,应该保证各差值最小者为零:决定了非基变量为xi5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/23若想用xk取代xl成为可行解中的基本变量，就应该选 所对应的行成为转轴行，即所选取的行要满足条件:规则规则5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/2

12、3例：例：基本可行解：x1=3 x5=5 x2=x3=x4=0基本变量x1、x5 基本可行解的转换：1）x2、x4系数全部为负，只能选取x3所在的第3列为转轴行 2）,由于 ，则取第一行为转轴行,于是取a13=2为转轴元素，使x3取代x1成为基本变量。5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/23经转轴运算得：得基本可行解：5.3 基本可行解的转换（2）基本可行解到基本可行解的转换2021/9/23结论：可把松驰变量作为初始基本可行解中的一部分基本变量。原始约束条件:引入松驰变量:可得一组基本可行解：5.3 基本可行解的转换（3）初始基本可行解的求法2021/9/

13、235.3 单纯形方法及应用举例要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过 个），但当m和n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。单纯形法的基本思路是：从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。按照单纯形法的思路求解线性规划问题,要解决三个技术问题：（1）给出第一个基本可行解；（2）转换到另一个基本可行解；（3）检验一个基本可行解是否是最优解。2021/9/23515.3 单纯形方法及应用举例把线性规划问题

14、变成标准形，观察是否每个约束方程中都有独有的、系数为1的变量。p如果是，则取这些变量作为基变量，便得到一个基本可行解；p否则，就给没有这种变量的约束条件添加一个人工变量，同时修改目标函数。（1）确定初始基可行解2021/9/23525.3 单纯形方法及应用举例（1）确定初始基可行解标准形变化2021/9/23535.3 单纯形方法及应用举例（1）确定初始基可行解首先有假定的系数矩阵A中包含一个m阶单位矩阵，即有m个单位列向量，那么这m个单位列向量所对应的基本可行解是一个基本可行解。设A的前m列为单位向量，即：（1）2021/9/23545.3 单纯形方法及应用举例（1）确定初始基可行解显然，是

15、（L,P）的一个基本可行解，其中，。我们就从这个初始基本可行解，开始单纯形法的迭代（搜索）的第一步。从（1）式中求解出：即（2）取非基变量等于零，得到初始基可行解2021/9/23555.3 单纯形方法及应用举例（2）基可行解转换基可行解转换是从一个基可行解转换为相邻的基可行解（即从一个顶点转到另一个顶点）。p定义：两个基可行解是相邻的，如果它们之间变换且仅变换一个基变量。p规则：规则。2021/9/23565.3 单纯形方法及应用举例（2）基可行解转换 规则P1 P2 P3 Pm Pm+1 Pj Pn b2021/9/23575.3 单纯形方法及应用举例（3）最优性检验和解的判别将基可行解X

16、(0)和X(1)分别代入目标函数得：被称为检验数，通常简写为 或如果单纯形表最后一行中的 都满足 ，则对应的基本可行解是最优解；否则，就不是最优解。2021/9/23585.3 单纯形方法及应用举例用单纯形法求解线性规划问题的具体步骤如下：找出初始可行基，确定初始基本可行解，建立初始单纯形表；转。检验对应于非基变量的检验数 。若 （xj为非基变量）都成立，则当前单纯形表对应的基本解就是最优解，停止计算；否则转。在所有 中，若最大 对应的xk的系数aik0(i=1,2,m)，则此问题为无界解（无解），停止计算；否则转。2021/9/23595.3 单纯形方法及应用举例根据 确定xk为换入变量；根

17、据规则确定相应的换出变量。转。以aik为中心元素进行变换，并得到中心元素aik旋转运算得到新的单纯形表。转 单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是，则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。2021/9/23605.3 单纯形方法及应用举例单纯形表的格式：迭代次数XBCBx1x2xnb比值C1C2Cn0 x1C1a11a12a1nb11x2C2a21a22a2nb22.xmCmam1am2amnbmmZjZjZjZjj12n20

18、21/9/23615.3 单纯形方法及应用举例（4）单纯形应用举例例5-6：用图解法和单纯形法求如下线性规划问题的最优解。2021/9/23625.3 单纯形方法及应用举例（4）单纯形应用举例0123456712345(2.25,0)4x1+x2=91、图解法求解2021/9/23635.3 单纯形方法及应用举例（4）单纯形应用举例2、单纯形法求解迭代次数基变量CBx1x2x3x4b比值01310742019Zjj2021/9/23645.3 单纯形方法及应用举例（4）单纯形应用举例2、单纯形法求解迭代次数基变量CBx1x2x3x4b比值41000 x3013107x4042019Zj0000

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

20、0000j4100迭代次数基变量CBx1x2x3x4b比值41001x3002.51-0.254.75x1410.500.252.25Zj42019j0-10-12021/9/23675.3 单纯形方法及应用举例（4）单纯形应用举例例5-7：用单纯形法求如下线性规划问题的最优解。2021/9/23685.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 02021/9/23695.3 单纯形方法及应用举例（4）单纯形应用举例迭代

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

22、2021/9/23715.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。2021/9/2372例5-8：用单纯形法求如下线性规划问题的最优解。5.3 单纯形方法及应用举例（4）单纯形应用举例2021/9/2373迭代次数基变量CBx1x2x3x4x5b比值230001x301010-1/222x40400121

23、64x2301001/43-j2000-3/49迭代次数基变量CBx1x2x3x4x5b比值230000 x301210084x404001116-x5004001123j2300005.3 单纯形方法及应用举例（4）单纯形应用举例2021/9/2374迭代次数基变量CBx1x2x3x4x5b比值230001x121001/404x5000-21/214x23011/2-1/802j00-3/2-1/8014迭代次数基变量CBx1x2x3x4x5b比值230000 x121010-1/22-x4000-41284x2301001/4312j00-201/413此问题的最优解为:x1*=4,x2

24、*=2,x5*=4，x3*=x4*=x1*=0,z*=2 4+3 2=145.3 单纯形方法及应用举例（4）单纯形应用举例2021/9/23755.4 单纯形方法的特殊情况最终产生最优值的单纯形表中，某一非基本变量的检验数为0，意味着作任何增大，目标函数的最优值不变。此时线性规划问题的最优解并不唯一，有多重最优解。（见例题）（1）无穷最优解例5-9：用单纯形法求如下线性规划问题的最优解。2021/9/23765.4 单纯形方法的特殊情况解：另Z=-Z，将原线性规划问题变为MAX形式。（1）无穷最优解迭代次数基变量CBx1x2x3x4b比值-3-1-1-10 x3-1-221042x4-1310

25、166j-2200-82021/9/23775.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*=（1 3 0 0）所以：X*=X1*+（1-）X2*，其中0 0的非基变量中选取下标最小的进基；当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环，当然，这样也可能使收敛速度降低。

26、2021/9/23845.4 单纯形方法的特殊情况（4）总结1、在迭代过程中要保持常数列向量非负，这能保证基解的非负性。最小比值能做到这一点。2、主元素不能为0，因为行的初等变换不能把0变成1。3、主元素不能为负数，因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。4、每一步运算只能用矩阵初等行变换。2021/9/23855.5 单纯形方法进一步讨论所给LP的标准型中约束矩阵中没有现成的可行基怎么办？人工变量法针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。（1）人工变量法标准化规范化1规范化22021/9/2386（1）人工变量法但是，对于用单纯形法求解LP问题：首先，转化

27、成标准形式：5.5 单纯形方法进一步讨论2021/9/2387（1）人工变量法再强行加上人工变量，使其出现单位矩阵：5.5 单纯形方法进一步讨论2021/9/2388（1）人工变量法但是，这样处理后：p不易接受。因为是x6，x7强行引进，称为人工变量。与x4，x5不一样。x4，x5称为松弛变量和剩余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。p人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量，为此，下文介绍使用大M法。5.5 单纯形方法进一步

28、讨论2021/9/2389（2）大M法使用大M处理后：其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。5.5 单纯形方法进一步讨论2021/9/2390（2）大M法例5-11：用图解法和单纯形法求如下线性规划问题的最优解。5.5 单纯形方法进一步讨论2021/9/2391（2）大M法5012345671234(7,0)4x1+x2=28最优解是x1=7,x2=0，此时Max Z=281、图解法求解5.5 单纯形方法进一步讨论2021/9/2392（2）大M法2、单纯形法求解5.5 单纯形方法进一步讨论2021/9/2393（2）大M法2、单

29、纯形法求解迭代次数基变量CBx1x2x3x4x5b比值4100-M0 x301310077/1x5-M420-1199/4Zj-4M-2M0M-Mj4+4M1+2M0-M0基变量列中 x5 换为 x1；改CB列，-M 换为 4 M可以取10005.5 单纯形方法进一步讨论2021/9/2394作业用单纯形方法求解如下模型：用单纯形方法求解如下模型：Max Z=5=5x1 1+2+2x2 2+3+3x3 3-x4 4 x1 1+2+2x2 2+3+3x3 3=15 =15 2 2x1 1+x2 2+5+5x3 3=20 =20 x1 1+2+2x2 2+4+4x3 3 +x4 4 =26=26 x1 1,x2 2,x3 3,x4 4 0 02021/9/2395