数学建模 优化模型介绍p134

数学建模

优化模型介绍/sundae_meng引言---数学之重要……数学使人周密……----FrancisBacon

数学处于人类智能的中心领域……数学方法渗透、支配着一切自然科学的理论分支……它已愈来愈成为衡量成就的主要标志。

----vonNeumann

/sundae_meng引言---数学之重要

一门科学只有当它达到能够成功地运用数学时，才算真正发展了。

----KarlMarxGalileo:

展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像在黑暗的迷宫里游荡，什么也认识不清。数学是一种语言，是一切科学的共同语言/sundae_meng引言---数学之重要数学是一种技术，是高技术的本质数学技术----数学方法与计算技术的结合形成的一种关键性的、可实现的技术二十世纪最伟大的数学家----二十世纪最伟大的物理学家----D.HilbertA.EinsteinGoback诺贝尔奖菲尔兹奖/sundae_meng1.什么是数学模型？

数学模型是对于现实世界的一个特定对象，一个特定目的，根据特有的内在规律，做出一些必要的假设，运用适当的数学工具，得到一个数学结构．简单地说：就是系统的某种特征的本质的数学表达式（或是用数学术语对部分现实世界的描述），即用数学式子（如函数、图形、代数方程、微分方程、积分方程、差分方程等）来描述（表述、模拟）所研究的客观对象或系统在某一方面的存在规律．/sundae_meng2.什么是数学建模?

数学建模是利用数学方法解决实际问题的一种实践．即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，然后运用先进的数学方法及计算机技术进行求解．观点：“所谓高科技就是一种数学技术”/sundae_meng

数学建模其实并不是什么新东西，可以说有了数学并需要用数学去解决实际问题，就一定要用数学的语言、方法去近似地刻画该实际问题，这种刻划的数学表述的就是一个数学模型，其过程就是数学建模的过程．数学模型一经提出，就要用一定的技术手段（计算、证明等）来求解并验证，其中大量的计算往往是必不可少的，高性能的计算机的出现使数学建模这一方法如虎添翼似的得到了飞速的发展，掀起一个高潮．

数学建模将各种知识综合应用于解决实际问题中，是培养和提高同学们应用所学知识分析问题、解决问题的能力的必备手段之一./sundae_meng数学建模参考书1.《数学模型》姜启源、谢金星、叶俊编高等教育出版社2.《数学建模方法及其应用》解放军信息工程大学韩中庚编高教社3.《数学模型与数学建模》刘来福、曾文艺编著北师大出版社4.叶其孝等，《大学生数学建模竞赛辅导教材（一）~（四）》，湖南教育出版社

5.赵静等，《数学建模与数学实验》，高等教育出版社，施普林格出版社/sundae_meng

规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为科学研究的各个方面，为社会节省的财富、创造的价值无法估量.

特别是在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-06年全国大学生数模竞越多的人所重视.随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出现了15次，占到了50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解.

/sundae_meng

优化问题，一般是指用“最好”的方式，使用或分配有限的资源，即劳动力、原材料、机器、资金等，使得费用最小或者利润最大。优化模型/sundae_mengminf(x)

--------目标函数

s.t.x

S

------约束集合，可行集其中，S

Rn，f:S

R，x

S称（fS)的可行解最优解:x*

S，满足f(x*)≤f(x),x

S。则称

x*为(fS)的全局最优解(最优解),

记g.opt.(globaloptimum),简记opt.最优值:x*为(fS)的最优解,则称f*=f(x*)

为

(fS)的最优值(最优目标函数值)数学规划模型的一般形式(fS)/sundae_meng局部最优解:x*

S，

x*的邻域N(x*)，使满足

f(x*)≤f(x),x

S

N(x*)

。则称x*为(fS)的局部最优解,记l.opt.(localoptimum)在上述定义中，当x

x*时有严格不等式成立，则分别称x*

为(fS)的严格全局最优解和严格局部最优解。严格l.opt.严格g.opt.l.opt./sundae_meng数学规划模型的一般形式函数形式:

f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)

≤0,i=1,2,…,m

hj(x)=0,j=1,2,…,l矩阵形式:minf(x)，f(x)

:Rn

R(fgh)s.t.g(x)

≤0,g(x):Rn

Rm

h(x)=0,h(x):Rn

Rl

当f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。/sundae_meng优化模型的简单分类

线性规划(LP)

目标和约束均为线性函数

非线性规划(NLP)

目标或约束中存在非线性函数

二次规划(QP)

目标为二次函数、约束为线性

整数规划(IP)

决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)

纯整数规划(PIP),混合整数规划(MIP)

一般整数规划，0-1（整数）规划连续优化离散优化数学规划/sundae_meng优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加

/sundae_meng

线性规划LinearProgramming/sundae_meng问题一：

任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？

两个引例/sundae_meng建立线性规划模型的基本步骤：（1）设出决策变量

（2）确定目标函数（3）确定约束条件找出待定的未知变量（决策变量），并用代数符号表示找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值

找出问题的所有的限制或约束，写出未知变量的线性方程或线性不等式/sundae_meng解

设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：

解答/sundae_meng问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：/sundae_meng故目标函数为：约束条件为：/sundae_meng线性规划模型：

解答返回/sundae_meng模型特点：目标函数(Objectivefunction)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

(=,

)b1a21x1+a22x2+….+a2nxn

(=,

)b2

….am1x1+am2x2+….+amnxn

(=,

)bmx1,x2….xn

0/sundae_meng线性规划的基本概念1.可行解(FeasibleSolution)——任一满足约束条件的一组决策变量的数值.2.可行域(FeasibleRegion)——所有可行解组成的集合，也称为可行解集.3.目标函数等值线(Objectivefunctionline)——为于同一直线上的点，具有相同的目标函数值./sundae_meng线性规划模型的解的几种情况线性规划问题有可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)/sundae_meng

数学建模中线性规划模型的常用解法线性规划问题的求解在理在理论上有单纯型法，在实际建模中常用以下解法：1.图解法2.LINGO软件包3.Excel中的规划求解4.MATLAB软件包主要介绍线性规划模型的MATlAB软件包和LINGO软件包解法/sundae_meng模型求解方法1.图解法例1max

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0

该问题的最优解为x1=50；x2=250x2z*=50x1+100x2=27500x1+x2≤300x1x2≤2502x1+x2≤400z1=50x1+100x2=0BOACDz2=14000/sundae_meng用MATLAB优化工具箱解线性规划minz=cX

1.模型：命令：x=linprog（c,A,b）

2.模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].式中：linprog称为调用函数，C,A,b称为输入参数，全部由用户提供，必须按规定的位置放置在原括号内./sundae_meng3.模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]

x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点,设置它有些情况下可以减少迭代工作量4.命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval./sundae_meng解编写M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];

A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];

b=[850;700;100;900];

Aeq=[];beq=[];

vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

C:/Documents%20and%20Settings/Administrator/%E6%A1%8C%E9%9D%A2/%E6%95%B0%E5%AD%A6%E6%A8%A1%E5%9E%8B/%E6%95%B0%E5%AD%A6%E5%BB%BA%E6%A8%A1%E4%B8%8E%E6%95%B0%E5%AD%A6%E5%AE%9E%E9%AA%8C%EF%BC%88%E7%AC%AC3%E7%89%88%EF%BC%89/%E7%AC%AC4%E8%AE%B2%20%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/xxgh1.m/sundae_meng解:编写M文件xxgh2.m如下：

c=[634];A=[010];b=[50];Aeq=[111];beq=[120];vlb=[30,0,20];vub=[];

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh2)/sundae_mengs.t.改写为：例3问题一的解答

问题/sundae_meng编写M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)/sundae_meng结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004

即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800./sundae_meng例2问题二的解答

问题改写为：/sundae_meng编写M文件xxgh4.m如下：c=[4036];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[915];%调用linprog函数：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh4)/sundae_meng结果为：x=9.00000.0000fval=360即只需聘用9个一级检验员.

注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.返回/sundae_meng用LINDO、LINGO优化工具箱解线性规划LINDO公司软件产品简要介绍

美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：

LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)What’sBest!:(SpreadSheete.g.EXCEL)(V7.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）/sundae_mengLINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)/sundae_meng一、LINDO软件包

下面我们通过一个例题来说明LINDO软件包的使用方法./sundae_meng问题：一奶制品加工厂用牛奶生产A1,A2两种奶制品，一桶牛奶可以在甲类设备上用12小时生产成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2.据市场要求，生产的两种奶制品全部能售出，且每公斤A1获利24元，每公斤A2获利16元，现在每天加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力没有限制.试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题。1）若用35元可以买到1桶牛奶，应否作这样的投资？若投资，每天最多购买多少桶牛奶2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？/sundae_meng1桶牛奶3kgA1

12小时8小时4kgA2

或获利24元/kg获利16元/kgx1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100kgA1

50桶牛奶每天基本模型/sundae_meng模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

z=0z=2400z=3600z

=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。/sundae_meng模型求解

软件实现

LINDOmax72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。/sundae_meng结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）原料无剩余时间无剩余加工能力剩余40/sundae_meng结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000最优解下“资源”增加1单位时“效益”的增量35元可买到1桶牛奶，要买吗?35<48,应该买！

聘用临时工人付出的工资最多每小时几元?2元！原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格/sundae_mengRANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

YesA1获利增加到30元/kg，应否改变生产计划?x1系数由243=72增至303=90<96,在允许范围内不变！约束条件不变!x1系数范围:(72-8,72+24)=(64,96)

x2系数范围:(48,72)/sundae_meng结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围35元可买到1桶牛奶,每天最多买多少?最多买10桶!目标函数不变!原料最多增加10时间最多增加53原料时间/sundae_meng模型求解

reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）,目标函数减少的量(对max型问题).OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量/sundae_meng1.使用LINDO的一些注意事项？“>”（或“<”）号与“>=”（或“<=”）功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义.行名以“）”结束行中注有“!”符号的后面部分为注释.如:

!It’sComment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：

TITLEThisModelisonlyanExample/sundae_meng变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界例如：“subx110”的作用等价于“x1<=10”

但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析.14.“END”后对0-1变量说明：INTn

或INTname15.“END”后对整数变量说明：GINn

或GINname

使用LINDO的一些注意事项/sundae_meng2.状态窗口（LINDOSolverStatus）当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒)/sundae_meng二、LINGO软件包/sundae_meng(1)LINGO模型的优点1.LINGO软件简介(2)对简单的LINGO程序LINGO也可以和LINDO一样编程但LINGO与LINDO语法有差异提供了灵活的编程语言（矩阵生成器）包含了LINDO的全部功能/sundae_mengLindo与简单Lingo程序的比较Model:

min=7*x1+3*x2;

x1+x2>=345.5;

x1>=98;

2*x1+x2<=600;

@gin(x1);

@gin(x2);

endmin7x1+3x2stx1+x2>=345.5x1>=982*x1+x2<=600endgin2lindo程序:lingo程序:/sundae_meng实验作业

某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过800箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每100箱甲饮料获利可增加1万元,问应否改变生产计划.返回/sundae_meng运输问题

---TransportationProblem运输问题(TransportationProblem)

以知有m个生产地点(source)Ai，i=1，…，m，可供应某种物资，其供应量（产量）(supply)为ai，i=1，…，m；有n个销售地点(destination)Bj，j=1，…，n，需要该种物资，其需要量（产量）(demand)为bj，j=1，…，n；从Ai到Bj运输单位物资的运价（单价）为cij；设Σai=Σbj，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。/sundae_meng

销地产地B1B2…Bn产量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam销量b1b2…bnΣaiΣbj产销平衡表(costandrequirementtable)/sundae_meng若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如下（模型Y）/sundae_meng产销不平衡的运输问题

----TotalSupplynotEqualtoTotalDemand一、产大于销(totalsupplyexceedstotaldemand)产大于销的运输问题的特征是Σai>Σbj，其数学模型为：/sundae_meng解此类问题可假想一个销地Bn+1，其需要量为：bn+1=Σai－Σbj；若用xi，n+1表示从Ai到Bn+1的运量，可令ci，n+1=0或等于第Ai产地储存单位物资的费用。因为xi，n+1实际上表示Ai产地没有运出去而库存的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：这样，m个产地、n个销地的不平衡运输问题，转化成了m个产地、n+1个销地的平衡运输问题，此时可用表上作业法求解。/sundae_meng二、销大于产(totaldemandexceedstotalsupply)销大于产的运输问题的特征是Σai<Σbj，其数学模型为：/sundae_meng解此问题可假想一个产地Am+1，其产量为：am+1=

Σbj－Σai；若用xm+1，j表示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：此时，可用表上作业法求解。/sundae_meng例某公司有6个供货栈（仓库），库存货物总数分别为60，55，51，43，41，52，现有8个客户各要一批货数量分别为35，37，22，32，41，32，43，38，各供货栈道8个客户的单位货物运输价见表供货栈到客户的单位货物运价客户货栈V1V2V3V4V5V6V7V8W162674259W249538582W352197433W476739271W523957265W655228143试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。/sundae_meng解引入决策变量代表从第个货栈到第个客户的货物运量.设表示从第个货栈到第个客户的单位货物运价表示第个货栈的最大供货量,表示第个客户的订货量.目标函数是总运输费用最少.约束条件有三条：1.各货栈运出的货物总量不超过其库存数

2.各客户收到的货物总量等于其订货数量3.决策变量非负数学模型为/sundae_meng

前面介绍的LinGO的基本用法，其优点是输入模型较直观，一般的数学表达式无需作大的变换即可直接输入.对于规模较小的的规划模型，用直接输入的方法是有利的，如果模型的变量和约束的条件个数比较多，若仍然用直接的输入方式，虽然也能求解并得到结果，但这种做法有明显的不足之处。模型的篇幅很长，不便于分析修改和扩展。

LinGO建模语言引入集合的概念，为建立大规模的数学规划模型提供了方便.用LinGO语言表达一个实际优化问题，称之为LinGO模型。

一、集合定义部分

集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与常量联系起来，是实际问题到数学的抽象。例中的6个仓库可以看成一个集合，8个客户可以看成另一个集合。/sundae_meng

每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容：集合的名称，集合内的成员（元素）、集合的属性（可以看成与该集合有关的变量或常量，相当于数组）.本例首先定义仓库集合：WH/W1..W6/:AI;

其中WH是集合的名称，W1..W6是集合内的成员，“..”是特定的省略号（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或空格分开),表明该集合有6个成员，分别对应于6个供货栈，AI是集合的属性，它可以看成是一个数组，有6个分量，分别表示各货栈现有货物的总数。集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义的字母数串来表示，式中“/”和“/:”是规定的语法规则。本例再定义客户集合：VD/V1..V8/:DJ;该集合有8个成员，DJ是集合的属性（有8个分量）表示各客户的需求量.以上两个集合称为初始集合（或称基本集合、原始集合）初始集合的属性都相当于一维数组。/sundae_meng为表示数学模型中从货栈到客户的运输关系以及与此相关的运输单价和运量再定义一个表示运输关系的集合：LINKS(WH,VD):C,X;该集合以初始集合WH和VD为基础，称为衍生集合（或称派生集合）.C和X是该衍生集合的两个属性，衍生集合的定义语句有如下要素组成：1）集合的名称；

(2)集合的初始集合；（3）集合的成员（可以省略不写）；（4）集合的属性（可以没有）

定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来，如果省略不写，则默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合LINKS的定以中没有指明成员，则它对应的初始集合WH有6个成员，VD有8个成员，因此LINKS成员取WH和VD的所有可能组合，即有48个成员，48个成员可以排列成一个矩阵。其行数与集合WH的成员个数相等，列数与集合VD成员的个数相等.相应地，集合LINKS的属性Ｃ和Ｘ都相当于二维数组，各有48个分量，Ｃ表示货栈Ｗi到客户Vj的单位货物运价

X表示货栈Wi到客户Vj的货物运量./sundae_meng本模型完整的集合定义为：SETS:WH/W1..W6/:AI;VD/V1..V8/DJ;LINKS(WH,VD):C,X;ENDSETS注：集合定义部分以语句SETS:开始，以ENDSETS语句结束，这两个语句需单独成一行，ENDSETS后面不加标点符号.二、数据初始化（数据段）

以上集合中属性X（有48个分量）是决策变量，是待求的未知数，属性AI、DJ和Ｃ（分别有６,8,48个分量）都是已知数，LINKS建模语言通过数据初始化部分来实现对已知属性赋以初始值，格式为：DATA:AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;C=6,2,6,7,4,2,5,94,9,5,3,8,5,8,25,2,1,9,7,4,3,37,6,7,3,9,2,7,12,3,9,5,7,2,6,55,5,2,2,8,1,4,3;ENDDATA注：数据初始化部分以语句DATA:开始，以ENDDATE语句结束，这两个语句需单独成一行，数据之间的逗号和空格可以互换。/sundae_meng三、目标函数和约束条件目标函数表达式

用LINGO语句表示为MIN=@SUM(LINKS(I,J):C(I,J)*X(I,J));

式中，@SUM是LINGO提供的内部函数，其作用是对某个集合的所有成员求制定表达式的和，该函数需要两个参数，第一个参数是集合名称，制定对该集合的所有成员求和，如果此集合是一个初始集合，它有m个成员，则求和运算对m个成员进行，相当于求，第二个参数是一个表达式，表示求和运算对该表达式进行，此处，@SUM的第一个参数是LINKS（I，J），表示求和运算对LINKS进行，该集合的维数为2，共有48个成员，运算规则是：先对48个成员分别求表达式C(I,J)*X(I,J)的值，然后求和，相当于求，表达式中的C和X是集合的两个属性，它们各有48个分量。注：如果表达式中参与酸的属性属于同一个集合，则语句中索引（相当于矩阵或数组的下标可以省略）（隐藏），假如表达式中参与运算的属性属于不同的集合，则不能省略属性的索引.本例的目标函数可以表示成MIN=@SUM(LINKS:C*X);/sundae_meng约束条件用ＬINGO语言描述该约束条件，语句为：@FOR(WH(I):@SUM(VD(J):X(I,J))<=AI(I));语句中的@FOR是LINGO提供的内部函数，它的作用是对某个集合的所有成员分别生成一个约束表达式，它有两个参数，第一个参数是集合名，表示对该集合的所有成员生成对应的约束表达式，上式@FOR的第一个参数为ＷＨ，它表示货栈，共有６个成员，故应生成６个约束表达式，@FOR的第二个参数是约束表达式的具体内容，此处再调用@SUM函数，表示该约束的左边是求和，是对集合ＶＤ的８个成员，并且对表达式Ｘ(I,J)中的第二维J求和，即约束表达式的右边是集合ＷＨ的属性AI，它有6个分量，与6个约束表达式一一对应，本句中的属性分别属于不同的集合，所以不能省略I,J.约束条件表示为@FOR(D(J)):@SUM(VD(J):X(I,J))=DJ(J));/sundae_meng完整的模型MODEL:SETS:WH/W1..W6/:AI;VD/V1..V8/:DJ;LINKS(WH,VD):C,X;ENDSETSDATA:AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;C=6,2,6,7,4,2,5,94,9,5,3,8,5,8,25,2,1,9,7,4,3,37,6,7,3,9,2,7,12,3,9,5,7,2,6,55,5,2,2,8,1,4,3;ENDDATAMIN=@SUM(LINKS(I,J):C(I,J)*X(I,J));!目标函数@FOR(WH(I):@SUM(VD(J):X(I,J))<=AI(I));!约束条件@FOR(VD(J):@SUM(VD(J):X(I,J))=DJ(J));END以“MODEL：”开始集合定义部分从(“SETS：”到“ENDSETS”)：定义集合及其属性以“END”结束给出优化目标和约束集合定义部分从(“DATA：”到“ENDDATA”)/sundae_meng整数规划

-----IntegerProgramming,IP整数规划（IntegerProgramming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。所有变量都要求为整数的称为纯整数规划（PureInteger

Programming）或称全整数规划（AllintegerProgramming）；仅有一部分变量要求为整数的称为混合整数规划（MixedIntegerProgramming）；有的变量限制其取值只能为0或1，这类特殊的整数规划称为0－1规划(0-1

IntegerProgramming)/sundae_meng整数规划问题及其数学模型例某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？设备材料甲乙资源限量材料A（kg）2314材料B（kg）10.54.5利润（元/件）32

/sundae_meng解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：Maxz=3x1+2x22x1+3x2≤14x1+0.5x2≤4.5x1、x2≥0,且为整数图4－1/sundae_meng要求该模型的解，不考虑整数约束条件，用图解法对相应线性规划求解，其最优解为：x1＝3.25x2＝2.5maxz＝14.75----凑整得到的（4，2）不在可行域范围内。--（3，2）点尽管在可行域内，但没有使目标达到极大化。--（4，1）使目标函数达到最大，即z＝14。IP可用LINDO直接求解max3x1+2x2st2x1+3x2<14x1+0.5x2<4.5endgin2“gin2”表示“前2个变量为整数”，等价于：ginx1ginx2其中“GIN2”表示2个变量都是一般整数变量。

（仍然默认为取值是非负的）/sundae_mengLINDO可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与LP问题类似,但需在END标志后定义整型变量。0/1型的变量可由INTEGER（可简写为INT）命令来标识，有以下两种可能的用法：

INTvname

INTn前者只将决策变量vname标识为0/1型,后者将当前模型中前n个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定,该顺序可由输出结果中的变量顺序查证是否一致）。一般的整数变量可用命令GIN（是GENERALINTEGER的意思）,其使用方式及格式与INT命令相似。。/sundae_mengSETX2TO<=2AT1,BND=14.50TWIN=13.507SETX1TO>=4AT2,BND=14.00TWIN=13.0010NEWINTEGERSOLUTIONOF14.0000000ATBRANCH2PIVOT10BOUNDONOPTIMUM:14.00000DELETEX1ATLEVEL2DELETEX2ATLEVEL1ENUMERATIONCOMPLETE.BRANCHES=2PIVOTS=10LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)14.00000VARIABLEVALUEREDUCEDCOSTX14.000000-3.000000X21.000000-2.000000ROWSLACKORSURPLUSDUALPRICES2)3.0000000.0000003)0.0000000.000000NO.ITERATIONS=10BRANCHES=2DETERM.=1.000E0最优值松弛和剩余变量（SLACKORSURPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCEDCOST和DUALPRICES的结果在整数规划中意义不大。

/sundae_meng例2、集装箱运货

货物体积(米3/箱)重量(百公斤/箱)利润(千元/箱)

甲5220

乙4510

装运限制2413/sundae_meng解：设X1,X2为甲、乙两货物各托运箱数5X1+4X2

242X1+5X2

13X1,X20X1,X2为整数maxZ=20X1+

10X2/sundae_meng例3、背包问题背包可装入8单位重量，10单位体积物品物品名称重量体积价值

1书52202摄像机31303枕头14104休闲食品23185衣服4515/sundae_meng解：Xi为是否带第i种物品maxZ=20X1+

30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5

82X1+X2+4X3+3X4+5X510Xi为0,1Model:Min=-(20*x1+30*x2+10*x3+18*x4+15*x5);5*x1+3*x2+x3+2*x4+4*x5<8;2*x1+x2+4*x3+2*x4+5*x5<10;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);ENDModel:Lingo求解/sundae_mengGlobaloptimalsolutionfound.Objectivevalue:-58.00000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX10.000000-20.00000X21.000000-30.00000X31.000000-10.00000X41.000000-18.00000X50.000000-15.00000RowSlackorSurplusDualPrice1-58.00000-1.00000022.0000000.00000033.0000000.000000/sundae_meng0－1整数规划用(Applications)（一）相互排斥的计划(Mutuallyexclusiveplanning)例4.6某公司拟在市东、西、南三区中建立门市部，有7个点Ai（i＝1，2，…，7）可供选择，要求满足以下条件：（1）在东区，在A1，A2，A3三个点中至多选两个；（2）在西区，A4，A5两个点中至少选一个；（3）在南区，A6，A7两个点为互斥点。（4）选A2点必选A5点。若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的0－1规划模型。/sundae_meng解：设决策变量为建立0－1规划模型如下：/sundae_meng（二）相互排斥的约束条件(Mutuallyexclusiveconstraints)例4.7某产品有A1和A2两种型号，需要经过B1、B2、B3三道工序，单位工时和利润、各工序每周工时限制见表所示，问工厂如何安排生产，才能使总利润最大？（B3工序有两种加工方式B31和B32，产品为整数）。 工时/件工序

型号B1B2B3利润（元/件）B31B32A10.30.20.30.225A20.70.10.50.440每周工时（小时/月）250100150120

/sundae_meng解：设A1、A2产品的生产数量分别为x1、x2件，在不考虑B31和B32相互排斥的情况下，问题的数学模型为/sundae_meng工序B3只能从两种加工方式中选择一种，那么约束条件（1）和（2）就成为相互排斥的约束条件。为了统一在一个问题中，引入0-1变量则数学模型为/sundae_meng（三）固定成本问题(Fixedcostproblem)例4.8某公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示：不考虑固定费用，小、中、大号容器每售出一个其利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，若生产，不管每种容器生产多少，都需要支付一笔固定费用：小号为100万元，中号为150万元，大号为200万元。问如何制定生产计划使获得的利润最大？资源小号容器中号容器大号容器金属板（吨）248劳动力（人/月）234机器设备（台/月）123/sundae_meng解：设x1、x2、x3分别为小号容器、中号容器、大号容器的生产数量。不考虑固定费用，则问题的数学模型为/sundae_meng若考虑固定费用就必须引入0—1变量：则该问题的数学模型为可以看出，当xj>0时，为使Z极大化，应有Yj=0/sundae_meng（四）布点问题(LocationProblem)例4.9

某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表4－9，请帮助该市制定一个布点最少的计划。表4－9消防车在各区间行驶时间表单位：min

地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140/sundae_meng解：引入0－1变量xi作决策变量，令本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表4－9可知，在地区1及地区2内设消防站都能达到此要求，即x1＋x2≥1因此本问题的数学模型为：

minz＝x1＋x2＋x3＋x4＋x5＋x6

x1＋x2≥1