数学规划模型与lingo入门ppt课件.pptx

《数学规划模型与lingo入门ppt课件.pptx》由会员分享，可在线阅读，更多相关《数学规划模型与lingo入门ppt课件.pptx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学规划模型与lingo入门数学规划模型n决策变量决策变量 x =(x1, x2, , xn )n目标函数目标函数 Min Z = f (x)n约束条件约束条件 s.t x A ( Rn ) 等式或不等式等式或不等式n求解求解线性：单纯形法线性：单纯形法非线性：非线性： 数学规划数学规划线性规划线性规划非线性规划非线性规划整数规划整数规划连续规划连续规划0-1规划规划一、Lingo软件二、Lingo基本语法1、定义了目标函数为MIN=. MAX=. 2、以一个分号“；”结尾 除SETS, ENDSETS, DATA , ENDDATA, END之外3、可以放在约束条件的右端，同时数字也可放在约

2、束条件的左端。4、假定各变量非负。5、注释：“！”6、为、逻辑运算符#NOT#否定#EQ#相等#NE#不等#AND#并且#OR#或者#GT#大于#GE#大于等于#LT#小于#LE#小于等于算术运算符+ - * / 关系运算符(=)三、Lingo运算符和函数1、运算符及其优先级、运算符及其优先级nLingo内部函数”ABS( X)SIN( X)COS( X)TAN( X)LOG( X)EXP( X)SMAX( list )SMIN( list )SIGN(X)FLOOR ( X)2、Lingo基本数学函数GIN( X)整数变量BIN( X)0-1变量FREE( X)自由变量BND(L, X,U)

3、L，U3、Lingo变量定界函数v分段函数IF(logical_condition, true_result, false_result)4、Lingo条件判断函数条件判断函数5、Lingo集合循环函数集合循环函数v难点！重点！略例1553150.200.40 xxxxx664460.100 xxxxx135501.3xx 123456min1.47.00.9634.1Lxxxxxx12345664:6.18.40.98.54.82.331.820.1stxxxxxxxxfree(x2);min=1.4*x1+7*x2+0.9*x3+6*x4+3*x5+4.1*x6;6.1*x1+8.4*x2

4、+.9*x3+8.5*x4+4.8*x5+2.3*x6=31.82;x6=x4+0.1;x3=if(x5 #gt# 0,x5-0.2,x1+0.4);x4=if(x6 #gt# 0,x6-0.1,x4);bnd(-5,x1,5); bnd(0,x3,1.3);456000 xxx例例2 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 每天：每天：1桶牛奶 3公斤A1 12小时 8

5、小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天线性规划模型的一般形式线性规划模型的一般形式11max,1,2,., .s.t.0,1,2,.,

6、 .ni iinik kikizcxa xb imxin 目标函数和所有的约束条件都是设计变量目标函数和所有的约束条件都是设计变量的线性函数的线性函数.min. s.tzcxAxbvlbxvub矩矩阵阵形形式式：模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目标目标函数函数 Z=0Z=2400Z=3360z=c (常数常数) 等值线等值线c在在B(20,30)点得到最优解点得到最

7、优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。 模型求解模型求解 软件实现软件实现 LINGO max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000

8、ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 例例2 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 3

9、5元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？ 每天：每天：结果解释结果解释 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.000

10、000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000

11、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单位时单位时“效益效益”的增的增量量 原料增加原料增加1单位单位, 利润增长利润增长48 时间增加时间增加1单位单位, 利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48, 应该买！应该买！

12、聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？ 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 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DE

13、CREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系数范围系数范围(64,96) x2系数范围系数范围(48,72) A1获利增加到获利增加到 30元元/千克，应否改变生产计划千克，应否改变生产计划 x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内 不变！不变！(

14、约束条件不变约束条件不变)结果解释结果解释 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 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.

15、000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)基本使用构成：构成：4 4个段个段v目标与约束段v集合段（SETS ENDSETS）v数据段（DATA ENDDATA）v初始段（INIT ENDINIT）v（计算段 (CALC E

16、NDCALC)）四、Lingo建模语言n某公司有6个建筑工地，位置坐标为(ai,bi) (单位：公里)，水泥日用量di (单位：吨）v假设：料场和工地之间有直线道路v（1）现有2料场，位于A(5,1)，B(2,7)，记(xj,yj)，j=1,2，日储量ej各有20吨。v制定每天的供应计划：即从A, B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。ia1.251.258.750.55.7537.25b1.251.250.754.7556.57.75d3547611例3 选址问题决策决策 目标目标 约束约束 解：n决策变量：料场j到工地i的运量 cij 12维n线性规划模型？nlingo表

17、达式？2622 1/2112161min()() .,1,.,6,1,20,1,.,6,1,2ijjijijiijijijjiijcxaybstcdicejcij目标：吨公里约束：需求 供应目标与约束段MODEL:Title Location Problem;sets: demand/1.6/:a,b,d; supply/1.2/:x,y,e; link(demand,supply):c;endsetsdata: a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; d=3,5,4,7,6,11; e=20,20; x,y=5,1,

18、2,7; enddatainit:endinitm i n = s u m ( l i n k ( i , j ) : c ( i , j ) * ( ( x ( j ) - a ( i ) ) 2 + ( y ( j ) -b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i);); for(supply(i):sum(demand(j):c(j,i)=e(i););for(supply: free(X); free(Y); );END集合段数据段初始段供应约束供应约束需求需求需求点的位置需求点的位置供需量供需量供应供应初始点初始点目标目标需求

19、约束需求约束连接连接n建筑工地位置坐标 (ai,bi) 、水泥日用量di ：对每个建筑工地（6个）都有一个对应的值都是一个由6个元素组成的数组是已知的n料场位置坐标 (xj,yj) 、日储量ej对每个料场（2个）都有一个对应的值都是一个由2个元素组成的数组目前是已知的n料场到建筑工地的供应计划 c i j 对每个料场与建筑工地之间（62）都有一个对应的值是一个62 个元素组成的矩阵是未知数nLINDO无数组，每个变量输入麻烦（1）Lingo的集合Set下标集合100个工地？1、Lingo的集合Set及其属性Attribute例3Lingo中集的定义语法：setname/member_list/

20、:attribute_list;setname/member_list/:attribute_list; 说明： setnamesetname为集的名称；为集的名称； /member_list/member_list/为成员列表；为成员列表； attribute_listattribute_list为属性列表。为属性列表。（2）集合Set及其属性Attributen定义数组下标集合demand/1.6/表示6个建筑工地a,b,d称为该集合的属性表示坐标(ai,bi) 、水泥日用量din定义数组下标集合supply/1.2/表示6个建筑工地该集合的属性x,y,e表示坐标(xj,yj) 、日储量e

21、j n定义数组下标集合link(demand,supply)表示62个料场到建筑工地的连接该集合的属性c表示每个料场与建筑工地之间供应计划c i j1到6的整数n建立下标集合（3）Lingo 建模语言集合段 数据段需求点的位置需求点的位置供需量供需量sets: demand/1.6/:a,b,d; supply/1.2/:x,y,e; link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; d=3,5,4,7,6,11; e=20,20;x,y=5,1,2,7;end

22、datav赋值需求需求供应供应连接连接n直接把元素列举出来n定义格式 集合名 元素列表 属性列表 setname /member_list/ : attribute_list; 可选项n元素列表显式列举法列出全部元素, 用逗号或空格分开隐式列举法 1.nn属性列表缺省集合可在程序中作为一循环变量使用，构造更复杂的派生集合n元素列表缺省必须在数据段给出元素列表赋值基本集合primary set（4）定义集合Set派生集合derived setn基于其它集合而派生出来的二维或多维集合n定义格式 集合名 父集合列表 元素列表 属性列表 setname(parent_set_list) /member

23、_list/ : attribute_list;n元素列表缺省所有组合稠密集合稠密集合、或数据段列表赋值n元素列表稀疏集合稀疏集合元素列表法枚举元素过滤法利用过滤条件setname(parent_set_list) |filtrate_condition :attribute_list;n建立 下标集合例3选址问题需求点的位置需求点的位置供需量供需量sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6

24、.5,7.75; d=3,5,4,7,6,11; e=20,20;x,y=5,1,2,7;enddatav赋值需求需求供应供应连接连接基本基本集合集合派生派生集合集合626152514241323122211211212121654321654321654321,cccccccccccceeyyxxddddddbbbbbbaaaaaa集合的类型setname /member_list/ : attribute_list;setname(parent_set_list) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; R

25、OADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS集合集合基本集合基本集合派生集合派生集合稠密集合稠密集合稀疏集合稀疏集合直接列举法直接列举法隐式列举法隐式列举法元素列表法元素列表法元素过滤法元素过滤法n难点！重点！v循环操作函数集合上的元素下标：集合函数名function(setname (set_index_list)|condition:expressi

26、on_list);集合名集合索引列表过滤条件表达式FORMAXMINSUM PROD2、Lingo集合循环函数n目标：吨公里例3 选址问题2622 1/211min()() ijjijijicxaybmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsn约束： 非负！for(supply: free(X); free(Y); );.0,1,.,6,1,2ijstcijfor(demand(i):su

27、m(supply(j):c(i,j)=d(i);); for(supply(i):sum(demand(j):c(j,i)=e(i););2161.,1,.,6,1,2ijijijjistcdicejv约束：需求供应目标与约束段MODEL:Title Location Problem;sets: demand/1.6/:a,b,d; supply/1.2/:x,y,e; link(demand,supply):c;endsetsdata: a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; d=3,5,4,7,6,11; e=20

28、,20; x,y=5,1,2,7; enddatainit:endinitm i n = s u m ( l i n k ( i , j ) : c ( i , j ) * ( ( x ( j ) - a ( i ) ) 2 + ( y ( j ) -b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i);); for(supply(i):sum(demand(j):c(j,i)=e(i););for(supply: free(X); free(Y); );END集合段数据段初始段供应约束供应约束需求需求需求点的位置需求点的位置供需量供需量供应供

29、应初始点初始点目标目标需求约束需求约束连接连接小结小结定义集合定义集合输入数据输入数据使用集合使用集合n6个建筑工地：坐标为(ai,bi) ，水泥日用量di n（2）改建两个新料场 需要确定新料场位置(xj,yj)和运量cij ，使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维线性规划模型线性规划模型?例3 选址问题进一步讨论2622 1/2112161min()() .,1,.,6,1,20,1,.,6,1,2ijjijijiijijijjiijcxaybstcdicejcij目标：吨公里约束：需求 供应集合段集合段数据段数据段初始段初始段目标与目标与约束段约束段 最优

30、：最优：89.8835(吨公里吨公里 )局部局部全部？全部？LINGOv求全局解nLingooptions边界n界面界面主窗口主窗口模型窗口模型窗口Model Window状态栏状态栏当前时间当前时间 当前光标当前光标位置位置 五、Lingo的菜单及对话框1、LINGO的界面的界面File|Open（F3）打开文件File|Print（F7）打印文件Edit|Copy(Ctrl+C)复制Edit|Undo(Ctrl+Z)取消操作Edit|Find (Ctrl+F)查找LINGO|Solution(Alt+O)显示解答Edit|Match Parenthesis(Ctrl+P)匹配括号LINGO

31、|Options(Ctrl+I)选项设置Window|Close All (Alt+X)关闭所有窗口Help|Contents（F1）在线帮助File|New（F2）新建文件File|Save(F4)保存文件Edit|Cut(Ctrl+X)剪切Edit|Paste(Ctrl+V)粘贴Edit|Redo(Ctrl+Y)恢复操作Edit | Go To Line(Ctrl+T)定位某行LINGO|Solve (Ctrl+S)求解模型LINGO|Picture(Ctrl+K)模型图示Window|Send to Back (Ctrl+B)窗口后置Window|Tile(Alt+T) 平铺窗口上下文相

32、关的帮助n 2、LINGO的工具栏nFileExport FileUser Database InfonEditPaste Paste Special Match Parenthesis Paste FunctionSelect Font Insert New Object Links Object PropertiesvLINGOLOOKGeneratePicture FileGenerateOptions3、LINGO的菜单栏Variables（变量数量）：变量数量）： 变量总数（变量总数（Total）、）、 非线性变量数（非线性变量数（Nonlinear）、）、 整数变量数（整数变量数（

33、Integer）。）。Constraints（约束数量）：约束数量）： 约束总数（约束总数（Total）、）、 非线性约束个数非线性约束个数(Nonlinear)。Nonzeros（非零系数数量）：非零系数数量）： 总数（总数（Total）、）、 非线性项系数个数非线性项系数个数(Nonlinear)Generator Memory Used (K) (内存使内存使用量用量)Elapsed Runtime (hh:mm:ss)（求解花费的时间）求解花费的时间） 4、LINGO的运行状态窗口求解求解器器(求求解程解程序序)状状态框态框当前模型的类型当前模型的类型 :LP，QP，ILP，IQP，P

34、ILP， PIQP，NLP，INLP，PINLP （以以I开头表示开头表示IP，以以PI开头表示开头表示PIP） 当前解的状态当前解的状态 : Global Optimum, Local Optimum, Feasible, Infeasible“(不可不可行行), Unbounded“(无界无界), Interrupted“(中断中断), Undetermined“(未确定未确定) 解的目标函数值解的目标函数值 当前约束不满足的总量当前约束不满足的总量(不是不不是不满足的约束的个数满足的约束的个数):实数（即使实数（即使该值该值=0，当前解也可能不可行，当前解也可能不可行，因为这个量中没有考

35、虑用上下界因为这个量中没有考虑用上下界命令形式给出的约束）命令形式给出的约束） 目前为止的目前为止的迭代次数迭代次数 运行状态扩展扩展的求的求解器解器(求解求解程序程序)状态状态框框使用的特殊求解程序使用的特殊求解程序 :B-and-B (分枝定界算法分枝定界算法)Global (全局最优求解程序全局最优求解程序)Multistart(用多个初始点求解的程序用多个初始点求解的程序) 目前为止找到的可行目前为止找到的可行解的最佳目标函数值解的最佳目标函数值 目标函数值的界目标函数值的界 特殊求解程序当前运行步数：特殊求解程序当前运行步数：分枝数分枝数(对对B-and-B程序程序)；子问题数子问题数(对对Global程序程序)；初始点数初始点数(对对Multistart程序程序)有效步数有效步数 运行状态n可设置80-90个控制参数 vInterface界面vGeneral Solver通用求解vLinear Solver线性求解vNonlinear Solver非线性求解vInteger Pre-Solver整数预处理vInteger Solver整数求解vGlobal Solver全局最优求解5、Options 7个选项卡