优化模型及求解.ppt

1、优化模型及求解,优化问题及 LINGO软件的应用,在工程技术、经济管理、科学研究和日常生活中，我们经常会遇到的一类决策问题是：在一系列客观或主观条件限制下，寻求使所关注的某个或多个指标达到最优的决策。这类问题称为最优化问题，研究处理这类问题的数学方法称为最优化方法，它也是运筹学和管理科学中解决定量问题的基本方法。在决策科学化、定量化的呼声日益高涨的今天，用最优化方法来解决定量的决策问题无疑是符合时代潮流与要求的，也应该是当今大学生必备的知识之一。,通常人们解决优化问题的手段大致有以下几种： （1）依赖过去的经验判断面临的问题。这种方法似乎切实可行，但是在处理过程中会融入决策者大量的主观因素，结

2、果未必是好的，且存在较大的风险。 （2）大量做试验进行比较。这虽然人为因素减少，比较真实可靠，但是投入费用大且结果未必是最好的。 （3）用数学方法建立优化模型求得最优决策，称为优化建模方法，所得模型称为优化模型。,用最优化方法解决决策问题包括两个基本步骤：首先，我们需要把实际决策问题翻译、表述成数学最优化的形式，即用数学建模方法建立决策问题的优化模型，简称为优化建模；其次，建立优化模型后，我们需要选择、利用优化方法和工具求解模型。优化建模方法自然具有一般的数学建模方法的共同特性，但优化模型又是一类既重要、又特殊的数学模型，因此优化建模方法又具有一定的特殊性和专业性。此外，由于优化模型的种类很多

3、，很多模型目前还没有有效的求解方法，不同的算法用于求解不同模型的效果可能差异很大，如何利用优化软件求解优化模型也有一定的专业性和技巧性。,优化模型是一种特殊的数学模型，优化建模方法是一种特殊的数学建模方法，优化模型一般由以下三个要素构成。,优化问题的建模实例,（1）决策变量：是问题要求解的未知 量，一般可用n维向量x来表示。,（2）目标函数：是该问题要优化的目 标数学表达式，是决策变量x的函数。,（3）约束条件：即决策变量的取值范 围，由该问题对决策变量的限制条件决定。,例1：某厂用原料A、B、C生产甲乙两种产品，已知生产单位甲产品需用三种原料为5，300，12个单位，利润8000元.生产单位

4、乙产品需用三种原料为3，80，4个单位，利润3000元。现有三种原料为500、20000、900个单位。问在此条件下如何生产获利最大？,这是一个简单的二元线性规划问题，数学 模型为：,这个模型的求解可以用图解法，也可用单纯形方法，我们在LINGO软件上求解。,例2：某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人。规定应聘者需连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，可在满足需要的条件下聘用总人数最少。,数学模型为：,例3：准备从5 名游泳运动员中选择4人参加4100 m混合泳接力赛。5名队员4种泳姿的百米成绩见

5、下表，问应如何选拔队员？,5名队员4种泳姿的百米平均成绩,引入0-1变量xij表示队员i参加泳姿j的比赛，则有,这是一个线性0-1规划模型,也是一个指派问题，我们可以用如下的方法来计算：,总用时为253.2秒,例4：某公司需要决定一年中四个季度的生 产量，已知每个季度的产品需求量分别是 40，60 ，25 ，75个单位，需求必须按时满 足。每个季度的正常常生产能力是40个单 位，单位产品的生产费用为400，若加班生 产，单位产品的生产费用为450，每个季度 末，单位产品的库存费用为20，假定生产 提前期为0，初始库存为10，如何安排生产 可使总费用最少？,我们用x,z,j,k分别表示需求量、正

6、常生产量、加班生产量和库存量，则有下面的数学模型：,一般来说，LINGO中建立的优化模型由以下三部分组成,1、集合段：这部分以“SETS:”开始，以”endsets”结束， 作用是定义必要的集合变量（set)及其元素（类似于 数组下标）和属性（类似于数组），如在例题模型中， 定义了集合季节，它包含四个季节指标，每个季节 有需求、正常生产量、加班生产量和库存量等属性；一 旦这样的定义建立起来，指标可任意确定。,2、目标与约束段：这部分没有段的开始和结束标记， 但是一般要用到LINGO的内部函数，尤其是与集合相 关的函数,3、数据段：这部分以“data:”开始，以”enddata”结束， 作用在于

7、对集合的属性输入必要的常数数据。,LINGO的运算符和函数,算术运算符有加、减、乘、除、乘幂,1）#AND#（与）、#OR#（或）、#NOT#（非） 2）#EQ#（等于）、#NE#（不等于）、 #GT#（大于）、#GE#（大于等于）、 #LT#（小于）、#LE#（小于等于）,逻辑运算符有以下九种,关系运算符表示数与数之间的大小关系，有三种 （大于等于）,基本的数学函数 abs(x)、 exp(x)、 log(x)、 sin(x)、 cos(x)、tan(x)、mod(x,y)、floor(x)、sign(x)、smax(list) 、 smin(list),集合循环函数 集合函数是指对集合上的

8、元素（下标）进行循环操作的函数。一般用法如下：,function(setname(set_index_list) | condition: expression _list);其中 function是集合函数名，是 for，max,min,prod, sum五种之一,setname是集合名；,set_index_list是集合索引列表(不需用时可省略),condition是用逻辑表达式描述的过滤条件，（通常含有索引，无条件时可以省略 ）,expression_list是一个表达式，（对for函数可以是一组表达式）,for(集合元素的循环函数)：对集合setname的每个元素独立的生成表达式，表

9、达式由expression_list描述（通常是优化问题的描述）,max（集合属性的最大值函数）； min （集合属性的最小值函数）；,prod（集合属性的乘积函数）； sum （集合属性的求和函数）；,集合操作函数 集合操作函数是指对集合进行操作的函数，主要有IN,INDEX,WRAP,SIZE四种,变量定界函数 变量定界函数是对变量的取值范围附加限制的函数，共有四种： BND(L,X,U):限制L=X=U BIN(X):限制X为0或1 FREE(X):取消对X的符号限制 GIN(X):限制X为整数,常见LINGO出错信息 LINGO错误编号及含义对照表,例5：某公司用两种原油A与B加工甲乙

10、 两种标号的汽油，甲乙两种汽油含原油 A的最低比例分别为50%和60%，每吨 售价分别为4.8千元和5.6千元。公司现有 原油A和B分别为500t和1000t，还可以 在市场上买到不超过1500t的原油A，其 市场价为购买量不超过500t时单价为每 吨10千元，超过500不到1000吨时，超 过部分每吨8千元，若购买超过1000吨， 超过部分每吨6千元。该公司应该如何 安排生产？,LINGO的进一步应用,问题分析,这是一个优化问题，需要安排原油的采购量和产品的生 产量。这个问题的难点是原油的采购价格比较复杂，是 一个分段函数关系，给利用优化模型造成一定困难。,模型建立,设原油A的购买量为x（吨

11、），则采购支出函数为,设原油A用于生产甲乙两种汽油的数量分别为x11和x12 原油B用于生产甲乙两种汽油的数量分别为x21和x22， 则目标函数为总利润函数最大：,约束条件包括加工两种汽油用的原油A、B的库存限制、原油A的购买量的限制以及两种汽油含原油的比例限制，它们可表示为：,模型求解,下面给出三种求解方法,第一种解法：将原油A的采购量分解为三个量，用x1,x2和x3分别表示以三种价格采购原油A的吨数，则有,这时目标函数为,这时应该注意到仅当以10千元/t的价格购买x1=500时 才能以8千元/t的价格购买x2，这个条件可表为,同样有,于是我们将模型输入LINGO如下：,得到最优解是用库存的

12、原油各500t生产 1000t汽油甲，利润为4800（千元）,这时LINGO得到的结果只是一个局部最 优解，我们用菜单命令LINGO|Options在 Global Solver上启动全局优化选项use global solver，重新执行求解，可得全局 最优解：购买1000t原油A，与库存的原 油A和B一起生产2500t汽油乙，利润为 5000（千元）,第二种解法：引入0-1变量将第一种解法中的非线性约束转化为线性约束。,令Y1=1, Y2=1, Y3=1分别表示以10（8，6）千 元/t的价格采购原油A，则第一种解法中的非 线性约束变为,这组约束隐含着变量Y1, Y2， Y3是递减的。,于

13、是我们将模型输入LINGO如下：,第三种解法：直接处理分段线性函数c(x),记x轴上的分点依次为b1, b2, b3, b4，当 x 属于 b1, b2时，记x= z1 b1+ z2 b2，z1+z2 =1, z1, z2 0， 同样，当 x 属于 b2, b3 时，记x= z2 b2+ z3 b3， z2+z3 =1, z2, z3 0，等等。,因为c(x)在每个小区间上是线性的，所以这时x 和c(x)可以统一的表示为：,为了表示x在那个小区间，引入0-1变量yk, (k=1,2,3)，当x在第 k个小区间时，yk=1，否则 yk=0，这样，z1, z2, z3, z4 , y1, y2,

14、y3 应满足,LINGO软件与外部数据的传递,（1）通过Windows剪贴板传递数据 （2）通过文本文件传递数据 （3）通过电子表格传递数据,例6：假设有多个市政府都需要一定的公款消费，每个城市只允许消费自身的财政收入，城市(i)的最低需求量为NEED(i)，最大供应量是SUPPLY(i)，消费成本是COST(i)，问如何消费可使总成本最小？,可以看出，这是一个简单的线性规划问题， 设消费量为ORD，则其数学模型为,只要给出合适的数据，这个问题的最优解是一目了然的。,（注意：LINGO对集合的属性是按列赋值的）,1、数据在WORD文件中给出,LINGO模型如下：,Sets: myset/|/:

15、cost,need,supply,ord; Endsets Min=sum(myset(i):ord(i)*cost(i); for(myset(i):ord(i)need(i); ord(i)supply(i); Data: Cost,need,supply=, Enddata,粘贴命令的方法,1、在Word中将城市名所在单元格复制(Ctrl+c)到剪贴板 2、回到LINGO窗口，利用菜单命令“EditPaste”或(Ctrl+V)将其粘贴到集合的元素列表位置 3、重复这个过程粘贴相应数据 4、注意LINGO对集合的属性是按列赋值的,2、数据在文本文件中给出,sets: myset/file

16、(my.ldt)/:file(my.ldt); endsets min=sum(myset(i):ord(i)*cos(i); for(myset(i): ord(i)nee(i); ord(i)sup(i); data: cos=file(my.ldt); nee=file(my.ldt); sup=file(my.ldt); enddata,通过文本文件输入数据的方法,1、通过文本文件输入数据使用的是FILE函数，这个 函数的一般用法是FILE(filename)filename是存放数据 的文件名，文件记录之间用 分开 2、模型集合段对集合的定义要两次用到FILE函数， 对应文本文件的前

17、两行 2、在程序的数据段用到三个FILE函数，对应文本文件 的后面三行,3、数据在电子表格文件中给出,sets: myset/ole(mydata,citi)/:cost,eed,supply,ordered; endsets min=sum(myset(i):ordered(i)*cost(i); for(myset(i): con1ordered(i)eed(i); con2ordered(i)supply(i); DATA: cost,eed,supply=ole(mydata.xls); ole(mydata,sulut)=ordered; enddata,3、数据在电子表格文件中给出

18、,通过Excel文件与LINGO系统传递数据是通过OLE函数。该函数只能在模型的集合段、数据段和初始段使用。这个函数的使用格式是ole(spreadsheet_filerange_name_list) 其中spreadsheet_file是电子表格文件的名称， range_name_list是指文件中包含数据的单元范围。,通过Excel文件向LINGO输入数据的方法如下： （以下面数据为例）,（1）：首先用excel建立一个名为mydata的数据文件，（见图）。 （2）选定表格的B2:B5单元，然后选择Excel的菜单命令“插入名称定义”，这时会弹出一个对话框，请你输入名称，你可以输入一个适当

19、的名称，例如citi。同样的方法，对C2:C5,F2:F5输入相应的名称如cost,eed,supply,ordered; 。这些单元取什么名称可以随意，最好取有一定提示意义的名字。 （3）在Excel中你对单元格取的是什么名字，在Lingo中调用时就必须用什么名字，二者必须一致。,sets: myset/ole(mydata,citi)/:cost,eed,supply,ordered; endsets min=sum(myset(i):ordered(i)*cost(i); for(myset(i): con1ordered(i)eed(i); con2ordered(i)supply(i

20、); DATA: cost,eed,supply=ole(mydata.xls); ole(mydata,sulut)=ordered; enddata,这个程序中有三个OLE函数调用，其作用说明如下：,1、ole(mydata,citi)：从文件mydata的citi所指示的 单元中取出数据，作为集合的元素,2、cost,eed,supply=ole(mydata.xls);从mydata.xls的Cost（eed,supply）指定的单元给cost（eed,supply） 赋值,3、ole(mydata,sulut)=ordered：将ordered的值输 出赋给mydata.xls文件中

21、由sulut指定的单元格,例7：“武汉国际抢渡长江挑战赛”于每年月日进行，由于水情、水性的不可预测性，这种竞赛更富有挑战性和观赏性。2002年5月1日，抢渡的起点设在武昌汉阳门码头，终点设在汉阳南岸咀 ，假设在竞渡区域两岸为平行直线，它们的垂直距离为1160米，从武昌汉阳门的正对岸到汉阳南岸咀的距离为1000米 ，流速沿离岸边距离的分布为 (设从武昌汉阳门垂直向上为 y轴正向),游泳者的速度大小（1.5米/秒）仍全程保持不变，试为他选择游泳方向和路线，估计他的成绩。,模型建立与求解 若游泳者的游泳速度为v，则垂直于对岸的分速度为v1=vcos,平行于两岸方向的分速度v=-vsin。于是游泳者尚平行于水流方向的合速度V=