数学建模】数独模型Lingo求解程序（精品推荐 免费分享）.doc

《数学建模】数独模型Lingo求解程序（精品推荐 免费分享）.doc》由会员分享，可在线阅读，更多相关《数学建模】数独模型Lingo求解程序（精品推荐 免费分享）.doc（24页珍藏版）》请在三一办公上搜索。

1、第2章 数独模型Lingo求解程序 本章信息指数理论性 应用性 趣味性 创新性 本章选择了LINGO建模语言,对数独模型编写了Lingo求解程序。2-1 Lingo简介 LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。 2.1.1 LINGO中的集 对实际问题建模的时候，总会遇到一群或多群相联系的对象，比如工厂、消费者群体、交通工具和雇工等等。LINGO允许把这些相联系的对象聚合成集（sets）。一旦把对象聚合成集，就可以利用集来最大限度的发挥LINGO建模语言的优势。集是L

2、INGO建模语言的基础，是程序设计最强有力的基本构件。借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型。LINGO有两种类型的集：原始集(primitive set)和派生集(derived set)。 2.1.1.1 定义原始集 为了定义一个原始集，必须定义：集的名字、集的成员（可选）和集成员的属性（可选）， 定义一个原始集，用下面的语法： setname/member_list/:attribute_list; 注意：用“”表示该部分内容可选。Setname是你选择的来标记集的名字， 最好具有较强的可读性。集名字必须严格符合标准命名

3、规则：以拉丁字母或下划线（_）为首字符，其后由拉丁字母（AZ）、下划线、阿拉伯数字（0，1，9）组成的总长度不超过32个字符的字符串，且不区分大小写。 注意：该命名规则同样适用于集成员名和属性名等的命名。 比如number/1.9/;定义一个原始集number，由于在后续的程序中不直接使用该集，故省略了后面的属性，该集有9个成员，由于成员的规律性，可以采用隐式罗列法来表示，即不必罗列出每个集成员。具体语法如下： setname/member1.memberN/: attribute_list; 这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间

4、的所有成员名。 2.1.1.2 定义派生集 为了定义一个派生集，必须定义：集的名字、父集的名字、集成员（可选）和集成员的属性（可选）。定义一个派生集，用下面的语法： setname(parent_set_list)/member_list/:attribute_list;setname是集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也可以是其它的派生集。 比如shudu(line,col):a;定义了一个派生集，它没有指定成员列表，那么LINGO会自

5、动创建父集line和col成员的所有组合作为派生集shudu的成员。A是该派生集的一个属性。 2.1.2 LINGO中的数据 在处理模型的数据时，需要为集指派一些成员并且在LINGO求解模型之前为集的某些属性指定值。为此，LINGO为用户提供了两个可选部分：输入集成员和数据的数据部分（Data Section）和为决策变量设置初始值的初始部分（Init Section）。比如：data:! 键盘输入;a=？;enddata 以data:开始，以enddata结束，语句前加了!后成为说明语句。LINGO规定，每个以分号“；”结束。 2.1.3 LINGO函数 LINGO有9种类型的函数：基本运算

6、符、数学函数、金融函数、概率函数、变量界定函数、集操作函数、集循环函数、数据输入输出函数、辅助函数。 2.1.3.1 基本运算符 这些运算符是非常基本的，甚至可以不认为它们是一类函数。事实上，在LINGO中它们是非常重要的。 2.1.3.1.1 算术运算符 算术运算符是针对数值进行操作的。LINGO提供了5种二元运算符：乘方、乘、除、加、减。LINGO唯一的一元算术运算符是取反函数“”。这些运算符的优先级由高到底为：（取反）、。运算符的运算次序为从左到右按优先级高低来执行。运算的次序可以用圆括号“（）”来改变。 2.1.3.1.2 逻辑运算符 在LINGO中，逻辑运算符主要用于集循环函数的条件

7、表达式中，来控制在函数中哪些集成员被包含，哪些被排斥。在创建稀疏集时用在成员资格过滤器中。LINGO具有种逻辑运算符： #not# 否定该操作数的逻辑值，not是一个一元运算符 #eq#若两个运算数相等，则为true；否则为flase #ne# 若两个运算符不相等，则为true；否则为flase #gt# 若左边的运算符严格大于右边的运算符，则为true；否则为flase #ge# 若左边的运算符大于或等于右边的运算符，则为true；否则为flase #lt# 若左边的运算符严格小于右边的运算符，则为true；否则为flase #le# 若左边的运算符小于或等于右边的运算符，则为true；否则

8、为flase #and# 仅当两个参数都为true时，结果为true；否则为flase #or# 仅当两个参数都为false时，结果为false；否则为true 这些运算符的优先级由高到低为： #not# #eq# #ne# #gt# #ge# #lt# #le# #and# #or# 2.1.3.1.3 关系运算符 在LINGO中，关系运算符主要是被用在模型中，来指定一个表达式的左边是否等于、小于等于、或者大于等于右边，形成模型的一个约束条件。关系运算符与逻辑运算符#eq#、#le#、#ge#截然不同，前者是模型中该关系运算符所指定关系的为真描述，而后者仅仅判断一个该关系是否被满足：满足为真

9、，不满足为假。 LINGO有三种关系运算符：“=”、“=”。LINGO中还能用“”表示大于等于关系。LINGO并不支持严格小于和严格大于关系运算符。 2.1.3.2 数学函数 LINGO提供了大量的标准数学函数： abs(x) 返回x的绝对值 sin(x) 返回x的正弦值，x采用弧度制 cos(x) 返回x的余弦值 tan(x) 返回x的正切值 exp(x) 返回常数e的x次方 log(x) 返回x的自然对数 lgm(x) 返回x的gamma函数的自然对数 sign(x) 如果x=0时，返回不超过x的最大整数；当x=0时，返回不超过x的最大整数；当x=0时，返回不超过x的最大整数；当x0时，返

10、回不低于x的最大整数。则数独数学模型Lingo求解程序如下：model:sets:number/1.9/;line/1.9/;wline/1.6/;col/1.9/;wcol/1.6/;gong/1.9/;wgong/1.4/;shudu(line,col):a;link(line,col,number):x;wlink(wline,wcol,number):y;endsetsdata:! 键盘输入;a=？;enddatamin=sum(link:x);for(shudu(i,j) | a(i,j) #ge# 1:x(i,j,a(i,j)=1); for(line(i):for(col(j):

11、sum(number(k):x(i,j,k)=1);for(line(i):for(number(k):sum(col(j):x(i,j,k)=1);for(col(j):for(number(k):sum(line(i):x(i,j,k)=1);for(gong(m):for(number(k):sum(link(i,j,k)| 3*floor(i-1)/3)+floor(j-1)/3)+1 #eq# m:x(i,j,k)=1);for(link(i,j,k):bin(x(i,j,k);end 例3861394652453189891在窗口数独数学模型Lingo求解程序中输入:a=0 0 0

12、 8 0 0 6 0 00 0 0 0 0 0 1 0 00 0 3 0 0 0 9 4 06 0 0 0 5 0 0 0 20 0 0 4 0 0 0 0 00 0 0 0 0 0 0 0 53 1 8 0 0 0 0 0 00 0 9 0 0 0 0 8 00 0 0 9 0 1 0 0 0;可得：921834657486795123753216948694158372135427896872369415318542769249673581567981234 2-5 三环六扇的环形数独的Lingo求解程序针对1.6.1的Lingo求解程序model:sets:ring/1.3/;fan/1

13、.6/;number/1.6/;link(ring,fan,number):x;endsets!输入已知数字;min=sum(link:x);for(ring(I):for(fan(j):sum(number(k):x(i,j,k)=1);for(fan(j)|j#le#5:for(number(k):sum(ring(i):x(i,j,k)+sum(ring(i):x(i,(j+1),k)=1);for(ring(i):for(number(k):sum(fan(j):x(i,j,k)=1);for(link:bin(x);end例4即已知： x(1,3,4)=1;x(1,4,2)=1;x(

14、3,5,5)=1;x(1,6,3)=1;x(3,6,6)=1;在求解环形数独的Lingo求解程序中输入上面的已知条件可得Lingo的运行结果： 2-6 四环八扇环的环形数独的Lingo求解程序四环八扇的环形数独是在32个空格里填写1至8的数字，要求要求每环的8个格子数字互不相同，每两个相邻扇区的8个格子数字互不相同。下面是四环八扇环的环形数独的Lingo求解程序。 model: sets: ring/1.4/; fan/1.8/; number/1.8/; link(ring,fan,number):x; endsets !输入已知数字; min=sum(link:x); for(ring(I

15、):for(fan(j):sum(number(k):x(i,j,k)=1);for(fan(j)|j#le#5:for(number(k):sum(ring(i):x(i,j,k)+sum(ring(i):x(i,(j+1),k)=1); for(ring(i):for(number(k):sum(fan(j):x(i,j,k)=1); for(link:bin(x); end例5 即在求解四环八扇环的环形数独的Lingo求解程序输入下面的已知条件：x(2,1,3)=1;x(1,2,1)=1;x(2,2,6)=1;x(1,3,2)=1;x(2,3,8)=1;x(2,4,5)=1;x(1,6,

16、5)=1;x(4,6,4)=1;x(1,7,7)=1;x(4,7,3)=1; 根据运行程序可得结果可得： 本章小结范围理论性程序设计应用性Lingo 编程语言趣味性数独创新性数独模型Lingo求解2-7作业1、设计两主对角线九宫数独（主对角线上的数字互不相同）的Lingo求解程序，并求解下面的九条主对角线的918双胞胎数独。1823952871543939574132974882541278392、设计312双胞胎数独的Lingo求解程序，并求解下面的312双胞胎数独。 423563、设计九条主对角线的918双胞胎数独的Lingo求解程序，并求解下面的九条主对角线的918双胞胎数独。2738945932148665178962145932648715192738 4、设计十六宫数独的Lingo求解程序，并求解下面的十六宫数独。1216149581114141213710151511581291191613671611443101210168111315415121378495961211348921261251615179210111661211615793131610271514711513316159651424103451211275、设计程序，使得