GAMs中文使用心得.doc

写在前面的话在学习和工作之余写点东西，这种想法由来已久了。只是总是觉得很忙，抽不出时间做一点点自己喜欢做的事情。突然有一天发现，你必须牺牲某些东西才能得到某些东西。所以，就索性写上几句话聊以自慰吧。最开始，只想翻译一下GAMS的用户手册。但是又觉得这样写很枯燥，不光读者不喜欢看，连自己也要打瞌睡了。如果想催眠的话，还不如去听评书。但是本书还是以解释GAMS的用法为主。中间夹杂着一些自己做modelling 的体验，还可能还有一些毫不相关的东西。可能有很多错误，请读者们原谅。想学习GAMS的同学，想必一定是数学，运筹学或计算机相关专业的了。让大家失望了，其实我的专业是chemical engineering, 本科时候做的是量子化学。阴差阳错上了贼船。但是觉得自己用了这么多年了，总该有点体会，能过帮帮大家。进入正题之前，还想啰嗦几句题外的话。能看到这篇文字的同学，恐怕大多数是在灯下苦读的学子。实际上学习某种工具并不重要。真正要学习的是知识，是思维的方法。就像很多计算机系的学生一样，把数据结构和算法精通了，任何工具都是一样的。所以，你用GAMS或者不用GAMS，都没有关系，要把握事物的本质，最关键的东西抓住了，任何语言就是一种输入法。另外，学习一定要有兴趣，要认识到他的beauty，不要把什么都换算成人民币，那样你会觉得很累。除了，coding 以外，还要博览群书，文史哲，拿来翻翻，就当休息了。最后，男子汉们，别忘了，谈一场轰轰烈烈的恋爱！第一章，基本概况GAMS是一种非常简单易学的运筹学建模语言 (），是由WORLD BANK 开发的。由于近几十年计算机软硬件的的高速发展，世界银行决定投资开发GAMS, 来提供：1 建立复杂模型的高级语言2 简单易学3 强大的描述代数及逻辑关系4 模型可以独立于算法系统GAMS 可以让使用者专心致力于模型的建立而省略了解法方面的考虑因为GAMS包含了解决通用的LP,NLP，MILP，MINLP等各类模型所需要的solver. 另外，GAMS提供了和外界进行交互的输入输出借口。使得用户很方便的导入导出data。下面当然是tutorial了，就想学习任何一种编程语言一样，最开始都要学习输出 hello world. 我们这里当然要复杂一点了，举一个最简单的例子，运输问题.这是一个经典的LP问题（不用解释什么是LP吧，呵呵）用点英语，呵呵，In the familiar transportation problem, we are given the supplies at several plants and the demands at several markets for a single commodity, and we are given the unit costs of shipping the commodity from plants to markets. The economic question is: how much shipment should there be between each plant and each market so as to minimize total transport cost?就是说，我们已知有一些工厂，生产出的产品要运往一些市场来满足他们的需求，每一个工厂的生产能力（每个工厂能提供产品的数量）以及每个市场的需求（每个市场需要产品的数量）是已知的。另外，我们还知道从特定的工厂到特定的市场，运输一件产品的运费。那么我们怎么样设计从每个工厂到每个市场运送货物的数量，使得总运费最小？Indices:i = plantsj = marketsGiven Data:ai = supply of commodity of plant i (in cases)bj = demand for commodity at market j (cases)cij = cost per unit shipment between plant i and market j ($/case)Decision Variables:Xij = amount of commodity to ship from plant i to market j在这里唯一的连续变量是Xi,j,模型就不用我说了吧。这是一个典型的线性规划问题，他的GAMS code isSetsi canning plants / seattle, san-diego /j markets / new-york, chicago, topeka / ;Parametersa(i) capacity of plant i in cases/ seattle 350san-diego 600 /b(j) demand at market j in cases/ new-york 325chicago 300topeka 275 / ;Table d(i,j) distance in thousands of milesnew-york chicago topekaseattle 2.5 1.7 1.8san-diego 2.5 1.8 1.4 ;Scalar f freight in dollars per case per thousand miles /90/ ;Parameter c(i,j) transport cost in thousands of dollars per case ;c(i,j) = f * d(i,j) / 1000 ;Variablesx(i,j) shipment quantities in casesz total transportation costs in thousands of dollars ;Positive Variable x ;Equationscost define objective functionsupply(i) observe supply limit at plant idemand(j) satisfy demand at market j ;cost . z =e= sum(i,j), c(i,j)*x(i,j) ;supply(i) . sum(j, x(i,j) =l= a(i) ;demand(j) . sum(i, x(i,j) =g= b(j) ;Model transport /all/ ;Solve transport using lp minimizing z ;Display x.l, x.m ;这是一个非常典型的LP（linear programming）问题,所有的变量和约束都是线性相关的。其实上面的LP例子虽然很简单，从GAMS的角度已经勾勒出大致的轮廓了。首先，我一般把GAMS模型分割成两部分。数据和模型，在gams里面最好要把数据和模型最大程度的分割开来。具体的建模的经验已后再详细论述。首先，我们看到的是数据中最抽象得部分：set.set是模型中最最基本的部分。通常我们用i,j来表示。例如，时间的维度可以用 set t /t1*t10/来表示，当然还可以有更加具体的形式：/1990*2008/。这里面当然代表的不是数字而是string了。parameters 是和set紧密相连的已知的Data。基本上很容易理解。可以用 A(i,j)来表示一个已知矩阵data的每一个元素。variables 当然有很多种了，在这里都是连续变量。可以先定义（所有变量都要先定义后使用）成variable x(i,j)再约束：positive variables x.上一部分除了variables之外的都是属于data的部分。这里说的好像有点啰嗦，我反复给大家灌输一个思想：数据和模型要尽量的分开，数据只不过是输入，模型是engine。变量有很多种，可以根据自己模型的需要定义。binary variables 非常的重要，在模型里面主要是作为决策变量的。interger variables 实际上可以用binary变量来表示。模型的主体实际上就是一系列约束的组合。你可以定义很多约束条件，也可以定义很多objective function。然后根据自己的需要组合成不同的模型。所以GAMS编程简单的说就是不很多相关的约束和目标函数组合到一起，然后调用不同类型的solver来解决。说到这里，大家对GAMS只能有一个大概的了解。我觉得写GAMS code 并不难，难的只有两点:1.定义你的模型。要选取最efficient的方法2.定义好你的set。模型里面所有的东西都和它有关，正所谓牵一发动全身。其他都是水到渠成。这几天简直忙迷糊了，才来写手册。对不起了。先从set开始。Set有很多的用法可以定义。最常见的形式就是：set t /Jan,Feb,Mar/这里最好不要用简单的，i,j 来表示,或者如果想和自己的模型一致的话，可以把general symbol 写成i,j,t的形式然后把每一个elemement写成具体的。每一个set还可以有自己的alias。也就是别名。因为很多时候还要建立很多二元操作。可以这样写：alias(c,cp,cpp,cppp);定义subset: set set01(set02): set01 是 set02 的subset高维度set：主要是定义mapping：mapping(i,j)/i1.j1,i2.j2/如果在模型里面要定义某种特定的操作，可以先在set里面定义。(a,b).c.d a.c.d, b.c.d(a,b).(c,d) .e a.c.e, b.c.e, a.d.e, b.d.e(a.1*3).c (a.1, a.2, a.3).c or a.1.c, a.2.c, a.3.c1*3. 1*3. 1*3 1.1.1, 1.1.2, 1.1.3, ., 3.3.3set的domain可以用card(i)来表示,顺序可以用ord(i)来表示。这两个操作在模型里面非常的重要，很多复杂的集合操作都是建立在这两个基础上的。下次开始讲data顺便说一句，微软已经开发一个solver foundation 来抗衡象GAMS这样的工具。你可以在excel里面建模。非常的简单。我曾经在他们的论坛上和一个以前在GAMS工作的人讨论过他们的有缺点。以后在详细的介绍给大家。今天讲讲Data。在GAMS里面Data无非就是你所已知的数据。主要有scalar，parameters,tables。在GAMS里面没有像java一样的private,public and protected变量的分别。可以说所有的变量都是全局的。scalaritem1nameoptionalexplanatorytext/numericalvalue/；Parameterdata(i,j,k) / i1.j1.k1 10 , i2.j1.k2 90 /;TableRESOURUSE(RESOURCE,PROCESS)RESOURCEUSAGEMakechairMaketableMakelampplantcap321.1salecontrct11;这里没什么可以讲的，就是注意把的行和列分清楚就可以了。在这里其实我语言方面讲的很少，觉得有gams的手册，大家都可以慢慢得理解。但是我反复说明一个观点，数据和模型的形式一定要尽量的general。在建立模型的时候一定要考虑到以后模型的地扩展性。在修改数据的时候，要尽量只修改数据的部分。各个模块要尽量的独立。刚刚开始很多人没有引起相应的重视。模型越来越复杂，到后来只好推倒重来了。最好的办法，是把数据完全和模型分离开来。可以写成txt文件放到gams里的classpath里面，在模型的源代码里面引用。（include.)这样，修改好数据后，只要修改相应的include file就可以了。在模型里面，可以包含变量的声明和定义和初始化。但是经常改变的变量最好放到data.txt里面。下面接受一下变量：变量是组成模型的最基本的元素。最好是先声明变量，再进行初始化。任何不加以约束的变量可以写成variables 或者是 free variables。另外还可以因需要定义：positive, nonnegative, negative, binary and integer 变量。这里需要提醒的是 binary variable,只能有0，1两个值。通常用来做决策的。还有integer variable的默认范围是从0到100。改动它的上下限已后会详细介绍。其实，整数变量可以由01变量通过线性组合得到。这里就不介绍了。另外，gams还支持另外两个特殊变量:SOS1和SOS2变量。SOS1变量值在一组变量里面，只有一个变量可以是非零的。但不一定是1。SOS2指一组变量里面，只有两个相邻的变量是非零的。这两个变量在比较高级的MILP模型中会遇到。变量声明方法示例：VariablesTcost TotalCostOfShipping-AllRoutes;BinaryVariablesBuild(Warehouse)WarehouseConstructionVariables;PositiveVariablesShipsw(Supplyl,Warehouse)ShipmenttowarehouseShipwm(Warehouse,Market)ShipmentfromWarehouseNonnegativeVariablesShipsm(Supplyl,Market)DirectshiptoDemand;SemicontVariablesX,y,z;下面说说变量的attributes。对于变量通常会有很多的约束条件，我们可以把它们写到Equations里面。但是变量的很多attributes可以对变量进行很多的简单的操作以免让equations的部分看起来过于繁杂。另外，在建立模型的时候，要设计某些算法，在算法执行的过程当中，不能嵌入equation。所以，要用到很多变量attributes的操作。其实， equations表示的是一种关系，而对于变量的Attribute操作实际上是一种赋值的操作。以变量X为例，x.lo=10000；设置变量下限。x.up=20000；设置变量上限。x.fx=0；固定变量的值。随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。Sets r rows / r1*r9 / c columns / c1*c9 / b blocks / b1*b9 / v values / v1*v9 / br(b,r) / b1*b3 .r1*r3, b4*b6 .r4*r6, b7*b9 .r7*r9 / bc(b,c) / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 / brc(b,r,c) block definitions ;brc(b,r,c) = br(b,r)*bc(b,c);Table problem(r,c) Hard problem with non-unique solution c1 c2 c3 c4 c5 c6 c7 c8 c9r1 2 6 7r2 6 2r3 4 8 1r4 5 9 3r5 3 5r6 2 8 7r7 1r8 7 8 6r9 5 3 8 ;Binary Variable X(r,c,v) assign value to cell (defined by row and column);Variable W objectiv value - anything;equations eq1(r,c) exactly one value for each cell eq2(c,v) column entries have to be unique eq3(r,v) row entries have to be unique eq4(b,v) block entries have to be unique nobj definition of objective - anything;X.fx(r,c,v)$(problem(r,c)=ord(v) = 1;eq1(r,c). sum(v, X(r,c,v) =E= 1;eq2(c,v). sum(r, X(r,c,v) =E= 1;eq3(r,v). sum(c, X(r,c,v) =E= 1;eq4(b,v). sum(brc(b,r,c), X(r,c,v) =E= 1;nobj. W =E= sum(r,c,v), X(r,c,v);model sudoku / all /;solve sudoku minimizing w using mip;最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的anything。set 的定义可以更加简单明了：setsr rows / r1 * r9/c columns / c1 * c9/v values / v1 * v9/sc sub-col /sc1 * sc3/sr sub-row /sr1 * sr3/scs(sc, c) /sc1.(c1*c3), sc2.(c4*c6), sc3.(c7*c9)/srs(sr, r) /sr1.(r1*r3), sr2.(r4*r6), sr3.(r7*r9)/ equations:eq1(r, c). sum(v, x(r, c, v) =E= 1;eq2(c, v). sum(r, x(r, c, v) =E= 1;eq3(r, v). sum(c, x(r, c, v) =E= 1;eq4(sr, sc, v). sum(c,r)$(scs(sc, c) and srs(sr, r), x(r, c, v) =E= 1; 下面说说 equation的写法。和变量的声明一样，equations也一定要声明后再定义。具体写法：Equationssupply(i) observe supply limit at plant idemand(j) satisfy demand at market j ;cost . z =e= sum(i,j), c(i,j)*x(i,j) ;supply(i) . sum(j, x(