《线性规划与编程演示文稿》由会员分享，可在线阅读，更多相关《线性规划与编程演示文稿（74页珍藏版）》请在金锄头文库上搜索。
1、线性规划与编程演示文稿线性规划与编程演示文稿第一页，共七十四页。（优选）线性规划与编程（优选）线性规划与编程第二页，共七十四页。2.1什么是数学规划什么是数学规划2.2连续性线性规划连续性线性规划2.3敏感性分析敏感性分析2.4整数线性规划整数线性规划2.50-1规划规划内容说明内容说明第三页，共七十四页。 数学规划数学规划俗称最优化俗称最优化, ,首先是一种理念首先是一种理念, ,其其次才是一种方法次才是一种方法, ,它所追求的是一种它所追求的是一种“至善至善”之道之道, ,一种追求卓越的精神一种追求卓越的精神. .2.1什么是数学规划什么是数学规划 小明同学，烧一壶水要小明同学，烧一壶水要
2、8分钟，灌开水要分钟，灌开水要1分钟，取牛奶和报纸要分钟，取牛奶和报纸要5分钟，整理书包要分钟，整理书包要6分钟，分钟，为了尽快做完这些事，怎样安排才能使时间最少为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？最少需要几分钟？ 第四页，共七十四页。 十个人各提一只水桶，同时到水龙头前打十个人各提一只水桶，同时到水龙头前打水。设水龙头注满第一个人的桶需要水。设水龙头注满第一个人的桶需要1分钟，分钟，注满第二个人的桶需要注满第二个人的桶需要2分钟，依此类推，注分钟，依此类推，注满第几个人的桶就需要几分钟，如果只有一满第几个人的桶就需要几分钟，如果只有一只水龙头，适当安排这只水龙头，适当
3、安排这10个人的顺序，就可个人的顺序，就可以使每个人所费的时间总和尽可能小，问这个以使每个人所费的时间总和尽可能小，问这个总费时至少是几分钟？总费时至少是几分钟？ 2.1什么是数学规划什么是数学规划第五页，共七十四页。 数学规划数学规划(最优化最优化)作为一门学科孕育于作为一门学科孕育于20世纪的世纪的30年代年代,诞生于第二次世界大战弥漫的硝烟中。诞生于第二次世界大战弥漫的硝烟中。 数学规划指在一系列客观或主观限制条件下，数学规划指在一系列客观或主观限制条件下，寻求合理分配有限资源使所关注的某个或多个指标寻求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法达到最大（
4、或最小）的数学理论和方法，是运筹学，是运筹学里一个十分重要的分支。里一个十分重要的分支。 2.1什么是数学规划什么是数学规划第六页，共七十四页。最优化问题的最优化问题的数学模型的一般形式数学模型的一般形式为：为： （1）（2）三个要素：三个要素：决策变量决策变量decisionbariable，目标函数目标函数objectivefunction，约束条件约束条件constraints。2.1什么是数学规划什么是数学规划第七页，共七十四页。约束条件（约束条件（2）所确定的）所确定的x的范围称为的范围称为可行域可行域feasibleregion，满足（，满足（2）的解）的解x称为称为可行解可行解f
5、easiblesolution，同时满足（，同时满足（1）（）（2）的解）的解x称为称为最优解最优解Optimalsolution，整个可行域上的最优解称为，整个可行域上的最优解称为全局最优解全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为，可行域中某个领域上的最优解称为局部局部最优解最优解localoptimalsolution。最优解所对应的目标函数。最优解所对应的目标函数值称为值称为最优值最优值optimum。2.1什么是数学规划什么是数学规划第八页，共七十四页。（一）（一）按有无约束条件按有无约束条件（2）可分为：）可分为：1.无约束优化无约束优化u
6、nconstrainedoptimization。2.约束优化约束优化constrainedoptimization。大部分实际问题都是约束优化问题。大部分实际问题都是约束优化问题。优化模型的分类优化模型的分类2.1什么是数学规划什么是数学规划第九页，共七十四页。（二）（二）按决策变量取值是否连续按决策变量取值是否连续可分为：可分为：1.数学规划或连续优化。数学规划或连续优化。可继续划分为可继续划分为线性规划线性规划(LP)Linearprogramming和和非线性规划非线性规划(NLP)Nonlinearprogramming。在非线性规。在非线性规划中有一种规划叫做划中有一种规划叫做二次
7、规划二次规划(QP)Quadraticprogramming，目标为二次函数，约束为线性函数。，目标为二次函数，约束为线性函数。2.离散优化或组合优化。离散优化或组合优化。包含：包含：整数规划整数规划(IP)Integerprogramming，整数规，整数规划中又包含很重要的一类规划：划中又包含很重要的一类规划：0-1（整数）规划（整数）规划Zero-oneprogramming，这类规划问题的决策变量只取，这类规划问题的决策变量只取0或者或者1。2.1什么是数学规划什么是数学规划第十页，共七十四页。（三）（三）按目标的多少按目标的多少可分为：可分为：1.单目标规划。单目标规划。2.多目标规
8、划。多目标规划。（四）（四）按模型中参数和变量是否具有不确定性按模型中参数和变量是否具有不确定性可分为：可分为：1.确定性规划。确定性规划。2.不确定性规划。不确定性规划。（五）（五）按问题求解的特性按问题求解的特性可分为：可分为：1.目标规划。目标规划。2.动态规划。动态规划。3.多层规划。多层规划。4.网络优化。网络优化。5.等等。等等。2.1什么是数学规划什么是数学规划第十一页，共七十四页。LINGO软件和软件和MATLAB软件。软件。对于对于LINGO软件，线性优化求解程序通常使用软件，线性优化求解程序通常使用单纯形法单纯形法simplexmethod，单纯形法虽然在实际应用中是最好最
9、，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了能解大规模问题，也提供了内点算法内点算法interiorpointmethod备选（备选（LINGO中一般称为障碍法，即中一般称为障碍法，即barrier），非线性优），非线性优化求解程序采用的是化求解程序采用的是顺序线性规划法顺序线性规划法，也可用，也可用顺序二次规顺序二次规划法划法，广义既约梯度法，另外可以使用多初始点（，广义既约梯度法，另外可以使用多初始点（LINGO中称中称multistart）找多个局部最优解增加找全局最优解的可）找
10、多个局部最优解增加找全局最优解的可能，还具有全局求解程序能，还具有全局求解程序分解原问题成一系列的分解原问题成一系列的凸规划凸规划。求解优化问题常用的软件求解优化问题常用的软件2.1什么是数学规划什么是数学规划第十二页，共七十四页。线性规划的一般形式：线性规划的一般形式： 2.2连续性线性规划连续性线性规划第十三页，共七十四页。一般线性规划问题都可以通过引入非负的松弛变量一般线性规划问题都可以通过引入非负的松弛变量slackvariable与非负的剩余变量与非负的剩余变量surplusv-ariable的方法的方法化为化为标准形式标准形式（约束全是等约束）。（约束全是等约束）。线性规划问题的可
11、行域线性规划问题的可行域feasibleregion是一个凸集是一个凸集convexset（任意两点的连线上的点都在区域内部，可以看（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解作是没有凹坑的凸多面体），所以最优解Optimalsolution/point在凸多面体的某个顶点上达到在凸多面体的某个顶点上达到求解方法：单纯形算法求解方法：单纯形算法simplexmethod。2.2连续性线性规划连续性线性规划第十四页，共七十四页。1.比例性比例性：每个决策变量对目标函数以及右端项的贡：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。献与该决策变量的
12、取值成正比。2.可加性可加性：每个决策变量对目标函数以及右端项的贡：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。献与其他决策变量的取值无关。3.连续性连续性：每个决策变量的取值都是连续的。：每个决策变量的取值都是连续的。 连续线性规划问题的性质连续线性规划问题的性质要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择有影响决策的若干约束条件有影响决策的若干约束条件2.2连续性线性规划连续性线性规划第十五页，共七十四页。例例1 运输问题运输问题2.2连续性线性规划连续性线性规划第十六页，共七十
13、四页。解解设设A1,A2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x1，x2，x3，x4，x5，x6吨。吨。题设量可总到下表：题设量可总到下表：2.2连续性线性规划连续性线性规划第十七页，共七十四页。结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：2.2连续性线性规划连续性线性规划第十八页，共七十四页。程序编写程序编写1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6;x1+x2+x34;x4+x5+x62;x2+x54;x3+x65;end提示：课件中的程提示：课件中的程序请先粘贴在记事序请先粘贴在记事本中再本中再转帖于转帖
14、于lingo软件中软件中2.2连续性线性规划连续性线性规划第十九页，共七十四页。运行结果运行结果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 0 Variable Value Reduced Cost X1 2.000000 0.000000 X2 0.000000 28.00000 X3 2.000000 0.000000 X4 0.000000 2.000000 X5 4.000000 0.000000 X6 3.000000 0.000000 Row Slack or
15、Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.000002.2连续性线性规划连续性线性规划第二十页，共七十四页。84库库存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1粮库粮库粮站粮站距离及运量距离及运量12122430824变量更换为：变量更换为：2.2连续性线性规划连续性线性规划第二十一页，共七十四页。模型模型:2.2连续性线性规划
16、连续性线性规划第二十二页，共七十四页。程序编写程序编写MODEL:TITLE 调运大米的运输问题程序调运大米的运输问题程序3;!定义集合段定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合定义粮库的集合;LIANGZHAN/1.3/:B;!定义粮站的集合定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离定义运量和距离;ENDSETSDATA:!粮库到粮站的距离粮库到粮站的距离;C= 12 24 8 30 12 24;2.2连续性线性规划连续性线性规划第二十三页，共七十四页。!粮库的限量粮库的限量;A=4 8 ;!粮站的限量粮站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!粮库上限的约束粮库上限的约束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 2.2连续性线性规划连续性线性规划第二十四页，共七十四页。程序的调试程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；
