《数学建模-数学规划模型及LINGO讲义汇总ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模-数学规划模型及LINGO讲义汇总ppt课件.ppt（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学规划模型及数学规划模型及LINGO讲义讲义 黄志勇黄志勇 河南科技大学数学与统计学院河南科技大学数学与统计学院 一一 数学规划引论数学规划引论l数数学学规规划划是是运运筹筹学学中中的的重重要要的的一一个个大大分分支支。所所研研究究的的问问题题来来源源于于军军事事、经经济济、管管理理等等领域的实际问题。领域的实际问题。l数数学学规规划划主主要要包包括括线线性性规规划划、非非线线性性规规划划、整数规划、动态规划、多目标规划等整数规划、动态规划、多目标规划等2l数学规划数学规划主要解决两个方面的问题：主要解决两个方面的问题：一、对于给定的人力、物力和财力，怎样一、对于给定的人力、物力和财力，怎样
2、才能发挥他们的最大效益；才能发挥他们的最大效益；二、对于给定的任务，怎样才能用最少的二、对于给定的任务，怎样才能用最少的人力、物力和财力去完成它。人力、物力和财力去完成它。3l从目标函数和约束条件的表达形式分为线性和非从目标函数和约束条件的表达形式分为线性和非线性；从变量形式可分为非负（正）的、自由的、线性；从变量形式可分为非负（正）的、自由的、整数的变量；从时间整数的变量；从时间 上可分为静态的和动态的；上可分为静态的和动态的；从目标函数的要求上可以分为单目标和多目标。从目标函数的要求上可以分为单目标和多目标。l而在数学建模竞赛中可能建立的模型是综合的。而在数学建模竞赛中可能建立的模型是综合
3、的。4l例例1 某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种两种产品，已知生产单位产品所需的设备台时，产品，已知生产单位产品所需的设备台时，A、B两种原料的消耗见下表：两种原料的消耗见下表：该厂每生产一件产品该厂每生产一件产品可获利可获利2元，每生产一件产品元，每生产一件产品可获利可获利3元。元。问：应如何安排生产计划使该厂获利最多问：应如何安排生产计划使该厂获利最多?产产品品设备设备1 12 28 8台台时时原料原料A A4 40 016kg16kg原料原料B B0 04 412kg12kg5l设设x1,x2表示计划期内产品表示计划期内产品、的产量。的产量。计划期内的利润计划期
4、内的利润:设备台时数的限制条件：设备台时数的限制条件：原材料原材料A、B的限制条件：的限制条件：根据实际意义：产品的产量均非负，故根据实际意义：产品的产量均非负，故6l所以该问题的数学模型为：所以该问题的数学模型为：l目标函数：目标函数：l满足约束条件：满足约束条件：7lQ:如何求解此问题的最优解？如何求解此问题的最优解？8l对于如此简单的线性规划问题可以利用图对于如此简单的线性规划问题可以利用图解法、单纯形法等求得最优解。也可以利解法、单纯形法等求得最优解。也可以利用用LINDO、LINGO等软件求解。等软件求解。9lQ：数学建模竞赛中所建模型会简单么？数学建模竞赛中所建模型会简单么？l显然
5、是不可能的。显然是不可能的。l如果建模中建立的是规划模型，那肯定是如果建模中建立的是规划模型，那肯定是综合的规划模型。综合的规划模型。10l借助上面的例子，可以有以下几种变形：借助上面的例子，可以有以下几种变形：l整数规划模型：整数规划模型：11l 非线性规划模型：非线性规划模型：12l目标规划模型：目标规划模型：13lQ:这些模型如何求解呢？这些模型如何求解呢？l我们可以利用我们可以利用LINGO软件进行求解。软件进行求解。14二二 LINGOLINGO软件介绍软件介绍l1 LINGO入门入门l当在当在windows下开始运行下开始运行LINGO系统时，会得系统时，会得到类似下面的一个窗口：
6、到类似下面的一个窗口：15l外层是主框架窗口，包含了所有菜单命令外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为窗口之下。在主窗口内的标题为LINGO Model LINGO1的窗口是的窗口是LINGO的默认的默认模型窗口，建立的模型都都要在该窗口内模型窗口，建立的模型都都要在该窗口内编码实现。编码实现。16l下面举两个例子下面举两个例子l例例1.1求解前面介绍的求解前面介绍的LP问题问题 17l在模型窗口中输入如下代码：在模型窗口中输入如下代码：max=2*x1+3*x2;x1+2*x2=8;4*x1=1
7、6;4*x2=12;然后点击工具条上的按钮然后点击工具条上的按钮 即可。即可。或者按或者按ctr+s 18l例例1.2 使用使用LINGO软件计算软件计算6个发点个发点8个收个收点的最小费用运输问题。产销单位运价表点的最小费用运输问题。产销单位运价表如下所示：如下所示：1920l使用使用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);21for(cd(i)sum(xd(j):x(i,
8、j)=a(i);data:a=60 55 51 43 41 52;b=35 37 22 32 41 32 43 38;c=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddataend222 LINGO中的集中的集l集是集是LINGOLINGO建模语言的基础，是程序设计建模语言的基础，是程序设计最强有力的基本构件。借助于集，能够用最强有力的基本构件。借助于集，能够用一个单一的、长的、简明的复合公式表示一个单一的、长的、简明的复合公式表示一系列相似
9、的约束，从而可以快速方便地一系列相似的约束，从而可以快速方便地表达规模较大的模型。表达规模较大的模型。23l集是一群相联系的对象，这些对象也称为集的集是一群相联系的对象，这些对象也称为集的成员成员。一个集可能是一系列产品、卡车或雇员。一个集可能是一系列产品、卡车或雇员。每个集成员可能有一个或多个与之有关联的特每个集成员可能有一个或多个与之有关联的特征，我们把这些特征称为征，我们把这些特征称为属性属性。属性值可以预。属性值可以预先给定，也可以是未知的，有待于先给定，也可以是未知的，有待于LINGO求解。求解。例如，产品集中的每个产品可以有一个价格属例如，产品集中的每个产品可以有一个价格属性；卡车
10、集中的每辆卡车可以有一个牵引力属性；卡车集中的每辆卡车可以有一个牵引力属性；雇员集中的每位雇员可以有一个薪水属性，性；雇员集中的每位雇员可以有一个薪水属性，也可以有一个生日属性等等。也可以有一个生日属性等等。24lLINGO有两种类型的集：原始集有两种类型的集：原始集(primitiveset)和派生集和派生集(derived set)。l一个原始集是由一些最基本的对象组成的。一个原始集是由一些最基本的对象组成的。l一个派生集是用一个或多个其它集来定义一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存的，也就是说，它的成员来自于其它已存在的集。在的集。25l集部分集部分是
11、LINGO模型的一个可选部分。在LINGO模型中使用集之前，必须在集部分事先定义。集部分以关键字“sets:”开始，以“endsets”结束。一个模型可以没有集部分，或有一个简单的集部分，或有多个集部分。一个集部分可以放置于模型的任何地方，但是一个集及其属性在模型约束中被引用之前必须定义它们。26l如何定义原始集如何定义原始集为了定义一个原始集，必须详细声明：为了定义一个原始集，必须详细声明：集的名字集的名字 可选，集的成员可选，集的成员 可选，集成员的属性可选，集成员的属性定义一个原始集，用下面的语法：定义一个原始集，用下面的语法：setname/member_list/:attribute
12、_list;注意：用注意：用“”表示该部分内容可选。表示该部分内容可选。27lSetname是你选择的来标记集的名字，最是你选择的来标记集的名字，最好具有较强的可读性。集名字必须严格符好具有较强的可读性。集名字必须严格符合标准命名规则：以拉丁字母或下划线合标准命名规则：以拉丁字母或下划线（_ _）为首字符，其后由拉丁字母（）为首字符，其后由拉丁字母（A AZ Z）、下划线、阿拉伯数字（）、下划线、阿拉伯数字（0 0，1 1，9 9）组成的总长度不超过）组成的总长度不超过3232个字符的字符个字符的字符串，且不区分大小写。串，且不区分大小写。28lMember_list是集成员列表。如果集成员放
13、是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定集定义中，那么可以在随后的数据部分定义它们。义它们。l 当显式罗列成员时，必须为每个成员当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。搁开，允许混合使用。29l例例2.1可以定义一个名为students的原始集，它具有成员John、Jill、Rose和Mike，属性有sex和age：sets:students/Jo
14、hn Jill,Rose Mike/:sex,age;endsets30l 当隐式罗列成员时，不必罗列出每个集当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法：成员。可采用如下语法：setname/member1.memberN/:attribute_list;这里的这里的member1member1是集的第一个成员名，是集的第一个成员名，memberNmemberN是集的最末一个成员名。是集的最末一个成员名。LINGOLINGO将将自动产生中间的所有成员名。自动产生中间的所有成员名。LINGOLINGO也接受也接受一些特定的首成员名和末成员名，用于创一些特定的首成员名和末成员名，用于创
15、建一些特殊的集。列表如下：建一些特殊的集。列表如下：31隐隐式成式成员员列表格式列表格式示例示例所所产产生集成生集成员员1.n1.n1.51.51,2,3,4,51,2,3,4,5StringM.StringNStringM.StringNCar2.car14Car2.car14Car2,Car3,Car4,Car14Car2,Car3,Car4,Car14DayM.DayNDayM.DayNMon.FriMon.FriMon,Tue,Wed,Thu,FriMon,Tue,Wed,Thu,FriMonthM.MonthNMonthM.MonthNOct.JanOct.JanOct,Nov,De
16、c,JanOct,Nov,Dec,JanMonthYearM.MonthYearMonthYearM.MonthYearN NOct2001.Jan2002Oct2001.Jan2002Oct2001,Nov2001,Dec2001,Oct2001,Nov2001,Dec2001,Jan2002Jan200232l集成员不放在集定义中，而在随后的数据部分数据部分来定义。例例2.2sets:students:sex,age;endsetsdata:students,sex,age=John 1 16 Jill 0 14 Rose 0 17 Mike 1 13;enddata33l如何定义派生集如
17、何定义派生集为了定义一个派生集，必须详细声明：为了定义一个派生集，必须详细声明：集的名字集的名字 父集的名字父集的名字 可选，集成员可选，集成员 可选，集成员的属性可选，集成员的属性可用下面的语法定义一个派生集：可用下面的语法定义一个派生集：setname(parent_set_list)/member_list/:attribute_list;34lsetname是集的名字。是集的名字。parent_set_list是已是已定义的集的列表，多个时必须用逗号隔开。定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么如果没有指定成员列表，那么LINGOLINGO会自会自动创建父集成员
18、的所有组合作为派生集的动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也成员。派生集的父集既可以是原始集，也可以是其它的派生集。可以是其它的派生集。35l例例2.3sets:product/A B/;machine/M N/;week/1.2/;allowed(product,machine,week):x;endsets36l成员列表被忽略时，派生集成员由父集成成员列表被忽略时，派生集成员由父集成员所有的组合构成，这样的派生集成为员所有的组合构成，这样的派生集成为稠稠密集密集。l如果限制派生集的成员，使它成为父集成如果限制派生集的成员，使它成为父集成员所有组合构成的集合
19、的一个子集，这样员所有组合构成的集合的一个子集，这样的派生集成为的派生集成为稀疏集稀疏集。37l如何生成如何生成稀疏集稀疏集？l有两种方式生成：有两种方式生成：显式罗列；显式罗列；设置成设置成员资格过滤器。员资格过滤器。使用前面的例子，显式罗列派生集的成员：使用前面的例子，显式罗列派生集的成员：allowed(product,machine,week)/A M 1,A N 2,B N 1/;38l如果需要生成一个大的、稀疏的集，那么如果需要生成一个大的、稀疏的集，那么显式罗列就很讨厌。幸运地是许多稀疏集显式罗列就很讨厌。幸运地是许多稀疏集的成员都满足一些条件以和非成员相区分。的成员都满足一些条
20、件以和非成员相区分。我们可以把这些逻辑条件看作我们可以把这些逻辑条件看作过滤器过滤器，在，在LINGO生成派生集的成员时把使逻辑条件生成派生集的成员时把使逻辑条件为假的成员从稠密集中过滤掉。为假的成员从稠密集中过滤掉。39l例例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;frien
21、d=0.30.50.60.4;enddata40l用竖线（用竖线（|）来标记一个成员资格过滤器）来标记一个成员资格过滤器的开始。的开始。#eq#是逻辑运算符，用来判断是是逻辑运算符，用来判断是否否“相等相等”，可参考，可参考4.&1可看作派生集可看作派生集的第的第1个原始父集的索引，它取遍该原始个原始父集的索引，它取遍该原始父集的所有成员；父集的所有成员；&2可看作派生集的第可看作派生集的第2 个原始父集的索引，它取遍该原始父集的个原始父集的索引，它取遍该原始父集的所有成员；所有成员；&3，&4，以此类推。，以此类推。41l注意如果派生集注意如果派生集B的父集是另外的派生集的父集是另外的派生集
22、A，那么上面所说的原始父集是集，那么上面所说的原始父集是集A向前向前回溯到最终的原始集，其顺序保持不变，回溯到最终的原始集，其顺序保持不变，并且派生集并且派生集A的过滤器对派生集的过滤器对派生集B仍然有仍然有效。因此，派生集的索引个数是最终原始效。因此，派生集的索引个数是最终原始父集的个数，索引的取值是从原始父集到父集的个数，索引的取值是从原始父集到当前派生集所作限制的总和。当前派生集所作限制的总和。42l总的来说，总的来说，LINGO可识别的集只有两种类可识别的集只有两种类型：原始集和派生集。型：原始集和派生集。l不同集类型的关系见下图。不同集类型的关系见下图。集集稠密集稠密集原始集原始集显
23、式罗显式罗列列稀疏集稀疏集过滤器过滤器派生集派生集LINGO集类型433 模型的数据部分和初始部分模型的数据部分和初始部分l在处理模型的数据时，需要为集指派一些在处理模型的数据时，需要为集指派一些成员并且在成员并且在LINGOLINGO求解模型之前为集的某些求解模型之前为集的某些属性指定值。为此，属性指定值。为此，LINGOLINGO为用户提供了两为用户提供了两个可选部分：输入集成员和数据的个可选部分：输入集成员和数据的数据部数据部分分（Data SectionData Section）和为决策变量设置初）和为决策变量设置初始值的始值的初始部分初始部分（InitSectionInitSecti
24、on）。）。44l3.1 模型的数据部分模型的数据部分 数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。其语法如下：object_list=value_list;45l例例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）实现同样的功能。46l例例3.2sets:set1/A,B,C/:X,Y;endsetsdata:X,
25、Y=1 4 2 5 3 6;enddata47l实时数据处理实时数据处理 在某些情况，对于模型中的某些数据并不在某些情况，对于模型中的某些数据并不是定值。譬如模型中有一个通货膨胀率的是定值。譬如模型中有一个通货膨胀率的参数，我们想在参数，我们想在2%至至6%范围内，对不同范围内，对不同的值求解模型，来观察模型的结果对通货的值求解模型，来观察模型的结果对通货膨胀的依赖有多么敏感。我们把这种情况膨胀的依赖有多么敏感。我们把这种情况称为实时数据处理（称为实时数据处理（what if analysis）。）。LINGO有一个特征可方便地做到这件事。有一个特征可方便地做到这件事。在本该放数的地方输入一个
26、问号（在本该放数的地方输入一个问号（?）。）。48l例例3.5data:interest_rate,inflation_rate=.085?;enddata每一次求解模型时，LINGO都会提示为参数inflation_rate输入一个值。在WINDOWS操作系统下，将会接收到一个类似下面的对话框：49l直接输入一个值再点击直接输入一个值再点击OK按钮，按钮，LINGO就会把就会把输入的值指定给输入的值指定给inflation_rate，然后继续求解模，然后继续求解模型。型。50l指定属性为一个值指定属性为一个值可以在数据声明的右边输入一个值来把所有的可以在数据声明的右边输入一个值来把所有的成员
27、的该属性指定为一个值。看下面的例子。成员的该属性指定为一个值。看下面的例子。例例3.6sets:days/MO,TU,WE,TH,FR,SA,SU/:needs;endsetsdata:needs=20;enddata51l例例3.7sets:days/MO,TU,WE,TH,FR,SA,SU/:needs,cost;endsetsdata:needs cost=20 100;enddata52l数据部分的未知数值数据部分的未知数值l例例3.8sets:years/1.5/:capacity;endsetsdata:capacity=,34,20,;enddata属性属性capacity的第的
28、第2个和第个和第3个值分别为个值分别为34和和20，其余的未知。其余的未知。53l模型的初始部分模型的初始部分 对实际问题的建模时，初始部分并不起到对实际问题的建模时，初始部分并不起到描述模型的作用，在初始部分输入的值仅描述模型的作用，在初始部分输入的值仅被被LINGO求解器当作初始点来用，并且仅求解器当作初始点来用，并且仅仅对仅对非线性模型非线性模型有用。一个初始部分以有用。一个初始部分以“init:”开始，以开始，以“endinit”结束。结束。54l例例3.9init:X,Y=0,.1;endinitY=log(X);X2+Y2=1;好的初始点会减少模型的求解时间。好的初始点会减少模型的
29、求解时间。554 LINGO函数函数lLINGO有9种类型的函数：1基本运算符：包括算术运算符、逻辑运算符和关系运算符2数学函数：三角函数和常规的数学函数3金融函数：LINGO提供的两种金融函数4概率函数：LINGO提供了大量概率相关的函数5变量界定函数：这类函数用来定义变量的取值范围6集操作函数：这类函数为对集的操作提供帮助7集循环函数：遍历集的元素，执行一定的操作的函数8数据输入输出函数：这类函数允许模型和外部数据源相联系，进行数据的输入输出9辅助函数：各种杂类函数56l基本运算符基本运算符l算术运算符算术运算符算术运算符是针对数值进行操作的。算术运算符是针对数值进行操作的。LINGO提提
30、供了供了5种二元运算符：种二元运算符：乘方乘方乘乘除除加加减减57lLINGOLINGO唯一的一元算术运算符是取反函数唯一的一元算术运算符是取反函数“”。l这些运算符的优先级由高到底为：这些运算符的优先级由高到底为：高高（取反）（取反）低低l例例4.1 4.1 算术运算符示例算术运算符示例。253，(2 4)5 58l逻辑运算符逻辑运算符LINGOLINGO具有种逻辑运算符：具有种逻辑运算符：#not#not#否定该操作数的逻辑值，否定该操作数的逻辑值，notnot是一个一元运算符是一个一元运算符#eqeq#若两个运算数相等，则为若两个运算数相等，则为truetrue；否则为；否则为flase
31、flase#nene#若两个运算符不相等，则为若两个运算符不相等，则为truetrue；否则为；否则为flaseflase#gtgt#若左边的运算符严格大于右边的运算符，则为若左边的运算符严格大于右边的运算符，则为truetrue；否则为否则为flaseflase#gege#若左边的运算符大于或等于右边的运算符，则为若左边的运算符大于或等于右边的运算符，则为 truetrue；否则为；否则为flaseflase59#ltlt#若左边的运算符严格小于右边的运若左边的运算符严格小于右边的运算符，则为算符，则为truetrue；否则为；否则为flaseflase#le#le#若左边的运算符小于或等于
32、右边的若左边的运算符小于或等于右边的运算符，则为运算符，则为truetrue；否则为；否则为flaseflase#and#and#仅当两个参数都为仅当两个参数都为truetrue时，结果为时，结果为truetrue；否则为；否则为flaseflase#or#or#仅当两个参数都为仅当两个参数都为falsefalse时，结果时，结果为为falsefalse；否则为；否则为truetrue60l这些运算符的优先级由高到低为：这些运算符的优先级由高到低为：高高#not#eq#ne#gt#ge#lt#le#低低#and#or#例例4.2 4.2 逻辑运算符示例逻辑运算符示例2#gt#3#and#4#g
33、t#2，其结果为假（其结果为假（0 0）61l关系运算符关系运算符LINGO有三种关系运算符：“=”、“=”。LINGO中还能用“”表示大于等于关系。LINGO并不支持严格小于和严格大于关系运算符。如果需要严格小于和严格大于关系，比如让A严格小于B：AB，那么可以把它变成如下的小于等于表达式：A+=B，这里是一个小的正数，它的值依赖于模型中A小于B多少才算不等。62l数学函数数学函数LINGO提供了大量的标准数学函数：提供了大量的标准数学函数：abs(x)返回返回x的绝对值的绝对值sin(x)返回返回x的正弦值，的正弦值，x采用弧度制采用弧度制cos(x)返回返回x的余弦值的余弦值tan(x)返回返回x的正切值的正切值exp(x)返回常数返回常数e的的x次方次方log(x)返回返回x的自然对数的自然对数63lgm(x)返回返回x的的gamma函数的自然对数函数的自然对数sign(x)如果如果x=0时，时，返回不超过返回不超过x的最大整数；当的最大整数；当x0时，返回不低时，返回不低于于x的最大整数。的最大整数。smax(x1,x2,xn)返回返回x1，x2，xn中的中的最大值最大值smin(x1,x2,xn)返回返回x1，x2，xn中的中的最小值最小值6465666768697071727374757677787980