《机械优化设计线性规划培训课件.pptx》由会员分享,可在线阅读,更多相关《机械优化设计线性规划培训课件.pptx(95页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、机械优化设计2017年6月上上 海海 海海 事事 大大 学学SHANGHAI MARITIME UNIVERSITYSHANGHAI MARITIME UNIVERSITY何军良何军良第一页,共95页。上海海事大学上海海事大学Shanghai Maritime University 1909 2009 2004 1912 1958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目 录CONTENTS一维搜索方法无约束优化方法线性规划 约束优化方法 第二页,共95页。第四章 无约束优化方法(fngf)线性规划的标准形式与基本(jbn)性质02 基本可行(kxng)解的转换 单纯形方法 单
2、纯形方法应用举例030405 修正单纯形法06 概述01第三页,共95页。4(1)定义(dngy)5.1 概述(i sh)目标函数和约束条件都是线性的,像这类约束函数和目标函数都是为线性函数的优化问题,称作线性规划问题。它的解法在理论和方法上都很成熟,实际应用也很广泛。虽然(surn)大多数工程设计是非线性的,但是也有采用线性逼近方法求解非线性问题的。此外,线性规划方法还常被用作解决非线性问题的子问题的工具,如在可行方向法中可行方向的寻求就是采用线性规划方法。当然,对于真正的线性优化问题,线性规划方法就更有用了。第四页,共95页。5(2)主要(zhyo)研究的问题5.1 概述(i sh)一类是
3、已有一定数量的资源(人力(rnl)、物质、时间等),研究如何充分合理地使用它们,才能使完成的任务量为最大。另一类是当一项任务确定以后,研究如何统筹安排,才能使完成任务所耗费的资源量为最少。实际上,上述两类问题是一个问题的两个不同的方面,都是求问题的最优解(max 或 min)。第五页,共95页。6(3)线性规划模型(mxng)建立5.1 概述(i sh)建模步骤(bzhu)1 确定决策变量:即需要我们作出决策或选择的量。一般情况下,题目问什么就设什么为决策变量。2 找出所有限定条件:即决策变量受到的所有的约束;3 写出目标函数:即问题所要达到的目标,并明确是max 还是 min。第六页,共95
4、页。7(1)线性规划(xin xn u hu)实例5.2 标准形式(xngsh)与基本性质解:设生产(shngchn)A、B两产品分别为x1,x2台,则该问题的优化数学模型为:例5-1:某工厂要生产A、B两种产品,每生产一台产品A 可获产值2万元;需占用一车间工作日3天,二车间工作日6天;每生产一台产品B 可获产值1万元;需占用一车间工作日5天,二车间工作日2天。现一车间可用于生产A、B产品的时间15天,二车间可用于生产A、B产品的时间24天。试求出生产组织者安排A、B两种产品的合理投资产数,以获得最大的总产值。第七页,共95页。8(1)线性规划(xin xn u hu)实例5.2 标准(bi
5、ozhn)形式与基本性质例5-2:生产甲种产品每件需使用(shyng)材料9kg、3个工时、4kw电,获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电,可获利120元。若每天能供应材料360kg,有300个工时,能供200kw电。试确定两种产品每天的产量,使每天可能获得的利润最大?分析:每天生产的甲、乙两种产品甲、乙两种产品分别为 件 (工时约束)(电力约束)(材料约束)(利润最大)第八页,共95页。9(1)线性规划(xin xn u hu)实例5.2 标准形式与基本(jbn)性质将其化成(hu chn)线性规划标准形式:求使且满足第九页,共95页。10(1)线性规划(xin
6、 xn u hu)实例5.2 标准形式(xngsh)与基本性质例5-3:某厂生产(shngchn)甲、乙两种产品,已知:两种产品分别由两条生产(shngchn)线生产(shngchn)。第一条生产(shngchn)甲,每天最多生产(shngchn)9件,第二条生产(shngchn)乙,每天最多生产(shngchn)7件;该厂仅有工人24名,生产(shngchn)甲每件用2工日,生产(shngchn)乙每件用3工日;产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产(shngchn)才能获得最大利润?日利润最大生产能力限制劳动力限制变量非负解:设甲、乙两种产品的日产件数分别为s.t.第
7、十页,共95页。11(1)线性规划(xin xn u hu)实例5.2 标准形式与基本(jbn)性质例5-4:某工厂(gngchng)生产A、B、C三种产品,现根据订货合同以及生产状况制定5月份的生产计划,已知合同甲为:A产品1000件,单件价格为500元,违约金为100元/件;合同乙为:B产品500件,单件价格为400元,违约金为120元/件;合同丙为:B产品600件,单件价格为420元,违约金为130元/件;C产品600件,单件价格为400元,违约金为90元/件;有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标,建立该工厂(gngchng)的生产计划线性规划模型。工序1工序
8、2工序3原材料1 原材料2其他成本产品A/件2323410产品B/件1132310产品C/件2124210总工时或原材料460040006000100008000工时或原材料成本(元)1510102040第十一页,共95页。12(1)线性规划(xin xn u hu)实例5.2 标准形式(xngsh)与基本性质例5-5:成批生产企业年度生产计划的按月分配。在成批生产的机械制造企业中,不同产品劳动量的结构上可能(knng)有很大差别。如:某种产品要求较多的车床加工时间,另一种产品的劳动量可能(knng)集中在铣床和其他机床上。因此,企业在按月分配年度计划任务时,应考虑到各种设备的均衡且最大负荷。
9、在年度计划按月分配时一般要考虑:1)从数量和品种上保证年度计划的完成;2)成批的产品尽可能(knng)在各个月内均衡生产或集中在几个月内生产;3)由于生产技术准备等方面原因,某些产品要在某个月后才能投产;4)根据合同要求,某些产品要求在年初交货;5)批量小的产品尽可能(knng)集中在一个月或几个月内生产出来,以便减少各个月的品种数量等等。如何在满足上述条件的基础上,使设备均衡负荷且最大负荷。第十二页,共95页。13(2)线性规划(xin xn u hu)的标准形式5.2 标准形式(xngsh)与基本性质第十三页,共95页。14(2)线性规划(xin xn u hu)的标准形式5.2 标准形式
10、(xngsh)与基本性质矩阵(j zhn)形式决策变量常数项系数矩阵价值系数其中:第十四页,共95页。15(2)线性规划的标准(biozhn)形式5.2 标准(biozhn)形式与基本性质矩阵(j zhn)形式的另一种表示max(min)zCTX s.t.AX(,)b X0第十五页,共95页。16(2)线性规划(xin xn u hu)的标准形式5.2 标准形式与基本(jbn)性质线性规划(xin xn u hu)的向量形式设则得LP的向量形式:第十六页,共95页。17(2)线性规划(xin xn u hu)的标准形式5.2 标准(biozhn)形式与基本性质线性规划(xin xn u hu)
11、数学模型的一般形式:求使且满足说明:1)m=n,唯一解2)mn,无解3)mm)为转轴元素,此时xt进入基,xs出基。这样就完成了从一个基本解到另一个基本解的转换5.3 基本可行(kxng)解的转换第三十九页,共95页。40(1)基本(jbn)解到基本(jbn)解的转换5.3 基本可行(kxng)解的转换解:用a11,a22作为轴元素进行两次转轴(zhunzhu)运算:例:给定如下方程组,试进行基本解的转换运算。得到一组基本解:x1=-12 x2=-20 x3=x4=x5=0第四十页,共95页。41(1)基本(jbn)解到基本(jbn)解的转换5.3 基本(jbn)可行解的转换用a25作为轴元素
12、进行第三次转轴(zhunzhu)运算:又得到一组基本可行解:x1=3 x5=5 x2=x3=x4=0此时x5进入基,x2出基。第四十一页,共95页。当已经得到一组基本可行解,若要求把xk选进基本变量,并使下一组基本解是可行解的话,则在第k列要选取不为任何(rnh)负值的元素作为转轴元素。5.3 基本(jbn)可行解的转换(2)基本可行(kxng)解到基本可行(kxng)解的转换第四十二页,共95页。alk作为转轴元素作为转轴元素(yun s)进行转轴运算:进行转轴运算:5.3 基本可行(kxng)解的转换(2)基本可行(kxng)解到基本可行(kxng)解的转换第四十三页,共95页。5.3 基
13、本(jbn)可行解的转换(2)基本(jbn)可行解到基本(jbn)可行解的转换第四十四页,共95页。方程组第一行发生(fshng)的变化:5.3 基本(jbn)可行解的转换(2)基本(jbn)可行解到基本(jbn)可行解的转换第四十五页,共95页。alk作为轴元素,xk选进基本变量后,xk的取值由零变成了一个(y)正值 ,则原来各基本变量的取值变为:若是基本(jbn)可行解,应该保证各差值最小者为零:决定(judng)了非基变量为xi5.3 基本可行解的转换(2)基本可行解到基本可行解的转换第四十六页,共95页。若想用xk取代(qdi)xl成为可行解中的基本变量,就应该选 所对应的行成为转轴行
14、,即所选取的行要满足条件:规则规则5.3 基本(jbn)可行解的转换(2)基本(jbn)可行解到基本(jbn)可行解的转换第四十七页,共95页。例:例:基本可行解:x1=3 x5=5 x2=x3=x4=0基本变量x1、x5 基本可行解的转换:1)x2、x4系数全部为负,只能选取x3所在的第3列为转轴行 2),由于 ,则取第一(dy)行为转轴行,于是取a13=2为转轴元素,使x3取代x1成为基本变量。5.3 基本(jbn)可行解的转换(2)基本(jbn)可行解到基本(jbn)可行解的转换第四十八页,共95页。经转轴(zhunzhu)运算得:得基本(jbn)可行解:5.3 基本(jbn)可行解的转
15、换(2)基本可行解到基本可行解的转换第四十九页,共95页。结论(jiln):可把松驰变量作为初始基本可行解中的一部分基本变量。原始(yunsh)约束条件:引入松驰(sn ch)变量:可得一组基本可行解:5.3 基本可行解的转换(3)初始基本可行解的求法第五十页,共95页。515.3 单纯形方法及应用(yngyng)举例要找到线性规划问题的最优解,只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个(不超过 个),但当m和n较大时,要用“穷举法”求出所有基本可行解也是行不通的。因此(ync),必须寻求一种更有效的方法。单纯形法的基本思路是:从线性规划问题的一个基本可行解开始,转换到另一个
16、使目标函数值增大的基本可行解。反复迭代,直到目标函数值达到最大时,就得到了最优解。按照单纯形法的思路求解线性规划问题,要解决三个技术问题:(1)给出第一个基本可行解;(2)转换到另一个基本可行解;(3)检验一个基本可行解是否是最优解。第五十一页,共95页。525.3 单纯形方法及应用(yngyng)举例把线性规划问题变成标准形,观察(gunch)是否每个约束方程中都有独有的、系数为1的变量。如果是,则取这些变量作为基变量,便得到一个基本可行解;否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数。(1)确定(qudng)初始基可行解第五十二页,共95页。535.3 单纯形方法及应
17、用(yngyng)举例(1)确定初始(ch sh)基可行解标准(biozhn)形变化第五十三页,共95页。545.3 单纯形方法及应用(yngyng)举例(1)确定(qudng)初始基可行解首先有假定的系数矩阵A中包含一个m阶单位矩阵,即有m个单位列向量,那么这m个单位列向量所对应(duyng)的基本可行解是一个基本可行解。设A的前m列为单位向量,即:(1)第五十四页,共95页。555.3 单纯形方法及应用(yngyng)举例(1)确定初始(ch sh)基可行解显然,是(L,P)的一个(y)基本可行解,其中,。我们就从这个初始基本可行解,开始单纯形法的迭代(搜索)的第一步。从(1)式中求解出:
18、即(2)取非基变量等于零,得到初始基可行解第五十五页,共95页。565.3 单纯形方法(fngf)及应用举例(2)基可行(kxng)解转换基可行解转换是从一个基可行解转换为相邻的基可行解(即从一个顶点转到另一个顶点)。定义:两个基可行解是相邻的,如果(rgu)它们之间变换且仅变换一个基变量。规则:规则。第五十六页,共95页。575.3 单纯形方法(fngf)及应用举例(2)基可行(kxng)解转换 规则(guz)P1 P2 P3 Pm Pm+1 Pj Pn b第五十七页,共95页。585.3 单纯形方法(fngf)及应用举例(3)最优性检验(jinyn)和解的判别将基可行解X(0)和X(1)分
19、别(fnbi)代入目标函数得:被称为检验数,通常简写为 或如果单纯形表最后一行中的 都满足 ,则对应的基本可行解是最优解;否则,就不是最优解。第五十八页,共95页。595.3 单纯形方法及应用(yngyng)举例用单纯形法求解线性规划问题的具体步骤如下:找出初始可行(kxng)基,确定初始基本可行(kxng)解,建立初始单纯形表;转。检验对应于非基变量的检验数 。若 (xj为非基变量)都成立,则当前单纯形表对应的基本解就是最优解,停止计算;否则转。在所有 中,若最大 对应的xk的系数aik0(i=1,2,m),则此问题为无界解(无解),停止计算;否则转。第五十九页,共95页。605.3 单纯形
20、方法(fngf)及应用举例根据(gnj)确定xk为换入变量;根据(gnj)规则确定相应的换出变量。转。以aik为中心元素进行变换,并得到中心元素aik旋转运算得到新的单纯形表。转 单纯形法的基本思路:从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解。直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划(xin xn u hu)问题无最优解为止。第六十页,共95页。615.3 单纯形方法(fngf)及应用举例单纯形表的格式(g shi):迭代次数XBCBx1x2xnb比值C1C2Cn0
21、x1C1a11a12a1nb11x2C2a21a22a2nb22.xmCmam1am2amnbmmZjZjZjZjj12n第六十一页,共95页。625.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例例5-6:用图解法和单纯形法求如下线性规划(xin xn u hu)问题的最优解。第六十二页,共95页。635.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例0123456712345(2.25,0)4x1+x2=91、图解法求解(qi ji)第六十三页,共95页。645.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例2、
22、单纯形法求解(qi ji)迭代次数基变量CBx1x2x3x4b比值01310742019Zjj第六十四页,共95页。655.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例2、单纯形法求解(qi ji)迭代次数基变量CBx1x2x3x4b比值41000 x3013107x4042019Zj00000j4100填目标函数系数、填基变量列、填CB列;计算Zj、计算检验数。第六十五页,共95页。665.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例2、单纯形法求解(qi ji)迭代次数基变量CBx1x2x3x4b比值41000 x30131077x4
23、0420199/4Zj00000j4100最优吗?查什么?不是!谁进基?检验数最大的x1进基,谁出基?x1的系数有正的吗?求比值?基变量列中 x4 换为 x1;改CB列,0 换为 4 第六十六页,共95页。675.3 单纯形方法及应用(yngyng)举例(4)单纯形应用(yngyng)举例2、单纯形法求解(qi ji)迭代次数基变量CBx1x2x3x4b比值41000 x30131077x40420199/4Zj00000j4100迭代次数基变量CBx1x2x3x4b比值41001x3002.51-0.254.75x1410.500.252.25Zj42019j0-10-1第六十七页,共95页
24、。685.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例例5-7:用单纯形法求如下(rxi)线性规划问题的最优解。第六十八页,共95页。695.3 单纯形方法及应用(yngyng)举例(4)单纯形应用(yngyng)举例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 0第六十九页,共95页。705.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例迭代次数基变量CBx1x2x3x4x5b比值50400000 x303510
25、0150150/5x400101020-x5085001300300/8Zj000000j5040000当前基本(jbn)可行解:(0,0,150,20,300),Z=0。第七十页,共95页。715.3 单纯形方法及应用(yngyng)举例(4)单纯形应用(yngyng)举例迭代次数基变量CBx1x2x3x4x5b比值50400001x30025/810-3/875/212x40010102020 x15015/8001/875/260Zj50125/40025/41875j035/400-25/4当前基本(jbn)可行解:(75/2,0,75/2,20,0),Z=1875。第七十一页,共95
26、页。725.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例迭代次数基变量CBx1x2x3x4x5b比值50400001x240018/250-3/2512x4000-8/2513/258x15010-5/2505/2530Zj504014/5026/51980j00-14/50-26/5当前(dngqin)解:(30,12,0,8,0),为最优,Z*=1980。第七十二页,共95页。73例5-8:用单纯形法求如下(rxi)线性规划问题的最优解。5.3 单纯形方法及应用(yngyng)举例(4)单纯形应用(yngyng)举例第七十三页,共95页。74迭代次数基变量CBx
27、1x2x3x4x5b比值230001x301010-1/222x4040012164x2301001/43-j2000-3/49迭代次数基变量CBx1x2x3x4x5b比值230000 x301210084x404001116-x5004001123j2300005.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例第七十四页,共95页。75迭代次数基变量CBx1x2x3x4x5b比值230001x121001/404x5000-21/214x23011/2-1/802j00-3/2-1/8014迭代次数基变量CBx1x2x3x4x5b比值230000 x121010-1
28、/22-x4000-41284x2301001/4312j00-201/413此问题(wnt)的最优解为:x1*=4,x2*=2,x5*=4,x3*=x4*=x1*=0,z*=2 4+3 2=145.3 单纯形方法(fngf)及应用举例(4)单纯形应用(yngyng)举例第七十五页,共95页。765.4 单纯形方法(fngf)的特殊情况最终产生最优值的单纯形表中,某一非基本变量的检验数为0,意味着作任何增大,目标(mbio)函数的最优值不变。此时线性规划问题的最优解并不唯一,有多重最优解。(见例题)(1)无穷(wqing)最优解例5-9:用单纯形法求如下线性规划问题的最优解。第七十六页,共95
29、页。775.4 单纯形方法的特殊(tsh)情况解:另Z=-Z,将原线性规划问题(wnt)变为MAX形式。(1)无穷(wqing)最优解迭代次数基变量CBx1x2x3x4b比值-3-1-1-10 x3-1-221042x4-1310166j-2200-8第七十七页,共95页。785.4 单纯形方法(fngf)的特殊情况(1)无穷(wqing)最优解迭代次数基变量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-
30、6最优解为:X1*=(0 2 0 4)X2*=(1 3 0 0)所以(suy):X*=X1*+(1-)X2*,其中0 0的非基变量中选取下标最小的进基;当有多个变量同时可作为出基变量时,选择下标最小的那个变量出基。这样就可以避免出现循环,当然,这样也可能使收敛速度降低。第八十四页,共95页。855.4 单纯形方法的特殊(tsh)情况(4)总结(zngji)1、在迭代过程中要保持常数列向量非负,这能保证基解的非负性。最小比值能做到这一点。2、主元素不能为0,因为行的初等变换不能把0变成1。3、主元素不能为负数,因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。4、每一步运算只能用矩阵
31、(j zhn)初等行变换。第八十五页,共95页。865.5 单纯形方法(fngf)进一步讨论所给LP的标准型中约束矩阵中没有现成的可行基怎么办?人工变量法针对(zhndu)标准形约束条件的系数矩阵中不含单位矩阵的处理方法。(1)人工(rngng)变量法标准化规范化1规范化2第八十六页,共95页。87(1)人工(rngng)变量法但是(dnsh),对于用单纯形法求解LP问题:首先(shuxin),转化成标准形式:5.5 单纯形方法进一步讨论第八十七页,共95页。88(1)人工(rngng)变量法再强行加上人工(rngng)变量,使其出现单位矩阵:5.5 单纯形方法(fngf)进一步讨论第八十八页
32、,共95页。89(1)人工(rngng)变量法但是,这样处理后:不易接受。因为是x6,x7强行引进,称为人工变量。与x4,x5不一样。x4,x5称为松弛变量和剩余变量,是为了将不等式改写为等式而引进的,而改写前后两个约束是等价(dngji)的。人工变量的引入一般来说是前后不等价(dngji)的。只有当最优解中,人工变量都取值零时(此时人工变量实质上就不存在了)才可认为它们是等价(dngji)的。处理办法:把人工变量从基变量中赶出来使其变为非基变量,为此,下文介绍使用大M法。5.5 单纯形方法(fngf)进一步讨论第八十九页,共95页。90(2)大M法使用(shyng)大M处理后:其中M为任意大
33、的实数,“-M”称为“罚因子”。用意:只要人工(rngng)变量取值大于零,目标函数就不可能实现最优。5.5 单纯形方法(fngf)进一步讨论第九十页,共95页。91(2)大M法例5-11:用图解法和单纯形法求如下(rxi)线性规划问题的最优解。5.5 单纯形方法(fngf)进一步讨论第九十一页,共95页。92(2)大M法5012345671234(7,0)4x1+x2=28最优解是x1=7,x2=0,此时Max Z=281、图解法求解(qi ji)5.5 单纯形方法(fngf)进一步讨论第九十二页,共95页。93(2)大M法2、单纯形法求解(qi ji)5.5 单纯形方法(fngf)进一步讨
34、论第九十三页,共95页。94(2)大M法2、单纯形法求解(qi ji)迭代次数基变量CBx1x2x3x4x5b比值4100-M0 x301310077/1x5-M420-1199/4Zj-4M-2M0M-Mj4+4M1+2M0-M0基变量(binling)列中 x5 换为 x1;改CB列,-M 换为 4 M可以(ky)取10005.5 单纯形方法进一步讨论第九十四页,共95页。95作业(zuy)用单纯形方法求解如下用单纯形方法求解如下(rxi)(rxi)模型:模型:Max Z=5x1+2x2+3x3-x4 Max Z=5x1+2x2+3x3-x4 x1+2x2+3x3=15 x1+2x2+3x3=15 2x1+x2+5x3=20 2x1+x2+5x3=20 x1+2x2+4x3 +x4 =26 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4 0 x1,x2,x3,x4 0第九十五页,共95页。