LINGO在数学建模中的应用

一、LINGO简介

LINGO[1]是美国LINDO系统公司开发的求解数学规划系列软件中你的一个,它的主要功能是求解大型线性、非线性和整数规划问题,LINGO的不同版本对模型的变量总数、非线性变量数目、整型变量数目和约束条件的数量做出不同的限制.

LINGO的主要功能特色为:

(1)既能求解线性规划问题,也有较强的求解非线性规划问题的能力; (2)输入模型简练直观; (3)运行速度快、计算能力强.

(4)内置建模语言,提供几十个内部函数,从而能以较少语句,较直观的方式描述较大规模的优化模型;

(5)将集合的概念引入编程语言,很容易将实际问题转换为LINGO模型; (6)能方便地与EXCEL、数据库等其他软件交换数据.

LINGO像其他软件一样,对他的语法有规定,LINGO的语法规定如下: （1） 求目标函数的最大值或最小值分别用MAX=?或MIN=?来表示;

(2) 每个语句必须以字母开头,由字母、数字和下划线所组成,昌都不超过32个字符,不区分大小写;

(3)每个语句必须以分号“;”结束,每行可以有多个语句,语句可以跨行; (4)如果对变量的取值范围没有特殊说明,则默认所有决策变量都非负;

(5)LINGO模型以语句“MODEL”开头,以语句“END”结束,对于比较简单的模型,这这两个语句可以省略.

LINGO提供了五十几个内部函数,使用这些函数可以大大减少编程工作量,这些函数都是以字符@开头,下面简单介绍其中的集合操作函数和变量定界函数及用法.

集合是LINGO建模语言中最重要的概念,使用集合操作函数能够实现强大的

1

功能,LINGO提供的常用集合操作函数有@FOR(s:e)、@SUM(s:e)、@MAX(s:e)、@MIN(s:e)等.@FOR(s:e)常用在约束条件中,表示对集合s中的每个成员都生成一个约束条件表达式,表达式的具体形式由参数e描述;@SUM(s:e) 表示对集合s中的每个成员,分别得到表达式e的值,然后返回所有这些值的和;@MAX(s:e) 表示对集合s中的每个成员,分别得到表达式e的值,然后返回所有这些值中的最大值;@MIN(s:e) 表示对集合s中的每个成员,分别得到表达式e的值,然后返回所有这些值中的最小值.

LINGO默认变量的取值可以从零到正无穷大,变量定界函数可以改变默认状态,如对整数规划,限定变量取整数,对0-1规划,限定变量取0 1或.LINGO提供的变量定界函数有:@BIN(X)、@BND(L,X,U)、@GIN(X)、@FREE(X).@BIN(X)限定X为0或1,在0-1规划中特别有用;@GIN(X)限定X为整数,在整数规划中特别有用;@BND(L,X,U)限定L＜X＜U,可用作约束条件;@FREE(X)取消对X的限定,即X可以取任意实数.

二、LINGO在线性规划中的应用

具有下列三个特征的问题称为线性规划问题(Linear program)[2]简称LP问题,其数学模型称为线性规划(LP)模型.

线性规划问题数学模型的一般形式为:求一组变量xj(j?1,2,?,n)的值,使其满足

max(min)z?c1x1?c2x2???cnxn,

?a11x1?a12x2???a1nx1n*b1,??a21x1?a22x2???a2nx2n*b2,?s.t.?? ?ax?ax???ax*b.nnnnnn22?n11?xj?0,j?1,2,?,n? 2

式中“*”代表“?”、“ ?”或“=”.

上述模型可简写为

nmax(min)z??cj?1jxj,

?n??aijxj*bi,i?1,2,?,ms.t.?j?1?x?0,j?1,2,?,n?jn

nj其中,变量xj称为决策变量,函数z??cj?1xj称为目标函数,条件?cjxj*bi称为约

j?1束条件,xj?0 称为非负约束.在经济问题中,又称cj为价值系数,bi为资源限量. 线性规划在科学决策与经营管理中实效明显[3],但是对于规模较大的线性模型,其求解过程非常繁琐,不易得出结果.而 LINGO中的内部集合函数有@FOR(s:e)、@SUM(s:e)、@MAX(s:e)、@MIN(s:e)等,可以用这些集合函数使程序编程简单可行,下面举例说明.

例1 某工厂有两条生产线,分别用来生产M和P两种型号的产品,利润分别为200元每个和300元每个,生产线的最大生产能力分别为每日100和120,生产线没生产一个M产品需要1个劳动日(1个工人工作8小时称为1个劳动日)进行调试、检测等工作,而每个P产品需要2个劳动日,该工厂每天共计能提供160个劳动日,假如原材料等其他条件不受限制,问应如何安排生产计划,才能使获得的利润最大？

解 设两种产品的生产量分别为x1和x2,则该问题的数学模型为:

目标函数 maxz?200x1?300x2

?x?100,??x2?120, ?x?x?160,2?1?x?0,i?1,2.?i 约束条件

编写LINGO程序如下:

3

MODEL: SETS:

SHC/1,2 /:A,B,C,X; YF/1,2,3 /:J; ENDSETS DATA:

A=1,2 ; B=100,120; C=200,300; ENDDATA

MAX=@SUM(SHC:C*X);

@FOR(SHC(I):X(I)

程序运行结果如下

Global optimal solution found.

Objective value: 29000.00 Total solver iterations: 0 Variable Value Reduced Cost A( 1) 1.000000 0.000000 A( 2) 2.000000 0.000000 B( 1) 100.0000 0.000000 B( 2) 120.0000 0.000000 C( 1) 200.0000 0.000000 C( 2) 300.0000 0.000000 X( 1) 100.0000 0.000000 X( 2) 30.00000 0.000000 J( 1) 0.000000 0.000000 J( 2) 0.000000 0.000000 J( 3) 0.000000 0.000000

4

Row Slack or Surplus Dual Price 1 29000.00 1.000000 2 0.000000 50.00000 3 90.00000 0.000000 4 0.000000 150.0000

最优解为x1?100,x2?30,最优值为z?29000.00.即每天生产100个M产品30个P产品,可获得29000元利润.

三、LINGO在整数规划和0-1规划中的应用

1 求解整数规划

整数规划[4]分为整数规划和混合整数规划,要求全部变量都为非负整数的数学规划称为纯整数规划,只要求部分变量为非负整数的数学规划称为混合整数规划.下面只讨论约束条件和目标函数均为线性的整数规划问题,即整数线性规划问题(以下简称整数规划,记为ILP),其数学模型的一般形式是

nmax?min?z??cj?1jxj,

?n??aijxj?bi?i?1,2,?,n??j?1?xj?0?j?1,2,?,n? s.t.? ?1? ?x全为整数或部分为整数。?j??且称线性规划问题

nmax?min?z??cj?1jxj,

5

?n??aijxj?bi?i?1,2,?,m?, s.t.?j?1 ?2?

?xj?0?j?1,2,?,n?.?为整数规划问题的松弛问题.

显然,整数规划?1?的可行域是其松弛问题?2?的可行域的一个子集.如果线性规划?2?的最优解为x?0?,相应的规划规划?1?的最优解为x*,则必然有cx*?cx?0?.

LINGO的内部函数@GIN(X)是限定X为整数,因此,LINGO对整数规划的求解是可行的.下面举例说明:

例2 某疗养院营养师要为某类病人拟订本周蔬菜类菜单,当前可供选择的蔬菜品种、价格和营养成分含量,以及病人所需养分的最低数量见表1,病人1周需14份蔬菜,为了口味的原因,规定每周内的卷心菜不多于2份,胡萝卜不多于3份,其他蔬菜不多于4份且至少1份.在满足要求的前提下,制定费用最少的一周菜单方案. 表1 可供蔬菜养分含量和价格 蔬菜 养分 每份蔬菜所含养分数量 铁 A1 A2 A3 A4 A5 A6 A7 青豆 萝卜 花菜 卷心菜 芹菜 土 豆 红柿 0.45 0.45 0.65 0.4 0.5 0.5 0.6 8 20 28 40 25 26 75 45 180 磷 维生素维生素A 415 C 22 0.3 0.35 0.6 0.2 0.4 0.6 0.2 7 0.2 0.25 0.3 0.12 0.15 0.21 0.25 4 烟酸 锌 每份价格 (元) 2.1 1.0 1.8 1.2 2.0 1.2 1.5 4065 5 850 75 76 235 240 43 27 48 8 20 每周最低需求 19800 450 解 用xi表示7种蔬菜的份数,ai表示蔬菜单价,bi表示每周最低营养需求,cij表示第i种蔬菜的第j种养分含量,建立如下整数规划模型

6

minz??ax

iii?17?7??cijxi?bj?i?1?x4?2? s.t.?x2?3,?x?1,i?1,3,5,6,7.?i?xi?1,i?1,3,5,6,7.??LINGO程序如下: MODEL: SETS:

SHC/1 2 3 4 5 6 7/:AI,X; YF/1 2 3 4 5 6/:BJ; JIAGE(SHC,YF):C; ENDSETS DATA:

AI=2 1 1.8 1.2 2.0 1.2 1.5; BJ=7 140 14800 400 7 4; C=0.45 20 415 22 0.3 0.2 0.45 28 4065 5 0.35 0.25 0.65 40 850 43 0.6 0.3 0.4 25 75 27 0.2 0.12 0.5 26 76 48 0.4 0.15 0.5 75 235 8 0.6 0.21 0.6 45 240 20 0.2 0.25; ENDDATA

MIN=@SUM(SHC:AI*X); @FOR(SHC(I):@GIN(X(I))); @FOR(SHC(I):X(I)>=1);

7

@SUM(SHC(I):X(I))=21; X(2)<=3; X(3)<=2;

@FOR(SHC(I)|I #NE# 2 #AND# I #NE# 4:X(I)<=4); @FOR(YF(J):@SUM(SHC(I):X(I)*C(I,J))>=BJ(J)); END

Global optimal solution found.

Objective value: 28.00000 Extended solver steps: 0 Total solver iterations: 6

Variable Value Reduced Cost

X( 1) 1.000000 2.000000 X( 2) 3.000000 1.000000 X( 3) 2.000000 1.800000 X( 4) 8.000000 1.200000 X( 5) 1.000000 2.000000 X( 6) 4.000000 1.200000 X( 7) 2.000000 1.500000

当x1?1,x2?3,x3?2,x4?8,x5?1,x6?4,x7?2时,目标函数最小,zmin?28.

2求解0-1规划

在整数规划中,当对变量的限定为变量的值只能取整数值时,我们把整数规划

称为0-1规划[5],0-1规划化为以下标准形式:

nmaxz??cj?1jxj,

8

?cj?0?j?1,2,?,n?,?n?s.t.??aijxj?bj?i?1,2,?,m?, ?j?1?x?0或1?j?1,2,?,n?.j?任意0-1规划模型如何化为标准形式:

(1)如果目标函数是求最小值,则对目标函数两边乘以-1,变为求最大值; (2)如果目标函数中某变量xj的系数cj?0,则令xj?1?yj替换xj为0-1变量, 于是变量yj在目标函数中的系数cj变成小于0;

(3)如果约束条件是“?”形式,则可两边乘以-1,变为“?”形式;

(4)如果约束条件中含有等式,则可将每个等式化为两个“?”形式的不等式. LINGO内部函数@BIN(X)的作用是限定X为0或1,因此,LINGO对整数规划的求解是可行的.下面举例说明:

例3 分配六个人去完成6项任务,每人完成一项,每项任务只能由一人去完成,六个人分别完成各项任务的效益如下表所示,试做出任务分配使效益最大. 各人完成各项任务的效益 任务 A B C D E F 20 15 16 5 4 7 17 15 33 12 8 6 9 12 18 16 30 13 12 8 11 27 19 14 - 7 10 21 10 32 - - - 6 11 13 人员 1 2 3 4 5 6 解 用xij(i?1,2,?,6,j?1,2,?6)表示第i个人是否完成第j项任务,当

xij?1表示第i个人完成第

j项任务,xij?0第i个人不完成第j项任务,用cij表示

9

第i个人完成第j项任务的效率 模型建立如下:

66ijminz???ci?1j?1xij

?6??xij?1?i?1 s.t.?6??xij?1??j?1编写程序如下: MODEL: SETS:

RENWU/1,2,3,4,5,6/; MEN/1,2,3,4,5,6/; WCHRW(MEN,RENWU):C,x; ENDSETS DATA:

C=20,15,16,5,4,7 17,15,33,12,8,6 9,12,18,16,30,13 12,8,11,27,19,14 0,7,10,21,10,32 0,0,0,6,11,13; ENDDATA

MAX=@SUM(WCHRW(I,J):C*X); @FOR(WCHRW(I,J):@BIN(X(I,J)));

@FOR(MEN(I):@SUM(RENWU(J):X(I,J))=1); @FOR(RENWU(J):@SUM(MEN(I):X(I,J))=1); END

10

Global optimal solution found.

Objective value: 142.0000 Objective bound: 142.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0

当x11?1,x23?1,x35?1,x44?1,x56?1,x62?1,时,zmax?142.即第一个人完成第一项任务,第二个人完成第二项任务,第三个人完成第三项任务,第四个人完成第四项任务,第五个人完成第五项任务,第六个人完成第六项任务时,效率最高.

四 LINGO在多目标规划中的应用

多目标规划的解法通常是根据问题的实际背景和特征,设法将多目标规划转化为单目标规划,从而获得满意解.常用的解法有[6]:

(1)主要目标法.确定一个主要目标,把次要目标作为约束条件并设定适当 界限值.

(2) 线性加权平均法.对每个目标按其重要程度赋予适当权重?i?0,且

??i,,p,是原来的p个?1,然后把??ifi(x)作为新的目标函数(其中fi(x)i?1,2?目标).

p(3)指数加权平均法.设fi(x)是原来的p个目标,令Z??[fi(x)]a,其中ai为指

ii数加权,把Z作为新的目标函数.

(4)理想点法.先分别求出p个单目标规划的最优解ft*,令

h(x)??(f(x)?ifi)*2,然后把它作为新的目标函数.

11

(5)分层序列法[7].将所有p个目标按其重要程度排序,先找出第一个最重要的目标的最优解,然后在保证前一个目标最优解的前提下,依次求下一个目标的最优解,一直求到最后一个目标为止.

这些方法各有其优点和适用的场合,但并非总是有效,有些方法存在一些不足之处,例如,线性加权求和法确定权重系数时有一定主观性,权重系数取值不同,结果也就不一样;线性加权求和法,指数加权乘积法和理想点法通常只能用在两个目标的单位(量纲)相同的情况,如投资时希望收益要大、风险要小,这是双目标规划,若收益和风险的物理单位(元或百分比)相同,可以考虑用线性加权求和法、指数加权乘积法或理想点法把它们组合起来,化双目标规划为点目标规划.如果两个目标是不同的物理量,它们的量纲不相同,数量级相差很大,将它们相加或比较是不合适的,如火箭弹射程的单位是米或千米,且数量级比较大,而射击精度通常用样本方差来表示,其量纲是平方米,且数量级小,将两者比较、相加或者求理想点是没有有意义的.下面介绍一个双目标规划的例子.

例 4 某工厂有工人300名,生产A,B,C,D四种产品,要求每人每周工作时间在20-48小时内,C的产量每周至少150件,而每周至多20吨煤,其他数据见下表: 产品 最大产量 销售量 成本 售价 能耗 生产时间 (件/周) (件/周) (元/件) (元/件) (吨煤/百件) (时/件) A 270 300 190 200 1.5 13 B 240 300 210 230 2 13.5 C 460 600 148 160 1.8 14 D 130 200 100 114 1.1 11.5 问应如何安排每周生产,才能使利润最高,而能耗最少？

解 用xi表示四种产品的产量,ai表示每件i产品的利润,bi表示每100件i产品的能耗,ci表示生产每件i产品的时间,di表示i种产品的最大产量.建立双目标规划模型如下:

12

4maxz??i?1aixi

4miny??bxii?1i

?4??cixi??14400,?i?1?4??cixi??12000,?i?1?4s.t.?bx??2000,??ii i?1??xi?N,i?1,2,3,4,?x??150,?3??xi??di,i?1,2,3,4.LINGO程序如下: MODEL: SETS:

YF/B1 B2 B3 B4 /:B,A,C,D,X; ENDSETS DATA:

A=10 20 12 14; B=1.5 2 1.8 1.1; C=13 13.5 14 11.5; D=270 240 460 130; ENDDATA

MAX=@SUM(YF(I):A*X); @FOR(YF(I):@GIN(X(I))); @SUM(YF(I):B(I)*X(I))<=2000;

13

X(3)>=150;

@FOR(YF(I):X(I)<=D(I)); @SUM(YF(I):C(I)*X(I))<=14400; @SUM(YF(I):C(I)*X(I))>=12000; END

具体求解结果为:

Objective value: 14620.00 Extended solver steps: 0 Total solver iterations: 3

Variable Value Reduced Cost

X( B1) 248.0000 -10.00000 X( B2) 240.0000 -20.00000 X( B3) 460.0000 -12.00000 X( B4) 130.0000 -14.00000

即A、B、C、D四种产品各生产248件、240件、460件、130件时,能使利润最高,最高利润为14620元.题目还要求能耗最少,因此用分层序列法,把利润最高的

44计算结果作为约束条件,即增加约束条件:?aixi?14620,把miny?i?1?bx作为目

iii?1标函数,建立单目标规划模型求解. LINGO程序如下: MODEL: SETS:

YF/B1 B2 B3 B4 /:B,A,C,D,X; ENDSETS DATA:

A=10 20 12 14; B=1.5 2 1.8 1.1;

14

C=13 13.5 14 11.5; D=270 240 460 130; ENDDATA

MIN=@SUM(YF(I):B(I)*X(I)/100); @SUM(YF(I):A*X)<=14620; @FOR(YF(I):@GIN(X(I))); @SUM(YF(I):B(I)*X(I))<=2000; X(3)>=150;

@FOR(YF(I):X(I)<=D(I)); @SUM(YF(I):C(I)*X(I))<=14400; @SUM(YF(I):C(I)*X(I))>=12000; END

具体求解结果为:

Objective value: 14.58900 Extended solver steps: 0 Total solver iterations: 5

Variable Value Reduced Cost

X( B1) 270.0000 0.1500000E-01 X( B2) 42.00000 0.2000000E-01 X( B3) 460.0000 0.1800000E-01 X( B4) 129.0000 0.1100000E-01

即每周生产A、B、C、D四种产品各270件、42件、460件、129件,能使利润最高,能耗最少.

五 用LINGO求非线性曲线拟合的最小二乘解

15

本文来源：https://www.bwwdw.com/article/zkfo.html