1、Lingo与线性规划Lingo与线性规划线性规划的标准形式是 (1)其中称为目标函数,自变量称为决策变量,不等式组(1)称为约束条件. 满足不等式组(1)的所有的集合称为可行域,在可行域里面使得z取最小值的称为最优解,最优解对应的函数值称为最优值。求解优化模型的主要软件有Lingo、Matlab、Excel等。其中Lingo是一款专业求解优化模型的软件,有其他软件不可替代的方便功能。本文将简要介绍其在线性规划领域的应用。一、基本规定1、目标函数输入格式max=函数解析式; 或者 min=函数解析式;2、约束条件输入格式利用:、=、与=没有区别。Lingo软件默认所以自变量都大于等于0.3、运算
2、加(+),减(-),乘(*),除(/),乘方(xa),要注意乘号(*)不能省略。4、变量名不区分大小写字母,不超过32个字符,必须以字母开头。5、标点符号每个语句以分号“;”结束,感叹号“!”开始的是说明语句(说明语句也需要以分号“;”结束)。但是,model,sets,data以“:”结尾。endsets,enddata,end尾部不加任何符号。6、命令不考虑先后次序7、MODEL语句一般程序必须先输入MODEL:表示开始输入模型,以“END”结束。对简单的模型,这两个语句也可以省略。8、改变变量的取值范围bin(变量名); 限制该变量为0或1. bnd(a,变量名,b); 限制该变量介于a
3、,b之间.free(变量名); 允许该变量为负数.gin(变量名); 限制该变量为整数.例1 求目标函数的最小值,约束条件为输入Lingo程序:min = 2*x1 + 3*x2;x1 + x2 = 350;x1 = 100;2*x1 + x2 = 600;有两种运行方式:1、点击工具条上的按钮 即可。2、点击菜单:LINGOSolve运行结果如下:下面对其各个部分进行说明:Global optimal solution found:表示已找到全局最优解。Objective value:表示最优值的大小。可见本题函数最小值800。 Infeasibilities:矛盾约束的数目。Total s
4、olver iterations:迭代次数。 Variable:变量。本题有两个变量。 Value:变量对应的最优解,即。Reduced Cost:变量在最优解的基础上增加一个单位,目标函数值的改变量。例如,一个变量的Reduced Cost值为8,那么当该变量增加一个单位,在最大化(最小化)问题中目标函数值将减少(增大)8个单位。Slack or Surplus:表示接近等于的程度,即约束离相等还差多少。在约束条件是=中,不是过剩程度。如果约束条件是=,则Slack or Surplus为0,该约束是个紧约束(或有效约束)。如果一个约束是矛盾的,即模型无可行解则Slack or surplu
5、s的值是负数。知道Slack or Surplus的值,可以帮助我们发现优化模型中错误的约束条件。在上例中第2和第4行松弛变量均为0,说明对于最优解来讲,两个约束(第2和4行)均取等号,即都是紧约束,第3行为150,即最优解使得第3行过剩150.Dual Price :对偶价格的值,它表示约束条件中的常数,每增加一个单位,目标函数值改变的数量(在最大化问题中目标函数值是增加,在最小化问题中目标函数值是减少)。比如,在上一个Min模型中第四行的1,表示2*x1 + x2 = 600增加一个单位到2*x1 + x2 options-general solver-dual computations:
6、prices & ranges-ok.第二步:菜单lingo-range2、灵敏度报告中常见的词汇Current coefficient:当前目标函数系数Allowable increase:允许增加量Allowable decrease:允许减少量Current RHS:当前右边常数项INFINITY:表示正无穷。例1 求解下列模型:max = 72*x1+64*x2;x1+x2 = 50;12*x1+8*x2 = 480;3*x1 = 100;并做灵敏度分析。求解报告:灵敏度分析报告:灵敏度分析报告的解读:x1的系数变化范围是(72-8,72+24)=(64,96);x2的系数变化范围是(
7、64-16,64+8)=(48,72)。注意:x1系数的允许范围需要x2系数64不变,反之亦然。由于目标函数的费用系数变化并不影响约束条件,因此此时最优基不变可以保证最优解也不变,但最优值变化。右边常数项中,第2行原来为50,当它在50-,50+10 = ,60范围变化时,最优基保持不变。第3行可以类似解释。对第4行,原来为100,当它在100-40,100+ = 60,+范围变化时,最优基保持不变。不过由于此时约束发生变化,最优基即使不变,最优解、最优值也会发生变化。三、数据输入对于大型的优化问题,即自变量比较多的时候,还像上两节那样输入目标函数和约束条件就比较麻烦了。一般输入数据的方法有两
8、种:一、建立向量、矩阵输入;二、调用外部数据。这里仅介绍第一种方法。1、建立向量命令格式:集合名称/集合维数/:向量名称例如:sets:set1/1.9/:x;set2/1.5/:a,b;endsets表示建立了两类集合。第一类集合set1,维数为9,x和y是向量名。向量x=(x(1), x(9)),其中x(i)是x的元素。第二类集合set2,维数为5,a和b都是向量名。向量a=(a(1), a (5)),其中a (i)是a的元素。向量b=(b(1), b(5)),其中b (i)是b的元素。2、建立矩阵命令格式:集合名称(集合1,集合2)/:矩阵名称例如:sets:set1/1.3/:x;se
9、t2/1.4/:a;link(set1, set2):A;endsets表示建立了一个矩阵类link,其矩阵的阶数为,A是具体的矩阵名。有两个命令是比较常见的:求和语句:sum(集合名(i):含集合名(i)的语句);循环语句:for(集合名(i):循环的语句);例3:求目标函数的最小值,约束条件为输入Lingo程序:model:sets:set1/1.2/:c,x;set2/1.3/:b;link(set2,set1):A;endsetsmax=sum(set1(i):c(i)*x(i);for(set2(i):sum(link(i,j):A(i,j)*x(j)=b(i);data:c=11
10、15;A=20 30 30 25 30 25;enddataend运行结果报告:例4、某地区有三个蔬菜生产基地,估计每年可供应本地区的蔬菜量表为:生产基地ABC蔬菜生产量(吨)783有四个地市需要该类蔬菜,需求表为:地区甲乙丙丁蔬菜生产量(吨)6633如果从各蔬菜生产基地到各地市的每吨蔬菜的运价表(单位:万元/吨)为: 地市生产基地甲乙丙丁A5879B49107C8429为了降低运输费,需要合理调拨资源.(1) 根据以上资料表制订一个使总的运费为最少的蔬菜调拨方案(2)如果有机会增加生产基地的产量1吨,问应当优先增加那个基地的产量? (3)如果将A到乙市的运价减少为5万元/吨,问这会影响最优的
11、调拨方案吗?设:第i个蔬菜生产基地,分别对应生产基地A,B,C;:第i个蔬菜需求地,分别对应蔬菜需求地市甲、乙、丙、丁;:总运输费用;:表示的是从第i个生产基地向第j个地市运输的蔬菜数量;:表示的是从第i个生产基地向第j个地市运输蔬菜的运价;:第i个蔬菜生产基地的蔬菜产量;:第j个地市的蔬菜需求量;那么有优化模型:输入Lingo程序求解模型:model:sets:set1/1.3/:b;set2/1.4/:q;link(set1,set2):c,x;endsetsmin=sum(link(i,j):c(i,j)*x(i,j);for(set1(i):sum(link(i,j): x(i,j)=
12、b(i);for(set2(j):sum(link(i,j): x(i,j)=q(j);data:c=5,8,7,9 4,9,10,7 8,4,2,9;b=7,8,3;q=6,6,3,3;enddataend运行结果如下:Global optimal solution found. Total solver iterations: 6 Variable Value Reduced Cost Row Slack or Surplus Dual Price从该报告可以得到:1、 最优的调拨方案为: 地市生产基地甲乙丙丁A1600B5003C0030 2、从Dual Price来看 生产基地A的供应
13、量增加1个单位,费用不变;生产基地B的供应量增加1个单位,费用减少1;生产基地C的供应量增加1个单位,费用减少4;城市甲的需求量增加1个单位,费用减少-5,即增加5;城市乙的需求量增加1个单位,费用减少-8,即增加8;城市丙的需求量增加1个单位,费用减少-6,即增加6;城市丁的需求量增加1个单位,费用减少-8,即增加8;3、从Slack or Surplus来看,所有的约束都是紧约束。可见每个生产基地的蔬菜都全部运完。然后做灵敏度分析:Ranges in which the basis is unchanged: Objective Coefficient Ranges Current All
14、owable Allowable Variable Coefficient Increase Decrease Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease可以得到以下信息:1、运价在下面的范围内最优的调拨方案不变: 地市生产基地甲乙丙丁A4,64,96, +8, +B3,57, +5, +0,8C1, +3,80,34, +2、生产基地的产量在下面的范围内最优基不变:生产基地ABC蔬菜生产量(吨)7, +8,96,93、四个地市的需求量在下面的范围内最优基不变:地区甲乙丙丁蔬菜生产量(吨
15、)5,60,60,32,3四、收集的一些问题1、 DETROITATLANTAHOUSTONTAMPA014010090225DETROIT1450111110119ATLANTA105115011378HOUSTON891091210-TAMPA21011782-0如何确定运输和生产方案,才能满足Houston 和 Tempa的需求且费用最低.2、设有三个化肥厂供应四个地区的农用化肥.假定等量的化肥在这些地区使用效果相同.各化肥厂年产量,各地区年需要量及从各化肥厂到各地区运送单位化肥的运价(万元/万吨)如下表所示.试求出总的运费最省的化肥调拨方案. 需求地区化肥厂IIIIIIIV产量(万吨)
16、A1613221750B1413191560C192023禁止50最低需求(万吨)3070010最高需求(万吨)507030不限3、某航运公司承担6个港口城市A,B,C,D,E,F的四条固定航线的物资运输任务.已知各条航线的起点,终点城市及每天航班数见下表:航线起点城市终点城市每天航班数1ED32BC23AF14DB1假定各条航线使用相同型号的船只,由各城市间的航程天数见下表: 到 从ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030又知每条船只每次装卸货物的时间各需1天,则该航运公司至少应配备多少条船,才能满足所有航线的运货要
17、求.4、如下图所示,节点间的线段表示某小区的弄堂,线段旁的数字表示弄堂的长度。邮局在其中某个节点,请设计邮递员投递路线。5、如下图所示,节点间的线段表示某区的街道,街道都是单行道,线段旁的数字表示街道的长度。邮局在其中某个节点,请设计邮递员投递路线。6、伦敦一家大公司计划将公司的一些部门搬出伦敦,以节约诸如房租人事等方面的费用,当然部门间的通信费用必将增加。公司由五个部门组成,A,B,C,D,和 E,考虑搬迁的地址为Bristol 和 Brighton。每个城市至多安置3个部门。各部门搬迁后每年能节约的费用(千镑)如下表:ABCDEBristol101510205Brighton1020151515各部门间每年的通信量(千单位)如下表:ABCDEABCD各部门间的通信单价(镑每年每单位)BristolBrightonLondonBristol51413Brighton1459London13910
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2