运筹学线性规划数学模型课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章,线性规划问题及单纯形法,线性规划问题及其数学模型,图解法,单纯形法原理,单纯形法计算步骤,单纯形法的进一步讨论,线性规划（概论）,两个重要人物：,1.,利奥尼德,康托洛维奇（,1912-1986,）,苏联数学家，对经济学的主要贡献在于：建立和发展了线性规划方法，并运用于经济分析，对线性规划方法的建立和发展做出了开创新贡献。,2.G.B.,丹齐克（,Dantzing,，,1914-2005,）,美国数学家，因创造了单纯形法，被称为“线性规划之父”。,1982,年，为表彰丹齐克，国际数学规划协会设立丹齐克奖。表彰在数学规划有突出贡献的人,几个重大历史事件：,1939,年，前苏联数学家康托洛维奇出版,生产组织和计划中的数学方法,一书,1947,年，美国数学家丹齐克提出单纯形算法（,Simpler,）,1951,年美国经济学家库普曼斯出版,生产与配置的活动分析,1950-1956,年，线性规划的对偶理论出现,1960,年丹齐克与沃尔夫建立大规模线性规划问题的分解算法,1975,年康托洛维奇和库普曼斯因“最有资源配置理论的贡献”荣获诺贝尔经济学奖,1979,年苏联数学家,Khachian,提出“椭球法”,1984,年印度数学家,Karmarkar,提出“投影梯度法”,线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。其基本点就是,在满足一定约束条件下，使预定的目标达到最优。,第一节 线性规划问题及其数学模型,线性规划在经营管理中，常常用来解决有限资源（人、财、物）的合理分配问题。在经营管理中，几乎一切问题都与有限资源的合理分配利用有关。,如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。,如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。,建立线性规划数学模型是解决线性规划问题的一个重要步骤。,建立的线性规划数学模型是否真正的反映客观实际，数学模型本身是否正确，都直接影响求解结果，从而影响决策结果，所以，建立正确的线性规划模型尤为重要。下面举例说明线性规划数学模型的建立。,一、线性规划数学模型的建立,某厂利用,A、B,两种原料，生产甲、乙两种产品，有关数据如下：,例1：（产品组合问题）,产品名称,甲 乙,单位产品消耗原料,原料名称,可供利用的原料数量（吨,/,日）,6,8,1 2,2 1,A,B,产品售价 （千元/吨）,3 2,根据市场调查，有如下资料：,1.乙产品的需求量至多 2 吨,/,日;,2.乙产品的需求量比甲产品的需求量至多大 1 吨,/,日。,求该厂产值最大的,生产方案,。,提出三个问题大家考虑：,1.问题的未知数是什么？,2.以什么准则进行决策？,3.约束条件是什么？,某厂利用,A、B,两种原料，生产甲、乙两种产品，有关数据如下：,例1：（产品组合问题）,产品名称,甲 乙,单位产品消耗原料,原料名称,可供利用的原料数量（吨,/,日）,6,8,1 2,2 1,A,B,产品售价 （千元/吨）,3 2,根据市场调查，有如下资料：,1.乙产品的需求量至多 2 吨,/,日;,2.乙产品的需求量比甲产品的需求量至多大 1 吨,/,日。,求该厂产值最大的,生产方案。,1.问题的未知数是什么？,2.以什么准则进行决策？,3.约束条件是什么？,设未知数,目标函数,约束方程,这里生产方案指的是如何安排甲、乙产品的产量。显然，,产量是未知数。, 设：甲产品的产量为,x,1,吨,/,日,乙产品的产量为,x,2,吨,/,日,决策准则是产值最大,，用,Z,代表产值，则有：,Z=3x,1,+2x,2,Z,是,x,1、,x,2,的函数，称为目标函数，目标是求极大值，,即：,max Z= 3x,1,+2x,2,约束条件（分三部分：资源限制、市场限制、非负限制）,x,1,+2x,2,6,2x,1,+x,2,8,x,2,2,x,2,-x,1,1,x,1,，,x,2,0,约束条件,资源限制,市场限制,非负限制,2万,m,3,1.4万,m,3,2万,m,3,1.4万,m,3,整理得数学模型：,目标函数：,min,z,= 1000,x,1,+ 800,x,2,约束条件：,s.t.,x,1,1,0.8,x,1,+,x,2,1,.6,x,1,2,x,2,1,.4,x,1,0,，,x,2,0,例,3,、合理下料问题,用7.4,m,长的钢筋，分别截取2.9,m、2.1m、1.5m,各至少100根，要求用料最少。,设,x,j,分别代表采用切割方案18所需7.4米的钢筋的数量。,二、线性规划问题的共同特征（模型的三要素）, 每一个问题都用一组,决策变量,(,x,1,，,x,2,，,，,x,n,),表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。, 存在一定的,约束条件,，这些约束条件可以用一组,线性等式或线性不等式,来表示。, 都有一个要求达到的目标，它可用决策变量的,线性函数,（称为,目标函数,）来表示。按问题的不同，要求目标函数实现最大化或最小化，,max,或,min,。,三、线性规划数学模型的一般表示方式,求解线性规划问题的任务是：在满足约束条件的所有(,x,1,，,x,2,，,x,n,)（,可行解）中求出使目标函数达到最大(小),z,值的决策变量值(,x,1,*,，,x,2,*,，,x,n,*,)（,最优解）。,1,.,和式,2,.,向量式,3,.,矩阵式,四、线性规划问题的标准形式,为了使线性规划问题的解法标准，就要把,一般形式化,为,标准形式,。其,一般形式,如下所示：,线性规划的,标准形式,：,1、目标函数为求极大值；,2、,x,j,0,，,j,=1,2,n,;,3,、,b,i,0,，,i,=1,2,m,;,4,、除非负约束外（,x,j,0,），其余,约束都为等式。,线性规划问题标准形式的要求如下：,标准形式的变换方法,1.,目标函数为,min,型，价值系数一律反号。,因为求,min,Z,等价于求,max (-,Z,),，所以可令,Z,= -,Z,，即化为,max,Z,2.,第,i,个约束的,b,i,为负值，则该行左右两端系数同时反号，同时不等号也要反向。,3.,第,i,个约束为, 型，在不等式左边增加一个非负的变量,x,n+i,，,称为松弛变量；同时令,c,n+i,= 0，,不等式变为等式。,4.,第,i,个约束为, 型，在不等式左边减去一个非负的变量,x,n+i,，,称为剩余变量；同时令,c,n+i,= 0，,不等式变为等式。,5.,若,x,j,0，,令,x,j,= -,x,j,，,代入非标准型，则有,x,j, 0,6.,若,x,j,无约束（不限），令,x,j,=,x,j,-,x,j,，,x,j, 0，,x,j, 0，,代入非标准型,变换举例,例,1.,将下述线性规划问题化为标准型：,令,其中,并按上述规则，该问题的标准形式为：,例,2.,将下述线性规划问题化为标准型,自己做一下练习,注意一下这几处,经过变换化为标准型如下：,x,1,+,x,2,+,x,3,7,x,1,x,2,+,x,3,2,3,x,1,+,x,2,+2,x,3,= 5,x,1,，,x,2,0，,x,3,为无符号约束,例,3,将下述线性规划问题化为标准型,min,z,= ,x,1,+2,x,2,3,x,3,解：用,x,4,-,x,5,替换,x,3,，,令,z,= -,z,x,1,+,x,2,+,(,x,4,-,x,5,) +,x,6,= 7,x,1,x,2,+,(,x,4,-,x,5,),-,x,7,= 2,3,x,1,+,x,2,+2,(,x,4,-,x,5,) = 5,x,1,，,x,2,，,x,4,，,x,5,，,x,6,，,x,7,0,max z,=,x,1,2,x,2,+,3,(,x,4,-,x,5,)+0,x,6,+0,x,7,用标准型求最优解后，再回到原变量。,