线性规划与LINGO编程剖析

1、线性规划与LINGO编程剖析线性规划与LINGO编程(1)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，约

3、束条件constraints。 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 optimizatio

4、n。2.约束优化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，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interior poi

6、nt method备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序分解原问题成一系列的凸规划。求解优化问题常用的软件2.1 什么是数学规划线性规划的一般形式： 2.2 连续性线性规划 一般线性规划问题都可以通过引入非负的松弛变量slack variable与非负的剩余变量surplus v-ariable的方法化为标准形式（约束全是等约束）。 线性规划问题的可行域feasible region是

7、一个凸集convex set（任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解Optimal solution/point在凸多面体的某个顶点上达到 求解方法：单纯形算法simplex method。 2.2 连续性线性规划1.比例性：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。2.可加性：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。3.连续性：每个决策变量的取值都是连续的。 连续线性规划问题的性质 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件2.2 连续性线性规划例1 运输

8、问题2.2 连续性线性规划解 设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提示：课件中的程序请先粘贴在记事本中再转帖于lingo软件中2.2 连续性线性规划运行结果 Global optimal solution found. Total solver iterations: 0

9、 Variable Value Reduced Cost Row Slack or Surplus Dual Price2.2 连续性线性规划84库存量x23x22x21A2542需要量x13x12x11A1B3B2B1粮库粮站距离及运量12122430824变量更换为：2.2 连续性线性规划模型:2.2 连续性线性规划程序编写MODEL:TITLE 调运大米的运输问题程序3;!定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合;LIANGZHAN/1.3/:B;!定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离;ENDSETSD

10、ATA:!粮库到粮站的距离;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.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；2.2 连续性线性规划例2 阶段生产问题 某公司

11、生产某产品,最大生产能力为10000单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元) 销售量1234 70 6000 72 7000 80 12000 76 6000求一生产计划,使 1)满足需求; 2)不超过生产能力;3)成本(生产成本与存储费之和)最低.2.2 连续性线性规划 解 假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.2.2 连续性线性规划model:title 生产计划程序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 1202X 6000;e=2 2 2 2

12、;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);end 2.2 连续性线性规划2.2 连续性线性规划Model:Title 生产计划程序2;Sets:yuefen/1.4/:c,x,e,d,s;endsetsdata:c=70 71 8

13、0 76;d=6000 7000 1202X 6000;e=2 2 2 2 ;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 连续性线性规划月份单位成本(元) 销售量1234 70 6000 72 7000 80 12000 76 60002.2 连续性线性规划76827676-80-7472-747270生产月10000100001000010000产量60004120007000600

14、0销量4321321需求月费用cij2.2 连续性线性规划建立模型如下：2.2 连续性线性规划model:title 生产计划程序3;sets:yuefen/1.4/:a,d,xx;!定义上三角矩阵;link(yuefen,yuefen)|&2#ge#&1:c,x;endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d=6000 7000 1202X 6000;a=10000 10000 10000 10000;enddatamin=sum(link:c*x);for(yuefen(i):sum(yuefen(j)|j#ge#i:x(i,j)

15、d(j););!得到每个月的生产量;for(yuefen(i):xx=sum(yuefen(j)|j#ge#i:x(i,j);End2.2 连续性线性规划Model Title: :生产计划程序1 Variable Value Reduced Cost 2.2 连续性线性规划 设有两个工厂A、B，产量都是10万个，工厂有三个仓库x，y，z，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为3，5，4，5万个。工厂到仓库、仓库到顾客的运费单价（元/个）见下表所示。试求总运费最少的运输方案以及总运费。 AB甲乙丙丁x43571020y2196715z5220674课后训练model:

16、title 转运问题;sets: Plant /A, B/: produce; Warhouse /x, y, z/; Customer /1.4/: require; LinkI ( Plant, Warhouse): cI, xI; LinkII ( Warhouse, Customer): cII, xII;endsetsdata: produce = 10, 10; require = 3, 5, 4, 5; cI = 4, 2, 5, 3, 1, 2; cII = 5, 7, 10, 20, 9, 6, 7, 15, 20, 6, 7, 4;enddata课后练习OBJ min =

17、sum( LinkI: cI * xI) + sum( LinkII: cII * xII);! The supply constraints;for( Plant(i): SUP sum( Warhouse(j): xI(i,j) = produce(i);! 运进仓库的量等于运出的量;for( Warhouse(j): MID sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k);! The demand constraints;for( Customer(k): DEM sum( Warhouse(j): xII(j,k) = require

18、(k);课后练习连续投资10万元A：从第1年 到第4年每年初要投资，次年末回收本利B：，最大投资4万元C：，最大投资3万元D：。求：5年末总资本最大。练习2 连续投资课后练习第1年第2年第3年第4年第5年Ax1Ax1Ax1Ax1ABx3BCx2CDx1Dx1Dx1Dx1Dx1D练习2解答变量设置课后练习模型建立 课后练习程序编写model:title 投资问题;max=1.15*x4a+1.40*x2c+1.25*x3b+1.06*x5d;x1a+x1d=100000;x2a+x2c+x2d=1.06*x1d;x3a+x3b+x3d=1.15*x1a+1.06*x2d;x4a+x4d=1.15

19、*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x3b=40000;x2c=30000;课后练习运行结果Global optimal solution found. Total solver iterations: 2 Model Title: 投资问题 Variable Value Reduced Cost课后练习 例3 生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）产品的单位利润降低到万元，要不要改变生产计划，如果降低到1万

20、元呢？）产品的单位利润增大到5万元，要不要改变生产计划？）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？ 产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润232.3 敏感性分析2.3 敏感性分析程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;TIMEx1+2*x28;A4*x116;B4*x212;END2.3 敏感性分析运行结果 Model Title: 生产计划问题 Variable Value Reduced Cost Row Slack or Surplus Dual Price 对问题1，安排是生产产品

21、4单位，产品2单位，最大盈利为14万元 。2.3 敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变. 2.3 敏感性分析要使用敏感性分析必须要在这里选择Prices & Ranges然后保存退出路径：LINGOOptionsGeneral Solver(通用求解程序)选项卡2.3 敏感性分析要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGORange， 2.3 敏感性分析Ranges in

22、which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 当前变量系数允许增加量允许减少量对问题2，产品的单位利润降低到万元，在（，）之间，所以不改变生产计划。如果降低到1万元，不在（，）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得

23、新的计划为安排是生产产品2单位，产品3单位，最大盈利为11万元.对问题3，要改变生产计划，更改程序得新计划为生产产品2单位，产品3单位，最大盈利为19万元.对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到8万元. 2.3 敏感性分析2.3 敏感性分析把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润. 在最优情况下，y的值就是资源的影子价格，影子价格有意义是有范围的。影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量 2.3 敏感性分析Range

24、s in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 运行结果 Model Title: 生产计划问题 Variable Value Reduced Cost Row Slack or Surplus Dual Price MAXF 14.

25、00000 A 0.000000 B 0.000000 TIME 4.000000 2.3 敏感性分析1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：例4 加工奶制品的生产计划2.3 敏感性分析x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数

26、 每天获利约束条件非负约束 线性规划模型(LP)2.3 敏感性分析Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 220桶牛奶生产A1, 30桶生产A2，利润3360元。 2.3 敏感性分析 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.000000 35元可买到1桶牛奶，要买吗？35 50; x2 + 2*x4 + x5 + 3*x6 20; x3 + x5 + 2*x715;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);