《数学建模提高班专题一--规划模型、案例及软件求解(2016-1-18)final》由会员分享，可在线阅读，更多相关《数学建模提高班专题一--规划模型、案例及软件求解(2016-1-18)final（94页珍藏版）》请在金锄头文库上搜索。
1、历届竞赛赛题基本解法,历届竞赛赛题基本解法,历届竞赛赛题基本解法,历届竞赛赛题基本解法,规划模型、案例及软件求解,一、引言,二、线性规划模型及软件求解,三、整数规划模型,四、多目标规划模型,在数模竞赛过程中，规划模型是最常见的一,类数学模型. 从92-09年全国大学生数模竞赛试题,的解题方法统计结果来看，规划模型共出现了18,次，占到了近50%，也就是说每两道竞赛题中就有,一道涉及到利用规划理论来分析、求解.,如何来分配有限资源，从而达到人们期望目标的优化分配数学模型. 它在数学建模中处于中心的地位. 这类问题一般可以归结为数学规划模型.规划模型的应用极其广泛，其作用已为越来越多的人所重视.,
2、一、引言,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,可行解（满足约束）与可行域（可行解的集合）最优解（取到最小大值的可行解）,约束优化的简单分类,线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,建立规划模型的一般步骤,1.确定决策变量和目标变量；2.确定目标函数的表达式；3
3、.寻找约束条件。,二、线性规划模型的求解,Lingo与Lindo求解,Matlab求解,Lingo与Lindo,Lindo与Lingo都是LINDO系统公司开发的专门用于求解最优化问题的软件包。与Lindo相比，Lingo软件主要具有两大优点：（1）除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题。（2）LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中。,LINDO和LINGO软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划(LP),非线性规划(NLP),二次规划(QP
4、),连续优化,整数规划(IP),LINGO,LINGO是Linear Interactive and General Optimizer的缩写，即“交互式的线性和通用优化求解器”。Lingo超强的优化计算能力在很多方面（线性规划、非线性规划、线性整数规划、非线性整数规划、非线性混合规划、二次规划等）比matlab、maple等强得多，Lingo编程简洁明了，数学模型不用做大的改动（或者不用改动）便可以直接采用Lingo语言编程，,LP QP NLP IP 全局优化(选) ILP IQP INLP,LINDO/LINGO软件的求解过程,LINDO/LINGO预处理程序,线性优化求解程序,非线性优
5、化求解程序,分枝定界管理程序,1. 确定常数2. 识别类型,1. 单纯形算法2. 内点算法(选),1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选),建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103),1某家具公司
6、制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：,若要求餐桌的生产量不超过5件，如何安排三种产品的生产可使利润最大？,解：用desks、tables和chairs分别表示三种产品的生产量，建立线性规划（LP）模型,在命令窗口中输入：Model:max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+0.5*chairs=8；tables=5;end,Global optimal solution fou
7、nd at iteration: 6 Objective value: 280.0000 Variable Value Reduced Cost DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 Row Slack or Surplus Dual Price 1 280.0000 1.000000 2 24.00000 0.000000 3 0.000000 10.00000 4 0.000000 10.00000 5 5.000000 0.000000,表示次迭代后得到全局最优解,表示最优目标值
8、为280,最优解中各变量的值,值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),给出松驰变量的值,若值为，表示该约束为紧约束,第一行表示目标函数,第二行对应第一个约束,对偶价格表示当对应约束有微小变动时, 目标函数的变化率,Model:max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+0.5*chairs=8;tables0.01;abs(chairs-8)0.01;end,2 加工奶
9、制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,时间480小时,至多加工100公斤A1,综上所述,Max z=72x1+64x2；s. t. x1+x250， 12x1+8x2480， 3x1100， x1，x20,Lingo模型,这
10、是一个（连 续）线性规划（LP）问题,模型求解,软件实现,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生产A1, 30桶生产A2，利润3360元。,max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;,结果解释,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.00000
11、0 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力剩余40,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR S
12、URPLUS 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, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,灵敏度分析,敏感性分析的作用是给出“Ranges in which the basis is unchanged”，即研究当目标函数的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基（矩阵）保持不变。注意：这里LINGO不询问是否进行敏感性分析。如果需要进行敏感性分析，必须用“LINGO |Options”命令打开系统选项对话框，在“General Solver”标签下的“Dual Computations”下拉列表中选中“Prices & Range”，再按下“OK”按钮激活敏感性分析功能。修改了系统选项后，以后只需调用“LINGO |Range”命令即可进行敏感性分析了。,
