资源预览内容
第1页 / 共268页
第2页 / 共268页
第3页 / 共268页
第4页 / 共268页
第5页 / 共268页
第6页 / 共268页
第7页 / 共268页
第8页 / 共268页
第9页 / 共268页
第10页 / 共268页
亲,该文档总共268页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
管理运筹学管理运筹学 经济管理学院 1.期末考试成绩占70%。 2.平时成绩占30% ,包括: l点名若干次 缺席六次不能参加考试,五次40分,四次50分,三次 60分,二次70分,一次80分,0次90分 l论文一篇 l论文题目待定 成绩评定方法 第0章 绪论 0.1 什么是运筹学 0.2 运筹学简史 0.3 运筹学模型 为何学习运筹学?最有效率!最经济!最和谐! 政府需要、企业需要、家庭需要、个人成长需要。 运筹学(Operations Research)是近几十年发展起来的一门 新兴的应用性学科。其主要思想是运用数学模型方法研究各种决 策问题的优化途径及方案,为管理决策者提供科学决策的参考依 据。 管理运筹学与运筹学的含义基本一致,只不过是为突出运筹 学的管理性质而加上了“管理”二字。 0.1 什么是运筹学 l0.1.1 引言 l田忌赛马;沈括运粮 l0.1.2 名称 l0.1.3 定义 l我国的定义: l0.1.4 特点 l0.1.5 内容 l确定型;随机型;混合型;模糊型 l0.1.6 相关学科 0.2 运筹学简史 混沌时期;朦眬时期;初创时期;确立时期; 扩展时期 我国运筹学发展概况 运筹学是指通过运用科学方法研究某一系统的 最优管理和控制,或者分析研究某一系统的运行状况 ,以及系统的管理问题和生产经营活动。主要研究方 法是定量化和模型化,特别是运用各种数学模型,目 的是基于所研究的系统,力求获得一个合理运用人力 、物力、财力和各种资源的最佳方案,以使系统获得 最优目标。 1948年,美国麻省理工学院率先开设了运筹学课程; 1950年,美国出版了第一份运筹学杂志; 1951年,Morse 和 Kimball 出版了运筹学方法第一 本以运筹学为名的专著,给出了运筹学的定义:为决策 机构在对其控制下业务活动进行决策时,提供以数量化 为基础的科学方法。 运筹学在中国的发展(我国现代运筹学概况) 1. 50年代中期钱学森、华罗庚、许国志等著名学者将 Operations Research(简称OR)从西方引入我国。 2. 1956年将Operations Research直译为“运用学” 3. 1957年将Operations Research.意译为“运筹学” 是取自史记高祖本记“夫运筹帷幄之中,决胜 于千里之外,吾不如子房” 一语,摘取“运筹”二字 作为这门科学的名称,既显示其军事的起源,也表明 运筹学的哲理思想远在我国古代已经存在。 (港台称“作业研究”) 中国的第一个运筹学研究小组是在钱学森、许国 志先生的推动下于1956年在中国科学院力学研究所成 立的。其应用是在1957年始于建筑业和纺织业,从 1958年开始在交通运输、工业、农业、水利建设、邮 电等方面使用。尤其是在运输方面,从物资调运、装 卸到调度等等。 1958年,建立了专门的运筹学研究室,但由于在 应用单纯形法解决粮食合理运输问题时遇到了困难, 我国运筹学工作者于是创立了运输问题的“图上作业 法”。1959年成立国际运筹学联合会(International Federation of Operations Research Societies, IFORS),我国于1982年加入IFORS,并于1999年8月组 织了第15届大会。 0.3 运筹学模型 l0.3.1 引言 l模型:就是现实系统的简仿物或抽象表示。 l运筹学模型属于后者。 l决策变量;约束条件;目标函数 l可行解、最优解。 l0.3.2 模型建立 数学模型举例:成本、收益和利润的数 学模型(略) 运筹学的应用(略) 第第 1 1 章章 L Linearinear P Programmingrogramming L L P P 线性规划线性规划基本性质基本性质 1.1 线性规划的一般模型 1.2 线性规划的图解法 1.3 线性规划的标准形式 1.4 线性规划的解及其性质 1.5 线性规划的应用模型 第1章 线性规划的基本性质 l线性规划是运筹学的一个分支,主要用于研 究解决有限资源的最佳分配问题,即如何对 有限资源做出最佳方式的调配和最有利的使 用,以便最充分地发挥资源的效能,以获取 最佳经济效益。 lLinear Programming - LP 1.1 线性规划的一般模型 1.1.1 引 例 例1 产品配比问题(范例) 某厂拟生产甲、乙两种产品,每件利润分别为3、5百元。 甲、乙产品的部件各自在A、B两个车间分别生产,每件甲、 乙产品的部件分别需要A、B车间的生产能力1、2工时。两件 产品的部件最后都要在C车间装配,装配每件甲、乙产品分别 需要3、4工时,三车间每天可用于生产这两种产品的工时分别 为8、12、36,问应如何安排生产这两种产品才能获利最多? 1.1 线性规划的一般模型 z z x1 x2决策变量 z z = 3x1 +5x2maxmax0 目标函数 x18 2x212 3x1+4x236 函数约束 x1,x20非负性约束 s.t.s.t. 甲 乙 1 0 3 0 2 4 8 12 36 A B C 车间 产品 单耗(工时/件)最大生产能力 (工时/天) 单位利润 (百元/件) 3 5 1.1 线性规划的一般模型 例2 配料问题 某化工厂根据一项合同要为用户生产一种用甲、乙 两种原料混合配制而成的特殊产品。甲、乙两种原料都 含有A,B,C三种化学成分,其含量(%)是:甲为12, 2, 3;乙为3,3,15。按合同规定,产品中三种化学 成分的含量(%)不得低于4,2,5。甲、乙原料成本为 每千克3,2元。 厂方希望总成本达到最小,则应如何配制该产品? 1.1 线性规划的一般模型 成分含量(%) 原料 化学成分 甲 乙 产品成分 最低含量(%) A B C 12 3 2 3 3 15 4 2 5 成本(元 /千克) 3 2 x x1 1 x x2 2 minz z=3x1+2x2 12x1+3x24 2x1+3x22 s.t.3x1+15x25 x1 +x2= 1 x1,x20 配料平衡条件 z z 1.1 线性规划的一般模型 1.1. 2 线性规划的一般模型 一般LP模型的三类参数三类参数: 价值系数价值系数c c j j ,消耗系数消耗系数a a ij ij ,右端常数右端常数b b i i . LP模型的三要素三要素:决策变量决策变量,目标函数目标函数,约束条件 约束条件. s.t. opt z=c1x1+c2x2+c3x3+cnxn a11x1 +a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm xj(或)0,或自由,j=1,2,n 1.2 线性规划的图解法 1.2.1 图解法的基本步骤 X*=(4,6)T z*=42 1画出可行域图形 2画出目标函数的 等值线及其法线 3确定最优点 maxz=3x1+5x2 x1 8 2x2 12 3x1+4x2 36 x1, x20 s.t. x1 x2 O(0,0) x1= 8 A(8,0) 2x2= 12 D(0,6) 3x1 +4x2 = 36 O(0,0) x1 x2 R R D(0,6) C(4,6) B(8,3) A(8,0) z = 15 z = 30 z 法向 z* = 42 边界方程边界方程 1.2 线性规划的图解法 1.2.2 几点说明 实际运用时还须注意以下几点: (1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问 题的整个可行域R R(若存在的话)也必然在此直线上。 (2)在画目标函数等值线时只须画两条就能确定其法线方向,为此, 只须赋给 z z 两个适当的值。 (3)在找出最优点后,关于其坐标值有两种确定方法: 在图上观测最优点坐标值 通过解方程组得出最优点坐标值 1.2 线性规划的图解法 1.2.3 几种可能结果 一、唯一解 如例1、例2都只有一个 最优点,属于唯一解的情形。 s.t. max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 , x2 0 二、多重解 z = 12 z* = 36 线段BCBC上无穷多个 点均为最优解。 O(0,0) x1 x2 R R D(0,6) C(4,6) B(8,3) A(8,0) 1.2 线性规划的图解法 x1 x2 z* 三、无界解 3 6 9 4812 x1 x2 R R2 2 R R1 1 R R 2 2 = = 四、无可行解 + R R1 1 1.3 线性规划的标准形式 1.3.1线性规划问题的标准形式 maxz=c1x1+c2x2+c3x3+cnxn s.t. a11x1+a12x2+a1nxn=b1(0) a21x1+a22x2+a2nxn=b2(0) am1x1+am2x2+amnxn=bm(0) x1,x2 , , xn0 简记为: maxz=cjxj j=1 n s.t. aijx j =bi, i=1, 2, , m j=1 n xj0,j=1, 2, , n maxz=CTX s.t. AX=b X0 (M1): (M2):(M3): (M) 1.3 线性规划的标准形式 1.3.2 非标准形LP问题的标准化 一、目标函数 min z = CTX 令 z= z max z= CTX 例:min z = 3x1 2x2 max z= 3x1 2x2 二、函数约束 bi0 两边同时乘以 -1 约束为形式 加上松弛变量 约束为形式 减去剩余变量 三、决策变量 若xk 0, 令 xk = xk,则 xk 0 若xk为自由变量, 令 xk = xk xk且 xk,xk 0 x x* f (x) - f (x) 1.3 线性规划的标准形式 z z = 3x1+5x2max x18 2x212 3x1+4x236 x1,x20 s.t. x1+x3 =8 2x2+x4=12 3x1 +4x2+x5=36 x1 ,x2 ,x3,x4,x50 s.t. z z = 3x1+5x2max 范例范例 +0 0 x3+0 0 x4+0 0 x5 1.3 线性规划的标准形式 minz=x1 2x2 3x3 x1 2x2x35 2x1 3x2x36 x1 x2 x3 2 x10,x30 s.t. 解:maxz= x1 2x23x3 s.t. x1 2x2x3+x4=5 2x1 3x2x3-x5=6 x1 x2 x3+x6= 2 x1,x4,x5,x60,x30 例4 将下述LP问题化成标准形 1.3 线性规划的标准形式 令x2=x2 x x2 2 ,且x2,x x 2 2 0 x3= - x x3 3 代入上式中,得 maxz= x1 2x2+2 x x2 2 3x x 3 3 x1 +2x22x x 2 2 +x x 3 3 +x4=5 2x1+3x23x x 2 2 +x x 3 3 x5= 6 x1+x2 x x2 2 +x x 3 3 +x6=2 x1,x2, x x2 2 ,x x 3 3 ,x4,x5,x60 s.t. 1.4 线性规划的解及其性质 1.4.1 线性规划的解的概念 一、可行解: 满足LP问题所有约束条件的X。 二、最优解: 满足目标要求的可行解X。 三、基本解: 只适用于标准形LP问题(M)。 (1) 基(矩阵) AX = b 设B B为A的一个m阶子矩阵,若|B B|0,则称B B 为约束方程组AX=b或标准形LP问题(M)的一个 基(矩阵)。 1.4 线性规划的解及其性质 范范 例例 A = 10100 02010 34001 x1x2x3x4x5 a1 a2 a3 a4 a5 可取B0=(a3,a4,a5)为基(|B0|0),这时 称 a3,a4,a5为基向量,而a1,a2为非基向量;称 x3,x4,x5为基变量,而x1,x2为非基变量。 1.4 线性规划的解及其性质 (2) 基本解 范例范例的标准形 maxz=3x1+5x2 s.t. x1+x3=8 2x2+x4=12 3x1+4x2+x5=36 x1 , x2,x3,x
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号