管理决策第二章

第2章数学规划方法管理决策方法课件22019/8/292.1基本概念及模型2.1.1数学规划（1）数学规划概述研究对象：数值最优化问题分支：线性规划、非线性规划、多目标规划、动态规划、参数规划、组合优化和整数规划、随机规划、模糊规划、非光滑优化、多层规划、全局优化、变分不等式与互补问题等。（2）一般形式（3）数学规划问题的表述求满足约束条件的x*，使成为最优，而将x*称为数学规划问题的最优解，将称为最优值。(3),,2,1,0)((2),,2,1,0)(s.t.(1))(optljXhmiXgXfji**Xff*Xf管理决策方法课件32019/8/292.1.2线性规划（1）线性规划概念(Linearprogramming)针对数学规划，如果决策变量为可控的连续变量，且目标函数和约束函数都是线性的，则称此类数学规划问题为线性规划问题。（2）基本性质比例性要求每个决策变量在目标函数和约束函数中，其贡献与决策变量的值存在直接比例性。可加性指所有决策变量对目标函数和约束函数的贡献是相互独立的（包括正向贡献和负向贡献），目标函数值等于每个决策变量各自对目标函数贡献的总和。确定性指线性规划中所有目标函数和约束函数中的系数都是确定的常数，不含随机因素。连续性指所有的决策变量取值为连续的数。2.1基本概念及模型管理决策方法课件42019/8/292.1.3整数规划（1）整数变量决策变量是整数，如电视产量，人的数量。（2）整数规划问题（IntegerProgramming，IP）在数学规划中，某些决策变量是整数变量的问题。（3）整数变量的分类一般离散型整数变量，即取值为多个离散整数的变量，如产品个数等。0-1变量，即取值为0或者1的变量，如表示某一经济、管理活动是否执行等。2.1基本概念及模型管理决策方法课件52019/8/292.1.4目标规划目标规划（GoalProgramming，GP）概念解决多目标决策的定量分析的数学规划方法。2.1基本概念及模型2.1.5非线性规划非线性规划（NonlinearProgramming，NLP）概念若某一数学规划问题的目标函数和约束函数中至少有一个是非线性的，则称此类数学规划为非线性规划。管理决策方法课件62019/8/29线性规划的建模，是将语言文字上的问题转化为线性规划问题。线性规划的建模从内容上主要包括三部分：决策变量的识别与描述目标函数的识别与描述约束条件的识别与描述2.2线性规划建模方法管理决策方法课件72019/8/292.2.1决策变量的识别与描述决策变量指运筹学问题或系统中待确定的某些变量，是决策方案的主要组成部分。范例牛奶厂生产计划制定问题2.2线性规划建模方法管理决策方法课件2019/8/29某奶制品加工厂用牛奶生产甲、乙两种奶制品;生产每千克甲需要0.25桶牛奶在A车间加工4工时;生产每千克乙需要0.2桶牛奶在B车间加工2工时。预计生产出的甲、乙能够全部售出；每千克甲获利32元，每千克乙获利16元。加工厂每天能得到80桶牛奶的供应；每天A车间的最大生产能力为640工时；B车间的最大生产能力为500工时。试为该厂制定生产计划，使得每天的获利最大。2.2线性规划建模方法管理决策方法课件92019/8/29决策变量的识别：这个优化问题的目标是使每天的获利最大，要做的决策是制定生产计划，即每天生产多少千克的甲奶制品和乙奶制品。决策变量的定义：设每天生产x1千克甲奶制品，x2千克乙奶制品。2.2线性规划建模方法管理决策方法课件102019/8/292.2.2目标函数的识别与描述目标函数是最优化标准或评价方法的数学描述，通常表示为决策变量的函数。在线性规划中，目标函数是决策变量的线性函数。范例中的目标是使每天的获利最大，设每天的获利为z元。每千克甲可获利32元，则x1千克甲可获利32x1元。每千克乙可获利16元，则x2千克乙可获利16x2元，故目标函数可表示为：2.2线性规划建模方法211632maxxxz管理决策方法课件2019/8/292.2.3约束条件的识别与描述约束条件：求目标函数最优值时的某些限制约束函数决策变量的非正性/非负性约束范例2.2线性规划建模方法牛奶A车间B车间利润甲产品0.25桶4工时—32乙产品0.20桶—2工时16供应量80桶640工时500工时管理决策方法课件122019/8/292.2线性规划建模方法范例中，决策受到三方面的限制：原料供应：生产甲、乙两种奶制品的原料总量不得超过每天的供应，即0.25x1+0.2x2≤80(桶)。A车间的生产能力：生产甲奶制品不得超过A车间的最大生产能力，即4x1≤640。B车间的生产能力：生产乙奶制品不得超过B车间的最大生产能力，即2x2≤500。,xxxxx.+x.xxz)5(00)4(5002)3(6404)2(8020250s.t.)1(1632max21212121管理决策方法课件132019/8/292.3.1线性规划的求解方法线性规划的求解方法图解法、单纯形法、椭球法、内点法等基于常用的运筹学软件包进行求解的，如winQSB、LINDO、LINGO和Excel等。2.3线性规划求解及决策分析管理决策方法课件142019/8/292.3线性规划求解及决策分析范例的可行域O(0,0)z法向D(0,250)C(160,0)H(160,200)G(160,250)I(120,250)x2x1=1600.25x1+0.2x2=80x2=250z=0x1(0,520)管理决策方法课件152019/8/29线性规划的解可能有以下几种情况：唯一最优解存在一个顶点使得目标函数达到最值。如上题中点H（160，200）。多重最优解线性规划问题有无数个最优解。如：在上例中如果因市场需求变化，甲奶制品的的获利减少为20元，其他条件不变，则目标函数变为：z=20x1+16x2。此时当目标函数向上移动时会与约束条件0.25x1+0.2x2≤80重合，所以这条直线上在可行域内的所有的点（即线段IH上的所有点）都是函数的最优解。2.3线性规划求解及决策分析管理决策方法课件162019/8/29无界解，即最优解无界目标函数：maxz=x1+x2约束条件：2.3线性规划求解及决策分析006231s.t.212121,xxxxxx管理决策方法课件z法向-3x1+2x2=6X22019/8/29可行域（如下图）：2.3线性规划求解及决策分析Z=0x1-x2=1X1管理决策方法课件182019/8/29无可行解若在范例中再增加两个约束条件5x1+4x2≥1800和5x1+4x2≤2200时，此线性规划问题的新可行域为空域(如下图)，此时不存在满足所有条件的x1和x2，即无可行解。2.3线性规划求解及决策分析X1=160X2=2500.25x1+0.2x2=80X1x2O(0,0)C(160,0)D(0,250)5x1+4x2≥18005x1+4x2≤2200管理决策方法课件192019/8/292.3.2线性规划问题的标准化（1）线性规划问题（LP问题）有许多不同形式目标函数的优化准则包括max和min形式。函数性约束的表达式包括≧、=和≦形式。决策变量的本身约束包括非负性约束，非正性约束和无约束（自由变量）形式。2.3线性规划求解及决策分析管理决策方法课件202019/8/29（2）LP问题的标准形式（简称标准形）(M1):2.3线性规划求解及决策分析nn332211xcxcxcxczmax0000s.t.2122112222212111212111,x,,xx)(bxaxaxa)(bxaxaxa)(bxaxaxanmnmnmmnnnn管理决策方法课件212019/8/29（3）LP问题的简记形式（一）（M2）：2.3线性规划求解及决策分析njjjxc1zmax,n,,j,m,,i,xbxajijijnj21210s.t.1管理决策方法课件222019/8/29（3）LP问题的简记形式（二）（M3）：2.3线性规划求解及决策分析XCzTmax0s.t.XBAX其中，cj称之为价值系数，bi称之为右端常数项，aij称之为消耗系数。TncccC),...,,(21，n21cccC，mnmmnnaaaaaaaaaA.....................212222111211，nxxxX...21mbbbb...21管理决策方法课件232019/8/29（4）非标准形LP问题的标准化方法：目标函数若目标函数形如minz=CTX，可令z′=－z，则有maxz′=－CTX，例如minz=4x1＋6x2可变换为maxz′=－4x1－6x2。函数性约束条件①若bi0，则表达式两边同时乘以-1；②若函数性约束为“≤”形式，则在“≤”左侧加上松弛变量；③若函数性约束为“≥”形式，则在“≥”左侧减去剩余变量。决策变量若xk≤0即满足非正性约束时，令xk=－xk′,则xk′≥0；若xk为自由变量时，令xk=xk′－xk〞，且xk′,xk〞≥0。2.3线性规划求解及决策分析管理决策方法课件242019/8/292.3.3线性规划的解（1）可行解若令某一LP问题的所有决策变量的解所构成的向量记为X，则满足LP问题所有约束条件的X称为可行解，所有可行解所构成的集合称为可行域，记为R。（2）最优解满足目标要求的可行解称为最优解，记为X*。最优解所对应的目标函数值称为最优值，记为Z*。2.3线性规划求解及决策分析管理决策方法课件252019/8/29（3）基本解基本解的概念只适用于标准形LP问题。范例的标准形：2.3线性规划求解及决策分析,xxxxxxxx.+x.xxz00500264048020250.s.t1632max21524132121管理决策方法课件262019/8/29设B是由标准型中函数性约束方程中的m个线性无关的系数列向量构成的m阶方阵且，则称B为LP问题标准形(M)的一个基矩阵(简称基)。设其中它是A（也是B）阵中第j个列向量，称为基向量；其余n-m个列向量称为非基向量。基向量对应的变量称为基变量；非基向量对应的变量称为非基变量。2.3线性规划求解及决策分析0,,21BaaaBmnjaaaaTmjjjj,2,1,,,2101B管理决策方法课件272019/8/29令所有非基变量等于0，基于(2-3)式中函数约束方程，则可得到所有基变量的取值，由此得到的解称为一个关于基B的基本解，简称基本解，也称之为标准形LP问题的一个基本解。若基本解中有一个或更多个基变量等于0，则称之为退化基本解。譬如范例，取基矩阵为2.3线性规划求解及决策分析5430,a,aaB由于，则x3，x4，x5为基变量，x1，x2为非基变量。令x1=0且x2=0，则范例标准型变为：00B管理决策方法课件282019/8/292.3线性规划求解及决策分析50064080543xxx求解上述方程组，可得关于B0的基本解为：T,,,,X50064080000管理决策方法课件292019/8/29另取2.3线性规划求解及决策分析00210001204321.,a,aaB因为，所以它也是一个基。它对应的基变量为x2，x3，x4，非基变量为x1，x5。令这时范例标准型方程组变为：01B，xx051500264080202432xxxx.管理决策方法课件302019/8/29该方程组有唯一解，为2.3线性规划求解及决策分析640,30,250432x