[理学]运筹学_线性规划_数学模型、.ppt

线性规划（概论） 两个重要人物： 1.利奥尼德·康托洛维奇（1912-1986） 苏联数学家，对经济学的主要贡献在于：建立和发展了线性规划方法，并运用于经济分析，对线性规划方法的建立和发展做出了开创新贡献。 2.G.B.丹齐克（Dantzing，1914-2005） 美国数学家，因创造了单纯形法，被称为“线性规划之父”。1982年，为表彰丹齐克，国际数学规划协会设立丹齐克奖。表彰在数学规划有突出贡献的人 几个重大历史事件： 1939年，前苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书 1947年，美国数学家丹齐克提出单纯形算法（Simpler） 1951年美国经济学家库普曼斯出版《生产与配置的活动分析》 1950-1956年，线性规划的对偶理论出现 1960年丹齐克与沃尔夫建立大规模线性规划问题的分解算法 1975年康托洛维奇和库普曼斯因“最有资源配置理论的贡献”荣获诺贝尔经济学奖 1979年苏联数学家Khachian提出“椭球法” 1984年印度数学家Karmarkar提出“投影梯度法” 线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。其基本点就是在满足一定约束条件下，使预定的目标达到最优。 例4营养问题 某动物饲养场利用n种天然饲料来配制混合饲料使用，已知单位第j种天然饲料的价格为cj，它含有第i种营养成份的量为aij；根据动物生长的需要，要求具有m种营养成份，且第i种营养成份的含量不得低于bi。试确定在保证动物营养需要的条件下用最低的饲料配合法。 设xj为第j种天然饲料的使用量，则aij xj为第j种天然饲料含有第i种营养成分的数量。则： 某集团有1000000元资金供投资，该集团有5个可供选择的投资项目，其中各种资料如下表： 例6、 [分析建模]：决策变量为从第 i 班开始工作的人数，设为 xi（i =1,2,3,4,5,6,7,8）。 例7、 例8、（模型） 符号规定和基本假设 模型简化 二、线性规划问题的共同特征（模型的三要素） ⑴ 每一个问题都用一组决策变量(x1，x2，…，xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。 ⑵ 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 ⑶ 都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化，max或min。 三、线性规划数学模型的一般表示方式 1.和式 2.向量式 3.矩阵式 2.标准式 线性规划的标准形式： 四、线性规划模型的一般步骤 ◆定义问题和收集数据。必须向管理者咨询所要　　考虑问题涉及到的数据及确定研究的合理目标。 ◆建立模型，用恰当的数学式表示问题。 ◆求出问题的最优解。 ◆进行敏感性分析，检查条件发生变化时可能发生的情况。 线性规划模型 求解线性规划问题的任务是：在满足约束条件的所有(x1，x2，…，xn)（可行解）中求出使目标函数达到最大(小)z 值的决策变量值(x1*，x2*，…，xn*)（最优解）。 为了使线性规划问题的解法标准，就要把一般形式化为标准形式。其一般形式如下所示： 1、目标函数为求极大值； 2、xj≥0，j=1,2,…n; 3、bi≥0，i=1,2,…m; 4、除非负约束外（ xj≥0 ），其余 约束都为等式。 线性规划问题标准形式的要求如下： 标准形式的变换方法 1.目标函数为min型，价值系数一律反号。 因为求min Z等价于求max (-Z)，所以可令Z= -Z，即化为max Z 2.第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向。 3.第i 个约束为 ? 型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 0，不等式变为等式。 4.第i 个约束为 ? 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 0，不等式变为等式。 5.若xj ?0，令 xj= -xj? ，代入非标准型，则有xj? ? 0 6.若xj 无约束（?不限），令 xj= xj? - xj?， xj? ? 0，xj? ? 0，代入非标准型 令 其中 并按上述规则，该问题的标准形式为： * * 线性规划问题 线性规划概论 线性规划问题及模型 线性规划问题的共同特征 线性规划一般表达式式及标准式 线性规划模型的一般步骤 *** 线性规划问题及其数学模型 线性规划在经营管理中，常常用来解决有限资源（人、财、物）的合理分配问题。在经营管理中，几乎一切问题都与有限资源