运筹学基础及应用.ppt

运筹学,(OperationsResearch),夫运筹策帷幄之中，决胜于千里之外史记高祖本纪,绪论,（1）运筹学简述（2）运筹学的主要内容（3）本课程的主要学习内容（4）运筹学的应用（5）本课程的教材及参考书（6）本课程授课方式与考核,本章主要内容：,一、古代朴素的运筹学思想,国外英文原名OperationsResearch简称“O.R.”直译为：运用研究或作业研究正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中,中国古代运筹学案例,二、运筹学的起源,（一）运筹学简述,运作研究(OperationalResearch)小组”:二战期间解决复杂的战略和战术问题。例如：如何合理运用雷达有效地对付德军空袭对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。二战后运筹学的发展经历了三个阶段（1）1945年到20世纪50年代初创建时期（2）20世纪50年代初到20世纪50年代末成长时期（3）20世纪60年代以来迅速发展和普及的时期,国内1956年成立第一个运筹学小组1957年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将O.R.正式翻译为“运筹学”,三、运筹学的定义,研究工具：数学，计算机科学及其他相关科学,研究目的：对有限资源进行合理规划、使用，并提供优化决策方案。,研究对象：复杂系统的组织和管理,参考大英百科全书、辞海、中国企业管理百科全书等。,四、运筹学研究的基本特点,系统的整体优化多学科的配合模型方法的应用,五、运筹学研究的基本步骤,分析与表述问题建立数学模型对问题求解对模型和模型导出的解进行检验建立对解的有效控制方案的实施,（二）运筹学的主要内容,数学规划（线性规划、整数规划、目标规划、动态规划等）图论存贮论排队论对策论（博弈论）决策论,（三）运筹学的应用,运筹学方法应用例线性规划生产结构优化非线性规划投资组合优化整数规划选址问题动态规划资源分配问题网络分析工程计划优化排队论服务系统优化存贮论订货库存管理决策分析机会选择,运筹学的广泛实际背景促使其不断发展并在经济管理和系统工程等多领域中发挥着令人瞩目的重要作用。诺贝尔经济学奖从1969年首发至今的57位获奖者中就有多位是运筹学家。1975年诺贝尔经济学奖授给了库普曼和康脱罗维奇，以表彰首先将线性规划与经济问题相联系而做出的贡献；1994年诺贝尔经济学奖授给了三位博弈论专家：纳什、泽尔腾、海萨尼。博弈论已经成为当代经济学的基石。2005年以色列经济学家罗伯特-奥曼和美国经济学家托马斯-斯切林，因“通过博弈论分析加强了我们对冲突和合作的理解”所作出的贡献而获奖。,发表的部分获奖项目,（四）本课程的教材及参考书,选用教材运筹学基础及应用胡运权主编（第五版）高等教育出版社参考教材运筹学教程胡运权主编（第4版）清华出版社管理运筹学韩伯棠主编（第2版）高等教育出版社运筹学(修订版)钱颂迪主编清华出版社,（五）本课程的主要学习内容,第一章线性规划及单纯形法第二章线性规划的对偶理论第三章运输问题第四章整数规划与分配问题,（六）本课程授课方式与考核,讲授为主，结合讨论、习题作业,第一章线性规划及单纯形法,LinearProgrammingandSimplexMethod,线性规划-发展简史,法国数学家J.-B.-J.傅里叶和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。,50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。,1979年苏联数学家.哈奇扬提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法-内点算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。,1.1939年，前苏联科学家康托洛维奇-生产组织与管理中的数学方法是线性规划应用于工业生产问题的开山之作；(LEONIDVITALIYEVICHKANTOROV(1912-1986),2.1947年，美国数学家乔治伯纳德丹齐格-单纯形法，被称为线性规划之父。GeorgeBernardDantzig(19142005),丹齐格在1946年获伯克利大学的博士学位。1947年，33岁提出了解决一种最优化问题的单纯形法,该方法奠定了线性规划的基础，使得经济学、环境科学、统计学应用等学科获得了迅速发展。Dantzig也因而被誉为“线性规划之父”。1952年他在兰德公司任研究数学家，在公司电脑上实行线性规划。1960年他被母校聘任教授计算机科学，终于当上运筹学中心主任。1966年他在史丹福大学当类似职位，留在那里直到1990年代退休。Dantzig在运筹学建树极高，获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linearprogrammingandextensions一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确定规划。SIAMJournalonOptimization1991年创刊号是献给他的。MathematicalProgrammingSociety为表彰丹齐格，设立丹齐格奖，1982年起每三年颁给一至两位在数学规划有突出贡献的人。,x,a,此为无约束的极值问题,1.1一般线性规划问题的数学模型,1-1问题的提出,例1用一块边长为a的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？,解：如图设四个角上减去的小正方形边长为x，则容器体积为：,时，容积最大,例2常山机器厂生产I、II两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：,如何安排生产才能使总的利润最大？,解：设计划期内两种产品的数量分别为x1，x2，则总利润为：,maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,简记为：,s.t.（约束于：）,z=2x1+3x2,在满足限制条件下求z的最大值。,此为有约束极值问题,1-2线性规划问题的数学模型,原型,模型,数学模型,提炼,数学工具,1、原型：现实世界中人们关心、研究的实际对象。模型：将某一部分信息简缩、提炼而构造的原型替代物。数学模型：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。,3、规划问题数学模型的三要素,（2）目标函数：问题要达到的目标要求，表示为决策变量的函数。用z=f(x1，x2，xn)表示。,（1）决策变量：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用x1，x2，xn表示。,（3）约束条件：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,2、规划问题,即求目标函数在若干约束条件下的最值。,4、线性规划问题（LinearProgramming）的数学模型,（2）一般形式：,（1）条件：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“L.P.”,max(或min)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn（=，）b1a21x1+a22x2+a2nxn（=，）b2am1x1+am2x2+amnxn（=，）bmx1,x2,xn0,（3）其他形式：,连加形式,向量形式,其中,称为价值行向量；,决策列向量,系数列向量,右端列向量,矩阵形式,其中,称为价值行向量；,决策列向量,右端列向量,约束矩阵或系数矩阵,1-3线性规划问题的标准形式,1、标准形式,或,2、条件,目标函数求极大值,约束条件全是等式（线性方程组）,决策变量全非负,右端常数全非负,3、标准化方法,（1）若目标函数求极小值，即,则令,转化为,（2）若约束条件为不等式，,则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。,注意：松弛变量在目标函数中系数全为0。,约束为不等式，减去松弛变量，化为等式约束条件；约束为不等式，加上松弛变量，化为等式约束条件。,多退少补,例：maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,s.t.,标准化,（3）若决策变量xj0，则令,（4）若决策变量xj取值无限制，则令,（5）若约束等式的右端常数bi0，则等式两边同时乘以“-1”。,其中,（“一分为二”）,例：将下列线性规划模型化为标准形式。,则问题化为标准形式：,并引入松弛变量x4,x5,课堂练习：将下列线性规划问题化为标准形式,线性规划问题的数学模型,标准形式如下：,1-4线性规划问题的解,已知线性规划的标准形式：,或,1、求解线性规划问题：,从满足（2）、（3）的方程组中找出一个解使目标函数（1）达到最大值。,2、可行解：,所有可行解的集合。,可行域：,满足约束条件（2）、（3）的解。记做,最优解：,使目标函数达到最大值的可行解。,（1）基：设A为线性规划问题约束条件的mn系数矩阵（m0，有如下结论：,(1)若对所有jm+1，有j0，则z（1）z（0），即z（0）为最优函数值，X（0）为唯一最优解；(2)若对所有jm+1，有j0，且存在某个非基变量的检验数k=0，则将Pk作为新的基向量得出新的基可行解X（1），满足z（1）=z（0），故z（1）也为最优函数值，从而X（1）也为最优解，X（0）、X（1）连线上所有点均为最优解，因此该线性规划模型具有无穷多最优解；(3)若存在某个j0，但对应的第j列系数全非正，即aij0，则当+时，有z（1）+，该线性规划模型具有无界解。,1.4单纯形法的计算步骤,1、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。,不妨假设A中前m列对应的子矩阵是单位矩阵，取其为基B，得到初始基可行解,m+3行,n+4列,第1行：价值行cj,第2行：变量行xj,最后一行：检验数行j,第1列：基价值列CB,第2列：基变量列XB,第3列：基解列b,最后一列：比值列,主体：系数矩阵Amn,2、单纯形表的结构,3、初始单纯形表：含初始基可行解的单纯形表,最优单纯形表：含最优解的单纯形表,4、单纯形法（SimplexMethod）：利用单纯形表求解线性规划问题的方法。,5、单纯形法的计算步骤,(1)化L.P.问题为标准形式,建立初始单纯形表；,(3)计算,以alk为主元素(简称主元，用表示)，进行线性方程组的初等行变换，将主元列Pk化为单位向量得到新的单纯形表，转入(2)。,（最大正检验数决定换入变量）,（最小比值决定换出变量）,例1：用单纯形法求解下列线性规划问题.,maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,s.t.,解：先标准化,再列初始单纯形表：,6,-,3,23000,以5为主元进行初等行变换,x1为换入变量,下面开始单纯形法迭代：,x5为换出变量,x2为换入变量,以2为主元进行初等行变换,x3为换出变量,主元化为1，主元列的其他元素化为0,此时得到唯一最优解X*=(3,3)T,Zmax=15。,例2用单纯形法求解下列线性规划问题,解：先标准化,1/3,-1/2,1/6,1/3,-1/3,3/4,12,唯一最优解,6、单纯形法中存在的问题,（1）存在两个以上的最大正检验数。任取一个最大正检验数对应的变量作为换入变量。,（2）出现两个以上相同的最小值。任取一个最小对应的变量作为换出变量。此时L.P.问题出现退化现象。,练习：,5-1人工变量法（大M法）,1.5单纯形法的进一步讨论,前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,例1：用单纯形法求解下列线性规划问题。,解：先标准化为,系数矩阵,但是A中没有单位矩阵，在A中人为的增加两列,此时,对应的约束方程组为：,该问题新增加了两个变量：x4,x5（称为人工变量）,A有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。,为使,必须保证在可行解中人工变量x4=x5=0，故令x4，x5在目标函数中的系数为M（其中M表示任意大的正数），这种添加人工变量求解LP的方法称为人工变量法,计算过程中出现了M，这种方法也称为大M法。,等价于,于是，这个线性规划问题转化为：,以下可用单纯形法继续求解。,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,-2-30-M-M,34,x4x5,-M-M,cj-zj,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,-1/2+M/20-M03/2-3M/2,-M-3,24,10-22-1011-11,x1x2,21,cj-zj,00-11-M1-M,-2-3,x5,0,唯一最优解,故zmin=7,注意：此时人工变量x4=x5=0,说明：若表中所有j0，但存在非0的人工变量，则该模型无可行解。,采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大M法失效。在这种情况下，可采用下面的两阶段法进行计算。,5-2两阶段法(将L.P.问题分成两个阶段来考虑),第一阶段:判断原L.P.问题是否存在可行解。给原L.P.问题加入人工变量，并构造仅含人工变量的目标函数w（人工变量在w中的系数一般取为1）并求w的最小值；然后用单纯形法求解。若求得wmin=0，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。,第二阶段：将第一阶段得到的最终表去掉人工变量，并将目标函数还原为原L.P.问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。,例：用两阶段法求解下列线性规划问题。,标准化,引入人工变量,z,(1)第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解这个问题，先标准化为；,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,000-1-1,34,x4x5,-1-1,cj-zj,2,3,-1,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,1/20-10-3/2,-10,24,10-22-1011-11,x1x2,21,cj-zj,000-1-1,00,x5,0,最优解,本问题有可行解，进入第二阶段,(2)第二阶段先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即maxz=-2x1-3x2+0 x3，继续迭代：,Cj,x1,x2,x3,XB,b,CB,10-2011,-2-30,21,x1x2,-2-3,cj-zj,0,0,-1,唯一最优解,故zmin=7,注意：两阶段法中不再出现大M，但需要解两个线性规划问题，要注意目标函数系数的变化。,5-3关于解的判别,例7用单纯形法解下列线性规划,无穷多解,当所有的，但某一非基变量检验数，存在无穷多最优解的条件是Ps列向量中至少存在一个元素，且能找出最优解.,例8用单纯形法解下列线性规划,无界解,若存在某个j0，但对应的第j列系数全非正，即aij0，则问题的解无界.,例9用单纯形法解下列线性规划,无可行解,若表中所有j0，但存在非0的人工变量，则该模型无可行解。,用最终单纯形表判断线性规划问题解的类型：,已知线性规划问题形如：,5-4单纯形法计算的向量、矩阵描述,引入松弛变量xs,记X=(XB,XN,XS)T其中，XS为松弛变量，在初始表中是基变量；XB为最终表中基变量；XN表示既不是初始表的基变量又不是最终表的基变量。注意：XS和XB允许有公共变量。,（2）A=(B,N,I)B,N,I分别为XB、XN、XS在初始表中对应的矩阵。,则（1）C=(CB,CN,0)CB,CN,0分别为XB、XN、XS在目标函数中的系数。,（3）A=(I,N,B-1)I,N,B-1分别为XB、XN、XS在最终表中对应的矩阵。,约束方程组两端同时左乘B-1，则可得如下表达式：,初始单纯形表,最终单纯形表,用单纯形表表示如下：,XSb,BNI,XBbINB-1,初始表XBXNXS,cj-zj0,0NS=（-y1,-y2,-ym）=-YT,最终表XBXNXS,cj-zjBN0,0,比较得：b=B-1bN=B-1N或者Pj=B-1PjS=-CBB-1=-YTN=CN-CBB-1N=CN-YTN或者j=Cj-CBB-1Pj,其中B-1为初始表中基变量在最终表对应的系数矩阵，B为最终表中基变量在初始表对应的系数矩阵。,例：用单纯形法求解下列线性规划问题.,maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,s.t.,解：先标准化,得到初始单纯形表：,6,-,3,23000,最终单纯形表：,X4010,X4010,可以验证：,根据上表可以列出初始单纯形表,5-5单纯形法小结,个数,取值限制,右端常数,约束方向,要求,系数,列初始表,1.7应用举例,一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：.需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；.为达到这个目标存在多种方案；.要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。,（一）、混合配料问题,例：某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。,解：,用i=1,2,3表示原料A、B、C；用j=1,2,3表示糖果甲、乙、丙；设xij为生产第j种糖果使用的第i种原料的质量，则该问题的数学模型为：,s.t.,原料供应限制,含量要求条件,用单纯形法求得：,即每月生产甲糖果kg，乙糖果kg，不生产丙糖果，可获得最大利润为5450元。,（二）、投资项目组合问题,例：兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资：1、三年内每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资；2、只允许第一年初投入，于第二年末收回，本利合计为投资额的150%,但此类投资限额不超过15万元；3、允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元；4、允许于第三年初投入，年末收回，可获利40%，但限额为10万元.试为该公司确立一个使第三年末本利和最大的投资组合方案，请建立这个问题的线性规划模型。,解：用xij表示第i年初投放到第j个项目的资金数，则建立如下线性规划模型：,第i年初,投入第j个项目,用单纯形法求得：,综上投资组合方案如下：,(三）、人力资源分配问题,例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?,解：设xi表示第i班次时开始上班的司机和乘务人员人数。,此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员150人。,（四）、套裁下料问题,例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。,设按方案、下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：,Lingo软件,LINGO软件是美国的LINDO系统公司（LindoSystemInc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等.,LINGO的语法规定：（1）求目标函数的最大值或最小值分别用MAX=或MIN=来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母（AZ）开头，由字母、数字（09）和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号