运筹学实验指导书.doc

运筹学实验指导书 运筹学实验课指导书软件简介LINDO是一种专门用于求解数学规划问题的软件包。 由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。 因此在数学、科研和工业界得到广泛应用。 LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。 也可以用于一些非线性和线性方程组的求解以及代数方程求根等。 LINDO中包含了一种建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。 LINDO6.1是求解线性、整数和二个规划问题的多功能工具。 LINDO6.1互动的环境可以让你容易得建立和求解最佳化问题，或者你可以将LINDO的最佳化引擎挂在您己开发的程序内。 而另一方面，LINDO也可以用来解决一些复杂的二次线性整数规划方面的实际问题。 如在大型的机器上，LINDO被用来解决一些拥有超过50,000各约束条件和200,000万个变量的大规模复杂问题LINGO则用于求解非线性规划（NLPNONLINEAR PROGRAMMING）和二次规则（QPQUARATIC PROGRAMING）其中LINGO6.0学生版最多可版最多达300个变量和150个约束的规则问题，其标准版的求解能力亦再104量级以上。 虽然LINDO和LINGO不能直接求解目标规划问题,但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。 1)什么是LINDO在这里有必要先让大家知道什么是运筹学。 运筹学是近四十年来发展起来的一门新兴学科。 它的目的是为行政管理人员在作决策时提供科学的依据。 因此，它是实现管理现代化的有力工具。 运筹学在生产管理、工程技术、军事作战、科学试验、财政经济以及社会科学中都得到了极为广泛的应用。 讲到这里，你已经被运筹学深深吸引了吧，至于你会怎么去学不是我们讨论的问题，在这里我们只说学运筹学要用到的工具。 应用运筹学去处理问题有两个重要特征一是从全局的观点出发；二是通过建立模型如数学模型或模拟模型，对于要求解的问题得到最合理的决策。 好了，说到这里，LINDO该出场了，它的作用就是负责把问题的最优决策求出来，省去大量难以想象的人工计算。 如果你是运筹学的学习者，你就必须拥有LINDO。 LINDO(Linear,INteractive,and DiscreteOptimizer)是一个解决二次线性整数规划问题的方便而强大的工具。 这些问题主要出现在商业、工业、研究和政府等领域。 已被证实LINDO能在其中发挥巨大作用的具体事务包括产品分销、成分混合、生产与个人事务安排、存货管理在这里不一一列举，但可以肯定的是，LINDO可以大展拳脚的领域是多不胜数的。 LINDO的主要设计原则是，如果一个用户只是想解决一个简单的问题，就不应该在学习LINDO的基本特性上花费太多的准备成本。 例如，某个用户想解决以下这样一个问题(看懂这个问题需要一定的运筹学知识，下面是一个实际问题的数学模型)Max2X+3Y Subject to4X+3Y103X+5Y12那么，用户就只需要打开LINDO，然后直接输入以上内容即可。 而另一方面，LINDO也可以用来解决一些复杂的二次线性整数规划方面的实际问题。 如在大型的机器上，LINDO被用来解决一些拥有超过50,000各约束条件和200,000万个变量的大规模复杂问题。 LINDO主要有三个基本使用模式。 对于一些中小规模的问题，LINDO只要通过键盘输入就可以方便地实现交互性良好的操作与使用，如输入一个模型是相当简单方便的事情。 另外，LINDO也可以对外建文件进行处理，只要这些文件里包含有必要的命令代码和输入数据，处理后就可以生成用于报告目的的文档。 最后，你还可以自建子程序，然后直接与LINDO相结合形成一个包括你自己的代码和LINDO本身的优化库的综合程序。 好了，别说那么多了，相信大家手都痒了，赶快用一个例子来看看它是怎样使用的。 1234下一页2)输入一个模型现在让我们用例子来说明怎样输入和求解一个模型。 当我们打开LINDO后，屏幕将出现以下窗口在外面标题为LINDO的是主窗口，它包含所有的其他窗口以及所有命令菜单和工具栏。 在里面的是一个新的空白的模型窗口，等下我们就会在那里直接输入一个简单的范例模型，但在此之前，我们首先需要简明地了解一下一个LINDO模型所必须具备的基本条件和要素。 一个LINDO模型至少需要具备三个要素目标、决策变量和约束条件。 第一个基本要素是目标，顾名思义，是指一个问题解决后所要达到的目标。 有两种目标可选择MAX或MIN，也就是最大化或最小化。 在一个典型的经济问题里，你可能想使你的获利最大化或成本最小化。 因此，LINDO模型里的第一个字必须是MAX或是MIN。 然后，在其后输入的一个式子就叫做目标函数。 现在假设要使利益最大化，就需要输入MAX10X15Y，然后回车。 那么，X和Y又是什么呢？他们是第二个要素模型里的决策变量，LINDO就是通过调整这些变量的值，使你的利益达到最大化。 它们可以表示两种产品的销售量，或者两个不同公司的销售量。 在这里每单位X（产品）的毛利是10，Y的是15。 他们是变量，在LINDO里，从开始使用他们的时候起，他们就存在。 目标和变量就讲这么多。 现在让我们来看一下约束条件。 在某种意义上，约束条件是我们所建立的模型中最重要的部分，它们需要认真地考虑。 在前面的例子里，我们打算使式子10X15Y的值最大，但对X和Y能卖出多少却没有加以限制，这当然不可能，因为在现实世界里会存在诸如劳动产出和有效性等限制因素。 所以我们会把X和Y的值限制在一个合理的范围之内而不是任其随意地取值。 于是我们需要在模型的另外一行里输入SUBJECT TO字样（或者可以只输入ST），跟着在后面分行输入X10和Y12。 有一点值得注意的是，LINDO会将符号理解为小于或等于而不是绝对的小于。 如果你喜欢的话，你可以用=来代替。 上一页很好，我们已经对X和Y加以限制了。 再假设我们只有有限的劳动力，如16单位的劳动力，产品X需要一个单位而Y需要两个单位。 现在我们继续加上一条约束条件X+2Y16。 最后，我们在另一行加上END字样以表明约束条件的结束。 这时，建立后的模型应该就是下面这个样子3)求解模型下面我们可以开始求解了。 从Solve菜单选择Solve命令，或者在窗口顶部的工具栏里按Solve按钮，LINDO就会开始对模型进行编译。 首先，LINDO会检查模型是否具有数学意义以及是否符合语法要求。 如果模型不能通过这一步检查，会看到以下报错信息An errorourred duringpilation online:n（产生错误的行数），LINDO会自动跳转到发生错误的行。 我们就可以检查该行的语法错误并改正过来。 通过这一检查阶段后，LINDO就会正式开始求解，这由一个叫LINDO solver的处理器完成。 当solver初始化时，会在屏幕上显示一个状态窗口，如下图所示这个状态窗口可以显示solver的进度，下表是对各项数据/控制按钮的说明数据项/控制说明Status给出当前解决方案的状态，可能的值包括Optimal（最优的）,Feasible（可行的）,Infeasible（不可行的）,Unbounded（未定的）solver的重复次数多余或错误约束条件数量目标函数的当前值标示得到最优整数解决方案值，该项只出现在IP（整数规划）模型。 IP模型中目标的理论范围由LINDO IPsolver分生出来的整型变量个数Elapsed Timesolver启动后所经过时间Update Interval状态窗口更新周期（秒）。 你可以把这个值设成任何一个非负数，如果把它设成零的话很可能会增加求解时间。 Interrupt Solver按下该按钮，solver将立刻停止并返回当前得到的最优解。 Close按下该按钮关闭状态窗口，solver继续运行。 状态窗口可以通过选取相应命令重新打开。 Iterations InfeasibilityObjective BestIP IPBound Branches上一页1234下一页当solver完成优化过程后将会提示你是否要进行灵敏度和范围分析（都是运筹学里面的术语）。 随着运筹学学习的深入，以后我们会用到这个有用的信息的，但现在我们先按下No按钮关闭状态窗口。 现在，屏幕将会出现一个名为Reports Window的窗口。 这个窗口里显示的就是LINDO的输出结果报告，它可以显示64，000个字符的信息。 如果有需要，LINDO会从顶部开始刷除部分输出以腾出空间来显示新的输出。 如果你有一个很长的解决方案报告，需要完整地进行阅读使用，你可以把这些信息从Reports Window写到另外一个磁盘文件里，方法是选取File|Log Output命令，快捷键是F10，然后你就可以找到该文件进行阅读使用。 还是回到我们的例子，Reports Window里显示的是模型的最优解决方案，如下所示按照顺序，报告首先告诉我们LINDO进行了两次运算后求出该解；跟着是在约束条件的约束下我们可以得到的最大利润是145；这时X和Y分别取值10和3。 值得注意的是，利润似乎更高的产品Y在这里居然用得比较少，这是因为我们前面所假设的劳动力供给的限制在起作用，在这里就很好地证明了运筹学的强大作用，使我们不致于因为一些表面现象而作出错误的决策。 怎么样？能感受到运筹学和LINDO的精彩之处吗？笔者谨把此文献给有志于学习运筹学的网友们，希望能起到一个引领的作用，因为LINDO的世界实在精彩，有很多激动人心的功能还需要大家去发掘钻研。 祝大家学有所成！4)注意事项1.变量与系数间可有空格，但不能有任何运算符号如(乘号“”等）变量名由字母和数字组成,但必须以字母开头,且长度不能超过8个英文字符2.一般LINDO中不能接受括号“（）“和逗号“，“，例:400(X1+X2)需写成400X1+400X2；10,000需写成100003.变量不能出现在一个约束条件的右端4.表达式应化简，如2X1+3X2-4X1应写成-2X1+3X25.LINDO文件中常有注释间杂于各命令(MANDS)之中,前面注有!符号.例如:!This isa ment.在LINDO模型的任何地方都可以用TITLE语句对输入的模型命名,用法是在TITLE后面写出其名字,在程序中单独占一行.例TITLE EXAMPLEMODEL FORCHAPTER2特特别强调:行号,TITLE语句,和注释语句是LINDO中唯一可以使用汉字字符的地方6.LINDO中已假定所有变量非负。 可在模型的“END”语句后面用“FREE name”语句将变量vname的非负假定取消。 例:FREE X17.数值要均衡化.8.可以在模型的END语句后面用命令SUB(set upperbound)设定变量的上界,用命令SLB（set lowerbound）设定变量的下界,例:Sub x110!作用等价于x1=209简单错误的检查和避免.5)建模要求1.尽量使用实数模型,减少整数约束.2.尽量使用光滑优化数学,尽量避免使用非光滑函数.3.尽量使用线性模型.4.合理设定变量的上下界,尽可能给出变量的初始值.5.模型中使用的数量级要适当.实验一线性规划及灵敏度分析例1:线性规划及灵敏度分析求解如下线性规划问题:某家具公司制造书桌,餐桌,和椅子,所用的资源有三种:木料,木工和漆工.生产数据如表所示,若要求桌子的生产量不超过5件,问如何安排三种产品的生产可使利润最大?书桌餐桌木料86漆工42木工21.5成品单价6030解:输入模型椅子11.50.520资源总数48208Max60desks+30tables+20chairs s.t.8desks+6tables+chairs=48(注:s.t.可用subject to代替,4desks+2tables+1.5chairs=20行号可省,但最好写上,=可简写为)2desks+1.5tables+0.5chairs=8end实验任务1)求解以下规划,并做灵敏度分析Max2x-3y+4z s.t.4x+3y+2z=10-3x+5y-z=8-5x-y-z=20=y=30,x无限制输入模型Max2x-3y+4z s.t.4x+3y+2z=10(注:s.t.可用subject to代替,行号可省,但最-3x+5y-z=12好写上,=可简写为=8-5x-y-z2end freex suby20slb z300=y=30实验二整数规划说明:LINDO可用于求解整数规划,模型的输入与线性规划相似,但在end标志后需定义整形变量INT(integer),GIN(general integer).INT vname将决策变量标识为0/1型INT n将前n个变量标识为0/1型GIN vname将决策变量标识为整数型GIN n将前n个变量标识为整数型例:某班准备从5名游泳队员中选择4人组成接力队，参加学校的4*100混合泳接力比赛，5名队员4种泳姿的百米平均成绩如下表，问应如何选拔队员组成接力队？Cij甲i=1乙i=2蝶泳j=166.857.2仰泳j=275.666蛙泳j=38766.4丙i=3丁i=4戊i=5787067.874.284.669.667.47183.8自由泳j=458.6记甲、乙、丙、丁、戊分别为i=1,2,3,4,5队员,记蝶泳、仰泳、蛙泳、自由泳分别为泳姿j=1,2,3,4，记队员i的第j种泳姿的百米最好成绩为cij(s)，引入5359.457.262.40-1变量建立模型如下min f=?4151jiijijxc s.t.5,4,3,2,1?,141?jixij,4,3,2,1?,151?ijxij Xij=0,1.输入模型MIN66.8x11+75.6x12+62.4x54Subject tox11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=50Tue)x1+x2x5+x6+x7=50Wed)x1+x2+x3+x6+x7=50Thu)x1+x2+x3+x4+x7=50Fri)x1+x2+x3+x4+x5=80Sat)x2+x3+x4+x5+x6=90Sun)x3+x4+x5+x6+x7=90End Gin7实验三二次规划例求解如下二次规划问题Max98x1+277x2-xs.t.x1+x2=100x1=0为整数输入模型x1+x2100;2-0.3x1x2-2x22max=98*x1+277*x2-x12-0.3*x1*x2-2*x22;x1=2*x2;gin(x1);gin(x2);编程语言与LINDO的区别1目标函数可以不放在前面，LINGO中语句顺序并不重要。 2将目标函数的表示方式从MAX变成了MAX=；3S.T.在LINGO中不再需要4在每个系数与变量之间增加了运算符*5每行后面增加了一个分号；6以model开始，以end结束，对简单模型，这两个命令也可以省略。 编程语言的基本原则1在LINGO中，以开头的语句都是函数调用语句。 如gin(x1);gin(x2)；free(x1);常用函数调用语句一般教材上都有，大家自己找。 2在LINGO中，sets,end sets,为设定集合语句，data,end dada,为输入数据语句。 3算术运算符+，-，*，/,(求幂)逻辑运算符#AND#（与）,#OR#（或）,#NOT#（非）#EQ#（等于）,#NE#（不等于）,#GT#（大于）,#GE#（大于等于）,#LE#（小于）,#LT#（小于等于）运算结果为1（ture）,或0(false)关系运算符(即(即=)LINDO模型基本要素1集合段（sets）这部分要以sets开始，,以end sets结束,作用于定义必要的集合变量及其元素和属性。 2目标与约束段这部分实际上定义了目标函数，约束条件等，一般要用到与集合有关的求和函数SUM和循环函数FOR等，可在具体实例中体会其功能与用法。 3数据段这部分要以data开始，,以end data结束,作用于对集合的属性输入必要的常数数据。 4初始段这部分要以INIT开始，,以end INIT结束,作用于对集合的属性定义初值。 若没有该项则可省。 5计算段这部分要以CALC开始，,以end CALC结束,作用于对原始数据进行预处理，但此段有时没有实际价值。 在计算段中也可以使用集合函数。 实验四最短路问题，例在纵横交错的公路网中，货车司机希望找到一条从一个城市S到另一个城市T的最短路。 假设下图表示的是该公路网，节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离，那么，货车从城市出发到达城市，如何选择行使路线，使所经过的路程最短A1B1C1S A2T A3B2C2输入程序model:sets:cities/s,A1,A2,A3,B1,B2,C1,C2,T/:L;ROADS(cities,cities)/s,A1s,A2s,A3A1,B1A1,B2A2,B1A2,B2A3,B1,A3,B2B1,C1B1,C2B2,C1B2,C2C1,T C2,T/:D;endsets data:D=633658674678956;L=0,;enddatafor(cities(i)|i#GT#index(s):L(i)=MIN(roads(j,i):L(j)+D(j,i););end实验五矩阵对策问题在晚八点至晚九点这个时段，两家电视台在竞争100万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容，两台展播方式及可能得到的观众如表，试确定两家电视台各自的策略。 电视台1西部片电视台2连续剧45喜剧片38输入模型model:连续剧155814喜剧片605014西部片35sets:optA/1.3/:x;optB/1.3/:y;AXB(optA,optB):Ca,Cb;endsets data:Ca=351560455850381470;Cb=658540554250628630;enddata Va=sum(AXB(i,j):Ca(i,j)*x(i)*y(j);Vb=sum(AXB(i,j):Cb(i,j)*x(i)*y(j);for(optA(i):sum(optB(j):Ca(i,j)*y(j)=Va);for(optB(j):sum(optA(i):Cb(i,j)*x(i)=Vb);sum(optA:x)=1;sum(optB:y)=1;free(Va);free(Vb);end实验六运输问题设有3个产地和4个销地的运输问题，其产量，销量及单位运费如下表所示，试求总运费最少的运输方案，及总运费。 B1B2B3B4产量A1626730A2495325A3881521销量15172212方法一用lindo求解设xij为从产地Ai到销地Bj的运输量输入模型Min6x11+2x12+6x13+7x14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34s.t.!the supplyconstraints X11+x12+x13+x14=30X21+x22+x23+x24=25X31+x32+x33+x34=21!the demandconstraints X11+x21+x31=15X12+x22+x32=17X13+x23+x33=22X14+x24+x34=12End方法二用lingo求解输入模型model:sets:warehouse/1.3/:a;customer/1.4/:b;routes(warehouse,customer):c,x;endsets data:a=30,25,21;b=15,17,22,12;c=6,2,6,7,4,9,5,3,8,8,1,5;enddataobjmin=sum(routes:c*x);!the supplyconstraints;for(warehouse(i):supsum(customer(j):x(i,j)=a(i);!the demandconstraints;for(customer(j):demsum(warehouse(i):x(i,j)=b(j);end实验七指派问题设有六人做六项工作，其收益矩阵如下表人工作1工作2工作3工作4工作5工作6123456xx912-15151287-1633181110-512162721648301910117613143213注其中-表示某人无法做某项工作，可将其收益设定为一个很大的负数。 方法一用lindo求解设?否则项工作人做第当第0,1jixij则建立如下模型max?6161ijijijxc s.t.,161?jij xi=1,26,（每人做一项工作）,161?iij xj=1,2,6,（每项工作有一人去做）Xij=0或1i,j=1,2,6输入模型max20x11+15x12+16x13+5x14+4x15+7x16+17x12+15x22+33x23+12x24+8x25+6x26+9x31+12x32+18x33+16x34+30x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46-99x51+7x52+10x53+21x54+10x55+32x56-99x61-99x62-99x63+6x64+11x65+13x66s.t.!each personmust beassigned tosome jobx11+x12+x13+x14+x15+x16=1x21+x22+x23+x24+x25+x26=1x31+x32+x33+x34+x35+x36=1x41+x42+x43+x44+x45+x46=1x51+x52+x53+x54+x55+x56=1x61+x62+x63+x64+x65+x66=1!each jobmust beassigned tosome personx11+x21+x31+x41+x51+x61=1x12+x22+x32+x43+x52+x62=1x13+x23+x33+x43+x53+x63=1x14+x24+x34+x44+x54+x64=1x15+x25+x35+x45+x55+x65=1x16+x26+x36+x46+x56+x66=1end方法二用