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

第一章线性规划问题及单纯形法,线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,线性规划（概论）两个重要人物：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：（产品组合问题）,产品名称,甲乙,单位产品消耗原料,原料名称,可供利用的原料数量（吨/日）,68,1221,AB,产品售价（千元/吨）,32,根据市场调查，有如下资料：1.乙产品的需求量至多2吨/日;2.乙产品的需求量比甲产品的需求量至多大1吨/日。求该厂产值最大的生产方案。,提出三个问题大家考虑：1.问题的未知数是什么？2.以什么准则进行决策？3.约束条件是什么？,某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：,例1：（产品组合问题）,产品名称,甲乙,单位产品消耗原料,原料名称,可供利用的原料数量（吨/日）,68,1221,AB,产品售价（千元/吨）,32,根据市场调查，有如下资料：1.乙产品的需求量至多2吨/日;2.乙产品的需求量比甲产品的需求量至多大1吨/日。,求该厂产值最大的生产方案。,1.问题的未知数是什么？2.以什么准则进行决策？3.约束条件是什么？,设未知数,目标函数,约束方程,这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。设：甲产品的产量为x1吨/日乙产品的产量为x2吨/日决策准则是产值最大，用Z代表产值，则有：Z=3x1+2x2Z是x1、x2的函数，称为目标函数，目标是求极大值，即：maxZ=3x1+2x2约束条件（分三部分：资源限制、市场限制、非负限制）x1+2x262x1+x28x22x2-x11x1，x20,约束条件,资源限制,市场限制,非负限制,整理得数学模型：目标函数：minz=1000 x1+800 x2约束条件：s.t.x110.8x1+x21.6x12x21.4x10，x20,例3、合理下料问题,用7.4m长的钢筋，分别截取2.9m、2.1m、1.5m各至少100根，要求用料最少。,设xj分别代表采用切割方案18所需7.4米的钢筋的数量。,二、线性规划问题的共同特征（模型的三要素）,每一个问题都用一组决策变量(x1，x2，xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化，max或min。,三、线性规划数学模型的一般表示方式,求解线性规划问题的任务是：在满足约束条件的所有(x1，x2，xn)（可行解）中求出使目标函数达到最大(小)z值的决策变量值(x1*，x2*，xn*)（最优解）。,1.和式,2.向量式,3.矩阵式,四、线性规划问题的标准形式,为了使线性规划问题的解法标准，就要把一般形式化为标准形式。其一般形式如下所示：,线性规划的标准形式：,1、目标函数为求极大值；2、xj0，j=1,2,n;3、bi0，i=1,2,m;4、除非负约束外（xj0），其余约束都为等式。,线性规划问题标准形式的要求如下：,标准形式的变换方法,1.目标函数为min型，价值系数一律反号。因为求minZ等价于求max(-Z)，所以可令Z=-Z，即化为maxZ2.第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向。3.第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0，不等式变为等式。4.第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0，不等式变为等式。5.若xj0，令xj=-xj，代入非标准型，则有xj06.若xj无约束（不限），令xj=xj-xj，xj0，xj0，代入非标准型,变换举例例1.将下述线性规划问题化为标准型：,令,其中,并按上述规则，该问题的标准形式为：,例2.将下述线性规划问题化为标准型,自己做一下练习,注意一下这几处,经过变换化为标准型如下：,x1+x2+x37x1x2+x323x1+x2+2x3=5x1，x20，x3为无符号约束,例3将下述线性规划问题化为标准型minz=x1+2x23x3,解：用x4-x5替换x3，令z=-z,x1+x2+(x4-x5)+x6=