运筹学 线性规划 数学模型.ppt

《运筹学 线性规划 数学模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划问题及单纯形法线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论线性规划（概论）两个重要人物：1.利奥尼德·康托洛维奇（1912-1986）苏联数学家，对经济学的主要贡献在于：建立和发展了线性规划方法，并运用于经济分析，对线性规划方法的建立和发展做出了开创新贡献。2.G.B.丹齐克（Dantzing，1914-2005）美国数学家，因创造了单纯形法，被称为“线性规划之父”。1982年，为表彰丹齐克，国际数学规划协会设立丹齐克奖。表彰在数学规划有突出贡献的人几个重大历史事件：1939年，前苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书194

2、7年，美国数学家丹齐克提出单纯形算法（Simpler）1951年美国经济学家库普曼斯出版《生产与配置的活动分析》1950-1956年，线性规划的对偶理论出现1960年丹齐克与沃尔夫建立大规模线性规划问题的分解算法1975年康托洛维奇和库普曼斯因“最有资源配置理论的贡献”荣获诺贝尔经济学奖1979年苏联数学家Khachian提出“椭球法”1984年印度数学家Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。其基本点就是在满足一定约束条件下，使预定的目标达到最优。第一节线性规划问题及其数学模型线性规划在经营管理

3、中，常常用来解决有限资源（人、财、物）的合理分配问题。在经营管理中，几乎一切问题都与有限资源的合理分配利用有关。如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。建立线性规划数学模型是解决线性规划问题的一个重要步骤。建立的线性规划数学模型是否真正的反映客观实际，数学模型本身是否正确，都直接影响求解结果，从而影响决策结果，所以，建立正确的线性规划模型尤为重要。下面举例说明线性规划数学模型的建立。一、线性规划数学模型的建立某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：例1：（产品组合问题）产品名称甲

4、乙单位产品消耗原料原料名称可供利用的原料数量（吨/日）681221AB产品售价（千元/吨）32根据市场调查，有如下资料：1.乙产品的需求量至多2吨/日;2.乙产品的需求量比甲产品的需求量至多大1吨/日。求该厂产值最大的生产方案。提出三个问题大家考虑：1.问题的未知数是什么？2.以什么准则进行决策？3.约束条件是什么？某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：例1：（产品组合问题）产品名称甲乙单位产品消耗原料原料名称可供利用的原料数量（吨/日）681221AB产品售价（千元/吨）32根据市场调查，有如下资料：1.乙产品的需求量至多2吨/日;2.乙产品的需求量比甲产品的需求量至多

5、大1吨/日。求该厂产值最大的生产方案。1.问题的未知数是什么？2.以什么准则进行决策？3.约束条件是什么？设未知数目标函数约束方程这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。①设：甲产品的产量为x1吨/日乙产品的产量为x2吨/日②决策准则是产值最大，用Z代表产值，则有：Z=3x1+2x2Z是x1、x2的函数，称为目标函数，目标是求极大值，即：maxZ=3x1+2x2③约束条件（分三部分：资源限制、市场限制、非负限制）x1+2x2≤62x1+x2≤8x2≤2x2-x1≤1x1，x2≥0约束条件资源限制市场限制非负限制2万m31.4万m32万m31.4万m3整理得数学模型：目

6、标函数：minz=1000x1+800x2约束条件：s.t.x110.8x1+x21.6x12x21.4x10，x20例3、合理下料问题用7.4m长的钢筋，分别截取2.9m、2.1m、1.5m各至少100根，要求用料最少。设xj分别代表采用切割方案1~8所需7.4米的钢筋的数量。二、线性规划问题的共同特征（模型的三要素）⑴每一个问题都用一组决策变量(x1，x2，…，xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。⑵存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。⑶都有一个要求达到的目标，它可用决策变量的线性函数（称为目标

7、函数）来表示。按问题的不同，要求目标函数实现最大化或最小化，max或min。三、线性规划数学模型的一般表示方式求解线性规划问题的任务是：在满足约束条件的所有(x1，x2，…，xn)（可行解）中求出使目标函数达到最大(小)z值的决策变量值(x1*，x2*，…，xn*)（最优解）。1.和式2.向量式3.矩阵式四、线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式。其一般形式如下所示：线