数学建模优化模型介绍.ppt

《数学建模优化模型介绍.ppt》由会员分享，可在线阅读，更多相关《数学建模优化模型介绍.ppt（134页珍藏版）》请在三一办公上搜索。

1、数学建模,优化模型介绍,引言-数学之重要,数学使人周密-Francis Bacon,数学处于人类智能的中心领域数学方法渗透、支配着一切自然科学的理论分支它已愈来愈成为衡量成就的主要标志。-von Neumann,引言-数学之重要,一门科学只有当它达到能够成功地运用 数学时，才算真正发展了。-Karl Marx,Galileo:展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像在黑暗的迷宫里游荡，什么也认识不清。,引言-数学之重要,数学技术-数学方法与计算技术的结合形 成的一种关键性的、可实现的技术,二十世纪最伟大的数学家-,二十世纪最伟大的物理学家-,D.Hilbert

2、,A.Einstein,Go back,诺贝尔奖,菲尔兹奖,1.什么是数学模型？,数学模型是对于现实世界的一个特定对象，一个特定目的，根据特有的内在规律，做出一些必要的假设，运用适当的数学工具，得到一个数学结构 简单地说：就是系统的某种特征的本质的数学表达式（或是用数学术语对部分现实世界的描述），即用数学式子（如函数、图形、代数方程、微分方程、积分方程、差分方程等）来描述（表述、模拟）所研究的客观对象或系统在某一方面的存在规律,2.什么是数学建模?,数学建模是利用数学方法解决实际问题的一种实践即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，然后运用先进的

3、数学方法及计算机技术进行求解,观点：“所谓高科技就是一种数学技术”,数学建模其实并不是什么新东西，可以说有了数学并需要用数学去解决实际问题，就一定要用数学的语言、方法去近似地刻画该实际问题，这种刻划的数学表述的就是一个数学模型，其过程就是数学建模的过程数学模型一经提出，就要用一定的技术手段（计算、证明等）来求解并验证，其中大量的计算往往是必不可少的，高性能的计算机的出现使数学建模这一方法如虎添翼似的得到了飞速的发展，掀起一个高潮 数学建模将各种知识综合应用于解决实际问题中，是培养和提高同学们应用所学知识分析问题、解决问题的能力的必备手段之一.,数学建模参考书,1.数学模型 姜启源、谢金星、叶俊

4、编 高等教育出版社,2.数学建模方法及其应用 解放军信息工程大学 韩中庚编 高教社,3.数学模型与数学建模 刘来福、曾文艺编著 北师大出版社,4.叶其孝等，大学生数学建模竞赛辅导教材（一）（四），湖南教育出版社,5.赵静等，数学建模与数学实验，高等教育出版社，施普林格出版社,规划模型的应用极其广泛，其作用已为越来,来越急速地渗透于工农业生产、商业活动、军事,行为 科学研究的各个方面，为社会节省的财富、,创造的价值无法估量.,特别是在数模竞赛过程中，规划模型是最常,见的一类数学模型.从92-06年全国大学生数模竞,越多的人所重视.随着计算机的逐渐普及，它越,赛试题的解题方法统计结果来看，规划模型

5、共出,现了15次，占到了50%，也就是说每两道竞赛题,中就有一道涉及到利用规划理论来分析、求解.,优化问题，一般是指用“最好”的方式，使用或分配有限的资源，即劳动力、原材料、机器、资金等，使得费用最小或者利润最大。,优化模型,min f(x)-目标函数 s.t.xS-约束集合，可行集其中，S Rn，f:S R，xS称（f S)的可行解最优解:x*S，满足f(x*)f(x),xS。则称 x*为(f S)的全局最优解(最优解),记 g.opt.(global optimum),简记 opt.最优值:x*为(f S)的最优解,则称 f*=f(x*)为(f S)的最优值(最优目标函数值),数学规划模型

6、的一般形式,(f S),局部最优解:x*S，x*的邻域 N(x*)，使满足 f(x*)f(x),x S N(x*)。则称 x*为(f S)的局部最优解,记 l.opt.(local optimum)在上述定义中，当x x*时有严格不等式成立，则分别称 x*为(f S)的严格全局最优解和严格局部最优解。,严格l.opt.,严格g.opt.,l.opt.,数学规划模型的一般形式,函数形式:f(x),gi(x),hj(x):RnR min f(x)(fgh)s.t.gi(x)0,i=1,2,m hj(x)=0,j=1,2,l矩阵形式:min f(x)，f(x):RnR(fgh)s.t.g(x)0,g

7、(x):RnRm h(x)=0,h(x):RnRl 当 f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。,优化模型的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问

8、题求解的难度增加,线性规划,Linear Programming,问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,两个引例,建立线性规划模型的基本步骤：,（1）设出决策变量,（2）确定目标函数,（3）确定约束条件,找出待定的未知变量（决策变量），并用代数符号表示,找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值,找出问题的所

9、有的限制或约束，写出未知变量的线性方程或 线性不等式,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：,解答,问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员

10、的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,线性规划模型：,解答,返 回,模型特点：目标函数(Objective function)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。,线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn(=,)b1 a21x1+a22x2+.+a2nxn(=,)b2.am1x1+am2x2+.+amnxn(=,)bm x1,x2.xn 0,线性规划的基本概念,1.可行解(Feasible Solution)任一满足约束条件的一组决策变量的数

11、值.,2.可行域(Feasible Region)所有可行解组成的集合，也称为可行解集.,3.目标函数等值线(Objective function line)为于同一直线上的点，具有相同的目标函数值.,线性规划模型的解的几种情况,数学建模中线性规划模型的常用解法 线性规划问题的求解在理在理论上有单纯型法，在实际建模中常用以下解法：,1.图解法,2.LINGO软件包,3.Excel中的规划求解,4.MATLAB 软件包,主要介绍线性规划模型的MATlAB软件包和LINGO软件包解法,模型求解方法,1.图解法,例1 max z=50 x1+100 x2 x1+x2300 2x1+x2400 x22

12、50 x1、x20 该问题的最优解为x1=50；x2=250,用MATLAB优化工具箱解线性规划,命令：x=linprog（c,A,b）,2.模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,式中：linprog 称为调用函数，C,A,b 称为输入参数，全部由用户提供，必须按规定的位置放置在原括号内.,命令：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表示初始点

13、,设置它有些情况下可以减少迭代工作量,4.命令：x,fval=linprog()返回最优解及处的目标函数值fval.,解 编写M文件xxgh1.m如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.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%2

14、0Settings/Administrator/%E6%A1%8C%E9%9D%A2/%E6%95%B0%E5%AD%A6%E6%A8%A1%E5%9E%8B/MATLAB6p1/bin/win32/matlab.exe),解:编写M文件xxgh2.m如下：c=6 3 4;A=0 1 0;b=50;Aeq=1 1 1;beq=120;vlb=30,0,20;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh2),例3 问题一的解答,问题,编写M文件xxgh3.m如下:f=13 9 10 11 12 8;A=0.4 1.1 1 0

15、0 0 0 0 0 0.5 1.2 1.3;b=800;900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh3),结果:x=0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.,例2 问

16、题二的解答,问题,改写为：,编写M文件xxgh4.m如下：c=40 36;A=-5-3;b=-45;Aeq=;beq=;vlb=zeros(2,1);vub=9 15;%调用linprog函数：x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh4),结果为：x=9.0000 0.0000fval=360即只需聘用9个一级检验员.,注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数

17、，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.,返 回,用LINDO、LINGO优化工具箱解线性规划,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司（LINDO Systems Inc.），网址：,LINDO:Linear INteractive and Discrete Optimizer(V6.1)LINGO:Linear INteractive General Optimizer(V8.0)LINDO API:LINDO Application Progra

18、mming Interface(V2.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V7.0),演示(试用)版、学生版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,LINDO和LINGO软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划(LP),非线性规划(NLP),二次规划(QP),连续优化,整数规划(IP),一、LINDO软件包,下面我们通过一个例题来说明LINDO软件包的使用方法.,问题：一奶制品加工厂用牛奶生产A1,A2 两种奶制品，一桶牛奶可以在甲类设备上用12小时生产成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2.据

19、市场要求，生产的两种奶制品全部能售出，且每公斤 A1获利24元，每公斤A2获利16元，现在每天加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力没有限制.试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题。,1）若用35元可以买到1桶牛奶，应否作这样的投资？若投资，每天最多购买多少桶牛奶2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利

20、164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100kgA1,基本模型,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINDO,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE

21、VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000,DO RANGE(SENSITIVITY)ANALYSIS?,No,结果解释,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.00

22、0000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,原料无剩余,时间无剩余,加工能力剩余40,结果解释,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000

23、 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000,最优解下“资源”增加1单位时“效益”的增量,35元可买到1桶牛奶，要买吗?,35 48,应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,影子价格,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRE

24、NT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围

25、,DO RANGE(SENSITIVITY)ANALYSIS?,Yes,A1获利增加到 30元/kg，应否改变生产计划?,x1系数由24 3=72增至303=9096,在允许范围内,不变！,约束条件不变!,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTH

26、AND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,35元可买到1桶牛奶,每天最多买多少?,最多买10桶!,目标函数不变!,原料最多增加10,时间最多增加53,原料,时间,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）,目标函数减少的量

27、(对max型问题).,OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,1.使用LINDO的一些注意事项？,“”（或“=”（或“=”）功能相同

28、变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义.行名以“）”结束行中注有“!”符号的后面部分为注释.如:!Its Comment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLE This Model is only an Example,变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2-4X1应写

29、成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界 例如：“sub x1 10”的作用等价于“x1=10”但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析.14.“END”后对0-1变量说明：INT n 或 INT name15.“END”后对整数变量说明：GIN n 或 GIN name,使用LINDO的一些注意事项,2.状态窗口（LINDO Solver Status）,当前状态：已达最优解迭代次数：18次约束不满足的“量”(

30、不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒),二、LINGO软件包,(1)LINGO模型的优点,1.LINGO软件简介,(2)对简单的LINGO程序,LINGO也可以和LINDO一样编程,但LINGO与LINDO语法有差异,提供了灵活的编程语言（矩阵生成器）,包含了LINDO的全部功能,Lindo与简单Lingo程序的比较,Model:min=7*x1+3*x2;x1+x2=345.5;x1=98;2*x1+x2=600;gin(x1);gin(x2);end,min 7x

31、1+3x2st x1+x2=345.5 x1=98 2*x1+x2=600end gin 2,lindo程序:,lingo程序:,实验作业,某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过800箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每100箱甲饮料获利可增加1万元,问应否改变生产计划.,返 回,运输问题-Transportation Probl

32、em,运输问题(Transportation Problem)以知有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，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。,产销平衡表(cost and requirement table),若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如

33、下（模型Y）,产销不平衡的运输问题-Total Supply not Equal to Total Demand,一、产大于销(total supply exceeds total demand)产大于销的运输问题的特征是ai bj，其数学模型为：,解此类问题可假想一个销地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+

34、1个销地的平衡运输问题，此时可用表上作业法求解。,二、销大于产(total demand exceeds total supply)销大于产的运输问题的特征是ai bj，其数学模型为：,解此问题可假想一个产地Am+1，其产量为：am+1=bjai；若用xm+1，j表示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：,此时，可用表上作业法求解。,例 某公司有6个供货栈（仓库），库存货物总数分别为60，55，51，43，41，52，现有8个客户各要一批货数量分别为

35、35，37，22，32，41，32，43，38，各供货栈道8个客户的单位货物运输价见表,供货栈到客户的单位货物运价,试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。,解 引入决策变量,代表从第,个货栈到第,个,客户的货物运量.,设,表示从第,个货栈到第 个客户的单位货物运价,表示第,个货栈的最大供货量,表示第,个客户的订货量.,目标函数是总运输费用最少.,约束条件有三条：1.各货栈运出的货物总量不超过其库存数 2.各客户收到的货物总量等于其订货数量3.决策变量 非负,数学模型为,前面介绍的LinGO的基本用法，其优点是输入模型较直观，一般的数学表达式无需作大的变换即可直接输入.对于规

36、模较小的的规划模型，用直接输入的方法是有利的，如果模型的变量和约束的条件个数比较多，若仍然用直接的输入方式，虽然也能求解并得到结果，但这种做法有明显的不足之处。模型的篇幅很长，不便于分析修改和扩展。LinGO 建模语言引入集合的概念，为建立大规模的数学规划模型提供了方便.用LinGO 语言表达一个实际优化问题，称之为 LinGO模型。,一、集合定义部分,集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与常量联系起来，是实际问题到数学的抽象。例中的6个仓库可以看成一个集合，8个客户可以看成另一个集合。,每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容：集合的名称，

37、集合内的成员（元素）、集合的属性（可以看成与该集合有关的变量或常量，相当于数组）.,本例首先定义仓库集合：WH/W1.W6/:AI;,其中WH是集合的名称，W1.W6是集合内的成员，“.”是特定的省略号（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或空格分开),表明该集合有6个成员，分别对应于6个供货栈，AI是集合的属性，它可以看成是一个数组，有6个分量，分别表示各货栈现有货物的总数。,集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义的字母数串来表示，式中“/”和“/:”是规定的语法规则。,本例再定义客户集合：VD/V1.V8/:DJ;,该集合有8个成员，DJ

38、是集合的属性（有8个分量）表示各客户的需求量.,以上两个集合称为初始集合（或称基本集合、原始集合）初始集合的属性都相当于一维数组。,为表示数学模型中从货栈到客户的运输关系以及与此相关的运输单价 和运量,再定义一个表示运输关系的集合：,LINKS(WH,VD):C,X;,该集合以初始集合WH 和 VD 为基础，称为衍生集合（或称派生集合）.C 和,X 是该衍生集合的两个属性，衍生集合的定义语句有如下要素组成：,1）集合的名称；(2)集合的初始集合；（3）集合的成员（可以省略不写）；（4）集合的属性（可以没有）,定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来，如果省略不写，则默认衍生集合

39、的成员取它所对应初始集合的所有可能组合，上述衍生集合LINKS的定以中没有指明成员，则它对应的初始集合WH 有6个成员，VD 有8 个成员，因此 LINKS成员取WH和VD的所有可能组合，即有48个成员，48个成员可以排列成一个矩阵。其行数与集合WH的成员个数相等，列数与集合VD成员的个数相等.相应地，集合LINKS的属性和都相当于二维数组，各有48个分量，表示货栈i 到客户Vj的单位货物运价 X 表示货栈Wi到客户Vj的货物运量.,本模型完整的集合定义为：SETS:WH/W1.W6/:AI;VD/V1.V8/DJ;LINKS(WH,VD):C,X;ENDSETS,注：集合定义部分以语句 SE

40、TS:开始，以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,9 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

41、,1,4,3;ENDDATA,注：数据初始化部分以语句 DATA:开始，以ENDDATE语句结束，这两个语句需单独成一行，数据之间的逗号和空格可以互换。,三、目标函数和约束条件,目标函数表达式,用LINGO语句表示为,MIN=SUM(LINKS(I,J):C(I,J)*X(I,J);,式中，SUM 是LINGO提供的内部函数，其作用是对某个集合的所有成员求制定表达式的和，该函数需要两个参数，第一个参数是集合名称，制定对该集合的所有成员求和，如果此集合是一个初始集合，它有m 个成员，则求和运算对m 个成员进行，相当于求，第二个参数是一个表达式，表示求和运算对该表达式进行，此处，SUM的第一个参数

42、是 LINKS（I，J），表示求和运算对 LINKS进行，该集合的维数为2，共有48个成员，运算规则是：先对48个成员分别求表达式 C(I,J)*X(I,J)的值，然后求和，相当于求，表达式中的 C和 X是集合的两个属性，它们各有48个分量。,注：如果表达式中参与酸的属性属于同一个集合，则 语句中索引（相当于矩阵或数组的下标可以省略）（隐藏），假如表达式中参与运算的属性属于不同的集合，则不能省略属性的索引.本例的目标函数可以表示成,MIN=SUM(LINKS:C*X);,约束条件,用INGO 语言描述该约束条件，语句为：FOR(WH(I):SUM(VD(J):X(I,J)=AI(I);,语句中

43、的FOR是LINGO提供的内部函数，它的作用是对某个集合的所有成员分别生成一个约束表达式，它有两个参数，第一个参数是集合名，表示对该集合的所有成员生成对应的约束表达式，上式 FOR 的第一个参数为，它表示货栈，共有个成员，故应生成个约束表达式，FOR 的第二个参数是约束表达式的具体内容，此处再调用SUM 函数，表示该约束的左边是求和，是对集合的个成员，并且对表达式(I,J)中的第二维 J 求和，即,约束表达式的右边是集合的属性AI，它有6个分量，与6个约束表达式一一对应，本句中的属性分别属于不同的集合，所以不能省略 I,J.,约束条件,表示为,FOR(D(J):SUM(VD(J):X(I,J)

44、=DJ(J);,完整的模型,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,9 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;ENDDATAMIN=SUM(LINKS(I,J):C(I,J)*X(I,J);!目标函数FOR(WH(I):SUM(VD(J):X(I,J)=AI

45、(I);!约束条件FOR(VD(J):SUM(VD(J):X(I,J)=DJ(J);END,以“MODEL：”开始,集合定义部分从(“SETS：”到“ENDSETS”)：定义集合及其属性,以“END”结束,给出优化目标和约束,集合定义部分从(“DATA：”到“ENDDATA”),整数规划-Integer Programming,IP,整数规划（Integer Programming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。所有变量都要求为整数的称为纯整数规划（Pure Integer Programming）或称全整数规划（All integ

46、er Programming）；仅有一部分变量要求为整数的称为混合整数规划（Mixed Integer Programming）；有的变量限制其取值只能为0或1，这类特殊的整数规划称为01规划(0-1 Integer Programming),整数规划问题及其数学模型例 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？,解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：,Maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20,且为整数,图41,要求该

47、模型的解，不考虑整数约束条件，用图解法对相应线性规划求解，其最优解为：x13.25 x22.5 max z14.75,-凑整得到的（4，2）不在可行域范围内。-（3，2）点尽管在可行域内，但没有使目标达到极大化。-（4，1）使目标函数达到最大，即z14。,IP可用LINDO直接求解,max 3x1+2x2st2x1+3x214x1+0.5x24.5endgin 2,“gin 2”表示“前2个变量为整数”，等价于：gin x1gin x2,其中“GIN 2”表示2个变量都是一般整数变量。（仍然默认为取值是非负的）,LINDO可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与LP问题类似

48、,但需在END标志后定义整型变量。,0/1型的变量可由INTEGER（可简写为INT）命令来标识，有以下两种可能的用法：INT vname INT n前者只将决策变量vname标识为0/1型,后者将当前模型中前n 个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定,该顺序可由输出结果中的变量顺序查证是否一致）。,一般的整数变量可用命令GIN（是GENERAL INTEGER的意思）,其使用方式及格式与INT 命令相似。,SET X2 TO=4 AT 2,BND=14.00 TWIN=13.00 10 NEW INTEGER SOLUTION OF 14.0000000 AT

49、BRANCH 2 PIVOT 10 BOUND ON OPTIMUM:14.00000 DELETE X1 AT LEVEL 2 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE.BRANCHES=2 PIVOTS=10 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)14.00000 VARIABLE VALUE REDUCED COST X1 4.000000-3.000000 X2 1.000000-2.00000

50、0 ROW SLACK OR SURPLUS DUAL PRICES 2)3.000000 0.000000 3)0.000000 0.000000 NO.ITERATIONS=10 BRANCHES=2 DETERM.=1.000E 0,最优值,松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCED COST和DUAL PRICES的结果在整数规划中意义不大。,例2、集装箱运货,解：设X1,X2 为甲、乙两货物各托运箱数,maxZ=20 X1+10 X2,例3、背包问题,背包可装入8单位重量，10单位体积物品,