数学建模-数学规划模型及LINGO讲义汇总

数学规划模型及LINGO讲义黄志勇河南科技大学数学与统计学院[e-mail]2一数学规划引论数学规划是运筹学中的重要的一个大分支。所研究的问题来源于军事、经济、管理等领域的实际问题。数学规划主要包括线性规划、非线性规划、整数规划、动态规划、多目标规划等3数学规划主要解决两个方面的问题：一、对于给定的人力、物力和财力，怎样才能发挥他们的最大效益；二、对于给定的任务，怎样才能用最少的人力、物力和财力去完成它。4从目标函数和约束条件的表达形式分为线性和非线性；从变量形式可分为非负（正）的、自由的、整数的变量；从时间上可分为静态的和动态的；从目标函数的要求上可以分为单目标和多目标。而在数学建模竞赛中可能建立的模型是综合的。5例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时，A、B两种原料的消耗见下表：该厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元。问：应如何安排生产计划使该厂获利最多?产品ⅠⅡ设备128台时原料A4016kg原料B0412kg6设x1,x2表示计划期内产品Ⅰ、Ⅱ的产量。计划期内的利润:设备台时数的限制条件：原材料A、B的限制条件：根据实际意义：产品的产量均非负，故2132xxZ8221xx12416421xx0,021xx7所以该问题的数学模型为：目标函数：满足约束条件：2132maxxxZ0,12416482212121xxxxxx8Q:如何求解此问题的最优解？9对于如此简单的线性规划问题可以利用图解法、单纯形法等求得最优解。也可以利用LINDO、LINGO等软件求解。10Q：数学建模竞赛中所建模型会简单么？显然是不可能的。如果建模中建立的是规划模型，那肯定是综合的规划模型。11借助上面的例子，可以有以下几种变形：整数规划模型：12121212max2328416412,0Zxxxxxxxx，且取整12非线性规划模型：212121212max2328416412,0Zxxxxxxxx13目标规划模型：1122233121112223312min()(3)()28416412,0,,0,1,2,3iiPdPddPdxxddxddxddxxddi14Q:这些模型如何求解呢？我们可以利用LINGO软件进行求解。15二LINGO软件介绍§1LINGO入门当在windows下开始运行LINGO系统时，会得到类似下面的一个窗口：16外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGOModel–LINGO1的窗口是LINGO的默认模型窗口，建立的模型都都要在该窗口内编码实现。17下面举两个例子例1.1求解前面介绍的LP问题12121212max2328416412,0Zxxxxxxxx18在模型窗口中输入如下代码：max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;然后点击工具条上的按钮即可。或者按ctr+s19例1.2使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价表如下所示：20B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量353722324132433821使用LINGO软件，编制程序如下：model:sets:cd/1..6/:a;xd/1..8/:b;links(cd,xd):c,x;endsetsmin=@sum(links:c*x);@for(xd(j):@sum(cd(i):x(i,j))=b(j));22@for(cd(i)@sum(xd(j):x(i,j))=a(i));data:a=605551434152;b=3537223241324338;c=626742954953858252197433767392712395726555228143;enddataend23§2LINGO中的集集是LINGO建模语言的基础，是程序设计最强有力的基本构件。借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型。24集是一群相联系的对象，这些对象也称为集的成员。一个集可能是一系列产品、卡车或雇员。每个集成员可能有一个或多个与之有关联的特征，我们把这些特征称为属性。属性值可以预先给定，也可以是未知的，有待于LINGO求解。例如，产品集中的每个产品可以有一个价格属性；卡车集中的每辆卡车可以有一个牵引力属性；雇员集中的每位雇员可以有一个薪水属性，也可以有一个生日属性等等。25LINGO有两种类型的集：原始集(primitiveset)和派生集(derivedset)。一个原始集是由一些最基本的对象组成的。一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。26集部分是LINGO模型的一个可选部分。在LINGO模型中使用集之前，必须在集部分事先定义。集部分以关键字“sets:”开始，以“endsets”结束。一个模型可以没有集部分，或有一个简单的集部分，或有多个集部分。一个集部分可以放置于模型的任何地方，但是一个集及其属性在模型约束中被引用之前必须定义它们。27如何定义原始集为了定义一个原始集，必须详细声明：·集的名字·可选，集的成员·可选，集成员的属性定义一个原始集，用下面的语法：setname[/member_list/][:attribute_list];注意：用“[]”表示该部分内容可选。28Setname是你选择的来标记集的名字，最好具有较强的可读性。集名字必须严格符合标准命名规则：以拉丁字母或下划线（_）为首字符，其后由拉丁字母（A—Z）、下划线、阿拉伯数字（0，1，…，9）组成的总长度不超过32个字符的字符串，且不区分大小写。29Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们。①当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。30例2.1可以定义一个名为students的原始集，它具有成员John、Jill、Rose和Mike，属性有sex和age：sets:students/JohnJill,RoseMike/:sex,age;endsets31②当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法：setname/member1..memberN/[:attribute_list];这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名，用于创建一些特殊的集。列表如下：32隐式成员列表格式示例所产生集成员1..n1..51,2,3,4,5StringM..StringNCar2..car14Car2,Car3,Car4,…,Car14DayM..DayNMon..FriMon,Tue,Wed,Thu,FriMonthM..MonthNOct..JanOct,Nov,Dec,JanMonthYearM..MonthYearNOct2001..Jan2002Oct2001,Nov2001,Dec2001,Jan200233③集成员不放在集定义中，而在随后的数据部分来定义。例2.2sets:students:sex,age;endsetsdata:students,sex,age=John116Jill014Rose017Mike113;enddata34如何定义派生集为了定义一个派生集，必须详细声明：·集的名字·父集的名字·可选，集成员·可选，集成员的属性可用下面的语法定义一个派生集：setname(parent_set_list)[/member_list/][:attribute_list];35setname是集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也可以是其它的派生集。36例2.3sets:product/AB/;machine/MN/;week/1..2/;allowed(product,machine,week):x;endsets37成员列表被忽略时，派生集成员由父集成员所有的组合构成，这样的派生集成为稠密集。如果限制派生集的成员，使它成为父集成员所有组合构成的集合的一个子集，这样的派生集成为稀疏集。38如何生成稀疏集？有两种方式生成：①显式罗列；②设置成员资格过滤器。使用前面的例子，显式罗列派生集的成员：allowed(product,machine,week)/AM1,AN2,BN1/;39如果需要生成一个大的、稀疏的集，那么显式罗列就很讨厌。幸运地是许多稀疏集的成员都满足一些条件以和非成员相区分。我们可以把这些逻辑条件看作过滤器，在LINGO生成派生集的成员时把使逻辑条件为假的成员从稠密集中过滤掉。40例2.4sets:students/John,Jill,Rose,Mike/:sex,age;linkmf(students,students)|sex(&1)#eq#1#and#sex(&2)#eq#0:friend;linkmf2(linkmf)|friend(&1,&2)#ge#0.5:x;endsetsdata:sex,age=116014017113;friend=0.30.50.60.4;enddata41用竖线（|）来标记一个成员资格过滤器的开始。#eq#是逻辑运算符，用来判断是否“相等”，可参考§4.&1可看作派生集的第1个原始父集的索引，它取遍该原始父集的所有成员；&2可看作派生集的第2个原始父集的索引，它取遍该原始父集的所有成员；&3，&4，……，以此类推。42注意如果派生集B的父集是另外的派生集A，那么上面所说的原始父集是集A向前回溯到最终的原始集，其顺序保持不变，并且派生集A的过滤器对派生集B仍然有效。因此，派生集的索引个数是最终原始父集的个数，索引的取值是从原始父集到当前派生集所作限制的总和。43总的来说，LINGO可识别的集只有两种类型：原始集和派生集。不同集类型的关系见下图。集稠密集原始集显式罗列稀疏集过滤器派生集LINGO集类型44§3模型的数据部分和初始部分在处理模型的数据时，需要为集指派一些成员并且在LINGO求解模型之前为集的某些属性指定值。为此，LINGO为用户提供了两个可选部分：输入集成员和数据的数据部分（DataSection）和为决策变量设置初始值的初始部分（InitSection）。45§3.1模型的数据部分数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。其语法如下：object_list=value_list;46例3.1sets:set1/A,B,C/:X,Y;endsetsdata:X=1,2,3;Y=4,5,6;enddata在集set1中定义了两个属性X和Y。X的三个值是1、2和3，Y的三个值是4、5和6。也可采用如下例子中的复合数据声明（datastatement）实现同样的功能。47例3.2sets:set1/A,B,C/:X,Y;endsetsdata:X,Y=142536;enddata48实时数据处理在某些情况，对于模型中的某些数据并不是定值。譬如模型中有一个通