广工管理运筹学运筹学-绪论及第2章.ppt

广东工业大学管理学院,1,运筹学,钟映竑 广东工业大学管理学院,2,绪论,什么是运筹学 运筹学研究的基本特征和基本方法 运筹学的主要分支 运筹学与管理科学,广东工业大学管理学院,3,什么是运筹学（不同的定义）,大英百科全书 中国大百科全书 辞海 中国企业管理百科全书,广东工业大学管理学院,4,大英百科全书的定义,运筹学是一门应用于管理有组织系统的科学。 运筹学为掌管这类系统的人提供决策目标和数量分析的工具。,广东工业大学管理学院,5,中国大百科全书的定义,运筹学用数学方法研究经济、民政和国防等部门在内外的约束条件下合理分配人力、物力、财力等资源，是实际系统有效运行的技术科学，它可以用来预测发展趋势，制订行动规划或优选可行方案。,广东工业大学管理学院,6,辞海的定义,运筹学主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到经济有效地使用人力物力。,广东工业大学管理学院,7,中国企业管理百科全书的定义,运筹学应用分析、实验、量化的方法，对经济管理系统中人财物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,广东工业大学管理学院,8,英国Operational research 美国Operations research 夫运筹帷幄之中，决胜千里之外。史记 齐王赛马 丁渭修宫 二战时英国的防空雷达系统,广东工业大学管理学院,9,运筹学的发展大致可分三个阶段: 运筹学诞生的三个来源：军事、管理和经济 1945-1950年代,创建时期; 1950年代,成长时期; 1960年代至今,普及和发展时期.,广东工业大学管理学院,10,运筹学的基本特征,系统的整体观念 多学科的综合 应用模型技术,广东工业大学管理学院,11,运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 通常以最优、最佳等作为决策目标，避开最劣的方案。,广东工业大学管理学院,12,运筹学的基本方法 模型化的方法,应用步骤： 分析与表述问题 建立模型 求解模型与优化方案 测试模型及对模型进行必要的修正 建立对解的有效控制 方案的实施,广东工业大学管理学院,13,决策过程（问题解决的过程）： 1）认清问题； 2）找出一些可供选择的方案； 3）确定目标或评估方案的标准； 4）评估各个方案：解的检验、灵敏性分析等； 5）选出一个最优的方案：决策； 6）执行此方案：回到实践中； 7）进行后评估：考察问题是否得到完满解决； 1）2）3）：形成问题； 4）5）：分析问题：定性分析与定量分析。构成决策。,广东工业大学管理学院,14,运筹学的主要分支,线性规划(linear programming) 非线性规划(nonlinear programming) 动态规划(dynamic programming) 图与网络分析(graph theory and network analysis) 存贮论(inventory theory) 排队论(queueing theory) 对策论(game theory) 决策论(decision theory),广东工业大学管理学院,15,第四节 运筹学与管理科学,国际上目前通行的说法：“运筹学”与“管理科学(management sciences )”在许多场合实际是指同一学科，不过前者强调方法而后者强调应用。 因此运筹学是现代科学管理的基础，从而在管理中有非常广泛的应用。,广东工业大学管理学院,16,生产计划：生产作业的计划、日程表的编排、合理下料、 配料问题、物料管理等，追求利润最大化和成本最小化 库存管理：多种物资库存量的管理，库存方式、库存量等 运输问题：确定最小成本的运输线路、物资的调拨、运输 工具的调度以及建厂地址的选择等 人事管理：对人员的需求和使用的预测，确定人员编制、 人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与销售 计划制定等 财务和会计：预测、贷款、成本分析、定价、证券管理、 现金管理等 * 设备维修、更新，项目选择、评价，工程优化设计与管理等,广东工业大学管理学院,17,运筹学方法使用情况(美1983),广东工业大学管理学院,18,运筹学方法在中国使用情况 (随机抽样),广东工业大学管理学院,19,运筹学在国内或国外的推广应用前景是非常广阔的。 工商企业对运筹学应用的需求是很大的。 在工商企业推广运筹学方面有大量的工作要做。,广东工业大学管理学院,20,由国际运筹与管理科学协会（INFORMS）和它的管理科学实践学会（College for the Practice of the Management Sciences）主持评奖的负有盛名的弗兰茨厄德曼（Frany Edlman）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入围者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物Interface的第一期上，下面列表就是发表在Interface期刊的一些获奖项目。,广东工业大学管理学院,21,广东工业大学管理学院,22,第二章 线性规划,线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论 应用举例,广东工业大学管理学院,23,第一节 线性规划及其数学模型,问题的提出 线性规划的数学模型 线性规划的标准形式,广东工业大学管理学院,24,例1,美佳公司计划制造I、II两种家电产品，已知各制造一件分别占用的设备A、B的台时、调试时间、调试工序每天可用于这两种家电的能力、各售出一件的获利情况如下表所示。,问该公司应每天制造两种家电各多少件，使获取的利润最大。,广东工业大学管理学院,25,例2 捷运公司租借仓库的问题,捷运公司在下一年度的1-4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积如下表所示。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租期不同的合同。试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,广东工业大学管理学院,26,广东工业大学管理学院,27,例1、例2的共同点,在现有各项资源条件的限制或约束下，如何确定方案，使预期目标达到最优。,例1的资源限制：设备A、B与调试工序每天可用时数。目标：总利润最大,例2的资源约束：租期内每月所需的仓库面积数。目标：总租金最小,广东工业大学管理学院,28,线性规划研究的问题大体上可归为两类： 1、给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务； 2、对于给定的任务，如何运筹规划，合理安排，以最少资源来完成它。,广东工业大学管理学院,29,线性规划要研究的两类问题中都包含有限制或约束条件：第一类问题的约束条件是“给出一定量的人力、物力和财务等资源”；第二类问题是“给定的任务”。在线性规划中，我们常要求这种约束条件可以用一组线性方程或线性不等式来描述。在约束满足的条件下，所要达到的结果称“目标”，第一类问题的目标是利用有限资源完成最大任务，第二类问题的目标是要用最少资源完成给定任务。在线性规划中，要求可以用一个线性函数来描述这种目标，并称这个线性函数为目标函数。 线性规划研究的各种实际问题尽管约束条件与目标不相同，但规划的目的就是使这些资源发挥最大限度的作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用数学的方式描述，规划的目的就是在给定的限制条件（或称约束条件）下，求目标函数的极值问题（包括极小值和极大值）。,广东工业大学管理学院,30,模型数学规划问题,广东工业大学管理学院,31,例1的数学模型,广东工业大学管理学院,32,广东工业大学管理学院,33,例2的数学模型,广东工业大学管理学院,34,例1 穗羊公司要加工两种产品I、II，需要使用两种原材料及某专用生产设备等三种资源，分别记为A、B、C。生产这两种产品的单位资源消耗、这些资源的每周可使用量及每单位产品可获利润见下表：,问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？,广东工业大学管理学院,35,根据问题所给数据，当产品I、II每周的产量分别是x1和x2时，总利润为,因此我们的目标就是,再考虑资源的限制:因此关于A原材料，我们有约束条件：,关于B原材料，有约束条件：,关于设备，有约束条件：,此外产品I和II每周的产量不可能是负数，因此关于这两个变量，还有约束：,广东工业大学管理学院,36,将上述数学表达式合起来，就得到这个问题的数学模型为：,其中s.t.是英文词组subject to的缩写，表示“受限制于”的意思，有时也约去不写出来。,例1中的问题常称为生产计划问题或产品组合（product mix）问题。,广东工业大学管理学院,37,例2 设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料。,因为，10米长的钢筋截为3米或4米长，共有三种截法： 截法：3 3 3 1 米 截法：3 3 4 0 米 截法：4 4 0 2 米 假设按截法，各截取10米长的钢筋分别为x1, x2, x3根,则可以获得3米长的短钢筋的根数是,4米长短钢筋的根数是,按问题要求它们应该不小于100根。,总共用料是,要达到最省料的目的，就必须使总用料最小。,广东工业大学管理学院,38,例2的模型就是,例2 中的问题常称为下料问题。,广东工业大学管理学院,39,模型的特征,模型的三个要素 （1）决策变量 （2）目标函数 （3）约束条件 线性规划模型的特征 （1）目标函数是决策变量的线性函数 （2）约束条件是含决策变量的线性等式或不等式,广东工业大学管理学院,40,线性规划模型的一般形式,广东工业大学管理学院,41,线性规划模型的一般形式（续1）,决策变量： 价值系数： 资源常数： 技术（工艺）系数：,广东工业大学管理学院,42,线性规划模型的一般形式（续2）,利用和号简化模型的表示,广东工业大学管理学院,43,线性规划模型的一般形式（续3）,向量形式：,式中,广东工业大学管理学院,44,线性规划模型的一般形式（续4）,矩阵形式：,其中,广东工业大学管理学院,45,线性规划模型的一般形式（续5）,注：决策变量通常是非负的，但从数学意义上决策变量可以取非正的值，或取任何实数。,广东工业大学管理学院,46,线性规划问题的（模型）的标准形式,广东工业大学管理学院,47,标准形式的特征,目标函数为求最大值 约束条件均为等式 资源常数非负 决策变量只能取非负值,不具备上述所有特征的线性规划问题称为非标准形式的线性规划问题,广东工业大学管理学院,48,化线性规划问题为标准形式的方法,（1）目标函数为求最小值的，即,将目标函数用其相反数代替，得到新的目标函数，即令 则求原目标函数的最小值问题等价于求新目标函数的最大值问题,广东工业大学管理学院,49,化线性规划问题为标准形式的方法（续1）,（2）右端常数小于零，即 将该约束条件两端同乘（-1）,（3）约束条件为不等式 “ ”型，左端加上一个非负的松弛变量 “ ”型，左端减去一个非负的剩余变量,松弛变量和剩余变量在目标函数中的系数为零,广东工业大学管理学院,50,化线性规划问题为标准形式的方法（续2）,（4）取值无约束的变量。用两个非负变量的差表示该变量。,（5）取非正值的变量。用其相反数代替该变量,P15 例3,广东工业大学管理学院,51,线性规划问题,要处理的内容,x1, x3,右端常数,不等式,不等式,最小化目标,处理后,广东工业大学管理学院,52,第二节 图解法,有关概念 满足所有约束条件的一组决策变量x1, x2, , xn称为LP问题的可行解 所有可行解的集合称为可行域 使得目标函数值达到最大的可行解称为LP问题的最优解（对最大化问题而言） 求解LP问题就是求出其最优解,广东工业大学管理学院,53,图解法及其目的,图解法即通过平面作图的方法求解线性规划，适用于只含两个决策变量的简单LP问题。 图解法的目的有二，一是利用它来说明LP问题求解的可能结局。二是在LP问题最优解存在时，求出最优解。,采用图解法时通常无须将LP问题化为标准形式,广东工业大学管理学院,54,图解法步骤：,在平面上建立直角坐标系,图示约束条件，找出可行域,图示目标函数,寻找最优解,广东工业大学管理学院,55,例1,Max z=2x1+x2 s.t. 5x215 6x1+2x2 24 x1+x2 5 x1,x20,x2=3,3x1+x2 =12,x1+x2 =5,最优解,可行域,x1,x2,广东工业大学管理学院,56,线性规划问题几种可能的结局,有唯一的最优解 有无穷多个最优解 无界解,4. 无解（无可行解）,广东工业大学管理学院,57,由图解法得到的启示,揭示了求LP问题的解的可能情况 若可行域非空，则必为凸集 若LP问题的最优解存在，则最优解或最优解之一是可行域的顶点 LP问题的求解思路（单纯形法）,先找出可行域的任一顶点，计算该顶点处的目标函数值；比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点为最优解（或最优解之一）对应的点，否则转到比这个点目标函数值更大的顶点，重复上述过程，直到找出目标函数值最大的顶点为止。,广东工业大学管理学院,58,第三节 单纯形法原理,线性规划解的基本概念,考虑标准形式的线性规划问题 可行解满足所有约束条件的解X=(x1,x2,xn)T,称为LP问题的可行解。所有可行解的集合称为可行域。,最优解使得目标函数达到最大值的可行解称为最优解。,LP问题的可行域是一个凸集。,广东工业大学管理学院,59,基设A为约束方程组的mn阶系数矩阵（通常总假定nm，且A的秩=m），若B是A的一个mm阶的满秩子矩阵，则称B是LP问题的一个基。若B是LP问题的一个基，则它的每一个列向量称为基向量，与基向量对应的变量称为基变量,LP问题的基本概念（续1）,广东工业大学管理学院,60,秩的概念,如果矩阵A中有一个r阶子式Dr不等于零，而所有r+1阶子式（如果存在的话）的值全等于零，则称Dr为矩阵A的一个最高阶非零子式，其阶数r称为矩阵A的秩。 注： Dr为行列式r的值。,广东工业大学管理学院,61,LP问题的基本概念（续2）,基解 在约束方程组 中令所有的非基变量xm+1=xm+2=xn=0,则由于剩下的变量（基变量）构成的方程组的系数行列式|B|0，因此约束方程组此时有唯一的解XB=（x1, x2, , xm, 0, , 0)T这个解称为LP问题的（对应基B的）基解。,很明显，对应着不同的基，LP问题有不同的基解。因此LP问题的基解不是唯一的，但总数不超过 此外基解不一定是可行解 。,广东工业大学管理学院,62,LP问题的基本概念（续3）,基可行解满足非负约束条件的基解称为基可行解,可行基对应着基可行解的基称为可行基,很明显LP问题的基可行解是有限的。并且每一个基可行解对应着可行域的一个顶点。,广东工业大学管理学院,63,找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。,广东工业大学管理学院,64,广东工业大学管理学院,65,凸集及其顶点,凸集如果一个非空集合中任意两点的连线段上所有点仍属于该集合，则称该集合为凸集。 凸集的顶点若凸集中的一个点不是任何另外两点连线段上的点，则称该点为这个凸集的顶点。,不是凸集,顶点,广东工业大学管理学院,66,几个基本定理,定理1 若LP问题存在可行解，则问题的可行域为凸集,定理2 LP问题的基可行解对应着LP问题可行域的顶点,定理3 若LP问题有最优解，一定存在一个基可行解是最优解,广东工业大学管理学院,67,单纯形法迭代原理,单纯形法迭代步骤：,（依据：LP问题的最优解若存在，则一定有一个基可行解为最优解。）,广东工业大学管理学院,68,1.求初始基可行解,广东工业大学管理学院,69,求基可行解需要考虑的问题,是否便于计算目标函数值 是否便于判断其目标函数值是否为最大 是否便于转换到目标函数值更大的相邻基可行解,广东工业大学管理学院,70,初始基可行解,通常都是从一种特殊的基可行解出发求解LP问题，这一特殊的基可行解称为初始基可行解。初始基可行解对应的基，也称初始可行基，它具有特定的形式，它是单位矩阵或者由单位矩阵经过交换列以后得到的矩阵。相应的基变量称为初始基变量，它是一组变量，具有特点：共有m个变量，恰好每个约束方程包含一个变量，且该变量的系数为1。,广东工业大学管理学院,71,已知初始基变量，求初始基可行解,以例1为例说明求法。添加松弛变量后例1可标准化为,其中x3, x4, x5为初始基变量，初始基可行解为,广东工业大学管理学院,72,2.判别最优性,不难发现这时每个初始基变量取的值恰好就是包含这个变量的约束方程的右端常数值，非基变量取的值为零。将这个解代入到目标函数，就可得到这个解对应的目标函数值。,目标函数目前的值为零，很明显如果能使的变量x1或x2取正值的话，目标函数的值还可以增加。所以目标函数还未达到其最大值。 一般地，若目标函数已经表示成了非基变量的函数，且其中非基变量的系数中还有正数，则目标函数还可能增大。这时目标函数中各变量的系数称为检验数。,这时目标函数的表达式为,广东工业大学管理学院,73,3.旋转,若基可行解不是最优解，则需要转到一个相邻的基可行解，并使得目标函数值增加。,所谓相邻的基可行解是指两个基可行解只有一个基变量不同而其它的基变量都相同。,要从一个基可行解转到与它相邻的基可行解，意味着需要将一个非基变量变成基变量，而且将一个原来的基变量变为非基变量，前者称为换入变量，后者称为换出变量。,广东工业大学管理学院,74,确定换入变量,目的：新的基变量换入后，会使目标函数值增大（通常还希望增加的越大越好）,因此选择在目标函数中系数为正值的非基变量作为换入变量，通常取在目标函数中最大的正系数对应的非基变量为换入变量，即取最大的正检验数对应的非基变量为换入变量。,换入变量为 x1,对例1，这时目标函数为,广东工业大学管理学院,75,确定换出变量,由于基变量只有m个，因此将一个非基变量变为基变量后，必须将一个原来的基变量变为非基变量，这个变量就是所谓的换出变量。 换出变量与换入变量是密切相关的。设xk是换入变量。若xk0，则第i个约束条件可以写成,并且由于其余的非基变量保持零值，因此,广东工业大学管理学院,76,由此可见为保证xi0，就必须 从而对所有的i，若aik0，则,广东工业大学管理学院,77,若确定xk为换入变量，则可估计xk的取值，使得：其余的决策变量都取非负值；并且目标函数得到尽可能的增加。对前者，只须 对所有的i成立，即,为了使目标函数尽可能增加，显然应该有,广东工业大学管理学院,78,这意味着xl可以是非基变量。因此取xl为换出变量。也就是取使得,成立的l 对应的基变量xl为换出变量。,对例1 由于已经确定了x1是换入变量。而,因此x4是换出变量,24/6 5/1,广东工业大学管理学院,79,确定换出变量等价于确定了一组新的基变量，为了方便地求出相应的基解，接下来将进行如下的运算：将这组新的基变量的系数矩阵化为单位矩阵（或单位矩阵交换列后得到的矩阵），这等价于使得这组基变量中每个变量只出现在一个方程中并且在该方程中的系数为1，这称为旋转运算。,旋转运算可以利用对约束方程组进行加减消元法完成。,广东工业大学管理学院,80,对例1的约束方程组,第2式6,第3式 第2式,广东工业大学管理学院,81,由此可以立即得到新的基解为,很明显，它是基可行解。为了判断这一新的基可行解是否为最优解，需要将原目标函数改写为新的非基变量的函数。原目标函数为,但是,代入目标函数，得,广东工业大学管理学院,82,即,其中系数1/3，-1/6分别是非基变量x2，x4的检验数。,因此对应于这一新的基可行解，目标函数值为z = 8。问题是这一目标函数值是否为最优的目标函数值。,由于x2的系数（检验数）为1/3，是正数，因此如果能使x2取正数，则目标函数还能增加。因此该基可行解仍不是最优解。,一般地，对一个基可行解而言，若非基变量的检验数中存在正数，则该解不是最优解；否则它一定是最优解。,广东工业大学管理学院,83,单纯形法求解过程小结,（1）求出初始基可行解,（2）通过非基变量在目标函数中的系数（检验数）是否都小于或等于零，判别该基可行解是否为最优解。若是，结束运算；否则进行下一步。,（3）确定换入变量。取最大的正检验数对应的变量为换入变量。,（4）确定换出变量。用换入变量在各方程中的正的系数去除该方程的右端常数，在除得的商中取最小者，该最小商所在方程中的基变量就是换出变量。由此得到一组新的基变量。,（5）旋转运算。将新的基变量在约束方程中的系数矩阵化为单位矩阵（或单位矩阵交换列后的矩阵）。回到第（2）步。,广东工业大学管理学院,84,单纯形表的方法,单纯形法的所有运算实际上都可归结为对LP模型的目标函数系数以及约束方程组的系数（矩阵）的运算。为了简化运算过程，并使运算过程程序化。人们构造了单纯形表来进行运算,广东工业大学管理学院,85,Xb,0 0 0,Cb,初始单纯形表,例1 中的模型化为标准形式后为,j,广东工业大学管理学院,86,基变量,目标函数系数,右端常数,基变量在目标函数中的系数,约束方程组系数矩阵,检验数,基可行解：,目标函数值为：z = 0,这个基可行解不是最优解,广东工业大学管理学院,87,换入变量,24/6 5/1,换出变量,主元,旋转运算的目的：通过矩阵的初等行变换，使主元变为1，主元列的其他数变为0。变换后为,0,1/3,0,-1/3,0,广东工业大学管理学院,88,0,1/3,0,-1/3,0,基可行解为：,目标函数值为：z=8,15/5 4/(1/3) 1/(2/3),0,0,0,-1/4,-1/2,广东工业大学管理学院,89,0,0,0,-1/4,-1/2,最优解为：,最优目标函数值为：z=8.5,8 ,因此对例1中的问题，最优的生产计划安排是每天生产甲家电3.5件，乙家电1.5件，每天可以得到的最大利润为8.5元。（按此计划安排生产，每天设备A可富余7.5台时）,广东工业大学管理学院,90,初始单纯形表,最终单纯形表,单纯形表合并的表示,广东工业大学管理学院,91,无穷多个最优解,检验数的实际意义：检验数是非基变量每增加一个单位，目标函数的增加值。,因此如果在最终单纯形表中，当所有的检验数都小于或等于零，并且存在非基变量的检验数等于零的情况时，LP问题存在无穷多个最优解。,实际上，此时可选择检验数为零的非基变量为换入变量，迭代到一个新的基可行解，它的目标函数值等于最优解的目标函数值，从而也是最优解。因此有无穷多个最优解。,广东工业大学管理学院,92,无界解,若换入变量（或正检验数）所在列的所有系数都小于或等于零，则LP问题为无界解。例如，如果单纯形表为,则目标函数无界。,广东工业大学管理学院,93,实际上换入变量为x1，相应的约束方程组为,由于x2仍是非基变量，因此,由此可见，不管x1取什么样的正数，x3、x4、x5都保持非负，这意味着x1的取值没有任何限制，从而目标函数值可以无限增加。,广东工业大学管理学院,94,最小化的线性规划问题,在关于LP问题模型的标准形式中，关于目标函数的要求可以降低，即不必要求目标函数是求最大值，而可以是求最小值。,对最小化的LP问题，单纯形法求解过程有 两处值得注意的修改。,1. 最优解的判别：当所有检验数大于或等于0时，单纯形表给出的解是最优解,2. 换入变量的确定：最小的负检验数对应的变量为换入变量,广东工业大学管理学院,95,例 求解如下的最小化LP问题,广东工业大学管理学院,96,广东工业大学管理学院,97,单纯形法的进一步讨论,如果约束方程不存在前面所述的初始基变量，处理的方式是通过添加人工变量来得到所需要的初始基变量。,添加人工变量的方法是，先化约束条件为标准形式。然后在不含初始基变量的方程的左边人为地加上一个非负变量（人工变量），作为该方程的初始基变量，不同的方程添加的人工变量也不同。,原来的条件分别为“”,“”和“”型，加人工变量的方法,广东工业大学管理学院,98,人工变量的处理,人工变量是由于应用单纯形法求解的需要人为添加的变量，因此在最终单纯形表的基变量中不应包含人工变量。因此人工变量应该逐个从基变量中换出来。,为了使人工变量能从基变量中逐个换出，可采用如下两种方法：大M法和两阶段