运筹学讲义.doc

运筹学 物流管理专业第一章 绪论一 运筹学的发展历史 1学科起源：二战期间英美等国军事部门集中多学科人员，研究提高武器系统效能，如反空袭雷达控制系统，使雷达和高炮相配合。诺将物理学家布莱克特（Blackett）领导研究小组“Operational Research”，多学科构成（布莱克特马戏团）。战争结束后专家转移到企业和院校学科形成。 2我国古代的运筹思想：齐王赛马齐王“上中下”，田忌“下上中”丁渭修皇宫北宋真宗宰相丁渭（澶chan州之盟的主和派），主持皇宫失火后的修复。宫前大街取土、引汴河运料、完工后回填废土。3我国近代以来：50年代开始钱学森、许志国等引进运筹学理论，华罗庚教授回国后从事优选法和统筹法研究推广（烧茶壶的故事）4翻译：来自汉高祖“夫运筹帷幄之中,决胜千里之外,吾不如子房;填国家,抚百姓,给饷馈,不绝粮道,吾不如萧何;连百万之众,战必胜,攻必取,吾不如韩信。”台湾地区直译为“运作研究”。二 运筹学的特点运筹学存在多种定义，如“依照给定目标和条件，从众多方案中选择最优方案的最优化技术”，学科特点：最优化、定量化1 多种专家的协作2 科学的方法：从实际情况出发，通过假设的模型打到一个符合实际的结论3 目的在于解决实际问题。4 需要系统的信息资料5 需要建立模型运筹学的核心问题就是通过合适的模型分析系统的未来情况6 对于复杂问题，需要计算机三 运筹学的模型运筹学的主要特点是通过模型来描述和分析所认定范围内的系统状态。分析过程包括：真实系统数据准备系统分析、问题描述模型建立和修改模型求解和检验结果分析和实施1 系统分析和问题描述。认定问题的实质社会经济问题复杂性、不可重复性，不同于具有可控性的物理模型（提高企业效益：开发市场？增加设备？加强研发？）。明确系统的主要目标（利润最大化、市场占有率最大化、销售收入最大化？GDP增长、可持续协调增长？）、找出系统主要变量和参数、变化范围、相互关系及其对目标的影响。分析问题的可行性：技术可行性有无现成的运筹学方法？ 经济可行性研究的成本和预期的效果，考虑运筹决策的时间和代价，要对研究问题的深度和广度作出一定限制 操作可行性研究人员的配备2 建立数学模型要尽可能简单；要能完整的描述所研究的系统。 研究中，先对复杂问题抽象出关键性因素，简单化处理；再深入研究接近实际。 典型的模型包括：（1）一组需要通过求解模型确定的决策变量 （2）一个反映决策目标的决策函数 （3）一组反映系统逻辑关系和约束关系的约束方程 （4）模型要使用的各种参数表达式为： 决策函数 （包括最优解、次优解、满意解；单一目标、多目标） 约束条件 （等式时为平衡条件）为可控变量，为已知参数，为随机因素（确定性模型无随机因素） 3模型求解和检验搜集资料，对缺少的资料和不可控因素的处理（58年人口数据）：补充？做假设？先作出初步决策？分析模型，确定不同行动方案对目标的影响（最核心的工作）；检验分析结论与实际是否符合，原因：模型假设是否忽略重要因素？数据是否完整？4结果分析和实施作为决策参考（实际决策时，进一步考虑模型没有考虑的因素）。四 学科内容和应用领域1数学规划理论（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、决策论、对策论、排队论、存贮论、随机过程、质量管理、统计回归、模拟、数值分析等等。2 经济应用领域（1）市场营销 广告预算、媒体选择、竞争性定价、新产品开发、销售计划制定等（2）生产计划 运用线性规划和模拟方法，确定生产、库存和人力的配合的生产计划（3）库存管理应用存贮论，停车场面积、计算机内存、新增发电设备容量等（4） 运输问题列车时刻表制定、空运安排（5）财政和会计应用统计分析、数学规划、决策分析等，分析预算、贷款、证券投资、定价等（6）人事管理、设备维护、计算机系统（内存分配、文件查找、文件处理）、城市管理第二章 线性规划与单纯形方法线性规划是运筹学一个主要分支，是求一个线性函数在满足一组线性等式（或不等式方程）的约束条件下极值问题。47年美国Dantzig提出单纯形算法（simplex）求解线性规划问题；现用计算机可以解决上万个约束条件和决策变量的线性规划问题。50年代苏联康脱洛维奇和美国Koopmans应用于经济问题分析（生产理论的生产决策和成本控制），同时获得诺将。本章主要介绍：线性规划的基本概念：数学表达式、简单线性规划问题的图解法等 线性规划的基本理论和单纯形求解法第一节 线性规划的基本概念一 线性规划模型1 例子1： 生产计划问题：某家具厂生产桌子和椅子，桌子售价50元/个，椅子售价30元/个。需要木工和油漆工，生产一个桌子需要木工4小时，油漆工2小时， 生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时120小时，油漆工工时50小时。如何组织生产，使得每月销售收入最大？分析： 确定决策变量生产桌子的数量，生产椅子的数量 确定目标函数使销售收入最大， 确定约束方程 木工， 油漆工 变量取值限制非负约束 ， 2 线性规划的一般形式： 线性规划模型一般包括三个部分：（1）由决策变量构成的反映决策者目标的目标函数；（2）一组由决策变量的线性等式或不等式构成的约束方程（subject to）；（3）限制决策变量取值范围的非负约束一般形式：为决策变量，反映n种生产经营活动；为目标函数，为目标函数系数，反映决策变量的单位费用和收益；列向量为m种资源的可用量；为技术系数或投入产出系数，表示j种经营需要第i种资源的投入量。线性规划隐含的假定：（1）比例性假定，决策变量引起目标函数和约束方程成比例的变化，即每种经营活动对目标函数的贡献是一个常数。否则非线性规划 （2）可加性假设，每个决策变量对目标函数和约束方程的影响是独立的，（3）连续性假设，决策变量取连续值，否则整数规划（4）确定性假设，所有参数都是确定性，否则随机规划3 两变量的线性规划问题图解法： 在例1中，决策变量和的数值可以由直角坐标系表示，任一点的坐标表示一个决策方案。根据约束条件，作出阴影区域。一些概念的描述说明：可行解在阴影区域包括边界点，决策变量和的值都满足约束条件，这些点都是；可行域所有可行解的集合称为线性规划的线性规划的解（最优解）可行解中使得目标函数值极大或极小的那个可行解。极点可行域的顶点，对于线性规划问题极点数量是有限的。 线性规划解的类型：（1） 对于极大化问题，最优解总是在极点处取得；（2） 若目标函数的斜率与某一约束方程斜率相同，则存在最优值相同的多重解；（3） 若可行域为开集，最有值趋于无穷大，成为无界解。可能忽略了重要约束。（4） 若可行域为空集，则无解。原因是模型错误或者约束条件相矛盾。作业：1 投资证券组合的选择问题（见MBA运筹学教材P15），根据问题描述，建立运筹学模型。 2 图解法求解下列线性规划问题 第二节 线性规划问题的数学模型和标准形式习题讲解：线性规划问题的图解法几点启示：（1）线性规划问题的解有：唯一最优解、无穷多最优解、无界解和无可行解 （2）若可行域存在，则是凸集 （3）若最优解存在，则一定是在凸集的顶点上取得 （4）（类似于计算机编程，寻找一组数的最大值）搜寻最优解的方法：先计算一个顶点处的目标函数值，然后比较周围相邻顶点的值，直到找到最优值。1 线性规划问题的数学模型一般形式的线性规划问题：一般形式：简写： 用向量形式表达：式中 用矩阵形式表示：；为技术系数或投入产出系数，A为约束变量的系数矩阵。2 线性规划问题的标准形式 为了便于计算机求解，将线性规划问题的目标函数和约束条件标准化为 即：目标函数极大值、等式约束、常数b非负、变量x非负其他非标准形式的转化（不等式关系不便进行高斯消元法）：（1） 目标函数为极小值：令，则，即目标函数系数添加负号（2） 约束条件为不等式当时，如，令，则有：，。称为松弛变量，表示未被充分利用的资源，目标函数中系数为0。当时，如，令，则有：，。称为剩余变量，表示超用的资源，目标函数中系数为0。（3） 取值无约束的变量如x为当期某种产品产量与上一期产量的差，其取值可正可负。可令（4） 变量。可令。3 线性规划问题的标准形式两个例子（1）（作业）投资证券组合的选择设为第i种投资方式在总投资额中占的比例，线性规划模型：标准化：约束条件中四个不等式，引进，则（2）线性规划问题解：令，则：作业1：请将下列线性规划问题化为标准形式4 线性规划问题的解几个基本概念【复习：向量组的秩向量组T的极大无关组中所含向量的个数称为向量组的，记为r（T）。矩阵的秩矩阵的行向量组的秩称为矩阵A的行秩，矩阵的行秩和列秩相同，通称矩阵的秩，记为r（A）。，当A的行向量组线性无关时，r（A）m，为行满秩阵，也为满秩阵克莱姆法则n个未知数和n个方程的线性方程组，若系数行列式，则方程组有唯一解】在标准形式（1.1）（1.2）（1.3）中，可行解满足约束条件（1.2）（1.3）的解称为线性规划问题的。全部可行解的集合称为可行域。最优解使目标函数（1.1）达到最大值的可行解称为基在线性规划问题中，设A为约束变量的mn阶系数矩阵（设nm），则秩为m（表示各个约束条件是不相关的）。在矩阵A中选取一个mm的满秩子矩阵B，B称为线性规划问题P的一个基。设，B中的每个列向量称为基向量。与基向量对应的变量称为基变量，其他的变量为非基变量。基解令所有非基变量，由于B满秩，由克莱姆法则，可得到m个基变量的唯一解，加上为零的非基变量，称为线性规划问题P 的基解。基解总数不超过（可以迭代搜寻最优解）基可行解满足变量非负约束的基解称为可行基对应于基可行解的基称为5 线性规划问题的解例子：找出下面线性规划问题的全部基、基解、基可行解和最优解 解：先化为标准形式 再列出约束变量的系数矩阵：，矩阵的秩r（A）3，列出全部的基：基基解基可行解目标函数值X1X2X3X4X5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0注意：,其中和为线性相关，故只有八个基；去掉变量非负的约束，剩下5个可行基。作业2：请找出下面线性规划问题的全部基、基解、基可行解和最优解第三节 单纯形法原理（1947，Dantzig提出的基本求解方法）1 预备知识凸集和顶点凸集直观上，若集合中任意两点，其连线上的点也是集合中的点，则称数学定义：对任何，有，则称C为凸集。例如：凸不是凸集；环不是凸集，定义空集和实数集Rn为凸集顶点如果C中不存在任何两个不同的点X1、X2，使得X成为这两个点连线上的一个点，则点X称为数学定义：对任何，不存在，则称X是凸集C的2 几个基本定理的证明定理1若线性规划问题存在可行解，则问题的可行域是凸集。证明思路：根据可行域定义（满足线性规划的约束条件的点集C），要证明其为凸集根据凸集定义，需证明C内两点的连线也在C内即可。设为C内任意两点，即满足约束条件：，。 现证此两点的连线也满足约束条件，即将代入约束条件，可知其成立，故X也在C内，得证。引理线性规划问题的可行解为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。同学提出的问题：基可行解中非基变量可取非零值？由引理，此时该非基变量作为正分量，其却是线性相关的，因此其不是基可行解不是基可行解的具体含义由定理2可知。 定理2线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。，上述定理等价于“X不是可行域的顶点X不是基可行解”（1） X不是基可行解由引理可知线性相关在解X的邻域内可用另外两点线性表示非顶点X不是基可行解设X的前m个分量为正， （3-1）由引理，对应的系数向量线性相关，即存在不全为零的： （3-2）（3-1）u（3-2），得：（3-1）u（3-2），得：令X（1）， X（2），并使得u取值满足，设则可知X（1），X（2），同时，因此，X不是顶点。（2）X不是可行域的顶点不是基可行解设不是可行域的顶点，根据顶点定义，可以找到可行域内不同的2点Y和Z：因，当，必有：。由x的定义，即：，； 将可行域的点X代入约束方程：由Y、Z都是可行域内，满足约束方程：，两式相剪， 得出： （33） 由于Y和Z都是可行域内不同的两点，故不全为零，由上式可知，线性相关，X不是基可行解。定理3若线性规划问题有最优解，则一定存在一个基可行解是最优解。证明：设是线性规划问题的最优解，是目标函数的最大值。若不是基可行解定理2可知其不是顶点可行域内存在过的直线上两点：，将其代入目标函数：。 由是目标函数的最大值，故：可得：，。 若仍不是基可行解，继续寻找，直至为一个基可行解，目标函数值为。3 确定初始基可行解根据上述定理，最优解一定在基可行解中。单纯形法思路：先找到一个初始可行基，若不是最优解，转换到另一个基可行解，并使得目标函数值增大，直到最优解。给定线性规划问题：变成标准型后，每个约束加上松弛变量，其系数矩阵（单位矩阵）即构成初始基，基可行解为：。当约束条件为“”或者“”时，可以添加人工变量构造一个单位矩阵作为初始基。4 从初始基可行解转换到另一基可行解目标函数值增大设初始基为，满足约束条件： （34）对应一个基为，其它基向量可以用这个基线性表示： 现从理论角度推导该问题的另一个基：由上式， 乘上整数：，上式与（34）相加得： （35）由此可得约束方程的另一个解X(1)： （36）欲使X(1)成为基可行解，根据引理，基的秩m，上述（m1）个分量中至少有一个为零讨论的取值，使得其中一个分量为零：令（a小于0时分量显然成立） （37）可得：此时，正分量最多m个，对应m个新的基向量线性无关，（36）式中，将取值代入，得新的基可行解X(1) 解释：已知初始基解（34），通过引入新的非基向量，得出相应的一个解X(1)；由于增加了新的基变量，为了使X(1)满足基可行解，需要将其中一个原基变量变成0，通过的合适取值达到此目的。 5 最优性检验和解的判别将基可行解X(0)、X(1)代入目标函数：，由于取值（37）确定，设，当时，有。对检验数取值进行最优性检验的判别定理：（1） 将其它非基向量逐一代入后，当所有，现有顶点对应的基可行解即为最优解；（2） 当所有，并且某个非基变量的（即非基变量的检验数为0），另一顶点对应的基可行解也为最优解两点连线也是，有无穷多解；（3） 若存在某个非基变量的，且该向量的所有分量。可知，对于任意，都满足。故可取任意值（不必37式约束）。当，此时无界解。（4） 如果某个非基变量的，且该向量的某一分量表明存在着更优解，进行换基迭代，重复进行。6 检验数的数学意义由目标函数的典则形式，对非基变量求导：含义：检验数在数学上解释为非基变量的单位改变量引起目标函数值的改变量。第四节 单纯形法的计算步骤1 步骤 （1） 将线性规划问题化为标准型，求初始基的可行解，列出初始单纯形表；（2） 对表中最后一行检验数取值进行最优性检验如果第（4）种情况，换基迭代；（3） 确定换入基变量：选择原则找一个最大检验数其对应的非基变量，作为换入基变量。 含义代表该目标函数值逼近最优值收敛速度最快。（4） 确定换出基变量：选择原则根据上一节中原则，对于新换入的基向量，（单位矩阵的基解）确定作为换出基变量，元素决定了换入、换出的基向量，称为主元素。含义根据换入向量，把那些资源约束b最小、消耗系数a最大的原向量换掉（5） 运用高斯消去法，将换入向量变成单位向量，得到新的基可行解，作新的单纯形表。（6） 比较检验数，重复过程。2 例子：线性规划问题：解：（1） 化为标准型：（2） 取组成一个单位矩阵的基，得基解，列出初始单纯形表1：cj 23000CB基bx1x2x3x4x50x312221000x416400100x51505001cjzj () 23000 其中，最后一行检验数根据第一列（目标函数系数）减去基变量的系数CB与相应消耗系数aij的乘积。（3）最大检验数3对应非基向量x2作为换入向量；（4） 根据，确定换出向量为第三行15所对应的基x5。 主元素为对应的5。其中第二行不满足，故不考虑。（5）单纯形表第2列的基进行调换：x5x2，对应调换目标函数系数03；运用高斯消去法，将x2换入向量化为单位向量，主元素位置5化为1，资源向量相应变化列出新的单纯形表2：cj 23000CB基bx1x2x3x4x50x3620102/50x416400103x2301001/5cjzj () 20003/5 （6）计算最后一行检验数，新的最大数2对应非基向量x1作为换入向量；根据，确定换出向量为第一行6所对应的基x3。 单纯形表前2列的基进行调换：x3x1，对应调换目标函数系数02；运用高斯消去法，将x1换入向量化为单位向量，列出新的单纯形表3：cj 23000CB基bx1x2x3x4x52x13101/201/50x4400214/53x2301001/5cjzj () 00101/5（7）计算最后一行检验数，所有的，得最优解，目标函数值。3 讨论：（1）当出现2个以上相同的最大检验数时，任取一个换入即可； （2）相持出现2个以上相同的最小值，高斯消去法时另一个基变量将为0，称为退化。在理论上会有循环的可能，实际上很少，任取一个换出即可。 退化指基解中非零分量的个数少于m，称基解为。举例：表2中若b4的16换成12，则表3中b4为0，最优解。第五节 单纯形法的进一步讨论1 人工变量法（第一种方法：大M法） 当约束方程为时，添加m个松弛变量构成的单位矩阵，作为初始基；对于约束条件“”情况，由于减去剩余变量，不存在单位矩阵需求解联立方程组、并且不能保证解非负的基可行解条件，如何解决？ （1）添加人工变量构成单位矩阵，作为初始基。 （2）添加后，原不等式约束条件如何满足？若最终的基解中人工变量取值为0（变为非基变量），此时为基可行解； （3）取值为0的约束，反映在目标函数中，人工变量的系数添加足够大的负值（M），作为数学符号参加运算。其是一种罚函数法，单纯形法的寻优机制将人工变量赶出基外。 含义：只有当人工变量取0时，目标函数才能取得最大值。 （4）局限：计算机求解时，将M设为最大字长的数，但是如果其它参数a、b、c与其接近，或远小于，则发生取值误差，？采用两阶段法解决。（补充知识：罚函数法与障碍函数法是求解约束极小化问题的较好的算法，其基本原理是在原目标函数中加上一个罚（障碍）函数，而得到一个增广目标函数。罚（障碍）函数的功能是对非可行或企图穿越边界而逃离可行域的点赋予一个极大的函数值。可以作一个形象的比喻：在约束极小化问题中，约束条件是一条“法律”，凡是不服从这条“法律”的点被处以“罚款”的“经济制裁”，而且“罚款”的数额极高。这样，在对新的目标函数进行无约束极小化的过程中，就会迫使迭代点逐步逼近（当迭代点在可行域外时）或者不能离开可行域（当迭代点在可行域内时），这样所得的关于增广目标函数的无约束极小化的解就会逼近于原目标函数的约束极小化的解。也就是说，可以将约束极小化问题通过增广目标函数而化成无约束极小化问题）举例：求解线性规划问题分析：化为标准形式后添加人工变量，得：（2）列单纯形表：cj 3 0100MMCB基bx1x2x3x4x5x6x70x441111000Mx612110110Mx790310001cjzj 32M 4M10M000x4330211100x212110110Mx766040331cjzj 36M014M03M4M00x4000011/21/21/20x23011/30001/33x11102/301/21/21/6cjzj 00303/2M3/2M1/20x4000011/21/21/20x25/21/21001/41/41/41x33/23/20103/43/41/4cjzj 9/20003/4M+3/4M1/4计算最后一行检验数，所有非基，去掉人工变量，得最优解，目标值2人工变量法（第一种方法：两阶段法） 第一阶段：寻找一个初始可行基添加人工变量构成初始基，构造求极小值的目标函数min （除人工变量系数为1，其它变量系数为0。根据罚函数，此时原目标函数趋于极大值）。运用单纯形法计算（或者人工变量对应的取1；或者作为最小化检验）若目标函数的解为min w0，表明基中的人工变量为0，结果是可行基；若目标函数的解为min w0，表明最优解的基变量中含有人工变量，原约束方程无可行解。第二阶段：得到初始可行基后，去掉其中的人工变量，从最后一个单纯形表出发，继续求解原目标函数max z。举例：上例中，化为标准型：第一阶段：求解，列单纯形表1：cj 0 000011CB基bx1x2x3x4x5x6x70x4411110001x6121101101x790310001cjzj 24001000x4330211100x2121101101x76【6】040331cjzj 6040340出现了退化现象，任选其一。0x4000011/21/21/20x23011/30001/30x11102/301/21/21/6cjzj 0000011此时，满足所有的，得基解，人工变量x6、x7为0，解是基可行解。 第二阶段：求解，根据最后一表（由新目标函数，CB列和cj行变化）：cj 30100CB基bx1x2x3x4x50x4000011/20x23011/3003x11102/301/2cjzj () 00303/20x4000011/20x25/21/21001/41x33/23/20103/4cjzj () 9/20003/4计算最后一行检验数，所有非基的，得最优解，目标函数值。3 根据单纯形表判断解的类型（根据非基变量的检验数j）：35创建时间：2008-8-31 10:34:00xjxxjx（或0）x（或0）j运筹学 物流管理专业 最优解 非最优，继续迭代 无界解（所有aij0）7创建时间：2005-9-21 0:39:00x + xj0 运筹学 物流管理专业 无穷解（至少有一个aij0） 无可行解：当所有时，人工变量仍留在基变量中4 单纯形表计算的向量矩阵描述（选讲）：创建时间：2008-8-31 10:34:00标准形式：，其中将系数矩阵A分为初始基的单位矩阵I和非基变量的系数矩阵BN，单纯形表的计算过程是对系数矩阵A进行初等变换，使得非基向量B变换为基向量I，I变换为B1。见下表:初始解非基变量基变量bBNIcjzjN0,0,0 实施基变换后，基可行解基变量非基变量bINB1cjzj0,0,0NY 其中：， 给定单位矩阵构成的初始基，可以通过矩阵运算直接求出新的单纯形表应用于对偶问题分析。5 Excel求解线性规划问题： （参见网络课程中的上机实验指导说明辅助材料，可下载）Excel的工作表用作描述问题与建立模型时，就被称做Spreadsheet。本实验指导书第二部分旨在帮助学生在运筹学课程中，学习如何运用Excel对复杂的实际系统进行描述与建模，并用计算机求解。由于避免了大量繁琐的数学公式，使得运筹学的理论方法简明直观，容易理解与应用，因此，掌握它有利于运筹学理论的学习，也特别有利于那些注重应用的企业管理人员的学习，为企业决策人员与管理人员掌握与应用运筹学理论提供一个有益的工具。6 作业1：请分别用单纯形法的大M法和两阶段法求解线性规划问题，并分析解的类型。（A） （B）作业2（应用题工业原材料的合理利用）：要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根，已知原材料长7.4m，如何下料最节省？（仅建立标准模型即可，可用Excell求解） （分析思路：原材料7.4m可以有多种下料组合方式，分别列出并计算每种组合的料头大小，目标是总的料头最小）7 本章小结（1）化标准形式 变量：时不变、时令、 无约束时令 约束条件：右端项时，两段乘以“1”； ； ； 目标函数： 极小值时，令 添加变量的系数第六节 数据包络分析1 基本概念 数据包络分析(data envelopment analysis, DEA)是具有多投入和多产出的决策单元（Decision Making Units, 简称DMU）进行绩效评价的方法。1986年由由美国运筹学家A. Charnes和W. W. Cooper等学者创建它主要采用数学规划方法，利用观察到的样本数据，对具有相同类型的多投入、多产出的决策单元进行生产有效性评价。适用情况：当所有投入产出指标均可以折算为同一单位（货币值），采用投入产出比指标； 当投入产出无法折算为同一