管理运筹学--课件

管理运筹学主讲教师:黄毅博士Tel:13787022506经济管理学院1.期末考试成绩占70%。2.平时成绩占30%，包括：点名若干次缺席六次不能参加考试，五次40分，四次50分，三次60分，二次70分，一次80分，0次90分论文一篇论文题目——待定成绩评定方法第0章绪论0.1什么是运筹学0.2运筹学简史0.3运筹学模型为何学习运筹学？最有效率！最经济！最和谐！政府需要、企业需要、家庭需要、个人成长需要。运筹学（OperationsResearch）是近几十年发展起来的一门新兴的应用性学科。其主要思想是运用数学模型方法研究各种决策问题的优化途径及方案，为管理决策者提供科学决策的参考依据。管理运筹学与运筹学的含义基本一致，只不过是为突出运筹学的管理性质而加上了“管理”二字。0.1什么是运筹学0.1.1引言田忌赛马；沈括运粮0.1.2名称0.1.3定义我国的定义：0.1.4特点0.1.5内容确定型；随机型；混合型；模糊型0.1.6相关学科0.2运筹学简史混沌时期；朦眬时期；初创时期；确立时期；扩展时期我国运筹学发展概况运筹学是指通过运用科学方法研究某一系统的最优管理和控制，或者分析研究某一系统的运行状况，以及系统的管理问题和生产经营活动。主要研究方法是定量化和模型化，特别是运用各种数学模型，目的是基于所研究的系统，力求获得一个合理运用人力、物力、财力和各种资源的最佳方案，以使系统获得最优目标。1948年，美国麻省理工学院率先开设了运筹学课程；1950年，美国出版了第一份运筹学杂志；1951年，Morse和Kimball出版了《运筹学方法》第一本以运筹学为名的专著，给出了运筹学的定义：为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。运筹学在中国的发展（我国现代运筹学概况）1.50年代中期钱学森、华罗庚、许国志等著名学者将OperationsResearch（简称OR）从西方引入我国。2.1956年将OperationsResearch直译为“运用学”3.1957年将OperationsResearch.意译为“运筹学”是取自《史记·高祖本记》“夫运筹帷幄之中，决胜于千里之外，吾不如子房”一语，摘取“运筹”二字作为这门科学的名称，既显示其军事的起源，也表明运筹学的哲理思想远在我国古代已经存在。(港台称“作业研究”）中国的第一个运筹学研究小组是在钱学森、许国志先生的推动下于1956年在中国科学院力学研究所成立的。其应用是在1957年始于建筑业和纺织业，从1958年开始在交通运输、工业、农业、水利建设、邮电等方面使用。尤其是在运输方面，从物资调运、装卸到调度等等。1958年，建立了专门的运筹学研究室，但由于在应用单纯形法解决粮食合理运输问题时遇到了困难，我国运筹学工作者于是创立了运输问题的“图上作业法”。1959年成立国际运筹学联合会(InternationalFederationofOperationsResearchSocieties，IFORS)，我国于1982年加入IFORS，并于1999年8月组织了第15届大会。0.3运筹学模型0.3.1引言模型：就是现实系统的简仿物或抽象表示。运筹学模型属于后者。决策变量；约束条件；目标函数可行解、最优解。0.3.2模型建立数学模型举例：成本、收益和利润的数学模型（略）运筹学的应用（略）第1章LinearProgrammingLP线性规划基本性质1.1线性规划的一般模型1.2线性规划的图解法1.3线性规划的标准形式1.4线性规划的解及其性质1.5线性规划的应用模型第1章线性规划的基本性质线性规划是运筹学的一个分支，主要用于研究解决有限资源的最佳分配问题，即如何对有限资源做出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能，以获取最佳经济效益。LinearProgramming---LP1.1线性规划的一般模型1.1.1引例例1产品配比问题（范例）某厂拟生产甲、乙两种产品，每件利润分别为3、5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1、2工时。两件产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3、4工时，三车间每天可用于生产这两种产品的工时分别为8、12、36，问应如何安排生产这两种产品才能获利最多？1.1线性规划的一般模型zx1x2决策变量z=3x1+5x2max0目标函数x1≤8①2x2≤12②3x1+4x2≤36③函数约束x1，x2≥0④非负性约束s.t.甲乙10302481236ABC车间产品单耗（工时/件）最大生产能力（工时/天）单位利润（百元/件）351.1线性规划的一般模型例2配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A，B，C三种化学成分，其含量(%)是:甲为12，2，3；乙为3，3，15。按合同规定，产品中三种化学成分的含量(%)不得低于4，2，5。甲、乙原料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配制该产品？1.1线性规划的一般模型成分含量(%)原料化学成分甲乙产品成分最低含量(%)ABC12323315425成本（元/千克）32x1x2minz=3x1+2x212x1+3x2≥42x1+3x2≥2s.t.3x1+15x2≥5x1+x2=1x1,x2≥0配料平衡条件z1.1线性规划的一般模型1.1.2线性规划的一般模型一般LP模型的三类参数：价值系数cj，消耗系数aij，右端常数bi.LP模型的三要素：决策变量，目标函数，约束条件.s.t.optz=c1x1+c2x2+c3x3+…+cnxna11x1+a12x2+…+a1nxnb1a21x1+a22x2+…+a2nxnb2…am1x1+am2x2+…+amnxnbmxj≥(或≤)0,或自由,j=1,2,…,n1.2线性规划的图解法1.2.1图解法的基本步骤X*=(4,6)Tz*=421°画出可行域图形2°画出目标函数的等值线及其法线3°确定最优点maxz=3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z法向z*=42边界方程1.2线性规划的图解法1.2.2几点说明实际运用时还须注意以下几点:(1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,只须赋给z两个适当的值。(3)在找出最优点后,关于其坐标值有两种确定方法:①在图上观测最优点坐标值②通过解方程组得出最优点坐标值1.2线性规划的图解法1.2.3几种可能结果一、唯一解如例1、例2都只有一个最优点，属于唯一解的情形。s.t.maxz=3x1+4x2x1≤82x2≤123x1+4x2≤36x1，x2≥0二、多重解z=12z*=36线段BC上无穷多个点均为最优解。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)1.2线性规划的图解法x1x2z*三、无界解3694812x1x2R2R1∩R2=Ø四、无可行解+∞R11.3线性规划的标准形式1.3.1线性规划问题的标准形式maxz=c1x1+c2x2+c3x3+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1(≥0)a21x1+a22x2+…+a2nxn=b2(≥0)………am1x1+am2x2+…+amnxn=bm(≥0)x1,x2,…,xn≥0简记为：maxz=∑cjxjj=1ns.t.∑aijxj=bi,i=1,2,…,mj=1nxj≥0,j=1,2,…,nmaxz=CTXs.t.AX=bX≥0(M1):(M2):(M3):(M)1.3线性规划的标准形式1.3.2非标准形LP问题的标准化一、目标函数minz=CTX令z′=－zmaxz′=－CTX例：minz=3x1＋2x2maxz′=－3x1－2x2二、函数约束⑴bi0两边同时乘以-1⑵约束为≤形式加上松弛变量⑶约束为≥形式减去剩余变量三、决策变量若xk≤0,令xk=－xk′,则xk′≥0若xk为自由变量,令xk=xk′－xk〞且xk′,xk〞≥0•xx*f(x)-f(x)1.3线性规划的标准形式z=3x1+5x2maxx1≤82x2≤123x1+4x2≤36x1，x2≥0s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1，x2，x3，x4，x5≥0s.t.z=3x1+5x2max范例+0x3+0x4+0x51.3线性规划的标准形式minz=x1＋2x2－3x3x1＋2x2－x3≤52x1＋3x2－x3≥6－x1－x2＋x3≥－2x1≥0,x3≤0s.t.解:maxz′=－x1－2x2＋3x3s.t.x1＋2x2－x3+x4=52x1＋3x2－x3-x5=6x1＋x2－x3+x6=2x1,x4,x5,x6≥0,x3≤0例4将下述LP问题化成标准形1.3线性规划的标准形式令x2=x2′－x2〞，且x2′，x2〞≥0x3=-x3′代入上式中，得maxz′=－x1－2x2′+2x2〞－3x3′x1+2x2′－2x2〞+x3′+x4=52x1+3x2′－3x2〞+x3′－x5=6x1+x2′－x2〞+x3′+x6=2x1,x2′,x2〞,x3′,x4,x5,x6≥0s.t.1.4线性规划的解及其性质1.4.1线性规划的解的概念一、可行解:满足LP问题所有约束条件的X。二、最优解:满足目标要求的可行解X。三、基本解:只适用于标准形LP问题（M）。(1)基(矩阵)AX=b设B为A的一个m阶子矩阵，若|B|≠0,则称B为约束方程组AX=b或标准形LP问题(M)的一个基（矩阵）。1.4线性规划的解及其性质范例A=101000201034001x1x2x3x4x5a1a2a3a4a5可取B0=（a3,a4,a5）为基（|B0|≠0）,这时称a3,a4,a5为基向量，而a1,a2为非基向量；称x3,x4,x5为基变量，而x1,x2为非基变量。1.4线性规划的解及其性质(2)基本解范例的标准形maxz=3x1+5x2s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0取B0=（a3,a4,a5）为基，令一切非基变量x1=x2=0,可解得基变量x3=8，x4=12，x5=36则得一特解X0=(0，0，8，12，36)T称为一个(关于B0为基的)基本解。1.4线性规划的解及其性质也可取B1=(a2,a3,a4)为基,得X1=(0，9，8，-6，0)T还可取B2=(a1,a2,a3)为基,得X2=(4，6，4，0，0)T等等。四、基本可行解满足非负性约束的基本解。如X0，X2；而X1不可行。对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为0，则称其为一个退化的基本(可行)解，否则为非退化的。如设：X=(0，6，5，0，0)T是一个基本可行解，其中x5=0为基变量，则该X为退化的基本可行解。1.4线性规划的解及其性质非退化的基本(可行)解，并恰有n–m个0分量。基本可行解对应的基，称为可行基；最优基本解对应的基，称为最优基。如：基B0=(a2,a3,a4)对应X0=(0，0，8，12，36)T可行基B1=(a2,a3,a4)对应X1=(0，9，8，-6，0)T不可行基B2=(a1,a2,a3)对应X2=(4，6，4，0，0)T恰有m个非0分量，为可行基为非可行基为最优基x*x*B*1.4线性规划的解及其性质1.4.2凸性的几个基本概念一、凸集设SEn，对任意两点X∈S，Y∈S，若对满足0≤μ≤1的一切实数μ，都有μX+(1-μ)Y∈S则称S为凸集。XYXY凸集凸集非凸集非表示S中两点X，Y连线上的任一点凸集的几何意义：凸集S中任意两点X，Y连线