第2章 数学规划方法,2,2020/8/3,2.1基本概念及模型,2.1.1数学规划 （1）数学规划概述 研究对象：数值最优化问题 分支：线性规划、非线性规划、多目标规划、动态规划、参数规划、组合优化和整数规划、随机规划、模糊规划、非光滑优化、多层规划、全局优化、变分不等式与互补问题等。 （2）一般形式 （3）数学规划问题的表述 求满足约束条件的x*，使 成为最优，而将x*称为数学规划问题的最优解，将 称为最优值。,3,2020/8/3,2.1.2 线性规划,（1） 线性规划概念(Linear programming) 针对数学规划，如果决策变量为可控的连续变量，且目标函数和约束函数都是线性的，则称此类数学规划问题为线性规划问题。 （2）基本性质 比例性 要求每个决策变量在目标函数和约束函数中，其贡献与决策变量的值存在直接比例性。 可加性 指所有决策变量对目标函数和约束函数的贡献是相互独立的（包括正向贡献和负向贡献），目标函数值等于每个决策变量各自对目标函数贡献的总和。 确定性 指线性规划中所有目标函数和约束函数中的系数都是确定的常数，不含随机因素。 连续性 指所有的决策变量取值为连续的数。,2.1基本概念及模型,4,2020/8/3,2.1.3 整数规划,（1）整数变量 决策变量是整数，如电视产量，人的数量。 （2）整数规划问题（Integer Programming，IP） 在数学规划中，某些决策变量是整数变量的问题。 （3）整数变量的分类 一般离散型整数变量，即取值为多个离散整数的变量，如产品个数等。 0-1变量，即取值为0或者1的变量，如表示某一经济、管理活动是否执行等。,2.1基本概念及模型,5,2020/8/3,2.1.4目标规划,目标规划（Goal Programming，GP）概念 解决多目标决策的定量分析的数学规划方法 。,2.1基本概念及模型,2.1.5非线性规划,非线性规划（Nonlinear Programming，NLP）概念 若某一数学规划问题的目标函数和约束函数中至少有一个是非线性的，则称此类数学规划为非线性规划 。,6,2020/8/3,线性规划的建模，是将语言文字上的问题转化为线性规划问题。 线性规划的建模从内容上主要包括三部分： 决策变量的识别与描述 目标函数的识别与描述 约束条件的识别与描述,2.2线性规划建模方法,7,2020/8/3,2.2.1 决策变量的识别与描述,决策变量 指运筹学问题或系统中待确定的某些变量，是决策方案的主要组成部分。 范例 牛奶厂生产计划制定问题,2.2线性规划建模方法,2020/8/3,某奶制品加工厂用牛奶生产甲、乙两种奶制品; 生产每千克甲需要0.25桶牛奶在A车间加工4工时; 生产每千克乙需要0.2桶牛奶在B车间加工2工时。 预计生产出的甲、乙能够全部售出； 每千克甲获利32元，每千克乙获利16元。 加工厂每天能得到80桶牛奶的供应； 每天A车间的最大生产能力为640工时； B车间的最大生产能力为500工时。 试为该厂制定生产计划，使得每天的获利最大。,2.2线性规划建模方法,9,2020/8/3,决策变量的识别： 这个优化问题的目标是使每天的获利最大，要做的决策是制定生产计划，即每天生产多少千克的甲奶制品和乙奶制品。 决策变量的定义： 设每天生产x1千克甲奶制品，x2千克乙奶制品。,2.2线性规划建模方法,10,2020/8/3,2.2.2目标函数的识别与描述,目标函数是最优化标准或评价方法的数学描述，通常表示为决策变量的函数。在线性规划中，目标函数是决策变量的线性函数。 范例中的目标是使每天的获利最大，设每天的获利为z元。每千克甲可获利32元，则x1千克甲可获利32 x1元。每千克乙可获利16元，则x2千克乙可获利16 x2元，故目标函数可表示为：,2.2线性规划建模方法,2020/8/3,2.2.3约束条件的识别与描述,约束条件：求目标函数最优值时的某些限制 约束函数 决策变量的非正性/非负性约束 范例,2.2线性规划建模方法,12,2020/8/3,2.2线性规划建模方法,范例中，决策受到三方面的限制： 原料供应：生产甲、乙两种奶制品的原料总量不得超过每天的供应，即0.25x1 +0.2x2 80(桶)。 A车间的生产能力：生产甲奶制品不得超过A车间的最大生产能力，即4 x1 640。 B车间的生产能力：生产乙奶制品不得超过B车间的最大生产能力，即2x2 500。,13,2020/8/3,2.3.1线性规划的求解方法,线性规划的求解方法 图解法、单纯形法、椭球法、内点法等 基于常用的运筹学软件包进行求解的，如win QSB、LINDO、LINGO和Excel等。,2.3 线性规划求解及决策分析,14,2020/8/3,2.3 线性规划求解及决策分析,范例的可行域,O(0,0),z法向,D(0,250),C(160,0),H(160,200),G(160,250),I(120,250),x2,x1=160,0.25x1+0.2x2=80,x2=250,z=0,x1,(0,520),15,2020/8/3,线性规划的解可能有以下几种情况： 唯一最优解 存在一个顶点使得目标函数达到最值。如上题中点H（160，200）。 多重最优解 线性规划问题有无数个最优解。如：在上例中如果因市场需求变化，甲奶制品的的获利减少为20元，其他条件不变，则目标函数变为：z=20 x1+16 x2。此时当目标函数向上移动时会与约束条件0.25x1 +0.2x2 80重合，所以这条直线上在可行域内的所有的点（即线段IH上的所有点）都是函数的最优解。,2.3 线性规划求解及决策分析,16,2020/8/3,无界解，即最优解无界 目标函数：max z= x1+ x2 约束条件：,2.3 线性规划求解及决策分析,z法向,-3x1+2x2=6,X2,2020/8/3,可行域（如下图）：,2.3 线性规划求解及决策分析,Z=0,x1-x2=1,X1,18,2020/8/3,无可行解 若在范例中再增加两个约束条件5x1+4x21800和5x1+4x22200时，此线性规划问题的新可行域为空域(如下图)， 此时不存在满足所有条件的x1和x2，即无可行解。,2.3 线性规划求解及决策分析,5x1+4x21800,5x1+4x2 2200,19,2020/8/3,2.3.2线性规划问题的标准化,（1）线性规划问题（LP问题）有许多不同形式 目标函数的优化准则包括max和min形式。 函数性约束的表达式包括、=和形式。 决策变量的本身约束包括非负性约束，非正性约束和无约束（自由变量）形式。,2.3 线性规划求解及决策分析,20,2020/8/3,（2）LP问题的标准形式（简称标准形） (M1):,2.3 线性规划求解及决策分析,21,2020/8/3,（3） LP问题的简记形式（一） （M2）：,2.3 线性规划求解及决策分析,22,2020/8/3,（3） LP问题的简记形式（二） （M3）：,2.3 线性规划求解及决策分析,其中，cj称之为价值系数，bi称之为右端常数项，aij称之为消耗系数。,23,2020/8/3,（4）非标准形LP问题的标准化方法： 目标函数 若目标函数形如min z = CTX，可令 z=z，则有max z=CTX，例如min z = 4x16x2可变换为max z=4x16x2。 函数性约束条件 若bi0，则表达式两边同时乘以 -1； 若函数性约束为“”形式， 则在“”左侧加上松弛变量； 若函数性约束为“”形式， 则在“”左侧减去剩余变量。 决策变量 若xk 0即满足非正性约束时，令 xk=xk,则 xk 0； 若xk为自由变量时，令 xk=xkxk，且 xk,xk0。,2.3 线性规划求解及决策分析,24,2020/8/3,2.3.3线性规划的解,（1）可行解 若令某一LP问题的所有决策变量的解所构成的向量记为X，则满足LP问题所有约束条件的X称为可行解，所有可行解所构成的集合称为可行域，记为R。 （2）最优解 满足目标要求的可行解称为最优解，记为X *。最优解所对应的目标函数值称为最优值，记为Z*。,2.3 线性规划求解及决策分析,25,2020/8/3,（3）基本解 基本解的概念只适用于标准形LP问题。 范例的标准形：,2.3 线性规划求解及决策分析,26,2020/8/3,设B是由标准型中函数性约束方程中的m个线性无关的系数列向量构成的m阶方阵且 ，则称B为LP问题标准形(M)的一个基矩阵(简称基)。 设 其中 它是A（也是B）阵中第j个列向量，称为基向量；其余n-m个列向量称为非基向量。基向量对应的变量称为基变量；非基向量对应的变量称为非基变量。,2.3 线性规划求解及决策分析,27,2020/8/3,令所有非基变量等于0，基于(2-3)式中函数约束方程，则可得到所有基变量的取值，由此得到的解称为一个关于基B的基本解，简称基本解，也称之为标准形LP问题的一个基本解。若基本解中有一个或更多个基变量等于0 ，则称之为退化基本解。 譬如范例，取基矩阵为,2.3 线性规划求解及决策分析,由于 ，则x3，x4，x5为基变量，x1，x2为非基变量。令x1=0且x2=0，则范例标准型变为：,28,2020/8/3,2.3 线性规划求解及决策分析,求解上述方程组，可得关于B0的基本解为：,29,2020/8/3,另取,2.3 线性规划求解及决策分析,因为 ，所以它也是一个基。它对应的基变量为x2，x3，x4，非基变量为x1，x5。令 这时范例标准型方程组变为：,30,2020/8/3,该方程组有唯一解，为,2.3 线性规划求解及决策分析,于是可得到关于基的基本解为,31,2020/8/3,再取,2.3 线性规划求解及决策分析,为基（因 ）,同理可得关于基的基本解为：,32,2020/8/3,2.3 线性规划求解及决策分析,再取,为基（因 ），同理可得关于B3的基本解为：,它的前两个分量为：恰好是范例的最优解，故称为最优基本解。,33,2020/8/3,总结 有一个基，就有一个基本解。图2- 1中的点O，C，D，H，G，I各对应范例的一个基本解。O (0，0)点对应基本解X0，D(0，250)点对应基本解X1，G(160，250)点对应基本解X2，H(160，200）点对应基本解X * 。,2.3 线性规划求解及决策分析,34,2020/8/3,2.3.4 线性规划问题的灵敏度分析概述,概念 灵敏度分析是分析研究一个线性规划模型中的参数取值的变化对最优解或最优基的影响。 灵敏度分析的任务之一就是确定参数的影响范围。 可以借助Win QSB等运筹学软件包求解模型参数的影响范围。,2.3线性规划求解及决策分析,35,2020/8/3,当某一右端常数项或价值系数在其影响范围内发生变化时，最优基与最优解的变化情况如下： （1）当单独某一bi在其影响范围内变化时，最优基保持不变，但最优解可能变化。 （2）当某一参数cj为非基变量的系数并单独在其影响范围内变化时，最优基保持不变，且最优解和最优值也保持不变。 （3）当某一参数cj为基变量的系数并单独在其影响范围内变化时，最优基与最优解保持不变，但最优值发生变化。,2.3线性规划求解及决策分析,36,2020/8/3,如范例，经计算可得c1的影响范围是20,+)，c2的影响范围是0,25.6。由于x1和x2均是基变量，所以当c1和c2均在影响范围内变化时，最优基与最优解保持不变，但最优值发生变化。 另外，经计算可得，每天可得的牛奶桶数b1的影响范围是40,90，A车间的生产能力上限b2的影响范围是480，1280，B车间的生产能力上限b3的影响范围是400,+)。上述三个