规划问题的基本概念专题培训课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,规划问题的基本概念,推荐参考书,胡运权,.,运筹学教程,.,清华大学出版社,.1998,韩伯棠,.,管理运筹学,.,高等教育出版社,.2010,谢金星等,.,优化建模与,Lindo/Lingo,软件,.,清华大学出版社,.2005,谭永基等,.,经济管理数学模型案例教程,.,高教出版社,.2013,谭永基,.,数学模型,.,复旦大学出版社,.2005,姜启源,.,数学模型,.,高等教育出版社,.2010,但静,.,数学建模与数学实验,.,高等教育出版社,.2003,姜启源等,.,大学数学实验,.,清华大学出版社,.2004,美,Joe Zhu,著,.,数据包络分析,.,科学出版社,.2016,谢中华,.Matlab,统计分析与应用：,40,个案例分析,.,北航出版社,.2010,规划问题及其模型,在工程技术、经济管理、科学研究等领域中，决策者要求在满足一系列条件要求下，求材料最省、重量最轻、成本最低、时间最短、路程最短、利润最大、误差最小、产量最大等等，都称为,优化问题,。习惯上，上述的最省、最轻、最低、最短、最大等统称,最优,。,对于给定的优化问题，决策者根据问题的背景知识或试验数据，将问题进一步简化，用,一系列数学符号,(,变量,),来代替问题所涉及的各种已知或未知要素，用这些符号的函数等式或者不等式来反映客观条件或约束，并用这些符号的函数来反映决策者的诉求,（欲望或目标），这样的约束和诉求就构成了相应问题的,规划模型,。,一、两个案例,案例,1,（生产决策问题）,（一个线性规划模型）,案例,2,（路灯照度问题）,（一个非线性规划问题）,通过两个案例，学习规划模型的建立必要步骤以及书写的规范格式。,某工厂在计划期内要安排,I,、,II,两种产品生产。生产单位产品所需的设备台时、,A,，,B,两种原材料的消耗、资源的限制以及单件产品利润如表,1-1,所示,表,1-1,问工厂应分别生产多少单位产品,I,和产品,II,，才能获利最多？,I,II,资源限制,设 备,原 料,A,原 料,B,1,1,300,台时,2,1,400 kg,0,1,250 kg,利润（元）,50,100,案例,1,生产决策问题,（一个简单的线性规划问题,）,【,问题分析,】,（,1,）这是一个生产决策问题，决策者的目标是生产利润最大（,2,）与利润有关的是产品的销售量与售价（或单位利润）；（,3,）生产产品就要消耗资源（这与产量有关），而各种资源又受到客观限制。,经验：收入与销售量有关，而资源的消耗量与产品的产量有关。,【,问题假设,】,（,1,）产品,I,的产量等于销售量；,（,2,）产品,II,的产量等于销售量。,【,符号设置,】,x,1,产品,I,的一个周期的产量（单位：件）；,x,2,产品,II,的一个周期的产量（单位：件）；,z,工厂一个周期内的总利润（单位：元）。,（,其中，,x,1,x,2,称为决策变量,）,I,II,资源限制,设 备,原 料,A,原 料,B,1,1,300,台时,2,1,400 kg,0,1,250 kg,利润（元）,50,100,【,建立模型,】,工厂一个生产周期的总利润,x,1,x,2,生产资料约束,（设备限时）,（原料,A,限量）,（原料,B,限量）,资源的实际消耗,资源的拥有量,限制,I,II,资源限制,设 备,原 料,A,原 料,B,1,1,300,台时,2,1,400 kg,0,1,250 kg,利润（元）,50,100,其它约束,：,因为,x,1,和,x,2,都是产品的产量，所以，从数学意义上，有,厂家的诉求,：一个周期内利润,z,越大越好！,(max z),以上分析，将生产过程的未知要素（,产品产量,）用,x,1,x,2,表示，各种,客观约束,都表达为,x,1,x,2,的函数不等式，厂家的,诉求,（利润）也是,x,1,x,2,的函数表达式，将这些数学结构写在一起，就是这个规划问题的,数学模型,：,这个规划模型，如果抛开这个问题的背景，就是求在五个约束条件下，一次函数,z=50 x,1,+100 x,2,的最大值，这是一个纯数学意义上的极大值问题。,【,数学模型,】,目标函数,条件约束,变量约束,约束,Subject to,受约束于，满足于,虽然有些问题的数学结构很难用数学式子来表达，但习惯上我们称,决策变量、约束条件、目标函数,为规划问题的,三要素,。这个问题的目标和约束都是决策变量的一次表达式，称为,线性规划,。,决策变量,案例,2,路灯照度问题,(,一个非线性规划问题,）,如图,2-1,所示，在一条,s=20m,宽的道路两侧，分别安装了一只,2kw,和一只,3kw,的路灯，它们离地面的高度分别为,h,1,=5m,和,h,2,=6m,。（,1,）在漆黑的夜晚，当两只路灯开启时，两只路灯连线路面上最暗的点和最亮的点在哪里？（,2,）如果,3kw,路灯的高度可以在,3m,到,9m,之间变化，如何求得路面上最暗和最亮的点的位置？（,3,）如果两只路灯的高度均可以在,3m,到,9m,之间变化，结果将如何？,图,2-1,o,s,x,P,1,P,2,h,1,h,2,r,1,r,2,【,问题分析,】,经验,：（,物理学背景知识）,光源点,P,1,在点,x,处的照度（照亮强度）,I,1,，,I,1,与功率,P,1,成正例，与距离,r,1,的平方成反比，与照射角度,1,的正弦成正比。即,其中，,k,为比例系数，同时也是平衡量纲（单位）的量。,图,2-1,o,s,x,P,1,P,2,h,1,h,2,r,1,r,2,图,2-1,o,s,x,P,1,P,2,h,1,h,2,r,1,r,2,【,问题假设,】,（,1,）,p,1,p,2,都可以看成点光源；,（,2,）,p,1,p,2,在,x,的照度可以叠加（求和）；,【,符号设置,】,（符号设置如有图,2-1,所示）,I:,某点处的照度（亮度）；,I,1,：灯,P,1,在该点处的照度；,I,2,：灯,P,2,在该点处的照度；,（,3,）光源只来至两盏灯。,s:,街道宽；,p,1,p,2,:,两个光源的功率；,h,1,h,2,:,两盏灯的高度；,r,1,r,2,:,两盏路灯到,x,的距离；,x:,街道某点的坐标，介于,0,和,s,之间；,1,2,:,光线的入射角。,图,2-1,o,s,x,P,1,P,2,h,1,h,2,r,1,r,2,两只灯在点,x,处的照度为,其中，,变量之间的关系,【,建立模型,】,问题,(1),：灯高度不变，求路面照度最弱最强的位置,x,。,数学模型,1,s.t.,也可以化简为,代入已知参数，模型简化为,即求一元函数,I(x),在,0,，,20,上的,最大值与最小值,。,问题,(2),：当,3kw,的灯的高度在,3m,到,9m,之间变化时，路面的最暗和最亮点。,数学模型,2,即求,二元函数,I(x,h,2,),在所给矩形闭区域上的最大值与最小值。,问题,(3),：两只灯的高度都在,3m,到,9m,之间变化时，求路面的最暗和最亮点。,数学模型,3,即求,三元函数,I(x,h,1,h,2,),在所给条件下的上的最大值与最小值,。,像这种目标函数或者约束条件是决策变量的非一次（非线性）的规划模型，称为,非线性规划模型,。,二、规划问题解的概念,1,、线性规划解的概念,通过具体的例子，学习线性规划问题的可行解、可行域、最优解等概念；通过图解法了解线性规划解的情况；,2,、非线性规划解的概念,通过具体的例子，学习非线性规划的可行解、可行域、局部最优解、全局最优解等概念；通过例子了解非线性规划求解的特点；,3,、,小结,对比线性规划和非线性规划,的图解法，总结两种规划解的不同点（,局部和全局,）和相同点（,迭代法,）。,1,、线性规划解的概念,1.1,线性规划的可行解,若,x,1,x,2,满足条件,14,则称向量,为线性规划问题的,一个可行解,。,1,2,3,4,例如,其中,x,(1),x,(2),为可行解，而,x,(3),x,(4),不是可行解。,所有可行解构成的集合,称为该线性规划的,可行域,。,在例,1,中，若存在,x*=x,1,*,x,2,*,T,对,D,中任何,x=x,1,x,2,T,，都有,称,x*,为该线性规划的,最优解,（使目标函数最大或最小的,可行解,）。,1.2,线性规划的可行域,1.3,线性规划的最优解,1.4,可行解、可行域、最优解的几何意义,可以用图解法求解两个决策变量的线性规划问题。,例,3,用图解法求解如下线性规划问题,解 图解法,步骤,：,（,1,）,用,x,1,，,x,2,分别表示横坐标和纵坐标，并根据,x,1,x,2,=0,，,绘制坐标系,；,（,2,）,图示各个约束条件,所表达的基线及其变化方向,；,（,3,）,由满足所有条件的点（,可行解,）构成的集合（区域）,就是,可行域,，,（,4,）,图示目标函数,的基线，并由变量的变化方向确定基线的平移方向，最后确定,最优解,；,x,1,x,2,0,5x,2,=15,6x,1,+2x,2,=24,x,1,+x,2,=5,Q,1,Q,2,Q,3,Q,4,可行区域,D,x,2,=z-2x,1,使得目标函数最大,的点,Q,2,(3.5,1.5),Q,2,对应的点就是线性规划问题的,唯一最优解,：,x*=x,1,*=3.5,x,2,*=1.5,T,。,例,4,用图解法观察下述问题的最优解情况,x,1,x,2,0,5x,2,=15,6x,1,+2x,2,=24,x,1,+x,2,=5,Q,1,Q,2,Q,3,Q,4,x,2,+x,1,=0,可以看出，,Q,2,Q,3,上的点全是最优解。,即问题有,无穷多最优解,。,例,5,判断如下线性规划的解情况,X,2,=3,x,1,x,2,0,x,2,+x,1,=0,可以看出，在可行域内，当可行解变化时，目标函数可以无限增大。即问题为,无界解,。,例,6,判断如右线性规划问题的解情况,可以看出，该问题两个约束矛盾,，,无可行解,。,综上所述，对于线性规划问题，其结果不外乎下面几种情况：,（,1,）,有最优解,：唯一最优解或无穷多最优解，且最优解一定在可行域某顶点达到；,（,2,）,无界解,；,（,3,）,无可行解,。,在实际的线性规划模型的计算中，如果遇到（,2,）情况，说明,漏掉了重要的约束,；如果遇到（,3,）情况，说明问题,有,约束冲突,，检查约束条件，一般采取如下策略：,要么留下主要约束，去掉与之矛盾的次要的约束；要么承认矛盾的合理性，采用多目标规划,。,在建立规划模型时，若目标函数如例,2,中决策变量或者约束方程（不等式）中某些变量为非一次（不是线性），则称建立的数学模型为非线性规划模型。,5,2,、非线性规划解的概念,模型,5,为非线性规划的标准模型,(,目标最小化，所有约束都是大于等于,),，很多优化理论的推导和优化程序的编译都是按照这种模式展开）。,6,模型,6,称为无约束优化。默认,7,模型,7,称为,二次规划,(,目标是决策变量的二次型，约束都是决策变量的线性约束，它的很多性质跟线性规划类似,),。,2.1,可行集（可行域,）,给定非线性规划问题,5,10,11,12,2.1.1,可行解,若,x,1,x,2,满足条件,10,11,12,，则称向量,x=x,1,x,2,T,为非线规划,5,的可行解。,10,11,12,例如：,其中,x,(1),x,(4),不是此问题的可行解，而,x,(2),x,(3),是规划问题,5,的,可行解,。,2.1.2,可行集（可行域,）,称为非线性规划问题,5,的可行集（域）。,例,8,利用图解法，求解如下非线性规划问题,【,问题分析,】:,决策变量为,x=(x,1,x,2,),T,。目标函数表示决,策变量,=(x,1,x,2,),T,到点,(2,1),T,的距离的平方（体现为以,(2,1),为圆心的,圆周半径,变化）；,第一个约束是一条,抛物线,（开口朝左,x,1,为横轴）；,第二个约束为,一次不等式,；同时决策变量非负。,（注意等号）,解 以,x,1,和,x,2,分别为横轴和纵轴，,建立直角坐标系,，如图,2-2,：,（,1,）绘制约束曲线；,（,2,）标出可行域：,x,1,x,2,0,(,右上,),2.5,(,在抛物线上,),A,B,C,D,抛物线段,ABCD,为可行域；,图,2-2,x,1,x,2,0,(,右上,),2.5,1,2,A,B,C,D,如图,2-2,（续）,（,3,）绘制目标函数曲线,该问题的目标是在抛物线段,ABCD,上找一个点，使得这个点到,(2,1),T,的距离的平方最小（,距离本身也是最小,）。这样的点位于以,(2,1),T,为圆心的圆周上。由图示可知，点,D,到,(2,1),T,的距离最小。即,D(4,1),T,就是抛物线段,ABCD,上到点,(2,1),T,距离平方最小的点。,2.2,非线性规划的解的概念,2.2.1,局部极小（极大）点,如右图所示，点,B(2.9104,4.3275),T,比附近的其它点对应的目标函数值都小，称,为,局部极小点,，对应的目标值,f(B),为,局部极小值,；点,C(6.25,2.5),T,对应的目,标函数值比附近的其它目标函数值都大，称为,局部极大点,，对应的目标函数,f(C),称为,局部极大值,。,因为抛物线段,ABCD,上，,B,左右的点到,(2,1),T,的距离都大于,B,到,(2,1),T,的距离；,C,左右的点到,(2,1),T,的距离都小于,C,到,(2,1),T,的距离。,2.2.2,全局最小（最大）点,如右图所示，点,D(4,1),T,到,(2,1),T,的距离小于抛物线段,ABCD,上其它任何点到,(2,1),T,的距离，称点,D,为此规划的,全局最小值点,，,f(D),称为,全局最小值,。,点,A(0,5),T,到点,(2,1),T,的距离大于抛物线段,ABCD,上任何点到,(2,1),T,的距离，称点,A,为全,局最大值点,，,f(A),称为,全局最大值,。,3.1,、线性规划求解的特点,例,3,的图解法截图,3,、,线性规划与非线性规划最优解求解的根本区别,例,4,图解法截图,线性规划最优解的特点,：,（,1,）线性规划的可行域都是直线段围成的（凸）多边形区域；,（,2,）只要线性规划存在最优解（不管是唯一最优解还是无穷多最优解），就一定会在边界的,顶点处,到达；,（,3,）寻找线性规划最优解的原理：,【,单纯形法,】,步骤,1,：在,OQ,1,Q,2,Q,3,Q,4,O,边界上，任取一个顶点，比如,O,点，计算,O,的目标函数值，比较,O,与相邻的顶点,Q,1,和,Q,4,对应的的目标函数值，如果,O,点的目标函数值最大（最大化目标），,O,就是最优解；,步骤,2,：如果存在相邻点对应的目标函数值比,O,点对应的目标函数值大（比如,Q,1,),，用,Q,1,点代替刚才的,O,点，重复步骤,1,，直到某个点对应的目标函数值比相邻的点对应的目标函数值都大。,对线性规划解的全局性：,对于线性规划问题，得到的,任何一个最优解,都是,全局最优解,。,3.2,、非线性规划求解的特点,例,8,图解法截图,非线性规划求解原理和线性规划求解原理大致都用,迭代法,。,步骤,1,：如右图所示，在可行域,ABCD,抛物线段上任取一个初始点,O,（,有风险,），比如这个初始点选在,AB,之间的某点；,步骤,2,：从,O,点分别试着朝,A,和朝,B,方向走，比较哪个方向会让目标函数减小（最小化目标，如果有多个方向，就选取目标函数减小最快的方向），就准备朝那个方向迈出步伐；,步骤,3,：确定了朝,B,方向目标函数会减小，就朝,B,方向跨出最大一步，到达步伐的终点,O,1,；,步骤,4,：用,O,1,替代,O,点，重复步骤,13,，直到没有方向可走为止。,非线性规划迭代法计算的风险,：寻找最小（或最大）依赖于初始点。比如刚才的迭代初始值选在,AB,之间，就会将,B,点误作为全局最小值点。规避这种风险的方法除了从迭代方法上作改进，就是,多选几个初始点,计算，然后比较每次计算的最优解，再选取你认为最合适的一个点为全局最优解。（例如：,设,wifi,信号源在,(2,1),T,，你拿着手机在,ABC D,段上找离信号源最近的点）,三、按照决策变量要求识别规划模型,1,、整数规划模型,部分决策变量要求取整数，这个要求人能识别，智能机器能识别，同时要求软件能识别；,2,、,0-1,规划,对于“是”与“非”的选择问题，多用,0-1,变量来实现，同样要求人、机器、软件都能识别；,3,、通过案例,学习，了解不同变量之间的交叉约束的线性约束表达。,1,、,整数规划模型,例,9,货物托运问题（一般整数规划）,某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运限制如表,1-2,货物,每件体积,/,英尺,3,每件重量,/100kg,每件利润,/,百元,甲,195,4,2,乙,273,40,3,托运限制,1365,140,表,1-2,且甲种货物最多托运,4,件，问两种货物各托运多少件，可获利最大。,【,问题假设,】,（,1,）甲乙两种货物不可分割，即按整数计件；,（,2,）甲乙两货物的体积可以直接相加（软体积）。比如水的体积，就是所占空间的体积（软体积）；碎石的体积就比所占空间的体积小（硬体积）。,【,符号设置,】,x,1,甲货物装运的件数；,x,2,乙货物装运的件数；,z,一次运输的利润（单位：百元）,【,建立模型,】,根据问题描述，则总利润为,【,问题分析,】,（此问题已高度简化，,问题分析,略去）,运输体积约束,运输重量约束,货物要求约束,货物分割要求,x,1,x,2,要求取整数；,非负约束,【,数学模型,】,x,1,x,2,取整（或,x,1,x,2,Z,）,线性规划,整数线性规划,这种要求所有决策变量的线性规划就称为,线性整数规划,；要求部分变量取整的称为,混合线性整数规划。,例,10,投资场所的选择（一般,0-1,规划）,某公司计划在市区的东、南、西、北四个区建立销售门面。拟议中有,10,个位置,A,i,(i=1,2,10),可供选择，考虑到各个地区居民消费水平以及居民的居住密度，规定：,在东区,A,1,A,2,A,3,三个点中至少选择两个；,在西区,A,4,A,5,两个点中至少选择一个；,在南区,A,6,A,7,两个点中至少选择一个；,在北区,A,8,A,9,A,10,三个点中至少选择,2,个。,A,i,各个点的设备投资以及每年可获利润由于地点不同都不一样，预测情况如下表,A,1,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,投资额,100,120,150,80,70,90,80,140,160,180,利 润,36,40,50,22,20,30,25,48,58,61,另外，投资总额不能超过,720,万元，问应该选择哪几家销售点，可使得年利润为最大？,【,问题分析,】,根据问题的叙述，每个点最多建立一个销售网点，若设,x,i,为第,i,小区建立的销售网点数,，则,在第,i,个点建立销售网点,在第,i,个点不建销售网点,i=1,2,10,这样的,0-1,决策变量,，有如下,性质,：,即对每个点,x,i,来说，,要么取,0,，要么取,1,，这样的变量就称为,0-1,变量，因此，变量也可以设成,（,1,）,x,i,+x,j,=1,：,x,i,和,x,j,有且只有一个取,1,，另外一个取,0,；,（,2,）,x,i,+x,j,=1,：,x,i,和,x,j,至少一个取,1,；,（,4,）,kx,j,：要么取,k,，要么取,0,；,（,5,）,x,1,+x,2,+x,m,=p(p=m),：,m,个中恰好取,p,个；,（,6,）,x,1,+x,2,+x,m,=p,：,m,个中至少取,p,个；,（,8,）,x,i,=x,j,：若第,j,个被选中，则第,i,个也被选中。,思考,：,x,i,+x,j,=x,k,表达的意思？,【,问题假设,】,（,1,）每个点最多建立一个门面。,【,符号设置,】,x,i,点,A,i,建立的门面数，,i=1,2,10,，其中,z,表示年总利润。,根据问题叙述，总利润为,总投资额约束,【,建立模型,】,选择约束,：,东区,A,1,A,2,A,3,三个点至少选择两个,:,西区,A,4,A,5,两个点至少选择一个：,南区,A,6,A,7,两个点至少选择一个：,北区,A,8,A,9,A,10,三个点至少选择两个：,变量约束,：,【,数学模型,】,s.t.,像这种,决策变量只取,0,和,1,的线性规划,，称为,0-1,线性规划,，属于特殊的整数线性规划，在实际问题中应用广泛。,软件也能识别！,例,11,固定成本问题,(,变量交叉约束,）,高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器的各种资源的数量如表,1-3,所示,表,1-3,资 源,小号容器,中号容器,大号容器,金属板,/t,劳动力,/,（人,/,月）,机器设备,/,（台,/,月）,2,2,1,4,3,2,8,4,3,不考虑固定费用，每种容器出售一只的利润分别为,4,万元，,5,万元，,6,万元，可使用的金属板有,500t,，劳动力有,300,人,/,月，机器有,100,台,/,月。,此外，只要生产，不管每种容器的制造数量是多少，都要支付一笔固定的费用，小号为,100,万元，中号为,150,万元，大号为,200,万元。现在要制定一个月生产计划，使得获利为最大。,【,问题分析,】,此问题是一个生产决策问题，决策者需要决定三种型号的容器各生产多少件。不管哪种型号的容器，只要产量在,1,件或,1,件以上，就需要铺设生产线，其固定费用需要支出；若此型号的容器的产量为,0,，就不用铺设生产线，就不需要支出固定费用。,【,问题假设,】,（,1,）不管哪种容器，不可分割，即整数计件；,（,2,）生产常识：如果某种容器不生产,(,产量为,0,），则固定费用不用支出；,【,符号设置,】,x,1,x,2,x,3,表示小、中、大三种容器的产量；,y,1,表示生产小号容器的固定费用支出次数；,y,2,生产中号容器的固定费用支出次数；,y,3,生产大号容器的固定费用的支出次数；,（,3,）三种容器的产量等于销售量。,【,建立模型,】,或,支出第,i,号容器的固定费用，,不支出第,i,号容器的固定费用，,i=1,2,3,表示小号、中号、大号容器；,根据假设（,2,），有,（变量交叉约束）,z,表示生产利润。,公司的利润为,z,（万元），根据题意，有,各种限制为：,钢板限制：,劳动力限制：,机器设备限制：,变量约束：,x,1,x,2,x,3,取整数；,y,1,y,2,y,3,取,0,和,1.,【,数学模型,】,s.t.,x,1,x,2,x,3,=0,x,1,x,2,x,3,取整数，,y,1,y,2,y,3,取,0,或,1.,*,*,所对应的约束，人懂！计算机未必能懂！,变量之间的约束关系：,（,M,是一个很大的正数，比如,M=500,）,（,1,）最大化目标（利润）,1,2,思考：为何这时,1,与,2,是等价约束？,模型的改进,变量之间的约束关系：,（其中，,M,是一个很大的正整数，比如,M=500,。）,（,2,）无目标方向的约束关系（即不管,z,是最大化还是最小化）的转化：,【,数学模型,1】,s.t.,x,1,x,2,x,3,=0,x,1,x,2,x,3,取整数，,y,1,y,2,y,3,取,0,或,1.,这个问题，,x,i,的取值不超过,100,，取,M=100,即可。,【,数学模型,2】,s.t.,x,1,x,2,x,3,=0,x,1,x,2,x,3,取整数，,y,1,y,2,y,3,取,0,或,1.,(,非线性表达,),模型,1,是线性规划，模型,2,是非线性规划（模型规模庞大时,计算复杂，费时不讨好）,