运筹学线性规划数学模型.ppt
第一章 线性规划问题及单纯形法,线性规划问题及其数学模型 图解法 单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,线性规划（概论）两个重要人物：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,1 22 1,AB,产品售价（千元/吨）,3 2,根据市场调查，有如下资料：1.乙产品的需求量至多 2 吨/日;2.乙产品的需求量比甲产品的需求量至多大 1 吨/日。求该厂产值最大的生产方案。,提出三个问题大家考虑：1.问题的未知数是什么？2.以什么准则进行决策？3.约束条件是什么？,某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：,例1：（产品组合问题）,产品名称,甲 乙,单位产品消耗原料,原料名称,可供利用的原料数量（吨/日）,68,1 22 1,AB,产品售价（千元/吨）,3 2,根据市场调查，有如下资料：1.乙产品的需求量至多 2 吨/日;2.乙产品的需求量比甲产品的需求量至多大 1 吨/日。,求该厂产值最大的生产方案。,1.问题的未知数是什么？2.以什么准则进行决策？3.约束条件是什么？,设未知数,目标函数,约束方程,这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。设：甲产品的产量为 x1 吨/日 乙产品的产量为 x2 吨/日 决策准则是产值最大，用 Z 代表产值，则有：Z=3x1+2x2 Z 是x1、x2 的函数，称为目标函数，目标是求极大值，即：max Z=3x1+2x2 约束条件（分三部分：资源限制、市场限制、非负限制）x1+2x26 2x1+x28 x22 x2-x11 x1，x20,约束条件,资源限制,市场限制,非负限制,整理得数学模型：目标函数：min z=1000 x1+800 x2约束条件：s.t.x1 1 0.8 x1+x2 1.6 x1 2 x2 1.4 x1 0，x2 0,例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型，价值系数一律反号。因为求min Z等价于求max(-Z)，所以可令Z=-Z，即化为max Z2.第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向。3.第i 个约束为 型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令 cn+i=0，不等式变为等式。4.第i 个约束为 型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令 cn+i=0，不等式变为等式。5.若xj 0，令 xj=-xj，代入非标准型，则有xj 06.若xj 无约束（不限），令 xj=xj-xj，xj 0，xj 0，代入非标准型,变换举例 例1.将下述线性规划问题化为标准型：,令,其中,并按上述规则，该问题的标准形式为：,例2.将下述线性规划问题化为标准型,自己做一下练习,注意一下这几处,经过变换化为标准型如下：,x1+x2+x3 7 x1 x2+x3 23 x1+x2+2 x3=5x1，x2 0，x3为无符号约束,例3将下述线性规划问题化为标准型 min z=x1+2x2 3x3,解：用x4-x5 替换x3，令z=-z,x1+x2+(x4-x5)+x6=7 x1 x2+(x4-x5)-x7=23x1+x2+2(x4-x5)=5 x1，x2，x4，x5，x6，x7 0,max z=x1 2x2+3(x4-x5)+0 x6+0 x7,用标准型求最优解后，再回到原变量。,
