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

第一章 线性规划问题及单纯形法;线性规划（概论） 两个重要人物： 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.问题的未知数是什么？ 2.以什么准则进行决策？ 3.约束条件是什么？;某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：;1.问题的未知数是什么？ 2.以什么准则进行决策？ 3.约束条件是什么？; 这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。 ① 设：甲产品的产量为 x1 吨/日 乙产品的产量为 x2 吨/日 ② 决策准则是产值最大，用 Z 代表产值，则有： Z=3x1+2x2 Z 是x1、x2 的函数，称为目标函数，目标是求极大值， 即：max Z= 3x1+2x2 ③ 约束条件（分三部分：资源限制、市场限制、非负限制） x1+2x2≤6 2x1+x2≤8 x2≤2 x2 -x1≤1 x1，x2≥0 ;2万m3;2万m3;整理得数学模型： 目标函数： 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、合理下料问题; 设 xj 分别代表采用切割方案1~8所需7.4米的钢筋的数量。;;二、线性规划问题的共同特征（模型的三要素）;三、线性规划数学模型的一般表示方式; 求解线性规划问题的任务是：在满足约束条件的所有(x1，x2，…，xn)（可行解）中求出使目标函数达到最大(小)z 值的决策变量值(x1*，x2*，…，xn*)（最优解）。 ; 1.和式;2.向量式;3.矩阵式;四、线性规划问题的标准形式;线性规划的标准形式：;1、目标函数为求极大值； 2、xj≥0，j=1,2,…n; 3、bi≥0，i=1,2,…m; 4、除非负约束外（ xj≥0 ），其余 约束都为等式。;标准形式的变换方法; 变换举例 例1.将下述线性规划问题化为标准型：;;例2.将下述线性规划问题化为标准型;经过变换化为标准型如下：; x1 + x2 + x3 ? 7 x1 – x2 + x3 ? 2 –3 x1+ x2 +2 x3 = 5 x1，x2 ?0，x3为无符号约束第一章 线性规划问题及单纯形法;线性规划（概论） 两个重要人物： 1.利奥尼德·康托洛维奇（1912-1986） 苏联数学家，对经济学的主要贡献在于：建立和发展了线性规划方法，并运用于经济分析，对线性规划方法的建立和发展做出了开创新贡献。 2.G.B.丹齐克（Dantzing，1914-2005） 美国数学家，因创造了单纯形法，被称为“线性规划之父”。1982年，为表彰丹齐克，国际数学规划协会设立丹齐克奖