系统原理与分析方法课件-8 Linear optimisation.pptx

Systemtheoryandanalysismethod

系统原理与分析方法秦华鹏HuapengQINAssociateProfessorPekingUniv.ShenzhenGraduateSchoolOffice:E414Telno:-Mail:qinhp@pkusz.edu.cnNov2015

第8讲线性优化算法

Algorithmsforlinearoptimization案例图解法单纯形法

案例：农药管理问题农药管理问题农田上施加的农药流失到湖泊中，危害到吃鱼的鸟类农户如何管理农田，才不会对鸟类造成危害？条件湖泊容积为105m3，湖水的平均停留时间为半年周围有农田103ha，种植两种作物湖水中的农药在食物链中被富集，农药浓度随着食物链呈几何级数增长。鸟类能忍受的最大农药浓度为100ppm(mg/L)

农药随食物链富集情况

系统和目标的确定系统的目标系统的边界约束条件系统要素与决策变量

建立变量间的数量关系决策变量：X1——蔬菜种植面积（ha）；X2——粮食种植面积（ha）净收益：Z=（300-160）X1+（150-50）X2种植蔬菜?入湖农药量=6*0.15*X1=0.9X1kg种植粮食?入湖农药量=2.5*0.20*X2=0.5X2kg湖水平均农药浓度C=（0.9X1+0.5X2）/（105/0.5）kg/m3=（0.9X1+0.5X2）/200ppm鹰体内的农药浓度=C4ppm

建立变量与目标、约束条件关系目标函数：Z=（300-160）X1+（150-50）X2约束条件：

农药管理的线性优化蔬菜单位面积的净收益粮食单位面积的净收益蔬菜单位面积的农药流失量粮食单位面积的农药流失量农药流失入湖限制量种植面积限制量

2图解法农药管理问题的图解法灵敏度分析线性优化问题解的特点

农药管理问题的图解法可行解可行域0100200300400500600700800020040060080010001200X2(ha)X1(ha)优化问题在可行域上有哪些信誉好的足球投注网站最佳点0.9x1+0.5x2=632.5x1+x2=100

目标函数等值线的特征目标函数等值线：针对目标函数，假设Z取定值（如C）时，X1和X2变化所构成的直线C取不同值对应的目标函数等值线相互平行0100200300400500600700800020040060080010001200X2(ha)X1(ha)CC2C1

有哪些信誉好的足球投注网站最优解可行域优化问题在可行域上，通过平行移动目标函数等值线，有哪些信誉好的足球投注网站最佳点

ACB可行域x1=332.25x2=668.75最优解为A点：X1=331.25haX2=668.75ha最大净收益：$113250最优解

图解法的步骤画由约束条件限制范围（可行域）穿过可行域，画目标函数Z=c的等值线确定等值线移动方向若minZ，减小c，观察等值线移动方向，以该方向作为搜寻最优解的方向；若maxZ，增加c，观察等值线移动方向，以该方向作为搜寻最优解的方向沿最优解搜寻方向平移等值线，找到等值线与可行域相接的最终边际点，该切点即为最优解。

2.2灵敏度分析模型中参数对最优解影响的灵敏程度，例如：蔬菜的净收益140?50$/ha时，目标函数值的变化？蔬菜的净收益140?220$/ha时，目标函数值的变化？

种植蔬菜净收益下降为50$/ha时可行域ACBx1=0x2=1000目标函数Z’=50X1+100X2最优解是为C点：X1=0ha，X2=1000ha最大净收益：$100000

种植蔬菜净收益上升为220$/ha时可行域ACBx1=702.78x2=0目标函数Z’=220X1+100X2最优解为B点：X1=702.78ha，X2=0ha最大净收益：$154610

农药管理问题的灵敏度分析最优解由目标函数和两个约束条件的相对斜率所确定：b1/b21.8，最优解Bb1/b21，最优解C1b1/b21.8，最优解Ab1/b2=1或1.8，目标线与CA或AB重合，有无数个有相同目标值的最优解可行域ACB农药流失入湖约束方程的斜率-1.8种植面积约束方程斜率-1

2.3线性优化解的特点解有可能出现的情况：有最优解无最优解唯一最优解无可行解：约束条件无共同区域无穷多最优解：目标函数等值线与最优解搜寻方向上某约束条件的边界线平行可行域无界：如最优解搜寻方向上可行域无界时，无最优解

优化解的几何解释线性优化问题可行解构成的可行域，一般是凸多边形若存在唯一最优解，则一定在可行域的某个顶点上