单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,管理决策方法课件,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 数学规划方法,2,2024/11/18,2.1,基本概念及模型,2.1.1,数学规划,（,1,）数学规划概述,研究对象：数值最优化问题,分支：线性规划、非线性规划、多目标规划、动态规划、参数规划、组合优化和整数规划、随机规划、模糊规划、非光滑优化、多层规划、全局优化、变分不等式与互补问题等。,（,2,）一般形式,（,3,）数学规划问题的表述,求满足约束条件的,x,*,，使 成为最优，而将,x,*,称为数学规划问题的最优解，将 称为最优值。,3,2024/11/18,2.1.2,线性规划,（,1,） 线性规划概念,(,Linear programming,),针对数学规划，如果决策变量为可控的连续变量，且目标函数和约束函数都是线性的，则称此类数学规划问题为线性规划问题。,（,2,）基本性质,比例性,要求每个决策变量在目标函数和约束函数中，其贡献与决策变量的值存在直接比例性。,可加性,指所有决策变量对目标函数和约束函数的贡献是相互独立的（包括正向贡献和负向贡献），目标函数值等于每个决策变量各自对目标函数贡献的总和,。,确定性,指线性规划中所有目标函数和约束函数中的系数都是确定的常数，不含随机因素,。,连续性,指所有的决策变量取值为连续的数。,2.1,基本概念及模型,4,2024/11/18,2.1.3,整数规划,（,1,）整数变量,决策变量是整数，如电视产量，人的数量。,（,2,）整数规划问题（,Integer Programming,，,IP,）,在数学规划中，某些决策变量是整数变量的问题。,（,3,）整数变量的分类,一般离散型整数变量，即取值为多个离散整数的变量，如产品个数等。,0-1,变量，即取值为,0,或者,1,的变量，如表示某一经济、管理活动是否执行等。,2.1,基本概念及模型,5,2024/11/18,2.1.4,目标规划,目标规划（,Goal Programming,，,GP,）概念,解决多目标决策的定量分析的数学规划方法 。,2.1,基本概念及模型,2.1.5,非线性规划,非线性规划（,Nonlinear Programming,，,NLP,）概念,若某一数学规划问题的目标函数和约束函数中至少有一个是非线性的，则称此类数学规划为非线性规划 。,6,2024/11/18,线性规划的建模，是将语言文字上的问题转化为线性规划问题。,线性规划的建模从内容上主要包括三部分：,决策变量的识别与描述,目标函数的识别与描述,约束条件的识别与描述,2.2,线性规划建模方法,7,2024/11/18,2.2.1,决策变量的识别与描述,决策变量,指运筹学问题或系统中待确定的某些变量，是决策方案的主要组成部分,。,范例,牛奶厂生产计划制定问题,2.2,线性规划建模方法,2024/11/18,某奶制品加工厂用牛奶生产甲、乙两种奶制品,;,生产每千克甲需要,0.25,桶牛奶在,A,车间加工,4,工时,;,生产每千克乙需要,0.2,桶牛奶在,B,车间加工,2,工时。,预计生产出的甲、乙能够全部售出；,每千克甲获利,32,元，每千克乙获利,16,元。,加工厂每天能得到,80,桶牛奶的供应；,每天,A,车间的最大生产能力为,640,工时；,B,车间的最大生产能力为,500,工时。,试为该厂制定生产计划，使得每天的获利最大。,2.2,线性规划建模方法,9,2024/11/18,决策变量的识别：,这个优化问题的目标是使每天的获利最大，要做的决策是制定生产计划，即每天生产多少千克的甲奶制品和乙奶制品。,决策变量的定义：,设每天生产,x,1,千克甲奶制品，,x,2,千克乙奶制品。,2.2,线性规划建模方法,10,2024/11/18,2.2.2,目标函数的识别与描述,目标函数是最优化标准或评价方法的数学描述，通常表示为决策变量的函数。在线性规划中，目标函数是决策变量的线性函数。,范例中的目标是使每天的获利最大，设每天的获利为,z,元。每千克甲可获利,32,元，则,x,1,千克甲可获利,32,x,1,元。每千克乙可获利,16,元，则,x,2,千克乙可获利,16,x,2,元，故目标函数可表示为：,2.2,线性规划建模方法,2024/11/18,2,.2.3,约束条件的识别与描述,约束条件：求目标函数最优值时的某些限制,约束函数,决策变量的非正性,/,非负性约束,范例,2.2,线性规划建模方法,牛奶,A,车间,B,车间,利润,甲产品,0.25,桶,4,工时,32,乙产品,0.20,桶,2,工时,16,供应量,80,桶,640,工时,500,工时,12,2024/11/18,2.2,线性规划建模方法,范例中，决策受到三方面的限制：,原料供应：生产甲、乙两种奶制品的原料总量不得超过每天的供应，即,0.25,x,1,+0.2,x,2,80(,桶,),。,A,车间的生产能力：生产甲奶制品不得超过,A,车间的最大生产能力，即,4,x,1,640,。,B,车间的生产能力：生产乙奶制品不得超过,B,车间的最大生产能力，即,2,x,2,500,。,13,2024/11/18,2.3.1,线性规划的求解方法,线性规划的求解方法,图解法、单纯形法、椭球法、内点法等,基于常用的运筹学软件包进行求解的，如,win QSB,、,LINDO,、,LINGO,和,Excel,等,。,2.3,线性规划求解及决策分析,14,2024/11/18,2.3,线性规划求解及决策分析,范例的可行域,O(0,0),z,法向,D(0,250),C(160,0),H(160,200),G(160,250),I(120,250),x,2,x,1,=160,0.25x,1,+0.2x,2,=80,x,2,=250,z=0,x,1,(0,520),15,2024/11/18,线性规划的解可能有以下几种情况：,唯一最优解,存在一个顶点使得目标函数达到最值。如上题中点,H,（,160,，,200,）,。,多重最优解,线性规划问题有无数个最优解。如：在上例中如果因市场需求变化，甲奶制品的的获利减少为,20,元，其他条件不变，则目标函数变为：,z,=20,x,1,+16,x,2,。此时当目标函数向上移动时会与约束条件,0.25,x,1,+0.2,x,2,80,重合，所以这条直线上在可行域内的所有的点（即线段,IH,上的所有点）都是函数的最优解。,2.3,线性规划求解及决策分析,16,2024/11/18,无界解，即最优解无界,目标函数：,max,z,=,x,1,+,x,2,约束条件：,2.3,线性规划求解及决策分析,z,法向,-3,x,1,+2,x,2,=6,X,2,2024/11/18,可行域（如下图）,：,2.3,线性规划求解及决策分析,Z=0,x,1,-,x,2,=1,X,1,18,2024/11/18,无可行解,若在范例中再增加两个约束条件,5,x,1,+4,x,2,1800,和,5,x,1,+4,x,2,2200,时，此线性规划问题的新可行域为空域,(,如下图,),， 此时不存在满足所有条件的,x,1,和,x,2,，即无可行解。,2.3,线性规划求解及决策分析,5,x,1,+4,x,2,1800,5,x,1,+4,x,2,2200,19,2024/11/18,2,.3.2,线性规划问题的标准化,（,1,）线性规划问题（,LP,问题）有许多不同形式,目标函数的优化准则包括,max,和,min,形式。,函数性约束的表达式包括、,=,和形式。,决策变量的本身约束包括非负性约束，非正性约束和无约束（自由变量）形式。,2.3,线性规划求解及决策分析,20,2024/11/18,（,2,）,LP,问题的标准形式（简称标准形）,(M1):,2.3,线性规划求解及决策分析,21,2024/11/18,（,3,）,LP,问题的简记形式,（一）,（,M2,）：,2.3,线性规划求解及决策分析,22,2024/11/18,（,3,）,LP,问题的简记形式（二）,（,M3,）：,2.3,线性规划求解及决策分析,其中，,c,j,称之为价值系数，,b,i,称之为右端常数项，,a,ij,称之为消耗系数。,23,2024/11/18,（,4,）非标准形,LP,问题的标准化方法：,目标函数,若目标函数形如,min,z,=,C,T,X,，可令,z=,z,，则有,max z=,C,T,X,，,例如,min z = 4,x,1,6,x,2,可变换为,max z=,4,x,1,6,x,2,。,函数性约束条件, 若,b,i,24,顾客,1,的选择条件：,8,l,11,+5,l,21,+5,l,12,+7,l,22,+12,l,13,+9,l,23,+7,l,33,1+24,y,1,即,8,l,11,+5,l,21,+5,l,12,+7,l,22,+12,l,13,+9,l,23,+7,l,33,24,y,1,1,2.6,整数线性规划问题,101,2024/11/18,同理可得其他,7,位顾客的约束条件；,对于属性的选择还有约束，每一种属性只需一个。,对于属性,1,（款式），有以下约束：,l,11,+,l,21,=1,（,l,11,和,l,21,都是,0-1,变量）；,同理，对于属性,2,和属性,3,分别有：,l,12,+,l,22,=1,l,13,+,l,23,+,l,33,=1,2.6,整数线性规划问题,此问题的数学模型为：,目标函数：,102,2024/11/18,约束条件,2.6,整数线性规划问题,103,2024/11/18,经计算得：,2.6,整数线性规划问题,即,l,11,=,l,1,2,=,l,1,3,=1,，,y,1,=,y,3,=,y,6,=1,，最优值为,3,，就是说彩虹服饰设计这种风衣，最多将会得到,7,位顾客中,3,位的青睐。,由于,l,11,=,l,12,=,l,13,=1,，所以彩虹服饰应设计长款、亚麻、暗色系的风衣，顾客,1,，,3,，,6,将偏好彩虹风衣。,104,2024/11/18,2.7.1,目标规划问题实例,例,2- 14,工厂选址问题,工厂选址不仅要考虑厂址与消费市场、厂址与原材料产地之间的物流费用，还要考虑厂址周围的劳动力、交通运输等因素，而且随着环境问题的日益突出，工厂选址还要考虑工厂对周边环境的影响、工厂的公众形象等问题。,例,2- 15,市场调查问题,市场调查往往存在着多个目标，既希望调查能够深入和全面以达到良好的效果，又要考虑成本、时间等因素。,2.7,目标规划问题,105,2024/11/18,例,2- 16,某玩具厂商手