最优化模型计算讲座一

最优化模型计算

——LINGO软件与应用讲座

东南大学数学系 殷翔第二讲 最优化问题的LINGO建模与求解第三讲 LINGO软件与外部文件间的数据传递第四讲 应用LINGO软件求解数学建模问题第一讲最优化模型与LINGO入门教材(TextBook)

LINGO和Excel在数学建模中的应用.袁新生等编著.科学出版社参考书目(Reference)

LINGO用户指南(LINGO8.0的帮助文档)

最优化模型与实验.朱德通编著.同济大学出版社

OptimizationModelingwithLINGO(SixthEdition).LINDOSystems,Inc.()ApplicationsofoptimizationwithXpress-MP.DashOptimizationLtd.

()运筹学.刁在筠等编著.高等教育出版社

新编运筹学教程.杨文鹏等编著.陕西科学技术出版社第一讲最优化模型与LINGO入门最优化问题的数学模型

LINDO公司的主要软件产品及功能简介

LINGO软件使用简介

LINGO常用函数第一讲最优化模型与LINGO入门运筹学，即最优化理论，或在有的领域被称为管理科学，是近几十年发展和形成的一门新兴的应用性学科。它主要解决最优生产计划、最优分配、最优设计、最优决策、最佳管理等最优化问题。主要研究方法是定量化、系统化和模型化方法，特别是运用各种数学模型和技术来解决问题。

由于实际问题的规模一般都很大，即使建立了数学模型，找到了求解方法，但面对庞大的计算量也只能望而却步。“工欲善其事，必先利其器”，一个方便而强大的求解最优化问题软件是必不可少的。LINGO优化软件包就是一个理想的软件工具。

最优化模型

实际问题的最优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划第一讲最优化模型与LINGO入门LINDO公司软件产品简要介绍

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

LINGO:LinearINteractiveGeneralOptimizer(V10.0)LINDOAPI:LINDOApplicationProgrammingInterface(V5.0)What’sBest!:(SpreadSheete.g.EXCEL)(V9.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）第一讲最优化模型与LINGO入门LINGO软件能求解的优化模型

LINGO

LINDO最优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化问题整数规划(IP)第一讲最优化模型与LINGO入门LINGO软件使用简介例1：奶制品加工计划1桶牛奶

3公斤A1

12小时

8小时

4公斤A2

加工利润24元/公斤

利润16元/公斤

50桶牛奶、

时间480小时、

加工至多100公斤A1

问题1：制订生产计划，使每天获利最大？

问题2：若市场有35元1桶牛奶，是否购买？每天最多买多少?

问题3：如聘用临时工，其工资最多是每小时几元?

问题4：A1利润改为30元/公斤，是否需调整计划？

每天：第一讲最优化模型与LINGO入门x1桶牛奶生产A1

x2桶牛奶生产A2

获利

24×3x1

获利

16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

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

线性规划模型(LP)分析：首先考虑问题1，建立数学规划模型第一讲最优化模型与LINGO入门Globaloptimalsolutionfoundatiteration:4

Objectivevalue:3360.000VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.00000020.00000048.0000030.0000002.000000440.000000.000000max=72*x1+64*x2;x1+x2<=50;12*x1+8*x2<=480;3*x1<=100;第一讲最优化模型与LINGO入门打开LINGO8.0，在模型窗口输入LINGO程序所有的决策变量均默认为非负目标函数用max=或min=表示每个语句必须以分号“；”结束，每行可以有多个语句，语句可以跨行，注释语句以“！”开头LINGO模型以语句“MODEL：”开头，“END”结束。（可略）LINGO模型默认的文件格式为*.lg4，其它还有文本格式*.lng点击工具条上的按钮，执行程序，得到结果：

4次迭代后得到全局最优解最优目标值为3360最优解：20桶牛奶生产A1,30桶生产A2“SlackorSurplus”表示松驰变量值，即约束条件中的资源剩余量。资源剩余为零的约束为紧约束（有效约束）

第一讲最优化模型与LINGO入门“ReducedCost”表示变量在最优单纯形表中的判别数（检验数），表示当变量单位变化时,目标值的变化量Globaloptimalsolutionfoundatiteration:4

Objectivevalue:3360.000VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.00000020.00000048.0000030.0000002.000000440.000000.000000基变量的ReducedCost值为0；非基变量xj的ReducedCost值表示当该非基变量xj

增加一个单位时目标函数的减少量(max型问题)Globaloptimalsolutionfoundatiteration:4

Objectivevalue:3360.000VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.00000020.00000048.0000030.0000002.000000440.000000.000000“DualPrice”（对偶价格）表示在最优解下，某资源增加一个单位时，目标值的增量（也称影子价格）每个约束都有一对偶价格，非紧约束的对偶价格为0；紧约束（资源无剩余）的对偶价格非0，表示增加单位资源的最高出价

第一讲最优化模型与LINGO入门Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowable

VariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000

RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000灵敏度分析

“ObjectiveCoefficientRanges”：约束条件不变，在最优解不变的条件下，目标系数允许变化的范围

x1系数范围(72-8=64,72+24=96)

x2系数范围(64-16=48,64+8=72)

“RighthandSideRanges”：目标函数不变，在影子价格有意义（最优基不变）的条件下，约束右端允许变化的范围

至多增加10桶牛奶，或加工时间增加53小时问题2：若1桶牛奶的市场价35元<1桶牛奶的影子价格48，可以购买至多10桶（？）问题3：临时工每小时工资最多不超过1小时加工时间的影子价格2问题4：A1利润改为30元/公斤，每桶牛奶生产A1的利润为30*3=90<96，不调整计划太好了！全交给LINGO去做吧！我现在需要考虑更重要的事！第一讲最优化模型与LINGO入门目标函数与约束条件段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）LINGO模型的构成：4个段对于简单的模型，可以用上面方法直接输入LINGO模型。但是当问题规模较大或约束众多时，必须利用LINGO提供的建模语言，简单而有效表达模型。注：线性问题不需要初始段第一讲最优化模型与LINGO入门例2:求有6个发点和8个收点的最小费用运输问题。产销单位运价如下表。

第一讲最优化模型与LINGO入门分析：先建立该运输问题的数学模型xij表示从第i个发点到第j个收点的货物运输量。记cij表示从第i个发点到第j个收点的单位货物运价，ai表示第i个发点的最大供货量，dj表示第j个收点的需求量。总运输费用最少决策变量目标函数约束条件各发点运出货物量不超过其产量各收点收到货物量等于其销量决策变量非负限制各产、销点的产量和销量约束，决策变量限制线性规划模型第一讲最优化模型与LINGO入门model: !6发点8收点运输问题;sets:!

集合段;wh/w1..w6/:ai;vd/v1..v8/:dj;

links(wh,vd):C,X;endsetsmin=@sum(links:C*X); !目标函数;@for(vd(J):

@sum(wh(I):X(I,J))=dj(J));!需求约束;@for(wh(I):

@sum(vd(J):X(I,J))<=ai(I));!产量约束;data: !

数据段;

ai=605551434152;

dj=3537223241324338;C=626742954953858252197433767392712395726555228143;enddataend集合段（Sets-endsets）数据段（data-enddata）目标函数与约束条件段

第一讲最优化模型与LINGO入门sets:!

集合段;wh/w1..w6/:ai;vd/v1..v8/:dj;

links(wh,vd):C,X;endsetsdata: !

数据段;

ai=605551434152;

dj=3537223241324338;C=626742954953858252197433767392712395726555228143;enddatamin=@sum(links:C*X); !目标函数;@for(vd(J):

@sum(wh(I):X(I,J))=dj(J));!需求约束;@for(wh(I):

@sum(vd(J):X(I,J))<=ai(I));!产量约束;集合要先定义、后使用定义集合的名称、集合内成员（元素）、集合的属性（与集合结构相同的一维数组）“..”是特定省略号。集合links是以基本集合wh和vd为基础的派生集合，其属性C、X是二维数组数据间可以用逗号或空格隔开

数据部分也可以指定一些标量变量值，称为参数

集合属性的右边输入一个值，将该属性所有成员都赋予这个值

用一个问号（?）取代数值，表示该数据将在执行程序时通过对话框输入同语句min=@sum(links(I,J):C(I,J)*X(I,J));@sum是LINGO内部函数，作用是对某集合所有成员，求指定表达式的和；@for是对某集合所有成员，分别生成一个约束表达式@sum和@for可以嵌套使用第一讲最优化模型与LINGO入门Globaloptimalsolutionfoundatiteration:20Objectivevalue:664.0000

VariableValueReducedCostX(W1,V1)0.0000005.000000X(W1,V2)19.000000.000000………………………X(W6,V7)3.0000000.000000X(W6,V8)0.0000003.00000020次迭代后得到全局最优解总费用最少为664最优运输方案如下最优解行数太多，略第一讲最优化模型与LINGO入门LINGO提供的基本函数

LINGO有9种类型的函数：一、基本运算符：包括算术运算符、逻辑运算符和关系运算符二、数学函数：包括三角函数和常规的数学函数三、金融函数：LINGO提供的两种金融函数四、概率函数：LINGO提供了大量概率相关的函数五、变量界定函数：这类函数用来定义变量的取值范围六、集操作函数：这类函数为对集的操作提供帮助七、循环函数：遍历集的元素，执行一定的操作的函数八、数据输入输出函数：这类函数允许模型和外部数据源相联系，进行数据的输入输出九、辅助函数：各种杂类函数第一讲最优化模型与LINGO入门一、基本运算符：包括算术运算符、逻辑运算符和关系运算符算术运算符（对数值进行操作） 一元算术运算符： ﹣取反函数 二元运算符（5种）： ＾乘方 ﹡乘 ／除 ﹢加 ﹣减逻辑运算符（在集循环函数的条件表达式中，以控制在函数中哪些集成员被包含、或被排斥。在创建稀疏集时，用于成员资格过滤器中） 逻辑运算符（９种）：

#not#否定该操作数的逻辑值，＃not＃是一个一元运算符

#eq#若两个运算数相等，则为true；否则为flase #ne#若两个运算符不相等，则为true；否则为flase #gt#若左边的运算符严格大于右边的运算符，则为true；否则为flase #ge#若左边的运算符大于或等于右边的运算符，则为true；否则为flase #lt#若左边的运算符严格小于右边的运算符，则为true；否则为flase #le#若左边的运算符小于或等于右边的运算符，则为true；否则为flase #and#仅当两个参数都为true时，结果为true；否则为flase #or#仅当两个参数都为false时，结果为false；否则为true关系运算符（指定一个表达式的左边是否等于、小于等于、或者大于等于右边，形成模型的一个约束条件） 关系运算符（3种）：= <= >=

第一讲最优化模型与LINGO入门二、数学函数：包括三角函数和常规的数学函数@abs(x)

返回x的绝对值@sin(x)

返回x的正弦值，x采用弧度制@cos(x)

返回x的余弦值@tan(x)

返回x的正切值@exp(x)

返回常数e的x次方@log(x)

返回x的自然对数@lgm(x)

返回x的gamma函数的自然对数@sign(x)

如果x<0返回-1；否则，返回1@floor(x)

返回x的整数部分。当x>=0时，返回不超过x的最大整数；当x<0时，返回不低于x的最大整数。@smax(x1,x2,…,xn)

返回x1，x2，…，xn中的最大值@smin(x1,x2,…,xn)

返回x1，x2，…，xn中的最小值第一讲最优化模型与LINGO入门三、金融函数：LINGO提供的两种金融函数@fpa(I,n)

返回如下情形的净现值：单位时段利率为I，连续n个时段支付，每个时段支付单位费用。若每个时段支付x单位的费用，则净现值可用x乘以@fpa(I,n)算得。@fpa(I,n)的计算公式为：

@fpl(I,n)

返回如下情形的净现值：单位时段利率为I，第n个时段支付单位费用。@fpl(I,n)的计算公式为：

@fpa(I,n)与@fpl(I,n)两个函数间的关系：第一讲最优化模型与LINGO入门四、概率函数：LINGO提供了大量概率相关的函数@pbn(p,n,x) 二项分布的累积分布函数。当n、x不是整数时，用线性插值法进行计算。@pcx(n,x) 自由度为n的χ2分布的累积分布函数。@peb(a,x) 当到达负荷为a，服务系统有x个服务器且允许无穷排队时的Erlang繁忙概率。@pel(a,x) 当到达负荷为a，服务系统有x个服务器且不允许排队时的Erlang繁忙概率。@pfd(n,d,x) 自由度为n和d的F分布的累积分布函数。@pfs(a,x,c) 当负荷上限为