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

第2章 数独模型Lingo求解程序 本章信息指数理论性 应用性 趣味性 创新性 本章选择了LINGO建模语言,对数独模型编写了Lingo求解程序。2-1 Lingo简介 LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。 2.1.1 LINGO中的集 对实际问题建模的时候，总会遇到一群或多群相联系的对象，比如工厂、消费者群体、交通工具和雇工等等。LINGO允许把这些相联系的对象聚合成集（sets）。一旦把对象聚合成集，就可以利用集来最大限度的发挥LINGO建模语言的优势。集是LINGO建模语言的基础，是程序设计最强有力的基本构件。借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型。LINGO有两种类型的集：原始集(primitive set)和派生集(derived set)。 2.1.1.1 定义原始集 为了定义一个原始集，必须定义：集的名字、集的成员（可选）和集成员的属性（可选）， 定义一个原始集，用下面的语法： setname/member_list/:attribute_list; 注意：用“”表示该部分内容可选。Setname是你选择的来标记集的名字， 最好具有较强的可读性。集名字必须严格符合标准命名规则：以拉丁字母或下划线（_）为首字符，其后由拉丁字母（AZ）、下划线、阿拉伯数字（0，1，9）组成的总长度不超过32个字符的字符串，且不区分大小写。 注意：该命名规则同样适用于集成员名和属性名等的命名。 比如number/1.9/;定义一个原始集number，由于在后续的程序中不直接使用该集，故省略了后面的属性，该集有9个成员，由于成员的规律性，可以采用隐式罗列法来表示，即不必罗列出每个集成员。具体语法如下： setname/member1.memberN/: attribute_list; 这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。 2.1.1.2 定义派生集 为了定义一个派生集，必须定义：集的名字、父集的名字、集成员（可选）和集成员的属性（可选）。定义一个派生集，用下面的语法： setname(parent_set_list)/member_list/:attribute_list;setname是集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也可以是其它的派生集。 比如shudu(line,col):a;定义了一个派生集，它没有指定成员列表，那么LINGO会自动创建父集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种类型的函数：基本运算符、数学函数、金融函数、概率函数、变量界定函数、集操作函数、集循环函数、数据输入输出函数、辅助函数。 2.1.3.1 基本运算符 这些运算符是非常基本的，甚至可以不认为它们是一类函数。事实上，在LINGO中它们是非常重要的。 2.1.3.1.1 算术运算符 算术运算符是针对数值进行操作的。LINGO提供了5种二元运算符：乘方、乘、除、加、减。LINGO唯一的一元算术运算符是取反函数“”。这些运算符的优先级由高到底为：（取反）、。运算符的运算次序为从左到右按优先级高低来执行。运算的次序可以用圆括号“（）”来改变。 2.1.3.1.2 逻辑运算符 在LINGO中，逻辑运算符主要用于集循环函数的条件表达式中，来控制在函数中哪些集成员被包含，哪些被排斥。在创建稀疏集时用在成员资格过滤器中。LINGO具有种逻辑运算符： #not# 否定该操作数的逻辑值，not是一个一元运算符 #eq#若两个运算数相等，则为true；否则为flase #ne# 若两个运算符不相等，则为true；否则为flase #gt# 若左边的运算符严格大于右边的运算符，则为true；否则为flase #ge# 若左边的运算符大于或等于右边的运算符，则为true；否则为flase #lt# 若左边的运算符严格小于右边的运算符，则为true；否则为flase #le# 若左边的运算符小于或等于右边的运算符，则为true；否则为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#截然不同，前者是模型中该关系运算符所指定关系的为真描述，而后者仅仅判断一个该关系是否被满足：满足为真，不满足为假。 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返回-1；否则，返回1 floor(x) 返回x的整数部分。当x>=0时，返回不超过x的最大整数；当x<0时，返回不低于x的最大整数。 smax(x1,x2,xn) 返回x1，x2，xn中的最大值 smin(x1,x2,xn) 返回x1，x2，xn中的最小值2.1.3.3 金融函数 LINGO提供了两个金融函数。 1fpa(I,n)返回如下情形的净现值：单位时段利率为I，连续n个时段支付，每个时段支付单位费用。若每个时段支付x单位的费用，则净现值可用x乘fpa(I,n)算得。fpa的计算公式为 。净现值就是在一定时期内为了获得一定收益在该时期初所支付的实际费用。 2fpl(I,n)返回如下情形的净现值：单位时段利率为I，第n个时段支付单位费用。fpl(I,n)的计算公式为 。 2.1.3.4 概率函数 1pbn(p,n,x)二项分布的累积分布函数。当n和（或）x不是整数时，用线性插值法进行计算。 2pcx(n,x)自由度为n的2分布的累积分布函数。 3peb(a,x)当到达负荷为a，服务系统有x个服务器且允许无穷排队时Erlang繁忙概率。 4pel(a,x)当到达负荷为a，服务系统有x个服务器且不允许排队时的Erlang繁忙概率。 5pfd(n,d,x)自由度为n和d的F分布的累积分布函数。 6pfs(a,x,c)当负荷上限为a，顾客数为c，平行服务器数量为x时，有限源的Poisson服务系统的等待或返修顾客数的期望值。a是顾客数乘以平均服务时间，再除以平均返修时间。当c和（或）x不是整数时，采用线性插值进行计算。 7phg(pop,g,n,x)超几何（Hypergeometric）分布的累积分布函数。pop表示产品总数，g是正品数。从所有产品中任意取出n（npop）件。pop，g，n和x都可以是非整数，这时采用线性插值进行计算。 8ppl(a,x)Poisson分布的线性损失函数，即返回max(0,z-x)的期望值，其中随机变量z服从均值为a的Poisson分布。 9pps(a,x)均值为a的Poisson分布的累积分布函数。当x不是整数时，采用线性插值进行计算。 10psl(x)单位正态线性损失函数，即返回max(0,z-x)的期望值，其中随机变量z服从标准正态分布。 11psn(x)标准正态分布的累积分布函数。 12ptd(n,x)自由度为n的t分布的累积分布函数。 13qrand(seed)产生服从(0,1)区间的拟随机数。qrand只允许在模型的数据部分使用，它将用拟随机数填满集属性。通常，声明一个m×n的二维表，m表示运行实验的次数，n表示每次实验所需的随机数的个数。在行内，随机数是独立分布的；在行间，随机数是非常均匀的。这些随机数是用“分层取样”的方法产生的。 14rand(seed)返回0和1间的伪随机数，依赖于指定的种子。典型用法是U(I+1)=rand(U(I)。注意如果seed不变，那么产生的随机数也不变。 2.1.3.5 变量界定函数 变量界定函数实现对变量取值范围的附加限制，共4种： bin(x) 限制x为0或1 bnd(L,x,U) 限制LxU free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数 gin(x) 限制x为整数在默认情况下，LINGO规定变量是非负的，也就是说下界为0，上界为+。free取消了默认的下界为0的限制，使变量也可以取负值。bnd用于设定一个变量的上下界,它也可以取消默认下界为0的约束。 2.1.3.6集操作函数 LINGO提供了几个函数帮助处理集。 1in(set_name,primitive_index_1 ,primitive_index_2,)如果元素在指定集中，返回1；否则返回0。 2index(set_name, primitive_set_element)该函数返回在集set_name中原始集成员primitive_set_element的索引。如果set_name被忽略，那么LINGO将返回与primitive_set_element匹配的第一个原始集成员的索引。如果找不到，则产生一个错误。 3wrap(index,limit)该函数返回j=index-k*limit，其中k是一个整数，取适当值保证j落在区间1，limit内。该函数相当于index模limit再加1。该函数在循环、多阶段计划编制中特别有用。 4size(set_name)该函数返回集set_name的成员个数。在模型中明确给出集大小时最好使用该函数。它的使用使模型更加数据中立，集大小改变时也更易维护。 2.1.3.7 集循环函数 集循环函数遍历整个集进行操作。其语法为 function(setname(set_index_list)|conditional_qualifier:expression_list); function相应于下面罗列的四个集循环函数之一；setname是要遍历的集；set_ index_list是集索引列表；conditional_qualifier是用来限制集循环函数的范围，当集循环函数遍历集的每个成员时，LINGO都要对conditional_qualifier进行评价，若结果为真，则对该成员执行function操作，否则跳过，继续执行下一次循环。expression_list是被应用到每个集成员的表达式列表，当用的是for函数时，expression_list可以包含多个表达式，其间用逗号隔开。这些表达式将被作为约束加到模型中。当使用其余的三个集循环函数时，expression_list只能有一个表达式。如果省略set_index_list，那么在expression_list中引用的所有属性的类型都是setname集。 1for该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过for函数允许只输入一个约束，然后LINGO自动产生每个集成员的约束。 2sum该函数返回遍历指定的集成员的一个表达式的和。 3min和max返回指定的集成员的一个表达式的最小值或最大值。 2.1.3.8 输入和输出函数 输入和输出函数可以把模型和外部数据比如文本文件、数据库和电子表格等连接起来。 1file函数 该函数用从外部文件中输入数据，可以放在模型中任何地方。该函数的语法格式为file(filename)。这里filename是文件名，可以采用相对路径和绝对路径两种表示方式。file函数对同一文件的两种表示方式的处理和对两个不同的文件处理是一样的，这一点必须注意。 2text函数 该函数被用在数据部分用来把解输出至文本文件中。它可以输出集成员和集属性值。其语法为text(filename)，这里filename是文件名，可以采用相对路径和绝对路径两种表示方式。如果忽略filename，那么数据就被输出到标准输出设备（大多数情形都是屏幕）。text函数仅能出现在模型数据部分的一条语句的左边，右边是集名（用来输出该集的所有成员名）或集属性名（用来输出该集属性的值）。 3ole函数 OLE是从EXCEL中引入或输出数据的接口函数，它是基于传输的OLE技术。OLE传输直接在内存中传输数据，并不借助于中间文件。当使用OLE时，LINGO先装载EXCEL，再通知EXCEL装载指定的电子数据表，最后从电子数据表中获得Ranges。为了使用OLE函数，必须有EXCEL5及其以上版本。OLE函数可在数据部分和初始部分引入数据。OLE可以同时读集成员和集属性，集成员最好用文本格式，集属性最好用数值格式。原始集每个集成员需要一个单元(cell)，而对于n元的派生集每个集成员需要n个单元，这里第一行的n个单元对应派生集的第一个集成员，第二行的n个单元对应派生集的第二个集成员，依此类推。OLE只能读一维或二维的Ranges（在单个的EXCEL工作表(sheet)中），但不能读间断的或三维的Ranges。Ranges是自左而右、自上而下来读。 2.1.3.9 辅助函数 1if(logical_condition,true_result,false_result)，if函数将评价一个逻辑表达式logical_condition，如果为真，返回true_ result，否则返回false_result。 2warn(text,logical_condition)，如果逻辑条件logical_condition为真，则产生一个内容为text的信息框。 2-2 九宫数独Lingo程序利用Lingo编程语言，对第1章的九宫数独建立数学模型进行程序设计。利用floor（x）能够返回x的整数部分。即当x>=0时，返回不超过x的最大整数；当x<0时，返回不低于x的最大整数。为了加快求解速度和在已知条件不充分也能够求解,在程序中增加语句min=sum(link:x),数独模型Lingo求解程序如下：model:sets:number/1.9/;line/1.9/;col/1.9/;gong/1.9/;shudu(line,col):a;link(line,col,number):x;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):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例117932896553918264314713在九宫数独数学模型Lingo 求解程序中输入：a=1 0 0 0 0 7 0 9 0 0 3 0 0 2 0 0 0 80 0 9 6 0 0 5 0 00 0 5 3 0 0 9 0 00 1 0 0 8 0 0 0 26 0 0 0 0 4 0 0 03 0 0 0 0 0 0 1 00 4 0 0 0 0 0 0 70 0 1 0 0 0 3 0 0 ;可得下面的结果。 164857293537921468289643571475312986913586742628794135396275814842139657751468329 2-3幻方数独数学模型Lingo求解程序 在2-2 九宫数独Lingo求解程序中，增加第3、5、7 三个九宫格中每个九宫格的横行、竖行的和都等于15的要求，可得幻方数独数学模型Lingo求解程序：model:sets:number/1.9/;line/1.9/;col/1.9/;gong/1.9/;shudu(line,col):a;link(line,col,number):x;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):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(line(i)|i#ge#1#and#i#le#3:sum(number(k): k*x(i,7,k)+ sum(number(k): k*x(i,8,k)+ sum(number(k): k*x(i,9,k)=15);for(line(i)|i#ge#4#and#i#le#6:sum(number(k): k*x(i,4,k)+ sum(number(k): k*x(i,5,k)+ sum(number(k): k*x(i,6,k)=15);for(line(i)|i#ge#7#and#i#le#9:sum(number(k): k*x(i,1,k)+ sum(number(k): k*x(i,2,k)+ sum(number(k): k*x(i,3,k)=15);for(line(i)|i#ge#1#and#i#le#3:sum(number(k): k*x(7,i,k)+ sum(number(k): k*x(8,i,k)+ sum(number(k): k*x(9,i,k)=15);for(line(i)|i#ge#4#and#i#le#6:sum(number(k): k*x(4,i,k)+ sum(number(k): k*x(5,i,k)+ sum(number(k): k*x(6,i,k)=15);for(line(i)|i#ge#7#and#i#le#9:sum(number(k): k*x(1,i,k)+ sum(number(k): k*x(2,i,k)+ sum(number(k): k*x(3,i,k)=15); for(link(i,j,k):bin(x(i,j,k); End例28357916414359168在幻方数独数学模型Lingo求解程序中输入:a=0 8 0 0 0 0 0 0 0 3 5 0 0 0 7 0 0 0 0 0 9 0 0 1 0 0 0 0 0 0 0 0 0 6 4 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 3 0 0 5 0 0 0 0 0 9 0 0 0 1 6 0 0 0 0 0 0 0 8 0;可得：781563429352497861469281375238159647976834152514672938627318594843925716195746283 2-4 窗口数独数学模型Lingo求解程序 利用floor（x）能够返回x的整数部分。即当x>=0时，返回不超过x的最大整数；当x<0时，返回不低于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):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 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.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(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):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,5)=1;x(4,6,4)=1;x(1,7,7)=1;x(4,7,3)=1; 根据运行程序可得结果可得： 本章小结范围理论性程序设计应用性Lingo 编程语言趣味性数独创新性数独模型Lingo求解2-7作业1、设计两主对角线九宫数独（主对角线上的数字互不相同）的Lingo求解程序，并求解下面的九条主对角线的9×18双胞胎数独。1823952871543939574132974882541278392、设计3×12双胞胎数独的Lingo求解程序，并求解下面的3×12双胞胎数独。 423563、设计九条主对角线的9×18双胞胎数独的Lingo求解程序，并求解下面的九条主对角线的9×18双胞胎数独。2738945932148665178962145932648715192738 4、设计十六宫数独的Lingo求解程序，并求解下面的十六宫数独。1216149581114141213710151511581291191613671611443101210168111315415121378495961211348921261251615179210111661211615793131610271514711513316159651424103451211275、设计程序，使得