【大学竞赛】数学建模辅导 优化部分ppt(P134)

1、数学建模数学建模 优化模型介绍引言-数学之重要数学使人周密数学使人周密 - francis bacon 数学处于人类智能的中心领域数学处于人类智能的中心领域数学方数学方法渗透、支配着一切自然科学的理论分支法渗透、支配着一切自然科学的理论分支它已愈来愈成为衡量成就的主要标志。它已愈来愈成为衡量成就的主要标志。 - von neumann 引言-数学之重要 一门科学只有当它达到能够成功地运用一门科学只有当它达到能够成功地运用 数学时，才算真正发展了。数学时，才算真正发展了。 - - karl marxgalileo : : 展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像

2、在黑暗的迷宫里游荡，什么也认识不清。数学是一种语言，是一切科学的共同语言数学是一种语言，是一切科学的共同语言引言-数学之重要数学是一种技术，是高技术的本质数学是一种技术，是高技术的本质数学技术数学技术-数学方法与计算技术的结合形 成的一种关键性的、可实现的技术二十世纪最伟大的数学家-二十世纪最伟大的物理学家-d.hilberta.einsteingo back诺贝尔诺贝尔奖奖菲尔兹奖菲尔兹奖1. 什么是数学模型？什么是数学模型？ 数学模型数学模型是对于现实世界的一个特定对象特定对象，一个特定目的特定目的，根据特有的内在规律内在规律，做出一些必要的假必要的假设设，运用适当的数学工具数学工具，得到

3、一个数学结构数学结构 简单地说：就是系统的某种特征的本质的数学表达式（或是用数学术语对部分现实世界的描述），即用数学式子（如函数、图形、代数方程、微分方程、积分方程、差分方程等）来描述（表述、模拟）所研究的客观对象或系统在某一方面的存在规律2. 什么是数学建模什么是数学建模? 数学建模数学建模是利用数学方法解决实际问题的一种实践即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，然后运用先进的数学方法及计算机技术进行求解 观点：观点：“所谓所谓高科技高科技就是一种就是一种数学技术数学技术” 数学建模数学建模其实并不是什么新东西，可以说有了数学并需要用数学去解

4、决实际问题，就一定要用数学的语言、方法去近似地刻画该实际问题，这种刻划的数学表述的就是一个数学模型，其过程就是数学建模的过程数学模型一经提出，就要用一定的技术手段（计算、证明等）来求解并验证，其中大量的计算往往是必不可少的，高性能的计算机的出现使数学建模这一方法如虎添翼似的得到了飞速的发展，掀起一个高潮 数学建模将各种知识综合应用于解决实际问题中，是培养和提高同学们应用所学知识分析问题、解决问题的能力的必备手段之一.数学建模参考书数学建模参考书1.数学模型 姜启源、谢金星、叶俊编 高等教育出版社 2.数学建模方法及其应用 解放军信息工程大学 韩中庚编 高教社 3.数学模型与数学建模 刘来福、曾

5、文艺编著 北师大出版社4. 叶其孝等，大学生数学建模竞赛辅导教材（一）（四），湖南教育出版社5.赵静等，数学建模与数学实验，高等教育出版社，施普林格出版社 规划模型的应用极其广泛，其作用已为越来规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事行为行为 科学研究的各个方面，为社会节省的财富、科学研究的各个方面，为社会节省的财富、创造的价值无法估量创造的价值无法估量. 特别是在数模竞赛过程中，规划模型是最常特别是在数模竞赛过程中，规划模型是最常见的一类数学模型见的一类数学模型. 从从92-06年全国大学生数模竞年全国大学生数

6、模竞越多的人所重视越多的人所重视. 随着计算机的逐渐普及，它越随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出赛试题的解题方法统计结果来看，规划模型共出现了现了15次，占到了次，占到了50%，也就是说每两道竞赛题，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解. 优化问题，一般是指用“最好”的方式，使用或分配有限的资源，即劳动力、原材料、机器、资金等，使得费用最小或者利润最大。优化模型优化模型min min f(x) -目标函数目标函数 s.t. s.t. x s -约束集合，可行集约束集合，可行集其中，其中，s r r

7、n n，f : :s r r，x s称（称（f s ) )的可行解的可行解n最优解最优解: : x* s，满足满足f (x*) f (x), x s。则称则称 x*为为( (f s) )的全局最优解的全局最优解( (最优解最优解),), 记记 g.opt.( (global optimum),),简记简记 opt.n最优值最优值: : x*为为( (f s) )的最优解的最优解, , 则称则称 f * = f (x*) 为为 ( (f s) )的最优值的最优值( (最优目标函数值最优目标函数值) )数学规划模型的一般形式数学规划模型的一般形式(f s)n局部最优解局部最优解: : x* s，

8、x* 的邻域的邻域 n(x*) ，使满足，使满足 f (x*) f (x), x s n(x*) 。则称则称 x*为为( (f s) )的局部最的局部最优解优解, ,记记 l .opt.( (local optimum) )n在上述定义中，当在上述定义中，当x x* 时有严格不等式成立，时有严格不等式成立，则分别则分别称称 x* 为为( (f s) )的严格全局最优解和严格局部最优解的严格全局最优解和严格局部最优解。严格严格l .opt .严格严格g .opt .l .opt .数学规划模型的一般形式数学规划模型的一般形式 函数形式函数形式: f(x), gi(x) , hj(x) : rnr

9、 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(x) : rnrm h(x) = 0 , h(x) : rnrl 当当 f(x), gi(x) , hj(x)均为线性函数时，称线性均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划规划；若其中有非线性函数时，称非线性规划。优化模型的优化模型的简单分类简单分类 线性规划线性规划(lp) 目标和约束均为线性函数目标和约束均为线性函数 非线性规划非线性规划(

10、nlp) 目标或约束中存在非线性函数目标或约束中存在非线性函数 二次规划二次规划(qp) 目标为二次函数、约束为线性目标为二次函数、约束为线性 整数规划整数规划(ip) 决策变量决策变量(全部或部分全部或部分)为整数为整数 整数整数线性线性规划规划(ilp)，整数，整数非线性非线性规划规划(inlp) 纯整数规划纯整数规划(pip), 混合整数规划混合整数规划(mip) 一般整数规划，一般整数规划，0-1（整数）规划（整数）规划njidxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min连连续续优优化化离离散散优优化化数学规划数学规划优化模型的简单分类和求解难度优化模

11、型的简单分类和求解难度 优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划 问题求解的难度增加 线性规划线性规划linear programming问题一问题一 ： 任务分配问题任务分配问题：某车间有甲、乙两台机床，可用某车间有甲、乙两台机床，可用于加工三种工件于加工三种工件.假定这两台车床的可用台时数分别为假定这两台车床的可用台时数分别为800和和900，三种工件的数量分别为，三种工件的数量分别为400、600和和500，且已知用三种，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如不同车床加工单位数量不同工件所需的台时数和加工费用如

12、下表下表.问怎样分配车床的加工任务，才能既满足加工工件的要问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？求，又使加工费用最低？ 两个引例两个引例建立线性规划模型的基本步骤建立线性规划模型的基本步骤：（1）设出决策变量设出决策变量 （2）确定目标函数确定目标函数（3）确定约束条件确定约束条件找出待定的未知变量（决策变量），并用代数符号表示找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值 找出问题的所有的限制或约束，写出未知变量的线性方程或 线性不等式解解 设在甲车床上加工工件设在甲车床上加工工件1、2、3的数量分别为的数量分别为x1、x2、x3，在乙

13、车床上加工工件在乙车床上加工工件1、2、3的数量分别为的数量分别为x4、x5、x6,可建立以可建立以下线性规划模型：下线性规划模型： 解答问题二：问题二： 某厂每日某厂每日8小时的产量不低于小时的产量不低于1800件件.为了进行质量为了进行质量控制，计划聘请两种不同水平的检验员控制，计划聘请两种不同水平的检验员.一级检验员的标准为：一级检验员的标准为：速度速度25件件/小时，正确率小时，正确率98%，计时工资，计时工资4元元/小时；二级检验员小时；二级检验员的标准为：速度的标准为：速度15件件/小时，正确率小时，正确率95%，计时工资，计时工资3元元/小时小时.检检验员每错检一次，工厂要损失验

14、员每错检一次，工厂要损失2元元.为使总检验费用最省，该工为使总检验费用最省，该工厂应聘一级、二级检验员各几名？厂应聘一级、二级检验员各几名？解解 设需要一级和二级检验员的人数分别为设需要一级和二级检验员的人数分别为x1、x2人人,则应付检验员的工资为：则应付检验员的工资为：212124323848xxxx因检验员错检而造成的损失为因检验员错检而造成的损失为：21211282)%5158%2258(xxxx故目标函数为：故目标函数为：2121213640)128()2432(minxxxxxxz约束条件为：0, 0180015818002581800158258212121xxxxxx线性规划模

15、型：线性规划模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答返 回模型特点：目标函数模型特点：目标函数(objective function)与约束条件与约束条件(constraint)均为线性的；均为线性的；目标函数实现极大化或极小化。目标函数实现极大化或极小化。min( ). (max) s.tucxaxbvlbxvub矩矩阵阵形形式式：线性规划的线性规划的基本概念基本概念1.可行解可行解(feasible solution)任一满足约束条件的任一满足约束条件的一组决策变量的数值一组决策变量的数值.2.可行域可行域(feasible region

16、)所有可行解组成的集合，所有可行解组成的集合，也称为可行解集也称为可行解集. 3. 目标函数等值线目标函数等值线(objective function line)为于同一直线上的点，具有相同的目标函数值为于同一直线上的点，具有相同的目标函数值.线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有可行解有可行解(feasible)无可行解无可行解（infeasible）有最优解（有最优解（optimal）无最优解无最优解(unbounded) 数学建模中线性规划模型的常用解法数学建模中线性规划模型的常用解法 线性规划问题的求解在理在理论上有单纯型法，在实际建模线性规划

17、问题的求解在理在理论上有单纯型法，在实际建模中常用以下解法：中常用以下解法：1.图解法图解法2.lingo软件包软件包3.excel中的规划求解中的规划求解4. matlab 软件包软件包主要介绍线性规划模型的主要介绍线性规划模型的matlab软件包和软件包和lingo软件包解法软件包解法模型求解方法模型求解方法1. 图解法图解法例1 max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 该问题的最优解为该问题的最优解为x1=50=50；x2=250=250 x2z*=50 x1+100 x2=27500 x1 + x2300 x1x22

18、502x1 + x2400z1=50 x1+100 x2=0boacdz2=14000用用matlab优化工具箱解线性规划优化工具箱解线性规划min z=cx s.t.axb1. 模型：命令：x=linprog（c, a, b） 2. 模型：min z=cx s.t.axbbeqxaeq命令：x=linprog（c，a，b，aeq,beq）注意：若没有不等式： 存在，则令a= ，b= .bax 式中：linprog 称为调用函数，c, a, b 称为输入参数，全部由用户提供，必须按规定的位置放置在原括号内.3. 模型：min z=cx s.t.axbbeqxaeqvlbxvub命令：1 x=l

19、inprog（c，a，b，aeq, beq, vlb，vub） 2 x=linprog（c，a，b，aeq, beq, vlb，vub, x0） 注意：1 若没有等式约束: , 则令aeq= , beq= . 2其中x0表示初始点 ,设置它有些情况下可以减少迭代工作量beqxaeq4. 命令：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

20、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) to matlab (xxgh1)解解: 编写编写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)123m in( 634 )xzxx

21、32120030 xxx1231111 2 0s .t. 0105 0 xxxs.t.xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0x改写为：例例3 问题一的解答 问题问题编写编写m文件文件xxgh3.m如下如下:f = 13 9 10 11 12 8;a = 0.4 1.1 1 0 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 = linp

22、rog(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 问题二的解答 问题问题 213640minxxz s.t. )45(3521xx改写为：编写编写m文件文件xxgh4.m如下：如下：c = 40 36;a=-5 -3;b=-45;aeq=;beq=;vlb = zeros(2,1)

23、;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，故它就是该整数规划的最优解，故它就是该整数规划的最优解.若用线性规划若用线性规

24、划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解最优解，这样的整数规划应用专门的方法求解.返 回用用lindo、lingo优化工具箱解线性规划优化工具箱解线性规划lindo 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(chicago)大学的大学的linus schrage教授于教授于1980年前后开发年前后开发, 后来成立后来成立 lindo系统公司（系统公司（lindo systems inc.），）， 网址：网址：http:/ lindo: linear int

25、eractive and discrete optimizer (v6.1)lingo: linear interactive general optimizer (v8.0)lindo api: lindo application programming interface (v2.0)whats best!: (spreadsheet e.g. excel) (v7.0)演示演示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版 （求解（求解问题规模问题规模和和选件选件不同）不同）lindolindo和和lingolingo软件能求解的优化模型

26、软件能求解的优化模型 lingo lindo优化模型优化模型线性规划线性规划(lp)非线性规划非线性规划(nlp)二次规划二次规划(qp)连续优化连续优化整数规划整数规划(ip)一、一、lindo软件包软件包 下面我们通过一个例题来说明下面我们通过一个例题来说明lindo软件包的使用方法软件包的使用方法.问题：一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产a1, a2 两种奶制品，一桶两种奶制品，一桶牛奶可以在甲类设备上用牛奶可以在甲类设备上用12小时生产成小时生产成3公斤公斤a1，或者在乙类设，或者在乙类设备上用备上用8小时加工成小时加工成4公斤公斤a2.据市场要求，生产的两种奶制品全部据

27、市场要求，生产的两种奶制品全部能售出，且每公斤能售出，且每公斤 a1获利获利24元，每公斤元，每公斤a2获利获利16元，现在每天加元，现在每天加工厂每天能得到工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天至多能加工小时，并且甲类设备每天至多能加工100公斤公斤a1，乙类设备的，乙类设备的加工能力没有限制加工能力没有限制.试为该厂制定一个生产计划，使每天获利最大，试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下并进一步讨论以下3个附加问题。个附加问题。1）若用）若用35元可以买到元可以买到1桶牛奶，应否作这

28、样的投资？若投资，桶牛奶，应否作这样的投资？若投资，每天最多购买多少桶牛奶每天最多购买多少桶牛奶2）若可以聘用临时工人以增加劳动时间，付给临时工人的）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？工资最多是每小时几元？3）由于市场需求变化，每公斤）由于市场需求变化，每公斤a1的获利增加到的获利增加到30元，应否元，应否改变生产计划？改变生产计划？1桶桶牛奶牛奶 3kga1 12小时小时 8小时小时 4kga2 或或获利获利24元元/kg 获利获利16元元/kg x1桶牛奶生产桶牛奶生产a1 x2桶牛奶生产桶牛奶生产a2 获利获利 243x1 获利获利 164 x2 原料

29、供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 12max7264zxx每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(lp)时间时间480小时小时 至多加工至多加工100kga1 50桶牛奶桶牛奶 每天每天基本基本模型模型模型求解模型求解 图解法图解法 x1x20abcdl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl12max

30、7264zxx目标目标函数函数 z=0z=2400z=3600z =c (常数常数) 等值线等值线c在在b(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。 模型求解模型求解 软件实现软件实现 lindomax 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end objective function value 1) 3360.000 v

31、ariable 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.000000do range (sensitivity) analysis? no20桶牛奶生产桶牛奶生产a1, 30桶生产桶生产a2，利润，利润3360元。元。 结果解释结果解释 objective function value 1) 3360.000 variable v

32、alue 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.000000max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40结果解释结果解释

33、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最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量 35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?35 48, 应该买！应该买！ 聘用临时工人付出的工资最多每

34、小时几元聘用临时工人付出的工资最多每小时几元? 2元！元！原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位, 利润增长利润增长2 加工能力增长加工能力增长不不影响利润影响利润影子价格影子价格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 right

35、hand 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最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围 do range(sensitivity) analysis? yes a1获利增加到获利增加到 30元元/kg，应否改变生产计划，应否改变生产计划? x1系数由系数由24 3=72增至增至30

36、 3=90”（或（或“=”（或（或“=”）功能相同）功能相同2. 变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车), 但无运算符但无运算符3. 变量名以字母开头，不能超过变量名以字母开头，不能超过8个字符个字符4. 变量名不区分大小写（包括变量名不区分大小写（包括lindo中的关键字）中的关键字）5. 目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6. 行号行号(行名行名)自动产生或人为定义自动产生或人为定义.行名以行名以“）”结束结束7. 行中注有行中注有“!”符号的后面部分为注释符号的后面部分为注释.如如: ! its comment.8.

37、 在模型的任何地方都可以用在模型的任何地方都可以用“title” 对模型命名对模型命名（最多（最多72个字符），如：个字符），如： title this model is only an example9. 变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“( )”和逗号和逗号“,”等任何符号等任何符号, 例例: 400(x1+x2)需写为需写为400x1+400x211.表达式应化简，如表达式应化简，如2x1+3x2- 4x1应写成应写成 -2x1+3x212.缺省假定所有变量非负；可在模型的缺省假定所有变量非负；可在模型的“end”

38、语句语句后用后用“free name”将变量将变量name的非负假定取消的非负假定取消13.可在可在 “end”后用后用“sub” 或或“slb” 设定变量上下设定变量上下界界 例如：例如： “sub x1 10”的作用等价于的作用等价于“x1=345.5 x1+x2=345.5; ; x1=98; x1=98; 2 2* *x1+x2=600 x1+x2=345.5 x1+x2=345.5 x1=98 x1=98 2 2* *x1+x2=600 x1+x2bj，其数学模型为： njmixnjbxmiaxxcfijmijijnjiijminjijij, 1;, 1,0, 1, 1min1111

39、 解此类问题可假想一个销地解此类问题可假想一个销地bn+1，其需要量为：，其需要量为：bn+1=aai i bbj j；若用；若用xi，n+1表示从表示从ai到到bn+1的运量，的运量， 可令可令ci，n+1=0或等于或等于第第ai产地储存单位物资的费用。产地储存单位物资的费用。 因为因为xi，n+1实际上表示实际上表示ai产地产地没有运出去而库存的物资数量。经处理后，问题变成了产销平没有运出去而库存的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：衡的运输问题，其数学模型为：这样，这样，m个产地、个产地、n个销地的不平衡运输问题，转化成了个销地的不平衡运输问题，转化成了m个产

40、地、个产地、n+1个销地的平衡运输问题，此时可用表上作业法求解。个销地的平衡运输问题，此时可用表上作业法求解。1, 1;, 1, 01, 1, 1min111111njmixnjbxmiaxxcfijmijijnjiijminjijij二、销大于产二、销大于产(total demand exceeds total supply) 销大于产的运输问题的特征是ai bj，其数学模型为： njmixnjbxmiaxxcfijmijijnjiijminjijij, 1;, 1,0, 1, 1min1111 解此问题可假想一个产地am+1，其产量为：am+1 = bjai； 若用xm+1，j表示从am+

41、1到bj的运量，可令cm+1，j=0或等于第bj产地每缺单位物资的损失。因为xm+1，j实际上表示bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：此时，可用表上作业法求解。此时，可用表上作业法求解。njmixnjbxmiaxxcfijmijijnjiijminjijij, 1; 1, 1, 0, 11, 1min111111例例 某公司有某公司有6个供货栈（仓库），库存货物总数分别为个供货栈（仓库），库存货物总数分别为60，55，51，43，41，52，现有，现有8个客户各要一批货数量分别为个客户各要一批货数量分别为35，37，22，32，41，32，43，38，

42、各供货栈道，各供货栈道8个客户的单位货物运输价见表个客户的单位货物运输价见表供货栈到客户的单位货物运价供货栈到客户的单位货物运价客户客户 货栈货栈v1v2v3v4v5v6v7v8w162674259w249538582w352197433w476739271w523957265w655228143试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。试确定各货栈到各客户处的货物调运数量，使总的运输费用最小。解解 引入决策变量引入决策变量代表从第代表从第个货栈到第个货栈到第个个客户的货物运量客户的货物运量. 设设表示从第表示从第 个货栈个货栈到第 个客户的单位货物运价表示第表示第 个货栈的最

43、大供货量个货栈的最大供货量,表示第表示第个客户的订货量个客户的订货量.目标函数是总运输费用最少目标函数是总运输费用最少.约束条件有三条：约束条件有三条：1. 各货栈运出的货物总量不超过其库存数各货栈运出的货物总量不超过其库存数 2.各客户收到的货物总量等于其订货数量各客户收到的货物总量等于其订货数量3. 决策变量决策变量 非负非负数学模型为数学模型为 前面介绍的前面介绍的lingo的基本用法，其优点是输入模型较直观，的基本用法，其优点是输入模型较直观，一般的数学表达式无需作大的变换即可直接输入一般的数学表达式无需作大的变换即可直接输入.对于规模较对于规模较小的的规划模型，用直接输入的方法是有利

44、的，如果模型的小的的规划模型，用直接输入的方法是有利的，如果模型的变量和约束的条件个数比较多，若仍然用直接的输入方式，变量和约束的条件个数比较多，若仍然用直接的输入方式，虽然也能求解并得到结果，但这种做法有明显的不足之处。虽然也能求解并得到结果，但这种做法有明显的不足之处。模型的篇幅很长，不便于分析修改和扩展。模型的篇幅很长，不便于分析修改和扩展。 lingo 建模语言引入集合的概念，为建立大规模的数学规建模语言引入集合的概念，为建立大规模的数学规划模型提供了方便划模型提供了方便. 用用lingo 语言表达一个实际优化问题，语言表达一个实际优化问题，称之为称之为 lingo模型。模型。 一、集

45、合定义部分一、集合定义部分 集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与集合是一组相关对象构成的组合，代表模型中的实际事物，并与数学变量与常量联系起来，是实际问题到数学的抽象。例中的常量联系起来，是实际问题到数学的抽象。例中的6个仓库可以看成一个集合，个仓库可以看成一个集合，8个客户可以看成另一个集合。个客户可以看成另一个集合。 每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容每个集合在使用之前需要预先给出定义，定义集合时要明确三方面的内容：集合集合的名称的名称，集合内的成员（元素）集合内的成员（元素）、集合的属性（可以看成与该集合有关的变量集合的属性（可

46、以看成与该集合有关的变量或常量，相当于数组）或常量，相当于数组）.本例首先定义仓库集合本例首先定义仓库集合：wh/w1.w6/:ai; 其中其中wh是集合的名称，是集合的名称，w1.w6是集合内的成员，是集合内的成员， “.” 是特定的省略号是特定的省略号（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或（如果不用该省略号，也可以把成员一一罗列出来，成员之间用逗号或空格分开空格分开),表明该集合有表明该集合有6个成员，分别对应于个成员，分别对应于6个供货栈，个供货栈，ai是集合的属性，是集合的属性，它可以看成是一个数组，有它可以看成是一个数组，有6个分量，分别表示各货栈现有货物的总

47、数。个分量，分别表示各货栈现有货物的总数。集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义集合、成员、属性的命名规则与变量相同，可按自己的意愿，用有一定意义的字母数串来表示，式中的字母数串来表示，式中“/ ”和和“/:” 是规定的语法规则是规定的语法规则。本例再定义客户集合本例再定义客户集合：vd/v1.v8/:dj;该集合有该集合有8个成员，个成员，dj 是集合的属性（有是集合的属性（有8个分量）表示各客户的需求量个分量）表示各客户的需求量.以上两个集合称为初始集合（或称基本集合、原始集合）初始集合的属性都初始集合（或称基本集合、原始集合）初始集合的属性都相当于一维数组。相

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

49、不写，则定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来，如果省略不写，则默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合默认衍生集合的成员取它所对应初始集合的所有可能组合，上述衍生集合links的定的定以中没有指明成员，则它对应的初始集合以中没有指明成员，则它对应的初始集合wh 有有6个成员，个成员，vd 有有8 个成员，因此个成员，因此 links成员取成员取wh和和vd的所有可能组合，即有的所有可能组合，即有48个成员，个成员，48个成员可以排列成一个矩阵。其个成员可以排列成一个矩阵。其行数与集合行数与集合wh的成员个数相等，列数与集合的成员个数相等，列数与集合v

50、d成员的个数相等成员的个数相等. 相应地，集合相应地，集合links的的属性和都相当于二维数组，各有属性和都相当于二维数组，各有48个分量，表示货栈个分量，表示货栈i 到客户到客户vj的单位货物运价的单位货物运价 x 表示货栈表示货栈wi到客户到客户vj的货物运量的货物运量.本模型完整的集合定义为：sets:wh/w1.w6/:ai;vd/v1.v8/dj;links(wh,vd):c,x;endsets注：集合定义部分以语句注：集合定义部分以语句 sets: 开始，开始，以以endsets语句结束，这两个语句需单独成一行，语句结束，这两个语句需单独成一行，endsets后面不加标点符号后面不

51、加标点符号.二、数据初始化（数据段）二、数据初始化（数据段） 以上集合中属性以上集合中属性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

52、,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;enddata注：数据初始化部分以语句注：数据初始化部分以语句 data:开始，以开始，以enddate语句结束，这两个语句需单独成一行，数语句结束，这两个语句需单独成一行，数据之间的逗号和空格可以互换。据之间的逗号和空格可以互换。三、目标函数和约束条件三、目标函数和约束条件目标函数表达式目标函数表达式 用用lingo语句表示为语句表示为min=sum(links(i,j):c(i,j)*x(i,j); 式中，式中，sum 是是lingo提供的内部函数，其作用是对某个集合的所有成员提供的内部函

53、数，其作用是对某个集合的所有成员求制定表达式的和，该函数需要两个参数，第一个参数是求制定表达式的和，该函数需要两个参数，第一个参数是集合名称集合名称，制定对该，制定对该集合的所有成员求和，如果此集合是一个初始集合，它有集合的所有成员求和，如果此集合是一个初始集合，它有m 个成员，则求和运算个成员，则求和运算对对m 个成员进行，相当于求个成员进行，相当于求 ，第二个参数是一个表达式，表示求和运算对该，第二个参数是一个表达式，表示求和运算对该表达式进行，此处，表达式进行，此处， sum的第一个参数是的第一个参数是 links（i，j），表示求和运算），表示求和运算对对 links进行，进行， 该集

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

55、为：for(wh(i): sum(vd(j):x(i,j)=ai(i);语句中的for是lingo提供的内部函数，它的作用是对某个集合的所有成员分别生成一个约束表达式，它有两个参数，第一个参数是集合名，表示对该集合的所有成员生成对应的约束表达式，上式 for 的第一个参数为，它表示货栈，共有个成员，故应生成个约束表达式，for 的第二个参数是约束表达式的具体内容，此处再调用sum 函数，表示该约束的左边是求和，是对集合的个成员，并且对表达式(i,j) 中的第二维 j 求和，即约束表达式的右边是集合的属性ai，它有6个分量，与6个约束表达式一一对应，本句中的属性分别属于不同的集合，所以不能省略

56、i,j.约束条件 表示为 for(d(j): sum(vd(j):x(i,j)=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

57、)*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” )整数规划整数规划 -integer programming, ip整数规划整数规划（integer programming）主要是指整数线）主要是指整数线

58、性规划。一个线性规划问题，如果要求部分决策变量性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。为整数，则构成一个整数规划问题。所有变量都要求为整数的称为所有变量都要求为整数的称为纯整数规划纯整数规划（pure integer programming）或称）或称全整数规划全整数规划（all integer programming）；）；仅有一部分变量要求为整数的称为仅有一部分变量要求为整数的称为混合整数规划混合整数规划（mixed integer programming）；）；有的变量限制其取值只能为有的变量限制其取值只能为0或或1，这类特殊的整数规，这类特殊的整数

59、规划称为划称为01规划规划(0-1 integer programming )整数规划问题及其数学模型整数规划问题及其数学模型例 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料a、材料b，有关数据如下，问这两种设备各生产多少使工厂利润最大？设备设备材材 料料甲甲乙乙资源限量资源限量材料材料a（kg）2314材料材料b（kg）10.54.5利润（元利润（元/件）件）32 解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20,且为整数且为整数图41要求该模型的解，

60、不考虑整数约束条件，用图解法要求该模型的解，不考虑整数约束条件，用图解法对相应线性规划求解，其最优解为：对相应线性规划求解，其最优解为：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个变量为个变量为整数整数”，等价于：，