运筹学讲稿.docVIP

第  PAGE 9 页 共  NUMPAGES 9 页 运 筹 学 讲 稿 一、运筹学的简史 运筹学的早期工作及其历史可追溯到1914年，当时兰彻斯特（Lanchester）提出了军事运筹学的战斗方程；1917年，丹麦工程师埃尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排对论的一些著名公式；20世纪20年代初提出了存储论的最优批量公式.1947年美国数学家丹西格（G..B.Danting）在解决美国空军军事规划问题时，提出了线性规划及单纯形法.早在1939年，前苏联学者康托洛维奇（JT.B.KaHTopobny）在解决工业生产组织和计划问题时，已提出了类似线性规划模型，并给出了“解乘数法”的求解法.可惜当时未被重视. 运筹学作为一门科学诞生于20世纪30年代末期，通常认为运筹学的活动是第二次世界大战早期从军事部门开始的.当时，英国为了研究“如何最好的运用空军及新发明的雷达保卫国家”，成立了一个由??方面的专家组成的交叉学科小组，即最早的运筹小组.进行“作战研究”（Operational,research），后来中文译名为“运筹学”.（我国在1956年曾用过运用学的名词，到1957年正式定名为运筹学）. 第二次世界大战期间，英、美军队中的运筹学小组研究诸如护航舰队保护商对的编队问题；当船队遭受德国潜艇的攻击时，如何使船队损失最小的问题，反潜深水炸弹的合理起爆深度问题；稀有资源在军队中的分配问题等.第二次世界大战后，特别是运筹学在军事上的显著成功，引起了人们的广泛的关注，运筹学很快深入到工业、商业、政府部门等，并得到了迅速发展. 在20世纪50年代中期，钱学森、许国志等教授全面介绍运筹学，并结合我国特点在国内推广应用.1957年，我国在建筑业和纺织业中首先应用运筹学；从1958年开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用.在解决邮递员合理投递线路时，管梅谷教授提出了国外称之为“中国邮路问题”的解法；从20世纪60年代起，运筹学在钢铁和石油部门开始得到了比较全面、深入的应用.从1965年起，统筹法在建筑业、大型设备维修计划等方面的应用取得了可喜的进展；1970年在全国大部分省、市和部门推广优选法；70年代中期，最优化方法在工程设计界受到了广泛的重视，并在许多方面取得成果；排队论开始应用于矿山、港口、电信及计算机等方面；图论用于线路布置、计算机设计、化学物品的存放等；70年代后期,存储论在应用汽车工业等方面获得成功.在此期间，以华罗庚教授为首的一大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平. 运筹学是一门应用科学，至今还没有统一且确切的定义. 参见： 程理民《运筹学模型与方法教程》 钱颂迪主编《运筹学》，清华大学出版 二、引例 例1 某工厂生产甲、乙两种产品，生产每件产品需要原材料、能源消耗、劳动力及所获利如下表所示： 品种原材料（千克）能源消耗（百元）劳动力（人）利润（千元）甲2145乙3626现有库存原材料1400千克；能源消耗总额不超过2400百元；全厂劳动满员为2000人，试安排生产任务（生产甲、乙产品各多少件），使获得利润最大，并求出最大利润. [模型建立]设安排生产甲产品x件，乙产品y件，相应的利润为S ,则此问题的数学模型为： maxS=5x+6y s.t. 2x+3y≦1400 x+6y≦2400 (1) 4x+2y≦2000 x0,y0,x,y∈Z 这是一个整数线性规划问题. 例2 某工厂有100台机器，拟分四期使用，在每一期中有生产任务，两种.设第k个周期初有完好的机器台，根据经验，若周期初把、-台机器分别投入任务、，则周期末分别有/3、台机器作废（k=1，2，3，4）.如果在一个生产周期中每一台机器执行任务可收益10千元，执行任务可收益7千元，问怎样分配机器使收益最大？试建立数学模型. [数学模型的建立] 按题设，，（k=1、2、3、4）受约束于(subject to 简记为 s.t.） =+(-),0≤≤ 且=100 第K个周期收益10+7（-），因此四个周期的总收益为 V=（10+7（-）），于是问题的数学模型为： Max V=（10+7(-）） s.t. =+(-) (2) 0≤≤ ，且=100 ， k=1,2,3,4 这是一个分步决策，且为线性规划问题. 例3 某投资者有5亿元，想取其中的一部分对项目，进行投资，设投资亿元项目 ,从历史资