文档介绍：工商管理专业基础课运筹学主讲人:刘舒燕武汉理工大学管理学院工商管理系第一部分线性规划(Linear Programming,简称LP)?线性规划的发展?1939年,前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题 1947年,Dantzig提出求解线性规划的单纯形法 1950-1956年,主要研究线性规划的对偶理论 1958年,发表整数规划的割平面法?1960年,Dantzig和Wolfe研究成功分解算法,奠定了大规模线性规划问题理论和算法的基础。?1979年,Khachiyan,1984年,Karmarkaa研究成功线性规划的多项式算法。线性规划研究的主要问题一类是已有一定数量的资源(人力、物质、时间等),研究如何充分合理地使用它们,才能使完成的任务量为最大。——实际上,上述两类问题是一个问题的两个不同的方面,都是求问题的最优解(max 或min )。另一类是当一项任务确定以后,研究如何统筹安排,才能使完成任务所耗费的资源量为最少。 某厂生产两种产品,下表给出了单位产品所需资源及单位产品利润问:应如何安排生产计划,才能使总利润最大?§ 线性规划的基本概念一、问题的提出解::设产品I、II的产量分别为x1、:设总运费为z,则有:max z = 2 x1 + 3 :x1 + 2x2≤ 8 4x1≤ 164x2≤ 12 x1,x2≥ 某厂生产三种药物,这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要求:生产A种药物至少160单位;B种药物恰好200单位,C种药物不超过180单位,且使原料总成本最小。解::设四种原料的使用量分别为:x1、x2 、x3、:设总成本为z,则有:min z = 5 x1 + 6 x2 + 7 x3 + 8 :x1 + 2x2 + x3 + x4≥160 2x1 +4 x3 +2 x4=160 3x1+x2 +x3 +2 x4 ≤180 x1、x2、x3、x4≥08221丁7141丙6102乙5321甲单位成本(元/吨)CBA药物原料二、:X = (x1,x2,…..,xn):max(minz) = c1x1 + c2x2 + ……. + :a11x1 + a12x2 +……..+ a1nxn≤(=≥) b1 a21x1 + a22x2 +……..+ a2nxn≤(=≥) b2………………………………………… am1x1 + am2x2 +……..+ amnxn≤(=≥) bm x1,x2,……xn≥0三、模型特点1 都用一组决策变量X = (x1,x2,…,xn)T表示某一方案,且决策变量取值非负;———满足以上三个条件的数学模型称为线性规划2 都有一个要达到的目标,并且目标要求可以表示成决策变量的线性函数;3 都有一组约束条件,这些约束条件可以用决策变量的线性等式或线性不等式来表示。其它形式其中:),,2,1(0),,2,1(max(min)11njxmibxaxczjnjijijnjjj???????????①求和形式②矩阵形式0max(min)???XbAXCXz???????????????nxxxX?21决策变量常数项???????????????nbbbb?21系数矩阵??nmijmnmmnnaaaaaaaaaaA????????????????????????2**********价值系数???21?其中:§ 线性规划数学模型的建立一、建模条件1 优化条件:问题所要达到的目标能用线型函数描述,且能够用极值(max 或min)来表示;2 限定条件:达到目标受到一定的限制,且这些限制能够用决策变量的线性等式或线性不等式表示;3 选择条件:有多种可选择的方案供决策者选择,以便找出最优方案。二、建模步骤1 确定决策变量:即需要我们作出决策或选择的量。一般情况下,题目问什么就设什么为决策变量。2 找出所有限定条件:即决策变量受到的所有的约束;3 写出目标函数:即问题所要达到的目标,并明确是max 还是min。三、 某工厂生产A、B两种产品,有关资料如下表所示:设总成本为z,A、B产品销量为x1、x2,产品C的销售量为x3,报废量为x4,则:max z = 4 x1 + 10