文档介绍：第三章线性规划模型应用运筹学浙江大学管理学院杜红博士副教授第三章线性规划模型线性规划问题的提出线性规划问题的建模典型特征和基本条件一般模型和标准模型线性规划的图解方法敏感分析与影子价格线性规划模型的应用线性规划问题的提出解决有限资源的最佳分配问题。即如何对有限的资源作出最佳方式的调配和最有利的使用,以使最充分地发挥资源的效能去获取最佳的经济效益。线性规划(LinearProgramming,LP)康托洛维奇1939《生产组织与计划中的数学方法》丹捷格(美)1947单纯形方法第三章线性规划模型线性规划问题的提出线性规划(LP)问题包含下列要素:变量:决策要控制的因素目标:决策目标(最优)的数学描述约束条件:实现目标的一组限制条件求LP问题:在约束条件下使目标最优的一组变量的取值解决环节:确定问题、建立模型、问题求解、经济分析、敏感性分析第三章线性规划模型建立线性规划问题模型线性规划问题举例:教材P40LP模型:决策变量:每周的生产批次G、T目标函数:maxZ=30×G+20×T(获利最大)约束条件:1×G+2×T≤40(配料工序约束)(.)2×G+1×T≤40(整流工序约束)1×G+1×T≤25(包装工序约束)G≥0;T≥0(生产批次的非负约束)第三章线性规划模型第三章线性规划模型建立线性规划问题模型总结模型构建的一般思路:确定该LP问题的目标是什么?实现目标取决于什么因素和条件?确定哪几个因素为决策变量?目标如何用决策变量来加以描述?约束条件如何表达?决策变量本身是否有限制条件?第三章线性规划模型例3-1:请你构建以下问题的LP模型:某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:用线性规划制订使总利润最大的生产计划。第三章线性规划模型建立的模型如下:设变量xi为第i种产品的生产件数(i=1,2,3,4),目标函数Z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下,可以建立如下的线性规划模型:maxZ=++++++≤+++≤+++≤5000x1,x2,x3,x4≥0求解这个线性规划,可以得到最优解为:x1==1500 x3=0x4= 最大利润为: z=(元)请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多,设备类型很多的情况下,用手工方法安排生产计划很难获得满意的结果。另外,变量是否需要取整也是需要考虑的问题。第三章线性规划模型总结:线性规划问题的典型特征可用一些变量表示这类问题的待定方案,这些变量(决策变量)的一组值代表一个具体方案;存在一定的约束条件,这些约束条件都能用关于决策变量的线性不等式或等式来表示;有一个期望达到的目标,这个目标能以某种确定的数量指标刻划出来,而这种数量指标可表示为关于决策变量的线性函数,按所考虑的问题的不同,要求该函数值最大化或最小值。第三章线性规划模型