机械优化设计第五章(哈工大—孙靖民)

1、Page 2* 目标函数和约束条件都是线性的，像这类约束目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解的，但是也有采用线性逼近方法求解非线性问题的。非线性问题的。此外，线性规划方法还常被用作解决非线性问题的此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求子问题的工具

2、，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。化问题，线性规划方法就更有用了。Page 3*0024261553. .2max21212121xxxxxxt sxxz解：设生产解：设生产A、B两产品分别两产品分别为为x1, x2台，则该问题的优化台，则该问题的优化数学模型为：数学模型为：例例5-1： 某工厂要生产某工厂要生产A、B两种产品，两种产品，每生产一台产品每生产一台产品A 可获产值可获产值2万元；万元；需占用一车间工作日需占用一车间工作日3天，二车间工天，二车间工作日作日6天；每生

3、产一台产品天；每生产一台产品B 可获产可获产值值1万元；需占用一车间工作日万元；需占用一车间工作日5天，天，二车间工作日二车间工作日2天。现一车间可用于天。现一车间可用于生产生产A、B产品的时间产品的时间15天，二车间天，二车间可用于生产可用于生产A、B产品的时间产品的时间24天。天。试求出生产组织者安排试求出生产组织者安排A、B两种产两种产品的合理投资产数，以获得最大的总品的合理投资产数，以获得最大的总产值。产值。Page 4*例例5-2：生产甲种产品每件需使用材料生产甲种产品每件需使用材料9kg9kg、3 3个工时、个工时、4kw4kw电，获电，获利润利润6060元。生产乙种产品每件需用材

4、料元。生产乙种产品每件需用材料4kg4kg、1010个工时、个工时、5kw5kw电，电，可获利可获利120120元。若每天能供应材料元。若每天能供应材料360kg360kg，有，有300300个工时，能供个工时，能供200kw200kw电。试确定两种产品每天的产量，使每天可能获得的电。试确定两种产品每天的产量，使每天可能获得的利润利润最大最大？ 12,x x1212(,)60120maxf x xxx112()94360gXxx分析：分析：每天生产的每天生产的分别为分别为 件件 （工时约束）（工时约束）（电力约束）（电力约束）（材料约束）（材料约束）( (利润最大利润最大) )212()310

5、300gXxx312()45200gXxxPage 5*例5-3：某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？日利润最大日利润最大生产能力限制生产能力限制劳动力限制劳动力限制变量非负变量非负12121212max()4080972324,0F Xxxxxxxx xs.t.Page 6*线性规划数学模型的一般形式：线性规划数学模型的一般形式：11 11221121 1222221

6、122nnnnmmmnnma xa xa xba xa xa xba xaxaxb求求T12nxx xx1122( )m innnfxc xc xc x使使且满足且满足0(1,2, )ixin 0(1,2,)jbjm 说明：说明：1 1）m=n,m=n,唯一解唯一解2 2）mn,mn,无解无解3 3）mn,mm)为转轴元素，此时为转轴元素，此时xt进入进入基，基， xs出基。这样就完成了从一个基本解到另一个基本出基。这样就完成了从一个基本解到另一个基本解的转换解的转换staPage 26*1234512345541322058xxxxxxxxxx解：用解：用a11, a22作为轴元素进行两次转

7、轴运算：作为轴元素进行两次转轴运算：例：给定如下方程组，试进行基本解的转换运算。例：给定如下方程组，试进行基本解的转换运算。134523450723120123420 xxxxxxxx 得到一组得到一组基本解：基本解： x1=-12 x2=-20 x3=x4=x5=0Page 27*用用a25作为轴元素进行第三次转轴运算：作为轴元素进行第三次转轴运算：1234234531203441303544xxxxxxxx又得到一组又得到一组基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0此时此时x5进入基，进入基， x2出基。出基。Page 28*二、基本可行解到基本可行解的转换二、基

8、本可行解到基本可行解的转换121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx111211001lnmnlmmlkknlmmmmmkknmaxa xa xbxxxaxaxa xb当已经得到一组基本可行解，若要求把当已经得到一组基本可行解，若要求把xk选进基本变量，选进基本变量，并使下一组基本解是可行解的话并使下一组基本解是可行解的话Page 29*alk作为转轴元素进行转轴运算：作为转轴元素进行转轴运算：121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa x

9、bxxxaxa xa xbxxx1112110101lnmnlmlmnlklklkmmmmmkkknmaabxxaaaxxxaxaxa xxbPage 30*1121111111211000100nlnmmmkknlmlmmnlklklkkxxxaxa xa xbaabxxxxaaaxx1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa xPage 31*方程组第一行发生的变化：方程组第一行发生的变化：1121111111211111100000nlnmmmkknlmlmkmknklklkklk

10、kxxxaxa xa xbaabxxxaxaxaaaaa x1112111111121111111100()0()000lnnlnlmmmkmkknlklklmlmkmkkknklkllklklkkbbaaaaxxxaaxxaaxaaaabxxxaxa xaxaaaaPage 32*若想用若想用xk取代取代xl成为可行解中的基本变量，成为可行解中的基本变量，即所选取的行即所选取的行要满足条件要满足条件: :0lka min ()lkllkbxa规则规则Page 33*例：例：1234234531203441303544xxxxxxxx基本可行解：基本可行解： x1=3 x5=5 x2=x3=x

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

12、量。可把松驰变量作为初始基本可行解中的基本变量。12312352100,1,2,3ixxxxxxxi 123412350520100,1,2,3,4,5ixxxxxxxxxi 451235,10,0 xxxxx三、初始基本可行解的求法三、初始基本可行解的求法原始约束条件原始约束条件:引入松驰变量引入松驰变量:可得一组基本可行解：可得一组基本可行解：Page 36*一、单纯形法的基本思想一、单纯形法的基本思想从一个初始基本可行解从一个初始基本可行解X X0 0出发，寻找目标函数有较出发，寻找目标函数有较大下降的一个新的基本可行解大下降的一个新的基本可行解X X1 1, ,代替原来的基本可行代替原

13、来的基本可行解解X X0 0，如此完成一次迭代。随后作出判断，如果未达到，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。所以经过有限次迭代一定能达到最优解。采用单纯形法求解线性规划问题，主要应解决以下三个问题：采用单纯形法求解线性规划问题，主要应解决以下三个问题：（1）如何确定初始基本可行解；）如何确定初始基本可行解；（2）如何由一个基本可行解迭代出另一个基本可行解，）如何由一个基本可行解迭代出另一个基本可行解，同同时保证目标函数的下降性时保证目标函数的下降性；（

14、3）如何判断一个基本可行解是否为最优解。）如何判断一个基本可行解是否为最优解。Page 37*二二. .最优解规则最优解规则 对应一组基本可行解：对应一组基本可行解： 前前m个变量组成基本可行解的基本变量个变量组成基本可行解的基本变量相应的目标函数值为相应的目标函数值为: :1 122( )00mmf xc bc bc b12 ,0,0TmXb bb1mlllcbPage 38*经过转轴运算得到另经过转轴运算得到另一组基本可行解为一组基本可行解为:111222kkssskmmmkkxbaxbaxXbaxbax其中：其中：0 ()ssskxbasm 进基变量进基变量xk出基变量出基变量xsPag

15、e 39*对应的目标函数为对应的目标函数为: :111222( )()()()()00kkssskmmmkkf xc bac bac bacbac11mmllllkkllcbc ac1( )mkllklf xcc a( )kf xrPage 40*由于要求由于要求( )( )( )kf xf xrf x0kr结论结论: :一旦所有的一旦所有的 , ,即可停止即可停止 转轴运算转轴运算, ,对应的可行解就是对应的可行解就是最优解。最优解。r是是 对线性规划问题的解进行最优性检验的标对线性规划问题的解进行最优性检验的标 志，称之为检验数。志，称之为检验数。10mkkllklrcc a010mkkllklrcc aPage 41*1minmkllkklcc a具体计算时应选取具体计算时应选