线性、整数规划模型.ppt

优化建模与计算,许顺维,参考书优化建模与LINDO/LINGO软件,谢金星,薛毅编著,清华大学出版社,2005年7月第1版.,内容提要,1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO软件简介,1.优化模型的基本概念,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化:在一定条件下，寻求使目标最大(小)的决策,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值),局部最优解与整体最优解,局部最优解(LocalOptimalSolution,如x1)整体最优解(GlobalOptimalSolution,如x2),优化模型的简单分类,线性规划(LP)目标和约束均为线性函数非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2.优化模型实例,目标函数,约束条件,例2.1线性规划模型(LP),模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域线段组成的凸多边形,目标函数等值线为直线,最优解凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G.B.Dantzig,1947),线性规划模型的解的几种情况,目标,98x1+277x2x120.3x1x22x22,约束,x1+x2100 x12x2x1,x20,二次规划模型(QP),若还要求变量为整数，则是整数二次规划模型(IQP),二次规划模型(QP)-例1.2,决策变量：cij，(xj,yj)16维,非线性规划模型(NLP),非线性规划模型(NLP)例1.3：,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数整数非线性规划(NLP)目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数混合整数规划(MIP)决策变量有整数，也有实数,0-1规划决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,基本思想：隐式地枚举一切可行解（“分而治之”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.,分枝定界法（Bmilkx1+x250;time12*x1+8*x2480;cpct3*x1100;end,Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,20桶牛奶生产A1,30桶生产A2，利润3360元.,LINGO的语法规定：（1）求目标函数的最大值或最小值分别用MAX=或MIN=来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母(AZ)开头，由字母、数字(09)和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号，例如OBJMAX=200*X1+300*X2；,LINGO的语法规定：（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句;（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；（7）乘号“*”必须输入，不能省略。（8）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略。,模型求解,软件实现,LINGO,model:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end,Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,20桶牛奶生产A1,30桶生产A2，利润3360元.,模型求解,reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,结果解释,Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,model:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,最优解下“资源”增加1单位时“效益”的增量,影子价格,35元可买到1桶牛奶，要买吗?,3548,应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,该命令产生当前模型的灵敏度分析报告（需要通过Lingo菜单设置激活）,(1)最优解保持不变的情况下,目标函数的系数变化范围;(2)在影子价格和缩减成本系数都不变的前提下,约束条件右边的常数变化范围;,敏感性分析(“LINGO|Ranges”),注意：灵敏性分析耗费相当多的求解时间，因此当速度很关键时,就没有必要激活它,Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000,最优解不变时目标函数系数允许变化范围,敏感性分析(“LINGO|Ranges”),x1系数范围(64,96),x2系数范围(48,72),A1获利增加到30元/kg，应否改变生产计划?,x1系数由243=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶,每天最多买多少?,最多买10桶!,(目标函数不变),充分条件!,奶制品的生产与销售,由于产品利润、加工时间等均为常数，可建立线性规划模型.,线性规划模型的三要素：决策变量、目标函数、约束条件.,用LINGO求解，输出丰富，利用影子价格和灵敏性分析可对结果做进一步研究.,建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做.,主要内容,整数规划方法,43,2020年6月5日,整数规划的一般模型；,整数规划解的求解方法；,整数规划的软件求解方法；,0-1规划的模型与求解方法；,整数规划的应用案例分析。,如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,制订月生产计划，使工厂的利润最大.,引例汽车生产计划,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3）模型中增加条件：x1,x2,x3均为整数，重新求解.,ObjectiveValue:632.2581VariableValueReducedCostX164.5161290.000000X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226,结果为小数，怎么办？,1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大.,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.,但必须检验它们是否满足约束条件.为什么？,IP可用LINGO直接求解,整数规划(IntegerProgramming,简记IP),IP的最优解x1=64，x2=168，x3=0，最优值z=632,Globaloptimalsolutionfound.Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCostX164.00000-2.000000X2168.0000-3.000000X30.000000-4.000000,模型求解,IP结果输出,IP模型LINGO求解,Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x30;gin(x1);gin(x2);gin(x3);,方法3：化为非线性规划,非线性规划（Non-LinearProgramming，简记NLP）,若生产某类汽车，则至少生产80辆，求生产计划.,x1=0或80,最优解同前.,一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.,53,2020年6月5日,2.整数规划模型的一般形式,一、整数规划的一般模型,问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题,整数规划模型示例,54,2020年6月5日,固定资源分配问题,问题分析与准备,固定资源分配问题,目标,总利润,各车间、各资源利润,资源分配量,决策变量,56,2020年6月5日,固定资源分配问题,3、整数规划的LINGO解法,二、整数规划的求解方法,57,2020年6月5日,58,2020年6月5日,1、0-1整数规划的模型,三、0-1整数规划,59,2020年6月5日,2、指派（或分配）问题,三、0-1整数规划,在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。,2.指派（或分配）问题,60,2020年6月5日,现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：,问如何分配何人去完成何项目使完成4项任务所需总时间最少？,61,2020年6月5日,2.指派（或分配）问题,62,2020年6月5日,2.指派（或分配）问题,63,2020年6月5日,2.指派（或分配）问题,64,2020年6月5日,2.指派（或分配）问题,指派问题的一般模型：,65,2020年6月5日,2.指派（或分配）问题,指派问题的一般模型：,66,2020年6月5日,匈牙利算法的基本思想,因为每个指派问题都有一个相应的效益矩阵，通过初等变换修改效益矩阵的行或列，使得在每一行或列中至少有一个零元素，直到在不同行不同列中都至少有一个零元素为止。从而得到与这些零元素相对应的一个完全分配方案，这个方案对原问题而言是一个最优的分配方案。,3.指派问题的匈牙利算法,67,2020年6月5日,用LINGO求解0-1规划模型,4、0-1规划的LINGO解法,如何选拔队员组成4100m混合泳接力队?,例1混合泳接力队的选拔,5名候选人的百米成绩,穷举法：组成接力队的方案共有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,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.457.5(s),方案是否调整？,敏感性分析？,新方案:乙蝶泳、丙仰泳、丁蛙泳、戊自由泳,IP一般没有与LP相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的.,c43,c54的新数据重新输入模型，用LINGO求解,原分配方案:甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.,讨论,最优解：x21=x32=x43=x51=1,成绩为,混合泳接力队的选拔,指派(Assignment)问题：有若干项任务,每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?,人员数量与任务数量相等,人员数量大于任务数量(本例),人员数量小于任务数量?,建立0-1规划模型是常用方法,为了选修课程门数最少，应学习哪些课程？,例选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,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变量表示策略选择是常用的方法,“要选甲