Lingo与线性规划

1、共享知识分享快乐卑微如蝼蚁、坚强似大象Lingo与线性规划线性规划的标准形式是s.t(1)Min Z 二GXi 111CnXnam1 X1f I f amnxn bmx i =12川,n其中Z rqXi * |CnXn称为目标函数，自变量为称为决策变量，不等式组(1)称为约 束条件满足不等式组(1)的所有(X1,|(,Xn)的集合称为可行域，在可行域里面使得Z取最小值的(X1,|,Xn)称为最优解，最优解对应的函数值称为最优值。求解优化模型的主要软件有 Lin go、Matlab、Excel等。其中Lingo是一款专 业求解优化模型的软件，有其他软件不可替代的方便功能。本文将简要介绍其在 线性

2、规划领域的应用。一、基本规定1、目标函数输入格式max=S数解析式；或者 min= 函数解析式；2、约束条件输入格式利用： 、=、=等符号。但是 与 =没有区别。Lin go软件默认所以自 变量都大于等于0.3、运算加(+),减(-),乘(*),除(/),乘方(xAa)，要注意乘号(*)不能省略。4、变量名不区分大小写字母，不超过 32个字符，必须以字母开头。5、标点符号每个语句以分号“；”结束，感叹号“！”开始的是说明语句（说明语句也需 要以分号“；” 结束）。但是，model，sets，data 以“：”结尾。endsets，enddata， end尾部不加任何符号。6、命令不考虑先后次序

3、7、MODE语句一般程序必须先输入 MODEL表示开始输入模型，以“ END结束。对简单 的模型，这两个语句也可以省略。8改变变量的取值范围bin（变量名）；bnda,变量名,b）；free（变量名）；限制该变量为0或1.限制该变量介于a,b之间.允许该变量为负数gin（变量名）；限制该变量为整数例1求目标函数乙=2捲-3X2的最小值，约束条件为st 为 +x2 H350X! 1002% 2x2 一 600XX -0输入Lingo程序:min = 2*x1 + 3*x2;x1 + x2 = 350;x1 = 100;2*x1 + x2 0 口口CIDCI 1X00000Rou Slack or

4、 Surplus1 900*00002 o.ooooao3 150.00004 0X00000F面对其各个部分进行说明：Global optimal solution found :表示已找到全局最优解。Objective value：表示最优值的大小。可见本题函数最小值zmin =800。In feasibilities :矛盾约束的数目Total solver iterati ons:迭代次数。Variable：变量。本题有两个变量。Value：变量对应的最优解，即x, =250,x2 =100。Reduced Cost变量Xi在最优解的基础上增加一个单位，目标函数值的改变 量。例如，一个

5、变量的Reduced Cos值为8，那么当该变量增加一个单位，在最 大化（最小化）问题中目标函数值将减少（增大）8个单位。Slack or Surplus表示接近等于的程度，即约束离相等还差多少。在约束条 件是=中，不是过剩程度。如果约束条件是 =，则Slack or Surplus为0，该约束是个紧约束（或有效约束）。如果一个约束是矛 盾的，即模型无可行解则 Slack or surplus的值是负数。知道Slack or Surplus的值，可以帮助我们发现优化模型中错误的约束条件。 在上例中第2和第4行松弛变量均为0,说明对于最优解来讲，两个约束（第2和4 行）均取等号，即都是紧约束，第

6、3行为150,即最优解使得第3行过剩150.Dual Price :对偶价格的值，它表示约束条件中的常数，每增加一个单位，目标函数值改变的数量（在最大化问题中目标函数值是增加，在最小化问题中目标函数值是减少）。比如，在上一个Min模型中第四行的1，表示2*x1 + x2 = 600 增加一个单位到2*x1 + x2 options-general solver-dual computati on s:prices & ran ges-ok.卑微如蝼蚁、坚强似大象第二步：菜单 lingo-range2、灵敏度报告中常见的词汇Curre nt coefficie nt:当前目标函数系数Allowa

7、ble in crease:允许增加量Allowable decrease:允许减少量Current RHS :当前右边常数项INFINITY :表示正无穷。例1求解下列模型:max = 72*x1+64*x2; x1+x2 = 50;12*x1+8*x2 = 480;3*x1 = 100;并做灵敏度分析。求解报告：Global optimal salution found.Objective value:3360Infeasibilities:0-00000DTotal solver iterations:VariableValuededucedXI00000o.ooaoooX230.000

8、00-000000RowSlack or SurplusDual Price13360.000l.OOQOOO20-00000018-0000030.0000002.003000马-10- 口01口,000灵敏度分析报告:OtojECtiVE Coefficient RangesCurrantAllowableVariableCoeficientIncreaseDecreaseXI72.0000024.000008000000X264.00000S.00000016onooois unchanged:Righthand Side RangesROWCu匚rentAllowsJQleAHqwsJ

9、qIsRHSIncreaseDecrease250.0000010.000006.66666734S0.000053.3333380.000004100.0000IMFINITY40.00000Ranges in which the basis灵敏度分析报告的解读:x1的系数变化范围是(72-8 , 72+24 ) = (64 , 96); x2的系数变化范围是 (64-16，64+8)=(48，72)。注意：x1系数的允许范围需要x2系数64不变， 反之亦然。由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。右边常数项中，第2行原来为50，当它

10、在50-6.67，50+10 = 43.33，60 范围变化时，最优基保持不变。第 3行可以类似解释。对第4行，原来为100， 当它在100-40，100+ = 60，范围变化时，最优基保持不变。不过由于此 时约束发生变化，最优基即使不变，最优解、最优值也会发生变化。三、数据输入对于大型的优化问题，即自变量比较多的时候，还像上两节那样输入目标函 数和约束条件就比较麻烦了。一般输入数据的方法有两种：一、建立向量、矩阵 输入；二、调用外部数据。这里仅介绍第一种方法。1、建立向量命令格式：集合名称/集合维数/ :向量名称例如:sets :set1/1.9/:x;set2/1.5/:a,b;en ds

11、etsx=)表示建立了两类集合。第一类集合setl，维数为9, x和y是向量名。向量(x(1),x(9),其中x(i)是x的元素。第二类集合set2，维数为5, a和b都是向量名。向量a= (a，,a),其中b (i)是b的元素其中a (i)是a的元素。向量b= (b(1),b(5)2、建立矩阵命令格式：集合名称(集合1,集合2) / :矩阵名称例如：sets :set1/1.3/:x;set2/ 1.4/:a;lin k(set1, set2):A;en dsets表示建立了一个矩阵类link，其矩阵的阶数为3 4, A是具体的矩阵名有两个命令是比较常见的：求和语句：sum集合名(i):含集

12、合名(i)的语句)；循环语句：for(集合名(i):循环的语句);例3:求目标函数乙=11洛+15x2的最小值，约束条件为s.t 20x1 + 30X2 兰360 30X1 +25X2 兰 2000| 30x1 +35X2 兰 300 IxX2 兰 0输入Lingo程序：model:sets :set1/1.2/:c,x;set2/ 1.3/:b;lin k(set2,set1):A;en dsetsmax=su(iset1(i):c(i)*x(i);for(set2(i):sum nk(i,j):A(i,j)*x(j)v=b(i);data:c=11 15;A=20 3030 2530 25

13、;b=360 2000 300;en ddataend运行结果报告:iao.oooo0r000DOO右Loba丄 ciptzLina丄 solution :faundl. Ob j ect ive vvlI u.e:Ini easito ilitiea:Toe al so ivex 1is-VariableValueReduced CostCt 1J11.00000CL 000000C( 2ISa-ODOOD口纽1J口 cmcmci了 口 cicimX 2)IS.000000000000Bt 1)360 .DCIOCI0000000BE 2EQ 口 ChOQ 口aooDaoo3so 口 mo

14、口口口口口0口At1)20.00000口.OODOOOAl 1, 2)30.000000OODOOOA J 130.00000cl oaooooAf S 2ZSadDOOD口aDOD口口At 31J30.00000OQDQOOAt 3, 2)25.000000000000FewOCD甘ol Price1ISO 口口1口仃口。口20 OODOOO口OODOOO31700.000DOODOOO4CL OODOQODr6000000例4、某地区有三个蔬菜生产基地，估计每年可供应本地区的蔬菜量表为:生产基地ABC蔬菜生产量(吨)783有四个地市需要该类蔬菜，需求表为:地区甲乙丙丁蔬菜生产量(吨)663

15、3(1)根据以上资料表制订一个使总的运费为最少的蔬菜调拨方案. 如果有机会增加生产基地的产量1吨，问应当优先增加那个基地的产 量？(3) 如果将A到乙市的运价减少为5万元/吨，问这会影响最优的调拨方案 吗？设A :第i个蔬菜生产基地，i= 1,2,3，分别对应生产基地 A, B, C;B,:第i个蔬菜需求地，i =1,2,3,4，分别对应蔬菜需求地市甲、乙、丙、 丁；Q：总运输费用；Xj ：表示的是从第i个生产基地向第j个地市运输的蔬菜数量；Cij :表示的是从第i个生产基地向第j个地市运输蔬菜的运价；b :第i个蔬菜生产基地的蔬菜产量；qi :第j个地市的蔬菜需求量；那么有优化模型：34mi

16、n Q 八 qni 4 j JX11+ X12+ X13+X14X21+ X22+ X23+X240,1,2,3; j =1,2,3,4输入Lin go程序求解模型:model:sets :set1/1.3/:b;set2/1.4/:q;li nk(set1,set2):c,x;en dsetsmin =sum nk(i,j):c(i,j)*x(i,j);for(set1(i):sumnk(i,j): x(i,j)=b(i);for(set2(j):sumnk(i,j): x(i,j)=q(j);data:c=5,8,7,94,9,10,78,4,2,9;b=7,8,3; q=6,6,3,3;

17、enddataend运行结果如下：Global optimal solution found.100.00000.000000Objective value:Infeasibilities:Total solver iterations:VariableValueReduced CostB( 1)7.0000000.000000B( 2)8.0000000.000000B( 3)3.0000000.000000Q( 1)6.0000000.000000Q( 2)6.0000000.000000Q( 3)3.0000000.000000Q( 4)3.0000000.000000C( 1, 1)5

18、.0000000.000000C( 1, 2)8.0000000.000000C( 1, 3)7.0000000.000000C( 1, 4)9.0000000.000000C( 2, 1)4.0000000.000000C( 2, 2)9.0000000.000000C( 2, 3)10.000000.000000C( 2, 4)7.0000000.000000C( 3, 1)8.0000000.000000C( 3, 2)4.0000000.000000C( 3, 3)2.0000000.000000C( 3, 4)9.0000000.000000X( 1, 1)1.0000000.000

19、000X( 1, 2)6.0000000.000000X( 1, 3)0.0000001.000000X( 1, 4)0.0000001.000000X( 2, 1)5.0000000.000000X( 2, 2)0.0000002.000000X( 2, 3)0.0000005.000000X( 2, 4)3.0000000.000000X( 3, 1)0.0000007.000000X( 3, 2)0.0000000.000000X( 3, 3)3.0000000.000000X( 3, 4)0.0000005.000000Row Slack or Surplus Dual Price1

20、100.0000-1.0000002 0.0000000.0000003 0.0000001.0000004 0.0000004.000000-5.000000-8.000000-6.000000-8.0000005 0.0000006 0.0000007 0.0000008 0.000000从该报告可以得到：1、 最优的调拨方案为：、地市生产基地甲乙丙丁A1600B5003C0030生产基地A的供应量增加1个单位,费用不变;生产基地B的供应量增加1个单位,费用减少1；生产基地C的供应量增加1个单位,费用减少4；城市甲的需求量增加1个单位,费用减少-5即增加5；城市乙的需求量增加1个单位,费用

21、减少-8即增加8；城市丙的需求量增加1个单位,费用减少-6即增加6；城市丁的需求量增加1个单位,费用减少-8即增加8；2、从 Dual Price 来看卑微如蝼蚁、坚强似大象来看，所有的约束都是紧约束。可见每个生产基地的蔬3、从 Slack or Surplus菜都全部运完。然后做灵敏度分析:Ran ges in which the basis is un cha nged:Objective Coefficient RangesCurre ntAllowable AllowableVariableCoefficie ntIn creaseDecreaseX( 1, 1)5.0000001.0

22、000001.000000X( 1, 2)8.0000001.0000004.000000X( 1, 3)7.000000INFINITY1.000000X( 1,4)9.000000INFINITY1.000000X( 2, 1)4.0000001.0000001.000000X( 2, 2)9.000000INFINITY2.000000X( 2, 3)10.00000INFINITY5.000000X( 2, 4)7.0000001.000000INFINITYX( 3, 1)8.000000INFINITY7.000000X( 3, 2)4.0000004.0000001.000000

23、X( 3, 3)2.0000001.000000INFINITYX( 3, 4)9.000000INFINITY5.000000Rightha nd Side Ran gesRowCurre ntAllowableAllowableRHSIn creaseDecrease27.000000INFINITY0.038.0000001.0000000.043.0000006.0000000.056.0000000.01.00000066.0000000.06.00000073.0000000.03.00000083.0000000.01.000000可以得到以下信息:1运价在下面的范围内最优的调拨

24、方案不变地市生产基地甲乙丙丁A4,64,96, + 鬥8, +mB3,57, +-5, +門0,8C1, +m3,80,34, +門2、生产基地的产量在下面的范围内最优基不变生产基地ABC蔬菜生产量（吨）7, +呵8,96,93、四个地市的需求量在下面的范围内最优基不变地区甲乙丙丁蔬菜生产量（吨）5,60,60,32,3四、收集的一些问题1、福特在L.A.和Detroit 生产汽车,在Atlanta 有一仓库,供应点为 Houston和Tampa;城市间每辆汽车运输费用见下表.L.A.的生产能力为1100辆, Detroit 的生产能力为2900辆.Houston汽车需求量为2400辆,Tampa汽车需 求量为1500辆,L.ADETROITATLANTAHOUSTONTAMPAL.A.014010090225DETROIT1450111110119ATLANTA105115011378HOUSTON891091210-TAMPA21011782-0如何确定运输和生产方案,才能满足Houston和Tempa的需求且费用最低.2、设有三个化肥厂供应四个地区的农用化肥.假定等量的化肥在这些地区使