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

规划问题的基本概念推荐参考书胡运权.运筹学教程.清华大学出版社.1998韩伯棠.管理运筹学.高等教育出版社.2010谢金星等.优化建模与Lindo/Lingo软件.清华大学出版社.2005谭永基等.经济管理数学模型案例教程.高教出版社.2013谭永基.数学模型.复旦大学出版社.2005姜启源.数学模型.高等教育出版社.2010但静.数学建模与数学实验.高等教育出版社.2003姜启源等.大学数学实验.清华大学出版社.2004[美]JoeZhu著.数据包络分析.科学出版社.2016谢中华.Matlab统计分析与应用：40个案例分析.北航出版社.2010规划问题及其模型

在工程技术、经济管理、科学研究等领域中，决策者要求在满足一系列条件要求下，求材料最省、重量最轻、成本最低、时间最短、路程最短、利润最大、误差最小、产量最大等等，都称为优化问题。习惯上，上述的最省、最轻、最低、最短、最大等统称最优。

对于给定的优化问题，决策者根据问题的背景知识或试验数据，将问题进一步简化，用一系列数学符号(变量)来代替问题所涉及的各种已知或未知要素，用这些符号的函数等式或者不等式来反映客观条件或约束，并用这些符号的函数来反映决策者的诉求（欲望或目标），这样的约束和诉求就构成了相应问题的规划模型。一、两个案例案例1

（生产决策问题）

（一个线性规划模型）案例2

（路灯照度问题）

（一个非线性规划问题）

通过两个案例，学习规划模型的建立必要步骤以及书写的规范格式。

某工厂在计划期内要安排I、II两种产品生产。生产单位产品所需的设备台时、A，B两种原材料的消耗、资源的限制以及单件产品利润如表1-1所示表1-1问工厂应分别生产多少单位产品I和产品II，才能获利最多？III资源限制设备原料A原料B11300台时21400kg01250kg利润（元）50100案例1生产决策问题（一个简单的线性规划问题）【问题分析]】（1）这是一个生产决策问题，决策者的目标是生产利润最大（2）与利润有关的是产品的销售量与售价（或单位利润）；（3）生产产品就要消耗资源（这与产量有关），而各种资源又受到客观限制。经验：收入与销售量有关，而资源的消耗量与产品的产量有关。【问题假设】

（1）产品I的产量等于销售量；（2）产品II的产量等于销售量。【符号设置】x1

产品I的一个周期的产量（单位：件）；x2

产品II的一个周期的产量（单位：件）；z工厂一个周期内的总利润（单位：元）。（其中，x1,x2称为决策变量）III资源限制设备原料A原料B11300台时21400kg01250kg利润（元）50100【建立模型】工厂一个生产周期的总利润x1x2生产资料约束（设备限时）（原料A限量）（原料B限量）资源的实际消耗资源的拥有量限制III资源限制设备原料A原料B11300台时21400kg01250kg利润（元）50100其它约束：因为x1和x2都是产品的产量，所以，从数学意义上，有厂家的诉求：一个周期内利润z越大越好！(maxz)

以上分析，将生产过程的未知要素（产品产量）用x1,x2表示，各种客观约束都表达为x1,x2的函数不等式，厂家的诉求（利润）也是x1,x2的函数表达式，将这些数学结构写在一起，就是这个规划问题的数学模型：

这个规划模型，如果抛开这个问题的背景，就是求在五个约束条件下，一次函数z=50x1+100x2的最大值，这是一个纯数学意义上的极大值问题。【数学模型】目标函数条件约束变量约束约束Subjectto受约束于，满足于

虽然有些问题的数学结构很难用数学式子来表达，但习惯上我们称决策变量、约束条件、目标函数为规划问题的三要素。这个问题的目标和约束都是决策变量的一次表达式，称为线性规划。决策变量案例2路灯照度问题(一个非线性规划问题）

如图2-1所示，在一条s=20m宽的道路两侧，分别安装了一只2kw和一只3kw的路灯，它们离地面的高度分别为h1=5m和h2=6m。（1）在漆黑的夜晚，当两只路灯开启时，两只路灯连线路面上最暗的点和最亮的点在哪里？（2）如果3kw路灯的高度可以在3m到9m之间变化，如何求得路面上最暗和最亮的点的位置？（3）如果两只路灯的高度均可以在3m到9m之间变化，结果将如何？图2-1osxP1P2h1h2r1r2【问题分析】经验：（物理学背景知识）

光源点P1在点x处的照度（照亮强度）I1，I1与功率P1成正例，与距离r1的平方成反比，与照射角度α1的正弦成正比。即其中，k为比例系数，同时也是平衡量纲（单位）的量。图2-1osxP1P2h1h2r1r2图2-1osxP1P2h1h2r1r2【问题假设】（1）p1,p2都可以看成点光源；（2）p1,p2在x的照度可以叠加（求和）；【符号设置】（符号设置如有图2-1所示）I:某点处的照度（亮度）；I1：灯P1在该点处的照度；I2：灯P2在该点处的照度；（3）光源只来至两盏灯。s:街道宽；

p1,p2:两个光源的功率；h1,h2:两盏灯的高度；

r1,r2:两盏路灯到x的距离；

x:街道某点的坐标，介于0和s之间；

α1,

α2:光线的入射角。图2-1osxP1P2h1h2r1r2两只灯在点x处的照度为其中，变量之间的关系【建立模型】问题(1)：灯高度不变，求路面照度最弱最强的位置x。数学模型1s.t.也可以化简为代入已知参数，模型简化为即求一元函数I(x)在[0，20]上的最大值与最小值。问题(2)：当3kw的灯的高度在3m到9m之间变化时，路面的最暗和最亮点。数学模型2

即求二元函数I(x,h2)在所给矩形闭区域上的最大值与最小值。问题(3)：两只灯的高度都在3m到9m之间变化时，求路面的最暗和最亮点。数学模型3即求三元函数I(x,h1,h2)在所给条件下的上的最大值与最小值。

像这种目标函数或者约束条件是决策变量的非一次（非线性）的规划模型，称为非线性规划模型。二、规划问题解的概念1、线性规划解的概念

通过具体的例子，学习线性规划问题的可行解、可行域、最优解等概念；通过图解法了解线性规划解的情况；2、非线性规划解的概念

通过具体的例子，学习非线性规划的可行解、可行域、局部最优解、全局最优解等概念；通过例子了解非线性规划求解的特点；3、小结

对比线性规划和非线性规划的图解法，总结两种规划解的不同点（局部和全局）和相同点（迭代法）。1、线性规划解的概念1.1线性规划的可行解

若x1,x2满足条件[1]~[4],则称向量为线性规划问题的一个可行解。[1][2][3][4]例如其中x(1),x(2)为可行解，而x(3),x(4)不是可行解。所有可行解构成的集合称为该线性规划的可行域。

在例1中，若存在x*=[x1*,x2*]T,对D中任何x=[x1,x2]T，都有称x*为该线性规划的最优解（使目标函数最大或最小的可行解）。1.2线性规划的可行域1.3线性规划的最优解1.4可行解、可行域、最优解的几何意义可以用图解法求解两个决策变量的线性规划问题。例3用图解法求解如下线性规划问题解图解法步骤：（1）用x1，x2分别表示横坐标和纵坐标，并根据x1,x2>=0，绘制坐标系；（2）图示各个约束条件所表达的基线及其变化方向；（3）由满足所有条件的点（可行解）构成的集合（区域）就是可行域，（4）图示目标函数的基线，并由变量的变化方向确定基线的平移方向，最后确定最优解；x1x205x2=156x1+2x2=24x1+x2=5Q1Q2Q3Q4可行区域Dx2=z-2x1使得目标函数最大的点Q2(3.5,1.5)Q2对应的点就是线性规划问题的唯一最优解：x*=[x1*=3.5,x2*=1.5]T。

例4用图解法观察下述问题的最优解情况x1x205x2=156x1+2x2=24x1+x2=5Q1Q2Q3Q4x2+x1=0可以看出，Q2Q3上的点全是最优解。即问题有无穷多最优解。

例5判断如下线性规划的解情况X2=3x1x20x2+x1=0可以看出，在可行域内，当可行解变化时，目标函数可以无限增大。即问题为无界解。例6

判断如右线性规划问题的解情况可以看出，该问题两个约束矛盾，无可行解。

综上所述，对于线性规划问题，其结果不外乎下面几种情况：（1）有最优解：唯一最优解或无穷多最优解，且最优解一定在可行域某顶点达到；（2）无界解；（3）无可行解。

在实际的线性规划模型的计算中，如果遇到（2）情况，说明漏掉了重要的约束；如果遇到（3）情况，说明问题有约束冲突，检查约束条件，一般采取如下策略：要么留下主要约束，去掉与之矛盾的次要的约束；要么承认矛盾的合理性，采用多目标规划。

在建立规划模型时，若目标函数如例2中决策变量或者约束方程（不等式）中某些变量为非一次（不是线性），则称建立的数学模型为非线性规划模型。[5]2、非线性规划解的概念模型[5]为非线性规划的标准模型(目标最小化，所有约束都是大于等于)，很多优化理论的推导和优化程序的编译都是按照这种模式展开）。[6]模型[6]称为无约束优化。默认[7]模型[7]称为二次规划(目标是决策变量的二次型，约束都是决策变量的线性约束，它的很多性质跟线性规划类似)。2.1可行集（可行域）给定非线性规划问题[5][10][11][12]2.1.1可行解若x1,x2满足条件[10],[11],[12]，则称向量x=[x1,x2]T为非线规划[5]的可行解。[10][11][12]例如：其中x(1),x(4)不是此问题的可行解，而x(2),x(3)是规划问题[5]的可行解。2.1.2可行集（可行域）称为非线性规划问题[5]的可行集（域）。例8利用图解法，求解如下非线性规划问题【问题分析】:决策变量为x=(x1,x2)T。目标函数表示决策变量ｘ=(x1,x2)T到点(2,1)T的距离的平方（体现为以(2,1)为圆心的圆周半径变化）；第一个约束是一条抛物线（开口朝左,x1为横轴）；第二个约束为一次不等式；同时决策变量非负。（注意等号）解以x1和x2分别为横轴和纵轴，建立直角坐标系，如图2-2：（1）绘制约束曲线；（2）标出可行域：x1x20(右上)2.5(在抛物线上)ABCD抛物线段ABCD为可行域；图2-2x1x20(右上)2.512ABCD如图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：在OQ1Q2Q3Q4O边界上，任取一个顶点，比如O点，计算O的目标函数值，比较O与相邻的顶点Q1和Q4对应的的目标函数值，如果O点的目标函数值最大（最大化目标），O就是最优解；步骤2：如果存在相邻点对应的目标函数值比O点对应的目标函数值大（比如Q1)，用Q1点代替刚才的O点，重复步骤1，直到某个点对应的目标函数值比相邻的点对应的目标函数值都大。对线性规划解的全局性：对于线性规划问题，得到的任何一个最优解都是全局最优解。3.2、非线性规划求解的特点例8图解法截图非线性规划求解原理和线性规划求解原理大致都用迭代法。步骤1：如右图所示，在可行域ABCD抛物线段上任取一个初始点O（有风险），比如这个初始点选在AB之间的某点；步骤2：从O点分别试着朝A和朝B方向走，比较哪个方向会让目标函数减小（最小化目标，如果有多个方向，就选取目标函数减小最快的方向），就准备朝那个方向迈出步伐；步骤3：确定了朝B方向目标函数会减小，就朝B方向跨出最大一步，到达步伐的终点O1；步骤4：用O1替代O点，重复步骤1~3，直到没有方向可走为止。非线性规划迭代法计算的风险：寻找最小（或最大）依赖于初始点。比如刚才的迭代初始值选在AB之间，就会将B点误作为全局最小值点。规避这种风险的方法除了从迭代方法上作改进，就是多选几个初始点计算，然后比较每次计算的最优解，再选取你认为最合适的一个点为全局最优解。（例如：设wifi信号源在(2,1)T，你拿着手机在ABCD段上找离信号源最近的点）三、按照决策变量要求识别规划模型1、整数规划模型

部分决策变量要求取整数，这个要求人能识别，智能机器能识别，同时要求软件能识别；2、0-1规划

对于“是”与“非”的选择问题，多用0-1变量来实现，同样要求人、机器、软件都能识别；3、通过案例学习，了解不同变量之间的交叉约束的线性约束表达。1、整数规划模型例9货物托运问题（一般整数规划）

某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运限制如表1-2货物每件体积/英尺3每件重量/100kg每件利润/百元甲19542乙273403托运限制1365140表1-2

且甲种货物最多托运4件，问两种货物各托运多少件，可获利最大。【问题假设】（1）甲乙两种货物不可分割，即按整数计件；（2）甲乙两货物的体积可以直接相加（软体积）。比如水的体积，就是所占空间的体积（软体积）；碎石的体积就比所占空间的体积小（硬体积）。【符号设置】x1

甲货物装运的件数；x2

乙货物装运的件数；z一次运输的利润（单位：百元）【建立模型】根据问题描述，则总利润为【问题分析】（此问题已高度简化，[问题分析]略去）运输体积约束运输重量约束货物要求约束货物分割要求x1,x2要求取整数；非负约束【数学模型】x1,x2取整（或x1,x2∈Z）线性规划整数线性规划

这种要求所有决策变量的线性规划就称为线性整数规划；要求部分变量取整的称为混合线性整数规划。例10投资场所的选择（一般0-1规划）

某公司计划在市区的东、南、西、北四个区建立销售门面。拟议中有10个位置Ai(i=1,2,…,10)可供选择，考虑到各个地区居民消费水平以及居民的居住密度，规定：在东区A1,A2,A3三个点中至少选择两个；在西区A4,A5两个点中至少选择一个；在南区A6,A7两个点中至少选择一个；在北区A8,A9,A10三个点中至少选择2个。Ai各个点的设备投资以及每年可获利润由于地点不同都不一样，预测情况如下表A1A2A3A4A5A6A7A8A9A10投资额10012015080709080140160180利润36405022203025485861

另外，投资总额不能超过720万元，问应该选择哪几家销售点，可使得年利润为最大？【问题分析】

根据问题的叙述，每个点最多建立一个销售网点，若设xi为第i小区建立的销售网点数，则在第i个点建立销售网点在第i个点不建销售网点i=1,2,…,10这样的0-1决策变量，有如下性质：

即对每个点xi来说，要么取0，要么取1，这样的变量就称为0-1变量，因此，变量也可以设成（1）xi+xj=1：xi和xj有且只有一个取1，另外一个取0；（2）xi+xj<=1：xi和xj最一个多取1；（3）xi+xj>=1：xi和xj至少一个取1；（4）kxj：要么取k，要么取0；（5）x1+x2+…+xm=p(p<=m)：m个中恰好取p个；（6）x1+x2+…+xm<=p：m个中至多取p个；（7）x1+x2+…+xm>=p：m个中至少取p个；（8）xi>=xj：若第j个被选中，则第i个也被选中。思考：xi+xj>=xk表达的意思？？？【问题假设】（1）每个点最多建立一个门面。【符号设置】xi

点Ai建立的门面数，i=1,2,…,10，其中z表示年总利润。根据问题叙述，总利润为总投资额约束【建立模型】选择约束：东区A1,A2,A3三个点至少选择两个:西区A4,A5两个点至少选择一个：南区A6,A7两个点至少选择一个：北区A8,A9,A10三个点至少选择两个：变量约束：【数学模型】s.t.

像这种决策变量只取0和1的线性规划，称为0-1线性规划，属于特殊的整数线性规划，在实际问题中应用广泛。软件也能识别！！例11固定成本问题(变量交叉约束）

高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器的各种资源的数量如表1-3所示表1-3资源小号容器中号容器大号容器金属板/t劳动力/（人/月）机器设备/（台/月）221432843

不考虑固定费用，每种容器出售一只的利润分别为4万元，5万元，6万元，可使用的金属板有500t，劳动力有300人/月，机器有100台/月。

此外，只要生产，不管每种容器的制造数量是多少，都要支付一笔固定的费用，小号为100万元，中号为150万元，大号为200万元。现在要制定一个月生产计划，使