解放军文职招聘考试运筹数学

 运筹数学

　　运筹学的产生是第二次世界大战前后的事．1933年希特勒在德国掌权，英国就开始进行适当的准备来防御可能发生的空袭．结果在1937年末研制出雷达和飓风式战斗机．但是1938年7月进行的空战演习中，雷达和战斗机临时凑和，不能形成一个有效的空防体系．因此，当时英国在海岸的雷达研制工作的领导人罗维(A．P．Rowe)建议进行关于雷达战斗机系统的运用方面(与纯技术方面相对立)的研究工作，他还创造出“运用的研究”(operational research)一即运筹学这个词来称呼这种研究工作，这可以说运筹学正式诞生．他和威廉斯(E．C． Willia-ms)发展了发现和预防空袭的方法，并且在布莱开特(P．M．S．Blackett 1897—1974)直接领导下，成立了运筹小组．这些直接导致英国防空体系根本上的改进，在1940年8、9月间经受住了决定性的考验．美国参战之后，在1942年底，美国也进行类似的研究工作．由于从事战时工作的科学家在战后大力倡导，而使运筹学的理论和应用在战后得到了蓬勃的发展，并由军用扩大到民用许多领域，产生许多分支学科．主要学科是数学规划(包含线性规划、非线性规划、整数规划、组合最优化乃至动态规划等)、对策论、排队论、库存论、搜索论、决策分析等．

　　规划问题从数学上讲是具有约束的最优化问题．如线性规划是考虑在线性等式及不等式组的条件下求线性目标函数的极值问题．它在经济上的应用，来源于冯·诺伊曼1928年证明的对策论基本定理——极大极小定理．后来列昂节夫(W．Leontiev，1906—)关于投入产出分析在1941年提出的模型及1944年冯·诺伊曼及摩根施坦(Morgenstern，1902—1977)在他们的名著《对策论及经济行为》(Theory of Games and Economic Be-havior)中更提出竞争模型．库普曼斯(T．C．Koopmans，1910—1985)在1951年出版《生产与配置的活动分析》中独立地对线性规划的创建及发展作出贡献，并因此获1975年诺贝尔经济学奖．其中把线性规划问题化为数学上凸集或凸体的理论，其中线性不等式及凸体的对偶性起着关键的作用．这方面的理论可追溯到蒙日(1781)及傅里叶(1823)关于n维欧氏空间内凸锥、凸多面体理论，匈牙利数学家法卡斯(J．Farkas，1847—1930)给出特殊线性规划问题有解的充分必要条件，1956年塔克尔(A．W．Tucker，1915—)给出一般解的存在条件．这些理论在数学上已成为独立的学科，并由欧氏空间推广到函数空间及一般的拓扑线性空间．对于应用问题，更重要的是实用的计算方法：在这方面苏联的数学家康托洛维奇(Л.В.Канторвич，1912—1986)在1939年已做了先驱性工作，著有《生产组织与计划工作中的数学方法》，并因此获1976年诺贝尔经济学奖，由于当时环境，长期未受到注意．现代实用的方法主要是丹齐格(G．B．Dantzig， 1917—)在1947年提出的单形法，其后有一系列变形及改进，这种方法可以编成程序在计算机上运用，1977年苏联的哈奇洋(Л.Г.Хачиян)、1983年印度的卡马卡(A．Karmarkar)作出许多改进．

　　当线性规划的条件有各种变化时，得出各种规划，它们的解法基础大都仍基于线性规划的研究结果．当限定一部分为全部变元取整数值时，称为整数规划．求解整数规划，首先由戈莫瑞(R．E．Gomory，1929—)于1959年提出来．如果目标函数或约束条件中包括非线性函数，就称为非线性规划．在极值在边界上达到的简单条件下，库恩(H．W．Kuhn)及塔克尔早在1951年就发展了拉格朗日乘子法予以解决，而一般情形唯一性的讨论十分困难，只有当凸函数或凸区域的情形可以通过推广线性规划而解决，这发展成凸规划．在目标函数为正定二次函数(因而是凸函数)这种特殊二次规划情形下，还可以得出更有效的算法，毕利(E．M．L．Beale)于1959年提出的方法可以说是单形法的直接推广，其后还有各种各样方法的混合及改进．六十年代发展出另一种应用很广的几何规划，其目标函数变元的幂次不一定是整数．运筹学处理另一大类随机性模型，此外还有无约束的最优化问题．

　　1957年美国数学家贝尔曼(R．Bellman，1920—1984)提出另一种最优化技术——动态规划．它把问题分为一串子问题，它与变分法及邦德里亚金极大原理有关，更适于用微分方程来表述，却应用于离散的组合问题．它在运筹学及控制理论中都有着广泛的应用．

　　在第二次世界大战前就开始研究的随机模型的运筹学理论有排队论和对策论．战后还有价值论、决策论、搜索论、模拟论等等．排队论的问题随着公用服务事业的发展而提出来，特别是售票窗口的设置及电话线路设计等问题．最早1907年约翰森(Jo-hannsen)及1909年厄朗(A．K．Erlang)开始研究特殊情形，至1953年肯达尔(D．G．Kendall，1918—)引进标准记号，并应用马尔科夫链理论，正式建立了系统的排队论．基弗(J．Kiefer， 1924—1981)及沃尔弗维兹(J．Wolfowitz，1910—1981)在1955年更建立了多窗口排队系统理论．