《线性规划与LINGO编程课件》由会员分享，可在线阅读，更多相关《线性规划与LINGO编程课件（75页珍藏版）》请在金锄头文库上搜索。
1、内容说明,以下内容在数学建模与数学实验（第二版） （汪晓银 ，周保平主编）第3章,2.1 什么是数学规划 2.2 连续性线性规划 2.3 敏感性分析 2.4 整数线性规划 2.5 0-1规划,内容说明,数学规划俗称最优化,首先是一种理念,其次才是一种方法,它所追求的是一种“至善”之道,一种追求卓越的精神.,2.1 什么是数学规划,小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟，整理书包要6分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？,十个人各提一只水桶，同时到水龙头前打水。设水龙头注满第一个人的桶需要1分钟，注满第二个人的桶需要2分钟，依此类推，注满第几
2、个人的桶就需要几分钟，如果只有一只水龙头，适当安排这10个人的顺序，就可以使每个人所费的时间总和尽可能小，问这个总费时至少是几分钟？,2.1 什么是数学规划,数学规划(最优化)作为一门学科孕育于20世纪的30年代,诞生于第二次世界大战弥漫的硝烟中。 数学规划指在一系列客观或主观限制条件下，寻求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法，是运筹学里一个十分重要的分支。,2.1 什么是数学规划,最优化问题的数学模型的一般形式为：,（1）,（2）,三个要素：决策变量decision bariable，目标函数objective function，约束条件constra
3、ints。,2.1 什么是数学规划,约束条件（2）所确定的x的范围称为可行域feasible region，满足（2）的解x称为可行解feasible solution，同时满足（1）（2）的解x称为最优解Optimal solution，整个可行域上的最优解称为全局最优解global optimal solution，可行域中某个领域上的最优解称为局部最优解local optimal solution。最优解所对应的目标函数值称为最优值optimum。,2.1 什么是数学规划,（一）按有无约束条件（2）可分为： 1.无约束优化unconstrained optimization。 2.约束优
4、化constrained optimization。 大部分实际问题都是约束优化问题。,优化模型的分类,2.1 什么是数学规划,（二）按决策变量取值是否连续可分为： 1.数学规划或连续优化。 可继续划分为线性规划(LP)Linear programming和非线性规划(NLP) Nonlinear programming。在非线性规划中有一种规划叫做二次规划(QP)Quadratic programming，目标为二次函数，约束为线性函数。 2.离散优化或组合优化。 包含：整数规划(IP)Integer programming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-on
5、e programming，这类规划问题的决策变量只取0或者1。,2.1 什么是数学规划,（三）按目标的多少可分为： 1.单目标规划。 2.多目标规划。 （四）按模型中参数和变量是否具有不确定性可分为： 1.确定性规划。 2.不确定性规划。 （五）按问题求解的特性可分为： 1.目标规划。 2.动态规划。 3.多层规划。 4.网络优化。 5.等等。,2.1 什么是数学规划,LINGO软件和MATLAB软件。 对于LINGO软件，线性优化求解程序通常使用单纯形法simplex method，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点
6、算法interior point method备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序分解原问题成一系列的凸规划。,求解优化问题常用的软件,2.1 什么是数学规划,线性规划的一般形式：,2.2 连续性线性规划,一般线性规划问题都可以通过引入非负的松弛变量slack variable与非负的剩余变量surplus v-ariable的方法化为标准形式（约束全是等约束）。,线性规划问题的可行
7、域feasible region是一个凸集convex set（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解Optimal solution/point在凸多面体的某个顶点上达到,求解方法：单纯形算法simplex method。,2.2 连续性线性规划,1.比例性：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。 2.可加性：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。 3.连续性：每个决策变量的取值都是连续的。,连续线性规划问题的性质,要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干
8、约束条件,2.2 连续性线性规划,例1 运输问题,2.2 连续性线性规划,解 设A1,A2调运到三个粮站的大米分别为x1， x2， x3， x4， x5， x6吨。,题设量可总到下表：,2.2 连续性线性规划,结合存量限制和需量限制得数学模型：,2.2 连续性线性规划,程序编写1 model: min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6 ; x1+x2+x32 ; x2+x54 ; x3+x65 ; end,提示：课件中的程序请先粘贴在记事本中再 转帖于lingo软件中,2.2 连续性线性规划,运行结果 Global optimal solution foun
9、d. 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 Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.0000
10、00 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.00000,2.2 连续性线性规划,变量更换为：,2.2 连续性线性规划,模型:,2.2 连续性线性规划,程序编写 MODEL: TITLE 调运大米的运输问题程序3; !定义集合段; SETS: LIANGKU/1.2/:A;!定义粮库的集合; LIANGZHAN/1.3/:B;!定义粮站的集合; YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离; ENDSETS DATA: !粮库到粮站的距离; C= 12 24 8 30 12 24;,2.
11、2 连续性线性规划,!粮库的限量; A=4 8 ; !粮站的限量; B=2 4 5; ENDDATA OBJMIN=SUM(YULIANG:C*X); !粮库上限的约束; FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J); END,2.2 连续性线性规划,程序的调试 1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改； 2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围； 3.可以边写程序边运行，保证每行书写都是正确的程序；,2.2 连续性线性规划,例2 阶段生产问题,某公司生产某产品,最大生产能力为10000单位,
12、每单位存储费2元,预定的销售量与单位成本如下:,求一生产计划,使 1)满足需求; 2)不超过生产能力; 3)成本(生产成本与存储费之和)最低.,2.2 连续性线性规划,解 假定1月初无库存,4月底买完,当月生产的不库 存,库存量无限制.,2.2 连续性线性规划,model: title 生产计划程序1; Sets: yuefen/1.4/:c,x,e,d; endsets data: c=70 71 80 76; d=6000 7000 12000 6000; e=2 2 2 2 ; a=10000; enddata min=sum(yuefen:c*x)+ sum(yuefen(j)|j#l
13、t#4: sum(yuefen(i)|i#le#j:x-d)*e(j+1); for(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x) sum(yuefen(i)|i#le#j:d); sum(yuefen:x)= sum(yuefen:d); for(yuefen:xa); end,2.2 连续性线性规划,2.2 连续性线性规划,Model: Title 生产计划程序2; Sets: yuefen/1.4/:c,x,e,d,s; endsets data: c=70 71 80 76; d=6000 7000 12000 6000; e=2 2 2 2 ;
14、a=10000; enddata min=sum(yuefen:c*x+e*s); for(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i); s(4)+x(4)-d(4)=0; s(1)=0; for(yuefen:xa); End,2.2 连续性线性规划,2.2 连续性线性规划,2.2 连续性线性规划,建立模型如下：,2.2 连续性线性规划,model: title 生产计划程序3; sets: yuefen/1.4/:a,d,xx; !定义上三角矩阵; link(yuefen,yuefen)| End,2.2 连续性线性规划,Model Title: :生产计
15、划程序1 Variable Value Reduced Cost A 10000.00 0.000000 C( 1) 70.00000 0.000000 C( 2) 71.00000 0.000000 C( 3) 80.00000 0.000000 C( 4) 76.00000 0.000000 X( 1) 10000.00 0.000000 X( 2) 10000.00 0.000000 X( 3) 5000.000 0.000000 X( 4) 6000.000 0.000000 E( 1) 2.000000 0.000000 E( 2) 2.000000 0.000000 E( 3) 2.000000 0.000000 E( 4) 2.000000 0.000000 D( 1) 6000.000 0.000000 D( 2) 7000.000 0.000000 D( 3) 12000.00 0.000000 D( 4) 6000.000 0.000000,2.2 连续性线性规划,设有两个工厂A、B，产量都是10万个，工厂有三个仓库x，y，z，产品都先送到仓库。现有
