线性、整数规划模型.ppt

《线性、整数规划模型.ppt》由会员分享，可在线阅读，更多相关《线性、整数规划模型.ppt（91页珍藏版）》请在三一办公上搜索。

1、优化建模与计算,许顺维,参考书优化建模与LINDO/LINGO软件,谢金星,薛毅编著,清华大学出版社,2005年7月第1版.http:/,内容提要,1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO 软件简介,1.优化模型的基本概念,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化:在一定条件下，寻求使目标最大(小)的决策,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化

2、(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值),局部最优解与整体最优解,局部最优解(Local Optimal Solution,如 x1)整体最优解(Global Optimal Solution,如 x2),优化模型的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,优化

3、模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2.优化模型实例,目标函数,约束条件,例2.1 线性规划模型(LP),模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边

4、形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G.B.Dantzig,1947),线性规划模型的解的几种情况,目标,98 x1+277 x2 x12 0.3 x1 x2 2x22,约束,x1+x2 100 x1 2 x2x1,x2 0,二次规划模型(QP),若还要求 变量为整数，则是整数二次规划模型(IQP),二次规划模型(QP)-例1.2,决策变量：ci j，(xj,yj)16维,非线性规划模型(NLP),非线性规划模型(NLP)例1.3：,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数 整数非线性规划(NLP)目

5、标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数 混合整数规划(MIP)决策变量有整数，也有实数,0-1规划 决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,基本思想：隐式地枚举一切可行解（“分而治之”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.,分枝定界法（B&B:Bra

6、nch and Bound）,整数线性规划的分枝定界算法,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,3.LINDO/LINGO软件简介,常用优化软件,1.LINDO/LINGO软件2.MATLAB优化工具箱/Mathematic的优化功能3.SAS(统计分析)软件的优化功能4.EXCEL软件的优化功能5.其他（

7、如CPLEX等）,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划 bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束

8、优化,二次规划quadprog,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司（LINDO Systems Inc.），网址：,LINDO:Linear INteractive and Discrete Optimizer(V6.1)LINDO API:LINDO Application Programming Interface(V4.1)LINGO:Linear INteractive General Optimizer(V10.0)Whats Best!:(SpreadSheet e.g

9、.EXCEL)(V8.0),演示(试用)版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解等。LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。LINGO可以求解:线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等。,LINDO/LINGO软件能求解的模型,优化,线性规划,非线性规划,二次规划,连续优化

10、,整数规划,LINDO,LINGO,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于103),需要掌握的几个重要方面,LINGO：正确阅读求解报告；掌握集合(SETS)的应用；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法,1.2 了解LI

11、NGO的菜单,新建,打开,保存,打印,剪切,复制,粘贴,取消,重做,查找,定位,匹配括号,求解,显示答案,模型图示,选项设置,窗口后置,关闭所有窗口,平铺窗口,在线帮助,上下文相关帮助,文件菜单,编辑菜单,LINGO菜单,窗口菜单,帮助菜单,变量,约束,非零系数,内存使用量,已运行时间,求解器状态,扩展求解器状态,例1 加工奶制品的生产计划,50桶牛奶,时间480h,至多加工100kgA1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/kg，应否改变生产计划？,每天：,问题,x1桶牛奶生

12、产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480h,至多加工100kgA1,基本模型,模型求解,软件实现,LINGO,model:max=72*x1+64*x2;milk x1+x250;time 12*x1+8*x2480;cpct 3*x1100;end,Global optimal solution found.Objective value:3360.000 Total solver iterations:2 Variable Value Reduced C

13、ost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,20桶牛奶生产A1,30桶生产A2，利润3360元.,LINGO的语法规定：（1）求目标函数的最大值或最小值分别用MAX=或MIN=来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母(AZ)开头，由字母、数字(09

14、)和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号，例如OBJMAX=200*X1+300*X2；,LINGO的语法规定：（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句;（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；（7）乘号“*”必须输入，不能省略。（8）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略。,模型求解,软件实现,LINGO,model:max=72*x1+64*x2;milk x1+x250;time 12*x1+8*x2480;cpct 3*x1100;end,Gl

15、obal optimal solution found.Objective value:3360.000 Total solver iterations:2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,20桶牛奶生产A1,30桶生产A2，利润3360元.,模型求

16、解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),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 NO.ITERATIONS=2,也可理解为：为了使该非基变量变成基变量，目

17、标函数中对应系数应增加的量,结果解释,Global optimal solution found.Objective value:3360.000 Total solver iterations:2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,model:max

18、=72*x1+64*x2;milk x1+x250;time 12*x1+8*x2480;cpct 3*x1100;end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,Global optimal solution found.Objective value:3360.000 Total solver iterations:2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MIL

19、K 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,最优解下“资源”增加1单位时“效益”的增量,影子价格,35元可买到1桶牛奶，要买吗?,35 48,应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,该命令产生当前模型的灵敏度分析报告（需要通过Lingo菜单设置激活）,(1)最优解保持不变的情况下,目标函数的系数变化范围;(2)在影子价格和缩减成本系数都不变的前提下,约束条件右边的常数变化范围;,敏感性分析(“LINGO|Ranges”),注意：灵敏性分析耗费相当多的求解时间，因此当速度很关键时,就没有必要

20、激活它,Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.6

21、66667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000,最优解不变时目标函数系数允许变化范围,敏感性分析(“LINGO|Ranges”),x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/kg，应否改变生产计划?,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable All

22、owableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000,影子价格有意义时约束右端的允许变化范围,原料最

23、多增加10,时间最多增加53,35元可买到1桶牛奶,每天最多买多少?,最多买10桶!,(目标函数不变),充分条件!,奶制品的生产与销售,由于产品利润、加工时间等均为常数，可建立线性规划模型.,线性规划模型的三要素：决策变量、目标函数、约束条件.,用LINGO求解，输出丰富，利用影子价格和灵敏性分析可对结果做进一步研究.,建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做.,主要内容,整数规划方法,43,2023年9月29日,整数规划的一般模型；,整数规划解的求解方法；,整数规划的软件求解方法；,0-1规划的模型与求解方法；,整数规划的应用案例分析。,如果生产某一类型汽车，则至少要生产

24、80辆，那么最优的生产计划应作何改变？,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,制订月生产计划，使工厂的利润最大.,引例 汽车生产计划,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3）模型中增加条件：x1,x2,x3 均为整数，重新求解.,Objective Value:632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237

25、Row Slack or Surplus Dual Price 2 0.000000 0.731183 3 0.000000 0.003226,结果为小数，怎么办？,1）舍去小数：取x1=64，x2=167，算出目标函数值 z=629，与LP最优值632.2581相差不大.,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.,但必须检验它们是否满足约束条件.为什么？,IP可用LINGO直接求解,整数规划(Integer Programming,简记IP),IP 的最优解x1=64，x2=168，x3=0，最优值z=632,Global

26、optimal solution found.Objective value:632.0000 Extended solver steps:0 Total solver iterations:3 Variable Value Reduced Cost X1 64.00000-2.000000 X2 168.0000-3.000000 X3 0.000000-4.000000,模型求解,IP 结果输出,IP模型LINGO求解,Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2)

27、;gin(x3);end,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划.,x1,x2,x3=0 或 80,x1=80，x2=150，x3=0，最优值z=610,LINGO中对0-1变量的限定：bin(y1);bin(y2);bin(y3);,方法2：引入0-1变量，化为整数规划,M为大的正数,本例可取1000,Objective Value:610.0000 Variable Value Reduced Cost X1 80.000000-2.000000 X2 150

28、.000000-3.000000 X3 0.000000-4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0 或 80,最优解同前,IP模型LINGO求解,Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x380*y1;%取M=1000 x280*y2;x280*y2;gin(x1);gin(x2);gin(x3);%整数约束bin(y1);bin(y2);bin(y3);%0-1变量end,max=2*x1+3*x

29、2+4*x3;1.5*x1+3*x2+5*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);,方法3：化为非线性规划,非线性规划（Non-Linear Programming，简记NLP）,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0 或 80,最优解同前.,一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.,53,2023年9月29日,2.整数规划模型的一般形式,一、整数规划的一般模型,问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最

30、优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题,整数规划模型示例,54,2023年9月29日,固定资源分配问题,问题分析与准备,固定资源分配问题,目标,总利润,各车间、各资源利润,资源分配量,决策变量,56,2023年9月29日,固定资源分配问题,3、整数规划的LINGO解法,二、整数规划的求解方法,57,2023年9月29日,58,2023年9月29日,1、0-1整数规划的模型,三、0-1 整 数 规 划,59,2023年9月29日,2、指派（或分配）问题,三、0-1 整 数 规 划,在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任

31、务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。,2.指派（或分配）问题,60,2023年9月29日,现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：,问如何分配何人去完成何项目使完成4项任务所需总时间最少？,61,2023年9月29日,2.指派（或分配）问题,62,2023年9月29日,2.指派（或分配）问题,63,2023年9月29日,2.指派（或分配）问题,64,2023年9月29日,2.指派（或分配）问题,指

32、派问题的一般模型：,65,2023年9月29日,2.指派（或分配）问题,指派问题的一般模型：,66,2023年9月29日,匈牙利算法的基本思想,因为每个指派问题都有一个相应的效益矩阵，通过初等变换修改效益矩阵的行或列，使得在每一行或列中至少有一个零元素，直到在不同行不同列中都至少有一个零元素为止。从而得到与这些零元素相对应的一个完全分配方案，这个方案对原问题而言是一个最优的分配方案。,3.指派问题的匈牙利算法,67,2023年9月29日,用LINGO求解0-1规划模型,4、0-1规划的LINGO解法,如何选拔队员组成4100m混合泳接力队?,例1 混合泳接力队的选拔,5名候选人的百米成绩,穷举

33、法：组成接力队的方案共有5!=120种.,讨论:丁的蛙泳成绩退步到；戊的自由泳成绩进步到,组成接力队的方案是否应该调整？,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(s)队员i第j 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,模型求解,MODEL:sets:person/1.5/;position/1.4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6

34、,57.2,67.4,71,83.8,62.4;enddata,输入LINGO求解,min=sum(link:c*x);for(person(i):sum(position(j):x(i,j)=1;);for(position(i):sum(person(j):x(j,i)=1;);for(link:bin(x);END,模型求解,最优解：x14=x21=x32=x43=1,其他变量为0;,输入LINGO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,成绩为253.2(s)=,丁蛙泳c43=69.675.2(s)，戊自由泳c54=62.4 57.5(s),方案是否调整？,敏感性分析？,新方案

35、:乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP一般没有与LP相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的.,c43,c54 的新数据重新输入模型，用LINGO求解,原分配方案:甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,讨论,最优解：x21=x32=x43=x51=1,成绩为,混合泳接力队的选拔,指派(Assignment)问题：有若干项任务,每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?,人员数量与任务数量相等,人员数量大于任务数量(本例),人员数量小于任务数量?,建立0-1规划模型是

36、常用方法,为了选修课程门数最少，应学习哪些课程？,例 选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课，2门计算机课.,先修课程要求,最优解：x1=x2=x3=x6=x7=x9=1,其他为0；6门课程，总学分21.,0-1规划模型,约束条件,x3=1必有x1=x2=1,模型求解（LINGO）,选 课 策 略,用0-1变量表示策略选择是常用的方法,“要选甲(x1)必选乙(x2)”可用x1 x2描述.,“要选甲(x1)必不选乙(x2)”怎样描述?,

37、“甲乙二人至多选一人”怎样描述?,“甲乙二人至少选一人”怎样描述?,78,2023年9月29日,四、案例分析:兼职值班员问题,1.问题的提出,79,2023年9月29日,实验室开放时间为上午8:00至晚上10:00;开放时间内须有且仅有一名学生值班;规定大学生每周值班不少于8小时;研究生每周值班不少于7小时;每名学生每周值班不超3次;每次值班不少于2小时;每天安排值班的学生不超过3人，且其中必须有一名研究生.试为该实验室安排一张人员的值班表，使总支付的报酬这最少。,四、案例分析:兼职值班员问题,1.问题的提出,80,2023年9月29日,四、案例分析:兼职值班员问题,问题的分析,目标,总报酬,

38、每人报酬,每人值班时长,每人每天值班时长,值班时刻表,81,2023年9月29日,四、案例分析:兼职值班员问题,2.模型的建立与求解,82,2023年9月29日,四、案例分析:兼职值班员问题,目标总报酬每人报酬每人值班时长每人每天值班时长值班时刻表,83,2023年9月29日,四、案例分析:兼职值班员问题,实验室开放时间为上午8:00至晚上10:00;,开放时间内须有且仅有一名学生值班;,84,2023年9月29日,四、案例分析:兼职值班员问题,规定大学生每周值班不少于8小时;,85,2023年9月29日,四、案例分析:兼职值班员问题,研究生每周值班不少于7小时;,86,2023年9月29日,四、案例分析:兼职值班员问题,每名学生每周值班不超3次(周末除外);,87,2023年9月29日,四、案例分析:兼职值班员问题,每次值班不少于2小时;,不超过每天小时上限;,88,2023年9月29日,四、案例分析:兼职值班员问题,每天安排值班的学生不超过3人，,且必须有一名研究生.,2、模型的建立与求解,89,2023年9月29日,问题的数学模型：,90,2023年9月29日,3、模型的求解结果,91,2023年9月29日,3、模型的求解结果,