第2讲-线性规划与LINGO编程

华中农业大学数学建模创新实践基地系列课件第2讲线性规划与LINGO编程华中农业大学内容说明以下内容在《数学建模与数学实验（第二版）》（汪晓银，周保平主编）第3章2.1什么是数学规划2.2连续性线性规划2.3敏感性分析2.4整数线性规划2.50-1规划内容说明数学规划俗称最优化,首先是一种理念,其次才是一种方法,它所追求的是一种“至善”之道,一种追求卓越的精神.2.1什么是数学规划小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟，整理书包要6分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？十个人各提一只水桶，同时到水龙头前打水。设水龙头注满第一个人的桶需要1分钟，注满第二个人的桶需要2分钟，依此类推，注满第几个人的桶就需要几分钟，如果只有一只水龙头，适当安排这10个人的顺序，就可以使每个人所费的时间总和尽可能小，问这个总费时至少是几分钟？2.1什么是数学规划数学规划(最优化)作为一门学科孕育于20世纪的30年代,诞生于第二次世界大战弥漫的硝烟中。数学规划指在一系列客观或主观限制条件下，寻求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法，是运筹学里一个十分重要的分支。2.1什么是数学规划最优化问题的数学模型的一般形式为：xfzoptskjiRDxnkxtmjxglixhts,,1,0,,1,0,,1,0..（1）（2）三个要素：决策变量decisionbariable，目标函数objectivefunction，约束条件constraints。2.1什么是数学规划约束条件（2）所确定的x的范围称为可行域feasibleregion，满足（2）的解x称为可行解feasiblesolution，同时满足（1）（2）的解x称为最优解Optimalsolution，整个可行域上的最优解称为全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为局部最优解localoptimalsolution。最优解所对应的目标函数值称为最优值optimum。2.1什么是数学规划（一）按有无约束条件（2）可分为：1.无约束优化unconstrainedoptimization。2.约束优化constrainedoptimization。大部分实际问题都是约束优化问题。优化模型的分类2.1什么是数学规划（二）按决策变量取值是否连续可分为：1.数学规划或连续优化。可继续划分为线性规划(LP)Linearprogramming和非线性规划(NLP)Nonlinearprogramming。在非线性规划中有一种规划叫做二次规划(QP)Quadraticprogramming，目标为二次函数，约束为线性函数。2.离散优化或组合优化。包含：整数规划(IP)Integerprogramming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-oneprogramming，这类规划问题的决策变量只取0或者1。2.1什么是数学规划（三）按目标的多少可分为：1.单目标规划。2.多目标规划。（四）按模型中参数和变量是否具有不确定性可分为：1.确定性规划。2.不确定性规划。（五）按问题求解的特性可分为：1.目标规划。2.动态规划。3.多层规划。4.网络优化。5.……等等。2.1什么是数学规划LINGO软件和MATLAB软件。对于LINGO软件，线性优化求解程序通常使用单纯形法simplexmethod，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interiorpointmethod备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序—分解原问题成一系列的凸规划。求解优化问题常用的软件2.1什么是数学规划线性规划的一般形式：njjjxczz1)max(min或njxmibxatsjijij,,1,0,,1,)(n1j..或或2.2连续性线性规划一般线性规划问题都可以通过引入非负的松弛变量slackvariable与非负的剩余变量surplusv-ariable的方法化为标准形式（约束全是等约束）。线性规划问题的可行域feasibleregion是一个凸集convexset（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解Optimalsolution/point在凸多面体的某个顶点上达到求解方法：单纯形算法simplexmethod。2.2连续性线性规划1.比例性：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。2.可加性：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。3.连续性：每个决策变量的取值都是连续的。连续线性规划问题的性质要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2.2连续性线性规划241230A282412A1B3B2B1粮库粮站距离。问如何调运使运费最低如下公里单位距离两个粮库到三个粮站的吨大米分别为三个粮站至少需要吨吨为两个粮库现存大米分别调运大米向三个粮站有两个粮库,):(,5,4,2,8,4,,,,32121BBBAA例1运输问题2.2连续性线性规划解设A1,A2调运到三个粮站的大米分别为x1，x2，x3，x4，x5，x6吨。题设量可总到下表：84库存量x6x5x4A2542需要量x3x2x1A1B3B2B1粮库粮站距离及运量121224308242.2连续性线性规划结合存量限制和需量限制得数学模型：65432124123082412minxxxxxxf0,,,,,54284..654321635241654321xxxxxxxxxxxxxxxxxxts2.2连续性线性规划程序编写1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6;x1+x2+x34;x4+x5+x68;x1+x42;x2+x54;x3+x65;end提示：课件中的程序请先粘贴在记事本中再转帖于lingo软件中2.2连续性线性规划运行结果Globaloptimalsolutionfound.Objectivevalue:160.0000Totalsolveriterations:0VariableValueReducedCostX12.0000000.000000X20.00000028.00000X32.0000000.000000X40.0000002.000000X54.0000000.000000X63.0000000.000000RowSlackorSurplusDualPrice1160.0000-1.00000020.00000016.0000031.0000000.00000040.000000-28.0000050.000000-12.0000060.000000-24.000002.2连续性线性规划84库存量x23x22x21A2542需要量x13x12x11A1B3B2B112122430824变量更换为：2.2连续性线性规划23222113121124123082412xxxxxxfmin054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,,,,,..模型:2.2连续性线性规划程序编写MODEL:TITLE调运大米的运输问题程序3;!定义集合段;SETS:LIANGKU/1..2/:A;!定义粮库的集合;LIANGZHAN/1..3/:B;!定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离;ENDSETSDATA:!粮库到粮站的距离;C=12248301224;2.2连续性线性规划!粮库的限量;A=48;!粮站的限量;B=245;ENDDATA[OBJ]MIN=@SUM(YULIANG:C*X);!粮库上限的约束;@FOR(LIANGKU(I):[LK]@SUM(LIANGZHAN(J):X(I,J))A(I));!粮站下限的约束;@FOR(LIANGZHAN(J):[LZ]@SUM(LIANGKU(I):X(I,J))B(J));END2.2连续性线性规划程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；2.2连续性线性规划例2阶段生产问题某公司生产某产品,最大生产能力为10000单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元)销售量12347060007270008012000766000求一生产计划,使1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.2.2连续性线性规划1je解假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.为单位成本，为存储费，为销售量，月产量，为第：设模型iiiicedixjiijiidx1131j41jjjxcfmin4,23,11000003,2,1..414111ixdxjdxtsiiiiijijiii2.2连续性线性规划model:title生产计划程序1;Sets:yuefen/1..4/:c,x,e,d;endsetsdata:c=70718076;d=60007000120006000;e=2222;a=10000;enddatamin=@sum(yuefen:c*x)+@sum(yuefen(j)|j#lt#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);end2.2连续性线性规划.iiiiisicedix月初的库存量为为单位成本，设第为存储费，为销售量，月产量，为第：设模型4141miniiiiiisexcf..ts1is,iiidxs4,3,2,1i0051ss432104321100000，，，，，，，isixii2.2连续性线性规划Model:Title生产计划程序2;Sets:yuefen/1..4/:c,x,e,d,s;endsetsdata:c=70718076;d=60007000120006000;e=2222;a=10000;enddatamin=@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);End2.2连续性线性规划.,,:月的销售量示的第表存储费之和月卖出时的生产成本与生产的产品在第月表示第月卖出的数量月生产的产品在第表示第设化为运输问题模型jdjicjixjijij月份单位成本(元)销售量123470600072700080120007660002.2连续性线性规划76827676---80--7472-74727010000100001000010000产量600041200070006