线性、整数规划模型课件

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

2、的决策,5,学习交流PPT,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束) 可行解（只满足约束）与最优解(取到最优值),6,学习交流PPT,局部最优解与整体最优解,局部最优解 (Local Optimal Solution, 如 x1 ) 整体最优解 (Global Optimal Solution, 如 x2 ),7,学习交流PPT,优化模型的 简单分类,线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)

3、为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,8,学习交流PPT,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,9,学习交流PPT,2. 优化模型实例,目标函数,约束条件,例2.1 线性规划模型(LP),10,学习交流PPT,模型求解,图解法,约束条件,目标函数,z=c (常数) 等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解

4、一定在凸多边形的某个顶点取得。,11,学习交流PPT,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G. B. Dantzig, 1947),12,学习交流PPT,线性规划模型的解的几种情况,13,学习交流PPT,目标,98 x1 + 277 x2 x12 0.3 x1 x2 2x22,约束,x1 + x2 100 x1 2 x

5、2 x1 , x2 0,二次规划模型(QP),若还要求 变量为整数，则是整数二次规划模型(IQP),二次规划模型(QP)-例1.2,14,学习交流PPT,决策变量： ci j，(xj,yj)16维,非线性规划模型 (NLP),非线性规划模型(NLP)例1.3：,15,学习交流PPT,整数规划问题一般形式,整数线性规划(ILP) 目标和约束均为线性函数 整数非线性规划(NLP) 目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数,0-1规划 决策变量只取0或1,16,学习交流PPT,取消整数规划中决策变量

6、为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,17,学习交流PPT,基本思想：隐式地枚举一切可行解（“分而治之”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）. 这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.,分枝定界法（B milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,Global optimal solution found. Obje

7、ctive 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元.,32,学习交流PPT,LINGO的语法规定： （1）求目标函数的

8、最大值或最小值分别用MAX=或MIN=来表示； （2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行； （3）变量名称必须以字母(AZ)开头，由字母、数字(09)和下划线所组成，长度不超过32个字符，不区分大小写； （4）可以给语句加上标号，例如OBJMAX=200*X1+300*X2；,33,学习交流PPT,LINGO的语法规定： （5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句; （6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负； （7）乘号“*”必须输入，不能省略。 （8）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单

9、的模型，这两个语句可以省略。,34,学习交流PPT,模型求解,软件实现,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 Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dua

10、l 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元.,35,学习交流PPT,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0

11、.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,也可理解为： 为了使该非基变量变成基变量，目标函数中对应系数应增加的量,36,学习交流PPT,结果解释,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000

12、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 = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,37,学习交流PPT,结果解释,Global optimal solution f

13、ound. 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,最优解下“资源”增加1单位时“效益”的增量,影子价格,35元可买到1桶牛奶，要买吗?,35 48,

14、应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,38,学习交流PPT,该命令产生当前模型的灵敏度分析报告 （需要通过Lingo菜单设置激活）,(1)最优解保持不变的情况下,目标函数的系数变化范围; (2)在影子价格和缩减成本系数都不变的前提下,约束条件右边的常数变化范围;,敏感性分析 (“LINGO|Ranges” ),注意：灵敏性分析耗费相当多的求解时间，因此当速度很关键时,就没有必要激活它,39,学习交流PPT,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowabl

15、e Allowable Variable 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,最优解不变时目标函数系数允许变化范

16、围,敏感性分析 (“LINGO|Ranges” ),x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/kg，应否改变生产计划?,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),40,学习交流PPT,结果解释,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.0000

17、00 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,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶, 每天最多买多少?,最多买10桶!,(目标函数不变),充分条件 !,41,学习交流PPT,奶

18、制品的生产与销售,由于产品利润、加工时间等均为常数，可建立线性规划模型.,线性规划模型的三要素：决策变量、目标函数、约束条件.,用LINGO求解，输出丰富，利用影子价格和灵敏性分析可对结果做进一步研究.,建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做.,42,学习交流PPT,主要内容,整数规划方法,43,2020年7月13日,整数规划的一般模型；,整数规划解的求解方法；,整数规划的软件求解方法；,0-1规划的模型与求解方法；,整数规划的应用案例分析。,43,学习交流PPT,如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？,汽车厂生产三种类型的汽车，已知各

19、类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,制订月生产计划，使工厂的利润最大.,引例 汽车生产计划,44,学习交流PPT,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,汽车厂生产计划,模型建立,线性规划模型(LP),45,学习交流PPT,模型求解,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 Row Slack

20、 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，通过比较可能得到更优的解.,但必须检验它们是否满足约束条件. 为什么？,46,学习交流PPT,IP可用LINGO直接求解,整数规划(Integer Programming,简记IP),IP 的最优解x1=64，x2=168，x3=0，最优值z=632,Glob

21、al 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 结果输出,47,学习交流PPT,IP模型LINGO求解,Model： max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3600; 280*x1+250*x2+400

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

23、riable Value Reduced Cost X1 80.000000 -2.000000 X2 150.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,最优解同前,50,学习交流PPT,IP模型LINGO求解,Model： max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x380*y1; % 取M=1000 x280*y2; x280*y2; g

24、in(x1);gin(x2);gin(x3); % 整数约束 bin(y1); bin(y2); bin(y3); % 0-1变量 end,51,学习交流PPT,max=2*x1+3*x2+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,最优解同前.,一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要

25、求得到全局最优解时.,52,学习交流PPT,53,2020年7月13日,2. 整数规划模型的一般形式,一、整数规划的一般模型,问题是如何求解整数规划问题呢？ 能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？ 实际上，可借鉴这种思想来解决整数规划问题,53,学习交流PPT,整数规划模型示例,54,2020年7月13日,固定资源分配问题,54,学习交流PPT,问 题 分 析 与 准 备,固定资源分配问题,目标,总利润,各车间、各资源利润,资源分配量,决策变量,55,学习交流PPT,56,2020年7月13日,固定资源分配问题,56,学习交流PPT,3、整数规划的

26、LINGO解法,二、整数规划的求解方法,57,2020年7月13日,57,学习交流PPT,58,2020年7月13日,1、0-1整数规划的模型,三、0-1 整 数 规 划,58,学习交流PPT,59,2020年7月13日,2、指派（或分配）问题,三、0-1 整 数 规 划,在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。 例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。 如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。,59,学习交流PPT,2. 指派（或分配）问题,60,2020年7

27、月13日,现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：,问如何分配何人去完成何项目使完成4项任务所需总时间最少？,60,学习交流PPT,61,2020年7月13日,2. 指派（或分配）问题,61,学习交流PPT,62,2020年7月13日,2. 指派（或分配）问题,62,学习交流PPT,63,2020年7月13日,2. 指派（或分配）问题,63,学习交流PPT,64,2020年7月13日,2. 指派（或分配）问题,指派问题的一般模型：,64,学习交流PPT,65,2020年7月13日,2. 指派（或分配）问题,指派问题的一

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

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

30、, 53, 78, 67.8, 84.6, 59.4, 70, 74.2, 69.6, 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,70,学习交流PPT,模型求解,最优解：x14 = x21 = x32 = x43 = 1, 其他变量为0;,输入LINGO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁

31、 蛙泳.,成绩为253.2(s)=,71,学习交流PPT,丁蛙泳c43 = 69.675.2 (s)，戊自由泳c54= 62.4 57.5 (s), 方案是否调整？,敏感性分析？,新方案:乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP一般没有与LP相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的.,c43, c54 的新数据重新输入模型，用LINGO求解,原分配方案: 甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,讨论,最优解：x21 = x32 = x43 = x51 = 1, 成绩为,72,学习交流PPT,混合泳接力队的选拔,指派(Assignment)问题：有若干项任务, 每项

32、任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?,人员数量与任务数量相等,人员数量大于任务数量(本例),人员数量小于任务数量 ?,建立0-1规划模型是常用方法,73,学习交流PPT,为了选修课程门数最少，应学习哪些课程 ？,例 选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,74,学习交流PPT,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课， 2门计算机课.,75,学习交流PPT,先修课程要求,最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其他为0；6门课程，总学分21.,0-1规划模型,约束条件,x3=1必有x1 = x2 =1,模型求解（LINGO）,76,学习交流PPT,选 课 策 略