运筹学讲义.doc

运筹学讲义绪论(2学时)参考教材:运筹学基础教程(魏权龄)管理运筹学(韩伯棠)管理运筹学通论(韩大卫)运筹学(胡运权)先修课程:一元微积分、线性代数、概率统计学时:48+(8)主讲教师:狄军锋运筹学发展运筹学的产生最早与1938年出现于英国,简称OR(operationalResearch)夫运筹帷幄之中,决胜于千里之外,吾不如子房。---史记古代运筹学思想:田忌赛马+丁谓挖沟+沈括运军粮二战中的运筹学:反潜艇策略、深水炸弹的起爆深度、诺曼底登陆运筹学在我国的发展:50年代中期,钱学森、许国志等教授将运筹学由西方引入我国。管梅谷(1962年,山东师范大学):“中国邮递员问题”华罗庚:优选法(1970)和统筹法(1965)2、运筹学的定义:管理运筹学是一门应用科学,它广泛应用现有的科学技术和数学方法,解决管理中提出的专门问题,为决策者选择最优或较优的决策提供定量依据。运筹学是一门新兴的交叉学科,来源于军事、管理和经济。本课程主要介绍用于解决管理领域问题的运筹学,因此称为管理运筹学,也有人称为管理科学。二、运筹学解决问题的思路提出问题→建模→求解→结果分析与调整→实施运筹学的学科内容:线性规划(LP);*整数规划(IP);*非线性规划(NP);*多目标规划(MP);动态规划(DP);对策论(GT);决策分析(DA);存贮论(IC);排队论(QT);图论(GraphTheory)三、章节安排1、绪论(2学时)2、线性规划(14学时)3、动态规划(6学时)4、存储论(6学时)5、对策论(10学时)6、决策论(6学时)7、统筹方法(2学时)8、总复习(2学时)四、应用举例猴子运香蕉海盗分宝石猜生日第二章线性规划*主要内容1、线性规划的一般形式、压缩形式、矩阵形式、向量形式2、线性规划问题的图解法(3)3、线性规划问题的标准形式4、单纯形方法(4)5、线性规划问题应用举例(3)6、运输问题的解法(4)§1线性规划问题的基本模型引例【引例1】某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品需的设备台时,A、B两种原材料的消耗以及每种产品可获利润如下表所示。问应如何安排生产进度使工厂的获利最多?ⅠⅡ资源限量设备128台时原材料A4016kg原材料B0412kg单位产品利润(元)23该问题可用一句话描述:即在有限资源的情况下,求使利润最大的生产计划方案。【引例2】营养配餐问题假定一个成年人每天需要从食物中获取300cal热量,55g蛋白质,88mg钙。如果一个市场上有四种食品可供选择,它们每kg所含热量和营养成分以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食物的费用最小?序号食品名称热量(cal)蛋白质(g)钙(mg)价格(元)1猪肉100050400202鸡蛋8006020073大米9002030054白菜200105002LP问题的模型*线性规划:变量满足线性约束的条件下,求使线性目标函数值最优的问题。1、一般形式2、紧缩形式3、矩阵形式4、向量形式其中,,,。线性规划标准模型由线性规划模型的一般形式的讨论可知,线性规划模型有多种不同情况:目标函数可以是最大或最小,约束条件可以有大于等于、小于等于或等于三种情况。为便于线性规划模型的求解,可将线性规划模型的一般形式统一转化为标准形式,这里规定线性规划标准模型的条件:目标函数最小化、约束条件为等式、决策变量均非负、右端项非负。线性规划标准模型的一般表达式:化一般型为标准型:→≤→左边+松弛变量;≥→左边-剩余变量变量→;变量无限制→令→等式两边同乘以(-1).§2图解法线性规划几何解的有关概念考虑线性规划模型一般形式:可行解:凡满足约束条件和非负条件的决策变量的取值称为线性规划可行解。可行域:所有可行解的集合称为线性规划的可行域。最优解:使目标函数达到最优值的可行解称为线性规划的最优解。图解法基本步骤在明确线性规划可行解、可行域和最优解的基础上,介绍线性规划的图解法。对于两个或三个变量的线性规划问题,可以通过平面图或立体图进行求解,是线性规划问题解的几何表示。图解法的优点简单、直观,有助于理解线性规划问题求解的基本原理。它的局限性在于只能对两个或三个变量的线性规划问题求解。图解法的基本步骤可以概括如下:(1)建立平面(空间)直角坐标系。取决策变量为坐标向量,标出坐标原点、坐标轴指向及单位长度。(2)确定线性规划解可行域。根据非负条件和约束条件画出解的可行域。只有在第一象限的点才满足线性规划非负条件,将以不等式表示的每个约束条件化为等式,在坐标系第一象限作出约束直线,每条约束直线将第一象限划分为两个半平面,通过判断确定不等式所决定的半平面。所有约束直线可能形成或不能形成相交区域,若能形成相交区域,相交区域任意点所表示解称为此线性规划可行解,这些符合约束限制的点集合,称为